The K-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks

ABSTRACT

We propose an approach to topology control based on the principle of maintaining the number of neighbors of every node equal to or slightly below a specific value k. The approach enforces symmetry on the resulting communication graph, thereby easing the operation of higher layer protocols. To evaluate the performance of our approach, we estimate the value of k that guarantees connectivity of the communication graph with high probability. We then define k-Neigh, a fully distributed, asynchronous, and localized protocol that follows the above approach and uses distance estimation. We prove that k-Neigh terminates at every node after a total of 2n messages have been exchanged (with n nodes in the network) and within strictly bounded time. Finally, we present simulations results which show that our approach is about 20% more energy-efficient than a widely-studied existing protocol.

REFERENCES

• 1: M. Bahramgiri, M. Hajiaghayi, V.S. Mirrokni, "Fault-tolerant ad 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks", Proc. IEEE Int. Conference on Computer Communications and Networks, pp. 392--397, 2002.
• 2: Lichun Bao , J. J. Garcia-Luna-Aceves, Channel access scheduling in Ad Hoc networks with unidirectional links, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.9-18, July 2001, Rome, Italy [doi>10.1145/381448.381450]
• 3: Douglas M. Blough , Mauro Leoncini , Giovanni Resta , Paolo Santi, On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.71-82, August 25-30, 2002
• 4: D.M. Blough, M. Leoncini, G. Resta, P. Santi, "The k-Neighbors Protocol for Symmetric Topology Control in Ad Hoc Networks", Tech. Rep. IIT-TR-23/2002, Istituto di Informatica e Telematica, Pisa -- Italy, Dec. 2002.
• 5: S.A. Borbash, E.H. Jennings, "Distributed Topology Control Algorithm for Multihop Wireless Networks", Proc. IEEE Int. Joint Conference on Neural Networks, pp. 355--360, 2002.
• 6: J. Bruck, M. Franceschetti, L. Schulman, "Microcellular Systems, Random Walks, and Wave Propagation", Proc. IEEE Symposium on Antennas and Propagation, pp. 220--223, 2002.
• 7: J. Chang, L. Tassiulas, "Energy Conserving Routing in Wireless Ad Hoc Networks", Proc. IEEE INFOCOM 2000, pp. 22--31, 2000.
• 8: Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri, Hardness Results for the Power Range Assignmet Problem in Packet Radio Networks, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.197-208, August 08-11, 1999
• 9: L. Girod, D. Estrin, "Robust Range Estimation Using Acoustic and Multimodal Sensing", IEEE/RSJ International Conference on Intelligent Robots and Systems, 2001.
• 10: P. Gupta, P.R. Kumar, "Critical Power for Asymptotic Connectivity in Wireless Networks", Stochastic Analysis, Control, Optimization and Applications, Birkhauser, Boston, pp. 547--566, 1998.
• 11: Z. Huang, C. Shen, C. Srisathapornphat, C. Jaikaeo, "Topology Control for Ad Hoc Networks with Directional Antennas", Proc. IEEE Int. Conference on Computer Communications and Networks, pp. 16--21, 2002.
• 12: Eun-Sun Jung , Nitin H. Vaidya, A power control MAC protocol for ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570651]
• 13: V. Kawadia, P.R. Kumar, "Power Control and Clustering in Ad Hoc Networks", to appear in Proc. IEEE Infocom 03, 2003.
• 14: Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Power consumption in packet radio networks, Theoretical Computer Science, v.243 n.1-2, p.289-305, July 28, 2000 [doi>10.1016/S0304-3975(98)00223-0]
• 15: Ronny Krashinsky , Hari Balakrishnan, Minimizing energy for wireless web access with bounded slowdown, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570660]
• 16: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.264-273, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384043]
• 17: J. Liu, B. Li, "MobileGrid: Capacity-aware Topology Control in Mobile Ad Hoc Networks", Proc. IEEE Int. Conference on Computer Communications and Networks, pp. 570--574, 2002.
• 18: Mahesh K. Marina , Samir R. Das, Routing performance in the presence of unidirectional links in multihop 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.513803]
• 19: S. Narayanaswamy, V. Kawadia, R.S. Sreenivas, P.R. Kumar, "Power Control in Ad Hoc Networks: Theory, Architecture, Algorithm and Implementation of the COMPOW Protocol", Proc. European Wireless 2002, pp. 156--162, 2002.
• 20: Kaveh Pahlavan , Allen H. Levesque, Wireless information networks, Wiley-Interscience, New York, NY, 1995
• 21: M.R. Pearlman, Z.J. Haas, B.P. Manvell, "Using Multi-Hop Acknowledgements to Discover and Reliably Communicate over Unidirectional Links in Ad Hoc Networks", Proc. Wireless Communications and Networking Conference (WCNC), pp. 532--537, 2000.
• 22: Ravi Prakash, A routing algorithm for wireless ad hoc networks with unidirectional links, Wireless Networks, v.7 n.6, p.617-625, November 2001 [doi>10.1023/A:1012371402221]
• 23: R. Ramanathan, R. Rosales-Hain, "Topology Control of Multihop Wireless Networks using Transmit Power Adjustment", Proc. IEEE Infocom 2000, pp. 404--413, 2000.
• 24: V. Ramasubramanian, R. Chandra, D. Mosse, "Providing a Bidirectional Abstraction for Unidirectional Ad Hoc Networks", Proc. IEEE Infocom 02, pp. 1258--1267, 2002.
• 25: V. Rodoplu, T.H. Meng, "Minimum Energy Mobile Wireless Networks", IEEE Journal Selected Areas in Comm., Vol. 17, n. 8, pp. 1333--1344, 1999.
• 26: M. Sanchez, P. Manzoni, Z.J. Haas, "Determination of Critical Transmitting Range in Ad Hoc Networks", Proc. Multiaccess, Mobility and Teletraffic for Wireless Communications Conference, 1999.
• 27: Paolo Santi , Douglas M. Blough, The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.1, p.25-39, January 2003 [doi>10.1109/TMC.2003.1195149]
• 28: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• 29: Sasha Slijepcevic , Seapahn Megerian , Miodrag Potkonjak, Location errors in wireless embedded sensor networks: sources, models, and effects on applications, ACM SIGMOBILE Mobile Computing and Communications Review, v.6 n.3, July 2002 [doi>10.1145/581291.581301]
• 30: R. Wattenhofer, L. Li, P. Bahl, Y. Wang, "Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks", Proc. IEEE Infocom 2001, pp. 1388--1397, 2001.
• 31: F. Xue, P.R. Kumar, "The Number of Neighbors Needed for Connectivity of Wireless Networks", internet draft, available at http://decision.csl.uiuc.edu/prkumar/postscript_files.html#Wireless%20Networks.

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
connectivity, energy consumption, symmetric range assignment, topology control, wireless ad hoc networks