一种基于联盟博弈的航空动态网络路径规划方法

摘要

本发明提供一种基于联盟博弈的航空动态网络路径规划方法；首先，获取航空动态网络图，计算航空网络拓扑关系变化率，选取时间间隔，根据选取的时间间隔将航空动态网络图转换为多幅静态网络拓扑图；其次，根据静态网络拓扑图中每个飞机节点与其邻居节点间的欧式距离，对静态网络拓扑图进行简化；最后，基于简化的静态网络拓扑图，通过飞机节点相互合作建立联盟结构，以传输流量和延迟时间为博弈规则，规划出航空网络中的传输路径。本发明更有效地利用了航空网络中的闲置资源，并且确保了航空通信的可靠性和有效性。

权利要求

1.一种基于联盟博弈的航空动态网络路径规划方法，其特征在于，包括：

获取航空动态网络图，计算航空网络拓扑关系变化率，选取时间间隔，根据选取的时间间隔将航空动态网络图转换为多幅静态网络拓扑图；

根据静态网络拓扑图中每个飞机节点与其邻居节点间的欧式距离，对所述静态网络拓扑图进行简化；

基于简化的静态网络拓扑图，通过飞机节点相互合作建立联盟结构，以传输流量和延迟时间为博弈规则，规划出航空网络中的传输路径。

2.如权利要求1所述的基于联盟博弈的航空动态网络路径规划方法，其特征在于，获取航空动态网络图，计算航空网络拓扑关系变化率，选取时间间隔，根据选取的时间间隔将航空动态网络图转换为多幅静态网络拓扑图，包括：根据航班飞行数据计算航班的航迹数据，构建航空动态网络图；

根据预设时间间隔将航空动态网络图划分为多个时间段内的静态网络图；

根据视距传播规则，形成多个静态网络图的初始结构，计算在每个时间段内的航空网络拓扑关系变化率；

当航空网络拓扑关系变化率大于等于预设阈值时，继续细分时间段，重新对航空动态网络图进行划分，直到每个时间段内的航空网络拓扑关系变化率小于预设阈值时，选取此时的时间间隔将航空动态网络图转换为多幅静态网络拓扑图，保证每个时间段内的航空网络拓扑关系相对保持不变。

3.如权利要求2所述的基于联盟博弈的航空动态网络路径规划方法，其特征在于，所述航班飞行数据包括:航班号、出发地、目的地及对应经纬度、出发时间，以及到达时间；所述航迹数据包括：航班整个航程中的经纬度、飞行高度、飞行速度，以及飞行时间。

4.如权利要求3所述的基于联盟博弈的航空动态网络路径规划方法，其特征在于，所述出发时间、到达时间，以及飞行时间均统一用UTC表示；所述航班飞行数据为飞机飞行的24小时航班数据信息。

5.如权利要求1所述的基于联盟博弈的航空动态网络路径规划方法，其特征在于，所述根据静态网络拓扑图中每个飞机节点与其邻居节点间的欧式距离，对所述静态网络拓扑图进行简化，包括：在静态网络拓扑图中的每一飞机节点周边划分扇形区域；每一扇形区域内的节点为该扇形区域对应的飞机节点的邻居节点；

计算各飞机节点的邻居节点与该飞机节点之间的欧式距离；

保留各扇形区域内欧式距离最小的邻居节点，同时删除该扇形区域内的其他邻居节点，从而形成简化后的航空网络拓扑结构。

6.如权利要求5所述的基于联盟博弈的航空动态网络路径规划方法，其特征在于，在静态网络拓扑图中的每一飞机节点周边划分扇形区域，具体为：选取其中一飞机节点，以选取的飞机节点为中心，最大通信距离为半径画圆，将所画的圆以α为参数，划分成n个扇形区域；其中，α表示预设角度，n＝2π/α，且n的取值为整数；

所述计算各飞机节点的邻居节点与该飞机节点之间的欧式距离，具体为：

通过该飞机节点所在的位置坐标和其邻居节点所在的位置坐标，计算该飞机节点的每个扇形区域内的邻居节点与该飞机节点之间的角度angle，并根据角度angle将对应的邻居节点划分到相应的扇形区域内；

在每一邻居节点均划分到相应的扇形区域内后，计算出该飞机节点每一扇形区域内的每一邻居节点与该飞机节点的欧氏距离。

7.如权利要求1所述的基于联盟博弈的航空动态网络路径规划方法，其特征在于，基于简化的静态网络拓扑图，通过飞机节点相互合作建立联盟结构，以传输流量和延迟时间为博弈规则，规划出航空网络中的传输路径，包括：基于简化的静态网络拓扑图，选取一段时间内形成的航空互联网，在初始时间设定一部分飞机节点为目的节点De，其余的飞机节点作为中继节点Re，形成数据传输路径；其中每个飞机节点先随机选择基站接入，若某一飞机节点的通信范围内没有基站，则不进行连接，形成初始联盟结构；

根据初始联盟结构的包传输成功率和延迟时间计算其总效益；

