UWSNs中基于AUV移动的覆盖盲区修复算法

发布时间：2019-12-03 02:11

【摘要】：提出了一种水下无线传感器网络(UWSNs)中基于自主水下航行器(AUV)移动的覆盖算法。首先将要覆盖的区域网格化,然后以适当的策略遍历各个小格,从而实现盲区的覆盖修复。该算法克服了水下环境复杂未知、覆盖场景多样化而难以可靠覆盖的问题,同时使得AUV路径移动消耗最小化。文中还对3D场景和多AUVs协同等情况进行了分析和探讨。仿真实验表明,该算法在覆盖盲区规则、不规则或不连续等场景下均有较好的表现。
【图文】：

割草机,算法,遍历

角，根据ＡＵＶ的移动特点这需要付出大量额外能量才能完成。图１割草机算法遍历示意３本文算法３．１问题建模当前考虑２Ｄ场景下ＡＵＶ如何覆盖盲区（形状不确定，亦可能由若干不连续的小块组成）。假定ＡＵＶ的有效探测范围是以其自身为圆心、半径固定的圆形。ＡＵＶ在移动过程中连续地采集附近的兴趣数据。我们希望ＡＵＶ以尽可能小的路径代价完成覆盖任务，即移动距离尽可能短。本文不考虑定位问题，假定节点携带ＧＰＳ并能够准确实时获知自身坐标。ＡＵＶ能耗计算公式如下：Ｅｃ＝ｋ１Ｌ＋ｋ２ｒ∑（Ｍａｘ（θ－θ０，０）π）α（１）其中，Ｌ为ＡＵＶ移动路径长度，ｒ为ＡＵＶ感知半径，θ为ＡＵＶ每次转向的转角大小，θ０为每次转向的免费额度（即忽略小角度转角所消耗的能量），ｋ１、ｋ２和α为系数。３．２算法描述针对上述问题及模型，我们提出了下面的ＣＢＲＡ－ＡＭ（ＣｏｖｅｒａｇｅＢｌｉｎｄＲｅｓｔｏｒａｔｉｏｎＡｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＡＵＶＭｏｖｅ－ｍｅｎｔ）算法。如图２所示，首先将待探索的盲区水域网格化为若干个正六边形的小格。在２Ｄ平面上，正六边形是可紧凑拼接的最多边数的正多边形。边数更多意味着每个小格具有更多的邻居小格，这对本算法有利。如图３所示，设定每个正六边形的边长等于ＡＵＶ的覆盖半径（此时，，每个小格的大小刚好等于ＡＵＶ覆盖圆的内接正六边形），这样，当ＡＵＶ移至某个正六边形小格的中心时，即可完成对该小格的覆盖。当ＡＵＶ遍历所有的小格质心时，即可完成对盲区的覆盖。为了最小化ＡＵＶ的路

网格化,盲区

：Ｅｃ＝ｋ１Ｌ＋ｋ２ｒ∑（Ｍａｘ（θ－θ０，０）π）α（１）其中，Ｌ为ＡＵＶ移动路径长度，ｒ为ＡＵＶ感知半径，θ为ＡＵＶ每次转向的转角大小，θ０为每次转向的免费额度（即忽略小角度转角所消耗的能量），ｋ１、ｋ２和α为系数。３．２算法描述针对上述问题及模型，我们提出了下面的ＣＢＲＡ－ＡＭ（ＣｏｖｅｒａｇｅＢｌｉｎｄＲｅｓｔｏｒａｔｉｏｎＡｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＡＵＶＭｏｖｅ－ｍｅｎｔ）算法。如图２所示，首先将待探索的盲区水域网格化为若干个正六边形的小格。在２Ｄ平面上，正六边形是可紧凑拼接的最多边数的正多边形。边数更多意味着每个小格具有更多的邻居小格，这对本算法有利。如图３所示，设定每个正六边形的边长等于ＡＵＶ的覆盖半径（此时，每个小格的大小刚好等于ＡＵＶ覆盖圆的内接正六边形），这样，当ＡＵＶ移至某个正六边形小格的中心时，即可完成对该小格的覆盖。当ＡＵＶ遍历所有的小格质心时，即可完成对盲区的覆盖。为了最小化ＡＵＶ的路径消耗，本文设计了一种算法来尝试求得该问题的近似解。图２盲区网格化划分图３ＡＵＶ覆盖范围内接正六边形受到上文提到的割草机算法的启发，所设计的算法的整体思路为：ＡＵＶ尽可能贴着已经覆盖的区域（或不需要覆盖的区域）进行移动，这样有利于缩短移动路径、提高覆盖效率和减少能量消耗。假定ＡＵＶ当前位于某个小格，其遵循如下规则来决定下一步的移动位置，具体算法如下：Ｓｔｅｐ１ＡＵＶ检查自身所在小格周围６个邻居格的状态，选取未覆盖过的小格作为候选格。Ｓｔｅｐ２检查每个候选

【参考文献】