Constructing Minimum Energy Mobile Wireless Networks

Energy conservation is a critical issue in designing wireless ad hoc networks, as the nodes are powered by batteries only. Given a set of wireless network nodes, the directed weighted transmission graph G t has an edge uv if and only if node v is in the transmission range of node u and the weight of uv is typically defined as jjuvjj + c for a constant 2 5 and c > 0. The minimum power topology Gm is the smallest subgraph of G t that contains the shortest paths between all pairs of nodes, i.e., the union of all shortest paths. In this paper, we described a distributed positionbased networking protocol to construct an enclosure graph Ge , which is an approximation of Gm . The time complexity of each node u is O(min(dG t (u)dGe (u); dG t (u) log dG t (u))), where dG(u) is the degree of node u in a graph G. The space required at each node to compute the minimum power topology is O(dG t (u)). This improves the previous result that computes Gm in O(dG t (u) ) time using O(dG t (u) ) spaces. We also show that the average degree dGe (u) is usually a constant, which is at most 6. Our result is first developed for stationary network and then extended to mobile networks