Đại Học Quốc Gia Tp. Hồ Chí Minh
TRƯỜNG ĐẠI HỌC BÁCH KHOA
--------------------

TRẦN MINH HƯNG

THIẾT KẾ VÀ MÔ PHỎNG
GIAO THỨC ĐỊNH TUYẾN HỮU HIỆU CHO
MẠNG KHÔNG DÂY
Ở LỚP HAI CỦA MÔ HÌNH OSI
Chun ngành : Khoa Học Máy Tính

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 7 năm 2009


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
Cán bộ hướng dẫn khoa học : Tiến sĩ Lê Ngọc Minh ........................................

Cán bộ chấm nhận xét 1 : Tiến sĩ Thoại Nam....................................................

Cán bộ chấm nhận xét 2 : Tiến sĩ Võ Văn Khang..............................................

Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp. HCM ngày
25 tháng 8 năm 2009.
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
(Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ luận văn thạc sĩ)
1. Tiến sĩ Trần Văn Hoài ..........................

2. Tiến sĩ Lê Ngọc Minh ..........................
3. Tiến sĩ Thoại Nam................................
4. Tiến sĩ Võ Văn Khang..........................
5. Tiến sĩ Nguyễn Đức Cường .................
Xác nhận của Chủ tịch Hội đồng đánh giá LV và Bộ môn quản lý chuyên ngành sau
khi luận văn đã được sửa chữa (nếu có).
Chủ tịch Hội đồng đánh giá LV

Bộ môn quản lý chuyên ngành


TRƯỜNG ĐH BÁCH KHOA TP. HCM
PHÒNG ĐÀO TẠO SĐH

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc

Tp. HCM, ngày 1 tháng 7 năm 2009.

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: TRẦN MINH HƯNG .....................................Phái: Nam .......................
Ngày, tháng, năm sinh: 19/02/1982 ...........................................Nơi sinh: Tiền Giang ......
Chuyên ngành: Khoa Học Máy Tính .........................................MSHV:00707168............
I- TÊN ĐỀ TÀI: THIẾT KẾ VÀ MÔ PHỎNG GIAO THỨC ĐỊNH TUYẾN HỮU
HIỆU CHO MẠNG KHÔNG DÂY Ở LỚP HAI CỦA MƠ HÌNH OSI ...........................
.............................................................................................................................................
.............................................................................................................................................
II- NHIỆM VỤ VÀ NỘI DUNG:
Tìm hiểu nền tảng lý thuyết của các giải thuật định tuyến cho mạng WMN hiện nay và giải
thuật định tuyến link state XL gần đây (8/2008) Thiết kế một giao thức định tuyến hữu hiệu

cho mạng WMN và tiến hành mô phỏng để so sánh với các giải thuật đã biết khác..........
.............................................................................................................................................
.............................................................................................................................................
.............................................................................................................................................
III- NGÀY GIAO NHIỆM VỤ: 10/1/2007 ......................................................................
IV- NGÀY HOÀN THÀNH NHIỆM VỤ: 1/7/2009 .......................................................
V- CÁN BỘ HƯỚNG DẪN : Tiến sĩ Lê Ngọc Minh .......................................................
.............................................................................................................................................
CÁN BỘ HƯỚNG DẪN

Tiến sĩ Lê Ngọc Minh

CN BỘ MÔN
QL CHUYÊN NGÀNH


1

LỜI CAM ĐOAN
Tôi xin cam đoan rằng ngoại trừ các kết quả tham khảo từ các cơng trình khác như
đã ghi rõ trong luận văn, các nội dung chính trình bày trong luận văn là do chính tơi
thực hiện. Các số liệu trong luận văn được sử dụng trung thực và chưa có phần nào
nội dung của luận văn được nộp để lấy bằng tại bất cứ trường nào hay từng được
cơng bố tại bất kỳ cơng trình nào khác.
TP HCM, ngày 3 tháng 7 năm 2009
Tác giả luận văn

Trần Minh Hưng



2

LỜI CẢM ƠN
Để hồn thành tốt luận văn này tơi vô cùng chân thành cảm ơn sự giúp đỡ cũng như
sự chỉ bảo tận tình của các thầy cơ, đặc biệt thầy hướng dẫn trong suốt thời gian
thực hiện luận văn . Bên cạnh đó được sự quan tâm, sẵn sàng chỉ dẫn của các bạn
bè, các anh, các chị đã giúp tơi có thêm động hơn nữa lực để hồn tất luận văn này.
Đặc biệt tơi xin gửi lời chân thành biết ơn đến bố mẹ đã sinh ra và chăm sóc, dạy dỗ
và ni dưỡng tơi nên người để tơi có được ngày hơm nay. Mặc dù đã hết sức cố
gắng nhưng chắc rằng luận văn sẽ không thể tránh khỏi thiếu sót, kính mong mọi
người góp ý thêm cho luận văn của tơi được hồn thiện hơn. Một lần nữa tôi xin
chân thành cảm ơn.
TP HCM, ngày 3 tháng 7 năm 2009
Tác giả luận văn

Trần Minh Hưng


3

TĨM TẮT LUẬN VĂN
Wireless mesh network (WMN) là mạng khơng dây kết nối tự do bởi các nút sử
dụng tín hiệu radio (máy tính xách tay, điện thoại và các thiết bị không dây khác)
không sử dụng điều khiển tập trung. Các giao thức định tuyến cho WMN hiện tại
đều thực hiện ở lớp mạng sử dụng địa chỉ IP. Luận văn sẽ trình bày giao thức định
tuyến đơn giản và hiệu quả cho WMN gọi là giao thức định tuyến DLL-XL ở lớp
dữ liệu sử dụng địa chỉ vật lý cũng như các kết quả mô phỏng thu được. Giao thức
định tuyến DLL-XL sẽ sử dụng các kỹ thuật ngăn chặn những cập nhật không cần
thiết để tăng hiệu quả của việc định tuyến.



