基于目标分层和路径分割策略的扫描覆盖算法

张景昱,刘京菊,叶春明

(国防科技大学 电子对抗学院,合肥 230037)

0 概述

目前,无线传感器网络(Wireless Sensor Networks,WSNs)在医疗、工业以及军事领域得到广泛应用,覆盖问题是无线传感器网络研究中最重要的问题之一,常用的覆盖问题模型有区域覆盖、栅栏覆盖和扫描覆盖[1]。区域覆盖通过在整个区域内部署传感器节点,使得区域所有位置均处于传感器节点的感知范围内。区域覆盖虽然可以满足许多场景的需求,但由于其对传感器数量和感知能力存在硬性要求,在多数目标确定的情境下会造成极大的资源浪费。栅栏覆盖通常应用于区域内的入侵者检测,其属于一种静态覆盖模型,不能对特定目标进行监视[2]。

扫描覆盖的概念最早来源于机器人的路径规划问题,在路径规划过程中,机器人需要经过预先设定的一系列目的地,使得所有目的地都包含在最终设定的路径中,同时使得总路径最短。由于存在不同的目标和限制条件,使得路径规划方法不能直接应用于无线传感器网络的覆盖问题研究中。考虑到现有硬件技术可以使得传感器节点具有移动能力,同时需要覆盖的目标也具有一定的时间容忍性,研究人员即提出扫描覆盖的概念。如今,扫描覆盖已经被应用于很多场景中,例如,在森林火灾的监控过程中,通过提前勘察等手段获得整个森林可能发生火灾的区域,在这些位置部署移动传感器节点以周期性地对区域进行感知,从而极大程度地提高森林火灾的预警能力。

近年来,学者们提出了多种关于扫描覆盖问题的算法,此类算法的实现大多集中在以最少传感器节点数量、最短扫描周期、最短扫描路径等为目标的场景中。研究人员将需要覆盖的目标抽象化为兴趣点(POI)点集,将扫描覆盖问题抽象化为TSP问题进行求解,并设计合适的算法策略使其满足场景监视的需求[3-4]。

在实际应用场景中,不同的POI对应不同的重要程度。例如在战场环境中,敌方的关键基地和关键兵种的监视相较于其他位置而言更加重要,对这种重点位置应考虑增加监视时间。因此,需要给POI赋予不同的权重值进行区分,同时为其分配不同的扫描覆盖时间。但是,目前针对权重节点扫描覆盖策略研究较少,基本上将权重节点所在扫描路径的数量作为其权重值进行处理。此种方法虽然可以增加对权重节点的扫描时间,但是也会增加许多无效路径,使得部署代价过高。在扫描路径的规划过程中,扫描路径、路径的覆盖效率等也需要根据实际场景进行设计。

本文在权重目标条件中加入返回基站的时间限制,提出一种带有权重目标和返回时间约束的扫描覆盖问题WTSC,并证明其为NP-hard问题。针对该问题,本文设计一种目标分层策略用以区分权重POI,同时部署基站的位置。针对每个层级的POI,提出基于贪婪策略的TSP路径计算方法,获取每个层级的初始路径并针对初始路径设计一种环路分割策略,以得到所有移动传感器的部署位置。

1 相关研究

近年来,学者们关于扫描覆盖问题进行了较多的研究。文献[5]较早提出扫描覆盖的概念,其设计M-WSN中最少感知节点的扫描覆盖问题并计算满足需求的最少移动感知节点数量。该文证明了扫描覆盖问题是一个NP-hard问题,提出集中式算法CSweep和分布式算法DSweep 2种解决方法,但是这2种方法的应用场景过于理想,路径利用效率较低。文献[6]分析得出,CSweep算法难以应用于POI需求不同的情况,而Dsweep算法虽然灵活,但是由于其策略原因使得一部分节点长期被忽视。现有研究通常只关注对POI对的访问,对于获取到POI数据后如何进行汇总分析并未说明。因此,文献[6]将上述两方面问题相结合,对比车辆路径问题,提出一种基于聚类的扫描覆盖算法FCSC。该算法先通过聚类将位置近的POI进行分类,然后使用启发式算法生成扫描路径。

