（计算机科学与技术专业论文）移动无线传感器网络中机会主义路由研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 作为2 1 世纪重要的技术之一，无线传感器网络受到了广大研究者的关注，并 得到了广泛应用。其中，野生动物监控成为热点应用之一。野生动物监控网属于 移动无线传感器网络，其路由面临着众多挑战。 相比于传统无线路由算法，机会主义路由充分利用了无线信道质量时变性以 及广播特性，行之有效的提高了无线网络性能。作为一种新型的后择路由，机会 主义路由目前受到了广泛的关注，并成为无线领域研究的热点之一。但机会主义 路由仍面临众多急需解决的问题，如转发候选集选取问题、空间重用问题等。针 对这些问题，本文重点研究和设计符合移动无线传感器网络特性的机会主义路由。 针对转发候选集选取问题，本文提出了移动无线传感器网络中基于r s s i 的机 会主义路由o r r s s i 。目前存在的机会主义路由算法或需要大量能耗以交互路由 报文，或需要昂贵设备的支持，而且这些算法均不能反映节点移动性，因此不适 合于移动无线传感器网络。o r r s s i 思想来源于蜜蜂寻蜜行为，通过功率较大啦 s i n k 节点周期广播b e a c o n 报文，其他传感节点通过获取r s s i 信息建立并更新机 会概率值，以机会概率值为准则选择转发候选节点集，对报文实施机会主义路由。 o r r s s i 不需要大量的路由交互报文，同时又能一定程度上体现无线信道质 量；不需要昂贵设备的支持，符合传感器网络低成本的特性；引入移动方向矢量 m y ，反映节点移动性对机会主义路由的影响。文中在n s 2 下实现并模拟了 o r - r s s i ，模拟实验表明：与传统的t i n y a o d v 相比，o r r s s i 具有报文成功传 输率高、网络有效吞吐量大以及能耗低等优点，适合于移动无线传感器网络。 针对空间重用、重复冗余报文问题，目前学者们提出了基于网络编码的机会 主义路由o i 渊c 。但是，这些路由算法均采用完全网络编码方式实现，使得目标 节点必须等到k 个线性无关的编码报文后才能同时解码得到k 个原始报文，增加 了报文平均延迟，而且报文到达不均衡，不利于目标节点的处理。针对于此，本 文提出基于部分网络编码的机会主义路由o r - p n c ，以期改进o r - n c 的不足。 o r p n c 中，转发候选节点对接收到的报文进行任意长度的部分编码转发，目 标节点处能均衡的解码原始报文，因此降低了报文平均延迟。本文在e c l i p s e3 0 下设计并实现了o r p n c 。测试实验表明：对于不同的k 值，o r - p n c 的报文延 迟一般比o r - n c 小，当k = 6 时，延迟降低可达2 6 4 8 9 。 总之，我们为移动无线传感器网络提出了两种机会主义路由o r r s s i 和 o r p n c ，并且做了大量实验。研究结果具有较好的理论和实践价值。 主题词：移动无线传感器网络，机会主义路由，r s s i ，网络编码 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t a so n eo ft h ei m p o r t a n tt e c h n o l o g i e si nt h e21 吼c e n t u r y w i r e l e s ss e n s o rn e t w o r k s ( w s n s ) h a v ea t t r a c t e dag r e a to fc o n c e r n sa n da r ew i d e l yu s e d a m o n gt h e m ，t h e w i l d l i f e m o n i t o r i n ga p p l i c a t i o n s h o u l db et h eh o t t e s to n e w i l d l i f em o n i t o r i n g a p p l i c a t i o nn e t w o r kb e l o n g st ot h em o b i l ew i r e l e s ss e n s o rn e t w o r k ( m w s n ) ，a n di t s r o u t i n gt e c h n o l o g yf a c e sw i t hal o to fc h a l l e n g e s a sc o m p a r e dw i t ht r a d i t i o n a lw i r e l e s sr o u t i n ga l g o r i t h m s ，o p p o r t u n i s t i cr o u t i n g f o r ) t a k e sf u l la d v a n t a g eo ft h eb r o a d c a s t i n gn a t u r eo fw i r e l e s sc h a n n e l ，弱w e l la st h e t i m e v a r y i n gc h a r a c t e r i s t i co f w i r e l e s sc h a n n e lq u a l i t y t h u s o rh a si m p r o v e dn e t w o r k p e r f o r m a n c eg r e a t l y a san e wp o s t - d e t e r m i n e dr o u t i n g ，o p p o r t u n i s t i cr o u t i n gh a s d r a w naw i d er a n g eo fc o n c e r n sa n db e c o m eo n eo ft h eh o t t e s tr e s e a r c h e si nm a n e t h o w e v e r , o p p o r t u n i s t i cr o u t i n gi s s t i l l f a c i n gm a n yu r g e n tp r o b l e m s ，s u c ha s f o r w a r d i n g c a n d i d a t es e l e c t i o n ，s p a t i a lr e u s e ，a n ds oo n t os o l v et h e s ep r o b l e m s ，t h i s t h e s i sm a i n l yf o c u s e so nt h ed e s i g n i n go fo p p o r t u n i s t i cr o u t i n gf o rm o b i l ew i r e l e s s s e n s o rn e t w o r k s t os o l v et h ef o r w a r d i n g c a n d i d a t es e l e c t i o np r o b l e m ，t h et h e s i sh a sp r o p o s e da l l o p p o r t u n i s t i cr o u t i n gb a s e do nr s s i ( r e c e i v e ds i g n a ls t r e n g t hi n d i c a t o r ) ，n a m e d o r - r s s i ，f o rm o b i l ew i r e l e s ss e n s o rn e t w o r k s i nt h ep r o p o s e dp r o t o c o l ，o p p o r t u n i s t i c p r o b a b i l i 够( o p ) b a s e do nt h er s s io ft h es i n k sb e a c o np a c k e t sa n dm o b i l i t y 。v e c t o r ( m v ) i se s t a b l i s h e da n dt h eb e s tn o d ew i t ht h eh i g h e s to pa v a i l a b l ea tt h a ti n s t a n ti s u s e dt os t o r ea n dr e l a yp a c k e t sa te a c hh o pa f t e rp a c k e t sa r eb r o a d c a s t e d t h ei d e ao fo r r s s ic o m e sf r o mb e h a v i o ro fh o n e yb e e s d i f f e r e n tf r o me x i s t i n g o p p o r t u n i s t i cr o u t i n ga l g o r i t h m s o r - r s s id o e sn o tn e e dt h es u p p o r to fe x p e n s i v e d e v i c e so rc o n s u m eag r e a to fe n e r g yf o ri n t e r c h a n g i n gr o u t i n gp a c k e t s w 1 1 a ti sm o r e ， o r r s s ii n t r o d u c e st h em o b i l i t yv e c t o r 聊vt or e f l e c tn o d e s m o b i l i t y w eh a v ei m p l e m e n t e do r - r s s ii nn s 2a n dd o n ean u m b e ro fs i m u l a t i o n e x p e r i m e n t s s i m u l a t i o nr e s u l t ss h o wt h a to r - r s s i i sm o r ef e a s i b l ef o rs p a r s em w s i n a n dp e r f o r m sb e t t e ro ns u c c e s s f u ld e l i v e r yr a t i o ，g o o d p u ta n de n e r g yo v e r h e a da s c o m p a r e dw i t ht r a d i t i o n a lt i n y a o d v t os o l v et h ep r o b l e mo fs p a t i a lr e u s ea n dr e d u n d a n tc o p yp a c k e t s ，r e s e a r c h e r sh a v e p r o p o s e do p p o r t u n i s t i cr o u t i n gb a s e dn e t w o r kc o d i n g ( n c ) ，n a m e d0 r - n c h o w e v e r ， t h e s ea l g o r i t h m sa l la d o p tt h ew a yo ff u l ln e t w o r kc o d i n g ，w h i c hm a k e st h e d e s t i n a t i o nn o d ew a i tt od e c o d et h eo r i g i n a lp a c k e t su n t i lkl i n e a ri n d e p e n d e n tc o d e d p a c k e t sh a v ea r r i v e d t h e r e f o r e ，t h i ss i t u a t i o nr e s u l t si na i li n c r e a s eo ft h ep a c k e t a v e r a g ed e l a ya n dm a k e st h ed e s t i n a t i o nn o d eu n c o m f o r t a b l et od e a l 、i r i t l lt h ep a c k e t s s oi nt h et h e s i s ，w eh a v ep r o p o s e da no p p o r t u n i s t i cr o u t i n gb a s e do np a r t i a l n e t w o r kc o d i n g ，n a m e do r - p n c ，t r y i n gt ol o w e rt h ep a c k e ta v e r a g ed e l a y i n 第i i 页 国防科学技术大学研究生院硕士学位论文 o r - p n c f o r w a r d i n gc a n d i d a t en o d e sr a n d o m l yc h o o s er e c e i v e dp a c k e t st oe n c o d en e w p a c k e t 、析t hr a n d o ml e n g t ha n dt h ed e s t i n a t i o nn o d ec a l ld e c o d eo r i g i n a lp a c k e t s r a n d o m l y w eh a v ei m p l e m e n t e do r p n ci ne c l i p s e 3 0a n dd o n ep r a c t i c a l e x p e r i m e n t sw i t ht w ow i r e l e s sn o d e s ，w h i c ha r ee q u i p e dw i t h8 0 2 1 1gw i r e l e s sn e t w o r k c a r d s e x p e r i m e n t sr e s u l t ss h o wt h a t ：w i t l ld i f f e r e n tv a l u e so fp a r a m e t e rk t h ep a c k e t a v e r a g ed e l a yo fo r p n ci sc o m m o n l ys m a l l e rt h a nt h a to fo r n c w h e nki s6 ，t h e a v e r a g ed e l a yc a nd e c r e a s eb y2 6 4 8 9 h o w e v e r ，w i t hi n c r e a s i n go fv a l u eo fk ，t h e i m p r o v e m e n to f0 r - p n cw i l ls l o wd o w n o re v e nw o r s et h a no r n c i ns u m m a r y ，w eh a v ep r o p o s e dt w oo p p o r t u n i s t i cr o u t i n g ，o r - r s s ia n do r - n c ， f o rm o b i l ew i r e l e s ss e n s o rn e t w o r k s m o r e o v e r ，s o m ei n d e p te x p e r i m e n t s i n c l u d i n g s i m u l a t i o ne x p e r i m e n t sa n dp r a c t i c a le x p e r i m e n t s ，h a v eb e e nd o n ef o ro p p o r t u n i s t i c r o u t i n g e x p e r i m e n tr e s u l t sa r ev a l u a b l e k e yw o r d s ：m w s n ，o p p o r t u n i s t i cr o u t i n g ，r s s i ，n e t w o r kc o d i n g 第i i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表4 1 参数设置。4 4 表5 1o r p n c 部分实验测试数据( d n ) 5 9 第1 v 页 国防科学技术大学研究生院硕士学位论文 图目录 图1 1 无线传感器网络结构副1 1 1 图1 2 动物监测简单结构图【9 1 3 图1 3 无线网络传统最短路径路由一5 图1 4 传统无线路由下一跳v s 机会主义路由下一跳集7 图2 1 机会主义路由转发节点集与候选节点集1 0 图2 2 无线信道质量时变性1 1 图2 3 节点广播信号强度分布图1 2 图2 4 无线传输概率表示二13 图2 5 节点接收集时间关系图1 3 图2 6 先决路由v s 后择路由1 4 图2 7 机会主义路由分类图15 图2 8 转发候选集节点依次确认1 6 图2 9 无线拓扑图17 图2 1 0 各节点到节点e 的e t x 值1 7 图2 1le x o r 2 采用批次发送18 图2 12e x o r 2 传输调度图。18 图2 1 3 基于e t x 选择转发候选集的局限性1 9 图2 1 4 基于地理信息的机会主义路由2 0 图2 1 5 传统单路径v s 机会主义路由平行多路径2 l 图3 1 移动传感器网络利用移动节点储存转发报文【4 1 1 2 3 图3 2 节点移动性对机会概率值o p 的影响。2 4 图3 3r s s i 与距离之间的关系趋势图t 蛔2 5 图3 4r s s i 与无线信道质量关系实验场景图2 6 图3 5r s s i 与无线信道质量柱状图2 6 图3 6 蜜蜂采蜜行为2 8 图3 7 移动方向矢量示意图。3 0 图3 8o r r s s i 示例图一3l 图3 9o r r s s i 报文格式31 图3 。l oo r - r s s i 算法伪码3 3 图3 1 1 转发节点工作流程图3 4 图3 1 2 路由空洞3 7 图3 1 3 节点x 移向节点d 3 7 第v 页 国防科学技术大学研究生院硕士学位论文 图3 1 4 节点x 远离节点d ，而邻居节点可能移向节点d 3 8 图4 1 使用n s 2 进行网络模拟的过程4 1 图4 2n s 2 部分类结构图1 47 。4 1 图4 3n s 2 中报文在节点间流动示意【47 。4 2 图4 4 节点状态图4 3 图4 5 模拟场景一4 4 图4 6 简单场景下报文传输成功率4 5 图4 7 简单场景下报文平均延迟4 5 图4 8 复杂场景下不同节点密度的报文传输成功率4 6 图4 9 复杂场景下不同节点密度报文平均延迟4 7 图4 1 0 复杂场景下不同节点密度有效吞吐量4 8 图4 1 1 复杂场景下不同密度能耗比较4 8 图5 1 不使用网络编码的传输【4 引5 0 图5 2 使用网络编码减少传输次数【4 8 1 5l 图5 3 网络编码在机会主义路由的应用f 5 2 1 5 2 图5 5 基于完全网络编码的机会主义路由5 4 图5 6 基于部分网络编码的机会主义路由5 5 图5 7o r p n c 报文格式一5 6 图5 8o r p n c 算法伪码5 7 图5 9o r - p n c 程序类图5 8 图5 1 0o r p n c 接收端程序执行效果图5 8 图5 1 1o r p n c 实验拓扑图5 9 图5 1 2 不同k 值下，报文平均延迟比较6 0 图5 1 3 不同k 值下，解出k 个报文需要的报文数6 0 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：整邈五绫笾盛墨圆终生扭金圭墓整由盈盔 学位论文作者签名：整亟日期：议弦名年少月 f 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：整边垂绫笾盛墨圆缝生扭金圭幺整由盈究 学位论文作者签名：霾立亟日期：渤g 年，二月土，日 作者指导教师签名：是趣至二日期：b 毋年口月列日 国防科学技术大学研究生院硕士学位论文 第一章绪论 无线传感器网络( w i r e l e s ss e n s o r n e t w o r k s ，w s n ) 是近年来兴起的一种重要的 无线网络技术，被认为是2 1 世纪最重要的技术之一，它将对人类未来的生活方式 产生巨大影响 1 1 闭，并被美国麻省理工学院技术评论杂志评为对人类未来生活 产生深远影响的十大新兴技术之首【3 l 。路由技术是影响无线传感器网络性能的重要 困素，然而在无线应用领域路由技术又面临诸多挑战，困此无线传感器网络路由 技术一直为研究的热点难点。 1 1 研究背景 随着微电子技术、计算机技术、无线通信和无线网络等技术的飞速发展，无 线传感器网络技术得到快速发展和广泛应用，其中包括军事应用、环境监测、医 疗健康、智能交通和野生动物监测等等。但是，由于无线传感器网络具有能源有 限、通信计算能力有限、动态拓扑等特点，使其路由技术面临更多困难和挑战。 1 11 无线传盛器网络 无线传感器网络( w i r e l e s ss e n s o r n e t w o r k ，w s n ) 由部署在监测区域内的大 量廉价的微型传感器节点组成，通过无线通信方式形成的一个多跳、自组织的网 络系统【1 其应用结构一般如图1 1 所示。近年来，随着微电子技术、计算机技 术、无线通信和无线网络等技术的飞速发展，无线传感器网络技术得至4 快速发展 和具体应用。 ：。”一一。”：一： 。 、一一 1 一j ，。1 _ 。 i1 m 、 ，i 。 。当 图i a 无线传感器呵络结构图1 1 】 通过传感器网络节点之间的协作来感知、采集和处理网络覆盖区域中的各种 信息，乃至人类无法到达地域的各种信息，在实际的应用领域中越来越突出其重 要作用【”。具有自组织和分布智能化的传感器技术广泛应用于军事侦察、环境监测、 第1 页 国防科学技术大学研究生院硕士学位论文 医疗健康、野生动物监测等各种领域，已经引起人们的广泛关注，并得到了大量 的研究。 无线传感器网络具有节点成本低廉，无需能源、通信等基础设施的支持，随 时随地自组成网等优点，这些便宜微小的智能传感器能被快速的布置到任何需要 的地方，因此应用范围极其广泛。其主要应用领域包括：军事侦察、环境监测、 医疗、建筑物监测、野生动物监测等等。当然，在空间探索和灾难拯救等特殊的 领域，无线传感器网络也有其得天独厚的技术优势。 军事应用【6 】【7 】 传感器网络具有可快速部署、可自组织、隐蔽性强和容错性的特点，因此非 常适合在军事上应用。因为无线传感器网络是由密集型、低成本、随机分布的节 点组成的，自组织性和容错能力使其不会因为某些节点在恶意攻击中的损坏而导 致整个系统的崩溃，这是传统的传感器技术所无法比拟的，也正是由于这一点， 使无线传感器网络非常适合应用于恶劣的战场环境中，包括监控我军兵力、装备 和物资，监视冲突区，侦察敌方地形和布防，定位攻击目标，评估损失，侦察和 探测核、生物和化学攻击等。 环境监测吲 随着人们对于环境的日益关注，需要对生存的环境进行监测，如对温度、湿 度、光线及水源进行监测等。通过传统方式采集原始数据是一件困难的工作，而 利用无线传感器网络对野外环境中随机性的数据进行获取，却十分方便。当然， 无线传感器网络还可用于研究环境变化对农作物的影响，监测海洋、大气和土壤 的成分等。a l e r t t i j 系统中就是利用数种传感器来监测降雨量、河水水位和土壤 水分，并依此预测爆发山洪的可能性。类似地，无线传感器网络对预防森林火灾、 煤矿预警等也起到一定的作用。 医疗健康【5 j 如果将传感器节点部署在心脏或其它病变部位，可以及时有效地获取病情， 医生就可以随时了解被监护病人的病情，进行及时处理。还可以利用传感器网络 长时间地收集人的生理数据，这些数据在研制新药品的过程中是非常有用的，而 安装在被监测对象身上的微型传感器也不会给人的正常生活带来太多的不便。总 之，无线传感器网络为未来的远程医疗提供了更加方便、快捷的技术实现手段。 建筑及城市管理 无线传感器可以灵活方便地布置于建筑物内，获取室内环境参数，从而为居 室环境控制和危险报警提供依据： ( 1 ) 智能家居：通过布置于房间内的温度、湿度、光照、空气成分等无线传感 器，感知居室不同部分的微观状况，从而对空调、门窗以及其他家电进行自动控 第2 页 国防科学拄术大学研究生院硕士学位论文 制，提供给人们智能、舒适的居住环境”j 。 ( 2 ) 建筑安全：通过布置于建筑物内的图像、声音、气体检测、温度、压力、 辐射等传感器，发现异常事件及时报警，自动启动应急措施。 ( 3 ) 智能交通：通过布置于道路上的速度、识别传感器，监测交通流量等信息， 为出行者提供信息服务，发现违章能及时报警和记录”j a 野生动物监测 为了保护野生动物以及更好的研究它们的习性，生物学家们把无线传感器网 络应用于野生动物监测i 州，其收集的信息包括：野生动物的位置、迁徙、群居活 动、生活习性等等，应用实例有z e b r a n e t l 9 1 和s w i m j 。 本文研究的应用背景为野生动物群监测，群首领一般装有大功率、能量较充 裕的s i n k 节点，而其他群成员装有小功率、能量有限的无线传感器节点，传感节 点经过一跳或者多跳方式与s i n k 节点通讯，而s i n k 节点通过卫星或者丛林中设立 的基站把信息传回信息处理中心，其网络结构大致如图l2 所示。 抻 恤 哦 诫 ”谗。鼹 凹1 2 动物监测简单结构图 1 12 无线传盛器网络路由技术面临的挑战 计算机网络中，路由即是寻找一个节点到目标节点最佳路径的问题【l “。路径 选择的好坏直接影响到网络数据传输的延迟、吞吐量、报文成功率等性能，因此 路由技术是影响网络性能的重要因素之一在无线网络领域也不例外。 与传统的无线通信网络不同，无线传感器网络具有节点能量有限，通信、计 算能力有限，所处环境复杂恶劣，节点移动性造成网络拓扑动态变化等特点，从 而也使得无线传感器网络路由技术面临众多挑战 4 1 ： 1 、电源能量有限 传感器节点通常体积微小，只能携带能量十分有限的电池。由于传感器节点 第3 页 国防科学技术大学研究生院硕士学位论文 个数多，成本低廉，分布区域广，而且部署环境复杂，传感器节点能源难以得到 补充或者更换。因此如何在路由过程中节省能耗，最大化网络的生命周期是无线 传感器网络路由技术研究所面临的一个挑战。 2 、通信能力有限 无线传感器网络的通信带宽窄而且经常变化，通信覆盖范围只有几十米到几 百米；由于受到高山、建筑物、茂密植物等地势地貌以及风雨雷电等自然环境的 影响，传感器节点可能会长时间脱离网络、离线工作。因此如何在通信能力有限 的情况下高质量地完成感知信息的路由传输也是我们面临的挑战之一。 3 、计算能力有限 无线传感器网络中的传感器节点都采用嵌入式处理器和存储器，嵌入式系统 的计算能力和存储空间十分有限，因此传感器节点的计算能力、存储能力有限， 不能缓存大量的路由报文，更不能快速的对大规模路由表进行查询。因此，如何 设计小缓存、快速、稳定的路由算法，是我们面临的第三个挑战。 4 、节点数目多，网络规模大 、 为了获取精确信息，在监测区域通常部署大量传感器节点，传感器数目可达 成千上万个，因此传感器网络规模巨大。网络规模大，也就意味着经过多跳完成 数据传输的路径跳步数增加，影响路由因素也随之增加。因此，如何设计多跳步 数、稳定的路由算法，是我们面临的第四个挑战。 5 、网络拓扑动态变化 无线传感器网络具有很强的动态性，网络中的传感器节点、感知对象和数据 收集者这三要素都可能具有移动性，并且经常有新节点加入或旧节点失效。所以， 任何一个元素位置发生变化，网络的拓扑结构也就随之改变，而网络拓扑的动态 变化往往造成路由的频繁失效或者修复。因此，如何设计稳定可靠的路由算法成 为我们面临的第五个挑战。 1 2 无线网络中路由技术 最早的无线网络只是简单地使用有线网络中的最短路径路由，但效果不理想。 研究者们发展了一系列的a d h o e 网络路由算法，如经典的d s r 、a o d v 等，但 这些算法没有充分利用无线信道的特点，性能也十分有限。因此，近几年发展起 来的充分利用无线信道特点的机会主义路由成为研究的热点。 1 2 1 传统最短路径路由 两种主要的最短路径路由算法包括：d v 1 3 】【1 4 】和l s 13 1 。d v ( d i s t a n c ev e c t o r ， 距离矢量) 算法将当前路由器的路由信息传送给相邻路由器，相邻路由器将这些信 第4 页 国防科学技术大学研究生院硕士学位论文 息加入自身的路由表。而l s ( l i n ks t a t e ，链路状态) 算法将链路状态信息传给域内 所有的路由器，接收路由器利用这些信息构建网络拓扑图，并利用图论中的最短 路径优先算法决定路由。 相比之下，距离向量算法比较简单，而链路状态算法较为复杂，占用的c p u 和内存也要多一些。但是由于链路状态算法采用的是自身的计算结果，所以比较 不容易产生路由循环。r i p 是d v 类算法的典型代表，而o s p f 是l s 的代表协议。 传统的最短路径路由广泛适用于有线静态网络，要求路由器维护整个网络的 矢量或者状态表，并实时更新路由表状态，因此网络中产生大量的路由报文，并 要求实时掌握整个网络的拓扑状态信息，这不适用于能力有限、拓扑频繁变化的 无线网络，特别是无线传感器网络。 1 2 2a d h o c 网络路由 a d h o c 网络( 即无线自组网) 中传统的路由算法都是根据不同的衡量准则在源 节点到目标节点间可达的所有路径中找到一条最短路径( s h o r t e s tp a t h ) 或者多条次 优路径【i 】。当路径确定后，数据包沿着固定的路径以多跳的方式发送到目标节点。 例如图1 3 ，假设节点a 到节点d 的最优路径为：a b c d ，则数据包沿着该固定 路径逐跳传输，直到该路径失效或者传输完成。因此，传统无线网络路由中每一 跳数据包发送出去前，下一跳都是确定的，所以传统路由也称为先决路由 p d r ( p r e d e t e r m i n e dr o u t i n g ) 。 图1 3 无线网络传统最短路径路由 传统无线网络路由可以分为表驱动路由p r ( p r o a c t i v er o u t i n g ) 和按需路由 r r ( r e a c t i v er o u t i n g ) 。表驱动路由借鉴有线网络中路由算法得来，要求每个节点 维护一个或多个局部路由信息表，试图维护网络中某些可用的传输路径，而不管 当时的数据传输是否需要这些路径，当网络拓扑变化时，更新信息传遍整个网络， 以维护一致的网络视图。但是当网络拓扑频繁的变化时，为了维护那些大量无用 路由而产生的路由维护信息将大大降低带宽利用率。因此，按需路由应运而生。 该路由算法只有在源节点需要向某个目标节点传送数据时，才发起建立以及维护 一条或若干条有用路由。因此，按需路由适用于拓扑动态变化的无线自组织网络， 第5 页 国防科学技术大学研究生院硕士学位论文 并得到了广泛应用，其中最具有代表性的路由算法为a o d v u s 1 6 i ( a d h o e o n - d e m a n dd i s t a n c ev e c t o rr o u t i n g ) 。 a o d v 路由算法是基于距离矢量的按需单路径路由协议，结合了 d s d v ( d e s t i n a t i o ns e q u e n c e dd i s t a n c e - v e c t o rr o u t i n g ) 和d s r i iq ( d y n a m i cs o u r c e r o u t i n g ) 的优点，引入d s d v 中的目的序列号以避免环路。该协议主要分为路由发 现和路由维护两部分。路由发现阶段，源节点通过发送r r e q 搜寻可用路由，目 标节点接收到r r e q 后回应r r e p 建立路由；路由维护主要通过路由出错分组r r e r 来报告。a o d v 协议通过周期性广播h e l l o 分组来监视链路连通性。当节点 监测到链路出错时，则向其邻居节点发送r r e r ，收到r r e r 的节点，将路由表 的相应路由设置为无效，并继续传播r r e r 。当源节点收到此r r e r 后，重新发 起一次路由发现过程，寻找新的可用路由。 综上所述，传统无线路由算法是先决路由：报文发出之前，下一跳是确定的。 但由于节点的移动或者环境的变化，无线自组网的拓扑以及链路质量变化都比较 频繁，路由将很不稳定，所以路由发现时得到的最优路由未必就是数据传送时的 最佳路径，而且传统无线路由也没有很好的利用无线网络广播特性( 可能多个节点 接收到数据包，本文第二章将详细介绍该特性) 。 针对传统无线先决路由的缺点，目前研究者提出了一种新型路由机会主 义路由o r 1 8 】【1 9 l ( o p p o r t u n i s t i cr o u t i n g ) 。该类路由为后择路由，报文发送出去后再 根据当时无线信道质量等因素选择下一跳。相比传统无线路由，机会主义路由在 很大程度上提高了无线自组网的性能。因此也很快成为当前国内外无线网络领域 研究热点之一。 1 2 3 机会主义路由o r 近几年针对无线网络提出的机会主义路由o r 是一种后择路由，不以源一目标 节点间直接可达路径为基础，充分利用无线信道的广播特性，尽可能地克服动态 拓扑、链路信道变化频繁等影响，从而有效提高无线网络性能【l 9 】【2 0 】【2 1 1 。 机会主义路由利用下一跳集来完成转发，而不再是传统无线路由中的下一跳。 如图1 4 ( a ) 所示，传统无线路由的下一跳是确定的( 图中下一跳为x 节点) ，报文发 送出去后，一旦这个确定的节点不能成功接收到报文，则源节点要重新发送该报 文，该过程循环直到下一跳节点成功接收到报文。但无线网络中报文传输采用的 是广播方式，虽然x 节点不能成功接收报文，其他中间节点成功接收的概率却很 大。如果能利用已经成功接收报文的其他任意中间节点进行转发，其性能势必将 比源节点重传要高，如图1 4 ( b ) 所示。 第6 页 国防科学技术大学研究生院硕士学位论文 增 图1 4 传统无线路由下一跳v s 机会主义路由下一跳舞 另外，传统无线路由不适合于移动无线网络。传统无线路由协议都存在共性 假设：数据源节点与汇聚节点问总是存在一条可用路径。但实际的移动环境下， 节点任意动态移动，因而链路也随时间变化而改变。正由于拓扑动态变化、链路 变化频繁以及节点有限的传输通信距离，上述假设是不成立的。换句话说节点 间不一定总是存在一条可达路径，即使有时存在，但持续时间较短也不足以完成 数据的传输。 然而在机会主义路由中，报文发送出去后再根据当时的信道质量和接收情况 选择下一跳进行转发，没有确定的路径，不以路径为基础伸缩性优异因此适 用于移动环境下的无线网络应用例如新型网络机会网络i 【i 。机会网络是 m a n e t 和w s n 的一种重要的发展形式。在机会网络中，并不假设两个希望通信 的节点间存在完整的路径，机会路由通常在网络中暂存消息以等待到目的节点的 路径出现。 m o m s 等人在0 5 年s i g c o m m j 二e x o r i o q 一文中首次提出机会主义路由的概念， 此后机会主义路由在无线网络中展现的良好性能吸引了广大研究者的关注，成为 研究的热点之一。虽然研究者提出了众多方法，但是机会主义路由的研究仍处于 起步阶段，仍面临许多挑战和急于解决的难题( 将在第二章详细阐述) ，其中主要包 括： 转发候选集的选择问题： 空间重用、重复冗余报文问题： 多路径干扰、能耗等问题。 目前，机会主义路由的大多研究集中于静态a d h o e 网络环境。本文尝试把机 会主义路由应用于移动无线传感器网络，着重研究机会主义路由在移动环境下转 发候选集选取、重复冗余报文消除等问题。 1 3 课题主要研究内容 移动无线传感器网络路由面临着众多挑战。节点移动性造成网络拓扑动态变 第7 页 国防科学技术大学研究生院硕十学位论文 化，往往使源目标节点i 训不存在直接可达路径，使得目自订基于静念传器网络提出 的最短路径路由协议无法适用。机会主义路由充分利用了无线信道质量时变性以 及广播特性，行之有效的提高了无线网络性能。作为一种新型的后择路由，机会 主义路由目前受到了广泛的关注，并成为无线领域研究的热点之一。但机会主义 路由仍面临众多急需解决的问题，如转发候选集选取问题、空间重用问题等。针 对这些问题，本文重点研究和设计符合移动无线传感器网络特性的机会主义路由。 针对转发候选集问题，本文提出移动无线传感器网络中基于移动向量而、信 号强度指示值r s s i 的机会主义路由o r r s s i ；针对空间重用、重复冗余报文问题， 本文提出了基于部分网络编码的机会主义路由o r p n c 。总结起来，本文的主要工 作和贡献包括： 1 信号强度指示值r s s i 信息被普遍应用于传感器网络的定位技术，本文首 次将其引入传感器网络路由设计；相对于地理路由，r s s i 信息不需要其 它昂贵设备的支持，并一定程度上体现了信道的质量，降低网络成本的同 时减小报文延时。 2 其它机会主义路由，如基于e t x 、e a x 等，虽能体现路由信道质量，但 需要大量的路由交互报文，消耗大量的能量，不适用于能量有限的传感器 网络；本文提出的o r - r s s i 路由协议保证一定信道质量的同时，交互报 文少，报文成功率较高，能耗低。 3 其它机会主义路由建立的机会概率值以标量为主，不能很好的体现移动传 感器网络中节点的移动特性；而节点移动性对转发候选节点的选取至关重 要，本文提出的o r r s s i 路由引入移