基于蚁群算法的无线Mesh网络QoS路由研究

发布时间：2019-04-26 21:41

【摘要】：无线Mesh网络是一种能为用户提供宽带连接服务的多跳自组织、自配置网络。随着网络不断发展和用户需求的提高，用户希望网络能提供具有服务质量(Quality of Service, QoS)保障的业务。而多QoS约束下的路由是NP-难问题，传统算法不能很好地解决该问题。蚁群算法(AntColony Optimization, ACO)是一种能行之有效地处理多约束优化问题的算法，本文研究蚁群算法并将其应用于无线Mesh网络多约束QoS路由问题。主要从如下两方面展开： 1.研究现有的蚁群算法应用于网络QoS路由问题的方式，在分析其优缺点的基础上，结合非常具有前景的无线Mesh网络混合结构特征，提出一种差异度蚁群多约束QoS路由算法IARQM。该算法综合考虑所发现路径的差异度来更新信息素，能有效避免信息素局部堆积导致的搜索能力下降。同时，考虑到信息素对寻径的重要作用，算法提供缓存恢复机制，为暂时失效节点保留已积累的信息素，提高算法健壮性。并采用寻径时倾向于更为稳定的路由器节点的方法，进一步保证网络的稳定性。论文实现了IARQM算法，并进行了仿真实验，结果表明该算法具有较好的性能和QoS保障能力。 2.一般无线Mesh网络中采用单径路由协议，但单径路由协议存在可能造成网络负载不平衡、节点拥塞发生等不足，因此，在研究现有基于蚁群算法的多径路由基础上，提出一种并行摄动导向性蚁群多径路由算法PGARQ。PGARQ为了更好地生成节点关联度低的多条路径，，在算法中引入并行处理，利用并行节点的高速计算和处理能力并行地生成路径；同时，针对蚁群算法容易陷入局部最优解，结合导向性局部搜索算法改进，并设计一种摄动方式进一步优化算法求解结果。实验结果表明，PGARQ能较快地生成节点之间不相关的路径，提高计算精度和减少计算时间，较好地保证了网络QoS。
[Abstract]:Wireless Mesh network is a kind of multi-hop self-organizing and self-configuring network which can provide broadband connection service to users. With the continuous development of the network and the improvement of users' needs, users hope that the network can provide services with quality of service (Quality of Service, QoS). However, routing with multi-QoS constraints is a difficult problem for NP-, and the traditional algorithm can not solve the problem very well. Ant colony algorithm (AntColony Optimization, ACO) is an effective algorithm to deal with multi-constrained optimization problems. In this paper, ant colony algorithm is studied and applied to multi-constrained QoS routing problem in wireless Mesh networks. Mainly from the following two aspects: 1. Based on the analysis of the advantages and disadvantages of ant colony algorithm (ACA) applied to network QoS routing problems, a new ant colony multiple constrained QoS routing algorithm (IARQM.) is proposed, which is based on the promising hybrid structure of wireless Mesh networks. The algorithm takes into account the difference degree of the paths found to update the pheromone, which can effectively avoid the decrease of the searching ability caused by the local accumulation of the pheromone. At the same time, considering the important role of pheromone in routing, the algorithm provides a buffer recovery mechanism to retain the accumulated pheromones for temporary failure nodes and improve the robustness of the algorithm. In order to ensure the stability of the network, we adopt the method of routing which tends to be more stable router nodes. The IARQM algorithm is implemented in this paper, and the simulation results show that the algorithm has good performance and QoS guarantee ability. 2. In general, single-path routing protocol is used in wireless Mesh networks, but single-path routing protocol may cause network load imbalance, node congestion and so on. Therefore, on the basis of researching the existing multi-path routing based on ant colony algorithm (ACA), A parallel perturbed oriented ant colony multipath routing algorithm (PGARQ.PGARQ) is proposed in order to generate multi-paths with low correlation degree of nodes. Parallel processing is introduced into the algorithm and parallel paths are generated by using the high-speed computing and processing ability of parallel nodes. At the same time, the ant colony algorithm is easy to fall into the local optimal solution, combined with the directed local search algorithm improvement, and designed a perturbation way to further optimize the algorithm to solve the results. The experimental results show that PGARQ can quickly generate unrelated paths between nodes, improve computational accuracy and reduce computing time, thus ensuring the network QoS. better.
【学位授予单位】：南京航空航天大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.09;TP18

【参考文献】