位置信息辅助的机间自组网路由协议研究

史琰　杨鹏

摘要：提出了一种适用于机间自组网的路由协议算法，该算法使用位置信息辅助计算节点间的链路持续时间，并以此链路持续时间作为拓扑稳定情况的预测。各节点则依据跳数最小原则和链路持续时间最长原则进行路由计算，并在条件允许的情况下，为网络中的节点建立两条路由。仿真结果表明，该算法能够满足机间自组网的高动态拓扑变化，提供良好的网络性能。

关键词：自组织网络；链路持续时间；表驱动路由；多路径路由

机间自组织网络是移动Ad Hoc网络（MANET）在航空通信领域的应用，其基本思想是：在一定范围内的飞行节点通过互相发送控制信息、感知信息等自动地建立起一个MANET[1]。在机间自组网中，飞行节点不但作为消息的收发节点，同时还在网络中担当路由器的功能，这使得机间自组网可以采用多跳的方式传输数据，扩大网络的覆盖范围。

机间自组网应用于民航通信可为空中交通管理提供新的技术[2]，为航班提供通信保障[3]；应用于军航通信可发挥抗毁、协同等优势，提升平台的战术效能[4]。与一般的自组织网络相比，机间自组网不但具有多跳、自组织、无中心等固有的特点，同时还具有节点分布场景广密度低[5]、网络拓扑的高动态性[6]、信道质量的不稳定性[7]、网络的异构性和临时性。

1 位置信息辅助的机间自组网路由

1.1 机间自组网路由存在的问题

由于机间自组织网络具有节点快速移动、拓扑变化迅速的特点。在使用以往的基于最短路径的路由时，路由计算时只考虑了路径的长度。这在节点静止或节点低速移动的场景中能够适用，但是在机间自组织网络中，节点的快速移动会导致节点间的无线链路频繁通断。节点间链路的持续时间已成为影响路由的重要因素：距离最短的路径其链路持续时间可能很短，其在通信过程中的失效则会导致丢包率上升从而降低网络性能；链路持续时间长的路径可能增加路由的距离，加重网络中节点的负载，同时会增大信息传输的端到端时延。为了使所设计的路由协议适应节点的移动并能够使网络具有良好的性能，在路由算法中将采用最短路径原则和最长链路持续时间原则相结合。

1.2 位置信息辅助的链路持续时间计算

如图1所示，假设两节点A和B，其中节点A的经纬度分别为[（?A，θA）]，速度为[νA]，航向为[CA]，飞行高度为[HA]；节点B的经纬度分别为（[?B，θB]），速度为[νB]，航向为[CB]，飞行高度为[HB]。以下关于角度的计算均是以正北方向为基准方向，节点B对于节点A的方位角为γ，两节点间的航向夹角为α，节点A的航向与两节点间连线的夹角为β，两节点A、B与地球球心形成的球心角为[δAB]，节点间的最大通信距离为R。

根据两节点的经纬度信息，我们可以计算出两节点以地球球心为顶点形成的角距离：

最后，通过上述计算可以得到节点A、B间的链路持续时间：

（1）当时[νA=νB且α=0]时，如果[SR]，节点A和节点B无法通信，链路持续时间为0。

（2）当[νA≠νB或α≠0]时，节点A和节点B间链路持续时间为：

1.3 位置信息辅助的路由算法步骤

在本算法中，节点内部包含有2种类型结构表：网络拓扑表TE和节点路由表RT。

每个机间自组网节点在本地存储一张拓扑表TE，用于存储网络中各节点的位置信息。该拓扑表包含参数LINK_TIME以表明相邻节点之间的链路持续时间。如果节点i与节点j为邻节点， TE[i][j].IS_VALID_FLAG = 1可以表明两节点的邻居关系，并且TE[i][j].LINK_TIME可以表示节点i与节点j之间的链路持续时间。节点通过周期性地发送HELLO包的方式来进行拓扑表的建立和维护。HELLO包中会携带目前本节点已知的拓扑关系及链路信息。

节点内部使用节点路由表RT记录到达其他节点的路由，并且在条件允许的情况下，为网络中的节点建立两条路由：RT[i][0]和RT[i][1]，其中i为目的节点（[i]=1，2，…，N， N为网络中节点数量），标志0为优先路由，标志1为备份路由。与网络拓扑表TE类似，RT[i][0].IS_VALID_FLAG =1表明该路由表项有效，RT[i][0].PATH_TIME记录该路由路径的持续时间。

机间自组网节点通过上文所述的方法获取网络拓扑信息并更新相应的拓扑表项，然后各节点根据本地存储的拓扑表来计算路由生成表驱动路由表。

（1） 假设本地节点为S，节点S首先初始化本地路由表RT[i][j].IS_VALID_FLAG = 0 （[i]=1，2，…，N， j =0，1）；然后节点S再查找拓扑表TE内所有与自己为邻居的节点，即TE[S][j].IS_VALID_FLAG = 1，（j =1，2，…，N），如果存在就更新节点j对应的路由表表项，并记录其与节点j之间的链路持续时间、距离、下一跳。如图2所示，节点S根据本地的拓扑表为相邻的节点生成路由表，图中节点S首先生成到节点A和节点B的路由。