随机改变所述初始联盟结构中某些De的连接，如果De在当前时刻搜索不到可连接节点时，则进行等待，连接下一时段内通信范围内的Re；由De搜索周边可连接或下一时段可连接的邻居节点，从而生成新的数据传输路径，进而形成新的联盟结构；

根据新的联盟结构的包传输成功率和延迟时间计算其总效益；并将新的联盟结构的总效益和初始联盟结构的总效益进行对比；

若新的联盟结构总效益相比于初始联盟结构有所增加，则保存当前形成的航空网络连接，并且记录当前联盟结构的总效益；若新的联盟结构的总效益相比于初始联盟结构没有增加，则再次随机改变其中飞机节点之间的连接，再次形成新的联盟结构，所有的De不断重复这一过程直至不再发生任何转移为止，最终形成一个稳定的联盟结构。

8.如权利要求7所述的基于联盟博弈的航空动态网络路径规划方法，其特征在于，联盟结构的总效益的表达式如下：其中，u(Gini)表示联盟结构Gini的总效益，PSR(Gini)表示联盟结构Gini的包传输成功率，delay(Gini)表示联盟结构Gini的延迟时间，β为预设常量。

9.如权利要求8所述的基于联盟博弈的航空动态网络路径规划方法，其特征在于，整个联盟结构的延迟时间为联盟结构中每条路径传输数据所需时间和等待连接的时间之和，延迟时间的计算公式如下：其中，delay为延迟时间，data为每个目的节点接收的数据量，i，j为链接的两飞机节点，ratei，j为两节点i，j之间的最大信息传送速率，wait为等待连接的时间；

ratei，j由香农公式得出，其计算公式如下：

ratei，j＝Bw*log2(1+SNRi，j)

其中，Bw为信道带宽，SNRi，j为路径中两节点i，j传输数据的信号与噪声之比，SNRi，j的具体计算公式如下：SNRi，j＝PDD-20*lg(distancei，j)-20*lg(fc)+147.5-5-Noise-Bw其中，PDD为传输功率，distancei，j为两节点i，j之间的距离，fc为工作频率，Noise为传输过程中的噪音干扰，Bw为信道带宽。

10.如权利要求7所述的基于联盟博弈的航空动态网络路径规划方法，其特征在于，在所述由De搜索周边可连接或下一时段可连接的邻居节点，从而生成新的数据传输路径，进而形成新的联盟结构之后，所述方法还包括：对新的联盟结构中的各条路径情况进行检查，当共用同一中继节点的目的节点的数量超过预设上限值时，对相应路径进行调整。

说明书

一种基于联盟博弈的航空动态网络路径规划方法

技术领域

[0001] 本发明涉及航空网络技术领域，特别是指一种基于联盟博弈的航空动态网络路径规划方法。

背景技术

[0002] 移动通信和互联网接入已成为当今社会重要组成部分。近年来，商业航空公司正在尝试在客舱内提供互联网接入和蜂窝网络连接服务，由此催生了首批基于卫星的飞行信息服务提供商，包括Boeing、OnAir、AeroMobile和Panasonic。特别是跨洲的航空飞行，通常会穿越海洋和偏远区域，如大片水域、沙漠、极地等地区，这些地区很难在地面部署通信基础设施，大多通过卫星提供航空旅客的信息服务，但由于卫星通信的成本和时延都较大，因此航空互联网(Airborne lnternet)应运而生，例如美国的AirCell，通过A2A(Air-to-Air)通信链路提供更快和更便宜的信息服务。

[0003] 航空互联网是飞机通过直接空对空(A2A)通信链路形成的自组织无线网络，具有高移动性，传输范围广，三维空间等特性。在地面基站通信范围内的飞机接入地面基站网络，使得覆盖范围从近海扩展到海洋或远程空域。通过让飞机本身充当网络路由器中继站，在空中形成网状网络。在跨洋飞行中，飞机可以通过使用空中互联网作为到地面基础设施的桥梁，继而保持连接，从而绕过昂贵的卫星链路。从航空公司的角度来看，避免卫星连接可以大大降低通信成本。与地球同步卫星相比，另一个潜在的好处是减少了延迟，支持对延迟敏感的应用程序，如语音和视频会议。对于一颗地球静止卫星，信号从卫星到地面基站，需要大约250毫秒的单向端到端传输延迟。而航空互联网通过使用适当的服务质量(QoS)机制，如资源预留或分组优先级，可以提供较低的端到端延迟保证。但现有的航空网络依然存在不能有效利用航空网络中的闲置资源的问题。

发明内容

[0004] 本发明要解决的技术问题是提供一种基于联盟博弈的航空动态网络路径规划方法，解决现有的航空网络不能有效利用航空网络中的闲置资源的问题。

[0005] 为解决上述技术问题，本发明提供一种基于联盟博弈的航空动态网络路径规划方法，该基于联盟博弈的航空动态网络路径规划方法包括：

