基于粉粒子群优化的无线自组织网络路由技术研究
1 绪论
1.1 课题研究背景和意义
Ad Hoc，又称为移动自组织网络（MobileAd Hoc Networs, MANET），是由一组带有无线收发装置的移动节点组成的临时性网络，具有易搭建、自组织、不依赖应用环境的特点，在难以搭建有线网络的环境中具有很强的实用性，比如战场的士兵通讯网络、灾难地区的救援网络以及实时通讯的会议网络等，与有线网络共同担负着实现数据流通的功能。在通讯技术日渐发达的今天，Ad Hoc 日益受到人们的关注，在越来越广泛的领域里起着其他网络不可替代的作用。
在具体应用的过程中，为了适应不同的环境 ，Ad Hoc 中的节点随时处于移动现实，从而导致频繁的链路断链和网络中断，而现有的网络协议不能很好地适应这种变化，极大地影响了网络中数据的流通。并且随着 Ad Hoc 应用范围的不断扩大，要求 Ad Hoc在保持自身优点的同时，也要保证网络的通讯质量，如安全性要求、实时性要求等。要解决这些问题，最关键的是 Ad Hoc 网络要支持 QoS，即保证网络的数据传输符合一定的代价、带宽、延时等的要求。
使Ad Hoc网络支持 QoS 的基本方法是提供 QoS 保证体系，在这个体系中，最核心的技术是是找到一条具有足够资源的路径。在拓扑结构不断变化的 Ad Hoc 网络中寻找符合 QoS 要求的路径是一个多约束 NP 问题，而解决多约束 NP 问题的一个行之有效的方法就是利用粒子群算法来求解。相比遗传算法、蚁群算法等，粒子群算法[8]参数少，收敛快，在大规模问题的寻优过程中，能够提高问题的解决效率。
Ad Hoc 网络 QoS 路由协议的性能在很大程度上受到其动态变化的网络拓扑结构的限制。在传统有线网络中，发展较成熟稳重的协议主要有两类，一类是基于距离矢量的路由协议，其计算路由的依据是节点之间的距离，另一类是基于链路现实信息的路由，其计算路由的依据是网络的拓扑结构。这两类协议共同的特点是都要实时地维护网络的连接现实信息，因此需要周期性地发送大量的控制报文。
1.2 国内外研究现状
1.2.1 Ad Hoc网络研究现状
目前，无论在国际上，还是在区域上，越来越多的人投身于 Ad Hoc 网络技术的研究，研究的重点主要集中在 Ad Hoc 路由协议、多播/组播、MAC 控制、QoS 路由等方面。世界各国都成立了专门的研究组织机构，比如美国加州大学洛杉矶分校的无线自适应移动性实验室;、美国加州大学圣巴巴拉分校的移动性管理和联网实验室;等。从上世纪九十年代其国内对于 Ad Hoc 网络的研究也开始崭露头角，比如解放军理工大学、西安电子科技大学等，但由于起步较晚，组织结构分散，国内对 Ad Hoc 网络的研究没有得到一定的规模，所得成果较美国等发达国家也有一定的差距。
虽然基于QoS的路由协议是当前的研究热点，但取得的标志性成果并不多，人们所提出的各种路由机制也大多只停留在理论研究阶段，难以在现实中真正得到应用。总结人们的研究思路，设计具有 QoS约束的路由大致可从两个方向出发：
（1）改进尽力而为;的传统路由协议。这种思路的主要思想为计算最优路由的过程中考虑QoS约束，而不是单纯将最小跳数作为参考。在表驱动式路由协议中具体表现为在节点间交换的路由信息中增加QoS 参数的信息，最优路径的选择在源节点进行；而在按需式路由协议中只是在路由发现过程中增加QoS 约束，使得最终找到的路径能够满足业务的需求。
（2）设计针对QoS 约束条件的新型路由。这种设计思路完全舍弃传统路由协议的路由机制，另起炉灶，运用各种形式的路由策略来实现QoS 保障。这种思路的做法有很多，比如：
Chen于 1997 年提出一种基于 DSDV 协议的带宽约束路由算法，它的原理是在DSDV协议传输距离矢量的过程中，增加链路现实的信息，使得节点在获得到达目的节点路由时，也得到了该路由的最小带宽。由于采用的是表驱动的路由方式，节点在获得一条路径信息时，会引起所在链路连接现实的变化，从而引发新一轮的网络连接现实更新，进而增加了网络控制信息的比重，联通性能会受到很大程度的影响。
2Ad Hoc 网络及路由协议的分析
2.1 Ad Hoc网络概述
2.1.1 Ad Hoc网络特点及应用
Ad Hoc 网络是由一定数目的移动节点组成的临时网络，多跳的通信方式是它最大的网络特征。网络中的节点既能作为主机处理信息，也能作为路由器转发信息，并且节点之间采用随机的方式进行互联，只要移动到彼此的通信范围之内便可进行数据传输。除此之外，Ad Hoc不同于传统网络的特征还表现在如下几个方面：
（1）无中心、自组织。Ad Hoc 网络的结构组成决定了其可以在任意环境下搭建通信网络，并且形成的网络采用分布式的组织管理方式，这在很大程度上减少了网络对单个节点的依赖，增强了网络适应环境的鲁棒性。
（2）网络拓扑动态变化。为适应环境，网络中的节点始终处于随机运动现实，当两个节点移动到彼此通讯范围内时，两节点之间便会建立起一条通信链路，反之，若移开彼此的通讯范围，之前建立的通信链路便会断开。节点间随机地建立链路、断开链路导致整个网络的拓扑结构时刻在发生变化，并且变化不具有任何规律性。
（3）资源受限。通常状况下，Ad Hoc网络中的节点为体积较小的通讯设备，这就意味着它没有能够源源不断的提供能量的供电设备，因此节点的发射功率、计算能力、存储空间等都会在不同程度上受到限制。
（4）带宽受限。Ad Hoc网络通过无线信道进行通信，相比有线信道，无线信道能够提供的带宽本来就小，再加上节点间的竞争机制、无线信道的不稳定等因素，造成节点实际获得的带宽远小于理论值。
（5）安全及服务质量难以保障。移动Ad Hoc网络采用无线信道、分布式控制等技术，使其更容易受到窃听、篡改、拒绝服务等网络攻击，服务质量难以保障。开放的无线信道、无序的分布式管理、节点间的随机链接等因素导致网络的安全级别较低，很难抵御外来的蓄意破坏，进而极大降低了网络的通讯质量。
2.2 Ad Hoc网络路由协议
2.2.1 路由协议简介
Ad Hoc 网络的基本功能是完成数据的传递，这就要求源节点和目的节点之间至少存在一条连通的路由。路由协议的作用是寻找网络中源节点和目的节点之间的路由并完成数据的传输，如图 2.3所示。与传统网络不同，由于节点随机移动的特性，加之无线信道的不稳定，Ad Hoc 网络的拓扑结构随时都处于变化当中，在这种极端状况下建立路由并完成数据发送是一项挑战性极大的工作，因此路由协议在 Ad Hoc 网络组成结构中占据十分重要位置。在 Ad Hoc 网络中，路由协议肩负着监控网络拓扑变化、交换路由信息、发现并建立路径、传递分组、维护有效路径、修复断链路径等多项复杂的工作，它的性能的好坏直接关系到整个网络的连通现实和通讯功能，其工作机制也成为Ad Hoc网络研究中的热点。
随着对 Ad Hoc 网络应用和研究的不断深入，人们期望设计出更好的路由协议来满足日益增多的功能需求，具体来说一个好的Ad Hoc路由协议需满足以下条件：
（1）能敏锐地检测到网络拓扑的变化并迅速作出适当反应，且路由算法收敛较快；
（2）合理高效地利用网络资源，特别是带宽，用于信息交换的控制开销尽可能低；
（3）提供环路检测机制，选出的路由不能出现环路，这对于Ad Hoc 网络的路由协议是最基本也是最必要的一个要求；
（4）Ad Hoc 路由协议的主流发展方向是按需操作，在设计新的路由协议时，尽量符合总体发展趋势，避免走向极端；
3 粒子群优化算法及其改进........18
3.1 粒子群算法简介.............................18
3.1.1 粒子群算法原理···················18
4 基于粒子群算法的Ad Hoc网络QoS路由协议...........32
4.1 基于改进粒子群算法的Ad Hoc按需路由协议（PAODV）概述...........32
5 仿真实验及性能分析.............42
5.1NS2网络仿真软件概述...........................42
5.2 仿真环境和参数...............................43
5 仿真实验及性能分析
5.1 NS2网络仿真软件概述
在网络研究中，除了针对所存在的问题提出新的改进方案之外，还需要建立数学模型对该方案进行仿真，统计并分析结果数据，获得方案的性能参数，以评价它的可行性和有效性。由此可见网络仿真对网络研究所起的作用是极其重要的。市场上的做网络仿真的公司很多，也开发出许多基于不同机制、针对不同仿真性能的软件，包括商业的和非商业的。这些软件大都支持多种协议，并采用易于编程和组织的模块化框架，能够进行通用的网络仿真。其中，商业性的软件大多价格昂贵，且其代码不公开，不适宜作为实验室的通用仿真软件。非商业软件虽然在性能上不如商业软件完善，但由于开放的软件包，具有很强的实用性，且能完成通用的网络仿真，因此可用作网络研究仿真的实用工具。在主流的一些网络仿真软件中，NS2 由于源代码开放、构件库丰富、支持广域/移动等网络、支持有线/无线网络的 TCP 路由协议等多层协议，且经过 CMU大学以及众多研究结构的扩展后性能更加完善，目前已经成为Ad Hoc 路由协议的通用仿真平台，本文也使用NS2仿真工具对PAODV 协议进行仿真。
NS2 是由UC Bereley 和USC ISI 联合开发的，是一款开放源代码的网络仿真软件，任何人都可以使用和修改源代码。在本质上，它是一个离散时间模拟器，整个仿真过程就是基于一个绝对模拟时钟不断的产生事件、处理事件的循环，而这个循环是在任务调度器的控制下完成的。在循环中，任务调度器记录每一个事件的发起时间、类型、发起节点地址、目的节点地址、所使用的协议、等详细信息，并以文档的形式进行存储。
6 总结与展望
6.1 总结
本文研究是在 XXX基金项目《基于粒子群优化的AdHoc 网络路由协议研究》（No.202111013-1）的资助下展开的。近年来，越来越多的科研人员投入到Ad Hoc 网络的研究，使得网络的性能进一步提高，应用的范围也越来越广泛。本文主要讨论了 Ad Hoc网络的平面按需路由协议的改进，所做的工作总结如下：
（1）深入研究了粒子群算法的原理及其特点，分析种群多样性对算法迭代的影响，并从种群对算法进行改进，提出一种新的改进粒子群算法。在改进算法中，将 BP 神经网络的分类思想融合到粒子群算法中，使算法的多样性始终处于较高水平，增加了跳出局部最优解的概率。
（2）提出一种基于改进粒子群算法的 Ad Hoc平面按需路由协议 PAODV，详细设计了协议所使用的通信包的格式、最优路由的计算方法以及通信包的传输机制等。在使用改进粒子群算法进行最优路由的计算中，通过增加QoS约束，使寻找到的最优路由符合特定带宽和延时的要求，并在代价、带宽和延时之间取得一定的平衡。
（3）利用 NS2 仿真软件，分别在三种场景下对所提协议的性能进行测试，验证PAODV 协议可行性和有效性。实验结果分析显示，PAODV 路由协议比 AODV 协议更能适应网络拓扑结构的变化，有效提高了协议的分组投递率，降低了网络的传输延时，并减轻了控制信息给网络带来的额外负担，在一定程度上改善了网络的路由效率。
参考文献（略）