BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGÔ ĐỨC HẢO
TÌM HIỂU PHƯƠNG PHÁP NÂNG CAO HIỆU NĂNG
CỦA GIAO THỨC ZRP VỚI BL VÀ SD
TRONG MẠNG MANET
CHUYÊN NGÀNH:
MÃ SỐ:
KHOA HỌC MÁY TÍNH
60.48.01
LUẬN VĂN THẠC SĨ KHOA HỌC
CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS. VÕ THANH TÚ
Huế, 2013
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của
riêng tôi. Các số liệu và kết quả nghiên cứu nêu trong luận văn
là trung thực, được các đồng tác giả cho phép sử dụng và chưa
từng được công bố trong bất kỳ một công trình nào khác.
Học viên
Ngô Đức Hảo

Trước tiên, tôi xin được bày tỏ lòng biết ơn chân thành và
sâu sắc nhất đến thầy giáo hướng dẫn Phó giáo sư, Tiến sĩ Võ
Thanh Tú, người đã tận tình dẫn dắt và tạo mọi điều kiện tốt
nhất để tôi có thể hoàn thành luận văn này.
Tôi cũng xin chân thành cảm ơn các thầy cô giáo khoa
Công nghệ thông tin trường Đại học Khoa học – Đại học Huế,
những người đã trực tiếp giảng dạy, giúp đỡ và tạo mọi điều

kiện thuận lợi cho tôi trong quá trình học tập và nghiên cứu.
Xin được cảm ơn trường Cao đẳng sư phạm Thừa Thiên
Huế, Khoa Ngoại ngữ - Tin học đã tạo mọi điều kiện để tôi
được đi học và hoàn thành tốt khoá học.
Xin chân thành cảm ơn gia đình, các anh chị lớp cao học
Khoa học máy tính khoá 2011 và các bạn đồng nghiệp đã luôn
bên cạnh, động viên, khuyến khích tôi trong suốt thời gian
học tập và thực hiện đề tài.
Xin chân thành cảm ơn!
Học viên
Ngô Đức Hảo
MỤC LỤC
Trang
Trang phụ bìa
Lời cam đoan
Lời cảm ơn
Mục lục
Danh mục viết tắt
Danh mục các bảng
Danh mục các hình vẽ, đồ thị
MỞ ĐẦU 1
1. Tính cấp thiết của đề tài 1
2. Mục đích nghiên cứu đề tài 2
3. Phương pháp nghiên cứu 2
4. Ý nghĩa khoa học và thực tiễn của đề tài 3
5. Cấu trúc của luận văn 3
CHƯƠNG 1 5
TỔNG QUAN VỀ MẠNG MANET 5
1.1 Giới thiệu về mạng MANET 5
1.1.1 Mạng MANET 5