4

ABSTRACT
A wireless mesh network (WMN) is a communication network made up of radio
nodes (laptops, cell phones and other wireless devices) organized in a mesh
topology without central control. Almost all current routing protocols for WMN are
at network layer. This thesis presents a simple and efficient routing protocol, called
DLL-XL routing protocol, at data link layer with MAC address for WMN, and the
result of simulation. The DLL-XL routing protocol achieves routing efficiency by
suppressing updates from parts of the WMN when appropriate.


5

MỤC LỤC
DANH MỤC HÌNH .......................................................................................... 7
BẢNG VIẾT TẮT VÀ THUẬT NGỮ ............................................................. 9
Chương 1: PHÁT BIỂU VẤN ĐỀ.................................................................. 11
1.1 Giới thiệu wireless mesh network (WMN) .....................................................11
1.2 Bài toán định tuyến cho WMN........................................................................12
1.3 Hướng thực hiện ..............................................................................................13

Chương 2: CÁC CƠNG TRÌNH LIÊN QUAN ĐẾN LUẬN VĂN............... 15
2.1 Draft IEEE 802.11s .........................................................................................15
2.2 Dự án OLPC ....................................................................................................18
2.3 Dự án open80211s ........................................................................................19

Chương 3: CƠ SỞ LÝ THUYẾT và PHƯƠNG PHÁP GIẢI QUYẾT VẤN
ĐỀ.................................................................................................................... 20

3.1 Một số giải thuật định tuyến tiêu biểu.............................................................20
3.1.1 Giải thuật AODV......................................................................................20
3.1.2 Giải thuật OLSR .......................................................................................22
3.2 Kỹ thuật flooding trong định tuyến proactive .................................................23
3.3 Giải thuật XL...................................................................................................26
3.3.1 Giới thiệu giải thuật XL............................................................................26
3.3.2 Ý tưởng của giải thuật XL ........................................................................27
3.3.3 Chứng minh các tính chất của giải thuật XL ............................................30
3.3.4 Ứng dụng của giải thuật XL .....................................................................34
3.4. Phương pháp thực hiện...................................................................................34

Chương 4: NỘI DUNG LUẬN VĂN ............................................................. 36
4.1 Hiện thực giải thuật XL...................................................................................36
4.1.1 Chi phí kết nối ..........................................................................................36
4.1.2 Hiện thực giải thuật XL vào thiết kế giao thức định tuyến DDL-XL ......37
4.1.3 Các kỹ thuật dùng trong thiết kế giao thức định tuyến DLL-XL .............39
4.2. Thiết kế giao thức định tuyến DLL-XL ........................................................40
4.2.1 Giới thiệu ..................................................................................................40
4.2.2 Định dạng và chuyển tiếp gói ...................................................................41
4.2.3 Cơ sở dữ liệu.............................................................................................41
4.2.4 Định dạng, gửi và xử lý thông điệp HELLO ............................................43
2.5 Định dạng, gửi và xử lý thơng điệp TC .......................................................44
4.2.6 Tính tốn bảng định tuyến ........................................................................46
4.2.7 Số thứ tự....................................................................................................47
4.2.8 Quá trình khởi động một nút.....................................................................47
4.2.9 Kết nối với các mạng khác .......................................................................48
4.2.10 Các hằng số sử dụng trong giao thức......................................................48

Chương 5. MÔ PHỎNG VÀ ĐÁNH GIÁ ...................................................... 50
5.1 Tổng quan về ns-2 ...........................................................................................50

5.2 Giới thiệu lớp MAC trong ns-2 .......................................................................50


6

5. 3 Ngơn ngữ lập trình trong ns-2 ........................................................................52
5.4 Hiện thực mô đun định tuyến DLL-XL trong ns-2 .........................................55
5.5 Mô hình mạng dùng để mơ phỏng giao thức định tuyến DLL-XL .................55
5.6 Kết quả mô phỏng ...........................................................................................56
5.6.1 Thời gian và lượng thông điệp định tuyến để mạng đạt đến trạng thái tĩnh
...........................................................................................................................56
5.6.2 Lượng thông điệp và mật độ phân bố các nút...........................................58
5.6.3 Tổng lượng thơng điệp khi chi phí liên kết thay đổi ................................58
5.6.4 Số đường đi tối ưu khi sử dụng thông số xấp xỉ ε = 0.5 ..........................59
5.7 Đánh giá thông qua mô phỏng .......................................................................60

Chương 6: KẾT LUẬN................................................................................... 61
6.1 Những đóng góp của luận văn.........................................................................61
6.2 Hướng phát triển..............................................................................................61

Chương 7: THƯ MỤC THAM KHẢO........................................................... 63
PHỤ LỤC.......................................................................................................... 1
A Tải và cài đặt ns-2................................................................................................1
B Cài đặt giao thức định tuyến DLL-XL và OLSR ................................................1


7

DANH MỤC HÌNH
Hình 1.1: Một ứng dụng của WMN trong văn phịng...............................................11

Hình 1.2: Một ví dụ về định tuyến ............................................................................12
Hình 2.1: Các thành phần cơ bản trong WMN theo draft 802.11s ...........................16
Hình 2.2: Kiến trúc các khối chức năng của 802.11s ...............................................17
Hình 3.1: Flooding RREQ để tìm đường ..................................................................21
Hình 3.2: Mỗi nút khi nhận được RREQ sẽ tạo đường đi ngược .............................21
Hình 3.3: Đường đi được tìm thấy ............................................................................21
Hình 3.4: Khi kết nối thay đổi...................................................................................22
Hình 3.5: Multi-point relays......................................................................................23
Hình 3.6: Flooding trong định tuyến.........................................................................24
Hình 3.7: Sự dư thừa trong flooding .........................................................................24
Hình 3.8: Giới hạn flooding bằng phân cấp nhân tạo ...............................................25
Hình 3.9: Giới hạn flooding theo bán kính ...............................................................26
Hình 3.10: Mơ tả luật S1 và S2 .................................................................................27
Hình 3.11: Mơ tả luật C1...........................................................................................28
Hình 3.12: Ví dụ áp dụng các luật của giải thuật XL................................................28
Hình 3.13: Kết quả mơ phỏng giải thuật XL.............................................................29
Hình 3.14: Một ví dụ về mơ hình mạng ....................................................................30
Hình 3.15: Khung nhìn bên trong và bên ngồi của một cặp nút .............................31
Hình 4.1: Một ví dụ về chi phí airtime......................................................................37
Hình 4.2: Giải thuật cập nhật đường đi.....................................................................37
Hình 4.3: Quá trình khởi động nút ............................................................................48
Hình 5.1: Các thành phần của một nút khơng dây trong ns-2...................................52
Hình 5.2: Ví dụ mơ hình mạng đơn giản trong ns-2 .................................................54
Hình 5.3: Mơ hình lưới dùng để mơ phỏng ..............................................................55
Hình 5.4: Mơ hình một mạng ngẫu nhiên sinh bởi ns-2 ...........................................56
Hình 5.5: Tổng lượng thơng điệp cần để mạng đạt đến trạng thái tĩnh ....................57
Hình 5.6: Thời gian cần để mạng đạt trạng thái tĩnh ................................................57
Hình 5.7: Số lượng thơng điệp định tuyến khi mật độ nút thay đổi..........................58
Hình 5.8: Số lượng thơng điệp khi số chi phí kết nối thay đổi .................................59



8

DANH MỤC BẢNG
Bảng 4.1: Các hằng số trong công thức tính airtime.................................................37
Bảng 4.2: Định dạng Frame theo tài liệu draft 802.11s ............................................41
Bảng 4.3: Tập hợp các kết nối đến các nút kề ..........................................................41
Bảng 4.4: Tập hợp các nút kề....................................................................................42
Bảng 4.5: Tập hợp thông tin mạng chia sẻ với một nút kề .......................................42
Bảng 4.6: Tập hợp thông tin mạng của bản thân nút ................................................42
Bảng 4.7: Bảng thông tin đường đi ...........................................................................43
Bảng 4.8: Định dạng thông điệp TC .........................................................................43
Bảng 4.9: Định dạng thông điệp HELLO .................................................................44
Bảng 4.10: Định dạng thông điệp TC .......................................................................45
Bảng 5.1: Số đường đi tối ưu khi dùng thông số xấp xỉ ε = 0.5 ...............................59


9

BẢNG VIẾT TẮT VÀ THUẬT NGỮ
Thuật ngữ
mạng ad-hoc

Ý nghĩa
mạng không dây kết nối với nhau mà không cần điều
khiển tập trung, mỗi nút sẵn sàng chuyển tiếp dữ liệu
cho nút khác.
Ad-hoc On-Demand
một giao thức định tuyến thuộc loại định tuyến reactive
Distance Vector (AODV) cho mạng ad-hoc, được trình bày trong tài liệu RFC

Protocol
3561
Better Approach To
một giải thuật định tuyến cho mạng ad-hoc có thể hỗ trợ
Mobile Ad-hoc
nhiều thiết bị mạng trên cùng một thiết bị.
Networking (BATMAN)
Destination-Sequenced
một giao thức định tuyến cho mạng ad-hoc thuộc loại
Distance-Vector Routing định tuyến proactive dựa trên giải thuật Bellman-Ford.
(DSDV) Protocol
Dynamic Source Routing một giao thức định tuyến thuộc loại định tuyến reactive
(DSR) Protocol
cho WMN.
loại định tuyến mà các nút tham gia định tuyến liên tục
định tuyến proactive
cập nhật và giữ các đường đi tốt nhất.
định tuyến reactive
loại định tuyến mà các nút tham gia định tuyến chỉ tìm
đường đi khi có u cầu.
flooding
q trình gửi broadcast tất cả gói tin nhận được mà
mình khơng phải là đích đến dùng trong định tuyến.
HELLO
thơng điệp dùng trong giao thức định tuyến DLL-XL
của luận văn.
hop-count
số lượng nút trung gian mà thông điệp đi qua.
Hybrid Wireless Mesh
giải thuật định tuyến lai ở lớp hai của mơ hình OSI được

(HWMP) Protocol
trình bày trong tài liệu 802.11s.
Link-Life Based Routing một giao thức định tuyến thuộc loại định tuyến reactive
(LBR) Protocol
dùng cho mạng ad-hoc.
DLL-XL routing
giao thức định tuyến proactive cho mạng WMN được
protocol
thiết kế trong luận văn.
link-state network
thuật ngữ chỉ mạng sử dụng phương thức định tuyến
link-state routing protocol, đây là mạng mà mỗi nút sẽ
sẵn sàng thực hiện việc chuyển tiếp gói cho các nút
khác.
link-state routing
một trong hai loại giao định tuyến cơ bản cho mạng
protocol
chuyển tiếp gói (họ định tuyến còn lại là distance vector
routing ).
Multipoint Relay (MPR) những nút được những nút khác bầu chọn ra để thực
hiện công việc định tuyến.


