Các mạng Ad Hoc di động thu hút sự chú ý về m ột hình mẫu của cấu
hình mạng trong tương lai, với lợi ích là có khả năng triển khai nhanh vì
chúng không cần thiết bị phụ thuộc đã tồn tại.Đồng thời, mạng Ad Hochiếm
khi dựa vào các giao thức định tuyến đặc biệt, giao thức này phải được sửa lại
nhằm đáp ứng với sự thay đổi cấu trúc liên kết mạng.Trongnhững công nghệ
mạng LAN không dây, tiêu chuẩn IEEE 802.11MAC được xem như một công
nghệ nổi bật triển khai trong các mạng Ad Hoc. Sự nhận thức rõ về các mạng
Ad Hoc di động, việc cung cấp QoS (Quality of Service) hỗ trợ trong các
mạng Ad Hoclà một nhiệm vụ quan trọng. Trong số nhiều tham số của QoS,
sự công bằng luồng là một vấn đề quan trọng trong các mạng Ad Hoc. Trong
các mạng có dây truyền thống, sự không công bằng luồng xảy ra chủ yếu tại
tầng liên kết. Tuy nhiên, trong các mạng Ad Hocdi động, ngoài tầng kết nối,
tầng MAC có ảnh hưởng quan trọng trong vấn đề công bằng luồng. Mặc dù
IEEE 802.11 MAC cung cấp sự phân chia băng thông hợp lý cho mỗi nút,
nhưng để đạt được sự công bằng cho mỗi luồng, cần đến một phương thứcđưa
ra sự phân chia băng thông công bằng cho mỗi luồng. Đề tài“Bảo đảm công
bằng luồng trong các mạng Ad Hockhông dây”được viết với mong muốn
góp phần giải quyết vấn đề cấp thiết này.
87 trang |
Chia sẻ: oanhnt | Lượt xem: 1321 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Luận văn Bảo đảm công bằng luồng trong các mạng ad hoc không dây, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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
1
LỜI MỞ ĐẦU
1. Tính cấp thiết của đề tài
Các mạng Ad Hoc di động thu hút sự chú ý về một hình mẫu của cấu
hình mạng trong tương lai, với lợi ích là có khả năng triển khai nhanh vì
chúng không cần thiết bị phụ thuộc đã tồn tại. Đồng thời, mạng Ad Hoc hiếm
khi dựa vào các giao thức định tuyến đặc biệt, giao thức này phải được sửa lại
nhằm đáp ứng với sự thay đổi cấu trúc liên kết mạng. Trong những công nghệ
mạng LAN không dây, tiêu chuẩn IEEE 802.11MAC được xem như một công
nghệ nổi bật triển khai trong các mạng Ad Hoc. Sự nhận thức rõ về các mạng
Ad Hoc di động, việc cung cấp QoS (Quality of Service) hỗ trợ trong các
mạng Ad Hoc là một nhiệm vụ quan trọng. Trong số nhiều tham số của QoS,
sự công bằng luồng là một vấn đề quan trọng trong các mạng Ad Hoc. Trong
các mạng có dây truyền thống, sự không công bằng luồng xảy ra chủ yếu tại
tầng liên kết. Tuy nhiên, trong các mạng Ad Hoc di động, ngoài tầng kết nối,
tầng MAC có ảnh hưởng quan trọng trong vấn đề công bằng luồng. Mặc dù
IEEE 802.11 MAC cung cấp sự phân chia băng thông hợp lý cho mỗi nút,
nhưng để đạt được sự công bằng cho mỗi luồng, cần đến một phương thức đưa
ra sự phân chia băng thông công bằng cho mỗi luồng. Đề tài “Bảo đảm công
bằng luồng trong các mạng Ad Hoc không dây” được viết với mong muốn
góp phần giải quyết vấn đề cấp thiết này.
2. Tình hình nghiên cứu
Hiện nay, có rất nhiều công trình nghiên cứu đưa ra nhiều phương pháp
khác nhau nhằm đạt được sự công bằng trong các mạng không dây. Nhưng
những kết quả đạt được không còn đúng nữa khi áp dụng vào trong các mạng
Ad Hoc mà sự hoạt động của mạng không dựa trên sự tồn tại của cơ sở hạ tầng
tập trung.
Do đó, việc nghiên cứu một cách hệ thống các vấn đề về sự công bằng
trong các mạng Ad Hoc không dây nhằm đưa ra các giải pháp để tăng cường
QoS trên mỗi luồng sẽ tạo ra một cơ chế đáp ứng được sự công bằng trong các
mạng Ad Hoc.
2
3. Mục đích nghiên cứu
Trên cơ sở nghiên cứu một số vấn đề lý luận về nguyên lý, cơ chế hoạt
động của giao thức 802.11 và kinh nghiệm dựa trên một số bài viết về sự công
bằng trong mạng không dây, tác giả xác lập các luận cứ khoa học cho việc xây
dựng một cơ chế nhằm đảm bảo sự công bằng trong các mạng Ad Hoc.
Tìm hiểu nguyên nhân gây ra sự không công bằng thông qua việc phân
tích cơ chế hoạt động của giao thức trong các mô hình ứng dụng cụ thể. Từ đó
đưa ra giải pháp nhằm cải thiện sự công bằng cho mỗi luồng cũng như khả
năng thực thi và tiện ích môi trường trên mạng
4. Đối tượng, phạm vi nghiên cứu
Đối tượng nghiên cứu các vấn đề là: Lý luận liên quan đến mô hình, cấu
trúc, hoạt động của phân lớp 802.11 MAC trong các mạng không dây; kinh
nghiệm nghiên cứu sự công bằng trong các mạng không dây; các phân tích và
kết quả đạt được trong việc nghiên cứu sự công bằng trong các mạng Ad Hoc.
Phạm vi nghiên cứu: Cơ chế hoạt động DCF của phân lớp MAC và tầng
liên kết trong chuẩn IEEE 802.11b.
5. Phương pháp nghiên cứu
Để đạt được các mục đích đề ra, tác giả sử dụng các phương pháp nghiên
cứu như sau: Phương pháp phân tích, phương pháp mô tả, phương pháp thống
kê, mô phỏng ...
6. Kết cấu của luận văn
Ngoài Lời mở đầu và kết luận, nội dung của luận văn được trình bày
trong ba chương:
Chương I: “Tổng quan về phân lớp 802.11 MAC trong các mạng không
dây”
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”
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”
3
CHƯƠNG I
TỔNG QUAN VỀ PHÂN LỚP 802.11 MAC TRONG CÁC
MẠNG KHÔNG DÂY
1.1. Giới thiệu mô hình trong các mạng LAN không dây
Hai mô hình cơ bản sử dụng cho mạng LAN không dây là Ad Hoc và
mạng cơ sở hạ tầng. Hai mô hình này có sự khác biệt nhau rõ ràng về giới hạn
không gian sử dụng, cách quản lý mạng, kiến trúc mạng.
1.1.1. Ad Hoc (IBSS- Independent Basic Service Set)
Tập dịch vụ cơ bản không có cơ sở hạ tầng còn gọi là mạng Ad Hoc. Ad
Hoc là mô hình mạng mà trong đó chỉ bao gồm các máy trạm, không có
Access Point (AP). Mỗi thiết bị kết nối trực tiếp với các thiết bị khác trong
mạng. Mô hình này rất thích hợp cho việc kết nối một nhóm nhỏ các thiết bị
và không cần phải giao tiếp với các hệ thống mạng khác.
Hình 1.1. Mô hình dịch vụ cơ bản không có cơ sở hạ tầng
Định tuyến trong mạng Ad Hoc được xử lý bởi giao thức định tuyến Ad
Hoc, cài đặt ở tầng mạng. Trong giao thức định tuyến này, các nút mạng có
chức năng như là router, chúng có khả năng khám phá và duy trì đường đi đến
các nút mạng khác
Giao thức định tuyến Ad Hoc được chia làm 2 loại: sử dụng bảng định
tuyến và thiết lập đường đi theo yêu cầu của nút mạng nguồn. Bảng định tuyến
lưu trữ thông tin về đường đi giữa hai máy và duy trì tính chất “mới” của
4
thông tin định tuyến phát định kỳ trong mạng.
Các giao thức sử dụng bảng định tuyến bao gồm: DSDV (Destination-
Sequenced Distance Vector Routing), CGSR (Clusterhead Gateway Switch
Routing), WRP (Wireless Routing Protocol). Vấn đề chủ yếu đặt ra với giao
thức kiểu này là: cập nhật bảng và số lượng các đường đi cần lưu trữ. Việc cập
nhật thường xuyên dẫn đến tiêu hao nhiều năng lượng của các node và sinh ra
nhiều gói tin định tuyến làm tăng tải mạng, nếu cập nhật không thường xuyên
trong tình huống các nút mạng di chuyển nhanh sẽ dẫn đến định tuyến sai, do
các thông tin đã cũ.
Sử dụng giao thức “thiết lập đường đi theo yêu cầu nút nguồn” sẽ chỉ
thiết lập đường đi khi cần thiết. Khi một máy muốn truyền tin nó gửi gói tin
“khám phá đường đi” đến đích. Đường đi được thiết lập và duy trì cho đến khi
hai máy tính không muốn sử dụng hoặc không thể truy cập được qua kết nối
đó. Một số giao thức kiểu này là: AODV (Ad Hoc On-Demand Distance
Vector Routing), DSR (Distance Source Routing), TORA (Temporally-
Ordered Routing Algorithm), ABR (Associativity Based Routing), SSR
(Signal Stability Routing). Giao thức loại này có điểm lợi là các nút mạng
không phải duy trì thường xuyên đường đi đến các nút mạng khác. Nhược
điểm là khi có nhu cầu gửi, các nút mạng phải đợi một thời gian để đường đi
được thiết lập, do đó tăng độ trễ gói tin.
1.1.2. Tập dịch vụ cơ sở hạ tầng (IBSS - Infrastructure Basic Service Set)
Tập dịch vụ cơ sở hạ tầng là một mô hình mở rộng của một mạng
Wireless LAN (WLAN) đã có bằng cách sử dụng AP. AP đóng vai trò vừa là
cầu nối của mạng WLAN với các mạng khác vừa là trung tâm điều khiển sự
trao đổi thông tin trong mạng. Các AP sử dụng kĩ thuật “thăm dò” để điều
khiển việc truyền thông trong một BSS, kỹ thuật này thường được gọi là PCF
(Point Coordination Function), có nghĩa là thực hiện chức năng điều khiển
truy cập tập trung.
5
Distribution System
Hình 1.2. Mô hình mạng cơ sở hạ tầng
1.1.3. Tập dịch vụ mở rộng (ESS - Extended Service Set)
Tiêu chuẩn 802.11 mở rộng phạm vi di động tới một phạm vi bất kỳ
thông qua ESS. Một ESS là một tập hợp của các tập dịch vụ cơ sở hạ tầng nơi
mà các AP giao tiếp với nhau để chuyển lưu lượng từ một BSS tới một BSS
khác để làm cho việc di chuyển dễ dàng của các trạm giữa các BSS.
Hình 1.3. Tập hợp dịch vụ mở rộng
6
1.2. Mô tả chức năng phân lớp MAC
1.2.1. Kiến trúc MAC
Phân lớp MAC nằm trong lớp liên kết dữ liệu của mô hình OSI. Phân lớp
MAC xác định cách thức truyền các khung dữ liệu trên môi trường truyền dẫn
bằng cách kết hợp một địa chỉ vật lý cho mỗi thiết bị, xác định tôpô mạng và
thăm dò đường truyền.
Kiến trúc phân lớp MAC bao gồm hai khối chức năng: Khối chức năng
DCF (Distri