无线传感器网络中能量敏感感知节点选择算法

第３４卷　

Ｖｏ１．３４　第１１期　

Ｎｏ．１ｌ　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２００８年６月　

Ｊｕｎｅ　２００８　

・博士论文・　文章编号：１０００—＿Ｉ３４２８（２００８）１ｌ—ｏ００４＿＿０３　文献标识码：Ａ　中图分类号：ＴＰ３１２　

无线传感器网络中能量敏感感知节点选择算法　

尹小燕　，周兴社１，李　

（１．西北工业大学计算机学院，西安７１００７２；２　薇。，李士宁　

玉溪师范学院信息中心　玉溪６５３１００）　

摘要：如何保证在满足系统ＱｏＳ需求的同时延长网络的生命周期是无线传感器网络面临的最重要问题之一。提供高质量感知数据是无线　

传感器网络的目的，感知节点是网络能否实现这个目标的关键因素。为了节省感知节点的能量并实现负载均衡，该文提出一种能量敏感、　负载均衡并与物理位置无关的感知节点选择算法ＥＡＳＮＳ，综合考虑感知能力和剩余能量两因素对感知节点进行选择，用ＴＯＳＳＩＭ仿真工　

具对算法ＥＡＳＮＳ进行了仿真。仿真实验结果表明，采用ＥＡＳＮＳ算法与选择所有节点得到的平均温度之间的误差为Ｏ３％，能够有效地减　

少能量消耗，能量消耗约为选择所有节点方法的２５％，并能实现感知节点能耗负载均衡，延长系统生命周期。　

关键诃：无线传感器网络；感知节点；可替代感知节点；负载均衡　：　

Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｅｎｅｒｇｙ－ａｗａｒｅ　Ｓｅｎｓｉｎｇ　Ｎｏｄｅ　Ｓｅｌｅｃｔｉｏｎ　

ｉｎ　Ｗｉｒｅｌｅｓｓ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ　

ＹＩＮ　Ｘｉａｏ—ｙａｎ　，ＺＨＯＵ　Ｘｉｎｇ—ｓｈｅ　，ＬＩ　Ｗｅｉｚ，ＬＩ　Ｓｈｉ—ｎｉｎｇ　

ｆ１．Ｃｏｌｌｅｇｅ　ｏｆＣｏｍｐｕｔｅｒ，ＮｏｒｔｈｗｅｓｔｅｒｎＰｏｌｙｔｅｃｈｎｉｃａｌＵｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ　７１００７２：，２．ＣｅｎｔｅｒｏｆＩｎｆｏｒｍａｔｉｏｎ，ＹｕｘｉＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｙｕｘｉ　６５３ｌ（）（】）　

［Ａｂｓｔｒａｃｔ］Ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ　ｏｆｔｅｎ　ｆａｃｅ　ｔｈｅ　ｃｒｉｔｉｃａｌ　ｐｒｏｂｌｅｍ　ｏｆ　ｇｕａｒａｎｔｅｅｉｎｇ　ｔｈｅ　ｄｅｓｉｒｅｄ　ＱｏＳ（Ｑｕａｌｉｔｙ　ｏｆ　Ｓｅｒｖｉｃｅ）ｒｅｑｕｉｒｅｍｅｎｔ　ｗｈｉｌｅ　ｋｅｅｐｉｎｇ　

ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ　ｌｉｆｅｔｉｍｅ　ａｓ　ｌｏｎｇ　ａｓ　ｐｏｓｓｉｂｌｅ．Ａｃｑｕｉｒｉｎｇ　ｔｈｅ　ｈｉｇｈ　ｑｕａｌｉｔｙ　ｄａｔａ　ｉｓ　ｔｈｅ　ｇｏａｌ　ｏｆ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ．Ｓｅｎｓｉｎｇ　ｎｏｄｅｓ　ａｒｅ　ｔｈｅ　ｋｅｙ　ｆａｃｔｏｒ　

