Self-coordinating localized fair queueing in wireless ad hoc networks

Distributed fair queueing in a multihop, wireless ad hoc network is challenging for several reasons. First, the wireless channel is shared among multiple contending nodes in a spatial locality. Location-dependent channel contention complicates the fairness notion. Second, the sender of a flow does not have explicit information regarding the contending flows originated from other nodes. Fair queueing over ad hoc networks is a distributed scheduling problem by nature. Finally, the wireless channel capacity is a scarce resource. Spatial channel reuse, i.e., simultaneous transmissions of flows that do not interfere with each other, should be encouraged whenever possible. In this paper, we reexamine the fairness notion in an ad hoc network using a graph-theoretic formulation and extract the fairness requirements that an ad hoc fair queueing algorithm should possess. To meet these requirements, we propose maximize-local-minimum fair queueing (MLM-FQ), a novel distributed packet scheduling algorithm where local schedulers self-coordinate their scheduling decisions and collectively achieve fair bandwidth sharing. We then propose enhanced MLM-FQ (EMLM-FQ) to further improve the spatial channel reuse and limit the impact of inaccurate scheduling information resulted from collisions. EMLM-FQ achieves statistical short-term throughput and delay bounds over the shared wireless channel. Analysis and extensive simulations confirm the effectiveness and efficiency of our self-coordinating localized design in providing global fair channel access in wireless ad hoc networks.     

一种提高802.11无线Ad Hoc网络公平性的新机制-FFMA

实现多个数据流对无线信道的公平共享是802.11无线Ad Hoc网络中的一个重要议题,但802.11DCF机制在无线Ad Hoc网络中存在严重的公平性问题,甚至有可能出现单个节点或数据流独占信道而其他节点和数据流处于"饥饿"状态的情况.论文提出了一种新颖的保证数据流间公平性的MAC层接入机制FFMA(Flow rate-based Fair Medium Access),通过公平调度和公平竞争的方式,FFMA能够在数据流间公平地分配信道带宽资源.仿真结果表明,在无线Ad Hoc网络中,FFMA可以在保证信道吞吐量的前提下取得远优于802.11 DCF的数据流间的公平性.     

Sequential Coordination Function for Throughput and Fairness Enhancement of Wireless LANs

High throughput and fair resource sharing are two of the most important objectives in designing a medium access control (MAC) protocol. Currently, most MAC protocols including IEEE 802.11 DCF adopt a random access based approach in a distributed manner in order to coordinate the wireless channel accesses among competing stations. In this paper, we first identify that a random access?Cbased MAC protocol may suffer from MAC protocol overhead such as a random backoff for data transmission and a collision among simultaneously transmitting stations. Then, we propose a new MAC protocol, called sequential coordination function (SCF), which coordinates every station to send a data frame sequentially one after another in a distributed manner. By defining a service period and a joining period, the SCF eliminates unnecessary contentions during the service period, and by explicitly determining the sequence of frame transmission for each stations, it reduces collision occurrences and ensures fairness among stations in the service period. The performance of SCF is investigated through intensive simulations, which show that the SCF achieves higher throughput and fairness performances than other existing MAC protocols in a wide range of the traffic load and the number of stations.     

A topology-independent wireless fair queueing model in ad hoc networks

Fair queueing of rate and delay-sensitive packet flows in a shared-medium, multihop wireless network is challenging due to the unique design issues. These issues include: 1) spatial contention among transmitting flows in a spatial locality, as well as spatial reuse of bandwidth through concurrent flow transmissions in different network locations; 2) conflicts between ensuring fairness and maximizing spatial channel reuse; and 3) the distributed nature of ad hoc fair queueing. In this paper, we propose a new topology-independent fair queueing model for a shared-medium ad hoc network. Our fairness model ensures coordinated fair channel access among spatially contending flows, while seeking to maximize spatial reuse of bandwidth. We describe packetized algorithms that realize the fluid fairness model with analytical performance bounds. We further design a distributed implementation which approximates the ideal centralized algorithm. We present simulations and analysis on the performance of our proposed algorithms.     

