1

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHAN HỮU DŨNG

ĐÁNH GIÁ ẢNH HƯỞNG CỦA SỰ DI ĐỘNG
CỦA NÚT MẠNG ĐẾN HIỆU QUẢ CỦA CÁC THUẬT
TOÁN ĐỊNH TUYẾN TRONG MẠNG MANET LUẬN VĂN THẠC SĨ
Do thời gian và điều kiện có hạn nên luận văn không tránh khỏi có những thiếu
sót, tôi rất mong nhận được sự góp ý từ bạn bè, thầy cô và những người quan tâm đến
đề tài này.

Let’s start at the very beginning,
a very nice place to start,
when you sing, you begin with A, B, C,
when you simulate, you begin with the topology
- The ns Manual
3 Lời cam đoan
Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá
nhân tôi, không sao chép lại của người khác. Trong toàn bộ nội dung của luận văn,
những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn
tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp
pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định
cho lời cam đoan của mình.
Hà Nội, ngày 01 tháng 05 năm 2011
Phan Hữu Dũng 4 Mục lục

Lời cảm ơn 1
Lời cam đoan 3

3.2.1. Mục tiêu thiết kế các giao thức định tuyến cho mạng MANET 27
5

3.2.2. Áp dụng các thuật toán định tuyến truyền thống trong mạng MANET 28
3.3. Phân loại các giao thức định tuyến cho MANET
[16]
29
3.3.1. Các khái niệm liên quan 30
3.3.1.1. Định tuyến chủ ứng và định tuyến phản ứng 30
3.3.1.2. Cập nhật định kỳ và cập nhật theo sự kiện 30
3.3.1.3. Tính toán phi tập trung và tính toán phân tán 31
3.3.1.4. Đơn đường và đa đường 31
3.3.2. Phân loại các giao thức định tuyến 31
3.3.2.1. Destination-Sequence Distance Vector (DSDV) 32
3.3.2.2. Optimized Link State Routing Protocol (OLSR) 33
3.3.2.3. Ad hoc On-demand Distance Vector Routing (AODV) 35
3.3.2.4. Dynamic Source Routing (DSR)
[12]
36
3.3.2.5. So sánh các giao thức định tuyến cho MANET 38
Chương 4: NGHIÊN CỨU VIỆC SỬ DỤNG CÔNG CỤ MÔ PHỎNG VÀ PHÂN
TÍCH KẾT QUẢ 41
4.1. Lựa chọn phương pháp và công cụ đánh giá hiệu năng mạng
[1]
41
4.1.1. Lựa chọn phương pháp 41
4.1.1.1. Mô hình Giải tích 42
4.1.1.2. Mô phỏng mạng bằng chương trình máy tính 42
4.1.1.3. Đo trên mạng thực 42
4.1.1.4. Lý do sử dụng phương pháp mô phỏng để đánh giá hiệu năng mạng .43

4.5.1 Giao thức định tuyến DSDV 65
4.5.2 Giao thức định tuyến OLSR 66
4.5.3 Giao thức định tuyến AODV 66
4.5.4 Giao thức định tuyến DSR 67
Chương 5: ĐÁNH GIÁ HIỆU NĂNG CÁC GIAO THỨC ĐỊNH TUYẾN THEO
MỨC ĐỘ LINH ĐỘNG CỦA CÁC NÚT MẠNG 68
5.1. Thực nghiệm mô phỏng 68
5.1.1 Các thông số mô phỏng 68
5.1.2 Chương trình mô phỏng 69
5.2. Các độ đo hiệu năng được dùng trong luận văn 70
5.3. Kết quả mô phỏng 70
5.3.1 Mô phỏng sử dụng mô hình Random Waypoint 70
5.3.1.1 Thiết lập thông số mô phỏng 70
5.3.2.2 Kết quả và nhận xét 72
5.3.3 Mô phỏng sử dụng mô hình Random Walk 75
5.3.3.1 Thiết lập thông số mô phỏng 75
5.3.3.2 Kết quả và nhận xét 77
5.3.4 Đánh giá hiệu quả của các giao thức định tuyến 79
Chương 6: KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU 81
6.1. Kết quả đạt được của luận văn 81
6.2. Hướng nghiên cứu 82
TÀI LIỆU THAM KHẢO 83
PHỤ LỤC 84

