（计算机科学与技术专业论文）wsans中sensor与actor协调机制的研究.pdf

国防科学技术大学研究生院工学硕士学位论文 摘要 无线传感器反应网络( w s a n s ) 是由大量资源有限的传感节点和少数资源较 丰富的反应节点组成的，用于执行分布式传感和反应任务的一种新型网络模型。 其中，传感节点用于收集物理环境中的相关信息，反应节点用于接收和处理这些 信息，并对物理环境执行适当的反应这种网络系统被广泛地用于战场监视、小 气候控制、化学攻击检测、工业控制、家庭自动化及环境监控等许多领域。 为了有效地完成分布式传感反应任务，在传感节点之间，传感节点与反应节 点之间以及反应节点之间进行有效的协调是非常有必要的。本文主要研究了传感 节点与反应节点之间的协调选择问题。本文首先提出一种基于跳数受限和能量有 效的单个反应节点的协调选择算法船m e c t ，并给出了h b m e c t 的最优解决 方案的整数线性规划( 肼) 描述。在此基础上，本文具体给出了一个肿m e c t 的分布式近似解决算法，该算法在改良的地理分簇策略的基础上，形成了一棵以 单个反应节点为根的最小代价树，较好地解决了传感节点与单个反应节点之间的 协调选择问题。 在传感节点与单个反应节点协调选择的研究基础上，我们进一步研究了多个 反应节点的协调情况，并提出了一种分布式的跳数有限且能耗自适应的选择算法 d h b a e c c t ( d i s t r i b u t e dh o p - b o u n d e da n da d a p t i v ee n e r g yc o n s u m p t i o nc o s t t r e e ) ，同时给出了相应的最优解决方案的i l p 描述。d h b a e c c t 算法的目标是 要在事件区域中的源节点与作为数据接收者的反应节点问构造若干棵跳数有限且 能耗自适应用的数据聚合树。为此，本文提出了d h b a e c c t 的一个分布式近似算 法，该算法大大地减少了数据包从传感节点到目标反应节点的传输距离总和及数 据包传输能耗的总和，为传感节点与多个反应节点间的协调选择问题提供了一种 新的解决思路。 在算法性能评估部分，我们将h b m e c t 和d 衄a e c c t 的两个分布式近似算 法分别与m e c t 、m p c t 和传统的贪婪转发路由选择算法进行了性能对比，并给 出了相关的结果分析。 主题词：无线传感反应网络能量有效跳数受限最小代价树 第i 页 国防科学技术大学研究生院工学硕士学位论文 a b s t r a c t w i r e l e s ss e n s o ra n da c t o rn e t w o r k s ( w s a n s ) a r ec o m p o s e do fal a r g en u m b e ro f r e s o u r c e - l i m i t e ds e n s o r sa n das m a l ln u m b e ro fr e s o u r c e - r i c ha c t o r st op e r f o r m d i s t r i b u t e ds e n s i n ga n da c t i n gt a s k s s e n s o r sg a t h e ri n f o r m a t i o na b o u tt h ep h y s i c a l p h e n o m e n o n ，w h i l ea c t o r st a k ed e c i s i o n sa n d t h e np e r f o r ma p p r o p r i a t ea c t i o n su p o nt h e e n v i r o n m e n t t h e r ea r em a n yp o t e n t i a la p p l i c a t i o n so fw s a n s ，s u c ha sb a t t l e f i e l d s u r v e i l l a n c ea n dm i c r o c l i m a t ec o n t r o li nb u i l d i n g s ，n u c l e a r ，b i o l o g i c a la n dc h e m i c a l a t t a c kd e t e c t i o n ，i n d u s t r i a lc o n t r o l ，h o m ea u t o m a t i o na n de n v i r o n m e n t a lm o n i t o r i n g t oa c c o m p l i s he f f e c t i v e s e n s i n g a n d a c t i n g t a s k s e m c i e n tc o o r d i n a t i o n m e c h a n i s m so fs e n s o r - s e n s o r , s e n s o r - a c t o ra n da c t o r - a c t o ra r er e q u i r e d i nt h i sp a p e r , a s i n g l e a c t o rs e l e c t i o na l g o r i t h m sf o rw s a n sa r oa d d r e s s e df r o mh o p sa n de n e r g y c o n s t r a i n t s t 1 l cc o r r e s p o n d i n go p t i m a ls o l u t i o n 壬m 脏c t ( h o p - b o u n da n dm i n i m u m e n e r g yc o s tt r e e ) i sd e t e r m i n e db yi n t e g e rl i n e a rp r o g r a m m i n g ( i l p ) a n dt h e na d i s t r i b u t e d a p p r o x i m a t ea l g o r i t h mo fh b m e c ti sp r o v i d e d f o rc o o r d i n a t i o no f s e n s o r s - a c t o rb a s e do na ni m p r o v e dg e o g r a p h i c a lc l u s t e r i n gp a r a d i g mi nw h i c hc l u s t e r f o r m a t i o ni sf o r m e db ys o m em i n i m u mc o s tt r e e o nt h eb a s i so f s i n g l e - a c t o rc o o r d i n a t i o n ，w ec o n s i d e rt h es i t u a t i o no fm u l t i a c t o r s s e l e c t i o n b yr e c o m p u t i n gt h ee n e r g yc o n s u m p t i o nt oe v e r ya c t o ro ne v e r yr e l a ys e n s o r n o d e ，w ed e c i d ear i g h tn e x tr e l a yn o d ea n daa p p r o p r i a t en e wt a r g e ta c t o ra st h er o o to f m c t ( m i n i m u mc o s tt r e e ) w e c a l l t h i s a l g o r i t h md h b a e c c t r 】) i s t r i b u t e d h o p b o u n d e d a n d a d a p t i v ee n e r g yc o n s u m p t i o nc o s t t h e la n d g i v et h e c o r r e s p o n d i n go p t i m a ls o l u t i o nb yi l p a n dad i s t r i b u t e da p p r o x i m a t ea l g o r i t h mo f d h b a m e c ti sp r o v i d e df o rc o o r d i n a t i o no f s e m o r s a c t o r s i nt h ep e r f o r m a n c ee v a l u a t i o n 。t h ea p p r o x i m a t ea l g o r i t h mo fh b 厄c ti s c o m p a r e dw i t hm e e t ( m i n i m u me n e r g yc o s tt r e e ) a n dm p c t ( m i n i m u mp a t hc o s t t r e e ) a l g o r i t h m s a tt h es n m et i m e ，t h ea p p r o x i m a ta l g o r i t h mo fd i - i b a c c ti s c o m p a r e dw i t ht h et r a d i t i o n a lg f r ( g r e e d yf o r w a r d i n gr o u t i n g ) a l g o r i t h m n ms i m p l e a n a l y s i so f t w oa l g o r i t h m si sg i v ea tl a s t k e yw o r d s ：w i r e l e s ss e n s o ra n da c t o rn e t w o r k se n e r g ye f f i c i e n c y h o p b o u n d e d m i n i m u mc o s tt r e e 第i i 页 国防科学技术大学研究生院工学硕士学位论文 图2 1 图2 2 图2 3 图3 1 图3 2 图4 1 图4 2 图4 3 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图目录 w s a n s 的物理结构 a u t o m a t e d ( a ) 与s e m i a u t o m a t e d ( b ) w s a n s 的协议栈 单个反应节点的选择 4 5 6 1 0 分布式近似算法中的下一跳节点选择示意图2 3 多个反应节点的选择2 5 ( 6 个a c t o r ，1 0 0 个s e n s o r ) 分布式近似算法形成的最小代价树3 7 能耗自适应的目标节点选择算法。3 9 仿真场景示意图( 5 0 个s e n s o r ，4 个a c t o r ) 4 2 传感节点密度分析图 有限跳数阙值h 分析图。 仿真环境示意图( 1 0 0 个s e n s o r ，8 个a c t o r ) a c t o rn u m b e rv s a v e r a g et o t a le n e r g yo f m c t a c t o r sv s a v e r a g et o t a ld i s t a n c eo f m c t 4 3 4 4 4 5 4 7 4 8 第1 i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：里丛! 主塑! ! ! 墨缝! ! ! 盐遇狃剑鲤盈究 学位论文作者签名： 籀鱼 日期： 2 叩6 年罗月j 予日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：竖垡! 生! ! 堕! ! 蔓丝! ! ! 盐遇狃型煎婴究 学位论文作者签名： 绉鸯 作者指导教师签名 日期：2 耐年少月露日 日期：参n 多年7 月节日 国防科学技术大学研究生院工学硕士学位论文 第一章绪论 i i 课题背景 传感器技术、微机电系统，现代网络和无线通信等技术的进步，使无线传感 器网络( 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 ) 广泛地应用于军事国防、工农业控制、 城市管理、环境监测、抢险救灾等诸多领域。目前，对无线传感器网络的研究已 有近十年的历史，面对从w s n s 衍生出来的无线传感反应网络( w i r e l e s ss e n s o ra n d a c t o rn e t w o r k s ，w s a n s ) 的研究最近才开始。w s a n s 涉及到一组经无线介质连 接到一起的传感节点( s e n s o r s ) 和反应节点( a c t o r s ) ，前者从环境中收集数据， 后者则根据收集到的数据执行合适的操作【l 】这种将反应装置引进w s n s 所形成的 w s a n s ，极大地增强了无线传感器网络的应用能力和范围。例如，在发生火灾时， 传感节点将火灾的确切地点和强度转发给洒水节点，以便在火灾蔓延不可控制前 扑灭火源。总的来说，w s a n s 可以看作w s n s 与a d h o c 网络的结合，它可以是一 个完整的系统，如战场监视系统、核生化攻击检测系统“1 ，家庭自动化系统口1 和 环境监测系统等。 1 2w s a n s 的提出及其特点 w s a n s 是w s n s 的延伸，是一种新型网络模型。在w s a n s 中，执行数据收 集和协调的中央组织不是必须的与传统w s n s 中只有传感节点与汇聚节点( s i n k ) 通信相比，w s a n s 中除了传感节点与反应节点通信，还有反应节点与反应节点通 信的相关问题。w s a n s 中通信所实现的高效操作，都是通过传感节点和反应节点 之间协调来实现的。 与传统的w s n s 相比，w s a n s 具有如下特点： ( 1 ) 节点的异构性：传感反应网络中存在两类节点：传感节点：用来被动 检测环境，具有有限能量，处理能力和通信能力都比较弱。反应节点：用来主 动对外部环境实施操作的节点，具有更高的处理和通信能力；它在能量资源上有 更少的约束( 更长的电池寿命或者恒定电源) 。而在w s n s 中一般只有一种类型 的节点。 ( 2 ) 实时的要求：w s a n s 的一个主要目标就是减少检测和反应之间的通信 延迟，以便反应节点快速做出反应。例如，在火灾应用中，事件区域周围的反应 节点需要快速做出反应，并且传感数据在做出反应时必须是有效的。而在w s n s 中，汇聚节点一般距离事件区的传感节点比较远，从传感节点检测到数据到汇聚 第l 页 国防科学技术大学研究生院工学硕士学位论文 节点接收到数据需要很长的时间，实现实时需求难度更大。 ( 3 ) 部署要求不同：w s a n s 中不同种类节点的部署是不同的为了研究某 种现象，传感节点一般部署比较稠密，可能达到成百上千的数量级；由于操作任 务对覆盖和交互方式要求不同，反应节点部署比较稀疏。在w s n s 中，只有一种 类型的节点，不存在这种问题。 ( 4 ) 多种协调：在w s n s 中，主要的通信问题在于传感节点和汇聚节点之间； 在w s a n s 中，除了传感节点与反应节点之间通信问题外，大多数情况下还需要反 应节点相互通信，以实现对外面环境的实时精确的反应。 ( 5 ) 移动性：在w s a n s 中，节点，特别是反应节点，可能是移动的。例如， 分布式机器人应用中的机器人、战场中配备数字收发器的战士通常是移动的。在 w s n s 中，一般考虑节点是静止的，或微小移动。 1 3w s a n s 的特点所面临的研究问题 w s a n s 是w s n s 的延伸，是一种新型网络模型。在w s a n s 中，执行数据收 集和协调的中央组织不是必须的。与传统w s n s 中只有传感节点与汇聚节点( s i n k ) 通信相比，w s a n s 中除了传感节点与反应节点通信，还有反应节点与反应节点通 信的相关问题。w s a n s 中通信所实现的高效操作，都是通过传感节点和反应节点 之间协调来实现的。 w s a n s 是最近才开始提出来的新型网络模型，由于网络中存在s e n s o r 和a c t o r 两种不同类型的节点，从而产生了大量的协调和通信问题。其中最主要的一个问 题就是要在大量的s e n s o r 与a c t o r 之间提供一种低延时低能耗高效率的通信机制。 目前，这种s e n s o r 与a c t o r 间的协调机制存在许多有待解决的问题： ( 1 ) 对于事件区域中只有一个a c t o r 的情况，如果有多个s e n s o r 报告了同一 个事件，则会导致了关心这个事件的a c t o r 会在同一时刻收到很多不同s e n s o r 传 递过来的信息。因此，有必要确保在整个事件区域a c t o r 只对该事件执行一次适当 的反应。另外，如果在事件区域存在多个a c t o r ，则s e n s o r 在传递事件信息时要知 道如何选择合适的a c t o r 集，保证信息传递的低能耗、低延时和高可靠的要求，以 确保有合适的a c t o r 做出及时的反应。目前，w s a n s 中尚缺少有效的对a c t o r 进 行选择的算法。 ( 2 ) 在分布式决策中，为了方便s e n s o r 与a c t o r 协调时能够了解a c t o r 对事 件的适合程度，需要定义一种度量机制，以决定哪个或哪些a c t o r 适合作为事件的 反应节点。a c t o r 对事件的适合程度，主要是指选择的a c t o r 能否对接收到的事件 做出响应，以及响应是否能够满足事件的要求。目前，w s a n s 中尚缺少高效选择 某个a c t o r 作为决策中心以及如何在某个a c t o r 集中选择哪个a c t o r 作为决策中心 国防科学技术大学研究生院工学硕士学位论文 的算法。 ( 3 ) 与w s n s 一样，w s a n s 中s e n s o r 与a c t o r 之间的通信应该是低能耗的 通信而且在某些对通信延时敏感的应用中( 如火灾报警系统) ，两者之间的通 信还要考虑实时问题。因此，在w s a n s 中需要开发具有下列功能的协议：a ) 按 照应用约束，提供确切延迟界限的实时服务。b ) 传感节点和反应节点之间确保采 用能量高效的通信。目前，还没有一种有效的算法可以解决w s a n s 中的实时通信 问题。 基于以上问题，本课题将在s e n s o r 与a c t o r 的协调方面的技术进行研究，重 点是要在w s a n s 的网络路由方面设计高效的协调机制算法。 1 4 论文内容安排 本文共分六章，内空如下： 第一章主要介绍了课题的研究背景和面临的问题。 第二章主要介绍了w s a n s 的通信体系及发展现状，说明了课题研究的具体工 作，是对整篇论文的总体介绍 第三章主要介绍了单个反应节点选择情况下。传感节点与反应节点间的协调 通信问题，提出了一种基于跳数受限能量有效的单反应节点选择算法。 第四章主要就传感节点对多个反应节点间的协调问题进行了进一步的研究， 提出了一个跳数有限能耗自适应的分布式选择算法。 第五章对前两章提出的算法进行了有关的性能评估，并出给了相关结果详细 分析。 结束语部分对全文作了总结，并展望了未来的有关工作。 第3 页 国防科学技术大学研究生院工学硕士学位论文 第二章w s a n s 的通信体系及研究现状 2 1w s a n s 的通信体系 2 1 1w s a n s 的物理结构 在w s a n s 中，传感节点和反应节点的作用分别是从环境中收集数据和根据收 集到的数据执行合适的操作。如图l 所示，这些节点被部署在传感反应区域中， 由汇聚节点( s i n k ) 监控整个网络，并与任务管理节点( t a s km a n a g e m e n tn o d e ) 进行 通信，必要时与s c n s o r l a c t o 逋信l l j 。 在w s a n s 中，传感节点和反应节点的作用分别是从环境中收集数据和根据收 集到的数据执行合适的操作。如图2 1 所示，这些节点被部署在传感反应区域中， 由汇聚节点( s i n i 【) 监控整个网络，并与任务管理节点( t a s km a n a g e m e n tn o d e ) 进行 通信，必要时与s e n s o r a c t o r 通信。 图2 1w s a n s 的物理结构 当s e n s o r 检测到事件时，有两种方式将数据传输给a c t o r ，见图2 2 所示。第 一种称为半自动结构( s e m i a u t o m a t e d ，w s n s 所使用的方式) ：s e n s o r 先将数据路 由回s i n k ，由s i n k 发送操作命令给a c t o r 。这种方式需要s i n k 干预，但不需要s e n s o r 与a c t o r 之间和a c t o r 与a c t o r 之间的协调，类似于传统w s n s 结构。第二种称为 全自动结构( a u t o m a t e d ) ：s e n s o r 将数据传递给a c t o r ，由a c t o r 来处理数据，并执 行适当的操作。这种方式不需要s i n k 干预，而且由于s e n s o r 与a c t o r 的距离相对 接近，通信的延迟低，消耗的能量小，有利于延长网络的生存时间，但它需要分 布式的s e n s o r 与a c t o r 之间和a c t o r 与a c t o r 之间的协调。目前在w s a n s 中主要 第4 页 国防科学技术大学研究生院工学硕士学位论文 研究全自动结构。 图2 2a u t o m a t e d ( a ) 与s e m i - a u t o m a t e d w s a n s 中通信所实现的高效操作，都是通过s e n s o r 和a c t o r 之间协调来实现 的。全自动结构中s e n s o r 与a c t o r 的通信虽然类似于w s n s 中的s e n s o r 与s i n k 的 通信，但不同的是：在w s n s 中，通常只有一个固定的s i n k 节点，并且s i n k 只负 责收集传感数据；而在w s a n s 中，有大量移动的a c t o r 被部署在s e n s o r 的附近， 收集传感数据，并对环境做出适当的反应，在w s a n s 中，除了s e n s o r 与a c t o r 通信外，大多数情况下还需要a c t o r 相互问合作来实现整个任务。由于a c t o r 资源 相对丰富并且发射功率强，因此a c t o r 之间的相互间通信不同于s e n s o r 与a c t o r 的通信，它们通常采用长距离通信方式，类似于a d - h o c 的通信模式。 总得来说，w s a n s 可以看作w s n s 与a d h o c 网络的结合。因此，w s a n s 中除了要考虑w s n s 和a d h o c 网络的难题，还需要考虑实时特性、对环境作用等 新的特性。 2 1 2w s a n s 的协议结构 为了处理s e n s o r 和a c t o r 以及a c t o r 和a c t o r 之间的协调所带来的难题，需要研究 w s a n s 所用的协议栈。w s a n s 的协议栈由三个平面组成【“，如图2 3 所示。 第5 页 国防科学技术大学研究生院工学硕士学位论文 图2 3w s a n s 的协议栈 下面介绍每个平面的功能： ( 1 ) m a n a g c m a n tp l a n e ( 管理平面) ： p o w e rm a n a g e m e n t ：管理节点对能量的使用。比如，当某个节点的能 量级别过低时，管理平面通知协调平面该节点不能参与检测、转播、 反应等活动。 m o b i l i t ym a n a g e m e n t ：检测和注册节点的移动，维护网络的连通性。 在w s a n s 中，由于节点，特别是a c t o r ，可能是移动的，移动管理平 匿就可以方便a c t o r 跟踪邻居a c t o r 是谁。 f a u l t m a n a g e m e m ：探测和解决节点故障问题。 ( 2 ) c o o r d i n a t i o np l a n e ( 协调平面) ：该平面根据从通信平面和管理平面接收到 的数据，来决定一个节点要执行的操作。 ( 3 ) c o m m u n i c a t i o np l a n e ( 通信平面，：通信平面实现节点之间信息和连接关 系的交换和共享，是s e n s o r 和a c t o r 结构中最重要的一个平面，主要用来处理节 点的介质访问，路由的选择，数据包的传输等。 2 2 国内外研究现状及分析 近年来，w s a n s 越来越引起国内外研究人员的关注，并有专门为w s a n s 召开 的国际会访( s a n p a ( 传感反应网络协议与应用) 。目前，已经针对w s n s 提出许多协 议和算法，而对于从w s n s 中衍生出的w s a n s 却很少有这方面的研究成果。一些 第6 页 国防科学技术大学研究生院工学硕士学位论文 与w s a n s 相关的研究有：论文”1 ( 北卡罗莱纳卅l 大学电气计算机工程系，m o y u e n c h o w ) 只在控制工程方面涉及到传感反应网络；论文”( 法国圣母大学，h a e n g g i ， m ) 阐述了有关传感反应网络现有的、新兴的技术，但没有提及传感节点和反应节 点的交互问题；论文1 7 3 ( 南加州大学计算机科学系，b r i a n p g e r k e y ) 研究了反应 节点相互间协调，但没有提及传感节点与反应节点之间的协调；论文”，( 马里兰 大学电气计算机工程系，t h o m a sw c a r l e y ) 针对无线传感反应网络提出了无竞争 调度的t d m am a c 协议，文中将传感节点和反应节点看作同种类型的节点，而没 有指出w s a n s 的异构问题：论文四1 中，考虑了不同种类节点，研究了传感节点与 反应节点之间的路由路径，但没有研究传感节点与反应节点通信、反应节点与反 应节点通信中的协调和网络问题。 下面是国内外w s n s 和w s a n s 在路由技术方面的主要成果。 ( 1 ) d d ( d i r e c t e dd i f f u s i o n ，南加利福尼亚州大学，c i n t a n a g o n w i w a t ) “”： 它是一个以数据为中心，基于反向路径的传感网络通信模式。s i n k 加入网络后， 将兴趣泛洪到网络中。一个兴趣就代表一个查询，兴趣指定了s i n k 要求s e n s o r 收 集的信息属性。反过来，源节点将开始几个探测数据包泛洪到网络中。s i n k 选择 并加强最好的路径，然后源节点使用反向最好路径，将数据发送回s i n k 。该算法 考虑了多源单s i n k 、多s i n k 单源问题，但没有涉及多源多s i n k 的情况。另外，它 不能很好地处理s i n k 的移动问题，而且还会导致网络发送重复数据的复本到多个 s i n k 。 ( 2 ) l e a c h ( l o we n e r g ya d a p t i v ec l u s t e r i n gh i e r a r c h y ，麻省理工学院， h e i n z e l m a n ) n 1 】：它是一种基于簇的协议。协议针对s e n s o r 直接与基站通信代价 太高的情况，采用分簇结构，只需簇首与基站通信，这样可以大大减少通信开销； 针对簇首消耗的能量远大于非簇首节点，采用簇首随机轮转机制，将能量负载均 匀地分布到网络中的传感节点上，延长网络的生存时间。l e a c h 中实现传感网络 能量分布的最小化，但并不能满足w s a n s 的所有需求。l e a c h 中只有一种类型 的节点，并且不支持多跳通信。另外，只有少量s e n s o r 之间是连通的，或者只有少 量s e n s o r 检测到现象时，l e a c h 也不允许重新分配带宽。 ( 3 ) s e p ( s m b l e e l e c t i o n p r o t o c o l ，波士顿大学，g e o r g i o ss m a r a g d a k i s ) i j 埘： 在l e a c h 的基础上，根据传感节点的不同能量级将传感节点分成普通传感节点和 高级传感节点两种类型，并根据每个节点的剩余能量，通过加权选择概率来决定 簇头的分配。该协调比l e a c h 能更好地延长首个传感节点的死亡间隔，即所谓的 稳定周期( s t a b i l i t yp e r i o d ) ，而稳定周期的长短对那些要求传感网络反馈回可靠 的信息的应用来说是至关重要的。由于该协议仍然只支持单跳通信，也不能满足 w s a n s 的对能量分布的所有要求。 第7 页 国防科学技术大学研究生院工学硕士学位论文 ( 4 ) t t d d ( t w o t i e rd a t ad i s s e m i n a t i o n ，加州洛杉矾大学，f a ny e ) h 3 ： 通过计算s e n s o r 和转发地点之间的距离，t t i ) d 尝试建立一个虚拟的网格。距离最 小的s e n s o r 成为一个转发点。s i n k s 在网格内广播它们的查询兴趣，转发点将查询 兴趣发送给源。源沿着反向路径传送数据包至f s i n k s 。与定向扩散相比，它能更好 地处理s i n k 的移动。但它将重复的数据包发送到多个s i n k 。在w s a n s 中，资源丰 富的a c t o r 通过相互协调可以容易地交换数据，因而不需要发送重复的数据包到多 个a c t o r ，避免资源受限的传感节点消耗更多的能量。 ( 5 ) s e a d ( 汉城国立大学，h y u n gs e o kk i m 。) 1 4 3 ；它是一种可扩展、能 量高效的异步分发协议，在建立分发树和将数据分发给移动的s i n k s 上实现能量消 耗最小化，但它并没有处理端到端延迟的最小化，而这又是w s a n s 的一个主要目 标。开发s e a d 是针对所有的s i n k 以某个刷新速率向一个源请求数据的情形，而在 w s a n s 中，仅仅是事件附近的a c t o r 厶对事件信息感兴趣。 ( 6 ) s p e e d ( 弗吉尼亚州大学，t i a nh e ) ”：它提供了三种类型的实时通 信服务( e p 实时单播、实时区域多播和实时区域) ，是一种自适应，基于位置的实时 路由协议。采用反馈控制和非确定地域转发相结合的机制，维护跨跃传感网络所 需发送速率，实现端到端的软实时通信。但它不支持多个a c t o r 情况下s e n s o r 与a c t o r 之间的协调，也不支持a c t o r 的移动。 ( 7 ) m m s p e e d ( m u l t i - p a t hm u l t i - l a y e rs p e e dp r o t o c o l ，俄亥俄州大学，e m a d f e l e r n b a n ) “”：该协议是对s p e e d 协议的进一步研究，它通过对无线信道、能量、 处理能耗等多种资源的最优分配，试图在实时性和可靠性需求两方面为w s n 提供 不同的q o s j 艮务。该协议不需要全局的网络信息，在保证数据包的实时性和可靠性 的同时，具有较好的可扩展性和自适应性。但它同样不支持多p a c t o r 情况下s e n s o r 与a c t o r 芝l 间的协调，也不支持a c t o r 的移动。 ( 8 ) a n y c a s t ( 澳大利亚新南威尔士大学，w e nh u ) r 9 ：其主要思想是以每 个事件源为根构造一棵最短路径树，反应节点成为树的叶子节点。反应节点可以 动态地加入( 通过泛洪路由发现兴趣) 和离开。数据被发送到树上最近的反应节 点。它不支持传感节点相互间协调，造成重复发送内容相同的数据包，增加了不 必要的能量消耗，因为检测到同一事件的多个源之间信息是相关。它也不支持反 应节点相互间协调，这会导致离反应节点一跳距离的传感节点也会接收到来自网 络另一端的反应节点发送的兴趣，产生不必要的流量负载。 ( 9 ) m u l t i s t a tp r o t o c o l 【i ，j ：t o m m a s om c l o d i a 等人在w s a n s 分布式协调框架 中提出的多状态协调算法，该算法只考虑了传感节点与多个反应节点的协调问题， 不支持与单个反应节点的协调，也没支持节点的移动。 第8 页 国防科学技术大学研究生院工学硕士学位论文 ( 1 0 ) 论文【1 9 】口o l ：乔治亚州技术学院的r a r n a n u j a 等人针对传感节点与反应 节点间的紧密耦合问题，在应用层方面对传感节点与反应节点间因延时带来的查 询和命令的执行顺利的确定问题，任务执行的互斥等问题进行了研究，并给出相 关的分布式本地解决方案。论文i 阍【19 】跚中的有关算法主要是针对应用层进行的研 究，且传感节点与反应节点之间的通信与要汇聚节点( s i n kn o d e ) 参与协调，在 路由及能量分布等方面缺少对w s a n s 的支持。 另外，在论文【3 3 i 3 5 i 3 6 1 1 3 7 1 3 s 3 9 n o 4 1 】1 4 2 】中，研究人员分别就节点分簇，有效路 由保障等方面对现有的w s n s 网络提供了多种解决方案，但对w s a n s 的新特点的 支持仍存在技术上的缺陷。与国外的研究相比，国内在传感网络方面的研究成果 不多，主要是一些综述性、比较性的文章，如论文伫1 】瞄】f 2 3 】洲。国防科大也在传感 网络路由、操作系统方面进行研究。 由上可知，虽然已经有一些与w s a n s 相关的研究，但缺少因s e n s o r 与a c t o r 的共存所带来的挑战性问题的研究。因而，研究s e n s o r 与a c t o r 共存所带来的协 调问题和通信问题，具有十分重要的意义。 第9 页 国防科学技术大学研究生院工学硕士学位论文 第三章基于h b m e c t 的单个反应节点选择算法的研究 3 1 实时通信条件下单个反应节点选择的特点 在w s a n s 中，反应节点的选择好坏，直接影响通信的时延和网络生存时间。 对于单个反应节点选择( s m g l e a c t o r s e l e c t i o n ，s a s ) 的情况( 如图3 1 所示) ， s e n s o r 将数据只发送给事件区域( e v e n t - a r e a ，e a ) 附近的某一个a c t o r ，如果这个 a c t o r 有足够的能力来执行操作，它可以马上执行相关的操作。这意味着传感节点 和反应节点间的反应延时可以很小，从而不需要反应节点间的协调。另外，即使 一个a c t o r 没有满足执行操作的能力，它也可以向其他a c t o r 宣告消息。一旦收到其 他a m o r 的响应，它可以选择一个或多个可用的a c t o r ，并让它或它们执行操作来完 成对事件的响应i l 】脚】。 图3 1 单个反应节点的选择 因此，s a s 的关键是要在所有a 咖r 中确定哪个a c t o r 接收该数据。这需要在 事件区的s e m o r 为这个选择过程进行相互通信，并协调给出行选择结果。基于s a s 的上述特点，我们可从以下几个方面对s a s 进行考虑： ( 1 ) s e n s o r 的能量消耗：即s e n s o r 在查找到a c t o r 时，要构造一条从e a 到该 a 咖r 的最小能量路径来发送数据。 ( 2 ) a c t o r 与e a 的距离( 即跳数) ：这个距离应该很小，以实现低延迟、低能 耗的要求通常在数据转发过程中涉及的节点越多，能量消耗越大，网络生存时 间短。但问题是如何选择a c t o r ，使得它接近e v e n t a r e a 中的每个传感节点。 ( 3 ) a c t o r 的作用范围：因为a c t o r 为了对事件区执行适当的操作，事件区应该 第1 0 页 国防科学技术大学研究生院工学硕士学位论文 处于接收数据包的a c t o r 的作用范围内，但并不能保证所选择的a c t o r 的作用范围 能覆盖整个事件区。因此，s e n s o r 在寻找合适的a c t o r 时，要考虑a c t o r 对e v e n t - a r e a 是否有足够的作用覆盖，足够的能量和足够的能力来执行所需的反应。 基于上述特点以及在w s a n s 中对应用的实时性要求和传感节点的能量约束 这两个重要的因素，本章提出了基于跳数和能量约束的单个反应节点的选择算法 叼h o p b o u n d e da n dm i n i m u me n e r g yc o s tt r e e ，h b m e c t ) ，并对其进行整数线 性规划( i n t e g e rl i n e a rp r o g r a m m i n g ，i l p ) 来获得s a s 的最佳解决方案。 由于对i l p 问题直接求解比较困难( 即使我们使用像c p l e x l 2 5 1 这样的专用软件 来解决i l p 问题也是很困难的) ，所以本章首先讨论了最小代价树选择算法，作为 对h b m e c t 算法的一个理论参考。然后，给出了i - i b m e c t 的一个分布式近似算法 的解决方案，这是在目前的s a s 算法中没有提出过的。下面我们先给出与单反应节 点选择算法的网络模型和相关定义。 3 2 单反应节点选择算法的网络模型和相关定义 为了研究单个反应节点的选择算法，我们首先对网络中的传感节点和反应节 点做了如下假定： ( 1 ) 每个传感节点通过配备g p s 接收器，或者由本地服务器【1 0 l 提供，或者通 过其他定位技术来决定自身的位置1 2 6 1 。 ( 2 ) 每个传感节点周期性的向邻居节点发送自身的位置来获得邻居节点的位 置信息。 ( 3 ) 每个反应节点通过周期性地向事件区域发送信标( b e a t o n ) 来提供它的位 置信息。 ( 4 ) 每个传感节点具有相同的能力，比如相同的通信范围、能量和传感范围 等。 ( 5 ) 传感节点和反应节点都是不能移动的。 3 2 1 网络模型的定向图描述 对于由传感节点和反应节点组成的网络，我们可以用一个定向图g ( v ，e ) 来表 示在图g ( v e ) 中，v 是一个有限维数空间内的传感节点和反应节点的有限集 合( v = l v l ) 。e 代表有效的通信链路的集合，例如，e i j e ，当且仅当节点i 和节点 j 在彼此的传输范围内。假定a 代表反应节点的集合( m = l a i ) ，s 代表整个传感节 点的集合( s = l s l ) 。在这里，我们还涉及到一个数据接收者，它是某个从一个或 多个源节点收集数据流的反应节点。因此，我们假定s l 是产生数据流的源节点( 即 第t i 页 国防科学技术大学研究生院工学硕士学位论文 指那些能侦测到事件发生的传感节点) 的集合( s l = s 1 1 ) 。由此定义的图o ( v ，e ) 便可表示监测事件的传感节点和反应节点的集合，比如，对于事件区域中的传感 节点有如下关系：v = j + m ，矿= s u a ，s 1e - s ，s n a = 庐。 3 2 2 能量模型定义 为了研究多个反应节点的选择算法，我们定义物理层中每一位数据的能耗e 。 为：e ，= e ：? + 卢酽+ e 乏。其中，占嚣只考虑