传感器网络中一种最大生命周期的路径覆盖算法

刘志雄,邓旭东

(长沙学院 计算机工程与应用数学学院,长沙410022)(中国科学院 低温工程重点实验室,北京 100190)

1 引 言

随着传感技术、分布式信息处理和嵌入式计算技术的日益成熟,无线传感器网络(Wireless Sensor Networks,WSNs)在军事和民用领域获得了越来越广泛的应用[1].受限于体积和成本,传感器节点携带的电池能量极其有限且难以补充.因此,最大化监测寿命是WSN的核心目标之一[2].

在入侵检测等重要应用中,需要由传感器对目标物的移动路径进行覆盖,该类问题称为路径覆盖(path coverage)[3].国内外学者分析了节点部署密度与路径覆盖概率之间的关系[11-14],并针对一类特定场景提出了路径覆盖算法[15].这些工作假设目标物的移动轨迹为直线路径,且在特定场景中对传感器的精度、带宽等有特殊要求,在实际应用中受到很大限制.此外,已有算法没有对资源有限的传感器网络进行能量优化.针对以上问题,本文提出了一种基于最大加权二分匹配的路径覆盖算法,将路径离散成一些点,并将传感器节点分成多个可以独立覆盖路径的组,最后利用最大加权二分匹配对组内节点进行调度.

2 相关工作

为了对目标区域实施有效监控,需要根据监测任务完成覆盖部署.覆盖问题通常分为点覆盖、区域覆盖、栅栏覆盖和路径覆盖[3].以下分别对这四类覆盖问题的研究工作进行介绍.Abrams等[4]证明了最大化生命周期的传感器网络k覆盖是NP完全问题,并提出了随机算法和分布式贪婪算法.随机算法的思想是各节点随机选择一个覆盖集加入,该方法易于实施且鲁棒性强,但覆盖概率较低.在分布式算法中,各节点依据最大化自身收益的原则,按照编号顺序逐个选择覆盖集.由于节点在决策前需获取之前节点的决策信息,故该算法不属于严谨的分布式算法.此外,每个节点仅做一次决策,无法保证获得最优解.

Cardei等[5]提出了一种传感器网络目标覆盖的集中式算法DSC(disjoint set covers).DSC先将目标覆盖抽象成最大流图问题,然后给n个节点分配任务集.每个节点仅属于一个任务集,且每个任务集可以独立覆盖所有目标.接下来依次调度每个任务集轮流监控目标并传送数据,从而提高网络工作寿命.然而,一旦网络拓扑发生变化,这种静态分组策略将带来较大的维护开销.

Lu等[6]证明了即便所有传感器和目标点处于同一欧式平面,目标覆盖和数据收集的生命周期最大化是NP难问题,并提出了一种多项式时间的近似算法.其思想是通过构建虚拟骨干网络保证网络连通性,还通过调整节点感知半径实现能量有效覆盖,由路径中的叶子节点对网络进行监控并收集数据,其他节点只收集数据,然后构建最小权值的覆盖、数据收集树对节点进行调度.

Kumar等[7]提出了一种传感器网络栅栏覆盖生命周期最大化算法.算法通过寻找最大数量的不相交路径,分时间片轮流调度这些路径来监测栅栏,以最大化网络生命周期.无需在局部交换信息,各节点在时间片中以预定概率p进入活动状态,但无法保证覆盖概率.算法还推导了弱栅栏存在的临界条件,为后续栅栏覆盖的研究[8-10]提供了理论依据.

Ram等[11]和Manohar等[12]分别在同构和异构节点模型下,对二维区域中节点部署密度和路径k覆盖平均比例之间的关系进行了分析,并给出了数学表达式.Harada等[13]和Lei等[14]分别针对路径1覆盖和k覆盖的情形,研究了节点部署密度与覆盖概率之间的关系.上述工作仅研究了直线路径覆盖,在实际应用中具有很大的局限性.