ｆｏｒ　ｔｈｅ　ｎｅｔｗｏｒｋ　ｔＯ　ａｃｈｉｅｖｅ　ｔｈｅ　ｇｏａ１．Ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ｃｏｎｓｕｍｐｔｉｏｎ　ｏｆ　ｅｎｅｒｇｙ　ａｎｄ　ｂａｌａｎｃｅ　ｔｈｅ　ｅｎｅｒｇｙ　ｄｉｓｓｉｐａｔｉｏｎ　ａｍｏｎｇ　ｎｏｄｅｓ，ａｎ　ｅｎｅｒｇｙ—ａｗａｒｅ　

ｌｏａｄ—ｂａｌａｎｃ：ｉｎｇ　ａｎｄ　ｌｏｃａｔｉｏｎ—ｉｎｄｅｐｅｎｄｅｎｔ　ａｌｇｏｒｉｔｈｍ　ｎａｍｅｄ　ＥＡＳＮＳ　ｉｓ　ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ　ｓｅｌｅｃｔｓ　ｓｅｎｓｉｎｇ　ｎｏｄｅｓ　ｂａｓｅｄ　ｏｎ　ｂｏｔｈ　ｔｈｅｉｒ　ｓｅｎｓｉｎｇ　ａｂｉｌｉｔｙ　ａｎｄ　

ｃｕｒｒｅｎｔ　ｅｎｅｒｇｙ．Ｉｔ　ｓｉｍｕｌａｔｅｓ　ＥＡＳＮＳ　ｕｓｉｎｇ　ＴＯＳＳ／Ｍ．Ｓｉｍｕｌａｔｉｏｎ　ａｎｄ　ａｎａｌｙｓｉｓ　ｄｅｍｏｎｓｔｒａｔｅ　ｔｈａｔ　ＥＡＳＮＳ　ｎｏｔ　ｏｎｌｙ　ｃａｎ　ｐｒｏｖｉｄｅ　ｔｈｅ　ｄｅｓｉｒｅｄ　ｄａｔａ　ｅｆｆｅｃｔｉｖｅｌｙ．ｆｏｒ　ｉｎｓｔａｎｃｅ．ｔｈｅ　ｅｒｒｏｒ　ｏｆ　ｔｈｅ　ａｖｅｒａｇｅ　ｔｅｍｐｅｒａｔｕｒｅ　ｉｓ　Ｏ３％．ｂｕｔ　ａｌｓｏ　ｓａｖｅ　ｅｎｅｒｇｙ．ｇｒｅａｔｌｙ（ｔｈｅ　ｒａｔｉｏ　ｏｆ　ｅｎｅｒｇｙ　ｃｏｎｓｕｍｅｄ　ｂｙ　ＥＡＳＮＳ　ｔｏ　ｔｈａｔ　ｂｙ　

ｓｅｌｅｃｔｉｎｇ　ｔｏｔａｌ　ｎｏｄｅｓ　ｉｓ　ａｂｏｕｔ　２５％，Ｊ，ｂａｌａｎｃｅ　ｔｈｅ　ｅｎｅｒｇｙ　ｌｏａｄ　ａｍｏｎｇ　ｓｅｎｓｉｎｇ　ｎｏｄｅｓ，ａｎｄ　ｐｒｏｌｏｎｇ　ｔｈｅ　ｌｉｆｅｔｉｍｅ　ｏｆ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ．．　［Ｋｅｙ　ｗｏｒｄｓ］ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ：ｓｅｎｓｉｎｇ　ｎｏｄｅ；ｒｅｐｌａｃｅａｂｌｅ　ｓｅｎｓｉｎｇ　ｎｏｄｅ：，ｌｏａｄ—ｂａｌａｎｃｉｎｇ　

１概述　近年来，随着微机电系统、无线通信等技术的迅速发展，　

无线传感器网络（Ｗｉｒｅｌｅｓｓ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ，ＷＳＮ）应运而　生　。无线传感器网络的服务质量（ＱｏＳ）保证是该技术有效应　

用的核心问题之一。目前由于传感器网络ＱｏＳ技术研究的相　

对滞后，制约了无线传感器网络在对感知数据的准确性和实　

时性要求较高领域的应用。如在迫切需要解决煤矿安全监测　

