HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG
HOÀNG TRỌ MINH
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.02.08

TÓM TẮT LUẬN ÁN TIẾN SỸ KỸ THUẬT Hà Nội - 1/2014

Công trình hoàn thành tại:
Học viện Công nghệ Bưu chính Viễn thông
Tập đoàn Bưu chính Viễn thông Việt Nam

Người hướng dẫn khoa học:
1. PGS. TS. Nguyễn Quốc Bình

Nhằm tìm kiếm giải pháp cải thiện hiệu năng WMN, nghiên cứu
sinh sử dụng tiếp cận xuyên lớp (crosslayer) giữa lớp MAC và lớp định
tuyến. Tiếp cận phân tích hiệu năng bằng mô hình giải tích cho thấy tính
khả thi cao và là tiếp cận thông dụng do khả năng phản ánh tốt các thông
số vật lý và độ phức tạp tính toán thấp. Vì vậy,nghiên cứu 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 OLSR để đề 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.
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, nghiên cứu 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ể
2
như: thông lượng, độ trễ và tỷ lệ tổn thất gói tin. Tính đúng đắn và hiệu
quả của đề xuất được xác định qua các phân tích lý thuyết, phân tích số
và mô phỏng.
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: Các
đặc tính cơ bản ảnh hưởng tới hiệu năng mạng WMN; mô hình giải tích
biểu diễn cơ chế hoạt động của IEEE 802.11 DCF; Đề xuất một tham số
định tuyến mới cải thiện hiệu năng WMN.
Phƣơng pháp nghiên cứu
Trên cơ sở các nhiệm vụ nghiên cứu đã nêu ở trên, nghiên cứu sinh
dựa trên các công cụ toán học như lý thuyết xác suất, chuỗi Markov, các

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 [61], [63], [69]. 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: triển khai nhanh, khắc phục hiện tương che tầm
nhìn thẳng, công nghệ truyền thông tầm ngắn, truyền thông đa đường và
hỗ trợ nhiều công nghệ truy nhập vô tuyến. Vì vậy, công nghệ WMN có
nhiều ưu điểm nổi trội và có khả năng ứng dụng rộng rãi trong nhiều lĩnh
vực của đời sống.
1.1.1 Kiến trúc mạng hình lƣới không dây
Công nghệ truyền dẫn nền tảng cho WMN được xây dựng trên các
chuẩn công nghiệp thông dụng của Viện kỹ nghệ Điện và Điện tử IEEE
như: IEEE 802.11 [45], IEEE 802.15 [44] và IEEE 802.16 [46]. WMN
thực hiện truyền thông đa chặng không dây giữa các thiết bị đầu cuối di
4
động thông qua các thiết bị định tuyến bố trí tĩnh theo hình lưới. Mạng
hình lưới không dây được tổ chức theo các kiểu kiến trúc như: WMN
phẳng, WMN phân cấp và WMN lai ghép tùy theo từng kịch bản ứng
dụng.
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ệ ứng dụng cho
mạng WMN, một số các ứng dụng điển hình của WMN thể hiện sự bổ
sung thiết yếu cho các công nghệ hiện thời như: mạng truy nhập băng
rộng, mạng cộng đồng, mạng công sở, mạng vùng nhỏ, mạng giao thông
và mạng cảm biến.
1.2 CHẤT LƢỢNG DỊCH VỤ
1.2.1 Khái quát về chất lƣợng dịch vụ
Mục này chỉ ra các vấn đề cốt lõi của vấn đề cung cấp, đảm bảo QoS

