nguyễn huy thái Xử lý thông tin và truyền thông
2003 2005
Hà Nội
2005

Bộ giáo dục và đào tạo
Trường Đại học bách khoa Hà nội
------------------------

Luận Văn Thạc sỹ khoa học

Nghiên cứu giao thức định

tuyến nguồn động dsr trong
mạng ad hoc

nguyễn huy thái

Hà nội 2005


XLTT&TT 2003

MỤC LỤC
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT
DANH MỤC CÁC BẢNG
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
LỜI NĨI ĐẦU
CHƯƠNG 1. TỔNG QUAN VỀ MẠNG AD HOC
1.1 Giới thiệu chung
1.2 Mạng Ad hoc vô tuyến

1.2.1 Khái niệm
1.2.2 Đặc điểm của mạng Ad hoc
1.2.3 Các ứng dụng
1.3 Định tuyến trong mạng Ad hoc
CHƯƠNG 2. GIAO THỨC ĐỊNH TUYẾN MẠNG AD HOC
2.1 Các yêu cầu chung
2.2 Phân loại
2.2.1 Các giao thức định tuyến đơn hướng
2.2.2 Các giao thức định tuyến đa hướng
CHƯƠNG 3. GIAO THỨC ĐỊNH TUYẾN NGUỒN ĐỘNG DSR
3.1 Tổng quan về DSR
3.2 Một số giả định
3.3 Định tuyến nguồn
3.4 Khám phá tuyến
3.5 Duy trì tuyến
3.6 Bộ nhớ tuyến
CHƯƠNG 4. MỘT SỐ TỐI ƯU TRONG DSR
4.1 Tối ưu trong khám phá tuyến
4.1.1 Giới hạn số chặng trong Yêu cầu tuyến
4.1.2 Trả lời Yêu cầu tuyến dùng bộ nhớ tuyến
4.1.3 Ngăn chặn cơn bão Trả lời tuyến
4.1.4 Sự xếp chồng trên các yêu cầu tuyến
4.1.5 Hỗ trợ các liên kết đối xứng
4.2 Tối ưu trong Duy trì tuyến
4.2.1 Tận dụng lại gói
4.2.2 Tự động thu ngắn tuyến
4.2.3 Tăng q trình truyền lan các bản tin lỗi tuyến
4.3 Tối ưu trong kỹ thut nh tuyn
4.3.1 Chc nng giỏm sỏt


Giao thức định tuyến ®éng trong m¹ng Adhoc

1
1
3
3
7
7
10
13
13
16
18
19
20
20
21
23
24
28
30
33
33
33
33
34
36
36
36
36

37
37
38
38


XLTT&TT 2003

4.3.2 Chức năng xen rẽ nhánh
4.4 DSR hỗ trợ mạng không đồng nhất và IP di động
4.5 DSR với định tuyến đa hướng
4.6 So sánh DSR với một số giao thức khác
4.7 Điểm mạnh và điểm yếu
CHƯƠNG 5. CƠ SỞ ĐÁNH GIÁ
GIAO THỨC ĐỊNH TUYẾN AD HOC
5.1 Các hệ đo hiệu năng
5.1.1 Hệ số phân phát gói
5.1.2 Phần phụ trội định tuyến
5.1.3 Trễ từ đầu cuối đến đầu cuối
5.1.4 Thơng lượng từ đầu cuối đến đầu cuối
5.1.5 Tính tối ưu đường truyền
5.1.6 Thông số khác
5.2 Thông số kịch bản
5.2.1 Thông số di chuyển
5.2.2 Thời gian tạm dừng
5.3 Các hệ đo giá của Khám phá tuyến
5.3.1 Sự ngăn chặn
5.3.2 Giá khám phá
CHƯƠNG 6. CÁC CÔNG CỤ MÔ PHỎNG MẠNG ADHOC
6.1 Lựa chọn công cụ mô phỏng mạng Adhoc

6.1.1 Yêu cầu khi lựa chọn công cụ mô phỏng
6.1.2 So sánh công cụ mô phỏng
6.2 Ứng dụng công cụ mô phỏng cho mạng Ad hoc
6.2.1 Công cụ mô phỏng
6.2.2 Phần di động mở rộng
6.2.3 Chia sẻ phương tiện
6.2.4 Nút mạng
6.2.5 Sử dụng công cụ NS2
CHƯƠNG 7: THIẾT LẬP ỨNG DỤNG CỦA MẠNG ADHOC
7.1 Một số yêu cầu
7.1.1 Yêu cầu về phần cứng
7.1.2 Yêu cầu về phần mềm
7.2 Cài đặt phần cứng
7.2.1 Cài đặt Card Wireless LAN trong Window XP
7.2.2 Cài đặt Card Wireless LAN trong Window 2000
7.2.3 Cài đặt Card Wireless LAN trong Window NT
7.2.4 Cài đặt Card Wireless LAN trong Window 98/ME
7.2.5 Ci t Card Wireless LAN PCMCIA
Giao thức định tuyến ®éng trong m¹ng Adhoc

38
39
43
43
44
46
47
47
47
48

49
49
50
50
50
51
52
52
52
54
54
54
54
60
60
60
61
62
63
65
66
66
67
68
68
68
69
69
69



XLTT&TT 2003

7.3 Tạo SSID và đặt cấu hình cho Card
7.3.1 Tạo SSID cho mạng
7.3.2 Thiết lập thông số của mạng
7.4 Một số kinh nghiệm thực tế
7.4.1 Triển khai một số tính năng mở rộng
7.4.2 Một số kinh nghiệm thực tế thu được
KẾT LUẬN
TÀI LIỆU THAM KHẢO
PHỤ LỤC A. MỘT SỐ GIAO THỨC ĐỊNH TUYẾN
TIÊU BIỂU TRONG MẠNG AD HOC

Giao thøc định tuyến động trong mạng Adhoc

70
70
72
74
74
75
77
78
80


XLTT&TT 2003

CÁC KÝ HIỆU, CHỮ VIẾT TẮT

ABR

Associativity-Based Routing

ACK

ACKnowledgment

AMRoute

Ad hoc Multicast Routing

AP

Access Point

AODV

Ad-hoc On Demand Distance Vector

ARP

Address Resolution Protocol

BQ

Broadcast Query

BS


Base Station

CBR

Constant Bit Rate

CC

Computation Complexity

CGSR

Clusterhead Gateway Switch Routing

CSMA

Carrier Sense Multiple Access

CTS

Clear To Send

DCF

Distributed Coordination Function

DSDV

Destination Sequenced Distance Vector


DBF

Distributed Bellman Ford algorithm

DRP

Dynamic Routing Protocol

DSR

Dynamic Source Routing

DVMRP

Distance Vector Multicast Routing Protocol

ERS

Expanded Ring Search

FIFO

First In First Out

FSR

Fisheye State Routing

FSPL


Free Space Propagation Loss

GPS

Global Positioning System

GSR

Global State Routing

HSR

Hierarchical State Routing

HID

Hierarchical ID

IARP

Intrazone Routing Protocol

ICMP

Internet Control Message Protocol

IERP

Interzone Routing Protocol


ILS

Idealized Link-State protocol

Giao thức định tuyến động trong mạng Adhoc


XLTT&TT 2003

IMEP

Internet MANET Encapsulation Protocol

IMPORTANT

Impact of Mobility on Performance of RouTing protocols

IN

Intermediate Node

LAN

Local Area Network

LAM

Lightweight Multicast Protocol

LCC


Least Cluster Change

LL

Link Layer

LQ

Local Query

LRU

Least Recently Used

LS

Link State

MAC

Media Access Protocol

MANET

Mobile Ad-hoc NETworks

MAODV

Multicast Ad hoc On-Demand Vector routing protocol


MRL

Message Retransmission List

RPF

Reverse Path Forwarding

RREQ

Route Request

RREP

Route Reply

RRC

Route ReConstruction

RT

Routing Table

RTS

Request To Send

SRP


Static Routing Protocol

SSR

Signal Stability-Based Adaptive Routing protocol

SST

Signal Stability Table

SSID

Service set Identification

TCP

Transmission Control Protocol

TORA

Temporally Ordered Routing Algorithm

TRGR

Two Ray Ground Reflection

TT

Topology Table


TTL

Time To Live

WRP

Wireless Routing Protocol

Giao thức định tuyến ®éng trong m¹ng Adhoc


XLTT&TT 2003

DANH MỤC CÁC BẢNG
Bảng 2.1 So sánh các Giao thức định tuyến (Theo yêu cầu với Theo bảng)
Bảng 3.1 Các trường của tin báo Yêu cầu tuyến
Bảng 4.1 So sánh DSR với một số giao thức định tuyến điển hình
Bảng 5.1 Các biến trong thơng số di chuyển
Bảng 6.1 Yêu cầu chức năng các công cụ mô phỏng mạng Ad hoc
Bảng 6.2. Giao thức hỗ trợ
Bảng 6.3 Thông số cấu hình
Bảng 6.4 Khả năng thống kê
Bảng 7.1 Thơng số của Card Wireless LAN
Bảng A.1 So sánh các đặc tính của các giao thức định tuyến Ad hoc
Theo Bảng

17
25
43

51
57
58
59
59
67
88

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1 Mạng điện thoại vơ tuyến
Hình 1.2 Mạng Ad hoc di động – MANET
trong kiến trúc mạng vơ tuyến 4G
Hình 1.3 Mơ hình mạng Ad hoc gồm 3 nút mạng
Hình 1.4 Mạng Ad hoc vơ tuyến
Hình 1.5 Sơ đồ khối nút mạng bao gồm router và các host di động
Hình 1.6 So sánh 2 kiểu mạng di động (MANET và Mobile IP)
Hình 2.1 Hệ tọa độ cơ bản mơ tả mơi trường mạng Ad hoc
Hình 2.2 Phần phụ trội định tuyến và tính di động đối với
các cơ chế định tuyến khác nhau
Hình 3.1 DSR bao gồm 2 cơ chế Khám phá tuyến và Duy trì tuyến
Hình 3.2 Lưu đồ xử lý gói nhận được trong một nút
Hình 3.3 Quá trình thiết lập bản ghi định tuyến của DSR
Hình 3.4 Sử dụng ID yêu cầu để hạn chế truyền
các u cầu tuyến về một phía
Hình 3.5 Duy trì tuyến, nút C khơng thể chuyển tiếp từ A đến E
qua liên kết tới bước nhẩy tiếp theo D của nó
Hình 3.6 Một ví dụ sử dụng bộ đệm tuyến
Hình 3.7 Hạn chế đối với nhớ đệm thông tin định tuyến nghe lỏm:
Nút C đang chuyển tiếp gói tới E và nghe lỏm các gói từ X
Hình 4.1 Trả lời tuyến từ Bộ nhớ đệm tuyến

Hình 4.2 Một cơn bão Trả lời tuyến có thể xảy ra khi nhiều nút
trả lời cùng một Yêu cầu tuyến từ các Bộ nhớ đệm tuyến của chúng
Hình 4.3 Nút C thấy rằng tuyến nguồn tới D có thể ngắn hơn,
khi nó nghe lỏm một gói từ A dự định đến B trước tiên
Hình 4.4 Một mạng Ad hoc bao gồm các nút truyền thông với
các thiết bị vô tuyến phạm vi ngắn và các nút A, B, C có các
Giao thức định tuyến động trong mạng Adhoc

2
4
5
5
6
6
14
18
21
24
27
28
29
31
32
34
35
37
38


XLTT&TT 2003

thiết bị truyền thơng phạm vi dài
Hình 4.5 Một mạng Ad hoc bao gồm các nút với
các giao diện mạng khơng đồng nhất
Hình 5.1 Khung IMPORTANT
Hình 5.2 Ví dụ về di chuyển của nút mạng
Hình 5.3 Khám phá tuyến với một chi phí khám phá là 8 ,
Chính sách ngăn chặn là 6/11 hoặc 54%
Hình 6.1 Mơ hình q trình mơ phỏng bằng NS2
Hình 6.2 Mơ hình chia sẻ phương tiện
Hình 6.3 Mơ tả sơ đồ khối của nút mạng
Hình 6.4 Mơ tả q trình mơ phỏng bằng NS2

Giao thức định tuyến động trong mạng Adhoc

40
46
51
53
60
62
63
64


XLTT&TT 2003

LỜI NĨI ĐẦU
Ad Hoc là một phần trong cơng nghệ thơng tin hiện nay, trong đó người sử dụng
có thể trao đổi thơng tin trực tiếp với nhau hình thành một mạng tạm thời và không
cần đến cơ sở hạ tần mạng sẵn có. Mỗi nút trong mạng Ad Hoc vừa có chức năng

