bảo đảm công bằng luồng trong các mạng ad hoc không dây

i

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN HOÀNG CHIẾN

BẢO ĐẢM CÔNG BẰNG LUỒNG TRONG

CÁC MẠNG AD HOC KHÔNG DÂY

LUẬN VĂN THẠC SĨ

Hà Nội - 2009

ii

MỤC LỤC

LỜI MỞ ĐẦU................................................................................................1

CHƯƠNG I: TỔNG QUAN VỀ PHÂN LỚP 802.11 MAC TRONG CÁC

MẠNG KHÔNG DÂY...................................................................................3

1.1. Giới thiệu mô hình trong các mạng LAN không dây.........................3

1.1.1. Ad Hoc (IBSS- Independent Basic Service Set)..................................3

1.1.2. Tập dịch vụ cơ sở hạ tầng (IBSS - Infrastructure Basic Service Set)...4

1.1.3. Tập dịch vụ mở rộng (ESS - Extended Service Set)............................5

1.2. Mô tả chức năng phân lớp MAC ........................................................6

1.2.1. Kiến trúc MAC...................................................................................6

1.2.1.1. Chức năng phối hợp phân tán (DCF)...........................................6

1.2.1.2. Chức năng phối hợp điểm (PCF)..................................................7

1.2.1.3 Sự cùng tồn tại của DCF và PCF..................................................8

1.2.1.4. Phân mảnh ...................................................................................8

1.2.1.5. Dịch vụ dữ liệu MAC....................................................................9

1.2.1.6. Các kiểu khung.............................................................................9

1.2.1.6.1. Định dạng khung..................................................................10

1.2.1.6.2 Định dạng các khung thông thường ......................................14

1.2.2. DCF..................................................................................................16

1.2.2.1. Cơ chế cảm biến tần số...............................................................18

1.2.2.2. Các thông báo nhận tầng MAC ..................................................18

1.2.2.3. Interframe space (IFS) ...............................................................19

1.2.2.3.1. Short IFS (SIFS)...................................................................19

1.2.2.3.2. PCF IFS (PIFS) ...................................................................20

1.2.2.3.3. DCF IFS (DIFS) ..................................................................20

1.2.2.3.4. Extended IFS (EIFS) ............................................................21

1.2.2.4. Thời gian backoff ngẫu nhiên .....................................................21

1.2.2.5. Thủ tục truy cập DCF.................................................................22

1.2.2.5.1. Truy cập cơ sở......................................................................23

1.2.2.5.2. Thủ tục Backoff ....................................................................24

1.2.2.5.3. Thiết lập và cài đặt lại NAV.................................................25

iii

1.2.2.5.4. Điều khiển kênh....................................................................26

1.2.2.5.5. Cách sử dụng RTS/CTS với phân đoạn.................................28

1.2.2.5.6. Thủ tục CTS .........................................................................29

1.2.2.5.7. Thủ tục ACK ........................................................................30

1.2.2.5.8. Những quan hệ tính toán thời gian DCF ..............................31

CHƯƠNG II: PHÂN TÍCH NGUYÊN NHÂN CỦA SỰ KHÔNG CÔNG

BẰNG LUỒNG TRONG CÁC MẠNG AD HOC KHÔNG DÂY ............34

2.1. Vấn đề không công bằng luồng trong các mạng Ad Hoc không dây

...................................................................................................................34

2.1.1. Không cân bằng luồng gây ra bởi tầng liên kết .................................34

2.1.2. Không cân bằng luồng gây ra bởi tầng MAC....................................36

2.2. Một số cơ chế đảm bảo công bằng luồng trong các mạng không dây

...................................................................................................................38

2.2.1. Mô hình lập lịch tập trung.................................................................38

2.2.1.1 Mô hình mạng và các vấn đề liên quan đến sự công bằng ...........39

2.2.1.1.1. Mô hình mạng ......................................................................39

2.2.1.1.2. Vấn đề tranh chấp phụ thuộc vị trí và sử dụng lại không gian

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

2.2.1.1.3. Vấn đề xung đột giữa sự công bằng và sử dụng kênh tối đa .40

2.2.1.1.4. Giải pháp không gian...........................................................40

2.2.1.2. Mô hình lập lịch gói tin ..............................................................42

2.2.1.2.1. Mô hình fluid và đồ thị tranh chấp luồng .............................42

2.2.1.2.2. Đạt được công bằng tối thiểu thông qua chia sẻ hàng đợi

