基于遗传算法的无人机自组网吞吐量优化方法

刘建强，张森林，霍 帅，王 毅，陈 宇

(1.郑州航空工业管理学院 电子信息学院, 河南 郑州 450046;2.郑州航空工业管理学院 航空航天电子信息技术河南省协同创新中心，河南 郑州 450046；3.郑州航空工业管理学院 河南省通用航空技术重点实验室，河南 郑州 450046；4.郑州航空工业管理学院 科技处, 河南 郑州 450046)

0 引 言

无人机自织网可用于应急通信场合［1］。无人机承担通信节点的作用，而无人机间的空空链路及无人机对地面的空地链路则是网络的通信链路［2］。典型的无人机自组网如图1 所示。无人机自组网的吞吐量是一个重要的性能指标［3］。

在通信网络初始部署时，由于缺乏足够的需求信息，分配给无人机的位置可能不是最佳的，从而导致吞吐量不是最优。

为达成吞吐量最优，在网络运行过程中，无人机节点可以收集有关用户位置及其数据速率需求的信息，利用这些信息构建网络的全局视图，进而优化各种网络性能指标。本文提出了一种基于遗传算法的近似算法，用于优化无人机节点的位置和无人机节点与用户的连接关系，进而使吞吐量最大化。

1 研究进展和问题分析

无人机的位置影响各种网络性能指标，如吞吐量、覆盖范围、连接和收益。为解决通信容量与流量需求之间的不匹配问题，文献［4］开发了一种通过控制无人机航向角来优化中继链路性能的算法。文献［5］提出了一种用于最优端到端通信链的分散移动控制算法，该算法使用一组无人机充当通信中继节点。控制器使用随机近似计算优化通信目标函数，将无人机虚拟控制点的位置驱动到优化后的中继位置。文献［6］对干扰容量的影响因素进行了理论分析，并导出了容量的闭合表达式，该表达式可用于确定无人机的最佳位置。文献［7］认为，路由协议应考虑中继放置服务，为充当中继节点的无人机找到理想位置，从而避免无人机运动对视频传播的影响，并提出了一种无人机中继放置机制，以支持具有令人满意的体验质量（QoE）的实时视频的传输。文献［8］提出了多种分布式网关选择算法和基于云的稳定性控制机制。文献［9］提出了一种在无人机自组网中基于集群的控制平面消息管理，基于无人机上下文信息，控制器可以在不传输控制消息的情况下预测无人机信息，进而优化位置信息。

然而，上述算法大多考虑单个无人机的位置优化，或者在考虑多个无人机节点位置优化时，没有考虑用户流量需求带来的影响。实际上，一方面，无人机节点间的距离影响对应的链路容量，进而影响吞吐量；另一方面，当用户节点处于多个无人机节点的覆盖范围时，选择不同的无人机节点服务，也会影响网络整体的吞吐量。

如图2 所示的网络和用户、用户之间通信流量需求如表1 前两例所示，由于C2连接的无人机节点不同，导致使用图2（a）方案获得的吞吐量为10，使用图2（b）方案获得的吞吐量为19。统计数据如表1 后两列所示。

表1 节点选择影响吞吐量

图2 用户节点和无人机节点的连接对吞吐量的影响

从上述分析可以看出，通过优化无人机节点的位置以及无人机节点与服务用户之间的连接关系，无人机网络系统的吞吐量得到优化。

2 系统建模

2.1 问题描述

假设在既定地域内，有m个用户需要进行通信，现拟使用n架具有组网功能的无人机提供通信服务。如图3(a)所示，空心圆点表示一定区域内的用户节点，实心圆点表示自组织网络中的无人机节点。每个无人机节点可为多个用户节点提供通信服务，但每个用户节点在同一时间只可选择一个无人机节点享受服务，无人机节点间按自组织的方式连接成网络。图3(b)是图3(a)的二维示意描述。

图3 无人机自组织网络服务区域用户示意

2.2 模型建立

2.2.1 系统表示

记该系统为S（V，C，T）。其中V为该区域内的无人机节点，共有n个；C代表该区域内的通信用户，共有m个；T为系统中的流量需求。每个无人机节点或用户节点的位置Pi=(pi(x),pi(y),pi(z))。显然，节点均处于一个三维空间。由于所讨论的吞吐量和节点间距离相关，二维平面和三维空间在距离上没有本质差别，为了表述方便，本文拟在二维空间来描述。

