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.     

Optimal resource allocation in wireless ad hoc networks: a price-based approach

The shared-medium multihop nature of wireless ad hoc networks poses fundamental challenges to the design of effective resource allocation algorithms that are optimal with respect to resource utilization and fair across different network flows. None of the existing resource allocation algorithms in wireless ad hoc networks have realistically considered end-to-end flows spanning multiple hops. Moreover, strategies proposed in wireline networks are not applicable in the context of wireless ad hoc networks, due to their unique characteristics of location-dependent contention. In this paper, we propose a new price-based resource allocation framework in wireless ad hoc networks to achieve optimal resource utilization and fairness among competing end-to-end flows. We build our pricing framework on the notion of maximal cliques in wireless ad hoc networks, as compared to individual links in traditional wide-area wireline networks. Based on such a price-based theoretical framework, we present a two-tier iterative algorithm. Distributed across wireless nodes, the algorithm converges to a global network optimum with respect to resource allocations. We further improve the algorithm toward asynchronous network settings and prove its convergence. Extensive simulations under a variety of network environments have been conducted to validate our theoretical claims.     

Hybrid Dynamic Channel Assignment in Clustered Wireless Multihop CDMA/TDMA Ad Hoc Networks

A good channel assignment scheme in a multihop ad hoc network should not only guarantee successful data transmissions without collisions, but also enhance the channel spatial reuse to maximize the system throughput. It becomes very inefficient to use fixed channel assignment when the network size grows. Therefore, spatial reuse of channels become more important in a large multihop ad hoc network. In this paper, we consider an ad hoc network with an overlaid CDMA/TDMA structure. We divide each code into time slots to form the channels. A dynamic channel assignment (DCA) strategy called Hybrid-DCA is proposed in a clustered ad hoc network. This DCA strategy is designed to make the best use of available channels by taking advantage of the spatial reuse concept. In Hybrid-DCA, the increase in spatial reuse is achieved by adding certain control overhead. We show that the bandwidth saving due to channel spatial reuse is higher than the additional bandwidth spent on the control overhead.     

一种提高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的数据流间的公平性.     

PASA: power adaptation for starvation avoidance to deliver wireless multimedia

In recent years, there has been an increasing interest to deliver multimedia services over wireless ad hoc networks. Due to the existence of hidden terminal and absence of central control, the medium access control protocol as used in the ad hoc networks may lead to channel capture, where some flows monopolize the channel while others suffer from starvation. As a consequence, the system throughput and fairness are greatly degraded. After showing that static power control leads to channel capture, we propose and study a distributed dynamic power control scheme termed "power adaptation for starvation avoidance" (PASA), which dynamically adjusts the transmission power of a node so as to avoid starvation. PASA is shown to be effective in breaking channel captures, hence improving short-term fairness among contending flows. It is simple, fully autonomous and requires no communication overhead. Via extensive simulations, we show that our power control algorithm achieves much better fairness without compromising system throughput through better spatial reuse. Our experiments with video sequences transmitting over different network topologies show that PASA achieves much better video quality with lower start-up delay and buffer requirement.     

Efficient Packet Scheduling Using Channel Adaptive Fair Queueing in Distributed Mobile Computing Systems

In a distributed mobile computing system, an efficient packet scheduling policy is a crucial component to achieve a high utilization of the precious bandwidth resources while satisfying users' QoS (quality of service) demands. An important class of scheduling techniques, namely, the wireless fair queueing algorithms, have been extensively studied recently. However, a major drawback in existing approaches is that the channel model is overly simplified – a two-state channel (good or bad) is assumed. While it is relatively easy to analyze the system using such a simple model, the algorithms so designed are of a limited applicability in a practical environment, in which the level of burst errors is time-varying and can be exploited by using channel adaptive coding and modulation techniques. In this paper, we first argue that the existing algorithms cannot cater for a more realistic channel model and the traditional notion of fairness is not suitable. We then propose a new notion of fairness, which bounds the actual throughput normalized by channel capacity of any two data connections. Using the new fairness definition, we propose a new fair queueing algorithm called CAFQ (Channel Adaptive Fair Queueing), which, as indicated in our numerical studies, outperforms other algorithms in terms of overall system throughput and fairness among error prone connections.     

Ad hoc网络基于公平的带宽分配机制研究

