Max-life power schedule for connectivity and biconnectivity in wireless ad hoc networks

Given the initial energy supplies and the maximal transmission power of the individual nodes in a wireless ad hoc network, a power schedule of duration t for a specified topological property P is a scheduling of the transmission powers of the individual nodes over the period [0, t] such that (1) the total amount of energy consumed by each node during the period [0, t] does not exceed its initial energy supply, ( 2) the transmission power of each node at any moment in the period [0, t] does not exceed its maximal transmission power, and ( 3) the produced network topology at any moment in the period [0, t] satisfies the property P. The problem Max-Life Power Schedule for P seeks a power schedule of the maximal duration for P. Let g be the golden ratio (1 + root 5)/2, and is an element of be an arbitrarily positive constant less than one. In this paper, we present a 9g/(1 - epsilon)(2)-approximation algorithm for Max-Life Power Schedule for Connectivity, a 36g/(1 - e)(2)-approximation algorithm for Max- Life Power Schedule for 2-Node-Connectivity, and a 36g/(1 - e)(2)-approximation algorithm for Max- Life Power Schedule for 2-Edge-Connectivity.