LỜI MỞ ĐẦU
Cùng với sự gia tăng nhanh chóng về số lượng cũng như công nghệ của
các thiết bị di động kéo theo nhu cầu của người sử dụng công nghệ không dây
ngày càng cao và đa dạng.Vì vậy để đáp ứng được xu thế đó, mạng thông tin
không dây ngày nay phải gánh vác trọng trách lớn hơn là giải quyết vấn đề về lưu
lượng đa phương tiện, tốc độ cao, chất lượng ngày càng phải tốt hơn.
Nhờ sự chỉ đạo của khoa đã giúp em có điều kiện để tiếp cận với một trong
những kiểu mạng thông tin không dây linh hoạt, đáp ứng được nhu cầu đa dạng
của người dùng đó là mạng không dây ad hoc. Mạng Ad hoc đó là tập hợp của
hai hay nhiều thiết bị được trang bị khả năng nối mạng và truyền thông không
dây. Các thiết bị đó có thể giao tiếp với các nút mạng khác ngay lập tức trong
vùng phủ sóng hay một thiết bị không dây khác ngoài bên ngoài với điều kiện có
các nút trung gian để chuyển tiếp thông tin từ nút nguồn đến nút đích. Giao thức
định tuyến được sử dụng để khám phá tuyến giữa các nút giúp cho việc giao tiếp
trong mạng dễ dàng hơn. Mục đích chính của một giao thức định tuyến trong
mạng Ad hoc là thiết lập tuyến đường chính xác và hiệu quả giữa các cặp nút.
Giao thức định tuyến phải giảm lưu lượng điều khiển, đơn giản tính toán đường
định tuyến. Chính vì thế giao thức định tuyến đóng vai trò quan trọng trong vận
hành mạng Ad hoc.
Tên đề tài: Phân tích và đánh giá hiệu năng hoạt động của một số giao thức
định tuyến reactive trong mạng không dây Ad hoc. Đề tài đưa ra tổng quan về
mạng ad hoc, phân tích và đánh giá hiệu năng hoạt động của một số giao thức
định tuyến reactive trong mạng không dây Ad hoc.
Do thời gian cũng như trình độ còn hạn chế, đề tài không tránh khỏi những
thiếu sót, em rất mong nhận được ý kiến đóng góp.

1


Đề tài gồm 3 chương:
• Chương 1: Tổng quan về mạng Ad hocvà vấn đề đánh giá hiệu năng mạng

1.3.1 Tổng quan về NS-2...............................................................................21
1.3.2 Các thành phần của NS-2......................................................................21
CHƯƠNG 2: HOẠT ĐỘNG CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN
THEO YÊU CẦU..................................................................................................33
2.1 Tổng quan về định tuyến trong mạng ad hoc..............................................33

3


2.1.1 Tổng quan..............................................................................................33
2.1.2 Phân loại................................................................................................35
2.2 Một số giao thức định tuyến theo yêu cầu..................................................37
2.2.1 Giao thức định tuyến nguồn động (DSR).............................................38
2.2.2. Định tuyến vector cự ly theo yêu cầu tuỳ biến (AODV)....................42
2.2.3 Thuật toán định tuyến theo thứ tự tạm thời (TORA)...........................49
2.3 Tổng kết.......................................................................................................50
CHƯƠNG 3: XÂY DỰNG KỊCH BẢN MÔ PHỎNG ĐÁNH GIÁ HIỆU NĂNG
CỦA HAI GIAO THỨC ĐỊNH TUYẾN AODV VÀ DSR.................................51
3.1 Các bước cơ bản của một kịch bản mô phỏng NS-2...................................51
3.2 Vấn đề trong mô phỏng mạng và đánh giá hiệu năng cho hai giao thức
AODV và DSR...................................................................................................53
3.2.1 Thông số sử dụng để đánh giá hiệu năng hoạt động hai giao thức
AODV và DSR................................................................................................53
3.2.2 Cách thức phân tích kết quả mô phỏng của NS-2................................53
+ Xử lý file dữ liệu với công cụ awk.............................................................57
+ Vẽ đồ thị với xgraph...................................................................................58
3.2.3 Các kịch bản mô phỏng cho 2 giao thức AODV và DSR....................58
3.3 Kịch bản đánh giá hiệu năng.......................................................................61
3.3.1. Thiết lập tô-pô mạng............................................................................61
3.3.2 Mô phỏng và phân tích kết quả.............................................................62

