一种基于地理位置信息的AANET联合路由算法

摘要

本发明公开了一种简单有效的基于地理位置信息的联合路由算法，将地理路由中的贪婪转发策略和反应式路由相结合。本发明针对航空自组网高动态，节点密度低的特点，首先对地理路由中的贪婪转发策略做出改进，新的路由度量不仅考虑了节点的地理位置，还考虑了节点间的相对速度，排除了不稳定的下一跳转发节点。其次，本发明结合传统反应式路由的良好特性，利用RREQ/RREP机制替代地理路由中的周边转发机制，能更加有效处理路由空洞情况。与其它方法相比，本发明有效地结合了两类算法的优点，使其更加适用于航空自组网的网络环境。

权利要求

1.一种航空自组网AANET中的简单有效的基于地理位置信息的联合路由算法，其特征在于采用以下步骤：A、假设所有飞机节点都配备了GPS定位系统，节点首先获取所需的地理位置信息，包括节点自身的位置，一跳邻节点的位置以及目的节点的位置信息，以上信息分别通过GPS全球定位系统，信标机制和位置服务算法来获得；

B、该联合路由算法有两种工作模式，包括贪婪转发模式和反应式路由模式；

C、算法首先工作在贪婪转发模式；为了选择有效的下一跳节点，候选节点首先需要满足下式，以保证候选节点在当前节点的无线覆盖范围以内，其中假设数据包现在到达节点i，节点j是节点i的邻节点之一，目的节点为d，网络中每个节点的无线覆盖范围是R，ΔSi,j(t)为i，j到目的节点的距离差，Rvi,j(t)为节点间的瞬时相对速度，c为自由空间的光速；

R＞ΔSi,j(t)·Rvi,j(t)/c+ΔSi,j(t)

D、然后在候选邻节点中，根据新定义的路由度量MDT(minimum duration time)来进行数据转发，由下式给出：其中，Ni是节点i的邻节点集，该路由度量综合考虑节点的位置和相对速度，使转发路径更高效稳定；

E、当在转发过程中遇到路由空洞时，路由空洞即该节点的邻节点中不存在比自己具有更小MDT值的节点，此时切换到反应式路由模式，利用RREQ/RREP机制寻找可用路径并进行数据转发，在限定时间内若找不到有效路径，则丢弃此包；

F、一旦节点绕过空洞区域，且在其邻节点中存在比自己具有更小MDT值的节点，则返回到贪婪转发模式；

G、重复以上步骤直至完成数据转发。

说明书

一种基于地理位置信息的AANET联合路由算法

[0001] 技术领域：路由算法

[0002] 本发明涉及一种AANET(航空自组网)中基于地理位置信息的联合路由算法，更具体地，涉及一种将地理位置路由和反应式路由相结合的路由算法，并通过优化地理路由中贪婪转发模式的路由度量来提高网络的性能。背景技术：

[0003] 路由技术是航空自组网关键技术之一，而路由算法在很大程度上决定了整个网络的性能。典型的路由协议可以分为两大类：基于拓扑结构的路由协议和基于地理位置信息的路由协议。基于拓扑结构的路由协议通过路由探测获知网络中节点之间的连接关系和链路特性，由此来确定网络路由。其进一步又可划分为主动型、按需型和混合型路由。主动路由采用周期性的路由广播来交换路由信息，给定节点维护全网所有节点的路由，有效路由始终存在，发送时延小，但其开销较大且占用资源。按需路由根据发送节点的需要，按需进行路由发现，占用资源少，但时延较大。混合路由则结合了主动路由和被动路由的优点，可扩展性较好。由于现代航空飞行器基本都已配备GPS全球定位系统，节点可以方便地获取地理位置信息，基于地理位置信息的路由协议备受瞩目，在航空领域具有广阔的应用前景。该类协议需要预先获得自己的位置，一跳邻节点的位置以及目的节点的位置。它不需要在发送数据包之前维护路由表或建立路径。因此，即使在网络拓扑剧烈变化的情况下，地理路由也可以保持较好的简单性和可扩展性。

[0004] 在众多地理路由中，贪婪周边无状态路由协议(GPSR)是其中最经典的应用最为广泛的一种路由协议。GPSR协议有两种工作模式，其首先工作在贪婪模式，选择距离目的节点最近且比自己到目的点近的一跳邻节点作为下一跳转发节点。当出现路由空洞时就自动切换到周边转发模式，先将网络拓扑描述为平面图，再根据右手法则进行转发。然而GPSR应用于高动态拓扑、低节点密度的航空网络时面临着许多问题。首先GPSR的贪婪转发策略未考虑节点的移动性，其次采取周边遍历来解决路由空洞问题被证明是低效的，在高动态环境下导致数据包大量丢失且时延急剧增加。

[0005] 尽管目前已经提出大量的移动自组网路由协议，但其中很少是针对航空自组网的特定目标进行研究的。直到近几年，多跳无线网络在航空领域的研究得到越来越多的重视，这些研究也是针对航空自组网的不同方面的需求所开展的。在澳大利亚的AANET项目中提出了一种多径多普勒路由协议(MUDOR)，利用多普勒频移估计节点间的相对速度来判断节点间是相互靠近还是远离，并选择多普勒频移值最小的路径来构建路由。该算法有效减少了实时流量传输中的网络流量负载和传播时延。ARPAM是一个基于AODV的应用于商业航空网络的混合型路由协议，该协议利用位置信息发现最短路径并在源节点和目的节点之间建立完整的端到端路径。在欧盟的NEWSKY项目中使用了一种称作地理负载共享(GLSR)的路由算法，它利用前进速度，也就是速度与队列时延的比值作为下一跳选择的度量，同时满足离目标节点最近和加入最短队列的原则，有效的缓解了GPSR协议中的拥塞问题。发明内容：

