【作者】 孙浩然；

【导师】 石文孝；

【作者基本信息】 吉林大学 ， 通信与信息系统， 2017， 硕士

【摘要】 无线Mesh网络(Wireless Mesh Networks,WMN)由于其部署安装简单、稳定性好、带宽高等特点成为解决“最后一公里”的关键技术,受到广泛的关注。在无线Mesh网络的相关研究中,优化信道分配与路由来提升网络性能是重要的研究内容。在现有研究中,单纯的信道分配或路由的优化没有考虑信道与路由相互之间的影响,不能充分利用网络资源。信道分配与路由联合优化可以提高网络资源利用率,对提升网络性能有重要意义。目前很多联合优化算法首先构建联合优化网络模型,并将优化模型表示为线性规划问题。线性规划问题是NP难问题,当网络规模较大时一般采用启发式算法对其求解,但是现有的启发式算法存在未考虑信道与路由之间的影响以及复杂度高等问题。本文针对无线Mesh网络中传输链路负载不均衡的问题,考虑无线Mesh网络中网络资源限制条件,将信道分配、路由以及网络接口分配联合优化的网络优化模型表示为混合整数线性规划问题,提出一种可以快速收敛的启发式算法ILSG算法(Iterated Local Search with Greedy algorithm)求解混合整数线性规划问题。ILSG算法首先使用贪婪算法生成一个可用的网络初始信道分配方案。该贪婪算法在网络优化模型约束条件下,考虑网络连通性以及负载均衡,生成初始信道分配结果并将分配方案表示为一个可用的决策变量的初始值。然后将初始值代入局部迭代搜索法(ILS)求解规划问题,根据所得解确定网络资源分配方案。仿真结果表明,ILSG算法可以以更快的收敛速度得到优化模型的分配方案,在保证网络公平性的基础上提升了网络性能。跳数是路由的最基本度量之一,减小网络中的平均跳数可以降低网络的资源利用率。目前,对联合优化模型的规划问题求解使用的启发式算法在求解完成后,确定网络资源分配方案时,没有考虑网络中平均跳数。针对这一问题本文提出ILSG-H(Iterated Local Search with Greedy Algorithm-Hop Counts)算法,在ILSG算法对规划问题迭代求解完成后,对得到的决策变量的初始解,计算初始解对应的节点以及传输流,得到当前节点到对应的目的节点的最小跳数,将初始解与对应最小跳数的倒数的加权和作为确定网络信道与路由分配方案的参数,获得最终的信道与路由的优化分配方案。仿真结果表明,ILSG-H算法可以合理利用网络资源,提升网络性能。本文使用Matlab与NS-3对算法性能进行仿真比较,在Matlab上进行算法的仿真,对算法的性能进行仿真比较并获得网络资源分配方案;在NS-3仿真平台上构建多接口多信道的无线Mesh网络平台进行网络性能比较。仿真结果表明所提算法相比ILS算法可以以更小的计算量获得WMN网络中信道与路由联合分配方案,合理利用网络资源,提高网络中的平均吞吐量,降低平均端到端时延和平均丢包率。更多还原

【Abstract】 Wireless Mesh Networks(WMN)is a key technology to solve the "last mile" because of its simple installation,good stability and high bandwidth,has received widespread attention.In the reaearch on wireless mesh network,optimizing channel allocation and routing to improve network performance is an important research content In the existing research,the simple channel allocation or routing optimization does not take into account the impact of channel and routing,can not make full use of network resources.Jointing channel allocation and routing optimization can improve the utilization of network resources,has important meanings to enhance network performance.At present,many joint optimization algorithms have adopted the method of constructing the joint optimization network model and expressing the model as a linear programming problem,but the linear programming problem is NP-hard problem,so these algorithms use heuristic algorithm to solve problem,but the existing heuristic algorithms do not consider the influence of the channel and the route and has large amount of computation.Based on the problem of unbalanced transmission link in wireless Mesh networks,a mixed integer linear programming problem is used to represent the optimal model of joint channel allocation,routing metric and network interface assignment in this paper.A ILSG(Iterated Local Search with Greedy algorithm)heuristic algorithm is proposed which can quickly converge.The ILSG can solve the mixed integer linear programming problem.The ILSG algorithm generates an initial network channel allocation program using a greedy algorithm that complies with the network optimization model constraints,network connectivity,and load balancing.The allocation program is expressed as an available initial value,and the initial value is substituted into the local iterative search method(ILS)to obtain the planning problem solution and accordingly dete rmine the network resource allocation program.The simulation results show that the ILSG algorithm can get the optimal model allocation program at a faster convergence rate,and improve the network performance on the basis of ensuring the fairness of the network.The hop count is one of the most basic metrics of the route,and reducing the average number of hops in the network can reduce the resource utilization of the network.At present,the heuristic algorithms used in the planning problem that represent the joint optimization model do not consider other factors that can affect the network performance in the network when the network resource allocation result is determined after the solution of the planning problem is completed.In this paper,the ILSG-H(Iterated Local Search with Greedy Algorithm-Hop Counts)is put forward.After the ILSG algorithm iterativly solves the solution of the programming problem,the initial solution of the obtained decision variable is calculated,and the corresponding node and the transport stream are calculated The minimum number of hops of the current node to the corresponding destination node is obtained,and the weighted sum of the initial solution and the reciprocal of the corresponding minimum hops is taken as the parameter of the network channel and the route allocation scheme to obtain the optimal allocation result of the final channel and route.The simulation results show that the ILSG-H algorithm can make good use of the network resources to improve the network performance.In this paper,we use Matlab and NS-3 to compare the performance of the algorithm,simulate the algorithm on Matlab,compare the performance of the algorithm and get the network resource allocation scheme.Design multi-channel multi-channel wireless mesh network platform on NS-3 simulation platform for network performance comparison.The simulation results show that the proposed algorithm can obtain the joint scheme of channel and route in WMN network with reasonable calculation,and make reasonable use of network resources to improve the average throughput in the network and reduce the average end-to-end delay and the average packet loss rate.更多还原