（计算机科学与技术专业论文）基于蚁群算法的自组网路由技术研究.pdf

国防科技大学研究生院学位论文 摘要 移动a d h o e 网络是一种具有高度动态拓扑结构、节点任意移动的自组织网络， 其相互通信的两个节点间常常没有直接的链路，数据需要其他中间节点中继转发， 也被称为“移动多跳网络”。移动自组网灵活机动、适应环境能力强，对终端性 能要求不高，不需要固定基础设施的支持，具有较强的鲁棒性、抗毁性。 然而，移动自组网的特性也为路由协议提出了更高的要求。节点的移动性使 网络拓扑结构动态变化，终端使用可耗尽资源，无线传输带宽有限，使设计高度 自适应的路由协议，成为移动a dh o c 网络发展的一大挑战。 蚁群算法是一种从自然界中的社会性昆虫的特性受到启发，发展而来的一种 群集智能的搜索算法。所谓群集智能，是指单个智能个体只能完成相当简单的任 务，而整个智能体种群的合作则能出色地完成复杂的任务。蚂蚁搜索食物是群集 智能一个典型的例子。 蚁群算法在许多组合优化问题中获得了广泛的应用。由于分布式的计算、单 个智能体实现简单、支持多路径的特性，蚁群算法很适合用于a dh o c 网络路由。 基于蚁群的路由算法很多，然而人们在使用中发现，采用信息素正反馈机制，容 易导致停滞，即某条可用路径上的信息素浓度相比其它路径处于绝对优势，使绝 大多数数据分组沿此路径发送，导致网络性能大幅降低。停滞会使算法陷入次优 解，即使有更好的路径存在，也会因信息素浓度不高而较小可能被节点选择。如 果人为地控制信息素的浓度差别，虽然可避免路径的选择概率过高，但也有可能 使算法收敛交慢，同样会降低网络性能。 本文研究了蚁群算法的收敛性质，包括其在链路双向开销对称和不对称的网 络环境中的收敛性质，从理论的角度探究了停滞产生的原因。研究了不同控制信 息素方法对蚁群算法收敛性质的影响，以此为基础对蚁群算法进行改进。基于蚁 群算法使用概率选择机制进行路由的特性，本文提出使用信息熵来改进蚁群算法。 信息熵作为对系统不确定性的度量，能够自适应地控制不同路径选择概率的差距， 在保证网络资源利用率的前提下避免停滞；而使用信息熵衡量系统不确定性，也 可以为信息素更新的幅度提供依据，使系统能迅速收敛。 在经过对不同算法的分析和模拟后，本文提出了基于信息熵的蚁群路由算法， e a c r a 。该算法较能高效合理地分配网络资源，在保持多路径的同时，使最优路 径的使用率最高，而且较一般蚁群算法更能适应网络的变化，避免停滞的产生。 在m a t l a b 和n s - 2 仿真环境中的模拟结果，显示了e a c r a 的优异性能。 主题词：蚁群优化算法，a dh o c 网络，路由算法，信息熵，自适应 第i 页 国防科技大学研究生院学位论文 a b s t r a c t m o b i l ea dh o en e t w o r k s ( m a n e t ) a r eo n eo ft h ec a t e g o r i e so fw i r e l e s sn e t w o r k s w h i c hc o m p o s e db ys e l f - o r g a n i z e dn o d e st h a th a v eh i 曲m o b i l i t ya n dc a nm o v e a r b i t r a r i l y i f t w on o d e si nm o b i l ea dh o en e t w o r k sn e e dc o m m u n i c a t ew i t he a c ho t h e r , t h e r ei sc o n s t a n t l yn od i r e c tl i n kb e t w e e nt h e ma n dd a t ap a c k e t sm u s tb ef o r w a r d e db y o t h e ri n t e r m e d i a t en o d e s ，s om a n e ta r ea l s on a m e d m u l t i - h o pn e t w o r k m o b i l ea d h o en e t w o r k sa r ef l e x i b l ea n dc a nb ed e p l o y e di nm o s te l c e i lc r i t i c a le n v i r o n m e n t s ，a n d t h e r ei sn oh i g hp e r f o r m a n c er e q u i r e m e n tf o re n d p o i n t st oj o i nt h en e t w o r k m a n e t d o e sn o tn e e da n ys u p p o r to f f i x e di n f r a s t r u c t u r e s oi ti sv e r yr o b u s ta n de f f e c t i v e b 1 止m a n e t sc h 甜a c t o r sa l s oc h a l l e n g er o u t i n ga l g o r i t h m sf o rm a n e t n o d e s m o b i l i t yc a u s e st h en e t w o r k st o p o l o g yd y n a m i c a l l yc h a n 西n g , e n d p o i n t sa r eo ff i n i t e e n e r g yp o w e r , a n dt h eb a n d w i d t ho fw i r e l e s st r a n s m i s s i o ni sa l s on a r r o w r o u t i n gi n m o b i l ea dh o en e t w o r k si sar e a lc h a l l e n g e a n tc o l o n ya l g o r i t h mi sak i n do fs w a r mi n t e l l i g e n c eh e u r i s t i ca p p r o a c ht h a t i n s p i r e df r o ms o c i a li n s e c t si nn a t u r e s w a r mi n t e l l i g e n c er e f e r st h a to n ea g e n t c a l lo n l y d os o m ee a s yj o b s a n dv e r yc o m p l i c a t et a s k sm u s ta c c o m p l i s h e db yt h ec o o p e r a t i o no f e a c ha g e n ti naw h o l ec o l o n y at y p i c a le x a m p l eo fs w a r mi n t e l l i g e n c ei sa n t sf m d i n g f o o d s a n tc o l o n ya l g o r i t h m sh a v ew i d e l ya p p l i e dt os o l v em a n ye o m b i n a t o r yp r o b l e m s a n tc o l o n ya l g o r i t h 仰s u p p o r td i s t r i b u t e dc o m p u t i n ga n dm u l t i - p a t h t h ea g e n t sa r ea l s o e a s yt oi m p l e m e n t s oa n tc o l o n ya l g o r i t h m sj u s tm e e tt h en e e do fm o b i l ea dh o e n e t w o r kr o u t i n g n o wt h e r ea l em a n yk i n d so f a n tb a s e dr o u t i n ga l g o r i t h m sf o rm a n e t h o w e v e r , d u r i n gu s i n ga n tc o l o n ya l g o r i t h m , p e o p l ef o u n dt h a tp o s i t i v ep h e r o m o n e f e e d b a c km e c h a n i s mc a nl e a ds t a g n a t i o n , t h a ti s ，i ns e v e r a le f f e c t i v ep a t h s ，o n l yo n e p a t hh a sa b s o l u t ed o m i n a n tp h e r o m o n et r a i lt h i c k n e s sa n dm o s td a t ap a c k e t sa r e f o r w a r d e db yt h i sp a t h ，w h i c hs u b s t a n t i a l l yr e d u c e st h en e t w o r k sp e r f o r m a n c e e v e n t h e r ei sa n o t h e rm o r ee f f e c t i v ep a t h , d a t ap a c k e t sw i l ll e s sp r o b a b l yc h o o s ei t s o ， s t a g n a t i o nw i l lc a u s et h ea l g o r i t h mp l u n g ei n t ol e s so p t i m a ls o l u t i o m t h e r ea r cs o m e a p p r o a c h e st or i g i d l yr e s t r a i np h e r o m o n et r a i lt h i c k n e s si ne v e r yp a t hf r o mg e e i n ga n e x c e s s i v eh i 曲o rl o wv a l u e b u tt h i sk i n do f r e s t r i c t i o nm a yc a l l s ea l g o r i t h mc o n v e r g e s l o w l y ，w h i c ha l s ow i l lg e tal o w e rp e r f o r m a n c ei nd y 蚴n i ct o p o l o g yn e t w o r k s 1 1 l i sp a p e rg i v e sad e t a i lr e s e a r c ho nc o n v e r g e n c eo fa n tc o l o n ya l g o r i t h m s i n c l u d e di nt h ec o s t - s y m m e t r i ca n dc o s t - a s y m m e t r i cn e t w o r ke n v k o n m e n t s w ep r o v e t w ot h e o r e m sw h i c hd e p i c tt h e 黜o f s t a g n a t i o n w ci n v e s t i g a t ea n dc o m p a r es e v e r a l p h e r o m o n er e s t r i c t i o na p p r o a c h e s e f f e c to na n tc o l o n ya l g o r i t h m , b a s e do nt h i s ，w e i m p r o v ea n tc o l o n ya l g o r i t h m b e c a u s ea n t su t i l i z eap r o b a b i l i t ya p p r o a c ht oc h o o s e p a t h s ，w ep r o p o s ei n f o r m a t i o ne n t r o p yt oi m p r o v ea n tc o l o n ya l g o r i t h m s i n f o r m a t i o n 第n 页 国防科技大学研究生院学位论文 e n t r o p yi s t h eb e s tm e a s u r ef o ru n c e r t a i n t y , a n dc a l la d a p t i v e l yc o n t r o lc h o o s i n g p r o b a b i l i t yd i f f e r e n c e so fd i f f e r e n tp a t h s s ou s i n gi n f o r m a t i o ne n t r o p yw e9 8 1 1a v o i d s t a g n a t i o n w i t hh i g hn e t w o r kl e s o u r c ea s s i g n m e n t w h a t sm o r e , w ec a nu i n f o r m a t i o ne n t r o p yv a l u eo ft h es y s t e mt oc o n t r o lp h e r o m o n eu p c h 忙v a l u e ，w h i c hc a n l e a daq u i c kc o n v e r g e n c e a f t e rl o t so fa n a l y s i sa n ds i m u l a t i o n , t h i sp a p e rd e p i c t st h ee n t r o p yb a s e da n t c o l o n ya l g o r i t h m e a c r a t h i sa l g o r i t h mc a na s s i g nn e t w o r kr e s o u “瑚e f f e c t i v e l ya n d r e a s o n a b l y ，a n de n s u r em u l t i - p a t he f f e c t i v ec o e x i s tw i t hh i g h e s tu t i l i z a t i o nr a t i oo ft h e b e s to p t i m a lp a t h e a c r ai si n o l a d a p t i v et h a n5 0 m eo t h e ra n tc o l o n ya l g o r i t h r a s ，a n d c a na v o i ds t a g n a t i o ne f f e c t i v e l y w eh a v es i m u l a t i o n so nm a t l a ba n dn s - 2 ，a l lt h e r e s u l t ss h o we x c e l l e n tp 础o r m a n c eo f e a c r a k e yw o r d s ：a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ，a dh u en e t w o r k ，r o u t i n ga l g o r i t h m ， i n f o r m a t i o ne n t r o p y , a d a p t i v e 国防科技大学研究生院学位论文 表目录 表3 1 自组网中的路由技术。 表4 1 图4 7 中各条链路相关属性值 表4 2 图4 8 中各条链路相关属性值4 0 表4 3 图4 9 中各条链路相关属性值 表6 1 模拟环境参数 表6 2e a c r a 算法参数 4 1 5 9 第页 国防科技大学研究生院学位论文 图1 1 图2 1 图2 2 图3 1 图3 2 图3 3 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图5 9 图5 1 0 图5 1 1 图5 1 2 图5 1 3 图5 1 4 图5 1 5 图6 1 图6 2 图目录 一个无线a dh o e 网络 a dh o e 的多跳组网方式 单向信道示例 现实中蚁群寻找食物的过程 蚁群觅食的“双桥”实验 a c o 元搜索算法的伪代码 信息素蒸发示意图 老化示意图 两点模型 1 5 5 1 3 1 4 1 8 2 4 2 4 一般蚁群算法的伪代码图3 3 对称开销网络中一般概率算法收敛过程示意图 概率初值对收敛过程的影响 双向开销相近时一般概率算法收敛结果 双向开销相关较大网络中一般概率算法收敛过程示意图 3 3 3 4 3 9 4 0 双向开销差异较大的网络中一般概率算法受概率初值的影响示意图4 l 信息熵值的图形 信息熵机制的自适应特点 一般概率算法结合信息熵机制的概率表更新伪代码 一般概率算法结合限制信息素方法的概率表更新伪代码 一般概率算法结合限制信息素方法，两条链路时收敛过程 一般概率算法结合限制信息素方法，三条链路时收敛过程 一般概率算法结合限制信息素方法，四条链路时收敛过程 一般概率算法结合信息素平滑机制的概率表更新伪代码 仅仅使用平滑机制时算法运行过程 一般概率算法结合信息素平滑机制，两条链路时收敛过程 一般概率算法结合信息素平滑机制，三条链路时收敛过程 一般概率算法结合信息素平滑机制，四条链路时收敛过程，5 0 基于信息熵的一般概率算法，两条链路时的收敛过程 基于信息熵的一般概率算法，三条链路时的收敛过程 基于信息熵的一般概率算法，两条链路时的收敛过程 f a n t 示意图 b a n t 示意图 5 1 5 2 5 2 5 4 第v 页 们衢铂钉钉铝铝钞盼如 国防科技大学研究生院学位论文 图6 3 图6 4 图6 5 图6 6 平均递交率与停顿时间的函数图 路由协议的开销，由控制信息与数据信息比衡量 路由协议开销，由路由分组数量表示。 路由协议的平均端到端延迟。 6 0 6 1 。6 2 6 3 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目： 基王避箕洼塑自塑圆整由挂盔珏窀 学位论文作者签名：金望日期：如。6 年，) 月，1 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题日：基王数壁篡洼数皂堡圆整直技盔盈塞 学位论文作者签名：猃堕日期：加。绛，2 月，j 日 作者指导教师签名：坳宠日期：力柑j 矿月i f 日 国防科技大学研究生院学位论文 第一章绪论 1 1 课题背景及研究意义 1 1 1 无线a dh o c 网络概述 无线a dh o e 网络是一类不需要任何固定的基础设施支持、多跳中继的无线网 络。由于没有中心控制器，如其它无线网络中管理路由决策的固定路由器，在a dh o e 网络中进行路由有许多困难。无线a dh o e 网络中的所有移动节点通过分布式相互 协作的方式来进行路由决策。也就是说，a d h o e 无线网中的所有移动节点既作为终 端进行数据的收发，又充当网络路由器进行路由决策。a d h o e 无线网络的一个例子 如图1 1 所示。 图1 1 一个无线a d h o e 网络 a dh o e 无线网络适用于许多没有网络基础设施可供组网或者部署这些设施代 价太大的场合，举例如下： 军事任务：使用a dh o e 无线网络能快速有效地建立战术局域网用于军事行 动中。尤其是在敌战区，部署有基站的网络是相当困难的，极易被敌人摧 毁。 紧急抢险和灾难恢复：在传统通信基础设施因自然灾害、战争而被毁的地 第1 页 国防科技大学研究生院学位论文， 区，为救援工作及时建立起a d h o c 无线网络是非常必要的。 临时集会：会议、展览及其它不提供固定基站的场合，无线a dh o e 网络也 能发挥很好的作用。 a dh o c 网络灵活机动、组网迅速、适应性及鲁棒性强的特点使其成为近年来网 络研究的热点。然而，目前无线自组网仍面临许多挑战。无线a dh o c 网络中的节 点使用的是可耗尽能源，传输带宽有限，节点需同时具备终端和路由器的功能、 网络拓扑结构动态变化等特点，使得自组网路由成为自组网的关键和难点【l 】之一。 1 1 2 蚁群优化算法简介 蚁群算法最初是由意大利学者d o r i g om 等提出的一种群集智能【2 习算法。该算 法从蚂蚁寻找食物的进程受到启发：蚂蚁在寻找食物的过程中会在走过的路上留 下信息素，信息素浓度的大小对其他蚂蚁的行动决策进行影响，由此可知，从蚁 穴到食物源的路径中，路径越短，蚂蚁来回的时间越短，信息素挥发的量越小， 故信息素的浓度高，使更多的蚂蚁更倾向于选择短路径，则来回途中将留下更多 的信息素，如此的正反馈过程将使所有的蚂蚁最终都选择到达食物源的最短路径。 所谓群体智能，是每只蚂蚁的智能很低，完成的任务只是留下信息素，感受信息 素这样的简单工作，但一个蚁群却能因为许多蚂蚁的合作而完成复杂的任务。 蚁群算法最早被应用于t s p 问题【4 ，卯，由于其性能可以与遗传算法【6 】、模拟退 火算法m 、禁忌搜索算法【明等媲美甚至更优，逐渐被用于指派问趔9 】、车间作业调 度问剐1 0 1 、车辆路径问题 t 1 1 、图着色问题【1 2 】、路由算法问题【1 4 1 等等许多领域。蚁 群优化算法用于自组网路由的优势有： 支持多路径； 支持分布式的计算； 局部搜索方式支持节点睡眠； 路由表简单，控制信息少，甚至可由一般数据分组携带。 使用蚁群算法进行无线自组网路由虽然可以得到较好的性能，但蚁群算法也 存在着停滞和收敛较慢的矛盾。停滞是指，在路由过程中，由于某一路径在某一 ( 初始) 阶段质量较好，则此路径上信息素浓度较高，更多的蚂蚁也就是数据分 组更可能选择此路径，同时留下更多信息素，从而最终使所有的数据分组都通过 此路径传递，即此路径选择概率接近甚至到达1 。这样即使路径质量变差，数据分 组也很难选择其它路径传递，另外也不利于新的更好路径的发现。而如果控制信 息素的更新，限制信息素浓度，可在一定程度上避免停滞，却又可能导致收敛变 得比较慢。 第2 页 国防科技大学研究生院学位论文 1 2 本文研究的主要内容 本文从蚁群优化算法的特点及收敛性质入手，对蚁群路由算法的特点进行了 研究，对一般蚁群算法进行了改进，提出使用信息熵控制信息素更新过程的办法， 使蚁群路由算法在保证收敛迅速的前提下，较好的维持多路径。主要进行的工作 如下： ( 1 ) 研究了蚁群优化算法，了解了蚁群算法在不同组合优化问题中的实现，对 其性能、不同的信息素更新方式、收敛性进行了分析； ( 2 ) 详细研究了蚁群路由算法的收敛性，分别针对网络中链路开销对称和不对 称的情况证明了两个定理； ( 3 ) 以定理为指导，提出了使用信息熵改进蚁群算法的思想，通过模拟实现， 将基于信息熵机制的蚁群算法与以往多种不同克服停滞的方法进行了比 较分析，显示出信息熵机制的优越性； ( 4 ) 提出了基于信息熵的蚁群路由算法e a c r a ，在n s - 2 环境中进行了模拟并 与a o d v 、d s d v 、d s r 算法进行了模拟比较。 1 3 余下章节的内容 本文余下章节的内容如下： 第二章介绍了无线自组网的特点、关键技术和实现难点；对路由技术和自组 网路由进行了介绍，简介了典型的白组网路由协议： 第三章介绍了蚁群优化算法及其应用，从蚂蚁的生物学特征入手，讲解了蚁 群模型的建立；简介了蚁群算法应用的发展，简介了蚁群算法和蚁群路由算法的 典型应用： 第四章对蚁群路由算法的收敛性进行阐述，包括在网络链路开销对称和不对 称的环境中，算法的收敛性，从理论上探讨了停滞发生的原因： 第五章提出使用信息熵机制改进蚁群路由算法，描述了信息熵机制的自适应 特点，并通过实验与其他控制信息素的方法进行了比较； 第六章给出了基于信息熵的蚁群算法，并用网络模拟器与前述的传统路由算 法进行了性能的比较。 第3 页 国防科技大学研究生院学位论文 2 1 1 基本概念 第二章无线自组网路由简介 2 1 无线自组网的基本概念和特点 无线自组网( w i r e l e s sa dh o en e t w o r k ) ，也被称为多跳无线网( m u l t i - h o p w h l e s sn e t w o r k ) ，由一组带有无线通信收发装置的移动终端节点组成是一个多 跳的临时性无中心网络，可以在任何时刻、任何地点快速构建起一个移动通信网 络，并且不需要现有网络基础设施的支持，网络中的每个终端可以自由移动，地 位相等。 a dh o c 网络是一种移动通信和计算机网络相结合的网络，是移动计算机通信网 络的一种类型，后者是指用户终端可以在网内随意移动的计算机网络，所以a d h o c 网络是移动通信和计算机网络的交叉。作为一种无中心分布控制网络 ( i n f r a s t r u c t u r e 1 e s s n e t w o r k s ) ，自组网是一种自治的无线多跳网，整个网络没有 固定的基础设旌，可以在不能利用或不便利用现有网络基础设施的情况下，提供 一种通信支撑环境，拓宽了移动网络的应用场合。自组网中也没有固定的路由器， 由于终端的无线覆盖范围有限，两个无法直接进行通信的用户终端可以借助于其 他节点进行分组转发。每个节点都可以说是一个路由器，它们要能完成发现和维 护到其他节点路由的功能。典型例子有交互式的讲演、可以共享信息的商业会议、 战场上的信息中继以及紧急通信需要等。 2 1 2 特点 ( 1 ) 动态变化的网络拓扑结构； ( 2 ) 无中心网络的自组性； ( 3 ) 多跳组网方式； 如图2 1 所示，当自组网中的节点要与其覆盖范围之外的节点进行通信时，需 要通过中间节点的多跳转发，所以自组网是一个多跳的移动计算机网络，多跳是 研究自组网路由协议的前提和基础。与固定网络的多跳路由不同，自组网中的多 跳路由由普通的网络节点完成，而不是由专用的路由设备( 如路由器) 完成。 jj 、- 一一一一：溏、1 r 一一一一 ( 4 ) 有限的无线传输带宽； ( 5 ) 移动终端的自主性和局限性； ( 6 ) 网络采用分布式的控制； ( 7 ) 网络的安全性差； ( 8 ) 网络的可扩展性不强； ( 9 ) 存在单向的无线信道； 。 在采用无线通信的自组网环境中，由于各个无线终端发射功率的不同以及地 形环境的影响可能产生单向信道。如图2 2 所示，两个移动终端a 、b 中，a 由于 发射功率较大，所以能够到达b ，而反之不行，即存在一条a b 的单向信道。单 向信道为常规路由协议带来3 个严重影响【1 4 1 习：认知单向性、路由单向性和汇点 不可达。因此，常规路由协议计算出的路由不能准确反映自组网的拓扑结构，也 无法有效利用单向信道。对于需要逐跳确认的数据分组也由于单向信道的存在而 无法实施。 ( 1 0 ) 网络的生存时间短。 图2 2 单向信道示例 第5 页 国防科技大学研究生院学位论文 2 2 路由技术 路由算法可以根据多个特性来加以区分。算法设计者的特定目标将影响该路 由协议的操作，同时路由算法使用多种m e 缸c ，影响到最佳路径的计算。 2 2 1 路由算法的目标 路由算法通常具有下列设计目标的一个或多个【1 6 】： 优化。优化指路由算法选择最佳路径的能力，根据m e t r i c 的值和权值来计 算。路由协议必须严格定义计算m e t r i c 的算法； 简单、低耗。路由协议必须高效地提供其功能，尽量减少软件和应用的开 销。当路由协议软件运行在物理资源有限的计算机上时，高效尤其重要； 健壮、稳定。路由算法必须健壮，因为路由器位于网络的连接点，当它们 失效时会产生重大的问题。最好的路由算法通常是那些经过了时间考验， 证实在各种网络条件下都很稳定的算法； 快速收敛。路由算法必须能快速收敛，收敛是所有路由器对最佳路径达成 一致的过程。收敛很慢的路由算法可能会产生路由环或网路中断； 灵活性。路由算法还应该是灵活的，即它们应该迅速、准确地适应各种网 络环境。 2 _ 2 2 路由中的m e t r i c 路由表中含有由交换软件用以选择最佳路径的信息。路由算法使用了许多不 同的m e t t l e ( 跳数) 以确定最佳路径。复杂的路由算法可以基于多个m e t r i c 选择路 由，并把它们结合成一个复合的m e t r i c 。常用的m e t r i c 如下： 路径长度：路径长度是最常用的路由m e 伍c ； 可靠性：在路由算法中指网络链接的可依赖性，通常以位误率描述； 延迟：路由延迟指分组从源节点通过网络到达目的节点所花的时间。因为 延迟是多个重要变量的混合体，它是个比较常用且有效的m e t r i c ； 带宽：带宽指链接可用的流通容量； 负载：负载指网络资源，如路由器的繁忙程度。 2 3 自组网路由 2 3 1 自组网路由协议面临的问题 a dh o e 网络中由于节点的任意移动性导致拓扑结构动态、随机且较快速地变 第6 页 国防科技大学研究生院学位论文 化，这样常规路由在拓扑结构变化时，就会花很大的代价重新路由，而且协议状 态始终处于不收敛状态，占用大量的网络资源，致使信息的传输无法实现。 另外，a d h o e 网络不能采用常规路由协议主要由于以下几种因素： a dh o e 网络中无线传输设备功率的差异以及无线信道中的大量干扰导致 单向信道的存在； 无线信道的广播特性使得常规路由的网络选路过程中产生许多冗余链路； 常规路由的周期性广播路由更新分组会消耗大量的网络带宽； 常规路由协议周期性的路由更新分组会消耗大量的节点能源。 a dh o e 网络是一个多跳的移动计算机网络，其特性为a dh o e 网络路由协议设 计提出了新的问题和挑战，主要有以下几点： 网络的自组性； 动态变化的网络拓扑结构； 有限的无线传输带宽； 无线移动终端的局限性； 单向信道的存在； 分布式的控制网络： 有限的网络安全； 生存时间较短。 2 3 2 自组网对路由协议的要求 自组网路由协议的任务是实现路由【7 ，瑚。具体地说，主要有以下几个方面： 监控网络拓扑结构的变化；交换路由信息；确定目的节点的位置；产生、维护以 及取消路由；选择路由并转发数据。由于自组网具有动态拓扑、有限带宽、终端 受限、存在单向信道等特点，对在其上运行的路由协议便提出了许多具体而严格 的要求。相对于有线网络，有些要求是自组网特有的，这些要求主要有： 收敛迅速。自组网的拓扑结构是动态的，随时处于变化之中，这就要求路 由协议必须对拓扑的变化具有快速反应能力，在计算路由时能够迅速收 敛，及时获得有效的路由，避免出现目的节点不可达的情况； 提供无环路由。无论在有线网络还是无线网络，提供无环路由都是对路由 协议的一项基本要求。但在自组网中，由于拓扑结构动态变化会导致大量 已有路由信息在短时间内作废，从而更容易产生路由环路。因此，在自组 网中提供无环路由就显得尤为重要而且更难做到； 避免无穷计算。经典的距离矢量算法在某条链路失效时，有可能出现无穷 计算的情况。在自组网中，链路失效是经常发生的事，这就要求在自组网 第7 页 国防科技大学研究生院学位论文 中运行的路由协议必须能够避免无穷计算，不采用或者改进会出现无穷计 算的算法； 控制管理开销小。自组网中无线传输带宽有限，传送控制管理分组不可避 免地会消耗掉一部分带宽资源。为了更有效地利用宝贵的带宽资源，需要 尽可能地减小控制管理的开销； 对终端性能无过高要求。a dh o e 网络终端大都使用可耗尽资源，c p u 性能、 内存大小、外部存储容量等都低于固定的有线终端，因此，在自组网中不 能对终端性能要求过高。有线网络中用计算的复杂度来换取路由协议性能 的做法，在自组网中不再适用； 支持单向信道。在自组网中，经常有可能出现单向信道。支持单向信道， 也是对路由协议的要求之一； 尽量简单实用。简单有助于提高可靠性，简单有助于减少各种开销。在实 现路由功能的前提下力求简单，应是设计自组网路由协议的原则之一。 但目前提出的路由协议都尚未达到以上所有要求，提出一种适应性强的路由 协议是a dh o c 网络未来研究的一个具有挑战性的课题。 自组网的路由协议有着其特定的应用空间【1 9 1 。假设自组网的网络拓扑结构与 固定网络中一样较为固定，可以认为采用常规路由协议就基本解决了自组网中的 路由问题。假设自组网的拓扑结构变化极为剧烈，可以认为除了采用洪泛 ( f l o o d i n g ) 协议 2 0 , 2 1 , 捌外没有任何协议可以适应这种变化速度。在洪泛协议中， 中间节点只需要判断是否第一次收到接收到的分组，如果是而且自己不是目的节 点则继续转发。所以洪泛协议是一种最简单也是最可靠的路由协议，网络拓扑结 构变化对它毫无影响。但是洪泛协议会带来对网络带宽和设备能源的巨大消耗。 对于自组网的路由协议，其应用空间就是位于这两个极端之间，即网络的拓扑结 构发生变化，但是其变化速度不至于使洪泛协议成为唯一可用协议的应用场景。 2 3 3 自组网路由协议分类 传统的路由协议无法适应a dh o e 网络的需要，因此必须选择或设计适用于a d h o e 网络环境特点的路由协议田】。经过多年的研究，许多路由协议方案相继被提出。 除了m a n e t w g 发布的d s r 阱1 4 i 、a o d v 【2 5 ，1 4 1 、z r p 2 6 ( z o n e r o u t i n g p r o t o c 0 1 ) 等路由协议草案外，研究人员还发表了许多关于自组网路由的学术论文，如 d s d v l 2 7 ( d e s t i n a t i o n - s e q u e n c e ad i s t a n c e v e c t o rr o u t i n g ，目的节点序列距离矢 量路由) 、w r p 2 8 ( w i r e l e s sr o u t i n gp r o t o c o l ，无线路由协议) 、c g s r l 2 9 ( c l u s t c r - h e a d g a t e w a ys w i t c hr o u t i n g ，分群网关交换路由) 、轻型移动路由协议l m r l 3 0 和 r d m a r 3 1 】( r e l a t i v ed i s t a n c em i c r o - d i s c o v e r ya dh o e r o u t i n g ) 等。 第8 页 国防科技大学研究生院学位论文 表3 i 自组网中的路由技术 分类角度路由类型优点缺点典型协议 当节点需要发送数花费开销较大，应尽 d s d v ，w r p ， 据分组时，只要到目可能使路由更新紧s t a r a 3 2 、o s r t 3 3 i ， 从的节点的路由存在，随拓扑结构变化，但f s r 【圳、h s r p s 、 路 主动路由 所需的延时很小动态变化的拓扑结 z h l s l 3 6 由构可能使路由更新 发信息变得过时，路由 现 协议始终处于不收 策 敛状态 略 无需周期性路由信发送数据分组时，如a o d v 、d s r 、 的 息广播，节省了一定果没有到目的节点t o r a 3 7 、a b r 3 s l 、 角的网络资源的路由，需进行路由s s a l 3 9 1 、c b r p l 4 0 l 度 按需路由 发现，数据分组的转 发因路由发现过程 而被延迟 无特殊节点，网络中可扩展性较差，限制a o d v ，d s r ，刃劂， 从 业务流平均分散，路了网络的规模d s d v 、w r p ， 网 平面路由由协议鲁棒性较好， s t a r a 、l a r 【4 1 1 络 无需进行节点移动 逻性管理 辑 网络由多个簇组成，簇首节点的可靠性c g s r 、c e d a r 4 2 、 视 可扩展性较好，适合和稳定性对全网性z r p 、c b r p 图 大规模的自组网环 能影响较大，为支持 的 分群路由境节点在不同分群之 角 间漫游所进行的移 度动管理将产生一定 的协议开销 2 3 4 路由协议的评价 随着多种a dh o c 网络路由协议的提出，如何评价其性能的优劣、在进行协议 仿真时如何设定参数、目前有什么可选的仿真平台及其仿真语言等问题越来越被 重视，这些也逐渐成为研究的重要课题。随着r f c 2 5 0 1 1 4 3 1 ( 自组网路由协议性能 观点和评价) 的正式公布，这方面的工作得了到更有力的推动。 2 3 4 1 协议性能比较 目前提出的多种路由协议各有所长，但没有一种适用于所有的环境。因此， 第9 页 国防科技大学研究生院学位论文 在实际选用路由协议时，需要根据实际环境对其进行性能测定。根据r f c 2 5 0 1 ， 自组网路由协议的性能比较主要是从定性和定量两个方面进行。 ( 1 ) 定性比较 一个好的自组网的路由协议应当满足以下特性要求： 分布式运行方式； 提供无环路由； 按需进行协议操作； 安全性； 提供设备“睡眠”操作特性； 对单向信道的支持。 ( 2 ) 定量比较 通过以下几方面指标可以对自组网的路由协议性能进行定量分析评估： 端到端的数据吞吐量和平均延迟：通过分组传输质量的好坏来衡量路由协 议性能的好坏，可统计其均值、方差及分布等； 分组的平均递交率( 成功分组接收率) ； 路由协议效率：主要考察传输控制分组引起的开销，尤其是在控制信息与 数据信息共享同一信道的情况下，该性能将直接影响到整个系统效率的高 低： 路由获得时间：即统计节点有数据需要发送到数据成功发送的时间，主要 用于按需路由方式的a dh o e 网络路由协议的性能评价； 路由的准确性：一般用所提供的路由和最短路由之间的跳数差来衡量。 2 342 仿真模型的参数选择 现在提出的各种自组网路由协议在相应的文献中都提供了相应指标的模拟结 果。但是由于各自都是在不同的模拟环境下得到的，所以相互之间的可比性较差。 对于模拟仿真的另一个重要问题是模拟环境参数的设定。模拟环境参数主要包括： 网络规模，包括节点数、节点移动区域大小等。网络规模基本上决定了网 络的连接性。一个区域中的节点数越少，每节点的邻节点就越少，这样碰 撞的概率就越小； 网络的连接度； 网络拓扑结构的变化程度； 无线信道的传输带宽； 单向信道的比例； 信息流量的通信模式； 终端节点的运动模式。它是a dh o e 网络最重要的特性之一。在仿真时需要 第1 0 页 国防科技大学研究生院学位论文 设计一定的节点运动模式来反映动态的拓扑结构、链路的连接与断开； 网络负载包括分组大小及发送分组的速度。 需要强调的是，在构造仿真模型时，不同的节点运动模式将很大程度上影响 仿真结果。在设计节点运动模式时，可以考虑系统地隔离影响不同协议性能的因 素，也可以考虑设计最能贴切表示实际情况的模型，并注意用户移动方向、用户 密度及移动速度等特性。以下为现有的几种节点运动模式【1 6 1 ： r a n d o m w a y p o i n tm o d e l b r o w n i a nm o