一种分区的全向传感器栅栏覆盖构建算法*

任勇默,牛玉刚*,贾廷纲

(1.华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237;2.上海电气自动化集团,上海 200070)

一种分区的全向传感器栅栏覆盖构建算法*

任勇默1,牛玉刚1*,贾廷纲2

(1.华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237;2.上海电气自动化集团,上海 200070)

栅栏覆盖是传感器网络覆盖控制的研究热点之一。提出一种全向传感器栅栏分区构建算法(FCOIS)。算法中节点采取全向传感器感知模型,依照节点初始分布状态划分子区域,使每个子区域内节点个数尽量相等,并根据每个子区域内节点的分布情况确定栅栏的形成区间。在每个子区域内,依照从左至右的顺序构建栅栏,当各子区域的栅栏构建完毕后,采用贪婪算法对相邻子区域间栅栏的空隙进行填充。仿真结果证明该算法能够以较低的总能耗、平均能耗构建栅栏,显著节省了节点的使用数量与通信开销。

全向传感器;栅栏覆盖;FCOIS;子区域;通信开销

全向传感器相较于有向传感器,有着更广阔的感知视角,适用于在死角较多的地域集中监控,或用于复杂地理环境下的险情检测。若干个传感器节点所构成的集合,能够将监控区域进行分隔,用于感知进行跨区域穿越的目标,这种技术被称为栅栏覆盖。在栅栏覆盖问题中,由全向传感器组成的栅栏称为全向栅栏,由有向传感器组成的栅栏称为有向栅栏。在全向栅栏研究方面,如何提高栅栏的相关性能,并降低形成栅栏的难度,是无线传感器网络领域的一个研究热点[1]。

1 相关工作

目前已有许多与栅栏覆盖相关的研究工作[2-15],其中,文献[2]中定义了强栅栏、弱栅栏;文献[3]中提出了节点部署密度与感知目标概率之间的关系式;文献[4]研究了在有向传感器节点部署密度较大时,仅采取转动节点方式完成栅栏部署,但此方式不适用于全向栅栏的构建;文献[5]中提出了在栅栏系统中移动传感器的方式,以用于提前捕获目标;文献[6]提出了strong-greedy算法与strong-optimal算法,能够在节点密度较高时,利用原有的连通部分,再用贪婪算法与最优匹配算法完成对空隙部分的拼接,从而构建栅栏;文献[7]提出了异构传感器模型下的覆盖部署策略,但异构模型下的每个节点权重不一致,部署策略不完全适用于同构模型;文献[8]研究了矩形分区状态下栅栏最少节点数目与节点间距的计算方法,但最少的节点数与节点间距并不代表节点的能耗与通信开销最小;文献[10]提出PMNSB算法,采用以总移动距离最小为目标的匹配方式分区构建栅栏,但PMNSB算法下总移动距离最小有着较严格的约束条件,且分区方法为等分监控区域,并未考虑节点在区域内的分布权重;文献[11]提出了一种在栅栏出现空洞时,分阶段修补栅栏的策略;文献[12]提出了一种分布式自学习算法,能够提高栅栏系统的生存周期,但未对栅栏本身的构建方式进行优化;文献[13]提出了在链路可靠前提下,能够增强网络寿命的策略;文献[14]提出了最少节点构建k条不相交的栅栏,但使用最少节点不能保证单个节点最低的能耗;文献[15]研究了雷达传感器以总移动距离最小为目标实施区域覆盖,但该方法在栅栏工作时,需要激活栅栏中所有的节点同时工作,需要较高的通信开销。

本文将通过优化划分子区域的方式,对全向栅栏构建算法的性能进行改进。后续内容安排如下:第3节描述网络模型。第4节给出基于分区的全向同构传感器强栅栏构建方法(FCOIS)。第5节通过仿真实验对提出的算法进行性能评估。第6节总结全文并指出下一步工作。

2 相关模型和定义

全向传感器节点感知模型如图1所示。