của máy trạm vừa là một bộ định tuyến, các nút này luôn sẵn sàng chuyển tiếp gói
tin trong mạng. Chính vì vậy định tuyến trong mạng Adhoc là vấn đề quan trọng và
rất được quan tâm. Mạng Ad Hoc có khá nhiều điểm khác biệt so với mạng di động
tế bào truyền thống do vậy giao thức định tuyến trong mạng này phải đáp ứng thêm
nhiều yêu cầu kỹ thuật mới. Điều quan trọng nhất là giao thức định tuyến này phải
có khả năng thích nghi với cấu trúc mạng luôn thay đổi. Tiếp theo chúng ta cũng
phải kể đến những giới hạn như năng lực của thiết bị, khả năng lưu trữ, CPU, băng
thông,…Giao thức định tuyến phải làm giảm lưu lượng điều khiển, đơn giản hố
việc tính tốn đường định tuyến. Có thể nói giao thức định tuyến đóng vai trị
xương sống trong trong hoạt động của mạng Ad Hoc.
Luận văn trình bày tổng quan về mạng Ad Hoc, các giao thức định tuyến trong
mạng Ad Hoc, đặc biệt luận văn đi sâu nghiên cứu các vấn đề liên quan đến giao
thức định tuyến nguồn động DSR, môt số công cụ mô phỏng mạng Ad Hoc và thiết
lập một ứng dụng cụ thể của mạng Ad Hoc.
Do thời gian có hạn nên luận văn chắc chắn không thể đề cập hết được mọi khía
cạnh liên quan đến mạng Ad Hoc. Để luận văn ngày một hoàn thiện rất mong nhận
được nhiều ý kiến đóng góp q báu từ các Thày, các Cơ và các bạn.
Cuối cùng, em xin chân thành cảm ơn thầy giáo TS. Lê Đăng Hưng đã tận tình
hướng dẫn em hồn thành luận văn này. Qua đây tơi cũng xin được gửi lời cám ơn
tới gia đình và bạn bè đã động viên giúp sức cho tôi trong suốt thời gian học và
hoàn thành luận văn này.
Hà Nội, ngày

tháng 11 nm 2005

Nguyễn Huy Thái

Giao thức định tuyến động trong mạng Adhoc



XLTT&TT 2003

-1-

CHƯƠNG 1
TỔNG QUAN VỀ MẠNG AD HOC
1. 1 GIỚI THIỆU CHUNG
Kể từ những năm 1970, trao đổi thông tin vô tuyến giữa những người sử dụng
đầu cuối di động đã trở nên phổ biến hơn bao giờ hết. Công nghệ truyền thông này
ngày càng thu hút được nhiều người sử dụng. Số lượng các thiết bị kết nối với nhau
gia tăng rất nhanh; việc truy nhập các dịch vụ trực tuyến trở nên quen thuộc phổ cập
hơn với các dịch vụ như email, từ điển trực tuyến, thông tin du lịch, thể thao, thơng
tin thị trường chứng khốn ..v.v. Lý do chính là nhờ sự tiến bộ vượt bậc về công
nghệ điện tử gần đây trong các thiết bị như máy tính xách tay, các thiết bị thơng tin
dữ liệu vô tuyến, các modem không dây, các mạng Wireless LAN. Giá thành của
các thiết bị này tương đối hợp lý nhưng cho khả năng kết nối và truyền dữ liệu với
tốc độ rất cao.
Hiện nay, có hai xu hướng chính trong việc trao đổi thơng tin vơ tuyến giữa hai
nút mạng với nhau:
• Xu hướng I: Sử dụng mạng tế bào truyền thống đang tồn tại để truyền
dữ liệu và thoại.
Vấn đề chính gặp phải trong xu hướng này là quá trình chuyển giao mạng
tức là khi mạng điều khiển vị trí của thiết bị khi nó di chuyển từ BS này
BS khác không gây ra trễ hoặc mất các gói tin. Một vấn đề khác nữa: hình
thức mạng này phụ thuộc rất nhiều vào vùng phủ sóng của mạng tế bào
đang có sẵn. Thơng thường mạng điện thoại di động đáp ứng rất tốt nhu
cầu tại những nơi có mật độ dân cư đơng đúc, nới có nhiều dịch vụ được
cung cấp ví dụ như các thành phố lớn, khách sạn, sân bay, nhà ga xe
lửa,…và rất nhiều khu vực khác nữa. Công nghệ sử dụng trong thông tin
vô tuyến hiện nay đều phụ thuộc vào các trạm gốc BS. Những trạm này

kết nối với cơ sở hạ tầng mạng viễn thơng sẵn có và chuyển giao lưu
lượng đến các trạm khác. Do vậy việc mở rộng các dch v vựng ph súng
Giao thức định tuyến động trong m¹ng Ad Hoc


XLTT&TT 2003

-2-

của mạng vô tuyến trong xu hướng này con nhiều hạn chế và phụ thuộc
vào cơ sở hạ tầng mạng có sẵn.
Vấn đề nảy sinh là nhu cầu liên quan tới các dịch vụ vô tuyến rất nhiều nhưng
đôi khi cơ sở hạ tầng mạng tại đó lại chưa sẵn sàng hoặc để xây dựng cơ sở hạ tầng
mạng sẽ tốn nhiều chi phí nhưng khơng mang lại nhiều lợi nhuận cho nhà cung cấp
dịch vụ. Cấu trúc mạng điều khiển tập trung này vẫn còn khá phổ biến với các mạng
tế bào diện rộng đang tồn tại hiện nay ví dụ như mạng GSM, CDMA, UTMS,
PHS...
• Xu hướng II: Khi khơng có sẵn cơ sở hạ tầng mạng nhưng chúng ta
lại cần hình thành một mạng kiểu Ad Hoc cho những người có nhu cầu
trao đổi thơng tin với nhau. Khi đó các máy trong mạng Ad Hoc phải
sẵn sàng nhận và chuyển tiếp các gói tin và đảm bảo rằng các gói tin
đó đến được đích của chúng. Tuy nhiên, mơ hình mạng này bị giới hạn
bởi bán kính phục vụ (vùng phủ sóng vơ tuyến) của mỗi nút mạng. Bán
kính phục vụ này nhỏ hơn nhiều so với khoảng truyền dẫn của các BS
trong mạng tế bào. Hiện nay có nhiều giải pháp cho phép người sử
dụng thiết bị di động kết nối với nhau thông qua mạng Internet, thông
qua DHCP và Mobile IP (MIP). Tuy nhiên nó phụ thuộc vào khả năng
của các máy chủ có cho phép các máy tính kết nối hay khơng? Ngồi
ra, sử dụng MIP thơng tin của hai người sử dụng có vị trí địa lý cạnh
nhau sẽ phải định tuyến qua đường ngầm (tunelling) thơng qua mạng

Internet.

Hình 1.1 Mạng in thoi vụ tuyn
Giao thức định tuyến động trong mạng Ad Hoc


XLTT&TT 2003

-3-