A novel fair random access scheme with throughput optimization using fuzzy controller for wireless systems

Good backoff algorithms should be able to achieve high channel throughput while maintaining fairness among active nodes. In this paper, we propose a novel backoff algorithm to improve the fairness of random access channels, while maximizing channel throughput. The mechanism of the proposed backoff algorithm uses backoff delay (retransmission delay) and channel‐offered traffic to dynamically control the backoff interval, so that each active node increases its backoff interval in the case of collision by a factor which exponentially decreases as the backoff delay increases, and decreases its backoff interval in the case of successful transmission by a factor which exponentially decreases as the backoff delay of previous retransmission attempts increases. Also, the backoff interval is controlled according to the channel offered, traffic using a fuzzy controller to maximize channel throughput. Furthermore, the operation of the proposed backoff algorithm does not depend on knowledge of the number of active nodes. A computer simulation is developed using MATLAB to evaluate the performance of the proposed backoff algorithm and compare it with the binary exponential backoff (BEB) scheme, which is widely used owing to its high channel throughput, while its fairness is relatively poor. It is shown that the proposed backoff algorithm significantly outperforms the BEB scheme in terms of improving the performance of fairness, and converges to the ideal performance as the minimum backoff interval increases, while achieving high channel throughput. Copyright © 2008 John Wiley & Sons, Ltd.     

A k-Round Elimination Contention Scheme for WLANs

The contention resolution scheme is a key component in carrier-sense-based wireless MAC protocols. It has a major impact on MAC'S performance metrics such as throughput, delay, and jitter. The IEEE 802.11 DCF adopts a simple contention resolution scheme, namely, the binary exponential backoff (BEB) scheme. The BEB scheme achieves a reasonable performance for transmitting best-effort packets in small-sized wireless networks. However, as the network size increases, it suffers from inefficiency because of the medium contention, which leads to reduced performance. The main reason is that the BEB mechanism incurs an ever- increasing collision rate as the number of contending nodes increases. We devise a novel contention resolution scheme, a k-round elimination contention (k-EC) scheme. The k-EC scheme exhibits high efficiency and robustness during the collision resolution. More importantly, it is insensitive to the number of contending nodes. This feature makes it feasible for use in networks of different sizes. Simulation results show that the k-EC scheme offers a powerful remedy to medium contention resolution. It significantly outperforms the IEEE 802.11 DCF scheme in all the MAC'S performance metrics and also exhibits better fairness.     

Enhancing IEEE 802.11 MAC via a Sender-Initiated Reservation

The IEEE 802.11 MAC adopted a collision avoidance mechanism in which contending stations should wait a random backoff time before sending a frame. While the algorithm reduces the collision probability in general, a large number of stations may still experience heavy collisions thus decrease the throughput. In this paper, we propose a simple reservation scheme for enhancing the performance of multiple access in 802.11 MAC: when a transmitter sends a frame, if it has another frame to send in its output queue, it may reserve an additional time that is needed to send the next frame and receive an ACK for the frame. Thus a sender can occupy the medium for two data frames, while reducing the collision probability and improving channel utilization via the reservation. We develop a mathematical model to analyze the performance of proposed scheme, and perform simulations to evaluate its performance compared with the original MAC.     

EBA: an enhancement of the IEEE 802.11 DCF via distributed reservation

The IEEE 802.11 standard for wireless local area networks (WLANs) employs a medium access control (MAC), called distributed coordination function (DCF), which is based on carrier sense multiple access with collision avoidance (CSMA/CA). The collision avoidance mechanism utilizes the random backoff prior to each frame transmission attempt. The random nature of the backoff reduces the collision probability, but cannot completely eliminate collisions. It is known that the throughput performance of the 802.11 WLAN is significantly compromised as the number of stations increases. In this paper, we propose a novel distributed reservation-based MAC protocol, called early backoff announcement (EBA), which is backward compatible with the legacy DCF. Under EBA, a station announces its future backoff information in terms of the number of backoff slots via the MAC header of its frame being transmitted. All the stations receiving the information avoid collisions by excluding the same backoff duration when selecting their future backoff value. Through extensive simulations, EBA is found to achieve a significant increase in the throughput performance as well as a higher degree of fairness compared to the 802.11 DCF.     