1.1.2 Lịch sử phát triển: 5
1.1.3 Đặc điểm của mạng MANET: 6
1.2 Phân loại mạng MANET 8
1.2.1 Phân loại theo giao thức: 8
1.2.2 Phân loại theo chức năng của nút: 8
1.3 Các thuật toán định tuyến: 9
1.3.1 Thuật toán vector khoảng cách (Distance Vector): 9
1.3.2 Thuật toán trạng thái liên kết (Link State): 11
1.3.3 So sánh các thuật toán định tuyến: 12
1.4 Các giao thức định tuyến trên mạng MANET: 13
1.4.1 Giao thức định tuyến theo bảng ghi (Table – driven Routing Protocols)
14
1.4.2 Giao thức định tuyến theo yêu cầu (On – Demand Routing Protocol). .15
1.4.3 Giao thức định tuyến lai ghép (HybridRouting Protocols) 15
1.5 Ứng dụng của mạng MANET 17
1.6 Kết luận chương 1 19
CHƯƠNG 2 20
TÌM HIỀU PHƯƠNG PHÁP NÂNG CAO HIỆU NĂNG CỦA GIAO
THỨC ZRP VỚI BL VÀ SD TRONG MẠNG MANET 20
2.1 Giao thức định tuyến lai ZRP (Zone Routing Protocol) 20
2.1.1 Phân vùng trong ZRP 21
2.1.2 Kiến trúc của ZRP 23
2.1.3 Cơ chế định tuyến 25
2.1.3.1 Định tuyến nội vùng IARP 28
2.1.3.2 Định tuyến liên vùng IERP 29
2.1.3.3 Giải pháp quảng bá biên BRP 30
2.1.4 Các cơ chế điều khiển truy vấn 33
2.1.4.1 Cơ chế phát hiện truy vấn (Query Dectection) 34
2.1.4.2 Cơ chế kết thúc sớm ET (Early Termination) 36
2.1.4.3 Cơ chế làm trễ xử lý truy vấn ngẫu nhiên RQPD (Random Query

Processing Delay) 38
2.1.5 Bán kính vùng định tuyến 40
2.1.6 Ví dụ minh họa hoạt động của ZRP 41
2.2 Khám phá dịch vụ tại tầng định tuyến 43
2.3 Bộ lọc Bloom (BL) 44
2.4 ZRP và cơ chế hổ trợ khám phá cho dịch vụ sử dụng BL và SD 46
2.5 Kết luận chương 2 50
CHƯƠNG 3 51
ĐÁNH GIÁ HIỆU NĂNG CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN
TRÊN MẠNG MANET 51
3.1 Giới thiệu môi trường mô phỏng NS 51
3.1.1 Tổng quan về NS2 51
3.1.2 Kiến trúc của NS2 52
3.2 Mô phỏng mạng không dây trong môi trường NS 54
3.3 Mô phỏng giao thức định tuyến lai ZRP và SD-ZRP 54
3.4 Phân tích mô phỏng 55
3.4.1 Sự tác động của số lượng nút mạng đến hiệu năng của giao thức ZRP. 55
3.4.2 Sự tác động của vận tốc di chuyển của nút đến hiệu năng của giao thức
ZRP 58
3.4.3 Sự tác động của số lượng nút mạng đến hiệu năng của giao thức SD-
ZRP 59
3.4.4 So sánh kết quả mô phỏng giữa giao thức ZRP và SD-ZRP 60
3.5 Kết luận chương 3 62
KẾT LUẬN 64
1. Kết quả đạt được: 64
2. Hướng phát triển: 64
TÀI LIỆU THAM KHẢO 65
PHỤ LỤC
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT
AODV Ad-hoc On Demand Distance Vector

BL Bloom Filter
BRP Bordercast Resolution Protocol
DSDV Destination Sequenced Distance Vector
DSR Dynamic Source Routing
ET
Early Termination
HARP Hybrid Ad hoc Routing Protocol
IARP Intra-zone Routing Protocol
ID Identify
IERP Inter-zone Routing Protocol
MAC Medium Access Control
MANET Mobile Ad-hoc Network
NDP Neighbor Discovery Protocol
NS2 Network Simulation 2
OLSR Optimized Link State Routing
QD
Query Detection
RQPD
Random Query Processing Delay
SD Service Discovery
TORA Temporally Ordered Routing Algorithm
TTL Time To Live
UUID Unique Universal Identifiers
WRP Wireless Routing Protocol
ZRP Zone Routing Protocol
DANH MỤC CÁC BẢNG
Số hiệu bảng Tên bảng Trang
2.1
Tổng hợp quá trình quảng bá biên Error:
Referenc

e source
not
found
3.1
Kết quả mô phỏng về sự tác động của số lượng nút
mạng đến hiệu năng của giao thức ZRP
Error:
Referenc
e source
not
found
3.2
Kết quả mô phỏng về sự tác động của vận tốc di chuyển
của nút đến hiệu năng của giao thức ZRP
Error:
Referenc
e source
not
found
3.3
Kết quả mô phỏng về sự tác động của số lượng nút
mạng đến hiệu năng của giao thức SD-ZRP
Error:
Referenc
e source
not
found
3.4
Kết quả mô phỏng của giao thức ZRP và SD-ZRP Error:
Referenc

e source
not
found
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Số hiệu hình vẽ Tên hình vẽ Trang
1.1
Phân loại giao thức định tuyến trong mạng Ad Hoc Error:
Referen
ce
source
not
found
2.1
Ví dụ vùng định tuyến với r = 2 Error:
Referen
ce
source
not
found
2.2
Kiến trúc của ZRP Error:
Referen
ce
source
not
found
2.3
Cơ chế định tuyến ZRP Error:
Referen
ce

