ĐẠ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


Ket-noi.com
Ket-noi.com kho
kho tai
tai lieu
lieu mien
mien phi
phi

ĐẠ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Ƣ


phi
4

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

NHẬN XÉT CỦA GV HƢỚNG DẪN, GV PHẢN BIỆN

.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................

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



iii. Channel ...................................................................................................... 54
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


Ket-noi.com
Ket-noi.com kho
kho tai
tai lieu
lieu mien
mien phi
phi
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


Dynamic Source Routing (DSR) [6]
Greedy Other Adaptive Face Routing
Global Positioning System
Geographic Perimeter Stateless Routing Protocol
Geographics Routing Protocol
Network Simulator 3


Ket-noi.com
Ket-noi.com kho
kho tai
tai lieu
lieu mien
mien phi
phi
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-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


Ket-noi.com
Ket-noi.com kho
kho tai
tai lieu
lieu mien
mien phi
phi
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

Nội dung của bài Luận văn gồm có 4 chƣơng chính
Chƣơng 1- Giao thức định tuyến theo thông tin địa lý
Tóm lược tổng quan về giao thức định tuyến theo thông tin vị trí địa lý
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.


Ket-noi.com
Ket-noi.com kho
kho tai
tai lieu

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


Ket-noi.com
Ket-noi.com kho
kho tai
tai lieu
lieu mien
mien phi
phi
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

tiếp sẽ bị giữ lại và bị xóa. Luận văn sẽ trình bày một vài chiến lược tìm kiếm
đường đi phổ biến trong định tuyến sử dụng thông tin vị trí địa lý mạng không
dây ở phần tiếp theo.


17

1.2. Các chiến lƣợc định tuyến trong định tuyến địa lý
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 lam1
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.
-


gần với nút đích nhất trong mọi trường hợp thì việc định tuyến sẽ không thực
hiện thành công. Trong trường hợp này chiến lược định tuyến cần tới một vài
thao tác đơn giản để tiếp tục định tuyến bằng chiến lược tham lam. Phương thức
GEDIR [5] là một chiến lược định tuyến tham lam cùng với các bước quay lui.
Khi một thông tin định tuyến tìm thấy vùng trống (void area), thì nó sẽ gửi gói
tin về đúng nút đã chuyển tiếp trước đó, áp dụng lại quy tắc tham lam khi thực
hiện việc tìm kiếm nút kết thúc từ vùng lựa chọn, đó là chiến thuật lặp tự do.
Để cải thiện hiệu suất cho các thuật toán tham lam áp dụng lựa chọn MFR
và CR nếu tồn tại sẵn thông tin của nút hàng xóm cấp 2 (2- neighbhors) tương
ứng của mỗi nút. Một số thuật toán tham lam sử dụng thông tin của nút hàng
xóm cấp 2 đã được thiết kế tuy nhiên có thể làm tăng thời gian của độ trễ truyền
tin. Các thuật toán tham lam với hàng xóm cấp 2 có thể được thêm vào các thuật
toán thông minh để ngăn chặn những vùng trống trong định tuyến.
1.2.2. Chiến lƣợc định tuyến đi vòng
Khi định tuyến gói tin gặp phải vùng trống trong quá trình định tuyến,
trong trường hợp này gói tin sẽ không đi qua được các vùng trống theo chiến
lược tham lam. Một số thuật toán đã được áp dụng để gói tin có thể vượt qua
được các vùng trống. Tuy nhiên, định tuyến theo đồ thị phẳng là chiến lược
thường được sử dụng và thường áp dụng cùng với chiến lược tham lam.
Định tuyến đồ thị phẳng (Planar Graph Routing) [7] là chiến lược định
tuyến theo thông tin địa lý chuyển tiếp gói tin qua những vùng trống (void area)
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


kho tai
tai lieu
lieu mien
mien phi
phi
20

quảng bá vô thời hạn. Nếu một nút có nhiều hơn hai hàng xóm thì dẫn đến vấn
đề gây bảo gói tin quảng bá.
Thuật toán phát tràn có kiểm soát được chia thành hai thuật toán định tuyến
chính là phát tràn có kiểm soát số tuần tự - Sequence Number Controlled
Flooding (SNCF) và phát tràn đường đi ngược - Reverse Path Flooding (RPF).
Trong SNCF, mỗi nút sẽ gửi kèm theo địa chỉ của chính nó và số thứ tự vào gói
tin. Mỗi nút đều có một bộ nhớ và lưu số thứ tự. Nếu một nút nào đó nhận được
gói tin có số thứ tự và địa chỉ tồn tại trong bộ nhớ, nó sẽ bị loại bỏ tức thì. Trong
khi đó RPF thì mỗi nút sẽ gửi duy nhất gói tin chuyển tiếp. Nếu nó nhận được
gói tin từ nút tiếp theo phản hồi về, nó sẽ gửi lại thông tin cho nút chuyển tiếp
trước đó.
Tất cả các giao thức sử dụng chiến lược phát tràn đều có thuật toán làm
việc tương đối giống nhau với đặc điểm:
- Mỗi nút hoạt động như một thiết bị phát và thiết bị thu.
- Mỗi nút sẽ cố gắng gửi tất cả các gói tin tới các nút hàng xóm ngoại trừ
nút chuyển tiếp trước đó.
Kết quả nhận được là tin nhắn cuối cùng sẽ tìm ra đường đi của gói tin
trong mạng. Thuật toán có thể cần nhiều yêu cầu phức tạp hơn nhiều, trong một
số trường hợp, sẽ kiểm tra các gói tin nhận được của các nút để tránh sự trù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