Nói chung, khó có thể khẳng định rằng xu hướng I tốt hơn xu hướng II hay
ngược lại do nó phụ thuộc nhiều vào điều kiện cụ thể. Trong nhiều trường hợp
mạng Ad Hoc có nhiều ưu thế hơn mạng tế bào, cụ thể là:
-

Có thể khởi tạo mạng nhanh.

-

Có khả năng chống lỗi cao.

-

Kết nối mạng khơng giới hạn.

Mạng Ad Hoc không phụ thuộc vào cơ sở hạ tầng mạng có sẵn và do đó có thể
được triển khai ở bất kỳ nơi nào (kể cả nơi những nơi chưa có cơ sở hạ tầng mạng).
Mạng Ad Hoc rất hữu ích trong các tình huống khẩn cấp như thiên tai, tìm kiếm cứu
nạn tại và tại những nơi yêu cầu triển khai nhanh như trong chiến đấu... Mạng Ad
Hoc cũng rất hữu ích để thiết lập mạng WLAN nhanh phục vụ hội họp tại đó những

người tham gia có thể thiết trao đổi thơng tin với nhau mà khơng cần đến hạ tầng
mạng có sẵn.
Do các nút trong mạng Ad Hoc mạng phải thực hiện việc chuyển tiếp các gói tin
cho nhau nên cần có một số các giao thức đặc biệt trong định tuyến. Hiện nay quy
chuẩn cho các giao thức định tuyến trong mạng Ad Hoc còn hạn chế và chưa thực
sự đáp ứng được mọi vấn đề về kỹ thuật phát sinh. Do vậy trong tương lai còn khá
nhiều vấn đề kỹ thuật cần phải nghiên cứu, giải quyết và hoàn thiện chúng.
1.2 MẠNG AD HOC VƠ TUYẾN
1.2.1 Khái niệm
Mạng Ad Hoc vơ tuyến là mạng ngang hàng (peer-to-peer), đa chặng (multi-hop)
không quản lý tập trung. Nó bao gồm nhiều nút (node) di động và chia sẻ cùng một
kênh vô tuyến. Các nút trong phạm vi phủ sóng của nhau đóng vai trị như một bộ
định tuyến sẵn sàng nhận và chuyển tiếp các gói tin với nhau. Trong mạng Ad Hoc
khơng có sự tồn tại trước cơ sở hạ tầng mạng cố định. Mạng Ad Hoc có thể được
tạo ra và sử dụng "vào bất kỳ thời gian nào, ở bất kỳ đâu". Ngoài ra, mạng Ad Hoc
hoạt động ổn định hơn mạng tập trung thơng thường rất nhiều bởi tính phân tán của
chúng.

Giao thức định tuyến động trong mạng Ad Hoc


XLTT&TT 2003

-4-

Mạng Ad Hoc vơ tuyến có thể hình dung là tập hợp các nút di động, bán di động
hoặc tồn bộ các nút có khả năng di chuyển. Bán kính vùng phủ sóng của mỗi nút
thường bị giới hạn nên các nút trao đổi thông tin với nhau bằng phương pháp truyền
gói tin qua nhiều chặng. Do đó kết nối trong mạng Ad Hoc thường là kết nối đa
chặng (multi-hops). Các nút đóng vai trị như một bộ định tuyến trong mạng để đảm

bảo các gói dữ liệu được chuyển chính xác tới đích của chúng. Mỗi nút có một giao
diện vô tuyến và giao tiếp với nút mạng khác thơng qua sóng vơ tuyến hoặc qua
giao diện hồng ngoại. Máy tính xách tay hoặc PDA là ví dụ về các nút trong mạng
Ad Hoc. Nút trong mạng Ad Hoc có thể chuyển động nhưng cũng có thể đứng n.
Ví dụ như điểm truy nhập Internet - AP.

Hình 1.2 Mạng Ad Hoc di động- MANET trong kiến trúc mạng vơ tuyến 4G
Hình 1.3 minh hoạ một mạng Ad Hoc đơn giản gồm 3 nút mạng S và D là hai nút
mạng không nằm trong phạm vi truyền dẫn của nhau, chỳng giao tip vi nhau
Giao thức định tuyến động trong m¹ng Ad Hoc


XLTT&TT 2003

-5-

thông qua nút R, nút mạng trung gian (relay), để chuyển tiếp gói tin giữa các nút
mạng nằm ngồi khoảng cách truyền dẫn, như vậy nó có vai trị như bộ định tuyến
(router). Ba nút như vậy hình thành một mạng Ad Hoc.
Các mạng di động Ad Hoc nói chung đã giảm được chi phí quản lý so với các
mạng có dây. Những mạng này có khả năng tự cấu hình và có khả năng duy trì các
kết nối mng, thụng tin nh tuyn

Nút mạng S

oả

ng

tr


yề

nd

dẫ
n

ẫn

uy
ền

tru

kh
oả
ng

kh

Nút mạng D

Nút mạng R

Hình 1.3 Mơ hình mạng Ad Hoc gồm 3 nút mạng

Cerfiticate server

Điểm

truy nhập
www server

Public server

Hình 1.4 Mạng Ad Hoc vơ tuyến
Trong mạng Ad Hoc không tồn tại khái niệm quản lý tập trung. Điều này đảm
bảo mạng sẽ không gặp sự cố trong trường hợp nút mạng di chuyển ra ngồi vùng
phủ sóng của các nút mạng khác. Nút mạng có thể ra/vào mạng bất kỳ lúc nào. Một
nút di động có thể thực hiện đồng thời 2 vai trị trong khi trao đổi thông tin: máy
chủ và bộ định tuyến (Host/Router). Trong vai trò một máy chủ, một nút cú th l
Giao thức định tuyến động trong mạng Ad Hoc


XLTT&TT 2003

-6-

nguồn hoặc đích với các dạng lưu lượng khác nhau. Với vai trị bộ định tuyến, nó
chịu trách nhiệm chuyển tiếp các gói tới đích mong muốn và duy trì các đường định
tuyến.
Nút mạng có thể bao gồm một router và nhiều máy trạm di động liên kết với
nhau như Hình 1.5.
Host
Host

Router

Host
Hình 1.5 Sơ đồ khối nút mạng bao gồm router và các host di động

Mạng Ad Hoc còn có khả năng tự thay đổi cấu hình và tự khắc phục sự cố của
nút thông qua các thủ tục cấu hình lại mạng. Ví dụ: nếu một nút rời khỏi mạng sẽ
gây ra sự cố liên kết. Khi đó các nút mạng cịn lại có thể u cầu một định tuyến
mới và như vậy vấn đề đã được giải quyết. Điều này có thể gây ra khoảng thời gian
trễ đáng kể trong mạng. Tuy nhiên người sử dụng mạng Ad Hoc khơng phát hiện ra
thời gian trễ này.