source
not
found
2.4 Sơ đồ thuật toán của giao thức ZRP Error:
Referen
ce
source
Số hiệu hình vẽ Tên hình vẽ Trang
2.5
Ví dụ giải pháp quảng bá biên BRP Error:
Referen
ce
source
not
found
2.6
Cơ chế Phát hiện truy vấn (QD1/QD2) Error:
Referen
ce
source
not
found
2.7
Cơ chế Kết thúc sớm ET Error:
Referen
ce
source
not
found
2.8

RQPD Error:
Referen
ce
source
not
found
2.9
Minh họa hoạt động của giao thức ZRP Error:
Referen
ce
source
Số hiệu hình vẽ Tên hình vẽ Trang
2.10
Bộ lọc Bloom với hàm băm k = 4 Error:
Referen
ce
source
not
found
2.11 SvcCache và IARP 47
2.12
Định dạng gói tin IARP Error:
Referen
ce
source
not
found
3.1
Tổng quan về NS dưới góc độ người dùng Error:
Referen

ce
source
not
found
3.2
Mô hình mô phỏng mạng ZRP đang hoạt động Error:
Referen
ce
source
not
found
3.3 Biểu đồ kết quả mô phỏng về sự tác động của số lượng nút
mạng đến hiệu năng của giao thức ZRP
Error:
Referen
ce
Số hiệu hình vẽ Tên hình vẽ Trang
3.4
Biểu đồ kết quả mô phỏng về sự tác động của vận tốc di chuyển
của nút đến hiệu năng của giao thức ZRP
Error:
Referen
ce
source
not
found
3.5
Biểu đồ kết quả mô phỏng về sự tác động của số lượng nút
mạng đến hiệu năng của giao thức SD-ZRP
Error:

Referen
ce
source
not
found
3.6
So sánh kết quả mô phỏng của giao thức ZRP và SD-ZRP Error:
Referen
ce
source
not
found
MỞ ĐẦU
1. Tính cấp thiết của đề tài
Ngày nay, chúng ta đang sống trong thời đại bùng nổ thông tin, nhiều
công nghệ mới ra đời và được ứng dụng vào trong cuộc sống, đặc biệt là trong
lĩnh vực công nghệ thông tin và truyền thông. Các hệ thống truyền thông đã
phủ rộng khắp trên thế giới làm cho con người ở khắp nơi có thể thông tin
được với nhau mọi lúc mọi nơi.
Ban đầu, các thiết bị truyền thông được kết nối với nhau thông qua hệ
thống mạng có dây (wired). Hệ thống mạng có dây đã ra đời khá lâu và có
nhiều tác động to lớn đến sự phát triển của xã hội. Tuy nhiên, với sự phát
triển mạnh mẽ của khoa học công nghệ, các hệ thống mạng có dây dần bộc lộ
các hạn chế. Bên cạnh đó, sự ra đời và phát triển mạnh mẽ của các thiết bị di
động cá nhân như laptop, smartphone, tablet,… làm nảy sinh nhu cầu kết nối
các thiết bị này. Hệ thống mạng có dây không thể đáp ứng được nhu cầu này
và không phát huy hết được những ưu điểm của các thiết bị di động. Và sự ra
đời của mạng không dây (wireless) đã đáp ứng được nhu cầu kết nối của các
thiết bị di động.
Các thiết bị di động ngày càng phát triển mạnh mẽ, và nhu cầu kết nối