Hình 2.2: Phân loại các giao thức định tuyến trong mạng Ad hoc.......................35
Hình 2.3: Mô tả cơ chế hoạt động của định tuyến nguồn động (DSR).................38
Hình 2.4: Khám phá tuyến trong DSR..................................................................39
Hình 2.5: Duy trì tuyến.........................................................................................42
Hình 2.6: Quá trình khám phá tuyến trong AODV...............................................43
Hình 2.7: Thiết lập tuyến đường đi ngược...........................................................46
Hình 2.8: Thiết lập tuyến đường thuận.................................................................47
Hình 3.1: Hình ảnh của topo mạng trong NAM....................................................61
Hình 3.2: Thông lượng mạng qua giao thức AODV trong 100s với 30 nút.........62
Hình 3.3: Thông lượng mạng qua giao thức AODV trong 100s với 50 nút.........63
Hình 3.4: Thông lượng mạng qua AODV trong 100s với 50 nút và 30 nút.........63
Hình 3.5: Thông lượng mạng qua giao thức DSR với 30 nút...............................64
Hình 3.6: Thông lượng mạng qua giao thức DSR với 50 nút...............................65
Hình 3.7: Đồ thị biểu diễn thông lượng mạng qua DSR khi thay đổi số nút.......65
6


Hình 3.8: Thông lượng mạng của 2 giao thức AODV và DSR............................66
Hình 3.9: Số gói tin overhead của AODV trong 150s với 30 nút.........................67
Hình 3.10: Số gói tin overhead của AODV trong 150s với 50 nút.......................67
Hình 3.11: Số gói tin overhead của AODV khi thay đổi số nút mạng.................68
Hình 3.12: Số gói tin overhead của DSR trong 150s với 30 nút...........................69
Hình 3.12: Số gói tin overhead của DSR trong 150s với 50 nút...........................69
Hình 3.12: Số gói tin overhead của DSR khi thay đổi số nút...............................70
Hình 3.13: Số gói tin overhead của DSR và AODV trong 150s và 50 nút.........71

7


BẢNG THUẬT NGỮ VIẾT TẮT

OLSR
PDA
QoS
SRC
TCP
TTL
FTP

Mobile ad hoc network
Optimized Link State Routing
Personal digital assistant
Quality of service
Source
Transmission power control
Time To Live
File Transfer Protocol

8


CHƯƠNG 1: TỔNG QUAN VỀ MẠNG AD HOC VÀ
VẤN ĐỀ ĐÁNH GIÁ HIỆU NĂNG MẠNG
1.1 Tổng quan về mạng AD HOC
1.1.1 Mở đầu
Mạng máy tính từ lâu đã trở thành một phần không thể thiếu đối với nhiều
lĩnh vực đời sống xã hội, từ các hệ thống mạng cục bộ đến hệ thống mạng toàn
cầu như Internet. Mạng máy tính đưa mọi người trên thế giới đến gần nhau hơn,
mỗi người được tiếp cận với một nguồn thông tin, tri thức phong phú.
Xã hội phát triển, con người vận động không ngừng, một người kết nối vào
mạng bằng cáp vật lý thì việc di chuyển của họ bị hạn chế, nhu cầu đặt ra là vừa

