A Resolving Set based Algorithm for Fault Identification in Wireless Mesh Networks

Xiaoding Wang (Fujian Normal University, China)

Li Xu (Fujian Normal University, China)

Shuming Zhou (Fujian Normal University, China)

Joseph K. Liu (Institute for Infocomm Research, Singapore)

Abstract: Abstract: Wireless Mesh Networks (WMNs) have emerged as a key technology for next-generation wireless networking. By adding some Long-ranged Links, a wireless mesh network turns into a complex network with the characteristic of small worlds. As a communication backbone, the high fault tolerance is a significant property in communication of WMNs. In this paper, we design a novel malfunctioned router detection algorithm, denoted by A-SRS, on searching resolving set based on private neighbor of dominating set. The A-SRS not only offers a highly efficient solution to position malfunctioned routers against intermitted communication that guarantees the availability of network services, but also pursues the minimum number of detecting routers due to limited resource of wireless mesh routers. We also explore the cardinality of resolving set and complexity of A-SRS based on the parameters: the minimum degree, the size of underlying graph G and the number of iterations. The algorithm enjoys better simulation results that it employs less detecting routers than the other strategies in the size of resolving set.

Keywords: dominating set, fault tolerance, resolving set, wireless mesh network

Categories: C.2.0