Naslov
Energy-Efficient Broadcasting in All-Wireless Networks

Autori
Čagalj, Mario ; Hubaux, Jean-Pierre ; Enz, Christian

Izvornik
Wireless Networks (WINET) (1022-0038) 11 (2005), 1-2; 177-188

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
wireless ad hoc networks; minimum-energy networks; energy efficiency; approximation algorithms; complexity theory

Sažetak
In all-wireless networks, minimizing energy consumption is crucial as in most cases the nodes are battery-operated. We focus on the problem of power-optimal broadcast, for which it is well known that the broadcast nature of radio transmissions can be exploited to optimize energy consumption. This problem appears to be difficult to solve. We provide a formal proof of NP-completeness for the general case and give an NP-completeness result for the geometric case ; in the former, the network topology is represented by a generic graph with arbitrary weights, whereas in the latter a Euclidean distance is considered. For the general case, we show that it cannot be approximated better than O(log N), where N is the total number of nodes. We then describe an approximation algorithm that achieves the O(log N) approximation ratio. We also describe a new heuristic, Embedded Wireless Multicast Advantage. We show that it compares well with other proposals and we explain how it can be distributed.

Izvorni jezik
Engleski

Znanstvena područja
Elektrotehnika, Računarstvo

POVEZANOST RADA