航空自组织网络(aeronautical Ad Hoc network,AANET)是移动自组织网络(MANET)中的一种,它可以作为未来民航通信系统中天基网和地基网的重要补充用于未来民航的通信。AANET与传统的移动自组织网络相比,其节点的移动速度普遍较高,且移动轨迹受限,能量约束要求不高。节点的高速移动,会使网络的拓扑快速变化,节点之间链接频繁中断,从而导致路由路径的频繁中断,进而对应用建立的持续会话产生较大影响^[1]。上述问题对移动自组织网络路由协议的设计带来了新的挑战,要求协议能够实时感知网络拓扑的频繁变化,并根据拓扑的频繁变化采取有效的处理机制^[2]。为此,本文提出了一种新的基于拓扑结构的路由机制。其目标是在不依赖定位系统的情况下,根据飞机的移动特征对网络的拓扑进行控制,从而为AANET应用的部署提供理想的网络环境。

设2个飞行器节点m₁和m₂之间的间距为d;每个节点的通信范围为r;2个节点分别以v₁和v₂的速度移动。当2个节点m₁和m₂之间的间距d≤r时,在2节点之间创建1个链接。此时,随着节点的高速移动会出现2种情况:在v₁=v₂的情况下,节点之间的链接状态将会一直保持有效;在v₁≠v₂的情况下,节点之间的链接将会在一段时间后中断。根据同一航线上飞行器的飞行特征,v₁和v₂在极坐标系中可分别表示为(v₁,θ₁)和(v₂,θ₂),其中v₁,v₂∈[V_min,V_max],θ₁,θ₂∈｛0,Π｝,节点m₁和m₂的相对速度可表示为

点击浏览公式

其相对速率可表示为

点击浏览公式

相对速率函数依赖于相互独立的随机变量v₁、v₂、θ₁和θ₂。这里用随机变量V_r表示相对速度,相对速度的数学期望可定义为

点击浏览公式

因为公式(3)中的随机变量相互独立。所以联合分布函数f (V_r)等于其边缘分布函数的乘积,即

点击浏览公式

从而可得出相对速度的数学期望可表示为

点击浏览公式

设节点m₁和m₂在时刻t建立了一个链接l_link12,并且节点m₁相对于节点m₂以v_r的速度移动,如果相对速率|v_r|>0,则链接l_link12将在一段时间后断开。如果节点在时间区间(t,t+Δt)内移动速度不变,且相对距离不超过2r,则链接l_link12将一直处于可用状态。

对在t时刻建立的链接,在t+Δt时刻仍保持链路可用的概率可由下式表示

点击浏览公式

设节点m₁在t+Δt时刻的无线电覆盖区域与在t时刻的无线电覆盖区域的重叠部分用O_t+Δt(d)表示,则节点m₁以速度v₁在时间区间(t,t+Δt)内移动距离d(d≥0)时,其重叠区域O_t+Δt(d)的计算函数可表示为

点击浏览公式

下面以基于拓扑结构的路由机制中的Hello报文为实例,介绍节点移动过程中链接可用概率的计算方法。设Hello报文每隔T秒钟广播1次,以发现或维持相应的可用链接,则节点m₁与节点m₂移动一个周期T时间后的距离可由E(V_r)T计算得到。因此,在经过n个周期后,链接保持可用的概率可由公式(7)表示(其中N表示自然数集合)。

点击浏览公式

如果2个节点的相对移动方向只有正向和反向2种,则同向移动时,相对速度的数学期望的计算公式可由公式(4)简化为

点击浏览公式

当节点m₁和m₂反方向移动时,相对速度的数学期望的计算公式同样可由公式(4)简化为

点击浏览公式

定理1(同向链接定理) 在相同航线航行的节点两两建立的链接中,同向航行节点比反向航行节点建立的链接保持长时间可用的概率高。

证明 已知周期T为定值,2个移动节点的相对距离d=E(V_r)nT与E(V_r)成正比。由公式(8)和(9)知E(V_r)_{opposite direction}>E(V_r)_{same direction}。而函数O_t+Δt(d)在区间0≤d≤2r内是一个减函数。由已知条件和公式(7)可推出

点击浏览公式

AANET的路由协议在创建多跳路由路径时,如果能利用定理1的结论,可有效降低链路中断的概率,从而降低路由路径中断的概率。

定理2(反向链接定理) 在相同航线航行的节点中,对两两反向航行的节点之间所创建的所有链接,新创建的链接保持长时间可用的概率高。

证明 设时间周期为T,且两两反向航行的飞行器在不同时刻创建的2个链接分别为l_link1和l_link2,再设在时刻t时,链接l_link1持续了n个周期(其中n∈N),链接l_link2持续了(n-β)个周期(其中0<β<n,β∈N)。则根据公式(7),在时刻t链接l_link1和l_link2保持可用的概率分别由下式表示