Hình 1.6 So sánh 2 kiểu mạng di động (MANET và Mobile IP)
Ad Hoc vô tuyến chứa nhiều ưu điểm của mạng vô tuyến thông thường. Liên kết
giữa các nút mạng được hình thành nhanh khi chúng nằm trong vùng phủ sóng ca
nhau.

Giao thức định tuyến động trong mạng Ad Hoc


XLTT&TT 2003

-7-

1.2.2 Đặc điểm của mạng Ad Hoc
Trong mạng tế bào hoặc mạng IP di động: các nút di động trao đổi thông tin với
nhau thông thông qua các trạm gốc BS cố định. Các BS này tạo nên một mạng đa
chặng cố định. So với cấu trúc mạng nói trên mạng Ad Hoc có một số đặc tính nổi
bật khác như sau:
1. Cấu trúc tôpô động: Các nút tự do dịch chuyển do đó tơpơ mạng được đặc
trưng bởi tính đa chặng, thay đổi ngẫu nhiên tại các thời điểm không dự báo trước.
2. Dải thông hạn hẹp, các liên kết có dung lượng thay đổi: Các đường liên kết vơ
tuyến có dung lượng thấp hơn đáng kể so với các đường liên kết có dây. Đặc biệt
khi sử dụng các ứng dụng đa phương tiện băng thông sử dụng có thể vượt quá dung
lượng mạng. Bên cạnh đó độ lưu thốt các kênh liên lạc vơ tuyến thường nhỏ hơn

tốc độ truyền dẫn vô tuyến cực đại do tác động của đa truy nhập, pha đinh, tạp âm
và các trạng thái nhiễu.
3. Khả năng của các thiết bị di động trong mạng Ad Hoc bị hạn chế: Các nút
mạng bị giới hạn về khả năng như CPU, bộ nhớ, dung lượng nguồn ắc quy. Một số
nút trong mạng Ad Hoc hoạt động dựa vào các nguồn ăcquy. Đối với những nút
này, các tiêu chuẩn thiết kế hệ thống mạng quan trọng nhất là khả năng tiết kiệm
năng lượng. Sử dụng phương pháp định tuyến nhiều chặng đã khắc phục được rất
tốt vấn đề này.
4. Tính an tồn vật lý bị giới hạn: Các mạng vô tuyến di động thường bị tấn công
ở mức vật lý nhiều hơn so với các mạng cố định. Sự gia tăng khả năng nghe lén, các
cuộc tấn công để từ chối dịch vụ cần được xem xét kỹ lưỡng. Chính tính phi tập
trung trong điều khiển của mạng Ad Hoc đã cung cấp khả năng chống lại vấn đề
này.
1.2.3 Các ứng dụng
Lý do cơ bản để sử dụng các mạng Ad Hoc không phải tính khả thi của nó vào
bất kỳ lúc nào và bất kỳ đâu, bởi bất kỳ ai (như trong trường hợp các hệ thống tế
bào 2G và 3G). Sức mạnh chủ yếu trên thực tế là khả năng kết nối liên tục
(seamless connectivity) giữa các thiết bị trong vùng lân cận. Một số ứng dụng có thể
được tạo ra s dng mng Ad Hoc:
Giao thức định tuyến động trong m¹ng Ad Hoc


XLTT&TT 2003

-8-

Hội nghị
Một điều có thể nghĩ đến về các cuộc hội nghị và họp mặt tại đó hầu như mọi
người đều có máy tính xách tay hoặc PDA. Trong những cơ hội như vậy, mọi người
có thể kết nối với nhau mà không cần bất kỳ hạ tầng mạng sẵn có tại đó. Khi đó mọi

người có thể trao đổi thông tin với nhau, sử dụng máy in nội bộ, kết nối Internet
thông qua cổng Internet vô tuyến. Mọi người cịn có thể tải bản thuyết trình đang
trình bày, duyệt tồn bộ các trang trình chiếu trên thiết bị của họ hoặc in các trang
đó trên máy in nội bộ, e-mail bản thuyết trình tới các đồng nghiệp vắng mặt. Sử
dụng mạng Ad Hoc trong ứng dụng này đã giảm bớt được nhiều chi phí phát sinh
như chi phí mua (Hub, Switch, dây cáp, đầu RJ45..)
Hoạt động cứu hộ
Do mạng Ad Hoc có thể triển khai nhanh nên có thể sử dụng chúng trong các
cơng tác như tìm kiếm cứu hộ tại vùng có thảm hoạ, động đất, hoả hoạn, hay lụt lội.
Trong những trường hợp như vậy hạ tầng mạng hiện có đã bị hư hại và khơng sử
dụng được do vậy ứng dụng mạng Ad Hoc tại đây trở nên rất hữu hiệu.
Các mạng gia đình
Nhiều gia đình đã có một hoặc nhiều hơn một máy tính tại nhà. Vì các máy tính
này đặt tại nhiều phịng và mọi người đều mong muốn kết nối chúng với nhau. Thực
tế, hầu hết người sử dụng không thạo các vấn đề mạng do vậy với các ưu thế như
khả năng tự tổ chức (self-organizing), khả năng tự cấu hình mạng thì mạng Ad Hoc
là giải pháp đơn giản và hữu hiệu nhất.
Trong tương lai, mọi người có thể hình dung: nhiều thiết bị tại nhà kết nối mạng
và mọi người điều khiển được chúng từ xa. Các thiết bị đó có thể là máy giặt đặt ở
vị trí cố định, máy radio, máy tính xách tay có thể di chuyển. Trong trường hợp này,
dùng dây dẫn kết nối chúng lại với nhau là không phù hợp do các thiết bị này di
chuyển khắp nơi. Sử dụng mạng Ad Hoc trong trường hợp này thể hiện thực sự hiệu
quả. Nó đã khắc phục được mọi vấn đề về tính di ng v tớnh thay i trong cu
trỳc mng.

Giao thức định tuyến động trong mạng Ad Hoc


XLTT&TT 2003


-9-

