Energy-Efficient Virtual Backbones for Reception-Aware MANET

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