Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.ins.2017.03.011 | Inf. Sci. |
Keywords | Field | DocType |
Multi-hop wireless networks,Gateway deployment,Vertex k-centre,Substitution principle,Max-min hop | Network service,Wireless network,Mathematical optimization,Software deployment,Network planning and design,Liskov substitution principle,Default gateway,Optimization problem,Mathematics,Distributed computing,Discrete space | Journal |
Volume | Issue | ISSN |
400 | C | 0020-0255 |
Citations | PageRank | References |
2 | 0.35 | 23 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
shuqiang huang | 1 | 6 | 1.42 |
zhen zhang | 2 | 6 | 1.41 |
Yonghui Li | 3 | 3393 | 253.70 |
Zhusong Liu | 4 | 110 | 10.10 |
Yong-Hui Li | 5 | 2 | 0.35 |