一种移动传感网络中K-栅栏寿命的优化方法

薛 亮，王 然

(杭州电子科技大学 计算机学院，浙江 杭州 310018)

栅栏覆盖在国防和林业方面有着重要作用[1]。为了增加栅栏的可靠性，文献[2]提出了K-栅栏覆盖的概念，要求监测目标在穿越区域时至少能被K个传感器节点所感知。

目前大部分研究主要集中在使用静态传感器构建K-栅栏覆盖方面[3-5]。然而，静态传感器并不能覆盖到区域中某些特定的位置，从而导致覆盖漏洞出现，影响覆盖的质量。因此，使用移动传感器构建栅栏的研究受到了越来越多的关注。文献[6]使用移动传感器构建1-栅栏覆盖。文献[7～10]利用移动传感器构造节能的K-栅栏覆盖问题，并着重于减少传感器移动的距离。

上述研究都是试图通过减少传感器能耗的方式来实现延长网络寿命的目标。近年来，能量收集技术成为了一种新的可供选择的方案。传感器配备能量收集模块[11]，可收集环境中的能量(例如太阳能[12]、风能[13]等)来给电池补充能量。文献[14]将能量收集技术与K-栅栏覆盖相结合，最大化网络的寿命，但该研究仅考虑了传感器的静态场景。文献[15]使用具备能量收集能力的移动传感器和不具备能量收集能力的静态传感器共同构建栅栏覆盖。然而上述研究都没有考虑到区域内不同位置能量的差异性，例如部署在森林里的传感器由于存在树叶遮挡，导致各个位置接收到的太阳能强度存在差异。

基于能量收集技术，本研究认为传感器能够收集太阳能，且监测区域内不同位置的太阳能强度不一致。本文使用移动传感器构建K-栅栏覆盖，提出了一种集中式的栅栏构建和调度(Barrier Construction And Scheduling，BCAS)算法，有效地构建并调度栅栏，最大程度地延长了网络寿命。

1 相关模型

1.1 网络模型

图1 网络示意图Figure 1. Network diagram

1.2 传感器模型

传感器的监测半径为R，使用ZigBee技术直接与基站通信，并且具有移动和能量收集能力。电池容量为B，即传感器的初始能量。传感器有两种状态：活动状态和睡眠状态。传感器在活动状态下执行监测任务需要消耗能量，在睡眠状态下不执行任务，不需要消耗能量。假设传感器电池容量存在一个阈值百分比ε，当传感器的剩余能量小于Bε时，睡眠状态的传感器不能被激活，活动状态的传感器在监测任务执行完毕后立即睡眠。不考虑传感器移动的时间，即传感器的位置变化是瞬时完成的，因此可以认为传感器在移动时是不能收集能量的。

1.3 能耗模型

传感器需要不断监测目标区域以检测入侵者，并且还需要与基站通信，将数据传输到基站并接收基站的调度信息，因此需要考虑传感器的监测能耗率与通信能耗率。本文将监测能耗率和通信能耗率看作一个定值，称为传感能耗率，记为es(单位为J·s-1)。此外，还需要考虑传感器的移动能耗，将传感器每米移动的能耗记为em(单位为J·m-1)。

1.4 能量收集模型

区域Ω内不同太阳能区域中的太阳能强度随机分布在[a，b](单位为W)之间。本文用λu代表第u个太阳能区域内的太阳能强度，用ξ代表太阳能的接收效率。因此第u个太阳能区域内传感器si的能量收集率计算式为

ei(u)=ξλu

(1)

由于在现实中光照强度都是随时间变化的，文献[17～19]中采用取平均值的方式来表示光照强度，因此本文也采用这种方式。

1.5 时隙划分

将网络的运行时间离散化为小时隙，每个时隙的长度相等，表示为τt(t=1，2，…，T)，其中T为最后一个时隙。第t个时隙开始时传感器si的剩余能量Eit为

(2)

(3)

(4)

其中，t=1，2，…，T；Ei0=B，为传感器si的初始能量；τt-1代表第t-1个时隙的长度；τ0=0；ei(ut-1)代表在第t-1个时隙位于ut-1号太阳能区域中传感器si的能量收集率；es代表传感器传感的能耗率；lit代表传感器si在时隙t开始前移动的距离；em代表传感器每米移动的能耗；xit和yit为传感器si在第t个时隙在区域内Ω位置的横纵坐标值。

