灾区无人机救援系统中基于凸包理论的无人机部署算法_魏妍.pdf

第 卷 第 期 年 月弹 箭 与 制 导 学 报 ，.：收稿日期：基金项目：河南省高等学校重点科研资助项目（）资助作者简介：魏妍（），女，河南驻马店人，讲师，硕士，研究方向：计算机信息与智能信息处理。灾区无人机救援系统中基于凸包理论的无人机部署算法魏 妍，魏长宝（驻马店幼儿师范高等专科学校计算机系，河南 驻马店；河南大学教育科学学院，河南 开封；黄淮学院信息工程学院，河南 驻马店）摘 要：因机动灵活、操作简单，无人机（，）被广泛应用于应急救援系统。为此，提出基于测距的分布式 部署算法（）。与传统的部署算法不同，算法不再假设地面终端用户（，）的位置信息是已知信息。算法只需通过测量接收信号值，估计 与 间距离，然后再利用这些距离数据，并结合凸包理论，部署，使 与 间距离最小。同时，算法为分布式算法，每个 可独立运行，易部署。仿真结果表明，算法能够降低 与 间距离，提高 端的信息容量。关键词：无人机；测距；接收信号强度；凸包；部署中图分类号：.文献标志码：，（，；，；，）：（），（），：；引言无人机（）已在电讯、救援等应用领域广泛使用。在基于 的灾区救援中，为灾区内的地面终端用户（）提供通信服务。如何为这些 提供实时、高效的通信服务是此类应用的关键。的部署对通信服务质量有直接影响。文献分析了 的部署问题。其中文献只讨论了单 部署问题，而文献 讨论了多 部署场景。例如，文献提出了基于分布式算法部署，进而保证局部优化覆盖。文献提出了基于粒子群优化的 部署算法，以最小化 数。此外，为了最小化 与 间的平均距离，文献 提 出 了 优 化 覆 盖 质 量 的 部 署 算 法（）。然而，上述研究均假设 的位置信息是已知信息。但在真实的应用环境中，获取所有 的位置信息是非常困难的。为此，针对灾区救援场景，提出基于测距的分布式 部署算法（）。算法不再假设 的位置为已知信息，而是先通过接收信号强度估计 与 间的距离（测距）。再基于测距信息，并结合凸包理论，部署，使 与 间平均距离最小，进而 端获取较大的信息容量。第 期魏妍等：灾区无人机救援系统中基于凸包理论的无人机部署算法 系统模型及测距 系统模型考虑如图 所示的网络系统，其有 个地面终端用户，它们形成 集 ，。假定 是静态的，但其位置未知。令 表示第 个 在水平面上（地面）的二维位置，且 ，。网络还部署了 个，它们形成 集，。令 表示第 个 在空中的高度。令 表示第 个 在水平面上的位置坐标，即 （，），其中 ，。图 系统模型假定 与 间通信为视距链路。与 间的信道增益服从自由空间路径衰减模型。衰减强弱与两者间距离密切相关。第 个 与第 个 间距离可表示为：（）（）（）式中（，）表示第 个 的位置坐标。此外，令 表示第 个 离 个 距离中最短的距离：（）测距尽管 位置为未知信息，但是 通过接收信号强度（，）值，估计离其周围 的距离。具体而言，每个 知晓离集 内所有用户的距离。，（）式中：为部署的第 个；表示由离 最近的 所组成的 集；为 集中的第 个。依据式（）可知，对于 内任意一个 而言，是离它最近的。采用扩展 滤波估计 与 间距离。令 表示 从第 个 所接收的信号强度值，其表达式为：（）式中：表示传输功率；表示由环境决定的不确定性带来的测量误差；表示由环境决定的衰减因子；表示 与 间距离。问题描述为提高 对 的服务质量，即优化 部署，以最少的 数覆盖。假定 与 间通信信道在视距环境，路径衰耗是影响覆盖质量的主要因素。因此，通过缩短 与 间距离减少路径衰耗，最终提高覆盖质量。换而言之，目标函数就是搜索 的位置，致使 离其最近的 的平均最小距离为：（）（）（）式中：表示目标函数 搜索到的 位置点；表示 离其最近的 中第 个位置的最小距离。因此，需要求解的问题可表述为：给定 的位置，和 的高度，将 移动至位置，进而满足式（）。值得注意的是：位置是未知信息，也不知道它们自己位置。无需 的具体位置，只需要 与 的距离信息，这是 算法的一个显著特点。在基于视距链路的前提下，无论 在哪里，只要 与为该 服务的 间的距离相等，所接收的服务质量就相同。换而言之，服务质量取决于 与 间的相对距离，而不是相对位置。因此，算法只需测距，进而避免了估计 的位置所产生的通信开销或者计算开销。算法 凸包理论的引入凸包（）是数学概念，它的数学定义为：在一个向量空间 中，对于给定集合，所有包含 的凸集的交集 被称为 的凸包。而点集 的凸包是指一个最小凸多边形，满足 中的点或者在多边形边上或者在其内。图 中由红色线段围成的多边形就是点集 ，。图 点集 的凸包示例弹 箭 与 制 导 学 报第 卷 算法引用凸包理论求解式（）。为此，令 表示所有 位置，的凸包。若对于任意，它在水平面上的位置 属于，则一定可以通过寻找，使（）（）最小。当 的水平面位置 不属于（）时，就可利用 中离 最近的点 替代。因此，对于任何一个 而言，均满足：，其中，表示 与 间距离。因此，用点 替代 可使（）（）更小。此外，对于任意一个，函数（）是关于的连续函数。为此，在 内存在一些点，使（）（）最小。因此存在局部最小值的非空集，这些非空集内一定存在全局最小值。定义：对于 ，如果满足 ，则点集（，）是理想状态。其中 表示集的质心，它的位置坐标（，）可表示为：|（）式中：表示集 的元素个数；（，）表示 的位置坐标。命题：只要点集（，）是理想状态，那么它就是式（）的局部最小。证明：引入函数：（）（）对式（）进行展开，可得：（）（）（）（）（）（，）（）由式（）可知，如果将，作为变量，当 ，时，式（）、式（）达到最小值。此外，将点 至点 段看成直线段，式（）是沿着此线段严格递减。求解 离其最近的 的平均最小距离依据命题，为了求解式（），将 划分多个区。每个区的质心作为 的位置。具体而言，依据式（）对 的定义，以每个 所包含的所有 构成的空间为一个区，部署于该区的质心位置。接下来，需要解决的问题是如何将 移动至这些区的质心位置。部署过程分两步。步骤：在时刻，期间，先随机选择 个位置作为 的水平位置，即给（），（），（）值赋予初始值。其中（）表示第 个 在时刻 的位置。步骤：对于任意一个，在（，）时，执行以下 子步。）选择时刻，满足（）（）。即 在 时刻，的位置不同。）计算 在下一时刻的位置，即计算（）。先计算 和：（）（）（）（）（）式中：（），（）分别表示 时刻的 横坐标、纵坐标；（），（）分别表示在 时刻的 横坐标、纵坐标。再构建直线方程：（）而 的定义为：（）（）（）（）（）（）（）式中：（）表示在 时刻 与 间距离。因此，在 时刻 的位置（）可表示为：（）（）（）（）（）（）（）（）（）（）|（）沿着直线段从（）移动到（）。性能分析 仿真参数在 水平区域内部署 个 和 个。每个 的高度是固定的，且在 区间。考虑文献的路径衰耗模型。对于任意一个，其视距链路的损耗模型为：|（）式中：表示载波频率；光速 ；表示关于视距链路的损耗因子。因此，端所接收的信号功率为 ，其中第 期魏妍等：灾区无人机救援系统中基于凸包理论的无人机部署算法表示传输功率。假定所有 的传输功率相同。此外，端所获取的信息容量为：（）（）式中：表示由 覆盖的 数；（）表示 端的信噪比，且（），其中 表示噪声；表示带宽。这些参数在仿真中的取值为：，。的部署性能首先，分析 算法对 的部署性能。假定 个 随机分布于区域内。最初，先随机部署 个，它们的初始位置如图（）所示。再通过执行 节的部署步骤，分别移动至局部最优位置，如图（）所示。图中的红色曲线表示 的移动轨迹；蓝色的点表示；黑色的小圆点表示。图 的部署示例 算法的（）和信息容量 性能由原理分析可知，当 高度固定时，（）值越小，视距路径越短，对 的覆盖性能越好。图 给出 数对（）的影响，其中 。从图 可知，随着无人机数的增加，（）迅速下降。原因在于：无人机数越大，每个无人机需要覆盖的 越少，无人机离 更近。当无人机数增加至 数时，每个无人机只需为一个 服务，这时的（）最短。图 （）随无人机数的变化曲线图 给出了 数对信息容量 的性能影响。信息容量 反映了 端的信噪比，信号质量越好，信息容量 就越大，性能越好。图 随无人机数的变化曲线由图 可知，无人机数和 数均影响了信息容量。通常，无人机数的增加，有利于信息容量 的增加。原因在于：无人机数越多，拥有的带宽资源越多，这有利于提高信息容量。而随着 数的增加，信息容量 会下降。原因在于：数越多，分享带宽资源的用户数越多。然而，（）随无人机数的下降率和信息容量 随无人机数的增加率均随无人机数的增加变缓慢。这说明，在无人机数与 所获取的服务性能间存在平衡。因此，网络供应商可依据 对服务性能要求部署无人机数。对比分析为了更好地分析 算法的性能，选择文献提出的优化覆盖质量的 部署算法（）作为参照。算法中 知晓 的位置。为了准确地分析 位置信息对（）的影响，算法分别考虑、和 的 位置是已知信息的 种情况，将这三种情况分别标记为，和 图 给出 算法和 算法的（）性能对比，其中 ，。从图可知，算法弹 箭 与 制 导 学 报第 卷和 算法收敛后，算法的（）值低于，的（），但是高于 的（）值。图 算法和 算法的（）随无人机数的变化曲线此外，相比于 算法，算法降低了收敛速度。原因在于：算法中 的位置信息是已知的，而 算法需要估计 与 间的距离。图 进一步分析了 算法和 算法的（）性能。从图 可知，只有 的 的位置信息是已知时，算法的（）值才低于 算法的（）。当达到 的 的位置信息为已知时，算法的（）为 ，而 算法的（）为 。在这种情况下，算法的性能优于 算法，但是估计 的位置增加了通信开销和计算成本。图 已知 位置信息的比例对（）的影响上述分析是假定所测量的 与 间距离（测距）是准确的。然而，在实际环境中，测距可能存在误差。因此，分析 算法对测距误差的鲁棒性是十分必要的。假定在测距过程中存在 的测距误差。图 显示了（）随测距误差变化曲线。从图 可知，（）随测距误差的增加而缓慢增加。例如，当用户数为、测距误差为 时，（）只比无测距误差提升了 。这说明，算法对测距误差具有较强的鲁棒性。此外，用户数越多，测距误差对（）的影响越小。原因在于：对于给定的用户数而言，测距误差会影响（）。但所有的用户都计算（），这就降低了测距误差对（）的影响。这也解释了为什么用户数越多，测距误差对（）的影响越小。图 测距误差对（）的影响 结束语为了提高 对灾区中 的服务质量，研究了 的部署问题，并提出了 算法。算法通过缩短 与 间距离，提高 的服务质量。考虑到估计 的位置信息的计算成本，算法只需测距，无需定位。仿真结果表明，算法的性能逼近 算法的性能。文中假定 的高度不变，在部署 时没有考虑 的高度信息。后期，将考虑的 的高度信息，对 算法进行改进。参考文献：何尔利，纪澎善，贾向东，等 位置协助的无人机毫米波通信网络自适应信道估计 计算机工程，（）：，（）：，（），（）：，（）：，（）：第 期魏妍等：灾区无人机救援系统中基于凸包理论的无人机部署算法，（）：，：，（）：，：，（），（）：，：，（）：邹东尧，陈鹏伟，刘宽 一种改进的 测距定位算法 电讯技术，（）：，（）：，（）：，（）：李文勇，陈梅香，许树坡，等 基于分水岭和凸包理论的自然场景下未成熟苹果直径测量方法 农业工程学报，（）：，（）：，（）：