一种基于Dijkstra算法的航空平台组网技术

李德银，王胜海

(解放军92728部队，上海 200436)

随着航空兵部队日常训练水平的提升，对飞机进行全状态安全监控的需求日益增强。为了实现对空中飞机状态的实时监控，需要建立一个地空-空空高速实时无线传输网络，将飞行参数实时下传。但是，在飞机超低空和超视距飞行过程中，传统单一的TDMA网络难以满足无盲区通信需求，本文研究一种基于Dijkstra算法的Ad Hoc组网技术，以实现动态路由和数据中继转发功能，增加网络容量，提高网络覆盖范围和实时性。

1 Ad Hoc组网设计

Ad Hoc网络［1-2］是由一组无线移动节点组成的特殊分布式无线移动通信系统，是一种能够迅速展开使用的网络体系，其所有节点的地位平等，无需设置任何中心控制点;节点通过分层的网络协议和分布式算法相互协调，实现网络的自动组织和运行，可以动态地、随意地、频繁地进入和离开网络，一般不需要事先预警，且不会影响网络中其它节点的通信;网络中通信的源节点和目的节点不在直接通信范围之内时，可以经过多个中间节点转发，即报文可以经过多跳(Hop)到达目的地。因此，Ad Hoc网络被称为移动自组织对等多跳网络。Ad Hoc网络中的每个移动节点都具有路由器和主机两种功能。作为路由器，节点需要运行相应的路由协议，根据路由表参与分组转发和路由维护工作;而作为主机，节点需要运行面向用户的应用程序。

飞行参数实时下传网络通信方案中，每个空中平台配置一套机载通信终端，每个机载通信终端建立一张邻居信息表，机载通信终端通过周期性的广播路由来更新邻居信息表，地面中心站根据接收到的邻居信息，生成子网的拓扑表，在这个子网的拓扑结构上利用Dijkstra算法计算出每个节点到组网内其他节点的最短路径，即路由。得出路由表后，地面中心站需为每个机载通信终端分配资源，然后将路由表以及资源分配情况通过路由信令广播给各个机载通信终端，从而实现各个节点直接的数据传输。最后采用路由维护协议来更新路由以应对网络拓扑结构的变化，保证变化后的节点之间能正常通信，满足大范围无盲区通信需求。

2 网络路由的建立

2.1 邻居信息表

机载通信终端需要建立一个邻居信息表［3］，如图1所示。该信息表存储了对应每个邻居的记录，每一条记录为＜邻居节点地址、下两跳邻居节点地址、跳数、该信息记录的有效时间＞。在机载通信终端初始化的时候，邻居信息表为空。机载通信终端通过周期性的广播路由来更新邻居信息表。

机载通信终端维护的邻居信息表中的表项均在一定时间内有效，若存在超过有效时间的表项，机载通信 终端需要删除该表项。

图1 邻居信息表

2.2 网络拓扑表

地面中心站维持一张网络拓扑表，用于描述网络拓扑，计算路由。拓扑表包含三个部分:目的地址，到达目的地址所经过的中间节点的地址，表项有效时间。拓扑表中目的地址域保存所要到达的目的节点的地址，可以有多个表项具有相同的目的地址。表项有效时间用于表示该表项生存时间，超过生存时间的表项不能用于路由计算，必须删除。

2.3 邻居信息广播通告

邻居信息广播通告是机载通信终端通过周期性的发送邻居信息广播来实现的，在机载通信终端发送邻居信息广播时，以邻居信息为消息进行泛洪广播更新邻居信息表。

邻居信息广播消息不能被转发，只能在一跳范围内发送。假设机载A收到机载B发来的路由广播，在更新邻居信息表时算法步骤如下。

步骤1):对于B中的每一条邻居记录，若跳数大于3，则删除;否则，将下一跳节点值赋给下下一跳节点值，同时下一跳节点值修改为B，跳数加1，其余不变。检查A中是否有到达目的节点为B的邻居记录，若不存在，则在A中添加一条到B的邻居记录，其目的节点为B，下一跳为 B，下下一跳为空(NULL)，跳数加1。然后转步骤2)。

步骤2):对于修改后的B中的每一条记录，先检查在A中是否存在一条记录使得这2条记录的目的节点一样，若不存在，则增加该记录到A中，若存在，则转步骤3)。

步骤3):比较这2条记录的下一跳地址是否一样，若不一样，则将该记录添加到A中，否则，转步骤4)。

