Dual decomposition method for optimal and fair congestion control in Ad Hoc networks: Algorithm, implementation and evaluation

Wei Qiang Xu, Ya Ming Wang, Ji Ming Chen, George Baciu, Youxian Sun

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

For the design of a more efficient congestion control algorithm to optimize the resource allocation in Ad Hoc networks, the notion of the link's interference set is introduced to represent the contention relationship among flows in Ad Hoc networks, which is the fundamental difference from the contention relationship among flows in Internet. And the congestion control problem is formulated as a nonlinear optimization problem with the capacity constraint of the link's interference set. Then, based on the dual decomposition method, this problem is decomposed into many subproblems, which can be solved independently in a parallel fashion at each source/link, and builds the Dual Decomposition based Optimal and Fair Congestion Control framework (D2OFC2) to coordinate their source allocation among flows. Considering the synchronous implementation is difficult in realistic environment, the asynchronous implementation of D2OFC2is presented. To deploy the practical protocol of D2OFC2, three deployment techniques are proposed: Queue Size Estimation method (QSE), Neighbor Set Approximation method (NSA), and Extensive HELLO message-based Piggybacking (EHP).The MATLAB-based simulation results illustrate that D2OFC2can approach the globally optimal solution even in asynchronous environment. The NS2-based simulation results demonstrate that D2OFC2outperforms default TCP and ATCP to achieve an efficient and fair resource allocation in Ad Hoc networks under three scenarios, including chain topology, grid topology, and random topology.
Original languageEnglish
Pages (from-to)997-1007
Number of pages11
JournalJournal of Parallel and Distributed Computing
Volume68
Issue number7
DOIs
Publication statusPublished - 1 Jul 2008

Keywords

  • Ad Hoc networks
  • Congestion control
  • Dual decomposition
  • Resource allocation

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this