HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG

HOÀNG TRỌNG MINH CẢI THIỆN HIỆU NĂNG MẠNG HÌNH LƢỚI
KHÔNG DÂY QUA KỸ THUẬT ĐỊNH TUYẾN QOS

Chuyên ngành: Kỹ thuật Viễn thông
Mã số: 62.52.70.05

LUẬN ÁN TIẾN SỸ KỸ THUẬT

NGƢỜI HƢỚNG DẪN KHOA HỌC
1. PGS.TS. Nguyễn Quốc Bình
2. PGS.TS. Nguyễn Tiến Ban Hà Nội - 2013
i
LỜI CAM ĐOAN
Nghiên cứu sinh xin cam đoan đây là công trình nghiên cứu của chính mình.
Các số liệu, kết quả trong luận án là trung thực và chƣa từng đƣợc công bố trong bất
cứ công trình của bất kỳ tác giả nào khác.


iii
MỤC LỤC
LỜI CAM ĐOAN i
LỜI CẢM ƠN ii
MỤC LỤC iii
THUẬT NGỮ VIẾT TẮT vi
BẢNG KÝ HIỆU ix
DANH MỤC CÁC HÌNH VẼ xi
DANH MỤC CÁC BẢNG xii
MỞ ĐẦU 1
CHƢƠNG 1: KHÁI QUÁT CÁC VẤN ĐỀ LIÊN QUAN TỚI HIỆU
NĂNG MẠNG HÌNH LƢỚI KHÔNG DÂY 7
1.1 TỔNG QUAN MẠNG HÌNH LƢỚI KHÔNG DÂY 7
1.1.1 Kiến trúc mạng hình lƣới không dây 8
1.1.2 Một số ứng dụng điển hình 9
1.2 CHẤT LƢỢNG DỊCH VỤ 11
1.2.1 Khái quát về chất lƣợng dịch vụ 11
1.2.2 QoS với tiếp cận xuyên lớp trong WMN 13
1.3 KỸ THUẬT ĐỊNH TUYẾN QOS 13
1.3.1 Kỹ thuật định tuyến 13
1.3.2 Kỹ thuật định tuyến QoS 19
1.4 TÌNH HÌNH NGHIÊN CỨU TRÊN THẾ GIỚI VÀ TẠI VIỆT NAM 20
1.4.1 Hiệu năng và các tham số phản ánh 20
1.4.2 Các tiếp cận cải thiện hiệu năng 22
1.5 KẾT LUẬN CHƢƠNG 34
CHƢƠNG 2: BÀI TOÁN MÔ HÌNH HÓA GIAO THỨC ĐIỀU KHIỂN

4.3 ĐỀ XUẤT THAM SỐ ĐỊNH TUYẾN IARM 89
4.3.1 Tham số phản ánh nhiễu đề xuất IARM 90
4.3.2 Phân tích khả năng tƣơng thích 93
4.3.3 Tích hợp tham số IARM trong OLSR 95
4.4 MÔ PHỎNG VÀ THẢO LUẬN 101
4.4.1 Giới thiệu công cụ mô phỏng NS-2 101
4.4.2 Kịch bản mô phỏng 103
4.4.3 Kết quả và thảo luận 105
4.5 KẾT LUẬN CHƢƠNG 109
v
KẾT LUẬN VÀ KIẾN NGHỊ 111
CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA TÁC GIẢ 115
TÀI LIỆU THAM KHẢO 117
CAF
Channel Available Fraction
Tỷ lệ thời gian khả dụng kênh
CBR
Constant Bit Rate
Tốc độ bít cố định
CDMA
Code Division Multiple Access
Đa truy nhập phân chia theo mã
CFP
Contention Free Period
Chu kỳ không có tranh chấp
CP
Contention Period
Chu kỳ có tranh chấp
CSMA
Carrier Sense Multiple Access
Đa truy nhập cảm nhận sóng
mang
CSMA/CA
Carrier Sense Multiple
Access/Collision Avoidance
Đa truy nhập cảm nhận sóng
mang tránh xung đột
CSMA/CD
Carrier Sense Multiple
Access/Collision Detection
Đa truy nhập cảm nhận sóng
mang phát hiện xung đột
CTS

