基于改进NSGA-II算法的无人机组网拓扑关系与带宽分配优化策略

基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略
技术领域
1.本发明涉及无人机通信组网拓扑关系与带宽分配优化领域，具体涉及一种基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略。


背景技术：

2.随着通信网络系统的不断发展，无人机中继通信正成为传统通信网络的重要补充，无人机集群组网通信在未来的通信网络架构中很有前景。当地面目标区域无法以基础通信设施维持通信时，需要多架无人机组合完成过中继通信服务任务，从而完成整个通信网络的恢复和正常运行。现有一些针对优化无人机通信组网的研究在不断展开，提出了各种针对无人机通信组网的评价指标和优化方法，实现对于无人机组网通信性能的高效优化。
3.现有的对于无人机组网通信性能优化的研究仍然处于起步阶段，如何解决业务需求复杂与无人机载荷有限的问题，是解决无人机组网通信性能优化问题的关键因素。无人机组网通信性能优化面临着以下几个难点。首先，为了保证无人机集群组网的通信性能，综合优化策略的设定需要满足覆盖效果最优、链路负载低、链路稳定性强等要求。其次，目标区域用户的服务需求量不同，优先级顺序不同，导致区域用户服务覆盖量度不一，合理提供服务带宽难度较大。最后，不同于传统通信网络，因为无人机节点的高机动性和有限的能耗以及无人机组网的网络性能要求多样，导致多目标优化问题的维度较大，寻找优化目标之间的支配关系困难，优化过程的收敛压力较大。


技术实现要素：