[0006] 获取航空动态网络图，计算航空网络拓扑关系变化率，选取时间间隔，根据选取的时间间隔将航空动态网络图转换为多幅静态网络拓扑图；

[0007] 根据静态网络拓扑图中每个飞机节点与其邻居节点间的欧式距离，对所述静态网络拓扑图进行简化；

[0008] 基于简化的静态网络拓扑图，通过飞机节点相互合作建立联盟结构，以传输流量和延迟时间为博弈规则，规划出航空网络中的传输路径。

[0009] 其中，获取航空动态网络图，计算航空网络拓扑关系变化率，选取时间间隔，根据选取的时间间隔将航空动态网络图转换为多幅静态网络拓扑图，包括：

[0010] 根据航班飞行数据计算航班的航迹数据，构建航空动态网络图；

[0011] 根据预设时间间隔将航空动态网络图划分为多个时间段内的静态网络图；

[0012] 根据视距传播规则，形成多个静态网络图的初始结构，计算在每个时间段内的航空网络拓扑关系变化率；

[0013] 当航空网络拓扑关系变化率大于等于预设阈值时，继续细分时间段，重新对航空动态网络图进行划分，直到每个时间段内的航空网络拓扑关系变化率小于预设阈值时，选取此时的时间间隔将航空动态网络图转换为多幅静态网络拓扑图，保证每个时间段内的航空网络拓扑关系相对保持不变。

[0014] 其中，所述航班飞行数据包括：航班号、出发地、目的地及对应经纬度、出发时间，以及到达时间；所述航迹数据包括：航班整个航程中的经纬度、飞行高度、飞行速度，以及飞行时间。

[0015] 其中，所述出发时间、到达时间，以及飞行时间均统一用UTC表示；所述航班飞行数据为飞机飞行的24小时航班数据信息。

[0016] 其中，所述根据静态网络拓扑图中每个飞机节点与其邻居节点间的欧式距离，对所述静态网络拓扑图进行简化，包括：

[0017] 在静态网络拓扑图中的每一飞机节点周边划分扇形区域；每一扇形区域内的节点为该扇形区域对应的飞机节点的邻居节点；

[0018] 计算各飞机节点的邻居节点与该飞机节点之间的欧式距离；

[0019] 保留各扇形区域内欧式距离最小的邻居节点，同时删除该扇形区域内的其他邻居节点，从而形成简化后的航空网络拓扑结构。

[0020] 其中，在静态网络拓扑图中的每一飞机节点周边划分扇形区域，具体为：

[0021] 选取其中一飞机节点，以选取的飞机节点为中心，最大通信距离为半径画圆，将所画的圆以α为参数，划分成n个扇形区域；其中，n＝2π/α；

[0022] 所述计算各飞机节点的邻居节点与该飞机节点之间的欧式距离，具体为：

[0023] 通过该飞机节点所在的位置坐标和其邻居节点所在的位置坐标，计算该飞机节点的每个扇形区域内的邻居节点与该飞机节点之间的角度angle，并根据角度angle将对应的邻居节点划分到相应的扇形区域内；

[0024] 在每一邻居节点均划分到相应的扇形区域内后，计算出该飞机节点每一扇形区域内的每一邻居节点与该飞机节点的欧氏距离。

[0025] 其中，基于简化的静态网络拓扑图，通过飞机节点相互合作建立联盟结构，以传输流量和延迟时间为博弈规则，规划出航空网络中的传输路径，包括：

[0026] 基于简化的静态网络拓扑图，选取一段时间内形成的航空互联网，在初始时间设定一部分飞机节点为目的节点De，其余的飞机节点作为中继节点Re，形成数据传输路径；其中每个飞机节点先随机选择基站接入，若某一飞机节点的通信范围内没有基站，则不进行连接，形成初始联盟结构；

[0027] 根据初始联盟结构的包传输成功率和延迟时间计算其总效益；

[0028] 随机改变所述初始联盟结构中某些De的连接，如果De在当前时刻搜索不到可连接节点时，则进行等待，连接下一时段内通信范围内的Re；由De搜索周边可连接或下一时段可连接的邻居节点，从而生成新的数据传输路径，进而形成新的联盟结构；

[0029] 根据新的联盟结构的包传输成功率和延迟时间计算其总效益；并将新的联盟结构的总效益和初始联盟结构的总效益进行对比；

[0030] 若新的联盟结构总效益相比于初始联盟结构有所增加，则保存当前形成的航空网络连接，并且记录当前联盟结构的总效益；若新的联盟结构的总效益相比于初始联盟结构没有增加，则再次随机改变其中飞机节点之间的连接，再次形成新的联盟结构，所有的De不断重复这一过程直至不再发生任何转移为止，最终形成一个稳定的联盟结构。

[0031] 其中，联盟结构的总效益的表达式如下：

[0032]

[0033] 其中，u(Gini)表示联盟结构Gini的总效益，PSR(Gini)表示联盟结构Gini的包传输成功率，delay(Gini)表示联盟结构Gini的延迟时间，β为预设常量。

