ĐẠI HỌC THÁI NGUYÊN
.

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THƠNG

Phonesavanh PHONGSENPHENG

ĐÁNH GIÁ VỀ AN TỒN GIAO THỨC ĐỊNH TUYẾN
TRONG MẠNG MANET

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN - 2020


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THƠNG

Phonesavanh PHONGSENPHENG

ĐÁNH GIÁ VỀ AN TỒN GIAO THỨC ĐỊNH TUYẾN
TRONG MẠNG MANET
CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
Mã số: 8 480101

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Hướng dẫn khoa học: TS. Nguyễn Toàn Thắng

THÁI NGUYÊN - 2020

iii
LỜI CẢM ƠN
Trước tiên, tôi xin gửi lời cảm ơn chân thành tới TS Nguyễn Toàn Thắng, người
thầy đã tận tình giúp đỡ tơi trong suốt q trình làm luận văn và truyền cho tôi
những kinh nghiệm quý báu trong thời gian thực hiện đề tài.
Tôi xin gửi lời biết ơn sâu sắc tới thầy, cô trong trường Đaị Học Công Nghệ
Thông tin và truyền thông Đại học Thaí Nguyên. Thầy, cô đã truyền lại cho chúng tôi
những kiến thức vô cùng hữu ích trong thực tiễn, cũng như dạy chúng tôi phương pháp
nghiên cứu khoa học, phát huy khả năng tư duy sáng tạo trong mọi lĩnh vực.
Cuối cùng, tơi xin được cảm ơn gia đình, bạn bè, những người thân yêu nhất của
tôi. Mọi người luôn ở bên cạnh tôi, động viên, khuyến khích tôi học tập, nghiên cứu. Do
thời gian nghiên cứu và kinh nghiệm nghiên cứu chưa nhiều nên luận văn cịn nhiều
thiếu sót, rất mong nhận được những ý kiến góp ý của các Thầy/Cơ và các bạn học viên.


iv
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. Luận văn là kết quả của quá trình học tập, nghiên
cứu trong suốt khóa học. Trong các nội dung của luận văn, những vấn đề được trình bày
hoặc là kết quảcủa cá nhân hoặc là kết quả tổng hợp từ nhiều nguồn tài liệu khác. Những
kết quả nghiêncứu nào của cá nhân đều được chỉ rõ ràng trong luận văn. Các thông tin
tổng hợp hay các kếtquả lấy từ nhiều nguồn tài liệu khác đều được trích dẫn đầy đủ và
hợp lý. Tất 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 chịu hồn tồn 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.
Thái Nguyên , tháng

năm 2020


Người cam đoan

Phonesavanh PHONGSENPHENG


v
MỤC LỤC
LỜI CẢM ƠN ...................................................................................................................i
LỜI CAM ĐOAN ...........................................................................................................iv
MỤC LỤC .......................................................................................................................v
DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT ............................................................. vii
DANH MỤC HÌNH VẼ, ĐỒ THỊ ............................................................................... viii
DANH MỤC CÁC BẢNG ..............................................................................................x
MỞ ĐẦU .........................................................................................................................1
CHƯƠNG 1: TỔNG QUAN VỀ MANG MANET ........................................................2
1.1. Tổng quan về mạng MANET ................................................................................2
1.1.1 .Đặc điểm của mạng MANET .........................................................................2
1.1.2. Phân loại MANET ..........................................................................................4
1.1.3. Phân loại theo giao thức..................................................................................4
1.2. Vấn đề định tuyến trong mạng MANET ...............................................................6
1.2.1. Các thuật toán định tuyến truyền thống ..........................................................7
1.2.2. Bài toán định tuyến mạng MANET ................................................................8
1.2.3 .Các kỹ thuật định tuyến mạng MANET .........................................................9
1.2.4. Định tuyến Link State và Distance Vector .....................................................9
1.2. 5. Định tuyến chủ ứng và định tuyến phản ứng .................................................9
1.2.6. Cập nhật định kỳ và cập nhật theo sự kiện ....................................................9
1.2.7. Cấu trúc phẳng và cấu trúc phân cấp ............................................................10
1.2.8. Tính tốn phi tập trung và tính tốn phân tán ...............................................10
1.2.9. Định tuyến nguồn và định tuyến theo chặng ................................................10

1.3. Những vấn đề về an ninh trong mạng MANET ..................................................17
1.3.1. Thách thức về an ninh trong mạng MANET ................................................17
1.3.2. Các yêu cầu về an ninh ................................................................................17
1.4. Các phương thức tấn công trong giao thức định tuyến mạng .............................18
1.4.1. Tấn công bằng cách sửa đổi thông tin định tuyến ........................................19
1.4.2. Tấn công bằng cách mạo danh......................................................................19
1.4.3. Tấn công bằng cách tạo ra thông tin bịa đặt .................................................20
1.4.4. Một vài kiểu tấn cơng đặc biệt ......................................................................21
CHƯƠNG 2: TẤN CƠNG KIỂU LỖ ĐEN VÀO GIAO THỨC ĐỊNH TUYẾN AODV
VÀ MỘT SỐ GIẢI PHÁP PHỊNG CHỐNG TẤN CƠNG LỖ ĐEN .........................23
2.1. Lỗ hổng của giao thức AODV ............................................................................23


vi
2.2. Phân loại tấn công kiểu lỗ đen ............................................................................24
2.3. Một số giải pháp phịng chống tấn cơng lỗ đen trong giao thức AODV ............25
2.3.1. ARAN (Authenticated Routing for Ad hoc Networks) ................................ 25
2.3.2. SAODV (Secure Ad hoc On-demand Distance Vector) ..............................27
2.3.3. RAODV (Reverse Ad hoc On-demand Distance Vector) ............................30
2.3.4. IDSAODV (Intrusion Detection System Ad hoc On-demand Distance Vector) 32
CHƯƠNG 3: ĐÁNH GIÁ AN TOÀN GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG
MANET THÔNG QUA SỬ DỤNG CÔNG CỤ MÔ PHỎNG ....................................34
3.1. Phân tích lựa chọn phương pháp đánh giá ..........................................................34
3.2. Bộ mơ phỏng NS-2 và cài đặt mô phỏng [11] ....................................................35
3.2.1. Giới thiệu NS-2 .............................................................................................35
3.2.2. Các thành phần của bộ chương trình mơ phỏng NS-2..................................36
3.2.3. Các chức năng mơ phỏng chính của NS-2....................................................36
3.2.4. Thiết lập mô phỏng mạng MANET trong NS-2 ...........................................37
3.3. Cài đặt bổ sung các giao thức .............................................................................41
3.3.1. Cài đặt giao thức blackholeAODV mô phỏng tấn công lỗ đen ....................41