10

One Laptop Per Child
(OLPC)
Optimized Link-State
Routing (OLSR)
Protocol

TC
Time To Live (TTL)
Wireless Mesh Network
(WMN)
wireless local area
network (WLAN)
Approximate Link-State
(XL) Routing Algorithm

dự án phi lợi nhuận nhằm mục đích tạo cơ hội học tập
cho các trẻ em nghèo trên thế giới bằng cách cung cấp
cho mỗi em một máy tính rẻ, bền và tiết kiệm điện cùng
với các phần mềm mở cho phép tự học.
giải thuật định tuyến thuộc loại định tuyến proactive cho
mạng ad-hoc trên nền địa chỉ IP có tối ưu, được giới
thiệu trong tài liệu RFC 3626.
thông điệp dùng trong giao thức định tuyến DLL-XL
của luận văn.
giới hạn số nút (hoặc thời gian) mà thông điệp được
chuyển tiếp trong mạng trước khi bị loại bỏ.
một mạng gồm các thiết bị không dây kết nối với nhau
theo cấu trúc hỗn độn, không theo chuẩn (mạng con của
mạng ad-hoc).
mạng không dây cục bộ kết nối với nhau bằng sóng
radio.
giải thuật định tuyến dành cho mạng link-state nhằm
tăng hiệu quả định tuyến bằng cách giới hạn số lượng
cập nhật thơng qua việc flooding có lựa chọn, được
trình bày ở hội nghị SIGCOMM’08 (8/2008).



11

Chương 1: PHÁT BIỂU VẤN ĐỀ
1.1 Giới thiệu wireless mesh network (WMN)
Cùng với sự phát triển mạnh mẽ của công nghệ không dây, các thiết bị không dây
cũng phát triển rất nhanh về số lượng, tầm xa và chất lượng dịch vụ. Mạng ad-hoc
là mạng khơng dây khơng có sự điều khiển tập trung mà các nút sẽ thực hiện việc
chuyển tiếp dữ liệu cho các nút khác. Việc xác định nút nào sẽ chuyển tiếp dữ liệu
được xác định động dựa vào cấu trúc mạng lúc đó. Mỗi nút cũng sẽ đóng vai trị
một router và việc định tuyến cho nó là rất quan trọng.
WMN [9] là một mạng khơng dây ad-hoc kết nối với nhau bằng sóng radio trong đó
các nút tương đối ít di chuyển như mạng mobile ad-hoc [8]. WMN có thể được ứng
dụng cho nhiều kiểu hạ tầng mạng không dây khác nhau và một trong số đó là mạng
khơng dây cục bộ WLAN. WMN có khả năng thiết lập nhanh, phủ sóng trong
những khu vực khó thực hiện việc đi dây, có khả năng mở rộng và tự cấu hình để
đảm bảo hiệu suất. Ngồi ra WMN cịn có khả năng tăng tầm phủ sóng nhờ dùng
nhiều nút để chuyển tiếp dữ liệu, giảm năng lượng sử dụng nhờ truyền với năng
lượng thấp và tăng tải nhờ dùng đường đi ngắn.
Do đó WMN thường được dùng trong những trường hợp khẩn cấp như thiên tai,
chữa cháy, chống khủng bố và trong quân đội. WMN cũng được dùng trong những
trường hợp cần tiết kiệm chi phí như cơng ty, trường đại học.
Hình 1.1 mơ tả một ứng dụng của WMN trong một văn phịng.

Hình 1.1: Một ứng dụng của WMN trong văn phòng


12

1.2 Bài toán định tuyến cho WMN

broadcast/multicast

y
3

đường đi tốt nhất từ
x đến y

6

đường đi thay đổi
khi mạng thay đổi

8
5

7

4
1
x

2
z

Hình 1.2: Một ví dụ về định tuyến
Bài tốn định tuyến là bài tốn tìm đường đi giữa các nút trong mạng thỏa mãn một
yêu cầu nào đó để gửi dữ liệu giữa chúng. Hình 1.2 cho ta thấy một ví dụ về định
tuyến cho một mạng nhỏ có 11 nút. Các đường mũi tên đậm là các đường broadcast
từ nút x đến tất cả các nút. Có nhiều đường đi từ nút x đến nút y nhưng trong đó chỉ

có một đường đi tốt nhất. Đường đi từ nút x đến nút y có thể thay đổi khi có một nút
trên đường đi khơng cịn hoạt động. Bài tốn định tuyến phải đảm bảo nhận biết
được sự thay đổi này và tính tốn lại việc định tuyến cho phù hợp với hiện trạng
mạng lúc đó.
Tính đến thời điểm luận văn này được thực hiện (11/2008) đã có rất nhiều giải thuật
thực hiện công việc định tuyến cho WMN, một số giải thuật đã được thương mại
hóa. Tuy nhiên vẫn chưa có một chuẩn định tuyến thống nhất và được chấp nhận
rộng rãi cho WMN.
Các loại giải thuật định tuyến chính cho mạng WMN gồm có:
• Định tuyến proactive
Định tuyến proactive thực hiện định tuyến bằng cách định kỳ gửi thông điệp định
tuyến và bảo trì đường đi trong mạng. Mỗi nút ln giữ một danh sách các đích đến
cũng như các đường đi hợp lệ. Giải thuật cần một lượng lớn thơng điệp để bảo trì
đường đi và tốn nhiều thời gian để tính tốn lại bảng đường đi khi mạng có biến
động. Các giao thức định tuyến proactive tiêu biểu cho WMN là OLSR (Optimized
Link State Routing Protocol) [3], BATMAN (The Better Approach To Mobile Adhoc Networking) [20] và DSDV (Destination Sequenced Distance Vector Routing)
[16].


