Nghiên cứu cây R+ 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

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