无线传感器网络中节点非均匀分布的能量空洞问题

第３ｌ卷第２期计算机学报Ｖ０１．３１Ｎｏ．２２００８年２月ＣＨＩＮＥＳＥＪｏＵＲＮＡＬ０ＦＣＯＭＰＵＴＥＲＳＦｅｂ．２００８

无线传感器网络中节点非均匀分布的能量空洞问题

吴小兵陈贵海

（南京大学软件新技术国家重点实验室南京２１００９３）

摘要节点非均匀分布策略能缓解无线传感器网络中的能量空洞问题．文中从理论上探讨这种策略，证明在节点非均匀分布的圆形网络中，如果节点持续向Ｓｉｎｋ节点发送数据，能量空洞现象将无法避免，而当节点数目满足一定关系时，网络中能够实现次优能耗均衡．文中提出一种节点非均匀分布策略及相应的路由算法用于实现这种次优能耗均衡．模拟结果显示网络生存周期终止时，处于网络内部的节点几乎达到了能耗均衡．

关键词无线传感器网络；能量空洞；节点非均匀分布

中图法分类号ＴＰ３９３

ＴｈｅＥｎｅｒｇｙＨｏｌｅＰｒｏｂｌｅｍｏｆＮｏｎｕｎｉｆｏｒｍＮｏｄｅＤｉｓｔｒｉｂｕｔｉｏｎｉｎ

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

ＷＵＸｉａｏ－ＢｉｎｇＣＨＥＮＧｕｉ－Ｈａｉ

（ＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙｆｏｒＮｏｅｌＳｏｆｔｌｌｌａｒｅＴｅｃｈｎｏｌｏｇｙ，ＮａｎｊｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｎａ可ｉｎｇ２１００９３）ＡｂｓｔｒａｃｔＴｈｅｎｏｎｕｎｉｆｏｒｍｎｏｄｅｄｉｓｔｒｉｂｕｔｉｏｎｓｔｒａｔｅｇｙｃａｎｂｅｕｓｅｄｔｏｍｉｔｉｇａｔｅｔｈｅｅｎｅｒｇｙｈｏｌｅ

ｐｒｏｂｌｅｍｉｎｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅａｕｔｈｏｒｓｉｎｖｅｓｔｉｇａｔｅｔｈｅｔｈｅｏｒｅｔｉｃａｌａｓｐｅｃｔｓｏｆｔｈｅｎｏｎｕｎｉｆｏｒｍｎｏｄｅｄｉｓｔｒｉｂｕｔｉｏｎｓｔｒａｔｅｇｙｉｎｍｕｌｔｉ－ｈｏｐｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ，ａｎｄｐｒｏｖｅｔｈａｔｉｎａｃｉｒｃｕｌａｒｓｅｎｓｏｒｎｅｔｗｏｒｋｗｉｔｈｎｏｎｕｎｉｆｏｒｍｎｏｄｅｄｉｓｔｒｉｂｕｔｉｏｎａｎｄｃｏｎｓｔａｎｔｄａｔａｒｅｐｏｒｔｉｎｇ，ｔｈｅｕｎｂａｌａｎｃｅｄｅｎｅｒｇｙｄｅｐｌｅｔｉｏｎａｍｏｎｇｔｈｅｎｏｄｅｓｉｎｔｈｅｗｈｏｌｅｎｅｔｗｏｒｋｉｓｕｎａｖｏｉｄａｂｌｅ．Ｉｎｓｐｉｔｅｏｆｔｈｉｓｆａｃｔ，ｓｕｂｏｐｔｉｍａｌｅｎｅｒｇｙｅｆｆｉｃｉｅｎｃｙａｍｏｎｇｔｈｅｉｎｎｅｒｐａｒｔｓｏｆｔｈｅｎｅｔｗｏｒｋｉｓｐｏｓｓｉｂｌｅｉｆｔｈｅｎｕｍｂｅｒｏｆｎｏｄｅｓｉｎｔｈｅｎｅｔｗｏｒｋｉｓｑｕａｎｔｉｆｉｅｄａｎｄｍｅｅｔｓｓｏｍｅｃｏｎｄｉｔｉｏｎｓ．ＴｈｅａｕｔｈｏｒｓｐｒｏｐｏｓｅａｎｏｖｅｌｎｏｎｕｎｉｆｏｒｍｎｏｄｅｄｉｓｔｒｉｂｕｔｉｏｎｓｔｒａｔｅｇｙｂａｓｅｄｏｎｔｈｅｉｒａｎａｌｙｓｉｓａｎｄａｒｏｕｔｉｎｇａｌｇｏｒｉｔｈｍＣＯＵ—ｐｉｉｎｇｗｉｔｈｔｈｅｐｒｏｐｏｓｅｄｎｏｄｅｄｉｓｔｒｉｂｕｔｉｏｎｓｔｒａｔｅｇｙｆｏｒａｃｈｉｅｖｉｎｇｔｈｅｓｕｂｏｐｔｉｍａｌｅｎｅｒｇｙｅｆｆｉｃｉｅｎｃｙ．Ｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｗｈｅｎｔｈｅｎｅｔｗｏｒｋｌｉｆｅｔｉｍｅｅｎｄｓ，ｔｈｅｉｎｎｅｒｃｏｒｏｎａｓｎｅａｒｌｙａｔｔａｉｎｂａｌ—ａｎｃｅｄｅｎｅｒｇｙｄｅｐｌｅｔｉｏｎ．

Ｋｅｙｗｏｒｄｓｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ；ｅｎｅｒｇｙｈｏｌｅ；ｎｏｎｕｎｉｆｏｒｍｎｏｄｅｄｉｓｔｒｉｂｕｔｉｏｎ

１引言

ＭＥＭＳ技术的快速发展使大批量生产和制造微小而经济的传感器成为可能．传感器可以用于探测周围环境的温度、湿度等信息．无线传感器网络通常由多个传感器节点和一个信息收集节点（Ｓｉｎｋ）组成，布置在森林、农田、民用建筑等环境中收集人们感兴趣的信息［１］．

无线传感器网络中能耗效率非常重要．传感器节点间往往采用多跳方式进行通信，一些节点既产生数据也转发数据［１］．同时，数据流遵循多对一的

收稿日期：２００６—１２—２６；最终修改穑收到日期：２００７—０９—３０．本课题得到国家“九七三”重点基础研究发展规划项目基金（２００６ＣＢ３０３０００）、国家自然科学基金（６０５７３１３１，６０６７３１５４。６０７２１００２）和江苏省自然科学基金（ＢＫ２００５２０８，ＢＧ２００７０３９）资助．吴小兵。男，１９７９年生，博士研究生，研究方向为无线传感器网络．Ｅ－ｍａｉｌ。ｗｕｘｂ＠ｄｉｓｌａｂ．ｎｉｕ．ｅｄｕ．ｃａ．陈责海，男，１９６３年生，教授，博士生导师，研究领域为并行与分布式计算．

２５４计算机学报

模式，离Ｓｉｎｋ较近的节点需要承担更多的通信负载．因此这些节点容易过早耗尽自身的能量，导致在Ｓｉｎｋ周围出现能量空洞（ｅｎｅｒｇｙｈｏｌｅ）．能量空洞的出现使网络采集的数据不能进一步传送给Ｓｉｎｋ节点，此时网络的生存周期结束，网络中遗留大量未被充分利用的能量资源．文献ＥｚＳ／中模拟实验表明如果采用节点均匀分布策略，网络中可能有高达９０％的能量被浪费．我们把部分节点因为过早耗尽自身能量导致网络原有覆盖区域缺失或者数据无法送达Ｓｉｎｋ节点的现象称作“能量空洞”现象．

本文从理论上探讨采用节点非均匀分布策略的无线传感器网络中能量空洞能否避免的问题．Ｌｉ和Ｍｏｈａｐａｔｒａ［３１首先提出了一个用于分析无线传感器网络中的能量空洞的模型．作者假设网络中节点均匀分布，分析了层次结构、数据压缩等手段对避免能量空洞的有效性．Ｌｉａｎ等人在文献Ｅ４］中讨论了为节点装备不同的初始能量储备的方法提高网络数据容量的方法．作者假定在一个矩形的网络中节点均匀分布．这里网络的数据容量是指Ｓｉｎｋ节点收到的数据的总和．文献［３—４］都没有回答能量空洞能否避免的问题．

