（计算机应用技术专业论文）基于aco的wsn路由算法研究.pdf

摘要 w s n ( w i r e l e s ss e n s o rn e t w o r k ) 路由是w s n 应用中很重要的一种技术，它关系 到整个网络的稳定性和健壮性。利用蚂蚁算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 进行 路由是w s n 中一种有效的路由方法，它体现出了比以往算法较大的优越性，比如 可节省网络的能量，有效地延长整个网络的生命周期。近年来，学者们对利用a c o 进行w s n 路由进行了大量的研究和探讨，从网络位置、节省能量、拓扑结构等诸 多方面都取得了长足的进展。 本文围绕a c o 算法及其改进的问题，来研究利用a c o 算法进行的w s n 路由。 本文主要研究工作如下： ( 1 ) 在阐述和总结基本蚁群算法的原理、数学模型和实现过程的基础上，对基 本蚁群算法的最新研究作了分析。其次，对基本蚁群算法的性能和收敛性进行了 理论分析，为后续工作奠定了基础。 ( 2 ) 提出了基于a c o 的w s n 路幽改进算法。针对基本a c o 算法中各节点能 量消耗不均衡，出现局部最优路径的问题，提出了改进的a c o 算法，来解决各节 点能量消耗不均衡的问题，延长整个网络的生命周期，得出较优异的路径。通过 对改进a c o 算法的分析，对该算法进行了仿真。 ( 3 ) 提出了基于g a a c o 的w s n 路由改进算法。通过介绍遗传算法的原理和 运算流程，分析了该算法作为自适应全局概率搜索算法的优越性，并与a c o 算法 进行结合，提出了g a a c o 算法，并分析了其实现过程和收敛性。最后，利用该 算法对w s n 进行路由仿真，仿真结果证明了该算法的有效性。 关键词：w s n 路由；a c o 算法；遗传算法；g a a c o 算法；n s 2 a bs t r a c t t h ew s nr o u t i n gi sa ni m p o r t a n tt e c h n o l o g yo ft h ep r a c t i c a la p p l i c a t i o n so f w s n i tr e l a t e dt h es t a b i l i t ya n dr o b u s t n e s so ft h ee n t i r en e t w o r k i t sa ne f f e c t e d r o u t i n gm e t h o di nw s n w i t ha c o a l g o r i t h m ，a n di t s h o w sm o r ea d v a n t a g e st ot h e u s u a lm e a n s ，f o re x a m p l e ，s a v i n gm o r ep o w e ro fn o d e s ，l e n g t h e n i n gt h el i f e t i m eo f w s n s c h o l a r sm a d eal o te f f o r tt or e s e a r c ha n dd i s c u s sa c or o u t i n gi nw s n ，a n d a c q u i r e dal a r g e - s c a l ep r o g r e s si nm a n yf i e l d s ，f o re x a m p l e ，n o d e sp o s i t i o n ，p o w e r r e t r e n c ha n dt o p o l o g yc o n t r 0 1 t h i sp a p e ri sc e n t r e do nt h ea c o ，a n di ti si m p r o v e da l g o r i t h m ，t os t u d yt h ew s n r o u t i n gu s eb yt h ea c oa l g o r i t h m t h em a i ns t u d i e si nt h i sp a p e ra sf o l l o w e d ： ( 1 ) t h ea c oa l g o r i t h mi sp r e s e n t e d ，t h eb a s i ct h e o r i e sa n dt h eb a s i ca n tc o l o n y o p t i m i z a t i o na r ee m p h a s i z e d t h eb a s i cp r i n c i p l e s ，m a t h e m a t i c a lm o d e l ，a n dt h e p r o c e s so fr e a l i z a t i o n a r ea l la n a l y z e d t h e nat h e o r ya n a l y s i si sm a d ea b o u tt h e p e r f o r m a n c ea n da s t r i n g e n c yo fa c or o u t i n g ( 2 ) ar o u t i n ga l g o r i t h mb a s e do na c o i sp r o p o s e d t h ei m p r o v e da c o r o u t i n gi s p u tf o r w a r d ，t od e a lw i t ht h ed i s p r o p o r t i o no fp o w e rc o n s u m p t i o n ，a v o i dt h ep a r t i a l b e s tp a t ha n dl e n g t h e nt h el i f e t i m eo ft h ew s n t h ea n a l y s i sa n ds i m u l a t i o n sa r em a d e f o rt h ei m p r o v e da c o a l g o r i t h m ( 3 ) an e wm e t h o dg a a c oi sb r o u g h tf o r w a r d t h r o u g hi n t r o d u c i n g t h e p r i n c i p l e sa n df l o wc h a r to fg e n e t i ca l g o r i t h m ，t h ea d v a n t a g e so ft h ea d a p t i v ew h o l e p r o b a b i l i t ys e a r c ha l g o r i t h mi sa n a l y z e d ，i ti sc o m b i n e dw i t ha c or o u t i n g ，a n dt h e p e r f o r m a n c ei ss t u d i e d ，t h es i m u l a t i o n ss h o wt h a tt h eg a a c oi sm o r ee f f e c t i v et h a n a c o k e yw o r d s ：w s nr o u t i n g ；a n tc o l o n yo p t i m i z a t i o n ；g e n e t i ca l g o r i t h m ；g a a c o ； n s 2 n 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：【氓 吼纠僻易月 学位论文版权使用授权书 日 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囹。 ( 请在以上相应方框内打“4 ”) 名：1 撕蜗吼汐怍6 月多日 导师签名：驽l 日期：砂，。年 月多日 第一章引言 1 1 本课题的研究背景及意义 在当今信息技术飞跃发展的时代，以i n t e r n e t 为代表的网络给人们生活工作带 来了巨大地变化，政府上网、企业上网、家庭上网、电子商务等成了当今的热门 话题。嵌入式计算技术、微电子技术、无线通信等技术和分布式信息处理技术地 进步，进一步推动了传感器地快速发展。传感器在微小的体积内能够集成信息收 集、数据处理和无线通信等多种功能。w s n 网络就是由部署在目标区域内的大量 廉价的微型传感器节点所组成，通过无线通信的方式，形成一个多跳而又自组织 的网络系统，它的目的是协作地感知、采集和处理网络覆盖区域中特定目标的信 息，并发送到预定的观察站或者发送给预定的观察者。 w s n 网络将客观物理世界与逻辑信息世界融合在一起，正改变着人类与自然 界之间的交互方式。它作为信息获取和处理的一种新的技术，w s n 的覆盖区域广、 可快速部署、监测度高、高容错性、自组织性、动态性、可远程监控和以数据为 中心等特点比传统有线网络以及无线通讯网络a dh o e 有更广泛地应用。它可以应 用到工作人员无法到达的地方，比如沙漠、战场等，因此必将开辟出不少新颖而 有价值的商业应用。现在已经广泛应用于健康护理、军事侦察、空间探索、建筑 物状态监控、环境监测和智能家居等诸多领域。 虽然无线传感器的发展至今已经在网络协议、效率提升、能量优化、成本降 低等方面都取得了较大的进展，但仍有很多问题需要突破，这些问题涵盖了节点、 电源、跨层设计、网络安全、网络运行维护等方面。随着无线传感技术地不断进 步和完善，相信无线传感器网络必将融入我们的生活，发挥出巨大的应用价值。 无线传感器网络具有很多不同于传统网络的特点，如能量严重受限、拓扑结 构频繁变化等。因此，w s n 网络协议的设计同现有各种网络协议的设计大不相同， 因而面临着各种新的挑战。在协议栈的众多协议中，网络层路由算法的设计作为 一项关键技术已成为目前研究的热点。 1 2 本课题研究领域的研究动态 从2 0 0 0 年开始，国内外对w s n 路由技术的研究日趋热烈，取得了大量研究成 果。美国商业周刊和m i t 技术评论在预测未来技术发展的报告中，分别将w s n 列 为2 1 世纪最有影响的技术和改变世界的技术之一。无线传感器网络的网络通信技 术、中间件技术、节点及其嵌入式软件技术、基础设施技术、数据管理技术等方 面都取得了很快的进展。 根据不同的分类标准，w s n 路由协议可分为不同的类型。学术界目前还没统 一的分类标准。在这里将它分为能量路由协议；平面路由协议，如s p i n ( s e n s o r p r o t o c o l sf o ri n f o r m a t i o nv i an e g o t i a t i o n ) ，d d f d i r e c t e dd i f f u s i o n ) ，r u m o rr o u t i n g ， h r e e m r ( h i g h l y - - r e s i l i e n t ，e n e r g y - - e f f i c i e n tm u l t i p a t hr o u t i n g ) ，s m e n c e ( s m a l l m i n i m u me n e r g yc o m m u n i c a t i o nn e t w o r k ) 等；层次路由协议，如l e a c h ( l o w - - e n e r g ya d a p t i v ec l u s t e r i n gh i e r a r c h y ) ，t e e n ( t h r e s h o l ds e n s i t i v ee n e r g ye f f i c i e n t s e n s o rn e t w o r kp r o t o c 0 1 ) ，a p t e e n ( a d a p t i v ep e r i o d i ct h r e s ho l d - s e n s i t i v ee n e r g y e f f i c i e n ts e n s o rn e t w o r kp r o t o c o l l ，s o p ( s e l f - - o r g a n i z i n gp r o t o c 0 1 ) ；地理位置路由 协议，如g e a r ( g e o g r a p h i ca n de n e r g ya w a r er o u t i n g ) ，g e d i r ( t h eg e o g r a p h i c d i s t a n c er o u t i n g ) 等。目前，对无线传感器路由的研究已经从多个方面展开，如节 点定位、网络拓扑、健壮性、网络生存时间、节点移动、数据传输距离、可扩展 性、安全机制等方面。 由于各种条件的限制，目前对w s n 路由的研究大都是在仿真的实验环境下进 行。当前有许多优秀的网络仿真软件，其中有o p n e t 、n s 2 、m a t l a b 等，这些网络 仿真软件都采用了离散事件模拟技术，并提供了丰富的网络仿真模型库和高级语 言编程接口，这无疑提高了仿真软件的灵活性和使用方便性。 k a z e ms o h r a b y ，d a n i e lm i n o l i ，t a i e bz n a t i 1 j 等介绍了w s n 的技术、协议和 应用：j a g a n n a t h a ns a r a n g a p a n i l 2 】等介绍了无线传感器网络和a dh o c 网络的协议、 性能和网络控制；a z z e d i n eb o u k e r c h e t 3 】介绍了w s n 中的算法和协议。y l i ，t n e w e 4 j 介绍了应根据不同的应用来选择不同的路由协议。s i d d h a r t hr a m e s h t5 】介绍了一个 w s n 的协议框架：余勇昌，韦削6 】描述了无线传感器路由协议所面临的问题与挑 战，分析和比较了典型的平面路由协议及层次路由协议，最后总结了理想路由协 议应该具有的特点以及路由协议未来的研究策略及发展趋势。 由于传统网络中的服务质量( q u a l i t yo fs e r v i c e ，q o s ) 路由协议很难直接有效地 应用到无线传感器网络中，李士宁，滕文星，张琪等1 7 j 提出了新的q o s 路由协议。 他们探讨了无线传感器网络中q o s 路由协议的些特点，分析了设计q o s 路由协 议所面临的挑战；然后着重分析了当前提出的一些q o s 路由协议的q o s 机制、特 点以及优缺点，并对这些路由协议进行了分类和比较；最后总结了q o s 路由协议 未来的研究策略和发展趋势。但是该文主要是进行理论上的分析，距离实际应用 还有较大的差距。 周集良，李彩霞，曹奇英瞵】等通过对w s n 的拓扑结构进行分析和建立网络路 由模型，并结合遗传算法基本原理，提出了一种求解w s n 最优多路径的路由算法。 该算法采用可变长度染色体编码，采用选择、交叉和变异操作，充分利用基站的 信息资源和强大的计算和存储能力，全局地优化了w s n 多路径路由。但是，该算 法将大量的信息都传回基站进行分析与寻路，从更大程度上变相地消耗了节点的 2 能量，使得整个网络的能量利用率大大降低。 杨靖，熊伟丽，徐保副9 j 提出了一种基于蚁群算法的无线传感器网络路由算法。 该算法将网络分簇算法和蚁群算法的优点进行结合，将节点当前可用能量对路由 选择的影响考虑进去，使路由选择时既能均衡节点的能量消耗，又能利用蚁群算 法的正反馈作用末实现快速搜寻从簇头节点到汇聚节点的多跳最优路径，通过在 簇头节点进行数据汇聚降低节点通信的开销，从而降低了路由的开销。它采用了 如图1 1 的分簇模型( 簇直径为2 跳) 。 图1 1 簇的结构 所有与簇头节点相距1 跳的节点都属于簇内的节点。4 号6 号节点( 与簇头节 点的物理距离小于1 跳) 为簇的内部节点，2 号、3 号节点为边界节点( 与簇头节 点距离为1 跳) 。簇头节点将簇内节点和外部节点的通信联系起来。节点有效通信 距离大于等于节点物理距离为节点间能通信的约束条件。从图1 1 可知，簇头节 点与汇聚节点的通信是通过多跳方式进行的。每次要搜寻簇头节点到汇聚节点的 路径时，先从簇头节点发出m 只人工蚂蚁，每只人工蚂蚁都搜索从边界节点到汇 聚节点的最优路径，在进行一定次数的搜索后，找到一条公认的最优路径。为了 加快算法的搜索与收敛速度，该文采用了一个搜索角度，用来限制人工蚂蚁初始 数量及搜索出发点。 但是在该算法中，一方面，当簇内节点太多或者簇与簇之间相距太远时，会 引进簇头节点能量的急速消耗，从而引起网络的不稳定；另一方面，搜索角度的 大小控制难以掌握。如果搜索角度太大，则加大网络的能量、计算开销和收敛速 度；如果搜索角度太小，则有可能引起过早的收敛，找到的是局部最优解。 罗俊，薛胜军，赵娟娟等【l o 】利用粗糙集理论解决不确定性问题的优势，首次 将粗糙集理论应用到无线传感器网络的分簇算法中，提出了一种新的分簇算法： 基于粗糙集的w s n 分簇算法。主要是从簇的形成和簇头的产生两方面进行研究， 并结合粗糙集中的相关理论给出了比较详细的设计方案，成功地解决了传统分簇 算法的弊端。但是该算法的具体应用还有待进一步的研究和完善。 c s u r e s h ，g n a n ad h a s ，d r r s r a t a s t o g i l l l l 提出了利用a c o 方法来设计网络 的分簇结构，以便找出将数据从源节点传送到目的节点的最佳路径，并利用产生 伪随机数的算法对该算法的安全性进行了分析。但是，它没有考虑如何进行有效 的路由，也没有考虑路由中的q o s 保障。 a y o nc h a k r a b o r t y ，k a u s h i kc h a k r a b o r t y 等【1 2 1 通过优化节点的能量消耗提出了 一种新的数据汇聚算法，它利用粒子群优化算法( p a r t i c a ls w a r mo p t i m i z a t i o n ，p s o ) 和模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 来构造一个次优的数据汇聚链，以选择一 个相对有效率的节点来进行对基站的数据传送工作。在该算法中，每个节点只和 邻节点通信，并且根据节点的剩余能量和节点位置来轮流做传输节点，该算法比 l e a c h ( l o w e n e r g ya d a p t i v ec l u s t e r i n gh i e r a r c h y ) 和p e g a s i s ( p o w e r - e f f i c i e n t g a t h e r i n gi ns e n s o ri n f o r m a t i o ns y s t e m s ) 在相同条件下要有更大的优越性。 k s a l e e m ，n f i s a l ，s h a f i z a h 等【l3 】针对w s n 中新节点的加入以及旧节点的 失效问题，利用基于蚂蚁的自治路由算法，在选择路径时考虑了节点的能量水平、 连接质量、丢包率等因素，选出最优的路径。该算法主要分为三个管理模块：路 由管理模块，邻居节点管理模块，能量管理模块。他们的算法系统框图如图1 2 。 o 图1 2k s a l e e m ，n f i s a l ，s h a f i z a h 等的系统框图 在k s a l e e m ，n f i s a l ，s h a f i z a h 等的算法中，路由管理是重点，如图1 3 。 当进行路由时，它会从路由表中选择最优的“下一个节点 放到路由路径中去， 如果没有“最优 ，它会调用邻居节点管理，这一模块，从中选出“最优 ，如图 1 4 。 能量模块则根据网络的运行情况和对收发信息的要求，自动的调节收发信息 的节点，如一节点能量不达到标准，则换一节点收发信息。 4 仿真分析表明，该算法具有良好的性能，比较符合w s n 路由的要求，如能量 消耗水平，路由成功率和路由的时间限制等。 ， 黔 r ，髯 、 ，、 f 等量嚣1 、m 、k 。 ”、 广嚣芝吣 1 船 。一一 o f 加 夕 图1 3k s a l e e m ，n f i s a l ，s h a f i z a h 等的路由管理 图1 4k s a l e c m ，n f i s a l ，s h a f i z a h 等的邻居节点管理 夏鸿斌，须文波，刘渊【1 4 1 通过改进a c o 算法来达到一种能实现通信网络负 载平衡的群体智能路由策略。该算法采用的主要思想为：将蚁群划分为若干个子 群，不同子群的蚂蚁释放出不同类型的信息素。通过不同类型信息素之间的相互 制约作用，以及对链路负载的测量，提出了三种策略实现负载平衡路由。在模拟 网络上进行了不同策略的对比实验，以及与已有的群体智能路由算法的运行测试 比较。实验结果表明，他们提出的路由策略具有较好的效果和一定的优势。但是， 该算法随着子群的增大，其区别不同子群中信息素的要求也提高，给w s n 网络造 成了额外的计算开销，从而影响其整个网络的性能。 姜华，李寰i l5 j 针对无线m e s h 网q o s 的路由特点，结合遗传算法和蚁群算法 的特性，设计了一种遗传算法和蚁群算法相结合的算法，提出了遗传蚁群算法求 解无线m e s h 网q o s 路由问题的解决方案。该算法采用遗传算法生成初始信息素 分布，利用蚁群算法求精确解，并在遗传算法运行过程中动态确定遗传算法与蚁 群算法的最佳融合时机，实现两个算法的优势互补。实验结果表明，该算法在无 线m e s h 网q o s 路由选择中是高效的，性能明显优于遗传算法和蚁群算法。该算 法的思想可以利用到w s n 中。 刘晓东，冒勇军【1 6 】针对无线传感网络节点能量有限的特点，提出了一种改进 蚁群算法，将蚂蚁的信息素、网络的节点能量和各节点间的时延相结合，形成算 法控制因子。仿真结果表明，该算法可以均衡网络中各个节点的能量消耗，延长 整个网络的生命周期，缓解网络拥塞并降低平均传输时延。其思想可以利用到w s n 中。 a y a na c h a r y a ，a n a n ds e e t h a r a m ，a b h i s h e kb h a t t a c h a r y y a 等1 1 7 l 考虑到节点到 基站的路径长度和节点问路径长度两个因素，提出了利用a c o 算法来进行路由， 实验表明，它更好地延长了整个网络的生命周期，平衡了各节点的能量消耗，并 且保证选择的路径是最短的，从而从另一方面提高网络的性能。但是该算法没有 考虑数据丢包率以及时延等因素。 l e a c h 成簇算法是传感器网络中减少能量消耗的一种重要技术，它能够增强 网络的扩展性并延长整个网络的生命周期。l e a c h c 是l e a c h 协议的一个特定 版本，是一种集中式的簇头产生算法，由基站负责挑选簇头。但是节点与簇头， 簇头与基站间的通信都是通过一跳通信来进行，这样会造成簇头节点即要进行数 据的汇聚，又要进行通信，从而导致节点负载过重。朱子健，赵广社，苏丽芳等【l 8 】 在l e a c h c 协议中引入了非对称的多跳算法，使得簇头之间形成一个多跳的最优 路径通向基站，从而减少了簇头节点能量的消耗，延长了w s n 的寿命。但是其频 繁转换所造成的能量消耗，使得整个网络的整体性能趋于下降，特别是在比较大 型的网络中。 熊伟丽，王振兴，徐保国【19 j 为了更加有效地使用无线传感器节点有限的能量， 将蚁群优化算法应用到无线传感器网络的路径选择中，利用蚁群的动态适应性和 寻优能力，在分簇产生的簇头节点之间找到最优路径，进而达到均衡网络负载、 延长整个网络生命周期的目的。该算法没有考虑路径选择中的时延问题。 还有一些文献分别从地理位置2 0 - 2 加、网络的( 拓扑) 结构2 3 2 钔、自适应性2 6 - 2 引、 层次划分( 分簇) c 2 9 , 3 0 3 、能量控制 3 1 - 3 4 、基于生物特性的优化算法3 5 - 3 83 等方面 提出了不同的路由算法和见解，这些成果对w s n 路由的研究起了重要的推动作用， 为后来的学习和研究奠定了基础，指明了方向。 1 3 本文拟研究的主要内容 基于以上阐述和总结，可以得出：w s n 路由要得到进一步的发展，目前面临着 如下几个方面的问题： 1 、由于w s n 节点有限的能量、有限的计算和存储能力，在路由中如何最大程 6 度的利用好节点的能量和节点的处理能力，以便发挥出w s n 最大的路由载荷。 2 、网络路由中的设计理念和实际应用有较大的差距。 3 、路由的q o s 如何得到很好的保证及路由安全问题。 4 、路由中节点密度和空间多样性的解决。 5 、网络运行的维护问题。 本文将重点围绕第一个问题来对w s n 网络路由展开研究，以探讨出更好地符 合w s n 特点的方法。基于a c o 算法的正反馈性、协同性、并行性、鲁棒性等优点， 在此基础上进行改进，根据w s n 的特性，更好地进行w s n 路由。 本文所做的工作包括一下几个方面： 1 、在总结w s n 网络路由特点和a c o 算法的原理、数学模型、收敛性等特征 的基础上，提出了一种基于a c o 的w s n 改进路由算法。针对基本a c o 算法中各 节点能量消耗不均衡，出现局部最优路径的问题，提出了改进的a c o 算法，即通 过信息素不同的更新方式，来解决各节点能量消耗不均衡的现象，延长整个网络 的生命周期，得出较优异的路由路径。 2 、在分析了g a ( g e n e t i c a l g o r i t h m ) 算法特性的基础上，提出了基于g a a c o 的w s n 路由改进算法。通过阐述遗传算法的基本原理和运算流程，分析了该算法 作为自适应全局概率搜索算法的优越性，并与a c o 算法进行结合，结合两种算法 的优点，提出了g a a c o 算法。 1 4 本文的组织结构 本文的组织结构如下： 第一章为引言。总结了研究w s n 路由的背景和意义，国内外研究现状，并阐 述了本文所做的工作和文章的组织结构。 第二章为w s n 路由和蚁群算法。通过对平面路由、层次路由、地理位置路由、 可靠路由协议中几种算法思想及特点的简单介绍，为后面的学习和研究打下基础。 然后总结了蚁群优化算法的一般理论。重点阐述了a c o 算法的一般理论和基本蚁 群算法。通过介绍蚂蚁的觅食行为，总结出人工蚂蚁和自然蚂蚁的异同，从而使 人工蚂蚁能够继承自然蚂蚁的优点，并根据问题的特点，赋予人工蚂蚁更适合解 空间的一些特点，便于更好地完成工作。随后，对基本蚁群算法的性能和收敛性 进行了分析。 第三章提出了基于a c o 的w s n 路由改进算法。针对基本a c o 算法中各节点 能量消耗不均衡，出现局部最优路径的问题，提出了改进的a c o 算法，并利用该 算法对w s n 进行仿真路由，并分析了仿真结果。 第四章提出了基于g a a c o 的w s n 路由改进算法。通过阐述遗传算法的原理 和运算流程，分析了该算法作为自适应全局概率搜索算法的优越性，并与a c o 算 法进行结合，提出了g a a c o 算法，接着分析了其实现过程和收敛性。最后，利 用该算法对w s n 进行了仿真路由，分析其仿真结果。 第五章为总结与展望。对全文的主要研究工作进行总结，并展望下一步的研 究工作。 8 第二章w s n 路由及蚁群算法 2 1w s n 路由协议中几种算法思想概述 w s n 路由协议是w s n 组网的基础，其主要任务就是建立能量高效的优化路 径和可靠地传输传感器节点到s i n k 节点的数据。w s n 路由协议根据不同的标准， 其分类的方法也很多，目前国内外科研人员已设计了多种面向w s n 的路由协议， 本文将其分为四类：平面路由协议、层次路由协议、地理位置路由协议和可靠路 由协议。w s n 路由算法是w s n 路由协议的重要组成部分，在此将介绍这些路由 协议中一些比较典型的算法。 2 1 1 平面路由 1 信息协商协议 s p i n ( s e n s o rp r o t o c o l sf o ri n f o r m a t i o nv i an e g o t i a t i o n ) 协议是一组基于协商并 且具有能量自适应功能的传播协议 3 9 o 该协议中，节点利用三种消息进行通信： a d v ( 数据描述) 消息、r e q ( 数据请求) 消息和d a t a ( 数据) 消息。该协议用抽象的 元数据方式对数据进行命名，其方式没有统一标准。节点产生或收到数据后，用 包含元数据的数据描述消息向邻节点通告，需要数据的邻节点则用数据请求消息 提出请求，然后将数据消息发送到请求节点。该协议的优点是数据描述消息减轻 了内爆问题；通过数据命名解决了交叠问题；节点根据自身的资源和应用信息决 定是否进行数据描述的通告，避免了资源盲目利用的问题：与f l o o d i n g 和g o s s i p i n g 协议相比，更加有效地节约了能量。 可珂 珂 数据传输 a d v 扩散数据请求数据传输 图2 1s p i n 路由的建立与数据传输 图2 1 表示了s p i n 路由的建立与数据传输过程。该协议的缺点是，s p i n 的 广播机制不能保证数据的可靠传送，当产生或收到数据的节点的所有邻节点都不 9 需要该数据时，将导致该数据不能继续转发，以致较远节点无法得到需要的数据； 而当某s i n k 点对任何数据都有需要时，其周围节点的能量很容易耗尽。 有学者针对s p i n 协议和无线传感器网络的特点，提出了一种改进方法，解决 了路由选择和数据发送的盲点问题1 4 。 2 定向扩散路由协议 定向扩散d d ( d i r e c t e dd i f f u s i o n ) 路由协议是一种以数据为中心的信息传播协 议，与已有的路由算法有着截然不同的实现机制 3 9 30 运行d d 的传感器节点使用 基于属性的命名机制来描述数据，并通过向所有节点发送对某个命名数据的 i n t e r e s t 信息来完成数据收集。在传播i n t e r e s t 的过程中，指定范围内的节点利用缓 存机制动态维护接收数据的属性及指向信息源的梯度矢量等信息，同时激活相关 传感器节点来采集与该i n t e r e s t 相匹配的信息。节点对采集的信息进行简单的预处 理后，利用本地化规则和加强算法，建立一条到达目的节点的最佳路径。该协议 的优点是采用多路径，健壮性好，使用数据聚合减少了数据通信量，降低了能量 消耗，s i n k 节点根据实际情况采取增强或者减弱的方式，有效的利用能量，使用 查询驱动机制按需建立路由，避免了保存全网的信息。经仿真分析，该算法具有 很好的节能和可扩展特性。其缺点是建立梯度的过程开销很大，不适合多s i n k 节 点网络，数据聚合采用时间同步技术，带来较大的开销和时延。 2 1 2 层次路由 1 低能量自适应分簇协议 l e a c h 协议是一种基于多簇结构的路由协议 3 9 10 它的基本思想是通过随机 而又循环地选择簇首节点将整个网络的能量负载平均分配到每个传感器节点中， 从而达到降低网络能源消耗、提高网络整体生存时间的目的。l e a c h 在运行过程 中不断地循环执行簇重构过程。每个重构过程可分成两个阶段：簇建立阶段和数 据传输稳定阶段。为了节省资源开销，稳定阶段的持续时间一般要长于建立阶段 的时间。该协议的优点是随机选举簇头，很大程度上避免了某个簇头的能量过分 消耗，提高了网络的生存时间，而数据聚合则减少了节点间的通信量。与一般的 基于平面结构的路由协议和静态的基于多簇结构的路由协议相比，l e a c h 协议可 以将网络整体生存时间延长大约1 5 。其缺点是采用一跳通信，虽然传输时延小， 但要求节点具有较大的通信能力；另外，其扩展性不理想，不适合大规模的网络； 且在小规模网络中，离s i n k 节点较远的节点由于通信时要加大功率，也会导致其 生存时间变短；还有就是其频繁的选举簇头所引发的通信也消耗了不少能量。 针对l e a c h 路由协议中簇头节点在空间上分布不均以及在远距离数据传输 过程中能量消耗过多等不足，有学者提出一种改进的l e a c h 路由协议 l e a c h z m h ( 基于l e a c h 的区域簇头选择簇间多跳传输路由协议) ，采用了簇头 选择基于区域，簇间数据传输通过多跳进行的方法。他们给出了l e a c h z m h 的 1 0 正确性证明和复杂性分析。n s 2 仿真表明，改进的协议有效地延长了网络的存活 时间，性能优于l e a c h 协议1 4 。 2 节能的阈值敏感路由 节能的阈值敏感路由t e e n ( t h r e s h o l ds e n s i t i v ee n e r g ye f f i c i e n ts e n s o r n e t w o r kp r o t o c 0 1 ) 是具有实时性的路由协议3 明。它采用了与l e a c h 协议相同的多 簇结构和运行方式。不同的是，在簇的建立过程中，随着簇首节点的选定，簇首 除了通过t d m a ( t i m ed i v i s i o nm u l t i p l ea c c e s s ) 方法实现数据的调度，还向簇内成 员广播有关数据的两个参数：硬阈值和软阈值。硬阈值的初值由用户根据具体的 应用来进行确定；软阈值的初值为0 。在每轮簇头轮换的时候将两个阈值广播出去， 当监测数据第一次超过设置的硬阈值时，节点把这次数据设为新的硬阈值，并在 接下来的时隙内发送它。之后，只有监测数据超过硬阈值并且监测数据的变化幅 度不小于软阈值时，节点才会传送最新的监测数据，并将它设为新的硬闽值。通 过设置硬阈值和软闽值两个参数，t e e n 能够大大地减少数据传送的次数，从而达 到比l e a c h 算法更节能的目的。该协议的优点是适用于实时应用系统，可以对突 发事件做出快速反应，它的缺点是阈值的设定。如果阈值达不到，则不会传送任 何数据，二是如果符合阈值规定，则其立即传送数据，可能造成信息的冲突或者 信号的干扰。 2 1 3 地理位置路由 考虑到s e n s o r 节点能够直接获取自身地理位置，或者通过某些标杆节点获取， 利用节点的位置信息，把查询或者数据转发给需要的区域，缩减数据的传送范围， 从而进一步降低能耗。在很多路由算法中，相当的工作通过移植部分在a dh o c 研 究中的成果应用在w s n 中，取得很好的效果。 1 基于地理位置的自适应路由协议 g a f ( g e o g r a p h i ca d a p t i v ef i d e l i t y ) 主要为移动a d - h o c 网络设计，但是也可用 在无线传感器网络中。该协议把监测区域划分为若干虚拟的单元格，将节点按照 位置信息不同而划入不同的单元格；在每个单元格中定期选举产生一个簇头节点， 只有簇头节点保持活动，其他节点进入睡眠状态。在g a f 中，节点轮流从睡眠状 态变到工作状态，达到网络负载均衡。为了处理节点的移动性，节点估算自己离 开网格的时间并将之通知相邻节点，因而睡眠节点可以相应调整睡眠时间，在工 作节点离开本网格之前醒来并接替工作，从而保持路由精度。g a f 的优点是节点 数量增加可大大提高网络寿命，同时也解决了节点移动的问题。但是g a f 的缺陷 是在节点稀疏的情况下的节能效果不好，而且网格簇头的选择是随机的，没有考 虑节点剩余能量。 2 基于地理位置的能量感知路由协议 g e a r ( g e o g r a p h i ca n de n e r g ya w a r er o u t i n g ) 该协议算法假设己知事件区域的 位置信息，每个节点知道自己的位置信息和剩余能量信息，通过一个简单的h e l l o 消息交换机制来了解所有邻居节点的位置信息和剩余能量信息。将数据分组传送 到目标区域中所有的节点分两个阶段：目标域的数据传送阶段和域内的数据传送 阶段。在前一个阶段，当节点接收到数据分组后，它将邻接点同目标域的代价和 自己与目标域的代价相比较，代价更小，则选择代价小的邻接点作为下一跳节点； 若不存在更小代价，则认为存在路由空洞“h o l e ”，节点将根据邻居的最小代价来 选择下一跳节点。在后一阶段，可通过域内直接洪泛和迭代的目标域数据传送两 种方式让数据在域内扩散，直到目标域剩下唯一的节点。g e a r 的优点是：它将 网络中扩散的信息局限到适当的位置区域中，以减少了中间节点数量，从而降低 路由建立和数据传送的能量开销，进而更有效地提高网络的生命周期。其缺点是 依赖节点的g p s ( g l o b a lp o s i t i o n i n gs y s t e m ) 定位信息，成本较高。 该算法在d i r e c t e dd i f f u s i o n 算法的基础上做了一系列改进，考虑到s e n s o r 节 点的位置信息，在i n t e r e s t 报文中添加地址信息字段，并将i n t e r e s t 信息往特定的 方向传输以替代原来的泛洪方式，从而显著地节省其能量消耗。该算法引入了估 计代价( e s t i m a t e dc o s t ) 和自学习代价( 1 e a r n i n gc o s t ) 。通过计算两者的差值来选取 更接近s i n k 节点的节点作为下一跳节点。 2 1 4 可靠路由协议 基于某些应用对数据传输的可靠性提出了更高的要求，因而传感器网络路由 中一个重要的方面是研究可靠路由协议。传感器节点由于有限的能量供应和恶劣 的工作环境而经常面临失效的问题，为研究适合于传感器网络的可靠路由协议增 加了困难。 目前，研究人员提出的可靠路由协议主要从以下两个方面考虑：一是利用节点 的冗余性提供多条路径以保证通信的可靠性；二是建立对传输可靠性的估计机制， 从而保证每跳传输的可靠性。另外，某些传感器网络应用需要节点间通信具有一 定的实时性。 s p e e d 协议是一种很有效的可靠式路由协议，它在一定程度上实现了端到端的 传输速率保证、网络拥塞控制以及负载平衡。s p e e d 协议首先在相邻节点间交换传 输延迟，以得到总的网络负载情况；然后节点利用局部的地理信息和传输速率信 息选择下一跳的节点；同时通过邻居反馈机制来保证网络传输畅通，并且通过反 向压力路由变更机制避开延迟太大的链路和路由空洞。 1 s p e e d 协议设计目标 1 1 只保持邻居节点的信息，不用路由表； 2 ) 提供“力所能及 的速度来满足传输信息的实时性要求； 3 ) 不需要m a c 层有特殊的实时机制或额外的m a c 层q o s 机制； 4 ) 利用反向压力机制避开网络拥塞，提供q o s ； 1 2 5 ) 利用不确定的前向并发路径来平衡网络繁忙时的负载； 6 ) 采用分布式的算法来减少洪泛控制信息； 7 ) 采用与前述避免拥塞类似的机制来避免路由空洞。 2 s p e e d 协议的核心结构 1 ) 延迟估计机制 在s p e e d 协议中，延迟估计机制的作用是得到网络的负载情况，以判断网络 是否发生拥塞。节点记录到邻居节点的通信延迟来表示网络局部的通信负载。具 体过程是：发送节点给数据分组并加上时间戳；接收节点计算从收到数据分组到 发出确认的时间间隔，并将其作为一个字段加入确认报文；发送节点收到确认后， 从收发时间差中减去接收节点的处理时间，得到一跳的通信延迟。 2 ) s n g f 算法 s n g f ( s t a t e l e s sn o n d e t e r m i n i s t i cg e o g r a p h i cf o r w a r d i n g ) 算法用来选择满足传 输速率要求的下一跳节点的算法。节点将邻居节点分为两类：比自己距离目标区 域更近的节点和比自己离目标区域更远的节点。前者称为候选转发节点集合 ( f o r w a r d i n gc a n d i d a t es e t ，f c s ) 。节点计算到其f c s 集合中的每个节点的传输速 率。f c s 集合中的节点又根据传输速率是否满足预定的传输速率阈值，再分为两 类：大于速率阈值的邻居节点和小于速率阈值的邻居节点。若f c s 集合中有节点 的传输速率大于速率阈值，则在这些节点中按照一定的概率分布选择下一跳节点， 节点的传输速率越大，被选中的概率越大。 3 1 邻居反馈策略 邻居反馈策略是当s n g f 路由算法中找不到满足传输速率要求的下一跳节点 时采取的补偿机制。节点首先查看f c s 集合的节点，若f c s 集合中所有节点的传 输差错率大于零，则按照特定的公式计算转发概率；若存在节点的传输差错率为 零，表明存在节点