13

• Định tuyến reactive
Định tuyến reactive thực hiện định tuyến bằng cách flooding thông điệp yêu cầu
định tuyến (Route Request) trong mạng. Khi một nút cần một đường đi nó sẽ gửi
broadcast thông điệp RREQ đến các nút kề. Các nút kề này sau khi nhận được
thông điệp RREQ sẽ broadcast tiếp thông điệp đến các nút lân cận của nó. Q trình
này tiếp tục cho đến khi nút đích (hoặc nút trung gian có giữ đường đi đến đích)
nhận được RREQ thì sẽ sinh ra thơng điệp RREP trả lời và gửi ngược về cho nút có
yêu cầu. Giải thuật sẽ có thời gian đáp ứng chậm khi mạng lớn và sẽ gây ra nghẽn
khi có quá nhiều yêu cầu định tuyến. Các giao thức định tuyến reactive tiêu biểu

cho WMN là AODV (Ad-hoc Ondemand Distance Vector) [17], và DSR (Dynamic
Source Routing) [10].
• Định tuyến lai
Định tuyến lai là giải thuật định tuyến kết hợp định tuyến reactive và định tuyến
proactive. Tùy vào yêu cầu định tuyến cụ thể mà giải thuật sẽ thực hiện theo kiểu
proactive hay reactive. Giao thức định tuyến lai tiêu biểu là HWMP được giới thiệu
trong 802.11s Draft phiên bản 2.0 [11].

1.3 Hướng thực hiện
Tính đến thời điểm luận văn này được thực hiện (11/2008), việc hiện thực định
tuyến chủ yếu thực hiện ở lớp ba của mơ hình mạng OSI. Tuy nhiên việc hiện thực
định tuyến ở lớp ba có một số điểm hạn chế chưa thể giải quyết được như trong tài
liệu [2] đã nêu ra.
Việc thực hiện định tuyến ở lớp hai của mơ hình OSI sẽ giải quyết được những
nhược điểm trên và tối ưu được việc truyền nhận. Việc thực hiện tất cả các dịch vụ
của WMN ở lớp hai cũng sẽ giúp cho WMN có khả năng làm nền cho các dịch vụ ở
các lớp cao hơn và kết nối với các mạng khác dễ dàng mà không cần hiện thực
thêm. Hơn nữa việc hiện thực định tuyến ở lớp hai cịn có thể can thiệp được các
thơng số của mạng không dây (điều này khá quan trọng trong việc quản lý mạng
không dây). Tuy nhiên, việc hiện thực định tuyến ở lớp hai sẽ khó khăn và phức tạp
hơn do phải thực hiện trên nền địa chỉ vật lý và khơng có phân cấp địa chỉ IP như
lớp ba. Ta sẽ tiến hành thiết kế một giao thức định tuyến proactive ở lớp hai của mơ
hình OSI cho WMN.
Giải thuật XL (Approximate Link-state) [12] được trình bày ở hội nghị
SIGCOMM’08 (8/2008) bởi Kirill Levchenko ở khoa khoa học máy tính, đại học
California, San Diago. Đây là giải thuật định tuyến thuộc họ giải thuật định tuyến
link-state. Giải thuật giúp tăng hiệu quả định tuyến bằng cách giới hạn số lượng cập
nhật thơng qua việc flooding có lựa chọn. Thông qua các kết quả mô phỏng, tác giả
đã cho thấy rằng XL tốt hơn những giải thuật định tuyến thuộc họ định tuyến linkstate hiện tại về thời gian đáp ứng cũng như tổng chi phí định tuyến. Tuy nhiên việc
mô phỏng chỉ mới thực hiện ở mức các đối tượng nút trao đổi thông điệp với nhau



14

và tính tốn bảng định tuyến. Đến thời điểm luận văn được thực hiện vẫn chưa có
hiện thực nào để kiểm tra tính hiệu quả của giải thuật XL.
WMN có những tính chất đặc trưng của mạng khơng dây như kết nối khơng ổn
định, chuyển tiếp gói có lỗi đường truyền và các nút có khả năng di chuyển. Ngồi
ra mỗi nút WMN có thể kết nối với nhiều nút khác mà khơng làm tăng chi phí kết
nối nhờ sử dụng sóng radio chứ khơng cần phải đi dây. Khi thiết kế giao thức định
tuyến cho WMN ta phải chú ý đến các tính chất này.
Luận văn sẽ thiết kế và mô phỏng một giao thức định tuyến proactive hữu hiệu ở
lớp hai của mơ hình OSI dựa trên ý tưởng của giải thuật định tuyến XL gọi là giao
thức định tuyến DLL-XL. Giao thức định tuyến proactive này phải phù hợp với các
tính chất đặc trưng của mạng khơng dây và đảm bảo
• Cung cấp ngay thơng tin đúng về đường đi tối ưu khi có u cầu (proactive).
• Số lượng thơng điệp cũng như kích thước thơng điệp dùng để định tuyến là
thấp nhất có thể.
• Thiết kế giao thức ở lớp hai của mơ hình OSI.


15

