无线传感器网络中一种延长寿命的覆盖算法*

崔彦新,刘三阳,冯海林

(西安电子科技大学理学院,西安 710071)

无线传感器网络由大量的传感器节点组成,这些节点随机部署或者固定安置在监测区域,以感知、采集和处理监测区域中被测对象的信息,它们使用自身携带的电池供电,因此,有效且合理地利用有限的能量是无线传感器网络设计的核心[1-2],最小化能量消耗并最大化网络寿命成为无线传感器网络研究的热点之一。

现有的延长网络寿命的方法通常是在已知节点地理位置信息的条件下进行的,但是获取地理位置信息需要的开销很大,并且精度难以保证。若所获得的地理位置信息有误差,则许多延长寿命的算法就达不到预期的效果。Gaurav S.Kasbekar等人在文献[3]中第一次提出了一种分布式无坐标的调度机制,在保证完全覆盖的条件下,延长了网络寿命。算法需要精确的节点间的距离信息,可以通过文献[4-5]中提到的方法来确定。

但是文献[3]中的 DLM算法有一个明显的不足,就是 DLM算法一旦探测到覆盖空洞即告终止,即使网络中大量的节点还有很多的能量储备。这样不利于能量的有效利用[6]。如果可以将有能量储备的节点的能量利用起来,必然会很好的延长网络的寿命。因此,为了提高节点能量的利用率,本文在DLM算法基础上进行了改进,将传统的节点“休眠或激活”调度机制一般化,提出一种调整感知半径的节点调度算法 ASR-DLM(Ad justable Sensing Range-Distributed Lifetime Maximization)。这种方法有以下优点：①因为能量的消耗与感知半径的大小有直接的关系,感知半径越大,消耗的能量就越多,本文算法通过调整感知半径的大小,可以省去由于多余的覆盖而产生的能量浪费,提高能量的利用率。②ASR-DLM还可以完成对覆盖空洞的探测与填补。现有的覆盖空洞探测与填补的方法都是基于精确的地理位置信息的,而本文的算法不需要地理位置信息,节省了使用 GPS及信标节点的成本。另外,与需要地理位置信息的算法相比,可以避免由于定位误差的存在而影响网络服务质量。③与 DLM算法相比,DLM算法在探测到覆盖空洞时终止,寿命结束,本文的算法可以对探测到的覆盖空洞进行填补,大大延长了网络寿命。

1 网络模型

1.1 网络描述

考虑由n个传感器节点集合 S组成的无线传感器网络,传感器节点随机地分布在矩形区域。本文假设传感器节点的监测范围和通信区域满足单位圆性质[7]。传感器节点的感知半径可以调整,节点 u的感知半径集合用 Rs(u)表示,Rs(u)={r(1),r(2),…,r(p)},其中,r(1)表示传感器节点感知半径最小值;r(p)表示感知半径最大值。传感器节点的通信半径固定,用Rc表示。如果传感器网络中节点的通信半径大于两倍的感知半径,且无线传感器网络满足覆盖,则此网络为连通网络[7]。本文假设传感器节点的通信半径大于两倍的感知半径,则有 Rc＞2 r(p)。

另外,根据文献[3]中的要求,因为传感器节点不知道全局位置信息,所以,选择的节点部署区域比监测区域稍大一点。位于监测区域边界上的节点称为外围节点;位于监测区域内部的节点称为内部节点。每个节点可以根据文献[8-9]中提出的方法判断自己是外围节点还是内部节点。

1.2 模型假设

假设以下条件可以满足：

(1)假设可以得到两个节点相互之间的精确距离。

(2)传感器节点有着同步的时钟。

(3)每个传感器节点初始能量 B。

(4)处于休眠模式的传感器节点几乎不消耗能量,我们假定为 0。

(5)用 ek表示节点感知半径为 k时,单位时间消耗的能量,其中 eu(k)=cs◦r2(k),其中 cs为感知系数[6]。

(6)用 tk表示节点通信时消耗的能量,则 tk=ρ◦ct◦Tr4(u),19≤cs：ct≤35,其中,Tr(u)表示通信距离,ρ表示通信密度,例如 ρ=0.1表示 10个单位时间通信一次[6]。

2 预备知识

定义 1覆盖集：对于一个传感器节点组成的集合 C⊆S,若 C中的传感器节点的感知区域可以把监测区域完全覆盖,则称 C为一个传感器覆盖集,这里简称为覆盖集[3]。

定义 2覆盖空洞：传感器网络中如果存在一片连续的区域不被任何传感器节点的感知范围所覆盖,那么这片未被监测的连续区域称为一个覆盖空洞[7]。

定义 3如果两个传感器节点 u,v∈S的感知圆盘相交,则称这两个节点交叉。感知圆盘边界相交的两个交点称为交叉点[3]。