图1 全向传感器的传感模型

图1中,r表示节点的感知半径,O点的位置即为节点位于坐标轴中的相对位置(坐标),P点为一个需要被感知的目标,则当|OP|≤r时,目标才能够被节点感知,同时节点发出感知到目标的通信信号。

本文对所研究的全向传感器栅栏问题,作如下假设:①在监控区域内,所有传感器节点均是同构的,节点以随机投撒形式分布在区域内。投撒完毕后,每个节点在区域内的相对横、纵坐标均已知;②监控区域内的地理环境无差别,所有节点在区域内的单位移动能耗均相同;③在监控区域内,所有节点在感知到目标,输出通信信号时,相应的通信输出功率均相同;④所有节点均是无故障的。

定义1节点的运动能耗:节点的移动距离与单位移动能耗的乘积。

定义2节点通信开销:节点感知到穿越目标后,输出信号所消耗的能量。

定义3节点的投撒密度:传感器节点总数与监控区域面积的比值ρ。投撒密度对栅栏形成过程中的能耗与通信开销有着显著影响,后面在仿真实验中会进行详细分析。

本文研究的问题:在监控区域中以密度ρ随机部署节点之后,如何移动节点,节省每个节点的运动能耗,减少每条栅栏构建时所需要的节点数量,并尽量降低栅栏后续工作时的通信开销。

3 基于分区的全向同构传感器栅栏构建算法(FCOIS)

文献[6]中提出的strong-greedy算法通过先搜索初始状态下连通的节点,再通过对比各个连通区域之间的距离,进一步地选定栅栏所需的连通区域,而后采取贪婪算法将连通区域之间的空隙用其余的节点进行填补,这需要耗费大量的节点。文献[10]中提出的PMNSB算法将监控区域分成若干个子区域之后,同时在各个子区域内形成栅栏,而后再将各个子区域之间的栅栏用竖直栅栏进行连接,从而形成整个监控区域的栅栏。但竖直栅栏的使用增加了区域内节点的使用数量,同时也增大了子区域内栅栏工作状态下的通信开销。

针对上述问题,本文研究如何更合理地划分子区域,并在子区域内更充分地应用各节点之间的位置关系构建栅栏,提出了一种分区的全向传感器栅栏构建算法FCOIS(Fence Construction for Omnidirectional Isomorphism Sensor based on subarea)。整体监测区域的栅栏主体由各个子区域内栅栏的并集组成,若相邻子区域内栅栏之间有空隙,则需要沿竖直方向进行填补。

3.1 算法实现步骤

FCOIS算法具体步骤如下:

步骤1 设定子区域个数,并确定各子区域边界 将需划分的子区域个数记作V,投撒的传感器节点总数记作n,并将每个节点的横坐标按照从小到大的顺序进行排列,将从小到大顺序下排位为|n/V|的节点计入第1个子区域,并将其横坐标记为l1,则直线x=l1与监控区域的公共交线为第1个子区域的右边界,同时也为第2个子区域的左边界。同理,将排位为2|n/V|的节点计入第2个子区域,并将其横坐标记为l2,直线x=l2与监控区域的公共交线作为第2个子区域的右边界…直至第V个子区域的左右边界分别为x=lV-1与x=L(x=L即为整个监控区域的右边界)。如图2所示,即为节点数n=7,子区域数V=3下的子区域划分方式。显然,为了尽量使每个子区域内的节点个数尽可能均等(即第V个子区域内节点个数不能明显多于前V-1个子区域),在实际应用中,子区域的划分个数V应遵循n≫V的选取原则。

图2 子区域的划分

步骤2 确定栅栏的预设区域 在每个子区域内,统计节点纵坐标范围分别在0≤y≤2r、2r

步骤3 确定各子区域内栅栏的首节点 在预设区域内,选出每个子区域中横坐标最小的节点作为各子区域栅栏的首节点,若首节点横坐标与左边界之差大于半径r,则令其向左平行移动至恰与左边界相切,如图3(a)所示,首节点从A点运动至B点;若其横坐标与左边界之差小于等于半径r,则该节点不移动,如图3(b)所示。

