Đánh giá hiệu năng định tuyến đa phát trên duy trì một cách tối ưu cây khung trong mạng Manet

Đõ Huy Khôi và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 116 (02): 29 - 33<br /> <br /> ĐÁNH GIÁ HIỆU NĂNG ĐỊNH TUYẾN ĐA PHÁT DỰA TRÊN DUY TRÌ<br /> MỘT CÁCH TỐI ƢU CÂY KHUNG TRONG MẠNG MANET<br /> Đỗ Huy Khôi, Nguyễn Thị Thu Hằng*, Dƣơng Thúy Hƣờng<br /> Trường Đại học Công nghệ thông tin và truyền thông – ĐH Thái Nguyên<br /> <br /> TÓM TẮT<br /> Vấn đề định tuyến đa phát và các giao thức định tuyến đa phát trong mạng MANET là một trong<br /> những hƣớng nghiên cứu nhận đƣợc nhiều sự quan tâm. Có nhiều hƣớng tiếp cận khác nhau trong<br /> đó vấn đề định tuyến theo nguyên tắc xây dựng cây khung và tốt nhất là các cây khung có trọng số<br /> tối thiểu. Việc áp dụng giải thuật xây dựng cây khung có trọng số tối thiểu trong mạng tĩnh vào<br /> một mạng có hình trạng mạng động nhƣ MANET là khó thực hiện nên việc nghiên cứu giải thuật<br /> xây dựng và bảo trì tối ƣu cây khung đa phát trong mạng MANET – giải thuật STM (Spanning<br /> Tree for Multicasting)- là cần thiết. Bộ công cụ mô phỏng mạng NS-2 [1,9] đƣợc sử dụng để quan<br /> sát kết quả mô phỏng, đánh giá giải thuật xây dựng và bảo trì tối ƣu cây khung đa phát trong mạng<br /> MANET so với các giao thức đa phát khác nhƣ MAODV và PUMA với số lƣợng nút lớn để đánh<br /> giá chính xác hơn về hiệu năng mạng theo các tham số nhƣ thông lƣợng, độ trễ, chi phí phụ tải,…<br /> để thể hiện sự tối ƣu của giải thuật STM nhƣ chi phí định tuyến thấp hơn, hiệu năng tốt hơn so với<br /> phƣơng pháp thông thƣờng.<br /> Từ khóa: Mạng tự hợp di động, giao thức định tuyến đa phát theo yêu cầu dựa theo vector<br /> khoảng cách, giao thức cho đa phát hợp nhất dựa vào các bản tin thông báo, cây khung đa phát<br /> <br /> MỞ ĐẦU*<br /> Mạng không dây đặc biệt gọi là mạng tự hợp<br /> di động (MANET – Mobile Wireless Adhoc<br /> Network) là mạng động tạm thời đƣợc thiết<br /> lập bằng một tập hợp các nút mạng không dây<br /> tự trị mà không cần đến bất kỳ sự hỗ trợ về cơ<br /> sở hạ tầng mạng cố định cũng nhƣ hỗ trợ về<br /> quản lý tập trung.<br /> Trong mạng máy tính, dữ liệu có thể đƣợc<br /> truyền phát bằng ba cách khác nhau: đơn<br /> phát, phát tỏa và đa phát. Trong truyền thông<br /> đa phát, định tuyến là bài toán quan trọng, có<br /> cách thức thực thi khó khăn và tốn chi phí<br /> nhiều hơn so với phát tràn (broadcast), do<br /> phải có cơ chế điều khiển để không truyền dữ<br /> liệu tràn lan gây lãng phí băng thông mạng,<br /> mà chỉ truyền cho một số thành viên thuộc<br /> cùng nhóm truyền thông.<br /> Có nhiều phƣơng pháp đƣợc đƣa ra để xây<br /> dựng và bảo trì tối ƣu cây khung đa phát trong<br /> đó bài toán xây dựng đƣờng đi nối tất cả các nút<br /> trong nhóm đa phát sao cho tổng chi phí nhỏ<br /> nhất đang thu hút đƣợc nhiều sự quan tâm.<br /> *<br /> <br /> Tel: 01699 831287, Email: ntthang@ictu.edu.vn<br /> <br /> Trong bài báo này để đánh giá đƣợc sự tối ƣu<br /> của giải thuật tác giả sử dụng bộ công cụ mô<br /> phỏng mạng NS-2 để mô phỏng, đánh giá, so<br /> sánh các giải thuật đa phát STM [1],<br /> MOADV [4,8], PUMA [5] với số lƣợng nút<br /> lớn, hình trạng mạng động.<br /> THUẬT TOÁN XÂY DỰNG VÀ BẢO TRÌ<br /> TỐI ƢU CÂY KHUNG ĐA PHÁT TRONG<br /> MẠNG MANET<br /> Với đặc điểm của mạng MANET là sự khan<br /> hiếm của băng thông, thời gian tồn tại ngắn<br /> của các nút do hạn chế về năng lƣợng và cấu<br /> trúc liên kết động của các nút nên việc xây<br /> dựng giao thức định tuyến trong mạng<br /> MANET là một thách thức lớn.<br /> Một giao thức định tuyến có hiệu quả cho<br /> mạng MANET, đó là áp dụng giải thuật phân<br /> tán cho cây khung có trọng số tối thiểu nghĩa<br /> là coi mạng phân tán nhƣ là một đồ thị vô<br /> hƣớng có trọng số các cạnh là khác nhau.<br /> Giải thuật bảo trì cây khung trong mạng tĩnh<br /> Xét hệ phân tán là một đồ thị vô hƣớng, với<br /> tập các nút biểu diễn là các bộ xử lý của mạng<br /> và tập cạnh biểu diễn các liên kết truyền<br /> thông giữa các bộ xử lý. Mỗi nút trong mạng<br /> 29<br /> <br /> Đõ Huy Khôi và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> có một định danh phân biệt. Mỗi liên kết<br /> trong mạng có một trọng số nhất định, giả sử<br /> trọng số của liên kết là khác nhau.<br /> Trong quá trình xây dựng cây khung thủ tục<br /> quan trọng nhất là kết hợp mảnh, mỗi nút ban<br /> đầu đƣợc xem là một mảnh, các mảnh này sẽ<br /> dẫn kết hợp với nhau tạo thành một mảnh lớn<br /> hơn dựa trên việc tìm kiếm các liên kết ngoài<br /> có trọng số tối thiểu, việc kết hợp dần các<br /> mảnh tạo thành một cây khung hoàn chỉnh có<br /> trọng số nhỏ nhất.<br /> Giải thuật bảo trì cây khung trong mạng<br /> động (OMST)<br /> Xây dựng cây khung trong mạng động<br /> (OMST) [1] gặp nhiều khó khăn hơn trong<br /> mạng tĩnh vì hình trạng mạng thay đổi liên<br /> tục nên vấn đề cập nhật thông tin để bảo trì<br /> cây khung là cần thiết nhƣng tốn chi phí lớn<br /> hơn rất nhiều.<br /> Để khắc phục nhƣợc điểm này, giải thuật xây<br /> dựng và bảo trì cây khung trong mạng động<br /> đã đƣợc đề xuất, để tận dụng những kết quả<br /> xây dựng cây khung đã đạt đƣợc, mỗi khi có<br /> sự thay đổi trong mạng, các nút chỉ cần đáp<br /> ứng lại bằng cách thay đổi một số trạng thái<br /> của mình cho phù hợp, không thay đổi tất cả<br /> cây khung.<br /> Để lƣu trữ thông tin về cây khung, giải thuật<br /> bảo trì cây khung trong mạng động đƣa ra<br /> một cấu trúc dữ liệu đặc biệt để lƣu trữ trên<br /> mỗi nút, sử dụng để khôi phục lại cây khung<br /> trong trƣờng hợp có những thay đổi trong<br /> mạng, gọi là “rừng ảo” và “cây ảo” [1].<br /> Mỗi nút trong hệ thống sẽ đƣợc lƣu một<br /> “rừng ảo” trong bộ nhớ cục bộ, đó là cơ sở để<br /> các nút tìm kiếm thông tin về liên kết ngoài<br /> có trọng số tối thiểu để kết hợp các mảnh lại<br /> với nhau. Nhờ lấy đƣợc thông tin trong “rừng<br /> ảo” ngay tại chính nút hiện tại nên nó giảm độ<br /> phức tạp trong quá trình kết hợp mảnh.<br /> Hai thủ tục quan trọng nhất trong giải thuật,<br /> liên quan đến cấu trúc dữ liệu là thủ tục<br /> UPDATE và FIND. Ngoài ra trong giải thuật<br /> OMST còn một số thủ tục khác tƣơng tự giải<br /> 30<br /> <br /> 116 (02): 29 - 33<br /> <br /> thuật GHS-83 [3] để xây dựng cây khung tối<br /> thiểu nhƣ: thủ tục chuyển gốc – Change root,<br /> kết hợp mảnh – Merge, thủ tục xử lý khi cấu<br /> hình mạng thay đổi, thủ tục xử lý khi cấu hình<br /> mạng thay đổi trong quá trình kết hợp mảnh.<br /> Xây dựng và bảo trì tối ƣu cây khung đa<br /> phát trong mạng MANET (STM)<br /> Cây khung trong mạng đa phát đƣợc định<br /> nghĩa là một đồ thị vô hƣớng, cây khung con<br /> bao trùm một tập con các nút của đồ thị gọi là<br /> cây khung không đầy đủ hoặc cây khung đa<br /> phát (Spanning Tree for Multicast - STM).<br /> Lúc đó mỗi nút thuộc vào cây khung đa phát<br /> gọi là nút đa phát.<br /> Với giải thuật STM không chỉ bao gồm quá<br /> trình kết hợp mảnh thông qua liên kết đa phát<br /> mà còn có cả quá trình mở rộng mảnh theo<br /> đƣờng dẫn nhỏ nhất. Sau khi kết hợp, quá<br /> trình mở rộng tiếp tục đƣợc lặp lại. Tại mỗi<br /> lần lặp, mảnh STM sẽ chọn ra một nút ngoài<br /> tối thiểu để kết hợp.<br /> Mỗi nút trong mạng sẽ lƣu trữ danh sách các<br /> nút hàng xóm cùng với các liên kết đến các<br /> nút đó. Có 3 loại liên kết: Mesh_Link,<br /> Tree_Link, Data_Link [1].<br /> Giải thuật STM có các bƣớc thực hiện một số<br /> thủ tục để cập nhật các liên kết ngoài tốt nhất<br /> và thủ tục kết hợp để thiết lập liên kết mới và<br /> mở rộng mạng.<br /> ĐÁNH GIÁ HIỆU NĂNG CỦA MỘT SỐ<br /> GIAO THỨC ĐỊNH TUYẾN MẠNG MANET<br /> Tổng quan<br /> Môi trƣờng sử dụng để đánh giá hiệu năng các<br /> giao thức trên là công cụ NS-2 [2], phiên bản<br /> allinone 2.34, chạy trên hệ điều hành UNIX.<br /> Sử dụng NS2 để thực hiện đánh giá hiệu năng<br /> của giao thức STM và so sánh kết quả đánh<br /> giá với hiệu năng của các giao thức định<br /> tuyến đa phát khác nhƣ PUMA và MAODV.<br /> Để thực hiện phân tích các kết quả mô phỏng<br /> đồng thời đánh giá đƣợc hiệu năng của các<br /> giao thức STM, MAODV, PUMA cần cấu<br /> hình nhƣ các thông số đƣợc chỉ rõ ở hình 1.<br /> <br /> Đõ Huy Khôi và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 116 (02): 29 - 33<br /> <br /> tổng chi phí thông điệp vẫn giữ ở mức thấp<br /> đáp ứng cho mỗi thay đổi hình trạng mạng.<br /> - Đánh giá tỉ lệ phụ tải theo số nút tham gia<br /> <br /> Hình 1: Các tham số mô phỏng<br /> <br /> Bài báo này sẽ thực hiện cài đặt mô phỏng<br /> một mạng gồm là 50 nút và tiến hành phân<br /> tích đánh giá hiệu năng của các giao thức<br /> mạng bằng cách so sánh kết quả dựa trên một<br /> số độ đo hiệu năng nhƣ: tỷ lệ phụ tải, thông<br /> lƣợng trung bình, độ trễ trung bình.<br /> Kết quả mô phỏng:<br /> <br /> Hình 2: Cây khung sau khi kết thúc mô phỏng<br /> giao thức STM<br /> <br /> Kết quả đánh giá và nhận xét<br /> <br /> Hình 4. Biểu đồ tỷ lệ phụ tải theo số nút tham gia<br /> <br /> Biểu đồ tỷ lệ phụ tải theo số nút tham gia trên<br /> hình 4 cho thấy STM có chi phí điều khiển<br /> biến động nhiều hơn vì khi có nhiều nút tham<br /> gia mà hình trạng thay đổi liên tục, nên STM<br /> chƣa kịp đáp ứng xong, hoặc vừa kịp đáp ứng<br /> thì mạng lại thay đổi hình trạng nên số lƣợng<br /> gói tin thông báo tăng lên để xử lý các tình<br /> huống. Giao thức PUMA có sự ổn định hơn<br /> do PUMA là giao thức dựa theo lƣới nên có<br /> nhiều đƣờng đi khác nhau giữa các nút trong<br /> mạng, do đó mạng duy trì trạng thái kết nối liên<br /> tục, dù có một số liên kết bị đứt gãy, vì vậy chi<br /> phí thông điệp trung bình cao hơn STM.<br /> Đánh giá thông lƣợng trung bình<br /> - Đánh giá hiệu năng theo số nút phát<br /> <br /> Đánh giá tỉ lệ phụ tải<br /> - Đánh giá tỉ lệ phụ tải theo thời gian<br /> <br /> Hình 5: Biểu đồ biểu diễn tỷ lệ thông lượng trung<br /> bình theo số nút phát<br /> Hình 3. Biểu đồ tỷ lệ phụ tải theo thời gian<br /> <br /> Biểu đồ hình 3 cho thấy STM có tỷ lệ phụ tải<br /> thấp hơn so với PUMA và MAODV. Biểu đồ<br /> thể hiện sự tối ƣu khi thay đổi về thời gian thì<br /> <br /> Trên biểu đồ hình 5 có thể nhận thấy cả ba<br /> giao thức đều có thông lƣợng trung bình tăng<br /> lên theo số nút nguồn. Trong đó, STM có<br /> thông lƣợng trung bình cao hơn. Do STM và<br /> MAODV quản lý theo cây nên gói tin sẽ đi<br /> 31<br /> <br /> Đõ Huy Khôi và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 116 (02): 29 - 33<br /> <br /> theo các nhánh để đến đích, số lƣợng gói tin<br /> bị xung đột nhỏ và phải truyền lại thấp hơn,<br /> thông lƣợng cao hơn. Còn MAODV do quản<br /> lý theo lƣới, khi truyền theo broadcast gói tin<br /> sẽ truyền đi tất cả các liên kết trên mạng nên<br /> số lƣợng gói tin rất lớn tỷ lệ xung đột và phải<br /> truyền lại cao nên thông lƣợng của nó giảm<br /> hơn so với hai giao thức trên.<br /> - Đánh giá hiệu năng so với số nút tham gia<br /> Hình 8: Biểu đồ biểu diễn độ trễ<br /> theo số nút tham gia<br /> <br /> Hình 6: Biểu đồ biểu diễn tỷ lệ thông lượng trung<br /> bình theo số nút tham gia<br /> <br /> Trong hai biểu đồ hình 6 ta thấy tỉ lệ thông<br /> lƣợng trung bình của MAODV đạt cao hơn so<br /> với STM và PUMA. Điều này chứng tỏ ƣu<br /> thế của MAODN quản lý theo lƣới trong<br /> trƣờng hợp có nhiều nút tham gia và hình<br /> trạng mạng thay đổi lớn, nó sẽ đáp ứng nhanh<br /> hơn trong trƣờng hợp liên kết bị đứt và số<br /> lƣợng gói tin lớn có thế đi theo nhiều đƣờng,<br /> điều này tốt hơn hẳn so với hai giao thức<br /> MAODV và STM quản lý theo cây.<br /> Đánh giá độ trễ trung bình truyền thông<br /> - Độ trễ trung bình theo thời gian, số nút<br /> phát, số nút tham gia<br /> <br /> Hình 7: Biểu đồ biểu diễn độ trễ theo số nút phát<br /> <br /> 32<br /> <br /> Trong hai đồ thị thể hiện trên hình 7 và hình 8<br /> cho thấy MAODV có độ trễ cao hơn đáng kể<br /> so với STM và PUMA. Nhƣ vậy, khi số<br /> lƣợng nút tham gia vào mạng lớn thì giao<br /> thức STM và PUMA tốt hơn so với MAODV<br /> khi đánh giá theo các tiêu chí về độ trễ.<br /> KẾT LUẬN<br /> Với các kết quả đạt đƣợc, STM chứng minh<br /> rằng một giao thức dựa theo cây cũng có thể<br /> đạt đƣợc tỉ lệ truyền và độ trễ tốt tƣơng đƣơng<br /> với các giao thức dựa theo lƣới, nếu giao thức<br /> có thể đáp ứng đƣợc sự thay đổi mạng kịp<br /> thời với tổng chi phí thông điệp là nhỏ nhất,<br /> dẫn đến tổng chi phí thời gian cũng đƣợc<br /> giảm thiểu. STM sử dụng phù hợp với các<br /> mạng động ít thay đổi hình trạng mạng và có<br /> số lƣợng thành viên khá lớn.<br /> TÀI LIỆU THAM KHẢO<br /> 1. Nguyễn Trung Hải (2010), Định tuyến đa phát<br /> dựa trên bảo trì tối ưu cây khung trong mạng tự<br /> hợp di động, Luận Văn Thạc sĩ, Trƣờng Đại học<br /> Công nghệ, Đại học Quốc gia Hà Nội.<br /> 2. Nguyễn Đình Việt (2008), Bài giảng đánh giá<br /> hiệu nặng mạng máy tính, Trƣờng Đại học Công<br /> nghệ, Đại học Quốc gia Hà Nội.<br /> 3. Gallagher, Humblet, and Spira, (Jan. 1983). A<br /> Distributed Algorithm for Minimum-Weight<br /> Spanning Trees, ACM Transactions on<br /> Programming Languages and Systems 5.<br /> 4. E. Royer and C. Perkins, (August 1999) “Multicast<br /> operation of the ad hoc on-demand distance vector<br /> routing protocol,” in Proceedings of Mobicom.<br /> 5. Ravindra Vaishampayan, Efficient and Robust<br /> Multicast Routing in Mobile Ad hoc Networks,<br /> University of California, March 2006.<br /> 6. Baruch Awerbach, Israel Cidon, Shay Kutten,<br /> (2008). Optimal Maintenance of a Spanning Tree,<br /> January 13.<br /> <br /> Đõ Huy Khôi và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 7. Shuhui Yang and Jie Wu, New Technologies of<br /> Multicasting<br /> <br /> in<br /> <br /> MANET,<br /> <br /> Florida<br /> <br /> Atlantic<br /> <br /> University, Boca Raton.<br /> <br /> 116 (02): 29 - 33<br /> <br /> 8. Yufang Zhu, (2002)Pro-Active Connection<br /> Maintenance In Aodv And Maodv.<br /> 9.<br /> The<br /> Network<br /> Simulator<br /> ns-2:<br /> http://www.isi.edu/nsnam/ns/<br /> <br /> SUMMARY<br /> EVALUATION OF MULTICAST ROUTING PERFORMANCE BASED<br /> ON OPTIMAL MAINTENANCE OF A SPANNING TREE IN MANET<br /> Do Huy Khoi, Nguyen Thi Thu Hang*, Duong Thuy Huong<br /> College of Information and Communication Technology - TNU<br /> <br /> The multicast routing and multicast routing protocol in MANET is one of the most direction<br /> researches received much attention. There are many different approaches to routing, however the<br /> principles to building spanning tree and Minimum-Weight Spanning Trees happens to be the best<br /> choice. Applying Minimum-Weight Spanning Trees algorithm in static network into a dynamic<br /> network topologies such as MANET is difficult to perform, so a researching algorithm for building<br /> and optimally maintaining a spanning tree for multicasting in MANET – STM algorithm<br /> (Spanning Tree for Multicasting) – is necessary. The network simulation tool NS-2 is used to<br /> observe the results of simulation and evaluate algorithms for building and optimally maintaining a<br /> spanning tree for multicasting in the MANET compared with other multicasting protocols as<br /> MAODV and PUMA with a large number of nodes to more exactly evaluate network performance<br /> the parameters such as throughput, latency, load cost, ... to show the optimal algorithm STM as<br /> lower-cost routing, better performance than conventional methods.<br /> Keywords: Mobile adhoc network, Multicast Adhoc On-demand Distance Vector, Protocol for<br /> Unified Multicasting through Annoucements, multicast spanning tree<br /> <br /> Ngày nhận bài:25/01/2014; Ngày phản biện:10/02/2014; Ngày duyệt đăng: 26/02/2014<br /> Phản biện khoa học: TS.Phùng Trung Nghĩa – Trường ĐH Công nghệ Thông tin & Truyền thông - ĐHTN<br /> *<br /> <br /> Tel: 01699 831287, Email: ntthang@ictu.edu.vn<br /> <br /> 33<br /> <br />