Ad hoc网络是一种没有固定基础设施,由多个带有无线收发装置的移动终端组成的多跳临时性自治系统。它独特的个性决定了各数据流之间要竞争共享的有限带宽资源。因此,为了保证Ad hoc网络业务的服务质量,合理的带宽分配机制至关重要。介绍了无线Ad hoc网络的网络模型,对带宽分配机制的定义及约束条件进行描述分析,然后从公平的角度详细地分析了目前Ad hoc网络的带宽分配机制,并总结了各种分配机制的优缺点。     

A low-state packet marking framework for approximate fair bandwidth allocation

Misbehaving, non-congestion-reactive traffic is on the rise in the Internet. One way to control misbehaving traffic is to enforce local fairness among flows. Locally fair policies, such as fair-queueing and other fair AQM schemes, are inadequate to simultaneously control misbehaving traffic and provide high network utilization. We thus need to enforce globally fair bandwidth allocations. However, such schemes have typically been stateful and complex to implement and deploy. In this letter, we present a low state, lightweight scheme based on stateless fair packet marking at network edges followed by RIO queueing at core nodes, to control misbehaving flows with more efficient utilization of network bandwidth. Additionally, with low-state feedback from bottleneck routers, we show that, in practice, we can approximate global max-min fairness within an island of routers. We show, using simulations, that we can indeed control misbehaving flows and provide more globally fair bandwidth allocation.     

Bandwidth sharing: objectives and algorithms

This paper concerns the design of distributed algorithms for sharing network bandwidth resources among contending flows. The classical fairness notion is the so-called max-min fairness. The alternative proportional fairness criterion has recently been introduced by F. Kelly (see Eur. Trans. Telecommun., vol.8, p.33-7, 1997); we introduce a third criterion, which is naturally interpreted in terms of the delays experienced by ongoing transfers. We prove that fixed-size window control can achieve fair bandwidth sharing according to any of these criteria, provided scheduling at each link is performed in an appropriate manner. We then consider a distributed random scheme where each traffic source varies its sending rate randomly, based on binary feedback information from the network. We show how to select the source behavior so as to achieve an equilibrium distribution concentrated around the considered fair rate allocations. This stochastic analysis is then used to assess the asymptotic behavior of deterministic rate adaption procedures     

A Unified Architecture for the Design and Evaluation of Wireless Fair Queueing Algorithms

Fair queueing in the wireless domain poses significant challenges due to unique issues in the wireless channel such as location-dependent and bursty channel errors. In this paper, we present a wireless fair service model that captures the scheduling requirements of wireless scheduling algorithms, and present a unified wireless fair queueing architecture in which scheduling algorithms can be designed to achieve wireless fair service. We map seven recently proposed wireless fair scheduling algorithms to the unified architecture, and compare their properties through simulation and analysis. We conclude that some of these algorithms achieve the properties of wireless fair service including short-term and long-term fairness, short-term and long-term throughput bounds, and tight delay bounds for channel access.     

Exploiting spatial multiplexing and reuse in multi-antenna wireless ad hoc networks

Efficient exploitation of multiple antenna capabilities in ad hoc networks requires carefully designed cross-layer techniques. The work presented in this paper provides a medium access control (MAC)/physical cross-layer scheme for ad hoc networks to address several of the challenges involved in cross-layer design. Multiple antenna systems can be used to increase data rate by spatial multiplexing, that is communicating multiple parallel streams, and to increase spatial reuse by interference suppression. Our proposed scheme, called HYB, exploits both spatial multiplexing and reuse so a receiver node can receive multiple simultaneous data streams from a desired transmitter while suppressing interference from other transmitters in the neighborhood. HYB partitions the available degrees of freedom in the antenna array between spatial multiplexing and reuse which allows the user to obtain different performance characteristics. The applicability of HYB spans across all wireless environments, including line-of-sight and dense multipath scenarios.Simulations demonstrate the significant performance gains and flexibility offered by HYB. The simulation results also offer key insights into the multi-antenna resource allocation problem in ad hoc networks based on traffic patterns and network/transport layer protocols, and consequently provide guidelines for network configuration/management. We show that throughput increases when the degrees of freedom allocated to spatial multiplexing increases, while fairness increases when the degrees of freedom allocated to spatial reuse increases.     

