ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN QUỐC DŨNG CẢI TIẾN VÀ ĐÁNH GIÁ HIỆU NĂNG GIAO
THỨC ĐỊNH TUYẾN ĐI VÕNG DỰA TRÊN
PHÂN LOẠI NÖT THEO GÓC PHẦN TƢ
LUẬN VĂN THẠC SĨ
Hà Nội - 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN QUỐC DŨNG

CẢI TIẾN VÀ ĐÁNH GIÁ HIỆU NĂNG GIAO
THỨC ĐỊNH TUYẾN ĐI VÕNG DỰA TRÊN
PHÂN LOẠI NÖT THEO GÓC PHẦN TƢ

LỜI CẢM ƠN
Em xin gửi lời cảm ơn chân thành và sự tri ân sâu sắc đối với các thầy cô
của trường Đại học Công Nghệ, Đại học Quốc Gia Hà Nội, đặc biệt là các thầy
cô khoa Công nghệ thông tin của trường đã truyền dạy những kiến thức, kinh
nghiệm quý báu giúp em hoàn thành khóa học tại trường. Con xin gửi lời cảm
ơn tới gia đình, cảm ơn bạn bè đã tạo điều kiện thuận lợi trong quá trình học
tập và thực hiện luận văn tốt nghiệp.
Đặc biệt em xin chân thành cảm ơn TS. Hoàng Xuân Tùng, giảng viên khoa
Công nghệ thông tin. Thầy đã nhiệt tình hướng dẫn em hoàn thành tốt nghiệp.
Trong quá trình học tập, cũng như trong quá trình thực hiện luận văn, các
sai sót là khó tránh khỏi. Tuy nhiên em đã cố gắng tối đa để đảm bảo chất lượng
và các tiêu chí của nghiên cứu khoa học. Kính mong quí thầy cô góp ý để luận
văn của em được hoàn thiện hơn.
Em xin chân thành cảm ơn!
Học viên Nguyễn Quốc Dũng 5

MỤC LỤC

BẢNG KÝ HIỆU CÁC CHỬ VIẾT TẮT 9
DANH MỤC CÁC BẢNG BIỂU 10
DANH MỤC HÌNH ẢNH 11
LỜI MỞ ĐẦU 12
Chƣơng 1. GIAO THỨC ĐỊNH TUYẾN THEO THÔNG TIN VỊ TRÍ ĐỊA
LÝ 15
1.1. Tổng quan về giao thức định tuyến theo thông tin vị trí địa lý 15
1.2. Các chiến lược định tuyến trong định tuyến địa lý 17
1.2.1. Chiến lược định tuyến tham lam 17
1.2.2. Chiến lược định tuyến đi vòng 18
1.2.3. Chiến lược định tuyến phát tràn 19
1.3. Giao thức định tuyến “Greedy Perimeter Stateless Routing” 21
1.3.1. Tổng quan 21
1.3.2. Thuật toán định tuyến GPSR 22
Chƣơng 2. GIAO THỨC ĐỊNH TUYẾN “DETOUR ROUTING BASED
ON QUADRANT CLASSIFICATION” 25
2.1. Tổng quan 25
2.2. Chuyển tiếp tham lam và vấn đề vùng trống trong DRQC 26
2.2.1. Chiến lược chuyển tiếp tham lam 26
2.2.2. Vấn đề vùng trống trong giao thức DRQC 27
2.3. Thuật toán định tuyến trong giao thức DRQC 28
2.3.1. Khái niệm, định nghĩa 28
2.3.2. Trạng thái của các nút 28
2.3.3. Định dạng thông điệp gửi 29
2.3.4. Cấu trúc dữ liệu 30
2.3.5. Thuật toán xử lý định tuyến DRQC. 31

iv. Net Device 54
3. Cài đặt NS-3 55
i. Các phần mềm cần thiết 55
a) Mercurial 55
8
b) Waf 55
ii. Cài đặt và kiểm tra và thực hiện mô phỏng 56
a) Cài đặt NS-3 56
iii. Kiểm tra cài đặt và chạy thử chƣơng trình 61
4. Thêm mới module, cài đặt giao thức định tuyến GPSR và DRQC 63
i. Thêm mới module vào dự án NS-3 63
ii. Cài đặt giao thức định tuyến DRQC, GPSR 64
iii. Cài đặt giao thức DRQC 64
iv. Cài đặt giao thức GPSR 70
PHỤ LỤC 2 71 9
BẢNG KÝ HIỆU CÁC CHỬ VIẾT TẮT
STT
Chử viết tắt
Ý nghĩa
1
AODV