A new concept of fairness in flow‐aware networking

We demonstrate a new approach to assuring fairness in flow‐aware networking. Standard routine in flow‐aware networking guarantees that each flow receives the same amount of resources. This property can be exploited by dividing a single transmission into a number of flows. We propose and evaluate the per‐user fair packet scheduling mechanism, which ensures fairness among users (not flows). We also compare the new mechanism with the one already known from the literature, which is based on altering the admission control routine. Evaluation shows that the new concept of fairness provides better performance and fair resource distribution regardless of the behavior of users.     

CSMA/CA‐based medium access control for indoor millimeter wave networks

Millimeter wave (mmWave) communication is a promising technology to support high‐rate (e.g., multi‐Gbps) multimedia applications because of its large available bandwidth. Multipacket reception is one of the important capabilities of mmWave networks to capture a few packets simultaneously. This capability has the potential to improve medium access control layer performance. Because of the severe propagation loss in mmWave band, traditional backoff mechanisms in carrier sensing multiple access/collision avoidance (CSMA/CA) designed for narrowband systems can result not only in unfairness but also in significant throughput reduction. This paper proposes a novel backoff mechanism in CSMA/CA by giving a higher transmission probability to the node with a transmission failure than that with a transmission success, aiming to improve the system throughput. The transmission probability is adjusted by changing the contention window size according to the congestion status of each node and the whole network. The analysis demonstrates the effectiveness of the proposed backoff mechanism on reducing transmission collisions and increasing network throughput. Extensive simulations show that the proposed backoff mechanism can efficiently utilize network resources and significantly improve the network performance on system throughput and fairness. Copyright © 2014 John Wiley & Sons, Ltd.     

A high-performance and fair scheduler for the wireless network with a multi-state channel

This work presents a novel scheduler, exponential-rule fair queueing (EFQ), for fair scheduling in wireless networks with a multi-state channel. EFQ prefers flows destined to high-capacity channels to maintain a high throughput, and prefers flows with serious lagging to ensure excellent fairness. Simulation results demonstrate that EFQ not only provides higher throughput, but also maintains superior fairness, than existing schemes.     

Credit-based slot allocation for multimedia mobile ad hoc networks

This paper studies resource management for multimedia mobile ad hoc networks (MANET). In particular, we focus on providing fair scheduling with quality-of-service (QoS) support for MANET. We consider two types of flows: guaranteed and best effort flows. The goal is to satisfy the QoS requirements of guaranteed flows and to provide global fairness for best effort flows. In this paper, a credit-based fair scheduling mechanism called credit-based slot allocation protocol (CSAP) is proposed. In CSAP, nodes are logically grouped into clusters, each with a scheduler. Each scheduler assigns time slots to nodes in its cluster based on the first tier algorithm. The node scheduled to send at the next time slot then in turn assigns the time slot to a relayed flow determined by the second-tier algorithm. Each multihop flow is treated as multiple single-hop flow segments. These segments are then correlated such that a downstream segment will not be allocated a slot unless the upstream segments have all been allocated. We evaluate the performance of CSAP by simulations. The results show that CSAP meets the QoS requirements of guaranteed flows, provides global fairness for best effort flows, and improves overall system throughput.     

Relay-volunteered multi-rate cooperative MAC protocol for IEEE 802.11 WLANs

