Fault tolerant deployment and topology control in wireless networks

ABSTRACT

This paper investigate fault tolerance for wireless ad hoc networks. We consider a large-scale of wireless networks whose nodes are distributed randomly in a unit-area square region. Given n wireless nodes V, each with transmission range r_n, the wireless networks are often modeled by graph G(V,r_n) in which two nodes are connected if their Euclidean distance is no more than r_n.We first consider how the transmission range is related with the number of nodes in a fixed area such that the resulted network can sustain k fault nodes with high probability. We show that, for a unit-area square region, the probability that the network G(V,rn) is (k+1)-connected is at least e^-e-α when the transmission radius r_n satisfies n π r_n² ≥ ln n + (2k-1) ln ln n -2ln k! + 2α for k>0 and n sufficiently large. This result also applies to mobile networks when the moving of wireless nodes always generates randomly distributed positions. Our simulations show that n should be larger than 500 if k=2 or 3 and α = log n and n should be larger than 2500 if k=2 or 3 and α = log log n.We then present a localized method to control the network topology given a (k+1)-faults tolerant deployment G(V,r_n) of wireless nodes such that the resulting topology is still (k+1)-faults tolerant but with O(kn) communication links maintained. We show that the constructed topology is also a length spanner. Here a subgraph H is spanner of graph G, if for any two nodes, the length of the shortest path connecting them in H is no more than a small constant factor of the length of the shortest path connecting them in G.Finally, we conduct some simulations to study the practical transmission range to achieve certain probability of k-connected when n is not large enough.

REFERENCES

• 1: M. Bahramgiri, M.T. Hajiaghayi, and V.S. Mirrokni. Fault-tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks. In IEEE Int. Conf. on Computer Communications and Networks (ICCCN02), pages 392--397, 2002.
• 2: Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513811]
• 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: B. Bollobàs. Random Graphs. Cambridge University Press, 2001.
• 5: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, v.7 n.6, p.609-616, November 2001 [doi>10.1023/A:1012319418150]
• 6: S. Das, C. Perkins, and E. Royer. Performance comparison of two on-demand routing protocols for ad hoc networks. In Proceedings of IEEE INFOCOM, March 2000.
• 7: H. Dette and N. Henze. Some peculiar boundary phenomena for extremes of rth nearest neighbor links. Statistics & Probability Letters, 10:381--390, 1990.
• 8: A. Goldberg and S. Rao. Flows in undirected unit capacity networks. Technical Report 97-103, NEC Research Institute, Inc, 1997.
• 9: M. Grossglauser and D. Tse. Mobility increases the capacity of ad-hoc wireless networks. In INFOCOMM, vol. 3, pages 1360--1369, 2001.
• 10: P. Gupta and P. Kumar. Capacity of wireless networks. Technical report, University of Illinois, Urbana-Champaign, 1999.
• 11: P. Gupta and P. R. Kumar. Critical power for asymptotic connectivity in wireless networks. Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, W. M. McEneaney, G. Yin, and Q. Zhang (Eds.), 1998.
• 12: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.
• 13: 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]
• 14: X.-Y. Li, P.-J. Wan, and Y. Wang. Power efficient and sparse spanner for wireless ad hoc networks. In IEEE Int. Conf. on Computer Communications and Networks (ICCCN01), pages 564--567, 2001.
• 15: X.-Y. Li , P.-J. Wan , Y. Wang , O. Frieder, Sparse Power Efficient Topology for Wireless Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.296.2, January 07-10, 2002
• 16: T. Lukovszki. New Results on Geometric Spanners and Their Applications. PhD thesis, University of Paderborn, 1999.
• 17: D. Maltz, J. Broch, J. Jetcheva, and D. Johnson. The effects of on-demand behavior in routing protocols for multi-hop wireless ad hoc networks. IEEE JSAC, August 1999.
• 18: S. Narayanaswamy, V. Kawadia, R. Sreenivas, and P. Kumar. Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the COMPOW protocol. In European Wireless Conference, 2002.
• 19: O. D. Patrick. Connectivity in ad-hoc and hybrid networks.
• 20: M. Penrose. The longest edge of the random minimal spanning tree. Annals of Applied Probability, 7:340--361, 1997.
• 21: M. Penrose. Extremes for the minimal spanning tree on normally distributed points. Advances in Applied Probability, 30:628--639, 1998.
• 22: Mathew D. Penrose, On k-connectivity for a geometric random graph, Random Structures & Algorithms, v.15 n.2, p.145-164, Sept.1999 [doi>10.1002/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G]
• 23: M. Penrose. A strong law for the longest edge of the minimal spanning tree. Annals of Probability, 27:246--260, 1999.
• 24: C. Perkins. Ad-hoc on-demand distance vector routing. In MILCOM '97, Nov. 1997.
• 25: Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564602]
• 26: R. Ramanathan and R. Rosales-Hain. Topology control of multihop wireless networks using transmit power adjustment. In IEEE INFOCOM, 2000.
• 27: S. Ramanathan , Martha Steenstrup, A survey of routing techniques for mobile communications networks, Mobile Networks and Applications, v.1 n.2, p.89-104, Oct. 1996 [doi>10.1007/BF01193330]
• 28: E. Royer and C. Toh. A review of current routing protocols for ad-hoc mobile wireless networks. IEEE Personal Communications, Apr. 1999.
• 29: M. Sanchez, P. Manzoni, and Z. Haas. Determination of critical transmission range in ad-hoc networks. In Multiaccess, Mobility and Teletraffic for Wireless Communications (MMT'99), 1999.
• 30: Paolo Santi , Douglas M. Blough, An Evaluation of Connectivity in Mobile Wireless Ad Hoc Networks, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.89-102, June 23-26, 2002
• 31: Ivan Stojmenovic , Xu Lin, Loop-Free Hybrid Single-Path/Flooding Routing Algorithms with Guaranteed Delivery for Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.12 n.10, p.1023-1032, October 2001 [doi>10.1109/71.963415]
• 32: Yu Wang , Xiang-Yang Li, Distributed Spanner with Bounded Degree for Wireless Ad Hoc Networks, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.120, April 15-19, 2002
• 33: F. Xue and P. R. Kumar. The number of neighbors needed for connectivity of wireless networks.
• 34: A. C.-C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Computing, 11:721--736, 1982.
• 35: C.-W. Yi, P.-J. Wan, X.-Y. Li, and O. Frieder. Asymptotic distribution of the number of isolated nodes in wireless ad hoc networks with bernoulli nodes. In Proc. of IEEE WCNC, 2003.

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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Design, Theory

Keywords:
connectivity, fault tolerance, topology control, wireless ad hoc networks