Tập dịch vụ mở rộng
ETSI
European Telecomunications
Viện nghiên cứu viễn thông Châu
vii
Standard Institute
Âu
ETT
Expected Transmission Time
Thời gian truyền dẫn kỳ vọng
ETX
Expected Transmission Count
Tham số truyền dẫn kỳ vọng
FDMA
Frequency Division Multiple
Access
Đa truy nhập phân chia theo tần
số
HSLS
Hazy-Sighted Link State
Routing
(Giao thức) định tuyến trạng thái
liên kết Hazy-Sighted
iAWARE
Interference AWARE (routing
metric)
(Tham số định tuyến) phản ánh

Transmission Time
(Tham số định tuyến) thời gian
truyền dẫn kỳ vọng phản ánh tải
LLC
Logical Link Control
Điều khiển liên kết logic
MAC
Medium Access Control
Điều khiển truy nhập phƣơng tiện
MCOP
Multi-Constrained Optimal
Path
Tối ƣu đƣờng dẫn đa ràng buộc
MCP
Multi Constrained Problem
Bài toán đa ràng buộc
MoS
Mean of Score
Thang điểm đánh giá trung bình
MPR
Multi Point Relay
Chuyển tiếp đa điểm
NAV
Network Allocation Vector
Vectơ chỉ định mạng
NUM
Network Utility Maximization
Tối đa hóa lợi ích mạng
OFDM
Orthogonal Frequency Division

RREQ
Route Request
Yêu cầu tuyến
RTS
Request-to-Send
Yêu cầu để gửi
SIFS
Short InterFrame Space
Khoảng liên khung ngắn
TC
Topology Control
Điều khiển cấu hình
TCP
Transport Control Protocol
Giao thức điều khiển giao vận
TDMA
Time Division Multiple Access
Đa truy nhập phân chia theo thời
gian
VANET
Vehicular Ad-Hoc Network
Mạng tùy biến xe cộ
VCS
Vitual Carrier Sense
Cảm nhận sóng mang ảo
WCETT
Weighted Cumulative Expected
Transmission Time
(Tham số) thời gian truyền dẫn kỳ
vọng trọng số tích lũy

Ngƣỡng cảm nhận


Trễ truyền lan


Tốc độ phục vụ của hệ thống


Độ dài một khe thời gian vật lý


Tốc độ đến của gói tin


Khoảng bảo vệ xung quanh một nút tránh nhiễu
B

Trạng thái break trong mô hình kênh 4 trạng thái
card( )A

Lực lƣợng của tập A
ij
c

Trọng số liên kết giữa nút i và nút j
ij
C

Trọng số liên kết tối thiểu giữa nút i và nút j

Trạng thái idle trong mô hình nút và kênh 4 trạng thái
packet
L

Độ dài của một gói tin
m

Số lần truyền dẫn lại cực đại
M
Số lƣợng nút trung bình trong miền cảm nhận của một nút
H
M

Số lƣợng nút trung bình trong miền nút ẩn
N

Số lƣợng nút trung bình trong miền truyền dẫn của một nút
c
p

Xác suất xung đột
b
P

Xác suất lỗi bit
packet
L
e
P


r

Tỷ lệ chuyển phát gói tin thành công hƣớng về
packet
R

Tốc độ gói tin
s
R

Bán kính miền cảm nhận
t
R

Bán kính miền truyền dẫn
,sS

Trạng thái success trong mô hình nút và kênh 3,4 trạng thái


Tham số điều hòa
packet
T

Thời gian truyền dẫn gói tin
Th

Thông lƣợng mạng
W


st
p
và
'
st
p
với
M
thay đổi 50
Hình 2.8: Khảo sát giá trị
st
p
và
'
st
p
với sự thay đổi của
t
p
50
Hình 3.1: Kiến trúc và hàm phối hợp của IEEE 802.11 [46] 54
Hình 3.2: Lƣợc đồ truy nhập kênh cơ bản trong CSMA/CA [46] 55
Hình 3.3: Mô tả truyền thông giữa nút phát
i
và nút nhận
j
59
Hình 3.4: Chuỗi Markov của mô hình nút 4 trạng thái 60
Hình 3.5: Mô tả tính toán miền giao S
I

