无人机网络移动部署算法设计

袁万腾++李亚各

摘要：该文中提出了一种速度可控的虚拟力模型，考虑了节点运动状态与虚拟力间的关系，通过引入速度反馈作用力对节点的运动状态进行控制。该虚拟力模型中节点的运动能够较为准确的描述节点在移动部署过程中的运动特征。在此虚拟力模型的基础上，为了能够实现对兴趣点的快速覆盖，同时维持较好的网络连通特性，设计了一种兴趣点覆盖的移动部署算法。该算法通过节点设置标志值，避免了因兴趣点作用力过大造成节点分布集中的问题，增大了网络通信覆盖范围，维持了较好的网络连通性。

关键词：无人机网络；网络部署；虚拟力；覆盖

中图分类号：TN929 文献标识码：A 文章编号：1009-3044（2017）03-0056-04

Deployment Algorithm for UAV Network

YUAN Wan-teng LI Ya-ge

（Xian Aeronautics Computing Technique Research Institute， AVIC， Xian 710086， China）

Abstract：In this paper， a speed controllable virtual force model is proposed， Considering the relationship between the node motion state and virtual force， the speed feedback force is introduced to control the motion state of node. The movement of nodes in the virtual force model can accurately describe the motion characteristics during the process of node in mobile deployment. Based on the proposed virtual force model， in order to realize the rapid coverage of POI， at the same time maintain good connectivity， this paper designs a point of interest coverage mobile deployment algorithm.

Key words： UAV network； virtual force； network deployment； coverage

1 概述

無人机网络[1]由无人机（Unmanned Aerial Vehicle，UAV）节点组成，也可称为无人机Ad Hoc网络（Unmanned Aerial Vehicle network）。无人机平台作为侦察和监测的有效手段，很早就被应用到在军事和民用的应用中。使用无人机可以完成一系列复杂的任务，如搜索、摧毁，边境监视，林火治理，灾害监测等任务，并且具有较高的应用价值。

但无人机在提供通信服务方面一直受到很大限制，尤其当多架无人机通过组网的方式形成通信中继网络时，无人机节点的移动性和网络拓扑的动态特点会对节点间的通信质量造成冲击。无人机网络可以作为中继网络[2]使用，如固定网络的延伸部分，为无法连接到固定网络区域的用户提供临时的通信服务，同时也可以形成独立的网络，负责网络内节点间的通信，具有较好的实用性[3]，为了使得无人机网络的通信变得可靠，需要对网络的拓扑结构进行相应的控制，以确保网络能够保持较好的网络性能。这也是本文的研究方向。

2 无人机网络简介

Ad Hoc网络，又称无线自组织网络，是一种多跳的、无中心的、能够自组织的网络。Ad Hoc是由一组具有无线通信功能的移动终端组成的多跳临时性自治系统，每个终端都具有平等的地位。各节点之间的通信通过无线互联，通过有效的机制进行网络信息的共享，整个过程不需要人为的控制或者中心节点的调度。

无人机网络中的每个节点都具有两种功能，一种是作为主机，可以在终端上运行各种应用程序；一种是作为路由器，可以运行相应的路由协议，对数据包进行处理、转发。所以无线自组网的这种分布式和无中心的网络结构特性使得网络在复杂环境下能够维持较好的通信能力，具有很强的抗毁性和鲁棒性。由于网络中移动节点都具有路由的功能，可以将网络中的节点通过无线的方式连接成任意的拓扑结构。

3 无人机网络的特点

无人机网络是基于无人机集群构建的，充分地利用了无人机的优良特性。相比有人机，无人机无论是从飞机体积、重量还是外形都相对较小，更灵活也更具生命力。同时因为无人机的造价相比有人机低廉很多，不害怕损毁，所以可以同时使用多架无人机去完成某一特定任务，这时就需要通过飞行Ad Hoc网络来维持无人机之间的通信[4]。相比常见的固定网络、或者无线的蜂窝网络，无人机网络具有以下特征：

3.1 拓扑结构动态变化

由于无人机的移动性、环境的复杂性、无线信道之间的干扰等因素，无人机网络处于高度动态的环境中，无人机网络的拓扑结构不断发生变化，并且这种变化难以预测。

3.2 多跳的通信方式

由于无人机节点的无线传输范围会有一定的限制，为了能够实现点与点之间的通信或者是进行全网广播或者组播，就要求无人机网络具有多跳转发的通信机制，即网络中的消息需要经过中间节点的转发才能完成投递。

