（计算机系统结构专业论文）无线传感器网络中基于局部能量消耗最优的分簇协议研究.pdf

摘要 摘要 随着通讯与计算技术的不断发展，无线传感器网络作在发挥越来越重要的作 用。无线传感器网络通过传感器节点收集并传输观测数据，最终将观测数据交付 观察者。它跟传统无线网络最大的区别在于，该网络是以数据为中心的，这种性 质使得无线传感器网络在许多应用中有非常广阔的i ，j 景。 在无线传感器网络设计中有许多重要问题，其中最重要的一个问题就是如何 节省能量，延长网络的生命期。无线传感器网络中的分簇协议是一项重要的节能 技术。分簇协议选择部分节点作为簇头节点，非簇头节点将观测数据交付簇头节 点后就可以进入休眠状态以节省能量，由簇头节点对数掘进行处理、融合和传递， 最终交付基站。这一策略的引入有效减小了非簇头节点的能量消耗。 然而如何对簇头节点的分布进行控制是一个需要解决的问题。在以往的分簇 协议中，通常先对协议进行设计，多次运行协议后得到使得网络能量消耗最小的 最佳簇头个数。协议将簇头个数控制在最佳簇头个数附近，并使簇头节点在观测 区域中随机分布或均匀分布。按照相同的方式安排簇头节点分命，忽略了区域的 局部能量消耗特征。本文根据各区域的局部能量消耗模型，控制簇头节点的分布， 实现局部能量消耗的最优化，减少并均衡全网能量消耗。 本文首先针对单跳分簇网络提出了基于局部能量消耗最优的分簇协议。协议 思想是各节点根据与基站的距离计算竞争半径，使半径内节点的平均能量消耗最 小；如果节点在自己的竞争半径内能量最大，则赢得竞选当选簇头。其次，针对 多跳分簇网络，研究了降低簇头能量消耗的最优下一跳距离：节点根据到基站的 距离和角度，确定使局部能量消耗达到最优的竞争半径，赢得局部竞争的簇头节 点以最优下一跳距离寻找下一跳路由。仿真实验表明，基于局部能量消耗最优的 分簇协议有效减少了节点的能量消耗，延长了网络的生命期。 本论文中有特色的工作体现在如下几个方面：1 引入区域局部能量消耗特征 不同的思想，对簇头节点分行进行控制，实现区域能量消耗最小化，减少并均衡 全网能量消耗：2 j 备多跳路由和局部能量消耗最优相结合，进一步均衡簇头节点 的能量消耗：3 协议只用到已知信息或局部信息，不需要多次运行网络求最优参 数，优化了网络配置过程。 关键词：无线传感器网络局部能量消耗最优非均匀分簇多跳路由 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m m u n i c a t i o na n dc o m p u t i n gt e c h n o l o g y ，w i r e l e s s s e n s o rn e t w o r k s ( w s n ) i sp l a y i n ga ni n c r e a s i n g l yi m p o r t a n tr o l e t h em o s to b v i o u s d i f f e r e n c eb e t w e e ni ta n dt r a d i t i o n a lw i r e l e s sn e t w o r kl i e si ni ti sad a t a - c e n t r i c n e t w o r k ，w h i c hm a k e si tb eu s e dw i d e l y t h e r ea r em a n yi m p o r t a n ti s s u e sa b o u tw s nn e e dt ob ea d d r e s s e d t h em o s t i m p o r to n e i sh o wt os a v ee n e r g ya n dp r o l o n gn e t w o r k l i f e t i m e c l u s t e r i n gp r o t o c o li s a ni m p o r t a n te n e r g y s a v i n gt e c h n o l o g y s o m en o d e sa r es e l e c t e da sc l u s t e rh e a d s c l u s t e rh e a d sa r er e s p o n s i b l ef o ra g g r e g a t i n gd a t aa n dd e l i v e r i n gt h e mt ob a s es t a t i o n t h ee n e r g yo r d i n a r yn o d e sc o n s u m ec a nb er e d u c e de f f e c t i v e l yb yt h i ss t r a t e g y h o wt oc o n t r 0 1t h ed i s t r i b u t i o no ft h ec l u s t e rh e a d si sap r o b l e mn e e dt ob e a d d r e s s e d n o d e si nd i f f e r e n tr e g i o nc o n s u m ee n e r g yd i f f e r e n t l y ，w h i c hw a si g n o r e d b yp r e v i o u ss t u d i e s i nt h i st h e s i s ，t h ed i s t r i b u t i o no fc l u s t e rh e a d si sc o n t r o l e d b a s e d o nl o c a le n e r g yc o n s u m p t i o nm o d e l ，t om i n i m i z el o c a le n e r g yc o n s u m p t i o n t h em a i ni d e ai sn o d e sc o m p u t et h ec o m p e t er a d i u sb a s e do nt h ed i s t a n c e b e t w e e ni ta n db a s en a t i o n ，t om i n i m i z et h ea v e r a g ee n e r g yc o n s u m p t i o nw i t h i nt h e r a d i u sr e g i o n n e x t ，a i m i n ga tm u l t i - h o pn e t w o r k ，s t u d yt h eo p t i m a ld i s t a n c et ot h e n e x th o p ，a n dc o m p u t et h ec o m p e t er a d i u sb a s e do nd i s t a n c ea n da n g l et ot h eb a s e s t a t i o n ，t om i n i m i z et h el o c a le n e r g yc o n s u m p t i o n s i m u l a t i o nr e s u l t sr e p r e s e n t e n e r g yi ss a v e da n db a l a n c e de f f i c i e n t l y ，a n dt h el i f e t i m eo fn e t w o r ki sp r o l o n g e d t h e r ea r es o m ec h a r a c t e r i s t i c si nt h i st h e s i sa sf o l l o w ：1 c o n t r o lt h ed i s t r i b u t i o n o fc l u s t e rh e a d s ，t om i n i m i z et h el o c a le n e r g yc o n s u m p t i o n ；2 c o m b i n e dw i t ht h e m u l t i - h o pr o u t i n g ，b a l a n c et h eg l o b a le n e r g yc o n s u m p t i o nm o r ee f f i c i e n t l y ；3 a l lt h e p a r a m e t e r s i sk n o w ni n f o r m a t i o no rl o c a li n f o r m a t i o n ，t oo p t i m i z et h en e t w o r k c o n f i g u r a t i o np r o c e s s k e yw o r d s ：w i r e l e s s s e n s o r n e t w o r k s ，m i n i m a l l o c a l e n e r g yc o n s u m p t i o n ， u n e v e n u n i f o r mc l u s t e r i n g ，m u l t i h o pr o u t i n g i i 中国科学技术大学学位论文原创，i 生声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：签字同期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之，学位论文著作权拥有者授权中国科学技术大学j 爿j 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 翼兰二名： | 了遂导师签名：丝作者签名：望! ! ：塑导师签名：，：蝗竺 签字同期：二型塑掣参签字同期：舡 第l 章绪论 第1 章绪论 无线f 感器嗍络作为一种探知客观世界的新兴技术，引起了学术界的广泛注 意，并且在各个应用领域发挥着越来越重要的作用。由于传感器网络存在许多特 性，与传统的无线刚络有很大区别，所以在这一领域有很多技术热点、难点需要 解决【1 】。 本章首先对本文选题的原因和背景进行总结和归纳。之后，介绍本文的研究 目的、研究方案、研究结果。最后给出本文的结构安排。 1 1 选题背景 2 0 世纪9 0 年代以来，随着嵌入式系统、无线通信、网络及微电子机械系统 ( m i c r o e l e c t r o m e c h a n i s ms y s t e m ，m e m s ) 等技术的快速发展，具有感知、计算和 无线网络通信能力的传感器以及由其构成的无线传感器网络( w i r e l e s ss e n s o r n e t w o r k ，w s n ) 引起了人们的极大关注。美国商业周刊和m i t 技术评述在预 测未来技术发展的报告中，分别将无线传感器网络列为2 1 世纪最有影响的2 1 项 技术和改变州= 界的l0 人技术之- 2 1 ，它将会对人类未来的生活方式产生深远影 响。 无线传感器网络通常被配置在遥远、危险或者人类不可达的区域，对环境中 某种现象进行观测【3 】。传感器节点在观测区域中被配置后，就以自组织的方式 形成一个无线网络。传感器节点对环境数据进行感知，并加以计算处理，通过无 线例络中的其他传感器节点，以多跳路由的方式将数据交付基站。基站是个特殊 的节点，它与互联网、移动通信网络或卫星网相连接。收到观测数据后，基站就 通过这些传统i 删络将数据交付用户。传感器i 叫络对客观1 = 界的观测能力，极大地 提高了人类认识客观世界地能力，也拓宽了现有网络的功能 3 】。 无线传感器网络与已有的传统无线网络( 如无线自组网a dh o c 网络、无线局 域网w l a n 和蜂窝移动电话网络) 有着明显不同的设计目标 3 】。传统无线网络 是布节点高速移动的条件下，为节点优化路由选择，最大化带宽的利用率以及提 供一定的质量服务保证；- 而传感器节点在被配置后基本固定不动，并且观测区域 通常无法接近，凼此传感器节点的能晟无法得到后续补充，如何节省节点能量， 延长网络的生命周期是传感器网络设计的核心问题。其次，深入的研究表明【4 】， 无线化感器网络与f 冬统无线网络具有不同的技术要求。传统无线网络的设计遵循 第l 章绪论 着“端到端”的边缘论思想 5 】，即所有与功能相关的操作都在终端节点上完成， 网络巾的其他节点仅仅负责数据包的转发，这是一种以数据传输为中心的网络模 式。无线传感器网络中的所有节点既是数据的收集者，又为数据转发提供路由， 刚络关心的是观测数据最终交付基站，而小是传感器节点之间能禽互相通信，这 是一种以数据为中心的网络模式。这些独特的设计只标和技术要求，使得无线传 感器l 叫络面临新的技术挑战。目前对无线传感器刚络的硼究热点主要集中在以下 几个方面 6 】：拓扑控制协议、路由协议、媒体接入控帛o ( m a c ) 协议、安全性问题 以及一些共降技术。 拓扑控制作为无线传感器网络的大研究热点难点，对无线传感器网络的性 能有着巨大的影n l 句 7 】。首先，拓扑摔制协议需要保证传感器节点对观测区域的 覆盖 7 】，以得到关于区域中环境数据的完整信息，并为传感器节点到基站之问 寻找通路。其次，由于无线传感器网络中传感器节点数景巨大，可以通过拓扑控 制减少上作节点，节省网络能量。再次，拓扑控制协议可以降低通信干扰，提高 m a c 层协议效率，优化路由协议，为数据融合提供拓扑基础。因此研究传感器 网络的拓扑控制协议具有罩要意义。 _ 兀线传感器网络的拓扑控制协议。n l 。以分为功率控制协议和睡眠调度协议两 大类 7 】。功率控制协议根捌拓扑控制的度嚣调节网络中书。点的发射功率，以节 省能量，从而彤成不同的拓扑结构。它包括以下拓扑控制协议：c o m p o w 8 1 、 l m a 9 】、l m s t i 0 】、c b t c 11 】、r & m 1 2 币f fd i s t _ r n g 1 3 】等。睡眠调度协议 根据拓扑控制的度量需要将网络中的一部分节点置为睡眠状态以节省能量，从而 使网络巾的工作节点形成不同的拓扑结构。根据拓扑结构是否具有层次性，睡眠 调度叻议义分为非层次型睡眠调度协议和层次型睡眠调度协议( 分簇协议) 7 】 习f 层次型睡眠调度协议包括协议：r i s 1 4 、m s n l 1 5 、l d a s 1 6 、a s c e n t 1 7 、 p e a s 18 】、p e c a s 1 9 】、c c p 2 0 、s p a n 2 1 ：分簇协议包括以下协议：l e a c h 2 2 ， e e c s 2 3 ，l d s 2 4 ，g a f 2 5 1 ，g b r 2 6 1 ，t o p d i s c 2 7 ，h e e d 2 8 】、h e e d m 2 9 并1 1 e e u c 3 0 等。 无线传感器网络的拓扑控制协议要保证数据传输和网络的连通性，要为传感 器节点和基站之问提供路由，所以在设计拓扑控制协议时都需要结合路由协议 【3 l 】。同自，j 已经提出了一些路由协议：f l o o d i n g 3 2 、g o s s i p i n g 3 3 】、t e e n 3 4 、 p e g a s i s 3 5 】、s p i n 3 6 】、d i r e c t e dd i f f u s i o n 3 7 】、r u m o r 3 8 】、g p s r 3 9 】、 g e a r 4 0 】、s a r 4 1 】和s p e e d 4 2 等协议。这些协议使收集到的信息通过单跳或 者多跳的方式到达基站，与拓扑控制协议相结合，高效完成网络中的数据收集任 务。 2 第1 章绪论 1 2 研究目的、方案和结果 分簇协议选择一部分节点作为簇头节点，收集非簇头节点牛成的环境数据， 对数据进行融合处理后，将数据直接、或通过其他簇头节点交付基站。由于非簇 头节点将数据交付簇头节点后即口j 进入睡眠状态，因此分簇协议可以有效减少网 络的能阜= 消耗 4 3 1 。 分簇协议中，降低簇内信通开销和降低簇头节点的能量消耗成为降低网络 能量消耗的关键。簇头节点的分布对簇内通信开销和簇头节点能量消耗具有重要 影n 向 4 3 】。在已有的分簇协议 2 2 - 2 9 q h ，通常先对分簇协议进行设计，多次运 行协议得到使得网络能量消耗最小的最佳簇头个数。协议通过各种手段控制簇头 个数分布在最佳簇头个数附近，并且簇头随机 2 2 】或均匀f 2 3 】地分布在观测区域 内。然而在无线传感器网络中，南于每个区域与基站距离不同，该区域的能量消 耗特征并不相l 司，按照相同的方式安排簇头分布，不满足每个区域的能量消耗特 征的要求，每个区域的能量消耗并不能达到最小，从而增加了整个网络的能量消 耗。因此如何控制簇头节点分布，使得观测区域内各区域的能晕消耗最小是个 需要解决的问题。 此外，引入多跳路由协议可以有效减少和均衡簇头节点的能量消耗，但在 以往的多跳分簇协议中，下一跳路由节点的选择往往带有盲目性 2 9 1 ，致使部分 路南节点过早失效。如何使簇头节点建立的多跳路由可以减少和均衡能量消耗是 另一个需要解决的问题。 本文考虑了一种基于局部能量消耗最优的网络分簇协议。在该协议中，结 合不同的路由方式，研究网络巾节点的能量消耗模型。在单跳方式的网络中，所 有簇头节点和基站直接通信，为使网络中各区域内节点的平均能量消耗最小，需 要考虑根据区域到基站的距离对簇头节点的分布加以控制，并由此提出 s m l e c c ( s i n g l e h o pm i n i m a ll o c a le n e r g yc o n s u m p t i o nc l u s t e r i n g ) 协议。该协 议中每个节点根据与基站的距离计算最优竞争半径，竞争半径内节点的平均能量 消耗最小。节点在竞争半径内进行局部竞争，如果节点的剩余能量在自己的竞争 半径内最大则成为簇头节点。山于节点的竞争半径不同，最后簇头节点在观测区 域内呈非均匀分布。 存多跳方式的网络巾，由于簇头节点不与基站直接通信，需要将数据交付 多跳路由的下一跳节点。选择下一跳节点和控制簇头节点分布都会影响观测区域 内的能= 晕= 消耗， 由此提出m - m l e c c ( m u l t i h o pm i n i m a l l o c a l e n e r g y c o n s u m p t i o nc l u s t e r i n g ) 协议。该协议首先确定簇头节点选择下一跳节点的方 式。根据此方式研究节点的能量消耗模型，确定最优下一跳距离。节点根据到基 站的距离和角度计算节点的最优竞争半径，半径内节点的平均能量消耗最小。能 1 。 第1 章绪论 量最大的节点最后在竞争半径内的局部竞争中获胜并当选簇头节点。簇头节点根 据下一跳节点的选择方式和最优下一跳距离选择某个簇头节点成为自己的下一 跳节点。簇头节点最后非均匀分布布观测区域内。 理论分析给出s m l e c c 协议和m m l e c c 设计依据，并证明这两个协议 的正确性和可行性，仿真实验表明s m l e c c 协议均衡了网络中不同区域内节点 的能量消耗，较其他甲跳协议，有效延l j = = 了甲跳嗍络的生命期。同时仿真实验还 表明m m l e c c 协议减少并更进一步均衡了网络中簇头节点的能量消耗，较其 他多跳分簇协议生命期有较大幅度的提高。 本文的牛要贡献体现在两个方面：第一，根据调研，这是第一篇将局部能 量最优化思想引入无线传感器网络拓扑控制协议设计中的文章，该思想最优化了 i 叫络中局部区域内节点的平均能量消耗。减少并均衡了仝网能量消耗：第二，结 合路由协议，考虑路由方。式对节点能最消耗模型的影响。将多跳路由和局部能量 消耗最优思想结合。进一步均衡了网络中各节点间的能量消耗。 1 3 本文结构 现在介绍一下本文的结构安排。第：二章主要介绍无线传感器网络的研究现 状，包j 舌无线传感器i 捌络的基本概念、特点以及当前硼i ：究的热点难点。其次对无 线传感器网络中的拓扑控制协议给出综述，重点介缁几个重要的分簇协议，详细 介绍其中的簇头控制技术；最后给出关于路由协议的综述。木文的主要工作就是 基于局部能量消耗最优的思想，结合不同的路南机制，设计分簇协议以优化网络 中的能量消耗。第三章主要阐述s m l e c c 协议的理论基础、协议设计、协议分 析以及仿真结果。第四章闸述m m l e c c 协议的理论基础、协议设计、协议分 析以及仿真结果。最后是本文的总结与研究展望。 4 第2 章研究现状 第2 章研究现状 随着传感器技术和无线通讯技术的发展，无线传感器网络逐渐成为研究热 点。它在民用和军用领域有着广阔的应用前景。但由于无线传感器存在着能量受 限、以数据为中心等诸多不同于传统无线网络的特点 1 】，在能实际应用之前， 还有许多问题需要解决。 本章将对与本文有关的背景知识进行介绍。首先概述无线传感器网络的基 本概念，包括无线传感器网络的结构、协议栈、特点、应用以及目前的研究热点 等。其次对拓扑控制协议的研究进展进行综述，对几个重要的分簇协议做出深入 讨论。最后对现有的路山协议做简要介绍。 2 1 无线传感器网络综述 2 1 1 无线传感器网络体系结构 无线传感器网络系统包括三种类别的节点：传感器节点、基站和管理节点 【3 】。如图2 1 所示，传感器节点被配置在观测区域中，对观测区域中的环境数据 进行感知。在对收集的数据进行本地处理后，通过其他传感器节点，以多跳的方 式，将数据交付基站。基站通过互联网、移动通信网络或卫星将数据发送给管理 节点。 舰测l 域传感；i ： 仃点 图2 i 无线传感器网络体系结构 传感器节点1 办议十分有限的能量，它的处理能力、存储能力、和通讯能量相 对比较薄弱。传感器节点在观测区域中兼顾传感器和路由器双重功能 6 】。在对 5 笕2 章研究工见状 观测区域中的环境数据进行感知的同时，还要对数据进行存储、处理和转发。因 此对传感器节点的研究是口前研究传感器网络的重点。关于传感器节点的结构将 存下节给出详细介绍。 基站通常能量刁i 受到限制，并且它的处理能量和存储能力都较传感器节点 强。基站是一个类似网关的节点 1 】，一方面基站通过无线传感器网络特有的网 络协议与传感器节点进行通信：另方面，基站通过已有的嗍络协议与互联网中 的某个箭珲：市点进行仔务下达和数据交付探作。它既口j 以是个功能增强的传感器 节点，也可以是一个没有感知功能仅仅用米连接无线传感器网络和外部网络的网 芙设备 6 】。 2 1 2 传感器节点的结构 传感器节点包括传感器模块、处理器模块、无限通讯模块和能量处理模块四 个部分【4 4 】，如图2 2 所力。传感器模块负责感知和收集观测区域中的环境数据； 处理器模块除了负责整个传感器节点的运行，还负责对数据进行融合和处理：无 线通讯模块负责数据的接收和发送；能量处理模块负责能量的管理，传感器节点 通常使用微型电池。 恒ih c 叫h 圈忙阿 t “一覃。一罩 能h 供应模块 图2 2 传感器节点结构 4 4 】 2 1 3 无线传感器网络协议栈 与传统网络的分层协议相似，在无线传感器网络协议栈中包括物理层、数 据链路层、网络层、传输层和应用层 3 】，如图2 3 1 6 所示。 物理层负责无线电收发和信号调制： 数据链路层负责成帧、帧检测、媒体访问控制和着错控制： 嘲络层负责路由的生成、维护和选择； 传输层保证通信服务质量，负责数据流的传输控制； 一些用于监测任务的软件位于应用层， 6 第2 章研究现状 时间同步和定位子层既要为传输层以下的协议提供必要的信息支持，又要通 过传输层以下的协议与别的传感器节点进行协商。 图右边的各种机制在与其相关的层中发挥各自的作用： 拓扑控制机制，通过路由层和数据链路层控制网络拓扑结构； q o s 机制通过拓扑控制机制实现传输控制层的通信服务质量； 能量安仝移动机制。负责物理层以上各层的能量安全移动事务的管理； 网络管理机制贯穿网络的所有层，各层都需要网络管理的支持。 图2 3 无线传感器网络协议栈【6 】 2 1 4 无线传感器网络的特点 传感器节点具有的能冒= 、计算能量、存储能力和通信能力非常有限。传统 无线网络的首要设计目标是提供高服务质量和高效的带宽利用率，其次才考虑能 ：晕= ；而无线传感器网络的首要设计目标是能量的高效使用，这也是无线传感器网 络和传统网络最罩要的区别之一。无线传感器网络具有的特点有【6 ： ( 1 ) 硬件资源有限。由于受到价格，硬件体积，功耗等限制，传感器节点的存 储能力，处理能力都较弱。 ( 2 )电源有限。传感器节点通常由电池供电，且无线传感器网络通常配置在人 无法到达的区域，冈此无法保证能量的后续补充。 ( 3 ) 光中心。无线传感器网络中所有节点地位平等，没有严格的中心节点。无 线传感器网络利用扪邻节点间的相互协作来进行通信，具有很强的协作性。 ( 4 )白组织。对网络不进行预设。节点通过分层协议和分布式算法协调各自的 监控行为，节点开机后快速、自动形成一个独立的无线刚络。 ( 5 ) 多跳路由。无线传感器网络中，节点只能同它的邻居直接通信。如果想和 射频范围之外的节点进行通信，则需要通过中间节点进行路由。普通节点充当路 7 第2 章研究现状 l 【j 设备。 ( 6 ) 动态拓扑。节点可能因为能量耗尽或故障退m 网络，也可能为增加数据精 度加入网络，或有可能节点存网络中移动，因此无线传感器网络具有动态拓扑组 织功能。 ( 7 ) 节点数量多。为得到精确的环境数据，无线传感器网络中通常配置大量节 点。高密度的刚络还能保证例络的容错性，能量有效性。 ( 8 ) 以数掘为中心的网络。无线传感器网络是仟务型网络【3 】。用户使用传感 器网络查询事件时，关心的是数据最终可以传递到终端，而不是数据被哪些传感 器节点共享。 2 1 5 无线传感器网络的应用 无线传感器网络的应用前景非常广泛【3 】，能够广泛应用于军事，环境监测和 预报 4 5 ，4 6 】，健康护理 4 7 】，建筑物状态监控，复杂机械监控，城市交通 4 8 】， v f 日- j 探索 4 9 】，大型车间和仓库管理，以及机场，大型工业远去的安伞监测等领 域。随着无线传感器网络的深入研究和j 泛应用，无线传感器网络将逐渐深入到 人类生活的各个领域。 2 1 6 无线传感器网络的研究热点和难点 无线传感器网络不i 刮于传统网络的特征，使得它有很多关键技术有待发现和 研究。无线传感器网络当前研究的热点、难点包括拓扑控制、网络协议、网络安 全、时间同步、定位技术、数据融合等【6 】。 ( 1 ) 拓扑拧制【7 1 拓扑控制协议可以生成良好的拓扑结构，可以提高路由协议和m a c 协议的 效率为数据聚合、时间同步、定位技术提供拓扑基础 7 】。而且拓扑控制还是 一项重要的节能技术。因此拓扑控制是硼i ：究无线传感器l 叫络的核- t l , 技术之一，也 是本文重点研究的内容。 拓扑控制问题可以描述为在保证一定的网络覆盖度和连通度的前提下，通过 改变节点的发射功率或使得节点轮流工作的方式，减少节点的能量消耗 7 】。拓 扑控制分为功率捧制和睡眠调度两种。功率摔n t , j j 义存保证网络覆盖度和连通度 的前提下，调节节点的发射助牢，减少节点的发送功率，均衡节点甲跳可达的邻 居数目【7 】。已绎提 了c o m p o w 8 等时功率分配算法，l m a 9 等基于节点 度数的算法，l m s t i o 】、c b t c 1l 】、d i s t _ r n g 1 3 】等基于邻近图的近似算法。 睡眠调度机制，则是对节点进行调度，使得一部分节点处于休眠状态以节省能量， 8 笕2 章硎究现状 而另一部分节点保持工作状态，继续对网络q j 的环境数据进行收集和路山【7 】。 睡眠调度机制又分为非层次型的睡眠调度机制和层次型的睡眠调度节制。层次型 的睡眠凋度机制是让一些节点作为簇头节点，由簇头节点接收簇内节点收集的环 境数据，并将它们路由至基站；其他非簇头节点可以暂时关闭通信模块，进入休 眠状态以节省能量 7 】：月前提出了t 0 p d i s c 【2 7 】成簇算法，改进的g a f 2 5 虚拟 地理嘲格分簇算法，以及l e a c h 2 2 弄- e ih e e d 2 8 等自组织成簇算法。 ( 2 ) 路由协议f 8 】 网络层的路由协议决定节点将环境数据向基站交付时的传输路径。无线传感 器嘲络巾，路由协议巾节省单个节点的能量消耗是需要考虑的问题，然而整个刚 络能量的均衡消耗则是设计的重点，延长整个网络的生存期是路由协议设计的目 标。九线传感器网络是以数据为中心的，因此建立路时是寻找环境数据的收集 节点到荩站之间的转发路径，而不是在传感器节点之间寻找路由。目前提出了多 种类型的传感器网络路由协议。如定向扩散【3 7 】和谣传路由 3 8 等基于查询的路 由协议，g e a r 4 0 等基于地理位置的路由协议，s a r d i i 并l is p e e d 4 2 等支持 o o s 的路由协议。 ( 3 ) 媒体访问控制协议 5 0 1 数据链路层的媒体访问控制协议用来连接物理层和网络层，控制传感器节点 的通信过程和工作模式 5 0 】。 无线传感器网络的m a c 协议和传统网络的m a c 协议不同，首先要考虑的 就是节省能量。存m a c 层的能量浪费主要表现在空闲侦听，接收不必要数据和 碰撞重传等 5 0 。为了减少能量的消耗，m a c 协议通常采用“侦听睡眠”交替 的无线信道侦听机制，传感器节点在需要收发数据时才对无线信道进行侦听，没 有数据需要收发时就j s 量进入睡眠状态 5 0 1 。近期提出了s - m a c 5 l 】、t - m a c 5 2 】 和s i r 【5 3 】等基于竞争的m a c 协议，t r a m a 5 4 、d m a c 5 5 着i - in 期性调度等 时分复用的m a c 协议，以及c s m a c a 与c d m a 相结合、t d m a 和f d m a 相 结合的m a c 协议。 ( 4 ) 网络安全 5 6 】 无线传感器网络作为任务型网络，因此无线传感器网络要满足安全特性，必 须要保证：任务执行的机密性，数据产牛的可靠性，数据融合的高效性以及数据 传输的安全性1 5 6 。无线传感器网络的安全保证与传统网络在许多方面有很大的 不同。首先，实现安全需要的算法必须较为简单，过于复杂的算法不适合无线传 感器网络对算法简单高效的要求：其次，要针对传感器节点有限的计算资源和能 量资源，优化算法设计；另外，安全算法要顾及全网和单个节点的安全特性，使 9 第2 章司f 究现状 得网络和节点都排除安伞隐患。 无线传感器网络s p i n s 安全框架 5 7 】在机密性、点到点的消息认证、完整性 鉴别、新鲜性、认证广播方面定义了完整有效的机制和算法。安= 拿= 管理方面目前 以密钥预分布模型作为安全初始化和维护的主要机制，其中随机密钥对模型 ( 5 8 1 ，q - c o m p o s i t e 随机密钥对模型【5 9 】是最有代表性的算法。 ( 5 ) 时间同步 6 0 】 时间同步是使无线传感器网络r f l 节点协作工作的一个关键机制。i ：1 前已提出 了多个时问同步机制，其中r b s 6 1 】、t i n y m i n i - s y n c 6 2 和t p s n 6 3 是三个 基奉的同步机制。r b s 机制是基于接收者一接收者的时钟同步：一个节点广播 一个参考分组，广播范罔内的两个节点分别采用本地时钟记录参考分组的到达时 间，通过交换记录时间来实现它们之间的时钟同步。t i n y m i n i s y n c 是简单 的轻量级的同步机制：假设节点的时钟飘逸遵循线性变化，那么可通过交换时间 标记分组来估计两个节点问的最优匹配偏移量。t p s n 采用层次结构实现整个网 络节点的时间同步：所有节点按照层次结构进行逻辑分级，通过基于发送者一接 收者的节点对方式，每个节点能够与上一级的某个节点进行i 司步，从而实现所有 节点都与根节点的时间同步。 ( 6 ) 定位技术 6 4 】 对收集环境数据的传感器节点进行定位是传感器网络最基本的功能之一。定 位机制必须满足自组织性，健壮性，能量高效，分布武计算等要求 6 4 】。 定位技术的基本思想足位置未知的节点根据少数信标 6 4 】节点，根据定位算法确 定自身的位置。信标节点的位置是已知的。根据定位过程巾是畲需要测量节点之 间的距离或角度，无线传感器网络中的定位机制分为基丁- 距离的定位和距离无关 的定位。根据测量节点间距离或方位时采用的方法，基于距离的定位分为基于 t o a 的定位【6 5 】、幕。- f t d o a 的定位【6 6 】、荩丁a o a 的定位 6 7 1 、荩tr s s i 的 定位【6 8 】等。目前提出的距离无关的定位机制主要有质心算法 6 9 】、d v - h o p 算法 【7 0 】、a m o r p h o u s 算法【7 1 】、a p i t 算法【7 2 】等。由于距离无关的定位机制刁i 需要 对绝对距离或方位进行测量，降低了对节点硬件的要求，更适合于节点价格低廉、 节点数量巨人的无线传感器i 叫络。但是距离无关的定位机制定位误差相应有所增 加，但是其定位精度能够满足多数无线传感器网络应用的要求，是月前重点关注 的定位机制。 ( 7 ) 数据融合 7 3 】 减少路由过程中转发的数据量能够有效地节省能量，冈此在各个传感器节点 收集数据的过程中，可利用节点的本地计算和存储能力对数据进行融合，避免冗 1 0 第2 章珂1 ：究i 见状 余信息的转发，以达到节省能量的目的【7 3 】。 数据融合技术可以与传感器网络的多个协议层次进行结合【7 3 】。在应用层， 可以利用分布式数据库对数据的冗余度进行改善，对采集到的环境数据进行筛 选，实现相关数据的融合：在例络层r f l ，很多路由协议均结合了数据融合机制， 以期减少数据传输量，减少节点通信过程的能量消耗；此外，还有独立于其他协 议层的数据融合协议层，在不损失信息完整性的基础上，减少m a c 层的发送冲 突和头部丌销达到节省能量的目的。 数据融合技术祉节省能量、减小信息冗余度的同时，可能会造成其他性能的 下降 7 3 】。首先是延迟的增加，根据融合度对路南进行选择、对环境数据进行融 合操作、等待其他数据前米融合，这三个点都有可能增加网络延迟。其次是鲁棒 性的下降，无线传感器嗍络相对于传统i 叫络有更高的节点失效率以及数据丢失 率，数据融合可以大幅度降低数据的冗余性，但对信息进行筛选可能丢失更多的 信息量，因此也降低了网络的鲁棒性。 ( 8 ) 数据管刊a 7 4 】 从数据存储的角度看，无线传感器网络可以被当成是一种分布式数据库。可 以将例络中存储数据的逻辑形式与网络中存储数据的物理形式进行分离，使得无 线传感器网络的用户只需要关心数据查询的逻辑形式，通过逻辑形式得到所需数 据 7 4 1 。以数据库的方法在无线传感器网络中进行数据管理。 传感器网络的数据管理系统的结构一i 要有集中式、半分布式、分布式以及层 次式结构【7 4 】，目前大多数研究工作均集中在半分布式结构方面。传感器网络中 数据的存储分为网络外部存储，本地存储和以数据为中心的数据存储三种方式。 以数据为中心的存储方。式可以降低能量消耗，提高通信效率。基于地理散列表的 方法【7 5 】是一种常用的以数据为中心的数据存储方式。无线传感器网络的数据查 询语言多采用类s o l 语言 7 4 】。伶询操作可以按照集中式、分布式或流水线式查 询进行设计。集中式查询由于传送了冗余数据而增加了能量消耗：分布式查询利 片j 聚集技术日j 以显著降低通信开销；而流水线式聚集技术可以提高分布式查询的 聚集正确性。 2 2 无线传感器网络拓扑控制协议 2 2 1 拓扑控制分类 ( 1 )拓扑控制算法从管理方式可划分为节点功率控制和睡眠调度控制两类。其 巾节点功率控制机制指通过调节节点的发射功率，以保证网络连通，同时尽量避 第2 章研究现状 免隐终端和暴露终端 7 6 】问题。睡眠调度机中部分节点进入休眠状态以达到节能 的日的。功率控制适用于网络规模相对较小的网络，而睡眠调度适用于部分节点 可以实行休眠策略的大规模网络。 ( 2 ) 从拓扑的形成依据来看，算法可分为几何方式和概率方式 7 7 】。几何方式 以某种特定结构( 如最小生成树( m i n i m u ms p a n n i n gt r e e ，m s t ) 、r n g 图 【7 8 ( r e l a t i v en e i g h b o r h o o dg r a p h ) 、g g l 蛩 7 8 ( g a b r i e lg r a p h ) 、d t i 蛩 7 8 】( d e l a u n a y t r i a n g u l a t i o n ) 及y g 图 7 8 】( y a og r a p h ) 等来建立网络拓扑，概率方式( 如几何随机图 【7 9 】、占位理论 8 0 】、连续渗流理沦 8l 】) 指讣算具有较好性质时的节点功率和 度值，j f ：按此形成拓扑： ( 3 )从算法的实现需求看，可分为基于精确地理位置的算法、基于方位信息的 算法和基于邻居集信息的算法： ( 4 ) 根据最终生成拓扑中节点功率是否致，可区分为临界传输功率( c r i t i c a l t r a n s m i t t i n gr a n g e ，c t r 8 2 】) 算法和差异传输功率分配算法： ( 5 ) 从算法的执行频率，- 日j - 把算泫分为周期性执行算泫与单数据包( p e r - p a c k e t ) 调整的拓扑控制算法： ( 6 ) 根据算法是否考虑节点的剩余能量问题，。口j 分为基于能量的拓扑控制算法 和非基于能量的拓扑控制算法： ( 7 ) 根据算法的实现需全局网络信息还是局部网络信息，可分为基于全局信息 的算法和基于局部信息的算法。 2 2 2 拓扑控制的设计目标 拓扑控制研究的问题是：在保证一定的网络连通质量和覆盖质量的前提下， 以延长网络的生命期和实现负载均衡为主要目标，对通信_ t 扰、网络延迟、简单 性、可靠性、可扩展性等其他性能进行综合考虑，形成一个优化的i 叫络拓扑结构。 更好地为路由等协议服务。下面介绍拓扑控制中一般要考虑的设计日标 7 】： ( 1 )覆盖：覆盖可以看成是对无线传感器网络服务质量的度量。覆盖要解决的 问题是网络对物理世界的感知能力【8 3 】。覆盖问题可以分为区域覆盖、点覆盖和 栅栏覆盖( b a r r i e rc o v e r a g e ) 【8 4 】，区域覆盖研究对目标区域的覆盖( 取得环境数 据) 问题；点覆盖研究对一些离散的目标点的覆盖问题；栅栏覆盖研究运动物体 穿越网络部署区域被发现的概率问题。如果目标区域中的任何点都被k 个传感 器节点监测，就称例络是k 覆盏的，一般要求目标区域的每一个点至少被一个节 点监测，巳i ji 覆盖。覆薷是拓扑控制的基本问题。 ( 2 ) 连通：传感器网络一般是人规模的，而传感器节点地通信范围有限，所以 传感器节点收集到的环境数据一般要以多跳的方式交付基站。这就要求拓扑控制 1 2 第2 章研究现状 必须保证网络的连通性。如果至少要去掉k 个传感器节点才能使网络不连通，就 称网络是k 连通的，拓扑控制一般要保证网络是连通( 1 连通) 的。 ( 3 )网络生命期：网络生命期有多种定义一般将网络生命期定义为直到死亡 节点的百分比低于某个阀值时的持续时间 8 5 】。也可以认为网络只有在满足一定 的覆盖质量、连通质量、某个或某些其他服务质量时才是存活的 8 6 。最大限度 地延长网络的生命期是一个十分复杂的问题，它一直是拓扑控制研究的主要目 标。 ( 4 ) 吞吐能力：设目标区域是一个凸区域，每个节点的吞吐率为兄b i t s s ，在理 想情况下，则有关系式 8 7 】： 名一1 6 a w 幸l b i t s 刀2 胛， 由此可以看出通过功率控制减小发射半径和通过睡眠调度减小工作网络的规模， 在节省能量的同时，可以在一定程度上提高网络的吞吐能力。 ( 5 ) 干扰和竞争：减小通信干扰、减少m a c 层的竞争可以有效延长网络的生 命期。对于功率控制机制，网络无线信道竞争区域的大小与节点的发射半径，| 成 fl 匕 8 8 】，所以减小，就可以减少竞争。睡h 民调度显然也可以通过使尽可能多的节 点睡眠来减小干扰和减少竞争。 ( 6 )网络延迟：当网络负载较高时，低发射功率会带来较小的端到端延迟：而 在低负载情况下，低发射功率会带来较大的端到端延迟【8 9 。 ( 7 ) 拓扑性质：在设计拓扑控制( 特别是功率控