On the node-scheduling approach to topology control in ad hoc networks

Budhaditya Deb, Badri Nath

Research output: Contribution to conferencePaperpeer-review

22 Scopus citations

Abstract

In this paper, we analyze the node scheduling approach of topology control in the context of reliable packet delivery. In node scheduling, only a minimum set of nodes needed for routing purposes (usually determined by a minimum connected dominating set, MCDS) are kept active. However, a very low density resulting from switching off nodes can adversely affect the performance of data delivery due to three factors. First, our analysis shows that at low density, the average path length increases by a factor more than previously thought. Second, protocols such as the Hop-By-Hop Broadcast (HHB) reliability scheme (which relies on high network degree for optimum performance) suffer. Third, with limited buffers at nodes, the overhead is more pronounced to the extent of making the network unstable. Using probabilistic models, we derive the relationship between network density and overhead based on the above factors and find the density conditions for minimum power consumption. We also propose a, fully distributed and message-optimal node scheduling algorithm with a constant approximation bound based on the concept of Virtual Connected Dominating Sets. The scheme can asymptotically achieve optimal density conditions while adapting to different network parameters. Copyright ACM.

Original languageEnglish (US)
Pages14-25
Number of pages12
DOIs
StatePublished - 2005
EventMOBIHOC 2005: 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing - Urbana-Champaign, IL, United States
Duration: May 25 2005May 28 2005

Other

OtherMOBIHOC 2005: 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing
CountryUnited States
CityUrbana-Champaign, IL
Period5/25/055/28/05

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • Ad-Hoc Networks
  • Minimum Virtual Dominating Sets
  • Node Scheduling
  • Reliable Packet Delivery
  • Topology Control

Fingerprint Dive into the research topics of 'On the node-scheduling approach to topology control in ad hoc networks'. Together they form a unique fingerprint.

Cite this