图3 首节点运动方式

步骤4 在各子区域内形成栅栏 在各子区域内,判断剩余的所有节点中,是否有节点的感知区域与首节点感知区域相交。若有,选出其中横坐标最大的节点作为第2个节点,不进行移动,如图4(a)所示,选取C点作为第2个节点;若没有节点的感知区域与首节点感知区域相交(或相切),则以首节点正右方向+2r处作为第2个节点的目标位置,选取距离此目标位置最近的节点移动至该目标位置,如图4(b)所示,由于|BC|≤|AC|,选取B处节点移动至C点作为第2个节点。

图4 节点的选择

在第i(i≥2)个节点移动完毕后,依照同样的节点选取方式选取第i+1个节点。随着i的逐一增加,直至第i+1个节点能够与子区域右边界产生交点,子区域内的栅栏构建完毕。子区域内所剩余的节点不移动。

步骤5 在监控区域整体上形成首条栅栏 当各子区域内栅栏构建完毕,判断相邻子区域间的栅栏是否有相交部分。若是,则不需填充节点;否则,则从周围挑选节点,按竖直方向对相邻子区域间的栅栏空隙进行填充,节点依照贪婪算法选取,使填充段内各节点运动能耗最小。

步骤6 构建其余K-1条栅栏 若K>1,从剩余的区域段中找出节点个数最多的区域段(之前已参与构建栅栏的节点不重复计入),重复步骤2至步骤5的操作,形成第2条至第K条栅栏,算法结束。

FCOIS算法伪代码如下:

01:Divide the subareas in the area

02:In each subarea,the interval section with the largest number of nodes is selected

03:The interval in which the node is the most is the final preset area

04:Determine the first node in each subarea

05:If the first node intersects the left border

06:The first node remains in place

07:Else move parallel to the left until tangent to the left border

08:If the next node perceived range intersects the perceived range of the node

09:The next node remains in place

10:Else select the nearest distance node to move to the target position on the right side of the node,and the distance from the node is equal to the diameter of the sensing range

11:Repeat the above operation until the fence in the subarea is formed

12:If there is a gap between the fence of the subarea

13:The nodes fill the voids according to the greedy algorithm

14:End

15:Delete the used nodes

16:If the number of fencesK>1

17:Build the remainingK-1 fences

18:End

3.2 算法的性能分析

如果监控区域未分区,那么为了避免目标穿越栅栏时出现遗漏目标的情况,整条栅栏上的节点均需被激活至工作状态。然而,在监控区域内采取划分子区域的方式,当目标穿越时,仅需激活子区域内栅栏的节点,有效地减少了激活节点的数量,降低通信开销。如图5所示。

图5 目标穿越子区域内的栅栏

当节点投撒完毕之后,选出各子区域中节点个数最多,且节点纵坐标分布最集中的区域段作为每个子区域内栅栏的预设区域,能够尽可能地减少各子区域间栅栏竖直方向的偏差,并降低节点竖直分量上的移动距离,从而节省单个节点的运动能耗。

在各子区域内,若采取从中间至两侧边界的构建方式构建栅栏,可能会导致栅栏两端朝向两个相反的方向偏离,这将加大栅栏竖直方向上的偏差程度,使各子区域间栅栏的拼接需要更多的节点。同时,栅栏耗费更多的节点将导致总能耗与通信开销增大。因此,为了尽量降低各相邻子区域间栅栏竖直方向上的偏移程度,降低子区域边界上栅栏拼接所使用的节点数,不失一般性,规定各子区域内栅栏的构建顺序为从左至右。

