A Bandwidth-Aware Router Placement Scheme for Wireless Mesh Networks
Wu Wen · Chinese Journal of Computers · 2014
Wireless mesh networking is one of the most important access technologies for Mobile Internet,and the problem concerning how to deploy mesh routers(MRs)reasonablely and efficiently has been attracting increasingly more attention from research community,in order to achieve better network performance with relatively low deployment costs.In this paper,firstly, we present a hierarchical deployment scenario model and related assumptions.On this basis,the problem of MR placement is formulated as a mixed integer linear programming(MILP)issue. Then,we propose a novel network-flow-based greedy algorithm for MR placement,called NF Greedy,which iteratively selects the node with maximum weight from MR candidates and deploys the corresponding MRs.The node weight is defined as the average increment of available bandwidth requirements in current iteration,which can be obtained by network flow method.Finally, we conduct simulation experiments through which the proposed algorithm is compared with existing algorithms,and the results show that the deployed MRs of our algorithm are only a little more than that of the MILP based algorithm,and are significantly fewer than that of the heuristic ILSearch algorithm.Moreover,the simulation results also demonstrate that our algorithm can be well applied in large-scale WMNs where the solutions of the MILP based algorithm cannot be obatained.