giữa các thiết bị này cũng ngày càng đòi hỏi cao hơn về tốc độ và khả năng di
chuyển trong khi kết nối mạng. Mạng tùy biến di động – MANET (Mobile
Ad-hoc Network) là một trong những công nghệ vượt trội đáp ứng được nhu
cầu đó nhờ khả năng hoạt động không phụ thuộc vào cơ sở hạ tầng cố định,
chi phí hoạt động thấp, triển khai nhanh và có tính di động cao. Mạng
MANET là một mạng bao gồm các thiết bị di động kết nối ngang hàng hình
thành nên một mạng mà không cần sự trợ giúp của các thiết bị trung tâm hay
cơ sở hạ tầng cố định. Mỗi nút trong mạng MANET vừa là thiết bị thu, vừa là
thiết bị phát. Đồng thời, mỗi nút đều có khả năng di chuyển về mọi hướng
1
theo các tốc độ khác nhau làm cho topo mạng thay đổi liên tục. Vấn đề đáng
quan tâm của mạng MANET là định tuyến. Các giao thức định tuyến truyền
thống không phù hợp với mạng MANET mà cần phải được thay thế bằng một
hệ thống các giao thức định tuyến mới. Hệ thống các giao thức định tuyến
trên mạng MANET được chia thành 3 nhóm chính: định tuyến chủ động
(Proactive), định tuyến bị động (Reactive) và định tuyến lai ghép (Hybrid).
Tuy nhiên, hiện nay mạng MANET vẫn chưa được ứng dụng rộng rãi và vẫn
đang được nghiên cứu nhằm cải tiến hơn nữa các giao thức định tuyến để đạt
được hiệu quả hoạt động tốt hơn.
Vì vậy, luận văn này tôi tiếp tục nghiên về vấn đề định tuyến trên mạng
MANET. Mỗi giao thức định tuyến trên mạng MANET có những đặc điểm
riêng và phù hợp với một mô hình mạng nhất định. Nội dung chính của luận
văn sẽ tìm hiểu và nghiên cứu nâng cao phương pháp hiệu năng của giao thức
trên mạng Manet. Các giao thức định tuyến trong ZRP là sự kết hợp giữa giao
thức định tuyến chủ động và giao thức định bị động. Giao thức định tuyến
ZRP được đề xuất để kết hợp các đặc tính ưu điểm của giao thức định tuyến
chủ động và bị động.
2. Mục đích nghiên cứu đề tài
Nghiên cứu, tìm hiểu một số giao thức định tuyến lai ghép trên mạng
MANET.

So sánh, đánh giá hiệu năng của giao thức định tuyến lai ghép tiêu biểu
dựa trên phương pháp mô phỏng bằng NS2. Từ đó xác định môi trường áp
dụng tốt cho các giao thức để đảm bảo truyền thông tin cậy và hiệu quả.
3. Phương pháp nghiên cứu
Tìm kiếm, thu thập, tổng hợp tài liệu, nghiên cứu lý thuyết làm cơ sở để
đưa ra các đánh giá nhận xét.
2
Sử dụng công cụ mô phỏng NS2 để xây dựng mô hình mạng MANET,
mô phỏng sự hoạt động của các giao thức định tuyến. Từ kết quả thu được,
tiến hành phân tích, đánh giá để đưa ra kết luận.
4. Ý nghĩa khoa học và thực tiễn của đề tài
Giao thức định tuyến lai ghép là sự kết hợp của hai cơ chế định tuyến
chủ động và bị động. Vấn đề đặt ra là kết hợp như thế nào để đạt được hiệu
quả cao, đáng tin cậy. Các giao thức lai ghép được nghiên cứu đều dựa trên
nguyên tắc chung là mạng được chia thành các vùng, cơ chế tuyến chủ động
sử dụng cho định tuyến trong vùng và cơ chế bị động được sử dụng cho giao
tiếp giữa các vùng. Tuy nhiên mỗi giao thức lại có cách thức thực hiện khác
nhau dẫn đến những hiệu quả khác nhau. Hiện nay, các nhà nghiên cứu vẫn
đang tiếp tục đi sâu nghiên cứu vấn đề định tuyến lai ghép để đề xuất thêm
các thuật toán cải tiến của các giao thức này. Do đó, việc nghiên cứu các giao
thức định tuyến lai ghép trên mạng MANET là cần thiết và đó là cơ sở để đề
xuất thêm các thuật toán mới hoặc cải thiện nâng cao hiệu năng của các thuật
toán cũ.
Mạng MANET ra đời đã lâu và việc ứng dụng trong thực tế của nhiều
nước trên thế giới đã mang lại hiệu quả to lớn. Tuy nhiên, ở Việt Nam hiện
nay, mạng MANET vẫn chưa được ứng dụng rộng rãi. Do đó, việc nghiên
cứu mạng MANET và các giao thức định tuyến trong mạng MANET có ý
nghĩa quan trọng trong việc sớm đưa mạng MANET vào ứng dụng rộng rãi ở
nước ta hiện nay.
5. Cấu trúc của luận văn