Hình 4.6: So sánh trễ trung bình gói tin giữa OLSR và OLSR-IARM 107
Hình 4.7: Tỷ lệ chuyển phát gói tin thành công giữa OLSR và OLSR-IARM 107
Hình 4.8: So sánh tỷ lệ tổn thất gói tin giữa OLSR và OLSR-IARM 108
Hình 4.9: So sánh thông lƣợng của OLSR và OLSR-IARM 109

DANH MỤC CÁC BẢNG
Bảng 3.1: Ký hiệu các tham số 58
Bảng 3.2: Các tham số mô phỏng 70
Bảng 4.1: Các nội dung sửa đổi để khai báo và định dạng tham số 98
Bảng 4.2: Các nội dung sửa đổi để gửi nhận bản tin định tuyến 99
Bảng 4.3: Các nội dung sửa đổi để cập nhật thông tin định tuyến 100
Bảng 4.4: Các nội dung sửa đổi để tính toán định tuyến 100
Bảng 4.5: Tham số mô phỏng giao thức OLSR và OLSR-IARM 105
1
MỞ ĐẦU
Trong những năm gần đây, lĩnh vực truyền thông không dây đã chứng kiến
sự ra đời của hàng loạt các giải pháp công nghệ mới nhằm đáp ứng các yêu cầu, tiện
ích mới của ngƣời sử dụng. Trong đó, mạng hình lƣới không dây WMN (Wireless
Mesh Network) đƣợc cấu thành bởi các bộ định tuyến bố trí tĩnh cùng với các thiết
bị đầu cuối di động kết nối không dây với nhau theo hình lƣới, đƣợc coi là một giải
pháp then chốt của mạng không dây thế hệ mới nhằm mục tiêu cung cấp truy nhập
Internet không dây băng rộng với vùng phủ lớn. Truyền dẫn trong WMN đƣợc thực
hiện dựa trên các chuẩn công nghệ phổ biến hiện nay nhƣ IEEE 802.11, IEEE
802.15, IEEE 802.16… Với cấu trúc hình lƣới, WMN khắc phục sự hạn chế của
hiện tƣợng che khuất tầm nhìn thẳng trong các kết nối không dây truyền thống, tăng
dung lƣợng bằng các truyền dẫn tốc độ cao trong khoảng cách ngắn, tăng độ tin cậy
truyền thông cũng nhƣ giảm thiểu độ phức tạp trong triển khai hạ tầng mạng truy

thái hiện thời của mạng, mang lại sự cải thiện hiệu năng mạng. Vì vậy, theo hƣớng
tiếp cận xuyên lớp giữa lớp định tuyến và lớp MAC, luận án này phát triển một mô
hình giải tích mới phản ánh chất lƣợng liên kết và sử dụng nhƣ một thành phần dự
báo chất lƣợng liên kết kết hợp với thành phần đo chủ động sẵn có của giao thức
định tuyến tối ƣu trạng thái OLSR (Optimized Link State Routing) để đề xuất một
tham số định tuyến mới, cải thiện đƣợc các thông số hiệu năng WMN. Các kết quả
nghiên cứu đƣợc đánh giá và minh chứng qua phân tích số và mô phỏng.
Mục tiêu, đối tƣợng và phạm vi nghiên cứu
Với mục tiêu tìm kiếm một giải pháp khả thi cải thiện hiệu năng WMN thông
qua kỹ thuật định tuyến QoS, luận án này đề xuất một tham số định tuyến mới và
đƣợc tích hợp vào giao thức định tuyến OLSR nhằm cải thiện các thông số hiệu
năng chính của mạng cụ thể nhƣ: thông lƣợng, độ trễ và tỷ lệ tổn thất gói tin.
Các phân tích số và mô phỏng kiểm chứng đƣợc thực hiện trong kịch bản
mạng hình lƣới không dây sử dụng chuẩn IEEE 802.11b, đơn kênh, các nút mạng
phân bố đều và các thông số lớp Vật lý tiêu chuẩn. Các giả thiết trên đƣợc lựa chọn
nhằm thể hiện tính tổng quát và phản ánh tƣờng minh tác động của nhiễu liên luồng
tới quyết định định tuyến. Các kết quả mô phỏng đã chỉ ra giao thức định tuyến
3
OLSR với tham số định tuyến đề xuất đạt đƣợc mức cải thiện đáng kể khi so sánh
với giao thức định tuyến OLSR nguyên gốc.
Nhiệm vụ nghiên cứu
Để đạt đƣợc mục tiêu và đối tƣợng nghiên cứu đã nêu ở trên, nhiệm vụ
nghiên cứu đƣợc nghiên cứu sinh tập trung vào các vấn đề sau:
1. Nghiên cứu tổng quát về ảnh hƣởng của các đặc tính chủ yếu trong mạng
hình lƣới không dây tới hiệu năng mạng, cơ sở học thuật của bài toán định
tuyến QoS, các giải pháp cải thiện hiệu năng đƣợc đề xuất trong các nghiên
cứu trƣớc dƣới góc độ sử dụng công cụ toán học. Từ đó sáng tỏ cách thức