phạm vi truyền dẫn không dây của mỗi máy nhưng chúng có thể truyền thông
nếu các host khác giữa chúng cũng tham gia vào mạng ad hoc sẵn sàng để
chuyển tiếp các gói tin cho chúng. Ví dụ trong mạng minh họa hình 1.1 host di
động C không nằm trong phạm vi truyền dữ liệu của host không dây A(chỉ ra bởi
vòng tròn xung quanh A) và host A không nằm trong phạm vi của host C. Trong
trường hợp này nếu A và C muốn trao đổi các gói tin, chúng có thể tranh thủ dịch
vụ của host B để B chuyển tiếp các gói tin cho chúng vì B nằm trong phạm vi
chồng chéo giữa phạm vi của A và C.

Hình 1.1: Một mạng ad hoc đơn giản với 3 host di động không dây

Hình 1.2: Mô hình mô tả một mạng Ad hoc trong thực tế

10


Trong Ad hoc không tồn tại khái niệm quản lý tập trung, nó đảm bảo
mạng sẽ không bị sập vì trường hợp nút mạng di chuyển ra ngoài khoảng truyền
dẫn của các nút mạng khác. Nút mạng có thể ra vào bất cứ lúc nào. Do khoảng
truyền dẫn của nút mạng là hạn chế nên chúng trao đổi thông tin bằng phương
pháp truyền gói tin qua nhiều bước (Multihops). Để làm được điều này, thì tất cả
các nút mạng phải có khả năng chuyển tiếp gói tin đến nút mạng khác, do vậy tất
cả các nút mạng trong Ad hoc có thể hoạt động như máy trạm và router. Nên nút
mạng có thể bao gồm một router và một máy trạm liên kết với nhau. Một router
thực hiện các giao thức định tuyến, máy trạm di động có địa chỉ IP.
Ad hoc cũng có khả năng thực hiện thay đổi về cấu hình mạng và khắc phục
sự cố của nút mạng thông qua thủ tục cấu hình lại mạng. Ví dụ: Nếu nút mạng
rời khỏi mạng sẽ gây ra sự cố liên kết, nút mạng bị ảnh hưởng có thể yêu cầu
đường định tuyến mới và vấn đề sẽ được giải quyết. Điều này sẽ gây ra trễ trên
mạng, tuy nhiên với người sử dụng Ad hoc vẫn hoạt động bình thường.

được sử dụng cho trường hợp triển khai cơ sở hạ tầng mạng là khó khăn.
a. Dịch vụ khẩn cấp
Bất kỳ đâu khi có trường hợp khẩn cẩp xảy ra đều cần có sự kết hợp của các
nhân viên cứu hộ. Giải pháp thông thường là dùng thiết bị vô tuyến. Tuy nhiên,
khi cơ sở hạ tầng bị hỏng hoặc không còn hoạt động thì giải pháp là gì? Ad hoc
chính là câu trả lời nhanh nhất và phù hợp nhất. Điều này có thể không có ý
nghĩa với khu vực tổn thất nhỏ, tuy nhiên với thảm họa thiên nhiên có khu vực
ảnh hưởng tàn phá rộng lớn, việc liên lạc rất quan trọng nên Ad hoc trở thành
giải pháp hữu ích.
b. Hội nghị
Trong hội nghị, hội thảo cần trao đổi thông tin giữa các đại biểu hoặc với
hội nghị khác. Đây là một nhu cầu lớn trong thời đại phát triển nhanh về thông
tin như hiện nay, khi mà giải pháp home network chưa thật sự sẵn sàng. Giải
pháp hiện tại là sử dụng các mạng có sẵn cho các đại biểu tham dự tuy nhiên nó
có độ trễ lớn, ví dụ giải pháp Mobile IP . Và Ad hoc là giải pháp chiếm ưu thế.

12