7 Danh mục hình vẽ
Hình 1. Phân loại các mạng không dây dựa trên quy mô. 14
Hình 2. Mạng WLAN có cơ sở hạ tầng 16

Hình 32. Đánh giá kết quả trễ đầu cuối trong mô hình Random Walk 77
Hình 33. Đánh giá kết quả thông lượng trong mô hình Random Walk 78
8

Hình 34. Đánh giá kết quả tải chuẩn hóa trong mô hình Random Walk 78
9 Danh mục bảng
Bảng 1. Tổng quan về họ các chuẩn IEEE 802.11 [2] 17
Bảng 2. Tổng quan về họ các chuẩn ETSI HIPERLAN [2] 17
Bảng 3. Tổng quan về họ các chuẩn IEEE 802.15 18
Bảng 4: So sánh độ phức tạp của các giao thức định tuyến 39
Bảng 5: So sánh các đặc điểm của các giao thức định tuyến 39
Bảng 6: So sánh các đặc điểm của các giao thức định tuyến 40
Bảng 7. Các tham số của mô hình Random Waypoint 62
Bảng 8. Các tham số của mô hình Random Walk 63
Bảng 9. Các tham số hoạt động của DSDV trong NS2 65
Bảng 10. Các tham số hoạt động của OLSR trong NS2 66
Bảng 11. Các tham số hoạt động của AODV trong NS2 66
Bảng 12. Các tham số hoạt động của DSR trong NS2 67
Bảng 13. Cấu hình các mạng mô phỏng trong mô hình Random Waypoint 71
Bảng 14. Cấu hình các mạng mô phỏng theo mô hình Random Walk 76 10 Bảng ký hiệu các chữ viết tắt
AODV Ad hoc On-demand Distance Vector

RREP Route Reply
RREQ Route Request
RTS Request To Send
SURAN Survivable Radio Network
TDMA/TDD Time Division Multiple Access/ Time Division Duplex
TORA Temporally-Ordered Routing Algorithm
UMTS Universal Mobile Telecommunications Systems
VINT Virtual InterNetwork Testbed
WIFI Wireless Fidelity
WiMAX World Interoperability for MicroAccess
WLAN Wireless Local Area Network
WMAN Wireless Metropolitan Area Networks
WPAN Wireless Personal Area Networks
WRP Wireless Routing Protocol
WWAN Wireless Wide Area Networks
ZRP Zone Routing Protocol

12 Chương 1: GIỚI THIỆU
1.1. Đặt vấn đề
Mạng di động không dây đặc biệt MANET (Mobile Wireless Adhoc Network) cho
phép các máy tính di động thực hiện kết nối và truyền thông với nhau không cần dựa trên
cơ sở hạ tầng mạng có dây. Trong MANET mọi nút mạng đều có thể thực hiện chức năng
của một router, chúng cộng tác với nhau, thực hiện chuyển tiếp các gói tin hộ các nút mạng
khác nếu các nút mạng này không thể truyền trực tiếp với nút nhận. Định tuyến là bài toán
quan trọng nhất đối với việc nghiên cứu MANET. Cho đến nay, đã có nhiều thuật toán định
tuyến được đề xuất, mỗi thuật toán đều có các ưu và nhược điểm riêng. Điều đặc biệt là
mức độ của các ưu nhược điểm phụ thuộc rất nhiều vào mức độ di động của các nút mạng.

1.3. Tổ chức của luận văn
Luận văn được tổ chức thành sáu chương, cụ thể như sau:
 Chương 1: GIỚI THIỆU
 Chương 2: MẠNG WLAN VÀ MẠNG MANET
 Chương 3: CÁC GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG MANET
 Chương 4: NGHIÊN CỨU VIỆC SỬ DỤNG CÔNG CỤ MÔ PHỎNG VÀ