Ｏｌａｒｉｕ和ＳｔｏｊｍｅｎｏｖｉｃＥ朝第一次证明了在特定条件下，无线传感器网络中的能量空洞不可避免．他们同样假设网络中节点均匀分布，传感器节点持续向Ｓｉｎｋ节点汇报数据．Ｌｉａｎ［２３等人还提出采用节点非均匀分布策略提高数据容量的思想，但仍然没有涉及节点非均匀分布策略下的能量空洞问题．文献Ｅ６３简要讨论了使用节点非均匀分布策略的能量空洞问题．作者假设网络中的每个节点数据采集率可调，给出了避免能量空洞的条件．

在文献Ｅ７３的工作基础上，本文从理论上进一步探讨无线传感器网络中采用节点非均匀分布策略的能量空洞问题．不同于文献Ｅ６３的是：本文假设网络中的每个节点数据采集率恒定，同时考虑数据发送和接收过程中的能量消耗，得出了不同的结论并给出了能够实现次优能耗效率的条件和具体的路由算法．本文证明了如果在一个圆形的无线传感器网络中节点非均匀分布并持续向Ｓｉｎｋ节点发送数据，节点间的能耗不均衡现象将无法避免，即能量空洞不可避免．但是如果将网络分为多个同心等宽的圆环，网络中节点数目除最外圆环外，由外环至内环以等比ｑ递增，且最外圆环中节点数目是其相邻内环节点数目的１／（ｑ一１），网络能获得次优的能耗效率．基于这种分析，本文提出了一个新的节点非均匀分布策略并设计了相应的路由算法用于获得次优的能耗效率．模拟结果显示当网络的生存周期终止时，网络内环中的节点间几乎达到了能耗均衡．

２相关工作

针对无线传感器网络中的能量空洞问题已经有一些应对机制提出．下面介绍一些相关工作，其中一部分已经在上一节中提到．

Ｌｉ和Ｍａｈａｐａｔｒａ［３］首先提出一个数学模型用于分析无线传感器网络中的能量空洞问题．文中假定一个圆形的网络中节点均匀分布．该模型从网络流量的角度出发，分析和比较几种针对能量空洞问题的常见方法的有效性．文中指出在一个节点均匀分布的无线传感器网络中，采用层次结构和数据压缩机制对于缓解能量空洞问题是有效的，增加数据采集率使能量空洞问题更加严重，而在网络中增加节点的作用不明显．文中没有讨论无线传感器网络中能量空洞能否避免的问题．

文献Ｅ４３中作者假定在一个矩形网络中节点均匀分布．为了提高网络的数据容量，文中提出一种节点初始能量非均匀分布的方法，使距离Ｓｉｎｋ较近的节点有较多的初始能量储备．作者同时提出一种基于移动Ｓｉｎｋ的路由算法．

Ｏｌａｒｉｕ和Ｓｔｏｊｍｅｎｏｖｉｃｒｓ３给出了第一个关于能否避免能量空洞问题的理论结果．和文献［３］一样，作者假定一个圆形网络中的节点均匀分布，节点持续向Ｓｉｎｋ汇报收集到的数据．文中使用的能量消耗模型是Ｅ—ｄ４＋ｃ，口是能量衰减系数，ｄ是数据发送方和接收方的距离，ｃ是一个正值常数．作者进一步假设网络中节点的发射半径可调，证明如果网络中被划分的圆环等宽，在路由上的能耗能够降到最低，但是此时网络中可能会出现能量空洞．作者证明当ａ＞２时通过调整圆环的宽度可以避免能量空洞出现，而ａ＝２时，网络中则无法避免能量空洞形成．在多跳的网络中，能量空洞往往会在离Ｓｉｎｋ近的区域形成．一般认为在离Ｓｉｎｋ较近的地方放置更多的传感器节点是一种能够缓解能量空洞问题的措施，这就是所谓的节点非均匀分布策略．ＬｉａｎＥ２１等人探讨了这种策略对于提高数据容量的有效性；同时他们提出一种路由算法，该算法使部分节点轮流休眠用于节省能量消耗．

Ｏｌａｒｉｕ和Ｓｔｏｊｍｅｎｏｖｉｃ［６３讨论了在网络中采用节点非均匀分布策略避免能量空洞的问题，不同于

２期吴小兵等：无线传感器网络中节点非均匀分布的能量空洞问题２５５

文献［３，５］的是，作者假定网络中节点具有不同的数据率．文中仅考虑节点在发送数据过程中消耗的能量．作者认为如果网络中第ｉ个圆环中节点密度和（志＋１一ｉ）成正比，网络中能够避免能量空洞问题，惫是将圆形网络划分为等宽圆环的最佳数目．在这种方法中，离Ｓｉｎｋ近的节点只能有较低的数据率．Ｐｅｒｉｌｌｏ［８３等人总结了无线传感器网络中出现能量空洞的两种情况．在第一种情况下，网络中所有的传感器节点直接将监测到的数据发送给Ｓｉｎｋ，这样离Ｓｉｎｋ较远的节点更容易耗尽自身的能量．在另外一种情况下，网络中的节点通过多跳方式将监测到的数据传递给Ｓｉｎｋ，这样离Ｓｉｎｋ近的节点较快耗尽自身的能量．当某些节点最先耗尽自身的能量时，在它们监测的区域就形成能量空洞．作者假定节点的通信半径可变，将网络生存周期的最大化问题归结为一个线性规划问题．

文献［９—１３］等探讨了在无线传感器网络中通过分簇机制建立网络层次结构的方法．ＬＥＡＣＨｃ叼使用簇头节点轮换的方法来选择簇头节点，避免簇头过早耗尽自身的能量．和ＬＥＡＣＨ不同，ＨＥＥＤ［１０］在选择簇头节点时考虑了节点的剩余能量和簇内通信代价．ＵＣＳＣｌｌ］，ＥＥＣＳ［坨３和ＥＥＵＣ［１３３考虑到网络中部分簇头节点可能会承担较多的网络流量或者在单位时间内有较多的能耗，提出了形成不同大小的簇的思想．这些方法在能耗较多的区域形成较小的簇，这样簇头节点有较多的剩余能量用于转发来自其他节点的数据．

其他的一些相关工作试图引入动态性来缓解无线传感器网络中能耗不均衡的问题．Ｗａｎｇ［１４３等人使用一个移动中继节点来延长网络的生存周期．作者发现移动中继仅需要在离Ｓｉｎｋ节点两跳范围内移动，网络的生存周期就可以提高近四倍．文中还提出了两种节点移动和路由算法．Ｌｕｏ和Ｈｕｂａｕｘｒｌ５３采用移动Ｓｉｎｋ的方法来解决网络中节点能耗不均衡的问题．由于采用了移动的Ｓｉｎｋ，它周围的节点随着时间不断变化，这样可以避免在Ｓｉｎｋ节点周围形成能量空洞．作者证明在一个圆形的传感器网络中，将Ｓｉｎｋ节点放置在圆心位置最能节省能量，如果采用移动Ｓｉｎｋ的方式，Ｓｉｎｋ沿网络的边缘移动是最符合节能要求的．

３网络模型及假设

与文献［１４］类似，本文假设网络中所有的节点分布在一个半径为Ｒ的圆形区域中．网络中唯一的Ｓｉｎｋ放置于圆心处，如图１所示．我们还假设所有的节点都是同质的，并且都有一个ＩＤ号，每个节点的通信半径固定为１个单位．网络被划分为Ｒ（Ｒ＞１）个相邻的环状区域，每个圆环的宽度是１个单位．从内向外。用Ｇ表示第ｉ个圆环，这样Ｃｌ区域中的节点到Ｓｉｎｋ的距离在（ｉ一１）和ｉ之问．

图１圆形网络区域

另外，假设网络中的每个节点在单位时间内产生和发送Ｌ比特数据，处于圆环｛Ｇｉ≠Ｒ）中的节点需要向Ｓｉｎｋ转发自身和处于圆环｛Ｃｊ｝（ｉ＋１）≤．ｆ≤Ｒ）中节点产生的数据．特别地，圆环Ｇ中的节点不需要为其他圆环中的节点转发数据．另外假设在任何一个转发节点都没有数据聚集（ｄａｔａａｇｇｒｅｇａｔｉｏｎ）过程．本文使用的能量消耗模型是：每个节点的初始能量是￡＞Ｏ．Ｓｉｎｋ没有能量限制．一个节点发送一比特数据消耗的能量是ｅ，，接受一比特数据消耗的能量是ｅ。，这里ｅ，＞ｅ：＞Ｏ．后面我们可以看到本文的结论也适用于ｅｚ＞Ｐ。的情形．