[0034] 其中，整个联盟结构的延迟时间为联盟结构中每条路径传输数据所需时间和等待连接的时间之和，延迟时间的计算公式如下：

[0035]

[0036] 其中，delay为延迟时间，data为每个目的节点接收的数据量，i，j为链接的两飞机节点，ratei，j为两节点i，j之间的最大信息传送速率，wait为等待连接的时间；

[0037] ratei，j由香农公式得出，其计算公式如下：

[0038] ratei，j＝Bw*log2(1+SNRi，j)

[0039] 其中，Bw为信道带宽，SNRi，j为路径中两节点i，j传输数据的信号与噪声之比，SNRi，j的具体计算公式如下：

[0040] SNRi，j＝PDD-20*lg(distancei，j)-20*lg(fc)+147.5-5-Noise-Bw[0041] 其中，PDD为传输功率，distancei，j为两节点i，j之间的距离，fc为工作频率，Noise为传输过程中的噪音干扰，Bw为信道带宽。

[0042] 其中，在所述由De搜索周边可连接或下一时段可连接的邻居节点，从而生成新的数据传输路径，进而形成新的联盟结构之后，所述方法还包括：

[0043] 对新的联盟结构中的各条路径情况进行检查，当共用同一中继节点的目的节点的数量超过预设上限值时，对相应路径进行调整。

[0044] 本发明的上述技术方案的有益效果如下：

[0045] 本发明通过获取航空动态网络图，计算航空网络拓扑关系变化率，选取时间间隔，根据选取的时间间隔将航空动态网络图转换为多幅静态网络拓扑图；根据静态网络拓扑图中每个飞机节点与其邻居节点间的欧式距离，对静态网络拓扑图进行简化；基于简化的静态网络拓扑图，通过飞机节点相互合作建立联盟结构，以传输流量和延迟时间为博弈规则，规划出航空网络中的传输路径。更有效地利用了航空网络中的闲置资源，且确保了航空通信的可靠性和有效性。

附图说明

[0046] 图1为本发明第一实施例提供的基于联盟博弈的航空动态网络路径规划方法的流程示意图；

[0047] 图2为本发明第二实施例提供的某一时刻飞机的实际分布图；

[0048] 图3为本发明第二实施例提供的根据视距规则形成的初始航空网络图；

[0049] 图4为本发明第二实施例提供的简化完的航空网络图；

[0050] 图5为本发明第二实施例提供的中继站buffer为20Mb，带宽为1MHz的情况下形成稳定联盟博弈的整个迭代过程示意图；

[0051] 图6为本发明第二实施例提供的中继站buffer为20Mb，带宽为1MHz的情况下不同时隙(1min和3m in)的效益函数变化情况示意图；

[0052] 图7为本发明第二实施例提供的带宽为1MHz时隙为3min情况下，中继站buffer变化过程中形成的联盟效益函数的变化示意图；

[0053] 图8为本发明第二实施例提供的中继站buffer为20mb时隙为3min情况下，带宽变化所形成的联盟效益函数值。

具体实施方式

[0054] 为使本发明要解决的技术问题、技术方案和优点更加清楚，下面将结合附图及具体实施例进行详细描述；应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。

[0055] 首先航空互联网中飞机节点飞行距离远，航线分布广，单跳通信半径可达上百公里，航线上或航线交叉附近的飞机节点密度较大，因此形成的航空互联网拓扑链接较为复杂。因此需要对其进行拓扑优化和控制，删除掉冗余的通信链路。这一操作可以避免不必要的能量消耗，节约节点资源，方便后续的路由选择。其次航空互联网中飞机节点并不是做随机运动，而是沿着航线飞行，高动态性是航空网络的一大特点，因此飞机节点在无法直接连接到基站的情况下，飞机节点之间可以通过A2A链路直接共享数据，交换各自的飞行状态，链路情况等信息，构建一个更加稳定的A2A通信网络。最后在航空动态网中例如跨洋航班形成的航空网络，飞机距离地面基站较远的情况下，设定一部分飞机为中继站，通过飞机节点进行数据传输，将航空互联网链路链接及信息共享转换为所有A2A节点参与的联盟博弈，以时延和包传输成功率为效益函数，规划航空互联网传输路径，最大化效益函数。

[0056] 下面以具体实施例的方式进一步对本发明的方案进行说明：

[0057] 第一实施例

[0058] 请参阅图1，本实施例提供一种基于联盟博弈的航空动态网络路径规划方法，该基于联盟博弈的航空动态网络路径规划方法包括：

[0059] S101，获取航空动态网络图，计算航空网络拓扑关系变化率，选取时间间隔，根据选取的时间间隔将航空动态网络图转换为多幅静态网络拓扑图；

[0060] S102，根据静态网络拓扑图中每个飞机节点与其邻居节点间的欧式距离，对静态网络拓扑图进行简化；

[0061] S103，基于简化的静态网络拓扑图，通过飞机节点相互合作建立联盟结构，以传输流量和延迟时间为博弈规则，规划出航空网络中的传输路径。

