## 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,r_{n}) is (k + 1)-connected is at least e^{-e-α} when the transmission radius r_{n} satisfies nπr_{n}^{2} ≥ 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, 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.

Original language | English |
---|---|

Pages | 117-128 |

Number of pages | 12 |

State | Published - 19 Nov 2003 |

Event | MOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing - Annapolis, MD, United States Duration: 1 Jun 2003 → 3 Jun 2003 |

### Conference

Conference | MOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing |
---|---|

Country | United States |

City | Annapolis, MD |

Period | 1/06/03 → 3/06/03 |

## Keywords

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