Chương 2: CÁC CƠNG TRÌNH LIÊN QUAN ĐẾN LUẬN VĂN
Các cơng trình liên quan đến luận văn chủ yếu là các cơng trình liên quan đến
802.11s, một đề xuất chuẩn giao tiếp chung dành cho WMN ở lớp hai của mơ hình
OSI. Phần 1 sẽ giới thiệu sơ lược về 802.11s. Phần 2 và phần 3 sẽ giới thiệu về hai
dự án rất lớn sử dụng 802.11s, đó là dự án OPLC và dự án open80211s.

2.1 Draft IEEE 802.11s

Draft 802.11s [11] là bản phác thảo của một nhóm nghiên cứu thuộc tổ chức IEEE
thành lập từ tháng 9 năm 2003 nhằm thiết kế một chuẩn giao tiếp chung cho WMN.
Đến ngày luận văn này được thực hiện thì bản phác thảo có phiên bản Draft 2.0 và
vẫn chưa được IEEE thông qua do chưa đủ số phiếu yêu cầu. Tuy vẫn chưa thành
chuẩn IEEE nhưng bản phác thảo này đã đề ra khá chi tiết về việc kết nối và giao
tiếp cho WMN.
WMN được mô tả trong draft 802.11s gồm có các thành phần sau
• Mesh Point (MP): bất kỳ thiết bị nào của chuẩn 802.11 có lớp MAC và lớp
giao tiếp vật lý trong WMN và hỗ trợ các dịch vụ của WMN.
• Mesh Access Point (MAP): bất kỳ một Mesh Point nào mà nó cũng chính là
một Access Point theo chuẩn 802.11s.
• Station (STA): các máy trạm có thiết bị giao tiếp theo chuẩn 802.11s
• Mesh Link: một kết nối hai chiều theo chuẩn 802.11 giữa hai Mesh Point.
• Mesh Path: một tập hợp các Mesh Link kết nối từ Mesh Point nguồn đến
Mesh Point đích
• Link Metric: một tiêu chuẩn dùng để đánh giá hiệu suất và chất lượng của
một Mesh Link trong một Mesh Path.
• Mesh Service: tập hợp các dịch vụ được cung cấp bởi WMN nhằm hỗ trợ
điều khiển, quản lý và thao tác trong WMN.
Hình 2.1 chỉ cho ta thấy rõ các thành phần và tương tác giữa các thành phần trong
WMN theo draft 802.11s


16

wired infrastructure

MAP

MP


MAP

STA

MAP

MAP

STA

MP
STA

STA

STA

STA

radio link
mesh radio link

Hình 2.1: Các thành phần cơ bản trong WMN theo draft 802.11s
( page 19)
Phạm vi thiết kế của draft 802.11s là tích hợp dịch vụ và giao thức của WMN với
chuẩn không dây 802.11 ở lớp MAC. Hình 2.2 cho ta thấy kiến trúc các khối chức
năng của 802.11s gồm có
• Khối chức năng định tuyến, chuyển tiếp gói: Chứa chức năng phát hiện node
lân cận và chức năng thu thập các tham số đo trạng thái đường liên kết vô

tuyến sử dụng cho định tuyến. Các giao thức định tuyến sử dụng địa chỉ
MAC làm địa chỉ nhận dạng cũng như cho chức năng chuyển tiếp gói. Để sử
dụng hiệu quả nguồn tài ngun vơ tuyến, giao thức định tuyến sử dụng các
tham số vô tuyến và các kênh đa tần số phù hợp với các điều kiện vơ tuyến
để định tuyến.
• Khối đo lường và tính tốn: Chứa chức năng tính tốn các tham số vô tuyến
được sử dụng trong giao thức định tuyến và chức năng đo lường các điều
kiện vô tuyến để lựa chọn kênh tần số.
• Khối điều phối truy nhập phương tiện: Bao gồm các chức năng chống suy
giảm hiệu năng do các hiện tượng che dấu thông tin nút, các chức năng thực
hiện điều khiển ưu tiên, điều khiển tắc nghẽn, điều khiển quản lý và chức
năng kích hoạt sử dụng lại tần số.
• Khối bảo mật: Chứa các chức năng bảo mật để bảo vệ các khung dữ liệu
mang trên mạng và các khung quản lý được sử dụng bởi các chức năng quản
lý như giao thức định tuyến. Các phương pháp an ninh cho WLAN được
định nghĩa trong chuẩn 802.11i.


17

• Khối liên mạng: IEEE 802.11 là một phần trong cấu trúc IEEE 802 vì thế
WMN thực hiện kết nối với các mạng khác (ví dụ: 802.3) thơng qua chức
năng cầu nối nằm tại MPP.
• Khối chức năng quản lý và cấu hình: Khối này gồm một giao diện WMN
được sử dụng để tự động thiết lập các tham số tần số vơ tuyến MP với mục
đích quản lý chính sách chất lượng dịch vụ.

802.11s

Kết nối liên mạng

Định tuyến
và chuyển
tiếp gói

Quản lý và cấu hình WMN
Đo lường
và tính tốn
mạng

Điều phối
truy nhập
phương
tiện

Bảo mật

Lớp MAC thấp (IEEE 802.11 e/n)

Lớp vật lý (IEEE 802.11 a/b/g/n)

Hình 2.2: Kiến trúc các khối chức năng của 802.11s
Mục tiêu của draft 802.11s là nhằm kết nối những nút của WMN với nhau thành
một mạng không dây phân bố khơng cần quản lý tập trung và có thể tự cấu hình
nhằm đạt được các mục tiêu sau
• Tăng phạm vi phủ sóng và tính mềm dẻo của mạng (so với việc dùng access
point).
• Tăng độ tin tưởng của mạng (mạng vẫn hoạt động tốt kể cả khi có một số nút
khơng hoạt động).
• Đảm bảo tính bảo mật (tích hợp vào 802.11i).
• Đảm bảo truyền nhận đa phương tiện giữa các thiết bị.

