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

HOÀNG TRỌ 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

TÓM TẮT LUẬN ÁN TIẾN SỸ KỸ THUẬT

Hà Nội - 2013


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
2. PSG. TS Nguyễn Tiến Ban

Phản biện 1:…………………………………………………………
………………………………………………………….
Phản biện 2:…………………………………………………………
………………………………………………………….
Phản biện 3:…………………………………………………………
………………………………………………………….

Luận án sẽ được bảo vệ trước hội đồng chấm luận án tại Học viện

thông đa bước không dây và các yêu cầu cung cấp chất lượng dịch vụ

Interference Analytical Model in 802.11-based Wireless Mesh

QoS (Quality of Service) đã cho thấy một số thách thức mà WMN cần

Networks”,

Wireless

phải vượt qua về mặt hiệu năng mạng. Trong đó, ảnh hưởng của hiện

Computing

tượng tranh chấp kênh và tác động nhiễu giữa các truyền dẫn đồng thời

IEEE

Communications,

Conference
Networking

Publications,
and

Mobile

(WiCOM), 2012 8th International Conference on, pp. 1 – 4.
9. Trong-Minh Hoang, Minh Hoang, “A Novel Analytical Model to


networks under serious attacks”, IEEE Conference Publications,

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

Computing,

chủ động sẵn có của giao thức OLSR để đề xuất một tham số định tuyến

Management

and

Telecommunications

(ComManTel), 2013 International Conference on, pp. 295 –

mới, cải thiện được các thông số hiệu năng WMN.

297.

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 tuyến mới phản ánh nhiễu trong mạng hình lưới không dây

định tuyến mới cải thiện hiệu năng WMN.

IEEE 802.11”, Tạp chí khoa học và kỹ thuật quân sự, ISSN

Phương pháp nghiên cứu

1859-1043, số 13, 2011.

Trên cơ sở các nhiệm vụ nghiên cứu đã nêu ở trên, nghiên cứu sinh

3.

Hoang Trong Minh, Hoang Minh, Nguyen Quoc Binh, “A Novel

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

Computation for Supplementing Interference Analytical Model

phương pháp tính để xác minh tính đúng đắn về mặt lý thuyết. Công cụ

in 802.11-based Wireless Mesh Networks”, Tạp chí khoa học và

mô phỏng sự kiện rời rạc được sử dụng trong luận án nhằm để kiểm

công nghệ, ISSN 0866-708x, số 2, 2012.

chứng tính hợp lý của đề xuất.


tiện trong điều kiện bão hòa

6.

Hoang Trong Minh, Hoang Minh,“A Novel Interference Aware

Chương 3: Xây dựng mô hình giải tích đánh giá chất lượng liên kết

routing metric for QoS provision in 802.11 wireless mesh

Chương 4: Đề xuất tham số định tuyến QoS cải thiện hiệu năng mạng

network”, Tạp chí khoa học và công nghệ, ISSN 0866-708x, số

hình lưới không dây

1A, 2013.
Hà nội, tháng 12 năm 2013


26

3

 Trong một số ứng dụng thực tiễn yêu cầu hạ tầng WMN đáp ứng các
điều kiện QoS chặt chẽ của ứng dụng như trễ, tỷ lệ tổn thất gói tin tối
đa, băng thông tối thiểu,... Vì vậy, các quyết định định tuyến đảm bảo
QoS của ứng dụng cần hỗ trợ các cơ chế xác định yêu cầu đầu vào và
bổ sung điều kiện ràng buộc định tuyến. Điều này cũng dẫn tới các

án cần tiếp tục phát triển và mở rộng với các công cụ mô phỏng hoặc
các giải pháp phân tích số khác.
Trên đây là một số kết luận và hướng kiến nghị tiếp theo của luận
án, nghiên cứu sinh chân thành cảm ơn các thầy hướng dẫn khoa học và
các nhà khoa học đã định hướng và phản biện để giúp nghiên cứu sinh
hoàn thành luận á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.

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