3.3 自组织

无人机网络是由无人机组成的临时无线自治系统。由于无人机网络的拓扑结构会因为节点的移动而发生改变，所以目前的一些无线路由技术不能适用。无人机网络应具有在无基础设施的前提下可以实现快速的组网的能力。

3.4 网络的分布式控制

由于无人机网络中的节点既是移动终端同时兼有路由的功能，因为不存在中心控制节点，所以每个节点的地位都是平等的，一般都采用的是分布控制的方式，这样也增强了网络的鲁棒性和抗毁性。

4 移动部署算法设计

4.1 无人机节点的运动分析

假设在二维平面内，无人机集群是由N个相同的无人机组成，分别表示为N1，N2….，Nn。对于单个无人机节点，其运动服从运动学规律，可以用数学模型表示为：

[xi=vimivi=Fi] （1）

其中，xi，vi，mi，Fi分别表示第i个无人机的位置向量、速度向量、节点质量和控制输入量。

在本文中，节点通过迭代计算的方式更新本地的运动状态信息并计算目标位置，令Xi表示单个节点的运动状态量：

[Xik=xikvik] （2）

Xi（k）表示节点i在k时刻的运动状态，xi（k）表示其位置向量，vi（k）表示其速度向量。将公式3进行离散化得到节点状态量的迭代计算公式：

[Xik+1=1T01xikvik+tT-t2tFikmi] （3）

其中T为每一步的时间长度，Fi（k）为k时刻节点i的控制输入，t表示控制输入的作用时间。通过公式3-16就可以由当前的运动状态信息计算得到下一时刻的运动状态。根据该运动状态更新方程可知，在每一个时隙T内节点会先做t秒的匀加速运动，当速度达到某节点的速度上限时，节点停止加速运动并在剩余的时间做匀速直线运动，直到该轮移动过程结束。

因为本文中采用的是分布式的方法进行移动部署，每个节点可以进行自主的移动。节点能够获得邻居节点的相关信息，并根据移动算法进行移动，移动部署算法的具体内容如表1所示。

表1 单兴趣点覆盖移动部署算法

[初始化：

初始化节点、兴趣点的初始位置，并将初始化为0；

节点通过广播消息将自己的相关信息发送给一跳邻居；＼&本地信息更新：

While（True）do{

節点i在T的时间内接收一跳邻居发送的广播包，并根据广播包内的信息更新本地信息：

1）节点通过收到的Hello消息生成一个邻居表Ni，Ni中记录了节点i的一跳邻居；

2）当节点i的flag值为0时，节点i判断兴趣点是否在自己的通信范围内，如果是，再判断自己的邻居节点中，是否有节点的flag值为1，如果没有就将自己的flag值设为1；反之如果有就将自己的flag值设为2；

3）当兴趣点没有在节点的通信范围内时，就判断自己的邻居节点中是否有节点的flag值非零，如果有，当节点i的邻居个数大于2时，就将自己的flag值设为2；

4）当节点没有邻居且flag值非0时，将flag置0；

}＼&主要步骤：

While（||vi||>vth） do {

节点i的速度大于阈值时，节点计算所受的虚拟力：

1）判断节点所受虚拟力的类型：

[if flagi==2 Fi′=j∈NFij； Fi=Fi′+Fiv；else Fi′=j∈NFij+FiP； Fi=Fi′+Fiv； ]

2）判断虚拟力作用的时间：

[if Fi′miT>vmax t=vmaxFi′T；else t=T； ]

3）计算虚拟力并更新运动状态：

[xi=xi+viT+tT-t2Fi2mi ；vi=vi+Fitmi； ]

4）节点会根据计算所得的虚拟力移动到下一目的位置，并通过Hello消息将自己的信息广播给自己的一跳邻居。

}＼&]

5 实验仿真

本文基于MATLAB2013b软件对提出的算法进行仿真，仿真的区域为500m×500m的正方形区域，实验中节点的个数从10变化到100，节点通信半径的变化范围为10m到100m，目的是测试不同条件下算法的性能。在整个部署过程中，每一轮的时间间隙为T=1秒。速度阈值vth=0.1m/s，当所有节点的速度小于这一阈值时，认为网络的拓扑结构近似达到一种稳定状态。节点的初始部署状态是随机分布在整个指定区域内，具体的实验参数如表2中所示。

表2 实验参数