[0062] 其中，上述S101包括如下步骤：

[0063] 根据24小时的航班飞行数据计算航班的航迹数据，构建航空动态网络图；其中，航班飞行数据包括：航班号、出发地、目的地及对应经纬度、出发时间，以及到达时间等；航迹数据包括：航班整个航程中的经纬度、飞行高度、飞行速度，以及飞行时间等，其中的时间均统一用UTC表示；

[0064] 根据预设时间间隔将航空动态网络图划分为多个时间段内的静态网络图；

[0065] 根据视距传播规则，形成多个静态网络图的初始结构，计算在每个时间段内的航空网络拓扑关系变化率；

[0066] 当航空网络拓扑关系变化率大于等于预设阈值时，继续细分时间段，重新对航空动态网络图进行划分，直到每个时间段内的航空网络拓扑关系变化率小于预设阈值时，选取此时的时间间隔将航空动态网络图转换为多幅静态网络拓扑图，保证每个时间段内的航空网络拓扑关系相对保持不变。

[0067] 上述S102包括如下步骤：

[0068] 在静态网络拓扑图中的每一飞机节点周边划分扇形区域；每一扇形区域内的节点为该扇形区域对应的飞机节点的邻居节点；

[0069] 计算各飞机节点的邻居节点与该飞机节点之间的欧式距离；

[0070] 保留各扇形区域内欧式距离最小的邻居节点，同时删除该扇形区域内的其他邻居节点，从而形成简化后的航空网络拓扑结构。

[0071] 其中，在静态网络拓扑图中的每一飞机节点周边划分扇形区域，具体为：

[0072] 选取其中一飞机节点，以选取的飞机节点为中心，最大通信距离为半径画圆，将所画的圆以α为参数，划分成n个扇形区域；其中，n＝2π/α；

[0073] 计算各飞机节点的邻居节点与该飞机节点之间的欧式距离，具体为：

[0074] 通过该飞机节点所在的位置坐标和其邻居节点所在的位置坐标，计算该飞机节点的每个扇形区域内的邻居节点与该飞机节点之间的角度angle，并根据角度angle将对应的邻居节点划分到相应的扇形区域内；

[0075] 在每一邻居节点均划分到相应的扇形区域内后，计算出该飞机节点每一扇形区域内的每一邻居节点与该飞机节点的欧氏距离。

[0076] 上述S103包括如下步骤：

[0077] 基于简化的静态网络拓扑图，选取一段时间内形成的航空互联网，在初始时间设定一部分飞机节点为目的节点De，其余的飞机节点作为中继节点Re，形成数据传输路径；其中每个飞机节点先随机选择基站接入，若某一飞机节点的通信范围内没有基站，则不进行连接，形成初始联盟结构；

[0078] 根据初始联盟结构的包传输成功率和延迟时间计算其总效益；

[0079] 随机改变初始联盟结构中某些De的连接，如果De在当前时刻搜索不到可连接节点时，则进行等待，连接下一时段内通信范围内的Re；由De搜索周边可连接或下一时段可连接的邻居节点，从而生成新的数据传输路径，进而形成新的联盟结构；并对新的联盟结构中的各条路径情况进行检查，当共用同一中继节点的目的节点的数量超过预设上限值时，对相应路径进行调整；

[0080] 根据新的联盟结构的包传输成功率和延迟时间计算其总效益；并将新的联盟结构的总效益和初始联盟结构的总效益进行对比；

[0081] 若新的联盟结构总效益相比于初始联盟结构有所增加，则保存当前形成的航空网络连接，并且记录当前联盟结构的总效益；若新的联盟结构的总效益相比于初始联盟结构没有增加，则再次随机改变其中飞机节点之间的连接，再次形成新的联盟结构，所有的De不断重复这一过程直至不再发生任何转移为止，最终形成一个稳定的联盟结构。

[0082] 其中，联盟结构的总效益的表达式如下：

[0083]

[0084] 其中，u(Gini)表示联盟结构Gini的总效益，PSR(Gini)表示联盟结构Gini的包传输成功率，delay(Gini)表示联盟结构Gini的延迟时间，β为预设常量。

[0085] 其中，整个联盟结构的延迟时间为联盟结构中每条路径传输数据所需时间和等待连接的时间之和，延迟时间的计算公式如下：

[0086]

[0087] 其中，delay为延迟时间，data为每个目的节点接收的数据量，i，j为链接的两飞机节点，ratei，j为两节点i，j之间的最大信息传送速率，wait为等待连接的时间；

[0088] ratei，j由香农公式得出，其计算公式如下：

[0089] ratei，j＝Bw*log2(1+SNRi，j)

[0090] 其中，Bw为信道带宽，SNRi，j为路径中两节点i，j传输数据的信号与噪声之比，SNRi，j的具体计算公式如下：

