无线Mesh网络中的骨干网络部署的优化

Optimization of Wiring Layout in Mesh Network

在满足用户需求情况下,优化无线Mesh网络中接入点(TAPs)放置以及布线线路以减小布线成本。首先,把该问题中的布线问题模型化为欧氏空间中准组Steiner树问题。解决传统的组Steiner树问题的算法在该问题上并不适用。其次,针对该问题特有的特征给出了一种近似算法。最后,为了达到最小化网络布线的成本的目的,在布线的基础上使用线性规划达到最小化TAPs数目。模拟实验的结果表明,该方法能够显著降低布线成本。优化方法对于无线Mesh网络的骨干网络的部署具有重要指导意义。

This paper optimizes the placement of TAPs in Wireless Mesh network and minimizes the layout cost while meeting user＇s demand. First, layout problem is modeled as Quasi - Group Steiner Tree Problem. Traditional algorithms, which solve traditional Steiner Tree Problem are not efficient for solving this problem. Secondly, an approximation algorithm based on this problem＇s specifics is given. Finally, after solving the wiring layout problem, Linear Programming is used to minimize the number of TAPs deployed in network and the cost of wiring layout. Simulations show that this method can minimize the layout cost distinctively. It is of significance for optimizing the wiring layout in Mesh Network.