基于粒子均衡的移动传感器网络覆盖控制研究
2016-12-13 来源：重庆大学自动化学院 作者：张洪德 石为人 杨磊 王楷
摘 要：现代仪器正在向着网络化和智能化方向发展，传感器网络则是具体体现之一，各个传感器测量的数据可以通过网络以单跳或多跳方式传送到控制节点，从而实现网络化的智能测量。传感器网络中各节点能否覆盖全区域，直接决定了测量结果是否为全样本覆盖集。本文在经典的虚拟力算法思想基础上，研究了基于粒子均衡的移动传感器网络覆盖控制性能，具体针对同构节点、异构节点、非规则区域等各种应用场合进行了分析和算法改进，利用仿真实验的方法验证了其性能。仿真实验证明，该算法对于同构节点和非规则区域均可以取得较好的覆盖效果和网络生命周期；对于异构网络则需要进行适当调整，将邻居区域的概念由同构节点网络中的两倍于感知范围扩展为最大的联合感知范围，使得节点在其邻居节点范围内能够维护最低限度的通信链路，就可以使其远离邻居节点，从达到预期的网络性能。同时研究了在实际应用中算法的鲁棒性，主要针对在部分节点丧失通信能力以及节点丧失移动能力时算法的性能，实验表明仍能表现出较好的网络覆盖度。
关键词：移动传感器网络；粒子均衡；感知范围；通信范围
１.引言
无线传感器网络作为现代仪器网络化和智能化的发展成果，体现出了可随机布设、自适应网络拓扑等诸多优点，特别是适合布设在危险地域、灾难区域或者生化泄露地域进行参数测量和收集，但是正因为其自组织特性，对于定位、跟踪、路由、数据融合和网络覆盖等方面提出了更高的挑战，网络覆盖问题则直接影响着测量应用的效果，只有实现了全区域的覆盖，才能实现全样本的测量。目前研究移动传感器节点覆盖的问题，可以分为两类：基于虚拟的物理施加力（即虚拟力）的方法以及基于计算几何的方法。基于计算几何［８９］的方法则是调整节点的位置，以构建均匀的泰森多边刑法图解或者狄洛尼三角剖分。基于虚拟力的方法［１ ０１ ３］将传感器节点建模为电子或分子，通过节点之间的虚拟力或势场来决定靠近或拉远。本文主要针对虚拟力方法进行研究和改进，验证在同构网络、异构网络和不规则区域等不同环境下的覆盖控制性能，并研究节点丧失通信能力或移动能力时的鲁棒性。
２.相关工作
Ｈｏｗａｒｄ Ａ 等人提出一种基于势场的方法在目标区域中布设传感器节点，控制力定义为势场的负梯度，这种方法可以实现节点的均匀分布。ＶＦＡ（ｖｉｒｔｕａｌ ｆｏｒｃｅｓａｌｇｏｒｉｔｈｍ）的原理和势场的方法相类似，通过考虑相邻节点和障碍物施加的吸引力和排斥力来增加传感器网络的覆盖度。ＥＶＦＡ（ｅｘｐｏｎｅｎｔｉａｌ ｖｉｒｔｕａｌ ｆｏｒｃｅｓ ａｌｇｏｒｉｔｈｍ）算法在某些方面对ＶＦＡ 算法进行了改进，提供了一种指数虚拟力模型，确保在较大的通信距离范围内移动传感器网络能够迅速的达到稳定状态。ＣＰＶＦ （ｃｏｎｎｅｃｔｉｖｉｔｙ
ｐｒｅｓｅｒｖｅｄ ｖｉｒｔｕａｌ ｆｏｒｃｅｓ）算法保持连通的虚拟力算法充分考虑了网络的连通性能，具体思路是使得非连通节点朝向基站移动以建立连通链路，但是该算法没有解决大通信距离时的缺点。对ＶＦＡ 算法进行了优化，目的是解决传统虚拟力算法中的网络连通性和节点拥塞问题，以实现理想的节点布设，通信距离小时使用定向力来确保连续的网络连通，通信距离大时，使用节点与其距离远的节点之间的距离力判决来防止节点拥塞，仿真结果表明在不同的通信距离和感知距离比的情况下都具有很好的性能，而且在覆盖度、节点均匀度和连通度上都比以前的ＶＦＡ 具有更好的表现。
目前，已有研究主要是针对虚拟力算法的连通性能、覆盖度和避障性能进行了针对性研究，而算法在不同环境下，包括同构网络、异构网络和不规则区域，以及对于节点发生异常情况下的算法鲁棒性研究相对较少。
３.基于粒子均衡的覆盖控制算法
３.１ＥＰ 覆盖控制算法原理
粒子均衡（ｅｑｕｉｌｉｂｒｉｕｍ ｏｆ ｐａｒｔｉｃｌｅ，ＥＰ）的目标是使得分子电子和核子间的排斥力最小，每一个粒子都以分布式的方式来决定自己的最低能量点，其最终与其他粒子的距离也几乎相同。移动传感器网络的布设问题，与粒子问题类似。如果传感器位置距离相互太近，则覆盖度不高；相反地，如果传感器相互之间的位置太远，则区域覆盖不会重叠，可能会引起网络的分区。这两种情况和粒子的核子间排斥力和吸引力相类似。因此，可以使用和粒子均衡类似的处理方法，来计算以实现覆盖感知为目的的节点间最优距离。
本节假定移动传感器网络中所有节点都是相互对等的，粒子均衡覆盖控制算法是一种分布式自布设算法，该算法基于点对点模式。算法初始阶段，在某个给定区域内，通常是一个矩形区域，随机布设特定数量的节点。感知范围和通信范围假定已知。每个节点都可以感知或者检测其感知范围内的事件，在节点通信范围内的任意一对节点可以相互通信。节点间的通信主要用于邻居发现、获取邻居节点的位置、以及发送或者转发感知数据。邻居节点定义为在该节点通信范围内的节点。ＥＰ 覆盖控制布式算法在每一个节点都需要执行，一共包括４ 个阶段。
１ ）初始化阶段：该阶段主要是确定Ｒｃ、Ｒｓ 和节点初始位置ｐ０。通信范围Ｒｃ 和感知范围Ｒｓ 可认为是给定的。节点的初始位置用包含横坐标和纵坐标的矢量来标识，节点初始位置服从随机分布。需要指出的是，节点位置的维数不一定限制为在二维平面内。只要节点计算能力能够在规定时间内执行完节点布设算法，即计算能力和算法复杂度相适应，就可以适当提高到更高的维数。具体的实现方式可以通过增加位置矢量的维数、节点之间距离计算公式以及每个节点虚拟力计算公式的维数来达成。在ＥＰ 算法中，使用ｕ 来表示对区域密度的大致估计，称之为预期密度。计算公式为：
式中：Ｎ 为节点个数，Ｒｃ 为每个节点的通信距离，Ａ 为目标区域的面积。因此，预期密度就是节点均匀分布的时候覆盖整个目标区域所需节点的平均个数。节点的初始密度Ｄ０ 等于在其通信范围内的节点个数。在确定节点位置的时候会用到节点初始密度。
２）粒子力计算：利用虚拟力的概念来定义网络布设期间的节点移动。该虚拟力不仅取决于节点间的距离，还与节点当前的本地密度有关。本地密度越大，对应的就越大；本地密度越小，则对应的力就越小。和物理学中粒子间的库仑定律类似，节点间距离越近，产生的力越大；节点间距离越远，则产生的力越小。每一个粒子与其邻居之间保持一个特定距离，以达到吸引力和排斥力的均衡，称之为均衡点。在均衡点位置处，分子的电能和原子间的排斥力处于一个平衡状态，所有的能耗处于最小状态。施加在每一个粒子上的力仅取决于粒子之间的距离和其电量大小。对于节点ｉ 而言，在第ｎ 步骤受来自于邻居节点ｊ 所施加的虚拟力为：
每一个节点对当前节点位置上所施加的所有的虚拟力进行累加后，下一步判决其移动策略。该判决为本地判决，主要考虑本地态势，包括邻居节点的位置以及可能存在的死亡节点等。本地态势的信息都是由来自于通信范围内的节点所搜集的信息，并用于计算每一个节点的本地密度。每一个节点的移动策略都由其邻居节点联合施加的虚拟力所决定的。
３）振荡检查：节点何时应该停止运动是节点布设中一个重要的研究问题。在ＥＰ 算法中引入两种停止准则。如果某个节点来回几乎在同一个位置上运动多次，可认为该节点出于振荡状态。因此可以通过检查节点的历史运动轨迹，即可判断各个节点是否出于振荡状态。如果振荡次数Ｏｃｏｕｎｔ超过了振荡门限Ｏｌｉｍ，则停止节点移动，将节点放置于振荡点的质心位置。
４）稳态检查：如果节点移动在某个时间间隔Ｓｔａｂｉｌｉｔｙ（Ｓｌｉｍ）内小于门限ｔｈｒｅｓｈｏｌｄ２ ，则认为该节点达到稳态，无需再移动。对于那些由于能量耗尽或者移动模块损坏无法移动的静止节点而言，同样适用该停止准则。
３.２ＥＰ 覆盖控制算法的鲁棒性分析
从算法的总体结构上，ＥＰ 算法和虚拟力的基本思想是一致的，下面依据图１ 讨论节点Ａ 的下一步运动策略。节点Ｂ、Ｃ、Ｄ、Ｅ 都是在其通信范围内的邻居节点。用式（１ ）可以计算得到Ｂ、Ｃ、Ｄ、Ｅ ４ 个节点的虚拟力，即：ｆＢ、ｆＣ 、ｆＤ、ｆＥ。施加在节点Ａ 上的总的虚拟力：Ｆ ＝ｆＢ ＋ｆＣ＋ｆＤ ＋ｆＥ。该加法包括幅度和方向，属于矢量相加运算。
节点Ａ 根据计算结果移动到新的位置Ａ′。节点Ｃ 在所有的邻居节点中距离Ａ 最近，因此他们的间距应该增加。如果传感器节点位于远程区域或敌方境内，一些节点在布设期间以及布设结束后会受到一些自然或人为的破坏，可能会导致某些节点丧失移动性，而部分节点通信功能受到破坏。因此，需要研究具有鲁棒特性的布设算法以适应这些复杂情况。ＥＰ 算法具备上述的鲁棒特性。首先，当某个传感器节点丧失移动性时，节点不能再移动，可以看做是提前停止移动的节点。但是该节点仍然可以在传感器网络中充当静止节点使用。其可以移动的邻居节点仍然能够通过移动来改善整个网络的拓扑结构以优化网络性能。其次，当传感器节点丧失通信能力时，该节点在传感器网络中已经失去作用，因为其收集的数据无法进行传输。在这种情况下，通常邻居节点会移动到该节点的位置，代替原来的节点对因节点通信功能丧失而产生的新的无法覆盖的区域进行重新覆盖。该场景如图２ 所示。
在该图中，各个节点位置和前面的例子相同。假设节点Ｃ 在随机布设期间遭到破坏，其通信单元不能正常工作。此时，包括节点Ａ 在内的邻居节点在计算下一步运动时仍然采用原来的方法。也就是说，该异常的发生不影响邻居节点下一步运动判决的方法。但是，在具体计算公式中，上一个例子最大的虚拟力ｆＣ 此时会被排除在外，即：Ｆ ＝ｆＢ ＋ｆＤ ＋ｆＥ，节点Ａ 的下一个位置变为Ａ′。此时由于被破坏的节点Ｃ 而导致的无法覆盖的区域会被节点Ａ 重新覆盖。
由于每一个节点的移动只受邻居节点的当前状态所影响，因此每一个节点对环境的改变具有一定的适应性（比如节点失效、变化的区域形状等），可以自治的方式改变其位置，实现对目标区域的最大化覆盖和节点的均匀分布。
４..ＥＰ 覆盖控制算法的适应性分析和优化
４.１同构网络
在同构网络仿真中，选取２４ 个随机布设节点，区域为１ ０ ×１ ０ 的矩形，算法均基于ＭＡＴＬＡＢ 实现，假定感知距离Ｒｓ ＝２，通信距离Ｒｃ ＝４。
在图３ 中，给出了在算法运行之前的随机布设节点的位置和初始覆盖区域。圆点表示节点的位置，小圆和大圆分别表示了单个节点的感知范围和通信范围。可以看出，即便是在目标区域内有足够数量的节点，但是仍然有部分区域不能被随机布设的节点所覆盖。在这个示例中，网络不是全连通的，因此实际的覆盖比仅仅通过增加非连通的覆盖区域还要小。不管布设节点的个数是多少，在随机布设的情况下，都会有类似的情况发生。在上图中，覆盖度的计算值大于８２％，但是由于实际的网络被分为两部分，因此实际的覆盖度量值低于５５％。这种情况下，就需要进行拓扑的优化，以改善传感器网络的覆盖性能。
运行ＥＰ 覆盖控制算法后的节点位置和覆盖情况如图４ 所示。目标区域在算法运行后被完全覆盖。本次仿真运行时的参数值为：ｓｔａｂｌｅ ｓｔａｔｕｓ ｌｉｍｉｔ （Ｓｌｉｍ）＝５，ｏｓｃｉｌｌａｔｉｏｎ ｌｉｍｉｔ（Ｏｌｉｍ）＝５，ｔｈｒｅｓｈｏｌｄ（ｅ）ｆｏｒ ｏｓｃｉｌｌａｔｉｏｎ ａｎｄ ｓｔａｂｌｅ ｓｔａｔｕｓ ＝０．１ ５０ ６。此时网络是全连通的，而且目标区域完全覆盖，从图中看出，节点的空间分布比初始随机分布时更加均匀。
图４ 同时给出了ＥＰ 覆盖控制算法执行后，每一个节点从初始位置移动到最终位置的图。空心圆表示初始位置，实心圆表示最终位置。相对初始分布而言，每个节点的平均移动距离为４．０６５ ２，移动距离的标准方差为１ ．６６０ １ 。节点的平均移动距离越小，相应的因移动而消耗的能量也越小。而且，移动距离的标准方差越小，每个节点剩余的能量变化就不显著，从而具有全覆盖特性的网络生命周期就越长。
４.２异构网络
前面的仿真中，所有节点都假定具有相同能力，即均为同构节点。但是在实际中，很多情况下，出于经济原因等各种因素的考虑，往往会使用不同类型的节点。为此，本节研究异构传感器布设问题。为了既能描述问题又能简化问题，考虑两种类型的异构节点构建的传感器网络。为了适应异构传感器节点，ＥＰ 覆盖控制算法需要进行调整。如果某个节点具有更大的感知范围，则不需要很多的邻居节点来达到目标区域的覆盖要求。一个节点的虚拟力可以随着感知范围的增大而按比例提高。第ｎ步时第ｊ个节点（第ｉ 个节点的邻居节点）作用于第ｉ 个节点的虚拟力计算公式为：
式中：Ｒｉ
ｓ 表示第ｉ 个节点的感知范围，ｐｉ
ｎ 表示第ｉ 个节点
在第ｎ 步时的位置，Ｄｉ
ｎ 表示第ｉ 个节点在第ｎ 步时的本地密度。
和同构节点的式（１ ）比较，感知范围的和代替了式（１ ）中的通信范围。其目的是，只要能够在其邻居节点范围内维护最低限度的通信链路，就可以使其远离邻居节点。在异构节点的网络中，邻居区域的概念由同构节点网络中的两倍于感知范围扩展为最大的联合感知范围。仿真中仍然用了２４ 个节点，类型１ 传感器节点感知范围是２，类型２ 的节点感知范围为３。分别用带阴影和不带阴影的圆来表示两种类型节点的感知范围。两种类型的节点都假定具有相同的通信范围４。２４ 个节点中有１ ６ 个属于类型１ ，占全部节点的２ ／３；类型２ 只有８ 个，占总数１ ／３。图５ 为该仿真场景节点初始拓扑结构。
异构节点场景中节点位置和同构节点的场景是相同的，也就是说拓扑结构相同。由于使用了感知范围更大的传感器节点，初始网络覆盖度为９０．０２％，比同构节点场景的覆盖度要大的多。尽管网络初始覆盖度增加了，但是网络仍然是分割的，这就意味着目标区域中上部区域的传感器节点与下部区域的传感器节点之间存在一些无法通信的链路。因此，需要改善传感器节点的拓扑结构。运行修改后的ＥＰ 覆盖控制算法，可以得到如图６ 所示的拓扑图和节点位置变化情况。网络覆盖度达到１ ００％覆盖，均匀度也得以改善。
４.３非规则目标区域
在实际应用中，目标区域的形状不一定是矩形，可能是复杂的非规则形状区域。为了验证ＥＰ 覆盖控制算法处理不同形状目标区域的能力，将目标区域设置为的形状为两角镂空的矩形。
本次仿真的两角镂空的矩形目标区域以及节点的初始分布拓扑如图７ 所示。具体而言，目标区域是由笛卡尔坐标系的点所组成的一个内部区域，坐标点为：［（０，１ ０），（５，１ ０），（５，６），（１ ０，６），（１ ０，０），（２，０），（２，２），（０，２），（０，１ ０）］。一共有２４ 个节点，节点的感知范围是２，通信范围是４，初始状态时节点在目标区域内随机分布，所得到的覆盖度为８７．１ ２％。但随机布设得到的网络是分割的。运行ＥＰ 覆盖控制算法，可以得到如图８ 所示的改进的网络拓扑结构和节点位置变化情况。网络覆盖度达到１ ００％覆盖，均匀度也得以改善。
５.ＥＰ 覆盖控制算法性能的实验验证
实验测试平台和节点原型如图９ 所示，实验环境为空旷平地，目标区域为８ ｍ ×８ ｍ。为简化起见，传感器移动节点之间的通信采用洪范算法。受限于节点个数和移动速度的限制，放置２４ 个移动节点，移动速度设置为０．２ ｍ／ｓ，停顿时间设置为１ ｓ。
５.１节点丧失通信能力
如果节点丧失通信能力，节点就不再具有利用价值。因为即便节点仍然具有感知、计算和移动能力，但已经无法向用户报告数据，所以节点已没有任何用处。为了研究由于通信能力丧失而导致的节点丢失对网络布设过程产生什么样的影响，假定在２４ 个传感器节点组成的网络中有３ 个节点丧失通信能力。该仿真中节点的初始拓扑结构如图１ ０ 所示。由于丢失了３ 个节点，随机布设的传感器网络的初始覆盖度从图３ 所示的８２．８８％减少到７１ ．６２％。随机布设的传感器网络仍然是分割的。丧失通信能力节点标号为３、１ ６ 和２２。丧失通信能力的节点覆盖区域用无颜色填充的圆来表示，正常通信的节点的覆盖区域则用深色阴影的圆来表示。
ＥＰ 覆盖控制算法运行后的节点拓扑和节点位置变化情况如图１ １ 所示。可见，ＥＰ 算法执行后，网络是全连通的，而且网络覆盖度和均匀度也得以改善。
５.２节点丧失移动能力
如果节点丧失了移动能力，节点仍然可以在目标区域内作为网络的一个节点实现网络既定性能。为了研究部分节点丧失移动能力后，对于网络布设算法的影响，试验中假定２４ 个节点中的标号为３、１ ６、２２ 的３ 个节点丧失了移动能力。初始节点拓扑结构如图１ ２ 所示。随机布设的网络的拓扑结构并没有因为节点丧失移动能力而发生改变。随机布设得到的传感器网络是分割的。图中可以看出静止节点和移动节点之间有通信链路可以互通。
图１ ３ 给出了在３ 个节点丧失移动能力后，ＥＰ 覆盖控制算法执行所得到的网络拓扑结构和节点位置变化情况。可见，算法执行后所有的节点都可以通过单跳或者多跳的方式互通，而且网络覆盖度和均匀度也均得以改善。
６.结论
通过仿真分析和实验验证，基于粒子均衡的ＥＰ 覆盖控制算法在同构节点和非规则区域的应用场合能够取得很好的覆盖性能和网络生命周期，在异构网络中通过适当改进也可以获得预期性能。同时，ＥＰ 覆盖控制算法也具有一定的鲁棒性，当部分节点丧失通信能力或者部分节点丧失移动能力时算法仍能表现出良好的覆盖性能。因此，该算法对于实现网络化和智能化的仪器测量能够提供很好的网络覆盖保证，确保全样本测量。
投稿箱：
如果您有机床行业、企业相关新闻稿件发表，或进行资讯合作，欢迎联系本网编辑部， 邮箱：skjcsc@vip.sina.com
如果您有机床行业、企业相关新闻稿件发表，或进行资讯合作，欢迎联系本网编辑部， 邮箱：skjcsc@vip.sina.com
更多相关信息
- target=_blank> 毂帽鳍的节能机理分析
- target=_blank> 航空发动机内部损伤智能诊断系统研制
- target=_blank>世界级冲压车间技术
- target=_blank>发动机火花塞的使用与维护
- target=_blank> 280机车柴油机曲轴在船舶领域运用可靠性研究
新闻资讯
| 更多
- target=_blank>MB2120B型数控内圆磨床电主轴变频器的改造
- target=_blank>【雷尼绍】RESOLUTE™与MELSERVO-J5强强组合，实现更快速、精确、可靠的运动控制
- target=_blank>NSK开发低摩擦轮毂单元轴承 可增加电动汽车续航里程
- target=_blank>T68卧式镗床进给系统的数字化改造
- target=_blank>AGV+协作机器人在零件数控机床加工上下料中的应用
- target=_blank>2020年7月高端装备制造业、工业机器人，行业运行简述
- target=_blank>浅谈线切割机床中走丝与慢走丝
- target=_blank>ANCA整体PCD铣刀 —— 提高生产效率带来新的发展机遇
- target=_blank>伊斯卡，不止专注于金属加工
- target=_blank>EMAG成功收购Scherer Feinbau（舍勒公司），极大扩展了公司产品范围以及客户群体