10
DANH MỤC CÁC BẢNG BIỂU

Bảng 2-1: Định dạng thông điệp quảng bá 27
Bảng 2-2: Định dạng thông điệp dữ liệu 28
Bảng 2-3: Định dạng thông điệp phản hồi 28
Bảng 2-4: Định dạng cấu trúc bảng định tuyến 29
Bảng 2-5: Định dạng cấu trúc bảng hàng xóm 30
Bảng 3-1: Danh sách các nút hàng xóm DR-CR 39
Bảng 3-2: Danh sách nút hàng xóm mới DR-CR 40
Bảng 4-1: Bảng thông số kịch bản mô phỏng mạng ngẫu nhiên 42
Bảng 4-2: Kết quả tỷ lệ chuyển gói tin thành công 43
Bảng 4-3: Thông số mô phỏng mạng cố định 45
Hình 4-3. Cấu trúc mạng gồm 150 nút 45
Hình 4-4. Cấu trúc mạng gồm 200 nút 45
Hình 4-5. Cấu trúc mạng gồm 250 nút 45
Hình 4-6. Biểu đồ tỷ lệ chuyển gói tin thành công 46
Hình 4-7.Cấu trúc mạng có vị trí cố định 47
Hình 4-8. Thông lượng theo thời gian của các giao thức 48 12
LỜI MỞ ĐẦU
Định tuyến gói tin trong mạng cảm biến không dây (WSN – Wireless
Sensor Network) luôn gặp phải rất nhiều thách thức. Thách thức từ chính các
cấu trúc mạng luôn thay đổi hoặc những rào cản địa lý như sông, hồ, rừng, núi,
Những vấn đề trên là đối tượng nghiên cứu của nhiều giao thức định tuyến
của mạng WSN như: Dynamic Source Routing (DSR) [6], Ad-Hoc On-Demad
Distance Vector Routing (AODV) [6], Định tuyến theo thông tin vị trí địa lý
(geographic routing) là một nhánh nghiên cứu của vấn đề định tuyến trong mạng
WSN và có khả năng nâng cao hiệu suất định tuyến một cách đáng kể do các nút
không cần lưu trữ và cập nhật bảng định tuyến tới từng nút trong mạng [7].
Có nhiều giao thức định tuyến sử dụng thông tin vị trí địa lý đã được trình
bày, đề xuất như GPSR [3], DRQC [8], GOAFR [9] [2]. Tổng hợp lại từ các
giao thức đã được đề xuất có thể đúc kết ra một vài chiến lược định tuyến như
chiến lược tham lam [7], chiến lược tham lam kết hợp đi vòng [7] chiến lược
phát tràn [6], chiến lược phân chia nút theo góc phần tư [1]. Trong đó chiến lược
định tuyến phân chia nút theo góc phần tư là một chiến lược có nhiều ưu điểm
do kết hợp được tính hiệu quả của chiến lược tham lam và tránh được vùng
trống sớm.

