CN107396420A - 一种空地一体无线自组织网络分域路由算法 - Google Patents

Abstract

一种空地一体无线自组织网络分域路由算法，在网络分域阶段中，根据节点通信能力，采用人工分域的方式，将网络分成两层，其中所有机载节点组成核心域，而所有地面节点确定各自所归属的外围域，同时，每个外围域都会由机载节点指派一个节点为该域的边界节点，负责与核心域中的机载节点通信；在路由建立阶段中，在网络会存在域间路由和域内路由两种类型的路由，层1域中的地面节点只需要获得本分域的路由表，而核心域中的机载节点需要获得全网的路由表，机载和地面节点都是采用最短路径算法获得所需的路由表。该路由算法能够充分考虑网络的特性，从而能够加快路由建立，增加收敛速度快，同时降低路由开销小，并且算法简单且可实现性高。

Description

一种空地一体无线自组织网络分域路由算法

技术领域

本发明涉及无线自组织网络路由技术领域，具体为一种空地一体无线自组织网络分域路由算法。

背景技术

立体化的通信系统是未来的信息化网络的核心组成。而目前的地面无线自组网可以通过空中通信节点系统扩展，延伸保障范围。空中通信平台主要由无人机和飞艇所携带的机载通信设备组成，飞行高度在3-6km之间，不超过10 公里；飞艇的飞行速度大约为80km/h-100km/h，而无人机的飞行速度则可以达到几百公里每小时。一般升空平台通信节点覆盖距离要求达到几百公里，节点之间也可以达到百公里级距离的通信(以下为方便计算说明有以300公里为例)。地面通信网主要由车载的电台组成，一般要求完成30km-50km左右距离的通信。要求空中平台和地面平台之间也可以做到互联互通，即要求远距离空空、空地、地地链路的可靠通信保证，以搭建空地一体的无线自组织网络。

然而，应用这种空地一体化的通信网络给网络路由带来的新挑战。已存在并广泛使用的无线路由方式的性质和功能并不适用于新型的立体通信系统。已有的、成熟的无线网络技术，一般都是针对地面网络架构，而很少考虑到空中平台和地面网络同时存在的场景。所以，必须设计适用于这种空地一体的路由算法，提高网络的连通率。

路由的基本算法有以下三种：

(1)距离向量算法(Distance Vetor Routing)

距离向量算法基于下面的计算公式：

其中，D(i,j)表示从节点i(节点为网络或路由器)到节点j的最短路径， d(i,k)表示从节点i到节点k的直接路径，也就是说节点i和k之间没有中介节点。具体运算步骤如下：

(a)所有的路由器建立一个路由表，使系统中的所有目的地址都出现在表中。每一表项内容包括目的地址和下一站地址，记为元组(N,G)。

(b)路由器周期性地向邻居发送更新分组，更新分组的内容为路由表中的所有信息。

(c)邻居路由器接收处理更新分组。设更新分组来自G'，根据更新分组计算到目的地址N的路由开销为D'，如果D'<D，采用新的路由(N,G')。如果当前路由表中所存放的相应下一站地址为G'，也就是G'＝G，采用新的路由，不管D'是大是小。

(2)链路状态算法(Link State Routing)

链路状态算法，或者称为SPF(Shortest Path First)算法，其思路可以分为以下4个部分来描述：

(a)发现该路由器的邻居，获取它们的网络地址，建立相邻关系，并测量到每个相邻路由器的开销或延迟。建立相邻关系是通过发送Hello分组来实现的。

(b)将用于交换的信息收集起来，构造包含这些信息的链路状态分组。创建链路状态分组的时机分两种，一种为定期创建，另一种就是当有事件发生时创建。

(c)通过Flood(扩散)算法，向所有的其他路由器发送该分组。如何可靠地发布链路状态分组在链路状态路由选择算法中占相当大的比重，链路状态算法实现的好坏在一定程度上取决于Flood算法的优劣。

(d)根据收集到的链路状态信息，通过Dijkstra算法，计算本路由器到全网其他路由器或网络的最短距离。

(3)混合路由选择算法

混合路由选择算法使用了路径矢量来度量，这种度量较传统的距离矢量算法使用的度量更为精确。混合路由选择算法基于时间驱动，而不是定时发生，可以显著的节约传输的带宽，而且它比距离矢量路由算法汇聚速度快。在某种程度上可以说混合路由选择算法综合了距离矢量和链路状态两种算法的优点。具有代表性的是EIGRP，即增强型内部网关路由协议。

其中，以上三种的每一种方法都有其优点，但是都是针对地面单层通信网络所设计的，没有考虑空地一体网络的特点。针对上述问题，特提出一种空地一体无线自组织网络分域路由算法。

发明内容

本发明的目的在于提供一种空地一体无线自组织网络分域路由算法，以解决上述背景技术中提出的问题。

为实现上述目的，本发明提供如下技术方案：一种空地一体无线自组织网络分域路由算法，算法可分为网络分域和路由建立这两个阶段；

