Scheduling Algorithms for Performance and Fairness over IEEE 802.11 Multi-Hop Wireless Ad Hoc Networks

摘要

無線LANにおけるメディアアクセス制御のためのIEEE802.11MACプロトコルは無線アドホックネットワークにおけるde facto standardである。しかし，遅延，スループット，公平性の観点から，必ずしも良い特性が得られるとは言えない。問題点は，MAC層とリンク層における頼掛こある。これに関して多くの研究がある。ノード毎の公平性のためにIEEE801.11MACプロトコルの改良が提案されているが，MACプロトコルの変更はハードウェアの変更を伴い，従って実装が困難である。さらに，フロー毎の不公平性の問題もある。その他の方法として，FIFOによるフロー毎の不公平性を解決するためにRound Robin（RR）スケジューリングがあるが，この方法はMAC層において帯域が理想的に公平に配分されているという仮定を置いている。しかし，802.11はマルチホップアドホックネットワークにおいては必ずしも公平性を保証しない。本論文では，マルチホップアドホックネットワークにおけるフロー毎の公平性を達成するために，新たなスケジューリング方式Probabilistic Control Round robin Queue（PCRQ）を提案する。この方式はリンク層におけるスケジューリングであり，MAC層の公平性を仮定していない。提案法がUDPおよびTCPトラヒックに対して良好な特性を示すことを確認する。%IEEE 802.11 MAC protocol for medium access control in wireless Local Area Networks (LANs) is the de facto standard for wireless ad hoc networks, however, it does not perform well in terms of delay, throughput, and specially, fairness in multihop wireless ad hoc networks. The problems are due to MAC and link layer contention. Many researches have been published in this area. Among them, a modification of IEEE 802.11 MAC protocol was proposed to achieve per-node fairness, but the modification of MAC layer requires a change of hardware, so, it is difficult to implement. Moreover, it still faces up per-flow unfairness problem. As another solution, the Round Robin (RR) scheduling was introduced to overcome the per-flow unfairness problem caused by the First In First Out (FIFO) scheduling. Those solutions are based on the assumption that MAC layer gives the ideal fairness of bandwidth allocation, but IEEE 802.11 MAC protocol fails to ensure MAC layer fairness in multihop ad hoc network. In this paper, we propose a new scheduling method, Probabilistic Control on Round robin Queue (PCRQ) scheduling, aiming to achieve per-flow fairness in multihop ad hoc networks. In PCRQ scheduling, a new link layer scheduling is proposed without assuming the fairness of MAC layer. Our proposed method achieves good performance results in both UDP and TCP traffics.