On the node-scheduling approach to topology control in ad hoc networks

ABSTRACT

In this paper, we analyze the node scheduling approach of topology control in the context of reliable packet delivery. In node scheduling, only a minimum set of nodes needed for routing purposes (usually determined by a minimum connected dominating set, MCDS) are kept active. However, a very low density resulting from switching off nodes can adversely affect the performance of data delivery due to three factors. First, our analysis shows that at low density, the average path length increases by a factor more than previously thought. Second, protocols such as the Hop-By-Hop Broadcast (HHB) reliability scheme (which relies on high network degree for optimum performance) suffer. Third, with limited buffers at nodes, the overhead is more pronounced to the extent of making the network unstable. Using probabilistic models, we derive the relationship between network density and overhead based on the above factors and find the density conditions for minimum power consumption. We also propose a, fully distributed and message-optimal node scheduling algorithm with a constant approximation bound based on the concept of Virtual Connected Dominating Sets. The scheme can asymptotically achieve optimal density conditions while adapting to different network parameters.

REFERENCES

• 1: L. Kleinrock and J. Silvester, "Optimum Transmission Radii for Packet Radio Networks, or why Six is a Magic Number." IEEE National Telecommunications Conference, 1978.
• 2: Takagi, H. and L. Kleinrock, "Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals" , IEEE Trans. on Communications, Vol. COM-32, No. 3, pp. 246--257, March 1984.
• 3: Suresh Singh , C. S. Raghavendra, PAMAS—power aware multi-access protocol with signalling for ad hoc networks, ACM SIGCOMM Computer Communication Review, v.28 n.3, p.5-26, July 1998 [doi>10.1145/293927.293928]
• 4: Suman Banerjee , Archan Misra, Minimum energy paths for reliable communication in multi-hop wireless networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513818]
• 5: Quantitative Analysis of Transmission Power Control in Wireless Ad-hoc Networks, Proceedings of the 2002 International Conference on Parallel Processing Workshops, p.56, August 18-21, 2002
• 6: S. Agarwal, S. V. Krishnamurthy, R. H. Katz, S. K. Dao, "Distributed Power Control in Ad-hoc Wireless Networks" Personal Indoor Mobile Radio Conference Oct. 2001
• 7: Calinescu, S. Kapoor, A. Olshevsky, and A. Zelikovsky, "NetworkLifetime and Power Assignment in Ad-Hoc Wireless Networks", in ESA 2003.
• 8: I. Ali, S. Bansal, R.Gupta, A. Misra, R. Shorey and A. Razdan, "Energy Efficiency and Throughput for TCP Traffic in Multi-Hop Wireless Networks", Proceedings of IEEE INFOCOM 2002, June 2002, New York City, USA.
• 9: Li (Erran) Li , Prasun Sinha, Throughput and energy efficiency in topology-controlled multi-hop wireless sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941369]
• 10: B. Das, V Bhargavan, "Routing in Ad Hoc Networks Using Minimum connected dominating Sets". IEEE International Conference on Communications (ICC '97), June, 1997.
• 11: A. Ephremides, J.E. Wieselthier, and D.J. Baker, "A design concept for trliable mobile radio networks with frequency hopping signaling." Proc. of IEEE, 75, 1 (01/87) 56--73.
• 12: Mario Gerla , Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, v.1 n.3, p.255-265, 1995 [doi>10.1007/BF01200845]
• 13: Sudipto Guha , Samir Khuller, Approximation Algorithms for Connected Dominating Sets, Proceedings of the Fourth Annual European Symposium on Algorithms, p.179-193, September 25-27, 1996
• 14: P. Sinha, R. Sivakumar and V. Bharghavan, "CEDAR: a Core-Extraction Distributed Ad hoc Routing Algorithm" In proceedings of IEEE Infocom 1999.
• 15: V. Rodoplu and T.H.Meng, "Minimum Energy Mobile Wireless Networks", IEEE JSAC, Vol. 17, August 1999.
• 16: S. Bannerjee, S. Khuller, "A Clustering Scheme for Hierarchical Control in Wireless Networks", In Proceedings of IEEE INFOCOM 2001.
• 17: J. Wu, F. Dai, M. Gao, I. Stojmenovic, "On Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks", Journal of Communications and Networks, Vo. 4, No.1, March 2002
• 18: Di Tian , Nicolas D. Georganas, A coverage-preserving node scheduling scheme for large wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570744]
• 19: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 20: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 21: S. Bandhopadhyay, and E. J. Coyle, "An Energy Efficient Hierarchical Clustering algorithm for Wireless Sensor Networks", IEEE INFOCOM 2003.
• 22: S. G. Foss and S. A. Zuyev, "On Voronoi Aggregative Process Related to a Bivariate Poisson Process", Advances in Applied Probability, Vol. 28 no. 4, pp 965--981, 1996
• 23: Marathe, M. V., Breu, H., Hunt III, H. B., Ravi, S. S., and Rosenkrantz (1995), D. J. (1995), ``Simple heuristics for unit disk graphs'', Networks 25, 59--68.
• 24: I. Kang and R. Poovendran, "A Novel Power-Efficient Broadcast Routing Algorithm Exploiting Broadcast Efficiency with Omnidirectional and Directional Antenna", IEEE -VTC, Oct 6-9, 2003, Orlando, FL
• 25: Anand Srinivas , Eytan Modiano, Minimum energy disjoint path routing in wireless ad-hoc networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938999]
• 26: Jeffrey E. Wieselthier , Gam D. Nguyen , Anthony Ephremides, Algorithms for energy-efficient multicasting in static ad hoc wireless networks, Mobile Networks and Applications, v.6 n.3, p.251-263, June 2001 [doi>10.1023/A:1011478717164]
• 27: Budhaditya Deb , Sudeept Bhatnagar , Badri Nath, Information assurance in sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941373]
• 28: B. Deb, S. Bhatnagar, B. Nath, "Multi-Resolution State Retrieval Sensor Networks", Ist IEEE Int. Workshop on Sensor Network Protocols and Applications May 11, 2003
• 29: K. Arisha, M. Youssef and M. Younis, "Energy-aware TDMA-based MAC for Sensor Networks", In Proc. of IEEE IMPACCT, 2002
• 30: Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Message-optimal connected dominating sets in mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513820]
• 31: P.J. Wan, K. M. Alzoubi, O. Frieder, "Distributed Construction of Connected Dominating Sets in ad hoc wireless networks", IEEE INFOCOM 2002
• 32: N. Alon and J. Spencer, "The Probabilistic Method", John Wiley as part of the Inter-science Series in Discrete Mathematics and Optimization, 2000
• 33: Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.25-32, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872040]
• 34: Thomas Moscibroda , Roger Wattenhofer, Maximizing the Lifetime of Dominating Sets, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 12, p.242.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.276]
• 35: Jie Gao , Leonidas Guibas , John Hershberger , Li Zhang , An Zhu, Discrete mobile centers, Proceedings of the seventeenth annual symposium on Computational geometry, p.188-196, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378666]
• 36: Jerrold W. Grossman, Dominating sets whose closed stars form spanning trees, Discrete Mathematics, v.169 n.1-3, p.83-94, May 15, 1997 [doi>10.1016/0012-365X(95)00334-S]
• 37: P. J. Shweltzer, S.S. Lam.,"Buffer overflow in a store and forward network node", IBM J, Res. Dev. 1976

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance, Reliability, Theory

Keywords:
ad-hoc networks, minimum virtual dominating sets, node scheduling, reliable packet delivery, topology control