黄 帅，程良伦

(广东工业大学自动化学院，广州510006)

随着监测环境的日趋复杂多变，由传统传感器网络所获取的简单数据愈加不能满足人们对环境监测的全面需求，迫切需要将数据量大、内容丰富的图像、视频等媒体引入到以传感器网络为基础的环境监测活动中来，实现细粒度，精准信息的环境监测[1]。针对这种需求，作为传感器网络高级形式的有向传感器网络应运而生，它主要包括视频传感器网络和图像传感器网络。有向传感器网络的性能主要通过在监测区域内部署的传感器节点的覆盖率来体现[2]，因此优化有向传感器网络的覆盖对于合理分配网络的空间资源，更好地完成环境感知、信息获取任务以及提高网络的生存能力都具有重要的意义。但是由于有向传感器网络中传感器节点受视场限制，不能和传统传感器网络中的节点一样采用全向感知模型，因此有向传感器网络的覆盖问题相对于传统的传感器网络的要复杂许多。

目前，国内外已有很多学者[3－7，12]针对有向传感器网络的覆盖增强问题作了深入的研究。Ma等人在文献[3]中提出了一种2D感知模型并研究了有向传感器网络覆盖完整性以及通信连通性问题。在此基础上，文献[4]进一步提出了一种基于图论和计算几何的集中式覆盖增强算法，但是由于未能充分考虑到有向传感器节点局部位置及传感方向信息，该算法对有向传感器网络覆盖增强的能力相对有限。文献[5]设计了一种方向可调感知模型，并以此为基础提出了一种基于虚拟势场的有向传感器网络覆盖增强算法，巧妙的引入“质心”概念，将有向传感器网络的覆盖增强问题转化为质心均匀分布问题，以质心点作圆周运动代替节点传感方向的转动，达到消除网络中感知重叠区和盲区，增强网络覆盖的目的。文献[6]提出了一种基于虚拟势场的路径覆盖增强算法，将要解决的问题转化为质心点－运动轨迹点，质心点－质心点之间的虚拟力作用情况，以较小的代价获得了视频传感器网络对路径的充分覆盖，但是存在一个问题:当轨迹点对传感器节点的引力和其它传感器节点对该传感器节点的斥力合力为零时，此时如果该传感器节点和周围传感器节点存在大量共同的轨迹覆盖点，则该传感器节点并没有发挥轨迹点的有效覆盖功能，网络会陷入局部最小情况。文献[7]针对文献[6]存在的问题提出了一种基于改进势场的有向传感器网络路径覆盖增强算法，通过将相邻传感器节点对路径轨迹点的共同覆盖率引入到斥力计算中，有效引导节点的主感知方向调整，从而达到路径的高效覆盖。

传统基于虚拟力的覆盖增强算法只判断调整方向，节点的调整量为固定值，并且没有解决整个网络进入稳定状态后的冗余覆盖问题。本文在设计出方向可调感知模型后，提出一种基于虚拟力的有向传感器网络低冗余覆盖增强算法，建立虚拟力与角度调整量之间的关系模型，根据虚拟力的大小改变节点的角度调整量;当虚拟力小于某个阈值后，说明节点此刻进入了稳定状态，计算节点覆盖子集的集合，如果存在除了此节点以外的覆盖子集，则通知其中一个覆盖子集中包含的节点停止调整，同时此节点进入休眠状态。最后通过仿真实验证明算法的有效性，提高了有向传感器网络的调整效率，并且在保证覆盖率的前提下很好的解决了网络中的覆盖冗余问题。

1 有向传感器网络冗余覆盖增强问题

1．1 有向传感器节点的方向可调感知模型和覆盖子集

如图1所示，有向传感器节点的方向可调感知模型采用五元组 ＜P，R，V(t)，α，β＞来表示。其中P(x，y)表示节点的位置坐标;R表示节点的有效感知半径;V(t)=(Vx(t)，Vy(t))为节点在时刻t的感知方向;2α表示节点的有效感知角度;β表示节点感知方向的角度调整量。

