Distributed low-cost backbone formation for wireless ad hoc networks

ABSTRACT

Backbone has been used extensively in various aspects (e.g., routing, route maintenance, broadcast, scheduling) for wireless networks. Previous methods are mostly designed to minimize the backbone size. However, in many applications, it is desirable to construct a backbone with small cost when each wireless node has a cost of being in the backbone. In this paper, we first show that previous methods specifically designed to minimize the backbone size may produce a backbone with a large cost. We then propose an efficient distributed method to construct a weighted sparse backbone with low cost. We prove that the total cost of the constructed backbone is within a small constant factor of the optimum for homogeneous networks when either the nodes' costs are smooth or the network maximum node degree is bounded. We also show that with a small modification the constructed backbone is efficient for unicast: the total cost (or hop) of the least cost (or hop) path connecting any two nodes using backbone is no more than 3 (or 4) times of the least cost (or hop) path in the original communication graph. As a side product, we give an efficient overlay based multicast structure whose total cost is no more than 10 times of the minimum when the network is modeled by UDG. Our theoretical results are corroborated by our simulation studies.

REFERENCES

• 1: Khaled Alzoubi , Xiang-Yang Li , Yu Wang , Peng-Jun Wan , Ophir Frieder, Geometric Spanners for Wireless Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.408-421, April 2003 [doi>10.1109/TPDS.2003.1195412]
• 2: 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]
• 3: K. Alzoubi , P.-J. Wan , O. Frieder, New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.297, January 07-10, 2002
• 4: Baker, D., Ephremides, A., and Flynn, J. A. The Design and Simulation of a Mobile Radio Network with Distributed Control. IEEE Journal on Selected Areas in Comm. (1984), 226--237.
• 5: Baker, D. J., and Ephremides, A. The Architectural Organization of a Mobile Radio Network via a Distributed Algorithm. IEEE Transactions on Communications COM-29, 11 (November 1981), 1694--1701.
• 6: Lichun Bao , J. J. Garcia-Luna-Aceves, Topology management in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778432]
• 7: Stefano Basagni, Distributed Clustering for Ad Hoc Networks, Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), p.310, June 23-25, 1999
• 8: Basagni, S. Finding a maximal weighted independent set in wireless networks. Telecommunication Systems, Special Issue on Mobile Computing and Wireless Networks 18, 1/3 (September 2001), 155--168.
• 9: Basagni, S., Mastrogiovanni, M., and Petrioli, C. A performance comparison of protocols for clustering and backbone formation in large scale ad hoc networks. In 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS) (2004).
• 10: Christian Bettstetter , Roland Krausser, Scenario-based stability anlysis of the distributed mobility-adaptive clustering (DMAC) algorithm, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501445.501448]
• 11: Cǎlinescu, G. Computing 2-hop neighborhoods in ad hoc wireless networks. In AdHoc-Now 03 (2003).
• 12: Mainak Chatterjee , Sajal K. Das , Damla Turgut, WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks, Cluster Computing, v.5 n.2, p.193-204, April 2002 [doi>10.1023/A:1013941929408]
• 13: G. Chen , F. Nocetti , J. Gonzalez , I. Stojmenovic, Connectivity-Based k-Hop Clustering in Wireless Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 7, p.188.3, January 07-10, 2002
• 14: Chvátal, V. A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4, 3 (1979), 233--235.
• 15: Das, B., and Bharghavan, V. Routing in ad-hoc networks using minimum connected dominating sets. In 1997 IEEE Intern. Conference on on Communications (ICC'97) (1997), vol. 1, pp. 376--380.
• 16: Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
• 17: 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]
• 18: 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]
• 19: Guha, S., and Khuller, S. Approximation algorithms for connected dominating sets. Algorithmica 20, 4 (1998), 374--387.
• 20: Sudipto Guha , Samir Khuller, Improved methods for approximating node weighted Steiner trees and connected dominating sets, Information and Computation, v.150 n.1, p.57-74, April 10, 1999 [doi>10.1006/inco.1998.2754]
• 21: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 22: Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Journal of Algorithms, v.26 n.2, p.238-274, feb. 1998 [doi>10.1006/jagm.1997.0903]
• 23: Oleg Kachirski , Ratan Guha, Intrusion Detection Using Mobile Agents in Wireless Ad Hoc Networks, Proceedings of the IEEE Workshop on Knowledge Media Networking, p.153, July 10-12, 2002
• 24: Kozat, U. C., Kondylis, G., Ryu, B., and Marina, M. Virtual dynamic backbone for mobile ad hoc networks. In Proceedings of IEEE ICC 2001 (2001).
• 25: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, What cannot be computed locally!, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011811]
• 26: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Initializing newly deployed ad hoc and sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023746]
• 27: 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]
• 28: Xiang-Yang Li , Yu Wang, Simple heuristics and PTASs for intersection graphs in wireless ad hoc networks, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570819]
• 29: Li, X.-Y., Wang, Y., Wan, P.-J., Song, W.-Z., and Frieder, O. Localized low weight graph and its applications in wireless ad hoc networks. In IEEE INFOCOM 2004 (2004).
• 30: Liang, B., and Haas, Z. J. Virtual backbone generation and maintenance in ad hoc network mobility management. In Proc. of 19th IEEE INFOCOM (2000), vol. 3, pp. 1293--1302.
• 31: Lin, C. R., and Gerla, M. Adaptive clustering for mobile wireless networks. IEEE Journal of Selected Areas in Communications 15, 7 (1997), 1265--1275.
• 32: Liu, H., and Gupta, R. Selective backbone construction for topology control. In 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS) (2004).
• 33: A Dynamic Trust Model for Mobile Ad Hoc Networks, Proceedings of the 10th IEEE International Workshop on Future Trends of Distributed Computing Systems (FTDCS'04), p.80-85, May 26-28, 2004
• 34: Min, M., Wang, F., Du, D.-Z., and Pardalos, P. M. A reliable virtual backbone scheme in mobile ad-hoc networks. In 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS) (2004).
• 35: The Clade Vertebrata: Spines and Routing in Ad Hoc Networks, Proceedings of the Third IEEE Symposium on Computers & Communications, p.599, June 30-July 02, 1998
• 36: Smaragdakis, G., Matta, I., and Bestavros, A. SEP: A stable election protocol for clustered heterogeneous wireless sensor networks. In Second International Workshop on Sensor and Actor Network Protocols and Applications (2004).
• 37: Ivan Stojmenovic , Mahtab Seddigh , Jovisa Zunic, Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.14-25, January 2002 [doi>10.1109/71.980024]
• 38: Turgut, D., Das, S., Elmasri, R., and Turgut, B. Optimizing clustering algorithm in mobile ad hoc networks using genetic algorithmic approach. In IEEE GLOBECOM 2002 (2002).
• 39: Wan, P.-J., Alzoubi, K. M., and Frieder, O. Distributed construction of connected dominating set in wireless ad hoc networks. In INFOCOM (2002).
• 40: Wan, P.-J., Li, X.-Y., and Song, W.-Z. Theoretically good distributed OVSF-CDMA code assignment in wireless ad hoc networks, 2004. Submitted for publication.
• 41: Wu, J., and Li, H. A dominating-set-based routing scheme in ad hoc wireless networks. Telecommunication Systems Journal 3 (2001), 63--84.
• 42: Zheng, R., He, G., Gupta, I., and Sha, L. Time idexing in sensor networks. In 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS) (2004).

INDEX TERMS

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

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Network problems

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
clustering, connected dominating set, localized algorithm, weighted, wireless ad hoc/sensor networks