constructing minimum energy mobile wireless networks
Given a set of wireless network nodes N , 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 | uv | &agr; + c for a real constant 2 ? &gr;?4 and c & 0. The minimum power topology G m is the smallest subgraph of G t that contains the shortest paths between all pairs of nodes. We described a distributed position-based networking protocol to construct the enclosure graph G e , which is an approximation of G m . The total communication complexity is O ( n ). Let d G ( u ) be the degree of node u in a graph G . The time complexity of each node u is O ( d Gt )). The space required at each node is O ( d Gt ( u . This improves the previous result that approximates G m O ( d G t ( u ) 3 ) time using O ( d G t ( u 2 ) spaces. We also show that the average degree d G e ( u ) is usually a constant, which is at most 6. Our result is first developed for stationary network and then extended to mobile network.
energy mobility wireless networks network direct graph power topologies shortest path distributed approximation timing time complexity space mobile network batteries computation wireless ad hoc networks energy conservation paper critic posit