网络分域阶段：在网络初始化过程中，根据节点通信能力，采用人工分域的方式，将网络分成两层，其中所有机载节点组成核心域(层2)，而所有地面节点确定各自所归属的外围域(层1)，同时，每个外围域都会由机载节点指派一个节点为该域的边界节点，负责与核心域中的机载节点通信；

路由建立阶段：在网络分域后，会存在域间路由和域内路由两种类型的路由，层1域中的地面节点只需要获得本分域的路由表，而核心域中的机载节点需要获得全网的路由表，机载和地面节点都是采用最短路径算法获得所需的路由表。

优选的，所述的网络分域阶段，在网络初始化过程中，根据节点通信能力，将空地一体的无线自组织网络采用人工分域的方式实现，具体步骤如下；

步骤101，机载节点组成核心域：该分域模型共分为两层结构，考虑到空间节点更远距离的通信能力，手动将机载节点设置为核心域内的节点，核心域起到核心中转区域的作用；

步骤102，地面节点确定自己所归属的外围域：根据地面节点分布位置的天然区分，手动将地面节点按区域进行划分，即相近的地面节点组成一个外围域，地面上所有的外围域共同组成层1，因此，在层1中，一个外围域内的节点之间可以相互通信，但是，不同外围域内的节点必须通过由机载节点构成的核心中转区域转发到相应的外围域内；

步骤103，选定边界节点：层1域中的每个外围域都会有一个边界节点，负责与层2域中的机载节点通信，而边界节点由离该外围域最近的一个机载节点随机地在其中选择一个节点作为边界路由节点，在边界路由节点出现故障后，将由机载节点重新选举新的边界节点。

优选的，所述的路由建立阶段，网络中存在两种类型的路由：域间路由和域内路由。其中，域间路由是核心域中所有机载节点通过路由算法获得全网路由表。域内路由和域间路由都运行最短路径算法计算到目的节点的最佳路径，从而获得所需路由表。

在执行最短路径算法中，将节点间的传输时延等价于距离，传输时延越短，节点间的距离就越近，因此最短路径算法的具体步骤为：

步骤1，选取域内任意节点a作为源顶点则有S＝{a}，将域内其它节点组成的集合定为U_a；

步骤2，获得节点a到U_a集合中各个节点的距离，选取距离最小的节点 k，将其按顺序放入S集合，即S＝{a,k},同时，更新集合U_a中的元素，即 U_a＝U_a-{k}；

步骤3，以选定的节点k为源顶点的中继顶点，获得从节点a经过节点k 到U_a中各个节点的距离，选取距离最小的节点按顺序加入到S集合，并更新集合U_a中的元素；

步骤4，重复步骤3直至集合U_a为空，此时，节点a就获得到域内所有其它节点的路由信息。

与现有技术相比，本发明的有益效果是：一种空地一体无线自组织网络分域路由算法，路由建立和收敛速度快且开销小，外围域内的节点只需要维护本区域的路由表，因此网络的路由建立时间大大降低且路由开销小。当网络发送变化时，只需要更新本区域的路由表，所以路由收敛的时间也快，算法简单，可实现性高。从最短路由算法可看出，每个节点在获得路由表过程中，需要的先验信息少，算法复杂度低。同时，该算法考虑两种机载节点和地面节点的特性，将网络管理和数据转发放在功能较强且通信稳定的机载节点上，增加的方案的可实现性。

附图说明

图1为典型的分区场景示意图；

图2为分域及路由表建立过程；

图3为最短路径算法流程图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

请参阅图1-3，本发明提供一种技术方案：一种空地一体无线自组织网络分域路由算法，算法可分为网络分域和路由建立这两个阶段；

网络分域阶段：在网络初始化过程中，根据节点通信能力，采用人工分域的方式，将网络分成两层，其中所有机载节点组成核心域(层2)，而所有地面节点确定各自所归属的外围域(层1)，同时，每个外围域都会由机载节点指派一个节点为该域的边界节点，负责与核心域中的机载节点通信；

路由建立阶段：在网络分域后，会存在域间路由和域内路由两种类型的路由，层1域中的地面节点只需要获得本分域的路由表，而核心域中的机载节点需要获得全网的路由表，机载和地面节点都是采用最短路径算法获得所需的路由表。

所述的网络分域阶段，在网络初始化过程中，根据节点通信能力，将空地一体的无线自组织网络采用人工分域的方式实现，具体步骤如下；

步骤101，机载节点组成核心域：该分域模型共分为两层结构，考虑到空间节点更远距离的通信能力，手动将机载节点设置为核心域内的节点，核心域起到核心中转区域的作用；

步骤102，地面节点确定自己所归属的外围域：根据地面节点分布位置的天然区分，手动将地面节点按区域进行划分，即相近的地面节点组成一个外围域，地面上所有的外围域共同组成层1，因此，在层1中，一个外围域内的节点之间可以相互通信，但是，不同外围域内的节点必须通过由机载节点构成的核心中转区域转发到相应的外围域内；

步骤103，选定边界节点：层1域中的每个外围域都会有一个边界节点，负责与层2域中的机载节点通信，而边界节点由离该外围域最近的一个机载节点随机地在其中选择一个节点作为边界路由节点，在边界路由节点出现故障后，将由机载节点重新选举新的边界节点。