Nội dung luận văn gồm 3 chương:
Chương 1. Tổng quan về mạng MANET. Trong chương này chúng
tôi nghiên cứu các cơ sở lý thuyết của mạng MANET, các đặc điểm, phân
loại, các giao thức định tuyến và các ứng dụng của mạng MANET.
3
Chương 2. Tìm hiểu phương pháp nâng cao hiệu năng của giao
thức ZRP với BL và SD trong mạng MANET. Trong chương này chúng tôi
tìm hiểu, phân tích một số giao thức định tuyến lai ghép, và khám phá dịch vụ
tại tầng định tuyến, từ đó so sánh, rút ra ưu điểm, khuyết điểm của các giao
thức này và môi trường áp dụng tốt cho từng giao thức.
Chương 3: Đánh giá hiệu năng của một số giao thức định tuyến
trên mạng MANET. Sau khi nghiên cứu kỹ các giao thức định tuyến ở
chương 2, chúng tôi sử dụng phương pháp mô phỏng bằng NS2 để đánh giá
hiệu năng của giao thức định tuyến lai ghép.
Cuối cùng là kết luận và đề xuất một số hướng nghiên cứu tiếp tục
trong tương lai. Trong quá trình nghiên cứu, do còn nhiều hạn chế về khả
năng và thời gian thực hiện nên luận văn không thể tránh khỏi những thiếu
sót. Kính mong nhận được sự chỉ bảo của các Thầy Cô giáo, các nhận xét và
góp ý của bạn bè, đồng nghiệp để luận văn được hoàn thiện hơn.
4
CHƯƠNG 1
TỔNG QUAN VỀ MẠNG MANET
1.1 Giới thiệu về mạng MANET
Mạng tùy biến di động MANET (Mobile Ad hoc Network)[13], [14] là
mạng không có hạ tầng, MANET bao gồm các thiết bị di động kết nối ngang
hàng hình thành nên một mạng mà không cần sự trợ giúp của các thiết bị
trung tâm hay cơ sở hạ tầng cố định. Mạng MANET với khả năng hoạt động
không phụ thuộc vào cơ sở hạ tầng cố định, chi phí hoạt động thấp, triển khai
nhanh và tính di động cao đã đáp ứng được nhu cầu kết nối của các thiết bị di
động ngày càng mạnh mẽ hiện nay.

1.1.1 Mạng MANET
Với những ưu điểm của công nghệ truyền thông không dây cùng với sự
phát triển nhanh chóng của các thiết bị di động, các mạng không dây được
phát triển rất mạnh trong thời gian gần đây. Mạng không dây có thể được chia
thành hai kiểu: mạng hạ tầng và mạng không có hạ tầng. Trong kiểu mạng hạ
tầng, việc truyền thông giữa các phần tử mạng phụ thuộc vào sự hỗ trợ của
một hạ tầng mạng cố định. Trong khi đó, mạng không có hạ tầng hoạt động
không phụ thuộc vào hạ tầng cố định, các kết nối truyền thông được thiết lập
qua các liên kết không dây đa bước.
1.1.2 Lịch sử phát triển:
Nguyên lý làm việc của mạng Ad hoc bắt nguồn từ năm 1968 khi các
mạng ALOHA được thực hiện. Tuy 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, đây là cơ sở lý thuyết để phát triển kỹ thuật truy cập kênh phân tán vào
mạng Ad hoc.
Năm 1973 tổ chức DARPA đã bắt đầu làm việc trên mạng vô tuyến gói
tin PRnet. Đây là mạng vô tuyến gói tin đa chặng đầu tiên. Trong đó các nút
5
hợp tác với nhau để gửi dữ liệu tới một nút nằm ở xa khu vực kết nối thông
qua một nút khác. Nó cung cấp cơ chế cho việc quản lý hoạt động trên cơ sở
tập trung và phân tán. Một lợi điểm của làm việc đa chặng so với đơn chặng
là triển khai đa chặng tạo thuận lợi cho việc dùng lại tài nguyên kênh truyền
về cả không gian, thời gian và giảm năng lượng phát cần thiết.
Sau đó có nhiều mạng vô tuyến gói tin phát triển nhưng các hệ thống
không dây này vẫn chưa bao giờ tới tay người dùng cho đến khi chuẩn 802.11
ra đời. IEEE đã đổi tên mạng vô tuyến gói tin thành mạng Ad hoc.
1.1.3 Đặc điểm của mạng MANET:
Một mạng MANET bao gồm các hạ tầng di động (ví dụ một router với
nhiều host và thiết bị truyền thông vô tuyến), ở đây được gọi là các nút, đang
di chuyển tự do. Các nút có thể được đặt trên máy bay, tầu thủy, xe kéo, ô tô