tham số tổ hợp gồm các thành phần mang tính lõm với tính cộng hoặc
tính nhân hoặc sử dụng lời giải kinh nghiệm (heuristic) để giảm thiểu độ
phức tạp tính toán.
1.4 TÌNH HÌNH NGHIÊN CỨU TRÊN THẾ GIỚI VÀ TẠI VIỆT
NAM
Một trong số các chuẩn công nghệ phổ biến nhất được ứng dụng
rộng rãi cho WMN là họ chuẩn IEEE 802.11. Tuy nhiên, họ chuẩn IEEE
802.11 được thiết kế cho các truy nhập đơn chặng không dây thay vì cho
truyền thông đa chặng không dây. Nhằm sáng tỏ cách tiếp cận luận án,
6
vấn đề hiệu năng và các giải pháp cải thiện của các nghiên cứu trước
trong lĩnh vực này sẽ được trình bày vắn tắt.
1.4.1 Hiệu năng và các tham số phản ánh
Hiệu năng mạng, thước đo năng lực của mạng trong hoạt động điều
hành, không chỉ phụ thuộc vào các yếu tố nội tại của mạng mà còn phụ
thuộc rất lớn vào các ứng dụng triển khai trên đó. Để đánh giá hiệu năng,
các nghiên cứu sử dụng các tiêu chí hiệu năng mạng cụ thể như: thông
lượng, trễ từ đầu cuối tới đầu cuối hoặc tỷ lệ tổn thất gói tin.
1.4.2 Các tiếp cận cải thiện hiệu năng
Nhằm sáng tỏ cách tiếp cận học thuật của nghiên cứu, mục này khảo
sát và đánh giá các nghiên cứu trước trên thế giới và tại Việt nam dưới
góc độ sử dụng các công cụ toán học lý thuyết đồ thị, quy hoạch tuyến
tính và mô hình giải tích Trong đó, mô hình giải tích là tiếp cận mô
hình hóa có khả năng phản ánh tốt các thông số vật lý và độ phức tạp
tính toán không cao. Tuy nhiên, mô hình giải tích tập trung chính vào
mục tiêu đánh giá và phân tích hiệu năng và đặc biệt là độ chính xác của
mô hình phụ thuộc trực tiếp vào các giả thiết. Vì vậy, hướng tiếp cận này

đó đưa ra điều kiện bổ sung nhằm hoàn thiện mô hình giải tích cho thủ
tục đa truy nhập cảm nhận sóng mang/ tránh xung đột CSMA/CA trong
điều kiện bão hòa.
2.1 MỞ ĐẦU
Cơ chế hoạt động và hiện tượng xung đột tại lớp MAC được coi là
nguyên nhân chính gây suy giảm hiệu năng các phiên truyền dẫn [13],
8
[54], [82]. Đặc biệt, với cơ chế đa truy nhập cảm nhận sóng mang tránh
xung đột CSMA/CA trong mạng đa chặng, hiệu quả sử dụng kênh tiếp
tục suy giảm do sự ảnh hưởng của nhiễu do chính các truyền dẫn đồng
thời trong mạng gây ra. Các mục dưới đây trình bày và đánh giá thông
lượng liên kết của các cơ chế điều khiển truy nhập điển hình của các tác
giả trước và từ đó đưa ra các bổ sung cần thiết nhằm hoàn thiện mô hình
giải tích cho giao thức CSMA/CA trong điều kiện lưu lượng mạng bão
hòa.
2.2 CÁC NGHIÊN CỨU MÔ HÌNH HÓA GIAO THỨC ĐA TRUY
NHẬP PHƢƠNG TIỆN
2.2.1 Giao thức truy nhập kênh ALOHA
Giao thức truy nhập ngẫu nhiên đầu tiên được sử dụng cho các mạng
máy tính có tên gọi là ALOHA [2]. Cơ chế hoạt động của giao thức
ALOHA được coi là đơn giản nhất trong các cơ chế đa truy nhập.
2.2.2 Giao thức đa truy nhập cảm nhận sóng mang 1-persistent CSMA
1-persistent CSMA chỉ ra xác suất chiếm khe thời gian chắc chắn để
truyền dẫn (bằng 1) sau khi cảm nhận kênh rỗi. CSMA có thể sử dụng cơ
chế phân khe hoặc không phân khe thời gian để xác định cách thức tranh
chấp tài nguyên. Hiệu năng hoạt động của các biến thể 1-persistent
CSMA được tóm tắt trong mục này.

của các tác giả trước [13], [70], [102], phương pháp tính toán trạng thái
dừng chưa được chỉ ra một cách rõ ràng. Vì vậy, một lời giải tường minh
bằng phương pháp giải tích là cần thiết cho ứng dụng tính toán.
2.4 BỔ SUNG XÁC SUẤT TRANH CHẤP THẮNG
Trong các đề xuất của các tác giả trước [13], [70], [102], nghiên cứu
sinh nhận thấy giả thiết các nút cùng phát đồng thời và chiếm được kênh
trong quá trình backoff đã bỏ qua. Vì vậy, nghiên cứu sinh bổ sung xác
suất tranh chấp thắng cho bài toán mô hình hóa nhằm tăng độ chính xác
của mô hình giải tích. Xác suất truyền dẫn thành công phải bao gồm xác
suất tranh chấp thắng của nút trong trường hợp nhiều nút cùng tham gia
10
quá trình backoff Xác suất tranh chấp thắng ký hiệu là
win
P
và được tính
toán thông qua mệnh đề toán học sau.
Mệnh đề
Xét hàm số
:{1,2, , } {1,2, , }f p q
trong đó
,pq
, khi đó xác
suất
    
 
 