４对节点非均匀分布策略的理论分析

本节我们从能量的角度对在无线传感器网络中采用节点非均匀分布的策略进行理论分析．首先对组成网络的圆环进行能耗分析，然后证明在全网中最高效地实现能耗均衡不可能，即能量空洞不可避免．最后证明在除最外圆环外的内部圆环区域中实现能耗均衡是可能的．

４．１能耗分析

用Ｎ。表示圆环Ｃｉ中传感器节点的数目；Ｅ。表示圆环中所有节点在单位时间内的能耗；假设圆环中节点数据能够经过一跳传递给相邻的圆环，最终以经过ｉ跳后到达Ｓｉｎｋ节点．我们用下面的方式来计算每个圆环中所有节点消耗的能量．

根据以上假设和网络模型，圆环Ｇ中在单位时间内所有节点消耗的能量为

ＥＲ＝ＮＲＬｅｌ．

２５６计算机学报２００８短

其他圆环中的节点既要发送自身产生的数据，又要转发来自外部圆环的数据，所以

Ｅ。＝Ｌ［∑Ｎｔ（ｅｘ－＇［－ｅ２）＋Ｎｉｅｌ］，１≤ｉ≤Ｒ一１。这样每个圆环中所有节点在单位时间内消耗的能量是

ｆＮＲＬｅｌ＇ｉ＝Ｒ

Ｅ＝１Ｌ［１壹Ｍ（ｅｌ＂ｌ＇－ｅｚ）＂ｌ－Ｎｉｅｌ］’１＜艘一１ｑ？４．２网络能耗均衡的不可能性

理想情况下，网络中的每个节点同时耗尽自身的能量时，能耗效率得到了最优化．此时，网络的生存时间是

等一警一一等一等㈤

Ｅ１Ｅ２ＥＲ一１ＥＲ

、。７定理１．最优化能耗效率不可达，即式（２）不可能成立．

证明．仅需要证明在圆环Ｇ和ＣＲ一。之间不可能实现能耗均衡即可．采用反证法证明．

假设

．等＝等㈣

．ＥＲ—ｌＥＲ

“７成立．将式（１）代人式（３）后，经过简单的变换后我们得到

ＮＲ一１￡ＮＲＬｅｌ一ＮＲｅＬ［ＮＲ（Ｐ１＋口２）＋ＮＲ—ｌｅｌ］（４）化简式（４）后得到

ＮＲ（Ｐｌ４－已２）＝０（５）显然式（５）不可能成立．证毕．定理１表明在一个圆形网络中如果节点持续向Ｓｉｎｋ节点汇报数据，节点通信半径固定，即使使用节点非均匀分布策略也无法避免能量空洞的形成．这是由无线传感器网络内在的“多对一”的通信模式决定的．

４．３次优网络能耗均衡

尽管在全网范围内实现节点间的能耗均衡不可能，但是如果能够实现次优的能耗均衡也是非常有用的．我们定义次优的能耗均衡是网络中除了最外圆环中的节点外，其他圆环中的节点能够实现能耗均衡．

定理２．实现次优的能耗均衡在理论上是可能的，此时系统中除圆环ＣＲ中的节点外，其他节点能达到最佳的能耗效率．

证明．我们采用演绎方法证明下面的公式

成立．

学一百Ｎｉ＋一ｌｅ，１≤ｉ≤Ｒ一２

Ｅ｛Ｅ件１’１。‘３一

假设式（６）成立，则

（６）

兴一登Ｒ＞。‘㈣

Ｎ川

∑Ｎ。～

“。

●‘●＿

证明．令Ｎ一∑Ｎｉ表示网络中所有的节点

Ｎｆ胪…Ｎｋ胪善Ｍ

Ｎ件１

Ｎ一∑ｉ＋１Ｎ。Ｎ一奎Ｎ。

一等＞１，２≤ｉ≤Ｒ一２（９）

苫Ｒ－－１胪监箐型＇ｑ＞１＇１≤脚＿１．

∑Ｎ产ＮＲ（口州一１）．

∑Ｎｔ－－ＮＲｑ州（１０’扪撇边羲＝黼…瓮轩

２期吴小兵等：无线传感器网络中节点非均匀分布的能量空洞问题

２５７

５节点非均匀分布策略下的路由

本文提出的节点非均匀分布策略与文献Ｅ２３中的策略类似．基本思想是在离Ｓｉｎｋ较近的圆环中布置较多的节点．不同之处在于：基于前面的理论分析，我们能够定量规划网络中每个圆环中节点的数目．假设圆环Ｇ中节点的密度是Ｐ。，则从最外面的圆环ｃＲ到最里面的圆环Ｃ。，节点密度逐渐下降．因此

ＩＤｌ＞』Ｄ２＞』Ｄ３＞…＞佛

（１１）

在图１中颜色较深的圆环表示该区域的节点密

度较高．

在前面分析结果的基础上，我们假定从圆环Ｇ一。到圆环Ｃ。中的节点数目以等比系数ｑ（ｇ＞１）递增，而圆环ＣＲ和ＣＲ一，中的节点数目之比为

１／（ｑ一１），即

，ｑ＞ｌ，１≤ｉ≤Ｒ一２

（１２）

一ｌ

我们假设网络中的节点通过适当的布置，使得圆环ＣＲ的每个节点能够和圆环Ｃ置一。中的（ｇ一１）个节点直接通信，其他圆环中的每个节点能够和相邻的内环中的ｇ个节点直接通信，且它们间的距离是１个单位长度；这样建立到达Ｓｉｎｋ的路径跳数最小．

令Ｓｉ代表圆环Ｃ，的面积，则圆环Ｃ，中的节点密

度为

ｐ＝盟Ｓｉ一上ｎ（２ｉ－－１）

（１３）ｐ一一

ｋｌＪＪ

再根据式（１２），可以得出两个相邻圆环Ｇ＋。和Ｃｉ之间的节点密度之比为

Ｓｉｎｋ节点，外层节点选择其相邻内环中的对应节点

作为待选中继节点．假设网络中有一个初始化过程，使节点能够发现它的上游节点和下游的ｑ个待选中继节点并且记录下相应的ＩＤ标识（对于最外层的节点只需要发现它的（口一１）个待选中继节点）．为了在待选中继节点中平衡能量消耗，节点每次发送数据时总是选择这些待选中继节点中剩余能量最多的一个．如果存在多个含有最多能量的节点，随机选择它们当中的一个．在进行这种选择的过程中，节点必须和待选中继节点交换相关信息．选择完成以后，源节点就将自己收集到的数据和来自上游的数据发送给选中的中继节点．不转发上游数据的节点将自己的数据直接发送给一个选中的中继节点．被选中的中继节点将重复上述过程直到数据到达Ｃ。中的节点，最后数据被发送给Ｓｉｎｋ节点．

算法１．

基于节点非均匀分布策略的分布式

能耗均衡路由．

１．当从节点ｉ收到能量查询消息ＥＮＥＲＧＹ—ＱＵＥＲｙ＿

ＭＳＧ

如果ＴＨＩＳ．ｐａｒｅｎｔ．ｅｑｕａｌ（ｉ）为真，则Ｓｅｎｄ（ｉ，ＥＮＥＲＧＹ＿．ＡＣＫ—ＭＳＧ）

／／向父节点报告自身剩余能量信息；

否则ＤｉｓｃａｒｄＭｓｇ．

２．当从节点ｉ收到能量查询回复消息ＥＮＥＲＧｌ＿ＣＫ—

ＭＳＧ

如果ＴＨＩＳ．ｃｈｉｌｄ．ｅｑｕａｌ（ｉ）为真，则ＵｐｄａｔｅＥｎｅｒｇｙｌｎｆｏ（ＴＨＩＳ）

／／更新待选中继节点剩余能量信息；

否则ＤｉｓｃａｒｄＭｓｇ．