trong mạng cảm biến không dây, các chiến lược định tuyến trong mạng không
dây. Trong chương 1, còn tập trung giới thiệu về giao thức định tuyến “Greedy
Perimeter Staless Routing”, là giao thức định tuyến áp dụng chiến lược định
tuyến tham lam phổ biến và hiệu quả.
Chƣơng 2 – Giao thức định tuyến “Detour Routing Based on Quadrant
Classification”
Giới thiệu giao thức định tuyến địa lý “Detour Routing Based on Quadrand
Classification – DRQC” [8] đã được nhóm tác giả công bố trong một số công
trình nghiên cứu của họ. Kiến thức phần chương 2 tập trung phân tích và giới
thiệu về giao thức định tuyến đi vòng dựa trên phân loại nút theo góc phần tư
giúp làm cơ sở cho sự cải tiến giao thức DR-CR ở chương 3.
Chƣơng 3 – Giao thức Detour Routing based on Coordinates Rotation
Nội dung chương 3, phân tích một số hạn chế của giao thức DRQC. Trong
chương 3, chúng tôi đề xuất giải pháp quay trục giúp cho định tuyến gói tin hiệu
quả hơn. Cải tiến mới này được đặt tên là Detour Routing based on Coordination
Rotation (DR-CR).
Chƣơng 4 – Đánh giá hiệu năng
Giới thiệu về kịch bản mô phỏng, đánh giá hiệu năng của ba giao thức định
tuyến GPSR, DRQC và DR-CR (cải tiến từ DRQC), cũng như đánh giá và nhận
xét về tỷ lệ chuyển tiếp gói tin thành công, thông lượng trung bình của ba giao
thức trong từng trường hợp khác nhau.
14
Kết luận
Phần này đưa ra một số kết quả đạt được của quá trình nghiên cứu luận
văn, rút ra một số hạn chế, vấn đề gặp phải. Phần này sẽ trình bày một số định
hướng tiếp theo giúp hoàn thiện vấn đề nghiên cứu trong tương lai.