• Tối thiểu năng lượng sử dụng của mạng.
• Tương thích được với các chuẩn trước đó.
• Đảm bảo chính xác giao tiếp giữa các nút mạng.
• Có khả năng tăng tải của mạng.
Hiện nhóm phát triển draft 802.11s (802.11 TGs) đã đưa ra bản phác thảo draft2.0
vào tháng 9 năm 2008. Tuy vẫn chưa được thông qua nhưng draft 802.11s đã được
hiện thực trong một số dự án lớn như dự án OLPC và dự án open80211s vì tính tiện
lợi cũng như các tiềm năng mà WMN có thể mang lại.


18

2.2 Dự án OLPC
Dự án mỗi trẻ em một máy tính (OLPC) [15] là một dự án phi lợi nhuận nhằm mục
đích tạo cơ hội học tập cho các trẻ em nghèo trên thế giới bằng cách cung cấp cho
mỗi em một máy tính rẻ, bền và tiết kiệm điện cùng với các phần mềm mở cho phép
tự học. Khi nhận được các máy tính này, các trẻ em nghèo sẽ có nhiều cơ hội hơn
trong học tập; được học, được chia sẻ và được kết nối với nhau cũng như kết nối với
thế giới.
Dự án OLPC được hỗ trợ tài chính và kỹ thuật từ những cơng ty hàng đầu trong lĩnh
vực máy tính như AMD, Intel, Brightstar Corporation, eBay, Google, Microsoft,
Marvell, News Corporation, SES, Nortel Networks và Red Hat. Giá hiện tại một
máy tính xách tay XO của dự án là khoảng 175 USD. Nhưng các nhà sản xuất máy
tính XO hy vọng có thể giảm giá chỉ cịn 75 USD cho các thế hệ máy tính XO tiếp
theo. Máy được cài đặt cả Windows lẫn Linux và chạy tốt trên cả hai hệ điều hành
này. Cho đến tháng 5 năm 2009, dự án đã nhận được đơn đặt hàng cho khoảng
1374500 máy tính XO. Chi tiết về dự án có thể tìm thấy ở trang web của dự án
().
Dự án OLPC là dự án đầu tiên hiện thực giao tiếp cho WMN sử dụng thiết kế của
draft 802.11s trên máy tính XO. Tuy vậy hiện thực dự án có một số điểm khác so

với draft 802.11s dành cho WMN như:
• Hỗ trợ kết nối bất đối xứng.
• Hỗ trợ nhiều metric khác nhau.
• Chỉ hiện thực một phần của 802.11s.
• Sử dụng chip Marvell 88W8388 hỗ trợ chuẩn 802.11b/g và chế độ khơng
phân loại có thể chạy như một bộ định tuyến ngay khi bộ xử lý chính khơng
làm việc. Tuy vậy chip này bị hạn chế về bộ nhớ nên không thể hiện thực
một số chức năng như draft 802.11s đưa ra
Việc định tuyến giữa các máy XO trong WMN dựa trên giải thuật HWMP mà draft
802.11s đã đưa ra. Các máy sẽ kết nối với nhau thành một WMN khi dùng chung
tần số và giao tiếp không theo chuẩn. Việc định tuyến chỉ được thực hiện khi có u
cầu tìm đường đi giữa các máy. Định tuyến trong OLPC được hiện thực ở lớp hai
của mơ hình OSI và dùng địa chỉ MAC thay thế địa chỉ IP để có thể can thiệp được
các thơng số của mạng không dây (điều này khá quan trọng trong việc quản lý mạng
không dây).


19

2.3 Dự án open80211s
Dự án open80211s [21] là một dự án được hình thành dưới sự liên kết của nhiều tổ
chức và công ty lớn nhằm hiện thực draft 802.11s dưới hình thức mã nguồn mở.
Phần hiện thực của dự án open80211s được tiến hành trên hệ điều hành mở Linux
với các thiết bị không dây được hỗ trợ. Các dịng chipset được hỗ trợ gồm có
Atheros, Broadcom, Marvell, Intersil's Prism54 và Ralink. Phần hiện thực của dự án
thực hiện theo chuẩn 802.11s sử dụng định tuyến lai HWMP ở lớp hai dùng metric
là airtime. Chi tiết về dự án có thể tìm thấy tại trang web của dự án
().
Mục tiêu của dự án open80211s là hiện thực draft 802.11s và đưa phần mềm này
đến người dùng một cách rộng rãi để cuối cùng có thể kết nối các thiết bị không dây

dùng hệ điều hành Linux thành một mạng rất lớn.
Từ 4/3/2008 dự án đã hiện thực được việc kết nối các máy với nhau theo draft
802.11s trên một số thiết bị không dây sử dụng chip Atheros, Broadcom và Marvell.
Phần định tuyến của dự án open80211s được thực hiện ở lớp dữ liệu của mơ hình
OSI và sử dụng giải thuật HWMP như draft 802.11s đã đưa ra. Các hỗ trợ mới nhất
(trong phiên bản mới nhất 0.2.1) gồm quản lý kết nối, quản lý gửi tràn, định tuyến
HWMP sử dụng airtime metric, đáp ứng tần số cho nút kề, dị tìm WMN, làm sạch
card mạng dùng cho beaconing và chuyển tiếp gói.


20

