Article Preview
Top1. Introduction
The ninth United Nations Sustainable Development Goal is to build resilient infrastructure. One of his targets is to significantly increase access to ICT and strive to provide universal and affordable access to internet in Least Developed Countries by 2020. Universal and affordable access means “Leave No One Behind”. But the bulk of the unconnected is located in rural and hard-to-wire areas, with technical and financial limitations. Fortunately, Wireless Mesh Network (WMN) (Akyildiz, Wang, & Wang, 2005) has appeared as an appealing cost-effective solution to bridge the digital divide and to connect the unconnected. A Wireless Mesh Network (WMN) is a wireless network in which nodes are connected in a mesh topology. It is based on off-the-shelf Wi-Fi technology. For economic reasons, Rural Wireless Mesh Networks (RWMN) are typically composed of only one gateway and a set of mesh routers (MRs) which aim to cover only areas of interest in the locality. The sole gateway usually connects the network to Internet via a last mile solution such as VSAT. The success of the planning of such networks depends on the determination of an optimal placement of mesh nodes which provides good coverage while requiring fewest nodes. The planning of wireless networks in rural regions is more coverage-driven than capacity-driven (Bernardi, Marina, Talamona, & Rykovanov, 2011), which means we are more concerned by the area to cover than the capacity to provide. The aim during the planning is to minimize the overall cost of the architecture, while maximizing the coverage percentage of the area of interest. For realistic deployment scenarios, the problem of mesh node placement is a NP-hard combinatorial optimization problem which cannot be solved in polynomial time. This is why metaheuristics are usually required to optimize the planning.
Convergence time and robustness are important issues when it comes to developing or applying a stochastic optimisation technique. Simulated annealing (SA) is a probabilistic global optimisation technique used in large search spaces, which accepts some non-improving solutions in order to escape local optima. Since its introduction by Kirkpatrick et al. (1983), SA has been applied to a large variety of optimization scenarios, including the problem of node placement in Rural Wireless Mesh Networks (RWMN). Several years of experience using SA has led to the following general observations (Ingber, 1989):
- •
SA yields high-quality solutions, but may require large amounts of computation time;
- •
SA is especially advantageous in practical situations, where tailored algorithms are unavailable, due to its general applicability and its ease of implementation.
Several authors have attempted to reduce the convergence time for SA algorithms (Varanelli & Cohoon, 1999; Yuping, Shouwei, & Chunli, 2005). Other authors have recently tried to improve the solution quality of SA by providing hybrid approaches (Ezugwu, Adewumi, & Frîncu, 2017; Chen, Chien, Chena, & Chiena, 2011; Yannibelli & Amandi, 2013; Jia, Ma, Wang, & Liu, 2011). In this paper, we tackle the problem of improving the quality of solution and the robustness while minimising the convergence time of the SA approach in solving the problem of node placement in a Rural Wireless Mesh Network (RWMN). We consider the network model proposed in (Fendji, Thron, & Nlong, 2015). In this model, a given area to cover is decomposed into elementary areas which are identified as “required” or “optional” in terms of coverage, and “possible” or “not possible” in terms of node placement. We consider also the presence of obstacles that can hinder the connectivity. The aim is therefore to determine the location of mesh routers which maximizes the coverage of area of interest while ensuring the connectivity. To reach this goal, a placement approach based on the calculation of the centre of mass (CM) of area covered per router is proposed. This approach is later combined with the SA approach defined in (Fendji, Thron, & Nlong, 2016) in order to obtain a hybrid method, Simulated Annealing based Centre of mass (SAC).