3.3.2. Cài đặt giao thức IDSAODV làm giảm ảnh hưởng tấn công lỗ đen ............43
3.3.3. Cài đặt giao thức RAODV làm giảm ảnh hưởng tấn công lỗ đen ................46
3.4. Mô phỏng, đánh giá ảnh hưởng và giải pháp làm giảm hiệu ứng của tấn công lỗ
đen ..............................................................................................................................50
3.5. Tiến hành mô phỏng, phân tích tệp vết để tính các tham số hiệu năng ..............53
3.6. Đánh giá ảnh hưởng của tấn công lỗ đen trong các giao thức định tuyến AODV,
IDSAODV và RAODV ..............................................................................................69
KẾT LUẬN ...................................................................................................................71
TÀI LIỆU THAM KHẢO .............................................................................................72
PHỤ LỤC ......................................................................................................................74


vii
DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT

MANET

Mobile Adhoc NETwork

AODV

Adhoc On-demand Distance Vector

DSDV

Destination-Sequenced Distance Vector

DSR

Dynamic Source Routing


RAODV

Reverse Adhoc On-demand Distance Vector

IDSAODV Intrusion Detection System Adhoc On-demand Distance Vector
SAODV

Secure Adhoc On-demand Distance Vector

ARAN

Authenticated Routing for Ad hoc Networks

IP

Internet Protocol

RREQ

Route Request

RREP

Route Reply

R-RREQ

Reverse Route Request


SN

Sequence Number

HC

Hop count

ID

Identification

DV

Distance Vector LS Link State NS-2 Network Simulator 2


viii
DANH MỤC HÌNH VẼ, ĐỒ THỊ
Hình 1.1. Minh họa mạng MANET.................................................................................2
Hình 1.2. Single-hop ........................................................................................................4
Hình 1.3. Multi-hop .........................................................................................................4
Hình 1.4. Mơ hình mạng phân cấp ..................................................................................5
Hình 1.5. Mơ hình mạng kết hợp.....................................................................................6
Hình 1.6. Phân loại giao thức định tuyến trong mạng MANET ...................................11
Hình 1.7. Quá trình tìm đường trong AODV ................................................................ 13
Hình 1.8. Route discovery (nút A là nút nguồn, nút E là nút đích) ...............................16
Hình 1.9. Route maintenance (Nút C khơng thể chuyển tiếp gói tin từ nút A đến .......16
nút E do liên kết giữa C và D bị hỏng) ..........................................................................16
Hình 1.10. Các kiểu tấn cơng giao thức định tuyến trong mạng MANET ....................18

Hình 1.11 Ví dụ về tấn cơng bằng cách sửa đổi ............................................................19
Hình 1.12 Ví dụ về tấn cơng bằng cách mạo danh ........................................................20
Hình 1.13 Ví dụ về tấn công bằng cách tạo ra thông tin bịa đặt ...................................21
Hình 1.14 Ví dụ về tấn cơng Wormhole........................................................................21
Hình 2.1. Thực hiện tấn cơng lỗ đen bằng việc giả mạo gói tin RREQ ........................24
Hình 2.2. Thực hiện tấn cơng lỗ đen bằng việc giả mạo gói tin R REP........................25
Hình 2.3. Định dạng của thông điệp định tuyến RREQ (RREP) mở rộng ....................27
Hình 2.4. Cách tính hàm băm khi bắt đầu phát sinh RREQ hay RREP ........................29
Hình 2.5. Cách tính hàm băm tại nút trung gian ...........................................................29
Hình 2.6. Định dạng gói tin RREQ ...............................................................................30
Hình 2.7. Định dạng gói tin R-RREQ ...........................................................................31
Hình 2.8. Ví dụ về giao thức RAODV ..........................................................................32
Hình 3.1. Biểu đồ thể hiện tỷ lệ phân phát gói tin thành cơng với tỷ lệ nút lỗ đen tăng
dần và tốc độ 0m/s .........................................................................................................55
Hình 3.2. Biểu đồ thể hiện độ trễ trung bình với tỷ lệ nút lỗ đen tăng dần và tốc độ 0m/s...56
Hình 3.3. Biểu đồ thể hiện tổng phí với tỷ lệ nút lỗ đen tăng dần và tốc độ 0m/s ........57
Hình 3.4. Biểu đồ thể hiện tỷ lệ phân phát gói tin thành cơng .. với tỷ lệ nút lỗ đen tăng
dần và tốc độ 5m/s ......................................................................................................58
Hình 3.5. Biểu đồ thể hiện độ trễ trung bình với tỷ lệ nút lỗ đen tăng dần và tốc độ 5m/s...59


ix
Hình 3.6. Biểu đồ thể hiện tổng phí với tỷ lệ nút lỗ đen tăng dần và tốc độ 5m/s ........60
Hình 3.7. Biểu đồ thể hiện tỷ lệ phân phát gói tin thành cơng với tỷ lệ nút lỗ đen tăng
dần và tốc độ 10m/s .......................................................................................................61
Hình 3.8. Biểu đồ thể hiện độ trễ trung bình với tỷ lệ nút lỗ đen tăng dần và tốc độ
10m/s .............................................................................................................................62
Hình 3.9. Biểu đồ thể hiện tổng phí với tỷ lệ nút lỗ đen tăng dần và tốc độ 10 m/s .....63
Hình 3.10. Biểu đồ thể hiện độ trễ trung bình với tỷ lệ nút lỗ đen tăng dần ...... và tốc độ
15m/s ............................................................................................................................65

Hình 3.11. Biểu đồ thể hiện tổng phí với tỷ lệ nút lỗ đen tăng dần và tốc độ 15m/s ....66
Hình 3.12. Biểu đồ thể hiện tỷ lệ phân phát gói tin thành công với tỷ lệ nút lỗ đen tăng
dần và tốc độ 20m/s .......................................................................................................67
Hình 3.13. Biểu đồ thể hiện độ trễ trung bình với tỷ lệ nút lỗ đen tăng dần ...... và tốc độ
20m/s ............................................................................................................................68
Hình 3.14. Biểu đồ thể hiện tổng phí với tỷ lệ nút lỗ đen tăng dần và tốc độ 20m/s ....69
Hình 3.15. Biểu đồ thể hiện tổng phí với tỷ lệ nút lỗ đen tăng dần và tốc độ 20m/s ....69


