Fault tolerant deployment and topology control in wirelessad hocnetworks
Xiang‐Yang Li, Peng‐Jun Wan, Yu Wang, Chih‐Wei Yi · Wireless Communications and Mobile Computing · 2004
Abstract We consider a large‐scale of wirelessad hocnetworks whose nodes are distributed randomly in a two‐dimensional region Ω (more specifically, a unit square). Givennwireless nodesV, each with transmission rangern, the wireless networks are often modeled by graphG(V,rn) in which two nodes are connected if and only if their Euclidean distance is no more thanrn. We first consider how to relate the transmission range with the number of nodes in a fixed area such that the resulted network can sustainkfault nodes in its neighborhood with high probability when all nodes have the same transmission range. We show that, for a unit‐area square region Ω, the probability that the networkG(V,rn) isk‐connected is at least${\rm e}^{-{\rm e}^{-\alpha}}$ when the transmission radiusrnsatisfies$n \pi r_n^2 \ge {\rm ln}\ n \,+ (2k - 3) {\rm ln}\, {\rm ln}\, n - 2 \,{\rm ln}(k - 1)! + 2 \alpha \ {\rm for} \, k >\,1$ andnsufficiently large. This result also applies to mobile networks when the moving of wireless nodes always generates randomly distributed positions. We also conduct extensive simulations to study the practical transmission range to achieve certain probability the network beingk‐connectivity, when the number of nodesnis not large enough. The relation between the minimum node degree and the connectivity of graphG(V,r) is also studied. Setting the transmission range of all nodes tornguarantees thek‐connectivity with high probability, but some nodes may have excessive number of neighbours in the graphG(V,rn). We then present a localized method to construct a subgraph of the network topologyG(V,rn) such that the resulting subgraph is stillk‐connected but with much fewer communication links maintained. We show that the constructed topology has onlyO(k · n) links and is a length spanner. Here a graphH ⊆ Gis spanner for graphG, if for any two nodes, the length of the shortest path connecting them inHis no more than a small constant factor of the length of the shortest path connecting them inG. Finally, we conduct some simulations to study the practical transmission range to achieve certain probability ofk‐connected whennis not large enough. Copyright © 2004 John Wiley & Sons, Ltd.