有向传感网分块区域p-覆盖节点调度算法研究*

2015-05-09陈常超孙力娟

传感技术学报 2015年1期

关键词：传感消息部署

陈常超,孙力娟,韩崇,郭剑

(1.南京邮电大学计算机学院,南京 210003;2.江苏省无线传感网高技术研究重点实验室,南京 210003)

有向传感网分块区域p-覆盖节点调度算法研究*

陈常超,孙力娟*,韩崇,郭剑

(1.南京邮电大学计算机学院,南京 210003;2.江苏省无线传感网高技术研究重点实验室,南京 210003)

本文研究了分块区域p-覆盖的有向传感网节点调度问题,并提出了一种有效延长网络生存时间的节点调度方案。将区域划分为拥有不同监测需求的子区域,从有向传感器节点感知模型出发,设计了基于网格划分的节点感知范围度量方法,并在此基础上提出了分布式分区域节点调度算法DSSA(Distributed Subarea Sensor-schedule Algorithm),该算法是一个选取最少数量的节点去对每一个子区域进行p-覆盖的分布式贪心算法。算法同时还考虑了整体网络的连通。通过仿真深入评估了DSSA算法的性能。对比实验结果表明,DSSA算法可以显著延长网络生存时间。

有向传感网络;节点调度;区域划分;p-覆盖

无线传感网络WSNs(Wireless Sensor Networks)作为一种将逻辑上的信息世界与客观上的物理世界融合在一起的方式,参与到了许多实际应用中,例如实时流量监控、空气质量监控、污染监控等等[1]。无线传感网络感知节点有多种,过去大部分工作基于全方位角度感知的全向传感器假设,但在实际应用中存在多种有向传感器,例如相机传感器、超声传感器和红外传感器等[2-4]。节点调度作为提高WSN节点利用效率的一个方式,引起了很多学者的极大关注[5-7]。本文研究就是基于有向传感网络的节点调度问题。

针对于许多监测需求不严格的场景,部分的观测失误或者数据丢失也是可接受的,因此此类场景通常进行部分覆盖。例如,雨季对森林进行火灾监测时,由于雨季火险等级明显低于旱季,此时通常采用部分覆盖监测。同时森林的不同区域监测需求存在差异:在树木密度大或较为干燥区域,监测需求较高;而在树木密度小或有池塘沼泽等区域,监测需求相应较低。由此,针对不同的监测区域,采取不同的覆盖度是更加合理的一种方案。本文研究充分考虑区域覆盖时存在不同子区域监测需求不同的情况,提出了根据监测需求进行区域分块并单独调度的算法设计。

1 相关研究

WSNs覆盖调度问题已经取得广泛研究。Cheng等[8]针对有向传感网络,研究了“最大有向区域覆盖”MDAC(Maximum Directional Area Coverage)问题,即最大化覆盖区域面积。文中提出一种分布式贪心算法DGreedy(Distributed Greedy Algorithm)解决MDAC问题。Han等[9]针对有向传感器节点组成的有向传感网络中时空覆盖调度问题进行研究,设计了基于网格划分的基本区域生成方法,并在此基础上提出了节点最大覆盖调度迭代选择MaxGreedy算法。Chen等[10]同样通过网格划分的方法研究了无线传感网中的节点调度问题,其节点感知模型为圆形,最终提出了一个简单的近似算法来选取满足工作需求的最少节点来进行检测工作。以上研究成果都是将整个待覆盖区域作为一个整体,拥有相同的覆盖需求,来进行节点调度研究。然而在大面积部署传感器节点时,通常不同区域拥有不同监测需求。Li等[11]提出覆盖区域分块划分的概念,针对节点感知模型为圆形的情况下进行了节点调度算法的研究,提出了集中式覆盖调度算法(CPCA)和分布式覆盖调度协议(DPCP)。Zhou等[12]针对有向传感网进行了节点的覆盖调度研究,其研究成果同样考虑到目标重要性不同,然而其覆盖目标为关键点而非区域。最终提出了一个基于贪心算法的近似算法来对节点进行部署与调度。Zhang等[13]针对WSN多重覆盖问题进行了研究,提出了节点轮换唤醒与休眠的调度思路。