性质 1节点 u,v∈S的感知半径分别为 ru和rv,节点 u,v之间的距离记为 du,v,则它们是相交的当且仅当du,v＜ru+rv,du,v+ru＞rv,du,v+rv＞ru[3]。

性质 2考虑一个覆盖 C⊂S,设 u∈C与任何其他传感器节点都不交叉,则 C-{u}也是一个覆盖[3]。

定理 1考虑一个集合 C⊂S,C是一个覆盖集当且仅当 C中节点的感知区域可以覆盖 P中所有点[3]。设 P是监测区域内部所有交叉点组成的集合,简称为交叉点集。

推论 1在无线传感器网络工作时,设激活的传感器节点组成的集合为 A,P是交叉点集,若 A中节点的感知范围不能将 P中所有点覆盖,则覆盖空洞产生。

证明因为A中节点的感知范围不能将 P中所有点覆盖,根据定理 1,A不是一个传感器覆盖集,不能将监测区域完全覆盖,因此覆盖空洞产生。证毕。

根据推论 1,可以进行覆盖空洞的探测,本文的ASR-DLM算法就是根据推论 1进行覆盖空洞的探测。

用到的术语：

空洞边缘节点 传感器网络中如果存在一个传感器节点,其感知范围边缘某段圆弧未被其它传感器节点的感知区域所覆盖,则称节点为空洞边缘节点[7]。

图1 覆盖空洞

空洞边缘交叉点 传感器网络中如果存在两个空洞边缘节点互为感知邻居,且这两个传感器节点中存在一个交叉点,不被这两个节点之外的第 3个节点的感知范围所覆盖,则称该交叉点为空洞边缘交叉点[7]。简称边缘交叉点。

空洞边缘邻居 传感器网络中如果两个节点互为感知邻居并且这两个节点之间的交叉点至少有一个为空洞边缘交叉点,则这两个节点互为空洞边缘邻居[7]。

空洞环 传感器网络中相邻的空洞边缘节点组成的集合,与集合中节点的邻居组成的并集。如图2所示。

图2 空洞环

如图 2所示,{A,B,C,D,E,F,G}形成一个空洞环,{a,b,c,d,e,f,g}是空洞边缘交叉点。

3 问题与算法设计

3.1 问题陈述

最大化网络寿命问题是指在满足服务质量(如覆盖、连通等)条件下,采用节点轮换调度模式,轮换激活/休眠模式,每一轮中仅将部分节点投入活跃工作状态,而将冗余节点投入低功耗的睡眠状态,这样可以达到减少能量消耗和延长网络寿命的目的[3]。

文献[3]中DLM算法有初始化和激活两个阶段。首先初始化整个网络,使每个节点获知网络参数,这个步骤在网络开始运行时执行一次。然后,在每个子时间段开始时,即每一轮开始时,进入激活阶段。每个激活阶段选取一个最优的覆盖集,将最优覆盖集中的节点投入激活状态,开始工作,直到子时间段的结束。但是文献[3]中的 DLM算法有一个明显的不足,就是 DLM算法一旦探测到覆盖空洞即告终止,即使网络中大量的节点还有很多的能量储备。这样不利于能量的有效利用。为了提高节点能量的利用率,本文在 DLM算法基础上进行了改进,将传统的节点“休眠或激活”调度机制一般化,提出一种调整感知半径的节点调度算法ASR-DLM(Adjustable Sensing Range-Distributed Lifetime Maximization)。

3.2 算法设计

ASR-DLM算法由初始化、感知半径选择和激活三个阶段组成。初始化阶段使每个节点获知网络参数,在网络开始工作时执行一次。在每个子时间段,即每一轮,开始时首先选择感知半径的大小,然后执行激活阶段,选取最优覆盖集。

网络寿命随传感器节点的感知半径的增加而减小[11-12],因此,本文的算法尽可能设置小的感知半径。对节点的感知半径进行选择,需要先对每个节点赋权,对任意节点 u∈S,计算选取权值最大的感知半径为最优感知半径大小。其中 Pu是指节点 u感知范围内的交叉点组成的集合。|Pu|表示节点 u感知范围内的交叉点数目。因为感知半径越大,消耗能量就越多,所以,这里利用选择权值最大的感知半径,达到最小感知消耗和覆盖最多交叉点的双重目标,其中 Pu可以在没有地理位置信息的条件下获得[3]。

确定最优感知半径大小之后,选取最优覆盖集,方法根据文献[3]中的 DSC算法进行。

如果存在最优覆盖集,选取最优覆盖集中节点为激活节点,传感器网络开始正常工作;若不存在最优覆盖集,即探测到覆盖空洞,这时进行覆盖空洞的填补。