的问题中，传感器网络被认为是监测最易发生瓦斯爆炸的煤　炭采掘面的有效手段，但井下复杂恶劣的环境对无线传输的　

要求较高，而传感器网络ＱｏＳ的感知信息可靠性保证问题尚　

未切实解决，使得传感器网络不能大规模应用。为了达到数　

据精度或数据解析度等这些系统要求的ＱｏＳ指标，需要从数　

据采集的过程加以保证，而数据采集工作是由感知节点来完　成的，感知节点是无线传感器网络能否向用户提供高质量数　

据的关键因素。　本文针对特定监测类应用提出了能量敏感、负载均衡的　

感知节点选择算法ＥＡＳＮＳ，传感器节点首先对采集到的信号　

进行能量积分，簇头以积分值为依据，对传感器节点按感知　

能力进行分组、组内排序并对感知节点进行轮换选择，以达　

到节省能量，均衡负载的目的。　

２问题描述　

对于目标区域确定的监测类应用，如森林火灾预防或毒　气泄漏检测，由于传感器节点的感知半径一定，因此无线传　

感器网络中感知节点数目也是确定的。若感知节点的能量均　

耗尽，就会采集不到目标区域的数据，则该无线传感器网络　

的存在便没有任何价值。本文算法所做的工作如下：　

（１）对所有传感器节点进行判断，将其划分为感知节点和　

非感知节点２类。　（２）在满足ＱｏＳ需求的情况下，周期性地选取尽可能少的　

感知节点进行数据采集工作，同时设置其他感知节点为非活　

动状态。　

（３）感知节点的选取应考虑节点的剩余能量大小，以使所　

有感知节点能量消耗均衡，避免某些节点过早死亡。　

能量敏感的感知节点选择算法（ＥＡＳＮＳ）有如下的相关　

概念：　（１）感知节点。任一传感器节点，若其感知圆盘覆盖了一　

部分目标区域，即可对目标区域进行监测，则该节点为感知　

节点（感知圆盘是以节点为圆心、以感知半径为半径的圆）。　

基金项目：国家自然科学基金资助项目（６０５７３１６１ｊ；国家部委“十一　

五”预研基金资助项目　作者简介：尹小燕（１９７８一），女，博士，主研方向：网络化嵌入式计　

算，传感器网络；周兴社，教授、博士生导师；李薇，助理实验　

师；李士宁，教授、博士　收稿Ｈ期：２００７—０６—１０　Ｅ—ｍａｉｌ：ｓｃｈ—ｙｘｙ＠ｍａｉｌ．ｎｗｐｕ．ｅｄｕ．ｃ

ｎ　维普资讯 http://www.cqvip.com （２）感知节点集。由所有感知节点组成的集合。　

（３）可替代感知节点。在相同时问问隔内，节点ｉ与节点　

．，对信号的积分的差值不超过￡（￡为系统设定值），则２个节　

点互为可替代感知节点，记为ｒｅｐｌａｃｅ（／＂）＝ｉ或ｒｅｐｌａｃｅ（／）＝『ｃ　

３　ＥＡＳＮＳ算法　

本文提出的ＥＡＳＮＳ算法是基于分簇的，每一个簇包括　

簇头和众多簇内成员，簇头对整个簇进行控制管理，负责为　

簇内所有传感器节点分配时槽，收集和处理簇内传感器节点　

发来的数据，并将数据转发给汇聚节点。簇成员节点的状态　分为感知（ｓｅｎｓｉｎｇ）、转发（ｒｅｌａｙｉｎｇ）、感知并转发（ｓｅｎｓｉｎｇ＆　

ｒｅｌａｙｉｎｇ）和非活动（ｉｎａｃｔｉｖｅ）４种。　

ＥＡＳＮＳ算法的具体实现分为以下２个阶段：　

（１）确定感知节点阶段。该阶段的主要任务是确定能够对　目标区域进行感知的节点ＩＤ集合。本文依据文献［２—３Ｊ提出的　

传感器模型和文献［４ｊ提出的Ｅｘｐｏｓｕｒｅ模型对传感器节点进　