2.2.2 数据链路

用E来表示无人机节点间的链路集合，则图G（V，E）可表示该区域内的无人机自组织网络。记该图的邻接矩阵为A，即

一条通信链路au,v存在两个无人机节点u和v之间当且仅当它们之间的距离在彼此的传输范围内。也就是

这里RV2V是无人机之间通信的最大传输范围，而pu和pv分别表示无人机u和v的位置。

若有两个以上的节点存在一个无人机节点中，则选择一个距离较近的节点建立连接。本文假设所有链接都是对称的。任何两个无人机之间都存在一条路径，即图G是连通的。

每个无人机可以同时与所有相邻无人机通信而不会干扰其他无人机的通信。无人机到无人机的通信最大传输范围是RV2V。无人机到用户的通信最大传输范围是RV2C。无人机到无人机的最大通信传输范围大于无人机到用户的最大通信传输范围，即RV2V≥RV2C。

无人机及其相关用户通信信道与相邻无人机之间使用的信道不同。也就是说，如果cu表示无人机u与相关用户通信所使用的信道，则∃u∈V，k∈N(u),使cu≠ck，其中N(u)表示u的邻居的集合。这可有效地消除相邻无人机关联用户之间的干扰。

网络G服务的所有终端记为C(G)，无人机u∈V提供通信服务的用户集合记为C(u)。假设每个用户只从一个无人机节点处得到通信服务，所有的无人机节点覆盖全部用户，即

无人机和用户之间的关联关系用矩阵B表示，即

一条通信链路bu,v存在无人机节点v和用户节点u之间当且仅当它们之间的距离在彼此的传输范围内。也就是：

这里RV2C是无人机之间通信的传输范围，而pu和pv分别表示无人机u和用户v的位置。

2.2.3 流量需求

用无序偶（i,j）表示用户i和用户j之间的通信流，其流量需求大小用fij表示，则m个用户之间的流量需求用矩阵T表示。

流（i,j）在自组网中经过的路径记为Pij，链路l∈Pij的容量可以通过文献［10］中的方法获得。记cl,（i,j）为链路l∈Pij上流（i,j）的允许容量,当有多条流通过一段链路时，按照最大最小公平性原则分配各流的允许容量［11］。记Bij为流（i,j）的瓶颈链路上的允许容量，即

瓶颈链路可以是两个无人机之间，也可以是一个无人机与其关联用户之间。

则该流量所达到的吞吐量是

当fij≤Bij时，流（i,j）可实现的最大吞吐量为fij。如果fij≥Bij，则可通过增加Bij来增加流（i,j）的吞吐量τij。控制瓶颈链路上的节点彼此靠近可以实现这一目标。

2.2.4 吞吐量最大化描述

系统总吞吐量τ由给出。

在上述给定条件下，本文所有优化的目标为

(8.a)表示求取所有用户流的总和最大化。(8.b)第一式表示由无人机节点V和用户节点C组成，用户节点间的流量矩阵为T，这是系统的初始输入；第二式表示任何一个无人机节点最少有一个距离小于RV2V的无人机节点，第三式表示任何一个用户节点最少有一个距离小于RV2C的无人机节点，它们一起表示所有无人机节点都连接在网络上，所有用户都由无人机节点提供通信服务，这是系统的假设条件。

3 算法设计

如前所述，用户节点对无人机的选择以及无人机节点的位置都将影响网络的吞吐量，而吞吐量的优化又是一个复杂的过程。因此，本文引入遗传算法，利用遗传算法良好的全局优化能力来获得吞吐量的最大值。遗传算法［12］（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。算法要点包括以下几个方面。

3.1 地域编号

为了方便使用遗传算法，将无人机自组织网络地域用多个正六边形覆盖，并为每个网格进行编号，每个无人机节点或用户节点所处的位置用其所在的网格编号表示。如图4 所示，无人机V1、V2、V3、V4分别处于15、60、43和46号网格处。

图4 无人机自组织网络地域网格化示意