文献[7]研究动态传感器和静态传感器同时运行实现扫描覆盖的问题,并提出2个问题模型。第1个问题命名为t-Gsweep coverage,表示使用动、静传感器相结合的方法实现覆盖,并针对其中传感器与POI一一对应的特殊情况提出了更高效的解决方法。第2个问题是在移动传感器能量上限已知条件下以传感器节点数量最小为目标实现扫描覆盖。文献[8]分析了覆盖问题中的覆盖率,由于覆盖的重叠区域不规则、覆盖率很难计算,传统的网格点方式并未考虑实际目标的分布情况,因此对于动态特征区域会耗费过多资源。文献[8]通过定义特征点集,将传统的区域覆盖问题转换为基于特征点集的优化问题,针对WSNs分布式的特点,提出并行算法IWPSO,改善了传统算法容易陷入局部最优的不足。

文献[9]提出了MinExpand和Osweep 2种方法解决扫描覆盖问题。MinExpand方法不停添加新的POI到当前路径中,直至路径不能再添加新的POI,在添加过程中只将距离当前点最近的点作为候选点,再创建新的路径,直至所有POI被添加至路径中。Osweep方法是针对CSweep的一种改进,在扫描周期限制下,其将整个路径分割成一定数量的环路。文献[10]提出PPA算法,根据不规则网格分割区域算法(TIDA)的启发,分析每个网格内POI的个数,通过判定提前设定的平均周期、周期阀值和当前周期三者间的关系,对各个网格内POI的数量进行微调,以形成不同的环路并实现扫描覆盖。文献[11]将覆盖POI目标定为线条,将线条视为点,构建最小生成树抽象连接图,再将各个点之间的连接关系抽象成线段分割,增加新的分割点,对新图分配传感器实现扫描覆盖。文献[12]研究距离限制的扫描覆盖问题(MinSDCSC),其算法通过将扫描路径分割成k个部分,每个部分设置1个基站,以实现限制距离最短、节点数量较少的扫描覆盖。

文献[13]针对扫描覆盖中扫描周期最短的问题,研究其中3种不同的情况并设计3种对应算法。CycleSplit算法解决了每个传感器沿着预定轨迹周期运动情况下的扫描周期最短问题,HeteroCycleSplit算法解决了在传感器节点速度不同条件下的扫描覆盖问题,PathSplit算法解决了覆盖目标为路径情况下的扫描覆盖问题。文献[14]以扫描周期最短为目标设计了M3SR算法,该算法分别通过贪婪算法和二分算法对POI和路径进行处理,选出满足条件的扫描路径。文献[15]以扫描路径最短为目标,提出3种不同情境下的算法。其中,cyclesplit算法解决了所有传感器在各自环路内单独运行的问题,降低了OSweep算法的复杂度,Cocycle算法解决了传感器之间协同覆盖多目标的问题,augprim算法解决了传感器必须返回基站传递消息情况下的扫描覆盖问题。文献[16]以传感器节点数量最少为目标,提出PDBA算法,该算法在每条路径上增加尽量多的POI。文献[17]将扫描覆盖问题转化为TSP问题,通过将TSP问题分成2个阶段进行处理实现了对sweep覆盖问题的优化求解,同时设计平衡参数解决了各个节点之间负载不均衡的问题。