（2）节点S根据各一跳节点的拓扑关系计算两跳范围内的路由，如图3所示。

（3）节点S根据两跳节点的拓扑关系继续计算，并按照跳数的增加逐步扩散出去，直至到所有节点的路由都被计算出来。如图4所示，节点S根据本地的拓扑表中节点A和节点B的邻居关系生成两跳范围内的路由表，图中节点S通过节点A可以计算出两条跳数为两跳的路由，其中一条到节点C，另一条到节点D，同理节点S根据节点B的邻居关系计算到节点C的跳数为两跳的路由。由图中还可以看出节点S为节点C建立了两条路由，S到C的路由：优先路由为S→B→C，备份路由为S→A→D→C。

（4）在节点S计算路由表时，可能会出现节点S到某一节点j有多条路由，此时节点S依照图5所示原则对计算出的多条路由进行处理：

首先，节点S从计算出到节点j的多条路由中选择跳数最短的路由，当同时存在多条跳数最短的路由时，选择其中持续时间最长的路由作为优先路由，并将路由表项RT[j][0]按照上文所述方法更新；其次，当到节点j存在其他跳数次短但持续时间比优先路由时间长的路由时，将这条路由作为备份路由并更新路由表项RT[j][1]，同样当存在多条跳数次短的路由时，选择其中持续时间最长的路由作为备份路由。

如图6所示，假设图中的链路持续时间按其链路编号由大到小排列（链路1持续时间最长），节点S到节点A的链路持续时间最长且跳数最短，则节点S只为节点A建立一条优先路由：S→A。节点S到节点C的两条路由分别为：优先路由为S→B→C，备份路由为S→A→D→C。如图中所示，虽然链路S→A→C同样是两跳，但是由于其与链路S→B→C跳数相同且链路持续时间比S→B→C短，所以舍弃链路S→A→C。

总而言之，优先路由为节点S到节点j最短且持续时间最长的路由，备份路由为节点S到节点j次短但持续时间比优先路由时间长的路由。当节点S使用优先路由与节点j进行通信时发现链路即将断开时，节点S切换备份路由进行通信，以此来保障节点间通信的连续性。

2 位置信息辅助的路由算法仿真结果

仿真软件使用OPNET14.5，其中各参数设置如表1所示。

仿真中媒体接入控制层（MAC）采用时分多址（TDMA）的形式。时隙长度为2 ms，其中1 ms为发送数据，1 ms为保护间隔。时隙没有空间上的复用，节点发送周期为32 ms。物理层采用全向天线，信道速率为50 Mbit/s。节点每时隙内发送数据量上限为50 kbit，发送周期为32 ms。MAC层的发送速率上限为1.5625 Mbit/s。

图7仿真结果是在节点的移动速度固定为220 m/s，分组产生速率分别为10、20、30、40、70、100、130个/秒/节点，而MAC层缓存队列长度为1 000 pk下进行的。图7（a）为网络平均端到端时延，随着网络负载的增加，分组平均端到端时延由0.03 s增加到11.62 s；图7（b）为网络吞吐量与网络负载之间的关系，图7（c）为网络丢包率与网络负载的关系，由这两幅图可以看出随着负载的增加网络吞吐量逐渐增加并趋于稳定在10 Mbit/s，而网络丢包率增加到59%；由图7（d）为节点MAC层的传输能力统计曲线，可以看出网络中每个节点的MAC层均达到了其传输能力的上限，因此限制了网络性能的提升。

3 结束语

机间自组织网络具有节点快速移动、拓扑变化迅速的特点，机间自组织网络中的路由很大程度上受到这些特点的影响。位置信息辅助的最短路径原则和最长链路持续时间原则相结合的路由算法，可以降低高动态变化的网络拓扑对路由的影响。在网络拓扑允许的情况下，通过使用优先路由和备份路由的方法，保障了数据信息在节点间传输时不受链路通断的影响。

参考文献

[1] EHSSN S， ABBAS J. The Global in-Flight Internet [J]. IEEE Journal on Selected Areas in Communications， 2006， 24（9）： 1748-1757

[2] MAGGIE X C. Connectivity of Ad Hoc Networks for Advanced Air Traffic Management [J]. Journal of Aerospace Computing， Information and Communication， 2004， 1（5）： 225-238

[3] HU D T， SHIGERU S. A Proposal of Relaying Data in Aeronautical Communication for Oceanic Flight Routes Employing Mobile Ad Hoc Network[C]// 2009 First Asian Conference on Intelligent Information and Database Systems， Washington DC， USA， 2009

[4] 韩勇， 陈强， 王建新.机载网络技术综述[J].电讯技术， 2008，48（8）：111-114

[5] YANG W. Fundamental Issues in Systematic Design of Airborne Networks for Aviation[C]//IEEE Aerospace Conference， 2006

[6] JUSTIN P R， ABDUL J， EGEMEN K C， et al. High-Dynamic Cross-Layered Aeronautical Network Architecture [J]. Aerospace & Electronic Systems IEEE Transactions on， 2011， 47（4）：2742-2765

[7] ERIK H. Aeronautical channel modeling [J]. IEEE Transactions on Vehicular Technology， 2002， 51（2）： 254-264.doi： 10.1109/25.994803