Designing fault tolerant ad hoc networks

Wireless ad hoc networks, where mobile stations construct networks by mutual multi hop relaying, have been widely discussed, but its survivability has not been studied much. Most of the survivability researches on wireless networks are on cellular networks with fixed base stations, using models similar to wired networks. Survivable ad hoc network design, however, is different from the wired networks in fundamental aspects such as location dependence and broadcast feature. In this paper, we propose a platform and a network design scheme to incorporate these features. We first propose hexagonal grid, a novel platform for survivable ad hoc network design. We then set a problem of survivable ad hoc network design to minimize the relay while satisfying required survivability. We next propose enclosure algorithm, a novel heuristic algorithm to solve the problem. The complexity of the proposed algorithm is much smaller than a conventional combinatorial scheme. We then extend the proposed scheme to multilayer case, to obtain two-layer survivable network