基于匹配博弈的无人机群多跳中继路径优选算法*

曾弘扬，安思璇

（陆军工程大学 通信工程学院，江苏 南京 210007）

0 引言

无人机集群是由众多无人机单机构成的群体，基于信息交互和群体智能技术，可在危险、恶劣环境中自主协同完成多类复杂任务[1]。无人机群在执行数据采集等集群任务时，需要将采集的数据及时准确地传输至远距离的地面遥控中心。由于单个无人机传输距离有限，通常需要多跳中继以保障传输性能[2]。无人机群具有分布式组网、高机动性、能量受限等典型特点，因此在局部信息交互下实现自组织多跳中继节点优选，同时尽可能提升无人机群能量效率是中继传输优化必须实现的目标。

匹配博弈理论作为一种数学工具[1]，主要用于对具有矛盾的双边决策者进行建模分析，近年来在协同频谱共享[3]、微蜂窝D2D 通信[4]等网络模型得到了广泛关注，是解决分布式无线资源优化的有效方法。中继节点优选问题很适合利用匹配博弈进行建模分析，源节点和中继节点分别基于不同的优化目标设计自身的偏好函数，构建匹配列表，实现分布式节点互选。不同于其他博弈模型，匹配博弈的优化目标一般为稳定匹配，非常适合无人机群这种高动态网络的快速稳定优化。目前，利用匹配博弈进行的中继选择研究主要集中在协同通信[5]、基站选择[6-8]等场景，典型特点是只需进行一跳范围内的节点优选。在多跳中继传输的研究中，文献[9-10]提出了分布式多跳节点选择算法，但算法不具稳健性，无法适应拓扑动态变化的无人机群协同网络。文献[11-12]研究了分层匹配模型，但只是简单地将单层的匹配重复应用至多层网络，无法保障多跳中继传输的全局性能。

因此，本文以无人机集群的网络能量效率为优化目标，基于匹配博弈理论提出了一种分布式多跳中继路径优选算法。所提算法仅需要邻域范围内的无人机位置信息，即可获得接近全局最优的多跳传输性能。仿真结果表明，所提算法能够适应不同的网络拓扑，收敛迅速，非常适合高动态的无人机群通信场景。

1 系统模型

本文研究的系统模型如图1 所示。无人机群在执行侦察等数据采集任务时，源节点无人机需要在动态变化的网络拓扑中自主选择合适的多跳中继路径，将数据及时回传给地面遥控中心。假设网络中有N个有数据传输需求的源节点，M个可提供中继传输的中继节点。无人机均装配半双工单天线，发射功率可调，中继传输采用译码转发方式。本文所提算法需要获知邻域范围内无人机的位置信息，而为了实现自主飞行控制，集群网络中的无人机均会周期性地在邻域范围内广播包含自身地理位置的飞行控制信息。假设源节点sn(n=1,2,…,N)的数据经由K跳传输到达地面遥控中心d，即需要依次选择K-1 个中继节点。为了统一标记，将多跳中继链路sn→d上的所有节点依次记为rn(0),rn(1),…,rn(k)，其中rn(0)表示源节点sn(0)，rn(K)表示目的节点d。则多跳中继链路sn→d的传输容量[13]为：

图1 系统模型

所以，全网能量效率最大的多跳中继路径选择优化问题可以表示为：

其中，第一条约束条件表示无人机之间的连接关系是一对一的，第二条约束条件中表示多跳中继链路sn→d上第k+1 个节点能够正确解调时第k个节点的最小发射功率门限，Pmax表示最大发射功率限制。

在式（6）描述的多跳链路优选S 问题中，可以利用匹配博弈模型实现邻域节点之间的互选。匹配博弈模型可以表示为：