4.针对无人机通信组网优化面临的上述难点，本发明将提出一种基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略，通过改进nsga-ii算法与多通信性能指标考量，结合该问题的结构特征，克服该问题面临的复杂性能要求、带宽信息发展与高收敛压力等难点。
5.实现本发明目的的技术方案为：第一方面，本发明提供一种基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略，包括如下步骤：
6.步骤1，获取无人机飞行高度、部署位置、最大提供服务带宽；获取地面区域用户数量、业务需求量与业务优先级；
7.步骤2，建立考虑无人机执行灾区中继通信任务的距离模型，确定无人机执行中继任务的模型假设；
8.步骤3，建立考虑无人机组网通信性能的通信模型，确定无人机通信组网优化策略的评价指标；
9.步骤4，根据评价指标，确定优化目标；
10.步骤5，设计改进nsga-ii算法，根据olsr路由协议的参考路由求取多目标优化效
果最优的无人机组网拓扑关系与带宽分配优化策略集合作为最优策略。
11.第二方面，本发明提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如第一方面所述的基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略的步骤。
12.第三方面，本发明提供一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如第一方面所述的基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略的步骤。
13.本发明由于采用以上技术方案，能够取得如下的技术效果：
14.建立的无人机通信组网拓扑关系与带宽分配优化模型能够有效表征无人机组网性能需求，能够提高无人机通信组网的综合通信性能。基于以上模型，引入了olsr路由协议以保证无人机网络通信过程中链路的畅通与信息的可靠度。同时本算法结合高收敛压力的难点，对传统nsga-ii算法进行改进，在保证收敛精度的基础上，减少了收敛次数，缓解了多目标优化的收敛压力。
附图说明
15.图1是本发明的无人机组网拓扑关系与带宽分配策略优化原理框图。
16.图2是经过优化后的组网拓扑示意图。
具体实施方式
17.下面结合附图和实施例对本发明的技术方案作进一步详述。
18.如图1所示，本发明主要包括：初始化模块、无人机组网距离模型构建模块、无人机组网通信模型构建模块、评价指标与优化目标函数构建模块、优化算法模块、最优拓扑关系与带宽分配策略提取模块。结合流程图说明具体实现步骤为：
19.步骤1：初始化。获取无人机飞行高度、部署位置、最大提供服务带宽；地面区域用户数量和业务需求量与优先级。
20.步骤2：无人机组网距离模型构建模块。设定关于无人机组网执行中继服务的模型假设，其中，1)假设灾区地面区域为二维平面，其间存在若干随机分布的用户节点；2)假设无人机无线传输范围为，可覆盖以无线传输范围r为半径的地面圆形区域(其中r为无人机最大通信距离，h为无人机飞行高度)，而无人机机间是否能够互相通信，则由它们的欧式距离与r的大小关系进行判断；
21.关于地面用户区域与无人机集群给出如下定义，将待服务区域的二维平面o上分布的用户离散化为用户节点s1,s2,...,sk，||s||＝k，k为用户群节点数量。每个用户节点在二维平面上的位置为sk,(xk,yk)，k＝1,2,
…
,k。同理，无人机可离散化为无人机节点u1,u2,...,un,||u||＝n，n为无人机数量。每架无人机的位置为ui,(xi,yi,hi)，i＝1,2,
…
,n。一基站节点q存在在区域外近处(xq,yq)；
22.对于任意一个无人机节点ui，可计算出其对地面的无线传输范围计算所有无人机节点的无线传输范围，获得传输范围矩阵如下：
23.ri＝[r
1 r
2 ... rn]
ꢀꢀꢀ
(1)对于任意两个无人机节点ui,uj，节点间的欧式距离为
计算所有无人机节点间的欧式距离，建立无人机间的欧式距离矩阵，
[0024][0025]
当d
ij
＞r，即无人机间欧式距离大于无人机最大通信距离，则无人机间无法通信；反之，则无人机间可以通信。
[0026]
步骤3：无人机组网通信模型构建模块。在二维任务平面o内，假设每个用户需要传输的任务带宽为g，目标区域内总用户人数为p，设置二维平面内用户概率分布密度ρ(x,y)以表征整个用户区域内用户分布的密集程度，其中，
[0027][0028]
在用户群节点(xk,yk)处，用户需要传输服务的总带宽量为，
[0029]
y(xk,yk)＝gpρ(xk,yk)
ꢀꢀꢀ
(4)
[0030]
为了模拟实际灾难环境下用户服务优先级的情况，设置优先级函数η(x,y)，表示整个用户区域内每个用户集中节点的服务优先级程度，其中，
[0031][0032]
针对y(x,y)，η(x,y)进行快速非支配排序和拥挤度排序从而得到综合后的降序排列，在进行中继服务的过程中，对综合排序在上数据包的进行优先传输。
[0033]
在二维平面o内，无人机ui与平面内用户群节点的覆盖关系为其中，
[0034][0035]
在无人机ui的覆盖区域内，用户需要的服务带宽总量为，
[0036][0037]
设定无人机ui提供服务能力为ai，其中分配给其覆盖区域的为bi，为了不造成无人机有限的服务资源浪费，影响到无人机间通信质量，无人机分配给覆盖区域服务资源需要小于等于区域内用户需要的最大通信资源。则有，bi≤bi，bi＜ai。
[0038]
在无人机ui的覆盖区域内，为了模拟实际业务传输的情况，将所有用户群节点对应的y(x,y)降序排序，在实际业务传输过程中，根据业务带宽需求量的大小从高到低进行传输。根据上述内容，对于无人机ui的覆盖区域内，用户服务覆盖率为，
[0039]ci
＝bi/biꢀꢀꢀ
(8)对于整个无人机组网通信系统，总覆盖率为，
[0040][0041]
网络拓扑关系可根据dijkstra算法计算得到每个无人机节点到基站的通信跳数，无人机到基站跳数矩阵如下：
[0042]
n＝[n
1 n
2 ... nn]
ꢀꢀꢀ
(10)
[0043]
通信网络中的数据包传输依据olsr路由协议进行传输。由此我们可以得到起始节点向下一跳节点链路的负载。以z
ij
表示无人机节点ui和uj之间的链路通断关系。
[0044][0045]
记无人机节点ui和uj之间的链路负载为x
ij
，则有，
[0046][0047]
其中，l＝1,2,
…
,n。基于上述内容，可以得到无人机通信网络的链路负载为，
[0048][0049]
依据无人机集群连接度v和系统最大链路长度l表征，无人机集群连接度v越大，系统最大链路长度l越短，则系统稳定性和鲁棒性越强。
[0050]
对于单架无人机ui，它的连接度为cnti，由网络拓扑关系可以得到系统总连接度，
[0051][0052]
同理，得到无人机组网最大链路长度为l。
[0053]
步骤4：评价指标与优化目标函数构建模块。建立如下优化目标，
[0054][0055]
其中，f为优化函数，w1,w2,w3,w4表示权重参数，t为转置符号。
[0056]
步骤5：优化算法模块。将无人机拓扑关系矩阵和无人机带宽分配策略由数据串ω＝{ω1ω2...ωf…
ωm}，其中，m为数据串总长度。ω1到ωf表示无人机拓扑的通断关系，0为链路无法通信，1为链路正常通信。如无人机u1的带宽分配为b1＝20*ωf+21*ω
f+1
+
…
+26*ω
f+7
，其余无人机的分配数值类似。
[0057]
建立初始种群，并计算种群内各个个体对应的优化函数值。利用nsga-ii算法的快速非支配排序方法对种群进行快速分层，使得优良的个体更加接近于pareto前沿。拥挤度则由目标空间上的每一点与同层相邻两点之间的局部拥挤距离来计算，可以保持个体的多样性。
[0058]
对于排序后的种群，将优化函数值高的数据串与优化函数值高的数据串进行交叉变异操作。对于两个数据串，与交叉点为β。其中，表
示第t个数据串上的第e个数据点的值，该值在0,1之间取整。
[0059]
引入混沌序列x(α+1)＝4x(α)(1-x(α))(x(α+1)为混沌映射，α为自变量)改进交叉节点β的选取，则有，
[0060]
β＝[100*x(α+1)+2]
ꢀꢀꢀ
(16)
[0061]
交叉后的新数据串为，
[0062][0063]
在交叉后的数据串中随机选取2到m之间的三个数s,q,g，在满足设定的变异概率时，对这三个点的数据进行变异，具体变异过程如下，
[0064][0065]
s,q,g对应的数据值的变异次数为满足变异概率的数值。
[0066]
步骤6：最优拓扑关系与带宽分配策略提取模块。根据优化函数不断进行多目标优化过程，得到最优的决策解。
[0067]
本发明的实验结果如图2所示。其中，硬件环境为：cpu i7-12700h@2.30ghz，内存24g，一共对16个无人机节点进行拓扑关系与带宽分配策略进行优化。图2展示了拓扑关系优化结果。图中，圆点表示无人机节点，菱形表示基站，从图2可以看出在拓扑关系与带宽分配策略的优化过程中，组网尽可能地保持自身的稳定性和鲁棒性。基于无人机组网的性能指标可知，最优拓扑关系具有良好的链路稳定性和鲁棒性特征，并且在长时间工作过程中具有更好的能耗效果。
[0068]
本发明的无人机组网拓扑关系与带宽分配优化模型能够有效表征无人机通信组网的多通信性能指标，解决多性能优化下的难点。在进行模型求解时，结合高维多目标优化的问题，改进传统nsga-ii算法，能够在求解过程中保证算法精度并减少收敛次数，减缓收敛压力。
[0069]
本发明提供了一种基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略，具体实现该技术方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。

