The minimum-energy broadcast problem in symmetric wireless ad hoc networks

Document Type

Conference Paper

Department

Institute for Educational Development, East Africa

Abstract

Minimizing energy consumption in communication is a crucial problem in wireless ad hoc networks, as in most cases the nodes are powered by battery only. The minimum-energy broadcast problem is studied in this paper, for which it is well known that the broadcast nature of the radio transmission can be exploited to optimize energy consumption. This problem has been studied in a lot of literature on different models. In this paper a symmetric network is considered. First we propose an approximation algorithm, which takes O(mnα(mn)) a time, where m is the number of links, n is the number of nodes and α is the inverse of Ackerman's function. The algorithm delivers a broadcast tree with energy consumption being at most 2Hn-1 times of the optimal solution, where Hn-1 is the (n-1)st harmonic number. Since it has been proved that the minimum energy broadcast problem in general graph case (including symmetric case) cannot be approximated within a sub-logarithmic factor (unless P=NP), so the algorithm is almost optimal. For a special case where each node is equipped with the same type of battery it improves the known O(log3n)-approximation algorithm. Moreover for some asymmetric but nearly symmetric network, the algorithm can also be applied with O(ln n) performance guarantee. Finally a special case is studied, where the degree of network is bounded by a constant Δ and the ratio of the maximum transmission energy to the minimum transmission energy is bounded by another constant C. For the case we devise a 2(C+HΔ-1) -approximation algorithm.

Comments

This work was published before the author joined Aga Khan University.

Publication (Name of Journal)

ACOS'06: Proceedings of the 5th WSEAS international conference on Applied computer science

This document is currently not available here.

Share

COinS