Constructing minimum energy mobile wireless networks

ABSTRACT

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_mO(d_Gt(u)³) time using O(d_Gt(u²) spaces. We also show that the average degree d_Ge (u) is usually a constant, which is at most 6. Our result is first developed for stationary network and then extended to mobile network.

REFERENCES

• 1: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 2: E. Kranakis, H. Singh, and J. Urmtia. Compass routing on geometric networks. 2000.
• 3: Philip Klein , Satish Rao , Monika Rauch , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.27-37, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195092]
• 4: x.Y. Li, P.J. Wan, Y. Wang, Power efficient and sparse spanner for wireless ad hoe networks, ICCCN, 2001.
• 5: C. Perkins. Ad-hoe on-demand distance vector routing. In MILCOM '97, Nov. 1997.
• 6: S. Ramanathan , Martha Steenstrup, A survey of routing techniques for mobile communications networks, Mobile Networks and Applications, v.1 n.2, p.89-104, Oct. 1996 [doi>10.1007/BF01193330]
• 7: v. Rodoplu and T. H. Meng. Minimum energy mobile wireless networks. In Proceedings of the 1998 IEEE International Conference on Communications, ICC'98, volume 3, 1998.
• 8: E. Royer and C. Toh. A review of current routing protocols for ad-hoe mobile wireless networks. IEEE Personal Communications, Apr. 1999.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Algorithms