hoặc được mang theo người hay các thiết bị nhỏ, và có thể bao gồm nhiều
host trên một router. Một mạng MANET là một hệ thống các nút di động tự
trị. Hệ thống có thể hoạt động độc lập hoặc có thể có cổng để giao tiếp với
mạng cố định.
Các nút mạng MANET bao gồm các bộ phát và bộ thu sử dụng ăng ten
mọi 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 nào
đó, tùy thuộc vào vị trí của các nút và vùng phủ sóng bộ thu và bộ phát của
chúng, mức công suất phát và mức nhiễu đồng kênh, một kết nối vô tuyến
dưới dạng ngẫu nhiên, kiến trức nhiều bước hay mạng MANET tồn tại giữa
các nút. Kiến trúc này có thể thay đổi theo thời gian khi các nút di chuyển
hoặc điều chỉnh các thông số thu phát của chúng.
Mạng MANET có một số đặc điểm nổi bật sau đây:
Kiên trúc mạng động: Kiến trúc mạng luôn biến đổi sự di chuyển của
các nút mạng. Đây là đặc trưng quan trọng của mạng MANET. Mỗi nút trong
mạng có thể di chuyển tự do theo các hướng không thể biết trước, dẫn đến các
6
liên kết giữa các nút mạng thay đổi liên tục. Vì vậy, kiến trúc mạng thay đổi
liên tục làm ảnh hưởng đến hoạt động trao đổi thông tin giữa các nút mạng.
Khả năng tự thiết lập: Mạng MANET không phụ thuộc vào bất kỳ
một kiến trúc mạng sẵn có nào cũng như sự quản lý tập trung tại bất kỳ một
nút mạng nào. Các nút có vai trò ngang nhau và hoạt động độc lập nhau. Các
nút phải tự thiết lập các thông tin cần thiết cho chính mình (địa chỉ mạng,
thông tin định tuyến, …) khi gia nhập vào mạng cũng như tự điều chỉnh thông
tin khi mạng thay đổi. Do đó, các giao thức định tuyến trong mạng MANET
phải có cơ chế tự thiết lập, cập nhật và quản lý các thông tin cần thiết cho các
nút mạng.
Khoảng cách sóng ngắn: Nhìn chung, các nút trong mạng MANET sử
dụng tần số radio để trao đổi dữ liệu với nhau. Tuy nhiên khoảng cách sóng
radio của các thiết bị di động là rất hạn chế.

Năng lượng hạn chế: Tất cả các thiết bị di động đều sử dụng pin nên
khi tham gia vào mạng MANET chúng bị hạn chế về năng lượng, khả năng
xử lý của CPU, kích thước bộ nhớ. Vì vậy tiêu chí thiết kế quan trọng nhất
đối với việc tối ưu là tiết kiệm năng lượng.
Băng thông hạn chế: Các liên kết không dây có băng thông thấp hơn
so với đường truyền cáp và chúng còn chịu ảnh hưởng của sự nhiễu, suy giảm
tín hiệu, các điều kiện giao thoa vì thế mà thường nhỏ hơn tốc độ truyền lớn
nhất của sóng vô tuyến.
Bảo mật vật lý hạn chế: Các mạng di động vô tuyến thường thiên về
bảo mật lớp vật lý hơn so với các mạng hữu tuyến. Khả năng bị nghe trộm,
giả mạo và tấn công từ chối dịch vụ cần được xem xét cẩn thận. Các kĩ thuật
bảo mật liên kết hiện có thường được áp dụng cho các mạng vô tuyến để giảm
các nguy cơ về bảo mật. Bản chất không tập trung của điều khiển mạng trong
mạng MANET cũng tạo ra những ưu điểm đối với nhược điểm “single point
of failure” của các mạng quản lý tập trung.
7
1.2 Phân loại mạng MANET
1.2.1 Phân loại theo giao thức:
- Single-hop:
Mạng MANET định tuyến single-hop là mô hình mạng ad hoc đơn giản
nhất. Trong đó, tất cả các nút đều nằm trong cùng 1 vùng phủ sóng, nghĩa là
các nút có thể kết nối trực tiếp với nhau mà không cần 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 đủ để các nút liên kết trực tiếp với các nút khác trong mạng.
- Multi-hop:
Đây là mô hình phổ biết nhất trong mạng MANET. Trong mô hình này,
các nút có thể kết nối với các nút khác trong mạng mà không cần kết nối trực
tiếp với nhau. Các nút có thể định tuyến đến các nút khác thông qua các nút
trung gian trong mạng. Để mô hình này hoạt động một cách hoà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.

