改进的非均匀有向传感器网络节点部署方法*

谭 励，杨朝玉，杨明华，胡计鹏

（1.北京工商大学计算机与信息工程学院，北京100048；2.第二炮兵装备研究院，北京100094）

有向传感器网络是一种特殊的移动传感器网络，其节点不仅具有方向性，而且具有移动能力。

1 研究现状

1.1 有向传感器网络的部署

移动传感器网络是一种全新的信息获取与处理技术，其网络自组织、节点自移动，且低成本、低功耗的优势使其在多个领域得到了广泛应用。例如在环境领域，为了改善与大众生活健康息息相关的空气质量，构建兼具静止、可移动装置的混合传感器网络体系用于室内监测［1］；在基础设施中，基于信息物理融合系统CPS（Cyber-Physical System）分布式可计算无线传感器网络的出现，为智能建筑该方向的相关研究正逐渐扩宽与深入，尤其是针对节点方向性的部署问题。文献［4］以进行初期部署后出现的网络空洞为基础，构建Voronoi多边形，控制节点下一阶段的移动位置；文献［5］从安全应用角度出发，针对边界问题提出栅栏覆盖部署策略；文献［6］提出一种基于虚拟势场的有向传感器网络覆盖优化算法PCAFD（virtual Potential field based Converage Algorithm For Directional sensor networks）用于改进边界情况和网络优化过程中出现的节点往复运动现象，FFLRCA（Fictitious Force based Low Redundancy Coverage-enhancing Algorithm）算法用于网络进入稳定状态后根据节点及其冗余子集进行能量和位置上的调整；文献［7］采用分布式启发式算法，优化有向K覆盖问题，提高覆盖性能。此外，还有诸如最小代价算法［8］、启发式算法［9］、路径覆盖算法［10］等应用于传感器网络部署策略。

现有的有向传感器网络部署算法，主要解决了部署过程中的漏洞，能够较好的提高覆盖率。然而这些方法对于待覆盖区域缺乏分析，难以满足一些区域中的复杂部署要求。尤其是通过对待部署区域的分析发现，针对不同区域具有不同部署密度要求的有向传感器网络算法具有重要的实用意义。

本文提出了一种改进的非均匀有向传感器网络节点部署方法PFNDA（Potential Field based Non-uni⁃form Distribution Algorithm），能够适用于待部署区域的非均匀部署需求，针对区域内的优先监测块，引入“部署中心”对象模型，通过部署中心与传感器节点之间的相互作用，提高区域内的覆盖质量。

2 改进的非均匀有向节点部署算法

2.1 概念描述

2.1.1 部署中心

定义1部署中心范围。规定以重点监测区域中心为Sc圆心，该区域与中心的最远距离Rc为半径划定一圆形区域，该区域即为部署中心范围。

图1 部署中心

定义2部署中心密度。在节点集合覆盖能力不足的情况下，为保证节点尽可能广地分布，节点集合整体覆盖密度将有所下降。但对于部署中心而言仍需要保证足够的覆盖能力。因此，在部署中心范围内，将采取和其它区域不同的节点分布情况，这一控制系数则为部署中心密度。

2.1.2 有向节点

定义节点模型为带有虚拟力模型，由五元组＜p,L,α,θ,η＞表示。其中p表示节点的定位位置，L表示最远监测距离，α表示节点当前监测视角中轴指向角度，θ表示监测所能及的最大视角角度，η表示目标节点的邻近节点集合。

图2 有向节点

在非部署中心区域，目标节点与其邻近节点集合需要考虑两方面，其一是指向角度，其二是覆盖范围。当相邻节点间覆盖重叠量达到一定程度，则需要目标节点变换角度，提高覆盖率。

而在部署中心区域，覆盖重叠将作为次要考量，甚至可以忽视这一因素，对于非理想条件下，这种覆盖重叠甚至可以用于提升覆盖质量。指向角度作为主要的考量因素，目标节点的指向优先与部署中心有关。

2.2 算法模型