３．当从节点ｉ收到一个数据转发消息ＤＡＴＡ—ＦＯＲ—ＷＡＲＤ＿ＭＳＧ

①志一ＳｅｌｅｃｔＮｅｘｔＲｅｌａｙ（ＴＨＩＳ）

／／从待选中继节点中选择具有最大剩余能量的一个；②如果ＴＨＩＳ．ｐａｒｅｎｔ．ｅｑｕａｌ（ｉ）为真，则Ｓｅｎｄ（ｋ，ＤＡＴＡ—ＦＯＲＷＡＲＤ＿ＭＳＧ（ｄａｍ））

／／发送数据给中继节点量｝

否则ＤｉｓｃａｒｄＭｓｇ．

③Ｓｅｎｄ（ｋ，ＤＡＴＡ—ＦＯＲＷＡＲＤ—ＭＳＧ（ＴＨＩＳ．ｄａｔａ））

／／发送自身收集的数据给中继节点量．

４．没有收到消息时

①愚一ＳｅｌｅｃｔＮｅｘｔＲｅｌａｙ（ＴＨＩＳ）

／／从待选中继节点中选择最大剩余能量的一个，

②Ｓｅｎｄ（ｋ，ＤＡＴＡ—ＦＯＲＷＡＲＤ＿ＭＳＧ（ＴＨＩＳ．ｄａｔａ））

／／发送自身收集的数据给中继节点五．

６模拟分析

我们对本文提出的节点非均匀分布策略和相应

口

Ｗ气一Ｍ一‰‰一Ｍ

２５８计算机学报的路由算法进行了模拟，并比较了该策略和其他两

种节点分布策略在网络生存周期、网络能量剩余率

和数据送达率三方面的性能．我们采用在第３节中

给出的能量消耗模型，忽略了ＭＡＣ层和物理层的

相关因素．表１中是模拟实验使用的基本参数．

表１模拟参数

参数值

节点初始能鼍（￡）

发送一比特数据消耗能量（ｅ１）接收一比特数据消耗能量（ｅ２）单位数据长度（Ｌ）

网络半径（Ｒ）

最外环节点数（ＮＲ）

相邻内外环节点数目比（ｑ）

１００单位０．７５／１０４单位０．５／１０４单位１０００比特

２～６

４

２～３

６．１节点的剩余能量

首先在半径为４的网络中布置了３２个节点，最外圆环Ｃ４中有４个节点，ｃ３～Ｃ。３个圆环中的节点数目以等比系数２增长．图２中给出了当网络生存周期结束时，网络中每个节点的剩余能量值．其中，ＩＤ号在１和４之间的对应圆环Ｃ４中的节点，ＩＤ号在５和８之间的对应圆环Ｃ３中的节点，依此类推．网络的生存周期被定义为从最开始持续到网络中第一次出现有节点耗尽能量为止．当网络中的节点不能继续接收或者发送数据时，我们就认为该节点已经耗尽了能量．从图２中我们可以看出，当网络的生存周期结束时，最外圆环Ｃ４中节点的剩余能量最多，远大于其他圆环中节点的剩余能量，且其他圆环中节点的剩余能量值都小于０．５，说明这些节点几乎同时耗尽了能量，这和本文的分析一致．然后，我们在同样的网络区域布置了１０８个节点，最外圆环ｃ４中的节点数目是４，ｃ３－－－Ｃ，３个圆环中的节点数目以等比系数３增长．图３中给出网络的生存周期结束时各个节点的能量剩余．同样可以看到除最外圆环有较多能量剩余外，其他圆环中的节点几乎耗尽了能量．这和本文的分析也十分吻合．同时，可以看到外部圆环中的节点都仅有少于０．５个单位的能量剩余，说明了本文提出的基于节点非均匀分布策略的路由算法有非常高的能耗效率．

另外，对比图２和图３中最外圆环中的能量剩余值可以发现ｑ一３时能量剩余较少，可以解释如下：理论上当网络的生存周期结束时，内部圆环中的节点同时耗尽了自身的能量，仅有最外圆环中的节点有能量剩余，因此最外圆环中的剩余能量可以计算如下：

八ｒ．

Ｅ。。ｉｄ砌＝ＮＲｅ一；｝二’竖×ＥＲ．

根据式（１）和式（１２）得

Ｅ删越一盟丛掣（１５）

ｑｅｌｒｃ２

由式（１５）可以看出在其他参数固定的情况下，最外圆环中的剩余能量值仅与最外圆环中的节点数目和ｑ值有关．ｑ值较大时，剩余能量值较小，和模拟结果一致．

棚

龊

谣

藤

《

壮

节点ＩＤ号

图２网络生存周期结束时每个节点的剩余能量，ｑ一２

图３网络生存周期结束时每个节点的剩余能量，口＝３６．２和其他节点分布策略的比较

文献［２］提出的节点非均匀分布策略中假定部分节点不采集数据，仅转发数据．对于外环中采集数据的节点，在内部各个圆环中总是放置相同数目的节点专门用于转发数据．例如，如果最外圆环ＣＲ中有４个节点，则在内部（Ｒ一１）个圆环中各放置４个节点用于转发数据．可以认为采用这种策略的网络退化成一个单跳网络．因此，我们不比较本文提出的节点分布策略和文献ＦＺ－］提出的策略．

我们通过模拟实验比较了本文提出的节点非均匀分布策略和节点随机非均匀分布策略、节点均匀分布策略在网络生存周期、网络能量剩余率和数据送达率方面的性能．本文中所指的节点随机非均匀分布策略是指基于本文的分析，限定网络中各圆

２期吴小兵等：无线传感器网络中节点非均匀分布的能量空洞问题２５９

环中的节点数目；除最外圆环外，节点数目以等比口（ｑ＞１）增长；最外圆环和次外圆环中节点数目之比为１／（ｇ一１）．但每个圆环中的节点随机出现在圆环内的任何位置．节点均匀分布策略是指网络中的节点随机出现在网络中的任何位置，网络中任意圆环中节点的数目不限定．在使用节点非均匀分布和节点随机非均匀分布策略的模拟实验中，我们在最外圆环布置了４个节点，内部圆环以等比ｑ一２增长．我们模拟了网络半径从２到６的情形．所有数据都是算法在运行１０５次后的取平均值得到的结果．为了便于比较分析，我们在节点随机非均匀分布策略和节点均匀分布策略中实现了类似于本文提出的路由算法．算法中仍然有一个初始化过程用于节点找到它的下游中继候选节点．节点总是选择它的下游节点中有最多能量剩余的作为数据转发中继．图４中是网络在３种不同节点分布策略下的生存周期．可以看到网络半径为２时，在网络生存周期方面，采用均匀分布策略和随机非均匀分布策略的网络优于采用非均匀分布策略的网络．同时注意到此时采用均匀分布策略的网络的数据送达率小于５０％，采用随机非均匀分布策略的网络的数据送达率接近５０％，见图６．数据送达率是指Ｓｉｎｋ节点收到的数据占所有节点产生数据的比率．这说明采用这两种节点分布策略时，有接近或者超过一半的数据没有送达Ｓｉｎｋ节点，即圆环Ｃ。中的大部分节点没有转发外围节点的数据，所以网络的生存周期超过采用非均匀分布策略时的网络生存周期．当网络半径大于２时，采用非均匀分布策略时的网络生存周期都超过采用均匀分布策略和随机非均匀分布策略时的网络生存周期，并且随着Ｒ的增长网络生存周期变化不明显，说明了本文提出的非均匀分布策略有较好的扩展性．

勺

ａ

ｊ

ｏ

匣

＼

踩

匣

烛

刊

暑ｌ｝

匿

网络半径／Ｒ

图４不同节点分布策略的网络生存周期

图５中是网络在３种不同节点分布策略下的网络能量剩余率．在本文的讨论中，网络能量剩余率是指在网络的生存周期结束时，网络中剩余的能量总和与网络中所有节点的初始能量总和之间的比值．从图５中我们可以看到，随着网络半径的增大，采用非均匀分布策略的网络的能量剩余率呈递减趋势，使用均匀分布和随机非均匀分布策略的网络的能量剩余率呈递增趋势．采用节点非均匀分布策略的网络的能量剩余率要远低于采用其他两种节点分布策略时的网络的能量剩余率．另外，采用随机非均匀分布策略比采用均匀分布策略也有更高的能耗效率，也印证了非均匀分布策略相对于均匀分布策略的有效性．