步骤4):将A中的记录替换成序列号最新的那条路由记录。直到所有的邻居记录都更新完毕。

2.4 路由的建立

地面中心站根据接收到的邻居信息，生成子网的拓扑表，用于描述当前时刻的网络拓扑结构，拓扑表由目的节点、跳数、到达目的节点所经过的中间节点(包括源节点以及目的节点)组成。在这个拓扑结构上，可利用带权有向图上的Dijkstra算法计算出每个源点到其余各顶点的最短路径，即路由。地面中心站可以对任两个相邻的节点设置一个权重函数，权重函数可以根据不同的需求对链路宽带、时延、节点的能量等选择适当的权重来表示各路径的长短。

由于Ad Hoc网络的特点可见，一条路由的稳定性依赖于许多因素，这些因素有些是相互联系或相互制约的，所以很难选择出一条具有绝对稳定性的路由。而且，除稳定性外，路由协议还必须考虑路由延迟、吞吐量等。在选择路由的时候，不可能将所有的因素都考虑在内，在设置权重函数时各权重因子之和必须为1。

地面中心站根据路由表为机载通信终端分配资源，保证转发节点有足够的资源转发业务数据。地面中心站需要将路由表以及资源分配情况通过路由信令广播给各个机载通信终端。机载通信终端需要记录路由及资源配置信息，并转发该路由信令，保证子网内所有机载通信终端都能收到路由信令。

在图2中，机载1、机载2、机载3分别广播邻居信息表，中心站收到这3个机载广播的邻居信息表后，便可生成子网的拓扑表。如中心站收到机载3广播的邻居信息表中的＜机载7、机载5、机载6、机载3＞这条记录后，可得出中心站→机载3→机载5→机载6→机载7这样一条拓扑信息。

2.5 路由维护

网络中的每个节点通过周期性地与邻居节点交换邻居信息表来维持整个网络的路由信息，也可根据网络拓扑的变化来触发路由的更新。路由表是基于本地邻居和本地拓扑表计算的，因此，一旦这两个表出现任何变化，都需要触发路由的更新，重新计算路由表，准确地说，如果邻居节点集、拓扑表中任何一个出现变化，都需要重新计算路由表，更具体地说，邻居节点增加或减少，三跳邻居节点的增减，拓扑表中记录的增减，都将导致重新计算路由表。

3 Dijkstra算法及应用

Dijkstra算法主要是解决带权有向图上的单源点的最短路径问题［4］，该算法是一个按路径长度递增的次序产生最短路径的算法。在路由表的建立过程中可以使用该算法得出各节点到其它节点的路由信息。

首先，引进一个辅助向量D，D的每个分量D［i］表示当前所找到的从始点v到每个终点Vi的最短路径的长度。D的初态为:若从v到Vi有弧，则D［i］为弧上的圈值;否则置 D［i］为 ∞。显然，长度为 D［j］=Min{D［i］}(其中Vi属于V)的路径就是从v出发的长度最短的一条最短路径，此路径为(v，Vi)。

在一般情况下，下一跳长度次短的最短路径的长度必是

D［j］=Min{D［i］}(Vi属于(V － S))，其中，D［i］或者是弧(v，Vi)上的权值，或者是D［k］(Vk属于S)和弧(Vk，Vi)上的权值之和。

Dijkstra算法描述如下(假设共有n个节点):

1)假设用带权的邻接矩阵arcs来表示带权有向图，arcs［i］［j］表示弧(Vi，Vj)上的权值。若(Vi，Vj)不存在，则置arcs［i］［j］为∞(在计算机上可用允许的最大值代替)。N为已找到的从v出发的最短路径的终点的集合，它的初始状态为空集。那么，从v出发到图上其余各顶点(终点)Vi可能到达到的最短路径长度的初值为

D［i］=arcs［Locate Vex(G，v)］［i］Vi属于 V;

2)选择Vj，使得 D［j］=Min{D［i］}，Vi属于V － N;

Vj就是从v出发的最段路径的终点。令N=N∪{j};

3)修改从v出发到集合V－N上任一顶点Vk可达的最短路径长度。如果 D［J］+arcs［j］［k］＜ D［k］，则修改 D［k］为 D［k］=D［j］+arcs［j］［k］;

4)重复操作2)、3)共n－1次，由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。

