Per-node power minimal multicast trees which maximize time-to-first-failure in energy constrained static wireless networks: a 2-step heuristic approach

We consider the problem of jointly maximizing the time-to-first-failure (TTFF), defined as the time till the first node in the network runs out of battery energy, and minimizing the total power in energy constrained static wireless networks. It is shown in A.K. Das et al. (2004) that simply optimizing the TTFF criterion may not provide the ideally optimum solution. Besides maximizing the TTFF, the ideally optimum solution guarantees that the lifetimes of all nodes are at least as high as in other trees which provide the same TTFF. A composite objective function involving the TTFF and the sum of the transmitter powers is therefore proposed in A.K. Das et al. (2004), along with a discussion of an optimal solution methodology using mixed integer linear programming. In this paper, we discuss a 2-step heuristic-procedure for the joint optimization problem. The first step is a greedy iterative algorithm which provides an optimal solution, but with respect to the TTFF criterion only. The second step is a tree-improvement technique which is used to refine the TTFF-optimal tree such that the total transmitter power is minimized, without affecting the optimal TTFF. Recent work has shown that the power consumed in the receiver circuitry can be almost comparable to the transmit power, especially in short-range networks. Our algorithms are therefore designed to take into account both the transmitter side and receiver side power expenditures. Simulation results are presented to validate the performance of the algorithm