Các mạng vùng cá nhân PAN
Mạng vùng cá nhân PAN là mạng của các thiết bị liên quan chặt chẽ đối với mỗi
cá nhân. Những thiết bị này có thể được gắn vào quần áo của mỗi người hoặc là
được đặt trong túi. Trong tương lai, các thiết bị này có thể bao gồm cả các thiết bị
thực tế ảo, các thiết bị cảm biến (sense of touch). Khi sự tác động lẫn nhau giữa các
mạng PAN là cần thiết thì đặc tính di động trở nên vơ cùng quan trọng. Để thiết lập
thông tin giữa các mạng PAN chuyển động, cơng nghệ mạng Ad Hoc có thể được
áp dụng.
Mạng các Bộ cảm biến
Một số bộ cảm biến nhỏ xếp thành mạng Ad Hoc để cung cấp các thông tin chi
tiết về địa lý hay các điều kiện môi trường nguy hiểm. Thông qua công nghệ mạng
Ad Hoc, mọi hoạt động và thông tin từ các bộ cảm biến này có thể được thu thập từ
xa thay vì ta phải gửi các nhân viên làm việc tại các môi trường nguy hiểm trên. Các
bộ cảm biến là các máy thu phát vô tuyến được phân bố và làm việc thay thế các
nhân viên nói trên. Ứng dụng này được rất nhiều người quan tâm đặc biệt là ứng
dụng trong cơng nghiệp và qn sự.
Các trị chơi
Mạng Ad Hoc khơng chỉ được sử dụng trong các ứng dụng chuyên nghiệp mà
chúng cịn được sử dụng trong giải trí gia đình tại đó mọi người khơng cần biết họ
đang chơi với ai. Họ có thể chơi một trị chơi chống lại một người ngẫu nhiên trong
vùng lân cận. Ví dụ có thể hình dung tại bến xe lửa, trên ơ tơ buýt, trên sân bay,
thậm chí ngay cả trên máy bay nơi mọi người tốn nhiều thời gian để chờ đợi. Sử
dụng cơng nghệ mạng Ad Hoc trong giải trí đã tạo khả năng vơ tận đối với các trị
chơi. Chi phí cho việc nay là rất ít do khơng phải sử dụng hạ tầng mạng của bất kỳ
nhà cung cấp nào.
Qn sự
Khơng nghi ngờ gì các mạng Ad Hoc cịn có thể sử dụng hữu hiệu cho các mục
đích qn sự. Thực tế Bộ Quốc phòng Mỹ đã tài trợ rt nhiu cho cỏc nghiờn cu v


Giao thức định tuyến ®éng trong m¹ng Ad Hoc


XLTT&TT 2003

-10-

cơng nghệ chuyển mạch gói hoạt động khơng bị hạn chế bởi cơ sở hạ tầng cố định.
Năm 1972, DARPA đã bắt đầu nghiên cứu và giới thiệu Mạng vơ tuyến gói PRN.
Do đáp ứng được tính di động và khả năng triển nhanh nên mạng Ad Hoc rất hữu
ích trong ngành quân sự.
1.3 ĐỊNH TUYẾN TRONG MẠNG AD HOC
Gói tin muốn đến được đích phải chuyển tiếp nút mạng do đó để gói tin đến được
đúng đích thì phải sử dụng một phương pháp định tuyến tại các nút mạng đó. Giao
thức định tuyến này có hai chức năng: tìm/chọn tuyến cho các cặp nguồn - đích
khác nhau; và chuyển gói tin đến đúng đích. Chức năng thứ hai rất đơn giản có thể
sử dụng nhiều giao thức và cấu trúc dữ liệu (các bảng định tuyến) có sẵn. Trong
phạm vi giới hạn, luận văn chỉ đề cập đến chức năng thứ nhất của giao thức định
tuyến: đó là tìm/chọn tuyến.
Giao thức định tuyến là cần thiết, vậy sao không sử dụng các giao thức định
tuyến thông thường? Các giao thức thông thường như trạng thái liên kết và vectơ
khoảng cách đã được kiểm nghiệm và rất quen thuộc trong truyền thơng máy tính.
Tuy nhiên những giao thức thơng thường chỉ thích hợp với mạng có cấu trúc tĩnh.
Nó vấp phải những vấn đề gì khi áp dụng cho mạng Ad Hoc có cấu trúc ln thay
đổi?
Các giao thức định tuyến thơng thường
Vấn đề chính đối với các giao thức định tuyến thông thường là chúng được thiết
kế cho một tôpô tĩnh. Vấn đề lớn mà các giao thức định tuyến thông thường phải
đối mặt là sự thay đổi tôpô mạng thường xuyên. Trạng thái liên kết và vectơ khoảng

cách chỉ hoạt động hiệu quả trong mạng Ad Hoc trong đó các nút mạng ít di động
Một vấn đề khác với giao thức định tuyến thông thường là: hoạt động phụ thuộc
nhiều vào các bản tin điều khiển định tuyến định kỳ. Chúng yêu cầu cập nhật
thường xuyên bảng định tuyến của các nút mạng và do đó làm tiêu tốn tài nguyên
mạng như băng thông, công suất nguồn, khả năng xử lý của CPU. Trạng thái liên
kết và vectơ khoảng cách ln cố gắng duy trì các tuyến tới mọi đích mà khơng
quan tâm nút mạng đó có tham gia truyền thơng trong mạng hay khơng do vậy nó
làm tiêu tốn đáng kể tài nguyên mạng.
Giao thøc định tuyến động trong mạng Ad Hoc


XLTT&TT 2003

-11-

Đặc tính khác của các giao thức định tuyến thông thường là chúng công nhận các
liên kết phải là 2 chiều. Thực tế trong môi trường vô tuyến, điều này không phải lúc
nào cũng như vậy. Hiện nay, các giao thức định tuyến được đề xuất cho mạng Ad
Hoc đều dựa trên giao thức định tuyến cổ điển. Do đó việc tìm hiểu ngun lý hoạt
động của các giao thức định tuyến truyền thống như vectơ khoảng cách, trạng thái
liên kết, định tuyến nguồn là hết sức cần thiết. Sau đây xin trình bày sơ lược một số
giao thức định tuyến thông thường:
Trạng thái liên kết
Phương pháp định tuyến này dựa trên giá trị của mỗi liên kết (cost) và nút mạng
phải duy trì cấu trúc mạng theo tham số này. Tham số “giá trị” sẽ được cập nhật
bằng cách mỗi nút mạng sẽ gửi liên tục thông tin quảng bá về “giá trị ”của các liên
kết xuất phát từ nó đến tất cả các nút khác sử dụng thuật toán chọn đường kiểu phát
tràn lan (flooding). Mỗi nút mạng khi nhận được các thông tin này sẽ cập nhật cấu
trúc mạng và sử dụng thuật tốn tìm đường đi ngắn nhất đến nút mạng tiếp theo.
Liên kết có thể có giá trị khơng chính xác do nhiều ngun nhân như trễ đường