行判断。　假定被检测的信号为单位信号，文献［２—３］给出的传感器　

模型如式（１）所示：　

Ｓ（ｓ，ｐ）＝［ｄ（　，ｐ）］　／　（１）　其中，Ｓ是传感器的位置；Ｐ是被检测目标的位置；ｄ（ｓ，Ｐ）是　

传感器Ｓ和目标Ｐ之问的欧氏距离；Ｓ（ｓ，ｐ）是传感器Ｓ检测　

到的信号的强度，　和ｋ是依赖于传感器技术的参数。　

Ｅｘｐｏｓｕｒｅ表示目标在传感器网络中的暴露程度，传感器　

对信号持续测量一段时问，对信号进行能量积分，如果能量　

大于事先给定的阈值，则认为监测到事件的发生。Ａｄｌａｋｈａ　

等给出的Ｅｘｐｏｓｕｒｅ模型如式（２）所示：　

Ｖ＝　，ｐ）ｄｆ　

当某个传感器的Ｅｘｐｏｓｕｒｅ值大于事先给定的阈值　

时，即Ｖ＞　，则该传感器节点为感知节点。　

本阶段的具体操作分为如下２个步骤：　

１）簇头首先将所有簇成员节点设置为感知状态，经过时　问ｔ后，若某传感器节点对信号的能量积分满足Ｖ＞　，　

就形成数据帧（积分值　作为ｒｅａｄｉｎｇｓ值，剩余能量ｅｎｅｒｇｙ　

作为一个域），在簇头分配给自己的时槽内将数据帧发送给　簇头。　

２）簇头节点对所有收到的数据帧进行整理，相同的数据　

帧仅保留一份（针对经多径路由到簇头的同一数据帧）。簇头　

收到大量包含观测值的数据帧后，首先对所有数据帧按照　

ｒｅａｄｉｎｇｓ值进行排序，然后按照系统设定的￡进行计算，将感　知节点分为感知能力相近的多个分组如图中的组１，…，组　

ｉ，…，组ｎ，每个分组的第１个传感器节点与最后一个传感　

器节点的＂ｒｅａｄｉｎｇｓ值相差￡，如图１所示，组内的任意２个　传感器节点互为可替代感知节点。然后依次取出对应的节点　

ＩＤ，所有ＩＤ形成的集合即为感知节点集，集合中的任一传　

感器节点均可执行数据采集任务。　

组１　…　组ｉ　…组　／——＼＼／——＼、／—、＼　ｒｅａｄｉｎｇｓ（１１）＞ｍａｄｉｎｇｓ（１３Ｊ＞…＞ｒｅａｄｉｎｇｓ（２１）＞…＞ｒｅａｄｉｎｇｓＯ）＞‘‘ｘｅａｄｉｎ￣（『］＞ｒｅａｄｉｎｇｓ（　图１｛菌Ｉ知节点分组示意图　

（２）选择感知节点阶段。数据的精确度是系统ＱｏＳ的一个　

重要指标，取决于簇头节点选择哪些感知节点完成采集数据　

任务。如图２所示，感知节点Ａ，Ｂ，Ｃ均能感知到目标区域　，　

而Ｄ不能感知到目标区域丁。由于感知节点Ａ的观测值质量　最好，因此簇头选择Ａ来进行数据采集。簇头节点每发出一　

次对目标区域　的查询请求，若同时选择Ａ，Ｂ，Ｃ，系统的可　

靠性当然得以保障，但是网络的生命周期会大大缩短；若只　

选择Ａ，后续的查询重复选择感知节点Ａ的可能性也最大，　如此一来，Ａ就会比其他节点消耗更多的能量，导致能量消　

耗不均衡，Ａ会比其他节点早死亡，也可能会导致网络分割　

问题（如果Ａ为瓶颈节点，它的死亡将会导致整个网络被分割　

成若干个不相连的部分，网络的生命周期也就此终结）。为避　

免某些感知节点过早死亡而导致的网络分割问题，ＥＡＳＮＳ算　

法综合考虑观测值的优劣和能量２个因素来对感知节点进行