带有权重目标的扫描覆盖研究主要针对权重点的权重值处理问题展开。文献[18]研究了针对拥有不同权重值的目标实现扫描覆盖的问题,同时保证所有节点扫描周期趋于平衡。算法设置每个传感器的扫描周期,计算平均周期和标准差,并将权重POI的权重数值视为每个扫描周期内的访问次数。对于多个权重节点的情况,算法每次针对权重最大的节点进行迭代,对节点所在路径实现平均分割,直至所有节点被分割完毕。文献[19]研究了有时间限制和权重节点限制的扫描覆盖问题,首先根据POI权重确定初始路径,然后根据路径数量确定传感器数量、路径和初始位置,随后计算每个传感器的速度以保证扫描周期的稳定。同时,文献[19]算法设计了不同的时间片段,以保证各个POI在相同时段内不会被重复覆盖。文献[20]分别以节约能量和节点数量最少为目标设计扫描覆盖算法。针对节点数量最少的问题,选择动态与静态节点相结合的策略,首先根据边的长度和权重设计生成一颗最小生成树,通过对树进行分割处理设计动态节点路径和静态节点的位置。针对能量有限的问题,通过设定每个节点扫描周期内的能量上限和能量消耗参数,生成路径的最小森林,通过每一个树生成扫描路径。文献[21]针对文献[5]算法实际运行过程中存在的缺陷进行改进,使其能在拥有权重POI情况下使用。此外,针对不同POI需要不同的处理时间和扫描周期的问题,文献[21]提出了一种解决方法,该方法分为2个阶段,第1阶段确定节点数量,第2阶段确定移动策略和周期。

2 问题描述

本文问题描述为:对于POI已知的区域,在不同权重POI的覆盖需求和移动传感器返回基站的时间约束下,以尽量小的代价实现一种满足不同扫描时间要求的带时间约束的扫描覆盖算法。

上述问题与现有研究的假设相同,即当一个POI被覆盖时当且仅当移动传感器节点到达了此POI的位置。传感器节点都具有相同的感知能力和运动属性,节点之间可以构成无线传感器网络。在将实际场景转化为POI点集时,任何2个POI之间的距离由实际场景中两目标之间往返实际距离决定。POI之间构成的虚拟路径拟定为直线路径,路径代价与实际最小路径代价相同。

在扫描覆盖问题中,最常使用的模型是t-扫描覆盖(t-sweep coverage)模型。假设有n个移动传感器节点,节点集合为S={s1,s2,…,sn},整个区域中有m个POI节点,节点集合为H={h1,h2,…,hm}。任意2个POI节点hi和hj之间的欧式距离di,j表示hi和hj之间的路径代价,所有移动传感器都以相同的速度v运动。在每个设定的间隔之间,一个POI被覆盖当且仅当一个移动传感器节点移动到了此POI的位置。扫描覆盖与传统覆盖之间的差别是其不需要提供对目标的连续性覆盖。在扫描覆盖模型中,移动传感器节点只需要对POI在设定的时间间隔内至少覆盖一次,这样就能保证所有活动都能够在一定的延迟范围内被检测到。基于上述假设,t-扫描覆盖模型定义如下:

定义1(t-扫描覆盖模型) 一个POI满足t-扫描覆盖,当且仅当此POI每隔t时间被策略F规划下的移动传感器节点至少覆盖一次。

在定义1中,策略F即为移动传感器的路径规划策略,它规划了移动传感器节点在某一恒定速率下移动,并保证在整个运行过程中所有POI均能满足t-扫描覆盖。当一个POI满足t-扫描覆盖时,时间间隔t就被定为这个POI的扫描周期。在实际过程中,每个POI可能具有不同的扫描周期,只要所有ti均在统一设定的最大扫描周期Tmax内,就可认为所有的POI实现了t-扫描覆盖。

设定每个POI均有权重值,权重集合为W={w1,w2,…,wm},wmax和wmin分别表示POI的最大权重值和最小权重值。同时,整个场景中至少设置一个基站(sink node)用来处理每个周期内移动传感器收集到的POI信息。移动传感器在扫描周期内至少需要经过1次基站,即每个移动传感器都具有一个返回基站时间约束。因此,带有权重和返回时间约束的t-扫描覆盖(Weighted and Time-constrainedt-Sweep Coverage,WTSC)模型定义如下:

在WTSC模型下,需要设计一种移动节点的运行策略F来解决扫描覆盖问题,而在策略的设计过程中,需要在满足覆盖要求的前提下尽可能缩短扫描路径长度,以减少移动传感器节点的数量。