图1 有向传感器节点的覆盖模型

在增强过程中，网络中的每个节点都明确自身的覆盖范围，而它所覆盖的范围也可能由网络中的其它几个邻居节点所覆盖。

定义1定义集合Coi(v)为有向传感器节点v的一个覆盖子集，其中UV'∈Coi(v)可以覆盖有向传感器节点v的覆盖区域。

定义2定义Co(v)为覆盖节点v覆盖区域的所有覆盖子集的集合。

为了计算Co(v)，需要定义4个点(三个定点以及重心)来标识节点v的覆盖区域，如图1(a)所示。若Coi(v)∈Co(v)覆盖节点v所覆盖的区域成立，当且仅当满足以下条件:

(1)∀v'∈Coi(v)，v'覆盖点 d 以及{a，b，c}中至少一个点。

(2)Coi(v)可以覆盖 a、b、c、d 四个点。

1．2 有向传感器网络低冗余覆盖增强问题的分析

在做本文的研究之前，做出以下假设:

(1)有向传感器网络中部署的所有节点均同构，即所有节点的感知半径、传感夹角等参数都一样;

(2)在进行覆盖增强的调整过程中，所有节点位置不变，但其传感方向可调;

(3)有向传感器网络中各节点均明确其自身位置以及传感方向，并能对自身的传感方向进行调节，但是此调节仅限制于围绕固定点做圆周运动。

(4)有向传感器网络中节点的受力点为其方向可调感知模型的质心。

如图1(b)所示，节点 v的覆盖区域由 a、b、c、d四个点表示，可以找到满足条件的覆盖子集有AG={v2，v1}，BG={v3，v1}，CG={v1，v5}。根据前面提到的方法，节点v的覆盖子集的集合为:

当某个节点进入稳定状态后，计算此节点的覆盖子集的集合，如果存在除了此节点以外的覆盖子集，则通知其中一个覆盖子集中包含的节点停止调整，此节点进入休眠状态。

设Ai(t)表示节点vi在传感向量为V(t)时的感知面积，Ai(t)∪Aj(t)表示节点vi和节点vj的感知面积进行并运算后得到的总面积。当网络中节点的传感向量分别为(V1(t)，V2(t)，V3(t)，…，VN(t))时，有向传感器网络的覆盖率表示如下[5]:

其中，A表示监测区域的面积。

在一个监测区域内分布了N个结构相同的有向传感器节点，则区域覆盖增强算法可以看作一个求最优解的问题，即求解一组(V1(t)，V2(t)，V3(t)，…，VN(t))*，使得对于所有(V1(t)，V2(t)，V3(t)，…，VN(t))式(2)成立:

2 有向传感网络低冗余覆盖增强算法

2．1 虚拟力的建立以及合力的计算

虚拟势场(Potential Force)方法是解决传感器网络覆盖控制问题的典型方法之一[5]，许多关于传感器网络覆盖问题的文献[6－10]都采用了这种思想，假定传感器节点之间存在一种虚拟的斥力，而传感器节点与监测目标之间又存在一种虚拟的引力，通过这两种虚拟力的抗衡达到增强网络覆盖的目的，但是只是将虚拟力的合力方向做为调整节点感知方向的依据，每次调整的角度大小不变。调整角度值设定太小，时间步长转动较小，虽然调整准确度较高，但是推迟了整个网络稳定状态的到来;调整角度值设定太大，调整准确度降低，还有可能造成网络最终不能进入稳定状态。本文通过建立合力与调整角度大小之间的关系，动态改变节点感知方向的调整量，使整个网络能够更快的进入稳定状态。另外在实际应用中，考虑到成本问题，监测区域中所有的节点都具有移动能力是不现实的，而且也可能由于传感器节点位置的变化引起部分节点的失效，造成整个网络的拓扑结构发生变化。因此本文假定所有节点的调整仅限于围绕一点做旋转运动，且这一点为节点方向可调到感知模型的顶点。