mục theo cấu trúc sau:
Chƣơng 1 với tiêu đề “Khái quát các vấn đề liên quan tới hiệu năng mạng
hình lƣới không dây” trình bày các đặc tính kỹ thuật của mạng hình lƣới không dây,
các khái niệm cơ bản về QoS, bài toán cung cấp QoS và tính đặc thù của kỹ thuật
định tuyến QoS trong WMN. Trong đó, đáng chú ý là nội dung khảo sát về các giải
pháp cải thiện hiệu năng WMN dƣới góc độ toán học để làm sáng tỏ phạm vi
nghiên cứu và cách tiếp cận của luận án. Một phần nội dung của chƣơng liên quan
tới vấn đề khảo sát tham số định tuyến QoS trong WMN là nội dung trong bài báo
khoa học có tiêu đề “Khảo sát hiệu năng các tham số định tuyến trong mạng hình
lưới không dây WMN”, công bố trên Tạp chí Khoa học và Công nghệ - Các trƣờng
đại học kỹ thuật, số 76, năm 2010; và bài báo khoa học có tiêu đề “Nghiên cứu
tham số định tuyến mới phản ánh nhiễu trong mạng hình lưới không dây IEEE
802.11”, công bố trên Tạp chí nghiên cứu Khoa học và Công nghệ Quân sự, số 13,
2011.
Chƣơng 2 với tiêu đề “Bài toán mô hình hóa giao thức điều khiển truy nhập
phƣơng tiện trong điều kiện bão hòa” trình bày nghiên cứu khảo sát về các giải pháp
mô hình hóa giao thức điều khiển truy nhập phƣơng tiện của các tác giả trƣớc với
giả thiết luôn có gói tin cần chuyển trong hàng đợi. Những vấn đề trình bày trong
mục 2.3 và 2.4 của chƣơng này là kết quả nghiên cứu của nghiên cứu sinh liên quan
đến việc hoàn thiện kết quả đề xuất của các tác giả trƣớc. Một phần nội dung của
chƣơng 2 đã đƣợc trình bày trong bài báo khoa học có tiêu đề “A Novel
5
Computation for Supplementing Interference Analytical Model in 802.11-based
Wireless Mesh Networks”, công bố trên Tạp chí Khoa học và Công nghệ, Tập 50,
số 2, năm 2012.
Chƣơng 3 với tiêu đề “Xây dựng mô hình giải tích đánh giá chất lƣợng liên
kết” trình bày các nội dung nghiên cứu của nghiên cứu sinh liên quan tới việc đề