技术特征：
1.一种基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略，其特征在于，包括如下步骤：步骤1，获取无人机飞行高度、部署位置、最大提供服务带宽；获取地面区域用户数量、业务需求量与业务优先级；步骤2，建立考虑无人机执行灾区中继通信任务的距离模型，确定无人机执行中继任务的模型假设；步骤3，建立考虑无人机组网通信性能的通信模型，确定无人机通信组网优化策略的评价指标；步骤4，根据评价指标，确定优化目标；步骤5，设计改进nsga-ii算法，根据olsr路由协议的参考路由求取多目标优化效果最优的无人机组网拓扑关系与带宽分配优化策略集合作为最优策略。2.根据权利要求1所述的基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略，其特征在于，步骤2包括：步骤2-1，设定关于无人机组网执行中继服务的模型假设，其中，1)假设灾区地面区域为二维平面，其间存在若干随机分布的用户节点；2)假设无人机无线传输范围为，可覆盖以无线传输范围r为半径的地面圆形区域，其中r为无人机最大通信距离，h为无人机飞行高度，而无人机机间是否能够互相通信，则由它们的欧式距离与r的大小关系进行判断；步骤2-2，关于地面用户区域与无人机集群给出如下定义，将待服务区域的二维平面o上分布的用户离散化为用户节点s1,s2,...,s
k
，||s||＝k，k为用户群节点数量；每个用户节点在二维平面上的位置为s
k
,(x
k
,y
k
)，k＝1,2,
…
,k；同理，无人机可离散化为无人机节点u1,u2,...,u
n
,||u||＝n，n为无人机数量；每架无人机的位置为u
i
,(x
i
,y
i
,h
i
)，i＝1,2,
…
,n；一基站节点q存在在区域外近处(x
q
,y
q
)；步骤2-3，对于任意一个无人机节点u
i
，计算出其对地面的无线传输范围计算所有无人机节点的无线传输范围，获得传输范围矩阵如下：r
i
＝[r
1 r
2 ... r
n
]
ꢀꢀꢀꢀꢀꢀꢀ
(1)步骤2-4，对于任意两个无人机节点u
i
,u
j
，节点间的欧式距离为计算所有无人机节点间的欧式距离，建立无人机间的欧式距离矩阵，当d
ij
＞r，即无人机间欧式距离大于无人机最大通信距离，则无人机间无法通信；反之，则无人机间可以通信。3.根据权利要求2所述的基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优
化策略，其特征在于，步骤3包括：步骤3-1，在二维任务平面o内，假设每个用户需要传输的任务带宽为g，目标区域内总用户人数为p，设置二维平面内用户概率分布密度ρ(x,y)以表征整个用户区域内用户分布的密集程度，其中，在用户群节点(x
k
,y
k
)处，用户需要传输服务的总带宽量为：y(x
k
,y
k
)＝gpρ(x
k
,y
k
)
ꢀꢀꢀꢀꢀꢀ
(4)步骤3-2，设置优先级函数η(x,y)，表示整个用户区域内每个用户集中节点的服务优先级程度，其中，针对y(x,y)，η(x,y)进行快速非支配排序和拥挤度排序从而得到综合后的降序排列，在进行中继服务的过程中，对综合排序在上数据包的进行优先传输；步骤3-3，在二维平面o内，无人机u
i
与平面内用户群节点的覆盖关系为其中，在无人机u
i
的覆盖区域内，用户需要的服务带宽总量为，设定无人机u
i
提供服务能力为a
i
，其中分配给其覆盖区域的为b
i
，无人机分配给覆盖区域服务资源需要小于等于区域内用户需要的最大通信资源；则有，b
i
≤b
i
，b
i
＜a
i
；在无人机u
i
的覆盖区域内，将所有用户群节点对应的y(x,y)降序排序，根据业务带宽需求量的大小从高到低进行传输；对于无人机u
i
的覆盖区域内，用户服务覆盖率为，c
i
＝b
i
/b
i
ꢀꢀꢀꢀꢀ
(8)对于整个无人机组网通信系统，总覆盖率为，步骤3-4，网络拓扑关系可根据dijkstra算法计算得到每个无人机节点到基站的通信跳数，无人机到基站跳数矩阵如下：n＝[n
1 n
2 ... n
n
]
ꢀꢀꢀꢀꢀꢀ
(10)通信网络中的数据包传输依据olsr路由协议进行传输；由此得到起始节点向下一跳节点链路的负载；以z
ij
表示无人机节点u
i
和u
j
之间的链路通断关系；记无人机节点u
i
和u
j
之间的链路负载为x
ij
，则有，
其中，l＝1,2,
…
,n；基于上述内容，得到无人机通信网络的链路负载为，步骤3-5，依据无人机集群连接度v和系统最大链路长度l表征，无人机集群连接度v越大，系统最大链路长度l越短，则系统稳定性和鲁棒性越强；对于单架无人机u
i
，它的连接度为cnt
i
，由网络拓扑关系可得到系统总连接度，同理，得到无人机组网最大链路长度为l。4.根据权利要求3所述的基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略，其特征在于，步骤4包括：步骤4-1，建立如下优化目标，其中，f为优化函数，w1,w2,w3,w4表示权重参数，t为转置符号。5.根据权利要求4所述的基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略，其特征在于，步骤5包括：步骤5-1，将无人机拓扑关系矩阵和无人机带宽分配策略由数据串ω＝{ω1ω2...ω
f
…
ω
m
}，其中，m为数据串总长度；ω1到ω
f
表示无人机拓扑的通断关系，0为链路无法通信，1为链路正常通信；步骤5-2，建立初始种群，并计算种群内各个个体对应的优化函数值；利用nsga-ii算法的快速非支配排序方法对种群进行分层，拥挤度则由目标空间上的每一点与同层相邻两点之间的局部拥挤距离来计算；步骤5-3，对于排序后的种群，将优化函数值高的数据串与优化函数值高的数据串进行交叉变异操作；对于两个数据串，与交叉点为β；其中，表示第t个数据串上的第e个数据点的值，该值在0,1之间取整；引入混沌序列x(α+1)＝4x(α)(1-x(α))改进交叉节点β的选取，x(α+1)为混沌映射，α为自变量，则有，β＝[100*x(α+1)+2]
ꢀꢀꢀꢀꢀꢀ
(16)交叉后的新数据串为，步骤5-4，在交叉后的数据串中随机选取2到m之间的三个数s,q,g，在满足设定的变异概率时，对这三个点的数据进行变异，具体变异过程如下，
s,q,g对应的数据值的变异次数为满足变异概率的数值；步骤5-5，根据优化函数不断进行多目标优化过程，得到最优的决策解。6.一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现如权利要求1-5中任一所述的基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略。7.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现如权利要求1-5中任一所述的基于改进nsga-ii算法的无人机组网拓扑关系与带宽分配优化策略。

技术总结
本发明公开了一种基于改进NSGA-II算法的无人机组网拓扑关系与带宽分配优化策略，包括以下步骤：建立考虑无人机集群组网的通信性能模型，确定模型的约束条件和优化目标；基于OLSR路由协议，考虑问题特征生成通信链路中的参考路由；结合用户业务需求覆盖率、链路负载和稳定性使用改进NSGA-II算法对无人机网络拓扑关系及带宽分配策略集合进行评估，得到最优策略。本发明得到的无人机网络拓扑关系及带宽分配策略考虑了用户业务需求覆盖率、链路负载和稳定性，能够满足未来无人机任务条件下的通信性能要求，同时能减小算法收敛次数，缓解高维多目标优化的收敛压力。维多目标优化的收敛压力。维多目标优化的收敛压力。


技术研发人员：杨力 陈润州 黄琦龙 迟成
受保护的技术使用者：南京理工大学
技术研发日：2023.05.11
技术公布日：2023/8/23