ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
KHOA CÔNG NGHỆ THÔNG TIN
o0o
TIỂU LUẬN MÔN
ĐÁNH GIÁ HIỆU NĂNG MẠNG

Đề tài:
N
N
G
G
H
H
I
I
Ê
Ê
N
NC
C
Ứ
Ứ
U
UV

G
I
I
A
A
O
OT
T
H
H
Ứ
Ứ
C
CĐ
Đ
Ị
Ị
N
N
H
HT

GA
A
D
DH
H
O
O
C
C
.
.
G


d
d
ẫ
ẫ
n
n:
:P
P
G
G
S
S
.
.
T
T
S
SV
V
Õ

v
i
i
ê
ê
n
nt
t
h
h
ự
ự
c
ch
h
i
i
ệ
ệ
n
n:

N
G
GL
L
ớ
ớ
p
p:
:C
C
a
a
o
oh
h
ọ
ọ
c

0
1
1
1
1-
-2
2
0
0
1
1
3
3
Huế, tháng 01/2013
TIỂU LUẬN MÔN: ĐÁNH GIÁ HIỆU NĂNG MẠNG

Trang 3
MỤC LỤC
Trang
MỤC LỤC 3
LỜI NÓI ĐẦU 4

P.Kuppusamy, Dr.K.Thirunavukkarasu, Dr.B.Kalaavathi. Dựa vào bài báo trên bản
thân em chọn đề tài Nghiên cứu và so sánh các giao thức định tuyến trong mạng
Ad Hoc. Bằng những kiểm chứng thông qua mô phỏng, tiểu luận đưa ra các nhận
xét, đánh giá về hiệu suất mạng đối với từng giao thức định tuyến cụ thể khi các nút
mạng chuyển động với tốc độ và hướng đi thay đổi.
Nội dung của tiểu luận gồm các phần sau:
 Giới thiệu về mạng MANET
 Khái quát về các giao thức định tuyến OLSR, AODV và TORA
 Nghiên cứu và so sánh giao thức định tuyến Ad-Hoc
 Kết luận
Tuy đã rất cố gắng song bài viết không tránh khỏi những thiếu sót, em rất
mong nhận được sự đóng góp ý kiến của các thầy cô giáo và các anh chị học viên
lớp cao học Khoa học máy tính để bài viết được hoàn thiện hơn. Em xin chân thành
cám ơn.
TIỂU LUẬN MÔN: ĐÁNH GIÁ HIỆU NĂNG MẠNG

Trang 5
NỘI DUNG
I. GIỚI THIỆU
Mạng di động đặc biệt (Mobile Adhoc Netwowk) là mạng tự cấu hình của các nút
di động kết nối với nhau thông qua các liên kết không dây tạo nên mạng độc lập không
phụ thuộc vào cơ sở hạ tầng mạng. Các thiết bị trong mạng có thể di chuyển một cách tự
do theo mọi hướng, do đó liên kết của nó với các thiết bị khác cũng thay đổi một cách
thường xuyên.
Trong MANET tập hợp các nút di động không dây kết nối với nhau để tạo thành
mạng lưới tạm thời, trong đó các nút giao tiếp với nhau mà không có điều khiển tập trung.
Các nút được tự do chuyển động ngẫu nhiên và tự tổ chức tùy ý. Do đó topo mạng có thể
thay đổi nhanh chóng và dự đoán được. Các nút trong phạm vi radio của nhau có thể giao
tiếp trực tiếp, trong khi các nút từ xa dựa trên các nút lân cận của nó để chuyển tiếp các
gói tin như một router. Định tuyến là một vấn đề cốt lõi trong các mạng để gửi dữ liệu từ

Trang 6
II. KHÁI QUÁT VỀ CÁC GIAO THỨC ĐỊNH TUYẾN TRONG
MẠNG MANET: OLSR, AODV VÀ TORA
1. OLSR (Optimized Link State Routing Protocol):
OLSR là giao thức định tuyến chủ động dựa trên thuật toán trạng thái kết nối
(Link state). Các nút gửi định kỳ ra toàn mạng thông điệp “Hello” để trao đổi thông tin về
láng giềng. Thông tin này bao gồm IP của nút, số thứ tự và danh sách các thông tin khoảng
cách của các nút láng giềng. Sau khi cập nhật những thông tin này nút sẽ xây dựng lên
bảng định tuyến của nó và có cái nhìn tổng thể về toàn mạng. Dựa vào bảng định tuyến
này nó có thể tự tính được đường đi tới các nút khác dựa vào thuật toán tìm đường đi ngắn
nhất. Khi một nút nhận được một gói tin trùng lặp với cùng số thứ tự nó sẽ loại bỏ gói tin
này. Trong bảng định tuyến nút lưu trữ thông tin định tuyến tới tất cả các nút khác trong
mạng. Những thông tin này chỉ được cập nhật khi:
 Khi nút nhận thấy sự thay đổi trong quan hệ láng giềng (vd: mất liên kết
đến nút láng giềng,…)
 Tuyến đường tới các nút đích khác hết hạn (quá lâu không được cập
nhập)
 Phát hiện ra đường đi mới ngắn hơn để tới đích.
