（计算机系统结构专业论文）延迟容忍的移动传感网络路由算法研究.pdf

摘要 摘要 随着无线传感网络研究的不断深入，越来越多的应用要求网络中的节点部分 甚至全部具有移动性。例如，用于野生动物监控和追踪的无线传感网络、水下无 线传感网络等等。在移动传感网络中，由于节点的移动使得网络拓扑动态变化， 网络中没有稳定的端到端传输路径。而传统的有线网络或无线a dh o e 网络路由 算法都是基于网络中具有稳定的传输路径这一假设前提的，在移动传感网络中则 不能有效工作。因此，如何在网络拓扑动态变化的情况下，实现有效地端到端数 据传输是移动传感网络中首要解决的关键问题之一，具有重要的研究意义。 另一方面，近年来在无线网络领域出现了延迟容忍网络的新兴概念，泛指那 些没有稳定端到端传输路径的无线网络。其应用涵盖了太空网络、乡村网络、移 动传感网络、a dh o e 网络等等。目前，在延迟容忍网络路由算法方面已取得了 许多具有代表性的研究成果。由于移动传感网络正是一种典型的延迟容忍网络， 我们可以在延迟容忍网络体系结构下来研究移动传感网络的路由问题。因此，本 文在国家8 6 3 项目和自然科学基金项目的支持下，开展了延迟容忍的移动传感网 络路由算法研究。 具体的研究内容及创新点如下： 1 ) 本文首先考虑了一种半确定移动模型下的延迟容忍移动传感网络路由问 题。在这一网络模型中，我们假设节点根据一些先验知识或历史纪录已归纳出每 个节点在单位时间内访问各个网络区域的概率，在此基础上考虑以延迟最小为优 化目标的单副本报文传输路由问题，并提出了一个基于区域访问概率的延迟容忍 移动传感网络路由算法p r o a r e a 。 p r o a r e a 算法的主要创新之处在于：已有的基于概率的延迟容忍网络路由 算法认为节点的相遇概率越高则越可能尽快地将报文传输给对方，并利用这一思 想定性地指导路由选择，而p r o a r e a 算法则利用节点间的相遇概率，直接推 导出了节点间的期望传输延迟，并以此定量地指导路由选择。实验结果表明， p r o a r e a 算法比已有的算法在选择转发节点时更具有针对性，能够提高传输成 功率并降低传输延迟。 2 ) 本文还进一步地考虑了节点传输容量受限的延迟容忍移动传感网络路由 问题。假设网络中节点的传输容量有限，当报文传输的最优传输路径出现流量饱 和时，应该等待再传输还是策略性地选择其它路径进行传输，采用什么样的策略 才能使得总的传输延迟最小。本文则针对这一优化问题进行了研究，并提出了 p r o a r e a l c 算法。p r o a r e a l c 算法的主要创新之处在于：该算法将容量受 限的延迟容忍移动传感网络路由问题模型化为一个费用流问题，并利用最小费用 摘要 最大流算法成功地求解了该问题。实验结果表明，与相关算法相比， p r o a r e a l c 算法能够进一步地降低端到端数据传输延迟。 关键字：移动传感网络，无线传感网络，延迟容忍网络，容迟网络，路由算法 a b s t r a c t a st h es t u d yo fw i r e l e s ss e n s o rn e t w o r kg o e sd e e p e r , m o r ea n dm o r ea p p l i c a t i o n s r e q u i r et h en o d e si nn e t w o r kp a r t i a l l yo rt o t a l l yt ob em o b i l es u c ha st h ew i l d l i f e t r a c k e rn e t w o r k , u n d e r w a t e rs e n s o rn e t w o r k , e t c t h et o p o l o g yo fm o b i l es e n s o r n e t w o r k sd y n a m i c a l l yc h a n g e sd u et ot h em o b i l i t yo f n o d e s t h u s ，t h e r ea r en os t a b l e e n d - t o 。e n dd e l i v e r yp a t h si ns u c hn e t w o r k s a st h et r a d i t i o n a lr o u t i n ga l g o r i t h m si n w i r e dn e t w o r k so rw i r e l e s sa dh o cn e t w o r k sa r eb a s e do nt h ea s s u m p t i o nt h a tt h e r ea l e s t a b l ee n d - t o e n dd e l i v e r yp a t h s ，t h e yc a n n o tw o r kw e l li nm o b i l es e n s o rn e t w o r k s t h e r e f o r e ，h o wt oe f f i c i e n t l yd e l i v e rm e s s a g e si n t h en e t w o r kw i t hd y n a m i c a l t o p o l o g yi s as i g n i f i c a n tp r o b l e mt h a ts h o u l d p r i o rb es o l v e di nm o b i l es e n s o r n e t w o r k s o nt h eo t h e rh a n d , an o v e lc o n c e p t ，d e l a y - t o l e r a n tn e t w o r k , a r i s e si nw i r e l e s s n e t w o r kd o m a i n i tr e f e r st ot h o s en e t w o r k sw i t h o u ts t a b l ee n d t o e n dd e l i v e r yp a t h s ， w h i c hc o v e rt h eo u t e rs p a c en e t w o r k , v i l l a g en e t w o r k ，m o b i l es e n s o rn e t w o r k ， w i r e l e s sa dh o cn e t w o r k ，e t c b yf a r , t h e r eh a v eb e e nm a n y r e p r e s e n t a t i v er e s u l t si n t h er e s e a r c hf i e l do fd e l a y - t o l e r a n tn e t w o r kr o u t i n ga l g o r i t h m a sm o b i l es e n s o r n e t w o r kj u s ti sat y p i c a lc l a s so fd e l a y t o l e r a n tn e t w o r k s ，w ec a i ls t u d yt h er o u t i n g p r o b l e mo fm o b i l es e n s o rn e t w o r ku n d e rt h ed e l a y - t o l e r a n tn e t w o r ki n f r a s t r u c t u r e t h e r e f o r e ，w es t u d yt h er o u t i n gp r o b l e mi nd 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 s u n d e rt h es u p p o r to f n a t i o n a l8 6 3 p r o j e c ta n dn a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no f c h i n ap r o j e c t t h ec o n c r e t er e s e a r c hc o n t e n ta n dc r e a t i v ec o n t r i b u t i o n s a r ep r e s e n t e da s f o l l o w s 1 ) a sf i r s t , w ei n v e s t i g a t et h er o u t i n gp r o b l e mi nd e l a y - t o l e r a n tm o b i l es e n s o r n e t w o r ku n d e ras e m i - d e t e r m i n e dm o b i l i t ym o d e l i ns u c han e t w o r km o d e l ，w e a s s u m et h a tn o d e sh a v ed e r i v e do u tt h e i rv i s i t i n gp r o b a b i l i t i e st oe a c hn e t w o r kr r e ai n e v e r yt i m es l o tb a s e do ns o m ep r i o rk n o w l e d g eo rh i s t o r i c a lr e c o r d s t h e n , w es t u d y t h er o u t i n gp r o b l e mo fs i n g l e c o p ym e s s a g ed e l i v e r yi ns u c han e t w o r k ，a n dp r o p o s e a l l a r e a - v i s i t i n g - p r o b a b i l i t y b a s e dd 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 kr o u t i n g a l g o r i t h mp r o a r e as oa st oa c h i e v et h em i n i m u md e l i v e r yd e l a y t h em a i nc r e a t i v ec o n t r i b u t i o ni s i n t r o d u c e da sf o l l o w s t h e p r e v i o u s p r o b a b i l i t y - b a s e dd e l a y - t o l e r a n ta l g o r i t h m so n l yu t i l i z et h ei d e at h a tm o r et h em e e t i n g i i i p r o b a b i l i t y , m o r et h ep r o b a b i l i t yo fs u c c e s s f u ld e l i v e r yt oq u a l i t a t i v e l yg u i d et h e r o u t i n gs e l e c t i o n h o w e v e r , t h ep r o a r e aa l g o r i t h m d i r e c t l y d e r i v e so u tt h e e x p e c t e dd e l i v e r yd e l a yb e t w e e nn o d e sf r o mt h e i rm e e t i n gp r o b a b i l i t ya n du t i l i z e si t t oq u a n t i t a t i v e l y g u i d et h er o u t i n gs e l e c t i o n t h ee x p e r i m e n tr e s u l t ss h o wt h a t c o m p a r e dw i t ht h ep r e v i o u sa l g o r i t h m s ，t h ep r o h e ta l g o r i t h ms e l e c t st h er e l a y b e t t e rs ot h a ti t c a l li n c r e a s et h es u c c e s s f u ld e l i v e r yr a t ea n dr e d u c et h ed e l i v e r y d e l a y 2 ) f u r t h e r m o r e ，w ei n v e s t i g a t et h er o u t i n gp r o b l e mi nd e l a y t o l e r a n tm o b i l e s e n s o rn e t w o r kw i t hl i m i t e dt r a n s m i s s i o nc a p a c i t y s u p p o s et h a tt h et r a n s m i s s i o n c a p a c i 哆o fn o d e si nt h en e t w o r k w h e nt h ef l o wi nt h eo p t i m a ld e l i v e r yp a t hi s s a t u r a t e d ，w h a tas t r a t e g ys h o u l db ea d o p t e dt od e c r e a s et h et o t a ld e l i v e r yd e l a y , w a i t i n go rs e l e c t i n go t h e rd e l i v e r yp a t h ? t h i sp a p e rj u s ts t u d i e st h i sp r o b l e ma n d p r o p o s e st h ep r o a r e a l ca l g o r i t h m t h em a i nc r e a t i v ec o n t r i b u t i o ni st h a tt h i s a l g o r i t h mm o d e l i n gt h er o u t i n g p r o b l e mi nd 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 kw i t hl i m i t e dt r a n s m i s s i o nc a p a c i t ya s ac o s tf l o wp r o b l e m , a n du s et h e m i m m u m c o s tm a x i m u mf l o wa l g o r i t h mt o s u c c e s s f u l l ys o l v et h i sp r o b l e m t h ee x p e r i m e n tr e s u l t ss h o wt h a tc o m p a r e dw i t ht h e p r e v i o u sa l g o r i t h m s ，t h ep r o h e t - l ca l g o r i t h mc a l lr e d u c et h ee n d t o e n dd e l i v e r y d e l a yf u r t h e r k e y w o r d s ：m o b i l es e n s o rn 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 ，d e l a y t o l e r a n tn e t w o r k ， r o u t i n ga l g o r i t h m i v 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：橘掭奇签字日期： p o 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 函公开口保密( 年) 作者签名：扭堑壹 签字日期：! ：! ：! ：! 导师躲羔址生率 签字日期： 第一章绪论 第一章绪论 1 1 研究背景 1 1 1 移动传感网络概述 随着微电子技术、无线通信技术和计算技术的发展，在微小体积内集成了传 感器、数据处理单元和短程无线通信模块的传感器节点开始出现。无线传感网络 ( w i r e l e s ss e n s o r n e t w o r k s ，w s n s ) 就是由这些被布置在一定区域内的传感节点通 过协作自组织的方式组成的分布式网络。这种网络通过传感节点实时感知、收集、 处理布置区域周围环境或物体的信息，并将这些信息通过网络中的传感节点以多 跳中继的形式传递给用户终端，并接受来自用户的反馈。由于这种网络可以在没 有网络基础设施的情况下简单、快速的部署，而且不易摧毁，因而被广泛应用在 国防军事、环境监测、空间探索等领域，具有广阔的应用前景和研究价值，它被 美国时代周刊和m i t 技术评论为改变世界的十大技术之一和全球未来三大高科 技产业之一。 无线传感网络是由美国军方最早提出设想，美国国防部高级研究所计划署支 持研究的。随着大量项目的广泛展开，其应用逐渐由军事领域扩展到民用领域， 它也渐渐吸引了人们的注意力。目前，以加州大学b e r k e l y 分校、斯坦福大学等 世界著名大学和包括i n t e l 、c r o s s b o w 等著名企业纷纷对其基础理论和关键技术 展开深入的研究。在这方面，我国的中科院、上海微系统所、中科大、国防科大 等科研院校纷纷对其进行研究。总体而言，国内外的研究机构对这个领域的研究 均取得了不同程度的进展。 在研究过程中，人们提出了多种无线传感网络的体系结构，其中被广泛接 受的一种如图1 1 【1 】所示。从图中，我们可以看出无线传感网络系统一般由传感 节点、汇聚节点和任务管理节点组成，传感节点收集的数据被汇聚到汇聚节点， 然后经由互联网被用户接收到。传感节点一般通过随机抛洒的方式被布置在检测 区域，通过自组织的方式组成网络，它主要负责采集、处理周围环境或物体的信 息，同时，它还要对周围邻居节点发来的报文进行存储、路由或转发；汇聚节点 处于传感节点组成的网络和互联网或卫星之间，具有网关的功能，它主要负责两 者之间的通信，实现两种网络通信协议之间的转换；而任务管理节点直接与用户 通信，用户可以通过任务管理节点对传感网络进行了解、配置，以及发布一些检 测任务。 第一章绪论 图1 1 传感网络体系结构 人们除了提出传感网络的体系结构外，还提出了传感网络的协议栈，如图 1 2 t 2 】5 缶所示。图1 2 a 是早期的一个协议栈，从图中我们可以看到传感网络的协 议栈包含与i n t e r a c t 协议栈相对应的应用层、传输层等5 层，同时他还拥有任务 管理平台等3 个平台；后来，人们对这个协议栈进行了细化和改进，如图1 2 b 所示，从图中，我们可以看出时间同步和定位子层位置比较特殊，同时还有一部 分功能独立于协议栈之外，如网络管理部分。 应用层 传输层 嬲络层 数据链路层 物理层 图1 2 传感网络协议栈2 】 b ) 随着研究的不断深入，人们将传感网络应用到各种不同的场景中，其中，一 些场景要求节点具有移动性，如人们利用安放在动物身上的传感网络来研究草原 上生物种群活动特性【3 】、将节点安放在移动机器人上并通过移动节点来提高传感 网络的性能、以及应用于水下信息感知和收集的传感网络【4 】等等。在这些应用中， 由于环境的作用或载体的移动等原因使得网络中的节点部分甚至全部都具有不 同程度的移动性。通常，这一类的网络被称为移动传感网络。 移动传感网络是传统的静态传感网络的扩展，因而它首先具有传统传感网络 的一些基本特征，如： 1 ) 节点资源有限 2 第一章绪论 传感网络一般由几十、几百甚至上千个传感器组成，这就要求传感器成本低 廉，又因为其体积微小，所以节点通常携带能量十分有限的电池，这样就导致节 点硬件资源的有限性，如通信能力有限、计算和存储能力有限等。 2 ) 自组织网络 无线传感网络的应用环境通常是偏僻、人迹稀少的地方，在这些没有任何基 础设施的地方对节点的位置进行预先精确的设定是不可能的；同时在网络使用过 程中，由于节点能量耗尽、节点移动或环境的因素，原有的网络拓扑结构被破坏 掉，这样就需要传感节点具有自动组网的功能来适应拓扑结构的动态变化。 3 ) 多跳路由 节点受通信距离、节能或功率控制的限制，当节点无法与汇聚节点直接通信 时，需要由其他节点转发完成数据的传输，因此网络数据传输路由是多跳的。 除了具备传统静态传感网络的一些基本特征外，移动传感网络的一个最主要 特征就是： 4 ) 传感节点具有移动性 在不同的应用场景中，可能会由于网络部署环境的作用或节点载体的移动而 使得传感节点具有了移动性。在有些网络中，节点可以控制其载体的移动而能够 控制自身的移动行为。有些网络中，节点不能够控制其载体的移动，因而其移动 行为具有不确定性。 在移动传感网络中，由于节点具有不同程度的移动性，所以节点间的传输链 路时断时续，有时甚至没有链路的存在，而这恰恰是延迟容忍网络( d e l a yt o l e r a n t n e t w o r k ，d t n ) 的主要特性，所以我们可以在d t n 的体系结构下来研究移动传 感网络。 1 1 2 延迟容忍网络概述 d t n 网络是近年来无线网络领域新兴的一个研究热点，其概念最早由k e v i n f a l l 在著名国际会议s i g c o m m 2 0 0 3 上提出来的【5 1 ，它泛指节点之间没有稳定的 端到端的数据传输链路，甚至大部分时间处于中断状态而只能进行间歇性通信的 网络( 由此我们可以看出移动传感网络是d t n 网络的一部分，我们可以称它为 延迟容忍的移动传感网络) 。d t n 网络的应用范围很广，涵盖了许多i n t e m e t 之 外的通信网络，包括外太空星际间的通信网络、乡村网络、战争网络、野生动物 监控与追踪网络、移动a dh o e 网络等【6 】。延迟容忍网络的提出就是为这些延迟 过大、传输中断和双向数据传输非对称的网络提供一定品质的服务，它被认为是 实现“无线不在的网络 的一项关键技术，具有重要的研究意义。 自从k e v i nf a l l 于2 0 0 3 在s i g c o m m 中发表论文“ad e l a y t o l e r a n tn e t w o r k a 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 m e t s ，【5 1 ，提出d t n 网络的概念并定义了d t n 网 3 络基本的架构和运作情形后，又于s i g c o m m2 0 0 4 发表了一篇关于d t n 路由 的论文n 】。从此以后，有关d t n 网络的研究吸引了大家的关注，在世界范围内 都处于蓬勃发展中，现在有许多知名大学和研究机构或像m i c r o s o f t 、i n | e l 等知 名企业都有学者在研究d t n 。目前许多国际研讨会也以d t n 为主题，像网络方 面的顶级国际会议s i g c o m m 就连续于2 0 0 5 、2 0 0 6 两年为d t n 专门开设 w o r k s h o p 为各地研究者提供交流的平台；此外，d t n 方面的论文在一些网络 方面的国际性会议上如i n f o c o m 、m o b i h o c 、m o b i c o m 上也频繁出现。晟 近，国际互联网研究任务组( i n t m e t r e s e a r c h t a s k f o r c e ，i r t f ) 还专门成立了 延迟容忍网络研究组( d e l a y t o l e r a n tn e t w o r k i n gr e s e a r c hg r o u p ，d t n r o ) 来 对d i n 进行研究。 1 12 1d t n 的体系结构 2 0 0 7 年4 月，d t n r o 提出了一个d t n 体系结构吼我们知道，传统的 i n t e r a c t 的体系结构主要包括物理层、数据链路层、网络层、传输层和应用层。 d i n 体系结构则在此基础上，进一步地在应用层和传输层之间引入了一个所谓 的“捆绑层( b u n d l el a y e r ) ”( 如图l3 所示) 。这一层的协议在不同区域网络的边 界上连接不同的协议栈，提供一个通用的应用层网关基础设施，并且拥有存储转 发的功能；这一点类似于i n t e m e t 网关的功能。 传输层( t c p ) 网络层( i p ) 数据链路层 物理层 应用层 传输层( t c p ) 网络层( i p ) 数据链路层 物理层 i n t e m e t 体系分层d t n 体系分层 图1 3 i n t e m e t 与d t n 体系结构对比 由于引入了b u n d l e 层，d t n 网络的传输机制也有一些自身的特征。 i ) 一般而言，一个d i n 网络可以由多个区域网络组成，这些区域网络可 阻是i n t e m e t 网、公交系统网、卫星网络或传感器网络等。每个区域网 络可以有各自的网络协议，不同的区域网络之间不能通信，而d t n 网 络则可以通过处于两个不同区域网络之间的d t n 网关来运行b u n d l e 层 4 第一章绪论 协议，实现两个异构网络之间的通信，它采用可靠的消息路由代替了“尽 力而为”的p 分组交换，同时它也进行安全检查，以确保可以进行消息 转发。 2 ) 在d t n 网络中，两个节点之间不存在稳定的端到端数据传输链路，甚 至大部分时间处于中断状态而只能进行间歇性通信，一般而言，可以分 为如下几种情形1 9 ： 持续连接：节点之间的链路一直处于连通状态，如“一直在线”的i n t e r a c t 接入。 按需连接：节点间的链路根据需要在某个特定时间处于连通状态，如从 拨号者角度来看的拨号连接。 间歇性可预定连接：节点间的链路在某个特定时间和某个特定区域处于 连通状态，如近地卫星链路。 间歇性偶然连接：节点间链路只有在偶然连通时才可以使用。如移动的 红外设备或蓝牙设备。 间歇可预测性连接：不能预定，但可以根据以前的观察或其他历史信息 来预测链路连接的可能时间。 3 ) d t n 网络中的消息传输主要采取存储转发的机制。d t n 网络中的节点 主要可分为两种：p 节点( p e r s i s t e n t ) 和n p 节点( n op e r s i s t e n t ) 节点。其 中，p 节点可以拥有足够大的空间，所以可以保管一些传输数据，以后 再进行传输( 即“保管( c u s t o d y ) ”传输) ，而n p 节点没有足够大的空间， 所以它不能提供保管传输服务。如图1 4 所示，当d t n 网络路由消息时， 会先将数据传到p 节点，并存放在其b u n d l e 层的b u f f e r 中，然后由b u f f e r 层通过重传的方式负责消息的可靠传递。由于d t n 在b u n d l e 层提供了 保管转发通告、收到回复、外发消息通告、递送优先级、认证等六类分 级( c l a s so fs e r v i c e ，c o s ) 【1 0 】服务。因而，通过保管传输的方式，可以 在d t n 网络中实现一定程度的可靠传输。 1 1 2 2d t n 网络应用 d t n 网络的应用范围很广，涵盖了i n t e m e t 之外的许多通讯网络，如星际网 络、乡村网络、战争网络、野生动物监控与追踪网络、便携无线设备交换网络等 等【6 j ，下面我们对这些d t n 网络的应用领域进行一些介绍： 1 ) 星际网络【l l 1 2 】 星际网络是指外太空中星球间的数据传输，如短期目标的卫星传输和长期目 标的行星间传输。由于星际网络也拥有d t n 网络延迟比较长和链路不时中断的 特性，所以d t n 的确也十分适合在外太空星际网络中传输数据。美国n a s a 所 5 第一章绪论 应用层 捆绑层 传输层 网络层 链路层 物理层 源dtn传输 目的 d t n 主机d t n 路由d t n 路由d t n 主机 区域l ( 。c m p 网络) l 1 五荔石爵高鬲磊鬲；一 【。j一 图1 4d t n 网络数据传输机制 资助的i n t e r p l a n e t a r yi n t e m e tp r o j e c t 就是这方面的一个项卧1 1 ，1 2 1 ，而且美国的 i n f m e r ad t n 光网络部掣1 3 j 在近期已部署完成。 2 ) 乡村网络【1 4 - 1 7 】 在一些发展中国家或者偏远地区，网络的基础设施通常不完善而不能接入 i n t e m e t ，所以这些地方的人们上网不方便，甚至根本不能上网。在这种情况下， d t n 网络则可以为这些地区提供价格相对便宜而且具有一定质量水平的网络服 务。目前，在这方面已知的应用有为芬兰北部的游牧民族提供信息服务的s a a m i n e t w o r kc o n n e c t i v i t y 1 6 1 和b e r k e l e y 和i n t e l 研究院正在联合开发的t i e r 项卧1 7 1 。 3 ) 战争网络【l 刚 与a d h o c 网络相比，d t n 网络更能满足战争型的网络所需要的容忍不可靠 性、随机性、某种程度的延迟的需求，所以它可能更适合运用在战争型的网络中。 目前，美国陆军在这方面进行了一些研究，他在每个战场中的士兵身上安装了传 感器，从而形成了单兵作战系统来指导士兵在战场上的行动。 4 ) 野生动物监控【3 ，4 】 由于d t n 网络容忍传输链路中断，因而被应用于野生动物监控与追踪。在 普林斯顿设计的z e b r a n e tp r o j e c t 3 】中，研究人员在非洲草原的每只斑马的脖子上 戴了一个低功率省电而且可以互传资料的传感器，借此来研究它们的活动范围和 生活习性，而且研究人员会定期开车携带移动基站穿越斑马活动区域进行数据收 集。在监视海洋鲸鱼的水下d t n 网络项目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 m o d e l ) 【4 】中，每头鲸鱼通过嵌入在它们身上的特殊t a g 来进行数据传输，并通 过鲸鱼的移动将数据传输到在水面浮标或飞过的海鸟身上携带的基站。 5 ) 便携无线设备交换网络 6 第一章绪论 随着手机、p d a 等手持设备的大量普及，利用这些手持设备进行组网进行 数据交换和提供网络服务逐渐成为可能。这方面的实际应用有剑桥大学和i n t e l 研究院提出的p s n ( p o c k e ts w i t c h e dn e t w o r k ) f 1 9 】项目，由人随身携带的大量手持设 备形成d t n 网络，每个设备节点可以利用一些基础设备进入i n t e m e t 或相互之 间行进通信。 6 ) 车载网络 在现代社会中，随着具有短距离无线通信能力车辆的增多和车辆在城市中分 布的不均匀，人们可以组建一个移动车载网络来进行交通流量监控、路况监测、 交通事故预警等。m i t 开发的基于车辆传感器的信息收集和发布系统c a r t e l 2 0 】 可以提供路况收集、车辆诊断和路线导航等服务，人们在每台车辆上安装了一个 嵌入式c a r t e l 节点用来收集与车辆或交通相关的各种信息，当两台车辆相遇时， 它们就可以互相传递数据或进行i n t e m e t 访问。 从上面我们可以看出d t n 的应用与实际应用场景有关，它不仅与传统 i n t e m e t 差异较大，而且相互之间也千差万别。d t n 网络将各种不同的网络纳入 统一的框架，建立了一个全新的体系，拥有广阔的应用前景。 1 2 论文的选题意义 由于移动传感网络具有d t n 网络的特点网络中不存在稳定的端到端数 据传输链路，本质上就是一种典型的d t n 网络。为了充分借鉴d t n 网络的研究 成果，我们在d t n 体系结构下来研究移动传感网络。 在d t n 体系结构下来研究移动传感网络，如何进行实现高效的端到端数据 传输，即路由问题是延迟容忍传感网络首要解决的之一。在d t n 体系结构下， 网络节点由于移动而使得节点间没有稳定的端到端传输路径，甚至可能在任意时 刻都没有一条传输通路。而传统的有线网络或无线a dh o e 网络路由算法都是基 于“网络具有问题的传输路径”这一基本假设前提的，在没有稳定传输路径的延迟 容忍传感网络中均不能有效工作。因而，非常有必要针对延迟容忍传感网络研发 具有延迟容忍特性的路由算法。在大多数的实际应用中，延迟容忍传感网络拓扑 动态变化，而且其变化规律还具有时变性和不确定性，从而使得其路由问题极具 挑战性。因此，研究并提出高效的延迟容忍传感网络路由算法具有重要的意义。 事实上，在d t n 网络研究领域，针对不同的网络模型已经研究并提出了许 多的路由算法。其中一类具有影响力的算法则是假设节点已知自身和其它节点的 相遇概率，并认为“如果一个节点与目标节点的相遇概率越高，则越可能成功地 将报文传输给该目标节点”。然后，利用这一信息来指导其路由选择。这些算法 根据节点间的相遇概率，以端到端传输延迟为优化目标，采用了一种定性的路由 7 第一章绪论 决策，性能非常有限。本文则在此基础上，通过理论分析和计算提出了一个基于 定量指导的路由决策算法。另外，我们还假设了网络传输容量受限，进一步地改 进了算法。与已有的算法相比，性能更优，具有较好的理论意义和实际应用价值。 1 3 论文的主要贡献和结构 在后续章节中，本文先详细介绍了研究过程中常用的节点移动模型和d t n 网络中与本文相关的路由算法，并指出了它们的缺陷，在此基础上提出了一个基 于区域访问概率的路由算法_ p r o 趾迮a 算法，能够直接计算出节点间传输的 期望延迟，对路由决策进行定量指导，具有更好的效果；然后，我们在此基础上 进行进一步的研究，将这个算法推广到节点间传输链路有传输容量限制的场景 中，提出了相应的p r o a r e a l c 算法。本文具体贡献如下： 第一，在p r o a r e a 算法中，我们通过各节点访问区域单元的概率，计算 出了节点间的相遇概率，并进一步地推导出任意两节点间进行端到端数据传输的 期望延迟，从而辅助路由决策。由于我们能够计算出节点数据传输期望延迟的具 体值，因而，能够为路由决策提供一个定量的指导，有助于实现更为精确的面向 优化目标的路由选择。我们还通过仿真实验对p r o a r e a 算法与已有的算法， 包括p r o h e t 算法和e p i d e m i c 算法进行了性能比较，实验结果表明p r o a r e a 算法在选择转发节点时更具有针对性，能够提高数据传输的成功率并降低数据传 输延迟。 第二，我们在p r o a r e a 算法的基础上，进一步地考虑在节点间链路有传 输容量限制的条件下，采用什么样的策略才能使得总的传输延迟最小的最优化问 题。我们首先将该问题模型化为一个费用流问题，然后利用最小费用最大流算法 提出了p r o a r e a l c 算法，这样可以使在转发报文时最优路径不可得的情况通 过次优路径转发或继续等待，这样可以降低延迟。我们还通过仿真实验对 p r o a r e a l c 算法与已有的算法进行了性能比较，实验结果表明p r o a r e a - l c 算法在数据传输延迟方便有所降低，并提高了数据传输的成功率。 本文的组织结构如下： 第一章主要介绍了移动传感网络的相关概念和d t n 的研究背景和其体系结 构，指出移动传感网络具有d t n 网络的特点，所以我们可以在d t n 体系下研究 移动传感网络的路由问题。 第二章介绍d t n 路由问题的研究现状。这一章先指出d t n 路由算法的性能 评价标准，然后介绍了常见的节点移动模型，最后根据d t n 算法的分类分别对 其代表性路由算法进行了描述和分析，以此作为后续章节的背景知识。 第三章介绍了针对基于区域单元( c e l l ) 的移动模型，我们提出的p r o a r e a 8 第一章绪论 算法。这一章介绍了我们所使用的节点移动模型，并详细描述了p r o a r e a 算 法的每一个步骤，中间在必要的地方举例进行说明，最后我们还将算法与其它的 算法进行了性能上的比较。 第四章在针对c e l l 移动模型进行更深一步的研究，考虑在节点间链路容量 有限的情况下采用什么样的策略才能使得总的传输延迟最小的最优化问题，我们 将它转化为一个流问题，并根据相关的流算法提出了p r o a r e a l c 算法，仿真 结果表明p r o a r e a l c 算法可以在相应的场景下比其他相关的算法有更好的性 能。 第五章对全文进行总结，指出进一步研究的方向。 9 招二章延迟容忍网络路由算法 第二章延迟容忍网络路由算法 2l 概述 d t n 网络作为一个挑战性的网络，是近年来无线网络研究领域中的一个热 点。在这种网络中，节点间只能间歇性通信，链路甚至大部分时间处于中断状态， 因此节点间不存在稳定的端到端数据传输路径。它可以为具有延迟过大、数据包 丢失，可能暂时性没有连接等特点的传统i n t e n l e t 之外的网络( 如星际网络、乡 村网络、战争网络等 6 1 ) 提供一定品质的网络服务，具有重要的研究意义。 d t n 网络中，节点通信链路时断时续，具有时变性，传统l r t t e m e t 或无线网 络中关于“节点之间存在稳定的端到端通信链路”这一基本假设在d t n 中却不成 立。因而，传统网络的路由算法已经不再适用于d t n 网络。在d t n 网络中，数 据报文往往采用“存储一携带转发( s t o r e c a r r y f o r w a r d i n g ) ”的方式进行传输， 即源节点或中间节点可以先将数据报文缓存于本地，当它与下跳节点之间出现 通信时机时，则将报文传输给下一跳节点，然后由下一跳节点继续携带该报文， 依次传输直至报文最终转发到目标节点。 i e t r 图2 1d t n 网络报文传输实例 例如，在如图21 所示的一个仅有三个节点的简单延迟容忍网络中，节点1 想向节点3 传递数据信息，但两个节点间不存在稳定的端到端的数据传输路径， 它们之间的报文传输就是以“存储携带一转发”的方式实现的。在t = 0 时刻，在 任意两个节点间，一个节点处于另一个节点的传输半径之外，所以它们不能互相 进行数据传输，节点l 就携带存储在其缓存的数据进行继续移动。情形1 中，在 t = 1 时刻，节点l 移动到节点3 的传输半径内，这时两节点之间可以进行数据 第二章延迟容忍网络路由算法 传输，节点l 就将数据传输到节点3 中。情形2 中，t = l 时刻，节点1 和节点 2 移动到对方的传输半径内，节点1 将数据转发给节点2 ，节点2 就携带这些数 据继续移动；t = 2 时刻，节点2 和节点3 互相在对方的传输半径内，它们可以 互相传递数据，节点2 就将数据传递给节点3 。图中，两个节点处于同一个阴影 区域中表明两个节点互相在对方的传输半径内。 由于在网络研究领域，路由问题始终是一个核心问题，d t n 路由在d t n 网 络研究工作中具有十分重要的地位。而且自从i r t f 成立d t n r g 以来，人们对 d t n 网络的研究不断深入，加上在许多实际应用项刚6 】的支持下，d t n 网络的 研究工作进展迅速，取得了丰硕的成果，人们在d t n 路由方面也提出了许许多 多不同的具有理论研究意义的算法。本章对这些算法进行了描述和分析，具体结 构如下：第2 节介绍了d t n 路由算法的性能评价标准，第3 节介绍了d t n 研究 工作中用到的节点移动模型，第4 节介绍了d t n 算法的分类标准并根据分类标 准介绍一些代表性算法，第5 节对本章进行了总结。 2 2d t n 路由算法的性能评价标准 一般而言，为了在较短的时间内得到较多的数据信息或为了满足应用场景的 要求，路由算法以数据成功传输