在每个时隙开始前，栅栏中传感器剩余能量不得低于Bε才能确保节点能被激活；在时隙结束时，剩余能量必须大于0，才能确保节点在时隙内不会死去。考虑最极端的情况，时隙开始时剩余能量正好为Bε，时隙结束时剩余能量正好为0，因此时隙的长度τt可以计算为

(5)

其中，a为监测区域Ω内最小的太阳能强度值；ξ代表太阳能的接收效率。

传感器的移动距离限制如式(6)所示。

(6)

2 问题定义

定义1移动K-栅栏网络的生命周期：给定监测区域Ω和移动传感器集合S，从形成K-栅栏覆盖开始到无法调度移动传感器为形成K-栅栏覆盖的时间段，即移动K-栅栏网络的生命周期。

定义2移动K-栅栏网络的生命周期最大化问题：给定监测区域Ω和移动传感器集合S，调度传感器移动形成K-栅栏，并按时隙调度，使K-栅栏的网络生命周期最大。

基于以上定义可以将问题形式化

(7)

约束于

(8)

(9)

si∈Ba，∀t=1，2，…，T

(10)

式(7)是优化目标，表示最大化K-栅栏的生命周期。式(8)表示时隙开始前传感器的剩余能量必须大于等于阈值能量。式(9)表示时隙结束后传感器的剩余能量必须大于0。式(10)中Ba表示构成栅栏的传感器节点集合。上述约束作用于栅栏中的每个传感器和每个时隙。

3 算法设计

监测区域Ω内的太阳能强度是连续分布的，但这并不利于处理，因此需要使用离散化的思想，用边长为2R的小网格离散化区域Ω。传感器可以移动至网格的中心。传感器的能量收集率为该网格中心处的太阳能强度乘以太阳能接收效率。

本文提出的栅栏构建与调度算法主要分为构建阶段与调度阶段。在构建阶段构建出满足栅栏覆盖要求的栅栏个数，在调度阶段选择栅栏调度并进行节点移动以修补栅栏，延长网络的寿命。

3.1 构建阶段

定义3基线栅栏位置：能为区域提供1-栅栏覆盖的网格位置。

图2 监测区域的划分Figure 2. Division of monitoring area

算法1 基线栅栏位置选择算法Input: 太阳能强度λu,区域Ω,监测半径R,传感器集合SOutput: 区域Ω的基线栅栏位置bp1. 用边长2R的小正方形离散化区域Ω,得到水平子区域集合AH2. count=03. for AHz∈AH do:4. 选择最高平均太阳能强度的一行网格为基线栅栏位置bpz,如果存在多行满足条件的网格则计算AHz内传感器纵坐标平均值,选择纵坐标值离该平均值最近那行网格作为基线栅栏位置bpz。5. if count>0 do:6. 选择平均太阳能强度较大的一列网格位置使AHz-1中bpz-1与AHz中bpz相连,形成Ω中完整的基线栅栏位置bp7. end if8. count++9. end for

下一步需要将各个水平子区域内的基线栅栏位置连接，形成整个监测区域Ω内完整的基线栅栏位置。对于相邻的水平子区域AHz和AHz+1内的子基线栅栏位置bpz和bpz+1有两种方式可以连接。如图3所示，分别选择AHz中的网格sg1、sg2、sg3和AHz+1中的网格sg4、sg5、sg6。选择的标准为用于连接两个子基线栅栏位置的网格的平均太阳能强度最大。假设sg1、sg2、sg3处的平均太阳能强度大于sg4、sg5、sg6处的平均太阳能强度，此时会选择AHz中的网格sg1、sg2、sg3用于连接。对每个水平子区域都执行上述过程，直至形成整个监测区域内完整的基线栅栏位置。具体过程见算法1。

图3 连接位置的选择Figure 3. Choice of connection location

接下来考虑为区域Ω构建K-栅栏覆盖，考虑栅栏运行在能量收集的情况下，并且区域内的传感器有一定的冗余。因此可以在Ω内形成K+1条栅栏，在每个时隙开始前选择其中的K条激活，剩下的一条保持睡眠以补充能量。被选择激活的栅栏中每个传感器的能量不低于Bε，因此需要找出K+1个基线栅栏位置。