x
DANH MỤC CÁC BẢNG
Bảng 2.1. Các trường dễ bị tổn thương trong gói tin AODV ........................................23
Bảng 2.2. Các giá trị có thể của trường Hash_Function ...............................................29
Bảng 3.1. Tỷ lệ phân phát gói tin thành cơng với tỷ lệ nút lỗ đen tăng dần và tốc độ 0m/s ....54
Bảng 3.2. Độ trễ trung bình với tỷ lệ nút lỗ đen tăng dần và tốc độ 0m/s ....................56
Bảng 3.3. Tổng phí với tỷ lệ nút lỗ đen tăng dần và tốc độ 0m/s ..................................57
Bảng 3.4. Tỷ lệ phân phát gói tin thành công với tỷ lệ nút lỗ đen tăng dần và tốc độ 5m/s .58
Bảng 3.5. Độ trễ trung bình với tỷ lệ nút lỗ đen tăng dần và tốc độ 5m/s ....................59
Bảng 3.6. Tổng phí với tỷ lệ nút lỗ đen tăng dần và tốc độ 5m/s ..................................60
Bảng 3.7. Tỷ lệ phân phát gói tin thành cơng với tỷ lệ nút lỗ đen tăng dần và tốc độ 10m/s61
Bảng 3.8. Độ trễ trung bình với tỷ lệ nút lỗ đen tăng dần và tốc độ 10m/s ..................62
Bảng 3.9. Tổng phí với tỷ lệ nút lỗ đen tăng dần và tốc độ 10m/s ................................ 63
Bảng 3.10. Tỷ lệ phân phát gói tin thành công với tỷ lệ nút lỗ đen tăng dần và tốc độ 15m/s
.......................................................................................................................................64
Bảng 3.11. Độ trễ trung bình với tỷ lệ nút lỗ đen tăng dần và tốc độ 15m/s ................65
Bảng 3.12. Tổng phí với tỷ lệ nút lỗ đen tăng dần và tốc độ 15m/s ..............................66
Bảng 3.13. Tỷ lệ phân phát gói tin thành cơng với tỷ lệ nút lỗ đen tăng dần và tốc độ
20m/s .............................................................................................................................67
Bảng 3.14. Độ trễ trung bình với tỷ lệ nút lỗ đen tăng dần và tốc độ 20m/s ................68
Bảng 3.15. Tổng phí với tỷ lệ nút lỗ đen tăng dần và tốc độ 20m/s ..............................69



1
MỞ ĐẦU
Với hàng loạt các ưu điểm của công nghệ truyền thông không dây, các
mạng di động không dây đã được phát triển rất mạnh trong thời gian gần đây. 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. Về mặt thực tiễn, mạng MANET rất hữu ích cho các nhu cầu thiết
lập mạng khẩn cấp tại những nơi xảy ra thảm họa như: hỏa hoạn, lụt lội, động đất... hay
những nơi yêu cầu tính nhanh chóng, tạm thời như trong các trận chiến, do thám... Tuy
nhiên, chính vì những đặc điểm hoạt động không phụ thuộc vào cơ sở hạ tầng, truyền
thông trong không khí... đã khiến cho mạng MANET rất dễ bị tấn công. Những thách
thức đặt ra cho vấn đề bảo mật mạng MANET thường tập trung vào bảo mật tầng liên
kết, bảo mật định tuyến, trao đổi và quản lý khóa.
Trong phạm vi nghiên cứu của mình, luận văn sẽ trình bày một số vấn đề về an
tồn giao thức định tuyến trong mạng MANET, tấn công lỗ đen trong giao thức định
tuyến AODV, một số giải pháp để chống tấn công lỗ đen trong giao thức định tuyến
AODV mạng MANET, cụ thể là hai giải pháp IDSAODV và RAODV được trình bày ở
chương 3.
Bố cục của luận văn chia làm ba phần:
Chương 1: Tổng quan về mạng MANET
Chương 2: Tấn công kiểu lỗ đen vào giao thức định tuyến AODV và một số giải pháp
phịng chống tấn cơng lỗ đen
Chương 3: ĐÁNH GIÁ AN TOÀN GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG
MANET THÔNG QUA SỬ DỤNG CÔNG CỤ MÔ PHỎNG


2
CHƯƠNG 1: TỔNG QUAN VỀ MANG MANET

1.1. Tổng quan về mạng MANET
Mạng ad hoc di động (MANET) bao gồm các miền router kết nối lỏng với
nhau. Một mạng MANET được đặc trưng bởi một hoặc nhiều giao diện mange
MANET, các giao diện được phân biệt bởi “khả năng tiếp cận khơng đối xứng” thay
đổi theo thời gian của nó đối với các router lân cận. Các router này nhận dạng và duy
trì một cấu trúc định tuyến giữa chúng. Các router có thể giao tiếp thơng qua các kênh
vơ tuyến động với khả năng tiếp cận khơng đối xứng, có thể di động và có thể tham gia
hoặc rời khỏi mạng bất kì thời điểm nào. Để giao tiếp với nhau, các nốt mạng ad hoc
cần cấu hình giao diện mạng của nó với địa chỉ địa phương có giá trị trong khu vực
của mạng ad hoc đó.
Các nốt mạng ad hoc có thể phải cấu hình các địa chỉ tồn cầu có thể được định
tuyến, để giao tiếp với các thiết bị khác trên mạng Internet. Nhìn từ góc độ lớp IP, mạng
MANET có vai trị như một mạng multi-hop lớp 3 được tạo thành bởi các liên kết. Do
vậy mỗi nốt mạng ad hoc trong mạng MANET sẽ hoạt động như một router lớp 3 để
cung cấp kết nối với các nốt khác trong mạng. Mỗi nốt ad hoc duy trì các tuyến tới các
nốt khác trong mạng MANET và các tureen mạng tới các nốt đích ở ngồi mạng
MANET đó. Nếu đã được kết nối với mạng Internet, các mạng MANET sẽ trở thành
mạng rìa (edge network), nghĩa là biên giới của chúng được xác định bởi các router rìa
(edge-router). Do bản chất của các liên kết tạo nên mạng MANET, các nốt ad hoc trong
mange không chia sẻ truy nhập cho liên kết đơn báo hiệu đa điểm (multicast). Như vậy,
trong mạng MANET không dự trữ hay dành riêng liên kết đa điểm multicast và liên
kết quảng bá broadcast.