PHÂN TÍCH KẾT QUẢ
 Chương 5: ĐÁNH GIÁ HIỆU NĂNG CÁC GIAO THỨC ĐỊNH TUYẾN
THEO MỨC ĐỘ LINH ĐỘNG CỦA CÁC NÚT MẠNG
 Chương 6: KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU
Trong đó, chương một trình bày cơ sở khoa học và tính thực tiễn cũng như mục
tiêu nghiên cứu của luận văn. Chương hai đưa ra kiến thức cơ sở về mạng WLAN và
mạng MANET. Các kỹ thuật định tuyến truyền thống được sử dụng trong mạng cố
định và các giao thức định tuyến dùng trong mạng MANET được trình bày chương ba.
Chương bốn đưa ra cái nhìn tổng quan về bộ mô phỏng NS-2 và giới thiệu công cụ mô
phỏng mới iNSpect từ đó ứng dụng vào việc mô phỏng các giao thức định tuyến.
Chương năm sử dụng những kết quả mô phỏng thu được trong chương bốn để tính
toán các độ đo hiệu năng sau đó kết hợp với cơ sở lý thuyết về các giao thức định
tuyến trình bày trong chương ba để rút ra những đánh giá về ảnh hưởng của sự di dộng
của nút mạng đến hiệu quả của các giao thức định tuyến trong mạng MANET. Cuối
cùng, trong chương sáu là những nhận xét về kết quả đạt được và hướng nghiên cứu
tiếp theo của luận văn.

14 Chương 2: MẠNG WLAN VÀ MẠNG MANET
Mục tiêu của chương này là giới thiệu với người đọc những kiến thức cơ sở về
mạng WLAN và mạng MANET bao gồm lịch sử ra đời, các đặc điểm, những ưu nhược
điểm cũng như các ứng dụng trong khoa học, công nhệ và cuộc sống từ đó có cái nhìn

Tuy nhiên, đến giữa thập niên 1980 thì mạng WLAN mới phát triển mạnh khi
Uỷ ban Truyền thông Liên bang Mỹ FCC (US Federal Communications Commission)
quyết định cho phép sử dụng phổ biến các dải tần số công nghiệp, khoa học và y tế
ISM (Industrial, Scientific and Medical bands). Quyết định này cho phép các công ty
và người dùng sản xuất và sử dụng các sản phẩm không dây của họ mà không cần
FCC cấp giấy phép hoạt động. Từ đó, dẫn đến sự tăng trưởng vượt bậc trong lĩnh vực
mạng WLAN. Tuy nhiên, do sự xuất hiện của nhiều sản phẩm độc quyền nhưng lại
không có một tiêu chuẩn chung thống nhất, dẫn đến các sản phẩm không cùng một
công ty sản xuất có thể sẽ không tương thích với nhau. Vì vậy, yêu cầu đặt ra là phải
chuẩn hóa trong lĩnh vực mạng WLAN.
Hiện nay, trên thế giới chủ yếu sử dụng hai chuẩn phổ biến cho mạng WLAN là:
Chuẩn IEEE 802.11x do các Nhóm công tác của Viện công nghệ Điện và Điện Tử IEEE
(Institute of Electrical and Electronics Engineers) phát triển và chuẩn HiperLAN/x
(High Performance European Radio LAN) được phát triển bởi nhóm RES10 thuộc Viện
Tiêu chuẩn Viễn thông Châu Âu ETSI (European Telecommunications Standards
Institute). Chuẩn IEEE 802.11x sử dụng giao thức CSMA/CA, còn chuẩn HiperLAN/x
là giao thức TDMA/TDD. Chuẩn IEEE 802.11x được sử dụng phổ biến hơn so với
chuẩn HiperLAN/x nhưng chuẩn HiperLAN/x có những ưu điểm nổi trội khi đối phó
với vấn đề lưu lượng thời gian thực.
2.1.1.2. Phân loại mạng WLAN
Mạng WLAN có cơ sở hạ tầng
Mạng WLAN có cơ sở hạ tầng là mạng mà các nút mạng truyền thông với nhau
sử dụng một thiết bị trung tâm gọi là điểm truy cập chung AP (Access Point), hay còn
được gọi là trạm cơ sở BS (Base Station). Các trạm cơ sở không chỉ cung cấp khả năng
kết nối mạng mà nó còn thực hiện chức năng điều khiển truy cập đường truyền nhằm
chuyển tiếp thông tin từ nguồn đến đích. Ngoài ra, các điểm truy cập mạng còn thường
được kết nối với mạng có dây và được kết nối với Internet nên nó đóng vai trò như là
cầu nối giữa các mạng không dây và mạng có dây với nhau tạo thành một mạng diện
rộng. Tốc độ truyền dữ liệu của mạng không chỉ phụ thuộc vào đặc điểm của các nút
mạng mà còn phụ thuộc vào bán kính phủ sóng của các điểm truy cập mạng. Các nút

