虚拟力的三维技术解析

定义与假设

在介绍算法之前，需要作如下的定义和假设。定义1一个n-维欧几里得空间［E，(*，*)］由n-维实向量空间Rn和内积(*，*):E×ER组成，简记为E。欧几里得空间是一个赋范空间，范数为＊=(*，*槡)。欧几里得空间也是一个度量空间，距离函数定义为d(x，y)=x－y。定义2将无线传感网中的节点定义成八元组［O(x，y，z)，Rs，RC，kmin，α，β，gridt］。式中O(x，y，z)为节点的中心在三维空间中的三维坐标，坐标采用直角坐标系(x，y，z)来表示。RS为节点的感知半径，即节点上搭载的传感器设备的感知距离，由传感器设备的硬件参数所决定。RC为节点的通信半径，即节点上搭载的通信设备的通信距离，由通信设备的硬件参数所决定。kmin为防止节点碰撞设置的最小安全距离，根据搭载节点移动的装置体积和移动速度的不同，在程序中设置不同的值。kb为节点平衡距离，根据不同的探测任务在程序中设置不同的值。α和β为虚拟力调节参数和虚拟力增长指数，它们共同作用用于调整虚拟力变化曲线。gridt用于保存节点的斥力网数组，它是由斥力原点TO(x，y，z)和斥力网Ti(x，y，z)，i=1，2，3，…，n两部分组成。本文中的算法存在以下假设:假设1搭载节点的设备相互碰撞会导致损毁，因此节点间必须保持一定安全距离;假设2探测目标存在实体，节点与探测目标也必须保持安全距离;假设3节点能够感知探测目标的方向和距离。

基于虚拟力的三维部署算法

将VFA由二维空间扩展至三维空间VFA是最经典的虚拟力算法之一，因此拟试图在VFA上进行改进。由于VFA是分布在二维平面上的，但在某些情况下高度参数至关重要，所以首先需要把VFA定义在三维空间中，实现三维空间中的VFA(VFA3D)。在VFA3D中，首先需要先将节点位置由二维数组O(x，y)转换为三维数组O(x，y，z)，增加高度z这一维。由此在这个三维空间中的虚拟力也由二维向量F(x，y)转换为三维向量F(x，y，z)。通过这些变换，可成功地把传统的二维平面中的圆覆盖问题，转变成了三维空间中的球覆盖问题。因此在下文中将VFA中的几种虚拟力在VFA3D中做重新定义。节点间作用力在VFA3D算法中没必要完全按照现实世界中的范德华力来计算。为更好地适应需求，可以范德华力进行一定程度的简化。为了便于分析和观察，把节点间虚拟力分别用二维图和三维图来体现，节点A对周围的邻居节点产生虚拟力，最小号的球(圆)一共有四个，它们分别是节点A、B、C、D，它们的半径为每个节点的感知半径RS，中号的球(圆)半径为节点的A的节点平衡距离kb，最大号的球(圆)半径为节点A的通信半径RC。节点D在节点A的通信距离之外，因此它们之间无虚拟力;节点B在节点A的通信半径之内且与节点A距离大于节点平衡聚距离，因此受到由节点B指向节点A的引力;节点C在节点A的通信半径之内且与节点A的距离小于节点平衡距离，因此节点C受到由节点A指向节点C的斥力，当节点C与节点A的距离更小时，他们之间的斥力会更大，直至当距离小于最小安全距离时，它们之间的斥力变为无穷大。中心引力在VFA3D中，节点除了受到节点间的虚拟力，在初始状态下，还应受到来自于目标区域中心的引力作用。这样即使节点初始位置未布撒在目标区域内，或者由于个别节点初始位置脱离了节点群，无法进行正常的相互通信，也能通过中心引力的作用将脱离群体的一个或者多个节点拉回到目标区域，从而使全部节点都能连接起来，对目标区域进行全面的覆盖。由于固定的中心引力有着难以克服的弊端，因此提出了自适应中心引力算法。障碍物斥力节点在目标区域动态部署中，很可能会遇到障碍物，节点与障碍物进行碰撞会造成严重的损失。因此在VFA3D算法中，加入了障碍物斥力，能够有效地避免节点与障碍物之间的碰撞。针对复杂目标的精确覆盖部署算法在VFA3D中成功地把VFA由二维空间拓展至三维空间，但是仅仅这样的话是远远不够的，因为增加了一维并不仅仅是增加了一个高度参量，它所带来的各种问题也应运而生。首先最明显的就是计算压力大幅度提升，三维球覆盖问题中的计算复杂度与二维覆盖问题根本不在一个数量级上。其次在二维空间中探测目标一般都为一个点或者一个平面区域，而在三维空间中探测目标可能是一个点，一个空间曲线，空间曲面，甚至是一个不规则的空间多面体。所以任务目标更为复杂多变，一成不变的算法很难应对各种情况。因此提出了VFA3D的改进算法ECA3D(ExactCoveringAlgorithmin3—Dspace)，并在ECA3D中提出了目标斥力网以及自适应中心引力的概念。目标斥力网由于在实际探测任务中，对区域进行探测时，探测目标往往都不是一个规则的形态，使用传统的虚拟力动态部署算法需要大量的节点对目标进行全覆盖以期望能够收集到想要的全部数据。但是当探测目标不为凸多面体，甚至仅仅是一条不规则曲线或者曲面时，大量的节点都被浪费掉了，因为使用VFA3D最终部署的形态总会是一个不规则的类球体。因此为了能达到自适应的调整部署形态，使节点群能够根据探测目标形态的不同均匀的覆盖到目标表面，ECA3D提出了加入一个探测目标斥力场，在中心引力和目标斥力的共同作用下期望能够使节点群平衡分布在探测目标表面，实现目标的均匀覆盖。