công bằng ............................................................................................43

2.2.1.2.3 Các hàng đợi khe và các hàng đợi gói tin .............................45

2.2.2. Cơ chế phối hợp hàng đợi cho mỗi luồng .........................................46

2.2.2.1. Cô lập lưu lượng dữ liệu nguồn..................................................47

2.2.2.2. Trọng số khác nhau trên lưu lượng dữ liệu chuyển tiếp..............48

2.2.2.3. Hàng đợi cho mỗi luồng .............................................................49

2.2.3. Cơ chế phối hợp điều khiển truyền ...................................................50

2.2.3.1. Cơ chế nghe ...............................................................................50

2.2.3.2. Cơ chế backoff............................................................................51

2.2.3.3. Cơ chế tranh chấp cơ sở.............................................................51

iv

2.2.3.4. Cơ chế điều khiển tốc độ ............................................................52

2.2.3.5. Vấn đề nút ẩn đa chặng ..............................................................54

2.2.4. Cơ chế MACAW( Media Access Protocol for Wireless LAN’s) ......55

2.2.4.1. Các quy tắc điều khiển và trao đổi thông báo.............................55

2.2.4.2. Các quy tắc Backoff và sao chép ................................................57

2.2.5. Chuẩn IEEE 802.11 e MAC..............................................................60

CHƯƠNG III: GIẢI PHÁP CẢI THIỆN SỰ CÔNG BẰNG TRONG

CÁC MẠNG AD HOC KHÔNG DÂY.......................................................61

3.1. Giải pháp cải thiện sự công bằng cho mỗi luồng trong tầng liên kết

...................................................................................................................61

3.2. Giải pháp cải thiện sự công bằng cho mỗi luồng trong tầng MAC.63

3.3. Phân tích những đặc trưng của giải pháp cải thiện sự công bằng ..65

3.3.1. Đánh giá phân tích sự công bằng cho mỗi luồng...............................65

3.3.2. Đánh giá phân tích đối với môi trường tiện ích.................................67

3.4. Đánh giá các giải pháp thông qua mô phỏng ...................................68

3.4.1. Mô hình đơn chặng...........................................................................69

3.4.2. Mô hình đa chặng .............................................................................73

KẾT LUẬN ..................................................................................................77

v

DANH MỤC CÁC CHỮ VIẾT TẮT

Chữ viết tắt Tiếng Anh Tiếng Việt

ACK Acknownledgement Báo nhận

AP Access Point Điểm truy nhập

BSS Basic Service Set Tập dịch vụ cơ sở

CBR Constant Bit Rate Tốc độ bit cố định

CFP Contention Free Period Chu kỳ không xung đột

CP Contention Period Chu kỳ xung đột

CRC Cyclic redundancy code Mã dư vòng

CCA Clear channel assessment Đánh giá kênh toàn bộ

CW Contention window Cửa sổ xung đột

CSMA/CA

Carrier Sense Multiple

Access/ Collision

Avoidance

Đa truy nhập cảm nhận

sóng mang nhằm tránh

xung đột

DCF Distributed Coordination

Function

Chức năng phối hợp

phân tán

DIFS DCF interframe space Khoảng cách liên khung

DCF

DS Distribution system Hệ thống phân phối

ESS Extended service sets Tập dịch vụ mở rộng

EIFS Extended interframe

space

Khoảng cách liên khung

mở rộng

FCS Frame check sequence Chuỗi kiểm tra khung

FIFO First in First out Vào trước ra trước

IBSS Independent BSS BSS không phụ thuộc

IFS Interframe space Khoảng cách liên khung

IEEE Institute of Electrical and

Electronics Engineers

Viện các kỹ sư điện điện

tử

LAN Local area network Mạng cục bộ

LLC Logical link control Điều khiển liên kết logic

MLME MAC sublayer Thực thể quản lý lớp con

vi

management entity MAC

MAC Medium Access Control Điều khiển truy nhập

môi trường

MMPDU MAC management

protocol data unit

Đơn vị dữ liệu giao thức

quản lý MAC

MPDU MAC protocol data unit Đơn vị dữ liệu giao thức

MAC

MSDU MAC service data unit Đơn vị dữ liệu dịch vụ

MAC

NAV Network Allocation

Vector Vector định vị mạng

PCF Point Coordination

Function

Chức năng phối hợp

điểm

PIFS PCF interframe space Khoảng cách liên khung

ngắn PCF

PLCP Physical layer

convergence protocol