Hình 1.1. Minh họa mạng MANET
1.1.1 .Đặc điểm của mạng MANET
- Thiết bị tự trị đầu cuối (Autonomous terminal): Trong MANET, mỗi thiết bị
di động đầu cuối là một node tự trị. Nó có thể mạng chức năng của host và router. Bên
cạnh khả năng xử lý cơ bản của một host, các node di động này có thể chuyển đổi chức



3
năng như một router. Vì vậy, thiết bị đầu cuối và chuyển mạch là không thể phân biệt
được trong mạng MANET.
- Hoạt động phân tán (Distributed operation): Vì khơng có hệ thống mạng nền
tảng cho trung tâm kiểm soát hoạt động của mạng nên việc kiểm soát và quản lý hoạt
động của mạng được chia cho các thiết bị đầu cuối. Các node trong MANET địi hỏi
phải có sự phối hợp với nhau. Khi cần thiết các node hoạt động như một thiết bị chuyển
tiếp để thực hiện chức năng của mình như bảo mật và định tuyến.
- Định tuyến đa đường (Multihop routing): Thuật tốn định tuyến khơng dây cơ
bản có thể định tuyến một chặng và nhiều chặng dựa vào các thuộc tính liên kết khác
nhau và ciao thức định tuyến. Định tuyến đơn đường trong MANET đơn giản hơn
định tuyến đa đường ở vấn đề cấu trúc và thực hiện với chi phí thấp và ít ứng dụng. Khi
truyền các gói dữ liệu từ một nguồn của nó đến điểm trong phạm vi truyền tải trực tiếp
khơng dây, các gói dữ liệu sẽ được chuyển tiếp qua một hoặc nhiều trung gian các
nút.
- Tô-pô mạng động (Dynamic network topology): Vì các node là di động, nên
cấu trúc mạng có thể thay đổi nhanh và khơng thể biết trước, các kết nối giữa các thiết
bị đầu cuối có thể thay đổi theo thời gian. MANET sẽ thích ứng tuyến và điều kiện lan
truyền giống như mẫu di động và các node mạng di động. Các node di động trong mạng
thiết lập định tuyến động với nhau khi chúng di chuyển, hình thành mange riêng của
chúng trong khơng gian. Hơn nữa, một người dùng trong MANET có thể khơng chỉ
hoạt động trong mạng lưới di động đặc biệt, mà cịn có thể u cầu truy cập vào một
mạng cố định công cộng như Internet.
- Dao động về dung lượng liên kết (Fluctuating link capacity): Bản chất tỷ lệ bit
lỗi cao và thường xuyên biến động của kết nối không dây cần được quan tâm trong
mạng MANET. Đường đi từ đầu cuối này đến đầu cuối kia có thể được chia sẻ qua
một vài chặng. Kênh giao tiếp ở đầu cuối chịu ảnh hưởng của nhiễu, hiệu ứng đa đường,
sự giao thoa và băng thơng của nó ít hơn so với mạng có dây. Trong một vài tình huống,
truy cập của hai người dùng có thể qua nhiều liên kết khơng dây và các liên kết này có
thể khơng đồng nhất.

- Các thiết bị đầu cuối thường có khả năng chịu tải nhẹ (Light-weight
terminals): Trong hầu hết các trường hợp các node trong mạng MANET là thiết bị với


4
tốc độ xử lý của CPU thấp, bộ nhớ ít và lưu trữ điện năng ít. Vì vậy cần phải tối ưu hoá
các thuật toán và cơ chế.
1.1.2. Phân loại MANET
1.1.3. Phân loại theo giao thức
* Truyền một chặng (Single-hop):
- Mạng Manet định tuyến single-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 trunggian.
- 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.2. Single-hop
* Truyền đa chặng (Multi-hop):
- Đây là mơ hình phổ biến nhất trong mạng MANET, 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 qua các node
trung gian trong mạng.
- Để mơ hình này hoạt động một cách hồn hảo thì cần phải có giao thức định
tuyến phù hợp với mơ hình mạng MANET

Hình 1.3. Multi-hop


5
* Mobile multi-hop:

Mơ hình này cũng tương tự với mơ hình thứ hai nhưng sự khác biệt ở đâylà 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...
1.1.3.1. Phân loại theo chức năng
* Mạng MANET đẳng cấp (Flat):
Trong kiến trúc này tất cả các node có vai trị ngang hàng với nhau peerto- peer)
và các node đóng vai trị như các router định tuyến gói dữ liệu trên mạng. Trong những
mạng lớn thì cấu trúc Flat khơng tối ưu hố việc sử dụng tài ngun băng thơng của
mạng vì những thơng tin điều khiển phải truyền trên toàn bộ mạng. Tuy nhiên nó thích
hợp trong những tơ-pơ có các node di chuyển nhiều.
* Mạng MANET phân cấp (Hierarchical):
Đây là mơ hình sử dụng phổ biến nhất. Trong mơ hình này thì mạng chia thành
các miền (domain), trong mỗi domain bao gồm một hoặc nhiều cụm (cluster), mỗi
cluster bao gồm nhiều nút (node). Có hai loại nút là nút chủ hay cịn được gọi là nút cụm
trưởng (master node) và nút bình thường (nomal node).
- Master node: Là node quản trị một router có nhiệm vụ chuyển dữ liệu của các
node trong cluster đến các node trong cluster khác và ngược lại. Nói cách khác nó có
nhiệm vụ như một gateway.
- Normal node: Là các node nằm trong cùng một cluster. Nó có thể kết nối với
các node trong cluster hoặc kết nối với các cluster khác thơng qua master node.

Hình 1.4. Mơ hình mạng phân cấp
+ Với các cơ chế trên mạng sử dụng tài ngun băng thơng hiệu quả hơn vì các
thông báo điều khiển chỉ phải truyền trong phạm vi một cluster. Tuy nhiên việc quản


6
lý tính chuyển động của các node trở nên phức tạp hơn. Kiến trúc mạng phân cấp thích
hợp cho các mạng có tính chuyển động thấp.
* Mạng MANET kết hợp (Aggregate):
- Trong kiến trúc mạng này, mạng phân thành các vùng (zone) và các nút được