与均匀有向节点部署方法相比，非均匀部署方法中节点间的斥力作用同样基于质心点模型［11］。在此基础上，区别主要体现在移动节点在靠近部署中心时刻其相关属性发生变化。

图3 算法模型示意图

部署中心位置设为Sc，部署中心范围半径设为Rc。节点质心位置设为Sn，节点质心半径设为Rn。主要属性如下：

2.2.1 矢量引力

设区域内存在任意节点Pi，另有任一节点为Pj，则目标节点Pi受到的作用力Fi表示如下：

当节点Pj属于目标节点Pi的邻居节点集合Ni内且两节点间距离小于节点产生斥力的最大距离L斥时，目标节点受到该类节点产生的斥力向量；当节点Pj属于目标节点Pi的邻居节点集合内且两节点间距离介于节点产生引力的最小距离L引和节点产生斥力的最大距离L斥之间时，目标节点受到该类节点产生的引力向量；其它情况则不对目标节点产生作用力。

而节点与部署中心的作用力则相对简单。目标节点质心Sn(xn,yn)与部署中心Sc(xc,yc)的矢量距离为：

2.2.2 非均匀斥力

区域内活动的目标节点依据其与邻近节点的距离受到不同方向的虚拟斥力，且该值唯一。当目标节点在部署中心范围内时，为了获得更好的覆盖质量，根据需要调整虚拟斥力值。

若节点Pi在部署中心范围内，则调整后的节点Pi的作用力Fi′表示为

通过对参数fc的控制，减小节点模型的虚拟斥力以达到在部署中心范围内的节点集合分布更加密集。

2.2.3 节点方向控制

根据目标节点与部署中心距离d(Sn,Sc)判定目标节点的方向控制。当目标节点在部署中心范围外时，节点方向指向与其邻近节点集合相关，以提高覆盖率、减少重叠为主要目的，即当目标节点与邻近节点覆盖区域重叠时，节点方向变换直至没有重叠为止。为简化该步骤，可将圆周划分为多个等分区域，在目标节点变换方向时可按区域固定转动一定角度。当目标节点在部署中心范围内时，方向将以部署中心点为基准，使节点中轴线与部署中心点在同一条直线，以保证目标节点的视角中心指向部署中心区域。

2.2.4 部署质量评价

对于部署中心范围外的部署效果采用覆盖率评价，而对于部署中心内部涉及覆盖面积、覆盖方向、覆盖重叠多重考量，故使用部署质量这一指标进行评估。针对重点关注的覆盖面积问题，本次实验主要考量以下两点：

①有效节点数

该指标以实际应用角度出发，出于重点监测区域的产生使部分涉及该区域的节点监测目的不再是尽可能全面地监测更多区域，而改为优先监测以重点监测面积中心起始向外扩散至指定范围。为此本次实验认定重点区域内执行优先监测任务的节点即为有效节点，以此判定算法在非均匀部署条件下部分区域的重视程度。

②覆盖率

该指标通过节点在部署中心范围内覆盖面积与部署中心范围全面积之比进行判断。设总比面积为CN，单一节点面积为Cp，则覆盖面积指标表示为：

矢量引力和非均匀斥力属性均是有条件的，即在部署中心范围内才会生效，这表明范围的节点其一切调度策略均保留一般情况的有向传感器网络部署策略，故而对于范围外的覆盖质量评估不进行对比分析考察。

2.3 PFNDA算法描述

根据上述概念及模型属性分析，得到的改进的非均匀有向节点部署算法在保证原有网络覆盖质量的前提下，提高方向属性上的有效监测质量，使传感器网络更好地实现监测与通信功能。

算法伪代码如下：

算法具体步骤如下：

①初始化：节点根据其自身属性，关联其它节点，构建邻居节点集合。由于部署中心与节点基本具备相同属性，同样需要创建类似的节点集合。

