（通信与信息系统专业论文）定向扩散法的实现和改进.pdf

摘要 无线传感器网络是新近发展起来的一种面向特定应用的网络系统，具有很广+ 泛的应用 前景。但是它存在网络拓扑不固定，面向特定应用等不足，并受限于各种资源条件( 包括： 能量有限，计算能力不强，通信距离小等) 。 无线传感器网络是一种以数据为中心的网络，而网络数据传输离不开路由协议。考虑 到节点无全局统一标识，节点能量有限等不利因素，传统a dh o e 网络的路由方式不适用 于传感器网络。通过对传感器网络几个常用的协议和算法分析，发现它们都存在着不足， 需要一种专门为无线传感器网络设计的路由策略。 定向扩散法是专门为无线传感器网络设计所提出的路由模式。由于网络中传输的数据 需要被命名，数据可以被节点进行网络内处理，要求选用通路来传输数据包，所以定向 扩散法选用了“属性一值一操作符”模式的数据命名机制和对这类数据进行比较匹配的规 则，并且引入网络梯度来决定传输路径的选通。对定向扩散法的研究主要工作有两个方 面：第一方面，通过仿真实现定向扩散法，证明定向扩散法在减少能耗和选通数据传输 路径的良好效果。第二方面，在第一步的基础上，对监测区节点采集发送数据的方式做 出改动，进一步提高能量节省程度。本文把定向扩散法基本思想在n s 2 中仿真实现并设计 了系列试验，试验结果表明定向扩散法取得更优能量节省效果，并且没有较大时间延迟。 研究结果指明定向扩散法适合无线传感器网络路由需要，并可做进一步改进。 关键字： 传感器网络，路由协议，定向扩散法，能量节省 t h e i m p l e m e n t a n d i m p r o v e m e n t o f d i r e c t e dd i f f u s i o n a b s t r a c t w i r e l e s ss e n s o rn e t w o r ki san e wk i n do fn e t w o r k s y s t e m t h a ti sp r o p o s e df o rs o m e s p e e i f i c a p p l i c a t i o n s i ti sv e r yu s e f u li ns o m er e g i o n b u tw i r e l e s ss e n s o rn e t w o r ki sl i m i t e db yh i s r e s o u r c es u c ha s e n e r g y , c o m p u t a t i o na b i l i t y a n dc o m m u n i c a t i o nd i s t a n c e m o r e o v e r , i t s t o p o l o g y i sd y n a m i ca n di ti su s e df o rs o m e s p e c i f i ca p p l i c a t i o n w t r e l e s ss e n s o rn e t w o r ki sad a t a c e n t r i cs y s t e m ，d a t ac a n tb et r a n s m i t t e dw i t h o u tr o u t i n g p r o t o c o l si nn e t w o r k t h ed e s i g no fr o u t i n gp r o t o c o lf o rw i r e l e s ss e n s o rn e t w o r kn e e dt o c o n s i d e rt h a tn o d e sh a v en ou n i q u eg l o b a li da n dl i m i t e de n e r g y s ot h e e x i s t i n ga dh o c n e t w o r kr o u t i n gp r o t o c o l sa n da l g o r i t h ma r en o ts u i t a b l ef o rw i r e l e s ss e n s o rn e t w o r k b yt h e a n a l y s eo f s e v e r a lr o u t i n gp r o t o c o l s ，w ef i n dt h e r ea r es o m es h o r t c o m i n g s a s p e c i f i cr o u t i n g p r o t o c o l i sn e e d e d d i r e c t e dd i f l u s i o ni sd e s i g n e df o rw i r e l e s ss e n s o rn e t w o r k t h ed a t ai nt h en e t w o r ks h e u l d b en a m e d t h e nt h en a m e dd a t ac a l lb ep r o c e s s e di n n e t w o r k b y t h es e n s o rn o d ea n dt r a n s m i t t e d o nr e i n f o r c e dp a t h s ot h ea r t i c ld e s i g nam e t h o df o rd a t an a m i n g ( ”a t t r i b u t e - v a l u e - o p e r a t i o n ”) a n dp r o v i d ear u l ef o rd a t am a t c h i n ga n dam e t h o do fg r a d i e n tf o rd e c i d i n gw h i c hp a t hi s s e l e c t e d t h e r ea r et w op a r t so fw o r k si nr e s e a r c h ：t h ef i r s t ，b yu s i n gn e t w o r ks i m u l a t o r 2 ( n s 2 ) ，t h ea l g o r i t h mi si m p l e m e n t e da n ds i m u l a t e dt op r o v et h a tt h er e s u l to fs a v i n ge n e r g y a n dr o u t i n g t h es e c o n d ，i no r d e rt os a v em o r ee n e r g y , t h ea l g o r i t h mi si m p r o v e db yc h a n g i n g t h ew a yo fg a t h e r i n gd a t a b yu s i n gn s 2 ，t h ea r t i c l i m p l e m e n td i r e c t e dd i f f u s i o na n ds o m e e x a m i n a t i o n sa r et r i e dt ot e s tt h er e s u l tt h a tl e s se n e r g ya n dt o l e r a b l et i m ei su s e d t h er e s u l t s h o w st h a td i r e c t e dd i f f u s i o ni sf i tt ow i r e l e s ss e n s o rn e t w o r ka n dh a v eag o o dv i e wi nt h e f u t u r er e s e a e h k e y w o r d ： w ir e e s ss e n s o rn e t w o r k r o u t i n gp r o c o t o is ，d ir e c t e dd i f f u s i o n s a v ee n e r g y 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或其他单位的学位或证书所使用过的材料。与我同工作的同志对本研究所 做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：鱼鱼包日期：坦堕：；：主! 定向扩散法的实现和改进 1 引言 1 1 无线传感器网络 无线传感器网络是当前国际上备受关注、由多种学科高度交叉的新兴前沿研究热点 领域j 。它的研究最早起源于军事领域b 引，近几年来已经越来越引起了人们关注。它综 合了传感器技术、嵌入式计算技术、现代网络及无线通信技术、分布式信息处理技术等【4 ，”， 能够通过各类集成化的微型传感器协作地实时监测、感知和采集各种环境或监测对象的 信息，通过嵌入式系统对信息进行处理，并通过随机自组织无线通信网络以多跳中继方 式将所感知信息传送到用户终端。例如，传感器网络可以向正在准备进行登陆作战的部队 指挥官报告敌方岸滩的详实特征信息，为制定作战方案提供可靠的信息。传感器网络可以 使人们在任何时间、地点和任何环境条件下获取大量详实而可靠的信息。 可以如下定义无线传感器网络 6 1 ：无线传感器网络是由一组传感器以a dh o c 方式构 成的无线网络，其目的是协作地感知、采集和处理网络覆盖的地理区域中感知对象信息， 并发布给观察者。从上述定义可以看到，传感器、感知对象和观察者是传感器网络的三 个基本要素；无线网络是传感器之间、传感器与观察者之间的通信方式，用于在传感器 与观察者之间建立通信路径；协作地感知、采集、处理、发布感知信息是传感器网络的 基本功能。利用一组功能有限的传感器协作地完成大的感知任务是传感器网络的重要特 点。传感器网络中的部分或全部节点可以移动，传感器网络的拓扑结构也会随着节点的 移动而不断地动态变化。节点间以a dh o c 方式进行通信，每个节点都可以充当路由器的 角包，并且每个节点都具备动态搜索、定位和恢复连接的能力。 。 个典型的无线传感器网络的体系构建口l 包括分布式传感器节点( s e n s o rn o d e ) 、接收 发送器( s i n k ) 、互联网( i n t e m e t ) 和用户界面( u s e t ) 等，见图1 1 。传感器节点散布在指定 的感知区域内，每个节点都可以收集数据，并通过“多跳”路由方式把数据传送到接收发 送器。接收发送器也可以用同样的方式将信息发送给各节点。接收发送器直接与i n t e r n e t 或通信卫星相连，通过 n t e m e t 或通信卫星实现用户( 郎监测者) 与传感器之间的通信。 链感器区域佳感器节点 图1 1 一个典型的传感器网络的体系 f i g 1 1at y p i c a ls y s t e mo f w i r e l e s ss e n s o rn e t w o r k 传统意义上的监控网络，大多采用c s 结构的，即存在着一个主要的数据处理中心控 1 定向扩散法的实现和改进 制节点，其他的各个监控点和这个中心控制节点连接起来，所有的数据都直接传送到该 节点，进行集中的分析处理。而无线传感器网络不同于这种传统的网络结构，其中的各 个节点的地位都是一样的，它们只是和邻近的节点进行通信，大量的平等的节点自主的 组成了这样的网络。它的拓扑结构是动态的，网络中的大量节点自适应的维护着网络的 通信，协调的工作。和传统网络比较，无线传感器网络有着有着以下的特点8 】： ( 1 ) 无线传感器网络包括了大面积的空间分布 比如在军事应用方面，可以将无线传感器网络部署在战场上跟踪敌人的军事行动，智 能化的终端可以被大量地装在宣传品、子弹或炮弹壳中，在目标地点撒落下去，形成大 面积的监视网络。又比如，在洪水灾情监控方面，为了测量水势等数据，可以在目标地 点撤播大量的微型传感器，对水灾区域的数据进行采样等。 ( 2 ) 能源受限制 网络中每个节点的电源是有限的，网络大多工作在无人区或者对人体有伤害的恶劣 环境中，更换电源几乎是不可能的事，这势必要求网络功耗要小以延长网络的寿命，而 且要尽最大可能的节省电源消耗。 ( 3 ) 网络自动配置，自动识别节点 这包括自动组网、对入网的终端进行身份验证、防止非法用户入侵。相对于那些布置 在预先指定地点的传感器网络而言，无线传感器网络可以借鉴a dh o c 方式来配置，当然 前提是要有一套合适的通信协议保证网络在无人干预情况下自动运行。 ( 4 ) 网络的自动管理和高度协作性 在无线传感器网络中，数据处理由节点自身完成，这样做的目的是减少无线链路中 传送的数据量，只有与其他节点相关的信息才在链路中传送。以数据为中心是无线传感 器网络的又一个特点，由于节点不是预先计划的，而且节点位置也不是预先确定的，这 样就有一些节点由于发生较多错误或者不能执行指定任务而被中止运行。为了在网络中 监视目标对象，配置冗余节点是必要的，节点之间可以通信和协作，共享数据，这样可 以保证获得被监视对象比较全面的数据。 对用户来说，向所有位于观测区内的传感器发送一个数据请求，然后将采集的数据 送到指定节点处理，可以用一个多播路由协议把消息送到相关节点，这需要一个唯一的 地址表，对于用户而言，不需要知道每个传感器的具体身份号，所以可以用以数据为中 心的组网方式。 传感器网络具有十分广阔的应用前景，在军事国防、工农业、城市管理、生物医疗、 环境监测、抢险救灾、防恐反恐、危险区域远程控制等许多领域都有重要的科研价值和 巨大实用价值，已经引起了世界许多国家军界、学术界和工业界的高度重视，并成为进 入2 0 0 0 年以来公认的新兴前沿热点研究领域，被认为将对二十一世纪产生巨大影响力。 下面简要介绍传感器网络的一些应用。 ( 1 ) 军事应用【1 ，6 】 传感器网络研究最早起源于军事领域，实验系统有海洋声纳监测的大规模传感器网 络，也有监测地面物体的小型传感器网络。现代传感器网络应用中，通过飞机撒播、特 种炮弹发射等手段，可以将大量便宜的传感器密集地撒布于人员不便于到达的观察区域 如敌方阵地内，收集到有用的微观数据；在一部分传感器因为遭破坏等原因失效时，传 感器网络仍能完成观察任务。传感器网络的上述特点使得它具有重大军事价值，可以应 定向扩散法的实现和改进 用于监测人员、装备等情况以及单兵系统：通过在人员、装备上附带各种传感器，可以 让各级指挥员比较准确、及时地掌握己方的保存状态。通过在敌方阵地部署各种传感器， 可以了解敌方武器部署情况，为己方确定进攻目标和进攻路线提供依据。 ( 2 ) 环境应用p 1 应用于环境监测的传感器网络，一般具有部署简单、便宜、长期不需更换电池、无需 派人现场维护的优点。通过密集的节点布置，可以观察到微观的环境因素，为环境研究 和环境监测提供了崭新的途径。传感器网络研究在环境监测领域已经有很多的实例。这 些应用实例包括：对海岛鸟类生活规律的观测；气象现象的观测和天气预报；森林火警； 生物群落的微观观测等。 ( 3 ) 医疗应用i l o l 传感器网络在医疗领域也有成功实例。文献1 0 中提到的s s i m ( s m a r ts e n s o r sa n d i n t e g r a t e dm i c r o s y s t e m s ) 项目中，1 0 0 个微型传感器被植入病人眼中，从而帮助盲人获得 了一定程度的视觉。借助于各种医疗传感器网络，人们可以享受到更方便更舒适的医疗 服务，如远程健康监测，病变器官观察等。 ( 4 ) 建筑及城市管理i l i i 各种无线传感器可以灵活方便地布置于建筑物内，获取室内环境参数，从而为居室环 境控制和危险报警提供依据。 智能家居：通过布置于房间内的温度、湿度、光照、空气成分等无线传感器，感知居 室不同部分的微观状况，从而对空调、门窗以及其他家电进行自动控制，给人们以智能、 舒适的居住环境。 建筑安全：通过布置于建筑物内的图像、声音、气体检测、温度、压力、辐射等传感 器，发现异常事件及时报警，自动启动应急措施。 智能交通：通过布嚣于道路上的速度、识别传感器，监测交通流量等信息，为出行者 提供信息服务，发现违章能及时报警和记录。 ( 5 ) 反恐和公共安全 通过特殊用途的传感器，特别是生物化学传感器监测有害物、危险物的信息，最大限 度地减少其对人民群众生命安全造成的伤害。 1 2 传感器网络路由设计的难点和现状 在前面提到，无线传感器网络具有很广泛的应用前景，但是它的研究还很不成熟，还 有很多方面工作可以去做，而作为网络层中的热点难点问题之一的路由设计也引起了极 大关注。当大量的传感器节点散布在监控区域，需要一套路由协议用于连接采集数据的 传感器节点和接收节点，这是属于网络层的重要问题。 网络层要研究传感器网络通信协议和各种传感器网络技术。传感器网络路出协议第一 方面的研究是通过分析模拟，研究现有通信协议的性能，确定各种现有协议对于传感器网 络的可用性及其优缺点。第二方面的研究是以数据为中心的新的通信协议的研究，包括 通用能源有效性路由算法的研究、面向应用的能源有效性路由算法的研究、动态传感器 网络的路径重构技术的研究等。 在传感器网络发展初期，人们一度认为使用传统a d h o c 网络的路由协议就可以解决 传感器网络的路由需求。但是基于无线传感器网络自身用途和优点，人们发现传统a d h o c 定向扩散法的实现和改进 网络路由协议却不能适用于无线传感器网络： ( 1 ) 传感器网络是以数据为中心进行路由，它不同于a d h o c 网络的点对点通信模式； ( 2 ) 传感器网络随应用需求而变化，其路由协议是基于特定应用进行设计的，很难设 计通用性强的路由协议： ( 3 ) 传统网络( 包括有线和无线) 每一节点具有唯一的标识号( i d ) ，而传感器网络是基 于属性进行寻址的，不需给每一个节点分配唯一地址； ( 4 ) 由于传感器节点能量有限，所以路由设计一般将能效高放在首要位置，能量消耗 的问题将会左右传感器网络路由协议设计的发展。 传统的a dh o e 网络技术中业已成熟的解决方案可以借鉴到无线传感器网络中来，但 是开发专用的通信协议和路由算法已经成为了当前无线传感器网络领域内急待研究的课 题。 对无线传感器网络的路由协议的研究中，国外已经发展了6 8 年左右，当前美国很多 大学都有针对传感器网络的研究小组，而其中又以u c b ，u c l a ，u s c i s i 等大学的研究最为 领先。针对这些问题，这些大学开展了传感器网络通信协议的研究，先后提出了几类新的 通信协议1 6 1 ，包括基于谈判类协议、定向发布类协议、能源敏感类协议、多路径类协议、 传播路由类协议、以数据为中心的路由算法。但由于传感器网络的特点，通用性很强的 路由协议还是没有形成。下面简单的介绍几种基础的路由方案： ( 1 ) 泛洪法( f l o o d i n g ) 【1 2 】是一种传统的网络通信路由协议。如图1 3 所示，节点a 希 望发送一块数据给节点d ，使用泛洪法，节点a 首先通过网络将数据副本传送给它的每一 个邻居节点，每一个邻居节点又将其传输给各自的每一个邻居节点，( 除了刚刚给它们发 送数据副本的节点a 外) 。如此继续下去，直到将数据传输到目标节点d 停止，或者为 该数据所设定的生命期限变为零。 泛洪法所具有的优点：实现简单；不需要为保持网络拓扑信息和实现复杂的路由发 现算法而消耗计算资源；适用于健壮性要求高的场合。 表现不足的地方主要有：存在信息爆炸( i m p l o s i o n ) 问题，即出现一个节点可能得 到一个数据多个副本的现象；出现部分重叠( o v e r l a p ) 现象，如果处于同一观测环境的 两个相邻同类传感器节点同时对一个事件作出反应，二者采集的数据性质相同，数值相 近，那么，这两个节点的邻居节点将收到双份数据副本；盲目使用资源，即扩散法不 考虑各节点能量可用状况因而无法作出相应的自适应路由选择。 图1 2f l o o d i n g 法信息爆炸问题 f i g 1 2t h ei m p l o s i o np r o b l e m i nf l o o d i n g 泛洪是一种传统的路由技术，不要求维护网络的拓扑结构，并进行路由计算，接收到 消息的节点以广播形式转发分组。对于自组织的传感器网络，泛洪路由是一种较直接的 实现方法，但消息的内爆和重叠是其固有的缺陷。为了克服这些缺陷，s h e d e t n i e m i 等人 定向扩散法的实现和改进 提出了g o s s i p i n g 策略。 ( 2 ) 闲聊法( g o s s i p i n g ) i l3 j 是扩散法的改进版本。为节约能量，闲聊法使用随机性原则。 一节点发送数据，不再象扩散法那样，给它的每一个邻居节点发送数据副本，而是随机 选择某一个邻居节点，向它发送份数据副本。如果一个节点己收到它的邻居节点的数 据副本，若再次收到，那么，它将此数据发回它的邻居节点。 尽管闲聊法可避免出现信息爆炸问题，但是仍然无法解决部分重叠现象和盲目使用 资源问题，如图1 3 所示，信息r 被两条路径都传输了。而且有可能增加端到端的传输延 时，数据传输平均时延拉长，使传输速度变慢。 ， j 图1 3 闲聊法的数据重发问题 f i g 1 3t h eo v e r l a pp r o b l e mi ng o s s i p i n g 为了解决扩散法存在的不足之处，提出了s p 蹦法。s p i n 是种以数据为中心的自 适应通信路由协议，s p 叫协议目的是通过使用节点间的协商制度和资源自适应机制。 ( 3 ) s p i n ( s e n s o rp r o t o c o lf o i n f o r m a t i o nv i an e g o t i a t i o n ) “q ”1 是以数据为中心的自适应 路由协议，通过协商机制来解决泛洪算法中的内爆和重叠问题。传感器节点仅广播采集数 据的描述信息，当有相应的请求时，才。有目的地发送数据信息。 为了避免出现扩散法的信息爆炸问题和部分重叠现象，传感器节点在传送数据之前 彼此进行协商，协商制度可确保传输有用数据。节点问通过发送元数据( 即描述传感器节 点采集韵数据属性的数据，m e t a - d a t a ) ，而不是采集的整个数据进行协商。由于元数据大 小小于采集的数据，所以，传输元数据消耗的能量相对较少。为避免盲目使用资源，所 有传感器节点必须监控各自的能量变化情况。 在传输或接收数据之前，每个节点都必须检查各自可用的能量状况，如果处于低能 量水平，必须中止一些操作，比如充当数据中转站( 路由器) 角色的一些数据转发操作。 s p i n 协议中有3 种消息： 1 ) a d v 一用于新数据广播。当一个节点有数据可共亨时，它可用a d v 消息对外广播。 2 ) r e q 一用于请求发送数据。当一个节点希望接收d a t a 数据包时，发送r e q 消息。 3 ) d a t a - 包含元数据头( m e t a - d a t ah e a d e r ) 的传感器采集的数据包。 s p i n 协议具体发展出4 种不同的形式：s p i n p p 。采用点到点的通信模式，并假 定两节点间的通信不受其他节点的干扰，分组不会丢失，功率没有任何限制。要发送数 据的节点通过a d v 向它的相邻节点广播消息，感兴趣的节点通过r e q 发送请求，数据 源向请求者发送数据。接收到数据的节点再向它的相邻节点广播a d v 消息，如此重复， 使所有节点都有机会接收到任何数据。s p i n e c 。在s p i n p p 的基础上考虑了节点的功 耗，只有能够顺利完成所有任务且能量不低于设定闽值的节点才可参与数据交换。 s p l n b c 。设计了广播信道，使所有在有效半径内的节点可以同时完成数据交换。为了防 止产生重复的r e q 请求，节点在听到a d v 消息以后，设定一个随机定时器来控制r e q 请求的发送，其他节点听到该请求，主动放弃请求权利。s p i n r l 。它是对s p i n b c 的完善，主要考虑如何恢复无线链路引入的分组差错与丢失。记录a d v 消息的相关状态， 如果在确定时间间隔内接收不到请求数据，则发送重传请求，重传请求的次数有一定的 定向扩散法的实现和改进 限制。 下图1 4 更加明了的指出了s p i n 过程。 s 够眵店拶 圈1 4s p i n 协议工作阶段 h g 1 4s p i n p r o t o c o lp h a s e s ( 4 ) d i r e c t e dd i f f u s i o n ( 定向扩散法) 1 7 , 1 8 】：也是一种以数据为中心的路由协议。定向扩 散模型是e s t r i n 等人专门为传感器网络设计的路由策略，与已有的路由算法有着截然不同 的实现机制。d i r e c t e dd i f f u s i o n 协议的一大特点是引入网络梯度概念，并将其应用于无线 传感器网络的路由通信。 接收器或基站向所有传感器节点发送其兴趣( i n t e r e s t ) ，即通过分配不同属性值来表 示不同任务的描述符) ，每个传感器节点在收到兴趣后保存在各自的c a c h e 中。每个兴趣 项( i n t e r e s te n t r y ) 包含一个时间标签域( t i m e s t a m pf i e l d ) 和若干个梯度域( g r a d i e n tf i e l d ，按 成本最小化和能量自适应原则引导数据扩散的方向) 。当一个兴趣传遍整个网络后，从数 据源节点( 即兴趣所在区域的传感器节点) 到接收转发节点或基站之间的梯度就建立起来 了。旦数据源节点采集到兴趣所需的数据，那么源节点沿着该兴趣的梯度路径传输数 据到接收转发节点或基站。因为在后面的文章将会具体介绍定向扩散法，所以在这里就 不对定向扩散法做更多的介绍了。 1 3 定向扩散算法提出的意义和难处 在前面提到了无线传感器网络和传统网络的不同特点，这些不同特点给网络层路由 设计也提出了和过去不同的要求【1 7 , 1 8 】。例如： ( 1 ) 传感器网络中的传感器节点数量远大于a d h o c 网络中的节点数： ( 2 ) 传感器节点出现故障的频率要大于a dh o c 网络； ( 3 ) 传感器节点要比因特网和a dh o c 网络中的节点简单： ( 4 ) 传感器节点的能量有限； ( 5 ) 因特网的数据报头对于传感器网络来说太长，例如，每个节点必须有一个永久的 地址。 研究初期，人们以为把互连网或者a dh o c 网络的路由方式套用在传感器网络上就可 以。但是由于上述的各种不同特点和要求，通过前面几种路由方式的研究，发现过去的 定向扩散法的实现和改进 路由方式不能完全满足要求。在做了很多传统路由方式用于无线传感器网络的尝试后， 人们达成共识，要想无线传感器网络可实际应用起来，网络层的路由设计就必须取得质 的突破，必须针对无线传感器网络的特点去专门设计特定的路由策略。为此，美国u c l a 大学的e s m n 等人专门为传感器网络设计提出了路由策略：定向扩散法，它与传统路由算 法有着不同的实现机制，在针对无线传感器网络的各个特点，尤其是在和传统网络比较 中的不同点做出了各种处理措施。 该协议的中心就是在数据命名机制和数据扩散的基础上，完成在节点间的数据定向 扩散传输，即从网络中的某些接收节点注入查询任务，该任务在网络中扩散，当适当的 源节点收到该任务后，采取响应措施，返回数据给接收节点。其中数据命名机制很好的 满足了以数据为中心进行路由要求。关于定向扩散法的基本概念和基本原理，将会在后 续的章节做出更加详尽的解释。 在定向扩散法提出以后，无线传感器网络路由设计开始了一个新的台阶。改变此前 没有专门为无线传感器网络设计的路由策略的情况。定向扩散思想的提出为以数据为中 心的传感器网络路由设计指出了发展的主流方向，奠定了传感器网络路由设计的重要基 础。它是以数据为中心的网络路由设计的一个极为重要的里程碑，其后的传感器网络路 由协议设计都或多或少受到这种思想的影响。所以要入手传感器网络的路由设计，就应 当对定向扩散法有着深刻了解，掌握定向扩散法设计要点，这样才能更好的把握住无线 传感器网络路由设计的特殊要求和解决措施。 但是在研究定向扩散法的过程中，存在着诸多问题需要解决： 1 ) 由于国内对无线传感器网络的研究才起步，没有相关的中文资料可供借鉴，只能 查询国际上的相关文献。当前，国外发表文献中都没有具体介绍定向扩散法细节，这就 造成对定向扩散法的理解上的困难，需要去揣摩定向扩散法的设计意图，去分析出其中 细节上的处理。为了今后的查阅和给其它研究人员提供相关的中文资料，很有必要首先 把定向扩散法用文字描述出来，讨论其中各个基本概念。 2 ) 要选用合适的仿真工具。这种仿真工具要能很方便的实现自定义路由方式，同时 不用过多关注网络研究中的其他问题。此外，还要运行速度快，能方便产生大量网络节 点，对数据传输信息详细记录，最后结果能便于统计的要求。好的仿真工具能让数据结 果具有说服力，采用仿真工具n s 2 更多的基于上面的考虑。 3 ) 定向扩散法在能量节省和路径选通方面的优势能有多大，还需要设计合适的试验 测试。在本文的工作中，最为关注的参数是能量节省程度。 4 ) 能否在细节上改进定向扩散法，以获得更好能量节省效果是本文在研究之初提出 的一个疑问，这是在理解并实现定向扩散法的基础上的后续工作，也是本文工作最主要 的目的和成果之一。 本文的主要工作就是解决上面存在的问题，研究定向扩散法。 1 4 本文的主要工作 前面提到了无线传感器网络和专门为它设计的路由方法：定向扩散法。中科院计算 所苏州分会和中科院计算所网络研究室于2 0 0 4 年初开始了传感器网络的研究，本文作者 于2 0 0 3 年7 月至2 0 0 4 年1 1 月有幸参与了该项目，具体担任了无线传感器网络的路由设 计的主要先行研究工作。 定向扩散法的实现和改进 在无线传感器网络路由设计的研究期间，本文主要工作和成果有以下几个方面： ( 1 ) 对无线传感器网络的各种路由方法进行整理比较归纳出影响设计方案的主要因 素。在本文相关的开题综述中对这部分的工作经进行了详尽的介绍，在文章的1 ，2 节也 进行了说明。工作结果表明定向扩散法是无线传感器网络路由设计中的极具代表性的方 法，它是专门针对无线传感器网络的特点提出的路由策略，对今后的无线传感器网络的 路由设计有着巨大的借鉴作用，因此确定了定向扩散法做为传感器网络路由设计的重点。 ( 2 ) 本文要阐述的主要工作的第一个部分就是要对定向扩散法进行研究。由于当前发 表的文献中都没有具体提及定向扩散法的具体细节和实现，为了理解它的基本概念和基 本原理，本文通过仿真来达到这一目的。同时，为了观测它在路径选择上( 也就是时延 参数) 和能量节省两个性能参数上能否到达预期的效果，还设计一系列的试验来验证， 其中提高节省能量的性能是研究重点。 在对定向扩散法基本概念和基本原理的研究后，归纳出了定向扩散法的几个基本概 念：数据命名机制，兴趣，网络梯度，数据传输，数据通路的加强。对定向扩散法的细 节进行了整理，给予了书面文字的描述，这样一方面便于在后续工作中查阅，另方面 便于交接给其它研究人员。 本文选用了国际比较常用的网络仿真器n s 2 的仿真工具。在它的环境中，首先用c + 十 来实现定向扩散法具体协议，然后利用n s 2 提供的o t c l 语言接口来配置仿真试验场景。 为了测试定向扩散法在能量消耗和时延两个参数上的效果，设计了系列试验，分别是规 则和不规则网络拓扑结构下的试验。这一系列的试验结果很好的说明了定向扩散法在能 量节省上取得了优势，同时时间延迟上却没有较大的牺牲。 ( 3 ) 本文要阐述的主要工作的第二个部分就是改动定向扩散法的数据采集发送的方 式，目舶为了在能量消耗上取得更好的效果。如果控制住源头的冗余数据传输的产生， 就可暾节省在冗余数据传输时消耗的能量。因此在源节点进行数据采集时，利用传感器 网络节点的密度大的特点，选出监测区域的某个节点为二级节点，由它来接收监测区的 其它节点收集的数据，并且整理，这样在监测区就剔除冗余数据的产生。 为了验证这个改动是否可行。在能量节省方面是否能取得更好的优势，本文在n s 2 下进行了仿真，试验结果表明了这种改进的可行性。这部分的工作在本文的第五章做了 甚为详细的说明。 本文要阐述的主要工作主要就是( 2 ) 和( 3 ) 部分。对定向扩散法进行了详细的研 究，仿真和改进，目的就是深刻理解这种专门为无线传感器网络设计的路由方法，从而 为今后开发设计自己的无线传感器网络路由方法的一些有易的探索和尝试。总而言之， 希望能通过对具体的一两种代表性极强的方法的研究来展开今后对无线传感器网络路由 方法设计的工作。下面文章的结构也将围绕所做的工作进行详细介绍。 第二章对定向扩散算法基本概念做了介绍。算法有以下几令基本概念：兴趣，命名 机制，梯度，路径加固。定向扩散算法是应用在以数据为中心的网络系统。这类系统需 要对数据进行命名，这不同于传统的端到端的网络应用。对网络通路加强做了很详尽的 说明，指出这样做是为了让高质量的数据在高质量的路径上传输。第三章，在介绍n s 2 的 基础上介绍了的代码具体实现。在定向扩散法的c + + 实现中。首先设计了以数据为中心的 网络应用系统，然后在此基础上实现了定向扩散法。在o t c l 语言的介绍中，介绍了试验 场景的具体配置，如节点的各个参数设定，节点的创建，网络拓扑的生成，数据的产生 定向扩散法的实现和改进 发布等。最后还介绍了仿真以后生成的t r a c e 文件格式以及如何统计结果。在第四章，设 计了两个试验。第一个试验系列是为了查看定向扩散法是否能实现期望的路由方式，主 要是通过时延参数来观测，同时也观测了能量节省的效果，选择规则网格的拓扑图。第 二个试验则是采用不规则的拓扑结构，因为在实际应用中的传感器节点的分布最大可能 是没有规律的随机散落在一定的区域中去的。在仿真运行后，对能量和时间迟延都做出 统计，给出统计图。第五章中，根据在前面试验中发现的数据冗余问题，提出了改进方 法：选用监测区域的二级节点，在监测区就剔除冗余数据的传输。仿真试验表明，这种改 动可以获得更好的能量节省。在第六章对总结了全文，并对无线传感器网络路由设计的 研究做了展望! 定向扩散法的实现和改进 2 定向扩散算法理论基础 定向扩散法是一种以数据为中心的路由协议 1 7 , 1 8 , 1 9 】。该算法的主要特点是在数据扩散 的过程中，计算出代价较低的数据通路，进行比较直接的方向明确的数据传输。 在算法中，数据是要被描述的，通过属性组合( a t t r i b u t e - p a i r ) 的方式进行命名 ( n a m i n g ) 1 1 。接收发送器( s i n k ) 的业务查询作为对某些数据的兴趣( i n t e r e s t ) 被注入网 络，并在网络中扩散。这个扩散的过程同时也在网络中建立了若干的梯度( g r a d i e n t ) ，用 来提取出具体的所关心的事件( e v e n t ) ，也就是与i n t e r e s t h 匹配的实际数据。这些结果 数据会根据己有的梯度，沿着不同的路径返回到s i i l k 节点。然后算法会要求根据一定的标 准，从若干条返回路径中，选出它认为代价较低的一条进行数据传输。上面就是大致的 定向扩散法步骤，图2 1 描述了定向扩散法的不同工作阶段。 接收器 。 、o 图2 1 定向扩散路由原理 f i g 2 1p r i n c i p l eo f d i r e c t e dd i f f u s i o nr o u t i n g o 鬟掳萤苣 图2 1 f a ) 是接收发送器向源节点发送兴趣，把兴趣发表给整个网路。图2 i ( b ) n u 是在 源节点和接收发送器问建立网络梯度，为了方便简单起见，加入标量表示梯度大小。图 2 1 ( c ) 为按照最大梯度建立数据传输路线后，传输数据。 所以，算法有以下几个基本概念：兴趣，网络梯度，路径加固。兴趣就是监测者所 在的数据接收器( s i n k ) 的业务查询，通过一组属性组合来表示不同任务。节点收集到感兴 趣的数据后，针对不同的兴趣，将按照命名机制产生数据包。网络梯度的建立是为了把 数据包从数据源节点( s o u r c e ) 拉到数据接收发送器( s i n k ) 。路径加固( r e i n f o r c e m e n t ) 是选 择较优路径进行加固，以传输数据。 2 1 定向扩散法的基本概念 本文为了更加直观的介绍定向扩散法，在具体介绍之前，先举个例子，然后在这个 例子的基础上，对算法进行详细的介绍。比如在某处公路，放置了大量的传感器节点， 来对某些路段的汽车的分布进行监控。可以在监控中心，从该节点发出了对某区域的汽 车行踪的业务查询，当该区域的传感器节点收到这条任务后，就会按照要求的返回观测 结果。如监控中心发出了这样一条命令，请 一1 0 0 ，1 0 0 ，2 0 0 ，4 0 0 区域所有观测到有车辆 的节点，每隔1 0 毫秒向监控中心汇报一下情况，这条命令的有效期是l o 秒。 “ o o 定向扩散法的实现和改进 2 2 1 数据命名机制 在定向扩散算法中，是用一组属性值来命名兴趣和数据包 1 8 , 2 0 j ”。所以这么来做，是 因为传感器网络节点没有全局唯一的i d ，每个节点都只是知道邻近传感器节点的情况，而 不知道全局所有节点的信息。为了保证源节点产生的数据能够传输到监测者所在的接收 发送器，就需要把兴趣和采集的数据以一种方式对应起来【4 ”。因为这个原因，把兴趣用组 合属性值来描述，数据包也相应的使用了类似的属性值命名。象上面汽车监控的例子，就 可以简单的把观测任务，即兴趣按照下面的方式进行描述： t y p e = w h e e l e dv e h i c l e车辆类型 i n t r v a l= 1 0m s 每2 0 m s 发送一次数据 d u r a t i o r l= i 0s1 0 秒有效期 r e e t = 一1 0 0 ，1 0 0 ，2 0 0 ，4 0 0 传感器所在区域 因为该任务描述表达了对满足条件的数据的兴趣，所以把这个任务描述称为“兴趣 ( i n t e r e s t ) ”。当然这只是根简单的描述。通常雨言，一个兴趣的属性组合描述要包括：监 测对象，监测区域，起始时间，有效时间，发送周期等，不同的任务可以增加各自的特 殊的属性项。而源节点产生的数据包同样用一组属性值来表示，对应于兴趣的组合属性 的格式，对返回的匹配的响应数据也采用相同的规则命名，例如当一个传感器节点发现 了一辆卡车，它将发送下面格式的响应数据： t y p e = w h e e l e dv e h i e l e 车辆类型 1 1 1 s t a n c e= t m c k 具体车辆类型 l o c a t i o n = 2 5 ，2 2 0 采集节点的位置 i n t e n s i t y = 0 6信号强度 c o n f i d e n c e = 0 8 5信号可信匹配度 t i m e s t a m p = 0 1 ：0 2 ：1 2 数据采集时间 这样兴趣和相关的观测数据就对应联系起来了。这里要需要指出信号匹配度 ( i n t e n s i t y ) ，它表示采集的数据信号和兴趣的匹配度，数值越高表示采集到的数据越满足 观测要求。一般而言，每一属性都有一定的数值范围，也都可以设定一定的可信匹配度 的。这样可以避免低于可信度的无效数据的传输。 基于传感器网络中是一系列的业务查询，将定向扩散算法应用于某传感器网络的 第一步骤就是要根据应用的特点，制定一套数据命名模式。有多种不同的数据命名模式 可以选择，上面的汽车监控例子的列表方法不一定是最好的一种，只是为了自2 够清楚的 解释算法。 2 2 2 兴趣传播和梯度建立 当监控中心需要对某一区域进行监控，获取数据时，会生产兴趣，并且把它通过数据 接收发送器注a n 络中。在兴趣传播的过程中，相关的网络梯度也会随之建立起来。所 以把兴趣传播和梯度建立放在一起介绍【1 7 , 1 8 1 。 2 2 2 1 兴趣 兴趣就是监测业务，目的是为了获得特定的数据。当观测者想要查询监测某区域时 1 l 定向扩散法的实现和改进 就会以通过接收发送器向周边广播兴趣，逐级扩散，最终遍历全网，直到找到所有匹配的 监测区【”, 2 3 , 2 4 1 。 根据前面给出的命名模式，来具体描述一下兴趣是怎样在网络中传播的。数据接收发 送器节点初始化了这样一个兴趣，带有特定的t y p e 信息，要求响应节点处于r e c t 限制范 围内，时限是1 0 分钟，事件的发生时间间隔是1 0 毫秒，就是说要求事件响应频率是每秒 钟响应1 0 0 次。数据接收发送器节点对这个兴趣是有记录的。当超过了预定的持续时限， 该任务将被取消。 对于每一个监测业务，数据接收发送器节点都周期性的向它的邻节点广播兴趣，这样 做的原因是为了适应实际网络的不可靠性，保证兴趣不会在网络中丢失。初始的兴趣包 含着特定的观测区域( r e c t ) 和持续时限( d u r a t i o n ) 属性值，一开始，可以先把发送的 时间间隔的值取的比实际的要求响应间隔大一些。这么做并不包含着算法的什么一般性 的思想，只是针对分析的例子选择的比较有效的技巧。把这个初始的兴趣当作了一个探 路者来看待，让它到网络中搜寻是否有适当的响应节点。当收到了响应节点发回来的响 应数据，并根据一定的规则建立了比较直接的，高效的数据通路以后，才将数据的响应 频率调高。在前面