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

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.

Ngƣời cam đoan

Hoàng Trọng Minh

ii

LỜI CẢM ƠN

Nghiên cứu sinh xin bày tỏ sự biết ơn sâu sắc tới các Thầy hƣớng dẫn, Đại tá

PGS.TS Nguyễn Quốc Bình và PGS.TS Nguyễn Tiến Ban, vì đã định hƣớng và liên

tục hƣớng dẫn các nhiệm vụ khoa học trong suốt quá trình thực hiện luận án này.

Nghiên cứu sinh xin bày tỏ sự biết ơn các ý kiến chỉ dẫn của các nhà khoa

học GS.TSKH Nguyễn Ngọc San, PGS.TS Hoàng Minh, GS.TS Nguyễn Bình đã

giúp nghiên cứu sinh có đƣợc các kiến thức học thuật quý báu.

Nghiên cứu sinh bày tỏ lòng biết ơn Lãnh đạo Học viện, các thầy cô của

khoa Quốc tế và Đào tạo sau đại học, khoa Viễn thông 1 tại Học viện Công nghệ

Bƣu chính Viễn thông. Những hỗ trợ, động viên nghiên cứu của các cộng sự xin

đƣợc chân thành ghi nhận.

Nghiên cứu sinh chân thành bày tỏ lòng cảm ơn tới gia đình đã kiên trì chia

sẻ và động viên nghiên cứu sinh trong suốt quá trình thực hiện nội dung luận án.

Hà Nội, tháng 12 năm 2013

Hoàng Trọng Minh

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

TRUY NHẬP PHƢƠNG TIỆN TRONG ĐIỀU KIỆN BÃO HÒA ......... 35

2.1 MỞ ĐẦU................................................................................................................... 35

2.2 CÁC NGHIÊN CỨU MÔ HÌNH HÓA GIAO THỨC ĐA TRUY NHẬP PHƢƠNG

TIỆN................................................................................................................................ 36

2.2.1 Giao thức truy nhập kênh ALOHA..........................................................37

iv

2.2.2 Giao thức đa truy nhập cảm nhận sóng mang 1-persistent CSMA..........39

2.2.3 Giao thức đa truy nhập cảm nhận sóng mang p-persistent CSMA..........40

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

2.4 BỔ SUNG XÁC SUẤT TRANH CHẤP THẮNG ................................................... 46

2.5 KẾT LUẬN CHƢƠNG............................................................................................. 50

CHƢƠNG 3: XÂY DỰNG MÔ HÌNH GIẢI TÍCH ĐÁNH GIÁ CHẤT

LƢỢNG LIÊN KẾT...................................................................................... 52

3.1 MỞ ĐẦU................................................................................................................... 52

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

3.3 MÔ HÌNH GIẢI TÍCH IEEE 802.11 DCF ............................................................... 57

3.3.1 Các điều kiện biên giả thiết......................................................................57

3.3.2 Biểu diễn trạng thái nút qua mô hình giải tích.........................................60

3.3.3 Biểu diễn trạng thái kênh qua mô hình giải tích ......................................65

3.4 KẾT QUẢ PHÂN TÍCH SỐ VÀ THẢO LUẬN ...................................................... 69

3.5 KẾT LUẬN CHƢƠNG............................................................................................. 74

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

4.1 MỞ ĐẦU................................................................................................................... 76

4.2 ĐỊNH TUYẾN TRONG WMN................................................................................. 78

4.2.1 Giao thức định tuyến................................................................................78

4.2.2 Tham số định tuyến..................................................................................84

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

vi

THUẬT NGỮ VIẾT TẮT

ACK Acknowledgement Báo nhận

AIR Average Interference Ratio Tỷ số nhiễu trung bình

AODV Adhoc Ondemand Distance

Vector

(Giao thức định tuyến) vectơ

khoảng cách theo yêu cầu

AP Access Point Điểm truy nhập

BER Bit Error Ratio Tỷ số lỗi bit

BSS Basic Service Set Tập dịch vụ cơ bản

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 Clear-to-Send Xóa để gửi

CW Contention Window Cửa sổ tranh chấp

DCF Distributed Coordinated

Function

Hàm hợp tác phân tán

DIFS DCF InterFrame Space Khoảng liên khung hàm phối hợp

phân tán

DS Distribution System Hệ thống phân bổ

DSDV Destination Sequence Distance

Vector

(Giao thức định tuyến) vectơ

khoảng cách tuần tự đích

DSR Dynamic Source Routing (Giao thức) định tuyến nguồn

động

ELP Expected Link Performance Hiệu năng liên kết kỳ vọng

ESS Extended Service Set 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

nhiễu

IAR Interference Aware Routing (Tham số) định tuyến phản ánh

nhiễu

IARM Interference Aware Routing

Metric

Tham số định tuyến phản ánh

nhiễu

IBSS Independent Basic Service Set Tập dịch vụ cơ bản độc lập

IEEE Institute of Electrical and

Electronics Engineer

Viện kỹ nghệ Điện và Điện tử

ILP Integer Linear Programming Quy hoạch tuyến tính nguyên

IF(s) InterFrame space Khoảng thời gian liên khung

ITU-T ITU-Telecommunication

Standardization Sector

Liên minh viễn thông quốc tế -

Lĩnh vực tiêu chuẩn viễn thông

LAETT Load Aware Expected

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

Multiplexing

Ghép kênh phân chia tần số trực

giao

viii

OLSR Optimized Link State Routing (Giao thức) định tuyến trạng thái

liên kết tối ƣu

PCF Point Coordination Function Hàm hợp tác điểm

PCS Physical Carrier Sense Cảm nhận sóng mang lớp vật lý