chia vào trong các vùng. Mỗi nút bao gồm hai mức tô-pô: tô-pô mức nút mạng (node
level) và tô-pô mức vùng (zone level; high level topology).
- Ngồi ra, mỗi nút cịn đặc trưng bởi hai ID: 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.5. Mơ hình mạng kết hợp
1.2. Vấn đề định tuyến trong mạng MANET
Trên thực tế trước khi một gói tin đến được đích, nó có thể phải được truyền
qua nhiều chặng, như vậy cần có một giao thức định tuyến để tìm đường đi từ nguồn tới
đích qua hệ thống mạng. Giao thức định tuyến có hai chức năng chính, lựa chọn các
tuyến đường cho các cặp nguồn-đích và phân phối các gói tin đến đích chính xác.
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


7
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.
1.2.1. Các thuật tốn định tuyến truyền thống
Để tìm đường đi cho các gói tin qua hệ thống các router trong mạng, các giao
thức định tuyến truyền thống thường sử dụng giải thuật véc tơ khoảng cách (Distance
Vector Routing - DV) hoặc trạng thái liên kết (Link State Routing – LS). Thuật tốn

Distance Vector cịn được gọi là thuật toán Bellman-Ford, được dùng trong mạng
ARPANET lúc mới ra đời và được sử dụng trong mạng Internet với tên gọi là RIP
(Routing Information Protocol). Thuật toán Link State được sử dụng trong giao
thức OSPF (Open Shortest Path First) của Internet [12].
Trong giải thuật Distance Vector, mỗi router quảng bá một cách định kỳ tới các
hàng xóm thơng tin khoảng cách từ nó tới tất cả các router khác . Các router dựa trên
thơng tin nhận được này tính tốn đường đi tốt nhất tới các router khác. Bằng việc so
sánh các khoảng cách từ mỗi hàng xóm tới một đích nào đó, router có thể quyết định
hàng xóm nào sẽ là chặng tiếp theo trong đường đi tới đích để đường đi là tối ưu nhất.
Bảng định tuyến tại các router do đó lưu trữ các thơng tin về các đích trong mạng (các
router khác trong mạng), chặng tiếp theo và khoảng cách tới đích. Vấn đề với Distance
Vector là khả năng hội tụ chậm, và sự hình thành các vòng lặp định tuyến.
Trong giải thuật Link State, mỗi router duy trì một thơng tin đầy đủ về cấu hình
của toàn bộ mạng. Để làm được điều này, mỗi router quảng bá định kỳ các gói tin LSP
(Link State Packet) có chứa thơng tin về các hàng xóm và giá tới mỗi hàng xóm.
Các t hơng tin này sẽ được truyền tới tất cả các router trong mạng. Từ thông tin về
giá của các liên kết trong toàn bộ mạng, các router có thể tính tốn đường đi ngắn nhất
tới các đích có thể.
Việc sử dụng các giao thức định tuyến truyền thống trong mạng MANET với
việc xem mỗi nút như các router dẫn tới một loạt các vấn đề:
- Tiêu tốn băng thông mạng và năng lượng nguồn nuôi cho các cập nhật định kỳ.
- Các nút bị phá vỡ chế độ tiết kiệm năng lượng do liên tục phải nhận và gửi
thơng tin.
- Mạng có thể bị q tải với các thông tin cập nhật khi số nút trong mạng tăng,
do đó làm giảm tính khả mở của mạng.
- Các đường đi dư thừa được tích luỹ một cách không cần thiết.


8
- Hệ thống khó có thể phản hồi đủ nhanh với các thay đổi thường xuyên trong

cấu hình mạng.
1.2.2. Bài tốn định tuyến mạng MANET
Có thể thấy, các giao thức định tuyến truyền thống đặt q nhiều tính tốn và
truyền thông với các nút di động trong mạng MANET. Thêm vào đó, u cầu về tính
hội tụ của các giao thức sẽ khó có thể thực hiện trong mạng MANET vớitính chất động
của mơi trường. Mặc dù tốc độ hội tụ có thể cải thiện bằng cách gửi các thơng điệp cập
nhật thường xuyên hơn nhưng điều này sẽ làm tiêu tốn thêm băng thông và năng lượng
nguồn nuôi. Hơn nữa, khi cấu hình mạng ít thay đổi việc gửi thường xuyên các cập nhật
sẽ rất lãng phí.
Do vậy, các giao thức định tuyến trong mạng MANET cần giảm tổng phí cho
việc định tuyến, thích ứng nhanh và tự động với các điều kiện thay đổi của mạng. Giao
thức phải đảm bảo thực hiện hiệu quả trong môi trường khi các nút đứng yên và băng
thông là không giới hạn và đủ hiệu quả khi băng thông tồn tại giữa các nút thấp và mức
độ di chuyển và thay đổi cấu hình cao.
Do đó, thiết kế của các giao thức định tuyến trong mạng MANET thường xem
xét một số các yếu tố sau đây:
- Hoạt động phân tán: Cách tiếp cận tập trung sẽ thất bại do sẽ tốn rất nhiều
thời gian để tập hợp một trạng thái hiện tại và phát tán lại nó. Trong thời gian đó, cấu
hình có thể đã có các thay đổi khác.
- Khơng có lặp định tuyến: Hiện tượng xảy ra khi một phần nhỏ các gói tin quay
vịng trong mạng trong một khoảng thời gian nào đó. Một giải pháp có thể là sử dụng
giá trị thời gian quá hạn.
- Tính toán đường dựa trên yêu cầu: Thay thế việc duy trì định tuyến tới tất cả
các nút tại tất cả các thời điểm bằng việc thích ứng với dạng truyền thơng. Mục đích là
tận dụng hiệu quả năng lượng và băng thông, mặc dù độ trễ tăng lên do sự phát hiện
đường.
- Tính tốn đường trước: Khi độ trễ có vai trị quan trọng, và băng thông, các tài
nguyên năng lượng cho phép, việc tính toán đường trước sẽ giảm độ trễ phân phát.
- Bảo mật: Giao thức định tuyến mạng MANET có khả năng bị tấn cơng dễ dàng
ở một số dạng như xâm nhập truyền thông, phát lại, thay đổi các tiêu đề gói tin, điều