WTSC为一个NP-hard问题,其问题证明可以类比于多人旅行商问题(MTSP)。

3 算法设计

针对带有权重和返回时间限制的扫描覆盖问题,本文提出一种基于目标分层和路径分割的扫描覆盖算法TLPS,该算法的设计思路可以类比于MTSP问题的解决方法,首先通过将权重POI进行分层处理,将每一层的初始路径计算视为一个TSP路径计算,而且各个初始路径之间互相独立,将路径进行汇总即可得到MTSP问题的一种解决方法。同时,需要考虑扫描覆盖问题自身的限制,如传感器节点的移动速度、扫描周期和返回时间等因素,因此,TLPS算法可以分为3个部分:目标分层策略,基于贪心策略的TSP路径计算,环路分割策略。

3.1 目标分层策略

目标分层策略主要实现对基站位置的计算以及权重POI的分层处理。

1)基站位置的计算。在现有研究中,基站通常放置于权重值最高的POI位置处,这样设置的优点是无需额外计算扫描路径到达基站的位置。但是,此种设计也存在一些缺陷,在权重值最高处放置POI会使得所有的扫描路径均经过该位置,虽然会使该位置获得较大的覆盖时间,但是当权重值较高的一些POI相对于此位置过于分散时,会导致其他POI只能往返于当前位置和基站之间,并不能访问其他位置,从而产生极大的能量消耗,导致路径利用率较低。

针对上述问题,本文算法将所有POI位置信息和对应的权重值相结合,计算所有POI的加权位置并作为基站位置,加权位置信息计算公式如下:

(1)

式(1)中W=∑wi为所有权重之和,基站坐标(x,y)为所有权重POI坐标的加权平均值。

(1)获取当前POI的权重最值wmin和wmax。

(2)设置当前层的权重wcurrent=wmin,从最小权重值wmin开始,将所有权重值满足wi≥wcurrent的POI加入到当前的权重分层中。

(3)增大wcurrent并重复第2步,直至权重分层到达wmax。

目标分层策略的具体流程如算法1所示。

算法1目标分层策略

输入所有POI的位置和权重

输出基站位置,POI分层

1.根据输入,计算基站位置:

2.获取权重最值wmin和wmax

3.令wcurrent=wmin,从wmin开始,将权重大于wcurrent的POI加入当前的权重分层中

4.得到POI分层

3.2 基于贪心策略的TSP路径计算

本节对已经分层完毕的各层POI设计初始化扫描路径。针对每一层POI,初始化路径是指包括该层所有POI位置和基站的环路。可以将移动传感器视为一位旅行商,层内所有POI视为目的地城市,而基站则为旅行商的出发城市和最终返回城市。因此,初始化扫描路径问题可以视为多个TSP问题。

由于上述问题是一个NP-hard问题,因此不存在多项式时间内解决该问题的算法。为了简便计算,本文拟使用贪心策略解决此问题,每次选择距离最近的POI作为下一目标位置,具体过程如算法2所示。

算法2基于贪心策略的TSP路径计算算法

输入基站位置,POI分层

输出初始化路径

1.计算所有POI之间的路径代价以及所有POI到达基站的代价,得到代价矩阵WPOI

2.针对每一层POI:

3.从基站位置出发,每次选择一个当前层内的POI,直至所有POI被访问完毕,返回基站

4.在每次选择下一个POI时,仅选择当前剩余的所有层内与当前POI之间路径代价最小的POI作为下一位置

5.end

6.返回每一层路径总代价和POI访问顺序,访问顺序即为初始化路径

经过上述基于贪心策略的TSP算法计算,可以得出所有POI的初始化扫描路径,此部分计算得到了目标分割策略中每一层的TSP路径,路径之间互相独立,将所有路径汇总即可视为WTSP问题的一种解法。但是,上述路径并未考虑移动传感器速度、扫描周期以及返回时间等因素,难以解决WTSC问题,因此,需要对该扫描路径进行进一步处理。