A local fairness algorithm for gigabit LAN's/MAN's with spatialreuse

The authors present an algorithm to provide local fairness for ring and bus networks with spatial bandwidth reuse. Spatial bandwidth reuse can significantly increase the effective throughput delivered by the network. The proposed algorithm can be applied to any dual ring or bus architecture such as MetaRing. In the dual bus configuration, when transporting ATM cells, the local fairness algorithm can be implemented using two generic flow control (GFC) bits in the ATM cell header. In the performance it is shown that this local fairness algorithm can exploit the throughput advantage offered by spatial bandwidth reuse better than a global fairness algorithm. This is accomplished because it ensures fair use of network resources among nodes that are competing for the same subset of links, while permitting free access to noncongested parts of the network. The performance advantage of the local fairness scheme is demonstrated by simulating the system under various traffic scenarios and comparing the results to that of the MetaRing SAT-based global fairness algorithm. It is also shown that under certain traffic patterns, the performance of this algorithm achieves the optimal throughput result predicted by the known Max-Min fairness definition     

Design and analysis of an algorithm for fair service in error‐prone wireless channels

In order to support diverse communication‐intensive real‐time and non‐real‐time data flows over a scarce, varying and shared wireless channel with location‐dependent and bursty errors, we define a service model that has the following characteristics: short‐term fairness among flows which perceive a clean channel, long‐term fairness for flows with bounded channel error, worst‐case delay bounds for packets, short‐term throughput bounds for flows with clean channels and long‐term throughput bounds for all flows with bounded channel error, expanded schedulable region, and support for both delay sensitive and error sensitive data flows. We present the wireless fair service algorithm, and show through both analysis and simulation that it achieves the requirements of the service model in typical wireless network environments. The key aspects of the algorithm are the following: (a) an enhanced fair queueing based service scheme that supports decoupling of delay and bandwidth, (b) graceful service compensation for lagging flows and graceful service degradation for leading flows, (c) support for real‐time delay sensitive flows as well as non‐real‐time error sensitive flows, and (d) an implementation within the framework of the simple and robust CSMA/CA wireless medium access protocol. This revised version was published online in July 2006 with corrections to the Cover Date.     

A Hybrid Collision Avoidance Scheme for Ad Hoc Networks

A novel hybrid collision avoidance scheme that combines both sender-initiated and receiver-initiated collision-avoidance handshake is proposed for multi-hop ad hoc networks. The new scheme is compatible with the popular IEEE 802.11 MAC protocol and involves only some additional queue management and book-keeping work. Simulations of both UDP- and TCP-based applications are conducted with the IEEE 802.11 MAC protocol, a measurement-based fair scheme and the new scheme. It is shown that the new scheme can alleviate the fairness problem with almost no degradation in throughput. More importantly, it is shown that without explicit information exchange among nodes, the fairness problem cannot be solved conclusively if reasonable throughput is to be maintained. Hence it calls for further work to integrate the new collision avoidance scheme with other schemes that approximate fair queueing and use more contention information in channel access to achieve some QoS assurances in ad hoc networks.     

A QoS Routing Protocol with Bandwidth Allocation in Multichannel Ad Hoc Networks

Mobile multimedia applications have recently generated much interest in mobile ad hoc networks (MANETs) supporting quality-of-service (QoS) communications. Multiple non-interfering channels are available in 802.11 and 802.15 based wireless networks. Capacity of such channels can be combined to achieve higher QoS performance than for single channel networks. The capacity of MANETs can be substantially increased by equipping each network node with multiple interfaces that can operate on multiple non-overlapping channels. However, new scheduling, channel assignment, and routing protocols are required to utilize the increased bandwidth in multichannel MANETs. In this paper, we propose an on-demand routing protocol M-QoS-AODV in multichannel MANETs that incorporates a distributed channel assignment scheme and routing discovery process to support multimedia communication and to satisfy QoS bandwidth requirement. The proposed channel assignment scheme can efficiently express the channel usage and interference information within a certain range, which reduces interference and enhances channel reuse rate. This cross-layer design approach can significantly improve the performance of multichannel MANETs over existing routing algorithms. Simulation results show that the proposed M-QoS-AODV protocol can effectively increase throughput and reduce delay, as compared to AODV and M-AODV-R protocols.     

