空洞弧段引导下异构传感网的覆盖优化策略*

吴 仪，秦宁宁，2*

(1.江南大学轻工过程先进控制教育部重点实验室，物联网工程学院，江苏 无锡214122；2.南京航空航天大学电磁频谱空间认知动态系统工信部重点实验室，江苏 南京211106)

随机部署的异构无线传感器网络WSN(Wireless Sensor Networks)虽能节约人力，但会造成传感器分布不均与网络空洞繁多等通信覆盖问题，同时节点间的异构属性使网络拓扑更为复杂。所以利用节点间位置信息探测出空洞，并使用节点移动的方式对空洞进行相应的修复，成为高成本的二次部署之外的一种有效优化网络覆盖的方案。

集中式算法广泛用于解决传感器网络的探测与空洞修补，通过平台或核心节点收集到所有传感器节点的位置等信息，统一计算勾勒全局空洞，并指引节点调整位置优化拓扑。该模式精确度较高，偏差较小，但更依赖网络全局信息。为探测空洞，文献[1]利用Voronoi图对网络进行划分，并使用虚拟边缘膨胀方法探测空洞；Li[2]通过判断Delaunay剖分的三角形外心是否被三个节点所覆盖，来确定空洞存在与否；穆天圆[3]利用泰森多边形的大小指导蜂群算法中引领蜂的生成，以迅速定位全局空洞。在修补空洞的研究中，文献[4]结合Voronoi与Delaunay，建立盲区与待修复位置的匹配模型以实现空洞修补；除上述利用网络的计算几何架构信息外，凌春[5]也利用节点的覆盖信息指引蚁群搜索的方向，以信息素浓度判断节点的空洞边界信息；周宇[6]提出了最小覆盖圆与蜂窝生长两种修补空洞方法，对不同形状的空洞采取不同的算法进行修复。文献[7]通过空洞建立虚拟修复位置和移动节点的距离对照表，生成全局最佳的移动策略。文献[8]以非并行的方式选择含空洞劣弧的边界节点，并将其作为空洞修复驱动节点，采用弧二分法确定最佳修补位置。

虽然以寻优为目标的集中式算法精度较高，但运算复杂度也随之更大。分布式的本地算法将中央处理器的计算任务分散到各节点中，采用并行或时间戳交换的方式加快探测和修补效率。分布式探测空洞研究中，文献[9]建立极坐标系，得到邻居间相对位置与覆盖弧信息，确定节点的单纯覆盖弧序列并生成覆盖空洞；马文钰[10]提出了边界线段检测与圆周检测进阶式双算法，并将其扩展到K－覆盖场景。文献[11]使用周长边界算法验证节点是否被指定节点覆盖，并通过弧交点位置以确定是否为边界节点。为了分布式修补空洞，文献[12]通过覆盖邻居信息对节点建立模糊推理系统模型，选择最适合的邻居节点移动修补。Khalifa B[13]对空洞临界节点进行判断，量化其对空洞的重叠度和剩余能量，选择节点以膨胀或移动方式进行修补。黄祎[14]在考虑节点剩余能量、覆盖冗余率与移动距离信息的基础上，择优节点进行空洞修复。

在已有的优化空洞覆盖问题研究中，无论是利用复杂但准确的集中式方案，还是低成本但粗糙的分布式方案，皆普遍地将探测与修补过程人为分裂成两个独立环节加以研究；并且相比于同构网络的空洞研究，直接面向异构网络场景的成果更为罕见。

基于研究过程的分裂性和对象的单一化问题，论文提出的CHHA算法融入了异构元素，并连贯一致地解决传感网空洞的探测与修补。首先将连续空间面上寻找空洞的问题转化为在有限离散空间交点间寻找空洞；在节点收集的空洞信息顺序穿连的同时，巧妙勾勒空洞轨迹；为体现探测与修补空洞间的耦合关系，算法对勾勒的空洞弧信息与节点特征加以区分，给出针对性的修补方案。针对异构网络的CHHA算法，基于本地化完成探测勾勒空洞的同时，对空洞进行了较为高效的修补。

1 基本概念

1.1 场景架构

考虑到传感器节点间的异构性且具有移动属性，将对网络的模型做如下假设:

网络模型:矩形区域DetectArea＝X×Y内随机抛撒N个异构可移动的传感器节点S＝{s i(x i，y i)｜i＝1，2，…N}[15]，其中(x i，y i)为s i的中心坐标。