②矢量引力：节点与其邻居节点集合内的所有节点依次判断之间距离，根据判断条件得到最终目标节点受到的虚拟作用力矢量。部署中心同样与其节点集合进行判断，但部署中心本身不会被施加任何作用力，符合条件的周边节点通过自身位置得出受到的虚拟引力矢量。

③非均匀斥力：存在于部署中心的有效感知范围内部的传感器节点在判断虚拟作用力时除去与邻居节点集合之间的计算外，还会受到来自部署中心的作用力参数控制的影响。部署中心范围内节点之间的虚拟斥力数值将会经由该参数发生变动，而其他区域维持不变。

④稳定状态：重复步骤①～步骤③直至整体网络结构达到稳定状态则结束部署。

3 实验及结果分析

3.1 实验环境

本实验是在改进后的The ONE仿真器环境的基础上进行的。仿真器环境以节点为基本单位，不同的节点赋予各自不同的性能，或遵循不同的协议，并将这些属性建立在移动模型上，最终通过仿真环境的GUI图形界面体现节点分布、移动、通信的性能表现。

改进后的The ONE仿真器屏蔽了路径规划模块，节点将不再按路径规划移动，而是呈现自由移动的状态。在这样的环境下的性能展示与评估可以排除其它外在因素，而只针对节点自身，从而更加清晰直观。

3.1.1 实验需求

针对部署中心需要考虑面积覆盖和方向覆盖两个方面。对于面积覆盖本实验需要达到相对于非部署中心区域，部署中心区域的覆盖率有明显提升，而且需要增加覆盖质量（为防止节点自身故障而引起的覆盖或连通问题而特意留有一定程度的重叠覆盖）系数以进一步加强面积覆盖。在方向覆盖上则要求在部署中心围绕范围内的节点方向均面向部署中心，保证部署中心为最主要监测焦点。

3.2 结果分析

本次实验设定在规定区域内任意设定一坐标位置为部署中心点并随机抛洒N个节点。根据实验要求记录了一定时间内节点部署活动轨迹及其对应的覆盖率变化轨迹，如图4所示，其中t为以节点运动开始为基准的时间增值。

图4 节点变化轨迹

但仅有这一属性仍稍有不足。在保证部署中心范围内的所有移动节点均指向中心点的同时，也意味着当部署中心的邻近节点达到稳定状态时，未被覆盖的部分，即覆盖空白区域也达到了稳定状态，而且相比非部署中心范围而言更加稳定。这是由于临近节点的监测方向不再放生改变所引起的。因而在原有基础上，部署中心还增加了非均匀斥力属性。

非均匀斥力属性在节点的方向监测性上面并没有什么表现，然而该属性使部署中心区域内覆盖节点之间的空洞大幅减少，几乎可以达到完全覆盖的效果。当然，这是以增加部分覆盖重叠同时牺牲一定的覆盖面积为前提的。

3.3 对比分析

通过上述结果表述，为进一步深化分析，本文采用与覆盖优先算法PFPCA（Potential Field based Priority Coverage Algorithm）［12］进行相关有效节点数和覆盖率上的对比分析。

3.3.1 对比算法描述

基于虚拟势场的覆盖优先算法PFPCA用于实现移动传感器网络的自动化部署。该算法摆脱了节点自身有关动能的约束，使节点运动只与最终虚拟合力是否为零有关，节点的旋转只与合力沿圆周的切线方向向量有关。

3.3.2 有效节点数

本节记录了两种算法在同等实验条件（如表1所示）下存在于部署中心范围内的节点数量以时间为基准的变化轨迹，如图5所示。

表1 实验要求列表

图5 有效节点数变化轨迹

根据图表中两者间的比较，可以看到PFPCA算法并未对范围内的部署节点采取特殊的方向控制，节点的方向属性变化完全取决于邻近节点状态，因此该算法下有效节点数量呈现不稳定的随机态势。而改进后的PFNDA算法在矢量引力影响范围内，节点数量不再只能是随机出现有效方向，而是在属性控制下全部指向部署中心。而在引入非均匀斥力后，带来部署中心范围内的节点最大存在数量的增加，更是呈现大幅度提升。