(1)虚拟力的建立

经过前面的分析，利用虚拟视场解决有向传感器网络的区域覆盖问题可近似等价于质心点与质心点的虚拟斥力作用问题。有向传感器节点之间存在斥力，并且在2R范围内，节点之间的距离越近，斥力越大，反之越小。

相邻传感器节点vj对vi的虚拟斥力定义为:

俄罗斯国家杜马信息政策、信息技术和通信委员会副主任亚历山大·尤先科在人工智能论坛上指出，如今全世界都在竞相发展人工智能，在这个领域俄罗斯不能落后，俄罗斯有IT行业优势，国家对人工智能立法责无旁贷，同时要立法部门和政府部门协同，学术界及社会广泛支持。

其中，k为斥力常数;aij为单位向量，由节点vj的质心指向节点vi的质心;‖Yi－Yj‖为节点vj与节点vi质心之间的欧氏距离。

(2)合力的计算

定义3有向传感器网络中，当节点vj与节点vi质心之间的欧氏距离小于或等于节点感知半径的2倍时，则互为友邻节点。

假设节点vi的友邻节点的集合为Φi，则节点vi质心所受的合力为:Fi=∑j∈ΦiFij，vj∈Φi。由于规定有向传感器网络中的节点只能围绕其感知模型的顶点做旋转运动，因此节点感知方向的调整只受合力沿切线方向分量F'的影响，如图2所示。

图2 节点的质心点受力合力分析

2．2 调整角度的计算

从力学的角度讲，分量F'和传感器的质量以及节点做直线运动的加速度有关，但是由于节点只能做旋转，因此需要将直线加速度转化为角加速度。则有:

其中:a表示物体的直线加速度，R表示旋转半径，φ表示物体的角加速度，m为物体质量。由于调整角度的大小并不受m的影响，因此将式(4)简化为:

但在本文中，节点并不是一直在做旋转，而是每做一次旋转后计算分量F'以及调整角度的值再做旋转。因此式(5)中角加速度φ可以看作和调整角度有关联的一个量。

式(6)中α表示节点有效感知角度的一半;β表示节点感知方向的角度调整量。将式(5)与式(6)进行整合，得到:

其中，0≤β≤α。

2．3 区域覆盖增强算法描述

输入 节点vi及友邻节点的状态信息，包括:当前位置、最大感知半径、感知方向和最大感知角度，角度调整量初始化为0。

输出 节点vi的最终感知方向。

(1)初始化时间步长计数器t=0;

(2)计算节点vi的方向可调感知模型的质心坐标PVi(t);

(3)计算节点vi友邻节点集合Φi，X为集合Φi中包含的元素数目;

(4)while(1)

3 算法仿真及分析

通过在Matlab上进行一系列的仿真实验对本文提出的有向传感器网络低冗余覆盖算法进行验证。实验环境及参数取值见表1。

表1 实验环境及参数取值

按照表1所设定的实验参数进行实验，分别记录每个时间步长网络的覆盖率以及网络中处于激活状态的节点个数。图3为网络中活跃节点个数随时间变化曲线。图4显示了采用PFCEA算法与采用本文算法在初始覆盖率为65%，其它参数一样的情况下区域覆盖性能增强情况。从图3和图4可以看出，本文的算法和和PFCEA算法相比，最终的覆盖增强效果虽然差别不大，但是覆盖增强的效率却有明显的提高，由30个时间步长缩短为25个时间步长，提高了16．7个百分点，同时利用更少的节点达到了同样令人满意的覆盖增强效果。

图3 网络中活跃结点个数在覆盖增强过程中的变化曲线

图4 网络中活跃结点个数在覆盖增强过程中的变化曲线