- 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.
1.2.2 Phân loại theo chức năng của nút:
- Mạng MANET đẳng cấp (Flat):
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 đó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óa việc sử dụng
tài nguyên băng thông của mạng vì những gói 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 kiến trúc có các nút di
chuyển nhiều.
- Mạng MANET phân cấp (Hierarchical):
Trong mô hình này thì mạng chia thành các miền khác nhau, trong mỗi
miền bao gồm một hoặc nhiều cụm mỗi cụm chia thành nhiều nút. Có hai loại
nút là nút trưởng cụm và nút thành viên.
8
Nút trưởng cụm là nút quản trị một router có nhiệm vụ chuyển dữ liệu
của các nút trong cụm đến các nút trong cụm khác và ngược lại. Nút thành
viên là các nút nằm trong cùng một cụm. Nó có thể kết nối với các nút trong
cụm hoặc kết nối với các cụm khác thông qua nút trưởng cụm.
Với các cơ chế trên, mạng sử dụng tài nguyên băng thông hiệu quả hơn
vì các tin nhắn chỉ phải truyền trong 1 cụm. Tuy nhiên việc quản lý tính
chuyển động của các nút 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):
Mạng được chia thành nhiều vùng, mỗi vùng bao gồm nhiều nút. Kiến
trúc mạng được chia thành 2 cấp: Kiến trúc cấp thấp (cấp nút) và kiến trúc
cấp cao (cấp vùng). Mỗi nút được đặc trừng bởi ID nút và ID vùng. Trong
một vùng có thể áp dụng kiến trúc đẳng cấp hoặc kiến trúc phân cấp.

1.3 Các thuật toán định tuyến:
Trong mạng MANET, các nút mạng di chuyển tự do nên kiến trúc mạng
thay đổi liên tục gây khó khăn trong việc truyền tải các gói tin. Do đó, vấn đề
đáng quan tâm của mạng MANET là định tuyến. Để định tuyến trên mạng
MANET, người ta thường dùng 2 thuật toán [13], [15]: thuật toán vector khoảng
cách (Distance Vector) và thuật toán trạng thái liên kết (Link state).
1.3.1 Thuật toán vector khoảng cách (Distance Vector):
Thuật toán Bellman-Ford tính toán đường đi ngắn nhất từ nguồn tới
đích được mô tả như sau:
Input: Đồ thị (G,w,s);
Bellman-Ford-More(G,w,s):
- Bước 1: Khởi tạo nút nguồn s;
- Bước 2: for i = 1 to V[G] do
For mỗi cạnh (u,v)
∈
E[G] do
If d(v) > d(u) + w then { d(u), d(v) là chi phí được tính từ nút gốc đến
các đỉnh u,v}
d(v):= d(u) + w;
- Bước 3: for mỗi cạnh (u,v)
∈
E[G] do
9
If d[u] + w(u,v) < d[v] then
Return False;
Else
Return True;
Output: Cây đường đi ngắn nhất từ nút s đến các nút khác, kết quả hàm
trả về True nếu không có đỉnh nào mà đường đi đến nó có giá trị lớn hơn tổng
đường đi đến nút kề đứng trước nó với trọng số trên cạnh nối hai đỉnh u và v,