cấu trúc mạng (Mạng máy tính có dây), các thuật toán định tuyến địa lý không
cần phải duy trì và cập nhật thông tin bảng định tuyến [7]. GRP sử dụng thông
tin địa lý – Global Positioning System (GPS) để định tuyến. Nhiều thuật toán
định tuyến theo vị trí địa lý sử dụng chiến lược tham lam (greedy) nhằm cố gắng
tiếp cận tới vị trí nút đích trong mỗi bước chuyển tiếp gói tin theo một tiêu chí
tối ưu nào đó. Tuy nhiên, nhiều thuật toán tham lam sẽ thất bại hoặc có hiệu suất
định tuyến không cao trong các trường hợp có quá ít các nút trong phạm vi định
tuyến – vùng trống (void area). Chính vì vậy, có rất nhiều thuật toán cải tiến
hoặc kết hợp các chiến lược tìm kiếm khác nhau để xây dựng nên những thuật
toán định tuyến tối ưu cho các trường hợp khác nhau (GPSR [3], GOAFR [9])
Định tuyến theo thông tin địa lý – định tuyến địa lý (định tuyến dựa trên vị
trí địa lý hoặc là định tuyến theo hình học, là kỹ thuật gửi gói tin trong mạng qua
rất nhiều nút trung gian (Hops) bằng cách sử dụng thông tin chính là thông tin vị
trí địa lý của mỗi nút. GRP quyết định đường đi gói tin không được xây dựng từ
những địa chỉ mạng và bảng định tuyến chứa thông tin về định tuyến mà mỗi nút
trong mạng sẽ sử dụng thông tin vị trí địa lý của các nút kề nó (nút hàng xóm).
Mỗi một nút có thể chọn một nút hàng xóm là nút chuyển tiếp dựa theo một tiêu
chí tối ưu nào đó (ví dụ nút hàng xóm gần nút đích nhất). Nút này sẽ chuyển tiếp
thông tin tới nút đích qua các bước tiếp theo. Thực chất mỗi nút sẽ không có
bảng định tuyến, cũng không có những thiết bị định tuyến. Các giao thức định
16
tuyến địa lý rất cần thiết cho những mạng có sự thay đổi về cấu trúc như mạng
không dây, mạng ad-hoc, mạng cảm biến, . Trong mạng không dây định tuyến
truyền thống sử dụng thông tin bảng định tuyến và trạng thái liên kết là rất tốn
kém [7]. Các thuật toán định tuyến truyền thống sử dụng bảng định tuyến yêu
cầu chi phí cho xử lý và gửi nhận thông tin quảng bá là rất lớn và thường xuyên
phải cập nhật thông tin cho bảng định tuyến đối với những cấu trúc mạng luôn

1.2.1. Chiến lƣợc định tuyến tham lam
Một trong những phương pháp được đề xuất đầu tiên cho việc định tuyến
địa lý được công bố trong những năm 1980 là chiến lược định tuyến tham lam
[7]. Tất cả các giao thức định tuyến áp dụng theo chiến lược tham lam thì tại các
nút thực hiện chuyển tiếp sẽ quyết định chuyển tiếp gói tin một cách tối ưu theo
một tiêu chí tối ưu nhất so với nút hiện tại đang thực hiện tính toán.
Việc lựa chọn nút tiếp theo – next hops (Thiết bị mạng chuyển tiếp gói tin)
theo chiến lược chuyển tiếp tham lam dự trên những tiêu chí sau [7]:
- Progess (Khoảng cách tới đích): khoảng cách ngắn nhất của hình chiếu
các nút trên trục st (trục đích nguồn) (Hình 1-1):
- Khoảng cách tới đích ngắn nhất: Là khoảng cách địa lý từ chính các nút
đến nút đích (Hình 1-1).
- Góc xa, góc tách (góc tạo bởi nút nguồn - nút hàng xóm với trục nguồn
đích) (Hình 1-1).

Hình 1-1. Các tiêu chí lựa chọn trong chiến lược tham lam
1

Ví dụ Hình 1-1, giải thích chi tiết các tiêu chí lựa chọn tham lam tối ưu cho
việc định tuyến gói tin trong mạng máy tính không dây.
- NC (Nearest closer): Lựa chọn theo tiêu chí nút hàng xóm ngần nút
nguồn nhất.
- Greedy (Tham lam): Lựa chọn tiêu chí khoảng cách ngắn nhất từ nút
đích tới các nút hàng xóm.

1
Nguồn: tài liệu [7]
18
dựa vào các nút xung quanh vùng viên của các mặt phẳng theo quy tắc “bàn tay
phải” hoặc “bàn tay trái”. Vùng trống (vùng tối thiểu) luôn tồn tại các nút mạng
quanh vùng biên của những vùng trống, tại các vùng biên một nút cần chuyển
tiếp gói tin không thể tìm thấy một hàng xóm nào gần với đích hơn chính nó, nút
như vậy còn gọi là nút chết. Đồ thị phẳng là một nội dung quan trọng cho quá
19
trình phục hồi đường định tuyến gói tin từ những vấn đề vùng tối thiểu (Local
minimum) (Hình 1-2). Định tuyến đồ thị phẳng được xây dựng trên ý tưởng là
mọi liên kết các vị trí là một mạng truyền thông nằm trên các đồ thị phẳng. Và
một gói tin có thể chuyển tiếp thành công qua các mặt phẳng của đồ thị. Định
tuyến phụ thuộc vào mặt phẳng có nghĩa là các nút của mặt phẳng chuyển tiếp
thông tin qua vùng mạng biên bằng cách áp dụng quy tắc “Bàn tay phải” hoặc
“Bàn tay trái”. Quy tắc này rất tốt để giải quyết vấn đề chuyển gói tin qua vùng
trống. Một nút tìm kiếm các nút khác trong đường định tuyến nhằm để giải
quyết vấn đề vùng trống luôn tìm kiếm theo một con đường duy nhất là gửi gói
tin đến các nút bên trái hoặc gửi gói tin đến các nút bên phải. Kỹ thuật chuyển
tiếp gói tin dựa theo quy tắc bàn tay phải đã được các tác giả trình bày chi tiết
trong tài liệu [7].

Hình 1-2. Chiến lược định tuyến phẳng trong định tuyến địa lý
2
Hình 1-2, các mặt phẳng F1, F2, F3, F4 được tạo bởi các nút mạng. Khi áp
dụng quy tắc bàn tay phải hoặc bàn tay trái. Thuật toán sẽ tìm kiếm một đường
chuyển tiếp gói tin từ nút nguồn {s} tới nút đích {t} bằng cách chuyển tiếp qua
các đường biên của từng mặt phẳng.
1.2.3. Chiến lƣợc định tuyến phát tràn
Phát tràn là một chiến lược định tuyến đơn giản trong việc tìm kiếm đường

lặp và gói tin gửi đi vô hạn trong mạng. Một vài giao thức cải tiến của thuật toán
phát tràn gọi là phát tràn có chọn lọc nhằm giải quyết vấn đề chỉ gửi gói tin đến
những nút có cùng hướng với nút đích. Trong thuật toán phát tràn có chọn lọc
các bộ định tuyến không gửi gói tin đến tất cả các nút mà chỉ những nút có cùng
hướng với nút đích [6].
Lợi ích của thuật toán
Khi gửi một gói tin qua mạng, gói tin sẽ tìm kiếm tất cả các đường đi tới
đích để chọn được đường đi ngắn nhất. Đây là thuật toán đơn giản, dễ triển khai,
cài đặt.
Hạn chế
- Phát tràn có thể sẽ gây tốn kém về băng thông. Trong khi một tin nhắn
chỉ có một điểm đến, nó phải gửi đi tất cả các nút khác trong mạng.
Trong trường hợp này sẽ gây ra quá tải về băng thông và dễ bị tấn công
từ chối dịch vụ.
21
- Gói tin có thể được sao chép và tiếp tục được tải lên mạng và đòi hỏi
thuật toán phải xử lý phức tạp để loại bỏ những gói tin này.
- Các gói tin trùng lặp có thể lưu trữ mãi mãi. Trừ khi các biện pháp
phòng ngừa không được thực hiện.

1.3. Giao thức định tuyến “Greedy Perimeter Stateless Routing”
1.3.1. Tổng quan
Greedy Perimeter Stateless Routing (GPSR) là một thuật toán định tuyến
cổ điển cho mạng chuyển mạch gói không dây. GPSR dùng thông tin vị trí địa lý
của các thiết bị chuyển tiếp (Router) và thông tin vị trí của nút đích để quyết
định đường đi tiếp theo cho gói tin. GPSR chuyển tiếp gói tin sử dụng thuật toán
tham lam. Thuật toán tham lam dùng duy nhất thông tin vị trí địa lý của các thiết

- Chi phí giao thức gửi thông điệp: làm thế nào để các gói tin được gửi đi
là nhiều nhất.
- Tỷ lệ gói tin được gửi thành công: các gói tin gửi và chuyển thành công
tới đích như thế nào?
- Trạng thái của nút: mỗi nút sẽ lưu trữ dữ liệu thế nào.
1.3.2. Thuật toán định tuyến GPSR
Trong giao thức định tuyến GPSR, các gói tin được chuyển tiếp dựa trên sự
kết hợp của hai phương thức chuyển tiếp là: Chuyển tiếp tham lam – Greedy
forwarding và chuyển tiếp xung quanh vùng trống (Perimeter forwarding).
1.3.2.1. Chuyển tiếp tham lam trong GPSR Hình 1-3. Chuyển tiếp tham lam trong GPSR
3

Các gói tin trong mạng được gán các thông tin về vị trí địa lý của nút
nguồn và nút đích. Mỗi một nút trong mạng sẽ biết được thông tin về vị trí của
các nút hàng xóm với nó. Một nút thực hiện chuyển tiếp sẽ tính toán lựa chọn
một trong số các nút hàng xóm của nó ngần với nút đích nhất dựa theo thông tin
về vị trí nút đích và nút nguồn gán trong gói tin nó nhận được. Các bước chuyển
tiếp sẽ được thực hiện lặp lại tại mỗi nút khi nhận được gói tin cho tới khi gói tin
được gửi tới nút đích.

3
Nguồn: tài liệu [3]
23
Ví dụ chuyển tiếp tham lam trong Hình 1-3, khi nút x nhận được một gói

phẳng được tạo bởi các nút mạng xung quanh vùng trống. Khi gói tin được gửi
qua các nút y, x, z, qua mỗi nút gói tin sẽ được gửi đi theo cạnh bên phải của
hình đa giác tạo bởi các nút. Thứ tự gói tin sẽ đi qua mặt phẳng đa giác (Hình 1-
5) là y -> x -> z -> y. 5 Nguồn: tài liệu [3]
25
Chƣơng 2. GIAO THỨC ĐỊNH TUYẾN “DETOUR
ROUTING BASED ON QUADRANT CLASSIFICATION”
2.1. Tổng quan
Những vùng trống trong các cấu trúc mạng không dây như sông, hồ, rừng,
núi, … luôn dẫn đến hiệu suất định tuyến gói tin không hiệu quả. Vấn đề vùng
trống trong cấu trúc mạng không dây luôn là thách thức đối với các giao thức
định tuyến không dây. Để cải thiện hiệu suất trong các trường hợp này, thuật