根据推论 1探测是否有覆盖空洞,若探测到覆盖空洞,则增加传感器节点的感知半径,遵循空洞填补准则将覆盖空洞填补,达到完全覆盖后,网络开始正常工作。

空洞填补准则 空洞边缘节点在增加其感知半径过程中,应遵循：(1)感知半径增加的长度为一个单位长度,也就是说,若节点 u∈S的感知半径是r(k)时,将感知半径增加到 r(k+1)。若增加一个单位长度的感知半径未能填补覆盖空洞,再增加一个单位长度的感知半径,依次类推。(2)增加感知半径后,必须使得空洞边缘交叉点的数目减少。通过空洞边缘交叉点的数目不断减少至零,则覆盖空洞被填补完全。(3)给每个空洞边缘节点赋权,权值根据每增加一个单位长度的感知半径所能覆盖空洞边缘交叉点的数目来确定,拥有较大权值的节点优先增加其感知半径。这样就可以保证消耗最少的能量以覆盖较多的空洞边缘交叉点。(4)在空洞填补的过程中,需要保证覆盖空洞不会由于增加感知半径而造成当前空洞数量的变化,即填补节点不应该将覆盖空洞分裂[7]。如图 3所示,增加节点 C的感知半径造成了本来的覆盖空洞分裂成了两个覆盖空洞,这样就形成了两个空洞环。如果每次填补空洞都被分裂,最终会由于分裂的空洞个数过多而造成空洞填补工作的大大增加。

图3 空洞的分裂

3.3 寻找空洞环的方法

步骤①：空洞边缘节点的确定

有推论可知,当感知范围不能覆盖交叉点集 P中某些点时,覆盖空洞产生,因为 P中的点都有唯一的ID作为标识,因此,网络中传感器节点可以根据这个标志来确定是否为空洞边缘节点。若是空洞边缘节点,则通知邻居节点。这样,每个空洞边缘节点都有一个集合存储着它的空洞边缘邻居集。如图 3(a)中节点 A的空洞边缘邻居集就是 Nh(A)={C,G}。

步骤②：确定空洞环上的节点

当探测到覆盖空洞时,空洞边缘节点发起空洞环探测过程,对于如图 3(a)中所示的覆盖空洞而言,节点 A是空洞边缘节点,它发送 “空洞环”报文给空洞边缘邻居 Nh(A)={C,G},报文是由 A及 A的空洞边缘邻居 Nh(A)={C,G}组成的集合 H。然后 C和 G同时将“空洞环”报文进行修改,H=H∪Nh(C)-H∩Nh(C),然后发送给自己的空洞边缘邻居,包括节点 A。若“空洞环”报文不再有更新,则说明已经找到与节点 A相关的空洞环。

步骤③：计算空洞环上节点的填补权值

图4 增加感知半径

3.4 ASR-DLM算法

ASR-DLM算法的详细步骤,对于时段 j,进行以下算法：

Step 0 在时段 j开始时,计算节点的感知半径的最优值,将感知半径设置为最优值。

Step 1 在时段 j开始时,对任意节点 u∈S,计算 μ=4◦n◦B,c(u)=μl(u)和 W(u)=cu(j)/Bu。其中l(u)表示节点 u在时段 j开始时已消耗能量与初始能量的比值。Bu表示节点 u的初始能量,B表示所有节点初始能量的最大值。[3]

Step 2 对任意节点 u∈S,使用 DSC算法[3]确定节点的状态(工作 or休眠),并且确定最优的感知半径大小。

Step 3 根据推论 1探测覆盖空洞。若在上一步骤中激活节点的感知范围不能将交叉点集 P中所有点覆盖,说明有覆盖空洞产生,进入 Step4;激活节点的感知范围能将 P中所有点覆盖,则说明没有覆盖空洞,无线传感器网络可以正常工作,直到时段j结束。

Step 4 寻找空洞环。一个网络中可能会有若干个空洞环。对每个空洞环计算 Step 5。

Step 5 计算空洞环上的节点的填补权值Wh(u)。

Step 6 选择最大填补权值的节点,增加此节点的感知半径,并且向空洞邻居节点广播“增加”消息,消息包括节点的新感知半径,并更新空洞边缘节点集及空洞边缘交叉点集,形成新的空洞环,并向空洞边缘节点广播“新空洞环”消息,若“新空洞环”为空集,转 Step 7;否则转 Step 5。

Step 7 若已经不存在空洞环,转 Step 8;否则转Step 5。

Step 8 进入正常工作阶段,直到时段 j结束。

3.5 算法分析

