Minimum-energy broadcast in random-grid ad-hoc networks
Tiziana Calamoneri, Andrea E. F. Clementi, Angelo Monti, Gianluca Del Rossi, Riccardo Silvestri · 2008
The Min Energy Broadcast problem consists in assigning transmission ranges to the nodes of an ad-hoc network in order to guarantee a directed spanning tree from a given source node and, at the same time, to minimize the energy consumption (i.e. the energy cost) yielded by the range assignment. Min Energy Broadcast is known to be NP-hard. We consider random-grid networks where nodes are chosen independently at random from the n points of a √n x √n square grid in the plane. The probability of the existence of a node at a given point of the grid does depend on that point, that is, the probability distribution can be non-uniform.