PDF Packet Delivery Fraction Tỷ lệ chuyển phát gói thành công

PDR Packet Delivery Ratio Tỷ lệ chuyển phát gói tin

PIFS PCF InterFrame Space Khoảng liên khung hàm phối hợp

điểm

QoS Quality of Service Chất lƣợng dịch vụ

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

WLAN Wireless Local Area Network Mạng vùng cục bộ không dây

WMN Wireless Mesh Network Mạng hình lƣới không dây

WSN Wireless Sensor Network Mạng cảm biến không dây

ix

BẢNG KÝ HIỆU



Tỷ số giữa bán kính cảm nhận và bán kính truyền dẫn



Ngƣỡng nhạy thu

0

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

Cij

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

C

Trạng thái contention trong mô hình kênh 4 trạng thái

CW

Kích thƣớc cửa sổ tranh chấp

CW

Kích thƣớc cửa sổ tranh chấp trung bình

ij d

Khoảng cách vật lý từ nút i tới nút j

d

Trạng thái defer trong mô hình nút 4 trạng thái

ET[ ]

Độ dài khe thời gian ảo

χ

e

Vector riêng tƣơng ứng với giá trị riêng



f

Trạng thái failure trong mô hình nút 3,4 trạng thái

iI,

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

Lpacket

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

MH

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

Pb

Xác suất lỗi bit

Lpacket P

e

Xác suất lỗi gói tin có kích thƣớc L(bits)

x

P

Xác suất kênh rỗi trong một khe thời gian

s

p

Xác xuất một nút truyền gói tin thành công trong một khe thời gian

t

p

Xác xuất một nút truyền một gói tin trong một khe thời gian

Pwin

Xác suất tranh chấp thắng

P

Ma trận chuyển trạng thái

f

r

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

r

r

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

Rpacket

Tốc độ gói tin

R

s

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

Rt

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

s S,

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

Tpacket

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

Th

Thông lƣợng mạng

W

Trạng thái wait trong mô hình nút 3 trạng thái

xi

DANH MỤC CÁC HÌNH VẼ

Hình 1.1: Kiến trúc điển hình của mạng hình lƣới không dây [7]..............................8

Hình 1.2: Chuỗi Markov Bianchi [16]......................................................................31

Hình 2.1: Hoạt động của giao thức ALOHA [7].......................................................37

Hình 2.2: Hoạt động của giao thức Slotted ALOHA [57] ........................................38

Hình 2.3: Thông lƣợng chuẩn hóa của giao thức ALOHA và ALOHA phân khe [57]

...................................................................................................................................39

Hình 2.5: Chuỗi Markov 3 trạng thái của nút ...........................................................41

Hình 2.6: Biểu diễn mối quan hệ giữa

' pst

với

M

và

pt

.......................................49

Hình 2.7: Khảo sát giá trị

st p

và

' pst

với

M

thay đổi.............................................50

Hình 2.8: Khảo sát giá trị

pst

và

' pst

với sự thay đổi của

pt

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

.....................................................................62

Hình 3.6: Chuỗi Markov của mô hình kênh xung quanh nút....................................65

Hình 3.7: Mô tả các miền diện tích

A

S

và

I

S ...........................................................68

Hình 3.8: Quan hệ giữa thông lƣợng và số lƣợng nút (



thay đổi)...........................71

Hình 3.9: Quan hệ giữa thông lƣợng và số lƣợng nút trong điều kiện bão hòa........72

Hình 3.10: Mối quan hệ giữa thông lƣợng và số lƣợng nút (thay đổi BER ) ...........72

Hình 3.11: Mối quan hệ giữa thông lƣợng và số lƣợng nút (thay đổi



).................73

Hình 3.12: So sánh phƣơng pháp truy nhập cơ bản và RTS/CTS (thay đổi BER)...73

Hình 3.13: So sánh phƣơng pháp truy nhập cơ bản và RTS/CTS (thay đổi



)......74

Hình 4.1: Tính tuần tự của tham số định tuyến.........................................................93

Hình 4.2: Thiết kế xuyên lớp của giao thức OLSR...................................................97

Hình 4.3: Các nội dung sửa đổi giao thức OLSR-IARM trong NS-2.......................98

Hình 4.4: Kiến trúc cơ bản của NS-2......................................................................103

xii

Hình 4.5: Kịch bản mô phỏng.................................................................................104

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

nhập.

Bên cạnh các ƣu điểm về cấu hình và ứng dụng, chính cơ chế truyề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ụ QoS (Quality of

Service) đã cho thấy một số thách thức mà WMN cần phải vƣợt qua về mặt hiệu

năng mạng. Cụ thể, đặc tính truyền thông đa bƣớc không dây, sự biến động chất

lƣợng kênh truyền, cơ chế điều khiển phân tán và tác động nhiễu giữa các liên kết

hình lƣới là nguyên nhân gây suy giảm các thông số hiệu năng mạng nhƣ thông

lƣợng, thời gian trễ và tỷ lệ tổn thất gói tin. Trong đó, ảnh hƣởng của hiện tƣợng

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

kết là một trong các nguyên nhân chính gây ra sự suy giảm hiệu năng [7]. Vì vậy,

việc phản ánh chính xác các yếu tố trên vào quyết định chọn đƣờng cho gói tin là

một hƣớng tiếp cận thực tiễn, mang lại khả năng cải thiện các thông số hiệu năng

mạng.

Nhằm tìm kiếm giải pháp cải thiện hiệu năng WMN, các nghiên cứu gần

đây sử dụng tiếp cận xuyên lớp (crosslayer) để giảm thiểu sự sai khác biến thời gian