Hà nội, tháng 12 năm 2013
7
CHƢƠNG 1: KHÁI QUÁT CÁC VẤN ĐỀ LIÊN QUAN TỚI
HIỆU NĂNG MẠNG HÌNH LƢỚI KHÔNG DÂY
Tóm tắt: Nội dung của chương khái quát các đặc tính kỹ thuật của mạng hình lưới
không dây cùng với các ứng dụng điển hình, các vấn đề nền tảng của chất lượng
dịch vụ QoS (Quality of Service), tiếp cận giải quyết vấn đề hỗ trợ QoS trong mạng
hình lưới không dây và các điểm mấu chốt của kỹ thuật định tuyến QoS. Đặc biệt,
các giải pháp cải thiện hiệu năng của các nghiên cứu gần đây được tóm tắt qua
khía cạnh sử dụng công cụ toán học nhằm sáng tỏ cách thức tiếp cận học thuật của
luận án.
1.1 TỔNG QUAN MẠNG HÌNH LƢỚI KHÔNG DÂY
Trong những năm gần đây, truyền thông không dây đang phát triển rất mạnh
mẽ trong cả mạng không dây diện rộng và mạng không dây cục bộ, đem tới rất
nhiều ứng dụng dựa trên kết nối không dây. Tuy nhiên, qua các đặc tính kiến trúc và
công nghệ của các mạng truyền thống cho thấy một số điểm hạn chế trong việc
cung cấp yêu cầu kết nối và dịch vụ. Cụ thể, các mạng di động tế bào cung cấp vùng
phủ lớn nhƣng tốc độ bị hạn chế, trong khi các mạng truy nhập không dây cục bộ
cho phép truyền dẫn tốc độ cao nhƣng đi liền với đó là vùng phủ bị giới hạn do đặc
điểm công nghệ truyền dẫn tại phổ tần số cao. Vì vậy, giải pháp mạng kết nối hình
lƣới không dây WMN (Wireless Mesh Network) đã đƣợc hình thành nhƣ một giải
pháp then chốt cho mạng truy nhập không dây băng rộng với vùng phủ rộng [64],
[66], [72]. Dƣới góc độ ứng dụng công nghệ, WMN đƣợc phát triển mạnh mẽ nhờ
một số ƣu điểm chính nhƣ sau: (i) WMN có thể triển khai trong khu vực rộng với
giá thành triển khai thấp; (ii) công nghệ mạng hình lƣới có thể khắc phục các tuyến
kết nối có tầm che khuất và tổn thất đƣờng truyền lớn để mở rộng vùng phủ dịch vụ;
(iii) sử dụng các công nghệ truyền thông tầm ngắn, WMN có thể cải thiện tốc độ

thấp và độ ràng buộc tài nguyên cao.
Trong kiến trúc WMN phân cấp, các bộ định tuyến đƣợc kết nối hình lƣới
tạo nên hạ tầng mạng lõi không dây và kết nối trực tiếp tới các thiết bị đầu cuối
hoặc tới các mạng khác. Trách nhiệm tự cấu hình và duy trì hoạt động mạng đƣờng
trục WMN thuộc về các bộ định tuyến WMN. Bộ định tuyến hình lƣới còn đƣợc bổ
sung chức năng cầu nối và chức năng cổng (Bridge/Gateway) để kết nối tới các hạ
tầng mạng khác hay Internet. Kiến trúc này cho phép thực hiện quản lý tài nguyên
và tính di động tại các bộ định tuyến hình lƣới. Khi các thiết bị khách hàng di
chuyển trong cấu trúc không ràng buộc với hạ tầng mạng sẽ tạo ra nhóm hoặc tổ
chức mạng mới mang tính chất tùy biến. Trong cấu trúc phân nhóm, một số thông
tin trạng thái mạng đƣợc lƣu trữ cục bộ và các nút đóng vai trò trƣởng nhóm sẽ thực
hiện nhiệm vụ quản lý và điều phối thông tin giữa các nút trong mạng. Khi mạng có
sự biến động, chỉ các nút trƣởng nhóm có nhiệm vụ gửi các thông tin tóm tắt của
nhóm tới các nút khác nhằm giảm thiểu thông tin thừa trong quá trình quản lý và
điều khiển mạng.
Kiến trúc WMN lai ghép là tổ hợp của kiến trúc WMN phân cấp và kiến trúc
WMN phẳng. Các thiết bị khách hàng đƣợc kết nối hình lƣới có thể truy nhập tới
mạng lõi thông qua các bộ định tuyến WMN hoặc thiết bị khách hàng khác. Sự lai
ghép ở đây còn đƣợc thể hiện qua khía cạnh sử dụng các mạng không dây khác để
truyền thông, kiến trúc WMN lai ghép có thể sử dụng nhiều công nghệ khác nhau
cho cả mạng đƣờng trục và mạng truy nhập. Kiểu kiến trúc này hứa hẹn mang đến
rất nhiều lợi ích do khả năng kết hợp và liên điều hành với nhiều hạ tầng công nghệ
mạng khác nhau đem lại.
1.1.2 Một số ứng dụng điển hình
Nhờ vào các ƣu điểm về mặt cấu hình và công nghệ, một số ứng dụng điển
hình của WMN dƣới đây thể hiện sự bổ sung thiết yếu cho các công nghệ hiện thời
10

tránh đƣợc hiện tƣợng tắc nghẽn tại các kết nối backhaul. Ngoài các ứng dụng
11
truyền thông, WMN sử dụng cho mạng công sở còn đƣợc sử dụng cho các ứng
dụng điều khiển tự động nhƣ điện, nƣớc hay ánh sáng khi kết hợp với hệ thống cảm
biến.

Mạng vùng nhỏ
Kết nối hình lƣới đƣợc ứng dụng với các trạm cơ sở có phạm vi phủ sóng
nhỏ tƣơng đƣơng với các điểm truy nhập AP của mạng WLAN để phục vụ các kết
nối mạng femtocell. Từ đó, ngƣời dùng có thể chọn lựa linh hoạt phƣơng thức kết
nối phù hợp với mục đích sử dụng dịch vụ để tối ƣu tài nguyên. Kịch bản ứng dụng
này cho phép tận dụng các ƣu điểm của mạng tế bào nhƣ tính di động, chất lƣợng
kết nối và phổ tần không cấp phép của mạng truy nhập để tạo ra các kết nối xuyên
suốt cho các ứng dụng.

Mạng giao thông
Bên cạnh khả năng cung cấp kết nối truy nhập Internet, WMN đƣợc sử dụng
để cung cấp các dịch vụ đặc thù trong lĩnh vực giao thông nhƣ: ứng dụng cảnh báo,
điều hành và truyền thông ngang cấp giữa các phƣơng tiện đƣợc thực hiện theo
phƣơng thức tùy biến mà không yêu cầu hạ tầng mạng cố định.

Mạng cảm biến không dây
Mạng cảm biến không dây đƣợc ứng dụng rộng rãi trong rất nhiều lĩnh vực
bao gồm quân sự, ứng dụng khoa học và thƣơng mại. Các nút cảm biến thu thập
thông tin và đƣợc bố trí hình lƣới nhằm nâng cao độ tin cậy trong các phiên truyền
thông tới các hệ thống xử lý. Truyền thông đa chặng không dây cho phép triển khai
các nút cảm biến tới các vùng không thể triển khai hệ thống hữu tuyến, khoảng cách

nhập Internet băng rộng điển hình cần phải giải quyết một số vấn đề chính sau: hiện
chƣa tồn tại một khung làm việc chung hoàn thiện để đảm bảo QoS cho các dịch vụ
từ đầu cuối tới đầu cuối; dung lƣợng đƣợc yêu cầu cao do sự phát triển của thiết bị
và dịch vụ truy nhập; các ứng dụng đa phƣơng tiện đòi hỏi chặt chẽ các tham số
chất lƣợng nhƣ băng thông, độ trễ và tỷ lệ tổn thất gói tin; hiệu năng mạng bị suy
giảm do cơ chế truyền thông không dây đa chặng. Vì vậy, mục tiêu cung cấp và
đảm bảo QoS trong WMN luôn gắn liền với mục tiêu tối ƣu tài nguyên mạng và là
mục tiêu cấp thiết của các nhà nghiên cứu và khai thác mạng [20], [52].