3.3.3 覆盖率

本节记录了两种算法在同等实验条件（如表1所示）下部署中心范围内（部署中心范围外的部署方法并未受到改进的属性影响，故不在此进行比对）以时间为基准的覆盖率变化轨迹，如图6所示。

图6 覆盖率变化轨迹

从图6可以看出，改进后的算法在达到稳定状态时覆盖率相比PFPCA算法有明显提高，这是因为在增加了非均匀斥力属性后，由于节点间间隙的减小而导致覆盖效率有了一定程度的增长。

4 结束语

针对传感器网络重点区域重点覆盖的实际需求，提出了一种改进的非均匀有向传感器网络节点部署方法，经由本文实验对比表明，通过对原有的有向节点部署方法的改进，该算法优化了在处理局部重点监测时有可能发生的监测面积和方位监测不足的问题。下一步可引入例如移动节点的能源持续性和休眠机制，部分区域的具体有效监测指标等更为详细的技术参数，对有向节点部署方法做进一步的优化和提升。

［1］Xiang Yun，Piedrahita R，Dick R P，et al.A Hybrid Sensor System for IndoorAirQualityMonitoring：Proceedings-IEEEInternationalCon⁃ferenceonDistributedComputinginSensorSystems，2013［C］//Cam⁃bridgeMA，Unitedstates：IEEEComputerSociety，2013：96-104.

［2］高治军，王洪玉，王鑫，等.智能建筑室内环境分布式可计算WSN任务调度研究［J］.传感技术学报，2014，27（3）：378-382.

［3］胡永利，孙艳丰，尹宝才，等.物联网信息感知与交互技术［J］.计算机学报，2012，35（6）：1147-1163.

［4］Liang Chiukuo，Chung Chengyen，Li Chuangfeng.A Virtual Force Based Movement Scheme for Area Coverage in Directional Sensor Networks：Proceedings-2014 10th International Conference on In⁃telligent Information Hiding and Multimedia Signal Processing，2014［C］//Kitakyushu，Japan：Institute of Electrical and Electron⁃ics Engineers Inc，2014：718-722.

［5］Wang Zhibo，Liao Jilong，Cao Qing，et al.Barrier Coverage in Hy⁃brid Directional Sensor Networks：Proceedings-IEEE 10th Interna⁃tional Conference on Mobile Ad-Hoc and Sensor Systems，2013［C］//Hangzhou，China：IEEE Computer Society，2013：222-230.

［6］戴宁，毛剑琳，付丽霞，等.基于虚拟势场的有向传感器网络覆盖优化算法［J］.计算机应用研究，2014，31（3）：905-907.

［7］张美燕，蔡文郁.无线视频传感器网络有向感知K覆盖控制算法研究［J］.传感技术学报，2013，26（5）：728-733.

［8］Osais Y，St-Hilaire M，Yu F R.The Minimum Cost Sensor Place⁃ment Problem for Directional Wireless Sensor Networks：IEEE Ve⁃hicular Technology Conference，2008［C］//Calgary，AB，Canada：Institute of Electrical and Electronics Engineers Inc.，445 Hoes Lane/P.O.Box 1331，Piscataway，NJ 08855-1331，United States，2008：1-5.

［9］Shankarachary Ragi，Hans D Mittelmann.et al.Directional Sensor Control：Heuristic Approaches［J］.IEEE Sensors Journal，2015，15（1）：374-381.

［10］陶丹，马华东，刘亮.视频传感器网络中路径覆盖增强算法研究［J］.电子学报，2008，36（7）：1291-1296.

［11］陶丹，马华东，刘亮.基于虚拟势场的有向传感器网络覆盖增强算法［J］.软件学报，2007，18（5）：1152-1163.

［12］Tan Li，Chen Yucheng.et al.Priority Coverage Algorithm and Per⁃formance Simulation for Node Deployment in Directional Sensor Networks［J］.Sensor Letters，2014，12（2）：275-280.