[0091] SNRi，j＝PDD-20*lg(distancei，j)-20*lg(fc)+147.5-5-Noise-Bw[0092] 其中，PDD为传输功率，distancei，j为两节点i，j之间的距离，fc为工作频率，Noise为传输过程中的噪音干扰，Bw为信道带宽。

[0093] 本实施例通过获取航空动态网络图，计算航空网络拓扑关系变化率，选取时间间隔，根据选取的时间间隔将航空动态网络图转换为多幅静态网络拓扑图；根据静态网络拓扑图中每个飞机节点与其邻居节点间的欧式距离，对静态网络拓扑图进行简化；基于简化的静态网络拓扑图，通过飞机节点相互合作建立联盟结构，以传输流量和延迟时间为博弈规则，规划出航空网络中的传输路径。更有效地利用了航空网络中的闲置资源，且确保了航空通信的可靠性和有效性。

[0094] 第二实施例

[0095] 请参阅图2至图8，本实施例提供一种基于联盟博弈的航空动态网络路径规划方法，该基于联盟博弈的航空动态网络路径规划方法包括：

[0096] 1、通过航空公司的实际航班飞行数据，计算航班的航迹数据，航迹数据一般包括航班整个航程中的经纬度、飞行高度、飞行速度、飞行时间等信息。载入航迹数据，因为航空网络具有高动态性，因此以动态图模型来表示，动态的网络图可以划分为多个时间的静态图来，再根据视距传播规则，形成多个静态网络的初始结构，计算在每个时间段内的航空网络拓扑关系变化率，保证该段时间内的航空网络拓扑关系相对保持不变；

[0097] 2、对多个静态图拓扑结构进行简化；静态拓扑图的每个飞机节点i周边划分扇形区域，以节点i为圆心，以指定通信距离为半径的圆形区域，以角度α为扇形区域划分的参数，计算每个α扇形区域内的邻居节点v与节点u之间的欧式距离，保留其中距离最小的邻居节点，删除该扇形内其他邻居节点。依次对每个节点进行简化，形成简化后的航空网络拓扑结构；

[0098] 3、选取一段时间内形成的航空互联网，在初始时间设定一部分飞机节点De为目的节点，需要传送到一定的数据到目的节点，其余的飞机节点Re都可以作为中继节点，形成数据传输路径。每个飞机节点i先随机选择基站接入(通信范围内没有基站的不进行连接)，形成初始化联盟结构Gini；

[0099] 4、计算该阶段初始联盟的总效益。在航空互联网中主要出现两个问题。一是如何提高数据传输量，二是怎么保证数据传输的实时性，减少传输时延。从这两点出发，设计该联盟结构中的效益函数——系统功率，系统功率是以包传输成功率(packet success rate)和延迟共同为标准设计出的，计算初始联盟结构Gini的每条路径上节点之间的包传输成功率；

[0100] 5、形成初始联盟后，随机改变其中某些飞机节点De的连接，飞机的航线是固定的，所以飞机在当前时刻搜索不到可连接节点时，可进行等待，连接下一时段内通信范围内的飞机节点Re。最后De搜索周边可连接或下一时段可连接的邻居节点，生成新的数据传输路径，形成新的联盟，记为Scur；

[0101] 6、生成新的联盟结构Scur后计算当前联盟的总效益，若联盟总效益增加，则保存下当前形成的航空网络连接。并且记录当前联盟总效益函数；若联盟总效益没有增加，则再次随机改变其中飞机节点之间的连接，形成新的联盟，所有的飞机节点De不断重复这一过程直至不再发生任何转移为止，这样最后就形成了一个稳定的联盟结构。

[0102] 进一步地，上述步骤1具体为：获取航空公司的航班信息数据，航班数据信息一般包括航班号、出发地、目的地及对应经纬度、出发时间、到达时间。因为存在时差问题，所以将飞机的时间统一用UTC(Coordinated Universal Time)表示。飞机飞行是一个动态的过程，为了方便表示整个飞行过程的动态拓扑关系，选取飞机飞行的24小时航班数据信息，将其划分为若干个时间段，在每个时间段内的航空网络拓扑关系相对保持不变，计算航空网络中连续两个时隙之间的变化率，其中Ne为航空网络中边的条数，Ne(H(tk+1)-H(tk))为航空网络图中连续两个时隙中不同边的个数，当公式(1)变化率小于1％时，认为拓扑是静态的，相对没有发生变化。根据每个时间段对应的飞机航迹数据，包括飞机的飞行时刻，对应时刻的经纬度信息，航班号等，生成若干个时间段所对应的初始航空网络拓扑图。航空网络中的视距通信范围由无线电地平线决定。因此两个飞机节点之间的最大通信距离取决于节点的飞行高度和地形特征，根据勾股定理可计算出两个飞机之间的通信距离(公式(2))。其中h1和h2为每架飞机的飞行高度，R为地球半径，r为飞机的最大通信距离。

[0103]

[0104]

