Multicast time maximization in energy constrained wireless networks

Reference:

Patrik Floréen, Petteri Kaski, Jukka Kohonen, and Pekka Orponen. Multicast time maximization in energy constrained wireless networks. In Andrea Richa and Jennifer Welch, editors, Proceedings of the 2003 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC'03, San Diego CA, September 2003), pages 50–58, New York NY, 2003. Association for Computing Machinery.

Abstract:

We consider the problem of maximizing the lifetime of a given multicast connection in a wireless network of energy-constrained (e.g. battery-operated) nodes, by choosing ideal transmission power levels for the nodes relaying the connection. We distinguish between two basic operating modes: In a em static assignment, the power levels of the nodes are set at the beginning and remain unchanged until the nodes are depleted of energy. In a em dynamic assignment, the powers can be adjusted during operation. We show that lifetime-maximizing static power assignments can be found in polynomial time, whereas for dynamic assignments, a quantized-time version of the problem is NP-hard. We then study the approximability of the quantized dynamic case and conclude that no polynomial time approximation scheme (PTAS) exists for the problem unless P=NP. Finally, by considering two approximation heuristics for the dynamic case, we show experimentally that the lifetime of a dynamically maintained multicast connection can be made several times longer than what can be achieved by the best possible static assignment.

Keywords:

ad hoc networks, wireless communications, multicast, network lifetime, energy-aware computation

Suggested BibTeX entry:

@inproceedings{FKKO03,
    address = {New York NY},
    author = {Patrik Floréen and Petteri Kaski and Jukka Kohonen and Pekka Orponen},
    booktitle = {Proceedings of the 2003 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC'03, San Diego CA, September 2003)},
    editor = {Andrea Richa and Jennifer Welch},
    pages = {50--58},
    publisher = {Association for Computing Machinery},
    title = {Multicast time maximization in energy constrained wireless networks},
    year = {2003},
}