Fault-Tolerant Placement of Additional Mesh Nodes in Rural Wireless Mesh Networks: A Minimum Steiner Tree Based Centre of Mass With Bounded Edge Length

Abstract

Wireless mesh networks are presented as an attractive solution to reduce the digital divide between rural and developed areas. In a multi-hop fashion, they can cover larger spaces. However, their planning is subject to many constraints including robustness. In fact, the failure of a node may result in the partitioning of the network. The robustness of the network is therefore achieved by carefully placing additional nodes. This work tackles the problem of additional nodes minimization when planning bi and tri-connectivity from a given network. We propose a vertex augmentation approach inspired by the placement of Steiner points. The idea is to incrementally determine cut vertices and bridges in the network and to carefully place additional nodes to ensure connectivity, bi and tri-connectivity. The approach relies on an algorithm using the centre of mass of the blocks derived after the partitioning of the network. The proposed approach has been compared to a modified version of a former approach based on the Minimum Steiner Tree. The different experiments carried out show the competitiveness of the proposed approach to connect, bi-connect, and tri-connect the wireless mesh networks.