本文在以上研究基础上,考虑不同子区域监测需求不同的情况,基于网格划分方法,对基于有向感知模型的节点进行了调度算法的研究。对比已有算法增加了算法的普适性和精确性,对节点感知范围异构、子区域异构等都进行了考虑。

图1 有向传感节点感知范围模型

2 问题定义

2.1 节点感知模型

本文主要研究有向传感节点的调度问题,为便于抽象,将有向传感节点的感知模型定义在二维空间中[14]。如图1所示。

本文研究区域覆盖问题,节点或网络覆盖率的计算基于网络中节点的感知区域。

2.2 网络覆盖模型

本文考虑一个部署有N个有向传感节点的二维区域M,并且假设不存在两个节点部署位置相同。区域覆盖模式为冗余覆盖,即充分考虑节点衰亡情况,高密度部署了N个节点以提供调度保障,不同节点的监测区域可能存在重叠。下面给出本文中的p-覆盖定义。

定义1(P-覆盖) 给定二维区域M,根据不同监测需求将大区域M划分为不同的小区域Mj,并根据每个子区域的实际监测需求分别为其指定一覆盖比例pj。通过节点调度使任意子区域Mj满足:

(1)

则称该区域满足p-覆盖,该无线传感网络是满足p-覆盖的网络。

其中Sj表示子区域Mj的面积,Nj表示子区域Mj中部署的节点个数,seti表示子区域Mj中节点si感知范围内的网格集合,Ei表示节点si的存活状态,a表示网格划分步长。

如图2所示,整个二维区域M根据实际需求划分为了9个子区域M1～M9,每个子区域拥有不同的大小和形状。根据不同子区域的重要性,为每个子区域Mj设定一个需求覆盖比例pj。每个子区域中部署有异构的有向传感节点。子区域M7是一个比较重要的区域,因此需要90%覆盖。然而,针对子区域M2和M9,可能其非重要区域,因此仅50%覆盖就足够。通过这种策略,用户可以在部署阶段获得更大的自由度。同样是N个节点,在部署时可以根据不同子区域的权重,在关键子区域部署更多的传感器节点而对非关键区域则部署较少的节点,由此可以在相同的成本下有效地提高节点利用率。

图2 网络覆盖模型

图2中画出的节点数量并不代表实际部署数量,节点部署是一次性工作,因此在实际部署中通常进行更高密度的节点部署。

在针对全覆盖问题的研究中,网络终结的标志是节点不能对覆盖区域提供完全无死角覆盖。而本文研究覆盖问题为非全覆盖情况,同时还对覆盖区域根据重要性不同进行了划分,因此以往研究中的网络终结标志在此处并不适用。考虑到不同子区域拥有不同的覆盖需求和面积,本文将网络终结时间定义如下:

定义2(网络终结时间) 给定二维区域M,将其划分为J个子区域,对每一个子区域Mj设置覆盖需求pj,随着节点因为能量减少而衰亡,当满足:

(2)

时,表明网络终结。

其中,

(3)

(4)

Sj表示子区域Mj的面积,f为网络覆盖度,由用户根据覆盖需求给定。Bj表示子区域Mj的状态,Nj表示子区域Mj中部署的节点个数,seti表示子区域Mj中节点si感知范围内的网格集合,Ei表示节点si的存活状态,a表示网格划分步长,ei表示节点si的能量剩余。

综上,定义分块区域p-覆盖节点调度问题如下:

定义3(分块区域p-覆盖节点调度问题) 给定满足p-覆盖的区域M,通过设计节点调度算法使之在满足p-覆盖的前提下尽可能延长网络生存时间。

3 本文算法

