二维最优持久编队通信拓扑生成方法和系统

1.本发明涉及通信技术领域，具体涉及一种二维最优持久编队通信拓扑生成方法和系统。


背景技术：

2.针对多智能体持久编队消耗的总的通信代价进行优化时，若假设智能体之间通信的能量消耗是相等的研究方法，部分智能体由于过多地进行信息发送的操作而导致能量消耗过快将导致某一些智能体由于能量低而提前退出持久编队，从而缩短了队形保持的时间。为延长队形保持的时间，现有技术中提出了非对称链接下的持久编队通信拓扑优化方法。
3.具体的，航空学报，2022，43(1):324922，公开了《能耗均衡的三维最优持久编队通信拓扑生成》的论文。该论文的持久编队通信拓扑优化方法中，首先设计了一种通信拓扑离线优化机制，可参见图1，图1为现有技术中通信拓扑离线优化机制的示意图。该优化机制可以概括为：选择一个合适的周期，在编队运动之前计算出每个周期内的通信拓扑，在编队保持队形过程中据此定期调整通信拓扑，从而避免在线计算和发布通信拓扑带来额外的通信能耗。而在离线计算每个周期内的通信拓扑时，先估计出每个周期开始时每个智能体的剩余通信能量，并据此更新网络拓扑中各通信链接的权重，再从更新后的网络拓扑中生成一个三维最优持久图作为本周期内的通信拓扑。
4.其中，上述论文的最优持久编队通信拓扑生成方法可以应用于二维持久编队中。
5.上述论文的三维最优持久图的生成是基于刚度矩阵和弧添加操作，属于一种近似求解方法。且基于上述三维最优持久图生成方法生成的三维最优持久图，仅为弧的权重之和尽可能小的三维最小持久图，而并不能确定为弧的权重之和最小的三维最优持久图。
6.因此，亟需一种二维最优持久编队通信拓扑生成方法，以获取到弧的权重之和最低的二维最优持久编队通信拓扑。


技术实现要素：