Chương 3: CƠ SỞ LÝ THUYẾT và PHƯƠNG PHÁP GIẢI
QUYẾT VẤN ĐỀ
Phần III gồm có 4 phần chính. Phần một giới thiệu hai giải thuật định tuyến tiêu
biểu thuộc loại giải thuật định tuyến proactive và reactive để thấy được cách thức
định tuyến của từng loại giải thuật. Phần hai giới thiệu kỹ thuật flooding dùng trong
định tuyến proactive, các hạn chế và phương thức khắc phục flooding. Phần ba giới
thiệu giải thuật định tuyến XL. Phần bốn giới thiệu hướng thực hiện của luận văn,
đó là việc sử dụng ý tưởng của giải thuật định tuyến XL vào giao thức định tuyến
của luận văn.

3.1 Một số giải thuật định tuyến tiêu biểu
Việc định tuyến cho WMN có hai hướng chính tùy vào yêu cầu của ứng dụng cụ thể
và số lượng nút. Người ta chia định tuyến thành hai loại chính là định tuyến reactive
và định tuyến proactive. Định tuyến reactive chỉ tìm đường đi khi có u cầu bằng
cách flooding các gói yêu cầu định tuyến trong mạng. Trong khi đó, định tuyến
proactive sẽ tính tốn và giữ đường đi tối ưu đủ mới bằng cách định kỳ gửi thông
tin cập nhật trong mạng
Giải thuật định tuyến reactive tiêu biểu là giải thuật AODV được trình bày trong tài

liệu RFC 3561 [17]. Còn giải thuật định tuyến proactive tiêu biểu là giải thuật
OLSR trình bày trong tài liệu RFC 3626 [3].
3.1.1 Giải thuật AODV
Giải thuật định tuyến AODV thuộc loại giải thuật định tuyến reactive. Giải thuật
định tuyến AODV cho phép tìm đường tự động giữa nhiều nút trong WMN. Giải
thuật định tuyến AODV cho phép tìm đường nhanh chóng trong mạng có nhiều biến
động và khơng giữ đường đi khơng cịn sử dụng để giảm chi phí định tuyến trên
tồn mạng.
Giải thuật sử dụng các thơng điệp Route Request (RREQ), Route Reply (RREP) và
Route Error (RERR) để thực hiện định tuyến. Khi một nút cần thiết lập đường đi
đến một nút đích nó sẽ flooding thơng điệp RREQ trong mạng đến các nút kề. Nút
kề này sau khi nhận được gói tin yêu cầu định tuyến RREQ sẽ chuyển tiếp gói yêu
cầu đến các nút lân cận khác. Khi nút đích (hoặc nút trung gian có giữ đường đi đến
đích) nhận được yêu cầu sẽ sinh ra thông điệp RREP trả lời yêu cầu và gửi ngược
về cho nút có yêu cầu. Số lượng nút tối đa mà thơng điệp RREQ có thể đi qua được
quy định bởi trường TTL trong thông điệp.
Mỗi nút cũng sẽ quản lý trạng thái của nút kế tiếp trong một đường đi tích cực. Khi
một nút phát hiện nút kế tiếp không hoạt động sẽ gửi thông điệp RERR cho các nút
thuộc danh sách các nút trước nó có sử dụng nó làm đường đi. Danh sách các nút
này được thu thập trong q trình sinh và gửi thơng điệp RREP.


21

Giải thuật sử dụng một bảng đường đi để quản lý thơng tin về các đường đi tích cực
và dùng phương pháp đánh số thứ tự thông điệp để phân biệt độ mới của thơng điệp
(đảm bảo khơng gửi vịng thơng điệp cũ).
Các hình 3.1, 3.2, 3.3, 3.4 thể hiện quá trình tạo đường đi từ S đến D gồm có: gửi
RREQ, tạo đường đi ngược về đích cũng như gửi RERR khi kết nối của một nút nào
đó thay đổi.


Hình 3.1: Flooding RREQ để tìm đường
( />
Hình 3.2: Mỗi nút khi nhận được RREQ sẽ tạo đường đi ngược
( />
Hình 3.3: Đường đi được tìm thấy
( />

22

Hình 3.4: Khi kết nối thay đổi
( />Giải thuật AODV được dùng trong mạng không dây từ vài chục nút đến hàng ngàn
nút trong đó số lượng u cầu tính tốn đường đi giữa các nút không nhiều và
đường đi không bắt buộc phải là đường đi tối ưu. Mỗi nút phải tin tưởng các nút
khác trong mạng, khơng có quản lý tập trung và chỉ tính đường đi khi có yêu cầu
nhằm nâng cao hiệu suất, giảm lượng thông điệp điều khiển trong mạng.
3.1.2 Giải thuật OLSR
Giải thuật OLSR [3] là giải thuật định tuyến thuộc loại giải thuật định tuyến
proactive có tối ưu dùng trong mạng khơng dây ad-hoc. Giải thuật OLSR cung cấp
kết quả định tuyến ngay khi có u cầu dựa vào tính chủ động của việc tính tốn
định tuyến.
Mỗi nút sẽ chọn một tập nút xung quanh nó làm các nút MPR (phải đảm bảo kết nối
này là đối xứng). Giải thuật OLSR chỉ sử dụng các nút MPR để flooding thông điệp
định tuyến nhằm giảm lượng thông điệp định tuyến trong mạng. Các nút MPR sẽ
thơng báo cho các nút khác trong mạng rằng nó có thể đi đến những nút đã chọn nó
làm MPR.
Hơn nữa giải thuật OLSR chỉ cần flooding một phần thông tin kết nối trong mạng là
có thể tính được đường đi ngắn nhất nên giúp giảm dung lượng thông điệp điều
khiển. Phần thơng điệp được flooding này chính là chi phí kết nối từ MPR đến các
nút đã bầu nó làm MPR.