在無線隨意網路中達到極大-極小公平的分散式排程

Abstract

在無線隨意網路裡，每個使用者在頻帶上的競爭是取決於使用者的位置及週遭其他使用者的分布情形。此種特性造成有線網路的媒體存取層協定不適用於無線隨意網路。而目前較為普遍的無線隨意網路媒體存取層協定為載波檢測多路存取/碰撞避免，但是此協定在某些網路拓樸下會造成不公平的情況。因此我們採用最大-最小公平的頻寬分配來解決不公平的情況，而此分配可在公平的原則下盡可能的提高網路的整體效能。在論文裡,我們首先證明在無線隨意網路裡要達到極大-極小公平是NP-困難 (NP-hard) 的問題。加上無線隨意網路並沒有存取器，因此想要建造中央集權式的協定是困難的，所以我們藉由單次跳躍鄰居的串流列表做探索且分散式的排程。在協定裡，每個使用者根據之前傳送的情況調整自己的串流列表來達到極大-極小公平。並且為了使頻帶重覆利用優於載波檢測多路存取，我們將時間切割成連續的時槽以利同步的傳送。最後模擬實驗結果顯示，將串流列表與載波檢測多路存取結合或與時間同步結合，都可以有效的逼近極大-極小公平。

In wireless ad hoc networks, the contention between mobile nodes is spatial and location dependent, which is the reason that the Medium Access Control (MAC) protocol for wired networks is not applicable for wireless ad hoc networks. The most general wireless MAC protocol, CSMA/CA-based protocol, is not fair in some network topologies. We adopt max-min fairness allocation which is not only fair but to improve network throughput as much as possible to design a MAC protocol. In the thesis we first prove that achieving max-min fairness in wireless ad hoc networks is NP-hard. Since it is infrastructure-free in wireless ad hoc networks, which makes it difficult to provide a centralized protocol, we design a heuristic and fully distributed protocol referring to the flow lists of one-hop neighboring nodes. In the protocol, each node adjusts its flow list according to the recent transmission results to attain max-min fairness. We also divide time into consecutive time slots to make the transmission synchronized so that spatial reuse is better than CSMA-based protocol. Finally the simulation results reveal that the max-min-fairness-oriented flow-list scheduling with CSMA-based protocol or time synchronized protocol both have good performance in terms of max-min fairness.