7.(一)解决的技术问题
8.针对现有技术的不足，本发明提供了一种二维最优持久编队通信拓扑生成方法和系统，用于解决现有技术中无法准确获取到弧的权重之和最低的二维最优持久编队通信拓扑的问题。
9.(二)技术方案
10.为实现以上目的，本发明通过以下技术方案予以实现：
11.在本发明的第一方面，提供了一种二维最优持久编队通信拓扑生成方法，所述方法包括:
12.s1、获取二维持久编队的初始加权有向图d；
13.s2、获取预设的二维持久编队的约束条件，并以总弧权值最低为目标函数，构建以
生成二维最优持久编队通信拓扑的整数规划模型；
14.s3、基于所述初始加权有向图d和优化求解器cplex，对所述整数规划模型进行求解，得到求解结果，并对所述求解结果的秩进行判断，得到总弧权值最低的二维最优持久编队通信拓扑；其中，在对所述整数规划模型进行求解之前，所述方法还包括基于预设规则对所述二维持久编队的领航者节点进行约束。
15.可选的，所述s1中的初始加权有向图d，包括:
16.初始加权有向图d＝(v，a，w)；
17.其中，v表示节点的集合，vi∈v，i∈[1，n]，vi表示编队中的第i个节点，n表示二维持久编队中节点的总数量；
[0018]
a表示有向边的集合，a
ij
∈a，且i，j∈[1，n]，i≠j，a
ij
表示在加权有向图中，节点vi向节点vj进行信息传递的有向边；
[0019]
w表示弧权值的集合，且i，j∈[1，n]，表示有向边a
ij
的弧权值。
[0020]
可选的，所述s2中整数规划模型为目标函数，包括:
[0021]
目标函数为:
[0022][0023]
其中，x
ij
表示节点vi是否具备向节点vj发送信息的能力，若是，则x
ij
＝1；若否，则x
ij
＝0；表示有向边a
ij
的弧权值。
[0024]
可选的，所述s2中整数规划模型的约束条件，包括:
[0025]
约束条件1、任意两个节点之间的通信是单向的；
[0026]
x
ij
+x
ji
≤1，1≤i，j≤n
[0027]
约束条件2、任意一个节点的入度小于或等于2；
[0028][0029]
约束条件3、任意节点的出度与入度的和大于或等于2；
[0030][0031]
约束条件4、弧的总数量为2n-3；
[0032][0033]
约束条件5、在二维最优持久编队中，存在某个节点为领航者，且所述领航者的入度等于0；
[0034][0035]
可选的，所述s3中，基于所述初始加权有向图d和优化求解器cplex，对所述整数规
划模型进行求解，得到求解结果，并对所述求解结果的秩进行判断，得到总弧权值最低的二维最优持久编队通信拓扑，包括:
[0036]
s301、初始化l＝1，设置预设通信拓扑作为最优解；
[0037]
s302、将所述整数规划模型中的约束条件和目标函数输入至优化求解器cplex中；
[0038]
s303、设定v
l
为二维编队通信拓扑中的领航者；
[0039]
s304、基于v
l
和优化求解器cplex，对整数规划模型进行求解，获取二维持久编队通信拓扑，作为初始拓扑；
[0040]
s305、判断所述初始拓扑的总弧权值是否小于所述最优解的总弧权值，若是，则转s306；若否，则转s307；
[0041]
s306、判断所述最优解的对应的刚度矩阵的秩是否2*n-3，若是，则将所述初始拓扑替换为最优解，转s307；若否，则直接转s307；
[0042]
s307、判断l《n是否成立，若是，则l＝l+1，转s303；若否，则转s308；
[0043]
s308、将所述最优解作为总弧权值最低的二维最优持久编队通信拓扑。
[0044]
在本发明的第二方面，提供了一种二维最优持久编队通信拓扑生成系统，所述系统包括:
[0045]
第一获取模块，用于执行s1、获取二维持久编队的初始加权有向图d；
[0046]
第一构建模块，用于执行s2、获取预设的二维持久编队的约束条件，并以总弧权值最低为目标函数，构建以生成二维最优持久编队通信拓扑的整数规划模型；
[0047]
模型求解模块，用于执行s3、基于所述初始加权有向图d和优化求解器cplex，对所述整数规划模型进行求解，得到求解结果，并对所述求解结果的秩进行判断，得到总弧权值最低的二维最优持久编队通信拓扑；其中，在对所述整数规划模型进行求解之前，所述s3还包括基于预设规则对所述二维持久编队的领航者节点进行约束。
[0048]
可选的，所述第一获取模块中的初始加权有向图d，包括:
[0049]
初始加权有向图d＝(v，a，w)；
[0050]
其中，v表示节点的集合，vi∈v，i∈[1，n]，vi表示编队中的第i个节点，n表示二维持久编队中节点的总数量；
[0051]
a表示有向边的集合，a
ij
∈a，且i，j∈[1，n]，i≠j，a
ij
表示在加权有向图中，节点vi向节点vj进行信息传递的有向边；
[0052]
w表示弧权值的集合，且i，j∈[1，n]，表示有向边a
ij
的弧权值。
[0053]
可选的，所述第一构建模块中的目标函数，包括:
[0054]
目标函数为:
[0055][0056]
其中，x
ij
表示节点vi是否具备向节点vj发送信息的能力，若是，则x
ij
＝1；若否，则x
ij
＝0；表示有向边a
ij
的弧权值。
[0057]
可选的，所述第一构建模块中的约束条件，包括:
[0058]
约束条件1、任意两个节点之间的通信是单向的；
[0059]
x
ij
+x
ji
≤1，1≤i，j≤n
[0060]
约束条件2、任意一个节点的入度小于或等于2；
[0061][0062]
约束条件3、任意节点的出度与入度的和大于或等于2；
[0063][0064]
约束条件4、弧的总数量为2n-3；
[0065][0066]
约束条件5、在二维最优持久编队中，存在某个节点为领航者，所述领航者的入度等于0；
[0067][0068]
可选的，所述模型求解模块，包括:
[0069]
初始化子模块，用于执行s301、初始化l＝1，设置预设通信拓扑作为最优解；
[0070]
第一输入子模块，用于执行s302、将所述整数规划模型中的约束条件和目标函数输入至优化求解器cplex中；
[0071]
第一设定子模块，用于执行s303、设定v
l
为二维编队通信拓扑中的领航者；
[0072]
第一求解子模块，用于执行s304、基于v
l
和优化求解器cplex，对整数规划模型进行求解，获取二维持久编队通信拓扑，作为初始拓扑；
[0073]
第一判断子模块，用于执行s305、判断所述初始拓扑的总弧权值是否小于所述最优解的总弧权值，若是，则转第二判断子模块执行s306；若否，则转第三判断子模块执行s307；
[0074]
第二判断子模块，用于执行s306、判断所述最优解的对应的刚度矩阵的秩是否2*n-3，若是，则将所述初始拓扑替换为最优解，转第三判断子模块执行s307；若否，则直接转第三判断子模块执行s307；
[0075]
第三判断子模块，用于执行s307、判断l《n是否成立，若是，则l＝l+1，转第一设定子模块执行s303；若否，则转第一设置子模块执行s308；
[0076]
第一设置子模块，用于执行s308、将所述最优解设置为总弧权值最低的二维最优持久编队通信拓扑。
[0077]
(三)有益效果
[0078]
本发明提供了一种二维最优持久编队通信拓扑生成方法和系统。与现有技术相比，具备以下有益效果：
[0079]
本发明提供的二维最优持久编队通信拓扑生成方法，获取二维持久编队的初始加权有向图d；获取预设的二维持久编队的约束条件，并以总弧权值最低为目标函数，构建以生成二维最优持久编队通信拓扑的整数规划模型；基于所述初始加权有向图d和优化求解
器cplex，对所述整数规划模型进行求解，得到求解结果，并对所述求解结果的秩进行判断，得到总弧权值最低(即，本发明中弧的权重之和最低)的二维最优持久编队通信拓扑。其中，在对所述整数规划模型进行求解之前，所述生成方法还包括基于预设规则对所述二维持久编队的领航者节点进行约束。
[0080]
基于上述处理，本发明构建了包含约束条件和目标函数的拓扑生成模型，且该拓扑生成模型为一种整数规划模型，将生成二维最优持久编队通信拓扑的非线性求解问题转化为线性求解问题，并基于对二维持久编队的领航者节点进行约束和优化求解器cplex，对整数规划模型进行求解，并对求解结果的秩进行判断，进而得到了弧的权重之和最低的二维最优持久编队通信拓扑。
附图说明
[0081]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0082]
图1为现有技术中通信拓扑离线优化机制的示意图；
[0083]
图2为本发明提供的一种二维最优持久编队通信拓扑生成方法的流程图；
[0084]
图3为本发明提供的一种二维通信拓扑优化算法的结果示意图；
[0085]
图4a为本发明提供的一种对比算法的实验结果示意图；
[0086]
图4b为本发明提供的另一种对比算法的实验结果示意图；
[0087]
图5为本发明提供的一种对比试验结果的示意图；
[0088]
图6为本发明提供的一种二维最优持久编队通信拓扑生成系统的结构图；
[0089]
图7为本发明提供的一种电子设备的结构图。
具体实施方式
[0090]
为使本发明实施例的目的、技术方案和优点更加清楚，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0091]
根据航空学报，2022，43(1):324922，《能耗均衡的三维最优持久编队通信拓扑生成》，可知在现有技术的非对称链接下的持久编队通信拓扑优化方法中，包含了一种通信拓扑离线优化机制。
[0092]
上述通信拓扑离线优化机制可以概括为：选择一个合适的周期，在编队运动之前计算出每个周期内的通信拓扑，在编队保持队形过程中据此定期调整通信拓扑，从而避免在线计算和发布通信拓扑带来额外的通信能耗。
[0093]
由于只有在通信拓扑是一个二维持久图的前提下，二维持久编队才可以保持预先设定好的队形。不同的通信链接会有不同的权重，并且当通信链接权重越小时，表示节点vi剩余的能量越大。所以要想在保持多智能体编队既定队形的前提下，使队形可以保持更长的时间，就需要降低智能体编队通信的能量总消耗，并使每个智能体剩余的能量更加均衡。
[0094]
因此，针对上述通信拓扑离线优化机制，在通信拓扑的每个生成周期内，都需要构建弧的权重之和最低的二维最优持久编队通信拓扑。
[0095]
本发明提供了一种二维最优持久编队通信拓扑生成方法和系统，该方法包括：获取二维持久编队的初始加权有向图d；获取预设的二维持久编队的约束条件，并以总弧权值最低为目标函数，构建以生成二维最优持久编队通信拓扑的整数规划模型；基于所述初始加权有向图d和优化求解器cplex，对所述整数规划模型进行求解，得到求解结果，并对所述求解结果的秩进行判断，得到总弧权值最低的二维最优持久编队通信拓扑；其中，在对所述整数规划模型进行求解之前，所述生成方法还包括基于预设规则对所述二维持久编队的领航者节点进行约束。
[0096]
基于上述处理，构建了包含约束条件和目标函数的拓扑生成模型，且该拓扑生成模型为一种整数规划模型，将生成二维最优持久编队通信拓扑的非线性求解问题转化为线性求解问题。并基于预设规则对二维持久编队的领航者节点进行约束和优化求解器cplex，对整数规划模型进行求解，对求解结果的秩进行判断，进而得到了弧的权重之和最低的二维最优持久编队通信拓扑。
[0097]
为了更好的理解上述技术方案，下面将结合说明书附图以及具体的实施方式对上述技术方案进行详细的说明。
[0098]
首先，对本发明中的相关基础概念进行介绍。
[0099]
本发明中的二维编队可以理解为应用于二维平面场景下的多智能体编队。其中，仅有自身操作的智能体被称为单一智能体环境，其优点是简单，易于控制，但缺点也很明显，即对整个智能体系统全局信息的了解不全面，应用场景过于单一，一旦损坏，将无法继续执行任务。
[0100]
相较于单智能体，多智能体编队中的智能体可以与其它的智能体通过信息交互来完成复杂的任务。例如，在车辆编队自动驾驶领域，后方跟随车辆可以根据领队车辆的指令跟随行驶，减少环境感知探测和规划线路带来的能量消耗，以延长车队行驶距离。
[0101]
在编队保持某种合作队形的过程中，通信链路是智能体之间进行通信的介质，将智能体之间的通信介质——通信链路称为通信拓扑。当多个智能体组成的编队在执行预先设定好的任务时，通常情况下，会运用到编队整体控制的技术来保证编队中的每一个智能体都处于正常的工作状态。因此，智能体之间需要点对点通信来实现信息传输。智能体之间的通信链路即为这种点对点通信，整个智能体编队中所有通信链路的集合则被称为面向编队保持的多智能体编队通信拓扑。
[0102]
此外，在二维平面内，若无向图g＝(v，e)是二维最小刚性图，需要满足以下两个条件：
[0103]
(1)g有2
×
|v|-3条边；
[0104]
(2)g对应的刚度矩阵m的秩为2
×
|v|-3。
[0105]
在二维空间中，若加权有向图d＝(v，a，w)是二维最小持久图，需要满足以下两个条件：
[0106]
(1)d中每个节点的入度小于等于2；
[0107]
(2)d对应的无向图g＝(v，e)是一个二维最小刚性图。
[0108]
在二维平面内，一个加权有向图d＝(v，a，w)是一个二维最优持久图，当且仅当其
满足以下两个条件：
[0109]
(1)d是一个二维最小持久图。
[0110]
(2)d中的各条弧的权重总和，是在具有同样节点的所有的二维最小持久图中最小的。
[0111]
多智能体编队一般是通过领航者即其中的一个智能体带领，按照预先规划好的路线行进，其余智能体则通过通信链路获取信息做出反馈。由于在两个智能体之间传输信息时，发送端的智能体由于信号放大器消耗的功率，导致通信的过程中，发送端智能体比接收端智能体的要消耗更多的能量，同时由于不同的通信距离导致不同的能量消耗，编队中的每一个智能体所剩余的能量都不一定相等。所以有必要对非对称链接下的通信拓扑进行优化，以使多智能体编队能以完整的编队形态保持更长的工作时间。
[0112]
结合图1和《能耗均衡的三维最优持久编队通信拓扑生成》的内容可知，现有技术针对非链接下的通信拓扑进行优化方法中，包含一种通信拓扑离线优化机制。其中，离线计算每个周期内的通信拓扑的过程，可以概括为：先估计出每个周期开始时每个智能体的剩余通信能量，并据此更新网络拓扑中各通信链接的权重，再从更新后的网络拓扑中生成一个最优持久图作为本周期内的通信拓扑。
[0113]
然而，现有技术对单周期内针对编队通信拓扑进行优化时，仅能够获得弧的权重之和尽可能小的最小持久图，而并不能确定为弧的权重之和最小的最优持久图。
[0114]
为解决上述问题，本发明提出了一种二维最优持久编队通信拓扑生成方法和系统。参见图2，图2为本发明提供的一种二维最优持久编队通信拓扑生成方法的流程图，如图2所示，该方法包括以下步骤：
[0115]
s1、获取二维持久编队的初始加权有向图d。
[0116]
s2、获取预设的二维持久编队的约束条件，并以总弧权值最低为目标函数，构建以生成二维最优持久编队通信拓扑的整数规划模型。
[0117]
s3、基于所述初始加权有向图d和优化求解器cplex，对所述整数规划模型进行求解，得到求解结果，并对所述求解结果的秩进行判断，得到总弧权值最低的二维最优持久编队通信拓扑。其中，在对所述整数规划模型进行求解之前，所述生成方法还包括基于预设规则对所述二维持久编队的领航者节点进行约束。
[0118]
其中，本发明实施例设定共n个智能体，通过智能体之间的单向通信以形成并保持一个二维的编队队形s，该编队队形s中n个位置分别编号为{1，2，
…
，n}。节点即为多智能体编队中的智能体。
[0119]
基于上述处理，本发明构建了包含约束条件和目标函数的拓扑生成模型，且该拓扑生成模型为一种整数规划模型，将生成二维最优持久编队通信拓扑的非线性求解问题转化为线性求解问题，并基于对二维持久编队的领航者节点进行约束和优化求解器cplex，对整数规划模型进行求解，并对求解结果的秩进行判断，进而得到了弧的权重之和最低的二维最优持久编队通信拓扑。
[0120]
针对步骤s1，二维持久编队中所有的节点的链接组成了对应的网络拓扑，可以用加权有向图d＝(v，a，w)表示。在上述通信拓扑离线优化机制中，将单通信拓扑生成周期内最初的加权有向图，作为初始加权有向图。
[0121]
其中，v表示节点的集合，vi∈v，i∈[1，n]，vi表示编队中的第i个节点，n表示二维
持久编队中节点的总数量。
[0122]
a表示有向边的集合，a
ij
∈a，且i，j∈[1，n]，i≠j，a
ij
表示在加权有向图中，节点vi向节点vj进行信息传递的有向边。
[0123]
w表示弧权值的集合，且i，j∈[1，n]，表示有向边a
ij
的弧权值。在本发明实施例中，可以将两节点之间的距离近似作为弧权值。
[0124]
针对步骤s2，目标函数为：
[0125][0126]
其中，x
ij
表示节点vi是否具备向节点vj发送信息的能力，若是，则x
ij
＝1；若否，则x
ij
＝0。表示有向边a
ij
的弧权值。
[0127]
预设的二维持久编队的约束条件，包括：
[0128]
约束条件1、任意两个节点之间的通信是单向的；
[0129]
x
ij
+x
ji
≤1，1≤i，j≤n
[0130]
约束条件2、任意一个节点的入度小于或等于2；
[0131][0132]
约束条件3、任意节点的出度与入度的和大于或等于2；
[0133][0134]
约束条件4、弧的总数量为2n-3；
[0135][0136]
约束条件5、在二维最优持久编队中，存在某个节点为领航者，且所述领航者的入度等于0；
[0137][0138]
针对步骤s3，基于计算机对二维持久编队的领航者节点进行约束和优化求解器cplex，对整数规划模型进行求解，并对求解结果的秩进行判断，进而计算机得到了弧的权重之和最低的二维最优持久编队通信拓扑。
[0139]
在一些实施例中，步骤s3可以包括以下内容：
[0140]
s301、初始化l＝1，设置预设通信拓扑作为最优解。值得注意的是，预设通信拓扑对应的总弧权值的数值对应非常大，以保证后续步骤s304得到初始拓扑的总弧权值小于该预设通信拓扑的总弧权值。
[0141]
s302、将所述整数规划模型中的约束条件和目标函数输入至优化求解器cplex中。
[0142]
s303、设定v
l
为二维编队通信拓扑中的领航者。
[0143]
s304、基于v
l
和优化求解器cplex，对整数规划模型进行求解，获取二维持久编队通信拓扑，作为初始拓扑。
[0144]
s305、判断所述初始拓扑的总弧权值是否小于所述最优解的总弧权值，若是，则转s306；若否，则转s307。
[0145]
s306、判断所述最优解的对应的刚度矩阵的秩是否2*n-3，若是，则将所述初始拓扑替换为最优解，转s307；若否，则直接转s307。
[0146]
s307、判断l《n是否成立，若是，则l＝l+1，转s303；若否，则转s308；
[0147]
s308、将所述最优解作为总弧权值最低的二维最优持久编队通信拓扑。
[0148]
其中，步骤s303、s307中对领航者的处理内容，可以对应理解为步骤s3中的“基于预设规则对二维持久编队的领航者节点进行约束”。
[0149]
此外，针对基于优化求解器cplex对整数规划模型进行求解，发明人设计了一种非对称链接下的二维通信拓扑优化算法，如下所示。
[0150]
[0151]
[0152][0153]
一种实现方式中，基于上述算法和优化求解器cplex，计算机对整数规划模型进行求解，从而得到二维最优持久编队通信拓扑。
[0154]
基于上述处理，本发明提供了一种非对称链接下的二维持久编队通信拓扑的优化方法。通过这个方法，可以降低智能体编队的总体能量消耗，并使编队中的每一个智能体在通信方面的能量消耗得到平衡，可以获得更长的队形保持时间，以完成更多、更复杂的任务。
[0155]
具体的，本发明提出了一个整数规划模型，将现有技术中的非线性模型转化为线性模型，从现有研究模型的只能求出近似最优解优化为可以求得最优解，并且设计了求解算法，求得最优解，相比以往算法降低了编队通信消耗。
[0156]
由于二维持久编队中各智能体间的通信链路组成了通信拓扑，故可以用加权有向图t＝(v，a*，w*)，表示最终的二维最优持久编队；a*表示该二维最优持久编队有向边的集合；w*表示二维最优持久编队弧权值的集合。
[0157]
其中，vi为节点，其中vi∈v，i∈[1，n]，表示编队中的第i个智能体。
[0158]
aij为有向边，其中aij∈a*，i，j∈[1，n]∩i≠j，表示在智能体vi和向智能体vj间存在一条可以进行数据传输的通信链路，即智能体vi可以向智能体vj发送信息。
[0159]
w(t)是通信拓扑的总通信代价，计算公式如下:
[0160][0161]
结合《能耗均衡的三维最优持久编队通信拓扑生成》和本发明的技术方案，发明人构建了一种用于非对称链接下的二维持久编队通信拓扑优化方法，以降低多智能体编队的总体能量消耗，并使编队中的每一个智能体在通信方面的能量消耗得到平衡，获得更长的队形保持时间。
[0162]
根据《能耗均衡的三维最优持久编队通信拓扑生成》内容可见，本发明中非对称链接下的二维持久编队通信拓扑优化方法，包含一个离线的二维持久编队的通信拓扑的优化模型。其原理如下，在编队运行前，根据剩余的能量，可以根据链接的权重，将提前设计好的每一个周期内的通信拓扑，发送给编队中的每一个智能体。于是，在智能体行进过程当中，按照每个周期来调整通信拓扑，自动切换成相应的通信拓扑。优化模型的具体流程可参见图1。
[0163]
其中，智能体剩余通信能量估计的方法包括以下内容：
[0164][0165]
其中，ei表示单位时间内智能体vi消耗的能量大小：e
t
(l
ij
，d
ij
)为单位时间内智能体vi向智能体vj在发送信息的动作中消耗的能量大小；er(l
ji
，d
ji
)为单位时间智能体vi从智
能体vj在接收信息的动作中消耗的能量大小；l
ij
表示智能体vi单位时间向智能体vj发送信息的大小，单位为比特；d
ij
为智能体vi和智能体vj的通信距离；l
ji
表示智能体vj单位时间向智能体vi发送信息的大小，单位为比特；d
ji
为智能体vj和智能体vi的通信距离。
[0166]
计算e
t
(l
ij
，d
ij
)的公式如下
[0167][0168]
其中，e
elec
为常量，其值的大小取决于滤波、调制和数字编码和等多种因素；d0表示预设的通信距离阈值；ε
fris
和ε
amp
也为常量，其值的大小由接收机的灵敏系数和和噪声系数决定。
[0169]
计算er(l
ji
，d
ji
)的公式如下
[0170]er
(l
ji
，d
ji
)＝l
jieelec
[0171]
其中，l
ji
为智能体vi单位时间从智能体vj接收信息的体积，单位为比特；智能体vj和智能体vi的通信距离为d
ji
(数值上与d
ij
是相等的)。
[0172]
关于智能体剩余能量估计的方法为
[0173]ri
(u+1)＝ri(u)-ei(u)
×u[0174]
其中，ri(u+1)为第u+1个周期开始时智能体vi的剩余通信能量；ri(u)为第u个周期开始时智能体vi的剩余通信能量；ei(u)为单位时间内第u个周期中，智能体vi在通信方面所消耗的能量；字母u表示每一周期的长度，以秒(s)为单位。
[0175]
不同的智能体在保持队形的过程中，在发送和接收消息时会消耗不同的能量，不同的通信距离也会导致不同的能量消耗。由于智能体编队保持队形行进的时间越长，各个智能体剩余能量的差异就会越大，为了延长智能体编队保持队形的时间，就要降低剩余能量低的智能体的通信链接的权重，因此本发明的智能体编队网络拓扑中的通信权重更新的方法。
[0176]
该通信权重更新的公式如下所示：
[0177][0178]
其中，w(a
ij
)表示弧a
ij
的权重。可知，当vi的剩余能量ri(u)越小时，将会对应越大的vi发送链接a
ij
的权重。
[0179]
此外，当节点vi和节点vj所剩下的能量不一样时，可以推出如下公式：
[0180][0181]
由上述公式可知，节点vi和节点vj彼此之间的消息都可以接收到，但该两个节点间进行通信的连接的权重是不相等的，故通信链接是非对称的。
[0182]
本发明提出的二维最优持久编队通信拓扑生成方法，可以用于单周期内通信拓扑c生成，从而获取到总弧权值最低的二维最优持久编队通信拓扑，以降低智能体编队的总体能量消耗，并使编队中的每一个智能体在通信方面的能量消耗得到平衡，可以获得更长的队形保持时间。
[0183]
针对本发明的技术方案，发明人分别进行了不同的对比实验，包括针对单周期内
通信拓扑生成算法的对比文件1和针对非对称链接下通信拓扑优化方法的对比实验2。
[0184]
在对比试验中，发明人引入了如下对比对象，包括3dopg-ra算法、luo算法和wjr算法。其中，luo算法和wjr算法都是针对对称链接的情况进行设计，即认为通信的收发双方所消耗的能量是相等的，因此wjr算法和luo算法，都是直接将弧的权重与边的权重划等号。而3dopg-ra算法则认为，智能体编队中的通信链接是非对称的，wjr算法和luo算法在弧的权重的处理上的思路是不同的。
[0185]
因此，对于wjr算法和luo算法，需要重新设计转换策略，使弧的权重转换为边的权重。故发明人在wjr算法和luo算法的基础上，设计了不同的三类
[0186]
转换策略。
[0187]
第一类策略是在比较正向弧的权重和反向弧的权重中，选择较小的弧权重认
[0188]
为是对应的边权重，分别将其命名为wjr-min算法和luo-min算法；
[0189]
第二类策略是在正向弧和反向弧的权重比较过程中，选择较大的弧的权重认
[0190]
为是对应的边权重，分别将其命名为wjr-max算法和luo max算法；
[0191]
第三类策略是在比较正向弧和反向弧的权重中，随机选择一个正向弧或者反向弧，认为是对应的边的权重，分别将其命名为wjr-random算法和
[0192]
luo-random算法。
[0193]
值得注意的是，与上面提到的方法均有所不同的是，本发明通过将非线性求
[0194]
解问题转化为线性求解问题建模，使用cplex进行求解，进而选择最优解输出。
[0195]
针对单周期内通信拓扑生成算法的对比试验1，内容如下。
[0196]
设定有一个包含5节点的加权有向图，d＝(v，a，w)。其中，v＝
[0197]
{v1，v2，v3，v4，v5}，
[0198]
a＝
[0199]
{a
12
，a
13
，a
14
，a
15
，a
21
，a
23
，a
24
，a
25
，a
31
，a
32
，a
34
，a
35
，a
41
，a
42
，a
43
，a
45
，a
51
，{0.76，0.07，0.1，0.67，0.69，0.67，0.7，0.71，0.88，0.27，0.11，0.69，0.11，0.56，0.31。
[0200]
基于本发明的二维通信拓扑优化算法，对上述加权有向图进行求解。参见图3，
[0201]
图3为本发明提供的一种二维通信拓扑优化算法的结果示意图。如图3所示，可
[0202]
见其最优解为以节点5为领航者，w(c)＝1.93。
[0203]
基于不同的对比算法，对上述加权有向图进行求解。参见图4a、图4b，图4a
[0204]
为本发明提供的一种对比算法的实验结果示意图，图4b为本发明提供的另一种对
[0205]
比算法的实验结果示意图。
[0206]
如图4a所示，基于3dopg-ra算法得到的最优解中w(c)＝2.08；基于luo max算法得到的最优解中w(c)＝3.66；基于luo-random算法得到的最优解中
[0207]
w(c)＝3.85；基于luo-min算法得到的最优解中w(c)＝3.85。
[0208]
如图4b所示，基于wjr-max算法得到的最优解中w(c)＝3.21；基于wjr-random算法得到的最优解中w(c)＝2.20；基于wjr-min算法得到的最优解中w(c)＝2.20。
[0209]
基于对比试验1的结果，可知本发明的二维通信拓扑优化算法所得的最优解优于其它算法。
[0210]
针对非对称链接下通信拓扑优化方法的对比试验2。
[0211]
在对比试验2中，将u＝40s作为编队的离线拓扑更新周期的时间长度，以5节点作
为研究样本，来判断不同的算法是如何影响队形的保持时长。
[0212]
针对于每一种节点的数量，在大小为103×
103的二维平面中随机生成对应智能体节点数量的节点的坐标，以5节点进行6组队形的实验，每一组的队形分别通过上述提到的7组对比算法以及本文算法共8种算法来进行实验，记录下在不同算法下，每一组队形保持的平均时间。
[0213]
假定在实验开始前，每一个智能体都拥有ri＝2j的能量，在智能体编队队形的保持过程中，智能体通信在单位时间内需要发送大小为l
ij
＝1000的信息量，其它参数如下：e
elec
＝50nj/bit、ε
fris
＝10pj/bit/m2、ε
amp
＝0.001pj/bit/m4、d0＝2000m。
[0214]
参见图5，图5为本发明提供的一种对比试验结果的示意图。在5节点数量情况下，在不同算法下，每一组队形保持的平均时间如图5所示。可见，基于本发明技术方案所生成的通信拓扑能够使智能体编队的保持队形的时间得到延长
[0215]
通过对于对比实验1、对比实验2的实验结果的分析可知，基于本发明的二维持久编队通信拓扑优化方法，可以获取到总弧值更低的二维最优持久编队通信拓扑，使得二维持久编队通信的能量消耗降低，从而延长了二维持久编队保持队形的时间。
[0216]
基于相同的发明构思，本发明还提供了一种二维最优持久编队通信拓扑生成系统。参见图6，图6为本发明实施例提供的一种二维最优持久编队通信拓扑生成系统的结构图，如图6所示，该系统可以包括：
[0217]
第一获取模块601，用于执行s1、获取二维持久编队的初始加权有向图d。
[0218]
第一构建模块602，用于执行s2、获取预设的二维持久编队的约束条件，并以总弧权值最低为目标函数，构建以生成二维最优持久编队通信拓扑的整数规划模型。
[0219]
模型求解模块603，用于执行s3、基于所述初始加权有向图d和优化求解器cplex，对所述整数规划模型进行求解，得到求解结果，并对所述求解结果的秩进行判断，得到总弧权值最低的二维最优持久编队通信拓扑；其中，在对所述整数规划模型进行求解之前，s3所述生成方法还包括基于预设规则对所述二维持久编队的领航者节点进行约束。
[0220]
可理解的是，本发明实施例提供的二维最优持久编队通信拓扑生成系统与上述二维最优持久编队通信拓扑生成方法相对应，其有关内容的解释、举例、有益效果等部分可以参照二维最优持久编队通信拓扑生成方法中的相应内容，此处不再赘述。
[0221]
本发明实施例还提供了一种电子设备，参见图7，图7为本发明提供的一种电子设备的结构图，如图7所示，包括处理器701、通信接口702、存储器703和通信总线704，其中，处理器701，通信接口702，存储器703通过通信总线704完成相互间的通信，
[0222]
存储器703，用于存放计算机程序；
[0223]
处理器701，用于执行存储器703上所存放的程序时，实现上述任一二维最优持久编队通信拓扑生成方法。
[0224]
上述电子设备提到的通信总线可以是外设部件互连标准(peripheral component interconnect，pci)总线或扩展工业标准结构(extended industry standard architecture，eisa)总线等。该通信总线可以分为地址总线、数据总线、控制总线等。为便于表示，图中仅用一条粗线表示，但并不表示仅有一根总线或一种类型的总线。
[0225]
通信接口用于上述电子设备与其他设备之间的通信。
[0226]
存储器可以包括随机存取存储器(random access memory，ram)，也可以包括非易
失性存储器(non-volatile memory，nvm)，例如至少一个磁盘存储器。可选的，存储器还可以是至少一个位于远离前述处理器的存储装置。
[0227]
上述的处理器可以是通用处理器，包括中央处理器(central processing unit，cpu)、网络处理器(network processor，np)等；还可以是数字信号处理器(digital signal processor，dsp)、专用集成电路(application specific integrated circuit，asic)、现场可编程门阵列(field-programmable gate array，fpga)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件。
[0228]
在本发明提供的又一实施例中，还提供了一种计算机可读存储介质，该计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行时实现上述任一二维最优持久编队通信拓扑生成方法的步骤。
[0229]
在本发明提供的又一实施例中，还提供了一种包含指令的计算机程序产品，当其在计算机上运行时，使得计算机执行上述实施例中任一二维最优持久编队通信拓扑生成方法。
[0230]
在上述实施例中，可以全部或部分地通过软件、硬件、固件或者其任意组合来实现。当使用软件实现时，可以全部或部分地以计算机程序产品的形式实现。所述计算机程序产品包括一个或多个计算机指令。在计算机上加载和执行所述计算机程序指令时，全部或部分地产生按照本发明实施例所述的流程或功能。所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。所述计算机指令可以存储在计算机可读存储介质中，或者从一个计算机可读存储介质向另一个计算机可读存储介质传输，例如，所述计算机指令可以从一个网站站点、计算机、服务器或数据中心通过有线(例如同轴电缆、光纤、数字用户线(dsl))或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输。所述计算机可读存储介质可以是计算机能够存取的任何可用介质或者是包含一个或多个可用介质集成的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质，(例如，软盘、硬盘、磁带)、光介质(例如，dvd)、或者半导体介质(例如固态硬盘solid state disk(ssd))等。
[0231]
综上所述，与现有技术相比，具备以下有益效果：
[0232]
1、本发明构建了包含约束条件和目标函数的拓扑生成模型，且该拓扑生成模型为一种整数规划模型，将生成二维最优持久编队通信拓扑的非线性求解问题转化为线性求解问题，并基于对二维持久编队的领航者节点进行约束和优化求解器cplex，对整数规划模型进行求解，并对求解结果的秩进行判断，进而得到了弧的权重之和最低的二维最优持久编队通信拓扑。
[0233]
2、基于本发明技术方案所构建的非对称链接下的二维通信拓扑优化方法，可以有效降低了编队通信消耗，从而延长了二维持久编队保持队形的时间。
[0234]
需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在
包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。
[0235]
以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

技术特征：
1.一种二维最优持久编队通信拓扑生成方法，其特征在于，所述方法包括:s1、获取二维持久编队的初始加权有向图d；s2、获取预设的二维持久编队的约束条件，并以总弧权值最低为目标函数，构建以生成二维最优持久编队通信拓扑的整数规划模型；s3、基于所述初始加权有向图d和优化求解器cplex，对所述整数规划模型进行求解，得到求解结果，并对所述求解结果的秩进行判断，得到总弧权值最低的二维最优持久编队通信拓扑；其中，在对所述整数规划模型进行求解之前，所述方法还包括基于预设规则对所述二维持久编队的领航者节点进行约束。2.根据权利要求1所述的方法，其特征在于，所述s1中的初始加权有向图d，包括:初始加权有向图d＝(v，a，w)；其中，v表示节点的集合，v
i
∈v，i∈[1，n]，v
i
表示编队中的第i个节点，n表示二维持久编队中节点的总数量；a表示有向边的集合，a
ij
∈a，且i，j∈[1，n]，i≠j，a
ij
表示在加权有向图中，节点v
i
向节点v
j
进行信息传递的有向边；w表示弧权值的集合，且i，j∈[1，n]，i≠j，表示有向边a
ij
的弧权值。3.根据权利要求1所述的方法，其特征在于，所述s2中整数规划模型的目标函数，包括:目标函数为:其中，x
ij
表示节点v
i
是否具备向节点v
j
发送信息的能力，若是，则x
ij
＝1；若否，则x
ij
＝0；表示有向边a
ij
的弧权值。4.根据权利要求1所述的方法，其特征在于，s2中整数规划模型的约束条件，包括:约束条件1、任意两个节点之间的通信是单向的；x
ij
+x
ji
≤1，1≤i，j≤n约束条件2、任意一个节点的入度小于或等于2；约束条件3、任意节点的出度与入度的和大于或等于2；约束条件4、弧的总数量为2n-3；约束条件5、在二维最优持久编队中，存在某个节点为领航者，且所述领航者的入度等于0；
5.根据权利要求1所述的方法，其特征在于，所述s3中，基于初始加权有向图d和优化求解器cplex，对整数规划模型进行求解，得到求解结果，并对求解结果的秩进行判断，得到总弧权值最低的二维最优持久编队通信拓扑，包括:s301、初始化l＝1，设置预设通信拓扑作为最优解；s302、将所述整数规划模型中的约束条件和目标函数输入至优化求解器cplex中；s303、设定v
l
为二维编队通信拓扑中的领航者；s304、基于v
l
和优化求解器cplex，对整数规划模型进行求解，获取二维持久编队通信拓扑，作为初始拓扑；s305、判断所述初始拓扑的总弧权值是否小于所述最优解的总弧权值，若是，则转s306；若否，则转s307；s306、判断所述最优解对应的刚度矩阵的秩是否2*n-3，若是，则将所述初始拓扑替换为最优解，转s307；若否，则直接转s307；s307、判断l<n是否成立，若是，则l＝l+1，转s303；若否，则转s308；s308、将所述最优解作为总弧权值最低的二维最优持久编队通信拓扑。6.一种二维最优持久编队通信拓扑生成系统，其特征在于，所述系统包括:第一获取模块，用于执行s1、获取二维持久编队的初始加权有向图d；第一构建模块，用于执行s2、获取预设的二维持久编队的约束条件，并以总弧权值最低为目标函数，构建以生成二维最优持久编队通信拓扑的整数规划模型；模型求解模块，用于执行s3、基于所述初始加权有向图d和优化求解器cplex，对所述整数规划模型进行求解，得到求解结果，并对所述求解结果的秩进行判断，得到总弧权值最低的二维最优持久编队通信拓扑；其中，在对所述整数规划模型进行求解之前，s3还包括基于预设规则对所述二维持久编队的领航者节点进行约束。7.根据权利要求6所述的系统，其特征在于，所述第一获取模块中的初始加权有向图d，包括:初始加权有向图d＝(v，a，w)；其中，v表示节点的集合，v
i
∈v，i∈[1，n]，v
i
表示编队中的第i个节点，n表示二维持久编队中节点的总数量；a表示有向边的集合，a
ij
∈a，且i，j∈[1，n]，i≠j，a
ij
表示在加权有向图中，节点v
i
向节点v
j
进行信息传递的有向边；w表示弧权值的集合，且i，j∈[1，n]，i≠j，表示有向边α
ij
的弧权值。8.根据权利要求6所述的系统，其特征在于，所述第一构建模块中的目标函数，包括:目标函数为:其中，x
ij
表示节点v
i
是否具备向节点v
j
发送信息的能力，若是，则x
ij
＝1；若否，则x
ij
＝0；表示有向边a
ij
的弧权值。
9.根据权利要求6所述的系统，其特征在于，所述第一构建模块中的约束条件，包括:约束条件1、任意两个节点之间的通信是单向的；x
ij
+x
ji
≤1，1≤i，j≤n约束条件2、任意一个节点的入度小于或等于2；约束条件3、任意节点的出度与入度的和大于或等于2；约束条件4、弧的总数量为2n-3；约束条件5、在二维最优持久编队中，存在某个节点为领航者，所述领航者的入度等于0；10.根据权利要求6所述的系统，其特征在于，所述模型求解模块，包括:初始化子模块，用于执行s301、初始化l＝1，设置预设通信拓扑作为最优解；第一输入子模块，用于执行s302、将所述整数规划模型中的约束条件和目标函数输入至优化求解器cplex中；第一设定子模块，用于执行s303、设定v
l
为二维编队通信拓扑中的领航者；第一求解子模块，用于执行s304、基于v
l
和优化求解器cplex，对整数规划模型进行求解，获取二维持久编队通信拓扑，作为初始拓扑；第一判断子模块，用于执行s305、判断所述初始拓扑的总弧权值是否小于所述最优解的总弧权值，若是，则转第二判断子模块执行s306；若否，则转第三判断子模块执行s307；第二判断子模块，用于执行s306、判断所述最优解的对应的刚度矩阵的秩是否2*n-3，若是，则将所述初始拓扑替换为最优解，转第三判断子模块执行s307；若否，则直接转第三判断子模块执行s307；第三判断子模块，用于执行s307、判断l<n是否成立，若是，则l＝l+1，转第一设定子模块执行s303；若否，则转第一设置子模块执行s308；第一设置子模块，用于执行s308、将所述最优解设置为总弧权值最低的二维最优持久编队通信拓扑。

技术总结
本发明提供了一种二维最优持久编队通信拓扑生成方法和系统，涉及通信技术领域，方法包括：获取二维持久编队的初始加权有向图D；获取预设的二维持久编队的约束条件，并以总弧权值最低为目标函数，构建以生成二维最优持久编队通信拓扑的整数规划模型；基于初始加权有向图D和优化求解器CPLEX，对整数规划模型进行求解，得到求解结果，并对求解结果的秩进行判断，得到总弧权值最低的二维最优持久编队通信拓扑。基于上述处理，将生成二维最优持久编队通信拓扑的非线性求解问题转化为线性求解问题，并基于优化求解器CPLEX对拓扑生成模型进行求解，以及对求解结果的秩进行判断，得到弧的权重之和最低的二维最优持久编队通信拓扑。重之和最低的二维最优持久编队通信拓扑。重之和最低的二维最优持久编队通信拓扑。


技术研发人员：王国强 薛山 王天宇 程诚 阮以升 刘舒彤 应梓晨
受保护的技术使用者：合肥工业大学
技术研发日：2023.04.07
技术公布日：2023/7/28