Hình 3. Mạng WLAN không có cơ sở hạ tầng [10]
2.1.1.3. Các chuẩn đối với mạng WLAN
Chuẩn IEEE 802.11/x
802.11 802.11a 802.11b 802.11g
Frequency Range

(GHz)
2.4-2.4835
5.15-5.25 (lower)
5.25-5.35 (middle)
5.725-5.825 (upper)
2.4-2.4835 2.4-2.4835
Max.DataRate
(Mbps)
2 55 11 54
Range
< 10 m 27-30(lowerband) 75-100 30
Bảng 1. Tổng quan về họ các chuẩn IEEE 802.11 [2]
Chuẩn HIPERLAN/x

HIPERLAN
1
HIPERLAN
2
HIPERLAN
3
HIPERLAN
4
Application
WLAN

tốc độ truyền dữ liệu ở mức trung bình, trong khi 802.15.3 được phát triển cho mạng Ad
hoc với lớp MAC phù hợp cho truyền dữ liệu đa phương tiện có tốc độ truyền dữ liệu ở
mức cao và 802.15.4 định nghĩa giao thức liên kết nối các thiết bị ngoại vi truyền thông
sóng vô tuyến trong hệ thống mạng một người dùng có tốc độ truyền ở mức thấp.
802.15.1 802.15.3 802.15.4
Frequency Range

2.4 Ghz 2.4 Ghz 2.45 Ghz 915MHz 868MHz
Max.Data Rate
1 Mpbs 55 Mpbs 250 Kpbs 40 Kbps 20 Kbps
Range
< 10 m < 10 m 10 - 75 m
Bảng 3. Tổng quan về họ các chuẩn IEEE 802.15
2.1.2.2. Mạng đô thị WMAN theo chuẩn 802.16
Mạng đô thị không dây WMAN (Wireless Metropolitan Area Networks) được
định nghĩa là mạng có qui mô lớn có thể bao phủ một vùng đô thị như một thành phố,
một quận, huyện hoặc là một khu vực dân cư rộng lớn nào đó. Mạng này sử dụng các
công nghệ dành cho mạng diện rộng (WAN), có tốc độ truyền dẫn cao và khả năng
kháng lỗi mạnh.
Năm 2001, chuẩn IEEE 802.16 đã được thiết kế để mở ra một tập hợp các giao
tiếp dựa trên giao thức tầng MAC và lớp vật lý. Chuẩn 802.16 cũng đề cập đến công
nghệ WiMax là công nghệ không dây băng thông rộng đang phát triển rất nhanh với khả
năng triển khai trên phạm vi rộng và mang lại khả năng kết nối Internet tốc độ cao tới
các gia đình và công sở. Giao thức lớp MAC của chuẩn IEEE 802.16 hỗ trợ truy cập
không dây băng rộng điểm - đa điểm với tốc độ truyền dữ liệu cao trên cả hai hướng
truyền đa người dùng, trong cùng thời gian có thể cho phép hàng trăm thiết bị trên kênh
đó có thể được chia sẻ đa người dùng. IEEE 802.16 là giao diện cho hệ thống truy nhập
băng rộng cố định, lớp MAC và lớp vật lý (PHY) hoạt động ở 10 GHz - 66 GHz.
Ngoài ra chúng ta có thể kể ra các chuẩn mở rộng của chuẩn IEEE 802.16 như
chuẩn IEEE 802.16a ra đời năm 2003, chuẩn 802.16d được đưa ra năm 2004 là sự kết

