Đõ 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 />