瓣

《

熏

删

锰

酶

匿

网络半径／Ｒ

图５不同节点分布策略的网络能量剩余率在图６中，我们给出了这３种不同节点分布策略在数据送达率方面的性能比较．从图中可以看出，采用非均匀分布策略的网络在数据送达率方面表现最好，当网络半径增大时，数据送达率也增加，说明了该策略有较好的扩展性．采用随机非均匀分布策略的网络的数据送达率也呈上升趋势，从侧面再次说明了非均匀分布策略的有效性．

图６不同节点分布策略的数据送达率

２６０计算机学报２００８年

７结束语

本文从理论上分析了针对无线传感器网络中的能量空洞现象而采取的节点非均匀分布策略．分析表明无线传感器网络中，如果节点持续向Ｓｉｎｋ发送数据，即使采用节点非均匀分布策略也无法避免能量空洞的出现，这是由网络本身的多对一的数据通信模式决定的．能量空洞的出现会严重影响网络的能耗效率．尽管如此，我们证明网络中的节点满足一定的关系时，可以在网络中实现次优的能耗效率．本文提出一种新的节点非均匀分布策略并设计了相应的路由算法用于实现这种次优的能耗效率．该策略量化了网络中相邻圆环间的节点数目关系，在此基础上可以算出相邻圆环中的节点密度关系．模拟分析显示使用本文提出的节点非均匀分布策略及相应路由算法的网络达到了次优的能耗效率，网络中仅有非常少的能量被浪费．

节点非均匀分布策略是实现次优的能耗效率的基础．需要指出的是这种高效率同时伴随着一些网络开销．首先，网络中节点数由外环到内环以等比增长，导致网络中的节点总数呈指数级增长．因此，只有当传感器节点能够以低成本大规模生产时，这种节点非均匀策略才有可能．一个可能的替代方法是使用较少的节点，每个节点有不同的初始能量储备［４］．另外，本文假设了一个理想的ＭＡＣ层来处理节点间的信道问题．同时，在实际部署过程中我们还需要非常成熟的传感器节点制造技术和精确部署技术来保证这种非均匀分布策略能够实施．随着技术的进步，有可能对无线传感器网络进行自动化部署，这种自动化部署能够保证本文提出的非均匀分布的部署方案．即使在自动化部署不可行的情况下，也可以采用随机非均匀分布部署的方式．６．２节的实验结果也表明采用随机非均匀分布部署的方式能大幅提升整个网络的性能．

参考文献

［１］ＡｋｙｉｌｄｉｚＩＦ，ＳｕＷ，ＳａｎｋａｒａｓｕｂｒａｍａｎｉａｍＹ，ＣａｙｉｒｃｉＥ．Ａｓｕｒｖｅｙｏｎｓｅｎｓｏｒｎｅｔｗｏｒｋｓ．ＩＥＥＥＣｏｍｍｕｎｉｃａｔｉｏｎｓＭａｇａ－

ｚｉｎｅ，２００２，４０（８）：１０２—１１４

［２３ＬｉａｎＪ，ＮａｉｋＫ，ＡｇｎｅｗＧ．Ｄａｔａｃａｐａｃｉｔｙｉｍｐｒｏｖｅｍｅｎｔｏｆｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓｕｓｉｎｇｎｏｎ－ｕｎｉｆｏｒｍｓｅｎｓｏｒｄｉｓｔｒｉｂｕ—

ｔｉｏｎ．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＤｉｓｔｒｉｂｕｔｅｄＳｅｎｓｏｒＮｅｔｗｏｒｋｓ，

２００６，２（２）ｌ１２１－１４５

Ｅ３］ＬｉＪ，ＭｏｈａｐａｔｒａＰ．Ａｎａｎａｌｙｔｉｃａｌｍｏｄｅｌｆｏｒｔｈｅｅｎｅｒｇｙｈｏｌｅｐｒｏｂｌｅｍｉｎｍａｎｙ－ｔｏ－ｏｎｅｓｅｎｓｏｒｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ

ＩＥＥＥＶｅｈｉｃｕｌａｒ

ＴｅｃｈｎｏｌｏｇｙＣｏｎｆｅｒｅｎｃｅ．Ｄａｌｌａｓ。ＴＸ．２００５Ｉ２７２Ｉ－２７２５

ＬｉａｎＪ－ＣｈｅｎＬ，ＮａｉｋＫ，ＯｔｚｕＴ，ＡｇｎｅｗＧ．Ｍｏｄｅｌｉｎｇａｎｄ

ｅｎｈａｎｃｉｎｇｔｈｅｄａｔａｃａｐａｃｉｔｙｏｆｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ／／

ＰｈｏｈａＳ，ＬａＰｏｒｔａＴＦ，ＧｒｉｆｆｉｎＣｅｄｓ．ＩＥＥＥＭｏｎｏｇｒａｐｈｏｎ

ＳｅｎｓｏｒＮｅｔｗｏｒｋＯｐｅｒａｔｉｏｎｓ．ＩＥＥＥＰｒｅｓｓ，２００４：９１－１８３

ＯｌａｒｉｕＳ，ＳｔｏｊｍｅｎｏｖｉｃＩ．Ｄｅｓｉｇｎｇｕｉｄｅｌｉｎｅｓｆｏｒｍａｘｉｍｉｚｉｎｇｌｉ—

ｆｅｔｉｍｅａｎｄａｖｏｉｄｉｎｇｅｎｅｒｇｙｈｏｌｅｓｉｎｓｅｎｓｏｒｎｅｔｗｏｒｋｓｗｉｔｈｕｎｉ—

ｆｏｒｍｄｉｓｔｒｉｂｕｔｉｏｎａｎｄｕｎｉｆｏｒｍｒｅｐｏｒｔｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ

ＩＥＥＥｌＮＦＯＣＯＭ．Ｂａｒｃｅｌｏｎａ。Ｓｐａｉｎ，２００６：１—１２

０ｌａｒｉｕＳ，ＳｔｏｊｍｅｎｏｖｉｅＩ．Ｄａｔａ－ｃｅｎｔｒｉｃ

ｐｒｏｔｏｃｏｌｓ

ｆｏｒｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ／／ＳｔｏｊｍｅｎｏｖｉｃＩ．ＨａｎｄｂｏｏｋｏｆＳｅｎｓｏｒＮｅｔ—

ｗｏｒｋｓ：ＡｌｇｏｒｉｔｈｍｓａｎｄＡｒｃｈｉｔｅｃｔｕｒｅｓ．Ｗｉｌｅｙ，２００５：４１７－４５６

ＷｕＸＢ，ＣｈｅｎＧＨ，ＤａｓＳＫ．Ｏｎｔｈｅｅｎｅｒｇｙｈｏｌｅｐｒｏｂｌｅｍ

ｏｆｎｏｎｕｎｉｆｏｒｍｎｏｄｅｄｉｓｔｒｉｂｕｔｉｏｎｉｎｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔ—

ｗｏｒｋｓ／／Ｐｒｏｅｅｅｄｉｎｇｓｏｆｔｈｅ３ｒｄＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒ—

ｅｎｃｅｏｎ

ＭｏｂｉｌｅＡｄｈｏｃａｎｄＳｅｎｓｏｒＳｙｓｔｅｍｓ（ＭＡＳＳ）．Ｖａｎ－ｃｏｕｖｅｒ，Ｃａｎａｄａ，２００６Ｉ１８０—１８７

ＰｅｒｉｌｌｏＭ，ＣｈｅｎｇＺ，ＨｅｉｎｚｅｌｍａｎＷ．Ｏｎｔｈｅｐｒｏｂｌｅｍｏｆｕｓ—

ｂａｌａｎｃｅｄｌｏａｄｄｉｓｔｒｉｂｕｔｉｏｎｉｎｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ／／Ｐｒｏ—

ｃｅｅｄｉｎｇｓ

ｏｆｔｈｅＩＥＥＥＧＬＯＢＥＣＯＭＷｏｒｋｓｈｏｐｓｏｎＷｉｒｅｌｅｓｓＡｄＨｏｃａｎｄＳｅｎｓｏｒＮｅｔｗｏｒｋｓ．Ｄａｌｌａｓ，ＴＸ，２００４：７４—７９

