Energy-efficient virtual backbones for reception-aware MANET

Lee Joanne*, Bernard Mans

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

9 Citations (Scopus)
34 Downloads (Pure)


A simple, yet popular way to design energy-efficient routing for Mobile Ad Hoc Networks (MANET) is to use a virtual backbone that forms a minimum sized Connected Dominating Set (CDS) of the network topology. By minimising the number of forwarding nodes, it looks at extending the (battery-dependent) life-span of the network by minimising the number (and energy cost) of transmitting nodes. In this paper, we consider a more realistic model in which the energy cost of the receiving nodes (including nodes overhearing packets) is also taken into account, and show that current CDS algorithms may lead to backbones that are ineffective at minimising the overall energy cost during broadcast. We first prove that a (realistic) reception-aware model leads to a new NP-complete problem - we have coined this Connected Exact Cover - to reduce the energy drain due to the number of overheard receptions while broadcasting in MANET. This holds even if all nodes transmit at the same power. Then we introduce two algorithms, one centralised and one distributed, and show with several simulations that these algorithms generate virtual backbones that consume less energy during broadcasts compared to the best virtual backbone schemes known in the literature.

Original languageEnglish
Title of host publication2006 IEEE 63rd Vehicular Technology Conference
EditorsLynn Guarente
Place of PublicationPiscataway, N.J.
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages5
ISBN (Electronic)0780393929
ISBN (Print)0780393910, 9780780393929
Publication statusPublished - May 2006
Event2006 IEEE 63rd Vehicular Technology Conference, VTC 2006-Spring - Melbourne, Australia
Duration: 7 May 200610 Jul 2006


Other2006 IEEE 63rd Vehicular Technology Conference, VTC 2006-Spring

Bibliographical note

Copyright 2006 IEEE. Reprinted from Proceedings of the 2006 IEEE 63rd Vehicular Technology Conference (VTC2006). This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of Macquarie University’s products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to By choosing to view this document, you agree to all provisions of the copyright laws protecting it.


Dive into the research topics of 'Energy-efficient virtual backbones for reception-aware MANET'. Together they form a unique fingerprint.

Cite this