根据上节对节点及网络覆盖模型的定义,由于有向传感节点感知区域为扇形,并且节点感知模型异构且扇形的相交区域多为非凸多边形,通常在判断感知区域时,可以将连续的节点监测区域看作是由均匀离散的点组成,因此本文采用网格划分的方法来刻画节点覆盖区域,在网格化完成后,节点的监测区域通过网格点集合来表示。根据上文问题描述及定义,本文设计了如下调度算法。

3.1 分区域节点调度算法

假设有充足的节点被部署在二维区域M,区域M根据实际覆盖需求分为J子区域,并且节点部署满足p-覆盖,即

针对任意子区域Mj,有

(5)

图3 网络工作模式

本节提出一个分布式分区域节点调度算法DSSA来完成对区域的覆盖,算法在每一个子区域中分布式执行来进行节点调度工作,最终算法能够在保证每个子区域覆盖比例pj的同时最大化网络生存时间。定义网络工作模式为:决策期+运行期。决策期即算法执行阶段,通过执行DSSA算法在每一个子区域Mj选取一个工作节点集worksetj;运行期激活worksetj中的节点进行工作。当运行期结束后,重新进入决策期选取下一运行期需要激活的节点,如此往复循环执行。虽决策期网络并不能提供监测,但是与运行期相比,决策期的时间非常短,因此本文假设决策期带来的覆盖损失和能耗损失忽略不计。由于算法是循环执行的,在此定义1个决策期与1个执行期合称为网络工作模式中的一个网络周期,如图3所示。下面重点叙述决策期所执行的DSSA算法。

DSSA算法包含两部分,分别工作于如下两个阶段:选取阶段和连通阶段。每一阶段都有一固定的时间长度,该时间长度可保证算法在该阶段能够执行完毕,从而不会影响下一阶段算法的执行,如图3所示。

上图中选取阶段和连通阶段的短虚线表示该阶段的实际结束时间,其一定是在下一阶段开始之前,也就是说网络工作模式中每一网络周期都是相等的,从而保证选取阶段算法结束后不同子区域的连通阶段算法可以同步执行,进行连通不同子区域的操作。选取和连通阶段的具体任务为:①选取阶段:所有子区域Mj独立执行选取算法来构建一个能保证该子区域监控需求pj的节点集合worksetj;②连通阶段:将所有子区域的节点集合连通起来。

在每一个网络周期的开始,下面的算法都会在所有子区域中执行,来构建能够对子区域提供pj比例覆盖的worksetj。在描述算法之前,先做如下定义:

网格点状态(有效、无效) 针对任一节点si的感知网格点集seti,若seti中某一网格点已经被worksetj中的节点覆盖,则称在seti中该网格点状态为无效,否则称该网格点状态为有效。

有效网格点集Useti节点si感知网格点集seti中未被标记为无效的网格点集合,初始状态下Useti与seti相等。

重复网格点集Rseti节点si感知网格点集中被标记为无效的网格点集合,初始状态下Rseti为空。

子区域j当前覆盖网格点集Allnumj当前周期的决策期结束后,所有工作标志位q为1的节点所覆盖的网格点数目(集合中无重复网格点)。

3.1.1 选取阶段算法

算法1 选取阶段算法(执行于每一个节点si)

输入:子区域Mj的覆盖需求pj,Mj的面积Sj,网格步长a

输出:工作节点集worksetj(部分)

执行:

1:初始化:

2: Allnumj=0qi=0

3: 随机选择一节点,向其发送消息包msg(beRoot)

4: (算法执行于任一子区域Mj中的任一节点si中)

5:节点自动唤醒

6:if 接收到消息包msg(beRoot)

7:qi=1sroot=si

8: worksetj=worksetj∪sroot

9: Allnumj=Allnumj+numof(Usetroot)

11: goto算法2:连通阶段算法

12: else

13: 向所有邻居广播消息包msg(IamRoot)

//消息包中包含Usetroot字段

14: end if

15:end if

16:if接收到消息包msg(IamRoot)

17: ifq=1

18: throw msg

19: else

20: Rseti=Rseti+(Useti∩ Usetroot)

21: Useti=Useti-(Useti∩ Usetroot)