ngược lại hàm trả về giá trị False.
Thuật toán này dùng thuật toán Bellman – Ford, trong đó chỉ định một
con số, gọi là chi phí (hay trọng số), cho mỗi một liên kết giữa các nút trong
mạng. Các nút sẽ gửi thông tin về đường đi từ nút A đến nút B qua các kết nối
mang lại tổng chi phí thấp nhất.
Hoạt động của thuật toán như sau: Khi một nút khởi động lần đầu, nó chỉ
biết các nút kề trực tiếp với nó, gọi là nút láng giềng, và thông tin để đi đến đó
(thông tin này bao gồm danh sách của các nút đích, tổng chi phí đến từng đích và
nút kế tiếp để gửi dữ liệu đến đó tạo nên bảng định tuyến, hay bảng khoảng
cách). Mỗi nút, trong một tiến trình gửi đến từng láng giềng tổng chi phí của nó
để đi đến các nút đích mà nó biết. Các nút láng giềng phân tích thông tin này, và
so sánh với những thông tin mà chúng đang biết; bất kỳ điều gì cải thiện được
những thông tin chúng đang có, sẽ được đưa vào các bảng định tuyến của những
láng giềng này. Đến khi kết thúc, tất cả nút trên mạng sẽ tìm ra bước truyền kế
tiếp tối ưu đến tất cả mọi đích, và tổng chi phí tốt nhất.
Khi trong một mạng có nút gặp vấn đề, thì sẽ hủy các lộ trình đi qua
nút này và tạo nên thông tin mới trong bảng định tuyến. Sau đó chúng chuyển
thông tin này đến tất cả nút gần kề và lặp lại quá trình trên. Cuối cùng, tất cả
nút trên mạng nhận được thông tin cập nhật, và sau đó sẽ tìm đường đi mới
đến tất cả các đích mà chúng còn tới được.
Ưu điểm của thuật toán này là dễ cấu hình do quá trình xử lý đơn giản
nên ít tốn bộ nhớ. Tuy nhiên, thuật toán này có nhược điểm là hệ thống cung
cấp các thông số còn quá đơn giản nên có thể xẩy ra việc con đường tìm ra
10
chưa phải là tốt nhất. Do phải cập nhật định kỳ các bảng định tuyến, nên một
lượng băng thông đáng kể sẽ bị chiếm dụng. Ngoài ra, do các Router hội tụ
chậm, sẽ dẫn đến việc sai lệch trong bảng định tuyến gây ra hiện tượng lặp.
1.3.2 Thuật toán trạng thái liên kết (Link State):
Thuật toán trạng thái liên kết được dùng để xây dựng và tính toán
đường đi ngắn nhất từ nút nguồn đến tất cả các nút đích trong mạng. Thuật

toán Dijkstra được áp dụng trong giao thức định tuyến trạng thái liên kết được
thực hiện qua các bước sau:
Input: Đồ thị (G,w,s);
Dijkstra(G,w,s):
- Bước 1: Khởi tạo nút nguồn s;
- Bước 2: S: = {}; {Cuối cùng S sẽ chứa các đỉnh có trọng số đường đi
ngắn nhất từ s}
- Bước 3: Khởi tạo hàng đợi ưu tiên Q:= V[G] {Q chứa các đỉnh trong
đồ thị G}
- Bước 4: While Q<>{} do
u:=EXTRACT_MIN(Q) {Chọn ra đỉnh v trong Q lân cận đỉnh u có
trọng số cạnh (u,v) nhỏ nhất gán cho u}
- Bước 5: S:=U
∪
{u}; Q:=Q\{u}
- Bước 6: for mỗi đỉnh v
∈
Adj[u] do {v các đỉnh liền kề với u}
If d(v) > d(u) + w then {d(u), d(v) là chi phí được tính từ nút gốc đến
các đỉnh u, v}
d(v):=d(u) + w; {Quay lại bước 4};
Output: Cây đường đi ngắn nhất từ đỉnh s đến các nút trong mạng.
Khi áp dụng các thuật toán trạng thái kết nối, mỗi nút sử dụng dữ liệu
cơ sở của nó như là một bản đồ của mạng với dạng một đồ thị. Để làm điều
này, mỗi nút phát đi tới toàn mạng những thông tin về các nút khác mà nó có
thể kết nối được, và từng nút góp thông tin một cách độc lập vào bản đồ. Sử
dụng bản đồ này, mỗi nút sau đó sẽ xác định được tuyến đường tốt nhất từ nó
đến mọi nút khác.
Thuật toán này xây dựng cấu trúc dữ liệu dưới dạng cây, trong đó nút
hiện tại là gốc, và chứa mọi nút khác trong mạng. Bắt đầu với một cây ban

11