（通信与信息系统专业论文）无线传感器网络k重覆盖算法的研究.pdf

摘要 覆盖问题是无线传感器网络的基本问题，它是整个任务得以继续进行的基础。最 优覆盖是无线传感器网络应用的一个基本问题，是提供监测和目标跟踪服务质量的一 种度量。如何实现最优覆盖是网络拓扑管理的关键内容，与能量高效和可靠监测两方 面都直接相关。人们通常需要网络在完成监测任务的自，j 提下，尽量节省能耗以延长网 络寿命。覆盖反映了网络监测和实现目标跟踪的质量效果。覆盖问题已引起了业界越 来越多的关注。 本文介绍了无线传感器网络的覆盖与连通相关技术，对于无线传感器网络覆盖所 涉及的问题做出了详细的概述，说明了无线传感器网络覆盖亟待解决的问题，并给出 了一种基于k 重覆盖的c g s ( c o n t r o l l e dg r e e d ys l e e p ) 算法。同时对c g s 算法进行 改进，采用感知半径不等的传感器网络覆盖方式，并利用改进后的k n cc g s 算法得 到更符合于实际应用的网络覆盖率与生命期。 关键词：k 重覆盖c g s 算法k - n cc g s 算法覆盖率生命期 a b s t r a c t c o v e r a g ei st h eb a s i cp r o b l e mi nw i r e l e s ss e n s o rn e t w o r k s ；i ti st h ef o u n d a t i o nt h a tt h e w h o l em i s s i o nc a nc o n t i n u et ob ec a r r i e do n t h eb e s tc o v e r a g ei st h eb a s i cp r o b l e mo ft h e a p p l i c a t i o ni nw i r e l e s ss e n s o rn e t w o r k s ；i ti s am e a s u r e m e n to fs u p p l y i n gi n s p e c t i o na n d s e r v i c eo ft a r g e tt r a c k i n g h o wt oa c h i e v eo p t i m a lc o v e r a g ei sk e ye l e m e n t so ft h en e t w o r k t o p o l o g ym a n a g e m e n t ，a n di ti sr e l a t e db o t he n e r g ye f f i c i e n ta n dr e l i a b l em o n i t o r i n gd i r e c t l y i tu s u a l l yr e q u i r e st h ec o m p l e t i o no ft h em o n i t o r i n gt a s ko ft h en e t w o r ku n d e rt h ep r e m i s eo f s a v i n ge n e r g yc o n s u m p t i o na sm u c ha sp o s s i b l ei no r d e rt oe x t e n dt h en e t w o r kl i f e t i m e c o v e r a g er e f l e c t st h en e t w o r km o n i t o r i n ga n dr e a l i z a t i o no ft h eq u a l i t yo ft h ee f f e c to ft a r g e t t r a c k i n g c o v e r a g eh a sa t t r a c t e dm o r ea n dm o r ea t t e n t i o ni nt h er e l e v a n tf i e l d s t h i sp a p e rp r e s e n t st h ec o v e r a g ea n dc o n n e c t i v i t yp r o b l e m so fw i r e l e s ss e n s o rn e t w o r k s ， m a k ead e t a i l e dt ot h ec o v e r a g ep r o b l e m so fw i r e l e s ss e n s o rn e t w o r k s ，o u t l i n eo nr e q u i r i n g u r g e n ts o l u t i o no fw i r e l e s ss e n s o rn e t w o r kc o v e r a g ei s s u e s ，a n dg i v e sac g s ( c o n t r o l l e d g r e e d ys l e e p ) a l g o r i t h mb a s e dk - c o v e r a g e ，w ea d o p tt o d i f f e r e n c es e n s i n gr a d i u sr a n g e c o v e r a g em o d e u t i l i z i n gt h em e n d e dk n cc g sa l g o r i t h mt og a i nt h em o r ei nl i n ew i t ht h e p r a c t i c a la p p l i c a t i o no fn e t w o r kc o v e r a g er a t ea n dl i f e t i m e k e yw o r d s ：k c o v e r a g ec g sa l g o r i t h mk n cc g sa l g o r i t h mc o v e r a g er a t e n e t w o r kl i f e t i m e 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，无线传感器网络k 重覆盖算法的 研究是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中已 经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作 品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 作者签名：西圣终! 刍年三月堡同 。；r c r 1 一一一 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版 权使用规定”，同意长春理工大学保留并向中国科学信息研究所、中国优秀博硕 士学位论文全文数据库和c n k i 系列数据库及其它国家有关部门或机构送交学 位论文的复印件和电子版，允许论文被查阅和借阅。本人授权长春理工大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印 或扫描等复制手段保存和汇编学位论文。 作者签名：五墨鸳皇3 年- k h d h 指导导师签名： 年互月么 1 1 研究背景及研究的意义 第一章绪论 近年来，随着微电动机械的系统、数字电子技术的发展，无线通信也促进了低成本， 低功率和多功能传感器件的发展。这些设备可以自发地聚集、处理、和传送关于它们 周围环境的信息。当大量的节点协作，使用无线通信和非对称，多对的数据流程进 行通信，它们就构成无线传感器网络( 或简单传感器网络) 。 无线传感器网络( w s n ) 的应用研究被认为是2 1 世纪的一项挑战性科研课题，在 监控和军事领域具有重要的应用价值，如目标跟踪、入侵检测、气候监测、灾难管理 和战场侦查等。无线传感器网络是由部署在观测环境附近的大量微型廉价低功耗的传 感器节点组成，通过无线通信方式形成一个多跳的网络系统。作为一种全新的信息获 取和处理技术，它可在很多应用领域实现复杂的大规模监测和跟踪服务。 能够很好的理解和表征无线传感器网络是非常重要的，它可以在适用于不同的情 景来更好的帮助我们去设计和使用无线传感器网络，这就是覆盖问题。覆盖问题是无 线传感器网络的一个基本问题。通常覆盖反映了一个区域怎样能很好的审视传感器网 络的监控或跟踪。无线传感器网络的覆盖代表了网络能够提供的服务质量，因此，覆 盖是传感器网络可以提供服务质量的一个重要标准。例如：感兴趣的区域怎样被传感 器节点所监测到? 对于监测入侵目标传感器网络的效率怎样? 新技术在带来应用的同时，也带来了新的研究问题。传感器网络一个首要的目的 就是在感知区域内尽可能有效的监测目标，完全覆盖目标区域，以便使一个事件或一 个现象不被侦查到可能性非常小。因此，我们要在目标区域内放置一定数量的节点， 使区域中的每一个点至少都能被一个传感器节点所覆盖到，这样可以避免节点的重复 放置，提供高质量的覆盖。第二个问题就是能量，传感器节点由a a 电池提供能量， 节点工作的时间是有限的。而传感器网络通常都是被设计成比单个节点工作时问长许 多倍，多数节点的能量只能维持1 0 0 1 2 0 小时( 4 5 天) ，但网络的生命期需要维持几 个月。众所周知，当节点处于休眠状态，耗能仅是工作状态的0 1 。在网络中尽可能 使节点的占空比要低，以延长网络的生命期，因此，设计合理的调节节点工作状念的 算法是至关重要的。 在很多文献罩，都提到一个重要的问题：节点怎样能很好的监测物理区域? 换句话 说，在目标区域每一个位置怎样能至少被一个节点所覆盖? 为了满足准确的分类、跟 踪、和入侵侦察的目的，一些网络需要多重覆盖( 每一个区域至少被k 个节点所覆盖) 而不只是一重覆盖。当目标区域能够保证k 重覆盖并且仍然连通。那么，这个网络就 是一个完全的k 重连通覆盖。如果网络不是连通的，节点就不能向基站传输信息。 k 重覆盖的问题可以在许多领域中得到应用。在一些网络中需要有很好的覆盖，因 此，在网络中采用经济实用的算法很少的节点是非常必要的，同时也可能节省能量， 延长网络生命期。有效的调节算法需要调节节点的工作和休眠的状念，以提供持续的 网络服务【2 1 。 传感器节能覆盖问题的研究目前在国际上，特别是在美国十分热。覆盖问题是无 线传感器网络整个任务得以继续进行的基础，主要研究传感器监测物理空问的效果程 度，在网络体系结构的层次上，它可视为网络层的研究范畴。最优覆盖是无线传感器 网络应用的一个基本问题，是提供监测和目标跟踪服务质量的一种度量。如何实现最 优覆盖是网络拓扑管理的关键内容，与能量高效和可靠监测两方面都直接相关。人们 通常需要网络在完成监测任务的6 订提下，尽量节省能耗以延长网络寿命。覆盖反映了 网络监测和实现目标跟踪的质量效果。覆盖问题已引起了业界越来越多的关注。 1 2 研究内容 在构建无线传感器网络时，覆盖是无线传感器网络的基本问题之一，即如何部署 传感器网络节点，在保证一定的服务质量( q o s ) 条件下，达到网络覆盖范围最大化。 对无线传感器网络覆盖的测量能够使我们了解是否存在监测和通信盲区，了解被监测 区域的覆盖情况，从而重新调整传感器节点分布或者在将来添加传感器节点时可采取 的改进措施。更为广泛的是，我们还可以通过调整网络覆盖的密度，对被监测区域中 重要地区设置热点，部署更多的传感器节点，保证测量数据的可靠性。因此，网络覆 盖已不单纯是为了通信覆盖和监测区域覆盖，而是为了满足一定的应用需求。一般来 说，服务质量是衡量无线传感器网络覆盖的度量值。 如何部署节点才能实现网络的覆盖? 传统的有线网路和无线a dh o c 网络，可以通 过安放固定静态节点( 基站) 来实现网络覆盖，而无线传感器网络与应用有直接的关联， 覆盖的区域可能是静态环境( 如某生念领域的监测) ，也可能是特殊或恶劣的环境( 如火 灾现场、生化试验区域或者人迹罕至沙漠甚至外星球) 。在后一种情况下，节点的部署 往往是一个自动化的过程，通过飞行器将节点抛洒至被监测的区域，节点之问通过无线 链路建立通信环境，从而构建一个自组织网络【j j 。 c h u a n g 和y t s e n g ，在应用需要较强监测能力和较高容错率的情况下定义了一个 判断性的覆盖问题，目的是判断网络中的每一个点是否都在k 个传感器节点的覆盖之 下( k 是预先指定的值) ，每个节点的覆盖区域可以是任意大小。该工作提出了一个多项 式时| 日j 的算法，该算法可以很容易的转换为分布式算法。 本文提出了在保证无线传感器网络k 重覆盖的前提下，可以令网络中的冗余节点 休眠的可控制贪婪休眠算法，使占空比( 节点工作时间与休眠时l 、日j 的比值) 尽可能小。节 点可根据需要决定是否休眠。因此，减少了能量的损耗，延长了网络的生存期【4 1 。 1 3国内外研究现状 无线传感器网络一般具有高密度部署和节点能量受限的特点，通常采用工作节点 密度控制算法和节点状态调度机制，以达到在保证覆盖的自，j 提下减小能耗和延长网络 寿命的目的p y 舯j 。 在文献【8 9 j 中提出求解最大覆盖集的方法，将所有的传感器节点分成若干个不相交 的覆盖集( c o v e rs e t ) ，每个集合中的节点都可以独立地完成区域监测任务，这些集合 中的节点按轮次顺序执行区域监测任务。在文献1 8 j 中，s l i j e p c e v i c 等人证明了计算最大 的覆盖集是一个n p 完全问题，文献i 抚9 】分别提出了m o s t c o n s t r a i n e dl e a s t c o n s t r a i n i n g 算 法和基于g r a p h c o l o r i n g 近似算法。文献【8 ，9 j 提出的算法都是集中式的，并不适合传感器 节点数量众多的情况，而且两种算法都要依赖传感器节点的位置信息计算覆盖集。 x u 等人在文献1 6 j 中提出g a f ( g e o g r a p h i c a la d a p t i v ef i d e l i t y ) 算法。在g a f 算法中，每 个节点根据自己的物理位置信息，将整个区域划分为若干个格子( g r i d ) ，其大小必须保 证相邻格子中任何一对节点可以直接通信。因此，任何时候，只需在每个格子中选择 一个节点作为活动节点转发数据包，而其他节点进入节能睡眠状态就可以实现通信。 但是，g a f 算法并没有考虑到网络覆盖的问题。 t i a n 等人在文献1 6 j 中提出了基于节点状态调度的分布式覆盖算法，其中的免职合格 规贝j j ( o f f - d u t ye l i g i b i l i t yr u l e ) 可以根掘节点的物理位置信息或利用有向天线获得信号达 到角度来计算节点与其邻居的覆盖关系，选取工作节点。很明显，依赖于g p s 或a o a 信息，对于传感器来说是非常耗能且昂贵的。此外，免职合格规则没有考虑节点覆盖 区域可能出现过多的重叠，使得选出的工作节点数量过多，造成额外的能耗。文献i ll j 证 明了这种基于节点活动调度的算法是低效的。 y e 等人在文献i 列中提出了基于探测( p r o b i n g ) 的密度控制算法p e a s 。p e a s 算法 是基于探测机制的，也就是说，每个睡眠节点在一定时问内、在其探测范围内发送广 播消息p r b ，任何收到消息的工作节点返回应答消息。若节点收到应答消息，则进入睡 眠状念，工作节点继续工作，直至其能量耗尽或物理失效，否则，睡眠节点进入工作状 态。节点的物理位置用于计算节点探测范围和所要求的节点密度。显然，p e a s 算法中 的某些节点可能持续工作，导致其过早地死亡，整个网络中的节点能耗不均匀，影响 了覆盖质量1 4 。 文献【陀】中提出了一种基于概率而不是基于位置信息的分析节点冗余的数学方法。 根据该方法，节点可以根据自身感知半径内的邻居节点数量计算出自身成为冗余节点 的概率。由于不需要配备g p s 或有向天线，所以，节点的成本得到了控制；此外，也 不需要通过消息交换来获取节点的位置信息，所以减轻了传感器网络系统的通信丌销 然而，由于绝大多数节点的感知硬件和通信部件是完全独立的两个模块，即通信半径 和感知半径不一致。因此，要知道节点感知半径中的邻居节点数量，需要有专门的硬件 进行判断，这无疑要增加硬件的成本。 1 4 论文结构 论文主要是基于无线传感器网络k 重覆盖问题的研究，首先对无线传感器网络进 行了概述，并详细介绍无线传感器网络覆盖方法的分类以及基于k 重覆盖算法的随机 覆盖休眠算法与c g s 休眠算法和改进后的k n cc g s 算法，通过仿真结果的对比，说 明k n cc g s 算法优于c g s 算法与随机休眠算法。 本论文共分为七个章节： 第一章，介绍了本课题的来源、研究的背景、研究内容和国内外的研究现状。 第二章，介绍了无线传感器网络的体系结构、以及无线传感器网络的研究。 第三章，介绍了无线传感器网络覆盖的相关技术。详细介绍了无线传感器网络覆 盖方法的分类。 第四章，介绍了无线传感器网络基于最小k 重覆盖的随机休眠算法和协作休眠 c g s 算法以及改进后的k n cc g s 算法。 第五章，介绍了p r o w l e r 无线传感器仿真软件的设计原理。 第六章，给出了c g s 算法与改进后的k n cc g s 算法的仿真结果，并把仿真结果 与随机休眠算法进行对比，证明了k n cc g s 算法优于c g s 算法与随机休眠算法。 第七章，对论文进行了总结和展望，总结了本论文所做的工作，展望了无线传感 器网络未来的发展趋势。 4 第二章无线传感器网络的概述 21 无线传感器网络介绍 211 无线传感器网络慨念 更小、更廉价的低功耗计算设备代表的“后p c 时代”冲破了传统台式计算机和高 性能服务器的设计模式；普遍的网络化带来的计算处理能力是难以估量的：微机电系 统( 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 ) 的迅速发展奠定了设计和实现片上系 统( s y s t e mo l lc h i p ，简称s o c ) 的基础。以上三方面的高度集成又孕育出了许多新的信息 获取和处理模式，传感器网络就是其中一例。 随机分布的集成有传感嚣、数据处理单元和通信模块的微小节点通过无线信道相 连，自组织地构成网络系统。这些传感器节点借助于其内置的形式多样的传感器，测 量所在周边环境中的热、红外、声纳、雷达和地震波信号探测包括温度、湿度、噪 声、光强度、压力、土壤成分、移动物体的大小、速度和方向等众多人们感兴趣的物 理现象【”。在通信方式上，虽然可以采用有线、无线、红外和光等多种形式，但一般认 为短距离的无线低功率通信技术最适合传感器网络使用，为明确起见，一般称作无线 f | 1 传感器网络。但也不绝对b e r k e l e y 的s m a r td u s t 因为可以像尘埃一样悬浮在空中，有 效地避免了障碍物的遮挡，因此采用光作为通信介质。 蕾囝 | 垄| 21 无线传感器网络竹点示意幽 无线传感器网络是一种无中心节点的全分靠系统。通过随机投放的方式，众多传 感器节点被密集部署于监控区域。传感器节点削具有良好的协作能力，通过局部的数 据交换柬完成全局任务。由于传感器网络的节能要求，多跳、对等的通信方式较之传 统的单跳、主从通信方式更适合于无线传感器网络，同时还a t 有效避免在长距离无线 信号传播过程中所遇到的信号衰落和干扰等各种问题。通过网关传感器网络还u t 以 连接到现有的网络基础设施上( 如i n t e m e t 、移动通信网络等) 从而将采集到的信息 回传给远程的终端用户使用。 2 1 2 无线传感器网的特征 无线传感器网络以数据为中心，将能源的高效使用作为首要设计目标，专注于从 外界获取有效信息。除此以外，无线传感器网络还具有以下一些区别于无线自组织网 络的独有特征： ( 1 ) 规模大、密度高。为获取尽可能精确、完整的信息，无线传感器网络通常密 集部署在大片的监测区域中。 ( 2 ) 动态性强。无线传感器网络工作在一定的物理环境中。不断变化的外界环境 ( 如无线通信链路时断时续，突发事件产生导致网络任务负载变化等) 往往会严重影 响系统的功能，这就要求传感器节点能够随着环境的变化而适时地调整自身的工作状 态。 ( 3 ) 应用相关。无线传感器网络通过感知客观世界的物理量来获取外界的信息。 由于不同应用关心不同的物理量，因而对网络系统的要求也不同，其硬件平台、软件 系统和通信协议也必然会有很大差异。 ( 4 ) 以数据为中心。在无线传感器网络中，人们通常只关心某个区域内某个观测 指标的数值，而不会去具体关一心单个节点的观测数据l 。这就是无线传感器网络以数 据为中心的特点，它不同于传统网络的寻址过程，能够快速、有效地组织起各个节点 的信息并融合提取出有用信息直接传送给用户。 ( 5 ) 可靠性。由于传感器节点往往在无人值守的状态下工作，这使得网络的维护 变得十分困难，甚至不太可能，因而要求传感器节点非常坚固、不易损坏，在环境因 素变化不可预知的情况下能够很好地适应各种极端的环境。要求无线传感器网络的设 计必须具有很好的鲁棒性和容错性。 ( 6 ) 节点能力受限。传感器节点具有的能量、处理能力、存储能力和通信能力等 都十分有限，因而在实现各种网络协议和应用系统时，传感器节点的能力要受到以下 一些限制：电源能量、计算和存储能力、通信能力。 通常，无线通信的能耗与通信距离d 的关系为： e = k d ” 其中，2 2 ，那么一不能被 i 的圆周所覆盖。否则薯由i 覆盖的圆周大小可由图2 ( a ) 中所示，口= a r c c o s ( 坐乏2 ) 。 因此，s ，就落在j ，的 万一a ，万+ 口】的圆周中【1 1 。 4 2 2k n o ( 感应半径不是单位圆) 覆盖问题 图4 5 s 不能覆盖s i 图4 6 可以覆盖i 对于k n c 覆盖问题，传感器的感应范围会有些困难，但结果仍然可以从上面的分 析中得到。我们分两种情况束考虑。 第一种情况：s ，在s ，的外面，即：d ( s ，s ，) ，： ( 1 ) 如果- d ( s ，s ，) 一，那么s ，就不能被s ，所覆盖。 ( 2 ) 如果d ( 5 ，s ，) 一 0 d ( s f ，s 歹) + ，那么s ，在【o ，2 1 r 内由_ 所覆盖。 第二种情况一，在s f 之内，即：d ( s 。，s ，) o ，当r 并且v o ， p = 生学f 1 = - 1 + l = o 。为了使 p u l 。= y 一0 。这就是说为了达到1 0 0 的条件覆盖，那么节点可以休眠。 1 0 9 0 8 o 7 嚣0 6 ：05 兰0 4 0 3 02 0 1 0 1 09 o8 o7 嚣o 6 主o5 z 差04 o 3 0 2 0 1 0 图4 7 任意地区不被协点覆盖的概率为0 0 0 1 与任意地| 又：不被1 ，点覆盖的条件概率为0 0 0 1 4 3 2 覆盖密度 我们下一步将通过两种特殊的情况讨论覆盖密度，一个是几何分布丌关周期。另 一个是均一分布开关周期。我们使用这些例子的结果去讨论随机休眠调制的设计方 案。在这罩我们只考虑条件概率以这种方法更多是关注休眠机制的效率。 图4 8 几何分布的仃点i ：作与休眠状态，a ：i ：作，5 ：休眠 一h p 图4 9 随机分布的点l ：作与休眠状态，a ：i ：作，s ：休眠 弟一种情况，每一个传感器在一个时段独立的休目民概率。第二种情况休目民剧期t 。 均匀分布在 m s v s ，m s + v s 】，并且工作周期t 。是均匀分布在 讹一v a ，m a + l e a ，在这罩 坛和心是每一个周期的均值。工作与休眠的长度的方差分别是： 掣和 z 1 v e g 瓦( v i a 丁- i 一) 2 在节点在任意时间间隔的休眠概率由p 来确定。 p = 揣= 砀瓮。图4 8 我们能够让我们认识到几何丌关调制和均匀丌 关调制【4 1 。 当丌关周期是几何分布时，在尾分布中，至少n 个i 日j 隔中节事件不被覆盖的概率 为： 铂。o 胛) = 见旷zp 。膨= f ) 硇，一莩专耖”等 7 ， 硇。一喜筹 开关周期并不是无记忆的。以i 。( ，胛) 是非常复杂的。这是因为尾分布主要是由 开关过程决定的，做为丌并过程的独立的组成的结果。如果至少有一个丌关过程中 是丌，叠加的过程就是开。仅当所有的组成过程都是关，叠加过程就是关。接下来推 导以l 。o = ，2 ) 。 4 4 协作休眠 协作休眠的基本思想是能够维持较高的覆盖率。如图4 1 0 所示，在这个例子中a 所覆盖的区域完全由b 、c 和d 三个节点所覆盖，如果b 、c 、d 都处在工作状态，那么 a 就是一个冗余节a 表示网络中有冗余节点，b 表示合适的覆盖点。当我们关闭节点a ， 2 3 网络中的覆盖率是不会下降的。节点a 或者其它节点处于相同的状念时，可以通过通信 的方式了解其邻居节点和自身的位置。因此，传感器网络通过这种休眠机制，关闭冗 余节点以节省能量并维持较好的覆盖率【2 8 】。 图4 1 0 ( a ) 带有冗余节点的覆盖( b ) 合理的覆盖 在图4 8 ( a ) 中，对于b 、c 、d 来晚a 是完全冗余的。同时，相对于其它节点未给 出的节点，也可能是冗余的。如果a 和b 同时休眠，那么就会出现覆盖的盲，直到a 和b 都被再次激活。另外，这种方法也没有提到时间，无线传感器网络中的节点以怎样的 工作和休眠状态来平衡能量的消耗? 在图4 8 ( b ) 中，做到了持续的覆盖，同时平衡了能量的消耗以提供更好的鲁棒 性。理想的简单的方法就是一个节点确定是否进入休h 民状念不仅基于它的位置和邻居 节点，而且也基于它的剩余能量。我们晚这种算法可以达到10 0 的条件覆盖率即 ( p 一，= 0 ) 。同时，当节点密度增加时，相对于随机休眠算法可以大大降低占空比。通 “ 过一些基本的几何计算来检验。 4 4 1 角色互换协作休眠算法 我们认为通信半径相对于感应半径足够大。当通信半径小于感应半径时，此算法 仍可以实现。每一个节点通过g p s 装置或其它算法可以知道自身的位置。任意节点的邻 居是它感应范围内的任意节点。 在协作休眠算法中，节点是多角色的，可以是簇头、发起者、也可以是普通的节 点。节点通过同期性的向邻居节点发送坐标信息( c o r ) 来告知它的位置。c o r 中也 包括节点的i d 、角色信息、剩余能量。在丌始时所有的节点都是普通的节点。当一个 节点知道它的感知区域已经完全被它的邻居节点所覆盖时，那么此时它就可以进入休 眠状态。一个潜在的发起者当它收：至i j r e q 信息时就认为它已经是发起节点了。然后它 仍然处于工作状态直到符合条件的节点终止y j 进入休眠状态。符合条件的节点收到发 起者的确认信息，认为它是簇头，并周期性的发送信息，然后进入休眠状态。在没有 信息丢失的情况下，会从发起者那罩收到确认信息，并安全的进入休眠状念。然而， 如果有些信息丢失，潜在的节点就可能收不到丌始的r e q 信息，并且符合条件的节点 2 4 也可能收不到发起节点的所有a c k 信息。在这种情况下符合条件的节点就可能简单的 认为自己应该第一个进入休眠状态并发送r e q 信息后丌始休眠，或者在收到一个从子 发起节点的a c k 信息后休眠。下面我们分两种情况来分析，一种是信息不丢失，另一种 是信息丢失的情况。 在p a c p 时，个符合条件的节点只选择发起节点的信息而不是所有邻居节点的信 息。例如：在图4 1 0 ( b ) 中，节点a 是一个符合条件的节点，它可以充分的去选择节 点b 、c 、d 或者节点e 、f 、g 作为发起节点。彳将会选择一个集合( ! ! i i b 、c 、d ) ，并 通过发送r e 0 信息告知这些节点它自身的i d 、角色信息、剩余能量、发起节点表和休眠 时间。在收到这些信息后，b 、c 、d 将长时i 日j 的进入休眠状态，它们被认为是发起节 点。在这个例子中e 、f 、g 对于a 来 兑不是发起节点，如果它们变成符合条件的节点， 可以自由的进入休眠状态。 一个普通的节点仍处于工作状念并周期的检查自身是否符合条件。如果一个节点 不符合条件并进入休眠状态，那么它仍然是一个普通节点并继续周期性的检查自身是 否符合条件。如果一个节点符合条件并进入休眠状态，它丌始随机的延迟计算，当这 种计算终止时，它会向它最近的邻居广播一个r e q 信息。在它从发起节点那罩收到所 有的a c k 确认信息，它就会变成一个簇头并进入休眠状态。如果有先自订的一段时i h j 内 它没有收到a c k s 信息，那么它仍然是一个普通节点。如果一个符合条件的节点在延迟 终止前收到 r e q 信息并变成了一个发起节点，它就认为自己是一个发起节点，并报 告a c k 信息。由簇头选择的发起节点仍就继续它的角色，直到在先日订确定的休眠周期 结束，簇头变成了一个普通节点