toán khi tận dụng thủ tục sẵn có của giao thức định tuyến OLSR. Tham
số định tuyến IARM đã được chứng minh tính tương thích khi kết hợp
với giao thức định tuyến OLSR và cho thấy các kết quả cải thiện hiệu
năng trên các khía cạnh như trễ trung bình, tỷ lệ chuyển phát thành công
và tỷ lệ tổn thất gói tin cũng như thông lượng toàn mạng qua các kết quả
mô phỏng số. Các đóng góp chính trong nhóm kết quả này gồm:
 Xây dựng cấu trúc, thành phần tham số định tuyến QoS mới phản
ánh nhiễu IARM với các phân tích chứng minh tính tương thích của
tham số với thuật toán Dijktra;
 Sửa đổi và xây dựng module tính toán định tuyến của giao thức
OLSR để tích hợp với tham số định tuyến IARM;

gian điều hành khác biệt trên từng lớp đã dẫn tới mô hình kiến trúc phân

 Mô phỏng và chiết xuất các kết quả liên quan tới các tham số hiệu
năng mạng gồm trễ, tỷ lệ chuyển phát gói tin thành công, tỷ lệ tổn
thất gói tin và thông lượng mạng khi lưu lượng đầu vào thay đổi. So
sánh mức cải thiện hiệu năng mạng khi sử dụng OLSR-IARM để
xuất với OLSR nguyên gốc.

lớp không đạt được điểm tối ưu hiệu năng tổng thể của mạng WMN,

Bằng các phân tích lý thuyết và các kết quả mô phỏng được trình bày

việc cung cấp QoS trong WMN phụ thuộc vào tham số động của mạng

trong luận án đã cho thấy một số ưu điểm nhất định của tham số định

và môi trường điều khiển phân tán. Vì vậy, hướng tiếp cận xuyên lớp là


đề xuất có cấu trúc lai ghép nhằm khai thác điểm mạnh của phương pháp

đa tài nguyên mạng, và tối thiểu hoá giá thành mạng. Các vấn đề cơ bản

dự đoán trên cơ sở mô hình giải tích và tận dụng thủ tục cơ bản của giao

của kỹ thuật định tuyến được tóm tắt theo ba khía cạnh: thủ tục trao đổi

thức định tuyến OLSR. Trong quá trình thực hiện luận án, một số kết

và cập nhật thông tin, thuật toán tính toán đường dẫn và tham số định

quả khoa học mới đã được đề cập thuộc hai nhóm kết quả chính như sau:

tuyến.

1.

Mô hình giải tích đánh giá chất lượng liên kết cho mạng hình lưới
không dây dựa trên chuẩn IEEE 802.11

Trên cơ sở sử dụng công cụ toán học như lý thuyết xác suất và chuỗi
Markov, một mô hình giải tích biểu diễn hoạt động của giao thức điều
khiển truy nhập phương tiện trong tiêu chuẩn IEEE 802.11 DCF đã được
xây dựng mới. Các vấn đề đóng góp mới đã được công bố gồm:
 Mô hình hóa hoạt động giao thức IEEE 802.11 DCF bằng công cụ

giải tích dựa trên chuỗi Markov và các lý thuyết xác suất;
 Bổ sung và hoàn thiện các điều kiện thực tiễn gồm lưu lượng
không bão hòa và kênh không lý tưởng nhằm nâng cao độ chính


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

23
Các kết quả đều chỉ ra các tham số hiệu năng của giao thức OLSR-

trong lĩnh vực này sẽ được trình bày vắn tắt.

IARM đều tốt hơn so với OLSR trong tất cả các kịch bản. Kết quả thông

1.4.1 Hiệu năng và các tham số phản ánh

lượng trong hình 4.9 cho thấy thông lượng của OLSR-IARM luôn cao

Hiệu năng mạng, thước đo năng lực của mạng trong hoạt động điều

xấp xỉ gấp đôi so với thông lượng của OLSR.

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ô


bằng công cụ NS-2 để đánh giá ưu điểm của tham số đề xuất. Các kết

tiêu của đề tài nghiên cứu, mô hình giải tích mới được xây dựng với các