9
hướng các thơng điệp định tuyến. Do vậy, cần có các phương pháp bảo mật thích hợp
để ngăn chặn việc sửa đổi hoạt động của giao thức.
- Hoạt động nghỉ: Giao thức định tuyến cần cung cấp khả năng đáp ứng yêu cầu
bảo tồn năng lượng của các nút khi có thể.
- Hỗ trợ liên kết đơn hướng: hỗ trợ trường hợp khi các liên kết đơn hướng tồn tại
trong mạng MANET.
1.2.3 .Các kỹ thuật định tuyến mạng MANET
Các kỹ thuật định tuyến khác nhau được áp dụng trong các giao thức định tuyến
MANET có thể được tổng kết và trình bày như dưới đây.
1.2.4. Định tuyến Link State và Distance Vector
Một số các giao thức định tuyến mạng MANET dựa trên các kỹ thuật định tuyến
trong mạng có dây Link State và Distance Vector để xây dựng các giải thuật thích
ứng với mạng MANET. Vấn đề với định tuyến Link State là tổng phí định tuyến tăng
cao khi mạng có nhiều thay đổi. Vấn đề với định tuyến Distance Vector là hội tụ chậm
và có khuynh hướng tạo ra các vòng lặp định tuyến. Các giao thức định tuyến MANET
tìm cách khắc phục các hạn chế này bằng một số các sửa đổi. Ví dụ về các giao thức là
DSDV, OLSR,…
1.2. 5. Định tuyến chủ ứng và định tuyến phản ứng
- Định tuyến chủ ứng (Proactive): Là phương pháp định tuyến của các giao thức
truyền thống. Đường tới tất cả các đích được tính tốn trước. Các thơng tin định tuyến
được cập nhật định kỳ hoặc bất cứ khi nào cấu hình mạng thay đổi. Ưu điểm của phương
pháp là độ trễ phát gói tin thấp. Tuy nhiên, một số đường không cần dùng đến và việc
truyền các thông điệp định kỳ tiêu tốn băng thông khi mạng thay đổi nhanh.
- Định tuyến phản ứng (Reactive): Là phương pháp định tuyến theo yêu cầu.
Đường tới đích không được tính toán trước và chỉ được xác định khi cần đến. Quá trình
phát hiện liên kết bị hỏng và xây dựng lại đường được gọi là quá trình duy trì đường.
Ưu điểm của định tuyến phản ứng là hạn chế được băng thông do chỉ cần đường tới

các đích cần thiết và loại bỏ các cập nhật định kỳ. Tuy nhiên, vấn đề với phương pháp
là độ trễ lớn trước khi phát do việc phát hiện đường.
1.2.6. Cập nhật định kỳ và cập nhật theo sự kiện
- Cập nhật định kỳ thực hiện bằng việc phát các gói tin định tuyến một cách định
kỳ. Kỹ thuật này làm đơn giản hóa các giao thức và cho phép các nút học được về cấu


10
hình và trạng thái của tồn bộ mạng. Tuy nhiên, giá trị quãng thời gian cập nhật là một
tham số quan trọng.
- Cập nhật theo sự kiện diễn ra khi có sự kiện xảy ra trong mạng như liên kết
hỏng hoặc liên kết mới xuất hiện. Khi đó, gói tin cập nhật sẽ được quảng bá và trạng
thái cập nhật được truyền trong toàn bộ mạng. Nhưng khi mạng thay đổi nhanh, số
lượng gói tin cập nhật sẽ lớn và có thể gây ra các dao động về đường.
1.2.7. Cấu trúc phẳng và cấu trúc phân cấp
Trong cấu trúc phẳng, tất cả các nút trong mạng ở cùng mức với nhau và có chức
năng định tuyến như nhau. Cấu trúc phẳng đơn giản và hiệu quả với cácmạng nhỏ. Khi
mạng trở lên lớn, lượng thông tin định tuyến cũng sẽ lớn và sẽ mất nhiều thời gian để
thông tin định tuyến có thể tới được các nút ở xa.
Đối với các mạng lớn, định tuyến phân cấp được áp dụng để giải quyết vấn đề
trên. Trong định tuyến phân cấp, các nút được tổ chức động thành các phân hoạch gọi
là cụm (cluster), sau đó các cụm được kết hợp lại thành các phân hoạch lớn hơn gọi là
các siêu cụm (supercluster)... Việc tổ chức mạng thành các cụm giúp duy trì cấu hình
mạng tương đối bền vững. Tính chất động cao của các thành viên và cấu hình mạng
được giới hạn trong cụm. Chỉ có thơng tin mức cao, ổn định như mức cụm hoặc siêu
cụm được truyền qua khoảng cách xa do đó việc truyền các thơng tin điều khiển hay
tổng phí định tuyến được giảm đáng kể.
1.2.8. Tính tốn phi tập trung và tính tốn phân tán
- Trong giao thức dựa trên tính tốn phi tập trung, mọi nút trong mạng duy trì
thơng tin tồn cục hồn chỉnh về cấu hình mạng để tính tốn các đường đi ngay khi cần.

Tính toán đường trong Link State là ví dụ của tính tốn phi tập trung.
- Trong giao thức dựa trên tính tốn phân tán, mọi nút trong mạng chỉ duy trì
thơng tin bộ phận hoặc cục bộ về cấu hình mạng. Khi một đường cần được tính tốn,
nhiều nút sẽ phối hợp để tính tốn đường. Tính toán đường trong Distance Vector
và phát hiện đường trong các giao thức theo yêu cầu thuộc vào tiếp cận này.
1.2.9. Định tuyến nguồn và định tuyến theo chặng
- Trong định tuyến nguồn, nút nguồn đặt toàn bộ đường trong tiêu đề của gói tin
dữ liệu, các nút trung gian chuyển tiếp các gói tin theo đường trong tiêu đề. Các giao
thức này loại bỏ nhu cầu quảng cáo đường định kỳ và các gói tin phát hiện hàng xóm.