在时间复杂度方面,由于计算每个节点的运动状态所花费的时间相同,依照时间复杂度定义,考虑在最坏情况下,每个子区域内的节点恰好全部参与形成栅栏。设节点总数为n,划分了V个子区域。由于每个子区域内的节点不多于|n/V|个,且各子区域内栅栏的构建同时进行。因此在不多于|n/V|个节点中选出第1个节点,然后从|n/V|-1个节点中选出第2个节点,以此类推,直至栅栏形成完毕,时间复杂度为:O(|n/V|)2。若不划分子区域,即V=1,则时间复杂度为O(n)2。采取划分子区域的方式,有效地降低了算法的时间复杂度。

4 仿真结果

本文运用MATLAB7.0对此算法进行仿真,每组实验数据采用重复100次独立实验取平均值的方式获得。实验所涉及的参数指标如表1所示。

表1 参数说明

如果没有特别指明特定参数的数值,参数的默认值如表2所示。我们选取了文献[6]中的strong-greedy算法与文献[10]中的PMNSB算法与本文中的FCOIS算法进行了仿真比较。参考文献[6]和文献[10]中的实验数据,规定每个传感器节点的感知半径为5 m,每移动1个单位长度消耗3.6 J的能量。目标每穿越1次栅栏,单个节点激活通信信号消耗1.5 J的能量。

图6 FCOIS算法

参数取值L300mW200mJ13.6J/mJ21.5J/次P00.006个/m2K2V3

在默认参数下,给定同一初始节点投撒条件,FCOIS算法、strong-greedy算法、PMNSB算法形成的栅栏分别如图6～图8所示,可以看出,在同一初始投撒条件下,FCOIS算法构建2条栅栏所使用的节点数量明显少于strong-greedy算法与PMNSB算法。

图7 strong-greedy算法

图8 PMNSB算法

4.1 节点密度的影响

由于strong-greedy算法需要依赖监控区域内大量的连通区域,当投撒密度较低时可能会出现节点数量不足的情况,在较高投撒密度下才能发挥较好的性能。因此为了兼顾strong-greedy算法的应用要求,使对比结果更有意义,实验中以0.004的投撒密度起始,逐次将投撒密度递增0.001,直至0.008截止,其余实验参数值与表2所示参数一致。仿真实验结果如图9～图12所示。

图9 节点密度VS总能耗

图10 节点密度VS平均能耗

从图9中可以看到,当投撒密度增加时,3种算法的总能耗均明显下降,FCOIS算法的总能耗始终低于strong-greedy算法与PMNSB算法。虽然PMNSB算法在各子区域生成栅栏时,采取以总能耗最小为优化目标的部署策略,但其竖直栅栏的选取位置并非最优,对约束条件造成了影响,间接提高了PMNSB算法的总能耗。从图10中可以看到,随着密度从0.004增至0.008,节点的分布更密集,在3种算法下,每个节点平均移动的距离都减小。但随着密度的增大,在FCOIS算法中,节点感知区域之间出现相交的情况会增多,使得平均能耗得到了进一步的降低,相较strong-greedy算法和PMNSB算法,平均能耗下降的速率更快。这说明FCOIS算法中比strong-greedy算法和PMNSB算法更有效地利用了初始状态下连通的节点。

图11 节点密度VS能耗标准差

图12 节点密度VS栅栏使用节点数

对比图11、图12可以看到,对strong-greedy算法来说,虽然事先寻找到了若干个节点连通区域,但在节点密度较低时,其余节点需要移动更多的距离来填补空隙,导致了节点的能耗分布不均匀,能耗标准差较大,栅栏使用的节点数也较多,随着节点密度增大,使用的节点数大幅增加,能耗标准差也相应地减少。对PMNSB算法来说,以总能耗最小为最优目标,在约束条件下使用的节点个数较为稳定,几乎不随节点密度变化而变化,但总能耗最小的优化目标会部分牺牲节点能耗分布的均匀性,且各子区域间栅栏的预设区域不统一,导致竖直栅栏上使用了较多节点,进一步增大了能耗标准差。在FCOIS算法中,随着节点密度增大,感知区域连通的节点更多的参与构建栅栏,导致栅栏使用的节点数相应增多。又因为在FCOIS算法中,各子区域内栅栏的预设区域得到统一,竖直方向上用于填充空隙的节点较少,且竖直方向节点采取贪婪算法部署栅栏。在这些因素的综合作用下,FCOIS算法的能耗标准差始终明显低于strong-greedy算法与PMNSB算法。