点击浏览公式

点击浏览公式

由于函数O_t+Δt(d)的值在区间0≤d≤2r内递减,由此可推出p_connected(n)<p_connected(n-β)。因此,建立时间较长的链路l_link1保持可用的概率较小。

本节详述AANET网络拓扑控制机制中,如何根据节点移动特征检测识别同一航线的2个飞行器之间建立的可用链接。在基于拓扑结构的路由机制中,节点之间链接的发现与维护,主要通过定期交换Hello报文来实现。链路可依据时间的度量指标,通过收到Hello报文的数量来表示。引入节点逻辑邻居集合的概念,该集合是指可直接给其发送Hello报文的1跳节点的集合。

表 1是节点m_i的一个逻辑邻居集合列表(这里i=1),其中M_i表示m_i的逻辑邻居集合,t_i(m_x)表示节点m_i从它的邻居节点m_x首次接收到一个Hello报文的时间,并在它们之间建立1条单向链路的时刻。$\phi $_i(m_x)表示节点m_i和m_x之间的稳定度,用来度量m_i和m_x之间建立链接的持续时间。公式(10)是$\phi $_i(m_x)的具体计算方法,其中t表示当前时间,T表示接收Hello报文的周期,[]表示取整数位。

点击浏览公式

N_i(m_x)表示超时参数,意指当2节点之间超过N_i(m_x)时间没有Hello报文交互时,认为2节点之间的链接已经断开。N_i(m_x)指标的作用,是避免Hello报文因偶尔的干扰导致发送或接收失败时,误认为链接已经断开而设置的。本文设置N_i(m_x)=4T,这意味着链路检测机制可容忍连续3个周期没有收到Hello报文。因为出现3次以上连续丢失Hello报文的概率非常小,可以忽略不计^{[4, 5]}。当一个链接出现经历4个周期还未收到Hello报文时,则认定该链接中断,路由过程中将不再选择此链接,同时稳定度参数将会归零重新累加。但是,当稳定度参数重新达到一个定值时,该链接将会被重新认定为可用链接。

用稳定度参数来检测识别同航向飞行器之间建立的长可用链接。如公式(11)所示,当一个链接的稳定度参数$\phi $_i(m_x)大于一个给定值n_stab时,则认为该链接具有较高的稳定度,是一个长可用链接,用l_linkix-l表示。

点击浏览公式

下面具体说明n_stab值的确定方法。由公式(6)和(7)可知,当E(V_r)≠0且d>2r时,p_connected(n)=0成立;由于此时d=E(V_r)nT,因此可知当n>2r/E(V_r)T时,p_connected(n)=0。然而文献^[7]的研究发现,高速移动自组织网络中,保持链接可用状态下,节点相对速度的概率是按正态分布的,其中99.7％的速度分布在E(V_r)±3σ(σV_r)/3)范围内,其中σ表示分布的标准差。这里我们取相对速度分布的下限为E(V_r)-3σ,以获得较大的n_stab值。其计算公式为

点击浏览公式

由上式知,同一航线上,沿相同航向飞行的2个飞行器之间建立一个链接后,只在收到n_stab个以上的HELLO报文时,才能说明该链接是一个长可用链接。

AANET网络中,节点的移动特性使节点之间的链接不能总是长可用链接,经常会出现路由路径中的链接,无法保持长可用链接的情况。此时,路由过程就需要使用短可用链接来填补路由路径,以保障数据的可靠传输。这里,短可用链接是指$\phi $_i(m_x) <n_stab且可用时间较长的链接。短可用链接的识别算法需用到定理2的理论,可从1组不稳定链接($\phi $_i(m_x) <n_stab)中,挑选出可用时间较长的链接。即按照下式选择逻辑邻居集合中,稳定度参数值最小的链接为短可用链接

点击浏览公式

对于不稳定链接来讲,本方法不区别链接是由同向航行节点建立的还是由反向航行节点建立的,只选择$\phi $_i(m_x)值最低的链接为短可用链接。

当逻辑邻居节点都与一个节点具有长可用链接时,此节点可认为是一个稳定节点,并可作为广播网络拓扑发生变化的信息。为避免大量拓扑变化信息的广播造成泛洪现象,本文提出了一种广播代理选举算法。该算法可选择一个节点统一发送拓扑变化的信息。此外,该算法生成的由长可用链接组成的拓扑结构,可有效用于全网范围内的信息发布与传递。

设A(m_i)为节点m_i所选择的广播代理,且每个节点m_i只能选择一个广播代理,m_i也可通过Hello报文获知其逻辑邻居集合中的节点所选择的广播代理。m_i选择广播代理的方法如算法1所示。