22: 计算worthi的值,并封装为消息包msg(worthi),回传至其邻居根节点sroot

23: end if

24:end if

25:if接收到消息包msg(worthi)

26: ifq=0

27: throw msg

28: else

29: 选择最大的两个worth值记为Firworth,Secworth

30:snextroot=node(Firworth>Refworth? Firworth:Refworth)

//消息包msg(beRoot)中包含Allnumj、Refworth字段

31: ifsnextroot=sFirworth

32: msg(beRoot).Refworth=Secworth

33: else

34: msg(beRoot).Refworth=0

35: end if

36: 向snextroot发送消息包msg(beRoot)

37: end if

38:end if

39:ifq=1且未接收到消息包msg(worthi)

40: if Refworth!=0

41:snextroot=sRefworth

42: 向snextroot发送消息包msg(beRoot)

43: else

44: ifspreviousroot==NULL

45: 宣告子区域死亡,算法在该子区域Mj中停止执行

46: else

47: 向节点spreviousroot发送消息包msg(reCall)

48: end if

49: end if

50:end if

51:if接收到消息包msg(reCall)

52: ifq=0

53: throw msg

54: else

55:sroot=spreviousroot

56: goto 13

57: end if

58:end if

初次部署或上一周期运行阶段结束时,所有节点自动唤醒。算法随机选取一个节点s并将其设置为初始根节点sfirstroot(3行)。在决策期所有节点都将保持唤醒状态。当节点收到msg(beRoot)信息,其将自己q置1,加入worksetj。此时该节点称为根节点sroot。sroot执行:Allnumj=Allnumj+numof(Usetroot),然后考察Allnumj,如果满足:

(6)

子区域Mj选取阶段完成,算法转至连通阶段(6行～11行)。否则,sroot向邻居节点广播msg(IamRoot)消息包,消息中包含Usetroot(13行)。当节点si收到邻居根节点sroot发来的当选消息包,如果qi为1,忽略此消息包。如果qi为0,节点考察Useti与当选消息包中携带的Usetroot是否有重复网格点,如果有重复,将重复网格点从Useti中删除,加入Rseti。节点完成Useti和Rseti的更新后,计算自身worthi值并回传给sroot(16行～24行)(worth值的计算见3.2节)。

sroot接收到邻居节点回传的worth值,从中选取最大的两个worth值(记为Firworth和Secworth)和其对应的节点信息进行存储。然后sroot比较Firworth和msg(beRoot)包中的Refworth值的大小,选取较大者对应的节点记为snextroot,向snextroot发送msg(beRoot)信息。beRoot信息:如果snextroot为Firworth对应的节点,beRoot信息中的Refworth写为Secworth,否则,beRoot信息中的Refworth值置0.beRoot信息中还包含Allnumj(25行～38行)。

如果sroot未接收到邻居节点回传的worth值(说明sroot没有邻居节点或邻居节点已死亡),并且beRoot中的Refworth为0,sroot向其上一级根节点spreviousroot发送msg(reCall)回溯消息包。spreviousroot收到msg(reCall)回溯消息包后,算法转至13行。如果向上回溯至sfirstroot仍然不能找到snextroot,Bj置0,宣告子区域Mj死亡,Mj中的算法结束执行(39行～58行)

3.1.2 连通阶段算法

算法执行至此说明选取阶段已经结束,下面将进入连通阶段,将各个子区域中选取出来的工作节点集连通起来。算法等待连通阶段的起始时间点,当起始时间点到达,每一个worksetj中节点都将广播一个msg(connect)连通消息包,定义连通信息包的最大转发次数为Maxstep。连通信息包中包含变量distancej,初始为1,指代距离worksetj集合中节点的跳数,连通消息包每被转发一次,distancej加1。信息包中还包含转发过该消息包的路径节点信息。在接下来的算法中,Mk将会被用来代表子区域Mj的任何一个邻居子区域。对于任意节点si,其针对所在子区域Mj和其任意邻居子区域Mk维护有对应的变量Mindistancej和Mindistancek,初始为最大值,指代节点si距离worksetj和worksetk最短距离。算法伪代码如下:

