（计算机科学与技术专业论文）无线传感器网络几何路由技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 传感器网络是一种由低功耗设备组成、用于在无人照看的情况下监测野外情 况的网络。传感器网络可以用于环境检测、跟踪、设施保卫。路由算法和拓扑控 制是无线传感器网络的关键性问题。路由算法决定了无线传感器网络的通信效率， 拓扑控制决定了网络的底层拓扑。而路由算法的性能直接与底层拓扑相关。本文 主要针对无线传感器网络的路由问题和拓扑控制问题进行了深入研究。 几何路由协议非常适合无线传感器网络。这类协议利用节点的地理位置信息 提供高效、可扩展的路由。在无线传感器网络中。节点分布在一定的地理区域内， 节点间是否能够直接通信由它们之间的距离决定，因此几何路由协议符合无线传 感器网络的特点。小型而便宜的卫星定位接收机( g p s ) 的可用性和无g p s 的定 位算法的研究使得在无线传感器网络中应用几何路由协议成为可能。 本文在分析现有几何路由协议存在的问题的基础上，提出了转发矩形限制的 贪心面路由协议c g f r 。c g f r 协议包括拓扑控制层和几何路由层两个层次。协议 的目标是在保证分组转发的可达性，并在此前提下减少分组通过的路径长度。 拓扑控制算法是c g f r 协议的基础，其目的是构造满足几何路由协议要求的 底层拓扑，并提高几何路由协议的性能。拓扑控制算法的基本思想是用局部算法 构造网络拓扑的平面f - 支撑图，使得任意两个节点在拓扑控制算法生成的拓扑中的 最短路径长度不超过无拓扑控制的拓扑中的最短路径常数的t 倍。由于生成的拓扑 满足平面性，因此可以保证几何路由算法的分组可达性。由于生成的拓扑是f 支撑 图，因此为减少分组通过的路径长度提供了可能性。 拓扑控制算法分为静态拓扑控制算法和动态拓扑控制算法。静态拓扑控制算 法用于节点动态不变化的网络。动态拓扑算法以静态算法为基础，在节点动态加 入和退出网络时，维护网络拓扑是平面，支撑图。 几何路由算法是c g f r 协议的核心，其目的保证分组可达性的前提下高效地 转发分组。几何路由算法包括贪心路由算法c g r 、面路由算法c f r 和贪心面路由 算法c g f r 。 贪心路由算法c g r 的基本思想是用转发矩形限制选择转发节点的范围，以减 少分组通过的路径长度。本文证明了，c g r 算法通过的路径长度和跳步数不超过 理想网络中路径长度和跳步数的常数倍。模拟实验表明，转发矩形降虽然低了转 发的成功率，但是保证了路由长度的有界性。 面路由算法c f r 在保持面算法保证分组可达性的特性的基础上，通过使用类 第i 页 国防科学技术大学研究生院博士学位论文 似二分查找的方法避免了纯面算法近似广播算法的高开销。模拟实验表明，c f r 算法的开销低于现有的纯面路由算法的开销。 贪心面路由算法c g f r 结合了c g r 算法和c f r 算法的优点，既保证了分组 转发的可达性，又减少了分组通过的路由长度。本文证明了，c g f r 算法的开销与 最优几何路由算法的开销是同一个量级。模拟实验表明，c g f r 算法的开销低于现 有的保证可达性的几何路由算法。 几何路由协议的研究对无线传感器网络的应用将起到重要的推动作用。然而 对无线传感器网络的研究还处于起步阶段，为使之实用化还需付出更多努力。 主题词：无线传感器网络，拓扑控制，几何路由，d e l a u n a y 三角剖分，支撑 图，转发矩形，贪心路由，面路由 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t p a c t w i r e l e s ss e n s o rn e t w o r k sa r en e t w o r k so fs m a l ll o w - p o w e rd e v i c e st h a tc a n o p e r a t eu n a r e n d e dt om o n i t o ra n dm e a s u r ed i f f e r e n tp h e n o m e n ai nt h ee n v i r o n m e n t s e n s o rn e t w o r k ss u i t e df o rm o n i t o r i n g ，t r a c k i n ga n di n f t a s t r u e t u r ep r o t e c t i o n r o u t i n g a n dt o p o l o g yc o n t r o la r et w ok e yp r o b l e m s t h ee f f i c e n c yo fc o m m u i n i c a t i o nl a r g e l y d e p e n d so nt h er o u t i n gp r o t o c o l sa n dt h et o p o l o g yo ft h en e t w o r ki sd e t e r m i n e db y t o p o l o g yc o n t r o lp r o t o c o l s a st h ep e r f o r m a n c eo f r o u t i n gp r o t o c o l si sc l o s e l yr e l a t e dt o n e t w o r kt o p o l o g y ，t h e r e f o r e ，r o u t i n gp r o b l e ma n dt o p o l o g yc o n t r o lp r o b l e ma r et h e f o c u s e so f t h et h e s i s g e o m e t r i cr o u t i n gp r o t o c o l sa r cv e r ys n i t e df o rw i r e l e s ss e n s o rn e t w o r k s t h e s e p r o t o c o l st a k ea d v a n t a g eo ft h ep o s i t i o ni n f o r m a t i o no fn o d e st op r o v i d eh i g he f f i c i e n t a n ds c a l a b l er o u t i n g i nw i r e l e s ss e n s o rn e t w o r k s ，n o d e sa r ed i s t r i b u t e di ns o m e g e o g r a p h i ca r e a s ；t h e d i s t a n c eb e t w e e nn o d e sd e t e r m i n e sw h e t h e r t h e y c a n c o m m u n i c a t ee a c ho t h ed i r e c t l y t h e r e f o r e ，g e o m e t r i cr o u t i n gp r o t o c o l sa r es u i t e df o r t h ec h a r a c t e r i s t i co fw i r e l e s ss e n s o rn e t w o r k n 伦a v a i l a b i l i t yo fs m a l la n dc h e a pg p s r e c e i v e r sa n dt h er e s e a r c h e so fg p s - f r e el o c a t i o na l g o r i t h m sm a k ei tp o s s i b l et od e p l o y g e o m e t r i cr o u t i n gi nw i r e l e s ss e n s o rn e t w o r k i nt h i sp a p e r , b a s e do na r “y z i n gt h el i m i t a t i o n so fe x i s t i n gw o r k s ，an e w g e o m e t r i cr o u t i n gp r o t o c o l ，f o r w a r d i n gr e c t a n g l ec o n s t r a i n e dg r e e d yf a c er o u t i n g p r o t o c o l ( c g f r ) ，i sp r o p o s e d c g f rp r o t o c o lm a i n l ya i m st oe n s u r et h es u c c e s so f p a c k e td e l i v e r y ，a n dt h e nt or e d u c et h el e n g t ho rh o p so f r o u t et r a v e s e db yp a c k e t 1 1 1 ef o u n d a t i o no fc g f rp r o t o c o li st o p o l o g yc o n t r 0 1 t h ep u r p o s eo ft o p l o g y c o n t r o li st oc o n s t r u c tat o p o l o g yt os a t i s f yt h er e q u i r e m e n to fg e o m e t r i cp r o t o c o la n dt o i m p r o v et h ep e r f o r m a n c eo fg e o m e t r i cr o u t i n gp r o t o c 0 1 t h em a i ni d e ao ft o p o l o g y c o n r o li st oc o n s t r u c tap l a n a rt - s p a n n e ro ft h eo r i g i n a lt o p o l o g y ，i e f o re v e r yp a i ro f n o d e st h el e n g t ho ft h es h o r t e s tp a t hb e t w e e nt h e mi nt h et o p o l o g yc o n s t r u c t e db yt h e t o p o l o g yc o n t r o la l g o r i t h mi s n om o r et h a nt h a to ft h eo r i g i n a lt o p o l o g y a st h e t o p o l o g yc o n s t r u c t e db yt h et o p o l o g yc o n t r o la l g o r i t h mi sp l a n a r , i tm a ye n s u r et h e d e l i v e r yo fg e o m e t r i cr o u t i n ga l g o r i t h m a st h et o p o l o g yc o n s t r u c t e db yt h et o p o l o g y c o n t r o la l g o r i t h mi sat - s p a n n e r , i tp r o v i d e ss h o r t e rp a t hf o rg e o m e t r i cm u t i n gp r o t o c 0 1 t o p o l o g yc o n t r o li n c l u d e ss t a t i ct o p o l o g yc o n t r o la l g o r i t h ma n dd y n a m i ct o p o l o g y c o n t r o la l g o r i t h m s t a t i ct o p o l o g yc o n t r o la l g o r i t h mc o n s t r u c t sp l a n a rt - s p a n n e rf o r s t a t i cn e t w o r k , w h i c hi st h eb a s eo fd y n a m i ct o p o l o g yc o n t r o la l g o r i t h m d y n a m i c t o p o p l o g yc o n t r o la l g o r i t h mc a nm a i n t a i nt h et o p o l o g yt oh eap l a n a rt - s p a n n e ri n d y n a m i cn e t w o r k s ，w h e r en o d e sc a n j o i na n d l e a v en e t w o r ka ta n y t i m ea n da n y w h e r e t h ec o o fc g f ri sg e o m e t r i cm u t i n g w h o s ea i mi st oi m p r o v et h ef o r w a r d i n g e f f i c i e n c ya tt h eb a s eo ft h es u c c e s s f u ld e l i v e r y g e o m e t r i cr o u t i n ga l g o r i t h mi n c u d e s 第i i i 页 国防科学技术大学研究生院博士学位论文 f o r w a r d i n g r e c t a n g l e c o n s t r a i n e d g r e e d yr o u t i n g ( c g r )a l g o r i t h m , f o 删i n g r e c t a n g l e c o n s t r a i n e df a c e r o u t i n g ( c f r ) a l g o r i t h m a n d f o r w a r d i n g - r e c t a n g l ec o n s t r a i n e dg r e e d yf a c er o u t i n gf c g f r ) a l g o r i t h m t h ei d e ao fc g r a l g o r i t h mi sc o n s t r a i n i n gt h ec a n d i d a t eo fn e x th o pn o d e si n f o r w a r d i n g r e c t a n g l et ob o u n dt h el e n g t ho rh o p so ft h er o u t et r a v e r e db yp a c k e t i ti s p r o v e dt h a tc g ra l g o r i t h mc a nb o u n dt h el e n g t ho rh o p so ft h er o u t et r a v e r s e db y p a c k e tb yc o n s t a n tt i m e so f t h el e n g t ho rh o p so f t h er o u t ei ni d e a ln e t w o r k s i m u l a t i o n r e s u l t ss h o wt h a ta l t h o u g hf o r w a r d i n g - r e c t a n g l ed e c r e a s e st h er a t i o no fs u c c e s s f u l d e l i v e r y ，i tb o u n d st h el e n g t ho rh o p so f r o u t e a sa l lo t h e rf a c e - b a s e dr o u t i n g 。c f ra l g o r i t h me n s u r e st h es u c c e s s f u ld e l i v e r y n u s eaw a yl i k eb i n a r ys e a r c ht oa v o i dt h eh j 【g ho v e r h e a do f p u r ef a c er o u t i n ga l g o r i t h m s ， w h i c ha p p r o x i m a t e st h eo v e r h e a do fb r o a d c a s ta l g o r i t h m n l ec o n j e c t u r ei sc o n f i r m e d b ys i m u l a t i o nr e s u l t s c g f r a l g o r i t h mc o m b i n e st h ea d v a n t a g eo fc g ra l g o r i t h ma n dc f ra l g o r i t h m , w h i c he n s u r et h es u c c e s s f u ld e l i v e r ya n dh i g he f f i c i e n c y i ti sp r o v e dt h a tt h ec o s to f c g f ra l g o r i t h mi st h es a m eq u a n t i t ya st h eo p t i m a lg e o m e t r i cr o u t i n ga l g o r i t h m s i m u l a t i o nr e s u l t ss h o wt h a tt h ec o s to f c g f r a l g o r i t h mi sl e s st h a nt h a to f a n ye x i s t i n g g e o m e t r i ca l g o r i t h m s n l er e s e a r c ho fg e o m e t r i cr o u t i n gp r o t o c o lw i l lg r e a t l yp r o m o t et h ea p p l i c a t i o no f w i r e l e s ss e n s o rn e t w o r k h o w e v e r , r e l e v a n tr e s e a r c h e si nt h i sf i e l da r ej n s tb e g i n n i n g m a n ye f f o r t ss t i l ln e e dt ob em a d et or e a l i z ei t sf u t u r ea p p l i c a t i o n k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k s ，t o p o l o g yc o n t r o l ，g e o m e t r i cr o u t i n g ， d e l a u n a yt r i a n g u l a t i o n ，s p a n n e r ，f o r w a r d i n g r e c t a n g l e ，g r e e d yr o u t i n g ，f a c er o u t i n g 第i v 页 国防科学技术大学研究生院博士学位论文 图目录 图1 1 无线传感器网络体系结构l 图1 2 传感器节点硬件体系结构2 图l - 3 传感器节点软件系统结构2 图l - 4 无线传感器网络协议栈3 图2 - l 最大前进路由1 8 图2 - 2 最近向前路由1 8 图2 3 指南针路由1 9 图2 - 4 随机指南针路由1 9 图2 5 贪心路由算法2 0 图2 - 6 面路由算法2 3 图3 - lc g f r 协议框架2 7 图4 1 危险区域3 4 图4 2 引理4 - 6 3 5 图4 3 定理4 7 3 6 图4 4u d g 图4 2 图4 5a u d e l 图4 2 图4 6 通信开销比较4 5 图5 - l 任意多个错误的p r o p o s a l 消息4 8 图6 1 两种算法下欧式支撑因子比的比较情况6 5 图6 - 2 两种算法下网络支撑因子的比较6 6 图6 - 3 两种算法下分组成功转发率6 6 图7 1f r 算法示例。7 0 图7 2c f r 问题l 7 l 图7 - 3c f r 问题2 7 2 图7 4 欧式支撑因子的比较。7 6 图7 5 网络支撑因子比较7 7 图8 1 定理8 2 7 9 图8 2 图椭，m j + ，m 肿的分布情况8 l 图8 3 路径由两个节点组成9 2 图8 - 4 路径由三个节点组成9 3 图8 5 路径由四个节点组成9 3 图8 6 定理8 - 4 a 9 4 第v 页 国防科学技术大学研究生院博士学位论文 图8 ，7 定理8 4 b 9 5 图8 8 定理8 4 c 9 7 图8 - 9 欧式支撑因子比较9 9 图8 1 0 欧式支撑因子比较1 0 0 第v i 页 国防科学技术大学研究生院博士学位论文 表目录 表4 1c a u d e l 算法3 7 表舡2e c a u d e l 算法3 8 表4 - 3c h e c ki 童程3 8 表4 - 4 比较u d g 图，u d e l 图，p l d e l 图和a u d e l 图的总边数4 2 表5 - ld y n c a u d e l 算法的初始化构造部分。4 7 表5 2d y n c a u d e l 算法的异步部分。4 9 表5 3d y n c a u d e l 算法的同步部分。5 0 表5 - 4d y n e c a u d e l 算法的初始化构造部分5 3 表5 5d y n e c a u d e l 算法的动态维护部分的异步部分5 3 表5 石d y r l e c a u d e l 算法的动态维护部分的同步部分5 4 表6 1 贪心路由算法c g r 6 0 表6 2 模拟参数6 4 表7 1f r 算法6 9 表7 2 面路由算法c f r 7 2 表7 3 模拟参数7 5 表8 1 贪心面路由算法c g f r 7 8 表8 2 路径组合方式8 0 表8 3 模拟参数9 9 第v i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果。也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：丕绫篮壁墨圈签丛氲竖由筮盛珏窒 学位论文作者签名：壅丝 日期：2 彤年午月彳日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使周学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阋：可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印，缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目： 丕缦篮壁墨圄鳌且鱼整自拭壅盈左 学位论文作者签名：查丝日期：9 - 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 ) 是由部署在监测区域内大量 低成本、低功耗、具备感知、数据处理、存储和无线通信能力的传感器节点通过 自组织方式形成的网络，其目的是协作地采集、处理和传输网络覆盖区域中被感 知对象的信息。图1 1 是无线传感器网络体系结构示意图i l i 。典型的无线传感器网 络通常包括传感器节点( s e n s o rn o d e ) ，汇聚节点( s i n kn o d e ) 以及任务管理节点。大 量传感器节点通过随机部署或者确定部署的方式分布在监测区域内，通过自组织 方式形成多跳无线通信网络。传感器节点负责采集感兴趣事件或者目标的相关信 息，并沿某条路径通过其它节点将数据逐跳传回汇聚节点，最后再由汇聚节点通 过i n t e m e t 或者卫星网络将数据传送给任务管理节点。 图1 1 无线传感器网络体系结构 第1 页 国防科学技术大学研究生院博士学位论文 传感器节点是一个微型的嵌入式系统。图1 2 是典型的传感器节点硬件体系 结构示意图。传感器节点主要由传感器模块、处理器模块、无线通信模块和能量 供应模块组成。传感器模块与应用密切相关，主要包括采集物理信息的传感器和 相应的模数转换( a d c ) 部件。其它三个模块是与应用相对独立的部分。其中，处 理器模块负责对整个节点进行和管理、存储和处理本身采集的数据以及其它节点 发来的数据；无线通信模块负责通过无线通信与其它节点进行信息交互，比如收 发监测数据以及交换控制信息等：能量供应模块提供整个节点运行所需要的能量。 部分节点还包括定位系统以及执行( a c t u a t o r ) 模块等。 传蓐嚣模块处理器模块无线通信模块 卜器h 戕h 国卜副蝴l 能量供应模块 图1 - 2 传感器节点硬件体系结构 传感器节点的软件系统可以分为三个层次：操作系统层、系统服务层、应用 层( 图1 3 ) 。操作系统层提供硬件访问接口和任务执行环境。系统服务层包括网络 通信协议、能量管理、定位与定时等，主要为应用提供所需的系统服务。应用层 实现特定应用所需的功能，包括对来自多个传感器节点的数据进行融合等。 r 。 i ，。- - _ l - _ - - _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ - - _ _ _ - _ _ _ _ _ _ 。r 。i _ - - - - - _ _ _ _ i _ _ _ - ：l 艘用任务 li 数捌融合 l ： 琏掰屡 一一- | 圆圈圃圆圆；系统服务屡 ：i 移动管躞| i 能键褥理li 网络挑议ll 定位l 定时l ： 系统服务屡 一t ir _ _ _ - _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ - _ _ - _ _ - _ _ _ _ - _ _ _ _ _ _ _ _ - - _ _ _ _ _ - _ _ - _ _ 。_ i ：i 嵌入式撩份系统l ：操作系统屡 i 。一i l ， 图1 - 3 传感器节点软件系统结构 在实际应用中，传感器节点通常存在一些现实的约束1 2 l ： ( 1 ) 电源能量有限 由于体积和成本的限制，通常使用容量有限的电池为传感器节点提供能量。 此外，由于传感器节点数量大，而且通常部署在是沙漠、战场等危险环境中，更 第2 页 国防科学技术大学研究生院博士学位论文 换电池或者为电池充电是不现实的。因此，如何高效使用有限能量以最大化网络 生存时间是无线传感器网络设计面临的重要挑战。 ( 2 ) 通信能力有限 传感器节点无线通信的能耗与通信距离的，( 2sn s4 ) 次幂正比。随着通信 距离的增大，通信能耗急剧增加。由于节点的能量有限，因此应该在满足通信连 通度的前提下尽量减少单跳直接通信距离。 ( 3 ) 计算和存储能力有限 作为一种大规模部署的微型嵌入式系统，传感器节点必须价格低功耗小。这 些限制必然导致其携带的处理器能力较弱，存储器容量较小。这就要求面向无线 传感器网络的算法计算简单，易于在微型传感器节点上实现。汇聚节点通常具有 较强的处理能力、存贮能力和通信能力，并且其能量供应往往不受限制。它是连 接传感器网络与i n t e m e t 等外部网络的网关节点。用户可以通过管理节点收集监测 数据，发布监测任务，更新传感器节点配置以及对无线传感器网络进行管理等。 图l - 4 无线传感器网络协议栈 传感器节点通过网络协议自组成网。图1 - 4 是一个典型的无线传感器网络协 议栈示意刚”。这个协议栈包括物理层、数据链路层、网络层、传输层和应用层。 此外，协议栈还包括能量管理、移动管理和任务管理三个层面，使得传感器节点 能够按照能量高效的方式协同工作、路由数据以及共享资源。其中，物理层提供 简单但鲁棒的信号调制和无线收发技术；数据链路层负责数据成帧、信道访问控 制、冲突检测以及差错控制：网络层负责路由选择；传输层负责数据流的传输控 第3 页 国防科学技术大学研究生院博士学位论文 制；应用层由一系列与应用相关的软件组成；能量管理层面主要管理传感器节点 如何高效地使用有限能量，贯穿了网络协议栈各个层次：移动管理层面检测并注 册传感器节点的移动，为维护到汇聚节点的路由提供帮助，并且使传感器节点能 够及时更新邻居信息；任务管理层面负责实现节点间任务调度以及节点间负载均 衡。 无线传感器网络与移动自组网络( m o b i l ea dh o cn e t w o r k ，m a n e t ) 有类似之 处，但又自具特点。无线传感器网络具有如下特点： ( 1 ) 应用相关 无线传感器网络用来感知客观物理世界，获取物理世界信息。不同的传感器 网络应用关心不同的物理量，因此不同应用背景将导致不同的节点硬件平台、软 件系统和网络协议。无线传感器网络不能象i n t e m e t 一样具有统一的通信协议平 台，必须针对具体应用来研究传感器网络技术。这也是无线传感器网络区别于传 统网络系统的显著特征。 ( 2 ) 规模大 为了提高网络的可靠性，通常在目标区域内部署大量传感器节点，传感器网 络可能包含多达数千甚至上万个传感器节点。传感器网络的大规模性还能够通过 不同空间视角获得更大的信噪比，从而提高监测准确性。 ( 3 ) 高冗余 节点的大规模部署使得无线传感器网络通常具有较高的节点冗余，网络链路 冗余以及采集的数据冗余，从而使得系统具有很强的容错能力。 ( 4 ) 自组织 传感器节点通常被部署在没有基础结构的环境中。这就要求网络的建立和节 点间通信不依赖于固定的通信基础设施。传感器节点通过分布式网络协议形成自 组织网络，并能够自动调整以适应节点的移动、加入和退出、节点剩余能量以及 无线传输范围的变化等。 ( 5 ) 动态拓扑 除了节点移动带来的网络拓扑变化外，环境因素或者节点能量耗尽等因素可 能导致的节点故障或失效，环境条件变化造成的无线通信链路变化，为增强监测 精度而新加入节点，节点的功率控制，节点进入睡眠状态等均可能导致动态网络 拓扑结构。 ( 6 ) 空间位置寻址 无线传感器网络一般不需要支持任意两个传感器节点之间的点对点通信，传 感器节点不必具有全球唯一的标识，不必采用因特网的m 寻址。用户往往不关心 数据采集于哪一个节点，而关心数据所属的空间位置，因此可采取空间位置寻址 第4 页 国防科学技术大学研究生院博士学位论文 方式。从这个意义上讲，传感器网络通常以数据本身作为查询或传输线索，因此 传感器网络是一个以数据为中心的网络。 1 1 2 应用背景 无线传感器网络的应用前景广阔，能够广泛应用于军事、环境监测和预报、 健康护理、智能家居、城市交通以及空间探索等领域 3 1 1 7 1 。随着无线传感器网络的 深入研究和广泛应用，无线传感器网络将逐渐深入到人类生活的各个领域。无线 传感器网络具有可快速部署、自组织、隐蔽性强和可靠性高等特点，非常适合在 军事上应用。具体来讲，无线传感器网络可用于完成以下任务： 友军兵力和装备监视； 敌军兵力和地形侦察； 战场态势感知； 战争毁损评估； 目标检测、定位与跟踪； 核、生化攻击检测等。 在民用领域，无线传感器网络也存在广泛应用： 环境观测与预报，比如森林火险监测，洪水、泥石流等自然灾害预警，农 作物灌溉 情况监视，鸟类运动跟踪，生物栖息地监测等； 医疗护理，包括远程监测人体的各种生理数据，跟踪和监控医院内医生和 患者的行动，医院药物管理等； 智能家居； 抢险救灾； 建筑物状态监控； 商业库存管理； 产品质量监控： 城市交通管理，车辆跟踪与检测； 空间探索等。 信息技术正推动一场新的军事变革。信息化战争要求作战系统“看得明、反应 快、打得准”，谁在信息的获取、传输、处理上占据优势，谁就能掌握战争的主动 权。无线传感器网络以其独特的优势，能在多种场合满足军事信息获取的实时性、 准确性、全面性等需求。研究并设计实现高性能的无线传感器网络，具有重要的 应用价值和意义。 第5 页 国防科学技术大学研究生院博士学位论文 1 2 研究内容和研究现状 1 2 - 1 研究内容 作为当前信息领域的研究热点，无线传感器网络是一个涉及多学科交叉的研 究领域，其中存在许多问题需要研究和解决。总的来说，解决这些问题需要满足 如下的要求： 低能耗 节点的能耗对无线传感器网络的生存时间具有重大影响，是核心优化目标之 一。低能耗技术能在节点能量有限的条件下有效地延长网络生存时间。 可扩展性 无线传感器网络规模大、节点数量多，因此要求各项技术能够有效地适用于 大规模网络。 自适应性 可行的技术必须能够适应环境、网络拓扑的动态变化以及网络的高冗余特性 等。 简单性 传感器节点的计算、存储能力受限，因此现实可行的技术应是简单有效的技 术。 无线传感器网络的研究内容很多，按节点层面和网络层面可分为两大部分。 对传感器节点而言，研究内容主要包括： 传感器技术：研究多功能传感器、适应恶劣环境的传感器、传感器的微型 化等； 电源技术：研究体积小、容量大的高性能电源； 低功耗芯片技术：研究体积小、功耗低、功能强的c p u 、无线通信芯片 等： 无线通信技术：研究适合无线传感器网络的编码、多址访问等技术： 嵌入式操作系统：研究实时性强、代码量少、配置灵活、支持密集并发操 作的嵌入式操作系统，以及相关的应用开发支撑环境： 低能耗编译技术：研究有利于节能的程序编译技术： 节点的综合集成技术等。 在网络层面上，研究内容主要包括： 低能耗介质访问控制( m a c ) 协议 m a c 协议用来控制底层基础结构，控制传感器节点的通信过程和工作模式。 由于节点能量受限并且网络规模大，无线传感器网络的m a c 协议首先必须考虑 第6 页 国防科学技术大学研究生院博士学位论文 节省能量和可扩展性，其次才是考虑公平性、利用率和实时性等。为了节省能量， m a c 协议应该支持节点的休眠操作，使得节点在必要时可以关闭通信单元以及 c p u 的部分功能单元进入低功耗的睡眠状态。 高效路由协议 路由协议负责路由生成和选择，是传感器节点自组成网的核心。无线传感器 网络的特点和节点的固有约束要求必须以一种分布式、局部化的方式实现计算简 单、存储代价低的路由协议。存储复杂性和计算复杂性是无线传感器网络路由协 议的两个重要指标。在无线传感器网络中，路由协议不仅关心节点的路由表容量， 更关心节点转发分组时路由计算的复杂性。此外，还应该针对无线传感器网络流 量分布特点和应用任务要求优化路由技术，以满足无线传感器网络节点处理能力 有限的特点。 网络覆盖和网络规划 高密度部署的无线传感器网络中存在大量的冗余节点。如何利用节点冗余特 性提高能量利用效率，延长网络生存时间，是无线传感器网络的一个重要研究内 容。网络覆盖控制通过节点调度、密度控制等手段，在不影响网络覆盖性能条件 下，减少网络中活跃节点数量，并使得冗余节点交替工作，从而达到延长网络生 存时间的目的。网络规划研究如何部署传感器网络，使得网络覆盖质量最优以及 使用尽量小的代价实现被监测区域的无缝覆盖。 拓扑控制技术 拓扑控制主要的研究问题是如何通过功率控制以及骨干网节点的选择，删除 节点间不必要的无线通信链路，并使得网络拓扑满足一定的性质，如连通性、稀 疏性等，从而减少无线信号冲突，降低无线传输能耗，延长网络生存时间。拓扑 控制能够提高路由协议和m a c 协议的效率，并为数据融合、时钟同步和目标定 位等奠定基础，是无线传感器网络研究的核心问题之一。 定位技术 确定事件发生的位置或采集数据的节点位置是无线传感器网络基本功能之 一。为了提供有效的位置信息，传感器节点必须能够确定自身位置。由于节点存 在资源受限、随机部署、通信易受干扰等特点，定位机制必须满足自组织性、鲁 棒性、能量高效、分布计算等要求。当前主要的研究问题是如何在有路标和无路 标情况下，利用信号测距等手段实现传感器节点的分布协同定位，获得节点的绝 对或相对位置。 时钟同步技术 时钟同步是需要节点协同工作的无线传感器网络的一个关键机制。节点调度、 目标跟踪等都需要时钟同步提供支持。成本、体积和能耗是传感器网络时钟同步 第7 页 国防科学技术大学研究生院博士学位论文 的主要约束。传统的g p s 技术由于成本高、能耗大等限制不能很好地适用于无线 传感器网络。在设计面向无线传感器网络的时钟同步机制时，必须考虑能量高效、 可扩展性、鲁棒性以及稳定性等要求。 数据融合技术 节点冗余带来数据冗余，减少网络中传输的冗余数据能有效地节省能量。传 感器节点在收集数据的过程中，可利用节点自身的计算和存储能力进行数据融合， 去除冗余信息。但是数据融合技术在节省能量的同时，要以增加传输延迟以及降 低鲁捧性为代价。如何根据特定应用的需求，研究数据的缓存和融合策略以及多 传感器多数据类型环境下的数据融合方法是无线传感器网络的一个重要研究内 容。 数据管理技术 从数据存储的角度看，无线传感器网络可被视为一种分布