Hình 1.3: Ứng dụng trong các hội nghi
c. Home Networking
Rõ ràng sự hiện diện của máy tính xách tay và ứng dụng không dây làm nhu
cầu về home network tăng cao.Việc sử dụng kỹ thuật của Ad hoc cho phép chúng
tự cấu hình và hình thành mạng, điều này tiện lợi cho cả người không thật sự am
hiểu về mạng cũng như giảm được chi phí cho xây dựng thiết kế mạng. Hơn
nữa, nếu ta có nhu cầu sử dụng máy tính ở công sở, trường học thì khối lượng
thông tin quản lý mạng giảm xuống rõ rệt

Hình 1.4: Ứng dụng cho home networking
d. Mạng cá nhân (PAN)

đã có những quan tâm đáng kể cho sự phát triển kiểu mạng này,chủ yếu là trong
quân sự, công an, tình báo, khảo cổ học, nghiên cứu địa lý....Các bộ cảm biến có
thể có kích thước nhỏ nhưng khả năng truyền thông và lưu trữ tương đối tốt.
Trong quân sự đã dùng những máy móc hiện đại nhưng kích cỡ gần như hạt bụi
nên đối phương rất khó phát hiện và phá hủy chúng.
Trong lĩnh vực y tế, các bộ cảm biến cho phép giám sát liên tục thông tin
tiêu chuẩn về sự sống. Trong công nghệ thực phẩm, kỹ thuật nhịp cảm biến được
áp dụng để giám sát chất lượng có thể giúp ngăn ngừa các sản phẩm không đạt
yêu cầu nên tăng mức thỏa mãn cho khách hàng. Trong nông nghiệp, các bộ cảm
biến có thể giúp xác định chất lượng đất trồng và độ ẩm, chúng cũng có thể phát
hiện các hợp chất khác. Ngoài ra, các bộ cảm biến cũng được sử dụng rộng rãi
trong thông tin thời tiết và môi trường.
1.1.5 Phân loại mạng ad hoc
a. Theo cách thức định tuyến
+ Signal-hop:
Mạng Manet định tuyến singal-hop là loại mô hình mạng ad-hoc đơn giản
nhất. Trong đó, tất cả các node đều nằm trong cùng một vùng phủ sóng, nghĩa là
các node có thể kết nối trực tiếp với nhau mà không cần các node trung gian.
Mô hình này các node có thể di chuyển tự do nhưng chỉ trong một phạm vi
nhất định đủ để các node liên kết trực tiếp với các node khác trong mạng.

Hình 1.7: Đinh tuyến Single-hop

+ Multi-hop:
15


Đây là mô hình phổ biến nhất trong mạng ad hoc, nó khác với mô hình trước
là các node có thể kết nối với các node khác trong mạng mà có thể không cần
kết nối trực tiếp với nhau. Các node có thể định tuyến với các node khác thông

+ Mạng Manet kết hợp
Mạng = Zones, Zone = nodes
Mỗi node bao gồm hai mức topo : Topo mức thấp ( node level ), và
topo mức cao (zone level )
Mỗi node đặc trưng bởi: node ID và zone ID. Trong một Zone có thể áp
dụng kiến trúc đẳng cấp hoặc kiến trúc phân cấp.

Hình 1.10: Mô hình mạng kết hợp

17