算法2 连通阶段算法(执行于每一个节点si)

输入:节点工作集worksetj(部分)(即算法2的输出)

输出:节点工作集worksetj

执行:

1:(算法执行于任一子区域Mj中的任一节点si中)

2:if接收到消息包msg(connect)

3:ifqi=1

4:throwmsg

5:else

6:distancez++//z的取值可能为j或k

7:ifdistancez≥Maxstep

8:throwmsg

9:else

10:ifdistancez≤Mindistancez

11: 用distancez更新节点自身维护的Mindistancez

12:else

13: 用节点自身维护的Mindistancez更新distancez

14: 向邻居节点广播消息包msg(connect)

15:endif

16endif

17:endif

18:endif

19:ifMindistancej+Mindistancek≤Maxstep

20: q=1

21: 向每一个子区域Mj和Mk中的节点广播消息包msg(RouteSuccess) //消息包msg(RouteSuccess)告诉这些节点停止z为j或者k的msg(connect)消息包

22: 向所有处于连通路径上的节点发送消息包msg(turnOn),将这些节点的q置1,即这些节点也加入节点工作集worksetj

23:endif

24:ifq=0

25: 转至休眠状态直至下周期开始时唤醒

26:endif

当节点si接收到连通消息包,如果节点的qi为1,表明节点属于某一workset,不转发消息包(2行～4行)。否则对消息包中的distanceq(q可能为j或k)执行加1操作,并判断distanceq≥Maxstep是否成立。如果成立,不转发消息包(6行～8行)。否则,判断distanceq≤Mindistanceq是否成立,如果成立,用distanceq更新自己维护的Mindistanceq并转发消息包(10行～14行)。如果存在节点si,其维护的Mindistancej和Mindistancek满足:Mindistancej+Mindistancek≤Maxstep,广播路径建立消息包,告知子区域Mj和其任意邻居子区域Mk已经连通,停止转发任何Mk子区域相关的连通信息包,并发送msg(turnOn)激活消息包至该连通路径上的所有节点,将这些节点的q置1,即这些节点运行期也将激活运行来保证连通。如果节点的工作标志位q未被置1,表示其最终未被加入worksetj,其将会在决策期结束后自动恢复休眠状态(24行～26行)。

3.1.3 算法复杂度分析

选取阶段算法整体采用的是类贪心算法,由于贪心算法是“一条链”式的处理算法,每次处理皆发生在临近的几个节点之间,所以从算法整体来看其时间复杂度是较低的。经典贪心算法时间复杂度为O(N),然而考虑算法存在寻找失败的回溯过程,因此复杂度会比经典贪心算法复杂度略高,约为O(2N)左右。

由于算法独立执行于每一个节点,因此我们选任一节点si为例,分析其计算复杂度。针对任一节点si,算法执行过程中复杂度最高的是更新自身所维护的有效网格点集Useti和重复网格点集Rseti以及worth值的计算。更新操作仅仅需要两个集合的对比,而worth值计算也较为简单,因此算法整体计算复杂度不高。

由于涉及集合更新操作,因此不可避免会带来大量的信息传递。为降低消息复杂度,本文设计了集合增量更新策略。每次根节点通告有效节点时不需要广播所有已覆盖节点集合,而仅需要通告新增加节点集合,其他节点可以增量更新自己维护的Useti和Rseti。在采用网格法为基础的算法中,本文的设计大幅降低了消息复杂度。

连通阶段算法中不涉及太多计算操作,故计算复杂度在此忽略不计。算法为每个连通消息包设计有最大转发次数Maxstep以保证消息不会重复无限次转播,同时只要算法判断出连通路径算法及广播终止消息停止算法,因此算法时间复杂度低于O(Maxstep·N)。

3.2 worth值的计算