Zhang等[15]提出了一种适用于无线多媒体传感器网络的路径覆盖算法MTPCA(Moving Target based Path Coverage-enhancing Algorithm),将一种新的概率模型应用到基于虚拟势场的有向传感器网络中,并利用覆盖影响因子来校正扇区的中心位置,以达到更好的覆盖效果.MTPCA还通过路径曲线离散技术来获取目标点的实时位置,并利用节点间相互作用力和协作通信来调整传感器的移动方向,从而实现少量传感器对目标移动轨迹的覆盖.然而,由于对节点配备的能量及带宽要求较高,MTPCA无法顺利用于常规的传感器网络应用中.

综上可知,点覆盖、区域覆盖和栅栏覆盖的研究已经较为成熟,但路径覆盖及能量优化的研究还存在着不足.因此,本文基于曲线离散技术和最大加权二分匹配技术,提出了一种最大化生命周期的传感器网络路径覆盖算法.

3 问题及定义

3.1 问题描述

问题1.最大生命周期的路径覆盖.在传感器网络中存在路径￡,n个传感器节点S1,S2,…,Sn,调度传感器节点覆盖路径￡,并最大化网络生命周期L.

图1 传感器覆盖路径Fig.1 Sensors covering path

其中,路径覆盖的生命周期是指,从路径￡能被传感器节点完整覆盖的时间t0,到￡中任意一个点无法被覆盖的时间t1之间的时间段,即L=t1-t0.

本文通过分组调度传感器来实现最大生命周期的路径覆盖,例如在图1中,先将节点分为两组:W1={S3,S5,S7,S9,S12},W2={S1,S2,S4,S6,S8,S10,S11},然后轮流调度W1和W2来覆盖路径.这种分组可能并非最优,但通过一些启发式规则来接近最优.

3.2 相关定义

传感器Si的能量记为ASi,其所覆盖的路径￡中的点集合记为C(Si).路径￡中的点Pi简称路径点,N(Pi)表示覆盖点Pi的传感器集合.

定义1.覆盖加权二分图.WSNs中覆盖加权二分图定义为:B=(V1,V2,E).其中V1、V2和E分别表示传感器的集合、路径点的集合和边的集合.其中,边是指:若路径点Pk∈C(Sj),则ei=(Sj,Pk)是B中的一条边.边ei的权值w(ei)等于传感器Sj的能量,即w(ei)=ASj.

图2 最大加权二分匹配Fig.2 Maximum weighted bipartite matching

定义2.最大加权二分匹配.在二分图B=(V1,V2,E)中,匹配是指由一组无公共顶点的边构成的集合,其边的权值之和最大的匹配称为最大加权二分匹配.

如图2中,最大加权匹配是{(S1,P3),(S2,P2),(S3,P1)},权值之和为7.

4 启发式算法

最大生命周期的路径覆盖算法包括三个步骤:

1)首先,将路径离散成一些点;

2)其次,将传感器节点随机分为h组,再对组进行合并,使得每个组都能独立覆盖所有路径点;

3)然后,调度各组轮流覆盖路径,并对组内的传感器进行调度.各个传感器组的生命周期之和就是传感器网络路径覆盖的最大生命周期.以下分别介绍三个步骤.

4.1 路径离散

路径离散的目标为:对给定路径￡进行曲线离散,产生离散点的集合Q.

路径离散的过程为:假设路径￡上所有点的x坐标值的范围为(x1,xk),设定步长值d,先取路径￡中x坐标值为x1的点加入到集合Q,然后依次在x轴上移动距离d并相应从路径￡中取点,再将所取的点添加到集合Q,当取到x坐标值为xh的点结束.由于取点次数为(xk-x1)/d,故算法的时间复杂度为O((xk-x1)/d),算法具体描述如下:

输入:路径￡,步长值d1,最小和最大x坐标x1,xk

输出:一组离散点

1.Note the minimum and maximum x-coordinates in ￡ asx1,xk;

2.Set step-valued;

3.IfQis empty,xi=x1;

4.Else wherexi<=xk

5. get pointP=(xi,f(xi)),

6.Q=Q+{P},xi=xi+d;

7.ReturnQ.

4.2 传感器分组