将监测区域Ω在竖直方向上平均分成K+1个竖直子区域。分别在每个竖直子区域AVz内执行算法1找到对应的基线栅栏位置bp。然后，调度竖直子区域AVz内传感器，将其移动到基线栅栏位置bp处形成栅栏。传感器的移动不能跨越区域，构成栅栏的传感器集合为baz。本文采用贪心思想调度传感器移动。对于基线栅栏位置bp上的每个网格sgu，遍历竖直子区域AVz内的传感器集合Sz，找到与sgu中心距离最短的传感器sbest，将其移动至sgu处，并更新sbest的剩余能量。具体步骤见算法2。

算法2 K+1栅栏构建算法Input: 太阳能强度λu,区域Ω,监测半径R,传感器集合S,栅栏数KOutput: 区域Ω内的栅栏集合Ba1. 将区域Ω划分为K+1个竖直子区域,得到竖直子区域集合AV2. 对AVz∈AV执行算法1, 得到基线栅栏位置集合Bp3. for all bp∈Bp do:4. for grid sgu in bp do:5. for si∈Sz do:6. 计算len(si, sgu) 7. if len(si, sgu)

3.2 网络规模分析

区域Ω中能够形成的栅栏数是有限制的，与区域中传感器的节点密度有关，下面给出关于节点密度的定义。

定义4节点密度：监测区域Ω内传感器的数量与区域Ω面积的比值。

监测区域Ω内的节点密度ρ可以表示为

(11)

将监测区域划分为K+1个竖直子区域，每个竖直子区域AVz内的节点数量为NA。

图4 构成栅栏所需的最少传感器Figure 4. Minimal sensors required to form a barrier

(12)

每个竖直子区域AVz内形成栅栏覆盖所需的最少节点数为Nmin，如图4所示。

(13)

要保证竖直子区域AVz内节点数大于Nmin才能形成栅栏覆盖，因此可以推出监测区域Ω内能够满足的栅栏数K的上限。

(14)

图5 构成栅栏所需的最多传感器Figure 5. The most sensors required to form a barrier

由于实际应用时并不会总以最小的节点数形成栅栏，因此一般情况下并不能达到上限条件。由此可知，竖直子区域AVz内形成栅栏所需的最大节点数Nmax，如图5所示。

(15)

只要保证每个竖直子区域内的节点数NA≥Nmax就能在区域内形成栅栏覆盖。可以推出一定能满足所需栅栏覆盖数的节点密度ρ。

(16)

3.3 调度阶段

在监测区域Ω内生成K+1条栅栏后，需要调度算法来选择K条栅栏激活并调度，以延长网络的生命周期。调度算法分为两部分：栅栏选择策略和修补策略。栅栏选择策略为：在每个时隙τt开始时选择K条传感器平均剩余能量最大的栅栏激活执行监测任务，剩下的传感器进入睡眠状态以补充能量。

在时隙τt结束后可能存在一些栅栏中传感器的剩余能量小于Bε，要在下一个时隙τt+1开始前对栅栏进行修补，替换掉这些能量小于阈值的传感器节点。将竖直区域AVz中传感器集合Sz节点分为两类：构成栅栏的节点集合baz和其他不是构成栅栏的节点Szno(baz∪Szno=Sz)。定义移动权值ω(si，sj)为

(17)

其中，Ej为传感器sj的剩余能量；len(si，sj)为传感器si和传感器sj之间的距离。

修补策略为：对于竖直子区域AVz中构成栅栏的传感器集合baz中能量小于Bε的传感器si，遍历Szno节点集合，选择移动权重ω最大的节点sbest移动至节点si处进行替换以修补栅栏。更新sbest的剩余能量，对每个竖直子区域AVz都执行一次修补策略。

在每个时隙开始前都执行该调度算法，直至无法形成满足区域所需的K-栅栏覆盖要求。调度算法的具体过程见算法3。

算法3 栅栏调度算法Input: 栅栏集合Ba,栅栏数K,传感器集合S,电池容量B,阈值ε1. for baz∈Ba do:2. for si∈baz do:3. if Eiωmaxdo:7. ωmax=ω(si, sj), sbest= sj8. end if9. end for10. 移动 sbest到si, Ebest= Ebest - em×len(si, sbest) 11. baz= baz∪{sbest}, baz= baz(〛si} 12. Szno= Szno∪{si}, Szno= Szno(〛sbest}13. end if14. end for 15. end for16. 选择Ba中传感器平均剩余能量最大的K条baz激活,其余睡眠

