Yuan Xue

Price-based Resource Allocation in Wireless Networks

[Overview] [Results] [Software] [Publications] [Talks] [Funding Agents]

We investigate the problem of optimal resource allocation in wireless networks, where scarce resource is optimally utilized and fairly shared among different users. Compared with traditional wireline networks, the unique characteristics of wireless networks pose new challenges to this problem, and prevent verbatim applications of the existing resource allocation approaches. Particularly, the following issues of wireless networks need fresh treatment.

Interference of wireless communication. Compared with wireline networks where flows only contend at the router that performs flow scheduling (contention in the time domain), the unique characteristics of wireless networks show that, flows also compete for shared channel if they are within the interference ranges of each other (contention in the spatial domain). This presents the problem of designing the topology-aware resource allocation algorithm for contending multi-hop flows.

Complex resource usage. Sending data from one wireless node to another needs to consume multiple resources, most notably wireless bandwidth and battery energy. Wireless bandwidth is shared among neighboring nodes, while battery energy is private to the node itself. Thus end-to-end multihop flows need coordinated resource allocation between bandwidth and energy. In the wireline networks, this kind of complex resource usage does not occur.

Autonomous communication entities. The wireless nodes usually belong to different autonomous entities. They may lack the incentive to contribute to the network functionality in a cooperative way. Here cooperation has two-fold implications. First, each wireless node does not excessively and greedily inject traffic to the shared wireless channel. Second, intermediate nodes are willing to relay traffic for upstream nodes towards the destination at the cost of their own private resources. This presents the problem of designing appropriate incentive mechanisms to not only encourage cooperative behavior of selfish nodes, but also curb unfair and excessive resource usage.

Dynamic environment. Mobile users of wireless networks create a dynamic networking environment, where network topologies and resource usage
patterns are changing with time. Such environments require the resource allocation mechanism to adapt quickly to network and resource dynamics.

We study the problem of optimal resource allocation through theoretical modeling, algorithm design and system deployment. Based on solid theoretical analysis, I establish a novel contention-aware price-based resource allocation model. In this model, channel resource is precisely modeled as a set of independent elements that characterize the location-dependent contention and spatial reuse of wireless medium. Each element is a facet of the polytope defined by the independent set of the contention graph of the wireless network, which can be approximated by a maximal clique, as illustrated in the following figure:


(a) network topology	(b) contention graph	(c) facet of independent polytope	(d) clique in contention graph

Price is further generated based on the bandwidth demand and supply at each resource element, and is used to coordinate the resource allocation at different hops in a distributed way. The proposed pricing model of a wireless network is fundamentally different from a wireline network due to its unique characteristic.

Based on this pricing model, we present two sets of distributed algorithms, each following a different optimization method. In the dual method, price is dynamically adjusted via gradient projection method based on the relationship between the resource demand and its supply. Then the users make self-optimization decisions on their sending rates to maximize their own net benefits, which is the difference between their utilities and their costs. In the penalty method, price is generated based on a static function of the resource load and its capacity. Then the users adjust their rates in an additive increase and multiplicative decrease manner towards a self-optimization goal. We show that both distributed algorithms converge to the unique global optimal network operation point. The key challenge to implement the above resource allocation algorithms comes from the computational complexity of identifying resource elements and the communication overhead from the distributed algorithms. To address these challenges, we first present heuristics of these algorithms which approximate the original algorithms at different levels and different degrees by exploring the locality of the wireless network. Then we design low overhead communication protocols which are integrated with the existing ad hoc routing protocols.

The novel contribution of this work is that it is the first work to point out that the pricing model of a wireless network is fundamentally different from a wireline network. Since the pricing model constitutes the theoretical foundation for most rate control algorithms such as TCP, this observation reveals the intrinsic deficiency suffered by these solutions, such as unfairness and instability, when they are migrated from the wireline network to the wireless network.

Finally, we present a price-pair mechanism to coordinate the resource allocation between the wireless bandwidth and the battery energy, and to
provide incentives simultaneously, such that cooperation is promoted and the levels of cooperation are adequate to achieve the desired global
optimal network operation point. This global optimum is characterized with the concept of Nash Bargaining Solution (NBS), which not only provides the
Pareto optimal point for the network, but is also consistent with the fairness axioms of game theory. The price-pair model is illustrated in the following figure.

Results

We study the performance of our model and algorithms under three environments. The first environment assumes bounded communication delay and synchronized message updates. The second considers the asynchronous environments in wireless ad hoc networks. In both environments, we assume that the MAC layer scheduling is ideal in a sense that it can achieve the wireless channel capacity and the routing algorithm uses shortest path. The
third, which considers the realistic wireless environments, is built based on ns-2 simulator. It adopts two-ray ground reflection model as radio
propagation model and uses IEEE 802.11DCF as the MAC protocol. We are also building our solution on Linux systems and deploying it over an 802.11-based wireless testbed. The following shows the ns-2 simulation results on the convergence and equilibrium rate allocation of our algorithm.

Software

ns-2 based simulation code [download]

linux-based implementation code [download available soon]

Publications

Yuan Xue, Baochun Li, and Klara Nahrstedt, "Optimal Resource Allocation in Wireless Ad Hoc Networks: A Price-based Approach," to appear in IEEE Transactions on Mobile Computing, 2005.[pdf] [technical report]

Yuan Xue, Baochun Li, and Klara Nahrstedt, "Channel-Relay Price Pair: Towards Arbitrating Incentives in Wireless Ad hoc Networks,'' to appear in the Journal of Wireless Communications and Mobile Computing, Special Issue on Ad Hoc Networks, Wiley InterScience, 2004. (acceptance ratio = 9/38 = 23%) [pdf]

Yuan Xue, Baochun Li, and Klara Nahrstedt, "Price-based Resource Allocation in Wireless Ad hoc Networks,'' in Proc. of the 11th International Workshop on Quality of Service (IWQoS), also Lecture Notes in Computer Science, ACM Springer-Verlag, Vol. 2707, pp. 79-96, Monterey, CA, June, 2003. [pdf]

Yuan Xue, Hoang Nguyen, and Klara Nahstedt, "CAAQM: Channel-Aware Active Queue Management for Multi-Rate Wireless LAN," in preparation for conference publication.

Talks

The 11th International Workshop on Quality of Service (IWQoS) Presentation [ppt]

Funding Agents

This research was supported by the ONR MURI NAVY CU 37515-6281 grant and Vodafone Fellowship. Any opinions, findings, and conclusions are those of the authors and do not necessarily reflect the views of the above agencies.

Please direct comments and suggestions to Yuan Xue.
Last updated: Jan 1, 2005.