In IEEE 802.11, the rate of a station (STA) is dynamically determined by link adaptation. Low-rate STAs tend to hog more channel time than high-rate STAs due to fair characteristics of carrier sense multiple access/collision avoidance, leading to overall throughput degradation. It can be improved by limiting the transmission opportunities of low-rate STAs by backoff parameters. This, however, may cause unfair transmission opportunities to low-rate STAs. In an attempt to increase overall throughput by volunteer high-rate relay STAs while maintaining fairness, we propose a new cooperative medium access control (MAC) protocol, relay-volunteered multi-rate cooperative MAC (RM-CMAC) based on ready to send/clear to send in multi-rate IEEE 802.11. In the RM-CMAC protocol, we show that the effect of hogging channel time by low-rate STAs can be remedied by controlling the initial backoff window size of low-rate STAs and the reduced transmission opportunity of low-rate STAs can be compensated by the help of volunteer high-rate relay STAs. We analyze the performance of RM-CMAC, i.e., throughput and MAC delay, by a multi-rate embedded Markov chain model. We demonstrate that our analysis is accurate and the RM-CMAC protocol enhances the network throughput and MAC delay while maintaining the fairness of low-rate STAs.     

一种用于移动自组织网的多址接入动态时延退避策略

在移动Ad Hoc网络中，信道接入公平性和吞吐率是MAC协议需解决的重要问题，而IEEE802．11等协议采用的二进制指数退避算法BEB难以满足公平性要求。本文提出了一种基于对节点竞争失败次数（无效RTS）进行计数的方法估计信道争用情况，动态地分配退避计数器初值，从而实现移动Ad Hoc网络的公平多址接入。研究表明，该接入方法能够有效地反映源节点特性，接入公平性好，同时在高负荷和低负荷的情况下，都能提高网络吞吐量，提供良好的QoS保障。     

A Packet Scheduling Approach to QoS Support in Multihop Wireless Networks

Providing packet-level quality of service (QoS) is critical to support both rate-sensitive and delay-sensitive applications in bandwidth-constrained, shared-channel, multihop wireless networks. Packet scheduling has been a very popular paradigm to ensure minimum throughput and bounded delay access for packet flows. This work describes a packet scheduling approach to QoS provisioning in multihop wireless networks. Besides minimum throughput and delay bounds for each flow, our scheduling disciplines seek to achieve fair and maximum allocation of the shared wireless channel bandwidth. However, these two criteria can potentially be in conflict in a generic-topology multihop wireless network where a single logical channel is shared among multiple contending flows and spatial reuse of the channel bandwidth is possible. In this paper, we propose a new scheduling model that addresses this conflict. The main results of this paper are the following: (a) a two-tier service model that provides a minimum fair allocation of the channel bandwidth for each packet flow and additionally maximizes spatial reuse of bandwidth, (b) an ideal centralized packet scheduling algorithm that realizes the above service model, and (c) a practical distributed backoff-based channel contention mechanism that approximates the ideal service within the framework of the CSMA/CA protocol.     

Lock step: an algorithm to reduce wi-fi jitter

The exponential backoff algorithm used in IEEE 802.11 does not guarantee short term fairness between flows. We propose an algorithm based on IdleSense where each of N flows tries to transmit every W = 8N slots; i.e. 8 slots per flow with 7 idle. Each flow adaptively adjusts its contention window W based on the observed proportion of empty slots. One key aspect of Lock Step is setting a deterministic backoff after a successful transmission so that, for persistent flows, eventually all users are in lock step and transmit every 8N slots. Another key aspect is forcing a second collision between colliding users so all users can better estimate the proportion of idle slots per transmission thus allowing users to estimate N and hence the optimal backoff. This second collision can also be engineered to assist the ZigZag algorithm to decode the colliding packets. Even with transient flows Lock Step reduces jitter and can substantially increase the number of flows carrying Voice over IP traffic through a single access point.     

Enhanced binary exponential backoff algorithm for fair channel access in the ieee 802.11 medium access control protocol

The medium access control protocol determines system throughput in wireless mobile ad hoc networks following the ieee 802.11 standard. Under this standard, asynchronous data transmissions have a defined distributed coordination function that allows stations to contend for channel usage in a distributed manner via the carrier sensing multiple access with collision avoidance protocol. In distributed coordination function, a slotted binary exponential backoff (BEB) algorithm resolves collisions of packets transmitted simultaneously by different stations. The BEB algorithm prevents packet collisions during simultaneous access by randomizing moments at stations attempting to access the wireless channels. However, this randomization does not eliminate packet collisions entirely, leading to reduced system throughput and increased packet delay and drop. In addition, the BEB algorithm results in unfair channel access among stations. In this paper, we propose an enhanced binary exponential backoff algorithm to improve channel access fairness by adjusting the manner of increasing or decreasing the contention window based on the number of the successfully sent frames. We propose several configurations and use the NS2 simulator to analyze network performance. The enhanced binary exponential backoff algorithm improves channel access fairness, significantly increases network throughput capacity, and reduces packet delay and drop. Copyright © 2013 John Wiley & Sons, Ltd.     