truyền, sự phân mảnh mạng,… Khi cấu hình mạng thay đổi, vịng định tuyến khép
kín (loop) có thể hình thành. Tuy nhiên thời gian tồn tại của các vịng định tuyến
này rất ngắn vì chúng bị xố đi ngay khi bản tin đã đi qua.
Vectơ khoảng cách
Phương pháp định tuyến dựa trên vector khoảng cách đã có nhiều cải tiến hơn so
với phương pháp định tuyến dựa trên trạng thái liên kết trong đó mỗi nút mạng chỉ
giám sát giá trị của liên kết xuất phát từ nó. Nó khơng quảng bá thơng tin đến tất cả
nút trong mạng. Theo định kỳ nó sẽ gửi quảng bá đến các nút lân cận thông tin về
khoảng cách ngắn nhất đến các nút khác trong mạng. Nút mạng nhận được thơng tin
sẽ tính tốn và cập nhật lại bảng định tuyến của mình thơng qua thuật tốn tìm
đường ngắn nhất bằng cách so sánh vectơ khoảng cách của nó với thông tin vừa
nhận được.
So với định tuyến dựa theo trạng thái liên kết, định tuyến dựa trên vectơ khoảng
cách hiệu quả hơn và dễ thực hiện hơn. Phương pháp này yêu cầu ít bộ nhớ lưu trữ.
Tuy nhiên, định tuyến theo vectơ khoảng cách có thể tạo ra các vũng nh tuyn
Giao thức định tuyến động trong mạng Ad Hoc


XLTT&TT 2003

-12-

thời gian ngắn và vòng định tuyến thời gian dài. Nguyên nhân chính là do các nút
mạng chọn chặng đi tiếp theo dựa trên bảng định tuyến đã được xây dựng từ thông
tin quá cũ (không được cập nhật).
Định tuyến nguồn
Định tuyến nguồn hay định tuyến theo yêu cầu là kiểu định tuyến trong đó mỗi
gói tin mang theo một đường truyền trọn vẹn (sẽ được truyền trên mạng) trước khi
được gửi đi do vậy quyết định định tuyến được thực hiện ngay ở nút nguồn. Lợi
điểm của phương pháp này là tránh được các vòng lặp định tuyến. Tuy nhiên mỗi

gói tin địi hỏi phải có thêm một phần thông tin phụ trội (overhead).
Chọn đường tràn lan (Flooding)
Nhiều giao thức định tuyến đã sử dụng việc phát quảng bá để truyền thông tin
điều khiển từ nút gốc tới các nút khác còn lại. Việc phát quảng bá các thông tin điều
khiển hoạt động như sau: nút nguồn gửi thơng tin của nó tới các nút lân cận. Trong
trường hợp mạng vô tuyến, các nút lân cận đều nằm trong vùng phủ sóng của nút
nguồn. Sau đó các nút lân cận này tiếp tục chuyển tiếp thông tin điều khiển đó tới
lân cận tiếp theo của chúng và cứ như vậy q trình lặp lại cho đến khi gói tin đã
đến toàn bộ các nút trong mạng. Một nút mạng chỉ chuyển tiếp gói tin một lần thơng
qua tham số về thứ tự. Khi một gói tin mới đi qua, giá trị của tham số thứ tự này sẽ
tăng lên.
Định tuyến dựa trên bảng định tuyến xác định trước
Định tuyến dựa trên bảng định tuyến đòi hỏi giao thức ln phải duy trì, cập nhật
thơng tin định tuyến từ các nút khác còn lại trong mạng. Mỗi nút mạng phải có một
hoặc nhiều bảng định tuyến để lưu giữ thông tin định tuyến, dùng các bản tin cập
nhật định tuyến truyền trên mạng để đáp ứng lại sự thay i v cu trỳc mng.

Giao thức định tuyến động trong m¹ng Ad Hoc


XLTT&TT 2003

-13-

CHƯƠNG 2
GIAO THỨC ĐỊNH TUYẾN MẠNG AD HOC
2.1 CÁC YÊU CẦU CHUNG
Do các nút trong mạng Ad Hoc luôn di động và có nhiều đặc tính khác biệt nên
khơng thể áp dụng các giao thức định tuyến thông thường. Các mạng Ad Hoc
thường được đặc trưng bởi một tôpô động do các nút di chuyển và làm thay đổi vị

trí vật lý của chúng. Đối với mạng Ad Hoc, giao thức định tuyến động tỏ ra hiệu
quả và phù hợp hơn các phương pháp định tuyến thơng thường ví dụ như giao thức
định tuyến dựa trên vectơ khoảng cách và trạng thái liên kết. Thách thức trong việc
thiết kế các giao thức định tuyến động là khả năng cập nhật được mức di động của
nút mạng. Chính mức di động này là nguyên nhân làm thay đổi toàn bộ cấu trúc
tôpô của mạng. Một nút di động thường bị giới hạn bởi khả năng xử lý của CPU,
dung lượng lưu trữ, công suất nguồn và dải thông.
Môi trường truy nhập, mơi trường vơ tuyến cũng có những thuộc tính đặc biệt
cần phải chú ý khi thiết kế các giao thức cho mạng Ad Hoc. Ví dụ các đường truyền
vơ hướng. Những đường truyền này xuất hiện khi hai nút có cường độ phát khác
nhau và cho phép chỉ một nút nghe được nút kia. Nhưng chúng cũng có thể xuất
hiện do nhiễu từ môi trường xung quanh. Đa chặng trong mơi trường vơ tuyến có
thể gây ra tăng ích cơng suất truyền và tăng ích cơng suất do mối quan hệ căn bậc
hai giữa vùng phủ sóng và cơng suất phát ra. Bằng cách sử dụng đa chặng, các nút
có thể truyền các gói tin đi sử dụng cơng suất ra thấp.
Hình 2.1 mơ tả các trục cơ bản có thể sử dụng để đặc tả mơi trường mạng Ad
Hoc. Trục đầu tiên là số các nút trong mạng. Trục thứ 2 là tốc độ mà tại đó tơpơ
mạng thay đổi. Trục thứ ba là tải lưu lượng trong mạng. Khi môi trường di chuyển
từ gốc của 3 trục, vấn đề định tuyến trở nên khó khăn hơn. Tăng số các nút, tăng tốc
độ thay đổi tôpô (nghĩa là tăng tính di động của nút), hoặc tăng tải lưu lượng mong
muốn trên mạng là thách thức đối với các giao thc nh tuyn trong mng Ad Hoc.

Giao thức định tuyến động trong mạng Ad Hoc


XLTT&TT 2003

Sớ nút

-14-


̉i
Ta

Tơ

lư

́c đ

u

lư

ợ t

g
ợn

ha

yđ

ởi

tơ p

ơ

Hình 2.1 Hệ tọa độ cơ bản mô tả môi trường mạng Ad Hoc