其中，(S,R) 表示两组决策者；qi,qj(i∈S,j∈R)表示每一决策者所能匹配的最大节点数，称为匹配配额；≻i,≻j(i∈S,j∈R)分别表示决策者(S,R)的偏好关系，用于对另一方的用户进行排序，构建匹配偏好列表。可见，构建合适的偏好关系对节点的匹配选择非常重要。在无人机集群网络中，节点一般仅根据邻域范围内无人机的状态信息建立偏好关系，很难优选出全局能量效率最优的多跳链路。因此，本文首先对全局最优的多跳中继节点位置进行了分析证明，并基于此设计了匹配博弈中的偏好关系。

2 能量效率最优的中继节点位置

假设网络中每个节点的解调信干噪比门限均为γTH，路径损耗指数m>0，噪声方差为σ2，表示节点rn(k-1)到节点rn(k)的距离，本文主要考虑大尺度损耗对发射功率的影响，则：

其中(xn(k),yn(k),zn(k))(k=0,1,…,K-1)表示节点的地理位置坐标。若每个发射节点均以功率传输数据，则：

其中θn(k,K+1)表示节点rn(k)到节点rn(k+1)的向量和源节点sn到目的节点d的向量之间的夹角，Drn(0)→rn(K)表示源节点sn到目的节点d的直线距离。从式（8）的推导过程可以看出，在多跳中继链路sn→d上，当K-1 个中继节点刚好在的K个均分点位置时，整条链路可以达到最大的能量效率。本文根据这个结论设计了匹配博弈的偏好关系，寻找sn→d链路上距离最优中继节点最近的无人机中继数据，仅通过邻域范围内的位置信息交互实现了接近全局最优的多跳中继传输性能。

3 偏好关系建模

将多跳传输中有数据需要发送的节点称为发送方，即节点rn(k)(k=0,1,2,…,K-1)；接收数据的节点称为接收方，即节点rn(k+1)(k=0,1,2,…,K-1)。在rn(k)→rn(k+1)的节点匹配博弈中，偏好关系设计如下。

3.1 发送方的偏好

为了提高全网的能量效率，发送方在设计偏好关系时考虑两个因素。一个是倾向于选择在其一跳范围内的多个节点中选择距离最优中继节点位置最近节点；二是在候选节点中剔除掉距离最优中继节点过远的节点，以提高匹配效率。因此，发送方选择下一跳中继节点的偏好规则为：

发送方根据偏好关系对可选择的下一跳中继节点排序，选择偏好列表中最优的中继节点rn(k+1)发出中继申请，同时将的值发送给选中的节点。

3.2 接收方的偏好

为了提高全网的能量效率，接收方更倾向于在提出中继申请的节点中选择值最小的发送方，其偏好规则为：

接收方根据上述偏好规则建立自身的匹配列表，选择最优的发送方同意其中继请求。

4 多跳中继节点交换匹配算法

基于所设计的偏好关系，本文提出了一种多跳中继路径优选算法。所提算法采用交换匹配[12]的思想，分为链路计算、匹配发现和匹配交换3个阶段。同时，采用多档功率传输，即如果在多跳链路匹配过程中某一节点无法以当前发射功率匹配到合适的下一跳节点，则该链路的源节点会提高发射功率重新进行多跳匹配尝试。这样发送方能够通过增大发射功率扩大选择范围，保证了源节点到目的节点的连通性。无人机群多跳中继路径优选算法的具体流程如下。

初始化：集群网络中每一个无人机在邻域范围内周期性广播自己的地理位置信息，设置功率档位i=0，设置跳数k=0。

步骤1：链路计算

（1）设置发射功率档位i=i+1；

（2）第n个源节点根据当前功率档位、自身和目的基站的位置，判断所需中继跳数，并计算最优中继节点的位置。

步骤2：匹配发现

（1）K=K+1；

（2）发送方rn(k-1)根据式（11）的偏好规则建立下一跳节点的偏好列表，挑选最优节点发送匹配申请，同时将、多跳链路中最优中继节点位置以及功率档位信息携带发送。

步骤3：匹配交换

（1）接收方rn(k)根据式（12）进行偏好排序，对提交申请的发送方建立偏好列表，选择最优的发送方接受匹配申请；