4.2 栅栏的通信开销

当目标穿越栅栏时,目标所属子区域内,栅栏上的节点都会被激活,并发出通信信号。为了更准确地反映各算法下,目标穿越栅栏时的通信开销,并对比各算法在实际环境下的性能,仿真实验中采取逐一增大栅栏条数K,进行100次目标随机穿越栅栏实验求平均值的方式,对各算法下栅栏的通信开销进行对比。同时,为控制变量,避免实验数据受到其他因素的干扰,除栅栏数K之外的其余实验参数均与表2中一致,仿真结果如图13所示。

图13 栅栏数K VS 通信开销

从图13可以看出,随着栅栏数K的增加,由于预设区域的设定,FCOIS算法与PMNSB算法的子区域内节点数增加幅度较稳定,使FCOIS算法与PMNSB算法的通信开销呈近似线性增长。又因为PMNSB算法使用更多的节点构建竖直栅栏,因此FCOIS算法的通信开销始终明显低于PMNSB算法。而strong-greedy算法在构建前3条栅栏时的节点较充裕,导致strong-greedy算法的通信开销在K=1～3时增长速度较大,而在构建第4、第5条栅栏时,由于连通区域减少,可供参与构建栅栏的节点减少,使第4、第5条栅栏工作状态下整体的通信开销降低,通信开销随栅栏数K的增长速度变小,但整体通信开销明显大于FCOIS算法与PMNSB算法。不难推测:若节点数量足够充裕,随着栅栏数K的增大,FCOIS算法构建的栅栏,在工作状态下,相较strong-greedy算法与PMNSB算法构建的栅栏,能够明显降低通信开销,具备稳定的性能。

5 结论

本文主要研究基于分区的栅栏构建问题,提出FCOIS算法,按节点的分布情况较为平均地划分子区域,同时在每个子区域中按照从左到右的节点顺序构建子区域内的栅栏,并依照贪婪算法沿竖直方向完成各子区域间栅栏的拼接。仿真结果证明同等条件下,FCOIS算法可以用更少的节点,更低的平均能耗、总能耗与通信开销构建栅栏,且一定程度上兼顾了各节点之间能耗的均衡,降低了节点个体出现较大能耗的可能性,间接提高了栅栏的工作寿命。相较PMNSB算法与strong-greedy算法而言,FCOIS算法更好地兼顾了各项指标的优化,同时也为全向栅栏的优化问题提供了进一步的选择方向与可能性。

三维栅栏模型是更应用广泛的感知模型,如何高效地构建三维栅栏是下一步要研究的内容。

[1] 罗卿,林亚平,王雷,等. 传感器网络中基于数据融合的栅栏覆盖控制研究[J]. 电子与信息学报,2012,34(4):825-831.

[2] Santosh Kumar,Ten-Hwang Lai,Anish Arora. Barrier Coverage with Wireless Sensors[C]//Proc of the 11th Annual International Conference on Mobile Computing and Networking,2005:284-298.

[3] Wang Wei,Vikram Srinivasan,Kee-Chaing Chua,et al. Energy-Efficient Coverage for Target Detection in Wireless Sensor Networks[C]//Proc of the 6th International Conference on Information Processing in Sensor Networks. Boston:ACM Press,2007:313-322.

[4] 王林,刘文远,王琳,等. 基于有向传感器网络的强栅栏覆盖优化策略[J]. 小型微型计算机系统,2014,35(4):740-745.

[5] 舒坚,余坤,刘琳岚,等. 无线传感器网络中基于移动模型的栅栏覆盖研究[J]. 计算机研究与发展,2011,48(9):141-144.