1

n
n
nk
k k M
win t n t t
nk
M
P M p C p p P k e
n





    

. (2.22)
Xác suất tranh chấp thắng
win
P
ảnh hưởng trực tiếp tới xác suất truyền
dẫn thành công
st
p
của nút i. Trường hợp bỏ qua
win
P
ta có:
'
st st

và
t
p

11
Khi bổ sung xác suất tranh chấp thắng
win
P
vào xác suất truyền dẫn
thành công
st
P
, ta thu được kết quả theo công thức 2.24 và thể hiện trên
hình 2.6.
     
1
11
*
1
21
1 1 . 1
!
n
n
n n k
k k M
st t t n t t

CHẤT LƢỢNG LIÊN KẾT
Tóm tắt: Các tác động của nhiễu lên chất lượng liên kết không dây
trong WMN là một yếu tố chính gây suy giảm hiệu năng liên kết và cần
phải được phản ánh chính xác. Nội dung cốt lõi của chương trình bày về
một đề xuất mô hình giải tích mới nhằm phản ánh chính xác hiệu năng
liên kết không dây trong WMN dựa trên tiêu chuẩn IEEE 802.11 dưới
tác động của nhiễu liên luồng và tranh chấp. Các điều kiện bổ sung như
12
lưu lượng không bão hòa, kênh không lý tưởng được đưa vào mô hình
nhằm tương thích với điều kiện môi trường thực tế và cho phép ước
lượng tham số chất lượng liên kết.
3.1 MỞ ĐẦU
Đánh giá đúng chất lượng liên kết dưới các điều kiện động của mạng
như cấu hình thay đổi, lưu lượng biến động, hiện tượng xung đột và can
nhiễu là một vấn đề thách thức. Vì vậy, chương này trình bày đề xuất về
mô hình giải tích mới với các điều kiện tổng quát như: lưu lượng mạng
không bão hòa và kênh không lý tưởng.
3.2 ĐẶC TÍNH CỦA IEEE 802.11 DCF
Giao thức điều khiển truy nhập phương tiện IEEE 802.11 MAC được
sử dụng để hợp tác và lập lịch giữa các nút tranh chấp nhằm giảm thiểu
xung đột. Phương thức IEEE 802.11 DCF được sử dụng phổ biến trong
các mạng hình lưới không dây dựa trên họ chuẩn IEEE 802.11.
3.3 MÔ HÌNH GIẢI TÍCH IEEE 802.11 DCF
3.3.1 Các điều kiện biên giả thiết
Nhằm xây dựng mô hình giải tích IEEE 802.11 DCF trong mạng
WMN, một số giả thiết sẽ được đưa ra nhằm tương thích với điều kiện
mạng không bão hòa và chất lượng kênh không lý tưởng nhằm phản ánh

Từ các phương trình trên, ta tính toán được các trạng thái dừng của
mô hình trạng thái nút:
1
;;
22
1
;.
22
ds
ds
di di
di dd di dd
id id
df
di
fi
di di
id
di dd di dd
id id
p
pp
p p p p
pp
p
p
pp
p
p p p p
pp

p
và xác suất kênh rỗi trong một khe thời
gian (
P

).
t id
p p P



(3.17)
Phương tiện truyền dẫn trong mạng hình lưới được chia sẻ bởi số
lượng các nút hoạt động (active node) trong miền truyền dẫn nên hoạt
động của một nút phụ thuộc vào hoạt động của các nút khác. Vì vậy, xác
suất kênh rỗi được tính toán xấp xỉ qua xác suất dài hạn trong biểu thức
I I I
I I C C B B S S I IC C IB B IS S
S T T
P
S T S T S T S T T P T P T P T


     
. (3.18)
Từ phương trình (3.4) và (3.18), xác suất truyền trong một khe thời
gian là
 
 
.

IB
I C B S
II II II II
PP
P
P P P P
   
   
   