传感器分组包括两个阶段,首先随机将传感器分成h组,其次,由于部分组无法覆盖所有路径点,故采取策略将一些组进行合并,使得合并后的每个传感器组都能覆盖所有路径点.第一阶段为随机分组,其目标为:给定路径￡上的m个点P1,P2,…,Pm,以及n个部署的传感器节点S1,S2,…,Sn,寻找h个传感器分组T1,T2,…,Th,且每个分组能覆盖￡中的部分点.

随机分组的过程为:对每个路径点Pi,将覆盖Pi的传感器集合N(Pi)随机分成h组,最终将产生h组传感器,且每组传感器能覆盖路径￡中的部分点.算法需循环h*m次,每次从各个N(Pi)中随机移除部分传感器,共n个传感器,故算法的时间复杂度为O(mnh).算法具体描述如下:

输入:离散点集合Q,传感器S1,S2,…,Sn

输出:传感器组T1,T2,…,Th

1.N(P1)=Ø;

2. Fori=1 tohdo

3. Forj=1 tomdo

4. select random subsetN′ of N(Pj);

5.Ti=Ti+(N′-N(P1));

6.N(Pj)=N(Pj)-(N′-N(P1));

7.N(P1)=N(P1)+(N′-N(P1));

8.ReturnT1,T2,…,Th.

第二阶段为随机合并分组,其目标为:给定h组传感器T1,T2,…,Th,以及一组路径点Q={P1,P2,…,Pm},产生一组集合W1,W2,…,Wr(r≤h),使Wi能覆盖所有路径点.

随机合并分组的过程为:首先,将所有组以覆盖路径点数量的多少按照升序排序,其次,选取排序后的第一个组Ti,若其能覆盖所有路径点,则将Ti放入Wi并从分组中移除;反之,将Ti放入Wi后并选取下一个组Ti+1,若Ti+1能覆盖Wi无法覆盖的路径点,则将Ti+1加入Wi.重复上述步骤,直到Wi能覆盖所有路径点,或所有分组都被考虑到但仍无法覆盖全部路径点.如果还有路径点无法被Wi覆盖,则需考虑是否存在其他Wj能覆盖所有路径点.如果不存在,则返回null,反之剩余组及Wi都将被放置于Wj中.

由于计算每个传感器覆盖的路径点的时间复杂度为O(mnh),将h组传感器进行排序的时间复杂度为O(hlogh),合并分组的时间复杂度为O(h2),且logh

输入:传感器组T1,T2,…,Th,离散点集合Q

输出:新的传感器组W1,W2,…,Wr

1.T={T1,T2,…,Th},Q={P1,P2,…,Pm};

2.SortTby the number of covered points;

3.a=1;T′=T;Z=Q;

4.Whilea<=hdoWa=Ø;b=1;

5. WhileT′ &Z&(b<=h)do

6. If |C(Tb)-(Q-Z)|<=0

7.b++; continue;

8.Wa=Wa+{Tb};T′=T′-Tb;

9.Z=Z-C(Tb);b++;

10. IfZis emptya++

11. Else Ifa<=1 return NULL;

12. else addT′ intoWa-1;

13. addWrintoWa-1;a--;

14.ReturnW1,W2,…,Wa.

4.3 组调度及传感器调度

传感器分组之后,调度这些组进行监控,并使得路径覆盖生命周期最大化.由于组之间不相关,故调度顺序对网络生命周期没有影响.易知对每个组运行一次调度,即可实现网络生命周期最大化,该过程耗时O(a),其中a为传感器组的数量.

接下来对组内的传感器进行调度,其目标为:给定一组传感器W1,W2,…,Wa,以及一组路径点Q={P1,P2,…,Pm},调度传感器覆盖所有路径点,并使生命周期最大化.

传感器调度的过程为:先构建一个覆盖加权二分图B;再从图中找出一个最大加权二分匹配;接下来,由于要调度能量最多的传感器工作,因此,若选出的传感器无法覆盖所有路径点,则针对没有被覆盖的路径点继续构建覆盖加权二分图B′,直到所有路径点被覆盖或者直到剩余传感器都无法覆盖所有路径点.

为描述方便,将最大加权二分匹配简记为MWM(maximum weighted matching),传感器节点和边的数量均为n,路径点数量为m,最大加权匹配需要遍历所有传感器、边和路径点,故其耗时O(n2m),接下来还需遍历路径点求解B′,故总时间耗费为O(n2m2w),其中w是指所有边的最大权值.算法具体描述如下:

