We show that two incremental power heuristics for power assignment in a wireless sensor network have approximation ratio 2. Enhancements to these heuristics are proposed. It is shown that these enhancements do not reduce the approximation ratio of the considered incremental power heuristics. However, experiments conducted by us indicate that the proposed enhancements, reduce the power cost of the assignment on average. Further, the two-edge switch enhancement yields a power-cost reduction (relative to using minimum cost spanning trees) that is, on average, twice as much as obtainable from any of the heuristics proposed earlier.

We show that the problem of routing messages in a wireless sensor network so as to maximize network lifetime is NP-hard. In our model, the online model, each message has to be routed without knowledge of future route requests. We also develop an online heuristic to maximize network lifetime. Our heuristic, which performs two shortest path computations to route each message, is superior to previously published heuristics for lifetime maximization - our heuristic results in greater lifetime and its performance is less sensitive to the selection of heuristic parameters. Additionally, our heuristic is superior on the capacity metric

Summary form only given. We consider the problem of broadcasting messages in a wireless energy-limited network so as to maximize network lifetime. An O(e log e) algorithm to construct a broadcast tree that maximizes the critical energy of the network following the broadcast is developed. Additionally, we propose two new greedy heuristics to construct minimum energy broadcast trees. We show how our maximum critical energy algorithm may be coupled with our proposed greedy heuristics as well as with the greedy heuristics proposed earlier in the literature for the construction of minimum energy broadcast trees. Extensive simulations performed by us show that this coupling improves network lifetime significantly (between 48.3% and 328.9%) when compared with network lifetime using the base greedy heuristics in isolation.

We consider the problem of broadcasting messages in a wireless energy-limited network so as to maximize network lifetime. An O(e log e) algorithm to construct a broadcast tree that maximizes the critical energy of the network following the broadcast is developed. Additionally, we propose two new greedy heuristics to construct minimum energy broadcast trees. We show how our maximum critical energy algorithm may be coupled with our proposed greedy heuristics as well as with the greedy heuristics proposed for the construction of minimum energy broadcast trees. Extensive simulations performed by us show that this coupling improves network lifetime significantly (between 48.3 percent and 328.9 percent) when compared with network lifetime using the base greedy heuristics in isolation.