3.3 环路分割策略

本节对上节中得到的每一层扫描路径进行分割处理。在现有研究中,对于较长的扫描路径分割一般有2种解决方案:

2)第2种解决方案是对路径上所有点构建最小生成树,通过断开某些边使得断开的各个部分构成合适大小的连通分量,对连通分量进行处理构建环路。此种方法分割出的环路路径利用效率高,但是对于带有权重的POI分割效果并不理想。

本文在第2种解决方案中加入权重POI分割策略,提出一种环路分割策略,具体描述如下:

首先,计算单个移动传感器节点在单个扫描周期内的最大路径代价Pmax=vt,以此作为是否分割的一个判断参数;接着,针对每一个层级的初始化路径,以Pmax为标准,从当前路径中权重最大的POIi开始将其作为初始分割点,判断当前POIj的权重与当前权重层的权重值的大小关系,若当前POIj的权重大于当前权重层权重,则选择在此处断开,以保证当前权重节点可以满足对应于其权重的覆盖次数,若此位置不需要断开,则分别计算从此点开始到路径顺序中下一点以及到达基站的路径代价length,计算公式为:

length=lengthi,j+lengthi,node+lengthj,node

(2)

其中,lengthi,j为初始分割点与当前点之间的距离,lengthi,node和lengthj,node分别为这两点与基站间的距离。根据计算结果判断当前length与Pmax的关系,若length≤Pmax,则当前点从POIj前进到路径中下一个位置POIk;若length>Pmax,则当前点从POIj返回至路径中上一个位置,并在此位置断开,将此位置作为一个分割点,与上一分割点和基站之间构成环路。若在访问过程中所有POI都已经被访问过,则返回最初POI位置。最后,将从开始位置POIi到断点位置POIj再到基站最后返回开始位置的环形路径保存为一个分割路径,并将当前断点位置作为下一条环路的起始位置,沿着当前层初始路径按照上述步骤进行分割,直至当前层所有POI均在某一条环路中。环路分割策略流程如算法3所示。

算法3环路分割策略

输入POI分层,初始化路径

输出环路和移动传感器分配结果

1.计算Pmax=vt

2.针对每一层:

3.判断当前POIj与当前层间的权重关系

4.从权重最大的POIi位置分割,计算length

5.判断length与Pmax的关系

6.在断点POIj位置构建环路,并作为下一环路的起点

7.end

按照上述方法分割完所有的路径,得到一系列的环路,每条环路上部署一个移动传感器节点对该路径上的POI进行扫描覆盖,在该覆盖方法下,所有POI均满足WTSC模型要求。

4 实验验证

4.1 实验参数配置

在Matlab下进行实验以验证本文TLPS算法的性能。实验环境为500 m×500 m的正方形区域,所有POI随机均匀分布在此正方形区域内,POI节点权重值随机产生。移动传感器的移动速率相同,均为v,每个POI的扫描周期为相同的时间t,基站位置根据所有POI位置及权重共同计算得到。每次实验取100次结果的平均值作为最终结果。算法性能评估参数如下:

1)平均扫描周期:所有路径实际扫描周期的平均值。

2)移动传感器数量:在满足当前覆盖要求的条件下,算法部署在整个区域的传感器数量。

3)路径有效率:移动传感器实际运行路径与理论最大运行距离之间的比值,其反映当前路径被有效利用的程度,计算公式为:

(3)

其中,lengthmax=vt,为移动传感器的速度与扫描周期的乘积。

4.2 实验结果分析

本次实验将CSweep、MinExpand、OSweep和tcwtp作为对比算法。CSweep算法通过将所有节点划入同一条最短路径中,分割路径保证所有POI均可以被移动传感器覆盖;MinExpand算法根据当前设定的最高代价,不断添加新的POI到当前路径中以实现路径规划;OSweep在CSweep的基础上,将整条路径视为一条环路,不分割路径;tcwtp算法将POI的权重视为该位置所经过路径的数量,以此设计所有路径。由于上述算法均可以在相同的场景中应用且具有一定的优化效果,因此本文选择此4种算法作为对比算法。在实验过程中,所有移动传感器节点的性能相同。