显然，正六边形的边长越小，其所需网格数越多，与此同时，所描述的位置越精确。为了表征地域被正六边形划分的细腻程度，本文称正六边形的边长为粒度半径。

3.2 确定无人机节点之间的邻接矩阵

无人机自组织网络的自组织特性表现在在有效通信范围内，可以自主地和其他节点连接，即根据无人机节点集{Vi}，确定对应的邻接矩阵A。

根据文献［10］，在相关因素如发射功率、噪声功率、信道相同的情况下，两个节点之间距离越近，则其对应的链路容量越大。

因此，无人机节点之间链路生成可以采用如下方法：对于{Vi}中的任何一个节点u，计算和其他节点的空间距离，选择最近节点v*＝arg min|pu pv|并与之建立链路，即au,v= 1。

由于上述方法是选择距离最近的节点作为邻接节点，因此总能保证点对点之间链路容量最大。在此基础上进行优化，可以缩短优化过程。

根据邻接矩阵A，可以使用Dijkstra 算法得到两个节点之间的最短路径P。

3.3 确定用户和无人机之间的关联矩阵

如前所述，用户选择不同的无人机节点可能导致系统的吞吐量不同，因此需要优化用户和无人机之间的连接关系。

若用户i和对端j的流量需求为fij，该用户总的流量需求为无人机节点g的所有链路容量之和记为Tg。用户i仅处于一个无人机节点g的有效通信范围RV2C内，则直接连接到该无人机上；但是如果处于多个无人机节点的有效通信范围内，则需要选择连接在哪个无人机上。记连接在无人机节点g上的用户为Cg，则Cg按下式确定。

根据的结果，即可确定关联矩阵B中的bg,*。根据这种方法，同样可以得到其他无人机节点的关联矩阵元素，进而得到关联矩阵B。

利用关联矩阵B和流量矩阵T和3.2 节中获得的P，即可求得各流（i,j）在链路l上的允许容量cl,（i,j），进而求得（i,j）的瓶颈容量Bij。

接下来的过程主要是通过控制无人机节点的位置来增加Bij对应的链路容量。

3.4 确定无人机节点位置移动的范围

无人机可部署位置由两方面的因素决定：服务对象即用户的位置和邻居无人机节点的位置。要求其部署位置离其用户的距离不大于RV2C，离其邻居无人机节点的位置不大于RV2V。其部署范围如图5 所示。以相邻节点为圆心，以RV（不大于RV2V）为半径画圆；以用户位置为圆心，以RC（不大于RV2C）为半径画圆，则所有圆的交集即为该无人机部署的可选位置。显然，在这个范围内，该无人机节点和其他无人机节点以及用户都能保证正常的连接。本文称RC和RV为位置约束半径。显然，约束半径越大，则无人机可移动优化范围越大，反之亦然。

图5 位置约束半径示意图

如图5 所示，以V3的可移动优化范围为例，分别以其邻居无人机节点V1、V2、V4为圆心，以小于RV2V的RV为半径做圆；以其用户节点C6为圆心，以小于RV2C的RC为半径做圆，四个圆的重叠部分H 即为V3可移动优化的范围。同理，可以确定其他无人机节点的可移动范围。

3.5 编码并使用遗传算法进行优化

遗传算法求解优化问题首先要对问题进行编码形成种群，然后对种群进行遗传操作。

3.5.1 编码和种群初始化

优化对象是无人机节点的位置，为了方便使用经典遗传算法，这里进行二进制编码。由图4 和图5可以得到无人机可移动优化位置编号结果，如图6所示。例如无人机节点V3的可选择优化位置为{17，30，36，37，50}，该集合共5 个位置，可以使用3 位二进制数进行编码，如表2所示。

表2 节点位置遗传编码

图6 遗传编码示意图

将每一个无人机节点都按上述方法进行编码，按无人机序号将二进制字符串连接在一起，就是对地域内的无人机位置的一种表示。

假设第i个无人机节点位置的编码为Code(i),则一个可能的位置方案对应的染色体编码为：

求和表示的是字符串的连接。按照上述方法生成多个染色体，组成种群。

3.5.2 依据适应值进行遗传操作

1）适应值计算

染色体n对应的网络吞吐量用τ(n)表示，则