quả mô phỏng cho thấy OLSR-IARM có được mức cải thiện hiệu năng

điều kiện bổ sung mới như lưu lượng mạng không bão hòa và kênh

đáng kể so với OLSR nguyên gốc trên các khía cạnh hiệu năng như độ

không lý tưởng. Đó là cơ sở để xây dựng thành phần tham số định tuyến

trễ trung bình của gói tin, tỷ lệ chuyển phát gói tin thành công, xác suất

phản ánh nhiễu, cung cấp thông tin chất lượng liên kết tới lớp định tuyến

tổn thất gói và thông lượng mạng.

nhằm cải thiện hiệu năng mạng.


7

22
1.5 KẾT LUẬN CHƯƠNG

Nội dung của chương 1 đã thể hiện khái quát cấu trúc, ứng dụng của
WMN nhằm nổi bật các đặc tính riêng biệt của đối tượng cần quan tâm
nghiên cứu. Sự khác biệt về cấu trúc chức năng của mạng truyền thông
không dây với mạng hữu tuyến truyền thống cho thấy tiếp cận xuyên lớp

các tham số trong OLSR. Trễ chỉ tăng từ 50ms lên đến 250ms; tỷ lệ

cứu nhằm phân tích và đánh giá hiệu năng lớp liên kết dữ liệu. Điều kiện

chuyển phát gói tin giảm không đáng kể và vẫn duy trì ở mức trên 90%;

lưu lượng mạng bão hòa là điều kiện mấu chốt để xác định giá trị thông

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

lượng tối đa của liên kết. Chương này khái quát các giải pháp mô hình
hóa giao thức điều khiển truy nhập đã đề xuất của các tác giả trước, từ
đó đư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],
Hình 4.8: So sánh tỷ lệ tổn thất gói tin giữa OLSR và OLSR-IARM


8

21

[54], [82]. Đặc biệt, với cơ chế đa truy nhập cảm nhận sóng mang tránh

IARM sẽ được khảo sát dưới các tham số hiệu năng mạng cụ thể như:



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.
2.2.3 Giao thức đa truy nhập cảm nhận sóng mang p-persistent CSMA

Giao thức 1-CSMA được coi là trường hợp đặc biệt của giao thức p-

Hình 4.6: So sánh trễ trung bình gói tin giữa OLSR và OLSR-IARM

persistent CSMA. Trong giao thức p-CSMA, một nút phát thực hiện

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

truyền dẫn với xác suất p  1 khi cảm nhận được kênh rỗi. Hoạt động

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.


20

9

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ủa p-persistent CSMA được mô hình hóa qua các trạng thái của một nút


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

Hình 2.5: Chuỗi Markov 3 trạng thái của nút
Xác suất dừng của các trạng thái trên là

w 

1
pws
; s 
; f  1   w   s .
2  pww
2  pww

(2.6)

2.3. TÍNH TOÁN TRẠNG THÁI DỪNG

Theo tiếp cận mô hình hóa IEEE 802.11 DCF bằng chuỗi Markov

bản ứng dụng điển hình của WMN.

của các tác giả trước [13], [70], [102], phương pháp tính toán trạng thái

4.4.1 Giới thiệu công cụ mô phỏng NS-2

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

NS-2 vẫn là công cụ mô phỏng phổ biến nhất cho các nghiên cứu
lớp mạng do khả năng phản ánh tốt hoạt động của giao thức định tuyến.

19

quá trình backoff Xác suất tranh chấp thắng ký hiệu là Pwin và được tính

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

toán thông qua mệnh đề toán học sau.

xác định qua công thức:

Mệnh đề
Xét hàm số f :{1, 2,..., p}  {1, 2,..., q} trong đó p, q  , khi đó xác
suất
q 1

P*  P !i  1, 2,..., p f (i )  m  min1 j  q  f  j  

  q  m

thức:
IARM  l  

.

p

(4.13)

Tham số định tuyến IARM được xác định trên liên kết l qua công


n 1

pt

k

1  p 

n 1 k

t

n  2 k 1

.P

*