在所有POI位置和权重相同的条件下,5种对比算法在移动传感器节点速度不同时的平均扫描周期对比如图1所示。其中,POI数量设定为100,最小权重值设置为1,高权重的节点数量为当前权重节点数量的10%,传感器节点的移动速度为唯一变量,由0逐步增加到30。从图1可以看出,随着移动传感器节点速度的增加,所有算法的平均扫描周期均下降。由于OSweep算法不对路径进行分割,所有节点均在原路径上运动,路径的利用率最高,因此其扫描周期相对于其他算法最短。相较于CSweep、MinExpand和tcwtp算法,本文TLPS算法平均扫描周期更短,原因是本文算法在对初始路径进行分割时充分考虑了单个传感器节点的最大路径代价。TLPS算法的平均扫描周期更短,因此,在移动传感器节点速度相同的情况下,每个传感器在扫描周期内移动的距离也更短,即每个移动传感器的能耗更少。

图1 5种算法的平均扫描周期对比Fig.1 Comparison of average sweep period of five algorithms

在POI数量固定的情况下,平均移动传感器节点数量随扫描周期的变化情况如图2所示。其中,POI数量和权重设定与上一次实验相同,移动传感器节点移动速度设定为20,扫描周期为唯一变量,从5逐步增加到25。从图2可以看出,随着扫描周期的增大,所有算法的传感器节点数量均减少,这是由于单个传感器节点的移动路径增大,可以覆盖更多的POI,因此可以减少部分传感器节点数量。而在扫描周期相同的情况下,TLPS算法相对于不考虑权重节点的覆盖算法而言节点数量较多,但是相对于tcwtp算法而言节点数量较少。这是由于TLPS算法在部署时对已存在的最短路径进行分割,分割时尽可能选择权重节点位置,这样会降低路径的代价,间接减少移动传感器的数量,此外,相对于不考虑权重节点的覆盖算法而言节点数量较多是由于其覆盖了较多权重更高的POI,相对于其他算法,本文算法的权重节点有效覆盖率更高。

图2 5种算法的平均移动传感器数量对比Fig.2 Comparison of average number of moving sensors of five algorithms

对比分析5种算法部署传感器后的路径有效率,在本次实验中,POI的数量为唯一变量,从50逐步增加到250,高权重节点数量占当前权重节点数量的10%,移动传感器的速度设定为20,扫描周期设定为15。从图3和表1可以看出,OSweep算法的路径有效率最高,这是由于其所有的移动传感器均在一条路径上移动,多余路径最少。而TLPS算法的路径有效率相对其他3种算法更高,这是由于该算法在分割每条路径时参考当前路径长度和单个传感器最大路径之间的关系,尽可能在每次分割时都保证路径有效率相对更高。同时随着POI数量的增加,TLPS算法依然能保持较高的路径有效率,间接降低了节点部署的代价。

图3 5种算法的路径有效率对比Fig.3 Comparison of path efficiency of five algorithms

表1 5种算法的平均路径有效率Table 1 Average path efficiency of five algorithms

5 结束语

本文提出一种带有权重和返回时间限制的区域覆盖问题,并证明其为一个NP-hard问题,针对该问题设计一种基于目标分层和环路分割的区域覆盖算法TLPS。TLPS算法对区域内的所有POI进行权重分层,并根据POI的位置和权重设置基站的位置。将各层路径规划问题转化为TSP问题,基于贪心策略设计初始化路径。在此基础上,根据权重要求和路径长度限制,提出环路分割策略对初始化路径进行分割,构建相对应的环路以部署移动传感器。实验结果表明,相比CSweep、MinExpand和tcwtp算法,TLPS算法在增加少量移动传感器数量的条件下平均扫描周期更短,目标覆盖率与路径有效率更高。下一步将针对三维空间中的覆盖优化问题进行研究。