Topology management in ad hoc networks

ABSTRACT

The efficiency of a communication network depends not only on its control protocols, but also on its topology. We propose a distributed topology management algorithm that constructs and maintains a backbone topology based on a minimal dominating set (MDS) of the network. According to this algorithm, each node determines the membership in the MDS for itself and its one-hop neighbors based on two-hop neighbor information that is disseminated among neighboring nodes. The algorithm then ensures that the members of the MDS are connected into a connected dominating set (CDS), which can be used to form the backbone infrastructure of the communication network for such purposes as routing. The correctness of the algorithm is proven, and the efficiency is compared with other topology management heuristics using simulations. Our algorithm shows better behavior and higher stability in ad hoc networks than prior algorithms.

REFERENCES

• 1: A. Amis, R. Prakash, T. Vuong, and D.T. Huynh. MaxMin D-Cluster Formation in Wireless Ad Hoc Networks. In Proceedings of IEEE Conference on Computer Communications (INFOCOM), Mar. 1999.
• 2: 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
• 3: D.J. Baker and A. Ephremides. The architectural organization of a mobile radio network via a distributed algorithm. IEEE Transactions on Communications, COM-29(11):1694--701, Nov. 1981.
• 4: S. Banerjee and S. Khuller. A Clustering Scheme for Hierarchical Control in Multi-hop Wireless Networks. In Proceedings of IEEE Conference on Computer Communications (INFOCOM), Anchorage, Alaska, Apr. 2001.
• 5: Lichun Bao , J. J. Garcia-Luna-Aceves, A new approach to channel access scheduling for Ad Hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.210-221, July 2001, Rome, Italy [doi>10.1145/381677.381698]
• 6: Lichun Bao , J.J. Garcia-Luna-Aceves, Transmission scheduling in ad hoc networks with directional antennas, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570652]
• 7: P. Basu, N. Khan, and T. D.C. Little. A Mobility Based Metric for Clustering in Mobile Ad Hoc Networks. In International Workshop on Wireless Networks and Mobile Computing (WNMC2001), Scottsdale, Arizona, Apr. 16--19 2001.
• 8: 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]
• 9: C.C. Chiang, H.K. Wu, W. Liu, and M. Gerla. Routing in clustered multihop, mobile wireless networks with fading channel. In IEEE Singapore International Conference on Networks SICON'97, pages 197--211, Singapore, Apr. 14--17 1997.
• 10: T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, a. Qayyum, and L. Viennot. Optimized Link State Routing Protocol. In IEEE INMIC, Pakistan, 2001.
• 11: A. Ephremides, J. E. Wieselthier, and D. J. Baker. A design concept for reliable mobile radio networks with frequency hopping signaling. Proc. of IEEE, 75(1):56--73, Jan. 1987.
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: 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]
• 14: S. Guha and S. Khuller. Approximation algorithms for connected dominating sets. Algorithmica, 20, (no.4):374--87, Apr. 1998. Springer-Verlag.
• 15: L. Hu. Topology control for multihop packet radio networks. IEEE Transactions on Communications, 41(10):1474--81, Oct. 1993.
• 16: L. Jia, R. Rajaraman, and T. Suel. An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In Twentieth ACM Symposium on Principles of Distributed Computing PODC'01, Newport, Rhode Island, Aug. 26--29 2001.
• 17: P. Krishna , N. H. Vaidya , M. Chatterjee , D. K. Pradhan, A cluster-based approach for routing in dynamic networks, ACM SIGCOMM Computer Communication Review, v.27 n.2, p.49-64, Apr. 1997 [doi>10.1145/263876.263885]
• 18: L. Li, V. Bahl, Y.M. Wang, and R. Wattenhofer. Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks. In Proceedings of IEEE Conference on Computer Communications (INFOCOM), Apr. 2001.
• 19: C.R. Lin and M. Gerla. Adaptive Clustering for Mobile Wireless Networks. IEEE Journal on Selected Areas in Communications, 15(7):1265--75, Sep. 1997.
• 20: S. Narayanaswamy, V. Kawadia, R. S. Sreenivas, and P. R. Kumar. Power Control in Ad-Hoc Networks: Theory, Architecture, Algorithm and Implementation of the COMPOW Protocol. In Proceedings of the European Wireless Conference -- Next Generation Wireless Networks: Technologies, Protocols, Services and Applications, pages 156--162, Florence, Italy, Feb. 25--28 2002.
• 21: Ravi Prakash, Unidirectional links prove costly in wireless ad hoc networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.15-22, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313263]
• 22: R. Ramanathan and R. Rosales-Hain. Topology Control of Multihop Wireless Networks using Transmit Power Adjustment. In Proceedings of IEEE Conference on Computer Communications (INFOCOM), page N.A. IEEE, Mar. 26--30 2000.
• 23: Ram Ramanathan , Martha Steenstrup, Hierarchically-organized, multihop mobile wireless networks for quality-of-service support, Mobile Networks and Applications, v.3 n.1, p.101-119, June 1998 [doi>10.1023/A:1019148009641]
• 24: P. Sinha, R. Sivakumar, and V. Bharghavan. Enhancing ad hoc routing with dynamic virtual infrastructures. In Proceedings of IEEE Conference on Computer Communications (INFOCOM), pages 1763--72, Anchorage, AK, USA, Apr. 22--26 2001.
• 25: R. Sivakumar, P. Sinha, and V. Bharghavan. CEDAR: a core-extraction distributed ad hoc routing algorithm. IEEE Journal on Selected Areas in Communications, 17(8):1454--65, Aug. 1999.
• 26: H. Takagi and L. Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications, 32(3):246--57, Mar. 1984.

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

Keywords:
ad hoc networks, connected dominating set, minimum dominating set