（2）如果接收方已有连接，则根据式（12）判断新申请匹配的发送方效用值是否大于已有连接的效用值，如果是，接收方同意发送方的匹配请求，匹配结果进行交换；否则，接收方拒绝请求，匹配结果保持不变；

（3）匹配请求被拒绝的发送方将依次选择偏好列表中的次优节点发送匹配请求；直到发送方rn(k-1)和接收方rn(k)的匹配关系稳定不变，交换匹配结束。

（4）如果发送方所有匹配请求均被拒绝，则通过已建立的链路将失败信息返回给源节点，重复步骤1；否则，重复步骤2，直到sn→d的多跳中继链路匹配成功。

5 仿真结果与分析

本文从集群规模、源节点数量、中继节点数量、门限因子α共4 个角度对所提出的多跳链路优选算法进行仿真分析。仿真中，固定源节点在网络左侧边缘均匀分布，目的节点在网络右侧中点，中继节点在网络内部随机分布。如果发送方已达到最大发射功率仍无法形成有效多跳链路，则匹配失败。主要仿真参数如表1 所示。

表1 仿真参数表

5.1 网络覆盖范围对算法性能的影响

仿真中，设源节点数N=4，中继节点数M=50，门限因子α=0.3。图2（a）、图2（b）分别为网络覆盖范围500 m×500 m、2 000 m×2 000 m 时，基于所提算法4 个源节点获得的多跳传输路径。可以看出，所提算法能够根据网络覆盖范围的大小以不同发射功率自主匹配多跳路径。在如图2（b）所示的远距离通信场景中，更愿意通过增加跳数来提升多跳链路的能量效率。

图2 不同网络规模下的网络连接拓扑

5.2 源节点数量对算法性能的影响

仿真中，设网络覆盖范围为1 000 m×1 000 m，中继节点数M=50，门限因子α=0.3。图3（a）、图3（b）、图3（c）分别为源节点数量N为2、4和6 时基于所提算法源节点获得的多跳传输路径。可以看出，源节点数量增大后，所提算法依然可以有效支持源节点寻找到多跳路径。但是，由于竞争增大，部分链路可能由于某个中继申请被拒绝而被迫寻找次优的路径，符合算法设计预期。

图3 不同源节点数量下的网络连接拓扑

5.3 中继节点数量对算法性能的影响

仿真中，设网络覆盖范围为1 000 m×1 000 m，源节点数N=4，门限因子α=0.3。图4（a）、图4（b）、图4（c）分别为中继节点数M为8、32 和128 时基于所提算法源节点获得的多跳传输路径。可以看出，当中继节点数量较小时，源节点难以找到合适的中继节点，可能会选择直连链路；当中继节点数量增大时，源节点会有更高的概率发现合适的中继节点，更倾向于选择多跳传输提升能量效率。

图4 不同中继节点数量下的网络连接拓扑

5.4 门限因子α 对算法性能的影响

仿真中，设网络覆盖范围500 m×500 m，源节点数N=4，中继节点数M=50。图5 仿真了不同的α对网络能量效率的影响。若α过小，发送方提出匹配申请的条件过于严格，很难匹配到合适的中继节点，最终可能会选择直传链路，导致能量效率降低；而α过大时，发送方提出匹配申请的条件放宽，可能会选到性能较差的中继节点，最终也会导致能量效率降低。所以，从图5 可以看出，门限因子α存在一个最优值。通过多种网络拓扑的仿真发现，α取0.3 附近比较合适。

图5 不同门限因子α 下的网络能量效率

6 结语

本文以无人机集群的网络能量效率为优化目标，分析证明了多跳链路中最优中继位置的存在性，在此基础上利用匹配博弈理论，提出了一种基于分布式多跳中继路径优选算法。所提算法仅需要邻域范围内的无人机位置信息，即可获得接近全局最优的多跳传输性能。仿真结果表明，所提算法能够适应不同的网络拓扑，且收敛迅速，非常适合高动态的无人机群通信场景。