(3.27)
3.4 KẾT QUẢ PHÂN TÍCH SỐ VÀ THẢO LUẬN
Từ các giả thiết của mô hình giải tích đề xuất, xác suất truyền dẫn
thành công
s
p
là xác suất trạng thái dừng của trạng thái thành công
trong mô hình nút
s


(3.16). Từ phương trình (3.16) và (3.19), ta có hệ
hai phương trình phi tuyến với hai biến
s
p
và
t
p
có thể giải được bằng
phương pháp số. Khe thời gian ảo

, tỷ lệ miền cảm
nhận và miền truyền dẫn là

, tốc độ lưu lượng gói tin đến là

, tỷ lệ
lỗi bit của truyền dẫn là
b
p
và độ dài trung bình tải tin là
 
EP
.
3.5 KẾT LUẬN CHƢƠNG
Với mục tiêu đánh giá chất lượng liên kết không dây trong WMN,
nội dung của chương đã trình bày về một mô hình giải tích mới biểu diễn
16
hoạt động của IEEE 802.11 DCF. Trong đó, các điều kiện mới như lưu
lượng không bão hòa và kênh không lý tưởng được tích hợp vào mô hình
nhằm phản ánh đầy đủ các tác động tới chất lượng liên kết và hiệu năng
truyền dẫn. Trên cơ sở mô hình giải tích đề xuất, chất lượng liên kết sẽ
được phản ánh thông qua một tham số định tuyến phục vụ cho mục tiêu
nâng cao hiệu năng mạng trong chương tiếp theo.

CHƢƠNG 4: ĐỀ XUẤT THAM SỐ ĐỊNH TUYẾN QOS CẢI
THIỆN HIỆU NĂNG MẠNG HÌNH LƢỚI KHÔNG DÂY
Tóm tắt: Sự phổ biến của các ứng dụng đa phương tiện hiện nay đã dẫn

Thuộc vào lớp mạng truyền thông đa bước không dây, phần lớn các
giao thức định tuyến trong WMN được kế thừa từ giao thức định tuyến
trong mạng tùy biến không dây (Ad-hoc). Các giao thức định tuyến được
phân thành: giao thức định tuyến theo yêu cầu, giao thức định tuyến theo
bảng và giao thức định tuyến lai ghép
4.2.2 Tham số định tuyến
Dưới góc độ ảnh hưởng của nhiễu tới chất lượng liên kết, các tham số
định tuyến được đề xuất bởi các nghiên cứu gần đây có thể phân thành
hai loại: phản ánh gián tiếp sự ảnh hưởng của nhiễu và phản ánh trực
tiếp sự ảnh hưởng của nhiễu qua thành phần của tham số định tuyến.
Mục này cũng chỉ ra các ưu nhược điểm của các tham số định tuyến đề
xuất trước đây và chỉ ra cách tiếp cận riêng của nghiên cứu sinh.
18
4.3 ĐỀ XUẤT THAM SỐ ĐỊNH TUYẾN IARM
Các nội dung khảo sát về các tham số định tuyến cho thấy tác động
nhiễu lên liên kết không chỉ phản ánh qua miền thời gian như các đề
xuất của các tác giả trước mà còn cần phản ánh qua khía cạnh trạng thái.
Nghiên cứu sinh đề xuất xây dựng tham số định tuyến phản ánh nhiễu
IARM (Interference Aware Routing Metric) và các phân tích lý thuyết
chứng minh tính đúng đắn của tham số đề xuất.
4.3.1 Tham số phản ánh nhiễu đề xuất IARM
Tham số định tuyến đề xuất IARM phản ánh trực tiếp xác suất tổn
thất gói tin thông qua thủ tục thăm dò khi tích hợp với giao thức định
tuyến OLSR. Hai thành phần của IARM được xây dựng gồm: thành
phần phản ánh xác suất tổn thất gói tin thông qua tỷ lệ chuyển phát gói
tin của liên kết PDR (Packet Delivery Ratio) và tỷ lệ thời gian khả dụng
của kênh xung quanh một nút CAF (Channel Available Fraction). Các






(4.12)
Trong đó,
 
0,1
thresh