bởi các vùng trống trong hệ thống mạng, khi các điều kiện áp dụng thuật toán
tham lam được phục hồi thì GPSR sẽ áp dụng thuật toán tham lam thay vì định
tuyến đồ thị phẳng. GPSR lưu giữ lại duy nhất thông tin cục bộ vị trí của các nút
mạng nên GPSR sẽ được mở rộng tốt hơn nếu quy mô mạng tăng hơn các thuật
toán short-path và ad-hoc routing theo tài liệu [3].
Trong hệ thống mạng gồm toàn bộ các trạm không dây, giao tiếp qua lại
giữa những nút đích và nút nguồn có thể phải qua rất nhiều nút trung gian.
Trong cộng đồng các nhà nghiên cứu, nhiều thuật toán định tuyến cho mạng
không dây đã được đề xuất, thực hiện và kiểm chứng. Sự thay đổi cấu trúc mạng
trong mạng không dây là lớn hơn đối với mạng có dây. Trên hệ thống mạng có
dây, việc sử dụng các thuật toán định tuyến Distance Vector (DV) [1] và Link
state (LS) [6] là rất hiệu quả và được phát triển từ rất sớm, tuy nhiên một thuật
toán định tuyến luôn luôn phụ thuộc vào các yếu tố như:
- Tốc độ thay đổi của cấu trúc mạng
- Số lượng các nút mạng trong hệ thống
Cả hai yếu tố này sẽ làm cho thuật toán DV và LS trở nên phức tạp nếu
như áp dụng trong mạng không dây có tốc độ thay đổi cấu trúc lớn và số lượng


Ket-noi.com
Ket-noi.com kho
kho tai
tai lieu
lieu mien
mien phi
phi
22

các nút mạng nhiều. Vì vậy, một thuật toán định tuyến đã được đề xuất từ rất
sớm cho mạng không dây đó là: “Greedy Perimete Stateless Routing (GPSR)”.

tin gửi đến nút đích D, x xem xét các nút trong phạm vi phủ sóng tín hiệu của
nó. Nút x sẽ gửi gói tin tới nút y vì trong phạm vi phủ sóng của nút x không có
nút khác ngoài nút y có khoảng cách gần với nút D nhất. Quá trình chuyển tiếp
tham lam này sẽ được lặp lại cho tới khi gói tin đến được nút D.

Hình 1-4. Vấn đề vùng trống trong GPSR4
Nếu giữa nút D và nút x không tồn tại một nút trung gian nào có khoảng
cách gần với đích nhất hơn chính nút x và là hàng xóm của nút x, thì vấn đề
vùng trống xảy ra. Trong Hình 1-4, có 2 trường hợp gói tin được chuyển tới nút
D như sau: x->y->z->D hoặc x->w->v->D. Tuy nhiên thuật toán chuyển tiếp
tham lam sẽ không sử dụng cho hai trường hợp này.
1.3.2.2. Chuyển tiếp vùng biên (Perimeter Forwarding)
Trong giao thức định tuyến GPSR, khi một nút không tìm thấy các nút
hàng xóm thỏa mãn điều kiện chỉ ra trong lựa chọn tham lam thì chiến lược định
tuyến dựa trên đồ thị phẳng và quy tắc bàn tay phải được áp dụng [3]. Việc kết
hợp chuyển tiếp tham lam và chuyển tiếp vùng biên trong giao thức định tuyến
GPSR giúp cải thiện hiệu suất định tuyến gói tin.

4 Nguồn: tài liệu [3]


Ket-noi.com
Ket-noi.com kho
kho tai
tai lieu
lieu mien
mien phi
phi
24


có vấn đề vùng trống, ngược lại một nút là nút trắng nếu có khả năng xảy ra vấn
đề vùng trống. Trong quá trình xử lý định tuyến DRQC yêu cầu mỗi nút phải
chọn một hàng xóm cấp 2 là nút đỏ và có khoảng cách tới nút đích là ngắn nhất.
Nếu không có nút nào thỏa mãn điều kiện trên thì thuật toán tham lam tìm kiếm
với hàng xóm cấp 2 được áp dụng.
Vì các kiến trúc mạng không dây luôn thay đổi nên một chiến lược đơn
giản cho định tuyến trong mạng Wireless Sensor Network là chiến lược phát
tràn (flooding) giúp cho việc tìm kiếm đường đi của gói tin hiệu quả. Tuy nhiên,
phương thức này không thực sự hiệu quả trong các kiến trúc mạng quan tâm tới
năng lượng và băng thông đường truyền, bởi vì có rất nhiều các nút mạng phải
thực hiện chuyển tiếp gói tin quảng bá và các nút cũng phải xử lý rất nhiều gói
tin được gửi tới mà không thật sự cần thiết.
Có những giao thức định tuyến khác sử dụng thuật toán tham lam để định
tuyến, những thuật toán này hiệu quả hơn so với các thuật thoán phát tràn [8].
Thông thường thuật toán tham lam mỗi một nút yêu cầu giao tiếp duy nhất với