ＨｅｉｎｚｅｌｍａｎＷ。ＣｈａｎｄｒａｋａｓａｎＡ，ＢａｌａｋｒｉｓｈｎａｎＨ．Ａｎａｐｐｌｉ－

ｃａｔｉｏｎ－ｓｐｅｃｉｆｉｃｐｒｏｔｏｃｏｌａｒｃｈｉｔｅｃｔｕｒｅｆｏｒｗｉｒｅｌｅｓｓｍｉｃｒｏｓｅｎｓｏｒ

ｎｅｔｗｏｒｋｓ．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＷｉｒｅｌｅｓｓＣｏｍｍｕｎｉｃａｔｉｏｎｓ，

２００２，１（４）：６６０—６７０

ＹｏｕｎｉｓＯ，Ｆａｈｍｙｓ．ＨＥＥＤ：Ａｈｙｂｒｉｄ，ｅｎｅｒｇｙ－ｅｆｆｉｃｉｅｎｔ，

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

ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＭｏｂｉｌｅＣｏｍｐｕｔｉｎｇ，２００４，３（４）ｌ６６０—

６６９

ＳｏｒｏＳ，ＨｅｉｎｚｅｌｍａｎＷ．Ｐｒｏｌｏｎｇｉｎｇｔｈｅｌｉｒｅｔｉｍｅｏｆｗｉｒｅｌｅｓｓ

ｓｅｎｓｏｒｎｅｔｗｏｒｋｓｖｉａｕｎｅｑｕａｌｃｌｕｓｔｅｒｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ

５ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＷｏｒｋｓｈｏｐｏｎＡｌｇｏｒｉｔｈｍｆｏｒＷｉｒｅｌｅｓｓ，Ｍｏ—

ｂｉｌｅ，ＡｄＨｏｃａｎｄＳｅｎｓｏｒＮｅｔｗｏｒｋｓ．Ｄｅｎｖｅｒ，Ｃｏ。２００５

ＹｅＭ，ＬｉＣＦ，ＣｈｅｎＧＨ，ＷｕＪ．Ａｎｅｎｅｒｇｙｅｆｆｉｃｉｅｎｔｃｌｕｓｔｅ—

ｒｉｎｇｓｃｈｅｍｅｉｎｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒ—

ｎａｌｏｆＡｄＨｏｃ＆ＳｅｎｓｏｒＷｉｒｅｌｅｓｓＮｅｔｗｏｒｋｓ。２００７，３（２）：

９９－１１９

ＬｉＣＦ，ＹｅＭ，ＣｈｅｎＧＨ，ＷｕＪ．Ａｎｅｎｅｒｇｙ－ｅｆｆｉｃｉｅｎｔｕｎｅ。

ｑｕａｌｃｌｕｓｔｅｒｉｎｇｍｅｃｈａｎｉｓｍｆｏｒｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ／／

Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２ｎｄＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎ

ＭｏｂｉｌｅＡｄｈｏｅａｎｄＳｅｎｓｏｒＳｙｓｔｅｍｓ（ＭＡＳＳ）．Ｗａｓｈｉｎｇｔｏｎ

ＤＣ。２００５

ＷａｎｇＷ，ＳｒｉｎｉｖａｓａｎＶ，ＣｈｕａＫ．Ｕｓｉｎｇｍｏｂｉｌｅｒｅｌａｙｓｔｏｐｒｏ—

ｌｏｎｇｔｈｅｌｉｆｅｔｉｍｅｏｆｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆ

ｔｈｅＡＣＭＭｏｂｉＣｏｍ．Ｃｏｌｏｇｎｅ，Ｇｅｒｍａｎｙ，２００５ｌ２７０－２８３

ＬｕｏＪ，ＨｕｂａｕｘＪＰ．Ｊｏｉｎｔｍｏｂｉｌｉｔｙａｎｄｒｏｕｔｉｎｇｆｏｒｌｉｆｅｔｉｍｅ

ｅｌｏｎｇａｔｉｏｎｉｎｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ

ＩＥＥＥＩＮＦｏＣｏＭ．Ｓｅａｔｔｌｅ，ＷＡ，２００５Ｉ８１９－８３０ｑ

明

钉

刀

胡

叮

叼

妇

巧

妇

钉

趵

●

０

●

０

０

口

ｎ

口

口

ｎ

叫

２期吴小兵等：无线传感器网络中节点非均匀分布的能量空洞问题２６１

ＷＵＸｉａｏ－Ｂｍｇ，ｂｏｒｎｉｎ１９７９。Ｐｈ．Ｄ．

ｃａｎｄｉｄａｔｅ．ＨｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｆｏＣＵＳ

ｏｎｅｎｅｒｇｙ－ｅｆｆｉｃｉｅｎｔｄｅｓｉｇｎｉｎｗｉｒｅｌｅｓｓ

ｓｅｎｓｏｒｎｅｔｗｏｒｋｓ．

Ｂａｃｋｇｒｏｕｎｄ

Ｉｎａｍｕｌｔｉ－ｈｏｐｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋ，ａｓｕｂｓｅｔｏｆｎｏｄｅｓｂｅｈａｖｅｓａｓｂｏｔｈｄａｔａｏｒｉｇｉｎａｔｏｒａｎｄｒｏｕｔｅｒ．Ｄａｔａｃｏｌ－ｌｅｃｔｅｄｂｙｎｏｄｅｓｗｉｌｌｂｅｓｅｎｔｔｏｔｈｅｓｉｎｋｈｏｐｂｙｈｏｐ．Ａｓａｒｅ－ｓｕｔｔ，ｎｏｄｅｓｎｅａｒｅｒｔｈｅｓｉｎｋａｌｗａｙｓｒｕｎｏｕｔｏｆｅｎｅｒｇｙａｎｄｄｉｅｅａｒｌｉｅｒ。ｌｅａｄｉｎｇｔｏａｎｅｎｅｒｇｙｈｏｌｅｉｎｔｈｅｎｅｔｗｏｒｋ．ＮｏｍｏｒｅｄａｔａｃａｎｂｅｄｅｌｉｖｅｒｅｄｔＯｔｈｅｓｉｎｋａｎｄｑｕｉｔｅａｌｏｔｏｆｅｎｅｒｇｙｉｓｗａｓｔｅｄｗｈｅｎｔｈｅｅｎｅｒｇｙｈｏｌｅａｐｐｅａｒｓ．Ｔｈｅｎｏｎｕｎｉｆｏｒｍｎｏｄｅｄｉｓｔｒｉｂｕｔｉｏｎｓｔｒａｔｅｇｙ，ｉ．ｅ．，ａｄｄｉｎｇｍｏｒｅｎｏｄｅｓｔｏｔｈｅｔｒａｆｆｉｃ－ｉｎｔｅｎｓｉｖｅａｒｅａｓ，ｉｓａｎｉｎｔｕｉｔｉｖｅｗａｙｔＯｔａｃｋｌｅｔｈｉｓｐｒｏｂｌｅｍ．Ｂｕｔｗｈｅｔｈｅｒｔｈｉｓｋｉｎｄｏｆｓｔｒａｔｅｇｙｃａｎｔｈｏｒｏｕｇｈｌｙａｖｏｉｄｔｈｅｅｎｅｒｇｙｈｏｌｅｐｒｏｂｌｅｍｉｓｎｏｔｆｕｌｌｙｅｘｐｌｏｒｅｄ．ＴｈｅａｕｔｈｏｒｓｔｒｙｔＯａｎｓｗｅｒｔｈｉｓｑｕｅｓｔｉｏｎｉｎｔｈｉｓｐａｐｅｒ．Ｔｈｅａｕｔｈｏｒｓｐｒｏｖｅｔｈａｔａｌ—ｔｈｏｕｇｈｔｈｅｅｎｅｒｇｙｈｏｌｅｃａｎｎｏｔｂｅａｖｏｉｄｅｄｉｎａｎｅｔｗｏｒｋｗｉｔｈｎｏｎｕｎｉｆｏｒｍｎｏｄｅｄｉｓｔｒｉｂｕｔｉｏｎａｎｄｃｏｎｓｔａｎｔｄａｔａｒｅｐｏｒｔｉｎｇ，