输入:传感器组W1,W2,…,Wr,离散点集合Q

输出:Wi中的节点调度

1.ConstructB=(V1,V2,E);

2.Find a MWM inB,denoted byM;

3.While there is unmatched vertex inV2do

4.Denote unmatched vertices set byV2′;

5.ConstructB′ fromV1,V2′;

6.Find a MWM inB′;

7.For each vertexvinV2,letM(v)be the matched vertex inV1,and minimum energy in allM(v)is noted asmin_er;

8.ScheduleM(v)to covervandM(v),so each vertex inV1matched by vertex inV2spendmin_erenergy;

9.Delete the vertices inWiout of energy.

4.4 仿真实验

为了进一步验证算法性能,本文利用phython语言和C++语言建立了模拟仿真平台.仿真环境如下:在100×100m2监控区域中,取中心点为坐标原点(0,0),路径￡采用曲线函数y=0.1(x-10)(x-20)(0≤x≤100)产生,且路径￡被离散成10个点,传感器节点随机分布在路径点周围,节点初始能量为5和10之间的随机数.

实验1和实验2中,传感器感知半径为6m;实验三中,传感器节点的感知半径范围为1m～22m.实验1中,传感器节点的数量范围为0～200;实验2和实验3中,传感器节点的数量为150.假定传感器覆盖的点都是连续的,即若传感器Si覆盖离散的路径点Pj和Pk,则路径上Pj和Pk之间的点也能被Si覆盖.限于篇幅,仅给出了当传感器节点数量n、节点初始能量ASi以及传感器感知半径rs分别发生变化时,网络生命周期L变化情况方面的实验数据.取15次仿真实验的平均值作为试验结果.

实验1考察了网络生命周期随传感器数量变化的情况,如图3所示.从图中可以看出:

1)当网络中部署的传感器非常少时,传感器覆盖路径的生命周期为0,例如当n≤16时,L=0.其原因是此时没有足够的传感器来覆盖这些路径点.

2)随着传感器数量的增加,传感器覆盖路径的生命周期呈上升趋势,例如当n由25增大到100时,L则从6增到42.因为有越来越多的传感器覆盖网络中的路径点,故覆盖路径生命周期逐渐增大.

图3 生命周期L随传感器数量n变化Fig.3 Change of lifetime L with size of sensors n

图4 生命周期L随节点初始能量ASi变化Fig.4 Change of lifetime L with initial energy of sensors ASi

图5 生命周期L随节点感知半径rs变化Fig.5 Change of lifetime L with sensing radius of sensors rs

实验2给出了当n=150,且每个传感器具有相同的初始能量时,网络生命周期随传感器节点初始能量的变化情况,如图4所示.从图中可以看出,随着传感器的初始能量增大,传感器盖路径的寿命迅速增加,例如当ASi=5时,L=60,而当ASi增大到20时,L达到了410.这是因为节点初始能量是影响路径覆盖生命周期的关键因素之一,当传感器具有更多能量可供消耗时,生命周期也相应更大.

实验3观察了生命周期随传感器节点感知半径rs的变化情况,其中每个传感器随机具有5～10的初始能量,如图5所示.从图中可以看出,网络生命周期随传感器的感知半径增大而增多,例如当rs=2时L为40,而当rs=5时L为95.但是当感知半径增加到某个阈值时,网络的寿命不再增加,例如当rs≥7.5时L保持110不变,因为感知半径达到该阈值时传感器已经覆盖整个网络区域.

5 结 论

本文针对已有传感器网络路径覆盖算法存在的不足,提出了一种最大生命周期的路径覆盖算法.利用曲线离散将路径分割成点,并将部署的传感器分成多个能独立覆盖路径的组,再采用最大加权二分匹配技术对传感器组内节点进行调度,从而在覆盖路径的同时最大化网络生命.仿真实验考察了节点数量、节点初始能量及节点感知半径等因素对网络生命周期的影响.对算法性能进一步优化将是接下来的工作.