算法1 节点m_i选举其广播代理的算法

输入:M_i,｛$\phi $_i(m_x),A_i(m_x),t_i(m_x)｝∀m_x∈M_i

输出:A(m_i)

1) $\phi $_max ←return_-$\phi $_max-from_-table();

2) address←MAX_-INT;

3) A_mid←-1;

4) thershold←-1;

5)IF if_-stable_-node (m_i) THEN/*规则1-判断节点是否是稳定节点*/

6) FOR each neighbor m_x∈M_i DO

7) insert_-list(A_i(m_x),list_-BA);/*将邻居节点的广播代理插入列表中*/

8) END

9) IF (m_i is BA) THEN

10) insert_-list(m_i,list_-BA);

11) END

12) FOR each A_x∈list_-BA DO/*选出已有广播代理中稳定度最高的广播代理*/

13) FOR each neighbor m_x∈M_i DO

14) IF(m_x=A_x) AND if_-stable_-node(m_x) THEN/*规则2-选择邻居中的已是广播代理的节点为m_i的广播代理*/

15) A_mid←m_x;

16) END

17) END

18) IF(A_mid≠-1)THEN;/*代理节点已选出*/

19) BREAK;

20) END

21) IF (m_i=A_x) THEN/*规则3-选举自己为广播代理*/

22) A_mid←m_i;

23) BREAK;

24) END

25) END

26) IF(A_mid=-1)THEN/*规则4-选举邻居节点为一个新的广播代理*/

27) FOR each neighbor m_x∈M_i DO

28) IF($\phi $_max-$\phi $_i(m_x)-thershold≤0)

AND (address_-m_x<address) THEN

29) address←address_-m_x;

30) A_mid←m_x;

31) END

32) END

33) END

34) END

35) A(m_i)=A_mid;

上述算法中,规则1~4的原理说明如下:

规则1 当m_i与其逻辑邻居节点之间没有长可用链接时,它不选择任何节点做自己的广播代理;

规则2 当m_i未被其逻辑邻居节点选为广播代理,并且至少存在一个邻居节点m_x已经是一个广播代理时,m_i选择节点m_x为自己的广播代理;

规则3 当m_i是其逻辑邻居节点选择出来的广播代理之一,同时其地址又小于其他逻辑邻居节点选择出来的广播代理的地址时,m_i将选择自己作为广播代理;

规则4 当m_i的逻辑邻居中(m_x∈M_i),没有一个节点已选定广播代理时,m_i选择逻辑邻居集合中稳定度参数值最大的逻辑邻居中地址最小的节点作为广播代理;

上述算法中,规则4用于网络中选择第一个广播代理,规则2用于合并多个广播组。规则3用于自己充当广播代理时合并多个广播组。

传统的聚类算法在选举簇头的过程中通常需要使用2跳以外的节点信息,而本算法中广播代理的选举只使用1跳以外的邻居节点信息。因此,广播组是会发生重叠的。图 1是一个本算法的具体实例,图 1a)所示的网络中,节点m₁是由节点m₂、m₃和m₄选举出来的广播代理。应用规则3,节点m₁选举自己为广播代理。在节点m₅和m₆与网络有了物理链接后,如果m₅选举m₂为广播代理,m₆选举m₃为广播代理(如图 1b)所示),则在此情况下,广播代理m₁、m₂和m₃都是稳定节点,因此,m₁、m₂和m₃生成的拓扑是一个稳定拓扑。此时,节点集合｛m₁,m₂,m₃｝可将数据包发送到网络中所有的节点,且所生成的稳定拓扑也可用于信息的全网广播。

图 1 算法1的实例

图选项

但是,稳定拓扑并非在所有情况下,都能用于信息的全网广播。例如,对于图 1c)中的网络,如果通过稳定拓扑的节点集合｛m₁,m₂,m₃｝进行信息的全网广播时,并不能保证所有网络节点都一定能收到消息。事实上,由m₁和m₈驱动的广播路径,由于普通节点m₅和m₉之间不是长可用链接,因此m₁通过稳定拓扑｛m₁,m₂,m₃｝在全网的广播消息发送到m₅时,是无法继续发送到m₉和m₈的。同样,m₈在全网的广播消息只有m₉能收到,其他节点是收不到的。此类状况通常发生在飞行节点密度较低的时候。由于本算法仅关注稳定拓扑可用时间的问题。因此,全网广播的实时可达性可暂不考虑。