ＣＨＥＮＧｕｉ—Ｈａｉ。ｂｏｒｎｉｎ１９６３，ｐｒｏｆｅｓｓｏｒ。Ｐｈ．Ｄ．ｓｕｐｅｒ—ｖｉｓｏｒ．Ｈｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎｎｅｔ—ｗｏｒｋｓ，ｈｉｇｈｐｅｒｆｏｒｍａｎｃｅｃｏｍｐｕｔｅｒａｒｃｈｉｔｅｃｔｕｒｅ，ｇｒａｐｈｔｈｅｏ—ｒｙ，Ｐ２Ｐｃｏｍｐｕｔｉｎｇａｎｄｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ．

ｓｕｂｏｐｔｉｍａｌｅｎｅｒｇｙｅｆｆｉｃｉｅｎｃｙｉｓｓｔｉｌｌｐｏｓｓｉｂｌｅ．Ｔｈｅａｕｔｈｏｒｓｐｒｏｐｏｓｅａｎｅｗ

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

ＴｈｉｓｗｏｒｋｉｓｓｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＢａｓｉｃＲｅｓｅａｒｃｈＰｒｏ—ｇｒａｍ（９７３Ｐｒｏｇｒａｍ）ｏｆＣｈｉｎａｕｎｄｅｒｇｒａｎｔＮｎ２００６ＣＢ３０３０００，ｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃ?ｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒｇｒａｎｔｓＮｏｓ．６０５７３１３１，６０６７３１５４

ａｎｄ６０７２１００２，ａｎｄＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＪｉａｎｇｓｕＰｒｏｖｉｎｃｅｕｎｄｅｒｇｒａｎｔｓＮｏ．ＢＫ２００５２０８ａｎｄＮｏ．ＢＧ２００７０３９．Ｔｈｅｇｒｏｕｐｈａｓｐｕｂ—ｌｉｓｈｅｄｈｉｇｈｌｙｓｅｌｅｃｔｉｖｅｒｅｓｅａｒｃｈｐａｐｅｒｓｉｎｔｈｅｆｉｅｌｄｓｏｆｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ，ｗｉｒｅｌｅｓｓ

ｍｅｓｈｎｅｔｗｏｒｋｓ，ａｎｄＰ２Ｐｓｙｓ—

ｔｅｍｓ．

无线传感器网络中节点非均匀分布的能量空洞问题

作者：吴小兵， 陈贵海， WU Xiao-Bing， CHEN Gui-Hai

作者单位：南京大学软件新技术国家重点实验室,南京,210093

刊名：

计算机学报

英文刊名：CHINESE JOURNAL OF COMPUTERS

年，卷(期)：2008，31(2)

被引用次数：16次

参考文献(15条)

1.Akyildiz I F.Su W.Sankarasubramaniam Y.Cayirci E A survey on sensor networks 2002(08)

2.Lian J.Naik K.Agnew G Data capacity improvement of wireless sensor networks using non-uniform sensor distribu-tion 2006(02)

3.Li J.Mohapatra P An analytical model for the energy hole problem in many-to-one sensor networks 2005

4.Lian J.Chen L.Naik K.Otzu T,Agnew G Modeling and enhancing the data capacity of wireless sensor networks 2004

5.Olariu S.Stojmenovic I Design guidelines for maximizing li-fetime and avoiding energy holes in sensor networks with uni-form distribution and uniform reporting 2006

6.Olariu S.Stojmenovic I Data-centric protocols for wireless sensor networks 2005

7.Wu X B.Chen G H.Das S K On the energy hole problem of nonuniform node distribution in wireless sensor net-works 2006

8.Perillo M.Cheng Z.Heinzelman W On the problem of un-balanced load distribution in wireless sensor networks 2004

9.Heinzelman W.Chandrakasan A.Balakrishnan H An appli-cation-specific protocol architecture for wireless microsensor networks 2002(04)

10.Younis O.Fahmy S HEED:A hybrid,energy-efficient,distributed clustering approach for Ad hoc sensor networks 2004(04)

11.Soro S.Heinzelman W Prolonging the lifetime of wireless sensor networks via unequal clustering 2005

12.Ye M.Li C F.Chen G H.Wu J An energy efficient cluste-ring scheme in wireless sensor networks 2007(02)

13.Li C F.Ye M.Chen G H.Wu J An energy-efficient une-qual clustering mechanism for wireless sensor networks 2005

14.Wang W.Srinivasan V.Chua K Using mobile relays to pro-long the lifetime of wireless sensor networks 2005

15.Luo J.Hubaux J P Joint mobility and routing for lifetime elongation in wireless sensor networks 2005

相似文献(10条)

1.期刊论文曾志文.陈志刚.刘安丰.ZENG Zhi-Wen.CHEN Zhi-Gang.LIU An-Feng无线传感器网络中基于可调发射

无线传感器数据收集网络的多对一收集特征容易导致网络局部区域的能量消耗较高,形成能量空洞,从而导致整个网络过早死亡.文中通过分析无线传感器网络的数据分发特征,得到传感器网络的能量消耗分布情况、不同区域节点的寿命及其引起的数据传送延迟.在此基础上,在保证应用延迟需求前提下,提出了网络寿命最大化的求解算法.然后,依据数据传输率、能量消耗与延迟之间的相互影响,对可能形成能量空洞的区域选择一定比例的数据以较短的发射半径发送到能量消耗低的区域,以进一步提高网络性能.理论分析与模拟实验结果表明,该策略可延长网络寿命达17%.

2.学位论文龚颖莹一种支持有效域区分的无线传感器网络多径路由机制2009

随着现代微电子技术、无线通信技术、信号处理技术、计算机网络技术等的进步，传统的传感器信息获取技术从独立的单一化模式向集成化、微型化，进而向智能化、网络化方向发展，无线传感器网络成为信息获取最重要和最基本的技术之一。目前无线传感器网络技术已引起工业界和学术界的极大关注，成为当前信息领域研究和开发的热点，广泛应用于军事、环境监测、医疗护理、交通控制等领域。

路由协议是无线传感器网络的重要支撑技术之一，路由协议的性能和整个网络的性能密切相关。目前无线传感器网络著名的按需路由协议如AODV、MSRP等在完成数据分组从源节点到目的节点转发的同时，保证源和目的之间的单路径路由距离最短和能量消耗最优。然而随着无线传感器网络部署规模不断扩大，网络能量均衡、转发效率和路由稳定性逐渐成为路由协议设计重点考虑的因素，多径路由逐渐成为无线传感器网络研究的热点之一。由于无线传感器网络部署环境复杂，在设计多径路由时，必须考虑能量空洞、数据拥塞、覆盖盲区以及灾害发生等无效区域，本论文首次基于有效域区分设计一种无线传感器网络多径路由协议。

论文首先深入研究了当前无线传感器网络典型单路径路由协议和多径路由协议，分析当前路由协议设计考虑的因素和特点。然后提出本论文所设计的支持有效域区分的多径路由机制，描述了路由协议的设计思路，给出了具体的设计方案；详细描述了路由选择与转发方法，给出了报文格式；并通过在相交节点时引入“邻居表交互机制”；给出隔离无效区域的方法，以及实现有效域区分的多径路由具体方案。

随后，在北京交通大学下一代互联网互联设备国家工程实验室自主研发的微型传感路由器MSR6680上成功实现了该协议，并给出了在室内小型网络规模实际环境下的测试结果，进行了性能分析，与其它同类协议进行了对比。实验结果表明，本论文所设计的机制在稳定性、减少能量消耗的不均匀性、以及支持有效域区分等方面具有优势。最后，对论文所做工作进行总结，并对下一步工作提出改进意见。

3.期刊论文刘洪涛.程良伦.LIU Hong-tao.CHENG Liang-lun具有移动汇聚节点的环境监测系统设计-计算机工程

与应用2010,46(19)

环境污染是可持续经济发展中必须解决的问题,如何采取高效、便捷的方法监测环境显得尤为必要.设计了一种基于无线传感器网络的远程环境监测系统,并采用移动汇聚节点的方法,解决节点能量更换频繁且容易产生的"能量空洞"问题.实验结果表明.基于移动汇聚节点的环境监测系统能够延长网络的生命周期,确保各个节点的能量消耗均衡,并且网络整体数据包丢失率和时延与固定汇聚节点的监测系统接近.

