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

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



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 11
DANH MỤC HÌNH ẢNH

Hình 1-1. Các tiêu chí lựa chọn trong chiến lược tham lam 17
Hình 1-2. Chiến lược định tuyến phẳng trong định tuyến địa lý 19
Hình 1-3. Chuyển tiếp tham lam trong GPSR 22
Hình 1-4. Vấn đề vùng trống trong GPSR 23
Hình 1-5. Quy tắc bàn tay phải 24
Hình 2-1. Định tuyến gói tin theo chiến lược tham lam 26
Hình 2-2. Vùng trống trong giao thức DRQC 27
Hình 2-3. Định nghĩa các nút trong DRQC 28
Hình 2-4. Trạng thái của nút trong DRQC 29

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 luận văn này tôi tập trung trình bày về chiến lược định tuyến dựa
theo phân chia nút theo góc phần tư. Cụ thể, luận văn nghiên cứu chi tiết giao
thức DRQC [8], từ đó đánh giá và phát hiện hạn chế của giao thức này. Dựa trên
phân tích về hạn chế của giao thức DRQC, một cải tiến mới cho thuật toán, được
đặt tên là DR-CR (Detour Routing based on Coordination Rotation), được đề
xuất. Các thí nghiệm mô phỏng đánh giá hiệu năng của đề xuất được thực hiện
và cho thấy đề xuất cải tiến có thể nâng cao hiệu năng của định tuyến so với
giao thức DRQC gốc và cao hơn giao thức GPSR, một giao thức nổi tiếng và
phổ biến trong mạng WSN.
Việc mô phỏng, đánh giá hiệu năng được trình bày trong luận văn dựa trên
công cụ mô phỏng sự kiện mạng Network Simulation 3 (NS-3) [10][11]. Đây là
một công cụ mô phỏng sự kiện mạng được phát triển sau NS-2 và có nhiều cải
tiến về mặt cấu trúc để nhà phát triển có thể tự do hơn khi thực thi các giao thức
mạng. Đồng thời việc mô phỏng cũng được thực hiện hiệu quả hơn và chi tiết
hơn với nhiều khả năng đưa các sự kiện mô phỏng vào hệ thống [10]. Hạn chế

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.
15

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
thay đổi. Ngược lại, những thuật toán định tuyến địa lý được thiết kế để làm việc
với những cấu trúc mạng có trạng thái luôn thay đổi và hỗ trợ tốc độ cấp phát
gói tin cao trong các mạng di động. Tất cả nhũng thuật toán về định tuyến địa lý
đều tuân theo nhưng yêu cầu sau [7]:
- Một nút có thể xác định thông tin vị trí của chính nút đó.
- Một nút có thể biết vị trí của nút hàng xóm với nó.
- Trước khi chuyển tiếp thông tin phải biết trước vị trí nút đích.
Với yêu cầu thứ nhất, bằng các hệ thống GPS hoặc những hệ thống vệ tinh
dò tìm chuyển hướng cơ bản, thông tin về vị trí của những thiết bị rất nhỏ có thể
được dễ dàng xác định. Hơn nữa hệ thống dò tìm vị trí cho những ứng dụng
trong nhà, các thiết bị có kích thước nhỏ đã được phát triển từ rất sớm và ngày
càng phát triển. Với yêu cầu thứ 2, các nút cần quảng bá thông tin vị trí tới
những thành phần khác của mạng và thông tin vị trí của một nút sẵn sàng để tính
toán các nút tiếp theo gần với nút đích nhất trong quá trình định tuyến.
Điều kiện chính để có những yêu cầu giả định trên là phải có hệ thống

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
- CR (Compass Routing): Lựa chọn tiêu chí góc tạo bởi nút hàng xóm, nút
nguồn, nút đích là nhỏ nhất.
- NFP : Lựa chọn nút hàng xóm có khoảng cách hình chiếu gần nút nguồn
nhất.
- MFR: Lựa chọn nút hàng xóm có khoảng cách hình chiếu gần nút đích
nhất.
Chiến lược chuyển tiếp tham lam có một nhược điểm quan trọng: khi số
lượng các nút mạng trong một vùng diện tích rất ít hoặc không có hàng xóm nào
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

“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
đi của gói tin. Phát tràn sẽ gửi các gói tin qua tất cả các hàng xóm ngoại trừ nút
chuyển tiếp trước nó. Có hai loại thuật toán phát tràn chính là pháp tràn không
kiểm soát (Uncontrolled Flooding) và phát tràn có kiểm soát (Control Flooding).
Thuật toán phát tràn không kiểm soát có thể gây ra các vấn đề nghiêm
trọng trong quá trình quảng bá gói tin. Tất cả các nút có hàng xóm sẽ gửi gói tin

2 Nguồn: tài liệu [7]
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

- 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
bị trong hệ thống mạng để chuyển tiếp và thông tin vị trí địa lý của hàng xóm
hiện thời trong cấu trúc mạng, khi thuật toán tham lam không tìm thấy một nút
mạng tiếp theo của đường đi gói tin tới đích thì định tuyến gói tin trên mặt
phẳng được áp dụng để chuyển tiếp gói tin và phục hồi lại đường đi (chiến lược
phục hồi). Chiến lược phục hồi chuyển tiếp gói tin xung quanh mặt phẳng tạo
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ó

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
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 GPSR
4

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

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
toán định tuyến sử dụng thông tin vị trí địa lý áp dụng phương pháp tìm kiếm
tham lam để tìm kiếm thông tin về đường đi tới nút đích mà không phải lưu trữ
và bảo trì thông tin bảng định tuyến. Tuy nhiên, thuật toán tham lam định tuyến
gói tin không thành công hoặc hiệu suất thấp nếu gặp các vấn đề về vùng trống
(void area). Trong phần này tôi sẽ trình bày và phân tích thuật toán định tuyến
dựa trên phân chia góc phân tư “Detour Routing based on Quadrant
Classification (DRQC)” đã được tác giả trong tài liệu [8] đề xuất để giảm thiểu
xảy ra vấn đề vùng trống bằng cách ngăn chặn gửi gói tin đi, đến các vùng trống
trong cấu trúc mạng. Ý tưởng cơ bản của thuật toán là, mỗi nút sẽ biết được
thông tin vị trí địa lý của chính nó và thông tin vị trí của các nút hàng xóm cấp 1
(1-hop neighbors) và hàng xóm cấp 2 (2-hop neighbors). Các nút cũng sẽ xác
định trạng thái của nó là nút đỏ hoặc nút trắng. Một nút là nút đỏ nếu nó không
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.