无线传感器网络中节点部署的质量直接影响到网络的性能，部署问题作为无线传感器网络中研究的基本问题[1]，反映了传感器网络所能提供的感知服务质量。目前，对于传感器网络部署问题的研究，多数是以全向同构传感器作为研究对象[2-4]。全向同构传感器网络简化了节点模型，但应用领域却受到了限制，通常适用于检测如温度、湿度等简单的环境数据。有向传感器网络在人们的生产、生活中的应用更为普遍，由于感知角度受限，只需感知来自某一方向的信息，且感知角度范围通常存在差异，需要针对性地进行研究。
近年来针对有向传感器网络部署问题的研究越来越多。文献[5]针对无线传感器网络部署问题提出有向传感器网络方向感知模型, 没有对异构节点部署进行针对性研究。文献[6]通过物理学中虚拟势场的作用，提出了一种基于虚拟势场的有向传感器网络覆盖增强算法(Potential Field-based Coverage Enhancing Algorithm, PFCEA)，该算法中节点间的作用力同样基于质心点模型，与本文算法区别主要在于节点移动到目标路径后会通过自主旋转和移动增大覆盖率等。文献[7]针对重点区域覆盖不足的问题，提出了一种改进的非均匀有向传感器网络节点部署方法，该方法的使用场景主要在当需要覆盖重点区域时，使用传统方法不能有效突出重点区域；但研究对象仍然为有向同构节点，而异构节点更符合实际需求。文献[8]针对复杂区域的无线传感器网络覆盖优化问题，使用以扇形节点围绕质心点转动的节点模型，提出一种基于虚拟势场的复杂区域覆盖优化算法(Coverage Optimization Algorithm for directional sensor network in Complex Area, COACA)，通过减小节点的旋转面积实现部署优化，该算法的研究对象是有向同构节点；而本文的研究对象为异构节点，更具有实际应用价值。文献[9]提出了一种无线传感器网络动态覆盖算法，通过调整目标覆盖区域几何边界，协同调度无线传感器网络节点，从而实现目标区域无线传感器网络动态覆盖；该算法用于解决动态覆盖问题，不适合解决异构节点部署。文献[10]针对多跳无线传感器网络中数据采集只采用单目标优化策略带来的问题，提出一种基于多目标优化的可移动sink节点部署模型；该算法模型以传感器网络部署能耗最低为主要目标，而本文算法模型除以能耗为目标还考虑节点覆盖率、重叠率等指标。文献[11]针对高大规模密集部署的无线传感器网络节点覆盖率，提出一种基于虚拟力的节点分簇动态部署策略；该算法以打破网络中部节点受力平衡、降低部署过程中簇间干涉、提高节点覆盖率为目的，但没有考虑到节点的异构特性，仅仅针对有向同构节点进行研究。文献[12]针对覆盖空洞、节点分布不均匀问题，通过边界部署保证边界上的完全覆盖和连通；通过该算法部署不需要额外探测和修复成本，算法仅仅是基于传统算法模型上作了些改进，并没有考虑节点异构性。文献[13]在含有移动节点的混合无线传感器网络中，采用更符合实际情况的基于误警率的概率探测感知模型；该算法针对有同构节点能提高检测区域的覆盖率，但针对异构节点效果并不理想。
现有的部署算法大多数以同构节点作为研究对象，而异构性更符合实际需求。本文以异构的无线传感器网络作为研究对象，提出了有向异构传感器网络节点的感知模型、虚拟作用力模型，在此基础上提出了一种适于有向异构传感器网络目标路径覆盖的精确部署算法(Directional and Heterogeneous Precision Self-deployment Algorithm，DHPSA)，从而达到精确部署的目的，并且增大覆盖率、减小重叠率。
1 DHPSA模型 1.1 假设与定义首先作出如下假设与定义。
假设1 每个节点自身当前的位置可以通过全球定位系统(Global Positioning System，GPS)或相关算法计算出，并得到确定的坐标信息。
假设2 节点的通信半径为Rc，当两个节点间的直线距离Dij小于或等于节点本身的通信半径Rc时，这两个节点互为彼此的邻居节点，互相之间可以通信。
假设3 节点在通信半径Rc内能量连续，通信半径外通信能量为0。
定义1 在监控区域内，若某个节点与其邻接节点的覆盖区域存在重叠，则称重叠部分为这两个节点的覆盖重叠区域。
1.2 有向异构节点感知模型传感器感知能力是指传感器感知模型覆盖范围的大小，异构传感器网络主要体现在传感器感知能力的不同，通过简单的抽象，可以得到异构有向传感器节点的二维感知表示，如图 1所示。
|
图 1 有向异构传感器网络节点 Figure 1 Directional heterogeneous sensor network node |
有向异构传感器网络节点的二维感知模型为如图 2中实线所示的扇形，用三元组〈R, V, α〉表示。其中：R是扇形的半径，表示节点最大感知距离；V是单位向量，位于扇形的中轴线上，表示传感器的感知方向；α是该扇形的张角，表示传感器的感知角度，称为视场。特别地，当α=2π时，即为二维全向传感器。
|
图 2 有向异构传感器感知模型 Figure 2 Directional heterogeneous sensor perception model |
判断监测区域内位于T位置的目标点是否被位于P位置的传感器节点i〈Ri, Vi, αi〉覆盖，可以使用如下方法：如图 2所示，如果‖TP‖≤Ri且TP*Vi≥‖TP‖cos(αi/2)，则目标节点被覆盖，否则不被覆盖。
1.3 有向异构传感器网络作用力模型理想状态下，无线传感器节点在自动部署过程中通常受到两种类型的作用力，分别是节点之间虚拟作用力和路径所产生的虚拟引力。本文节点间作用力引入了斥力半径作为受力平衡位置，引入节点质心作为节点受力点。而路径对节点的引力引入了节点到路径的垂足点，节点每次移动都是沿着垂足点方向移动，从而减小能量的消耗。与文献[14]提出的基于虚拟力的精确部署算法(Virtual Force-based Precision Self-deployment Algorithm, VFPSA)不同，本文提出的DHPSA策略为当节点移动到路径后，节点通过受到邻居节点的合力来调整节点位置或旋转方向，通过不断地移动和旋转使覆盖率逐渐变大，重叠率逐渐变小。
1.3.1 节点作用力模型节点间作用力的模型是基于物理学中电场的概念，将传感器节点看作是电场中的某个带电荷的粒子，由于电场中存在引力和斥力，节点之间也存在引力和斥力的作用，其中节点距离和受力关系如图 3所示。
|
图 3 节点距离和受力关系 Figure 3 Relation between node distance and force |
由以上建立的距离和受力模型可建立如下作用力关系式。
其中，引力和斥力的作用范围都是[0，Rc]，其中Rc指节点的通信范围。假设存在Rk(Rc>Rk)，当节点Pi和Pj的距离0 < Dij < Rk时，节点Pi和Pj表现为斥力，并且斥力大小随着距离增大而减小；当节点Pi和Pj的距离Rc>Dij>Rk时，节点Pi和Pj表现为引力，并且引力大小随着距离增大而减小；当节点Pi和Pj的距离Dij=Rk时，节点Pi和Pj之间作用力为零，即最理想平衡状态。在通信范围内节点之间总是存在引力或斥力使得节点之间收敛于Rk，最终达到平衡状态。
节点A和B所受的作用力(包括引力和斥力)关系式如下：
| $ \begin{array}{l} F(A, B) = \\ \;\;\;\left\{ \begin{array}{l} {(\frac{\alpha }{{{k_1}{D_{ij}} + \beta }})^\theta }, \;\;\;\;\;\;\;0 < {D_{ij}} < {R_k}\\ 0, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{D_{ij}} = {R_k}或{D_{ij}} > {R_c}\\ -{(\frac{\alpha }{{{k_1}{D_{ij}} + \beta }})^\theta },\;\;\;\;\;\;\;{R_k} < {D_{ij}} \le {R_c} \end{array} \right. \end{array} $ | (1) |
其中：正号表示引力；负号表示斥力；Dij表示节点间距离；Rk表示平衡时距离；Rc表示通信半径；α、β、θ、k1表示为增益系数。
1.3.2 路径作用力模型为了实现节点对目标路径的有效覆盖，提出“引力曲线”的概念，即目标路径会对每一个节点产生引力，在此引力的作用下使得节点自主向目标路径移动，实现对目标路径的覆盖。对任意节点A，总能够找到一条到达目标路径的最短路径，其最短距离定义为D。最短路径所对应的目标路径上的垂足点，定义为节点在曲线上的投影点P。投影点P与节点A间存在引力作用，且引力由投影点P指向节点A，使得节点在移动过程中能够始终沿“最短路径”不断接近目标路径，最终完成对目标路径的覆盖，如图 4所示。
|
图 4 目标路径对节点作用力示意图 Figure 4 Force schematic diagram of target path to node |
节点受到引力曲线的引力可以用如式(2) 所示：
| $ F(i, j) = \left\{ \begin{array}{l} {\left( {\alpha /{d_{ij}}} \right)^\beta }, \;\;\;\;{d_{ij}} \ne 0\\ 0, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{d_{ij}} = 0 \end{array} \right. $ | (2) |
其中：i为传感器节点，j为节点在指定路径的垂足点，dij表示节点与垂足点间距离，0表示节点已经到达路径且路径对节点作用力为0。
1.3.3 节点旋转模型与文献[14]提出的精确部署算法相比，该算法节点间的作用力同样基于斥力模型，区别主要在于节点到达路径后，会受到邻居节点作用合力来进行移动和旋转，通过移动和旋转角度增大覆盖率与减小重叠率，如图 5所示。
|
图 5 节点旋转模型 Figure 5 Node rotation model |
图 5中：S表示传感器节点；V表示节点的感知方向的单位矢量；F合1和F合2分别表示节点受邻居节点的矢量合力，位于节点感知方向的不同两侧；若合力如F合1所示，则节点将逆时针旋转一个步长，若合力如F合2所示，则节点顺时针旋转一个步长，直到节点受力完全达到平衡状态。
2 DHPSA过程描述基于前面建立的模型，实现DHPSA，该算法是一个分布式算法，即所有待部署节点都并发地执行该算法。算法主要步骤如下。
1) 初始化。首先对节点初始位置和感知方向初始化，关联其他节点，构建每个节点的邻居节点集合。初始化节点合力为零时暂停的时间长度、节点的移动步长及到达路径后的旋转角度。
2) 移动过程中。节点与其邻居节集合内的所有节点依次判断之间的距离，通过距离来计算每个邻居节点对当前节点产生的作用力，最终得出邻居节点的合力；目标路径会对当前节点产生引力作用，计算出当前节点到目标路径投影点距离从而计算出引力大小；最终求出当前节点受到的合力从而确定移动的方向和距离。
3) 移动到路径后。节点移动到目标路径后将只会受到路径节点的作用力。首先，设置一个信号量变量sign，通过信号量来控制节点是移动优先还是旋转优先；其次，计算出当前节点受到邻居节点合力，将合力与节点感知方向比较，若合力在感知方向左侧，则节点将向左移动或旋转，若在右侧将向右侧移动或旋转，节点移动和旋转通过信号量控制进行选择，在旋转能减少重叠的情况下优先选择旋转。
4) 稳定状态。重复步骤1) 至3) 直到整个网络部署达到满足要求的覆盖率及重叠率。
算法伪代码描述如下：
初始化节点部署初期位置Pi(x, y)，Vi；
初始化时间步长Δt，移动步长stepLength，旋转角度Δθ；
While(1)
{
int sign=0；
//定义信号变量用于判断节点到达路径后移动或旋转操作
初始化Fni；
获得节点i当前坐标信息p(xi, yi)；
获得节点i当前感知方向v；
if(节点不在路径) //判断节点是否已经到达路径
{
搜索节点i的所有邻居节点；
按式(1) 判断并计算出引力或斥力大小Fi；
求出节点之间的作用力的合力Fni=Fi+Fni；
//邻居节点作用力的叠加
计算节点i在路径上的垂足点；
//采用有限分割，求得近似最短距离
按式(2) 计算得出曲线路径对节点i的引力Fpi；
计算出节点i所受到的合力，即Fi=Fni+Fpi；//矢量和
if(Fi==0) //判断合力
本次不移动，并等待一个Δt时间步长；
Else
沿着合力方向移动一个距离步长；
}
Else
{
搜索节点i的所有邻居节点；
按式(1) 判断并计算出引力或斥力大小Fi；
求出节点之间的作用力的合力Fni=Fi+Fni；
//邻居节点作用力的叠加
If (合力为零)
本轮不移动；
Else
将合力方向与感知方向比较，确定节点下一步运动方向；
判断信号量的值，确定节点下一步是移动还是旋转；
节点移动一个stepLength步长或旋转一个Δθ；
}
}
部署算法流程如图 6所示。
|
图 6 DHPSA主要流程 Figure 6 Main process for DHPSA |
算法核心部分分析如下。
1) 搜索邻居节点。
for (i=0;i < m; i++){
if (distance < R斥){
addCollections(p[i]);
}
} //构建邻居节点
复杂度分析 整个网络中存在m个传感器节点，系统循环搜索所有个节点，依次计算每个节点是否属于该节点的邻居节点，若是邻居节点将放入邻居节点集合中。循环次数为节点个数，因此时间复杂度为O(m)。
2) 向路径移动过程。
for (i=0;i < m; i++){
for (j=0; j < n; j++){
计算路径节点的作用力；
}
}
复杂度分析 当前节点每作一次移动将会搜索邻居节点并计算所有邻居节点作用力。由于搜索的时间复杂度为O(m)，计算邻居节点的时间复杂度为O(n)，所以最终复杂度为O(m*n)。
3 实验仿真与性能分析 3.1 部署质量评价无线传感器网络的部署效果与性能评价指标对于分析该部署的可用性与有效性至关重要，通常评价无线传感器网络的覆盖质量有以下几种指标：覆盖率、重叠率、平均移动距离、部署时间。
1) 覆盖率。
覆盖率通常定义为所有传感器覆盖的总面积与目标区域总面积的比值，其中节点覆盖的总面积取集合概念中的并集。如果节点Si的覆盖区域为Ai，区域总面积为A，则覆盖率为：
| $P = \left( {\bigcup\limits_{i = 1, 2, \cdots, n} {{A_i}} } \right)/A$ | (3) |
其中节点覆盖总区域取每个节点区域的并集，显然区域的总覆盖率小于或等于1。
2) 重叠率。
重叠率是指区域中所有节点的有效覆盖面积的并集占所有节点覆盖面积之和的百分比，用来衡量节点覆盖范围的有效性，计算公式如式(4) 所示：
| $CE = \left( {\bigcup\limits_{i = 1, 2, \cdots, n} {{A_i}} } \right)/\left( {\sum\limits_{i = 1, 2, \cdots, n} {{A_i}} } \right)$ | (4) |
在有向节点覆盖问题中，网络的重叠率不可能为0，重叠率反映了节点覆盖的重叠程度，重叠率越高表示当前节点间的覆盖重叠越严重；反之亦然。
3) 平均移动距离。
平均移动距离是指所有节点移动的距离之和的平均值，用来衡量节点能量消耗大小，计算公式如式(5) 所示：
| $D = \left( {\sum\limits_{i = 1, 2, \cdots, n} {{d_i}} } \right)/n$ | (5) |
其中：di为节点i移动的总距离，n为节点数量。
4) 部署时间。
部署时间是指所有节点都达到稳定状态后所需要的时间，部署时间短所需要的能量少，反之亦然。
3.2 实验仿真本实验是基于The ONE仿真模拟器，实验中以节点为单位，其中仿真器中每个扇形表示不同的节点，实验中异构节点分为3组，具有3种不同的感知角度，分别为60°、90°、120°，感知半径相同，通信半径也相同。
本次实验在模拟曲线路径(8×160) 随机抛洒150个节点, 每隔一段时间记录节点移动轨迹及其对应的覆盖率和重叠率的变化情况，如图 7所示记录了节点移动轨迹，其中t为以节点运动开始为基准的时间增加值。
|
图 7 节点移动轨迹 Figure 7 Node moving trajectory |
从节点部署轨迹可以看出，该算法能达到精确部署的目的，节点质心在邻居节点合力的作用下进行移动和旋转，从而覆盖整条路径。
3.3 算法对比分析基于实验结果，本节将本文算法与文献[14]提出的VFPSA进行对比分析。两种算法在同等实验条件(如表 1所示，其中dip指仿真环境中界面中节点的坐标位置)下进行，比较两种算法下随着部署时间的变化网络的覆盖率、重叠率、节点行走总距离及部署时间。
|
表 1 实验参数设置 Table 1 Setting of experimental parameters |
文献[14]提出的基于虚拟力的精确部署算法(VFPSA)用于实现移动传感器网络的自动化精确部署。该算法研究的是基于全向传感器节点模型，能实现精确部署，但只考虑了节点的移动没考虑旋转；而本文研究的是针对有向异构节点，不仅考虑节点移动还同步考虑节点的旋转。
3.3.2 覆盖率对比两种算法在同等实验参数(如表 1所示)下，通过式(3) 得出不同时刻的覆盖率变化轨迹如图 8所示。
|
图 8 覆盖率比较 Figure 8 Coverage rate comparison |
从图 8可以看出，本文提出的算法在实现精确部署的同时，覆盖率比VFPSA提升4.4%，主要因为是节点通过旋转使覆盖更为合理。
3.3.3 重叠率对比两种算法在同等实验参数(如表 1所示)下，通过式(4) 得出不同时刻的重叠率，如图 9所示，其中，时间坐标0刻度以节点都移动到指定路径后为基准。
|
图 9 重叠率比较 Figure 9 Overlap rate comparison |
从图 9可以看出，本文算法在达到精确部署的同时节点的重叠率比VFPSA平均下降了3.4%，主要原因是节点通过旋转微调，使重叠进一步减少。
3.3.4 平均移动距离对比两种算法在同等实验参数(如表 1所示)下，通过式(5) 得出不同时刻的距离平均值。以时间为基准的网络节点行走总距离平均值的变化轨迹，如图 10所示。
|
图 10 行走距离比较 Figure 10 Moving distance comparison |
从图 10可以看出，部署第一阶段(节点未移动到路径中)两种算法行走的总距离相差不大，进入第二阶段(节点已经移动到路径中)后本文算法的行走距离要比对比算法的短，减少2.1%，主要原因是因为采用了旋转优先策略，在出现重叠的情况下，优先通过旋转解决重叠。由于移动相比旋转会消耗更多的能量，所以本算法最终要消耗的能量要少。
3.3.5 部署时间对比两种算法在同等实验参数(如表 1所示)下，通过随机抛洒不同的节点数量对比各自部署所需要的时间。以节点数量为基准的部署时间的变化轨迹，如图 11所示。
|
图 11 部署时间比较 Figure 11 Deploying time comparison |
从图 11可以看出，本文提出的算法在不同规模节点数量的情况下相比VFPSA需要更少的部署时间，平均减少4.3%。主要原因是在部署过程中，节点只通过移动方式进行部署会在虚拟力边界出现局部最小问题，节点来回震荡无法平衡稳定，DHPSA通过旋转优先，减少了只移动节点带来的不稳定问题。
4 结语针对有向异构传感器网络精确部署问题，本文提出了一种基于虚拟力实现节点移动和旋转的精确部署算法，通过信号量控制节点的移动和旋转，从而达到更高的覆盖率及更低的重叠率。实验仿真结果表明，该算法能够实现精确部署且与VFPSA相比在覆盖率、重叠率、移动距离及部署时间具有更优的性能，下一步工作将围绕三维空间有向异构传感器网络部署问题进行深入研究。
| [1] | CARDEI M, WU J. Energy-efficient coverage problems in wireless Ad-Hoc sensor networks[J]. Computer Communications, 2006, 29(4): 413-420. DOI:10.1016/j.comcom.2004.12.025 |
| [2] | THAI M T, WANG F, DU D H, et al. Coverage problems in wireless sensor networks:designs and analysis[J]. International Journal of Sensor Networks, 2008, 3(3): 191-200. DOI:10.1504/IJSNET.2008.018482 |
| [3] | CHOW K Y, LUI K S, LAM E Y. Wireless sensor networks scheduling for full angle coverage[J]. Multidimensional Systems & Signal Processing, 2009, 20(2): 101-119. |
| [4] | LI Y, GAO S. Designing k-coverage schedules in wireless sensor networks[J]. Journal of Combinatorial Optimization, 2008, 15(2): 127-146. DOI:10.1007/s10878-007-9072-6 |
| [5] | MA H D, LIU Y H. On coverage problems of directional sensor networks[C]//Proceedings of the 2005 International Conference on Mobile Ad-Hoc and Sensor Networks. Berlin:Spring, 2005:721-731. |
| [6] | 陶丹, 马华东, 刘亮. 基于虚拟势场的有向传感器网络覆盖增强算法[J]. 软件学报, 2007, 18(5): 1152-1163. (TAO D, MA H D, LIU L. A virtual potential field based coverage-enhancing algorithm for directional sensor networks[J]. Journal of Software, 2007, 18(5): 1152-1163.) |
| [7] | 谭励, 杨朝玉, 杨明华, 等. 改进的有向传感器网络多中心部署算法[J]. 计算机应用与研究, 2016, 33(12): 3797-3800. (TAN L, YANG C Y, YANG M H, et al. Covering research to directional sensor networks based on deployment of multi-center[J]. Application Research of Computers, 2016, 33(12): 3797-3800.) |
| [8] | 谭励, 陈玉程. 复杂区域的有向传感器网络覆盖优化算法[J]. 计算机工程, 2015, 41(4): 14-18. (TAN L, CHEN Y C. Coverage optimization algorithm for directional sensor network in complex area[J]. Computer Engineering, 2015, 41(4): 14-18.) |
| [9] | 刘志强, 沈廼桐, 毛强, 等. 无线传感器网络动态覆盖的CVT算法[J]. 传感器与微系统, 2015, 34(6): 115-118. (LIU Z Q, SHEN N T, MAO Q, et al. A dynamic coverage algorithm for wireless sensor networks based on CVT[J]. Transducer and Microsystem Technologies, 2015, 34(6): 115-118.) |
| [10] | 方芳, 陈世平. 无线传感器网络中多目标优化节点部署模型[J]. 计算机应用研究, 2015, 32(4): 1166-1168. (FANG F, CHEN S P. Node deployment model of multi-objective optimization in wireless sensor networks[J]. Application Research of Computers, 2015, 32(4): 1166-1168.) |
| [11] | 金仁成, 韦宁, 徐浩, 等. 基于虚拟力的无线传感器网络分簇部署策略[J]. 东北大学学报(自然科学版), 2014, 35(5): 640-644. (JIN R C, WEI N, XU H, et al. Clustering dynamic deployment strategy based on virtual force in wireless sensor networks[J]. Journal of Northeastern University (Natural Science), 2014, 35(5): 640-644.) |
| [12] | 王学军. 一种改进的无线传感器网络节点部署方案[J]. 计算机工程, 2012, 38(19): 82-84. (WANG X J. An improved node deployment scheme in wireless sensor network[J]. Computer Engineering, 2012, 38(19): 82-84. DOI:10.3778/j.issn.1002-8331.2012.19.020) |
| [13] | 黄月, 吴成东, 张云洲, 等. 基于移动节点的无线传感器网络覆盖优化[J]. 东北大学学报(自然科学版), 2012, 33(2): 165-168. (HUANG Y, WU C D, ZHANG Y Z, et al. Coverage optimization of wireless sensor networks based on mobile nodes[J]. Journal of Northeastern University (Natural Science), 2012, 33(2): 165-168.) |
| [14] | 杨明华, 曹元大, 谭励, 等. 一种移动传感器网络精确部署算法[J]. 北京理工大学学报, 2009, 29(1): 27-31. (YANG M H, CAO Y D, TAN L, et al. A precision deployment algorithm in mobile sensor network[J]. Transaction of Beijing Institute of Technology, 2009, 29(1): 27-31.) |
| [15] | ZOU Y, CHAKRABARTY K. Uncertainty-aware and coverage-oriented deployment for sensor networks[J]. Journal of Parallel & Distributed Computing, 2004, 64(7): 788-798. |