4.期刊论文刘安丰.吴贤佑.陈志刚.Liu Anfeng.Wu Xianyou.Chen Zhigang一种基于PSO的有效能量空洞避免的无

线传感器路由算法-计算机研究与发展2009,46(4)

无线传感器网络路由的一个重要问题是如何有效地均衡整个网络的能量消耗水平,避免形成能量空洞,从而导致整个网络过早死亡.基于无线传感器网络特性,首先将路由问题转化为线性规划问题.并证明了路由问题与线性规划问题的等价性.在此基础上.利用粒子群算法(particle swarm optimization algorithm,PSO)来求解能量空洞避免路由问题.算法重新定义了PSO的粒子、粒子的运算与"飞行"规则,提出了基于PSO的无线传感器路由优化算法.算法不仅能够适用于平面网络,经过稍加改进同样可以适用于层次网络的路由算法.通过理论分析证实了算法的正确性,同时大量的模拟实验证实了算法的有效性.

5.期刊论文石婷婷.杨云.陈拥军.陈洁.张赟.SHI Ting-ting.YANG Yun.CHEN Yong-jun.CHEN Jie.ZHANG Yun一种

基于数据融合的WSN节点部署策略-微电子学与计算机2009,26(10)

采用非均匀的方法部署节点,提出了一种基于数据融合的节点部署策略.针对节点数据采集率恒定的圆形网络场景,根据避免能量空洞以及降低数据冗余度的思想部署传感器节点,通过该策略使得网络达到次级能耗均衡.仿真结果表明该方法能够缓解能量空洞问题,延长网络生命周期.

6.期刊论文刘安丰.阳国军.陈志刚.LIU An-feng.YANG Guo-jun.CHEN Zhi-gang基于不等簇半径轮换工作的传感

器网络能量空洞避免研究-通信学报2010,31(1)

从理论上分析了分簇网络不同簇半径下的能量消耗情况,得到的结论是:1)给出了网络寿命最大时的簇半径τ的计算表达式;2)提出一种新颖而简单的采用不等簇半径轮换工作的能最空洞避免策略,其核心是:网络寿命取决于能量消耗最大节点的能量消耗,当采用不等的簇半径轮换工作时,其能量消耗最大的节点不是同一节点,因而其综合的能量消耗比采用最优的固定簇半径的能量消耗还少,从而可有效提高网络寿命.理论分析与模拟实验结果表明,该策略实施简单,又能够有效地避免能量空洞现象,并显著地延长了网络的存活时间.

7.学位论文曾雅丽无线传感器网络延长网络生命周期算法的研究2010

无线传感器网络，是由一组数量大、成本低的传感器结点以无线

通信的方式构成的无线自组织网络。目前己被广泛应用于军事通信、

医疗、环境监测、农业等诸多领域，具有非常广阔的应用前景。

在传感器网络中，结点一般是通过多跳传输方式将感知信息传送

到基站，但是，结点采用多跳传输通常会产生能量空洞现象，即距离基

站较近的结点由于数据转发任务重而过早耗尽自身的能量，导致网络

无法正常工作或者网络原有覆盖区域缺失的现象。网络能耗不均衡是

产生能量空洞现象的原因，能量空洞现象使得网络生命周期结束而网

络中大量结点剩余了能量。另外，传感器结点的电池能量有限且无法

进行充电，如果每个结点都以最大功率传输数据，结点有限的能量将

被快速消耗，降低了网络生命周期。本文通过网络能耗均衡的策略来

避免能量空洞，提高能量利用率；通过功率控制来优化网络拓扑结构，

降低结点能量消耗，延长网络生命周期。本文主要完成了以下两个方

面的工作：

1)分析能量空洞现象产生的原因以及目前能耗均衡的策略。提

出了一种能耗均衡的非均匀分簇算法UCEA，避免了靠近基站的簇头

结点引起能量空洞的现象，使网络的能量消耗均衡，延长了网络寿命。

2)分析功率控制算法对网络生命周期的影响以及功率控制算法

存在的问题。提出了功率控制算法LSPT，该算法保证网络连通，并

使整个网络中结点间的路径能量消耗最小化；算法还加入避免能量空

洞现象的步骤，更大限度地提高能量的利用率。仿真实验表明：与

LMST，CBTC，K-neigh算法相比，LSPT算法更加节省了网络能量消

耗，延长了网络生命周期。

关键词：无线传感器网络，网络生命周期，能耗均衡，功率控制

8.期刊论文陈传峰.林玮.CHEN Chuan Feng.LIN Wei无线传感器网络不均匀环带能量均衡策略-电子技术应用

2009,35(6)

无线传感器网络的监测应用是典型的多对一网络,离Sink较近的节点需承担更多的通信负载,更容易过早地耗尽自身的能量,使网络在有大量剩余节点的情况下死亡.为此提出采用不均匀环带设计使节点能耗均衡,从而延长网络寿命的策略.利用本方法,在实际情况下不仅能确定环带半径,还延长了网络寿命.

9.期刊论文陈拥军.杨云.陈俊钦.石婷婷.张敬.杨婷.CHEN Yong-jun.YANG Yun.CHEN Jun-qin.SHI Ting-ting.

ZHANG Jing.YANG Ting一种基于Dijkstra+策略的路由空洞算法GEAR+-微电子学与计算机2009,26(10)

针对无线传感器网络中地理位置和能量路由(GEAR)算法可能产生的路由空洞问题,GEAR算法通过改变自身和邻居节点的代价来解决问题,但同一节点可能会再次遇到同一路由空洞.文中提出了一种基于Diikstra+策略的路由空洞GEAR+算法可以避免上述问题.仿真分析表明,该算法在平均能量消耗和节点发送数据分组的数量上都优于GEAR算法.

10.期刊论文王亮.钟先信.石军锋无线传感器网络能耗平衡策略的研究-传感器世界2007,13(3)

无线传感器网络中存在的多对-数据流使得节点能量消耗极不平衡,严重缩短了网络的生存时间.文章首先分析了网络中能耗不平衡的成因以及产生的影响,然后详细阐述了解决无线传感器网络能耗不均匀的几种策略,并分别指出了各种策略的特点,最后探讨了解决此类问题的发展方向.

引证文献(12条)

1.黄布毅.王俊.胡智宏.崔光照基于非均匀分蔟无线传感器网络自适应数据传送机制的研究[期刊论文]-计算机测量与控制 2010(2)

2.王建文.邹昌伟基于非均匀数据率的无线传感器网络平衡耗能算法[期刊论文]-福建师范大学学报（自然科学版） 2010(2)

3.胥楚贵.邓晓衡.邹豪杰无线传感器网络覆盖空洞修复策略[期刊论文]-传感技术学报 2010(2)

4.张萃玲.陈志刚.刘安丰.曾志文非均匀部署WSN的能量空洞避免策略[期刊论文]-计算机工程 2010(2)

5.万润泽.缑西梅.雷建军基于无线传感器网络的能量高效的非均匀分簇算法[期刊论文]-计算机工程与科学

2009(9)

6.陈传峰.林玮无线传感器网络不均匀环带能量均衡策略[期刊论文]-电子技术应用 2009(6)

7.胥楚贵.邓晓衡.邹豪杰无线传感器网络通信半径动态调整的能耗均衡策略[期刊论文]-传感技术学报 2009(5)

8.袁辉勇.李素君.羊四清.戴经国分层传感器网络的最大化寿命模型与求解[期刊论文]-计算机应用 2009(5)

9.袁辉勇.彭东海.王志和.彭剑圆环形传感器网络生命周期最大化模型与求解[期刊论文]-传感器与微系统

2009(2)

10.杨军.张德运非均匀分簇的无线传感器网络数据传送机制[期刊论文]-西安交通大学学报 2009(4)

11.王骥.徐国保.沈玉利基于无线传感器网络的海水检测系统设计[期刊论文]-通信技术 2008(12)

12.王骥.徐国保.沈玉利基于无线传感器网络的海水检测系统[期刊论文]-电讯技术 2008(9)

本文链接：https://www.sodocs.net/doc/07823525.html,/Periodical_jsjxb200802009.aspx

授权使用：中北大学(zbdxtsg)，授权号：c1612dae-9934-400c-aa72-9e2b00eff68b

下载时间：2010年11月11日