DSSA使用worth来衡量每一个节点能够提供的覆盖贡献,这种机制为选取最佳节点来对区域进行监控提供了保障。本文将seti分为两个部分,分别为:有效网格集Useti和重复网格集Rseti。有效网格集中的节点越多,相应的节点能够提供的覆盖贡献就越大,故而Useti与worthi正相关;而重复网格集中的网格点数越多,代表冗余覆盖越多,因此Rseti与worthi负相关。另外,节点的剩余能量e也将作为参考变量。最终,我们用这3个参数来对候选节点进行评估,worth值可以用如式(7)表示:

(7)

其中e代表节点剩余能量。当numof(Useti)=0时,代表节点si的Useti中没有网格点,即其不能提供任何覆盖贡献,此时将worthi值置0。λ、η、γ 3个变量根据不同应用场景或部署情况来取值调整3个参数的权重。

4 仿真实验

仿真实验采用C++语言,基于MicrosoftVisualStudio2013平台实现。本文研究节点调度算法比较准则是网络生存时间,其中包括各子区域网络生存时间和整体网络生存时间。本节将DSSA算法与如下3种算法进行对比:1、LongRange算法:根据文献[10]中最远距离选取思想,根节点每次选取通信距离内最远的邻居节点作为下一根节点。2、RandSchedule算法:根节点每次在邻居节点中随机选取一个节点作为下一根节点。3、NonSchedule算法:该算法不进行节点选择与调度,每次将子区域中所有节点全部打开运行,直到子区域中存活节点不能提供p比例覆盖,宣告子区域死亡。仿真基于二维区域M,随机划分为9个子区域,各子区域参数如表1所示。

表1 子区域划分情况

其他参数设置如表2所示。其中为方便比较,将节点剩余能量e的单位规格化为节点能够工作的网络周期数,如e=5,表示节点剩余能量能够保证其正常工作5个网络周期。

表2 算法仿真参数设置

不考虑整体网络覆盖度f,考察在4个调度算法调度下的各子区域最大生存时长,结果如图4所示。

图4 不同算法调度下的各子区域生存时长对比

由图4可以看出,在9个子区域中,DSSA算法均能够提供比其他3个算法更多的子区域生存时长。

下面抽取其中两个子区域M6和M9对比4种算法在选取节点工作集worksetj时的效率。

图5 节点工作集合选取效率对比

从图5(a)和图5(b)中可以看出,本文提出的DSSA算法在节点工作集worksetj选取时始终保持领先于其他3种算法的优势,即用更少的节点数就可满足预定的覆盖需求。在后期随着节点衰亡等因素,虽然worksetj中所需节点数有所上升,但仍低于其他3种算法。也正因为选取的合理与高效,使得DSSA算法能够提供的工作网络周期最多。

图6中将网络覆盖度f考虑进来,针对不同网络覆盖度f,对4种算法调度下的网络整体生存时间进行对比。其中NonSchelule表示的是不进行节点调度的网络生存时长,通过数据可以发现,如果不进行任何节点调度,即使在网络覆盖度f=0.1的情况下,网络最大生存时长(周期)也不会大于节点最大初始剩余能量5(网络周期)。而借助于节点调度算法,如本文提出的DSSA算法,在网络覆盖度f=0.7时,算法还能够保证18个周期的网络生存时长,足以说明DSSA算法的必要性和有效性。同时通过图6可以发现,文献[10]中提出的针对全向感知节点的LongRange节点调度算法完全不适用与有向传感网络中的节点调度问题,其性能表现甚至不如随机调度算法。而本文提出的DSSA算法在不同网络覆盖度下始终保持良好的性能表现。

图6 不同网络覆盖度下的算法性能表现对比

为对比不同节点部署密度下的算法性能表现,在上文仿真实验的基础上,对每一个子区域中节点部署个数减半和翻倍,分别重新进行仿真实验,如图7和图8所示。

图7 子区域节点部署数量减半时4种算法性能对比

图8 子区域节点部署数量翻倍时4种算法性能对比

其中图7和图8分别表示每个子区域的节点部署数量减半和翻倍时,4种算法调度下的网络生存时间对比。结合图6初始节点部署个数的对比图表,可以看出DSSA算法不论节点部署密度大小,性能表现始终明显领先于其他3种算法。同时随着节点部署密度的增加,DSSA算法相比其他3种算法的优势逐步拉大。

