Optimal Resource Allocation in Wireless Ad Hoc Networks: A Price-based Approach

Xue, Yuan; Li, Baochun; Nahrstedt, Klara

Permalink

https://hdl.handle.net/2142/10934 Copy

Description

Title

Optimal Resource Allocation in Wireless Ad Hoc Networks: A Price-based Approach

Author(s)

• Xue, Yuan
• Li, Baochun
• Nahrstedt, Klara

Issue Date

2004-12

Keyword(s)

• wireless networks
• ad hoc networks
• wireless ad hoc networks

Abstract

The shared-medium multi-hop 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 its 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 towards asynchronous network settings, and prove its convergence. Extensive simulations under a variety of network environments have been conducted to validate our theoretical claims.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/10934

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections