中文摘要：

兀线Mesh网络是移动互联网的一种重要接人方式，如何合理、高效地部署Mesh路山器（MeshRouter，MR），从而以较低的部署成本获得较好的网络性能，是当前的研究热点．文中首先给出一种分层的部署场景模型及十11关假设，并在此基础上利用混合整数线性规划方法对MR部署问题进行形式化描述；然后提出一种基于网络流的MR部署贪心算法NFGreedy，该算法以迭代的方式从MR候选位置集rrI选择权重最大的节点进行相应的节点部署，其中节点权重定义为当前网络可满足的最大用户带宽需求的平均增量，可利用网络流方法进行求解；最后通过一系列仿真实验将NFGreedy算法与现有算法进行对比，实验结果表明该算法与基于MILP的算法辑1比，虽然所部署的MR数量略多，但是能适用于较大规模的WMN；而与启发式的ILSearch算法相比，则大大减少了所部署MR的数最．

英文摘要：

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 effi ciently 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. （）n 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 （;-reedy, 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 band width 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.