《蚁群优化在移动自组网mpr节点选择问题中的应用研究》由会员分享，可在线阅读，更多相关《蚁群优化在移动自组网mpr节点选择问题中的应用研究（58页珍藏版）》请在金锄头文库上搜索。
1、中国科学技术大学 硕士学位论文 蚁群优化在移动自组网MPR节点选择问题中的应用研究 姓名：张禾良 申请学位级别：硕士 专业：计算机软件与理论 指导教师：熊焰 2011-04-06 摘 要 I 摘摘 要要 移动自组网(Mobile Ad hoc networks: MANET)是一种特殊的由移动节点所 组成的多跳自组织通信网络。与其它类型的网络相比，移动自组网具有灵活性、 健壮性等特点， 使其得到越来越广泛的关注， 并在通信技术研究中占有重要地位。 在移动自组网中，多点中继机制(Multipoint Relay: MPR)在移动网络中被用 来减少消息重复转发的次数， 进而限制了网络中的泛洪消息数
2、， 降低了网络开销。 该机制要求网络中的节点从本节点的一跳邻居集合中选出若干个可以覆盖其所 有二跳邻居的节点构成 MPR 节点集合，并且仅通过 MPR 节点转发消息。但由 于最小 MPR 集的选取属于 NP 难问题，传统的贪心算法方法在求解精度上往往 无法取得较好的结果，尤其是在网络密度较大的环境下。 针对以上问题，本文将蚁群优化用于最小 MPR 集选取问题的求解，并给出 了一种基于候选解的改进蚁群算法 CSACO(Candidate Solution Ant Colony Optimization)。通过使用候选解集进行信息素的更新，提高了算法的收敛速度， 同时避免了算法陷入早熟。模拟实验表
3、明，CSACO 可以有效降低 MPR 集的大 小，同时在较短的时间内收敛到最优解，提高网络性能。 本文的主要工作包括以下内容 1) 总结并分析了移动自组网中常见的路由协议；研究了多点中继机制的原 理，并给出了当前提出的用于进行 MPR 节点选取的方案，并分析了各自的优缺 点。 2) 通过对蚁群算法的机制的深入研究， 给出了解决最小 MPR 集选取问题的 蚁群算法模型，详细介绍了模型中各个组成部分，包括适应函数的构造、节点选 择的概率方程以及信息素更新方程的建立。为了验证模型的有效性，建立了仿真 实验环境，通过生成不同的网络环境并对各种环境下的对比实验数据进行分析， 进行算法的求解性能评估。 3
4、) 由于蚁群算法寻解速度较慢，易陷局部最优，在对已有的改进蚁群算法 进行研究后，本文提出了一种基于候选解的改进蚁群算法 CSACO。通过使用候 选解集进行信息素的更新，提高了算法的收敛速度，同时避免了算法陷入早熟。 模拟实验表明，相比于其它的 MPR 节点选择方法，CSACO 可以有效降低 MPR 集的大小，同时在较短的时间内收敛到最优解，提高网络性能。 关键词：关键词：移动自组网，蚁群优化，多点中继，最小 MPR 集，候选解 Abstract III ABSTRACT Mobile Ad hoc networks(MANET) is a special self-organized comm
5、unication network with multiple hops composed by mobile devices. Compared with other networks, MANET receives more and more concern for its flexibility and robustness, and plays an important part in the research of communication techniques. Multipoint Relay(MPR) is a mechanism to reduce the number o
6、f redundant retransmissions and flooding messages, so it reduces the overhead in Mobile Ad hoc networks. The elements in the MPR set of a given node in the network can only be selected from the set composed by the 1-hop neighbors of the given node, and all the 2-hop neighbors of the given node can b
7、e dominated by the nodes in the MPR set. However, the selection of MPR set with minimum size is NP-hard, the original greedy algorithm doesnt work well, especially in the dense networks. To solve this problem, we use the ant colony optimization (ACO) for the MPR set selection, then propose an improv
8、ed ACO algorithm called CSACO based on the concept of candidate solution. By using candidate solution set to update the pheromone, the speed of convergence is improved and the premature convergence is effectively avoided. Finally, the simulation results are presented to show that CSACO performs well
9、 in different scenarios: It significantly reduces the degree of the MPR set, and obtains the convergence in a shorter time. The main work of this paper includes the following: 1) Summarize and analysis the common routing protocols in MANET. After studying the principle of Multipoint Relay mechanism,
10、 we introduce the existing MPR selection methods, and present the analysis of their advantages and disadvantage. 2) Based on the learning of the Ant Colony Optimization, an ACO model to solve the MPR selection problem is proposed. We discuss every part of the model in detail, including the design of
11、 the fitness function, the probability equation for the selection, and the update equation for the pheromone. Simulations under different network scenarios are used to verify the validity of our model, and we analyze the simulation data of each scenario. The simulation results are presented to show
12、that the new MPR selection method produces better solutions. 3) To solve the problem of premature convergence and slow speed of ACO, on the basis of the existing improved ACO mechanism, we propose a new improved Abstract IV ACO algorithm called CSACO based on the concept of candidate solution. By us
13、ing candidate solution set to update the pheromone, the speed of convergence is improved and the premature convergence is effectively avoided. Finally, the simulation results are presented to show that: compared with several other MPR selection methods, CSACO receives a better performance in differe
14、nt scenarios: It significantly reduces the degree of the MPR set, and obtains the convergence in a shorter time. Key Words：Mobile Ad hoc networks, Ant Colony Optimization, Multipoint Relay, Candidate Solution, Minimum MPR Set 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不
15、包含任何他人已经发表或撰写 过的研究成果。 与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：_ 签字日期：_ 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一， 学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中国学 位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、 汇编学位论文。 本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 公开 保密（_年） 作者
16、签名：_ 导师签名：_ 签字日期：_ 签字日期：_ 第一章 绪 论 9 第一章第一章 绪绪 论论 随着科技的发展与计算机相关领域技术的不断进步， 无线网络在近些年得到 了飞速的发展。无线设备因其的便携与灵活性得到了人们越来越多的亲睐。而移 动自组网便是一种由移动节点所组成的特殊通信网络， 移动自组网本身具有无中 心、自组织以及多跳路由等特点，为网络系统的快速建立、节点成本及功耗的降 低等提供了有力的保证。因此，移动自组网在军事和民用等领域均已获得愈加广 泛的应用。 1.1 引言 作为一种自组织、多跳的无线通信网络，移动自组网因其所具备的灵活性及 抗毁性强等优点得到了广泛的关注与应用。在移动自组网中，节点可以随意进行 位置变动，且同时具备报文转发和路由功能，可以构成任意的网络拓扑。但由于 节点的传输能力有限，当节点间的距离超过传输半径时，必须通过中间节点进行 转发，因此，
