Luận văn 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 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 (Distributed Coordination Function là chức năng phối hợp phân tán) và khối chức năng PCF (Point Coordination Function là chức năng phối hợp điểm). Hình 1.4. Mô hình OSI và kiến trúc phân lớp MAC Các phương thức điều khiển truy cập tới các hệ thống WLAN có thể là ngẫu nhiên hoặc được sắp xếp. Hoạt động của hệ thống WLAN có thể tập trung, phân tán hoặc là kết hợp cả hai. Khi hoạt động của hệ thống là ngẫu nhiên, nó được gọi là DCF. Khi hoạt động của mạng được điều khiển, nó được gọi là PCF. 1.2.1.1. Chức năng phối hợp phân tán (DCF) DCF là phương pháp truy nhập theo chuẩn 802.11 cho phép tất cả các trạm trong một WLAN tranh chấp nhau nhằm dành quyền truy nhập vào môi trường truyền dẫn không dây có tính chất chia sẻ nhờ sử dụng giao thức 7 CSMA/CA. DCF sẽ được thực hiện trong tất cả các trạm, thay cho việc sử dụng cả IBSS và cấu hình mạng cơ sở hạ tầng. DCF cho phép hoạt động độc lập của các thiết bị dữ liệu vô tuyến. Trong một hệ thống dựa trên sự tranh chấp DCF, các thiết bị trao đổi thông tin yêu cầu một cách ngẫu nhiên các dịch vụ từ các kênh bên trong một hệ thống trao đổi thông tin. Bởi vì các yêu cầu trao đổi thông tin xảy ra một cách ngẫu nhiên, nên hai hay nhiều thiết bị có thể yêu cầu các dịch vụ một cách đồng thời. Điều khiển truy cập của một phiên DCF thường bao gồm việc yêu cầu các thiết bị phán đoán các hoạt động trước khi truyền và lắng nghe các dịch vụ nó yêu cầu có bị xung đột. Nếu thiết bị yêu cầu không nhận được một phản hồi cho yêu cầu của nó, nó sẽ trì hoãn trong một khoảng thời gian ngẫu nhiên trước khi truy cập lại. Một cải tiến của phương thức có thể sử dụng trong nhiều trường hợp khác nhau để giúp làm giảm tối thiểu các xung đột ở trạm truyền và nhận trao đổi các khung điều khiển ngắn [ yêu cầu gửi (RTS) và sẵn sàng để nhận (CTS) các khung] sau khi xác định môi trường đang rỗi và sau mọi sự trì hoãn hoặc backoff (thời gian chờ đợi trong một khoảng thời gian nhất định), trước khi truyền dữ liệu. Các mô hình mạng BSS (trong mô hình này chỉ có duy nhất một AP và các máy trạm), ESS (đây là mô hình mở rộng của BSS cho phép có nhiều AP và các máy trạm), IBSS (mô hình này không có AP mà chỉ có các máy trạm kết nối trực tiếp với nhau) đều có thể sử dụng được chế độ DCF. 1.2.1.2. Chức năng phối hợp điểm (PCF) PCF là chế độ hoạt động của các thiết bị vô tuyến được điều khiển trong chế độ cơ sở hạ tầng. Trong một hệ thống được điều khiển, các thiết bị trao đổi thông tin đợi cho đến khi nhận được một thông tin phản hồi trước khi chúng truyền bất kỳ một thông tin nào. Bởi vì việc trao đổi thông tin giữa các thiết bị được điều khiển bởi một thiết bị trung tâm nên ít có xung đột xảy ra. Để xác nhận dữ liệu truyền đã được nhận thành công, thông tin thăm dò sẽ có chứa thông tin về trạng thái của các gói tin mà đã được nhận. Nếu thiết bị gửi không nhận một sự xác nhận của việc truyền trong gói tin thăm dò, nó sẽ truyền lại dữ liệu. 8 Ưu điểm của PCF là đảm bảo được một khoảng thời gian trễ xác định vì vậy các ứng dụng yêu cầu về QoS (như các ứng dụng thoại hay truyền hình thời gian thực,…) có thể sử dụng trên nền chế độ truyền dẫn này. Khi sử dụng PCF, AP sẽ đảm nhiệm chức năng thực hiện thuật toán thăm dò do đó các mạng Ad Hoc không thể sử dụng chế độ này. PCF phải được sử dụng kết hợp với DCF. Có thể để kết hợp các lợi ích của DCF và PCF thành một hệ thống tốt hơn. Sự kết hợp dựa trên các khoảng thời gian đặc trưng được chỉ định trong DCF và PCF. Bằng việc kết hợp các quá trình này, có thể đảm bảo việc truyền dữ liệu dịch vụ thời gian thực và cho phép truy cập ngẫu nhiên. 1.2.1.3 Sự cùng tồn tại của DCF và PCF DCF và PCF sẽ cùng tồn tại theo một cách mà cho phép cả hai hoạt động đồng thời trong phạm vi cùng BSS. Khi một PC đang hoạt động trong một BSS, hai phương thức truy cập luân phiên, với một chu kỳ không xung đột (CFP -Contension Free Period) đi theo sau bởi một chu kỳ xung đột (CP - Contension Period). 1.2.1.4. Phân mảnh Quá trình phân chia một đơn vị dữ liệu dịch vụ MAC (MSDU - MAC service data unit) hay một đơn vị dữ liệu giao thức quản lý MAC (MMPDU - MAC management protocol data unit) vào trong các khung MAC cấp nhỏ hơn, các đơn vị dữ liệu giao thức MAC (MPDU-MAC protocol data units), được gọi là phân đoạn. Phân đoạn tạo ra các MPDU nhỏ hơn độ dài MSDU hay MMPDU gốc để tăng thêm độ tin cậy, bằng việc tăng dần khả năng truyền thành công của MSDU hay MMPDU trong trường hợp ở nơi mà kênh đặc trưng hạn chế tiếp nhận độ tin cậy với các khung dài. Phân đoạn được hoàn thành tại mỗi thiết bị truyền tức thời. Quá trình kết hợp lại MPDU thành một MSDU hoặc MMPDU đã được định nghĩa khi ghép phân đoạn. Ghép phân đoạn đã hoàn thành tại mỗi nơi nhận trực tiếp. Chỉ các MPDU với một địa chỉ nơi nhận duy nhất sẽ được phân đoạn. Các khung broadcast/multicast sẽ không được phân đoạn ngay cả khi độ dài của chúng vượt quá giới hạn phân đoạn. 9 Khi một MSDU có hướng nhận được từ điều khiển liên kết logic (LLC - logical link control) hoặc MMPDU có hướng nhận được từ thực thể quản lý lớp con MAC (MLME – MAC sublayer management entity) với một độ dài lớn hơn giới hạn phân đoạn, MSDU hoặc MMPDU sẽ được phân đoạn. MSDU hoặc MMPDU được tách ra thành các MPDU. Mỗi đoạn là một khung không lớn hơn giới hạn phân đoạn. Điều đó có thể xảy ra khi mà bất cứ đoạn nào có thể có một khung nhỏ hơn giới hạn phân đoạn. Một minh hoạ về sự phân đoạn được trình bày trong hình 1.5. Các MPDU là kết quả từ sự phân đoạn của một MSDU hoặc MMPDU để gửi đi khi truyền độc lập, mỗi thành phần được nhận tách biệt nhau. Điều này cho phép truyền lại xảy ra với mỗi đoạn, hơn là mỗi MSDU hoặc MMPDU. Hình 1.5. Phân đoạn Trừ khi ngắt do các giới hạn chiếm giữ môi trường đối với một tầng vật lý nhất định, các đoạn của một MSDU hoặc MMPDU đơn lẻ được gửi đi như một sự nỗ lực trong khoảng thời gian chu kỳ xung đột, sử dụng chỉ có một dẫn chứng của thủ tục truy cập môi trường DCF. Các đoạn của một MSDU hoặc MMPDU đơn lẻ được gửi trong khoảng thời gian một chu kỳ không xung đột khi những khung riêng lẻ tuân theo những quy tắc của một điểm phối hợp thủ tục truy cập môi trường. 1.2.1.5. Dịch vụ dữ liệu MAC Dịch vụ dữ liệu MAC sẽ thông dịch các yêu cầu dịch vụ MAC từ LLC thành các tín hiệu dữ liệu vào được sử dụng bởi máy trạng thái MAC. Dịch vụ dữ liệu MAC cũng sẽ thông dịch các tín hiệu dữ liệu ra từ máy trạng thái MAC thành các dấu hiệu dịch vụ tới LLC. 1.2.1.6. Các kiểu khung Có ba kiểu khung chính: 10  Khung dữ liệu (Data Frame): được sử dụng để truyền dữ liệu.  Khung điều khiển (Control Frame): được sử dụng để điều khiển truy cập môi trường (RTS, CTS, và ACK).  Khung quản lý (Management Frame): đó là các khung mà được truyền theo cùng một cách như các khung dữ liệu để trao đổi thông tin quản lý, nhưng không chuyển tiếp lên các tầng cao hơn. Mỗi một kiểu cũng được chia nhỏ thành các kiểu con khác nhau, theo các chức năng cụ thể. 1.2.1.6.1. Định dạng khung Tất cả các khung 802.11 bao gồm bởi các thành phần như sau: Preamble PLCP Header MAC Data CRC  Trường Preamble Điều này phụ thuộc vào tầng vật lý, bao gồm:  Synch: một chuỗi 80 bít luân phiên các số 0 và 1, chúng được sử dụng bởi sơ đồ mạnh tầng vật lý để lựa chọn anten thích hợp (nếu tính đa dạng được sử dụng), và phạm vi khoảng trống tần số xuất hiện trạng thái dừng để hiệu chỉnh và đồng bộ hoá với việc tính toán thời gian gói tin nhận được.  SFD: Một khung bắt đầu được phân định gồm có 16 bít nhị phân có dạng 0000 1100 1011 1101, chúng được sử dụng để định nghĩa việc tính toán thời gian khung.  Trường PLCP Header Đoạn đầu PLCP luôn luôn được truyền với 1 Mbit/s và bao gồm thông tin logic sẽ được sử dụng bởi tầng vật lý để giải mã khung, gồm có:  Độ dài từ PLCP_PDU: miêu tả số lượng các byte được chứa trong gói tin, điều này hữu ích đối với tầng vật lý để phát hiện chính xác thời điểm kết thúc của gói tin.  Trường tín hiệu PLCP: hiện thời chỉ chứa tốc độ thông tin, được mã hoá trong khoảng 0.5 Mbps rồi tăng dần từ 1 Mbit/s đến 4.5 11 Mbit/s.  Trường kiểm tra lỗi tiêu đề: đó là một trường 16 bít CRC để phát hiện lỗi.  Trường MAC data Hình sau cho thấy tổng quát định dạng khung MAC, một phần của trường này chỉ có trong bộ phận của các khung như được miêu tả sau đây. Hình 1.6 . Định dạng khung MAC Trường Frame Control Trường điều khiển khung chứa đựng thông tin sau đây: Hình 1.7. Trường điều khiển khung Trường Protocol version Trường này bao gồm 2 bít mà không thay đổi về kích thước và được sắp xếp ngang theo các phiên bản của chuẩn 802.11, và sẽ được sử dụng để nhận ra các phiên bản có thể xảy ra trong tương lai. Trong phiên bản của chuẩn hiện tại giá trị này được cố định là 0. Trường Type và subtype Có 6 bít định nghĩa kiểu và kiểu con của khung. Trường ToDS Bít này thiết lập là 1 khi khung được gửi tới AP để chuyển tiếp nó tới hệ thống phân phối (bao gồm trường hợp ở đó trạm đích là trong cùng BSS, và AP sắp đặt lại khung). Bít này được thiết lập là 0 trong tất cả các khung khác. 12 Trường FromDS Bít này thiết lập là 1 khi mà khung đang đi tới từ hệ thống phân phối (DS - Distribution System). Trường More Fragments Bít này thiêt lập là 1 khi mà có nhiều các đoạn thuộc về cùng một khung theo sau đoạn hiện thời này. Trường Retry Bít này cho biết rằng đoạn này là truyền lại của đoạn đã truyền trước đó, nó sẽ được sử dụng bởi trạm nhận để nhận ra bản sao truyền của các khung mà có thể xuất hiện khi một gói báo nhận bị mất. Trường Power Management Bít này cho biết chế độ quản lý năng lượng mà trạm muốn có sau khi truyền khung này. Điều này được sử dụng bởi các trạm mà đang thay đổi trạng thái hoặc từ chế độ tiết kiệm (PS-Power Save) được Active hoặc ngược lại. Trường More Data Bít này cũng được sử dụng cho chế độ quản lý năng lượng và nó được sử dụng bởi AP để cho biết rằng có nhiều khung hơn trong vùng đệm của trạm này. Trạm có thể quyết định sử dụng thông tin này để tiếp tục kiểm soát vòng hay thậm chí đang thay đổi chế độ tới Active. Trường WEP Bít này cho biết rằng thân khung được mã hóa theo giải thuật mã truy nhập tương đương có dây (WEP - wired equivalent privacy). Trường Order Bít này cho biết rằng khung này đang được gửi sử dụng lớp dịch vụ Strictly-Ordered 2. Trường Duration/ID 13 Trường này có hai nghĩa độc lập dựa trên kiểu khung: trong các thông báo thăm dò PS đây là ID của trạm và trong tất cả các khung khác đây là giá trị khoảng thời gian được sử dụng cho tính toán NAV. Trường Address Fields Một khung có thể bao gồm có tới 4 địa chỉ đang phụ thuộc vào các bít ToDS và FromDS được định nghĩa trong trường điều khiển, như sau: Address-1 Luôn luôn là địa chỉ nhận (ví dụ một trạm trong BSS mà ngay lập tức nhận được gói tin), nếu như ToDS được thiết lập đó là địa chỉ của AP, nếu như ToDS không được thiết lập thì đây là địa chỉ của trạm cuối. Address-2 Luôn luôn là địa chỉ máy phát (ví dụ một trạm mà về vật lý đang truyền gói tin), nếu như FromDS được thiết lập đây là địa chỉ của AP, nếu như nó không được thiết lập thì nó là địa chỉ của máy trạm. Address-3 Trong đa số những trường hợp còn lại, mất địa chỉ, trên một khung với FromDS được thiết lập là 1, sau đó Address-3 là địa chỉ nguồn gốc, nếu như khung có ToDS thiết lập thì Address-3 là địa chỉ đích. Address-4 Được sử dụng trên trường hợp đặc biệt nơi mà hệ thống phân phối không dây được sử dụng, và khung đang được truyền từ một điểm truy nhập tới một điểm khác, trong trường hợp này cả hai bít ToDS và FromDS được thiết lập, cho nên cả hai đích gốc và địa chỉ nguồn gốc là thiếu. Theo bảng tổng kết cách sử dụng các địa chỉ khác nhau theo sự bố trí các bít ToDS và FromDS. 14 Bảng 1.1. Sử dụng các địa chỉ khác nhau của hai bít ToDS và FromDS ToDS From DS Address 1 Address 2 Address 3 Address 4 0 0 DA SA BSSID N/A 0 1 DA BSSID SA N/A 1 0 BSSID SA DA N/A 1 1 RA TA DA SA Trường Sequence Control Trường Sequence Control được sử dụng để miêu tả thứ tự của các đoạn khác nhau đang thuộc về cùng một khung, và nhận ra các bản sao gói tin, nó bao gồm hai trường con Fragment Number, và Sequence Number, chúng định nghĩa khung và số lượng đoạn trong một khung.  CRC (Cyclic Redundancy Check) CRC là một trường 32 bít kiểm tra mã dư vòng. 1.2.1.6.2 Định dạng các khung thông thường  RTS Frame Format Cấu trúc khung RTS như sau: Hình1.8. Khung RTS RA (Receiver Address) của một khung RTS là địa chỉ của trạm, trên môi trường không dây, được dự định trực tiếp nhận dữ liệu kế tiếp hoặc khung quản lý. 15 TA (Transmitter address) sẽ là địa chỉ của trạm đang truyền khung RTS. Giá trị Duration là khoảng thời gian, trong một phần triệu của giây, được yêu cầu truyền dữ liệu kế tiếp hoặc khung quản lý, cộng với một khung CTS, cộng với một khung ACK, cộng với ba khoảng thời gian SIFS.  CTS Frame Format Cấu trúc khung RTS như sau: Hình1.9. Khung CTS RA của khung CTS được sao chép từ trường TA của khung RTS liền trước trực tiếp tới CTS mà đang trả lời. Giá trị Duration là giá trị đạt được từ trường Duration của khung RTS liền trước trực tiếp, trừ thời gian, trong một phần triệu của giây, yêu cầu truyền khung CTS và khoảng thời gian SIFS của nó.  ACK Frame Format Cấu trúc khung ACK như sau: Hình 1.10. Khung ACK RA của khung ACK được sao chép từ địa chỉ Address-2 của khung liền trước trực tiếp. Nếu như nhiều đoạn bít đã thiết lập là 0 trong trường Frame Control của khung liền trước, giá trị Duration được thiết lập là 0, nếu không giá trị Duration đạt được từ trường Duration của khung liền trước, trừ thời gian, trong một phần triệu giây, yêu cầu truyền khung ACK và khoảng thời gian SIFS của nó. 16 1.2.2. DCF Giao thức truy cập môi trường cơ bản là DCF cho phép tự động chia sẻ môi trường giữa các tầng vật lý tương thích thông qua sử dụng giao thức CSMA/CA và thời gian backoff ngẫu nhiên theo sau một trạng thái môi trường bận. Ngoài ra, tất cả lưu lượng có hướng sử dụng khung báo nhận xác thực trực tiếp (ACK) ở nơi mà việc truyền lại được lập lịch bởi nơi gửi nếu như không có khung ACK nào nhận được. Giao thức CSMA/CA được thiết kể để giảm bớt khả năng có thể xảy ra xung đột giữa các trạm cùng truy cập một môi trường, tại một điểm mà ở đó các xung đột có nhiều khả năng xảy ra. Ngay sau khi môi trường trở nên rỗi tiếp theo một môi trường bận (như được biểu thị bởi chức năng cảm biến tần số) là khi khả năng cao nhất xảy ra của một xung đột đã tồn tại. Đó là bởi vì nhiều trạm có thể đang đợi môi trường trở nên sẵn sàng để sử dụng trở lại. Đây là trạng thái cần phải có một thủ tục backoff ngẫu nhiên để giải quyết tranh chấp xung đột môi trường. Cảm biến tần số sẽ được thực hiện thông qua cả hai cơ chế ảo và vật lý. Cơ chế cảm biến tần số ảo đạt được bởi việc phân phối thông tin riêng biệt thông báo sắp xảy ra sử dụng môi trường. Sự trao đổi của các khung RTS và CTS trước khung dữ liệu hiện thời là một cách thức để phân phối thông tin môi trường riêng biệt này. Các khung RTS và CTS bao gồm một trường Duration/ ID để định nghĩa chu kỳ thời gian mà môi trường đã dành riêng để truyền khung dữ liệu hiện thời và gửi trả lại khung ACK. Tất cả trạm bên trong dải tiếp nhận của trạm nguồn (truyền RTS) hoặc trạm đích (truyền CTS) sẽ được biết về môi trường dự trữ. Kết quả là, một trạm có thể không nhận được dữ liệu từ trạm nguồn, nhưng vẫn biết rằng đang xảy ra việc sử dụng môi trường để truyền một khung dữ liệu. Một cách khác để phân phối thông tin môi trường riêng biệt là trường Duration/ID trong những khung có hướng. Trường này đưa ra thời gian mà môi trường đã dự trữ, hoặc kết thúc ngay lập tức theo sau ACK, hoặc trong trường hợp của một chuỗi phân đoạn, cho tới khi kết thúc của ACK sau đoạn kế tiếp. Sự trao đổi RTS/CTS cũng thực hiện cả hai kiểu phát hiện xung đột nhanh và kiểm tra đường truyền. Nếu như CTS trả lại không được phát hiện 17 bởi RTS các trạm nguồn, trạm nguồn có thể lặp lại quá trình (sau khi quan sát quy tắc sử dụng môi trường) nhanh hơn nếu như khung dữ liệu dài đã được truyền và khung ACK trả lại không được phát hiện. Một lợi thế khác của cơ chế RTS/CTS xảy ra ở nơi mà sử dụng nhiều BSS giống như một kênh chồng chéo. Cơ chế hạn chế môi trường làm việc thông qua các ranh giới vùng dịch vụ cơ sở (BSA-basic service area). Cơ chế RTS/CTS cũng có thể cải thiện quá trình hoạt động trong một trạng thái điển hình ở nơi mà tất cả các trạm có thể nhận từ AP, nhưng không thể nhận từ tất cả các trạm khác trong BSA. Cơ chế RTS/CTS không thể sử dụng được cho các MPDU với địa chỉ tức thời broadcast và multicast bởi vì có nhiều đích đến RTS, và như vậy nhiều khả năng các nguồn gửi cùng một lúc về CTS trong lúc trả lời. Cơ chế RTS/CTS không cần thiết phải sử dụng để truyền với mọi khung dữ liệu. Bởi vì việc bổ sung các khung RTS và CTS thêm vào ở phần đầu không có hiệu quả, cơ chế này không phải lúc nào cũng đúng, đặc biệt là với các khung dữ liệu ngắn. Sử dụng bằng cơ chế RTS/CTS là dưới quyền điều khiển của thuộc tính giới hạn RTS. Thuộc tính này có thể thiết lập trong mỗi trạm cơ sở. Cơ chế này cho phép các trạm được cấu hình sử dụng RTS/CTS hoặc thường xuyên, không bao giờ, hay chỉ trong các khung dài hơn so với chiều dài lý thuyết. Một trạm đã cấu hình không bắt đầu bằng cơ chế RTS/CTS sẽ vẫn cập nhật cơ chế cảm biến tần số ảo của nó với khoảng thời gian thông tin đã chứa đựng trong một khung RTS hoặc CTS nhận được, và sẽ thường xuyên đáp trả lại với một RTS được gửi tới nó bằng một CTS. Giao thức truy cập môi trường cho phép các trạm được hỗ trợ tập hợp có tốc độ dữ liệu khác nhau. Tất cả các trạm sẽ nhận toàn bộ tốc độ dữ liệu trong một tập tốc độ cơ sở và truyền một hoặc nhiều hơn tốc độ dữ liệu trong một tập tốc độ cơ sở. Để hỗ trợ quy trình hoạt động thích hợp của RTS/CTS và cơ chế cảm biến tần số ảo, tất cả các trạm sẽ có khả năng phát hiện các khung RTS và CTS. Vì lý do này các khung RTS và CTS sẽ được truyền với một tốc độ của tập tốc độ cơ sở. Các khung dữ liệu được gửi theo DCF sẽ sử dụng dữ liệu kiểu khung và dữ liệu con hoặc hàm Null. Các trạm đang nhận dữ liệu 18 kiểu khung sẽ chỉ xem xét thân khung như cơ sở của một chỉ định có thể xảy ra tới LLC. 1.2.2.1. Cơ chế cảm biến tần số Những chức năng vật lý và cảm biến tần số ảo được dùng để xác định trạng thái của môi trường. Khi một trong hai chức năng này cho biết môi trường đang bận, môi trường sẽ được coi là bận; mặt khác, nó sẽ được coi là rỗi. Một cơ chế cảm biến tần số vật lý sẽ được cung cấp bởi tầng vật lý. Những chi tiết về cảm biến tần số vật lý được cung cấp trong các đặc điểm kỹ thuật tầng vật lý riêng biệt. Một cơ chế cảm biến tần số ảo sẽ được cung cấp bởi MAC. Cơ chế này được nhắc tới như vectơ định vị mạng (NAV-network allocation vector). NAV duy trì một dự đoán về lưu lượng tương lai trong môi trường được dựa trên thông tin về khoảng thời gian mà được thông báo trong các khung RTS/CTS trước khi trao đổi dữ liệu thực tế. Thông tin khoảng thời gian cũng sẵn có trong phần đầu MAC của tất cả các khung được gửi trong khoảng thời gian chu kỳ xung đột khác với các khung điều khiển thăm dò tiết kiệm năng lượng. Cơ chế cảm biến tần số phối hợp trạng thái NAV và tình trạng truyền các trạm với cảm biến tần số vật lý để xác định trạng thái bận/ rỗi của môi trường. NAV có thể nghĩ đến như một máy đếm, nó đếm ngược tới 0 với một tốc độ không đổi. Khi máy đếm là 0, biểu thị cảm biến tần số ảo là môi trường đang rỗi; khi không phải là 0, biểu hiện đang bận. Môi trường sẽ được xác định bận mỗi khi một trạm đang truyền. 1.2.2.2. Các thông báo nhận tầng MAC Sự tiếp nhận một số các khung, phụ thuộc vào trạm đang nhận trả lời lại với thông báo nhận, thông thường là một khung ACK, nếu như chuỗi kiểm tra khung (FCS-frame check sequence) của khung vừa nhận được là đúng. Kỹ thuật này được biết đến để xác thực thông báo nhận. Thiếu sự tiếp nhận trong một khung ACK biểu thị rằng trạm nguồn có lỗi xảy ra. Lưu ý, tuy nhiên, trạm đích có thể đã nhận được chính xác khung, và lỗi đó có thể đã xảy ra trong khi tiếp nhận khung ACK. Khi trạm bắt đầu trao đổi khung, đây là điều kiện không thể phân biệt được lỗi khi xảy ra trong 19 khung ban đầu. 1.2.2.3. Interframe space (IFS) Khoảng thời gian giữa các khung được gọi là IFS. Một trạm sẽ xác định xem môi trường có rỗi thông qua sử dụng chức năng cảm biến tần số với một khoảng thời gian xác định. Bốn IFS khác nhau được định nghĩa để cung cấp các mức độ ưu tiên trong truy cập với môi trường không dây. Chúng được liệt kê theo thứ tự, từ ngắn nhất đến dài nhất. Hình 1.11 cho thấy một số những mối quan hệ này.  SIFS - short interframe space  PIFS - PCF interframe space  DIFS - DCF interframe space  EIFS - extended interframe space Các IFS khác nhau sẽ độc lập về tốc độ bít mỗi trạm. Thời gian IFS sẽ được định nghĩa như thời gian trống trên môi trường, và sẽ được cố định với mỗi tầng vật lý (thậm chí trong các tầng vật lý có khả năng nhiều tốc độ). Các giá trị IFS được xác định từ các thuộc tính được xác định bởi tầng vật lý. Hình 1.11. Một vài mối quan hệ IFS 1.2.2.3.1. Short IFS (SIFS) SIFS sẽ được sử dụng cho một khung ACK, một khung CTS, thứ hai hoặc MPDU kế tiếp của một chùm đoạn, và do một trạm trả lời với bất kỳ sự kiểm tra tuần tự bởi PCF. Nó cũng có thể được sử dụng bởi một điểm phối hợp cho bất kỳ kiểu khung trong khoảng thời gian chu kỳ không xung đột. SIFS là thời gian từ khi kết thúc biểu tượng cuối cùng của khung liền trước tới khi bắt đầu biểu tượng đầu tiên với phần đầu của khung kế tiếp như được nhìn 20 thấy tại giao diện trình bày. SIFS sẽ tính toán thời gian đạt được khi truyền khung kế tiếp được bắt đầu tại ranh giới khe TxSIFS. Sự thi hành chuẩn IEEE 802.11 sẽ không cho phép khoảng trống giữa các khung được định nghĩa phân chia bằng thời gian SIFS, khi đã đều đặn trên môi trường, tới sự thay đổi từ giá trị SIFS quy định bằng nhiều hơn ±10% của một khe thời gian trong tầng vật lý đang sử dụng. SIFS là ngắn nhất trong IFS. SIFS sẽ được sử dụng khi các trạm cho là đã nắm được môi trường và cần thiết phải giữ nó trong một khoảng thời gian của chuỗi trao đổi khung để thực hiện. Việc sử dụng khoảng trống nhỏ nhất giữa các phiên truyền bên trong chuỗi trao đổi khung ngăn chặn các trạm khác, mà được yêu cầu chờ đợi môi trường rỗi trong một khoảng trống thời gian dài hơn, từ sự cố gắng sử dụng môi trường, do đó dành quyền ưu tiên để hoàn thành chuỗi trao đổi khung trong tiến trình. 1.2.2.3.2. PCF IFS (PIFS) PIFS sẽ được sử dụng duy nhất bởi các trạm đang hoạt động dưới PCF để lấy được quyền ưu tiên truy cập môi trường khi bắt đầu chu kỳ không xung đột. Một trạm đang sử dụng PCF sẽ cho phép truyền lưu lượng không tranh chấp sau khi cơ chế cảm biến tần số của nó xác định rằng môi trường đang rỗi tại khe ranh giới TxPIFS. 1.2.2.3.3. DCF IFS (DIFS) DIFS sẽ được sử dụng bởi các trạm đang hoạt động dưới DCF để truyền các khung dữ liệu MPDU và các khung quản lý MMPDU. Một trạm đang sử dụng DCF sẽ cho phép truyền nếu cơ chế cảm biến tần số của nó xác định rằng môi trường đang rỗi tại khe ranh giới TxPIFS sau khi một khung được nhận chính xác, và thời gian backoff của nó hết hạn. Một trạm đang sử dụng DCF sẽ không truyền trong phạm vi một EIFS sau khi nó xác định rằng môi trường đang rỗi, tiếp theo sẽ tiếp nhận một khung đối với báo hiệu kết thúc nhận tầng vật lý gốc chứa đựng một lỗi hoặc một khung với một giá trị MAC FCS nào đó không chính xác. Một trạm có thể truyền sau khi nhận tiếp một khung không có lỗi, tái đồng bộ hoá trạm. Điều này cho phép trạm truyền sử dụng DIFS theo sau khung đó. 21 1.2.2.3.4. Extended IFS (EIFS) EIFS sẽ được sử dụng bởi DCF bất cứ khi nào tầng vật lý có chỉ thị tới MAC rằng một khung truyền đã bắt đầu mà kết quả là không nhận được chính xác về một khung MAC đầy đủ với một giá trị FCS chính xác. Khoảng thời gian giữa hai EIFS sẽ bắt đầu sau chỉ thị do tầng vật lý cho rằng môi trường rỗi sau khi phát hiện khung lỗi, không liên quan đến cơ chế cảm biến tần số ảo. EIFS được định nghĩa để cung cấp đủ thời gian cho một trạm khác để báo nhận được những gì, từ trạm này, một khung được nhận không chính xác trước khi trạm này bắt đầu truyền. Sự tiếp nhận một khung không có lỗi trong khoảng thời gian EIFS để đồng bộ hoá trạm gây ra trạng thái bận/rỗi hiện tại của môi trường, vì vậy EIFS được kết thúc và tiếp tục truy cập môi trường bình thường (sử dụng DIFS và, nếu cần thiết, backoff) sau khi nhận được khung đó. 1.2.2.4. Thời gian backoff ngẫu nhiên Một trạm yêu cầu bắt đầu truyền dữ liệu MPDU và/hoặc quản lý MMPDU sẽ gọi cơ chế cảm biến tần số để xác định trạng thái bận/rỗi của môi trường. Nếu như môi trường bận, trạm sẽ hoãn cho đến khi môi trường được xác định là rỗi mà không cần gián đoạn trong một khoảng thời gian bằng DIFS khi mà khung cuối cùng được phát hiện ra trên môi trường là đã được nhận chính xác, hoặc sau khi môi trường được xác định là rỗi không cần gián đoạn trong một khoảng thời gian bằng EIFS khi khung cuối cùng được được phát hiện ra trên môi trường là không được nhận chính xác. Sau thời gian rỗi của môi trường DIFS hay EIFS này, trạm tiếp theo sẽ phát ra một chu kỳ backoff ngẫu nhiên trong thời gian trì hoãn để bổ sung vào trước khi truyền, trừ khi thiết bị bấm giờ backoff đã chứa đựng một giá trị khác không, trong trường hợp này sự lựa chọn một số ngẫu nhiên là không cần thiết và không được thực hiện. Quá trình này làm giảm tổi thiểu các xung đột trong thời gian tranh chấp giữa các trạm mà đang trì hoãn với cùng một sự kiện. Backoff Time = Random() x aSlotTime Ở đây Random() là số nguyên giả ngẫu nhiên được lấy ra từ sự phân phối giống nhau lên trên khoảng thời gian [0,CW], CW(Contention window) là 22 một số nguyên trong phạm vi dải của các giá trị thuộc những đặc trưng tầng vật lý aCWmin và aCWmax, aCWmin ≤ CW ≤ aCWmax. aSlotTime là giá trị đặc trưng tầng vật lý có tên tương ứng. Tham số cửa sổ xung đột (CW) sẽ giữ một giá trị ban đầu của aCWmin. Mỗi trạm sẽ duy trì một trạm đếm lại ngắn (SSRC-station short retry count) cũng như một trạm đếm lại dài (SLRC-station long retry count ), cả hai cách đếm sẽ giữ một giá trị ban đầu là không. SSRC sẽ được tăng lên bất kỳ khi nào mọi sự đếm thử lại ngắn được kết hợp với bất cứ MSDU nào được tăng lên. SLRC sẽ được tăng lên bất kỳ khi nào mọi sự đếm thử lại dài được kết hợp với bất cứ MSDU nào được tăng lên. CW sẽ giữ giá trị tiếp theo trong các chuỗi lần nào cũng cố gắng để truyền một MPDU mà không thành công nhiều nguyên nhân hoặc là máy đếm thử lại STA được tăng lên, cho đến khi CW đạt đến giá trị aCWmax. Thử lại được định nghĩa như toàn bộ chuỗi của các khung được gửi, được phân chia bằng các khoảng thời gian SIFS, trong một cố gắng để thực hiện một MPDU. Khi mà nó đạt được aCWmax, CW sẽ giữ nguyên giá trị của aCWmax cho đến khi nó xác lập lại. Điều này cải thiện độ ổn định của giao thức truy cập dưới nhiều điều kiện. CW sẽ xác lập lại với aCWmin sau khi mọi cố gắng để truyền một MSDU hay MMPDU thành công, khi SLRC đạt được một giới hạn thử lại dài, hay là khi SSRC đạt được giới hạn thử lại ngắn. SSRC sẽ xác lập lại về 0 mỗi khi một khung CTS nhận được trả lời với một khung RTS, mỗi khi một khung ACK nhận được trả lời với việc truyền một MPDU hoặc MMPDU, hoặc mỗi khi một khung với một nhóm địa chỉ trong trường Address-1 đã được truyền. SLRC sẽ xác lập lại về 0 mỗi khi một khung ACK nhận được trả lời với việc truyền một MPDU hoặc MMPDU bằng độ dài lớn hơn so với bắt đầu RTS, hoặc mỗi khi một khung với một nhóm địa chỉ trong trường Address-1 đã được truyền. Tập hợp các giá trị của CW sẽ liên tục tăng với số nguyên luỹ thừa của 2, trừ 1, lúc bắt đầu với một giá trị aCWmin tầng vật lý riêng biệt, và tiếp tục tăng lên và bao gồm cả một giá trị aCWmax tầng vật lý riêng biệt. 1.2.2.5. Thủ tục truy cập DCF Phương thức truy cập CSMA/CA là nền tảng của DCF. Các quy tắc cho quá trình hoạt động thay đổi không đáng kể giữa DCF và PCF. 23 1.2.2.5.1. Truy cập cơ sở Truy cập cơ sở có liên quan tới cơ chế lõi sử dụng một trạm để xác định xem nó có thể truyền hay không. Nói chung, một trạm có thể truyền một MPDU chưa thực hiện khi nó hoạt động dưới phương thức truy cập DCF, hay khi thiếu một điểm phối hợp, hoặc trong chu kỳ xung đột của phương thức truy cập PCF, khi một trạm xác định rằng môi trường đang rỗi theo tỷ lệ lớn hơn hoặc bằng với một chu kỳ DIFS, hoặc một chu kỳ EIFS nếu như ngay lập tức sự kiện môi trường bận trước đó được gây ra bởi sự phát hiện một khung, tức là đã không nhận được tại trạm này với một giá trị MAC FCS chính xác. Nếu như, dưới những điều kiện này, môi trường được xác định bởi cơ chế cảm biến tần số là đang bận khi một trạm yêu cầu bắt đầu với khung ban đầu của một trong số các khung trao đổi, loại trừ chu kỳ không xung đột, giải thuật backoff ngẫu nhiên sẽ xảy ra. Trong khi một trạm đang có một tần số bước nhảy vật lý, quyền điều khiển kênh mất vào thời điểm dừng lại tại ranh giới và trạm sẽ phải chắc chắn lấy lại được kênh sau khi dừng lại tại ranh giới tiếp theo. Nó yêu cầu các trạm mà có tần số bước nhảy vật lý hoàn thành việc truyền toàn bộ MPDU và kết hợp báo nhận (nếu được yêu cầu) trước thời gian dừng lại tại ranh giới. Nếu như, khi đang truyền hoặc truyền lại một MPDU, không đủ thời gian còn lại trong lúc dừng để cho phép truyền MPDU cùng với báo nhận (nếu được yêu cầu), trạm sẽ trì hoãn việc truyền bằng cách lựa chọn một khoảng thời gian ngẫu nhiên, sử dụng CW hiện tại (không tăng lên với giá trị trong các phiên bản kế tiếp). Bộ đếm lại ngắn và bộ đếm lại dài đối với MSDU là không bị ảnh hưởng. Hình1.12. Phương thức truy nhập cơ sở 24 1.2.2.5.2. Thủ tục Backoff Thủ tục backoff sẽ được gọi đối với một trạm để truyền một khung khi phát hiện ra môi trường bận do được thông báo bởi tầng vật lý hoặc cơ chế cảm biến tần số ảo. Thủ tục backoff cũng sẽ được gọi khi một trạm đang truyền đưa đến kết luận truyền có lỗi. Để bắt đầu thủ tục backoff, trạm sẽ thiết lập bộ tính giờ backoff của nó với một thời gian backoff ngẫu nhiên. Tất cả các khe backoff xảy ra theo sau một chu kỳ DIFS trong thời gian mà môi trường được xác định là rỗi trong khoảng thời gian của chu kỳ DIFS, hoặc theo sau một chu kỳ EIFS trong khoảng thời gian mà môi trường được xác định là rỗi trong khoảng thời gian của chu kỳ EIFS theo đó phát hiện một khung mà đã không nhận được chính xác. Một trạm đang thực thiện thủ tục backoff sẽ sử dụng cơ chế cảm biến tần số để xác định liệu có hoạt động trong thời gian mỗi khe backoff hay không. Nếu như phạm vi hoạt động môi trường không được thông báo trong khoảng thời gian của một khe backoff riêng biệt, trong trường hợp này thủ tục backoff sẽ giảm thời gian backoff của nó bởi một khe thời gian. Nếu như môi trường được xác định là bận tại bất cứ thời gian nào trong khoảng thời gian một khe backoff, trong trường hợp này thủ tục backoff bị đình chỉ; tức là, bộ tính giờ backoff sẽ không giảm đối với khe đó. Môi trường sẽ được xác định là rỗi trong khoảng thời gian của một khu kỳ DIFS hoặc EIFS, thích hợp như, trước khi thủ tục backoff được cho phép bắt đầu lại. Quá trình truyền sẽ bắt đầu bất cứ khi nào bộ tính giờ backoff đạt đến con số 0. Một thủ tục backoff sẽ được thực hiện ngay lập tức sau khi kết thúc mỗi phiên truyền với nhiều đoạn bít thiết lập tiến tới 0 trong một MPDU gồm có kiểu dữ liệu, quản lý, hoặc điều khiển với thăm dò PS phụ, thậm chí nếu như các phiên truyền không được thêm vào hàng đợi hiện thời. Trong trường hợp các phiên truyền được thông báo nhận thành công, thủ tục backoff này sẽ bắt đầu tại nơi cuối cùng nhận được khung ACK. Trong trường hợp các phiên truyền không thành công phải cần đến tin báo nhận, thủ tục backoff này sẽ bắt đầu tại nơi cuối cùng trong khoảng thời gian chờ đợi ACK. Nếu như phiên 25 truyền thành công, giá trị CW trở lại tới CWmin trước khi khoảng thời gian backoff ngẫu nhiên được lựa chọn. Điều này đảm bảo rằng các khung được truyền từ một trạm luôn luôn được tách ra bởi ít nhất một khoảng thời gian backoff. Hiệu quả của thủ tục này là khi có nhiều trạm đang trì hoãn và đi vào thủ tục backoff ngẫu nhiên, trong trường hợp đó trạm lựa chọn thời gian backoff nhỏ nhất mà sử dụng thủ tục ngẫu nhiên sẽ chiến thắng xung đột. Hình 1.13. Thủ tục Backoff 1.2.2.5.3. Thiết lập và cài đặt lại NAV Các trạm nhận được một khung hợp lệ sẽ cập nhật NAV của chúng với thông tin nhận được trong trường Duration/ID, nhưng chỉ khi giá trị NAV mới lớn hơn giá trị NAV hiện tại và chỉ khi khung không được gửi tới trạm đang nhận. Các điều kiện thêm vào khác nhau có thể thiết lập hoặc khởi động lại NAV. Khi một NAV xác lập lại, một yêu cầu tầng vật lý khởi động lại sự sẵn sàng đánh giá sẽ được đưa ra. Hình 1.14 cho biết NAV trong các trạm mà có thể nhận được khung RTS, trong khi các trạm khác chỉ có thể nhận được khung CTS, kết quả là thanh NAV thấp hơn như nhìn thấy. 26 Hình 1.14 : RTS/CTS/DATA/ACK và thiết lập NAV Một trạm đang sử dụng thông tin từ một khung RTS gần nhất là cơ sở để cập nhật các thiết lập NAV cho phép thiết lập lại NAV của mình nếu không có dấu hiệu tầng vật lý bắt đầu nhận được phát hiện từ tầng vật lý trong khoảng thời gian một chu kỳ với thời gian bằng (2 x thời gian SIFS) + (thời gian CTS) + (2 x một khe thời gian) được bắt đầu với dấu hiệu tầng vật lý kết thúc nhận tương ứng để phát hiện khung RTS. Thời gian CTS sẽ được tính bằng cách sử dụng chiều dài của khung CTS và tốc độ dữ liệu tại khung RTS đó được sử dụng cho các NAV cập nhật gần nhất đã nhận được. 1.2.2.5.4. Điều khiển kênh SIFS được sử dụng để cung cấp một cơ chế phân phối MSDU hiệu quả. Sau khi có trạm đã tranh chấp được kênh, thì trạm đó sẽ tiếp tục gửi các đoạn cho đến khi hoặc tất cả các đoạn của một MSDU đơn hoặc MMPDU đã được gửi đi, hoặc một tin báo nhận không nhận được, hoặc một trạm bị hạn chế do việc gửi bất kỳ đoạn bổ sung nào đều được định trước bởi thời gian dừng lại ở ranh giới. Nên việc gửi các đoạn bị gián đoạn do một trong các lý do này, sau khi cơ hội tiếp theo để truyền xuất hiện trạm sẽ tiếp tục truyền. Một giải thuật trong đó một trạm quyết định các MSDU nào sẽ được tiếp theo sau khi đã cố gắng truyền không thành công là vượt quá phạm vi của chuẩn này, nhưng bất kỳ một thuật giải nào như vậy sẽ tuân thủ những sự hạn chế do chuẩn này cung cấp. 27 Hình 1.15. Minh họa việc truyền của một đoạn MSDU sử dụng SIFS Khi trạm nguồn truyền một đoạn, nó sẽ giải phóng kênh, rồi ngay lập tức theo dõi kênh bằng một tin báo nhận. Khi trạm đích vừa kết thúc gửi xác nhận, SIFS theo sau tin báo nhận sẽ được giữ lại cho trạm nguồn để tiếp tục (nếu cần thiết) với đoạn khác. Trạm gửi xác nhận sẽ không được truyền trên kênh ngay lập tức theo sau tin báo nhận. Quá trình gửi nhiều đoạn sau khi chắc chắn rằng kênh được định nghĩa như một chùm đoạn. Nếu trạm nguồn nhận được một tin báo nhận nhưng không có đủ thời gian để truyền khung kế tiếp và nhận tin báo nhận do xảy ra trước khi dừng tại ranh giới, trạm nguồn sẽ cho rằng các kênh được bắt đầu tại thời gian dừng kế tiếp. Nếu trạm nguồn không nhận được một khung tin báo nhận, nó sẽ cố gắng truyền lại MPDU lỗi hoặc một MPDU thích hợp khác, sau khi thực hiện thủ tục backoff và quá trình tranh chấp. Sau khi một trạm tranh chấp lấy kênh để truyền lại một đoạn của một MSDU, nó sẽ bắt đầu với đoạn cuối cùng mà không được xác nhận. Trạm đích sẽ nhận các đoạn theo thứ tự (do trạm nguồn gửi chúng theo thứ tự, và chúng được xác nhận riêng biệt). Tuy nhiên, có thể xảy ra, đó là trạm đích có thể nhận được các đoạn lặp lại. Nó sẽ là phản hồi lại trạm nhận để dò tìm và loại bỏ những đoạn lặp. Một trạm sẽ truyền sau SIFS chỉ dưới những điều kiện sau đây trong suốt thời gian một chùm đoạn:  Trạm vừa nhận được một đoạn và yêu cầu xác nhận.  Trạm nguồn nhận được một xác nhận của một đoạn trước, có nhiều đoạn do cùng một MSDU truyền, và có đủ thời gian trước khi dừng lại ranh giới kế tiếp để gửi đoạn tiếp theo và nhận được xác nhận của nó. Các quy tắc sau đây sẽ được áp dụng:  Khi một trạm đã truyền một khung khác với khung ban đầu hay khung 28 ở giữa, trạm đó sẽ không truyền trên kênh theo sau tin báo nhận cho khung đó, không thực hiện thủ tục backoff.  Khi một MSDU đã truyền thành công hoặc tất cả các cố gắng truyền lại đã bị thất bại, và một trạm có một MSDU kế tiếp để truyền, khi đó trạm sẽ thực hiện thủ tục backoff.  Chỉ những đoạn không được xác nhận sẽ được truyền lại. 1.2.2.5.5. Cách sử dụng RTS/CTS với phân đoạn Sau đây là một mô tả về việc sử dụng RTS/CTS cho một đoạn MSDU hay MMPDU. Các khung RTS/CTS định nghĩa khoảng thời gian sau khung và tin báo nhận. Trường Duration/ID trong dữ liệu và các ACK xác định rõ tổng thời gian của đoạn và tin báo nhận kế tiếp. Điều này được minh họa trong hình 1.16. Hình 1.16. RTS/CTS với các MSDU đã phân đoạn Mỗi khung chứa đựng thông tin mà xác định thời gian truyền tiếp theo. Thông tin khoảng thời gian từ các khung RTS sẽ được dùng để cập nhật NAV tiến tới chỉ ra trạng thái bận cho đến khi kết thúc ACK 0. Thông tin khoảng thời gian từ khung CTS cũng sẽ được dùng để cập nhật NAV tiến tới chỉ ra trạng thái bận cho đến khi kết thúc ACK 0. Cả hai khung 0 và ACK 0 sẽ chứa thông tin khoảng thời gian cập nhật NAV để chỉ ra trạng thái bận cho đến khi kết thúc ACK 1. Điều này sẽ được thực hiện bằng cách sử dụng trường Duration/ID trong các khung dữ liệu và ACK. Điều này sẽ tiếp tục cho đến khung cuối cùng, khung này sẽ có khoảng thời gian bằng thời gian một ACK cộng với thời gian một SIFS, và ACK của nó, ACK này sẽ có trường Duration/ID thiết lập bằng 0. Mỗi khung và ACK hành động như một RTS và CTS ảo, cho nên không có các khung RTS/CTS nào cần được tạo ra sau khi 29 RTS/CTS đó bắt đầu chuỗi trao đổi khung thậm chí các khung theo sau mặc dù có thể lớn hơn khi bắt đầu RTS. Tại những trạm sử dụng một tầng vật lý với bước nhảy tần số, khi có một khoảng thời gian không đủ trước khi dừng lại ở ranh giới kế tiếp để truyền khung tiếp theo, một trạm bắt đầu chuỗi trao đổi khung, có thể thiết lập trường Duration/ID trong dữ liệu cuối cùng hoặc khung điều khiển được truyền đi trước khi dừng lại ở ranh giới với một khoảng thời gian ACK cộng với một thời gian SIFS. Trong trường hợp khi một tin báo nhận được gửi đi nhưng không nhận được bởi trạm nguồn, các trạm mà nghe thấy khung, hay ACK, sẽ đánh dấu kênh trong trạng thái bận cho sự trao đổi khung kế tiếp do NAV đang được cập nhật từ những khung này. Đây là trường hợp xấu nhất, và được chỉ ra trong Hình 1.17. Nếu một tin báo nhận không được gửi đi bởi trạm đích, các trạm mà chỉ có thể nghe thấy trạm đích sẽ không cập nhật NAV của chúng và có thể cố gắng truy cập kênh khi NAV chúng cập nhật từ khung nhận được trước đó đạt đến 0. Tất cả các trạm mà nghe thấy nguồn sẽ tự do truy cập kênh sau khi NAV của chúng được cập nhật từ đoạn đang truyền kết thúc. Hình 1.17. RTS/CTS với độ ưu tiên truyền và thiếu báo nhận 1.2.2.5.6. Thủ tục CTS Một trạm có địa chỉ của một khung RTS sẽ truyền một khung CTS sau một chu kỳ SIFS nếu như NAV tại trạm nhận được khung RTS chỉ ra rằng môi trường là rỗi. Nếu như NAV tại trạm nhận được RTS chỉ ra rằng môi trường là không rỗi, tức là trạm sẽ không trả lời với khung RTS. Trường RA 30 của khung CTS sẽ là giá trị thu được từ trường TA của khung RTS, từ đó khung CTS này là một sự đáp lại. Trường Duration/ID trong khung CTS sẽ là trường khoảng thời gian từ khung RTS nhận được, được điều chỉnh bằng sự trừ đi một thời gian SIFS và số lượng micrô-giây được yêu cầu để truyền một khung CTS với tốc độ dữ liệu được dùng cho khung RTS tới khung CTS này là một sự đáp lại. Sau khi truyền một khung RTS, một trạm sẽ chờ trong một khoảng thời gian chờ đợi CTS, bắt đầu xác nhận tầng vật lý kết thúc truyền. Nếu một dấu hiệu tầng vật lý bắt đầu nhận không xuất hiện trong suốt khoảng thời gian chờ đợi CTS, một trạm sẽ kết thúc truyền RTS có lỗi, và trạm này sẽ gọi thủ tục backoff của nó vào lúc hết hạn trong khoảng thời gian chờ đợi CTS. Nếu như một dấu hiệu tầng vật lý bắt đầu nhận không xuất hiện trong suốt khoảng thời gian chờ đợi CTS, một trạm sẽ đợi dấu hiệu tầng vật lý kết thúc nhận tương ứng để quyết định liệu RTS đã truyền thành công hay không. Việc nhận ra giá trị khung CTS được gửi đi bằng cách nhận khung RTS, tương ứng với dấu hiệu tầng vật lý kết thúc nhận này, sẽ được làm sáng tỏ khi phản hồi thành công, cho phép chuỗi khung được tiếp tục. Việc nhận ra bất kỳ điều gì khác, bao gồm bất kỳ giá trị khung nào khác, sẽ được làm sáng tỏ khi không thành công trong việc truyền RTS. Trong trường hợp này, một trạm sẽ gọi thủ tục backoff của nó tại dấu hiệu tầng vật lý kết thúc nhận và có thể xử lý khung đã nhận được. 1.2.2.5.7. Thủ tục ACK Sau khi nhận thành công của một khung thuộc một kiểu mà yêu cầu tin báo nhận với bít ToDS được thiết lập, một AP sẽ tạo ra một khung ACK. Một khung ACK sẽ được truyền bởi trạm đích tức là không phải một AP, bất cứ lúc nào nó nhận thành công một khung unicast thuộc một kiểu mà yêu cầu tin báo nhận, nhưng không phải nếu như nó nhận một khung broadcast hoặc multicast cùng kiểu đó. Sau khi nhận thành công một khung yêu cầu tin báo nhận, truyền khung ACK sẽ bắt đầu sau một chu kỳ SIFS, mà không quan tâm đến trạng thái bận/rỗi của môi trường. Trạm nguồn sẽ chờ đợi trong khoảng thời gian chờ đợi ACK mà không 31 nhận khung ACK trước khi kết luận rằng MPDU bị lỗi. Sau khi đang truyền một MPDU mà yêu cầu một khung ACK lúc trả lời, trạm sẽ chờ trong một khoảng thời gian chờ đợi ACK, bắt đầu xác nhận tầng vật lý kết thúc truyền. Nếu dấu hiệu tầng vật lý bắt đầu nhận không xuất hiện trong suốt quãng thời gian chờ đợi ACK, một trạm kết luận rằng truyền MPDU đã bị lỗi, và trạm này sẽ gọi thủ tục backoff của nó hết hạn trong khoảng thời gian chờ đợi ACK. Nếu một dấu hiệu tầng vật lý bắt đầu nhận xuất hiện trong suốt quãng thời gian chờ đợi ACK, trạm sẽ chờ dấu hiệu tầng vật lý kết thúc nhận tương ứng để xác định khi nào truyền MPDU là thành công. Việc nhận ra khung ACK hợp lệ được gửi đi bằng sự nhận của MPDU yêu cầu tin báo nhận, tương ứng với dấu hiệu tầng vật lý kết thúc nhận này, sẽ được hiểu như một xác nhận thành công, cho phép các chuỗi khung tiếp tục, hoặc kết thúc mà không cần yêu cầu lại, tương ứng với chuỗi khung đặc biệt đang được thi hành. Sự nhận ra bất kỳ điều gì, bao gồm bất kỳ khung hợp lệ nào khác, sẽ được hiểu như lỗi của việc truyền MPDU. Trong trường hợp này, một trạm sẽ gọi thủ tục backoff của nó tại dấu hiệu tầng vật lý kết thúc nhận và có thể xử lý khung vừa nhận. Một trường hợp ngoại lệ đó là nhận ra khung không hợp lệ được gửi đi bởi bên nhận một khung thăm dò PS cũng sẽ được chấp nhận như tin báo nhận thành công của khung thăm dò PS. 1.2.2.5.8. Những quan hệ tính toán thời gian DCF Mối liên hệ giữa đặc điểm kỹ thuật IFS được định nghĩa như khoảng thời gian trống trên môi trường. Các thuộc tính kết hợp với nhau được cung cấp bởi tầng vật lý đặc trưng. Toàn bộ sự tính toán thời gian mà được tham chiếu từ khi kết thúc truyền, sẽ được tham chiếu từ khi kết thúc biểu tượng cuối cùng của một khung trên môi trường. Bắt đầu truyền sẽ rút về ký tự đầu tiên của khung tiếp theo trên môi trường. 32 Hình 1.18. Các mối quan hệ định thời DCF  D1 = Độ trễ nhận tần số sóng vô tuyến (RxRFDelay) + Độ trễ nhận giao thức hội tụ tầng vật lý (RxPLCPDelay)  D2 = D1 + Thời gian truyền trong không gian  Rx/Tx = Thời gian xoay quanh truyền và nhận (được bắt đầu với một yêu cầu tầng vật lý bắt đầu truyền)  M1 = M2 = Độ trễ xử lý tầng MAC (MACProDelay)  CCAdel = thời gian CCA – D1 Thời gian SIFS và khe thời gian (Slot Time) là cố định cho mỗi tầng vật lý.  Thời gian SIFS là : D1 + M1 + Rx/Tx  Slot Time là : Thời gian CCA + Rx/Tx + Thời gian xoay quanh truyền và nhận + M1 PIFS và DIFS nhận được từ các phương trình sau: PIFS = SIFS + Slot Time DIFS = SIFS + 2 x Slot Time EIFS nhận được từ SIFS và DIFS và độ dài về thời gian nó lấy để truyền một khung điều khiển ACK với tốc độ 1 Mbit/s bằng phương trình sau: EIFS = SIFS +(8 x ACKSize) +độ dài Preamble +độ dài đoạn đầu PLCP + DIFS 33 với ACKSize là chiều dài, trong các byte, của một khung ACK và ((8 x ACKSize) +độ dài Preamble + độ dài đoạn đầu PLCP) được diễn tả bằng micro giây yêu cầu để truyền tại tầng vật lý có tốc độ bắt buộc thấp nhất. Hình 1.18 minh họa mối liên hệ giữa SIFS, PIFS, và DIFS khi chúng đều đặn trong môi trường và các ranh giới MAC khác nhau. TxSIFS, TxPIFS, và TxDIFS. Các khe ranh giới này định nghĩa khi việc truyền sẽ tuỳ thuộc vào bởi MAC để đáp ứng các tính toán về thời gian IFS khác nhau trên môi trường, sau khi phát hiện kế tiếp về kết quả của khe thời gian liền trước CCA. Các phương trình sau định nghĩa các ranh giới khe MAC, sử dụng các thuộc tính được cung cấp bởi tầng vật lý, khi chúng bù cho việc thay đổi tính toán thời gian thi hành. Việc bắt đầu tham chiếu các khe ranh giới này như tới điểm kết thúc của ký tự cuối cùng của khung liền trước đó trên môi trường. TxSIFS = SIFS – Thời gian xoay quanh truyền và nhận TxPIFS = TxSIFS + Slot Time TxDIFS = TxSIFS + 2 x Slot Time. 34 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 2.1. Vấn đề không công bằng luồng trong các mạng Ad Hoc không dây Mạng Ad Hoc không dây như một hình mẫu của cấu hình mạng trong tương lai mà không cần bất cứ cơ sở hạ tầng nào như các bộ định tuyến và các trạm gốc. Việc sử dụng các thiết bị LAN không dây theo tiêu chuẩn IEEE 802.11 phổ biến trong các loại mạng khác nhau bao gồm cả mạng Ad Hoc, các mạng cảm biến, các mạng cá nhân, và các mạng mà nối liền với các trạm gốc của hệ thống di động tập trung thế hệ thứ tư. Để hiểu rõ về các mạng Ad Hoc, cần thiết phải kiểm soát cường độ QoS (Quality of Service) dưới dạng công bằng, ổn định, hiệu suất truyền.... Trong nhiều tham số QoS, công bằng cho mỗi luồng là một vấn đề quan trọng và khó giải quyết trong các mạng Ad Hoc vì nó được phân quyền một cách tự nhiên. Trong những mạng Ad Hoc không dây, vấn đề chính làm cho sự công bằng cho mỗi luồng trở nên xấu hơn tồn tại trên tầng liên kết và tầng MAC. Vì vậy sự không công bằng cho mỗi luồng trong các mạng Ad Hoc không dây có thể tách ra theo hai nhóm: không công bằng bởi tầng liên kết và không công bằng bởi tầng MAC. 2.1.1. Không cân bằng luồng gây ra bởi tầng liên kết Khi mạng Ad Hoc không dây chỉ bao gồm các nút di động, thì truyền thông giữa hai nút mà nút này không nằm trong dải truyền của nút kia đạt được bằng cách sử dụng nút khác như bước nhảy. Vì vậy, một nút phải cung cấp dịch vụ chuyển tiếp tới vài luồng và/hoặc tạo ra vài luồng của chính mình với mục đích là vùng đệm của nó được chia sẻ bởi nhiều luồng. Rõ ràng, nếu như vùng đệm không được chia sẻ công bằng, nó có thể dẫn đến sự không công bằng cho mỗi luồng. Đây là một vấn đề công bằng gây ra bởi tầng liên kết, vì vậy nó cần được giải quyết bởi một cơ chế dựa trên cơ sở tầng liên kết. Điều này được minh hoạ trong hình 2.1 thông qua một hình trạng mạng đơn giản. 35 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 Trong đó có hai luồng (Flow1, Flow2) được thiết lập từ nút S1 đến S3 và từ S2 đến S3. Khi mà S1 và S3 không nằm trong cùng dải truyền dẫn với nhau, S2 được sử dụng như một nút nhảy cho Flow1. Vì vậy, vùng đệm tại S2 được chia sẻ bởi cả hai luồng. Ở đây, chúng ta xem xét trường hợp S1 và S2 tạo ra lưu lượng theo cùng một tốc độ G và băng thông trung bình cực đại B. Đặt B12 và B23 tương ứng với băng thông của những kết nối từ S1 đến S2 và từ S2 đến S3, theo thứ tự được định sẵn. Hơn nữa, trong điều kiện mà chỉ có một hàng đợi FIFO (First In, First Out) được sử dụng trong tầng liên kết tại S2, gọi QFlow1:QFlow2 tương ứng với tỷ lệ phân chia vùng đệm của S2 cho Flow1 và Flow2. Để thấy được sự công bằng cho mỗi luồng, chúng ta tính riêng biệt từng thông lượng: Th(Flow1) and Th(Flow2). Để đơn giản hóa trong việc tính toán, chúng ta giả thiết rằng sự mất mát gói tin không xuất hiện trên những kết nối không dây. Đầu tiên chúng ta xem xét trường hợp khi G < 2 B . Trong trường hợp này, B12 cân bằng với G, và như vậy tỷ lệ phân chia vùng đệm của S2 là QFlow1:QFlow2 = G:G =1:1 (1) Phương trình (1) cho thấy rằng khi mà G nhỏ hơn 2 B , các luồng chia sẻ vùng đệm tại S2 một cách công bằng. Băng thông của mối kết nối từ S2 tới S3 là B23 = B – B12 = B – G, như vậy giá trị băng thông cực đại đối với Flow1 và Flow2 trên mối kết nối từ S2 đến S3 là 2 23B = 2 G)-(B . Điều đó được sinh ra từ (1) mà        ) 2 B <G 2 G)-(B ( 2 G)-(B= (2) ) 2 G)-(B <G ( G = nÕu nÕu Th(Flow2) = Th(Flow1) Th(Flow2) = Th(Flow1) 36 Phương trình bậc cao ở trên cho thấy rằng khi G nhỏ hơn 2 23B , thông lượng của mỗi luồng cân bằng với G. Phương trình dưới cho thấy rằng khi G lớn hơn hoặc bằng 2 23B , thông lượng của mỗi luồng sẽ bằng nhau về giá trị băng thông cực đại trên mỗi kết nối từ S2 đến S3 đối với mỗi luồng. Bây giờ, chúng ta xem xét trường hợp khi G ≥ 2 B . Khi mô hình bao gồm chỉ hai nút gửi (S1 và S2), và DCF cung cấp sự công bằng cho mỗi nút, B12 cân bằng với B/2. Như vậy, tỉ lệ phân chia vùng đệm của S2 là QFlow1:QFlow2 = 2 B :G (3) Từ (3), thông lượng cho Flow1 và Flow2 trên liên kết từ S2 tới S3 là 232/ 2/ B BG B   và 232/ B BG G   , tương ứng. Khi B23= B – B12= 2 B , thông lượng cho mỗi luồng là:              ) 2 BG ( 2GB BG = (4) ) 2 BG ( 2G)2(B 2B = nÕu nÕu Th(Flow2) Th(Flow1) Từ (2) và (4), cho thấy rằng sự công bằng cho mỗi luồng giảm sút một cách đáng kể với sự gia tăng của G. Khi vấn đề công bằng này gây ra bởi tầng liên kết (bộ đệm không được chia sẻ công bằng bởi các luồng), nó có thể được giải quyết bởi cơ chế dựa trên cơ sở tầng liên kết. 2.1.2. Không cân bằng luồng gây ra bởi tầng MAC Khi các nút di động chia sẻ môi trường không dây trong các mạng Ad Hoc, các nút mà nằm trong các dải truyền dẫn khác nhau sẽ không truyền các gói tin vào cùng một thời gian. Nếu chúng làm điều đó, sự thất lạc gói tin sẽ xảy ra, gây ra không thực hiện được quá trình truyền. Vấn đề này được giảm bớt đáng kể bởi cơ chế truy cập kênh DCF. Tuy nhiên, DCF cung cấp việc truy cập kênh không công bằng giữa các luồng, đặc biệt nếu ở đó có sự khác nhau về số lượng các luồng tại các nút di động mà nằm trong phạm vi cùng 37 một dải truyền. Đây là vấn đề công bằng gây ra bởi giao thức MAC, và nó cần được giải quyết bởi cơ chế dựa trên cơ sở tầng MAC, ở đó cung cấp sự truy cập kênh công bằng cho mỗi luồng. Xét hình trạng mạng đơn giản được minh hoạ trong hình 2.2 sau đây. S2 S4 S3 S0 S1 Flow 1 Flow 2 Flow 0 Hình 2.2. Mô hình sự không công bằng xuất hiện tại tầng MAC Trong đó S2 là một nút gửi của hai luồng (Flow1, Flow2), và S0 là một nút gửi của một luồng (Flow0). S0 và S2 nằm trong các dải truyền dẫn khác nhau. Cho G đại diện cho tỷ lệ cung cấp của các luồng riêng lẻ và B đại diện cho băng thông trung bình cực đại. Nếu chúng ta giả thiết rằng vùng đệm được phân chia công bằng đối với Flow1 và Flow2 trên tầng liên kết của S2, hai luồng đạt được sự cân bằng về thông lượng (đặt Th1 đại diện cho chúng). Khi 802.11 DCF MAC đã cung cấp sự phân chia băng thông công bằng cho mỗi nút, những thông lượng đạt được bởi mỗi luồng là:            ) 2 BG ( 4 B = , 2 B = (5) ) 2 B<G 3 B( 2 G)-(B = G, = ) 3 B<G ( G = nÕu nÕu nÕu Th1Th0 Th1Th0 Th1 = Th0 Ở đây Th0 đại diện cho thông lượng của Flow0. Phương trình đầu tiên cho thấy khi G nhỏ hơn 3 B , băng thông trung bình đủ bảo đảm cho mỗi luồng, và như vậy tất cả các luồng đều đạt được thông lượng bằng G. Phương trình cuối mô tả trường hợp cả hai nút gửi (S0 và S2) yêu cầu băng thông lớn hơn 38 hoặc bằng với 2 B . Trong trường hợp này, khi cơ chế MAC gốc là công bằng cho mỗi nút, cả S0 và S2 đều được gán băng thông bằng 2 B . Hình 2.3. Mô hình truy nhập kênh của cơ chế gốc Trong hình thể hiện rằng S0 và S2 truy cập kênh lần lượt và gửi một gói tin. Tuy nhiên, khi có hai luồng từ S2 nhưng chỉ có một luồng từ S0, tỷ lệ băng thông phân chia đối với mỗi luồng là Flow0:Flow1:Flow2 = 2:1:1. Như vậy, thông lượng đạt được bởi mỗi luồng theo mối quan hệ dưới đây. Th(Flow0) = Th(Flow1) + Th(Flow2) Kết quả là không công bằng cho mỗi luồng. Cuối cùng, phương trình ở giữa (5) cho thấy trong trường hợp ở đây S0 yêu cầu băng thông bằng G nhưng nó lại nhỏ hơn 2 B . Trong trường hợp này, S0 được yêu cầu gán băng thông bằng G, và băng thông còn lại (B – G) được cung cấp cho Flow1 và Flow2 tại S2. Từ (5), cho thấy sự không công bằng cho mỗi luồng trong hình 2.2. Khi vấn đề công bằng gây ra bởi tầng MAC, nó có thể được giải quyết bởi cơ chế dựa trên tầng MAC. 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 2.2.1. Mô hình lập lịch tập trung Mô hình lập lịch tập trung [7] đã đề xuất ý tưởng về một cơ chế làm nổi bật tiện ích kênh cực đại với mục đích cao nhất là đạt được công bằng và phân bổ băng thông của kênh tối đa. Tuy nhiên, cả hai tiêu chí có thể đưa đến tiềm năng xung đột trong một hình trạng chung của mạng không dây đa chặng nơi Flow0 Flow0 Trì hoãn truy cập Trì hoãn truy cập S0 Trì hoãn truy cập S2 Flow1 Flow2 Flow1 Trì hoãn truy cập Flow0 Trì hoãn truy cập Thời gian Thời gian 39 mà một kênh logic duy nhất được chia sẻ giữa đa luồng tranh chấp và khả năng sử dụng lại không gian của băng thông kênh là có thể xảy ra. Trong mô hình lập lịch các gói tin mà có các địa chỉ xung đột này, các kết quả chính đạt được bao gồm: một mô hình dịch vụ hai tầng mà cung cấp một sự phân chia băng thông kênh " công bằng " tối thiểu cho mỗi luồng gói tin và đồng thời sử dụng lại không gian băng thông cực đại, một giải thuật lập lịch gói tập trung lý tưởng mà được thực hiện mô hình dịch vụ ở trên, và một cơ chế tranh dành kênh dựa vào backoff được phân bố thực tế mà xấp xỉ dịch vụ lý tưởng bên trong khung của giao thức CSMA/ CA Tuy nhiên, một khi áp dụng kiến thức về topo mạng và luồng thông tin tại bộ lập lịch, giải thuật không còn phù hợp để sử dụng trong các mạng Ad Hoc nơi mà không tồn tại cơ sở hạ tầng tập trung. 2.2.1.1 Mô hình mạng và các vấn đề liên quan đến sự công bằng 2.2.1.1.1. Mô hình mạng Một mạng không dây đa chặng chuyển mạch gói trong môi trường không dây được chia sẻ giữa nhiều người sử dụng đang tranh chấp được xem xét, ví dụ, một kênh vật lý đơn với dung lượng C có thể sử dụng cho việc truyền không dây. Quá trình truyền được quảng bá cục bộ và chỉ nhận trong phạm vi dải truyền của một nguồn gửi có thể nhận được các gói tin của nó. Mỗi luồng gói tin tại tầng liên kết là một chuỗi các gói tin được truyền từ nguồn tới đích, nơi mà nguồn và đích là các miền lân cận. Hai luồng được định nghĩa như các luồng đang tranh chấp nếu cả nguồn gửi hay nguồn nhận của một luồng là trong phạm vị dải truyền của nguồn gửi hoặc nguồn nhận của luồng khác. Có ba giả định được đưa ra : miền lân cận là một thuộc tính giao hoán và từ đây tranh chấp luồng cũng có tính giao hoán, một nút không thể truyền và nhận các gói tin đồng thời, và một xung đột xảy ra khi một nguồn nhận đang nhận trong dải của hai nút đang truyền đồng thời, như vậy không thể dễ dàng nhận tín hiệu từ cả hai bên. 2.2.1.1.2. Vấn đề tranh chấp phụ thuộc vị trí và sử dụng lại không gian Vùng để truyền không dây hàm ý rằng có các xung đột, và kể từ đây tranh chấp để chia sẻ môi trường, sẽ phụ thuộc vào vị trí. Bản chất đặc trưng 40 vị trí tranh chấp, được kết hợp với bản chất đa chặng trong mạng, cho phép sử dụng lại không gian kênh. Đặc biệt, bất cứ hai luồng nào mà không gây nhiễu với mỗi luồng khác đều có khả năng truyền các gói tin dữ liệu đồng thời qua kênh vật lý. Sự lựa chọn các máy truyền đồng thời như vậy xác định toàn bộ sự sử dụng kênh, kể từ đây quy tắc lập lịch gói tin cần phải thực hiện sự lựa chọn đúng đắn trong quá trình truyền đồng thời khi tính đến việc xem xét sự công bằng ngang qua các luồng. Trong một mạng có dây và mạng tế bào gói, các gói tin được lập lịch độc lập tại mỗi liên kết, và bộ lập lịch tại một liên kết chỉ cần phải xem xét các luồng đang tranh chấp đối với liên kết đó. Sự công bằng fluid được định nghĩa cho các mạng như vậy, về bản chất, một thuộc tính cục bộ cho các luồng đang truyền trên mỗi liên kết và thuật toán lập lịch gói tin để đạt được mô hình công bằng fluid, chẳng hạn, Weighted Fair Queueing (hàng đợi công bằng có trọng số), bảo đảm sự công bằng cục bộ trong miền thời gian giữa các luồng đang tranh chấp mà chia sẻ một liên kết đơn. Trong một mạng không dây đa chặng chia sẻ môi trường, sự công bằng không thể được định nghĩa chỉ riêng đối với các luồng “cục bộ”, bởi vì khả năng sử dụng lại không gian kênh, và sự ràng buộc phụ thuộc vào vị trí trong sự lựa chọn các luồng để truyền đồng thời. Như vậy, sự công bằng phải được định nghĩa với các luồng đang tranh chấp trong cả hai miền thời gian và miền không gian. 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 Trong một liên kết có dây hay một tế bào trong một mạng tế bào gói, một luồng nhiều nhất có thể truyền vào bất cứ thời gian nào, và sự lập lịch các gói tin ngang qua các liên kết/các tế bào khác nhau là độc lập. Trong môi trường đích, nhiều luồng có thể truyền đồng thời, nhưng việc truyền một luồng trong một miền có ảnh hưởng trên các luồng khác có thể truyền trong phần còn lại của mạng. Tính chất “ toàn bộ” của sự lập lịch gói tin trong các mạng không dây chia sẻ kênh đa bước nhảy dẫn đến xung đột giữa việc đạt được sự công bằng và tăng tối đa sử dụng toàn bộ kênh. 2.2.1.1.4. Giải pháp không gian Mục đích của công việc này là gán địa chỉ các thoả hiệp giữa việc đạt được sự công bằng và tăng tối đa sử dụng kênh. Một giới hạn là cách tiếp cận 41 mà đạt được một số khái niệm xác định trước về sự công bằng không có việc lấy sử dụng kênh để tính toán. Tại một giới hạn khác là cách tiếp cận mà luôn luôn cố gắng lập lịch số lượng lớn nhất của các luồng được dự trữ không xung đột trong bất kỳ thời gian nào, bằng cách này làm tăng tối đa sử dụng toàn bộ kênh khi có khả năng hạn chế một số luồng. Trong việc này, vị trí ở giữa được xem xét và bắt buộc một khái niệm cơ sở về sự công bằng mà đảm bảo rằng mỗi luồng nhận tối thiểu sự phân bố kênh tuỳ thuộc vào sự ràng buộc này, được tìm kiếm để làm tăng tối đa sự sử dụng toàn bộ kênh. Một vấn đề cần quan tâm là sử dụng kênh cải thiện khi mô hình công bằng trở nên kém đi như thế nào. Điều này, phụ thuộc vào những yêu cầu của hệ thống, người quản trị mạng có khả năng lựa chọn một điểm đặc biệt trong giải pháp không gian. Đặc biệt, hai điểm trong giải pháp không gian được xem xét là:  Một luồng i với trọng số ri nhận cận dưới trên sự phân bố kênh của   )1(tBj j i r r C(t1,t2) trên một chu kỳ thời gian rất nhỏ (t1,t2), ở đó B(t) là tập hợp các luồng được dự trữ trong toàn bộ mạng vào thời điểm t. Với giả thuyết là cận dưới này ở trên sự phân phối kênh, phương pháp lập lịch được dùng để tăng tối đa sự phân phối toàn bộ kênh. Mô hình công bằng này là toàn bộ và không phụ thuộc cấu trúc liên kết theo ý nghĩa đó nó cho rằng trong trường hợp xấu nhất tất cả các luồng đang tranh chấp lẫn nhau.  2. Một luồng i với trọng số ri nhận cận dưới trên sự phân bố kênh của   )1(. tBj j i rk r C(t1,t2) trên một chu kỳ thời gian rất nhỏ (t1,t2), ở đó B(i,t) là tập hợp các luồng được dự trữ trong phạm vi khoảng cách hai bước nhảy (trong đồ thị nút) của luồng i tại thời điểm t và k là một hằng số. Với giải thuyết là cận dưới này ở trên sự phân phối kênh, quy tắc lập lịch được dùng để tăng tối đa sự phân phối toàn bộ kênh. Mô hình công bằng này là toàn bộ và phụ thuộc cấu trúc liên kết bởi vì nó cung cấp một cận dưới trên sự phân phối kênh đối với sự tranh chấp hiện tại trong một vị trí của luồng. Cách tiếp cận đầu tiên cung cấp sự công bằng kém hơn mô hình thứ hai, yêu cầu toàn bộ thông tin luồng được dự trữ để hoàn tất lập lịch, nhưng cung 42 cấp theo cách suy diễn trường hợp xấu nhất các ranh giới trên sự phân phối kênh là không làm thay đổi về cấu trúc liên kết mạng và kết quả là có thể cao hơn sự sử dụng toàn bộ kênh. 2.2.1.2. Mô hình lập lịch gói tin 2.2.1.2.1. Mô hình fluid và đồ thị tranh chấp luồng Trong mô hình fluid này, độ chi tiết của sự chia sẻ kênh là một bít, và mỗi luồng f được gán một trọng số rf. Mục đích là để gán một sự phân bố kênh tối thiểu tới mỗi luồng tương ứng với trọng số của nó, và tuỳ thuộc vào ràng buộc này, làm tăng tối đa sự sử dụng toàn bộ kênh. Bước đầu tiên trong mô hình là để chuyển đổi các luồng trong một cấu trúc liên kết mạng chung thành ra một đồ thị tranh chấp luồng, mô tả quan hệ tranh chấp về khoảng thời gian trống giữa các luồng đang truyền. Trong một đồ thị tranh chấp luồng, mỗi đỉnh đại diện cho một luồng được dự trữ, và một cạnh giữa hai đỉnh biểu thị rằng hai luồng này là đang tranh chấp. Các đỉnh mà không được kết nối biểu thị các luồng có thể truyền đồng thời. Như vậy, một tập hợp độc lập trong đồ thị tranh chấp luồng biểu thị một tập hợp truyền không xung đột. Việc xem xét đồ thị tranh chấp luồng cung cấp một sự hiểu biết sâu sắc về việc tại sao phải lập lịch công bằng trong miền đích là một vấn đề khó khăn duy nhất. Các đồ thị con không liên thông trong đồ thị tranh chấp luồng có thể được lập lịch độc lập. Trong một mạng có dây, các luồng tại tầng liên kết mà chia sẻ cùng liên kết đầu ra tạo thành một nhóm và mạng được biểu diễn bằng một tập hợp của các nhóm rời nhau, như vậy mỗi nhóm có thể được lập lịch độc lập và có nhiều hơn một nguồn gửi trong một nhóm tại một thời điểm. Trong một mạng không dây đa chặng có kênh được chia sẻ, nhiệm vụ là nhận ra một chuỗi thuộc các tập hợp độc lập (ví dụ các nguồn gửi đồng thời) tuỳ thuộc vào những ràng buộc cấu trúc liên kết của đồ thị, sao cho mỗi luồng nhận một sự đại diện tối thiểu trong chuỗi các tập hợp độc lập và tại cùng một thời điểm, toàn bộ các yếu tố của các tập hợp này được tăng tối đa. Phương pháp để đạt được mô hình công bằng bằng việc lựa chọn một tập hợp các luồng để truyền trong một giai đoạn hàng đợi công bằng, và sau đó 43 tăng tối đa sử dụng kênh bằng việc lựa chọn các luồng thêm vào để truyền trong một giai đoạn tập hợp độc lập cực đại tuỳ thuộc vào việc lựa chọn các luồng trong một giai đoạn hàng đợi công bằng. Những chi tiết chính xác của thuật toán trong hai giai đoạn quyết định liệu mô hình công bằng có là toàn bộ hay cục bộ không. 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 Hàng đợi công bằng fluid bắt buộc rằng khi một tập hợp những luồng F chia sẻ một kênh, một luồng i với trọng số ri nhận một sự phân phối kênh của C   )(tBj j i r r t qua bất cứ cửa sổ thời gian nhỏ t , ở đó C là dung lượng kênh và B(t) là tập hợp của các luồng chưa thực hiện tại thời gian t. Một vài thuật toán lập lịch đóng gói khác nhau tồn tại gần giống với mô hình hàng đợi công bằng fluid. Một biến thể lai của Start time Fair Queueing (STFQ) và Worst-case Fair Weighted Fair Queueing (WF2Q), sử dụng khi điểm xuất phát quy tắc lập lịch trong khung lập lịch lý tưởng hoá. Mỗi luồng có một hàng đợi với các gói tin của nó. Các gói tin trong một luồng thoả mãn theo thứ tự FIFO. Mỗi gói tin có hai thẻ, một thẻ bắt đầu và một thẻ kết thúc. Thẻ bắt đầu của nth gói tin của luồng i được chỉ rõ như sau: si,n=max{v(ti,n),fi,n-1} và thẻ kết thúc của n th gói tin của luồng i được chỉ rõ như sau: fi,n=si,n + L/ri ở đó si,n và fi,n biểu thị thẻ bắt đầu và thẻ kết thúc, v(t) là thời gian ảo tại thời điểm t, ti,n biểu thị thời gian đến của gói tin, và L là kích thước gói tin cố định. Thời gian ảo v(t) tại thời điểm t là tập hợp thẻ bắt đầu của gói tin hiện tại đang được truyền trên kênh. Sau khi truyền một gói tin, gói tin tiếp theo truyền được lựa chọn theo thuật toán sau đây.  Trong số tất cả các gói tin mà có thẻ bắt đầu không lớn hơn v(t) + L, gói tin với thẻ kết thúc nhỏ nhất được lựa chọn. 44  Nếu như không có gói tin như vậy, thì gói tin với thẻ bắt đầu nhỏ nhất được lựa chọn. Sự ràng buộc là không được thực hiện tuỳ tiện. Bây giờ trình bày các thuật toán lập lịch gói tin lý tưởng để đạt được các mô hình công bằng toàn bộ và cục bộ tương ứng. Nhắc lại trong mô hình công bằng toàn bộ, một luồng chưa thực hiện i nhận một sự phân phối kênh ít nhất C   )(tBj j i r r t trong thời gian (t, t + t ), ở đó B(t) là tập hợp của tất cả các luồng được dự trữ trong mạng. Thuộc tính công bằng này đồng nhất với một xấp xỉ bằng thuật toán hàng đợi công bằng đóng gói ở trên. Như vậy, sử dụng thuật toán này để cung cấp một sự phân phối “cơ sở”, và tuỳ thuộc vào sự phân phối này, tìm kiếm để tăng tối đa sử dụng lại toàn bộ kênh theo thuật toán sau đây: 1. Lựa chọn phần đầu dòng gói tin của luồng i* theo thuật toán hàng đợi công bằng đóng gói được mô tả ở trên. 2. Lựa chọn tập hợp độc lập cực đại Si* trong G – N[i*], ở đó N[i] biểu thị miền lân cận đóng của nút i trong đồ thị tranh chấp luồng. 3. Lập lịch các gói tin để truyền trong {i* } U Si*. Gia tăng thẻ bắt đầu và thẻ kết thúc của luồng i*, nhưng không thay cho bất cứ luồng nào trong Si. Thực tế rằng các thẻ không được gia tăng đối với các luồng trong Si* cho phép bộ lập lịch đạt được sử dụng lại kênh bổ sung tối đa có thể dành để phân phối cho i* “độc lập”, ví dụ các luồng mà nhận phân phối kênh bổ sung không chịu tải cho nó bằng việc tăng dần các thẻ của chúng. Nhắc lại rằng trong mô hình công bằng cục bộ, một luồng được dự trữ i nhận một sự phân phối kênh ít nhất C   )(tBj j i r r t trong thời gian (t, t + t ), ở đó B(t) là tập hợp của tất cả các luồng được dự trữ trong miền lân cận đóng của nó. Ngược lại trong mô hình công bằng toàn bộ, đạt được công bằng cục bộ sử dụng thuật toán hàng đợi công bằng đóng gói là ít thay đổi hơn, và yêu 45 cầu sự thay đổi sau đây: Giả sử D là một tập hợp “cơ sở” của các luồng được định nghĩa ở dưới; thời gian ảo v(t) là tập hợp tối đa các thẻ bắt đầu của phần đầu các gói tin thuộc các luồng trong D. Với thay đổi thuật toán hàng đợi công bằng đóng gói này, bây giờ định nghĩa thuật toán để đạt được mô hình công bằng cục bộ như sau. Sau khi truyền một gói tin 1. Thiết lập D tiến tới NULL. Đối với mỗi luồng, nếu như thẻ bắt đầu của phần đầu gói tin trong một luồng không lớn hơn v(t)+L, thì thiết lập trạng thái của luồng là tranh chấp, nếu không thiết lập trạng thái của luồng là không tranh chấp. 2. Nếu không có luồng nào trong trạng thái tranh chấp, thì thêm vào một luồng với thẻ bắt đầu cực tiểu tiến tới D và bỏ qua bước tiếp theo. Mặt khác, khi có các luồng trong trạng thái tranh chấp, lựa chọn một luồng f với thẻ kết thúc cực tiểu của phần đầu dòng gói tin và thêm vào f để thiết lập D. Thiết lập tất cả các luồng trong miền lân cận đóng của f, N[f], tiến tới không tranh chấp. 3. Cập nhật thời gian ảo v(t) để thẻ bắt đầu tăng tối đa của phần đầu dòng các gói tin giữa các luồng trong D. Cập nhật thẻ bắt đầu và thẻ kết thúc của các luồng trong D. 4. Lựa chọn tập hợp độc lập cực đại S trong đồ thị G - N[D]. 5. Lập lịch các luồng trong S  D để truyền. Không làm gia tăng các thẻ bắt đầu và thẻ kết thúc của các luồng trong S. Tập hợp D bao gồm các luồng mà nhận sự phân bố kênh như một kết quả của thuộc tính công bằng cục bộ, khi tập hợp S bao gồm các luồng mà nhận sự phân bố kênh bổ sung để tăng tối đa sử dụng toàn bộ kênh. 2.2.1.2.3 Các hàng đợi khe và các hàng đợi gói tin Trong các thuật toán lập lịch được lý tưởng hoá, các thẻ bắt đầu và kết thúc được cập nhật khi một luồng nhận sự phân bố kênh như một phần “chia sẻ công bằng” của nó, nhưng không là một phần của sự phân bố kênh được thêm vào để làm tăng tối đa sử dụng. Để phù hợp với lựa chọn cập nhật các 46 thẻ này, “các khe” được tách riêng ra, là đơn vị của sự phân bố kênh, từ “các gói tin”, đơn vị của quá trình truyền. Một luồng bao gồm hai hàng đợi, một hàng đợi khe và một hàng đợi gói tin. Các thẻ bắt đầu và kết thúc được liên kết với các khe nhưng không phải với các gói tin. Khi một gói tin đến với một luồng, nó được thêm vào hàng đợi gói tin, và một khe mới được thêm vào hàng đợi khe. Tương ứng các thẻ bắt đầu và kết thúc được gán cho một khe mới. Nếu một luồng nhận dịch vụ thông qua giai đoạn hàng đợi đang công bằng, thì nó truyền phần đầu dòng gói tin từ hàng đợi gói tin và xoá phần đầu dòng khe từ hàng đợi khe. Nếu nó nhận dịch vụ thông qua giai đoạn tập hợp độc lập cực đại, nó truyền một gói tin từ hàng đợi gói tin, nhưng cho phép hàng đợi khe không bị thay đổi. Khi tất cả các gói tin đều có kích thước cố định, việc tách hàng đợi khe và hàng đợi gói tin dễ dàng được hoàn thành. Đối với các gói tin có độ dài thay đổi, nguyên tắc tách làm việc cũng như vậy, nhưng phức tạp hơn. 2.2.2. Cơ chế phối hợp hàng đợi cho mỗi luồng Cơ chế phối hợp hàng đợi cho mỗi luồng [8] trong tầng liên kết và tầng MAC, để cải thiện sự công bằng cho mỗi luồng và tiện ích chung. Tuy nhiên, hành động này chỉ tập trung trong trường hợp nơi đó không công bằng luồng gây ra bởi tầng liên kết. Bởi vậy, các tác động của cơ chế này phụ thuộc nhiều vào tôpô mạng. Theo cơ chế này một nút sử dụng trong một mạng đa chặng phải truyền cả lưu lượng chuyển tiếp và lưu lượng dữ liệu của riêng nó. Vì vậy, ngoài tranh chấp với các nút khác vì có cùng nút đích, có một tranh chấp chắc chắn xảy ra giữa lưu lượng dữ liệu chuyển tiếp và của chính nó. Tranh chấp này không xuất hiện ở trong những vòng lặp cục bộ không dây cố định hay các mạng LAN không dây trong chế độ cơ sở hạ tầng nơi mà các nút sử dụng luôn luôn bằng khoảng cách một bước nhảy từ một trạm cơ sở hoặc một điểm truy nhập. Để rõ ràng, một mạng không dây đa chặng đơn giản với bốn nút như trình bày trong hình 2.4 được sử dụng để phân tích các giải pháp mà cơ chế phối hợp hàng đợi cho mỗi luồng đưa ra. 47 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 Với giả thiết rằng tất cả các luồng lưu lượng dữ liệu sẽ theo một hướng duy nhất về phía gateway (GW). Mỗi nút trong hình 2.4 có thể được mô hình như một thiết bị định tuyến không dây với hàng đợi tầng mạng và hàng đợi tầng MAC như trình bày trong hình 2.5. 2.2.2.1. Cô lập lưu lượng dữ liệu nguồn Việc sử dụng sự phối hợp hàng đợi mặc định trong phần lớn các thiết bị định tuyến, mỗi nút trong hình 2.4 có thể được mô hình như trình bày trong hình 2.5(a) (ví dụ, chỉ duy nhất một hàng đợi tầng mạng cung cấp cả hai luồng lưu lượng dữ liệu nguồn và lưu lượng dữ liệu chuyển tiếp). Việc giả thiết rằng hình 2.5 (a) trình bày các hàng đợi tầng mạng và MAC của nút 1 trong hình 2.4, f1 là luồng lưu lượng dữ liệu nguồn và f2, f3 và f4 là được chuyển tiếp. Tầng MAC cơ bản trình bày trong hình 2.5(a)-(d) là một mô hình phổ biến của chuẩn IEEE 802.11 như tầng MAC. Trong một mô hình như vậy, QoS không được hỗ trợ, nhưng sự công bằng tầng MAC tốt hơn được cung cấp. Với cơ chế hàng đợi cơ bản trong hình 2.5(a), nó làm sáng tỏ rằng luồng lưu lượng dữ liệu f1 sẽ nhận nhiều băng thông hơn và cuối cùng những luồng khác bị thiếu do tràn bộ nhớ. Từ đó vấn đề này là nguồn gốc của sự kiện mà cả lưu lượng chuyển tiếp và lưu lượng dữ liệu nguồn chia sẻ chung một hàng đợi, giải pháp đầu tiên mà đi đến một ý kiến là sử dụng các hàng đợi khác nhau cho chuyển tiếp và cho lưu lượng dữ liệu nguồn và điều khiển chúng theo kiểu round-robin. Sự phối hợp này sẽ cô lập lưu lượng dữ liệu nguồn mà đang vượt trội lưu lượng dữ liệu chuyển tiếp và bảo vệ lưu lượng dữ liệu được chuyển tiếp từ sự thiếu hụt đang tồn tại khởi đầu từ một nút. 48 Trong mạng được trình bày trong hình 2.4, băng thông chia sẻ tối đa mà mỗi nút có thể nhận được tại tầng mạng (ví dụ, mỗi luồng hoặc băng thông mỗi người dùng) là G. Khi một số nút có mang lưu lượng dữ liệu chuyển tiếp cũng như lưu lượng dữ liệu của chính bản thân chúng, băng thông mà các nút 1,2,3 và 4 cần sử dụng tại tầng MAC tương ứng là 4G, 2G, G và G. Tỷ lệ thông lượng tầng mạng bằng 1:1:1:1 và tỷ lệ thông lượng tầng MAC tương ứng bằng 4:2:1:1 có thể được duy trì khi tốc độ đưa ra tại mỗi nút ít hơn dung lượng của mạng. Tuy nhiên, khi tốc độ đưa ra tại mỗi nút tăng lên vượt quá dung lượng mạng, và cuối cùng mạng bão hoà (ví dụ, tất cả các nút chia sẻ như nhau băng thông tầng MAC do sự công bằng tầng MAC), kết quả là thông lượng cho mỗi luồng tại các nút 1-4 hội tụ lần lượt tới N B 2 , N B 8 , N B 4 và N B 8 , ở đó B là thông lượng lý thuyết tối đa của mạng, và N=4 là số lượng các nút. Hình 2.5. Những cơ chế 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. Vì vậy, khi mạng bão hoà, tỷ lệ thông lượng cho mỗi luồng của các nút 1, 2, 3 và 4 là 4:1:2:1 và tỷ lệ thông lượng MAC cho mỗi nút là 1:1:1:1. Việc cô lập lưu lượng dữ liệu nguồn bằng cách đặt hai hàng đợi công bằng tại tầng mạng cho thấy vẫn còn đáng kể sự không công bằng thông lượng cho mỗi luồng, mặc dù sự phối hợp là đơn giản để thực hiện và ngăn chặn sự thiếu hụt nghiêm trọng về lưu lượng dữ liệu chuyển tiếp. Sự công bằng được bảo đảm với sự phối hợp này chỉ khi độ dài của một chuỗi không vượt quá hai bước nhảy. 2.2.2.2. Trọng số khác nhau trên lưu lượng dữ liệu chuyển tiếp Để làm giảm bớt sự không công bằng, một cách khác cho phép gán các 49 trọng số khác nhau tới mỗi hàng đợi để hàng đợi với lưu lượng dữ liệu chuyển tiếp sẽ nhận nhiều băng thông hơn khi cần thiết. Sự phối hợp này là mô hình như trình bày trong hình 2.5(c), ở đó hình đĩa lớn hơn biểu thị rằng một trọng số lớn hơn cho hàng đợi đang chuyển tiếp. Trọng số hàng đợi đang chuyển tiếp có thể được cố định trong tất cả các nút của mạng, hoặc các trọng số khác nhau có thể được sử dụng, phụ thuộc vào số lượng lưu lượng dữ liệu chuyển tiếp tại mỗi nút. Cuối cùng giả thiết rằng số lượng lưu lượng dữ liệu chuyển tiếp có thể bằng cách nào đó được xác định theo một cách phân phối. Đối với mạng được trình bày trong hình 2.4, các tỷ lệ trọng số mong muốn của gốc đối lập với lưu lượng dữ liệu chuyển tiếp tương ứng là 1:3 và 1:1 cho nút 1 và 2. Như trong trường hợp mục trước, tỷ lệ thông lượng tầng mạng bằng 1:1:1:1 và tỷ lệ thông lượng tầng MAC tương ứng bằng 4:2:1:1 có thể được duy trì khi tốc độ đưa ra tại mỗi nút ít hơn G. Khi mạng bão hoà, các thông lượng cho mỗi luồng hội tụ tương ứng tới N B 4 , N B 16 3 , N B 8 3 và N B 16 3 . Kết quả tỷ lệ thông lượng cho mỗi luồng của các nút 1-4 là 4:6:3:3 và tỷ lệ thông lượng tầng MAC tương ứng là 1:1:1:1. Cho nhiều trọng số với lưu lượng dữ liệu chuyển tiếp hơn nữa làm giảm bớt vấn đề không công bằng, và tuy nhiên nó không đạt được sự công bằng lý tưởng. Sự không công bằng hiện nay là kết quả của cấu trúc liên kết không đối xứng của mạng, điều này thường là trường hợp trong một mạng thực. Tại nút 1, các gói tin đến từ nút 2 và 3 là được xử lý như nhau, mặc dù nút 2 phải chia sẻ băng thông với nút 4. 2.2.2.3. Hàng đợi cho mỗi luồng Một phương pháp phổ biến hơn là sử dụng hàng đợi cho mỗi luồng. Như trình bày trong hình 2.5(d), các gói tin của các luồng khác nhau được xếp vào hàng riêng biệt (dựa trên địa chỉ nguồn tầng mạng của chúng). Các luồng đơn hướng về phía gateway được xem xét trong lúc này. Khi mạng bão hoà, thông lượng Fi của luồng ith là: 4 1  N BF i 50 Tại nơi đó có thể tồn tại những mạng đang thiếu tài nguyên để làm hàng đợi cho mỗi luồng (chẳng hạn, trong một mạng cảm biến lớn). Tuy nhiên, trong nhiều ứng dụng đặc biệt là trong việc truy cập mạng ở đó nhiều ứng dụng đa chặng xảy ra đụng độ, hàng đợi cho mỗi luồng là một sự phối hợp khả thi. 2.2.3. Cơ chế phối hợp điều khiển truyền Cơ chế phối hợp điều khiển truyền [9] đã đề xuất một cơ chế theo đó tầng MAC theo dõi việc mất các gói tin trong môi trường không dây và điều khiển tốc độ lưu lượng. Cơ chế này tập trung xem xét cách điều khiển truy cập môi trường trong mạng cảm biến được thực hiện theo nhiều cách khác nhau. Đầu tiên, nghiên cứu cách thức để cơ chế nghe thích hợp với trường hợp ở đó tất cả các nút có thể nghe được nhau. Tiếp theo, cách mà backoff nên được bổ sung trong một mạng cảm biến và cuối cùng là cơ chế trong mạng đa chặng (bao gồm cơ chế điều khiển tranh chấp RTS/CTS truyền thống, cơ chế điều khiển tốc độ và cơ chế điều khiển tránh các nút ẩn trong mạng đa chặng). Tuy nhiên, cơ chế này chỉ tập trung trong trường hợp nơi đó sự không công bằng cho mỗi luồng được gây ra chủ yếu bởi tầng liên kết. 2.2.3.1. Cơ chế nghe Cơ chế đa truy nhập cảm nhận sóng mang (CSMA) và phát hiện xung đột (CD) được tìm thấy trong mạng Ethernet là một ví dụ của cơ chế nghe. Nghe rất hiệu quả khi tất cả các node có thể nghe được lẫn nhau (nghĩa là không có các nút ẩn). Thật không may, sự phát hiện xung đột là không thể thực hiện được trong công nghệ mạng không dây nếu không có sơ đồ mạch bổ sung. Mặc dù nghe là đơn giản, nó làm xuất hiện chi phí năng lượng, bởi vì sóng vô tuyến phải được bật để nghe. Để giữ gìn năng lượng, điều quan trọng là rút ngắn chiều dài cảm nhận sóng mang. Nhiều giao thức như IEEE 802.11 yêu cầu cảm nhận kênh thậm chí trong suốt quá trình backoff. Tuy nhiên, CSMA cho các mạng cảm biến nên lấy cơ hội này để tắt sóng vô tuyến. Bản chất đồng bộ cao của lưu lượng dữ liệu áp đặt một tiêu chuẩn mới cho CSMA. Do không có cơ chế phần cứng để phát hiện xung đột, các node mà xảy ra việc gửi tại cùng thời điểm sẽ gây lỗi lẫn nhau. Nếu mô hình lưu lượng dữ liệu của mỗi nút là độc lập, tình trạng này sẽ không có khả năng lặp 51 lại. Tuy nhiên, sự phát hiện một sự kiện vật lý chung sẽ đồng bộ hóa các nút này và dẫn đến chúng gửi tại cùng một thời điểm, điều này sẽ lặp lại một cách định kỳ. Kết quả là không phải truyền tất cả gói tin. Giải pháp đưa ra độ trễ ngẫu nhiên cho quá trình truyền để không đồng bộ hóa các node. 2.2.3.2. Cơ chế backoff Backoff là cơ chế được sử dụng rộng rãi trong điều khiển truy nhập môi trường để giảm tranh chấp. Ý tưởng của backoff là để hạn chế một node truy cập từ kênh trong một chu kỳ thời gian và hy vọng rằng, kênh sẽ trở nên rỗi sau chu kỳ backoff. Trong trường hợp các mạng cảm biến ở đó lưu lượng dữ liệu là một sự xếp chồng của các luồng chu kỳ khác nhau, backoff sẽ không chỉ hạn chế một node đang gửi trong một chu kỳ backoff. Trong thực tế, chu kỳ backoff sẽ được áp dụng khi một pha dịch chuyển đến một chu kỳ ứng dụng do đó sự đồng bộ giữa chu kỳ các luồng lưu lượng dữ liệu có thể bị phá vỡ. 2.2.3.3. Cơ chế tranh chấp cơ sở Rõ ràng các cơ chế điều khiển tranh chấp, được dùng rộng rãi tro