An Adaptive Generalized Transmission Protocol for Ad Hoc Networks

Wireless networking and group communication in combination allows groups of dispersed mobile users to collaborate. This paper presents AGENT, a medium access control (MAC) protocol that unifies point-to-point and multi-point transmission services to facilitate group communication in ad hoc networks. Analysis and experiments performed in a simulated ad hoc network demonstrate that AGENT exhibits reliable and stable performance with high spatial bandwidth reuse. Moreover, variation in the proportion of point-to-point and multi-point traffic is shown to have little impact on the overall performance of AGENT. Comparison with the other tested MAC protocols reveals that the performance of AGENT is superior, achieving higher channel utilization and lower access delay.     

Flow rank based probabilistic fair scheduling for wireless ad hoc networks

Fair scheduling is an ideal candidate for fair bandwidth sharing and thereby achieving fairness among the contending flows in a network. It is particularly challenging for ad hoc networks due to infrastructure free operation and location dependent contentions. As there is no entity to serve coordination among nodes, we need a mechanism to overcome inherent unreliability of the network to provide reduced collision and thereby higher throughput and adequate fair allocation of the shared medium among different contending flows. This paper proposes a flow rank based probabilistic fair scheduling technique. The main focus is to reduce the collision probability among the contending flows while maintaining the prioritized medium access for those flows, which ensures a weighted medium access control mechanism based on probabilistic round robin scheduling. Each flow maintains a flow-table upon which the rank is calculated and backoff value is assigned according to the rank of the flow, i.e., lower backoff interval to lower ranked flow. However, flow-table instability due to joining of a new flow, partially backlogged flow, hidden terminal and partially overlapped region exhibits a challenging problem that needs to be mitigated for our mechanism to work properly. We take appropriate measures to make the flow-table stabilized under such scenarios. Results show that our mechanism achieves better throughput and fairness compared to IEEE 802.11 MAC and existing ones.     

Fair Algorithms for Maximal Link Activation in Multihop Radio Networks

We present a distributed algorithm for obtaining a fair time slot allocation for link activation in a multihop radio network. We introduce the concept of maximal fairness in which the termination of a fair allocation algorithm is related to maximal reuse of the channel under a given fairness metric. The fairness metric can be freely interpreted as the expected link traffic load demands, link priorities, etc. Since respective demands for time slot allocation will not necessarily be equal, we define fairness in terms of the closeness of allocation to respective link demands while preserving the collision free property. The algorithm can be used in conjunction with existing link activation algorithms to provide a fairer and fuller utilization of the channel.     

A Distributed Channel Access Protocol for Ad Hoc Networks with Feedback Power Control

Distributed power control schemes are extensively employed in the cellular networks and are capable of improving the capacity of the network. However, the power control schemes from the cellular networks suffer from performance degradation due to self and direct-interference and hidden-terminal problems when directly employed in ad hoc networks. Most of the existing channel reservation-based power control protocols for ad hoc networks employ incremental power allocation rather than global allocation of the power to the incoming links; thus, they may not effectively utilize the spatial frequency reuse in the network. This paper presents a distributed channel access protocol that couples the channel reservation and the iterative/global transmission power control schemes in ad hoc networks. The designed protocol considers the convergence problem of the global power control in ad hoc networks. The designed access criteria employ the local admission control based on the sufficient criteria for admissibility and global power control for balancing the SIR (signal to interference ratio) of the links. In the performance evaluation study of the designed protocol, an almost twofold increase in the throughput and capacity is observed compared to the existing power-controlled protocol for ad hoc networks.     

Efficient delay based scheduling with fairness in multi-hop wireless mesh networks

Some scheduling algorithms have been designed to improve the performance of multi-hop wireless mesh networks (WMNs) recently. However the end-to-end delay is seldom considered as the complexity of multi-hop topology and open wireless shared channel. This article proposes an efficient delay based scheduling algorithm with the concept of buffer-data- hops. Considering the demand satisfaction factor (DSF), the proposed algorithm can also achieve a good fairness performance. Moreover, with the interference-based network model, the scheduling algorithm can maximize the spatial reuse, compared to those graph-based scheduling algorithms. Detailed theoretical analysis shows that the algorithm can minimize the end-to-end delay and make a fair scheduling to all the links.