用蚁群算法的其他应用本章小结第三章路由空洞路由空洞的产生路由空洞的危害路由空洞形成的初期危害路由空洞形成的后期危害路由空洞解决方法节点非均匀分布节点均匀分布算法本章小结第四章算法节点信息交换空洞边缘节点判定算法路由发现过程路由发现与虚拟路径的规划信息素更新数据传输本章小结第五章性能分析与仿真的优势算法分析控制报文开销分析路由平均跳数分析仿真及结果分析仿真工具概述仿真参数选择路由算法仿真及结果分析本章小结万方数据第六章总结与展望本文总结未来的工作参考文献附录攻读硕士学位期间撰写的论文致谢万方数据南京邮电大学硕士研究生学位论文第章绪论第章绪论随着近年来计算机技术，网络技术以及嵌入式技术的不断发展，社会对于快速并高效的无线通信有着愈来愈高的要求，这也同时极大的促进了通信技术的飞速发展。工信部于月日向中国移动通信集团公司中国电信集团公司和中国联合网络通信集团有限公司颁发第四代数字蜂窝移动通信业务经营许可。自年来我国发放了牌照后，仅仅过了五年的时间，于年底又发放了牌照。这些不断涌现出的新技术不断丰富着人们的生活。研究背景网络的前身是分组无线网，最早可以追溯到年美国国防部高级研究计划局，启动的分组无线网项目该项目主要负责研究如何在战场环境下应用分组无线网。这种网络与我们经常提及的无线网络不同，这些无线网络大多是基于不对称结构然不会去分析周围的环境，那么对于这些已经存在的障碍物必然无法避免，因此，可以把这类障碍物造成的空洞归类为不可预见的路由空洞另种路由空洞称之为能量空洞，能量空洞是因为种原因导致在个范围内节点的平均能量值大程度的低于周围其他节点的能量值，从而导致在该范围内的节点的能量已经无法支持自己的转发任务，或是若继续参加如普通节点样的多跳转发任务，就会在短时间内能量衰竭，成为前种节点。导致这种路由空洞的原因有很多，最直接的就是由于个网络中的节点在段时间内进行了大量的数据传输导致。例如在网络中的节点，所有网络中的传感器节点收集的信息最终要汇聚到节点上，再通过节点传输给数据分析计算机，在节点的周围不包括节点，因为节点异构与传感器节点，独立供电的传感器节点承担了过多的数据转发任务，最终会导致节点周围大量传感器节点因为能量枯竭而过早死亡，同时该节点也无法再收集信息。研究表明，当此种死亡时，网络中残余能量为网络总能量的。和已经给出了在节点均匀分布的传感器网络中能量空洞无法避免的证明。在此作出简要说明首先给出能耗模型，在网络中，能量的消耗来自于传输能耗感知能耗和数据处理能耗，其中主要的能耗由传输能耗引起。而传输能耗由分为了发送能耗和接收能耗，当个节点需要发送数据时，只需要消耗发送能耗如果是要转发数据，那么同时需要消耗发送万方数据南京邮电大学硕士研究生学位论文第三章路由空洞能耗和接收能耗。设单位时间传输单位数据能耗为，而接收能耗为，那么有，式中，都是正的常数，为发送距离。能量空洞模型基于节点均匀分布的网络，节点密度为，网络为个半径为的圆形，节点处于圆心位置。整个网络被半径为，的个同心圆分成了面积不等的个圆环为方便起见，将个圆环标记为最靠近圆心的圆也看做个圆环，不同圆环中的节点只能向相邻的圆环发送数据，其中满足，这里为了简便计算，设，如图所示图能量空洞模型从图的模型可以得到，每个圆环包含的节点数量为，假设每个节点单位时间内产生的数据量为，可以得到在环中的全部节点在单位时间内需要发送的数据包括了该环中产生的数据和外部圆环产生的数据，需要接受的数据为外部圆环产生的数据，那么可得第个圆环单位时间内每个节点的平均能量消耗为万方数据南京邮电大学硕士研究生学位论文第三章路由空洞最外层圆环内节点的平均能耗和第个圆环节点的平均能耗差为由模型的推导分析可得，那么，即使说，外层的圆环节点平均耗能始终比内层的圆环节点平均能耗低，也就是说能量空洞的问题在均匀分布节点的网络中必然存在。路由空洞的危害路由空洞在网络中几乎是无法避免的。路由空洞在网络中造成的危害从时间上划分可以分为路由空洞形成的初期和后期个阶段的危害。路由空洞形成的初期危害在空洞形成的初期，路由空洞将会影响到所有该空洞覆盖到的路由路径，造成这些路径的时效或部分失效，大部分的路径需要重新进行路由发现过程，并且在新发现的路由路径中几乎都会比现有路径要花费更大的代价，如图所示万方数据南京邮电大学硕士研究生学位论文第三章路由空洞图路由空洞初期危害在当前的网络中，有股数据流分别由流向，并且条路由路径互不影响。当路由空洞出现，如图中黑色节点为能量耗尽的节点，由于空洞的分割，造成了由流向的路由失效，而重新发现的路由将有更多的路由跳数，跳数增加的多少主要由路由空洞的大小来决定，因此该时期路由空洞的危害多少主要取决于形成空洞的半径大小。路由空洞形成的后期危害在实际应用中，在网络建立的初期，路由空洞的半径般是很小的，由于网络是多跳网络，所以即使在网络中存在路由空洞，只要数据传输的源节点和目的节点距离的距离不是过远，相当数量的路由空洞是网络可以容忍的。但是在路由空洞形成后，如果处理不当，例如使用了些不适宜的路由算法，就会造成路由空洞的扩大。这种扩大通常是致命的，因为这样的空洞会影响到更多路由路径，造成更多的路由失效，同时加重空洞边界路由的负担，路由空洞的扩大速率往往会成几何倍数增长。我们继续沿用上小节的例子，其中新建立的由流向的路由如图所示。万方数据南京邮电大学硕士研究生学位论文第三章路由空洞图路由空洞后期危害由于空洞的分割，条路由只能沿着路由空洞的边界进行数据传输，可以注意到，图中的这个边界节点同时存在在了以上条路由路线中，因此负担了原本倍于普通节点的能量消耗，快速的能量消耗会导致这个边界节点快速衰竭，当这些边界节点能量耗尽，它们所在的位置就会归入路由空洞的范围，路由空洞因此扩大。同时，从图中还可以看出扩大后的路由空洞令由流向的路由再次失效，重新的建立的路由中包含了新的空洞边界节点，其中还同样是由流向的路由中的中继节点，因此将会负担普通节点倍的能量消耗，这导致将会比更快的衰竭，从而生成更大的路由空洞，并且该空洞的扩大速度将会呈指数阶上升，在网络负载大的网络中这种现象尤其明显。路由空洞解决方法目前对于路由空洞的研究主要是以尽量平衡网络中节点的能量负载为目标，以达到延长网络整体生存周期的目的。国内外的研究者为该目标做了大量的研究，根据研究中网络的节点分布，可以将目前已有的解决方法归类为节点非均匀分布和节点均匀分布两类。万方数据南京邮电大学硕士研究生学位论文第三章路由空洞节点非均匀分布顾名思义，节点非均匀分布即在无线网络中单位面积内的节点密度不定相等，通过改变节点密度来使得内外节点能量消耗致，并达到延长网络寿命的目的。非均匀分布的研究比较早，但在散布节点时提出了更高的要求。下面给出如何设置节点密度的求解在式的证明中，可以得到因此在图的能耗模型中，若节点平均分布且节点产生数据速率相同，外环节点的平均能耗总是比内环节点的低。由于若是想让能耗模型中内外环的能量消耗速率相同，即因此若要求内外环的能量消耗速率相同，就要求相邻的两环内的节点数内环大于外环，且相邻两环的节点数量之比要满足式。节点均匀分布节点非均匀分布的无线网络节点可以保持同构的特点，但是由于对布网阶段散布节点作出了更高的要求，并且这样的要求是很难在实际中实现的，因此应用并不广泛，下面介绍几种基于节点均匀分布的路由空洞解决方案。在文献中提出了改变节点能量分布的方法来避免生成能量空洞，由于能量空洞的产生直接原因就是大量的数据传输导致节点周围节点能量消耗的比外层的节点快，那么直接的解决的方式就是在布网的时候就给靠近节点的普通节点更多的能量。实际上这使万方数据单位代码密级硕士学位论文论文题目基于蚁群的路由空洞研究韩晨秦军计算机应用技术分布计算技术与应用工学硕士二四年二月学号姓名导师学科专业研究方向申请学位类别论文提交日期万方数据万方数据南京邮电大学学位论文原创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人学位论文及涉及相关资料若有不实，愿意承担切相关的法律责任。南京邮电大学学位论文使用授权声明本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档允许论文被查阅和借阅可以将学位论文的全部或部分内容编入有关数据库进行检索可以采用影印缩印或扫描等复制手段保存汇编本学位论文。本文电子文档的内容和纸质论文的内容相致。论文的公布包括刊登授权南京邮电大学研究生院筹办理。涉密学位论文在解密后适用本授权书。研究生签名日期研究生签名导师签名日期万方数据摘要是个多跳临时性的对等移动自治系统，它由组带有无线收发装置的移动节点组成。然而由于节点能量有限网络拓扑结构变化频繁的原因，网络同样需要考虑很多传统网络不需要关心的问题，路由空洞问题就是其中重要问题之。路由空洞问题是随网络产生而带来的问题，从产生的原因可分为地理空洞和能量空洞两类。路由空洞初期体现出对网络的危害主要就是延长了路由路径，增加了网络时延。然而随着网络中的会话增多，网络负载加大，传统的路由算法方法会使大量的网络负载落在路由空洞的边缘节点上，造成路由空洞的边缘节点能量快速耗尽，并导致其快速死亡，同时扩大了路由空洞的半径，引来更多的网络负载落在路由空洞的边缘节点上。这样恶性循环，路由空洞会迅速扩大并导致网络生命