实验仿真

为了验证本文提出的算法是否能够达到预期效果，现设计了以下两组实验来进行验证分析。锥面覆盖实验在第一组试验中，首先分别采用三种算法对一空间锥面的上表面进行覆盖部署。三种算法分别是VFA3D算法，只添加目标斥力网的VFA3D算法和同时有目标斥力网以及自适应中心引力的ECA3D算法。然后通过对实验结果的部署图进行对比分析。最后就可以得出结论，在对复杂三维目标精确覆盖时，哪种算法可以取得更好的效果。若探测目标为锥面，现在需要探测锥面的外测的相关数据，图9是使用VFA算法简单的扩展到三维空间对目标进行覆盖部署，节点数为60。是只添加目标斥力网的VFA3D算法对目标进行覆盖部署，节点数为60。采用ECA3D算法对相同目标进行覆盖部署，节点数也是60。从三图中对比，很容易看出VFA3D算法在针对复杂目标时，效果远远不如ECA3D算法所达到的效果，因为VFA3D算法是从VFA算法改进而来，仅仅将VFA扩展至三维空间，它无法根据目标的不同自适应的调整节点群散开的形态。使用同一种形态应对复杂多变的情况，对探测目标的针对性较小，不能够根据探测目标的形态的不同而随之变化。从中加入透视效果以后，可以明显看出将VFA算法简单的扩展到三维空间中，节点群依然以一个类球的多面体的形态完成最终部署，大量的节点运动至锥面的下方。若是将中心引力点设置到高一些的位置上，锥面上方的节点也不会按照锥面的形态均匀展开，而是在锥面上多层覆盖。这样无论如何都会导致了大量的节点部署到了无用的位置，节点的利用率偏低。而图11中，本文提出的新型ECA3D算法能够根据探测目标的不同自适应的调整部署形态。现在探测目标为一个锥面，那么节点群在自适应中心引力和目标斥力网的作用下，能让节点群均匀的分散在被探测目标的表面，从而使每一个节点都发挥出最高的效率，节点的利用率远远高出VFA3D算法。中心引力未采用本文中的自适应中心引力算法，而是采用了传统的固定中心引力算法。对边两图明显可以看出采用固定中心引力点很容易由于选取中心引力点的不当造成覆盖上的漏洞，在凸多面体上表现得就是空洞，而在凹多面体上表现为堆积。由于自适应中心引力和斥力网合力的共同作用，节点群均匀且无漏洞的覆盖在锥面的表面上，和算法中受力分析预期的效果一致。

结束语

提出的ECA3D算法是一种针对三维空间中的复杂目标进行表面的包围覆盖的算法，以一定程度上提升算法复杂度为代价使算法能够更好地完成有针对性的探测任务。从仿真结果上来看，无论从覆盖率以及均匀度，ECA3D算法都远远超过了VFA3D算法，基本实现了预期的目标。ECA3D算法还有很大的提升空间，当探测目标表面过于复杂时表现欠佳，算法的复杂度也需要进一步的降低。

作者：李享 李轩涯 单位：中北大学电子与计算机科学技术学院 北京理工大学计算机学院