11
Vấn đề lớn nhất với định tuyến nguồn là khi mạng lớn và đường đi dài, việc đặt toàn bộ
đường trong tiêu đề gói tin sẽ làm lãng phí băng thông.
- Trong định tuyến theo chặng, đường tới đích được phân tán theo các chặng.
Khi một nút nhận được gói tin cần chuyển tới đích, nút chuyển tiếp gói tin theo chặng
tiếp theo tương ứng với đích. Vấn đề là tất cả các nút cần duy trì thơng tin định tuyến và
có khả năng hình thành lặp định tuyến.
1.2.9.1. Đơn đường và đa đường
Một số giao thức định tuyến tìm một đường duy nhất từ nguồn tới đích. Do đó,
giao thức trở lên đơn giản và tiết kiệm được không gian lưu trữ. Tuy nhiên, một số
giao thức khác lại tim nhiều đườn. Mục triêu của các
giao thức này là sự tin cậy và mạnh mẽ
1.2.9.2 Các giao thức định tuyến trong mạng MANET
Với các kỹ thuật định tuyến được trình bày có thể nhiều cách phân loại các
giao thức định tuyến mạng MANET như dựa trên cấa trúc ( phẳng hay phân cấp), thơng
tin trạng thái (tồn cục , phải tập trung hay phân tán , sựp lập lịch tính tốn đường (chủ
ứng hay phản ứng ) [13].

Hình 1.6. Phân loại giao thức định tuyến trong mạng MANET


1.2.9.3. Destination-Sequence Distance Vector (DSDV)
DSDV [14] là giao thức định tuyến chủ ứng dựa trên véc tơ khoảng cách theo
chặng. Mỗi nút trong mạng duy trì một bảng định tuyến có chứa chặng tiếp theo và số
chặng tới mỗi đích trong mạng. Để giữ các bảng định tuyên được cập nhật, DSDV yêu


12
cầu mỗi nút phát quảng bá định kỳ các cấp nhật định tuyến tới các hàng xóm và phát
ngay c ác cập nhật khi có các thay đổi quan trọng xảy ra trong mạng.
Để tránh lặp định tuyến DSDV sử dụng số thứ tự gắn với mỗi đường. Số thứ tự
cho thấy độ mới của đướng .Đườg có số thứ tự cao hơn được xem là tốt hơn. Tuy
nhiên, hai đường có cùng Số thứ tụ nhưng đường nào độ đo ( mettic) tốt hơn thì sẽ tốt
hơn. Số thứ tự này được khởi tạo ban đầu bởi nút đíct . Mỗi nút trong mạng quảng cáo
bằng việc tăng đều đặn số thứ tự chẵn của mình . Số thứ tự được tăng lên một khi mộ
nút phát hiện đường tới đích có liên kết hỏng khi khơng nhận được các cập nhật định
kỳ .Trong quảng cáo đường sua , nút phát hiện liên kết hỏng sẽ quảng cáo đường tới
đích có số chặng vơ hạn và tăng thứ tự đường.
Ngoài ra, để tránh sự bụng nổ các cập nhật định tuyến tại các thời điểm cấu hình
mạng thay đổi nhanh, DSDV cũng áp dụng cơ chế hãm các cập nhật tức thời khi có
các thay đổi xảy ra trong mạng. Bằng việc ghi nhận các quảng thời gian xảy ra những
thay đổi về đường, DSDV làm trễ các cập nhật tức thời theo thời gian đó.
Nhằm làm giảm hơn nữa lượng thơng tin trong các gói tin cập nhật, DSDV
sử dụng hai loại thông điệp cập nhật là: cập nhật đầy đủ (full dump) và cập nhật bổ
sung (incremental dump). Cập nhật đầy đủ mang tất cả thông tin định tuyến có trong
nút và cập nhật bổ sung chỉ mạng các thông tin về những thay đổi từ lần cập nhật đầy
đủ gần nhất. Để làm được điều này, DSDV lưu trữ hai bảng khác nhau, một dùng để
chuyển tiếp các gói tin, một để phát các gói tin cập nhật bổ sung. Cập nhật đầy đủ được
truyền tương đối ít thường xun khi ít có sự di chuyển của các nú mạng. Khi có các
thay đổi trong mạng nút thông thường chỉ phát cập nhật bổ sung.

1.2.9.4. Ad hoc On-demand Distance Vector Routing (AODV)
AODV [2] là giao thức dựa trên thuật toán vector khoảng cách. Giao thức AODV
tối thiểu hoá số bản tin quảng bá cần thiết bằng cách tạo ra các tuyến trên cơ sở theo
yêu cầu.


13

Hình 1.7. Quá trình tìm đường trong AODV
Quá trìnhtìm đường được khởi tạo bất cứ khi nào có một nút cần truyền tin với
một nút khác trong mạng mà không tìm thấy tuyến đường liên kết tới đích trong bảng
định tuyến. Nó phát quảng bá một gói u cầu tìm đường (RREQ) đến các nút lân
cận. Các nút lân cận này sau đó sẽ chuyển tiếp gói yêu cầu đến nút lân cận khác của
chúng. Quá trình cứ tiếp tục như thế cho đến khi có một nút trung gian nào đó xác định
được một tuyến đủ tươi”để đạt đến đích hoặc gói tin tìm đường được tìm đến đích.
AODV sử dụng số thứ tự đích để đảm bảo rằng tất cả các tuyến không bị lặp và chứa
hầu hết thơng tin tuyến hiện tại. Mỗi nút duy trì số tuần tự của nó cùng với ID quảng
bá. ID quảng bá được tăng lên mỗi khi nút khởi đầu một RREQ và cùng với địa chỉ IP
của nút, xác

định duy nhất một RREQ. Cùng với số tuần tự và ID quảng bá, nút

nguồn bao gồm trong RREQ hầu hết số tuần tự hiện tại của đích mà nó có.Các nút
trung gian trả lời RREQ chỉ khi chúng có một tuyến đến đích mà số tuần tự đích lớn hơn
hoặc bằng số tuần tự chứa trong RREQ.
Trong quá trình chuyển tiếp RREQ, các nút trung gian ghi vào bảng định tuyến
của chúng địa chỉ của các nút lân cận khi nhận được bản sao đầu tiên của gói quảng bá,
từ đó thiết lập được một đường dẫn theo thời gian. Nếu các bản sao của cùng một RREQ
được nhận sau đó tại một nút, các gói tin này sẽ bị huỷ. Khi RREQ đã đạt đến đích hay
một nút trung gian với tuyến“đủ tươi, nút đích (hoặc nút trung gian) đáp ứng lại yêu

cầu RREQ bằng cách phát unicast một gói tin trả lời (RREP) ngược trở về nút lân cận
mà từ đó nó nhận được RREQ. Khi RREP được định tuyến ngược theo đường dẫn, các
nút trên đường dẫn đó thiết lập các thực thể tuyến chuyển tiếp trong Bảng định tuyến
của chỉ nút mà nó nhận được RREP. Các thực thể tuyến chuyển tiếp này chỉ thị tuyến
chuyển tiếp. Cùng với mỗi thực thể tuyến là một bộ định thời tuyến có nhiệm vụ xố
các thực thể nếu nó không được sử dụng trong một thời hạn xác định.


14
Trong giao thức AODV, các tuyến được duy trì với điều kiện như sau:
Nếu nút nguồn di chuyển, nó có thể khởi tạo lại giao thức phát hiện tuyến để tìm ra tuyến
mới tới đích. Nếu nút dọc theo tuyến di chuyển, hàng xóm ở hướng nút nguồn sẽ thơng
báo về di chuyển và truyền đi thông điệp thông báo lỗi liên kết tới mỗi hàng xóm mà
hướng về nút nguồn để xóa khỏi phần của tuyến, cơng việc này được tiếp diễn cho tới
khi tới được nút nguồn. Nút nguồn sau đó có thể chọn để khởi tạo lại việc phát hiện
tuyến cho mỗi đích nếu tuyến vẫn còn được yêu cầu sử dụng.
AODV sử dụng các thông điệp HELLO được quảng bá định kỳ tới các hàng
xóm. Thơng điệp HELLO cho biết về sự tồn tại của nút và liên kết với nút vẫn hoạt
động. Khi thông điệp HELLO khơng đến từ một hàng xóm trước đó, nút đánh dấu liên
kết tới hàng xóm đó là hỏng và thông báo cho các nút bị ảnh hưởng bằng việc gửi thông
báo lỗi đường Route ERRor (RERR).
Giao thức AODV không hỗ trợ bất kỳ cơ chế an ninh nào để chống lại các cuộc
tấn cơng. Điểm yếu chính của giao thức AODV [22] là:
- Kẻ tấn cơng có thể đóng giả một nút nguồn S bằng cách phát quảng bá gói
RREQ với địa chỉ IP như là địa chỉ của nút nguồn S.
- Kẻ tấn cơng có thể giả làm nút đích D bằng cách phát quảng bá gói RREP
với địa chỉ như là địa chỉ của nút đích D.
- Kẻ tấn cơng có thể giảm giá trị trường hop count trong RREQ và RREP để các
nút nguồn cho rằng nó có tuyến đường đi ngắn nhất tới đích.
- Kẻ tấn cơng có thể tăng giá trị trường sequence number trong RREQ và RREP

làm các nút nguồn cho rằng nó có tuyến đường đi mới nhất đi tới đích.
- Kẻ tấn cơng có thể phát ra gói tin thơng báo tuyến đường bị lỗi làm sai lệch
thông tin bảng định tuyến trong mạng.
1.2.9. 5. Dynamic Source Routing (DSR)
Giao thức DSR [15] là một giao thức định tuyến đơn giản và hiệu quả được
thiết kế riêng cho việc sử dụng trong các mạng ad hoc không dây đa chặng với các nút
di động. Sử dụng DSR, mange hoàn toàn tự tổ chức và tự cấu hình, khơng cần cơ sở
hạ tầng mange sẵn có hoặc quản trị trung tâm. Các nút mạng hợp tác để chuyển tiếp các
gói tin cho nhau từ đó cho phép giao tiếp qua nhiều “chặng” giữa những nút
không trực tiếp nằm trong phạm vi truyền dẫn không dây của nút khác. Khi các nút
trong mạng lưới di chuyển xung quanh hoặc gia nhập hoặc rời khỏi mạng, hoặc các


15
điều kiện truyền dẫn không dây như các nguồn nhiễu thay đổi, thì tất cả định tuyến
được tự động xác định và duy trì bởi các giao thức định tuyến DSR. Vì số lượng các
chặng trung gian cần để đến được đích đến bất kỳ có thể thay đổi bất cứ khi nào, nên
tơ-pơ mạng có thể được thay đổi khá đa dạng và nhanh chóng.
Giao thức DSR là giao thức phản ứng dựa trên định tuyến nguồn xuất phát từ
nút nguồn, nó cho phép các nút tìm kiếm tự động một tuyến đường từ nguồn qua nhiều
chặng đến đích bất kỳ trong mạng ad hoc. Mỗi gói tin dữ liệu gửi đi mang trong tiêu đề
của nó danh sách được xếp thứ tự đầy đủ các nút mà nó phải đi qua, cho phép định
tuyến gói tin ở các nút trung gian có thể thực hiện nhanh chóng khơng có vịng lặp và
tránh u cầu phải cập nhật thơng tin định tuyến tại các nút trung gian mà các gói tin
được chuyển tiếp. Bằng cách thêm tuyến đường nguồn trong header của mỗi gói dữ
liệu, các nút đang chuyển tiếp hoặc đang nghe bất kỳ gói tin nào trong các gói tin đó có
thể dễ dàng lưu giữ thơng tin định tuyến để sử dụng trong tương lai.
Giao thức DSR gồm có hai cơ chế làm việc cùng nhau cho phép tìm kiếm và duy
trì các tuyến đường nguồn trong mạng ad hoc:
+ Route discovery (Cơ chế tìm kiếm tuyến đường): Là cơ chế mà theo đó một

nút nguồn S có nhu cầu gửi một gói tin đến một nút đích D có được một tuyến đường
từ nguồn đến nút đích D. Route discovery được sử dụng chỉ khi S cố gắng gửi một gói
tin đến D mà khơng thực sự biết một tuyến đường đến D.
Route discovery hoạt động như sau: Mỗi nút duy trì một bộ nhớ được gọi là route
cache, có chứa các tuyến đường đi đã biết. Khi tuyến đường được cần đến khơng có
trong route cache, Route discovery được khởi tạo bằng việc phát gói tin yêu cầu đường
Route Request. Khi một nút nhận được gói tin u cầu đường, nút tìm trong route
cache đường tới đích được yêu cầu. Nếu trong route cache khơng tìm thấy đường, nút
chuyển tiếp gói tin u cầu đường cho các hàng xóm sau khi bổ sung địa chỉ vào thứ
tự các chặng được lưu trong gói tin yêu cầu đường. Gói tin yêu cầu đường được truyền
qua mạng cho tới khi đến đích hoặc nút có đường đi tới đích. Nếu đường được tìm
thấy, gói tin trả lời (Route Reply) có chứa thứ tự các chặng tới đích được gửi trở lại
nguồn.