本文以图3为例讨论这种算法在图2中心站的拓扑表中的运用，即寻找源节点到网络中其他各节点的最短路径，为方便起见，设源节点(中心站)为节点0，然后一步步寻找源节点到其余各个节点(航空平台)的最短路径，直到把所有的节点都找到为止。其中图3中两节点之间连接线上的数字为权重。

表1是对图3网络进行求解的详细步骤，可以看出，上述的步骤2)、3)共执行了7次，表中带圈的数据时在每次执行时所寻找到的具有最小值的D(w)值，当第7次执行步骤2)、3)并得出了结果后，所有网络节点都包含在N中，整个算法结束。

图3 对应图2中网络拓扑结构Dijkstra算法运用

节点0为源节点，因此一开始在集合N为N={0}，因为节点0和节点1、节点2、节点3相连，故在初始化时，在D(1)、D(2)、D(3)中为节点0到这些节点的距离，而 D(4)、D(5)、D(6)、D(7)为∞。

在节点0以外的节点中，找出一个距离节点0最近的节点 w，即节点1，因为在 D(1)、D(2)、D(3)中，D(1)、D(3)最小。因此不妨将节点1加入到集合N中，这时N={0，1}，这时在步骤1)这一行和D(1)这一列下写入，表示节点1到节点0的距离为1，并且节点1在这个步骤中加入到集合N中了。

表1 计算节点1的最短路径步骤

接着就要对所有不在集合中的节点逐个执行。

对于节点2，原来的D(2)=2，因此节点2到节点1距离不变，仍为2;

对于节点3，原来的D(3)=1，因此节点3到节点0距离不变，仍为1;

对于节点4，到节点1的距离仍为∞;

图4 最短路径的生成步骤

对于节点5，到节点1的距离仍为∞;

对于节点6，到节点1的距离仍为∞;

对于节点7，到节点1的距离仍为∞。

在节点0和节点1以外的节点中，找出距节点0最近的节点，即节点3，将其添加到集合N中。以此循环，直到所有节点集合N不再变化为止。

最后就得出以节点0为根的最短路径树。图4给出了各个步骤执行后的结果。从最短路径树可以清楚地找出从源节点0到组网内任何节点的最短路径，即路由信息。

4 工程应用

本文针对飞行参数实时下传的用户需求，工程中建立地空-空空高速实时无线传输网络，以单地面中心站配置方式，机载电台直接与中心站进行通信，其应用场景如图5所示，机载电台采集的数据通过天线发送到无线信道，与地面站和其他机载电台共同构成无线通信网络，实时地将飞行数据传输至地面显控台。通过多架次的实际试飞验证(包括超低空和超视距飞行)，统计了能够表明网络运行情况的数据丢包率(见表2)，共统计10个飞行架次，丢包率最低0.03%，最高0.61%，丢包率最高时飞机作大机动、超视距飞行，采用了中继通信方式，有中继时由于增加了数据转发次数从而导致丢包率增加，飞机作大机动飞行时丢包率增加，主要是因为天线安装位置原因，飞机作大机动飞行时可能造成天线遮挡。总的来说，经试飞可以得出结论:基于Dijkstra算法Ad Hoc组网技术应用于某型飞机平台的空中组网后，成功实现了多架飞机飞行参数的超低空和超视距中继通信，数据丢包率低，组网通信稳定可靠，网络数据刷新率不低于8次/秒，带宽不小于2M，误码率小于1%，系统延时小于1s，支持3跳以内中继通信，能够满足部队超低空和超视距飞行无盲区通信需求。

图5 算法的工程应用

表2 空中试飞数据丢包率统计

5 结束语

本文针对空中平台高速、超低空和远距离移动等特点，提出了具有针对性的动态路由解决方案，并在部队日常训练中得到应用，能够满足飞行训练中高速实时的可靠无线传输需求，有助于实现飞行过程的安全状态监控，为提升航空兵部队训练质量奠定基础。

［1］陈林星，曾曦，曹毅.移动Ad Hoc网络——自组织分组无线网络技术［M］.北京:电子工业出版社，2012:3-7.

［2］厦海轮.无线AdHoc网络MAC协议及相关技术研究［D］.北京:北京邮电大学，2007:2-3.

［3］乐阳，龚健雅.Dijkstra最短路径算法的一种高效率实现［J］.武汉测绘科技大学学报，1999，24(3):209-211.

［4］严蔚敏，吴伟民.数据结构［M］.北京:清华大学出版社，1997:186-190.