Fault-Tolerant Placement of Additional Mesh Nodes in Rural Wireless Mesh Networks: A Minimum Steiner Tree Based Centre of Mass With Bounded Edge Length
DOI:
https://doi.org/10.14738/tnc.94.10754Keywords:
Biconnectivity, Triconnectivity, Wireless Mesh Networks, Minimum Steiner Tree, Centre of Mass, Bounded Edge.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.
References
J.L.F.K. Ebongue, Rethinking Network Connectivity in Rural Communities in Cameroon, in: ArXiv Prepr. ArXiv150504449, Lilongwe, Malaw, 2015. https://arxiv.org/ftp/arxiv/papers/1505/1505.04449.pdf.
J.L.E.K. Fendji, J.M. Nlong, Rural wireless mesh network: A design methodology, ArXiv Prepr. ArXiv150408213. (2015).
I.F. Akyildiz, X. Wang, Wireless mesh networks, John Wiley & Sons, 2009.
S.D. Samo, J.L.E.K. Fendji, Evaluation of Energy Consumption of Proactive, Reactive, and Hybrid Routing Protocols in Wireless Mesh Networks Using 802.11 Standards, J. Comput. Commun. 06 (2018) 1–30. https://doi.org/10.4236/jcc.2018.64001.
K.P. Eswaran, R.E. Tarjan, Augmentation problems, SIAM J. Comput. 5 (1976) 653–665.
A. Rosenthal, A. Goldner, Smallest augmentations to biconnect a graph, SIAM J. Comput. 6 (1977) 55–66.
G. Calinescu, P.-J. Wan, Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networks, Mob. Netw. Appl. 11 (2006) 121–128.
R.E. Moraes, C.C. Ribeiro, Power optimization in ad hoc wireless network topology control with biconnectivity requirements, Comput. Oper. Res. 40 (2013) 3188–3196.
Y. Zhou, X. Cai, Node Placement in Wireless Sensor Network to Achieve Biconnectivity, in: 2009 Int. Conf. Netw. Secur. Wirel. Commun. Trust. Comput., IEEE, 2009: pp. 309–314.
D. Benyamina, A. Hafid, M. Gendreau, On the design of bi-connected wireless mesh network infrastructure with QoS constraints, in: GLOBECOM 2009-2009 IEEE Glob. Telecommun. Conf., IEEE, 2009: pp. 1–8.
J.L. Fendji, C. Thron, J.M. Nlong, Simulated Annealing approach for mesh router placement in rural Wireless Mesh Networks, in: 7th Int. Conf. AFRICOMM, 2015: pp. 15–16.
J.L.E.K. Fendji, C. Thron, J.M. Nlong, A metropolis approach for mesh router nodes placement in rural wireless mesh networks, ArXiv Prepr. ArXiv150408212. (2015).
J.L.F.K. Ebongue, C. Thron, J.M. Nlong, Mesh Router Nodes placement in Rural Wireless Mesh Networks, ArXiv Prepr. ArXiv150503332. (2015).
J.L.K.E. Fendji, C. Thron, A Simulated Annealing Based Centre of Mass (SAC) Approach for Mesh Routers Placement in Rural Areas, Int. J. Oper. Res. Inf. Syst. IJORIS. (2020). www.igi-global.com/article/a-simulatedannealing-based-centre-of-mass-sac-approach-for-mesh-routers-placement-in-rural-areas/243420 (accessed June 12, 2020).
A. Ajayi, U. Roedig, C. Edwards, N. Race, A survey of rural Wireless Mesh Network (WMN) deployments, in: 2014 IEEE Asia Pac. Conf. Wirel. Mob., IEEE, 2014: pp. 119–125.
A. Ting, D. Chieng, K.H. Kwong, I. Andonovic, Optimization of heterogeneous multi-radio multi-hop rural wireless network, in: 2012 IEEE 14th Int. Conf. Commun. Technol. ICCT, 2012: pp. 1159–1165. https://doi.org/10.1109/ICCT.2012.6511372.
L.-H. Hsu, C.-K. Lin, Graph theory and interconnection networks, CRC press, 2008.
J. Park, A. Flores, Fermat’s point from five perspectives, Int. J. Math. Educ. Sci. Technol. 46 (2015) 425–441.
X. Cheng, D.-Z. Du, L. Wang, B. Xu, Relay sensor placement in wireless sensor networks, Wirel. Netw. 14 (2008) 347–355.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Jean Louis Kedieng Ebongue Fendji, Patience Leopold Bagona
This work is licensed under a Creative Commons Attribution 4.0 International License.
