×

Deployment optimization of multi-hop wireless networks based on substitution graph. (English) Zbl 1429.68192

Summary: In multi-hop wireless networks, the maximum number of hops between clients and the service gateway (GW) significantly impacts the quality of network service, and thus GW deployment optimization plays a critical role in network design and planning. It is well know that the optimal GW deployment can be formulated as a vertex k-centre problem. However, achieving the optimal solution of a k-centre problem is highly complex due to its large solution space. To address this issue we propose a new algorithm based on the substitution principle of network by exploring the inclusion relationship of adjacent node subsets, to reduce the original network to a smaller scale substitution graph. The proposed algorithm can eliminate a large number of redundant nodes, thus reducing the solution space of the optimization problem, and improving the probability of achieving a globally optimal solution. The performance of the proposed algorithm is also analysed. Simulation results show that the proposed \(t\)-step substitution algorithm can significantly reduce the solution space of the k-centre problem by up to 80%. We then apply the proposed algorithms to traditional optimization methods, such as genetic (GA), artificial immune (AIA), and K-means for solving discrete space problems, and it is shown that the substitution based algorithm can significantly improve the performance of respective traditional GA, AIA and K-means methods,yielding a better GW deployment scheme with a smaller covering radius.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68M10 Network design and communication in computer systems
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abo-Zahhad, M.; Sabora, N.; Sasaki, S.; Ahmed, S. M., A centralized immune Voronoi deployment algorithm for coverage maximization and energy conservation inmobile wireless sensor networks, Inf. Fusion, 30, 7, 36-51 (2016)
[2] Abdelkhalek, O.; Masri, H.; Krichen, S., An adaptive variable neighborhood search for solving the multi-objective node placement problem, Discrete Math. Electron., 47, 2, 189-196 (2015) · Zbl 1362.90120
[3] Abdelkhale, O.; Krichen, S.; Guitouni, A., A genetic algorithm based decision support system for the multi-objective node placement problem in next wireless generation network, Appl. Soft Comput., 33, 8, 278-291 (2015)
[4] Aoun, B.; Boutaba, R.; Iraqi, Y., Gateway placement optimization in WMN with QoS constraints, IEEE J. Sel. Area Commun., 24, 11, 2127-2136 (2006)
[5] Bardossy, M. G.; Raghavan, S., Approximate robust optimization for the connected facility location problem, Discrete Appl. Math., 210, 10, 246-260 (2016) · Zbl 1345.90054
[6] Bejerano, Y., Efficient integration of multihop wireless and wired networks with QoS constraints, IEEE/ACM Trans. Networking, 12, 6, 1064-1078 (2004)
[7] Breu, H.; Kirkpatrick, D., Unit disk graph recognition is NP -hard, Comput. Geom. Theor. Appl., 9, 1/2, 3-24 (1998) · Zbl 0894.68099
[8] Chaurasia, S. N.; Singh, A., A hybrid swarm intelligence approach to the registration area planning problem, Inf. Sci., 320, 5, 50-69 (2015)
[9] Durocher, S.; Jampani, K. R.; Lubiw, A.; Narayanan, L., Modeling gateway placement in wireless networks: geometric k-centres of unit disc graphs, Comput. Geom., 44, 5, 286-302 (2011) · Zbl 1214.90022
[10] Elshaikh, A.; Salhi, S.; Brimberg, J., An adaptive perturbation-based heuristic: an application to the continuous p-centre problem, Comput. Oper. Res., 75, 11, 1-11 (2016) · Zbl 1349.90583
[11] He, B.; Xie, B.; Agrawal, D. P., Optimizing deployment of internet gateway in wireless mesh networks, Comput. Commun., 31, 7, 1259-1275 (2008)
[12] Khalesian, M.; Delavar, M. R., Wireless sensors deployment optimization using a constrained Pareto-based multi-objective evolutionary approach, Eng. Appl. Artif. Intell., 53, 8, 126-139 (2016)
[13] Lin, C.-C., Dynamic router node placements in wireless mesh networks: a PSO approach with constriction coefficient and its convergence analysis, Inf. Sci., 232, 5, 294-308 (2013) · Zbl 1293.90083
[14] Lin, C.-C.; Chen, T.-H.; Chin, H.-H., Adaptive router node placement with gateway positions and QoS constraints in dynamic wireless mesh networks, J. Netw. Comput. Appl., 74, 10, 149-164 (2016)
[15] Liu, L. G.; Peng, Y. X.; Xu, W. Q., To converge more quickly and effectively-mean field annealing based optimal path selection in WMN, Inf. Sci., 294, 2, 216-226 (2015) · Zbl 1360.68785
[16] Li, Y.; Huang, S. Q.; Fan, R. S.; Zhang, Z.; Zhou, Y. Y., Research on gateway deployment of WMN based on maximum coupling subgraph and PSO algorithm, Soft Comput. (2015)
[17] Maggie, X. C.; Ling, Y.; Brain, M. S., Network connectivity assessment and improvement through relay node deployment, Theor. Comput. Sci., 660, 17, 86-101 (2017) · Zbl 1355.68203
[18] Megiddo, N.; Supowit, K. J., On the complexity of some common geometric location problems, SIAM J. Comput., 13, 1, 182-196 (1984) · Zbl 0534.68032
[19] Papadaki, K.; Friderikos, V., Gateway selection and routing in wireless mesh networks, Comput. Netw., 54, 2, 319-329 (2010) · Zbl 1185.68045
[20] Pavani, G. S.; Queiroz, A. F.; Pellegrini, J. C., Analysis of ant colony optimization-based routing in optical networks in the presence of byzantine failures, Inf. Sci., 340, 5, 27-40 (2016)
[21] Plesnik, J., On the computational complexity of centers locating in a graph, Appl. Math., 25, 6, 445-452 (1980) · Zbl 0454.68026
[22] Rebai, M.; Berre, M. L.; Snoussi, H.; Hnaien, F.; Khoukhi, L., Sensor deployment optimization methods to achieve both coverage and connectivity in wireless sensor networks, Comput. Oper. Res., 59, 7, 11-21 (2015) · Zbl 1348.90178
[23] Roberto, M.-C.; Rafael, R.-G.; Camacho, J.; Pedro, G.-T., Optimal relay placement in multi-hop wireless networks, Ad Hoc Netw., 46, 8, 23-36 (2016)
[24] Senel, F.; Younis, M., Novel relay node placement algorithms for establishing connected topologies, J. Netw. Comput. Appl., 70, 7, 114-130 (2016)
[25] Seyedzadegan, M.; Othman, M.; Ali, B. M., Zero-degree algorithm for internet gateway placement in backbone wireless mesh networks, J. Netw. Comput. Appl., 36, 6, 1705-1723 (2013)
[26] Sun, X. M.; Zhang, Y. M.; Ren, X.; Chen, K., Optimization deployment of wireless sensor networks based on culture-ant colony algorithm, Appl. Math. Comput., 250, 1, 58-70 (2015) · Zbl 1328.90168
[27] Tao, M.; Huang, S. Q.; Li, Y.; Yan, M.; Zhou, Y. Y., SA-PSO based optimizing reader deployment in large-scale RFID systems, J. Netw. Comput. Appl., 52, 6, 90-100 (2015)
[28] Xhafa, F.; Sánchez, C.; Barolli, A.; Takizawa, M., Solving mesh router nodes placement problem in wireless mesh networks by tabu search algorithm, J. Comput. Syst. Sci., 81, 8, 1417-1428 (2015) · Zbl 1328.68022
[29] Yoon, Y.; Kim, Y.-H., An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks, IEEE Trans. Cybern., 43, 5, 1473-1483 (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.