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

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