Giao thức hội tụ tầng vật

lý

PS Power save (mode) Chế độ tiến kiệm năng

lượng

RA Receiver address Địa chỉ nhận

RTS/CTS Request to Send/ Clear to

Send

Yêu cầu gửi/Sẵn sàng để

nhận

RR Round Robin Xoay vòng

Rx Receive or receiver Nhận hoặc thiết bị nhận

SA Source address Địa chỉ nguồn

SFD Start frame delimiter Bắt đầu phạm vi khung

SIFS Short interframe space Khoảng cách liên khung

ngắn

TA Transmitter address Địa chỉ thiết bị truyền

Tx Transmit or transmitter Truyền hoặc thiết bị

truyền

WLAN Wireless LAN Mạng LAN không dây

WEP Wired equivalent privacy Mã truy nhập tương

đương có dây

vii

DANH MỤC BẢNG BIỂU, HÌNH VẼ

Tên bảng/ Hình vẽ Trang

Hình 1.1. Mô hình dịch vụ cơ bản không có cơ sở hạ tầng 3

Hình 1.2. Mô hình mạng cơ sở hạ tầng 5

Hình 1.3. Tập hợp dịch vụ mở rộng 5

Hình 1.4. Mô hình OSI và kiến trúc phân lớp MAC 6

Hình 1.5. Phân đoạn 9

Hình 1.6. Định dạng khung MAC 11

Hình 1.7. Trường điều khiển khung 11

Bảng 1.1. Địa chỉ khác nhau của hai bit ToDS và FromDS 14

Hình 1.8. Khung RTS 14

Hình 1.9. Khung CTS 15

Hình 1.10. Khung ACK 15

Hình 1.11. Một vài mối quan hệ IFS 19

Hình 1.12. Phương thức truy nhập cơ sở 24

Hình 1.13. Thủ tục Backoff 25

Hình 1.14. RTS/CTS/DATA/ACK và thiết lập NAV 26

Hình 1.15. Minh họa việc truyền một đoạn MSDU sử dụng SIFS 27

Hình 1.16. RTS/CTS với các MSDU đã phân đoạn 28

Hình 1.17. RTS/CTS với độ ưu tiên truyền và thiếu báo nhận 29

Hình 1.18. Các mối quan hệ định thời DCF 32

Hình 2.1. Mô hình sự không công bằng xuất hiện tại tầng liên kết 35

viii

Hình 2.2. Mô hình sự không công bằng xuất hiện tại tầng MAC 37

Hình 2.3. Mô hình truy nhập kênh của cơ chế gốc

Hình 2.4. Một mạng không dây đa chặng đơn giản với bốn nút sử dụng

và một gateway

47

Hình 2.5. Những sự phối hợp hàng đợi thích hợp cho các mạng không

dây đa chặng. (a) Hàng đợi tầng mạng đơn.(b) Hai hàng đợi công bằng tại

tầng mạng.(c) Hai trọng số hàng đợi tại tầng mạng.(d) Hàng đợi công

bằng cho mỗi luồng tại tầng mạng.

48

Hình 3.1. Giải thuật xác định số lượng các luồng 62

Hình 3.2. Giải thuật truyền gói tin 64

Hình 3.3. Một thao tác truy nhập kênh đợi DIFS 64

Hình 3.4. FairnessIndex của mỗi cơ chế với mô hình mạng trong hình 2.1 67

Hình 3.5. FairnessIndex của mỗi cơ chế với mô hình mạng trong hình 2.2 67

Bảng 3.1. Các tham số mô phỏng 68

Bảng 3.2. Các đặc trưng riêng biệt của mỗi giải pháp 69

Hình 3.6. Mô hình đơn chặng 70

Hình 3.7. Thông lượng đạt được bởi mỗi luồng trong mô hình đơn chặng 70

Hình 3.8. So sánh FairnessIndex của mỗi cơ chế trong mô hình đơn

chặng

71

Hình 3.9. So sánh FairnessIndex (CBR) với số luồng tại S2 bằng 4 72

Hình 3.10. So sánh môi trường tiện ích trong mô hình đơn chặng 73

Hình 3.11. Mô hình đa chặng 73

Hình 3.12. Thông lượng đạt được bởi mỗi luồng trong mô hình đa chặng 74

Hình 3.13. So sánh FairnessIndex của mỗi cơ chế trong mô hình đa chặng 75

Hình 3.14. So sánh môi trường tiện ích trong mô hình đa chặng 76