[6] Wang Zhibo,Liao Jilong,Cao Qing,et al. Achievingk-Barrier Coverage in Hybrid Directional Sensor Networks[J]. IEEE Transactions on Mobile Computing,2014,13(7):1443-1455.

[7] 陈杰,杜庆伟,李晓禹,等. 概率模型下异构传感器网络部署算法的研究[J]. 小型微型计算机系统,2012,33(1):049-053.

[8] 胡照鹏,张长森. 基于矩形分区覆盖的节点确定部署策略[J]. 传感技术学报,2013,26(3):411-413.

[9] Xu Biaofei,Zhu Yuqing,Donghyun Kim,et al. Strengthening Barrier-Coverage of Static Sensor Network with Mobile Sensor Nodes[J]. Wireless Networks,2015,8491:368-377.

[10] 王超,范兴刚,王恒,等. 一种高效强K—栅栏覆盖构建算法[J]. 传感技术学报,2015,28(2):1-8.

[11] Anwar Saipulla,Cedric Westphal,Liu Benyuan,et al. Barrier Coverage with Line-Based Deployed Mobile Sensors[J]. Ad Hoc Networks,2013,11(4):1381-1391.

[12] Habib Mostafaei,Mohammad Reza Meybodi. An Energy Efficient Barrier Coverage Algorithm for Wireless Sensor Networks[J]. Wireless Personal Communications,2014. 77(3):2099-2115.

[13] Nowsheen Nusrat,Karmakar Gour,Kamruzzaman Joarder. A Path Reliability-Aware Data Delivery Protocolfor Underwater Acoustic Sensor Networks[J]. Journal of Network and Computer Applications,2016,75:385-397.

[14] Guo Ling,Li Deying,Zhu Yuqing,et al. Enhancing Barrier Coverage with Beta Quality of Monitoringin Wireless Camera Sensor Networks[J]. Ad Hoc Networks,2016,51:62-79.

[15] Chen Jiaoyan,Wang Bang,Liu Wenyu. Constructing Perimeter Barrier Coverage with Bistatic Radar Sensors[J]. Journal of Network and Computer Applications,2015,57:129-141.

任勇默(1994-),男,硕士研究生,主要研究领域为无线传感器网络,renyongmo@126.com;

牛玉刚(1964-),男,教授,博士生导师,主要研究领域为随机系统、智能电网、无线传感器网络,acniuyg@ecust.edu.cn;

贾廷纲(1973-),男,博士,教授级高工,主要研究领域为工业自动化。

APartitionedAlgorithmforConstructingOmnidirectionalSensorFenceCover*

RENYongmo1,NIUYugang1*,JIATinggang2

(1.Key Lab of Advanced Control and Optimization for Chemical Process of Ministry of Education,East China University of Science and Technology,Shanghai 200237,China;2.Automation Group of Shanghai Electric,Shanghai 200070,China)

Sensor coverage is one of the hot topics in sensor network coverage control. We propose a partitioned omnidirectional sensor fence construction algorithm(FCOIS). In the algorithm,the nodes adopt the omnidirectional sensor-aware model,and the sub-regions are divided according to the initial distribution state of the nodes so that the number of nodes in each sub-region is equal. The fence formation interval is determined by the distribution of nodes in each sub-region. In each sub-region,the fence is constructed according to the order from left to right. When the fence of each sub-area is built,the greedy algorithm is used to fill the gap of the fence between adjacent sub-regions. The simulation results show that the algorithm can build the fence with lower total energy consumption and average energy consumption,which can save the number of nodes and the communication cost.

omnidirectional sensor;fence coverage;FCOIS;sub-region;communication cost

项目来源:国家自然科学基金项目(61273073)

2017-03-07修改日期:2017-05-02

TP273

:A

:1004-1699(2017)09-1381-07

10.3969/j.issn.1004-1699.2017.09.014