Date Added: Jan 2010
Broadcast is a fundamental operation of Wireless Ad hoc NETworks (WANETs) and has widely been studied over the past few decades. However, most existing broadcasting strategies assume non-sleeping wireless nodes and thus are not suitable for uncoordinated duty-cycled WANETs, in which each node periodically switches on and off to save energy. In this paper, the authors study the Minimum-Transmission Broadcast problem in Uncoordinated Duty-cycled WANETs (MTB-UD problem) and prove its NP-hardness. They show that modifications of existing broadcast approaches can only provide a linear approximation ratio of O(n) (where n is the number of nodes in the network).