[区域大小＼&500m×500m＼&节点个数＼&10～100＼&通信半径Rc＼&10m～100m＼&最优距离dopt＼&Rc-0.5＼&时间步长T＼&1s＼&速度阈值vth＼&0.1m/s＼&兴趣点的位置＼&（0，0）＼&K1＼&0.25＼&K2＼&-0.25＼&K3＼&-1/t＼&]

5.1 拓扑变化

图1中所示为本文算法中网络拓扑结构随着时间的变化，选取的最大速度为5m/s，节点个数为50，通信半径为30m。初始时，网络中的节点随机的分布在整个区域内，如图1（a）所示。

图1 场景一拓扑变化

此后所有节点逐渐向兴趣点移动，并在兴趣点周围形成一个连通的网络，如图1（b）（c）。当兴趣点对所有节点不再产生力的作用时，节点只受到节点间作用力和速度反馈控制力的影响，并在此基础上进一步调整网络拓扑结构，如图1（e）所示。可以看到图1（e）（f）中，网络的拓扑结构基本保持稳定，类似正三角形拓扑结构，满足拓扑控制的目标。

5.2 覆盖范围

图2中为网络的覆盖范围与节点通信半径之间的关系，节点个数为50，通信半径从10m变化到100m。因为通过几何方法计算网络的通信覆盖范围较为困难，所以本文采用蒙特卡洛的方法来评估网络的覆盖范围。在给定的区域内均匀部署2.5×105个点，并检测这些点中一共有多少点能够被无人机节点所覆盖，并用被覆盖点占所有点的比例代替网络的覆盖范围。下文中关于覆盖范围的实验均以该种方式计算实验结果。网络的覆盖范围的大小可表示为：

[＼&（4）＼&]

由公式4可知，网络覆盖范围的大小与通信半径的平方成正比。随着通信半径的增加，覆盖范围不断增大。由于覆盖区域有限，当半径较大时，有些节点会覆盖到区域以外的地方，这一部分的面积不计算在内，所以可以看到两种算法在通信半径为100m时的覆盖范围接近1，表明指定的区域都基本被覆盖。从图2中可以看出，两种算法的覆盖范围随着通信半径的增大都是逐渐增大，并最后趋近概率1。但在通信半径较大时，文献[5]算法的覆盖范围小于本文算法的覆盖范围。本文算法中针对不同的最大速度，分别选择0.5m/s、1m/s、5m/s、10m/s四种速度上限，可以看到对于不同的最大速度其最后的覆盖范围基本相同。

图2 覆盖范围随通信半径变化

5.3 连通性

图3 连通概率随通信半径变化

图3中所示为网络连通概率随通信半径的变化曲线，分别选择节点个数为50个和30个两种情况进行分析，本文算法的最大速度分别选择的是0.5m/s和5m/s。从图中可知当本文算法选择不同的最大速度时，最终形成的网络在不同的通信半径下都能保持1或近似1的连通概率。文献[5]算法无法在半径较小时维持较好的连通性，这与其在半径较小时具有较大的节点间斥力和较小的兴趣点引力有关。

6 结论

本文针对无人机的运动特性，提出了一种速度可控的虚拟力模型，并将该模型看作控制目标，推导出节点受力的微分方程。可以看出节点的受力与节点位置信息和速度信息相关，模型较为简单，并能够准确描述节点在真实环境中的运动特征。本文中結合节点移动受控特性，引入了速度反馈作用力，设计了一种自主的移动部署方法则是研究如何能够通过节点的自主移动部署改善网络的性能，即利用节点的移动性对网络的拓扑结构进行重构，使得网络的相关性能，如连通性、覆盖范围、移动代价等指标达到设计要求。

参考文献：

[1] Bekmezci I， Sahingoz O K， Temel ?. Flying ad-hoc networks （FANETs）： a survey[J].Ad Hoc Networks， 2013，11（3）： 1254-1270.

[2] Pignaton de FreitasE. UAV relay network to support WSN connectivity. in Ultra Modern Telecommunications and Control Systems and Workshops （ICUMT） [J].2010 International Congress on， 2010.

[3] Chlamtac I， Conti M， Liu J J N.Mobile ad hoc networking： imperatives and challenges[J].Ad Hoc Networks， 2003， 1（1）： 13-64.

[4] 毛莺池.与位置无关的无线传感器网络连通性覆盖协议[J].软件学报， 2007， 18（7）： 1672-1684.

[5] Liu H. Simple movement control algorithm for bi-connectivity in robotic sensor networks. Selected Areas in Communications[J].IEEE Journal on， 2010，28（7）： 994-1005.