Tại châu Âu WCDMA được chọn là công nghệ chính, trong khi CDMA2000 đang phổ
biến ở Mỹ, 85% các mạng 3G trên thế giới được dựa trên công nghệ WCDMA.
2.2. Mạng di động không dây đặc biệt MANET
2.2.1. Giới thiệu mạng MANET
MANET là chữ viết tắt của cụm từ Mobile wireless Ad hoc NETwork, là tập hợp
các nút di động có trang bị các giao tiếp mạng không dây khi thiết lập truyền thông
không cần tới sự hiện diện của các cơ sở hạ tầng mạng và các quản trị trung tâm. Trong
MANET mọi nút mạng đều thực hiện chức năng của một router, chúng cộng tác với nhau,
thực hiện chuyển tiếp các gói tin hộ các nút mạng khác nếu các nút mạng này không thể
truyền trực tiếp với nút nhận.
M
obile = di động, không chịu sự quản lý của quản trị mạng.
MANET = Adhoc = không hạ tầng mạng, topo mạng động.
NETwork
20

Năm 1971, tại Đại học Hawaii các công nghệ mạng và truyền thông vô tuyến đã
được kết hợp lần đầu tiên trong dự án Alohanet. Mục tiêu của mạng này là kết nối các
cơ sở giáo dục ở Hawaii. Mặc dù các trạm làm việc là cố định nhưng giao thức
ALOHA thực hiện việc quản lý truy cập kênh truyền dưới dạng phân tán, do đó cung
cấp cơ sở cho sự phát triển về sau của các lược đồ truy cập kênh phân tán cho phép
hoạt động của mạng Ad Hoc.
Mạng MANET có khởi nguồn từ mạng PRNet (Packet Radio Network) và dự
án SURAN (Survivable Radio Network) của tổ chức DARPA (Defense Advanced

21

Ứng dụng của mạng MANET
Truyền dữ liệu không dây di động có những bước tiến cả về công nghệ và khả
năng sử dụng, động lực thúc đẩy là sự phát triển mạnh mẽ của Internet và sự thành
công của thế hệ hệ thống di động thứ hai (2G), thế hệ hệ thống di động thứ ba (3G).
Dự kiến trong tương lai gần, vai trò truyền dữ liệu khoảng cách ngắn sẽ phát triển, là
một phần bổ sung cho truyền thông quy mô lớn truyền thống bởi phần lớn các thiết bị
thông tin liên lạc cũng như giao tiếp giữa con người xảy ra ở khoảng cách nhỏ hơn
mười mét. Một yếu tố khác thúc đẩy sự phát triển của mạng Ad Hoc là các dải tần số
được cấp phép miễn phí đem đến việc sử dụng các công nghệ truyền thông phát triển
(như Bluetooth) triển khai dễ dàng và không tốn kém.
Mạng MANET có tiềm năng to lớn cho các ứng dụng thương mại và quân sự,
và đặc biệt hữu ích cho việc cung cấp sự hỗ trợ thông tin liên lạc tại những nơi không
có cơ sở hạ tầng thông tin liên lạc sẵn có hoặc việc triển khai một cơ sở hạ tầng cố
định về mặt kinh tế là không khả thi. Ứng dụng của MANET bao gồm các hoạt động
quân sự, cứu trợ khẩn cấp, chăm sóc y tế, hoạt động mạng gia đình, môi trường học
thuật và các hoạt động khắc phục thảm họa. Ví dụ về các tình huống thiên tai bao gồm
động đất và lũ lụt, nơi các đội cứu hộ cần phải phối hợp với nhau mà không có các
mạng cố định sẵn có; các hoạt động quân sự, nơi thông tin liên lạc trong một môi
trường thù địch; các doanh nghiệp, nơi nhân viên chia sẻ thông tin trong hội nghị…

Hình 4. Mạng MANET và Sensor không dây [14]
22

2.2.2. Các đặc điểm của mạng MANET
Trong mạng AD HOC, các nút là di động và được trang bị các bộ phát và bộ
nhận không dây sử dụng các loại ăng ten đẳng hướng để phát quảng bá hoặc ăng ten
định hướng để phát điểm-điểm, có thể điều chỉnh được, hoặc kết hợp các loại ăng ten
này. Tại một thời điểm, tùy thuộc vào vị trí của nút và dạng bao phủ của bộ nhận và

có thể kết nối trực tiếp với các nút khác mà không cần thông qua các nút trung gian.
Trong mô hình này, các nút có thể di chuyển tự do nhưng chỉ trong một phạm
vi nhất định đủ để nút có thể liên lạc trực tiếp với các node khác trong mạng.
23 Hình 5. Định tuyến Single-hop
Mạng MANET định tuyến đa chặng Multi-hop
Đây là mô hình phổ biến nhất trong mạng MANET, mô hình này khác với mô
hình trước là các nút có thể kết nối với các nút khác trong mạng mà có thể không cần
phải có kết nối trực tiếp với nhau. Các nút có thể định tuyến đến nút khác thông qua
các nút trung gian trong mạng. Để mô hình này có thể hoạt động một cách hoàn hảo
thì cần phải có các giao thức định tuyến phù hợp với mô hình mạng MANET.

Hình 6. Định tuyến Multi-hop
Mô hình MANET định tuyến Mobile Multi-hop
Mô hình này là sự mở rộng của mô hình thứ hai với một chút khác biệt: mô
hình này tập trung vào các ứng dụng có tính chất thời gian thực như audio, video.
2.2.3.2. Phân loại mạng MANET theo chức năng của Nút
Mạng MANET đẳng cấp (Flat MANET)
Trong kiến trúc này, tất cả các nút có vai trò ngang hàng với nhau (peer-to-
peer) và các nút cũng đóng vai trò như các router dùng để định tuyến các gói dữ liệu
truyền trên mạng. Trong những mạng lớn thì kiến trúc Flat không tối ưu cho việc sử
dụng tài nguyên băng thông của mạng vì những thông báo điều khiển (control
message) phải truyền trên toàn bộ mạng. Tuy nhiên, nó thích hợp trong những cấu
hình mà các nút di chuyển nhiều.
Mạng MANET phân cấp (Hierarchical MANET)
Đây là mô hình mạng được sử dụng phổ biến nhất trong mạng MANET. Trong
kiến trúc này, mạng chia làm các domain, trong mỗi domain bao gồm một hoặc nhiều
cluster với mỗi cluster bao gồm một hoặc nhiều nút. Do đó, nút trong kiến trúc này

Truyền thông trong mạng MANET dựa trên các đường đi đa chặng và mọi nút
mạng đều thực hiện chức năng của một router, chúng cộng tác với nhau, thực hiện
chuyển tiếp các gói tin hộ các nút mạng khác nếu các nút mạng này không thể truyền
trực tiếp với nút nhận, do vậy định tuyến là bài toán quan trọng nhất đối với việc
nghiên cứu MANET. Cho đến nay, đã có nhiều thuật toán định tuyến được đề xuất,
mỗi thuật toán đều có các ưu và nhược điểm riêng. Điều đặc biệt là mức độ của các ưu
nhược điểm phụ thuộc rất nhiều vào mức độ di động của các nút mạng. Một số thuật
toán là ưu việt hơn các thuật toán khác trong điều kiện các nút mạng di động ở mức độ
thấp nhưng lại kém hơn hẳn khi mức độ di động của các nút mạng tăng cao. Đề tài
luận văn này chỉ nghiên cứu sâu vấn đề định tuyến trong mạng MANET nhằm mục
đích đánh giá và so sánh ảnh hưởng của sự di động của nút mạng đến hiệu quả của một
số thuật toán định tuyến trong mạng MANET.