Fault tolerant deployment and topology control in wireless networks

Xiang Yang Li*, Peng Jun Wan, Yu Wang, Tsì-Uí İk

*Corresponding author for this work

Research output: Contribution to conferencePaper

122 Scopus citations

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 rn, the wireless networks are often modeled by graph G(V,rn) in which two nodes are connected if their Euclidean distance is no more than rn. 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 rn satisfies nπrn2 ≥ ln n + (2k - 1)ln ln n - 2 ln 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, rn) 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.

Original languageEnglish
Pages117-128
Number of pages12
StatePublished - 19 Nov 2003
EventMOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing - Annapolis, MD, United States
Duration: 1 Jun 20033 Jun 2003

Conference

ConferenceMOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing
CountryUnited States
CityAnnapolis, MD
Period1/06/033/06/03

Keywords

  • Connectivity
  • Fault tolerance
  • Topology control
  • Wireless ad hoc networks

Fingerprint Dive into the research topics of 'Fault tolerant deployment and topology control in wireless networks'. Together they form a unique fingerprint.

  • Cite this

    Li, X. Y., Wan, P. J., Wang, Y., & İk, T-U. (2003). Fault tolerant deployment and topology control in wireless networks. 117-128. Paper presented at MOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Annapolis, MD, United States.