Optimal hierarchical energy efficient design for MANETs

ABSTRACT

Due to the growing interest in mobile wireless Ad-Hoc networks' (MANETs) applications, researchers have proposed many routing protocols that differ in their objective. Energy efficiency and scalability are two of the most important objectives. In our previous work, we proposed a fuzzy based hierarchical energy efficient routing protocol (FEER) for large scale MANETs that aims to maximize the network's lifetime and increase its scalability. The problem has two parts: the clustering part and the routing part. In the first part, we cluster the network into two levels of hierarchy (cluster heads and normal nodes), connect the cluster heads (backbone) with each other, and connect the normal nodes to the cluster heads while maximizing the network lifetime. In the second part, we design energy efficient routing that uses the hierarchical structure. We call the first part, the energy efficient clustering problem (EEC). In this paper, we formulate three variations of EEC as integer linear programming (ILP) problems. We first consider a network with a fully connected backbone (EEC-FCB). Then, we relax the fully connected constraint and consider a network with a connected backbone (EEC-CB), not necessarily fully connected. Finally, we consider a more reliable network (EEC-R) by electing a backup cluster head for each cluster.

REFERENCES

• 1: Gupta, P. and Kumar, P. R. The Capacity of Wireless Networks. IEEE Transactions on Information Theory, IT-46, 2 (March 2000), 388--404.
• 2: Gupta, P., Gray, R., and Kumar, P. R. An Experimental Scaling Law for Ad Hoc Networks. (May 16, 2001), http://black1.csl.uiuc.edu/~prkumar/
• 3: El-Hajj, W., Kountanis, D., Al-Fuqaha, A., and Guizani, M. A Fuzzy-Based Hierarchical Energy Efficient Routing Protocol for Large Scale Mobile Ad Hoc Networks (FEER). IEEE International Conference on Communication (ICC'06), (Istanbul, Turkey, June 11--15, 2006).
• 4: Chang, J.-H. and Tassiulas, L. Routing for maximum system lifetime in wireless ad-hoc networks. In Proc. of 37th Annual Allerton Conference on Communication, Control, and Computing, (September 1999).
• 5: Chang, J.-H. and Tassiulas, L. Energy conserving routing in wireless ad-hoc networks. In Proc. of IEEE INFOCOM, (March 2000), 22--31.
• 6: Jae-Hwan Chang , Leandros Tassiulas, Fast Approximate Algorithms for Maximum Lifetime Routing in Wireless Ad-hoc Networks, Proceedings of the IFIP-TC6 / European Commission International Conference on Broadband Communications, High Performance Networking, and Performance of Communication Networks, p.702-713, May 14-19, 2000
• 7: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 8: Sankar, A. and Liu, Z. Maximum lifetime routing in wireless ad-hoc networks. In Proc. of IEEE INFOCOM, (2004).
• 9: Lin, CR and Gerla, M. Adaptive Clustering for Mobile Wireless Networks. IEEE JSAC, 15, (September 1997), 1265--1275.
• 10: Alan D. Amis , Ravi Prakash, Load-Balancing Clusters in Wireless Ad Hoc Networks, Proceedings of the 3rd IEEE Symposium on Application-Specific Systems and Software Engineering Technology (ASSET'00), p.25, March 24-25, 2000
• 11: Ryu, J.-H., Song, S., and Cho, D.-H. New Clustering Schemes for Energy Conservation in Two-Tiered Mobile Ad-Hoc Networks. IEEE International Conference on Communication (ICC'01), 3, (June 2001), 862--66.
• 12: Wu, J. On Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks. Journal of Communication and Networks, 4, 1, (March 2002), 59--70.
• 13: Yu, J. Y. and Chong, P. H. J. 3hBAC (3-hop between Adjacent Clusterheads): a Novel Non-overlapping Clustering Algorithm for Mobile Ad Hoc Networks. In Proc. of IEEE Pacrim'03, 1, (August 2003), 318--21.
• 14: Kawadia, V. and Kumar, P. R. Power control and clustering in ad hoc networks. In Proc. of IEEE INFOCOM, (2003).
• 15: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Design, Performance, Theory

Keywords:
energy efficiency, hierarchical design, integer linear programming, mobile wireless ad-hoc network