异构模型:传感器节点s i的多级异构属性体现在感知半径R s i∈[Rsmin，Rsmax]，节点均采用布尔感知模型[16]，即节点可以监测圆盘区域Sensori＝{(x，内的任意点。为满足节点间的通信要求，s i的通信半径Rc i需满足

1.2 相关定义

若点s i与s j间的欧式距离d(s i，s j)满足d(s i，s j)

定义1 弧交点

Sensori与Sensorj的弧交点记为:

若s j∉NeiListi，则｜AIi，j｜＝0；若d(s i，s j)＝R s i＋R s j，则｜AIi，j｜＝1；若d(s i，s j)

若∀C∈Arci_AB满足则Arci_AB为空洞弧，记为hole(Arci_AB)＝1；反之，hole(Arci_AB)＝0，其中，hole(·)＝1表示其中的元素·不被其他节点覆盖。s i的空洞弧集合记 为 HoleListi＝ { Arci_AIListxiAIListx＋1i｜ hole(Arci_AIListxiAIListx＋1i)＝1}，HoleListn i记为HoleListi中的第n条空洞弧，1≤n≤｜HoleListi｜。若圆心角则Arci_AB该弧称为优弧；反之为劣弧。

定义3 覆盖率[15]

DetectArea内，S中所有节点感知圆盘并集的占比，作为该网络的覆盖率，记为:

定义4 平均移动距离[16]

s i在优化前后的位置分别为(x i，y i)和(x′i，y′i)，则S在算法运行过程中的平均移动距离记为

2 勾勒空洞

探测空洞是优化网络拓扑的前提，节点如何从分布不均的网络中，准确并快速地探测出自身覆盖圆弧上的全部空洞弧是探测阶段的关键。通过一跳覆盖邻居信息，节点分布式地探测本地覆盖圆周上的空洞弧，并对其进行勾勒。

2.1 空洞弧判断策略

s i以自身为原点建立极坐标系，收发一次信息即可得到NeiListi，继而计算得出AIListi，AIListi中相邻的弧交点会将s i覆盖圆弧划分成若干个首尾相连且互不相交的弧子段。

定理1 若∃C∈Arci_AB使得hole(C)＝1(C≠A＆C≠B)，则hole(Arci_AB)＝1。

证明:采用反证法。假设∃C∈Arci_AB使得hole(C)＝1(C≠A＆C≠B)，但hole(Arci_AB)＝0。因为A和B是两个连续的弧交点，所以∀A′∈Arci_AB皆满足hole(A′)＝hole(Arci_A B)；由结论得知，hole(Arci_AB)＝0且C∈Arci_AB，所以hole(C)＝hole(Arci_AB)＝0，与假设矛盾，不成立。所以若∃C∈Arci_AB使得hole(C)＝1(C≠A＆C≠B)，则hole(Arci_AB)＝1，证毕。

2.2 空洞勾勒

通过两个相邻弧交点，即可得出两者间弧子段的空洞属性。按定理1对s i所有弧子段依次遍历，判断s i是否处于空洞边界，进而计算出s i的所有空洞弧段，并勾勒空洞弧。具体流程见表1伪代码所示。

表1 空洞勾勒步骤

Line6是基于定理1筛选空洞弧的过程。节点仅需自身一跳邻居位置信息，即可对自身覆盖圆弧进行拆分，进而勾勒出节点的所有空洞弧。

3 修补空洞

节点如何利用空洞信息来最大化移动效率，是网络拓扑优化的关键。论文中，si将会以HoleListi作为修补目标，依照空洞弧的数量与半径，选择自修补或招募冗余节点修补的方式对空洞弧进行相应填充。

3.1 节点冗余评估

若将某节点移除，网络覆盖率不会因此降低，则该节点为完全冗余节点。显然，完全冗余节点在网络中的实际价值并不大，甚至会产生信息冲突问题；但该类节点却能作为修补空洞的候选节点。若以合适的方式评估出完全冗余节点并加以应用，则能以较低的开销优化网络的拓扑性能。

定义5K－覆盖邻居交点

若∃ 1≤p≠q≤Degreei，满足条件｜AINeiListpi，NeiListqi∩Sensori｜≠0，则s i的覆盖邻居交点CAIListi＝AINeiListpiNeiListqi∩Sensori。 若s i∩NeiListi覆盖该交点的次数为K，s i的所有K－覆盖邻居交点组成集合K-CAIListi。

如图1所示，CAIListi＝{A，B，C，D，E，F，G，H，I}中，1－CAIListi＝{A，B，C，D，E，F，G}；2-CAIListi＝{H，I}，H、I被s i与s j同时覆盖。显而易见，对于s i的1－CAIListi，1对应的就是s i节点本身，若将s i移除，则1－CAIListi中所有点皆为新产生空洞的边界点。而对于si的K－覆盖邻居交点(K>1)，若将s i移除，仍有K－1个节点将该交点覆盖。

图1 空洞边界节点的空洞弧集合

定理2 若Degreei≠0，｜1－CAIListi｜＝0，｜Hole-Listi｜＝0皆成立，则Sensori是一个完全冗余节点。

证明:采用反证法。假设Degreei≠0，｜1－CAIListi｜＝0，｜HoleListi｜＝0皆成立，但s i不是一个完全冗余节点。由于s i不是一个完全冗余节点且｜HoleListi｜＝＝0，所以若移除s i，新产生的边界点一定在Sensori内，而Sensori内的边界点必定是1－覆盖邻居交点，与｜1－CAIListi｜＝＝0矛盾。所以若Degreei≠0，｜1－CAIListi｜＝＝0，｜HoleListi｜＝＝0皆成立，则s i是一个完全冗余节点，证毕。

节点通过自身一跳覆盖邻居信息即可得到自身的1－CAIListi，并与HoleListi信息辅以比较从而判断自身是否完全冗余。具体流程如表2所示。

表2 节点冗余评估步骤

上述流程中，s i收发一次信息得到NeiListi，并通过一跳覆盖邻居位置计算其1－覆盖交点。s i通过Degreei、CAIListi和HoleListi三个指标，即可精准判断自身于网络是否冗余。

3.2 自修补

探测出自身覆盖圆盘上的空洞弧之后，节点首先可以尝试移动自身填补空洞。

在｜HoleListi｜>1或∠HoleList1i>π/2的条件下，s i进行移动可能会产生更大的覆盖冗余或空洞，所以自身移动修补时仅选择唯一劣弧进行修复。另外，若s i移动时始终保持对1－CAIListi全覆盖，则s i不会新增空洞弧。

①自修补条件

Degreei>1的前提下，｜HoleListi｜＝1且为劣弧时，节点s i执行自修补。

②移动方向

为尽量填补空洞对网络覆盖造成的影响，将空洞弧中点设为目标方向，记为:

③移动距离

1－CAIListi中第k个点CAIListi｜)，以－αi为方向交Sensori于点Roundn。则s i执行自修补时的移动距离Disi为:

式中:k＝1，2，…，｜1－CAIListi｜。

3.3 招募修补

若节点s i不满足自修补条件，可从NeiListi招募完全冗余节点对空洞弧进行移动修复。

若s i为HoleListi中所有弧进行招募，会造成多段空洞弧对同一关联节点的反复招募计算，引发复杂度极大提升；再者，该举动会使得s i的邻居可能会面临“无节点可招募”问题，导致s i陷入局部最优。所以s i执行招募修补时，仅将弧targetArc满足作为修补目标。

3.3.1 招募匹配

给定s i，NeiListi中所有完全冗余节点组成招募候选节点集合表示ReListi中第n个节点在S中的编号，1≤n≤｜ReListi｜。

定义6 空洞匹配因子

若s j∈ReListi，DisSumj表示s j的总移动距离，l(targetArc)表示targetArc的直径，邻居s j对s i的空洞匹配因子记为:式中:ω1、ω2与ω3皆为空洞匹配因子的控制系数。

s i招募节点时考虑到ReListi的DisSumj以节约能耗，并优先招募Rs较小的节点以节约招募资源。

3.3.2 招募选择

设targetArc的两个弧交点分别为A(x a，y a)和B(x b，y b)，targetNodei目标位置target的计算公式为

上式可能会出现两个解target，target′，target满足d(targetNodei，target)>d(targetNodei，target′)。

3.4 修补实例

图2 与图3分别为节点满足自修补或招募修补条件时的移动轨迹。

如图2所示，1－CAIListi＝{A，B，C}，｜HoleListi｜＝1且所以s i执行自修补，向空洞弧中点方向α移动min(d A，d B，d C)＝d A，即点位置处。

图2 自修补空洞弧

如图3中所示，ReListi＝{s x，s y}。即使存在DisSumx＝DisSumy，但由于Rs xhMatchi，y成立，因此应招募s x进行修复。

图3 招募节点修补

3.5 算法流程

CHHA算法基于本地优化的操作，在精准探测空洞的前提下，极大提升了覆盖质量，并兼顾了节点能耗。CHHA算法能有效提高网络的应用价值，其分布式属性是贯穿整套识别、勾勒、修补空洞系统流程的精髓。对给定节点s i，CHHA算法仅需辐射其一跳范围内的通信邻居，即可对自身拓扑位置上的空洞进行全流程处理，具体流程描述如表3所示。

表3 CHHA算法流程

S中每个节点利用CHHA算法以基于本地的方式进行空洞探测与修补。Line1为探测阶段，节点仅利用自身一跳邻居信息即可检测出HoleListi；Line2－4为自修补补偿方案，节点通过场景拓扑计算本地最佳位置移动修补；Line5－13为招募修补方案，通过定义的空洞匹配因子，选择最佳匹配冗余节点，实现移动能耗与最优选择的多重增益。由于S在计算1－CAIListi时需要比较邻居与邻居的位置，所以算法的复杂度为o(｜NeiListi｜2)。

4 仿真实验

4.1 场景配置

论文的仿真实验采用MATLAB R2016a平台进行测试。仿真主要从可行性、空洞探测的算法复杂度及空洞修补的性能等方面进行验证。鉴于实际应用中传感器节点布置方式为随机布撒且节点具有异构性能，各仿真部分的结果均为多次位置、性能随机实验后的算术均值。

网络的异构差异主要体现在节点的感知半径Rs在给定范围内的随机性。默认参数配置如下:DetectArea＝100 m×100 m，R smin＝4 m，R smax＝6 m，N＝200。经大量实验结果分析得知，各算法在寻优15轮左右后逐渐收敛，故设定算法的寻优次数上限为times＝20。

4.2 效果测试

图4 统计了CHHA算法对空洞的识别与勾勒效果，以及运行前后对网络拓扑优化的对比。运行初期(times＝1)，空洞约存在17个，CovRatio(S)＝78%，随着算法的迭代运算，当达到次数上限(times＝20)时，CHHA算法的CovRatio(S)提升至98.12%，空洞个数仅为5个左右，且空洞面积极大缩小。可见，CHHA算法能对所有空洞精准判断，同时将网络逐渐铺散，达到显著提升场景覆盖的效果。但由于分布式算法的特性，节点对通信范围外的节点是不可见的；所以必须承认，局部修补的效果受到初始随机铺撒的影响，不能避免零碎空洞。

图4 CHHA算法的工作效果

4.3 效率测试

大多数算法为了更好地阐述问题与研究区分，通常将探测与修补空洞人为地拆分成两个问题进行解决，因此连贯而一体化完成空洞探测与修复的现有文献并不多见。因此，论文不失一般性地将CHHA算法分别与VEBC[1]、EBDC[11]、CHDA[9]三种经典空洞检测方法，HHHA[12]、MDL[13]两种经典空洞修补算法进行分步地性能测试与对比。

①空洞识别效率

探测空洞的效率可以通过机器的运算速度ConsumeTime直接反映。S的平均度记为AvgDegree＝可以表示网络的平均拥挤冗余程度。本实验将考察CHHA算法与同类的VEBC、EBDC、CHDA三种算法的检测效率对AvgDegree的敏感情况，即网络冗余程度对算法勾勒空洞效率的影响。论文中节点布撒的个数N一般皆大于200个，使用密集网络的主要原因是:密集网络的空洞更为的繁杂，在招募节点进行修补时有更多选择的空间；而在稀疏网络中，节点对空洞的探测效果与密集网络基本相同，但在修补时不大具有可行性，所以为了达到网络空洞的修补效果，论文的仿真部分皆从密集网络入手。

如图5(a)所示，随着AvgDegree增长，网络的冗余量上升，从而导致执行探测空洞过程的复杂度增大，因此四种算法的ConsumeTime呈递增趋势。由于CHHA算法仅需要一跳邻居信息即可勾勒空洞弧，其ConsumeTime随AvgDegree增长仅呈线性增长，因此其复杂度低于其他算法；VEBC算法由于使用到了通信半径外的虚拟点，即需要获取一跳以外的邻居信息，所需消耗的运算时间较高。

图5 算法效率对比图

②空洞修补效率

网络整体覆盖率的变化趋势可以直观评估空洞修补效率，因此该部分统计了CHHA算法与HHHA、MDL两种算法的覆盖性能提升情况。如图5(b)所示，三种算法均可对空洞弧进行不同程度的修补，有效优化网络的覆盖拓扑CovRatio，并趋于平稳。CHHA算法相较于HHHA、MDL两种算法上升的速度更快，在times＝8时就到达了最高CovRatio(98.2%)的98%，比HHHA算法提前7轮收敛，即Δtimes＝7。这是因为在招募冗余节点环节，符合要求的节点利用CHHA算法，可以有效招募并派遣自己覆盖邻居中的完全冗余节点，对自身覆盖圆盘上的空洞弧进行修补。可见，CHHA算法能以更高的迭代效率达到相对稳定与较优的覆盖率。

4.4 能耗对比

修补空洞弧时，传感器节点的移动会造成大量的能量损耗，通过能量损耗大小能够评估出算法的可行性。论文以网络S的平均移动距离AvgDis作为能量损耗的尺度，衡量CHHA与HHHA、MDL三种算法的能耗受times与AvgDegree的影响程度。

如图6所示，各算法的AvgDis随times的增加呈递减变化，这是因为随着算法的运行，空洞弧区间越来越少，场景覆盖率逐渐饱和；另一角度，AvgDegree的增加会导致节点间的拓扑结构更为“紧凑”，在修补时节点需要移动更远的距离才能铺散开。但CHHA算法的AvgDis图形始终被HHHA、MDL所“覆盖”，这是因为在选择冗余节点进行修补时，综合考虑冗余节点当前已移动距离以及冗余节点到空洞弧的距离，尽可能避免节点无效的移动损耗。如图所示，在实验中初始场景条件最好的Avg-Degree＝5条件下，CHHA算法(1.45 m)能比AvgDis最大的HHHA算法(1.98 m)节约四分之一左右的移动损耗，且对AvgDegree具有更低的敏感性。

图6 修补空洞能耗对比

4.5 对异构性的敏感度

异构性体现在网络中节点在拓扑和覆盖范围上的差异性，数值上体现为R smax与R smin间的跨度差异，其异构率HeteroRatio＝R smax/R smin则反映了这种感知半径的差异性。HeteroRatio不同的情况下，为保证节点间的连通性能，传感器网络的拓扑会不尽相同。本实验统计了CHHA与HHHA、MDL的覆盖率对HeteroRatio改变的敏感程度。

记ΔCovRatio为网络覆盖率在算法执行后的优化量。如图7可见，三种算法虽能在HeteroRatio不同的情况下，一定程度地有效提高ΔCovRatio(即ΔCovRatio>0)，但其增速在图中体现为下降趋势。原因在于，当HeteroRatio提高时，节点的空洞弧增加，很多完全冗余节点的直径(2Rs)小于空洞弧的跨度直径距离，不能有效修复空洞弧；同时节点异构率的增大也会导致网络中节点与节点间的拓扑更加地“紧凑”，冗余度相对提高，从而导致CovRatio受到影响。但CHHA的ΔCovRatio始终大于HHHA与MDL，这是由于每次在修补空洞弧时，节点计算冗余节点的空洞匹配因子时，会优先为目标空洞弧招募半径小、离空洞弧近的冗余节点进行修补，从而达到分布式最佳的策略。

图7 异构程度对覆盖率的影响

5 总结

论文针对异构传感器网络的拓扑问题，提出了一种分布式探测与修补空洞的算法。通过算法，节点仅需知道一跳邻居的信息即可计算出自身覆盖圆盘上的所有空洞弧；节点将对空洞弧的数量及大小进行判断，从而使用合适的修补策略对目标空洞弧进行分布式地修补，从而增强网络的覆盖效能。仿真结果表明，相较于VEBC、EBDC、CHDA三个已有的空洞发现策略，CHHA算法能以更高的效率检测空洞；且CHHA算法相较于HHHA、MDL也能以更高的效率、较低的能耗、对网络异构差异更低的敏感性对空洞弧进行修补。