Nghiên cứu cây cho định tuyến phân cấp đảm bảo chất lượng dịch vụ với định tuyến đa đường đa truyền phát - Nguyễn Thành Long

Công nghệ thông tin & Cơ sở toán học cho tin học N. T. Long, N. Đ. Thủy, P. H. Hoàng, “Nghiên cứu cây R+ đa đường đa truyền phát.” 106 NGHIÊN CỨU CÂY CHO ĐỊNH TUYẾN PHÂN CẤP ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ VỚI ĐỊNH TUYẾN ĐA ĐƯỜNG ĐA TRUYỀN PHÁT Nguyễn Thành Long1*, Nguyễn Đức Thuỷ2, Phạm Huy Hoàng3* Tóm tắt: Hiện tại vấn đề định tuyến hướng dịch vụ là cấp thiết, trong đó, vấn đề phân cụm trong định tuyến được đặt ra nhưng thường được giải quyết chưa tổng quát. Thường các tác giả chỉ đặt ra số cố định các mức, như là hai hoặc ba mức phân cấp. Vì vậy, giải pháp đưa ra thường là khó phát triển khi mạng trở nên phức tạp. Bài báo đề cập đến mô hình định tuyến phân cụm phân cấp tổng quát và một số cách để tối ưu việc phân cụm và tìm đường đi trong hệ thống mạng. Tương tự như định tuyến hướng nội dung, trong định tuyến hướng dịch vụ thì thông tin sẽ được tổ chức theo lớp, hoặc theo dịch vụ. Tuy nhiên, định tuyến lớp trên dựa trên định tuyến từ các lớp dưới để đưa ra quyết định. Bài báo sẽ tập trung nghiên cứu và đánh giá: (i) Áp dụng cây R để quản lý cấu hình mạng theo mô hình phân cụm phân cấp với các bộ điều khiển mạnh tại các điểm nút quản lý nhóm; (ii) Tạo cây đa truyền phát từ nút quản lý nhóm đến các nút thành viên tăng hiệu suất truyền; (iii) Tạo các tuyến tối ưu sử dụng thuật toán ACO (tối ưu hóa đàn kiến); (iv) Sử dụng mạng neuron nhân tạo để tối ưu phân cụm mạng. Mạng neuron là một kỹ thuật mới thuộc ngành trí tuệ nhận tạo, được sử dụng nhiều trong khoa học để phân cụm và nhận dạng. Từ khoá: MANET, , Dịch vụ, Định tuyến, Đa đường, Băng thông, Cụm, tree, Multicast, QOS, Overhead, Mạng nơ ron. 1. MÔ HÌNH MẠNG PHÂN CỤM PHÂN CẤP Quản lý mạng phân cụm phân cấp trong mạng di động với các nút thường xuyên thay đổi vị trí, các thủ tục để chấp nhận nút vào mạng và các nhóm phải thực hiện nhanh và hiệu quả. Các nút phải trao đổi thông tin định kỳ, hoặc khi có yêu cầu. Để phân cụm ta phải đưa ra điều kiện, trong bài viết sử dụng mạng Neuron để đánh giá nút có thuộc cụm và chọn trưởng cụm. Các cụm được hình thành ban đầu là tại mức lá của cây R, với nút trưởng cụm là nút lá. Để tạo nên mô hình phân cấp, các nút lá được gom lại thành các nhóm cũng như cách trên để hình thành các cụm cấp trên, mỗi nhóm có trưởng cụm là các nút trong của cây. Cứ hình thành dần lên trên ta có nút gốc cây sẽ quản lý mạng lớp trên cùng. Để đánh giá liên kết và tuyến trong mạng ta sử dụng thuật toán tối ưu lập cụm đàn kiến (ACO). Mỗi liên kết và tuyến sẽ có 1 xác suất tồn tại được xác định. Xác suất này được tính toán theo ACO. Khi xác suất nhỏ thì khả năng tồn tại thấp, do vậy, phải tìm nhiều tuyến giữa mỗi cặp nút (nguồn, đích). Khi cần truyền từ 1 nút đến 1 tập các nút ta hình thành cây đa truyền phát giữa nút cần truyền và tập các nút đích từ tập các tuyến tìm được bằng ACO. Khi đó có thể truyền đồng thời trên các tuyến có đảm bảo chất lượng để tăng hiệu suất. Để quản lý mạng phân cụm phân cấp hiệu quả có nhiều cách các tác giả đã đề ra. Nhưng các giải pháp này còn chưa giải quyết triệt để vấn đề cập nhật mạng và tìm đường đi tối ưu. Bài báo đề nghị dùng cấu trúc cây R để quản lý mô hình mạng này. Cây R là cây cân bằng và có số nút trên mỗi nhánh con là khá ổn định. Ngoài ra, các thuật toán để tìm kiếm và hình thành cây khá dễ dàng và đã có sẵn. Thời gian tìm kiếm trên cây này gần như không tăng khi số mức của cây tăng dựa trên kết quả thực nghiệm của các bài báo trước đây. Tuy nhiên, cây R luôn duy trì tính ổn định nội tại, khi thêm bớt nút cây sẽ được điều chỉnh lại để giữ cân bằng. Việc thêm nút vào cây luôn được thực Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 107 hiện tại nút lá, nút lá là nút tại mức cuối cùng trong cây để quản lý toàn bộ các phần tử cần quản lý đó là các nút mạng hay các thiết bị viễn thông di động. Các phần tử cần quản lý là bất kỳ thứ gì trong thực tế như nút mạng, dữ liệu thông thường, quá trình các nút được chấp nhận vào mỗi cụm theo các thuật toán sẽ được trình bày trong phần tiếp theo Vậy dùng cây R để quản lý mạng ta sẽ có: nút lá quản lý các phần tử mạng, các nút lá tiếp tục lập cụm và chọn ra phần tử quản lý nhóm hình thành nhóm lớp trên. Hệ thống các nút trong quản lý phân cấp, phần tử mạng cấp trên quản lý các phần tử mạng cấp dưới. Cứ như vậy cho đến nút gốc quản lý toàn bộ cây. Tuy nhiên, nút gốc của nhiều cây R hợp tác lại để quản lý các hệ thống mạng lớn hơn. Trong bài viết không đưa ra khái niệm nút trìu tuợng mà sử dụng luôn các nút mạng làm nút quản lý điều này rất phù hợp với môi trường mạng phân cấp. Tuy vậy, chọn nút quản lý phải tuân theo các điều kiện nhất định và phải được tối ưu như sử dụng logic mờ, như đã đề cập trong bài viết [6]. Ví dụ: ban đầu chỉ có 1 nút thì nút sẽ có mọi chức năng, gốc, lá, thành phần, nút trong, quản lý nhóm. Vì là quản lý nhóm nên nút sẽ phát ra thông điệp cho phép tham gia nhóm. Khi có một nút nào đó đến gần cũng phát ra thông điệp HELLO, hai bên sẽ bắt tay và nút mới sẽ gia nhập mạng có 2 nút. Lúc này 2 nút đàm phám tìm ra trưởng nhóm mới. Do nút mới có thể đạt được tiêu chí làm trưởng nhóm hơn. Lúc đó trưởng nhóm mới sẽ phát ra thông điệp mời gia nhập, nút thành viên có kết nối với trưởng nhóm. Khi số thành viên của nhóm ban đầu đạt được ngưỡng quy định nhóm sẽ phân đôi. Số thành viên của mạng lúc này được tìm theo công thức: N= + +3 (1) và lá số phần tử của 2 nhóm con vừa hình thành. , đều thuộc khoảng [m, M] là số nút có thể trong mỗi nhóm. Các nút khi kết nạp dần vào 2 nhóm con khi đạt đến ngưỡng M sẽ lại được tách ra thành 2 nhóm. Do vậy, giá trị m phải thuộc khoảng [0, ]. Khi số phần tử trong nhóm bằng m-1, nhóm sẽ bị huỷ để thêm các nút của cụm vào cây theo thuật toán thêm nút. Cứ như vậy lên mức trên lá tiếp tục tạo các cụm của các nút quản lý nhóm, các nút quản lý nhóm có 2 liên kết: i) Liên kết đến các nút con cấp dưới, có nhiều liên kết và phải thường xuyên cập nhật trạng thái; ii) Một liên kết lên nút quản lý nhóm cấp trên nó. Do vậy, một nút trong hay nút lá chỉ cần quản lý nhiều nhất là: M+1 liên kết. Mỗi nút thành viên của nhóm mức lá chỉ lưu một liên kết lên nút lá. Có nghĩa là nút chỉ bị quản lý, không tham gia quản lý. Nút gốc chỉ quản lý tối đa M liên kết. Thuật toán mạng Neural cũng có thể dùng để luyện với dữ liệu ban đầu là các trưởng cụm để tìm ra các ma trận trọng số. Sau đó, các nút mạng sẽ được đưa vào cụm nào cho kết quả gần với trưởng cụm nhất. 2. PHÂN TÍCH CHI TIẾT CẤU TRÚC CÂY CHO QUẢN LÝ MẠNG Cây R là bộ gồm các thành phần: (M, m, R, {F}). M, m là cận trên và dưới của số thành viên của mỗi cụm. R là gốc cây, {F} là tập các hàm tạo cây, cập nhật, thêm, xoá nút, điều chỉnh. Cây có thể được định nghĩa định nghĩa đệ quy theo biểu thức: = ( ) ( ) ( ). (2) Một cách tự nhiên mạng sẽ có cấu trúc phân cấp theo nhiều mức như một cây phân cấp chức năng trong các hệ thống lớn. Như hình 1 cho thấy mỗi nút trong là gốc của một cây con của cây ban đầu. Tại mỗi mức có số nút con khá ổn định, giả sử tại độ cao h, số nút tại mức này là thuộc khoảng: Công nghệ thông tin & Cơ sở toán học cho tin học N. T. Long, N. Đ. Thủy, P. H. Hoàng, “Nghiên cứu cây R+ đa đường đa truyền phát.” 108 [ ] (3) Do vậy, với cây có độ cao H số nút mạng chịu sự quản lý của một nút quản trị mạng (CH) nào đó ở mức lá: [ ] (4) Ngược lại, khi biết số nút mạng là N bao gồm cả nút mạng được quản lý và các nút quản lý tại mọi cấp. Độ cao của cây sẽ thuộc khoảng: [ (N)-1  (N)-1] (5) Dễ thấy cây đa truyền phát mặc định được tạo ra để truyền thông tin điều khiển hay dữ liệu từ một nút quản lý đến các nút con rồi đến các nút lá và đến các nút mạng được quản lý. Trong cây các nút tại một mức nào đó thuộc một cụm thường có các thuộc tính chung với nút trưởng cụm CH. Sự hình thành cấu trúc phân cấp một cách tự nhiên của cây sẽ được trình bày trong phần tiếp theo. Nút CH thường phải có năng lượng lớn hoạt động liên tục và quản lý hoạt động trao đổi giữa các nút trong cụm và của cụm với mạng bên ngoài. Mạng của các nút quản lý mạng CH hình thành khung của mạng như mạng xương sống (backbone) tạm thời giúp quản lý trao đổi thông tin nhanh và hiệu quả. Ký hiệu mạng nút quản trị phân cấp theo biểu thức đệ quy: NETWORK({CH}) = (6) Như hình trên ta thấy, các CH mức trên quản lý các CH mức dưới, đồng thời nó lại thuộc sự quản lý của CH lớp trên tiếp theo. Theo quy định số CH được quản lý trong 1 cụm cũng phải thuộc khoảng [m, M]. Cứ tiến dần đến nút gốc của cây, số nút của 1 mức ít dần, đến gốc cây là nút có cấu hình thường là mạnh nhất, khả năng xử lý nhanh nhất, ít di chuyển so với tâm của mạng và gần tâm của cả mạng nhất. Nút gốc phải hoạt động bền bỉ và duy trì được trạng thái ổn định nhất. Tuy nhiên, nút nào là gốc sẽ phải được chọn lựa từ mức lá theo mô hình Bottom – Up sử dụng các thuật toán trí tuệ nhân tạo hoặc logic mờ. 3. PHÂN TÍCH CÁC THUẬN LỢI KHI SỬ DỤNG CÂY CHO ĐỊNH TUYẾN PHÂN CẤP Các thủ tục xây dựng và cập nhật cây đã được trình bày khá kỹ trong các bài viết trước đây của chúng tôi [1-2-6]. Cây sẽ được hình thành theo mô hình Bottom – Up, do vậy rất dễ kiểm soát và điều chỉnh. Trong bài viết này trình bày về chi phí điều khiển mạng phân cấp sử dụng cây . Như trên đã định nghĩa cấu trúc cây dạng đệ quy: (Root) = ( ) R+( ) R+( ) (7) Hình 1. Cây có cấu trúc 2 mức với số nút trong 1 cụm thuộc khoảng [2 .. 3]. Hình 2. Cây với mô hình quản trị phân cấp. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 109 Gốc của cây truyền thông điệp điều khiển xuống các nút con là các nút quản trị cấp dưới hoặc các nút mạng khi mạng mới được hình thành chỉ có một nút quản trị và 1 số nút con: , , , . Đến lượt mình các nút trưởng cụm cấp dưới Childi tiếp tục truyền thông điệp điều khiển các nút con trong cụm của nó quản lý. Dễ thấy toàn bộ các nút trong, các nút lá và nút gốc của cây đều là nút quản trị. Các nút không quản trị là các nút mạng chịu sự kiểm soát của một nút lá nào đó. Nút trong có hai vai trò (i) là nút quản trị, (ii) là nút chịu sự quản trị. Nút gốc chỉ có vai trò quản trị. Sự quản lý này tạo nên mô hình phân cụm phân cấp. Tương tự như truyền trong cây Multicast. Do vậy, chi phí truyền thông tin điều khiển từ nút gốc đến tận các nút mạng được quản lý là: Overhead(control) = (8) Ni là số nút con trung bình của mỗi cụm trong mỗi tầng của mạng. Ban đầu là là số con của nút gốc, mỗi con của nút gốc có trung bình là , Cho đến mức lá mỗi cụm có trung bình con. Giả sử mạng có n tầng phân cấp. Thông thường khi một nút khi được thêm vào mạng tại một nút quản trị mạng nào đó thì thông tin điều khiển sẽ phát sinh từ nút đó. Thông tin nút được thêm phải truyền đến gốc cây để đánh giá và thêm vào cây. Nút sẽ đánh giá sự phù hợp của nút trong nhánh con nào thì truyền thông tin điều khiển cho nút con đó. Đến nút con lại tiếp tục tính toán cho đến tận nút lá. Rồi nút mới sẽ được bổ sung vào nhóm con mức lá. Do vậy, chi phí điều khiển cũng khá nhỏ. Chi tiết việc này sẽ được trình bày trong phần sau. Tuy nhiên, do mạng có cấu trúc phân cấp nên các việc sẽ được thực hiện đồng thời nên trong mỗi mức gần như các nút sẽ xử lý đồng thời nên tốc độ sẽ nhanh. Ngoài ra do việc truyền Multicast [1] trên một cây R+ có số mức phân cấp thường không nhiều cho chọn khoảng [m, M] hợp lý, làm cho thông tin điều khiển hay dữ liệu sẽ được truyền rất nhanh đến các nút lá hay nút mạng được quản lý. Khá dễ đảm bảo băng thông và độ trễ. Tuy nhiên, do mạng dễ dàng có kết nối giữa các nút CH nên vẫn có thể tạo các cây multicast giữa các nút trong trực tiếp. 4. QUÁ TRÌNH HÌNH THÀNH MẠNG SỬ DỤNG CÂY 4.1. Tuyển chọn nút Như đã trình bày, cây R+ được hình thành từ quá trình tự nhiên. Xuất phát từ gốc, nút sẽ được kiểm tra điều kiện ràng buộc. Chẳng hạn như khoảng cách từ nút đến tâm của nhóm. Như vậy, ta phải chia khoảng không gian mạng làm nhiều vùng. Mỗi vùng tương ứng với 1 cụm, các vùng sẽ được đánh giá đến tâm mạng theo khoảng cách . Mỗi nút sẽ có toạ độ trong không gian nhận được từ vệ tinh GPS. Khoảng cách đến gốc của cây dễ dàng tính được. Từ đó, ta sẽ đánh giá để đưa nút vào nhóm con nào. Sau đó đến nhóm con cấp dưới lại tiếp tục đánh giá để đưa nút vào nhóm con nào như đánh giá trên. Cứ như vậy đến nút lá, bổ sung vào nhóm lá phù hợp nhất. Do khoảng cách gần thì năng lượng tiêu hao sẽ rất nhỏ làm cho hiệu suất mạng sẽ cao. Ngoài ra có thể tối ưu hơn cùng điều kiện về công suất phát thu. Gọi P(x, y, z) là toạ độ của gốc cây, ( , , ) là toạ độ của 1 nút bất kỳ, khoảng cách giữa hai nút được tính theo công thức:  = (9) Từ toạ độ GPS tính ra toạ độ trong không gian 3 chiều khá dễ dàng. Chỉ cần chọn 1 điểm làm gốc, có toạ độ O(0, 0, 0). Công nghệ thông tin & Cơ sở toán học cho tin học N. T. Long, N. Đ. Thủy, P. H. Hoàng, “Nghiên cứu cây R+ đa đường đa truyền phát.” 110 Quy định mức trên cùng một nhóm thì gốc hay CH là gốc toạ độ. Nếu cùng khoảng cách thì dùng phép chọn ngẫu nhiên (random). Việc chọn này rất phù hợp với các mạng ngang hàng như mạng các bộ cảm biến sensor. Đối với các mạng khác ta nên xét thêm các yếu tố liên quan rồi tối ưu theo logic mờ. Xây dựng hàm phù hợp Fitness: F( , , , ) = (10) Trong đó, Wi là trọng số tương ứng với Pi để đánh giá đúng tầm quan trọng của mỗi tham số. Pi được làm mờ rồi có giá trị trong khoảng [0 .. 1]. Cùng với điều kiện: = 1 (11) Do vậy, giá trị hàm F cũng có giá trị thuộc khoảng [0 .. 1]. Dùng đánh giá theo các chuyên gia, cùng các phép suy diễn thích hợp tìm ra cụm nào nút thuộc vào. Tối đa F=1 khi mỗi =1. Tiếp đó đến cụm cấp dưới lại áp dụng như cấp trên cho đến cụm cấp lá. Do tiến hành đồng thời nên cũng khá nhanh tìm ra mạng cơ sở để thêm nút. Chẳng hạn như khi hình thành cây từ đầu. Mỗi cấp tiến hành đồng thời sẽ giảm thời gian đáng kể. 4.2. Tuyển chọn trưởng cụm Trưởng cụm được chọn dựa trên các tiêu chí độ mạnh về khả năng xử lý, năng lượng dự trữ. Tất cả các yếu tố này được làm mờ và cũng như trên dùng lô gíc mờ để đánh giá theo suy diễn và tri thức của mạng nơ ron hay chuyên gia. Xây dựng mạng nơ ron đánh giá theo hàm chuẩn sẽ chọn đúng yêu cầu đề ra rất nhanh và dễ dàng. Cũng như lô gíc mờ xây dựng hàm phù hợp, mạng nơ ron xây dựng hàm kernel - hàm lõi để đánh giá theo các tiêu chí đưa ra. Thiết lập các tham số đánh giá trưởng cụm theo chuyên gia và các điều kiện mạng cụ thể. Xây dựng hàm lõi: ( , , , ) = + (12) Trong đó, W0 là trọng số điều chỉnh, Wi là trọng số tương ứng với các tham số Pi. Các tham số được đo hay nhận được từ các thông điệp phát hiện cấu hình mạng. Tất cả các tham số của các nút sẽ được tập hợp tính toán tại nút trưởng cụm, nút nào cho kết quả hàm F lớn nhất sẽ được chọn là gốc cây. Các cụm cấp dưới được chọn theo các khoảng giá trị của kết quả của hàm. được điều chỉnh tuỳ thuộc tình trạng mạng cụ thể để khoảng chọn giá trị hàm lớn. Ngoài ra, cũng có thể dùng thuật toán GIEN để tối ưu việc chọn trưởng cụm, trong thuật toán GIEN cũng phải thiết lập hàm phù hợp, trên cơ sở các tham số cấu hình. Khi tìm ra mạng các trưởng cụm theo mô hình phân cấp như đã phân tích gọi là 1 solution của GIEN. Tiến hành nhiều lần để có nhiều solution gọi là một quần thể population trong GIEN. Áp dụng GIEN cho các solution này sẽ tìm ra mạng các trưởng cụm tối ưu. 5. SỬ DỤNG MẠNG NEURON ĐỂ PHÂN CỤM MẠNG 5.1. Giới thiệu Mạng nơ ron nhân tạo (ANN) được sử dụng nhiều trong khoa học để giải quyết các bài toán khoa học kỹ thuật có độ phức tạp cao, với các điều kiện đầu vào phức tạp. Mạng neuron có nhiều dạng, mỗi dạng thích hợp với các loại bài toán khác nhau. Trong đó, mạng có điều chỉnh trọng số bằng thuật toán lan truyền ngược để điều chỉnh trọng số được sử dụng rộng rãi để nhận dạng và phân loại dữ liệu. Một số tính chất quan trọng của ANN:  Kết hợp với các đầu vào thuộc vector đầu vào là vector trọng số. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 111  Mỗi neuron có hàm chuyển hay hàm kích hoạt để tạo ra kết quả.  Các vector trọng số được sinh ra ngẫu nhiên ban đầu, sau đó được điều chỉnh sau mỗi bước huấn luyện. 5.2. Cấu tạo mạng Neuron Mạng ANN có cấu trúc nhiều lớp, trong đó có 1 lớp vào, nhiều lớp ẩn và 1 lớp ra: ANN = (I, {H}, O) (13) Mục tiêu của mạng Neuron là tìm ma trận trọng số cho các lớp để cho với mỗi mẫu dữ liệu vào cho trước sẽ cho ra kết quả mong muốn: ANN( ) = (14) Trong đó: ( , ) là 1 cặp vector vào và kết quả mong muốn. Lớp vào I nhận dữ liệu là 1 vector, mỗi thành phần của vector được nhân với 1 trọng số, ban đầu được chọn ngẫu nhiên. Lấy tổng của tất cả các thành phần của vector ra của lớp hiện tại nhân với trọng số tương ứng là đầu vào cho lớp tiếp theo: = (15) Sau đó tín hiệu đầu vào được xử lý bởi hàm chuyển hay kích hoạt để cho ra kết quả: = Transfer_Function( ) (16) Để quá trình cập nhật trọng số nhanh ta chọn hàm chuyển là hàm có thể lấy đạo hàm được Sau khi tìm được các trưởng cụm theo như đã phân tích ở trên, ta sử dụng các thông số của trưởng cụm để luyện 1 mạng Neural tương ứng. Sau khi luyện thu được ma trận trọng số tương ứng. 5.3. Huấn luyện mạng Neuron Tại lớp ra kết quả của mạng được so sánh với kết quả mong muốn để cập nhật ma trận trọng số của các lớp trước gồm các lớp ẩn và vào. Lỗi được tính theo công thức (OVE - output value error) Ký hiệu, là sai lệch của kết quả mong ước và kết quả thực. [OVE] = [Desired Output Value] – [Calculated Output Result] (17) Tại lớp cuối cùng ta có: = - (18) Sau đó, tại các lớp tiếp theo theo hướng về đầu, tính gia số theo công thức: = (19) Trong đó: là gia số của kết quả của neuron k thuộc lớp i+1, là trọng số thứ k của neuron thứ j thuộc lớp i. Tiếp theo là tính trọng số mới theo trọng số mới và gia số: = + * * (20) Trong đó, n là số neuron của lớp i+1, là trọng số thứ k của neuron j của lớp thứ i. là tốc độ học của neuron, là gia số của neuron thứ k của lớp i+1. là kết quả đầu ra của neuron. Ta cập nhật vector trọng số cho bias của mỗi lớp theo công thức: Công nghệ thông tin & Cơ sở toán học cho tin học N. T. Long, N. Đ. Thủy, P. H. Hoàng, “Nghiên cứu cây R+ đa đường đa truyền phát.” 112 = + * * (21) Trong đó, là bias của lớp I, n là số neuron của lớp, là số gia của neuron thứ k của lớp i, là tốc độ học của neuron k trong lớp n. 5.4. Ứng dụng cho phân cụm Hình thành mạng Neuron cho để chọn các trưởng cụm, với các tiêu chí đầu vào là 1 vector các tham số dùng để chọn trưởng cụm. Mỗi mạng này sẽ được huấn luyện theo phân tích trên. Với mỗi nút để kiểm tra có thỏa mãn là trưởng cụm không ta phải thực hiện như sau:  Đo các thông số của nút, đưa vector thông số làm đầu vào cho các mạng neuron đã huấn luyện.  Mạng neuron nào cho kết quả gấn nhất với vector đầu ra của mạng sẽ được chấp nhận là trưởng cụm của cụm đó.  Sai số của vector đầu ra mong muốn và vector kết quả được tính bằng khoảng cách Euclid giữa 2 vector.  Sau đó trong quá trình hoạt động của mạng, định kỳ đo các thông số này của các nút trong cụm, nút nào cho ra kết quả sau lệch ít nhất so với phần đầu ra của mẫu sẽ được chọn làm trưởng cụm. Sau khi đã có các trưởng cụm rồi, đánh giá các nút còn lại để xác định thuộc cụm nào theo cách sau đây: Với mỗi nút mạng còn lại đưa thông tin vào mạng Neuron tương ứng với mỗi trưởng cụm, nút sẽ thuộc vào cụm cho kết quả gần trưởng cụm nhất của cụm. 6. TỐI ƯU MẠNG PHÂN CẤP DÙNG ANT COLONY OPTIMIZATION Một số đặc tính của thuật toán ACO:  Hoạt động phân tán: sử dụng tham số pheromone có thay đổi theo thời gian để đánh giá liên kết. Mặc định tham số này sẽ giảm theo thời gian khi các nút 2 đầu liên kết không nhận được gói tin của nhau.  Không có vòng lặp: Mỗi nút đăng ký 1 số trật tự duy nhất để cho cặp gói tìm tuyến Ant_Route_Request và Ant_Route_Reply.  Hoạt động theo yêu cầu: On demand protocol, các tuyến chỉ được thiết lập khi có yêu cầu. Các tuyến được hình thành bởi việc đánh giá thông số pheromone.  Hoạt động có nghỉ khi đạt được yêu cầu: Các nút sẽ chuyển sang chế độ nghỉ (sleep) khi thông số pheromone đạt được 1 giá trị ngưỡng theo quy định.  Có tính cục bộ: Bảng định tuyến và các thong tin thống kê của mỗi nút là cục bộ.  Đa đường: Mỗi nút đều duy trì nhiều tuyến đến mỗi đích.  Giảm được chi phí thông tin điều khiển: Bởi vì mỗi nút không trao đổi thông tin bảng định tuyến với các nút khác trên mạng. Do mạng di động nên các yếu tố chọn để tính toán đều có xác suất đúng do vậy gán cho các kết nối rồi đến các tuyến, cụm đều có xác suất tồn tại. Xác suất này sẽ được các trưởng cụm tính toán ngầm phía dưới. Nếu xác suất chọn không đủ yêu cầu, cụm sẽ tự động được hình thành lại, dựa trên thông tin nhận được từ các thông điệp HELLO. Trong định tuyến proactive, các thông điệp HELLO được trao đổi để phát hiện mạng nên dùng các thông điệp này để đánh giá xác suất là hợp lý. Tiến hành đo tần suất nhận các gói tin này trong các khoảng thời gian xác định, rồi đánh giá xác suất tồn tại các kết nối. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 113 7. ĐÁNH GIÁ VÀ HƯỚNG PHÁT TRIỂN Trên cơ sở phân tích như trên cùng với các mô phỏng áp dụng cây trong phân cụm dữ liệu, như để quản lý các logic vị từ trong quản lý các thông điệp trong mạng hướng nội dung hay hướng dịch vụ cho thấy cây rất phù hợp quản lý dữ liệu lớn có cấu trúc [6]. Tốc độ thực hiện gần như không phụ thuộc kích thước dữ liệu mà chỉ phụ thuộc vào các điều kiện chọn hàm đánh giá. Trừ trường hợp hình thành lại toàn bộ mạng. Tuy nhiên, tốc độ vẫn tăng đáng kể khi các tiến trình được thực hiện song song trên các hệ thống máy chủ lớn như Main frame. Do vậy, tốc độ được đánh giá theo hàm logarit của dữ liệu. Ngoài ra còn có thể phát triển mạng theo hướng kết nối các cây theo kiểu nối tiếp hoặc hình sao để tránh tính ràng buộc của cây. Hay có thể hình thành các cây Multicast từ các trưởng cụm từ các thông điệp overhear giữa các nút có cường độ thu phát mạnh. Theo cách này tận dụng càng hiệu quả băng thông và năng lực của nút. Trong tương lai gần nhóm nghiên cứu sẽ nghiên các mô hình mạng kết hợp các mô hình này để đưa ra kết quả tốt hơn. TÀI LIỆU THAM KHẢO [1]. Nguyen Thanh Long, Nguyen Duc Thuy, Pham Huy Hoang, “Research on Applying Hierachical Clustered Based Routing Technique Using Artificial Intelligence Algorithms for Quality of Service of Service Based Routing, Internet of Things and Cloud Computing”. Special Issue: Quality of Service of Service Based Routing. Vol. 3, No. 6-1, 2015, pp. 1-8. doi: 10.11648/j.iotcc.s.2015030601.11. [2]. Nguyen Thanh Long, Nguyen Duc Thuy, Pham Huy Hoang, “Research on Innovating and Applying Evolutionary Algorithms Based Hierarchical Clustering and Multiple Paths Routing for Guaranteed Quality of Service on Service Based Routing, Internet of Things and Cloud Computing”. Special Issue:Quality of Service of Service Based Routing. Vol. 3, No. 6-1, 2015, pp. 9-15. doi: 10.11648/j.iotcc.s.2015030601.12. [3]. Kartheek Srungaram, Dr. MHM Krishna Prasad, “Enhanced cluster based routing protocol for MANETS”. Department of Information Technology, JNTUK-UCEV, Vizianagaram, A.P, India. [4]. Candida Ferreira, Departamento de Ciências Agrárias, “Gene Expression Programming: A New Adaptive Algorithm for Solving Problems”, Universidade dos Açores, 9701-851 Terra-Chã, Angra do Heroísmo, Portugal [5]. Bibhash Roy, “Ant Colony based Routing for Mobile Ad-Hoc Networks towards Improved Quality of Services”. Tripura Institute of Technology, Tripura, India. [6]. Nguyen Thanh Long, Nguyen Duc Thuy, Pham Huy Hoang, “Innovating R Tree to Create Summary Filter for Message Forwarding Technique in Service-Based Routing”, Springer, ISBN: 978-3-642-41773-3, LNICST 121, p. 178, 2013. [7]. Long Thanh Nguyen, Tam Nguyen The, Chien Tran, Thuy Nguyen Duc. “Applying Multiple Paths Routing Technique Based on Fuzzy Logic and Genetic Algorithm for Routing Messages in Service - Oriented Routing”: Research on Innovating, Journal of Scalable Information Systems EAI. [8]. Kui-Ting Chen, Ke Fan, Yijun Dai and Takaaki Baba, “A Particle Swarm Optimization with Adaptive Multi-Swarm Strategy for Capacitated Vehicle Routing Problem”.Research Center and Graduate School of Information, Production and Systems, Waseda University, 2-7 Hibikino, Kitakyushu, Fukuoka, Japan. Công nghệ thông tin & Cơ sở toán học cho tin học N. T. Long, N. Đ. Thủy, P. H. Hoàng, “Nghiên cứu cây R+ đa đường đa truyền phát.” 114 [9]. Anjum A. Mohammed, “Optimal Routing In Ad-Hoc Network Using Genetic Algorithm”. Information Technology Department, College of Computer and Information Sciences, King Saud University, KSA, [10]. Sajid Hussain and Abdul W. Matin, Jodrey, “Hierarchical Cluster-based Routing in Wireless Sensor Networks”. School of Computer Science, Acadia University Wolfville, Nova Scotia, Canada, [11]. Bibhash Roy, “Ant Colony based Routing for Mobile Ad-Hoc Networks towards Improved Quality of Services”. Tripura Institute of Technology, Narsingarh, Tripura, India ABSTRACT INNOVATING TREE AND MULTICAST ROUTING TO MAKE QoS MULTIPLE PATHS FOR SERVICE BASED ROUTING As the content based routing, in the service based routing protocol, the information can be classified by categories or service classes. However the upper routing must be based on lower layers to make routing decisions. The paper aims at purpose to increate QOS of routing by hierarchical clustering routing by using tree in addition with some advanced techniques multicast routing, multiple paths, use GENETIC / BEE / ACO to optimize routes to transmit data. In tree model, the network’s nodes are managed by Bottom- Up model from leaf nodes to root of the tree. The paper analyzes and assesses: (i) Setup hierarchical clustering network by using R tree structure; (ii) Making multicast tree from some cluster heads for fast routing; (iii) Making optimized route by Ant Colony Optimization; (iv) The paper also mentions the Artificial Neural Network (ANN) to cluster network. ANN is commonly used in data clustering and image recognization. Keywords: MANET, , Service, Routing, Multi-Paths, Bandwidth, Cluster, Tree, Multicast, QOS, Overhead, Ant, ACO, ANN, Neuron, Network. Nhận bài ngày 28 tháng 10 năm 2016 Hoàn thiện ngày 01 tháng 11 năm 2016 Chấp nhận đăng ngày 14 tháng 12 năm 2016 Địa chỉ: 1Trung tâm Công nghệ thông tin, Viễn Thông Hà Nội; *Email: Ntlptpm1@yahoo.com; 2Viện kỹ thuật Bưu điện, Học Viện Bưu chính Viễn thông; 3Viện Công nghệ thông tin, Đại học Bách khoa Hà Nội. *Email: Hoangph@soict.hut.edu.vn.