所述的路由建立阶段，网络中存在两种类型的路由：域间路由和域内路由，其中，域间路由是核心域中所有机载节点通过路由算法获得全网路由表，域内路由和域间路由都运行最短路径算法计算到目的节点的最佳路径，从而获得所需路由表。

在执行最短路径算法中，将节点间的传输时延等价于距离，传输时延越短，节点间的距离就越近，因此最短路径算法的具体步骤为：

步骤1，选取域内任意节点a作为源顶点则有S＝{a}，将域内其它节点组成的集合定为U_a；

步骤2，获得节点a到U_a集合中各个节点的距离，选取距离最小的节点 k，将其按顺序放入S集合，即S＝{a,k},同时，更新集合U_a中的元素，即 U_a＝U_a-{k}；

步骤3，以选定的节点k为源顶点的中继顶点，获得从节点a经过节点k 到U_a中各个节点的距离，选取距离最小的节点按顺序加入到S集合，并更新集合U_a中的元素；

步骤4，重复步骤3直至集合U_a为空，此时，节点a就获得到域内所有其它节点的路由信息。

路由建立和收敛速度快且开销小，外围域内的节点只需要维护本区域的路由表，因此网络的路由建立时间大大降低且路由开销小。当网络发送变化时，只需要更新本区域的路由表，所以路由收敛的时间也快，算法简单，可实现性高。从最短路由算法可看出，每个节点在获得路由表过程中，需要的先验信息少，算法复杂度低。同时，该算法考虑两种机载节点和地面节点的特性，将网络管理和数据转发放在功能较强且通信稳定的机载节点上，增加的方案的可实现性。

在本发明的描述中，需要理解的是，术语“同轴”、“底部”、“一端”、“顶部”、“中部”、“另一端”、“上”、“一侧”、“顶部”、“内”、“前部”、“中央”、“两端”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。

在本发明中，除非另有明确的规定和限定，术语“安装”、“设置”、“连接”、“固定”、“旋接”等术语应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或成一体；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通或两个元件的相互作用关系，除非另有明确的限定，对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。

尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。

Claims (3)

1.一种空地一体无线自组织网络分域路由算法，其特征在于，算法可分为网络分域和路由建立这两个阶段；

网络分域阶段：在网络初始化过程中，根据节点通信能力，采用人工分域的方式，将网络分成两层，其中所有机载节点组成核心域（层2），而所有地面节点确定各自所归属的外围域（层1），同时，每个外围域都会由机载节点指派一个节点为该域的边界节点，负责与核心域中的机载节点通信；

路由建立阶段：在网络分域后，会存在域间路由和域内路由两种类型的路由，层1域中的地面节点只需要获得本分域的路由表，而核心域中的机载节点需要获得全网的路由表，机载和地面节点都是采用最短路径算法获得所需的路由表。

2.根据权利要求1所述的一种空地一体无线自组织网络分域路由算法，其特征在于，所述的网络分域阶段，在网络初始化过程中，根据节点通信能力，将空地一体的无线自组织网络采用人工分域的方式实现，具体步骤如下；

步骤101，机载节点组成核心域：该分域模型共分为两层结构，考虑到空间节点更远距离的通信能力，手动将机载节点设置为核心域内的节点，核心域起到核心中转区域的作用；

步骤102，地面节点确定自己所归属的外围域：根据地面节点分布位置的天然区分，手动将地面节点按区域进行划分，即相近的地面节点组成一个外围域，地面上所有的外围域共同组成层1，因此，在层1中，一个外围域内的节点之间可以相互通信，但是，不同外围域内的节点必须通过由机载节点构成的核心中转区域转发到相应的外围域内；

步骤103，选定边界节点：层1域中的每个外围域都会有一个边界节点，负责与层2域中的机载节点通信，而边界节点由离该外围域最近的一个机载节点随机地在其中选择一个节点作为边界路由节点，在边界路由节点出现故障后，将由机载节点重新选举新的边界节点。

3.根据权利要求1所述的一种空地一体无线自组织网络分域路由算法，其特征在于，所述的路由建立阶段，网络中存在两种类型的路由：域间路由和域内路由，其中，域间路由是核心域中所有机载节点通过路由算法获得全网路由表，域内路由和域间路由都运行最短路径算法计算到目的节点的最佳路径，从而获得所需路由表，在执行最短路径算法中，将节点间的传输时延等价于距离，传输时延越短，节点间的距离就越近，因此最短路径算法的具体步骤为：

步骤1，选取域内任意节点a作为源顶点则有S={a}，将域内其它节点组成的集合定为U_a；

步骤2，获得节点a到U_a集合中各个节点的距离，选取距离最小的节点k，将其按顺序放入S集合，即S={a,k},同时，更新集合U_a中的元素，即U_a=U_a-{k}；

步骤3，以选定的节点k为源顶点的中继顶点，获得从节点a经过节点k到U_a中各个节点的距离，选取距离最小的节点按顺序加入到S集合，并更新集合U_a中的元素；

步骤4，重复步骤3直至集合U_a为空，此时，节点a就获得到域内所有其它节点的路由信息。