1.2 Lý thuyết đánh giá hiệu năng mạng
1.2.1 Khái niệm đánh giá hiệu năng mạng
Đánh giá hiệu năng mạng là đánh giá tính hiệu quả và năng lực hoạt động
của hệ thống mạng trong những điều kiện cụ thể. Như vậy, việc đánh giá hiệu
năng mạng chính là tính toán và xác định hiệu quả, năng lực thực sự của hệ thống
trong các điều kiện khác nhau và dựa trên hai hướng tiếp cận chính là: kiến trúc
mạng và các kỹ thuật áp dụng trên kiến trúc mạng đó.
Đánh giá hiệu năng là hoạt động nhằm mục đích dự báo hành vi của hệ
thống một cách có định lượng. Khi một hệ thống được cấu hình lại hoặc điều
chỉnh về mặt cấu trúc thì việc đánh giá hiệu năng được sử dụng để đưa ra các dự
đoán tác động của những thay đổi đó về mặt hiệu năng của hệ thống.
Các điều kiện được sử dụng trong đánh giá hiệu năng mạng là rất quan
trọng, chúng ảnh hưởng trực tiếp tới các kết quả thu được. Trong các điều kiện
ảnh hưởng tới quá trình đánh giá hiệu năng thì kịch bản mô tả là yếu tố then chốt
quyết định giá trị hiệu năng, trong đó cần xác định các tham số đầu vào rõ ràng
như các nút tham gia hệ thống, thiết bị kết nối, tác nhân tham gia, giao thức hoạt
động, ứng dụng triển khai, thời gian thực hiện… Và rất nhiều yếu tố khác kết hợp
tạo ra một kịch bản hoàn thiện.

c. Phương pháp mô phỏng
Để giảm sai số của phương pháp toán học, giảm chi phí đầu tư cho hệ
thống trước khi đo trong thực tế, phương pháp mô phỏng được sử dụng. Việc mô
phỏng hệ thống đòi hỏi phải mô tả chính xác, chân thực tính năng, kỹ thuật, yếu
tố ràng buộc giữa các nhân tố tham gia và ảnh hưởng của môi trường tới hệ thống
trong thực tế khi xây dựng. Có hai phương pháp chính được sử dụng trong mô
phỏng hệ thống mạng là: mô phỏng thời gian thực và mô phỏng rời rạc. Để mô
phỏng theo thời gian thực là rất khó do vậy phương pháp phổ biến hiện nay là mô
phỏng rời rạc tức là các sự kiện được xác định rõ ràng và có thời điểm mô tả trên
trục thời gian.
1.2.3 Các thông số đánh giá hiệu năng mạng
Có rất nhiều thông số để đánh giá hiệu năng mạng. Những thông số này
rất quan trọng trong việc xem xét đánh giá của các giao thức định tuyến trong
một mạng. Các giao thức này cần được kiểm tra với các thông số nhất định cho

19


hoạt động của nó. Những thông số này có ảnh hưởng rất lớn trong việc lựa chọn
một giao thức định tuyến hiệu quả trong bất kỳ mạng nào.
- Tỷ lệ gói nhận được: Là tỷ lệ giữa số gói được nhận bởi nút mạng đích và số
gói được gửi đi từ lớp ứng dụng.
- Phần tải thông tin định tuyến: Cho biết hiệu năng sử dụng băng thông của giao
thức định tuyến.
- Trễ từ đầu cuối đến đầu cuối: Là thời gian mà gói tin truyền trên mạng từ nút
mạng nguồn đến nút mạng đích.
- Thông lượng từ đầu cuối đến đầu cuối: Thông lượng là khối lượng thông tin
truyền trên đường truyền trong một đơn vị thời gian (Kbps). Ý nghĩa: Khi
băng thông sẵn có trên mạng đã biết, thì trong mô phỏng băng thông thực sự
có được là bao nhiêu? Thông số thông lượng T sẽ cho biết băng thông thực sự

của Linux và Window.
1.3.2 Các thành phần của NS-2
Trong chương này chúng ta sẽ trình bày các bước đầu tiên gồm có :
•
•
•
•
•
•

Việc khởi tạo và kết thúc của bộ mô phỏng ns
Định nghĩa các node mạng, link, hàng đợi và topology
Định nghĩa các tác nhân (agent) và các ứng dụng
Công cụ hiển thị “nam”
Bám vết
Các biến ngẫu nhiên

Một vài ví dụ đơn giản được đưa ra sẽ cho phép chúng ta thực hiện các bước đầu
tiên với bộ mô phỏng ns.

21


a. Khởi tạo và kết thúc
Một mô phỏng ns bắt đầu với câu lệnh
set ns [new Simulator]

