（通信与信息系统专业论文）容迟移动传感器网络路由与缓存管理研究.pdf

摘要 摘要 无线传感器网络是一种特殊的无线通信网，其节点体积小，数量大，易于 部署并自组织成网，能够在各种特殊环境下采集数据并且把采集结果返还给人 们，极大得改变了人类的生活、工作方式，是2 1 世纪的重要新技术。 随着数据采集工作的进一步发展，传统的固定式传感器网络己经不能满足 某些应用场合，对移动对象的数据采集要求传感器设备随着被采集对象移动， 使数据采集更为精确、准时，容迟移动传感器网络应运而生。 容迟移动传感器网络由处于移动状态的传感器节点构成，在节点状态、网 络拓扑、数据传输以及数据汇聚能各个方面都具有明显的容迟特性。具体表现 在节点地理位置始终变化，网络拓扑高度动态，网络无固定的端到端链路，数 据传输由中间节点的“存储转发来完成。 本文针对移动对象的数据采集应用，分析了容迟移动传感器网络结构，总 结了该型网络与传统传感器网络的相同点和不同点，深入研究了容迟移动传感 器网络对路由协议所带来的新挑战。在调研和分析现有传感器网络的路由协议 基础上，本文提出一种新方案，该方案具备多跳传播和报文冗余的特点，同时 结合了相应的缓存管理策略，良好地解决了报文冗余造成的缓存占满问题。在 网络拓扑变化频繁，连接时断时续，节点缓存空间有限的情况下，本文提出的 方案相对于传统路由策略有明显优势，增加了报文传输成功率。减小了平均传 输延迟，同时对于不同重要性的报文提供了分级的服务质量支持。 关键字：容迟网络，无线传感器网络，路由协议，多复制路由，多跳传播 a b s t r a c t a b s t r a c t w s n ( w i r e l e s ss e n s o rn e t w o r k ) i sas p e c i a lt y p eo fw i r e l e s sc o m m u n i c a t i o n n e t w o r k sw h i c hi sa b l et oc o l l e c td a t ai nv a r i a b l ee n v i r o n m e n t sa n dt h e nf e e dt h e m b a c kt op e o p l e n o r m a l l y ，w s ni sc o m p o s e do fl a r g ea m o u n to ft i n ys e l f - o r g a n i z i n g n o d e s a sw s nh a sg r e a t l yc h a n g e dh u m a nl i f ea n dw o r k i n g ，i t sa ni m p o r t a n ts t a t e o ft h ea r tt e c h n o l o g yi nt h e215 c e n t u r y a sl o n ga sr e a lw o r l dd a t as e n s i n g g a t h e r i n gd e v e l o p e df u r t h e r , t h et r a d i t i o n a l f i x e d l o c a t i o ns e n s o rn e t w o r k sa r en o ta b l et oq u a l i f ys o m es p e c i f i ca p p l i c a t i o n ss u c h a sm o b i l ed e v i c e sa n dc r e a t u r e s t h es e n s o r sa r er e q u e s t e dt om o v et o g e t h e rw i t h t h e s eo b j e c t st og e tm o r ea c c u r a t ed a t a ，s ot h ed t m s n ( d e l a yt o l e r a n tm o b i l e s e n s o rn e t w o r k ) c o m e si n t oe y e s d t m s ni sc o n s t r u c t e db ym o b i l es e n s o rn o d e s t h en o d e s m o b i l i t y , d y n a m i c t o p o l o g y ，h i g hp a r t i t i o nr a t em a k e si t d i f f e r e n tf r o mt r a d i t i o n a ln e t w o r k s t os o l v e t h e s ep r o b l e m sw h i c hc a u s eo b v i o u sd e l a y , t h e “s a v ea n df o r w a r d m e t h o di sa d o p t e d b ys e n s o rn o d e s t h i st h e s i sa n a l y z e dt h es t r u c t u r eo fd t m s n ，c o m p a r e di tt ot r a d i t i o n a ls e n s o r n e t w o r k sa n dg a v et h ed i f f e r e n c e sb e t w e e nt h e m i ta l s or e s e a r c h e dt h en e w c h a l l e n g e st or o u t i n gp r o t o c o l sb yd t m s n a f t e ri n v e s t i g a t i n ga n da n a l y z i n gs o m e e x i s t i n gr o u t i n gp r o t o c o l s ，t h i sd i s s e r t a t i o np r o p o s e dan e w s c h e m ew h i c hh a st h e f e a t u r eo fm u l t i h o pr o u t i n ga n dr e d u n d a n tm e s s a g e s t h i ss c h e m ea l s oc o m b i n e s c o r r e s p o n d i n gb u f f e r - m a n a g e m e n tt a c t i c sw h i c hs o l v e dt h eb u f f e rf i l l i n gc r i s i sc a u s e d b y r e d u n d a n tm e s s a g e s w h e nt h et o p o l o g yo ft h en e t w o r kc h a n g e sq u i c k l y , c o n n e c t i o n sb e c o m eu n s t a b l ea n db u f f e rs i z eo ft h en o d e sa r ec o n s t r a i n e d ，t h es c h e m e p r o p o s e db yt h i st h e s i sh a sa no b v i o u sa d v a n t a g et ot r a d i t i o n a lm e t h o d s i ti n c r e a s e s t h es u c c e s st r a n s f e rr a t eo ft h em e s s a g e s ，d e c r e a s e st h ea v e r a g et r a n s f e rd e l a y i nt h e s a m et i m e ，i t s u p p o r t s c l a s s i f i e dq u a l i t yo fs e r v i c ef o rd i f f e r e n t i m p o r t a n c e m e s s a g e s 1 i i a b s t r a c t k e y w o r d s ：d e l a yt o l e r a n tn e t w o r k ，w i r e l e s ss e n s o rn e t w o r k ，r o u t i n g ，m u l t i c o p y ， m u l t i h o p l v 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：茸二蘑 签字日期：圣丝2 ：笸：圣 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫捕等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 囱公开口保密( 年) 作者签名：进二蓬 签字日期：2 翌2 ：笪：兰 导师签名： 签字日期： 第1 章绪论 1 1 引言 第1 章绪论 无线传感器网络w s n ( w i r e l e s ss e n s o rn e t w o r k ) 是一种新型的网络和计算 技术，它可以将客观世界中不断变化的信息数据持续高效地传递给人们，为人 们提供各种形式的服务。无线传感器网络不需要周定网络支持，具有快速展开。 抗毁能力强等特点，冈此被认为是2 1 世纪最重要的技术之一，随着无线传感器 网络的日益成熟和普及，人们的生活质量和生产效率将大大提高。 从节点的布置方式来看，无线传感器网络可以分为三种类型。一种是同定 的无线传感器网络，该类网络由固定的传感器节点和数据收集节点组成，传感 器和收发节点在安放完成后位置不再发生变化。第二种是部分固定的传感器网 络，该类网络的传感器节点通常被固定在个需要被采集数据的资源旁边，但 是受到传输距离的限制，数据收集通常使用可以移动的节点来完成，典型的例 子是f e r r y ，比如卫星中继传感器网络，其中近地卫星充当了f e r r y 的角色，只 有当近地卫星飞过传感器附近时，传感器节点才将数据发送给卫星，通过卫星 的通信链路回传到地面站。第三种是传感器节点和数据收集节点都在运动的网 络，传感器节点根据各种不同应用分布在不同的采集对象上，比如车、船、人 等，为了在不影响他们正常活动的情况下完成数据的采集，传感器节点和数据 收集节点必须随着他们的载体一起移动。 本文主要讨论的对象既是第三种无线传感器网络一容迟移动传感器网络 d t m s n ( d e l a y t o l e r a n tm o b i l es e n s o rn e t w o r k ) 。容迟移动传感器网络从功能和 应用上看，是无线传感器网络的一种，从网络构成来看，属于移动a d h o c 网络 m a n e t ( m o b i l ea dh o cn e t w o r k ) 中移动性在网络行为中占据主要地位的一种。 在这种网络中，不存在基站等设各，每个移动节点都是自主的能够相互通信的 传感器节点或者数据收发节点。这种结构的无线传感器网络在现在社会中的应 用非常广泛，如在军事、科研、商业领域的应用。由于其移动节点自组织成网、 易于架设的特性，比起传统固定网络在战争、野外活动等场合下有巨大的优势， 适合于组成战场信息系统、紧急救援救灾指挥、野生动物追踪、危险作业条件 第1 章绪论 科研数据采集等等。 容迟移动传感器网络有以下几个显著特征： l 。节点的移动性： 删络中的每个节点都不是固定刁i 动的，斯是可以独 立地做随机的运动。 2 动态的网络拓扑结构：由于网络中每个节点都可以自由得独立运动， 而节点的收发距离有限，使得节点之间的相互连通性随时改变，网 络拓扑不断变化。更糟糕的是，很多情况下网络拓扑的改变是随机 的，不可预料的。 3 传输；糟宽受限：通常情况下，无线链路的容量比相应的有线链路要 低很多，再考虑到无线传感器网络应用的复杂环境以及相互间的干 扰，低功率的发射天线，实际可获得的链路容量比理想的无线信道 还要低很多。 4 传感器节点能量受限：通常情况下，容迟移动传感器网络的节点都 是通信能力有限的小型便携式设备，为了不影响被采集者的正常活 动状态，这些便携式设备都需要使用电池供电，这决定了传感器节 点的能量是相当有限的。为了获得较长的使用时间，需要在天线发 射功率、精简m a c 和路由协议上下工夫。 1 2 研究背景 1 2 1 无线传感器网络的相关背景 2 0 0 3 年2 月，在美国技术评论杂志评选出对人类未来生活产生深远影 响的十大新兴技术中，无线传感器网络占据一席之地。2 0 0 3 年8 月，无线传感 器网络又在美国商业周刊在技术评论中获得2 1 世纪高技术领域的四大支柱 型产业中的第二位。自上世纪9 0 年代末国外就有大量企业和大学开展了无线传 感器网络的研发，企业方面有i n t e l 、i b m 、m i c r o s o f t 、h o n e y w e l l 等大量高技术 企业的研究机构参加；大学方面，u c b e r k e l e y 、m i t 、u i u c 、c o r n e l l 、h a r v a r d 等多个研究小组率先进行了相关研究。目前发展得比较成熟的是u c b e r k e l e y 的 第1 章绪论 m o t e l l ，2 】系列器件和操作系统t i n y o s 3 l 。近儿年，随着移动传感器网络的发展， 其在现实世界中的应 更为，“泛，主要应用领域有： 1 。军事应j 丑 无线传感器网络最早的用途就是军用，可以通过飞机播撒、人工布置等多 种方式安放到战场卜，迅速投入使用，难于被发现，并且自组织的特性使其抗 毁能力大大加强，少数节点的损坏不至于导致整个嘲络瘫痪。在战场上的无线 传感器网络可以监控战场状态，侦查兵力部署，也可以充当各种定向武器的向 导，为其定点打击提供地理位置信息。 2 自然环境科学 可以用于野生动物保护和研究，例如z e b mn e t 4 l ，监控了大草原上斑马群 落的迁徙特征，个体的生存与死亡。可以用于现代化农场的温度和湿度监控， 实现农作物远程智能灌溉和温度控制。 3 医疗健康 用于检测病人或者高危人群的体温、血压、脉搏等体征，无论用户在家或 者在医院都能迅速将数据发送至诊疗中心，对病人和高危人群进行长时间监控， 保证医疗的及时有效。 4 危险、紧急作业场合 在地震、有毒化学药品泄露、易燃易爆等危害生命的环境下，无线传感器 网络可以快速布置到现场，并且代替人的感官，在恶劣条件下获得灾情信息， 指挥抢险救灾。 5 商业应用 在导游系统、仓库管理和交通管理中，无线传感器网络都有其发挥用途的 场合。 1 2 2 容迟网络的相关背景 容迟网络d t n ( d e l a yt o l e r a n tn e t w o r k ) 最早是l 訇k e v i nf a l l 5 ) 提出，为了 应用于受g 愀c h n l e n g e dn e t w o r k 。受限网络是由于主机和路由器的移动而被 3 第1 章绪论 提出的，和传统网络有以下主要区别：传统网络认为数据源和i _ | 的地之问存在 长时间有效的端到端路径，而容迟嘲络不存在可靠的端到端传输路径；传统网 络中任f - 叮节点之问数据的最人往返时间不会太长，否则会认为是丢包，而容迟 网络经常出现节点之间长期无法通信的状况，时间可以长达数小时或数天：传 统网络端到- 丛1 而1 1 1 的分组丢失率较小，而容迟网络不能保证分组丢失率。具体的例 子有： 陆地移动网络t m n ( t e r r e s t r i a lm o b i l en e t w o r k s ) ：在很多情况下，由于节 点的移动性或射频冲突，这些网络会被意想不到得分离开。在某些情况下，网 络可能难以形成一条确定的端到端的完整链路，然而网络的分裂方式可以预测， 例如一辆按既定路线行驶的公共汽车，它可以被用作消息存储和转发的工具， 在途径一些固定节点时，使j j 有限的传输距离和节点进行通讯，并且捎带其它 节点的数据。 外来媒体网络e m n ( e x o t i cm e d i an e t w o r k s ) ：外来通信媒体包括了近地：卫 星通信、长距离无线链路( 例如秒级或分钟级传播延迟的太空通信系统) 、在大 气或水中采用声波调制的通信方式等等。这些系统有可预知的高延迟( 例如出 于行星的动态性) 、也可能有凶环境因素引起的损耗，或者提供- - 乖 t h 。划内的某 时段可用的存储转发网络服务( 例如每天一次或多次通过固定区域的低地轨道 通信卫星) 。 军事无线自组织网络：这类网络可能部署在敌对环境中。节点的移动性、 不可预测的环境因素或者故意的人为干扰都可能引起网络分裂。除此之外，当 有高优先级的业务时，低优先级业务需要和高优先级业务去竞争带宽，这将使 得信息转发经历更大的排队延迟。同时，出于可靠性和安全性考虑，这类系统 需要很强的安全协议。 传感器和传感器执行器网络：这类网络中的节点存在着严重的能量、存储 空间和计算能力的不足。此外，这类网络可能规模很大，包含数千乃至数百万 量级的节点。为了保存能量，这类网络中的通信常常是预订的，可能在一段时 间内不存在及时的通信路径。传感器和传感器执行器网络通常通过具有协议转 换能力的代理节点互联其他网络。 容迟网络路由技术是其中的关键，路由协议包括三个部分：如何建市网络 4 第1 章绪论 的拓扑结构、如何维护网络拓扑和路由算法。由于在d t n 中节点之问的连接是 不稳定的，所以删络的拓扑结构是随时变化的，这要求d t n 路山的：卜蔓月的并 不是选择最短路径或者最少跳数，而是最人化报义传输的可能性。因此，容迟 网络模型与无线传感器网络的应用环境非常相符，为传感器采集到的数据的传 输提供了解决方案， 1 3 相关工作 1 3 1 容迟网络的数据传输 容迟网络是一种间断联通的网络，所以容迟网络的协议需要能够接受频繁 的网络断开，同时整个网络范围内可能存在不同类型的协议，并且其间要进行 相互通信。容迟网络的提出最初是为了在星际网络i n t e r p l a n e t a r yi n t e r n e t 提供通讯 服务，此研究项目主要为了解决在深太空中，长延迟环境下的无线通信问题和 安置在极端环境下不同类型网络的相互连通f 6 ，7 1 。k e v i nf a l l 对容迟网络的结构 模型作了详细的阐述，提出了容迟网络协议的汇聚层：b u n d l e 层，该层位于容迟 网络体系结构的传输层以上，向应用层提供各种内容的服务，比如网内数据存 储转发、重传、网间互联等等。 近几年容迟网络技术和无线传感器网络逐渐融合。容迟的无线传感器网络 根据网络节点的移动性分成三类： 1 传感器节点固定的网络 此种具有容迟特性的传感器网络是静止不动的。由于传感器节点的电池容量 和天线传输距离的限制，节点不可能保持每时每刻都和其它节点连通。出于节 省能量的考虑，传感器节点的射频模块在大部分时间里处于关闭状态，这些长 期休眠的节点就构成了一个容迟的无线传感器网络。在嵌入式嘲络化传感中心 研制的无线地震传感阵列中，每个固定的传感器节点都有充裕的存储空间来保 存监测到的数据，并且通过中间节点进行可靠的数据传输 8 】。【9 】提出了一种可 以通过因特网下载数据的无线传感器网络，用于检测生活习性。s e n d t 项目 ( s e n s o rn e t w o r k i n gw i t hd e l a yt o l e r a n c e ) 【i 0 1 用于验证传感器网络用于水质监控 的可行性。容迟网络传感器网络：d t n s n 则提出了传感器网络协议栈和因特网 5 第1 章绪论 协议栈的h 联f 11 】。 2 具有可控移动节点的传感器网络 在此类1 x x j 络中，可移动的部分节点造成了其和第种州络工作方式的主要 区别：少数节点的移动能力用来支持网络的连通性。比如说，在【1 2 】1 1 - ，一类特 殊的称 - - - d a t am u l e 的移动节点被引入到网络中以在传感器布置非常稀疏的区域 内收集传感数据。每当这些d a t am u l e 移动到一个传感器节点附近，它接受传感 器节点的数据，暂时把这些数据存储在自身的非易失存储设备中，当d a t am u l e 移动到网络接入点n 寸，则将从不同传感器收集到的数据上传给用户，并清空自 身内存。这种利用特殊的移动节点来进行数据收集的机制只需要传感器节点进 行有限距离内的数据传输即可，充分节省了传感器节点自身的能量。 3 。具有移动的传感器节点的传感器蚓络 上述两类容迟的传感器网络中，主要的网络设备一一传感器节点都处于静 止状态。在第三类容迟传感器网络中，传感器节点本身即处于移动状态。z e b r a n e t 首次使用了移动的传感器节点实现野生动物追踪，获得了可供生物学研究的野 生动物迁徙数据 1 3 】。z e b r a n e t 项目旨在建立一个位置透明和能量透明的无线通 讯系统。一种基于历史信息的路由机制被用来完成数据交换。传感器节点被安 装在斑马的背上，随斑马群落一起移动。这些传感器节点在特定的时间段内打 开射频模块，搜寻周围的邻居节点，当一个节点发现了其邻居节点，如果该邻 居节点成功上传数据的可能性更大，该节点就将自身存储的传感数据发送给该 节点的邻居。这种简单的机制不能保证节点发现其地理位置上相邻的节点的成 功率，也不能保证任何程度的报文传输成功率。在【1 4 】【1 5 】中提出的被用来收集 鲸鱼的生理信息的s w i m ( s h a r e dw i r e l e s si n f o s t a t i o n ) 系统假设系统中所有的节 点的移动部是随机的，从而每个传感器节点与数据接入点相遇的机会都是相同 的。出于这种考虑，一个节点将自身的报文复制若干份，并分发给陆续与他相 遇的其他节点，以达到期望的传输成功率。在很多实际应用中，节点并不是随 机移动的，从而s w i m 并不能有效地工作。最差情形下，某些节点根本不可能与 数据接入点相遇，导致特定报文的传输失败。与此同时，基于网络编码的容迟 网络传输机制也相继被研究人员提出。一种基于擦除码e c ( e r a s u r ec o d i n g ) 的概 率| x x 络传输机制在【1 6 】中被提出。仿真的结果显示这种机制在网络负荷一定的前 提下达到了最差情况下的最优网络延迟( b e s tw o r s t c a s ed e l a yp e r f o r m a n c e ) 。然 6 第l 章绪论 而，这些研究仍然集中在网络的路由层，并假设m a c 层能够随时发现令| j 居节点， 而且旦两个节点成为邻届，所有需要的报义都可以有保障的完成。 1 3 2 容迟无线传感器网络的硬件结构 在容迟无线传感器网络中，节点的硬件结构一般是相同的，主要由四部分 组成：处理单元、数据采集单元、数据收发单元( 射频) 以及电源部分。数据 采集单元由个或多个传感器以及模数转换器a d c 组成。传感器将监测到的环 境信息转化成模拟信号，交予a d c 转变为数字信号交给处理单元。处理单元由 处理器和存储器组成，对于需要长期保存数据的节点，可能需要包含闪存；处 理器负责运行网络协议和应用程序。收发单元负责将需要交互通信的数据转换 成无线信号进行发送和接收，将多个节点连接成网络。典型容迟无线传感器网 络节点的硬件结构如图1 1 所示： 图1 。1 容迟无线传感器网络节点的硬件结构 1 3 3 容迟无线传感器网络的软件结构 网络内节点的软件一般是嵌入式系统或单片机系统，分为以下几个模块： 操作系统，驱动程序，应用程序，网络协议，数据采集和处理程序等。 其中，操作系统负责支持多任务和管理软件资源，应用程序根据网络的具 7 第1 章绪论 体背景不同而变化。网络协议是容迟传感器网络软件中最重要的部分，真接影 响到例络的性能，近年来，许多研究者在不同方向上对无线传感器网络的协议 进行了广泛的研究。 无线传感器节点的网络协议主要分为如下几层 1 ) 物理层 负责将m a c 层的数据转换为无线信号，调制并发送；从无线信道接收无线 信号，校验并转换为数据，向m a c 层传送。与传统的无线通信网络相比，有限 的能量限制了传感器节点的发送功率和距离。因此需要采用节能的解决方案， 如m i m o 技术，低阶调制技术、超宽带技术和射频标签技术等。 2 ) 数据链路层 数据链路层主要由媒体介质访问控制m a c 协议构成，主要负责解决信道的 多路传输，建立点到点的通信链路，节点间公平有效的共享通信媒介等问题。 3 ) 网络层 负责对传输层的数据进行路由，将数据多跳转发至基站。与传统网络不同， 传感器网络中，大量的数据流发生在节点与基站之间，数据的传递具有明确的 方向性，一般无需建立任意两个节点之间的路由。 4 ) 传输层 传输层的基本功能是从应用层接收数据，在必要时把它们划分成较小的单 元，组织数据流传递给网络层，确保信息可靠而有序的到达对方，并负责拥塞 控制和流量控制等。由于无线传感器网络资源和运算能力有限，一般不采用传 统的t c p 或u d p 协议，而采用更为简单节能的协议。 5 1 汇聚层 d t n 增加了汇聚层来把各种下层协议汇聚起来。在一个包含d t n 节点的区 域中，一些传输协议可能提供或不提供以下机制：可靠传递、连接( 有连接失 败提示) 、流量控制、拥塞控制和信息分界。因为捆绑转发功能假定下层具有可 靠的传递容量，且在形成保管传递时传递容量具有信息边界，所以缺乏这些特 性的传输协议可以得到扩展。不同的协议之间也可以通过汇聚层相互通信。d t n 的汇聚层和捆绑转发机制如下图所示，汇聚层位于无线传感器网络的传输层之 上，应用层之下，如图1 2 所示。 8 第1 章绪论 捆绑转发器 、 r 捆绑传输 f 捆绑应用jp c ! 、。 ( 1 j 圪，z ) r a n d o mw a y p o i n t 模型中一个节点的运动轨迹如图3 5 所示。 3 2 第3 章奔迟移动传感器网络的路巾和缓存臀理研究 图3 5 r a n d o mw a y p o i n t 模型节点运动轨迹 3 4 2r a n d o md i r e c t i o n 模型 随机方向模型和随机路点模型有一定的相似之处，不过其取消了路点的概 念，而使用( 0 。，3 6 0 。】之间的一个随机角度作为节点的运动方向，节点直沿这 个方向移动到限定2 - _ 维区域的边缘，进行一段时间的停留，再从( o 。，3 6 0 。】随机 选择一个方向继续运动周而复始。 r a n d o md i r e c t i o n 模型中一个节点的移动轨迹如图3 6 所示 3 3 第3 章容迟移动传感器| x x j 络的路【l i 和缓存箭理研究 图3 6 r a n d o md i r e c t i o n 模型节点运动轨迹 由图3 6 可以看出，实际上当节点移动到一个矩形区域的边缘时，其移动方 向只能在相应的18 0 0 范围内随机选择，若是刚好移动到矩形区域的角上，其移 动方向则只能在相应的9 0 。范围内选择。 3 4 第4 章系统实现与仿真结果 第4 章系统实现与仿真结果 4 1 多拷贝路由的模型分析 在这里首先进行多拷贝路由性能的理论分析。如图4 1 所示是一个简单的多 拷贝、转发模型。报文在源节点产生后，首先在蒯围节点间寻找复制的机会， 然后将报文复制给这些节点，使其成为转发节点。最后报文通过转发节点传送 到目的节点。 _ 一l 娘文复制 ，j： 、二兰= 二。 ， 图4 1 简单的多拷贝、转发模型图 图中虚线表示的是节点问的间歇性连接，在时间轴一l - ，这个连接过程是时 而可用，时而不可用的，如图4 2 ： 第4 章系统实现与仿真结果 型型l = l 删竺幽世呲型曼婴盐- 懈娥忡连豫 蚓42 问歇性连接的连续时间特点 如果节点间的间歇性连接时间间隔符合指数分布的规律，那么节点的连接 可以用马尔可夫过程来分析。【5t 中指出，r a n d o m w a y p o i n t ： l l r a n d o m d i r e c t i o n 运动模型的连接时间符合指数分布的规律。 为了便于分析，首先假定嘲络带宽是足够大的，两个节点的相遇过程足够 节点问完成报文传输。现在考虑网络中一个报文生成后的传输情况。由于节点 之间相遇的间隔时间符合指数分布，那么多拷贝路由的过程可以用一个连续时 间马尔可夫链( c t m c ) 来表示。此马尔可夫链包含有限个状态其中只有一个终 止态此终止态之前的状态转移表示了报文的复制或删除，不同的报文复制传 播策略决定了不同的状态转移概率。 图43 是一个典型的蹄由扩散过程的c t m c 过程： 五i 。而趴、一一面丽、 oo 、。t 固 o 图43 典型的路由扩散过程的c t m c 过程 圈中所示的容迟网络包含了n 个节点任意两个节点的连接间隔时间为 1 2 。状态d 表示报文被成功得传送到了目的节点，而其他的状态l ，2 j n 一1 则表示携带着报文副本的节点数。所以每一次报文的复制让携带报文副本的 节点数加一，既是状态向更高值的状态跳转。 第4 章系统实现与仿真结果 现存对本文用到的三种复制策略一路由扩散、源节点复制、二分法复制进行 分析，使用的模型均为连续时间马尔可夫链。设蹦络中节点的总数目为n ，报文 复制份数限制为j ，报文的产生速率为五，节点之间相遇的概率为z 。马尔可夫 链的状态集合可以表示为两部分： ， 中间态c i m 7和终止态d f = 1 在上述多项式中，m 表示报文历拥有f 份复制许可，系数q 表示携带芗份 报文复制许可的节点数目，表示报文的总复制份数限制，d 代表被传输报文的 成功到达。于是，至少携带一份报文副本的节点总数目可以表示为： c = yc ， 二- 一 o d 可以由前面任何一个中间态直接跳转，由于每个节点都有的几率- b 目的 节点直接相遇，所以中问态到终止态d 的转移概率为c t 。每个拥有超过一份报 文复制许可的节点，在于其他没有该报文的节点相遇时，都能够把报文复制给 对方，此报文的复制过程形成j ，一次中间态之间的状态转移。一个中问态可发 生的状态转移数目等于该状态下可以进行报文复制的节点的数目。由于可进行 ， 报文复制的节点由m i ( 1 f ，) 表示，所以其数目可以用c ，( 1 1 的报文复制许可的节点碰到一个没有该报文的节点时，复 制报文所导致的状态转移xj 】，可以由_ 卜式表示： x = c 1 耽1 + c f 聊i + + c t m 7 】厂= c 1 聊1 + + ( c 口+ 1 ) 聊口+ ( + 1 ) 聊6 + + ( c f 一1 ) m 7 + + c ，垅7 ， 其中l f ，q 1 ，1 c i ， i = 1 xj 】，的转移概率为： p 彳，= c f 。( n c 一1 ) x d 即报文直接传送成功的概率为： px d = , u c 对于三种不同的复制策略，其系数取值有所不同，如下表： 表4 1不同复制策略的系数取值 复制策略系数l口 b 路由扩散 n 一1z z 源节点复制 m i n ( j ，n 一1 ) 扣l1 二分法复制 m i n ( j ，n 一1 ) 【2 2 】 3 8 报文的平均传输延迟可以用下述方程来计算： 第4 章系统实现与仿真结果 p m m x ，。一p 舢尥。= 1 y x x d 其中x ，y 表示了两个不同的i | 间态，p x y 即是它们之问的转移概率。而 m 。r d ，m ，d 分别表示了从状态x 或y 到终止态d 的平均直接传输延迟。 4 2 系统实现 考虑到系统的应用背景是短距离的无线社会网络，个人手持通讯设备以及 传感器的传输距离有限，参与人数众多，然而个人的移动性比较随机，所以本 文采用r a n d o mw a y p o i n t 作为系统的移动模型，最为接近现实生活中的情况。文 中采用二分法复制的路由方法以及随机丢弃的缓存管理策略，证实其在这种环 境下能够提供比前人的方法更好的传输性能。 4 2 1 移动模型 随机路点，就是事先安排好一块区域，并且在这个区域范围内随机布下一 定数量的移动节点。下来，为每一个已经初始化好的移动节点决定一个移动目 的地，这个目的地的坐标也是在事先安排好的区域中随机选择的。所以我们事 先定义一个a 奉b 的矩形区域，那随机选择的x ，y 坐标分别服从【o ，a 】、【0 ，b 】之间 的均匀分布。然后，对每个移动节点再确定他走向目的地的速度，假设该节点 是匀速直线运动的，此速度也是服从 v l ，v 2 之间均匀分布的一个随机值。在一个 移动节点到达他的目的地后，停留一段时间，系统再为他产生下一个目的地， 节点不断运动直到指定时间。 4 2 2 相遇模型 每个节点的收发半径为r ，当两个节点的距离小于r 时，就判定两个节点为 相遇，相互之问可以进行报文的收发。近距离无线社会网络的带宽比较大，可 以认为不存在报文尚未发送完就断开连接的情况，所以每次节点的相遇都能按 照要求完成报文的传送。 3 9 第4 章系统实现与仿真结果 为了在程序中模拟节点的相遇，系统每秒记录下所有节点当前的位置 ( x f ，y i ) ( 1 f m ) ，其中m 为网络中节点的总数。 由此计算两个节点间的欧式距离d ( i ，) ： 广= _ d ( i ，) = 、( 誓一x ，) 2 + ( ”一y ，) 2 系统每秒钟计算每两个节点之间的距离，当d ( i ，) i 。 ，j? ，一：一二s ，： 2 04 06 08 0i 0 0 1 2 0 1 4 01 6 01 8 02 0 0 缓存容量 一单播路由 二分复制随即丢弃一4 v 二分复制随即丢弃一8一分复制随即丢弃1 6 路由扩散 圈47 不周路由方式和缓存容量下的平均传输延迟 第4 章系统实现与仿真结果 现在比较不同路由方式下的平均传输延迟，如图47 。如前文所述，单播路 由的延迟不随缓存容量的增加而变化。路由扩散方式在缓存容量较小时延迟最 夫，随着缓存容量增加，延迟显著减小。而二分法复制始终拥有较小的传输延 迟，在缓存容量超过8 0 后延迟的减小趋于平稳。复制许可n - 4 的平均延迟始终 高于n - 8 或1 6 的，说明未能充分利用转发缓存。复制许可n = g 的在缓存，j 、于 1 6 0 时，延迟小于n - 1 6 的，说明当缓存不够大时，太多的复制许可份数反而影 响总平均延迟。因此在缓存容量不是非常充裕时复制许可为8 份能够提供最 小的传输延迟。 蚓 捌 霹 不同缓存容量下高低优先级报文的平均延迟 2 0 4 0 6 0 8 01 0 01 2 01 4 01 6 01 8 02 0 0 缓存容量 + 高优先级报文 低优先级报文一- 所有报文 图4 8 不同优先级报文的平均延迟 最后在n = 8 的情况下比较一下高低两种优先级报文的平均延迟。由图48 可以看出，本文中针对不同优先级报文的处理方式保证了无论缓存容量充裕与 否，高优先级报文的平均延迟都明显小于低优先级报文在缓存容量较小的情 况下这种优势尤为明显。 加暑；鼬蚰加 第4 章系统实现与仿真结果 4 4 本章小结 本章主要对d t n 网络的多复制路南方法进行改进，充分利用有限的转发缓 存空间来保证传输成功率和延迟时问。使川控制复制份数的- 分法复制来进行 多复制路由，使用基于复制许可数和报文优先级的随机丢弃方式处理不矧报文 争抢有限转发缓存的矛盾，获得了更高的传输成功率和更低的平均传输延迟。 并且本文针对不同优先级报文采用不同的复制路由和缓存管理策略，在略微牺 牲低优先级报文传输性能的代价下，使高优先级报文的传输性能得到显著提升。 4 7 第5 章总结 5 1 本文的内容和成果 第5 章总结 容迟移动无线传感器网络的研究结果在流行性疾病预防，灾害预警，国防 和环保等各个方而都有明显的应用前景和潜在的产业经济价值，是当前交叉领 域研究的本文结合当前无线传感器网络和容迟网络的最新进展，立足于实际应 用，在国家自然科学基金项目的支持下，围绕协议栈设计，协议实现和协议仿 真，开展了容迟无线传感器网络的路由协议和缓存管理、服务质量的研究。取 得的主要成果如下： 对于路由协议，本文主要分析了容迟移动传感器网络和传统传感器网络的 主要区别，提出了在节点数目众多，连接变化频繁并且网络资源受限的环境下 的路由方法和节点缓存管理策略，以期保证复杂网络情况下的报文传输质量。 经过仿真证实这种方案在报文的传输成功率和平均延迟上都明显优于传统的路 由策略，并且对于不同重要性的报文，在服务质量分级上提供了支持。 5 2 未来工作展望 本文主要研究了容迟移动无线传感器网络的路由和缓存管理策略，由于时 间原因未能在实际节点上实现。在未来的工作中，计划将这些协议移植到实际 的传感器网络仿真平台中进行测试，促进协议的实用化。 本文所做的仿真是在节点连接带宽足够充裕的条件下进行的，如果节点带 宽受限，则在一次相遇过程中未必能完成所有的报文交换，此时对于路由方法 和缓存管理策略提出了新的要求。未来的工作中将会包含考虑节点带宽的研究。 4 9 参考文献 参考文献 【1 】y u c h e et s e n g , s h e n g - p ok u o ，e ta 1 2 0 0 3 l o c a t i o nt r a c k i n gi naw i r e l e s ss e n s o rn e t w o r k b ym o b i l ea g e n t sa n di t sd a t a f u s i o ns t r a t e g i e s c i np r o c e e d i n go ft h ei p s n ， l n c s ，2 6 3 4 ：6 2 5 6 41 。 【2 】b r o o k srr ，r a m a n a t h a n 只s a y e e dam a u g u s t2 0 0 3 d i s t r i b u t e dt a r g e tc l a s s i f i c a t i o na n d t r a c k i n gi ns e n s o rn e t w o r k s c i np r o c e e d i n go f t h ei e e e 9 1 ( 8 ) ：116 1 11 7 1 【3 】a k y i l d i z i f , s uw ：s a n k a r a s u b r a m a n i a mye ta 1 2 0 0 2 w i r e l e s ss e n s o rn e t w o r k s ：a s u r v e y j ，c o m p u t e rn e t w o r k s ，3 8 ( 4 ) ：3 9 3 4 2 2 【4 】t i l a ks ，a b u g h a z a l e hn b ，h e i n z e l m a nw 2 0 0 2 at a x o n o m yo fw i r e l e s sm i c r o s e n s o r n e t w o r km o d e l s m o b i l ec o m p u t i n ga n dc o m m u n i c a t i o n sr e v i e w , 1 ( 2 ) ：1 - 8 【5 】k f a l l ad e l a y - t o l e r a n tn e t w o r ka r c h i t e c t u r ef o rc h a l l e n g e di n t e r n e t s ，i np r o c e e d i n g s a c m s i g c o m m ，2 0 0 3 ，a u g u s t2 0 0 3 ，2 5 2 9 【6 】r d u r s t ，gm i l l e r , e t r a v i s ，“t c pe x t e n s i o n sf o rs p a c ec o m m u n i c a t i o n s ”，p r o c m o b i c o m 1 9 9 6 【7 】v c e 吒s b u r l e i g h ，a h o o k e ，l t o r g e r s o n ，r d u r s t ，k s c o t t ，k f a l l ，a n dh w e i s s ，“d e l a y t o l e r