[0006] 本发明的目的是针对AANET拓扑结构高动态，节点密度低的特点，提供一种更适合于该网络的基于地理位置信息的路由方法，该方法有效地结合了地理路由以及反应式路由的优点，并优化了地理路由中的贪婪转发模式。说明书附图1示出了该算法的基本流程图。

[0007] 基于地理信息的联合路由算法是这样实现的：

[0008] 1.首先，网络中的每个节点都获取相关地理位置信息，包括自己的位置，一跳邻节点的位置和目的节点位置信息。可以分别通过GPS全球定位系统，信标机制以及位置服务来获得。

[0009] 2.当节点之间开始进行通信时，首先工作在贪婪转发模式，每个节点维持一张周期更新的邻居表来跟踪一跳邻节点的位置信息。根据新的路由度量MDT(Minimum duration time)来选择下一跳转发节点。该路由度量综合考虑了节点的位置和相对速度，使得选取的路由更为高效稳定。

[0010] 3.转发过程中遇到路由空洞(说明书附图2描述了路由空洞的情况)时，自动切换至反应式路由模式，利用RREQ/RREP机制寻找可用路径。

[0011] 4.一旦节点绕过空洞区域并且在其邻节点中存在比自己具有更小MDT值的节点，则返回到贪婪转发模式。

[0012] 5.重复以上步骤，直至数据包到达目的节点。

[0013] 与其它的技术相比，本发明具有以下的优点：

[0014] 1.由于现代航空飞行器基本都已配备GPS全球定位系统，节点可以方便地获取地理位置信息，本发明有效地利用了地理信息。

[0015] 2.改进的路由度量不仅考虑了节点的地理距离，同时也考虑了节点间的相对速度，该策略使下一跳转发节点更加稳定可靠，从而提高通信质量，更加适应高动态的航空通信环境。

[0016] 3.利用反应式路由的RREQ/RREP机制替代GPSR协议中的周边转发模式，避免了过长的路由路径和路由环路，比周边遍历转发策略更加有效和可靠。

[0017] 4.本发明结合了地理路由和主动式路由的优点，并优化了其路由度量。附图说明：

[0018] 结合附图阅读本发明的以下详细描述，可以更好地理解本发明及其优点和其他特征，其中：

[0019] 图1示出了地理联合路由算法的基本流程图；

[0020] 图2示出了路由空洞的情况。具体实施方式：

[0021] 为了更好地理解本发明，下面将详细描述本发明的具体实施方式。

[0022] 1.网络中的每个节点都维持一张路由表，表信息包括自己的位置，一跳邻节点的位置和目的节点位置。可分别通过GPS全球定位系统，信标机制以及位置服务来获得。

[0023] 2.当节点之间开始进行通信时，首先工作在贪婪转发模式，每个节点维持一张周期更新的邻居表来跟踪一跳邻节点的位置信息，然后根据新的路由度量MDT选择下一跳转发节点。

[0024] 3.下面确定路由度量MDT，网络中节点i与j之间的地理距离Si,j可以用下式表示：

[0025]

[0026] 其中，(xi(t),xj(t))，(yi(t),yj(t))，(zi(t),zj(t))分别代表节点i，j在当前时刻t的位置坐标。

[0027] 节点间的瞬时相对速度为：

[0028]

[0029] 其中 分别代表节点i，j在当前时刻t的速度。

[0030] 4.假设数据包现在到达节点i，节点j是节点i的邻节点之一，目的节点为d。网络中每个节点的无线覆盖范围是R，则两节点到目的节点的距离差为：

[0031] ΔSi,j(t)＝Si,d(t)-Sj,d(t)  (3)

[0032] 5.为了选择有效的下一跳节点，候选节点首先需要满足下式，以保证候选节点在当前节点的无线覆盖范围以内。

[0033] R＞ΔSi,j(t)·Rvi,j(t)/c+ΔSi,j(t)  (4)

[0034] 我们定义度量MDT(minimum duration time)如下：

[0035]

[0036] 其中Ni是节点i的邻节点集。改进度量不仅考虑了节点的地理距离，同时也考虑了节点间的相对速度。源节点计算各邻居节点的MDT值，选择MDT值最小的邻节点作为下一跳转发节点。该策略使选择的下一跳节点更加稳定和可靠，从而提高通信质量，更加适应高动态的航空通信环境。

[0037] 8.当数据转发过程中遇到路由空洞时，采用如AODV一类的反应式路由算法替代周边遍历算法。贪婪转发失败的中间节点开启路由发现过程来寻找一条有效的路由条目到达目标节点，在限定的范围内广播RREQ路由请求包。当邻节点收到RREQ包时，首先检查RREQ包的目的地址，若目的地址是它本身，则产生并返回一个RREP路由回复包；否则，继续广播该RREQ直到到达目的节点。若在限定的时间内未找到到达目的的路径，则停止广播并丢弃此包。

[0038] 9.一旦节点绕过空洞区域并且在其邻节点中有比自己具有更小MDT值的节点，则返回贪婪转发模式。

[0039] 10.重复以上步骤，直至完成数据转发。

[0040] 综上所述，基于地理位置信息的联合路由算法不仅保留了地理路由中贪婪转发策略的高效性和简单性，还与反应式路由相结合，建立更加有效和稳定的路径。