Đây là dòng đầu tiên trong tập lệnh tcl. Dòng này khai báo 1 biến ns mới
dùng lệnh set, bạn có thể gọi biến ngẫu nhiên này như bạn muốn, tuy nhiên thông
thường người ta khai báo nó là ns vì đó là một thể hiện của lớp Simulator, do vậy

lệnh $ns flush-trace (xem thủ tục “finish” ở dưới). Trong trường hợp của chúng
ta, file được chỉ tới con trỏ “$ namfile” là file “out.tr”
Chú ý: các lệnh trace-all và namtrace-all có thể dẫn đến việc tạo ra các file kích
thước lớn. Nếu chúng ta muốn tiết kiệm không gian, các lệnh trace khác sẽ được
sử dụng bởi vậy khi tạo ra trace chỉ một tập con các sự kiện mô phỏng là thực sự
cần đến. Kết thúc chương trình được thể hiện bằng một thủ tuch “finish”
#Định nghĩa thủ tục “finish”
Proc finish {} {
glocal ns tracefile1 namfile
$ns flush-trace
close $tracefile1
close $namfile
exe nam out.nam &
exit 0
}

Từ khóa proc khai báo một thủ tục trong trường hợp này là finish và không
có tham số nào. Từ khóa global được dùng để cho biết rằng chúng ta đang dùng
các biến được khai báo ngoài thủ tục. Phương thức simulator “flush-trace” sẽ đổ
(dump) các trace vào các file tương ứng. Lệnh tcl “close” đóng các file bám vết
định nghĩa trước đó và “exec” thực thi chương trình nam cho hiển thị. Lưu ý rằng
chúng ta đã chuyển tên thật của file nam bám vết thành nam và không thực hiện
điều này với con trỏ namfile vì nó không phải câu lệnh ngoài. Giá trị không là
mặc định cho exit không lỗi (clean exit). Các giá trị khác có thể được dùng để
cho biết đó là một exit có một vài lỗi gì đó. Ở cuối chương trình ns chúng ta sẽ
gọi thủ tục “finish” và chỉ ra thời điểm kết thúc. Ví dụ
$ns at 125.0 “finish”

Sẽ được dùng để gọi “finish” vào thời điểm 125 giây. Thật vậy, phương
thức của simulator cho phép chúng ta lập lịch các sự kiện một cách chính xác.

hàng đợi được thực hiện bằng việc gửi các gói tin bị hủy tới một tác nhân Null.
Đối tượng TTL sẽ tính tham số Time to Live cho mỗi gói nhận được. Một liên
kết song công được xây dựng từ hai liên kết đơn công song song.
Chú ý rằng chúng ta định nghĩa dung lượng bộ đệm tương ứng với một
liên kết duy nhất giữa n2 và n3. Các hàng đợi tương ứng với tất cả liên kết khác
đều có giá trị mặc định là 50. Giá trị mặc định này nằm trong câu lệnh của ns
default.tcl

24


Hình 1.11: Kênh truyền đơn
#Tạo 6 node
Set n0 [$ns node]
Set n1 [$ns node]
Set n2 [$ns node]
Set n3 [$ns node]
Set n4 [$ns node]
Set n5 [$ns node]
#Tạo các liên kết cho các nút
$ns duplex-link $n0 $n2 2Mb 10ms DropTial
$ns duplex-link $n1 $n2 2Mb 10ms DropTial
$ns simplex-link $n2 $n3 0.3Mb 100ms DropTail
$ns simplex-link $n3 $n2 0.3Mb 100ms DropTail
$ns duplex-link $n3 $n4 0.5Mb 40ms DropTail
$ns duplex-link $n3 $n5 0.5Mb 30ms DropTail
#Đặt kích thước hàng đợi cho liên kết (n2-n3) bằng 20
$ns queue-limit $n2 $n3 20

Đoạn mã trên định nghĩa các nút, kênh truyền và gán kích cỡ hàng đợi