Điểm khác biệt giữa OLSR và LSR (Link State Protocol) là việc giao thức
OLSR hoạt động dựa trên việc một nhóm nút mạng cộng tác với nhau tạo nên một
kíp phát chuyển tiếp đa điểm (Multi-Point Relays - MPR). Mỗi nút N trong mạng sẽ
lựa chọn ra một tập các nút láng giềng của nó vào kíp đa điểm MPR(N), các nút
thuộc kíp đa điểm này sẽ chuyển tiếp các gói tin điều khiển được gửi từ N. Nút
không thuộc kíp đa điểm của N vẫn xử lý gói tin này nhưng sẽ không chuyển tiếp
đến các nút khác.

Hình1: Truyền gói tin dùng độ trễ đa điểm MPR.
a. Ưu điểm:
OLSR cũng là một giao thức định tuyến phẳng và nó không cần hệ thống quản trị
trung tâm để xử lý các quá trình định tuyến. Liên kết là đáng tin cậy cho các thông điệp

Các nút trung gian có thể trả lời RREQ chỉ khi nào chúng có một tuyến đến đích mà số
tuần tự đích tương ứng lớn hơn hoặc bằng số tuần tự chứa trong RREQ.
Trong suốt 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 từ khi nhận được bản sao đầu tiên của gói
quảng bá, theo đó 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 đó, các gói này sẽ bị huỷ bỏ. Một 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
bằng cách phát đơn phương một gói đáp ứng tuyến (RREP) ngược về nút lân cận mà từ đó
TIỂU LUẬN MÔN: ĐÁNH GIÁ HIỆU NĂNG MẠNG

Trang 8
nó thu đượ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 tích
cực. Cùng với mỗi thực thể tuyến là một bộ định thời tuyến có nhiệm vụ xoá các thực thể
nếu nó không được sử dụng trong một thời hạn xác định. Do một RREP chuyển tiếp trên
đường dẫn được thiết lập bởi một RREQ nên AODV chỉ hỗ trợ việc sử dụng đường truyền
đối xứng.
Quá trình định tuyến của AODV cũng bao gồm 2 cơ chế chính: cơ chế tạo thông
tin định tuyến và cơ chế duy trì thông tin định tuyến.
- Cơ chế tạo thông tin định tuyến sẽ được thiết lập khi một nút nguồn có nhu cầu
trao đổi thông tin với một nút khác trong hệ thống mạng MANET, mỗi nút trong hệ thống
mạng luôn duy trì 2 bộ đếm: Bộ đếm Sequence Number và Bộ đếm REQ_ID. Cặp thông
tin <Sequence Number, REQ_ID> là định danh duy nhất cho một gói tin RREQ.
- Cơ chế duy trì thông tin định tuyến: Cơ chế hoạt động của AODV là không cần
phải biết thông tin về các nút láng giềng, chỉ cần dựa vào các entry trong bảng định tuyến.
Vì vậy, khi một node nhận thấy rằng Next hop (chặng kế tiếp) của nó không thể tìm thấy,
thì nó sẽ phát một gói RRER (Route Error) khẩn cấp với số Sequence number bằng số
Sequence number trước đó cộng thêm 1, Hop count bằng ∞ và gởi đến tất cả các node láng
giềng đang ở trạng thái active, những node đó sẽ tiếp tục chuyển gói tin đó đến các node

TORA là một thuật toán định tuyến phân bố không có vòng lặp và độ thích nghi
cao, dựa trên khái niệm đảo ngược đường thông. TORA được đề xuất cho môi trường nối
mạng có tính linh động cao. Nó là một giao thức khởi phát từ nguồn và cung cấp đa tuyến
cho mọi cặp nút nguồn/đích cần thiết. Nguyên lý chủ đạo trong TORA là định vị các bản
tin điều khiển đối với mọi tập hợp các nút gần với nơi xảy ra sự thay đổi topo mạng. Để
thực hiện được điều này, các nút cần duy trì thông tin định tuyến về các nút kế cận (chỉ
một chặng). Giao thức này thực hiện 3 chức năng cơ bản:
+ Tạo các tuyến từ nguồn tới đích,
+ Duy trì các tuyến và
+ Xoá các tuyến không hợp lệ.
TIỂU LUẬN MÔN: ĐÁNH GIÁ HIỆU NĂNG MẠNG