从 ASR-DLM算法的步骤中可以看到,DLM算法在探测到覆盖空洞时即终止,而 ASR-DLM在此基础上,对覆盖空洞进行填补,从而延长了网络寿命。从能量角度来说,ASR-DLM算法从一开始就选择最优的感知半径,提高节点的能量利用率;然后再选择覆盖集,经过若干轮后,DLM算法探测到覆盖空洞并且宣告终止,但是 ASR-DLM算法还可以利用某些节点的剩余能量对覆盖空洞进行填补,无疑会延长网络寿命,填补覆盖空洞过程中消耗的能量,比如,确定空洞环消耗的能量,只有在探测到覆盖空洞时才发生,由此产生的额外的通信能量消耗只占节点总能量的一小部分,因此,不会对网络的寿命产生影响。

4 仿真

仿真实验在一个 50×50的方形区域中随机均匀部署节点,节点的初始能量是 B,DLM算法中感知半径与通信半径分别为 10和 22;ASR-DLM算法的感知半径为 Rs={8,9,10,11}和 22;对于每一个激活节点,每个时段消耗能量采用 eu(k)=cs◦r2(k),模型,其中 cs为感知系数,这里取 cs=0.01,则 DLM算法中激活节点每时段消耗的能量为 1,而 ASRDLM算法中激活节点每时段消耗的能量为 Es={0.64,0.81,1,1.21}。下面比较 DLM算法[3]和ASR-DLM算法。

首先检验 ASR-DLM算法和 DLM算法[3]获得的网络寿命随节点数目 n的变化情况,如图 5所示。仿真结果表明,ASR-DLM算法确实优于 DLM算法,并且随着节点数目的增多,优越性越突出。然后检验 ASR-DLM算法和 DLM算法[3]获得的网络寿命随节点初始能量大小 B的变化情况,如图 6所示。结果表明,两种算法获得的网络寿命都随着初始能量的增加,近似呈现线性关系,说明了两种算法中能量均能有效利用,但是,拥有较高初始能量时,使用ASR-DLM算法比 DLM算法获得了更长的网络寿命,总体来说,ASR-DLM算法是优于 DLM算法的。

图5 初始能量为 15,网络寿命随节点总数的变化情况

图6 节点总数为 150时,网络寿命随初始能量的变化情况

5 结论

本文设计了一种分布式无需地理位置信息的延长网络寿命算法,采用调整传感器节点感知半径的方法,在保证完全覆盖的基础上延长了网络寿命,可以将它扩展到 k-覆盖。本文的算法也可以用于覆盖空洞的探测与填补,在无需地理位置信息的条件下很有意义。

[1]Wang J,Medidi S,Medidi M.Energy-Efficient K-Coverage for Wireless Sensor Networks with Variable Sensing Radii[C]//Global Telecommunications Conference,Honolulu,2009：4518-4523.

[2]张晓丽,韩芳希,王瑞.基于 Voronoi图的无线传感器网络的节点调度机制[J].计算机应用,2006,26(6)：199-200.

[3]Kasbekar G,Bejerano Y,Sarkar S.Lifetime and Coverage Guarantees Through Distributed Coordinate-Free Sensor Activation[C]//Proceeding of the 15thAnnual International Conference on Mobile Computing and Networking Mobi Com 09.Beijing：ACM Press,2009：169-180.

[4]AlaviB,Pahlavan K.Modeling of the TOA-Based Distance Meas-urement Error Using UWB Indoor Radio Measurements[J].IEEE Communications Letters,2006,10(4)：275-277.

[5]Wen C,Morris R,Sethares W.Distance Estimation Using Bidirectional Communications Without Synchronous Clocking[J].IEEE Transactions on Signal Processing,2007,55(5)：1927-1939.

[6]Lu Mingming,Wu Jie,Cardei M,et al.Energy-Efficient Connected Coverage of Discrete Targets in Wireless Sensor Networks[J].International Journal ofAd Hoc and Ubiquitous Computing,2009,4(3/4)：137-147.

[7]苏瀚,汪芸.传感器网络中无需地理信息的空洞填补算法[J].计算机学报,2009,32(10)：158-170.

[8]Zhang C,Zhang Y,Fang Y.Detecting Coverage Boundary Nodes in Wireless Sensor Networks[C]//Proceeding of ICNSC,2006,6(4)：868-873.

[9]Wang Y,Gao J,Mitchell J.Boundary Recognition in Sensor Networks by Topological Methods[C]//Proceeding of the 12thAnnual International Conference on Mobile Computing and Networking.Los Angeles：ACM Press,2006：122-133.

[10]Guo LX,Wang X.Integrated Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks[J].ACM Transactions on Sensor Network,2005,1(1)：36-72.

[11]杨文国,郭田德,赵彤.异构监测传感器网络寿命最大化模型及其求解[J].计算机学报,2007,30(4)：532-538.

[12]孙瑞华,马春光,张国印,等.异构传感器网络代价最小模型[J].计算机应用,2008,28(5)：1280-1286.