An effective medium contention method to improve the performance of IEEE 802.11

In this paper, we propose an effective medium access mechanism to enhance performance of the IEEE 802.11 distributed coordination function (DCF). One of the primary issues of 802.11 is a contention-based medium access control (MAC) mechanism over a limited medium, which is shared by many mobile users. In the original 802.11 DCF, the binary exponential backoff algorithm with specific contention window size is employed to coordinate the competition for shared channel. Instead of binary exponential increase, we adopt linear increase for the contention window that is determined according to the competing number of nodes. We also assume that the access point can broadcast the number of mobile nodes to each station through management frames. An analytical model is developed for the throughput performance of the wireless medium. Using simulation results from the NS2 simulator, we show that our model can accurately predict the system saturation throughput, and can obtain better performance in terms of throughput, fairness, and packet drop.     

Temporal fairness guarantee in multi-rate wireless LANs for per-flow protection

Wireless LAN technologies such as IEEE 802.11a and 802.11b support high bandwidth and multi-rate data transmission to match the channel condition (i.e., signal to noise ratio). While some wireless packet fair queuing algorithms to achieve the per-flow throughput fairness have been proposed, they are not appropriate for guaranteeing QoS in multi-rate wireless LAN environments. We propose a wireless packet scheduling algorithm that uses the multi-state (multi-rate) wireless channel model and performs packet scheduling by taking into account the channel usage time of each flow. The proposed algorithm aims at per-flow protection by providing equal channel usage time for each flow. To achieve the per-flow protection, we propose a temporally fair scheduling algorithm called Contention-Aware Temporally fair Scheduling (CATS) which provides equal channel usage time for each flow. Channel usage time is defined as the sum of the packet transmission time and the contention overhead time due to the CSMA/CA mechanism. The CATS algorithm provides per-flow protection in wireless LAN environments where the channel qualities of mobile stations are dynamic over time, and where the packet sizes are application-dependent. We also extend CATS to Decentralized-CATS (D-CATS) to provide per-flow protection in the uplink transmission. Using an NS-2 simulation, we evaluate the fairness property of both CATS and D-CATS in various scenarios. Simulation results show that the throughput of mobile stations with stable link conditions is not degraded by the mobility (or link instability) of other stations or by packet size variations. D-CATS also shows less delay and less delay jitter than FIFO. In addition, since D-CATS can coordinate the number of contending mobile stations, the overall throughput is not degraded as the number of mobile stations increases. This work was supported in part by the Brain Korea 21 project of Ministry of Education and in part by the National Research Laboratory project of Ministry of Science and Technology, 2004, Korea.     

Fair MAC protocol for optical ring network of wavelength-shared access nodes

In this paper, a WDM optical ring consisting of access nodes with fixed transmitter-n fixed receivers (FT—FR ⁿ ) is considered. As access nodes share a wavelength channel there is trade-off between node throughput and fairness among them. In order to abbreviate the transmission unfairness and to increase the throughput, we propose p-persistent medium access control (MAC) protocol. Each node uses the carrier sense multiple access with collision avoidance (CSMA/CA) protocol to transmit packets, and decides whether to use a local empty slot with probability p when a transferred packet based on source-stripping is dropped and emptied. Numerical prediction for the proposed MAC protocol is introduced to compute the maximum node throughput under uniform traffic condition. For more detail results, we use network simulation with self-similar traffic and introduce various results. The proposed MAC protocol gives better node throughput than non-persistent protocol and shows an improved fairness factor than 1-persistent protocol. Through simulation, we also find the reasonable probability of p-persistent protocol for a given architecture.