Trang 11
Ban đầu để tạo ra một tuyến, nút phát đi một gói QUERY các nút láng giềng. Truy
vấn này được phát lại thông qua mạng cho đến khi nó đạt đến đích hoặc nút trung gian mà
nó có một tuyến đến đích. Nơi nhận các gói tin QUERY sau đó phát đi các gói tin
UPDATE, trong đó liệt kê chiều cao của nó đến đích. Khi gói tin này lan truyền trong
mạng, mỗi nút nhận được các gói tin UPDATE thiết lập chiều cao của nó đến một giá trị
lớn hơn chiều cao của láng giềng mà từ đó UPDATE nhận được. Này có tác dụng tạo ra
một loạt các liên kết trực tiếp từ người gửi ban đầu của gói QUERY đến nút mà ban đầu
tạo ra các gói tin UPDATE. Khi một nút phát hiện ra rằng các tuyến đến một đích đến
không còn giá trị, nó sẽ điều chỉnh chiều cao của nó để nó sẽ là một cực đại địa phương
đối với các nút láng giềng và sau đó truyền một gói tin UPDATE. Nếu node không có láng
giềng với chiều cao hữu hạn liên quan đến đích, sau đó các nút sẽ cố gắng phát hiện ra một
tuyến mới.
Quá trình tạo tuyến với TORA được mô phỏng như hình sau:

Hình 3: Quá trình tạo tuyến với TORA
Như thể hiện trong Hình 3, nút 6 không truyền QUERY từ nút 5 là nó đã nhìn thấy
và truyền thông điệp QUERY từ nút 4 và nguồn có thể nhận được một UPDATE từ nút 2,

Trang 13
III. NGHIÊN CỨU & SO SÁNH GIAO THỨC ĐỊNH TUYẾN AD
HOC.
Manet có một các độ đo định tính và định lượng có thể được sử dụng để so
sánh các giao thức định tuyến ad hoc. Bảng 1 minh họa so sánh các giao thức định
tuyến OLSR, AODV và TORA. Xem xét các độ đo sau đây để đánh giá hiệu suất
của giao thức định tuyến mạng ad hoc.
1) End-to-end Delay: Độ đo này biểu diễn độ trễ trung bình end-to-end và
chỉ ra mất bao lâu cho một gói tin đi từ nguồn đến lớp ứng dụng của điểm đích. Nó
bao gồm tất cả các độ trễ có thể gây ra bởi bộ đệm trong suốt tuyến phát hiện độ trễ,
độ trễ truyền tại MAC, hàng đợi tại giao diện hàng đợi, thời gian chuyển giao. Nó
được đo trong vài giây.
2) Packet Delivery Ratio: Tỷ lệ phân phối gói tin được tính bằng cách chia
số lượng các gói tin nhận được bởi điểm đích cho số lượng các gói dữ liệu gốc bởi
lớp ứng dụng của nguồn (tức là nguồn CBR). Nó quy định cụ thể tỷ lệ mất gói, như
là giới hạn thông lượng tối đa của mạng.
3) Media Access Delay: Thời gian một nút để truy cập trung bình để bắt
đầu truyền tải gói dữ liệu được gọi là như độ trể truy cập trung bình. Độ trễ này
được ghi lại cho mỗi gói tin khi nó được gửi đến lớp vật lý cho lần đầu tiên.
4) Path optimality: Độ đo này có thể được định nghĩa là sự khác biệt giữa
con đường thực tế thực hiện và con đường tốt nhất có thể cho một gói tin đến được
đích của nó.
5) Routing overhead: Độ đo này mô tả bao nhiêu gói định tuyến cho phát
hiện tuyến và bảo trì tuyến cần phải được gửi để truyền các gói dữ liệu.
Bảng 1. So sánh giao thức định tuyến Ad hoc

Bảng 2. Hiệu năng định tuyến trong trường hợp low mobility
TIỂU LUẬN MÔN: ĐÁNH GIÁ HIỆU NĂNG MẠNG

Trang 14

[2]. Khảo sát ảnh hưởng của sự chuyển động các nút mạng …. Luận văn tốt nghiệp Đại
học – Phạm Văn Tứ (ĐH Công Nghệ - DDHQG Hà Nội 2010)
[3]. Mar-Aodv: Một thuật toán định tuyến cải tiến trong mạng Manet dựa trên tác tử di
động – Võ Thanh Tú, Nguyễn Thúc Hải, Cung Trọng Cường (Hôi thảo quốc gia lần thứ XV)
[4] Internet