为验证本文提出的拓扑控制机制的效果,我们利用上述拓扑控制机制对OLSR协议进行了改进,设计了一个融入AANET网络节点移动特征的路由协议——链接可用度路由协议(link availability routing protocol,LAR)。并分别与OLSR、DSR、AODV、GPSR协议的性能进行了比较。对比的性能参数主要包括:路径可用率、路径长度、路径可用时间及端到端延迟4个参数。实验中定义了4个不同节点密度的场景,节点的平均邻居数分别设定为4、6、8和10,以保证以10公里为半径的圆周内飞行器数量个数分别保持在5、7、9和11。

仿真实验结果中端到端延迟的情况如表 2所示。从表 2的总体比对结果来看,本文提出的LAR协议比DSR和GPSR协议的端到端延迟要明显低很多,介于OLSR和AODV协议之间。就端到端延迟而言LAR比OLSR协议的性能略差一点,这主要是因为LAR协议中MPRs集合的节点数比OLSR协议优化过的MPRs集合中的节点数要多,这会致使LAR协议在网络拓扑更新时产生更多的广播控制报文。

表 3描述了不同模拟场景下不同协议的平均路径长度。OLSR协议在所有场景下都具有最小的平均路径长度。LAR协议的平均路径长度只稍大于OLSR协议,低于其他3个协议。而DSR协议则在几乎所有场景下都具有最长的平均路径长度。将表 2和表 3结合起来比较,我们可以发现平均路径长度的增加会导致端到端延迟的增加。然而,不是所有仿真场景下都有上述特性。这是因为每种路由协议都有其自身特点,不能一概而论的认为端到端延迟和平均路径长度之间一定成正比。当给定协议具有较小的平均路径长度时,如果路径饱和程度较高,则会表现出较高的端到端延迟。

表 4使用到给定目的节点的路径解析比率来描述路径的平均可用率。其中DSR和GPRS协议表现出较高的路径可用率,这主要是因为上述两协议都具有按需路由的特性。本文提出的LAR协议的路径可用率与AODV协议非常接近,远高于OLSR协议。对于最终用户来说,路径的可用率是一项很重要的指标,但对于网络的稳定性来讲路径的可用时间也是非常重要的^[3]。虽然仿真实验中DSR和GPSR协议的路径可用率最高,但它们表现出的端到端时延也是最长的。另外,DSR和GPSR协议还有一个问题,尽管它们可为一个给定目的节点解析出大量的路径,但从路径可用时间的角度来考虑,这些路径的质量并不高。

本文选择一个中低密度(场景2)和一个中高密度的空中交通场景(场景3)的仿真实验结果来分析路径的可用时间。而场景1和场景2的实验结果较为相似,场景3和场景4的实验结果较为相似,因此场景1和4的实验结果不再分析。分析过程中采用路径可用时间的累积分布函数(CDF,cumulative distribution function)来进一步分析不同协议的实验结果,如图 2所示。其中图 2a)是场景2中的路径可用时间的比对结果,图 2b)是场景3中的路径可用时间的比对结果。结合表 4的实验结果,可以发现GPSR和DSR协议虽然具有较高的路径可用率,但图 2中路径可用时间的累计分布函数值显示它们生成的路径中约有45％的路径可用时间不大于1 s。而LAR协议只有9％的路径的可用时间不大于1秒,明显低于GPSR和DSR协议。也就是说LAR协议创建的路径具有较长可用时间的概率较高。如图 2a)显示LAR协议所创建的路径中,可用时间不超过6 s的数量约为28％,而其他协议的数量都介于55％和78％之间。

图 2 路径可用时间的性能比对

图选项

所有仿真实验结果表明,本文提出的理论方法应用到LAR协议后,可明显增加路径的可用时间。而在实验过程中,我们发现只选择同向飞行的节点建立路由路径时,OLSR协议建立的路由路径可用率可达到72.18％,当选择双向飞行的节点建立路由路径时,路径可用度仅为45.27％。而从表 4的实验结果看,LAR协议在双向飞行的节点中建立路由路径的可用率可达到66.93％,接近OLSR协议在同向飞行节点中建立路由路径的可用率。此外,LAR协议在端到端延迟方面也表现出较好的性能,只有OLSR协议优于它。但其路径可用率的实验数据却优于OLSR协议,可以与AODV协议相媲美。因此,LAR协议对路由路径可用时间的改善表明,其更适合用于对网络稳定性要求较高的AANET网络。

本文提出了一种新的适用于AANET网络的拓扑控制机制。该机制通过提高网络拓扑中链接的可用时间来降低路由路径的中断概率,能有效提高路由协议的性能。实验结果表明,本文提出的理论方法可有效改善基于拓扑结构和基于位置路由协议的性能,主要体现在路径可用时间的提高。对于端到端延迟及路径可用率等其它性能指标,也可达到较为理想的水平。未来可进一步研究移动模型实时参数的概率模型,为进一步探索在不同移动条件下,实现自适应路由行为的研究提供所需的理论基础。