Naslov
Minimum-Energy Broadcast in All-Wireless Networks: NP-Completeness and Distribution Issues

Autori
Čagalj, M. ; Hubaux, J.-P. ; Enz, C

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
Proceedings of the 8th ACM/IEEE International Conference on Mobile Computing and Networking (ACM/IEEE MOBICOM 2002) / - , 2002

Skup
ACM/IEEE International Conference on Mobile Computing and Networking (ACM/IEEE MOBICOM)

Mjesto i datum
Atlanta (GA), Sjedinjene Američke Države; Gruzija, 23.09.2002. - 28.09.2002

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
Wireless ad hoc networks; minimum-energy networks

Sažetak
In all-wireless networks a crucial problem is to minimize energy consumption, as in most cases the nodes are batteryoperated. We focus on the problem of power-optimal broadcast, for which it is well known that the broadcast nature of the radio transmission can be exploited to optimize energy consumption. Several authors have conjectured that the problem of power-optimal broadcast is NP-complete. We provide here a formal proof, both for the general case and for the geometric one ; in the former case, the network topology is represented by a generic graph with arbitrary weights, whereas in the latter a Euclidean distance is considered. We then 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
Računarstvo

POVEZANOST RADA