[0105] 上述步骤2具体为：航空网络在建模时可以用无向图来进行表示。选取节点u，以u为中心，最大通信距离为半径画圆，在该圆内的其他节点都为节点u的邻居节点。将该圆以α为参数，划分成n(n＝2π/α)个α扇形区域，并进行编号1，2，3……n。通过飞机所在的坐标位置(x1，y1)，(x2，y2)计算每个扇形区域内节点u与邻居节点之间的角度angle，使用arcsin函数，得到两点之间的角度，划分到所在扇形区域计算节点u的每个α扇形区域中与邻居节点的欧氏距离。选取每个扇形区域中欧氏距离最小的节点，保留该邻居节点，最终形成简化的航空网络拓扑图。

[0106]

[0107]

[0108] 上述步骤3具体为：在该航空互联网中，设定一部分飞机节点De为目的节点，需要传送到一定数据到目的节点，其余的飞机节点Re都可以作为中继节点，形成数据传输路径。因为航空网络拓扑图是以时间段为划分的，所以飞机在选择中继节点时可以等待至多3个时间段进行连接。每个飞机节点i先随机选择基站接入(通信范围内没有基站的不进行连接)，形成初始联盟结构Gini。

[0109] 上述步骤4具体为：计算初始联盟的总效益。在用户服务质量对吞吐量和延迟敏感的网络中，描述效益函数的一个概念是系统功率(system power)，系统功率是以包传输成功率(packet success rate)和延迟共同为标准设计出的。整个网络的时延为联盟中每条路径传输数据所需时间和等待连接的时间之和，时延delay计算公式如下：

[0110]

[0111] 其中data为每个目的节点接收的数据量，而节点间传输数据速率公式由香农公式得出，计算出最大信息传送速率公式为：

[0112] ratei，j＝Bw*log2(1+SNRi，j)(i，j为链接的两飞机节点)  (6)

[0113] 其中Bw为信道带宽，SNRi，j为路径中两节点传输数据为信号与噪声之比，SNRi，j的具体计算公式如下：

[0114] SNRi，j＝PDD-20*lg(distancei，j)-20*lg(fc)+147.5-5-Noise-Bw  (7)[0115] 其中PDD为传输功率，distance为公式(4)中计算的两飞机节点之间的距离，fc为工作频率，Noise是在传输过程中的噪音干扰，Bw与公式相同，为信道带宽。此处SNR的单位为db，需要换算一下单位：

[0116]

[0117] 关于包传输成功率PSR，由于会出现一跳或者多跳的无线信道通信，因此节点之间传输每个数据包都会受到误码率(BER)的影响，利用Rayleigh fading中继多跳来计算误码率其中Nr是所有目的节点de的集合，例如{v1，v2...vn}，而Nr(i)表示流向i节点数据的路径中所经过的节点Nr(i)＝{v1，v2...vi-1}，

[0118]

[0119] 其中SNR的计算与上方公式(7)相同。因此由误码率公式可以得出PSR的计算公式如下：

[0120]

[0121] 综合以上公式PSR和delay可以得出效益函数公式，其中β可根据实际要求设定：

[0122]

[0123] 所述步骤(5)具体为：形成初始联盟后，随机改变其中某些飞机节点De的连接，飞机的航线是固定的，所以飞机在当前时刻搜索不到可连接节点时，可进行等待，连接下一时段内通信范围内的飞机节点Re。最后De搜索周边可连接或下一时段可连接的邻居节点，生成新的数据传输路径，形成新的联盟，记为Scur。并且对联盟中的多条路径情况进行检查，避免出现多个目的节点公用同个节点Re(有上限设置)，数据传输干扰过大的情况。

[0124] 所述步骤(6)具体为：生成新的联盟结构Scur后计算当前联盟的总效益若联盟总效益增加，则保存下当前形成的航空网络连接。并且记录当前联盟总效益函数；若联盟总效益没有增加，则再次随机改变其中飞机节点之间的连接形成新的联盟，所有的飞机节点De不断重复这一过程直至不再发生任何转移为止，即整个联盟中发生任何改变对于联盟的总效益都没有增进，这样最后就形成了一个稳定的联盟结构，保证了通信传输的可靠性。

[0125] 进一步地，本实施例的算法实现过程如下：

[0126]

[0127]

[0128] 下面结合仿真对本发明的应用效果作详细的描述。本实施例采用matlab2018a仿真工具，对基于联盟博弈的航空动态网络路径规划进行仿真。仿真参数如表一所示：

[0129] 表一 仿真参数

[0130]

[0131]

[0132] 1.本实例采用跨大西洋航班数据，选取24小时内的航班数据，生成对应的航迹信息数据，部分飞机航迹数据信息如表二，然后通过最大通信距离计算得出，一段时间内的航空互联网连通性是不变的，并且此时飞机的数量较多，生成初始的航空图如图2，可以看到该时刻的大部分飞机分布在大西洋上空：

[0133] 表二 飞机某一时刻部分航迹信息