其中τi,j(n)表示染色体n中由用户i到j的流量值。

每个染色体编码都有一个适应值，该值是评价该染色体的依据。对于本优化问题，适应度函数设计为：

其中τm,τavg分别为当前代染色体的最大和平均吞吐量。

这个适应度函数有以下特点：适应值范围为（0，1）；最大吞吐量对应的适应值为1，吞吐量为均值的染色体适应度为0.5；越靠近最优值，其适应值变化越灵敏，而在平均值以下，则下降更快。其好处在于：在算法初期尽快淘汰适应值较低的个体；在算法后期有效地拉开最优解附近点的适应值距离，避免陷入次优解。

2）染色体复制操作

当执行复制操作时，染色体n以概率进入下一代种群。

3）染色体杂交操作

经典的遗传算法杂交算子是选择两个染色体，随机选择一个杂交位i，然后两个染色体相互对应的交换从i+ 1 到末位的位段。对于本问题来说，由于染色体分段表征多个无人机节点的位置，若随机选择杂交位，可能会使杂交位对应的无人机节点位置表征错误。例如，若染色体中表征V3 的基因段为001 和100，若杂交点为2，则杂交后为基因段为000和101，而101为无效基因。

为避免这种情况，此处对经典遗传算法进行改进，限定杂交位置为各基因段的连接点，即可能的杂交位置为从而保证各位基因段的完整性。

4）染色体变异操作

经典的变异算子在染色体上随机产生变异位，即相应位取反，直接使用，同样会产生无效基因。如对于表7 中的基因段100，变异位选择了2 或3 位，都会产生无效基因。为避免这种情况，此处变异算子在经典变异算子的基础上增加基因健康检验，若出现无效基因，则重复经典基因算子，直到产生的基因是合法的为止。

3.5.3制定终止准则

停止准则可以表示为算法执行的最大代数。对于本问题来说，吞吐量最大就是各用户的流量需求总和若位置优化的吞吐量达到该值，优化可以结束；另一个条件是系统达不到用户的流量需求量，这时若优化的吞吐量最大值一直没有明显的提高，则可以终止迭代并输出当前吞吐量值作为问题的优化结果。

上述算法可以用如算法1 的伪代码来表示。首先将考察的地域进行网格化；第2行生成无人机节点i的可选择位置Po(i)，供优化选择使用；第6行使用随机的方法在Po(i)中选择一个位置，作为对应无人机位置优化的实现；第8行使用字符串连接的方式获取一个染色体Code(i)，并通过循环的方式获得多个染色体，形成初始种群；第10 行是遗传算法的终止条件，其中表示最近多代最大吞吐量的平均值，表示当前吞吐量和平均最大吞吐量的差值大于一定量；第11 行是计算当前种群中每个染色体的适应值；第12 至14 行根据前文所述的遗传算子进行染色体操作；第15 行求得当前进化的群体中最大的吞吐量值；第18行则是在结束进化后，根据最大吞吐量的值进行解码，从而得到对应无人机的位置。该优化的位置可以通过数据链路发送给各无人机，由飞控系统执行对应操作，控制无人机到目标位置，从而达到最大的网络吞吐量。

算法1 基于遗传算法的无人机位置优化输入:无人机自组网拓扑及用户流量需求输出:优化后的位置1 GriddingRegion()2 Po(i) ←OptionalPositionForUAV()3 generation=0 4 for i=0;i＜=Npop;i++5 for j=0;j＜=Nuav;j++6 P(j) ←InitalizePositions(Po(j))7 end for 8 Nuav Code（P(j)）)Code(i) ←∑j = 0 end for 10while(τ ≠∑i ∑jfij or||9 τ --τm ≥δ)do 11Fitness=Evaluate(Pop(generation))12Reproduction(Pop(generation))13Crossover(Pop(generation))14Mutation(Pop(generation))15 τm = MaxThought(Pop(generation))16generation++17end while 18Pmax ←DeCode(τm)

4 仿真结果

利用MATLAB 及其中的GA 工具箱进行了仿真。首先，生成地域内的通信用户位置以及用户对流量的需求，然后依照上述算法生成无人机节点位置，使得生成的图是连通的。