4 模拟实验

为了验证所提BCAS算法的性能，本文在IntelliJ IDEA平台下使用Java语言进行了模拟实验，并且与文献[8]中提到的MobiBar算法和文献[9] 中提到的Single Sensor 算法做了对比。为了保证实验的稳定性和准确性，每组实验都进行了50次模拟。实验区域的大小设置为400 m×150 m，太阳能区域大小为40 m×15 m，传感器节点均匀分布在区域Ω内，传感器的节点密度ρ为3，电池容量B为1 100 mAh×4 V，太阳能强度范围为0.008～0.036 W，监测半径R为5 m，太阳能接收效率ξ为0.2。将传感的能耗率es设置为0.03 J·s-1，传感器移动能耗em为1 J·m-1，传感器能量阈值百分比ε为3%，栅栏个数K为3。

本文使MobiBar算法和Single Sensor算法与BCAS算法运行于同样的能量收集区域，并且需要形成满足K-栅栏覆盖要求的栅栏数。对于Single Sensor算法，将整个监测区域分为两块，分别形成子栅栏并连接。本文分别从网络生命周期和构建栅栏平均移动距离的角度比较了算法的性能。

图6 栅栏数对生命周期的影响Figure 6. The effect of the number of barriers on lifetime

图6表明，随着栅栏数K的增加，BCAS算法下生命周期依次减小。这因为监测区域内传感器密度不变，而随着需要满足的栅栏数的增加，监测区域也会被划分成越来越多的子区域，每个子区域内的传感器数量会越来越少，因此能够用来修补栅栏的冗余传感器也会减少。然而MobiBar算法和Single Sensor算法的生命周期变化较小。这因为MobiBar和Single Sensor算法没有针对能量收集的场景进行调度优化。在栅栏数K变化的情况下，与MobiBar算法和Single Sensor算法相比，BCAS算法的生命周期平均提升了大约183%。

图7 节点密度对生命周期的影响Figure 7. The effect of node density on lifetime

图7显示，随着节点密度ρ的增加，BCAS算法的生命周期也会增加，而MobiBar和Single Sensor算法的生命周期变化较小。这是因为随着传感器密度增加，用来修补栅栏的传感器也会增加，因此生命周期得以延长，而MobiBar和Single Sensor算法并没有充分地利用冗余节点。相比MobiBar和Single Sensor算法，在节点密度变化的情况下，BCAS算法的生命周期平均提升了168%。

图8 栅栏数对平均移动距离的影响Figure 8. The effect of the number of barriers on average moving distance

图8显示出随着栅栏数K的增加，3种算法的平均移动距离都会增加。这因为随着栅栏数的增加，监测区域会被划分为越来越多的子区域，每个子区域内可供选择移动的传感器也变少，平均移动距离因此变大。在K=1时，MobiBar算法的平均移动距离最小，在K>1时，BCAS算法具有较好的性能，而MobiBar算法性能最差。在K变化时，与MobiBar算法和Single Sensor算法相比，BCAS算法平均移动距离减少了约20.6%和12%。

图9 节点密度对平均移动距离的影响Figure 9. The effect of node density on average moving distance

图9表明，随着节点密度ρ的增加，3种算法的平均移动距离都在下降。这因为随着传感器密度增加，可供选择的传感器数量也会增加，平均移动距离因此下降。在传感器密度变化的过程中，BCAS算法的平均移动距离少于MobiBar算法和Single Sensor算法。在密度小于0.008时，Single Sensor算法的平均移动距离要小于MobiBar算法；密度大于0.008时，则相反。随着传感器密度的变化，与MobiBar算法和Single Sensor算法相比，BCAS算法的平均移动距离分别减少了20.2%和14.2%。

5 结束语

本文在能量收集的移动传感网络中构建了K-栅栏覆盖，提出了最大化基于能量收集的移动传感器网络中K-栅栏覆盖的生命周期问题。为了解决该问题，本文使用离散化的思想，将监测区域划分为小网格 ，提出BCAS算法来构建和调度栅栏，并进行了模拟实验，实验结果证明了BCAS算法的有效性。由于本文使用的是集中式算法，需要基站集中计算，资源消耗较大，因此未来将专注于研究相应的分布式算法以降低资源消耗。