5 结语

为延长分块区域p-覆盖有向传感网络的生存时间,本文提出一种基于网格划分的分区域节点调度算法DSSA。首先对节点感知范围网格化划分,然后在每一个子区域的执行算法贪心式的进行节点工作集的选取调度。DSSA算法还对整体网络的连通进行了考虑。仿真实验表明,该算法对比已有算法表现出了良好的性能和稳定性。

[1]孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社,2005:59-61.

[2]Chen P,Hong K,Naikal N,et al.A Low-Bandwidth Camera Sensor Platform with Applications in Smart Camera Networks[J].ACM Transactions on Sensor Networks,2013,9(2):21.

[3]Sung T W,Yang C S.Voronoi-Based Coverage Improvement Approach for Wireless Directional Sensor Networks[J].Journal of Network and Computer Applications,2014,39:202-213.

[4]Singh A,Rossi A.A Genetic Algorithm Based Exact Approach for Lifetime Maximization of Directional Sensor Networks[J].Ad Hoc Networks,2013,11(3):1006-1021.

[5]Liu C,Cao G.Distributed Critical Location Coverage in Wireless Sensor Networks with Lifetime Constraint[C]//INFOCOM,2012 Proceedings IEEE.IEEE,2012:1314-1322.

[6]Ren Y,Zhang S,Zhang H.Theories and Algorithms of Coverage Control for Wireless Sensor Networks[J].Journal of Software,2006,17(3):422-433.

[7]刘端阳,暴占兵,程珍.一种可分负载WSN的能耗均衡负载调度算法[J].传感技术学报,2014,27(2):225-232.

[8]Cheng W F,Liao X K,Shen C X.Maximal Coverage Scheduling in Wireless Directional Sensor Networks[J].Journal of Software,2009,20(4):975-984.

[9]韩崇,孙力娟,郭剑.一种基于网格划分的有向传感网时空覆盖调度算法[J].南京邮电大学学报(自然科学版),2013,33(5):82-87.

[10]Chen H,Wu H,Tzeng N F.Grid-Based Approach for Working Node Selection in Wireless Sensor Networks[C]//Communi-cations,2004 IEEE International Conference on.IEEE,2004,6:3673-3678.

[11]Li Y,Ai C,Cai Z,et al.Sensor Scheduling for p-Percent Coverage in Wireless Sensor Networks[J].Cluster Computing,2011,14(1):27-40.

[12]Zhou P,Wu J,Long C.Probability-Based Optimal Coverage of PTZ Camera Networks[C]//Communications(ICC),2012 IEEE International Conference on.IEEE,2012:218-222.

[13]张蕾.无线传感器网络中多重覆盖算法的研究[J].传感技术学报,2014,27(6):802-806.

[14]Ma H,Liu Y.Correlation Based Video Processing in Video Sensor Networks[C]//Wireless Networks,Communications and Mobile Computing,2005 International Conference on.IEEE,2005,2:987-992.

A Scheduling Algorithm for Area-Dividingp-Persent Coverage in Directional Sensor Networks*

CHENChangchao,SUNLijuan*,HANChong,GUOJian

(1.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

In this paper,we study sensor scheduling problems for p-percent coverage area which is divided into different subareas.We propose a schedule to prolong the network lifetime.Based on different coverage requirement,we divide the initial whole area into different small subareas.Each subarea has its’ own coverage requirement p.Starting from the sensor model of directional sensor nodes,we propose an algorithm to describe node’s sensor area based on grid partition.Then we propose the Distributed Greed Subarea Scheduling Algorithm DSSA(Distributed Subarea Sensor-schedule Algorithm),which promises p-precent coverage for every subarea and use least number of nodes.This algorithm also consider network connectivity.The simulation results show that DSSA can prolong network lifetime significantly.

directional sensor networks;sensor schedule algorithm;area divided;p-percent coverage