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

Yuan Xue, L. I. Baochun, Klara Nahrstedt

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)347-364
Number of pages18
JournalIEEE Transactions on Mobile Computing
Volume5
Issue number4
DOIs
StatePublished - Jul 2006

Keywords

  • Algorithm/protocol design and analysis
  • Nonlinear programming
  • Wireless communication

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Optimal resource allocation in wireless ad hoc networks: A price-based approach'. Together they form a unique fingerprint.

Cite this