là giá trị ngưỡng lưu lượng có thể truyền trên
một liên kết không dây (giá trị ngưỡng được đặt là 0.96 nhằm tránh hiện
tượng quá tải). E[P] là giá trị trung bình độ dài của các gói tin và T
s
là
khoảng thời gian truyền dẫn thành công. Như vậy, mức độ chiếm dụng
kênh càng nhỏ thì thời gian khả dụng của kênh xung quanh nút đó càng
19
lớn. Giá trị tỷ lệ kênh khả dụng của liên kết l của cặp nút i và nút j được
xác định qua công thức:
      
min ,CAF l CAF i CAF j
. (4.13)
Tham số định tuyến IARM được xác định trên liên kết l qua công
thức:

các thuật toán tính toán đường dẫn không rơi vào độ phức tạp hàm mũ là
tham số định tuyến phải đảm bảo tính tuần tự [101]. Mục này chứng
minh tham số IARM đề xuất thỏa mãn tính tuần tự và không gây lặp
vòng.
4.3.3 Tích hợp tham số IARM trong OLSR
Nhằm kiểm chứng hiệu quả của tham số định tuyến đề xuất, nghiên
cứu này lựa chọn giao thức định tuyến OLSR để cải thiện vì khả năng tái
sử dụng một số tính năng có sẵn của giao thức này. Mục này trình bày
các sửa đổi cần thiết đối với OLSR để tương thích với tham số định
20
tuyến IARM theo mô hình tổ chức thông tin xuyên lớp. Dựa trên bộ công
cụ và mã nguồn mở sử dụng để cải thiện giao thức OLSR trong NS-2,
các nội dung sửa đổi và tính toán phù hợp với tham số định tuyến IARM
đề xuất được trình bày trong hình 4.3.
Hình 4.3: Các nội dung sửa đổi giao thức OLSR-IARM (NS-2)
4.4 MÔ PHỎNG VÀ THẢO LUẬN
Nhằm kiểm chứng tính đúng đắn của đề xuất, tham số định tuyến
phản ánh nhiễu IARM sẽ được tích hợp trong giao thức định tuyến
OLSR-IARM và so sánh với giao thức OLSR nguyên bản dưới các khía
cạnh như trễ, thông lượng, tỷ lệ chuyển tiếp gói tin ứng dụng và tỷ lệ tổn
thất gói. Mô phỏng được thực hiện trên công cụ mô phỏng NS-2 và kịch
bản ứng dụng điển hình của WMN.
4.4.1 Giới thiệu công cụ mô phỏng NS-2
NS-2 vẫn là công cụ mô phỏng phổ biến nhất cho các nghiên cứu

đề xuất, 4 tham số cơ bản phản ánh hiệu năng mạng được khảo sát gồm:
Trễ trung bình (ms), tỷ lệ chuyển phát thành công gói tin (%), tỷ lệ tổn
thất gói tin (%) và thông lượng( Kbps).

Hình 4.6: So sánh trễ trung bình gói tin giữa OLSR và OLSR-IARM
Khi tốc độ gửi gói tin tăng từ 2 gói/s lên 20 gói/s, các kết quả trong
các hình đều cho thấy các tham số hiệu năng của giao thức OLSR suy
giảm mạnh do xuất hiện các yếu tố gây nhiễu lên các đường dẫn gói tin.
22

Hình 4.7: Tỷ lệ chuyển phát gói tin thành công giữa OLSR và OLSR-IARM
Cụ thể, trễ tăng gần như tuyến tính từ khoảng 50 ms ở tốc độ gửi gói
tin 2 gói/s đến gần 500 ms ở tốc độ gửi gói tin 20 gói/s; tỷ lệ chuyển phát
gói tin thành công giảm khoảng 20% từ xấp xỉ 90% xuống xấp xỉ 70%;
tỷ lệ tổn thất gói của OLSR tăng từ gần 5% lên đến xấp xỉ 25%; thông
lượng giảm từ khoảng 700 Kbps xuống còn khoảng 300 Kbps. Trong khi
đó, mặc dù các tham số hiệu năng tương ứng của OLSR-IARM có sự
suy giảm nhưng mức độ suy giảm chậm hơn so với mức độ suy giảm của
các tham số trong OLSR. Trễ chỉ tăng từ 50ms lên đến 250ms; tỷ lệ
chuyển phát gói tin giảm không đáng kể và vẫn duy trì ở mức trên 90%;
tỷ lệ tổn thất gói cao nhất tại tốc độ gửi gói tin 20 gói/s là khoảng 6%.

Hình 4.8: So sánh tỷ lệ tổn thất gói tin giữa OLSR và OLSR-IARM
23