无人机高度保持在200 米。无人机对无人机通信的传输功率为2瓦，而无人机对无人机通信的传输距离RV2V保持在500 米。这意味着，如果任何两个无人机之间的距离在500米以内，则它们之间可以存在连接。无人机对用户通信的传输功率为1w，而无人机对用户通信的传输距离RV2C保持在250m。为了估计链路的吞吐量，基于发送—接收距离和信道（传播）模型估计SINR。然后，使用文献［10］计算适当的吞吐量值。对于遗传算法中的参数，种群规模取100，复制概率取0.4，交叉概率取0.4，变异概率取0.2。

4.1 无人机位置对链路流量和网络吞吐量的影响

表3 显示了四个流的细节（约束半径200 米和粒度半径30 米）。图7（a）显示了无人机的初始和最终（由算法确定）位置。在无人机的初始位置，没有一个流量的需求得到满足。然而，随着无人机最终位置的确定，流量2 和流量3 的需求得到充分满足，流量1和流量4的吞吐量有所增加。

表3 吞吐量优化统计

图7 位置优化对链路容量及网络吞吐量影响

图7（b）显示出算法如何通过迭代进行。最大总吞吐量在代30时实现。在代5中，流3的需求得到满足。此外，由于流1 和流4 共享一个瓶颈链路（即链路V2V3），因此在大多数情况下，它们的吞吐量是相同的。然而，在进化后期，流4的吞吐量略高于流1。当V3靠近V2时就会发生这种情况。在进化的三四代中，流4 的需求得到满足（7Mbps），流1 的吞吐量略有增加，而流2 的吞吐量急剧下降。流量2 的吞吐量急剧下降是由链路V2V3的容量下降引起的。因此，此时，流1和流4正在与流2争夺V3的位置。流1和4希望V3更接近V2，而流2希望V3更接近V4。最后由于流2对全网吞吐量提升效果更明显而获胜。

4.2 位置约束半径（Position Constraint Radius，PCR）的影响

表4 显示了四个流的详细信息。表中显示，随着位置约束半径的增大，吞吐量可能进一步提高。这是因为随着位置约束半径的增大，可以测试更多的无人机位置以提高吞吐量。

表4 吞吐量约束半径影响统计

图8 显示出位置约束半径如何影响吞吐量的改进。

图8 位置约束半径影响

在初始进化过程中，该算法对所有位置约束半径产生相似的吞吐量。然而，在第11次进化中，位置约束半径100m 对应的吞吐量落在位置约束半径150m 和200m 对应的吞吐量之后。同样，在第15 次进化中，位置约束半径150m 对应的吞吐量落在位置约束半径200m 对应的吞吐量之后。这是因为，位置约束半径越小，无人机的可优化机动范围就越受限。当位置约束半径100m 时的可优化机动范围是位置约束半径为150m 和200m 时可优化机动范围的子集。因此，在第11 代进化过程中，该算法尝试在位置约束半径为150m 和200m 情况下的位置优化，可能导致性能改进。但是，这些导致性能改进的位置可能落在位置约束半径为100m 的可优化机动范围之外。类似地，在迭代15 中，该算法尝试在位置约束半径200m 且不在位置约束半径150m 的范围内进行位置优化，从而导致吞吐量的提升。因此，当位置约束半径较大时，与较小的半径相比，可以获得更大的吞吐量改进。

4.3 粒度半径(Particle Size Radius,PSR)的影响

图9 显示了当算法搜索（近似）最优无人机位置时粒度半径的影响。在初始代中，较大的粒度半径会导致吞吐量的急剧增加；稍后，较小的粒度半径将逐渐增加。当粒度半径较大时，算法收敛速度较快，但通常情况下，确定的解不如粒度半径较小时接近最优解。粒度半径越小，算法收敛速度越慢，但确定的解越接近最优解。

图9 粒度半径影响

5 总 结

本文提出了一种基于遗传算法的近似算法，用于控制无人机的位置，优化无人机自组网的拓扑，进而使吞吐量最大化。仿真分析表明，该方法可以优化自组网的吞吐量，且优化速度和位置约束半径和粒度半径有关。本方法可以用于中继通信的无人机自组网提升吞吐量使用。