vào từng kịch bản ứng dụng cụ thể. Giá trị tham số định tuyến của mỗi

 k  1 

M

n

e

M


n2

n 1

M

n

e

M

.

n!

(2.23)

bảo một số tiêu chí như trình bày trong mục 1.3. Điều kiện tiên quyết để
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
Hình 2.6: Biểu diễn mối quan hệ giữa pst ' với M và p t



  Cn 1 pt 1  pt 
k

k

n 1 k

n
 M e M  . (2.24)

 n!


.P  k  1  
*

k 1

2.5 KẾT LUẬN CHƯƠNG

Trong chương 2 đã tóm tắt các mô hình hóa giao thức điều khiển truy

4.3.1 Tham số phản ánh nhiễu đề xuất IARM

nhập phương tiện điển hình của các tác giả trước. Các phương pháp điều

Tham số định tuyến đề xuất IARM phản ánh trực tiếp xác suất tổn

khiển truy nhập với các giả thiết đầu vào được mô hình hóa bằng các


0

thresh

 Cu (i )) 
Rdata

(4.10)

E[ P ]
TS

CHƯƠNG 3: XÂY DỰNG MÔ HÌNH GIẢI TÍCH ĐÁNH GIÁ
if C u (i )   thresh .

(4.12)

else

Trong đó, thresh   0,1 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à Ts 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

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ề


của gói tin, tỷ lệ tổn thất gói tin và tỷ lệ tổn thất gói tin ứng dụng.

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ề

4.2 ĐỊNH TUYẾN TRONG WMN

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

Mục này tóm tắt các đặc điểm chính của các giao thức định tuyến

không bão hòa và kênh không lý tưởng.

điển hình trong mạng WMN cùng với các tham số định tuyến được đề

3.2 ĐẶC TÍNH CỦA IEEE 802.11 DCF

xuất gần đây nhằm phân tích các ưu nhược điểm và các vấn đề mở cần

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

giải quyết.
4.2.1 Giao thức định tuyế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

các mạng hình lưới không dây dựa trên họ chuẩn IEEE 802.11.



13

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.
Hình 3.4: Chuỗi Markov của mô hình nút 4 trạng thái

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
tới sự thay thế các kỹ thuật định tuyến truyền thống bằng các kỹ thuật

Từ các xác suất thể hiện trên hình 3.4 ta thu được các phương trình
cân bằng trạng thái sau
 s   d p ds ;  i   d p di   i p ii

 f   d p df ;  d   i p id   d p dd   s   f

.

Với các điều kiện

định tuyến cung cấp QoS nhằm đáp ứng yêu cầu ngày càng cao của
người sử dụng. Mặt khác, từ góc độ vận hành và khai thác mạng,vấn đề
hiệu năng mạng luôn là một mối quan tâm hàng đầu của các nhà nghiên
cứu và triển khai. Vì vậy, nội dung chương này sẽ trình bày một tham số


 2  pdi  pdd  p 

id 

; s 

;i 

pds
pdi 

 2  pdi  pdd  p 

id 
pdi

;

(3.16)

1

pid 

pdi 



pid 

2  PII

; S 

PIS

.

2  PII

(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 ps 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ệ

Hình 3.6: Chuỗi Markov của mô hình kênh xung quanh nút
Xác suất pt được xác định bởi xác suất chuyển trạng thái từ Idle
sang Break của mô hình nút pid và xác suất kênh rỗi trong một khe thời
gian ( P ).

pt  pid  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







B

B

S

S

.

(3.18)

T  P T  PT  PT
I

IC

C

IB

B

IS


T

I

TI  PICTC  PIBTB  PIS TS

nhận và miền truyền dẫn là  , tốc độ lưu lượng gói tin đến là  , tỷ lệ
.

(3.19)

Với các xác suất thể hiện trên hình 3.6, ta tính toán được các trạng
thái dừng của mô hình kênh như dưới đây.

 I   I PII  C PCI   B PBI   S PSI   I PII   C   B   S   I PII   I  1;

lỗi bit của truyền dẫn là pb và độ dài trung bình tải tin là E  P  .
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