图5显示了不同节点规模对FFLRCA算法覆盖增强效果的影响。可以看出，当R，2α等其它参数一定时，随着节点规模N的增大，FFLRCA算法对覆盖率的增强效果增加到一定程度后开始较少。例如N=150时，网络的初始覆盖率已经达到了81．94%，相邻传感器节点之间形成覆盖盲区的概率降低，FFLRCA算法的覆盖增强性能开始消弱。

图5 节点个数N对增强效果的影响，其它参数:R=60，α =45°

图6显示了不同节点最大感知角度2α对FFLRCA算法覆盖增强效果的影响。当节点最大感知角度越小，单个节点的覆盖区域越小，相邻节点之间形成重叠区域的可能性就越小，FFLRCA算法的效果就不显著，随着节点感知角度的增加，N=110，R=40 m，网络覆盖率最高可提升15．1%;随着节点感知角度的继续增加，FFLRCA算法带来的覆盖增强效果降低。

图6 节点最大感知角度2α对增强效果的影响，其它参数:R=40，N=110

4 结束语

本文主要研究有向传感器网络中的区域覆盖增强问题。在建立改进型的方向可调感知模型后，提出一种基于虚拟力的低冗余覆盖增强算法。通过引入“虚拟力”以及虚拟力和调整角度之间的关系模型，利用节点之间的斥力逐渐消除网络中的感知重叠区和盲区，最终实现节点的快速调整和区域的高效覆盖。本文通过一系列实验证明了FFLRCA算法的有效性，并详细的分析了节点规模、最大感知角度对FFLRCA算法增强效果和执行效率提高程度的影响。

[1]Rita Cucchiara．Multimedia Surveillance Systems[C]//Proc of the ACM VSSN2005，New York:ACM Press，2005:1 －10．

[2]Zou Y，Chakrabarty K．Sensor Deployment and Target Localization in Distributed Sensor Networks[J]．ACM Transactions on Embedded Computing Systems，2004，3(1):61 －91．

[3]Ma H D，Liu Y H．On Coverage Problems of Directional Sensor Networks[C]//LNCS 3794:Proc of the Int Conf on Mobile Ad-Hoc and Sensor Networks Berlin:Springer，2005:721 －731．

[4]Tao D，Ma H D，Liu L．Coverage-Enhancing Algorithm for Directional Sensor Networks[C]//Stojmenovic I，Cao JN，eds Proc of the 2nd Int’1 Conf on Mobile Ad-Hoc and Sensor Networks Berlin:Springer-Verlag，2006:256 －267．

[5]Khatib O．Real-Time Obstacle Avoidance for Manipulators and Mobile Robots Research[J]．The International Journal of Robotics Research，1986，5(1):90 －98．

[6]陶丹，马华东，刘亮．视频传感器网络中路径覆盖增强算法研究[J]．电子学报，2008，36(7):1291 －1296．

[7]肖甫，王汝传，叶晓国，等．基于改进势场的有向传感器网络路径覆盖增强算法[J]．计算机研究与发展，2009，46(12):2126－2133．

[8]李石坚，徐从富，吴朝晖，等．面向目标跟踪的传感器网络布局优化及保护策略[J]．电子学报，2006，34(1):71 －76．

[9]Zou Y，Chakrabarty K．Sensor Deployment and Target Localization in Distributed Sensor Networks[J]．ACM Trans on Embedded Computing Systems，2004，3(1):61 －91．

[10]陶丹，马华东，刘亮．基于虚拟势场的有向传感器网络覆盖增强算法[J]．软件学报，2007，18(5):1152 －1163．

[11]温俊，蒋杰，窦文华．公平的有向传感器网络方向优化和节点调度算法[J]．软件学报，2009，20(3):644 －659．

[12]Habib M Ammari，Sajal K Das．A Study of K-Coverage and Measures of Connectivity in 3D Wireless Sensor Networks[J]．IEEE Transactions on Computers，2010，59(2):243 －256．