Các giao thức định tuyến trong mạng Ad Hoc có một số thuộc tính mong muốn
như sau:
Hoạt động phân tán
Giao thức định tuyến trong mạng Ad Hoc phải là giao thức phân tán yêu cầu độ
tin cậy cao. Do các nút là di động nên giao thức định tuyến tập trung là không phù
hợp. Mỗi nút mạng phải đủ thông minh để tạo các quyết định định tuyến sử dụng
các nút lân cận khác.
Khơng lặp vịng
Để nâng cao hiệu năng giao thức định tuyến mạng Ad Hoc phải đảm bảo các
tuyến được cung cấp khơng bị lặp vịng. Điều này tránh được các lãng phí như:
băng thơng hoặc cơng suất sử dụng của CPU.
Hoạt động dựa trên yêu cầu
Thuật toán định tuyến trong mạng Ad Hoc phải thích ứng với lưu lượng yêu cầu
hoặc nhu cầu cơ bản để sử dụng hiệu quả các tài nguyên năng lượng và dải thông
mạng. Giao thức đó chỉ tương tác khi cần thiết và giao thức đó khơng phát quảng bá
định kỳ các thơng tin điều khiển. Điều này làm giảm thiểu phần thông tin điều khiển
nhưng lại làm tăng độ trễ.
Tính tiên phong (proactive)

Giao thức định tuyến động trong mạng Ad Hoc


XLTT&TT 2003

-15-

Trong một số trường hợp phải tăng thời gian trễ do hoạt động dựa trên yêu cầu là
không chấp nhận được. Do đó phải sử dụng đặc tính tiên phong nếu tài nguyên của
mạng (về mặt dải thông) nằm trong khoảng cho phép.
Hỗ trợ liên kết theo một hướng

Môi trường vơ tuyến có thể là ngun nhân hình thành các liên kết theo một
hướng. Sử dụng các kiểu liên kết này và các kiểu liên kết hai chiều sẽ nâng cao hiệu
năng của giao thức định tuyến.
Tính bảo mật
Mơi trường vô tuyến rất dễ bị tấn công bởi các cuộc tấn công mạo danh. Do vậy
để đảm bảo an toàn cho các giao thức định tuyến, chúng ta cần một số biện pháp
phòng ngừa. Chẳng hạn nhận thực và mã hố là cách bảo mật thơng thường nhất
được áp dụng hiện nay. Vấn đề ở đây là việc phân bổ các khố và các nút trong
mạng Ad Hoc.
Bảo tồn năng lượng
Các nút trong mạng Ad Hoc có thể là các máy tính xách tay, các thiết bị cầm tay
PDA trong đó chúng bị giới hạn về năng lượng nguồn và do đó chúng sẽ sử dụng
một số phương thức chờ (standby) để tiết kiệm năng lượng. Do vậy các giao thức
định tuyến trong mạng Ad Hoc phải hỗ trợ được các chế độ hoạt động này.
Đa tuyến
Đa tuyến có thể được sử dụng để giảm các tương tác do sự thay đổi về cấu trúc
tôpô và trạng thái nghẽn mạng. Nếu một tuyến nào đó khơng cịn hiệu lực, một
tuyến khác có thể vẫn cịn hiệu lực và như vậy giao thức định tuyến không cần phải
khởi tạo thủ tục khám phá tuyến mới khác.
Hỗ trợ chất lượng dịch vụ QoS
Giao thức định tuyến trong mạng Ad Hoc cần kết hợp một số phương thức hỗ trợ
chất lượng dịch vụ QoS. Điều này phụ thuộc vào mục đích sử dụng của mạng, ví dụ
như mục đích hỗ trợ lưu lượng thời gian thực...
Để giải quyết vấn đề định tuyến trong mạng Ad Hoc, nhóm đặc trách kỹ thuật
Internet trong IETF đã thành lập ra nhóm cơng tác mạng Ad Hoc Di ng MANET.
Giao thức định tuyến động trong mạng Ad Hoc


XLTT&TT 2003


-16-

MANET là tổ chức nghiên cứu về mạng Ad Hoc, phát triển các đặc tính về định
tuyến cho mạng Ad Hoc dựa trên nền IP. Tổ chức này đã đưa ra kết quả nghiên cứu
dưới dạng bản dự thảo và một số khuyến nghị RFC. Hiện nay, chưa có một giao
thức chính thống và đầy đủ các tính năng như ở trên được đề xuất trong MANET.
Các giao thức đề xuất chỉ mới đáp ứng được chức năng chính là: tìm đường đi đến
đích, chứ khơng phải là đáp ứng tìm đường đi ngắn nhất hay tối ưu nhất. Tuy nhiên,
một số giao thức còn trong giai đoạn phát triển và hy vọng sẽ hỗ trợ nhiều chức
năng hơn.
2.2 PHÂN LOẠI
Các giao thức định tuyến có thể phân loại thành các dạng khác nhau phụ thuộc
vào các thuộc tính của chúng:
- Tập trung (Centralized) ngược với Phân tán (Distributed)
- Tĩnh (Static) ngược với Thích ứng (Adaptive)
- Tương tác (Reactive) ngược với Tiên phong(Proactive) hay là
- Định tuyến nguồn ngược với Chặng–theo–Chặng (Hop-by-hop)
Từ sự phân loại trên, chỉ có 2 loại cuối cùng là thích hợp trong nghiên cứu. Các
cơ chế định tuyến tin cậy trong điều khiển tập trung không đáp ứng được trong môi
trường mạng Ad Hoc phân tán. Tương tự, các lược đồ định tuyến tĩnh cũng không
đáp ứng được sự thay đổi của các trạng thái chuyển động.
Các giao thức mang tính tiên phong cố gắng đánh giá liên tục các tuyến trong
mạng để khi một gói cần phải chuyển tiếp thì tuyến đó đã sẵn sàng để sử dụng.
Trong thuật toán tiên phong phần phụ trội định tuyến là khơng đổi đối với các gói
định tuyến không dữ liệu. Trong các giao thức định tuyến theo bảng, mỗi nút duy trì
một hay nhiều bảng bao gồm thông tin định tuyến tới nút khác trong mạng. Tất cả
các nút mạng sẽ cập nhật các bảng này để duy trì một cách phù hợp thơng tin và
tình trạng của mạng. Khi tôpô mạng thay đổi, các nút truyền các bản tin thông báo
cho nhau để cập nhật thơng tin về tuyến của tồn bộ mạng. Kiểu định tuyến nguồn
là kiểu định tuyến trong đó phần mào đầu của gói tin sẽ chứa thơng tin của tồn bộ

tuyến. Kiểu định tuyến này có ưu điểm là các nút trung gian khụng cn yờu cu duy
Giao thức định tuyến ®éng trong m¹ng Ad Hoc