[0134]飞机号码 航班号 UTC时间 维度 经度
2 70 1740 57.32648 -31.7614
4 7249 1740 54.86795 3.560385
12 64 1740 51.73254 -10.9821
14 750 1740 54.21946 -20.2666
19 36 1740 47.51303 -34.3694
22 754 1740 52.24674 -18.4087
24 78 1740 50.57195 -67.953
25 7001 1740 52.73538 -15.0504
28 7397 1740 69.65679 -35.6493
29 1900 1740 48.4414 4.277563
30 1912 1740 50.32747 -39.5619
31 1914 1740 49.56718 -26.844
36 758 1740 46.29175 5.576832
37 7421 1740 56.88547 0.547134
38 7431 1740 56.16205 -92.0406
39 1908 1740 47.25051 -72.7772
40 104 1740 46.74831 -61.4925
41 40 1740 44.61433 -81.9023
42 46 1740 55.15189 -52.7802
45 7473 1740 54.52407 -14.5154
46 1916 1740 45.52879 -71.4002
47 110 1740 53.32269 -21.8443
48 204 1740 55.04095 -25.5231
49 290 1740 54.27844 -27.4642
51 704 1740 53.32418 -8.24177
53 740 1740 45.0805 -22.7782
54 744 1740 45.2609 -51.1753
55 208 1740 56.13727 -46.1293
57 724 1740 54.21272 -27.5666
60 1928 1740 55.74014 -25.5984
61 1932 1740 52.33395 -37.5434
65 48 1740 54.77225 -42.1779
66 50 1740 55.77715 -24.1722
71 786 1740 52.14762 -27.0226
72 1902 1740 51.50839 -7.76119
75 1910 1740 56.72815 -41.4722
79 120 1740 49.97431 -48.7303
82 742 1740 47.26985 -25.1967
83 7393 1740 44.08707 -117.214

[0135] 2.计算拓扑网络变化率，如果变化率小于或等于1％，则认为拓扑是静态的。否则，拓扑将继续细分时间段。图3表示在一定区域内4个连续拓扑的变化，其中变化率约为0.92％。根据航空网络视距传播规则，我们设定所有的飞机都处于同一高度，跨大西洋航班的典型飞行高度在FL310(31000英尺)到FL400(40000英尺)之间，本实例中，我们选取h＝
35000ft，Re＝6378.137km，带入公式计算得出r＝400nmi。生成的初始航空网络如图3，网络密集，不便于后续的路径选择选择操作。

[0136] 3.通过步骤2得到了初始的航空网络，但网络中存在一些离散点，因此去除航空网络中离散的点，保留最大连通子分量。根据连通关系，生成对应的邻接矩阵，计算节点的每个α扇形区域中与邻居节点的欧几里得距离。选取欧几里得距离最小的节点，保留与该邻居节点的连通性，去除该扇形区域与其他邻居节点的连通。若删除其他邻居节点连通时，使得整个航空网络的连通性消失，则不删除。图4是我们简化完成的航空网络拓扑结构，能够看到该算法大大减少了网络复杂度，便于后续的路由选择操作，也减少了网络节点的能量消耗。

[0137] 4.图5是联盟博弈算法迭代的过程，由图5可以看出在整个迭代过程中稳定的寻找最优值，效益函数值逐步上升，并且可以在有限的迭代次数内使得整个联盟稳定下来，得到最优值，本实施例中的效益函数是考虑误码率和传输时延两者设计而出的。图6是体现了动态图模型中时间间隔的设置对后续形成联盟博弈的影响，3min和1min两种时间间隔，整体时间都为30min，可以看出时间间隔越小，效益函数越大，但相差并不大，因为仿真间隔设置为3min是合理的。图7是中继站缓冲区变化过程中，形成的联盟效益函数的变化，因为整个数据传输过程是存在等待的，需要在等待时间将数据存放在缓冲区，所以中继站缓冲区也限制了后续传输中能够接受到数据量的大小及整体传输的时延大小。通过图7可以看出缓冲区越大，整体的效益函数值越大。图8是中继站buffer为20mb时隙为3min情况下，带宽变化所形成的联盟效益函数值。从整体模型来看，带宽参数影响了数据流的传输速率，所以带宽的增加也会使得接收的流量增多，传输时间变短，整体效益函数增加，但是随着带宽的增大，对效益函数的提升却变慢，因为还存在着缓冲区等其他的因素的限制。

[0138] 此外，需要说明的是，本领域内的技术人员应明白，本发明实施例的实施例可提供为方法、装置、或计算机程序产品。因此，本发明实施例可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明实施例可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

[0139] 本发明实施例是参照根据本发明实施例的方法、终端设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、嵌入式处理机或其他可编程数据处理终端设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理终端设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

[0140] 这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理终端设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。这些计算机程序指令也可装载到计算机或其他可编程数据处理终端设备上，使得在计算机或其他可编程终端设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程终端设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

[0141] 尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例做出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明实施例范围的所有变更和修改。

[0142] 还需要说明的是，在本文中，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者终端设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者终端设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者终端设备中还存在另外的相同要素。

[0143] 以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明所述原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。