CN103108374B - 一种混合结构矿井应急救援无线网状网的节能路由算法 - Google Patents

Abstract

本发明公开了一种混合结构矿井应急救援无线网状网的节能路由算法，包括以下步骤：步骤1：设置节点类型信息；步骤2：将Mesh无线终端的通信状态分为了三种类型，即“内部”状态、“边缘”状态以及“修复”状态；步骤3：每个Mesh终端节点维护一个Mesh骨干路由节点列表；步骤4：若发现第一Mesh终端处于“内部”状态，则直接根据Mesh骨干路由节点列表信息，选择与网关距离最近的邻居骨干路由节点，建立到达网关的路由。

Description

一种混合结构矿井应急救援无线网状网的节能路由算法

技术领域

本发明涉及网络技术领域，尤其涉及一种混合结构矿井应急救援无线网状网的节能路由算法。

背景技术

无线网状网，又称为无线Mesh网络，是一种能够实现自组网、自配置的无线多跳中继网络。无线网状网扩展不依赖有线基础设施，能够快速组网，具有灵活、便携、环境适应能力强等应用特性，是构建煤矿井下应急救援无线通信网络的优势技术。其中，基于混合网状网结构的井下应急救援无线网状网因其网络路径冗余度高，具有较强的传输鲁棒性，成为了研究热点。基于混合网状网结构的煤矿井下应急救援无线网状网结构如图1所示。

在基于混合网状网结构的矿井应急救援无线Mesh网络中，无线Mesh终端与Mesh骨干路由节点一样具有路由转发功能。由于现有无线网状网路由协议不区分网络节点类型，因此无线Mesh终端在执行其应用功能的基础上需承担额外的路由转发任务，这对无线Mesh终端的能量配置提出了较高要求。而在井下应急救援场景中，无线终端设备的能量储备较低，终端能耗问题严重制约了矿井应急救援通信系统的工作时长。

发明内容

本发明解决的技术问题在于提供一种路由算法，基于该算法可在保证矿井应急救援无线网状网的路由效率的前提下，尽量减少网络中的无线Mesh终端的中继能量消耗。

本发明实施例公开了一种混合结构矿井应急救援无线网状网的节能路由算法，包括以下步骤：

步骤1：设置节点类型信息，记为T，并规定T=1表示Mesh骨干路由节点，T=2表示无线Mesh终端节点；

步骤2：将Mesh无线终端的通信状态分为了三种类型，即“内部”状态、“边缘”状态以及“修复”状态，所述“内部”状态是指Mesh终端的通信范围内具有可达网关的骨干路由节点的情况；所述“边缘”状态是指Mesh终端的通信范围内不包含任何Me s h骨干路由节点的场景；所述“修复”状态是指Mesh终端的通信范围内包含Mesh骨干路由节点，但是这些骨干路由节点发生了故障或者与网关连接中断的情况；

步骤3：每个Mesh终端节点维护一个Mesh骨干路由节点列表，该列表记录了当前Mesh终端通信范围内的骨干路由节点的地址、有效期以及到达网关的跳数信息；若Mesh终端的Mesh骨干路由节点列表为空时，则说明当前节点为“边缘”状态；若不为空，且具有可达网关的骨干路由邻居节点，则表明当前节点为“内部”状态；否则，说明当前节点处于“修复”状态；

步骤4：若发现第一Mesh终端处于“内部”状态，则直接根据Mesh骨干路由节点列表信息，选择与网关距离最近的邻居骨干路由节点，建立到达网关的路由。

进一步，作为优选，在所述步骤4之后还包括以下步骤：

若发现第一Mesh终端处于“边缘”状态，则将启动基于请求-应答方式的路由发现机制，生成RREQ消息并向外广播；

接收到该RREQ信息的第二Mesh终端检查本地状态，若检查结果为“内部”状态，则首先根据RREQ消息更新第二Mesh终端到达第一Mesh终端以及上一跳节点的反向路由，然后根据自身到达网关的路由信息，产生一个RREP，并沿反向路径发送给第一Mesh终端；若检查结果为“边缘”状态或者“修复”状态，首先根据RREQ消息更新第二Mesh终端到达第一Mesh终端以及上一跳节点的反向路由，然后设置链路类型的路径权重，在第二Mesh终端更新RREQ消息中的节点类型信息、请求类型消息、跳数、链路类型的路径权重以及相关的地址序列号信息，并将更新后的RREQ消息向外广播。

进一步，作为优选，在所述步骤4之后还包括以下步骤：

若发现第一Mesh终端处于“修复”状态，则将启动基于请求-应答方式的路由发现机制，生成RREQ消息并向外广播；

若接收节点为第二Mesh终端时，接收到该RREQ信息的第二Mesh终端检查本地状态，若检查结果为“内部”状态，则首先根据RREQ消息更新第二Mesh终端到达第一Mesh终端以及上一跳节点的反向路由，然后根据自身到达网关的路由信息，产生一个RREP，并沿反向路径发送给第一Mesh终端；若检查结果为“边缘”状态或者“修复”状态，首先根据RREQ消息更新第二Mesh终端到达第一Mesh终端以及上一跳节点的反向路由，然后设置链路类型的路径权重，在第二Mesh终端更新RREQ消息中的节点类型信息、请求类型消息、跳数、链路类型的路径权重以及相关的地址序列号信息，并将更新后的RREQ消息向外广播；

若接收节点为骨干路由节点时，首先根据RREQ消息更新第二Mesh终端到达第一Mesh终端以及上一跳节点的反向路由，然后在第二Mesh终端更新RREQ消息中的节点类型信息、跳数、链路类型的路径权重以及相关的地址序列号等信息，并将更新后的RREQ消息继续向外广播。

本发明通过采用基于“状态”的路由选择机制，减少了RREQ路由请求消息的使用几率与广播范围，减少了Mesh终端用于中继广播RREQ消息的能量开销，同时降低了网络中的路由发现请求带宽开销，增加了路由效率，提高了网络的吞吐性能、稳定性与实时性。

附图说明

当结合附图考虑时，通过参照下面的详细描述，能够更完整更好地理解本发明以及容易得知其中许多伴随的优点，但此处所说明的附图用来提供对本发明的进一步理解，构成本发明的一部分，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定，其中：

图1为基于混合网状网结构的矿井应急救援无线网络结构图。

图2（a）为终端通信状态为“内部”状态的路由发现示例图。

图2（b）为终端通信状态为“边缘”状态的路由发现示例图。

图2（c）为终端通信状态为“修复”状态的路由发现示例图。

图3为RAODV协议中的HELLO报文格式。

图4为RAODV中RREQ的报文格式。

图5为网络吞吐量性能仿真曲线。

图6为网络端到端时延性能仿真曲线。

具体实施方式

参照图1-6对本发明的实施例进行说明。

为使上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

根据矿井应急救援通信场景中无线终端主要与网关通信的应用特性，本发明设计基于以下应用背景：

●    所有Mesh终端仅与网关进行通信；

●    Mesh骨干路由节点与网关之间采用先应式路由协议，任意骨干路由节点日常维护到达网关的路由信息。

按需距离矢量路由协议（ad hoc on demand distance vector routing,AODV）是无线网状网使用最为广泛的路由协议，且有研究表明该协议相比DSR、OLSR等路由协议在煤矿井下环境中的传输性能最好，据此，本发明延用了AODV路由协议中的基于请求-应答机制的路由发现与路由修复模式，并以减少无线Mesh终端的路由转发任务为目的，进行了具体的路由机制设计，因此本发明又称为改进型

AODV路由协议，简称RAODV路由协议。该协议的基本路由原理如下：

本发明根据无线Mesh终端的通信状态，将矿井应急救援无线网状网中的任意无线终端的通信状态分为了三种类型，即“内部”状态、“边缘”状态以及“修复”状态，分别如图2（a）、2（b）与2（c）中所示。在此基础上RAODV定义了Mesh终端在不同状态下的路由发现方式。

“内部”状态是指当前Mesh终端的通信范围内具有可达网关的骨干路由节点的情况。此时，采用ROADV的Mesh终端将采用类似AP模式的通信方式，直接通过骨干路由节点接入骨干传输网络，然后利用骨干传输网络实现与网关的信息交互。该方法避免了通过广播路由请求消息（Route Request，RREQ）进行路由发现，从而减少了Mesh终端对RREQ消息的中继广播能耗。图2（a）中的终端节点S即处于“内部”状态，其采用RAODV路由策略与网关D建立的路径如图中实线箭头所示，可见该路径不包含Mesh终端节点。

“边缘”状态是指Mesh终端的通信范围内不包含任何Mesh骨干路由节点的场景。此时，Mesh终端无法直接通过Mesh骨干路由节点接入骨干传输网络，需启用基于请求-应答方式的路由发现机制，向外广播RREQ请求消息，通过借助相邻的无线Mesh终端接入骨干传输网络。如图2（b）中节点S即为“边缘”节点，在RAODV策略下，其向外广播RREQ路由请求，该请求到达Mesh终端R时，由于R处于“内部”状态，所以R将停止对RREQ继续广播，并向S返回经由它接入骨干传输网络的传输路径，最后建立的路径如图中实线箭头所示。

“修复”状态是指Mesh终端的通信范围内包含Mesh骨干路由节点，但是这些骨干路由节点发生了故障或者与网关连接中断的情况，如图2（c）所示。此时，采用RAODV路由策略的Mesh终端同样启用基于请求-应答方式的路由修复机制，向外广播RREQ消息，并在所发现的路径中选择经过Mesh终端数目最少的路径作为最终路由返回源节点S，最终建立的路径如图中实线箭头所示。

为了实现上述不同“状态”下的路由过程，RAODV对AODV的路由协议内容进行了如下改进。

①为了使路由选择过程能够识别节点类型，RAODV在原AODV路由机制中引入了节点类型信息，记为T，并规定T=1表示Mesh骨干路由节点，T=2表示无线Mesh终端节点。

②为了方便获得当前Mesh终端的通信状态，RAODV在原有邻居列表的基础上增加了Mesh骨干路由节点列表，其数据结构如下：

每个Mesh终端节点维护一个Mesh骨干路由节点列表，该列表记录了当前Mesh终端通信范围内的骨干路由节点的地址、有效期以及到达网关的跳数等信息。若当前Mesh终端的Mesh骨干路由节点列表为空时，则说明当前节点为“边缘”状态；若不为空，且具有可达网关的骨干路由邻居节点，则表明为当前节点为“内部”状态；否则，说明当前节点处于“修复”状态。

③Mesh骨干路由节点列表通过HELLO消息进行维护。AODV中原HELLO消息不区分节点类型，且不传递本地到达网关的跳数信息。为了能够建立Mesh骨干路由节点列表，RAODV在原HELLO消息的保留字段中取出了2比特用于表示节点类型信息，如图3所示；同时，规定当T=1时，HELLO消息中的“跳数”字段等于本地到达网关的跳数，从而在不增加HELLO数据包大小的情况下实现了节点类型与到达网关跳数信息的传递。当收到T=1的HELLO消息时，Mesh终端将根据消息信息进行本地Mesh骨干路由节点列表的维护与更新。

④为使基于请求-应答的路由发现机制能够识别不同的通信“状态”，RAODV在AODV的RREQ报文中的“保留字段”中取出8比特用来表示请求类型信息rq_mode，如图4所示，并规定rq_mode=0x00表示“内部”状态，rq_mode=0x01表示“边缘”状态，rq_mode=0x02表示“修复”状态。当RREQ到达一个Mesh终端节点时，将根据该Mesh终端的状态更新其rq_mode值；当RREQ报文到达一个骨干路由节点时，其rq_mode值不变。

⑤为了使基于请求-应答方式的路由发现过程能够避免使用Mesh终端进行路由中继，RAODV提出了基于链路类型的路径权重路由判据，记为rt_weight，规定每条骨干传输链路的rt_weight等于1/3，其他与Mesh终端相连的非骨干传输链路的rt_weight等于1。

⑥为了使RREQ消息能够识别所经过的链路类型并记录所经过路径的rt_weight值，RAODV在原AODV的RREQ报文中另外加入了发送节点类型T与rt_weight两个字段，如图4所示。当当前节点的类型与RREQ中的T字段均显示为Mesh骨干路由节点时，说明RREQ的上一跳链路为骨干传输链路，此时令rt_weight增加1/3，否则，令rt_weight增加1。通过选择rt_weight值最小的路径，有效减少了数据传输路径中所包含的Mesh终端数量。在图2（c）中，实线箭头与虚线箭头分别指示了RAODV采用rt_weight作为路由判据所选择的路径与AODV基于跳数判据所选择的路径，如图所示，RAODV所选择的路径最大程度地减少了传输路径中的Mesh终端中继节点。从而降低了Mesh终端在数据传输中的路由转发任务，节约了Mesh终端能量。

下面结合图2，对本发明RAODV路由协议的具体实施过程进行了具体介绍。

假设在矿井应急救援无线网状网中，任意Mesh终端S希望与网关D进行通信，但发现本地路由表中不存在到达D的有效路由信息，此时节点S将通过查看本地Mesh骨干路由节点列表检查本地状态：

若发现当前自身处于“内部”状态，此时直接根据Mesh骨干路由节点列表信息，选择与网关距离最近的邻居骨干路由节点，建立到达网关的路由，然后将信息上传到骨干传输网络。在该情况下建立的传输路径如图2（a）所示。

若发现本地处于“边缘”状态或者“修复”状态，此时将启动基于请求-应答方式的路由发现机制，生成RREQ消息并向外广播。

矿井应急救援WMN中的任意节点接收到此RREQ消息后，将执行以下操作。

①检查RREQ消息的rq mode。

若{rq_mode=0x01}，表明上一跳无线Mesh终端节点处于“边缘”状态，因此接收到RREQ的节点只可能为Mesh终端。接收到该RREQ信息的Mesh终端检查本地状态。若检查结果为“内部”状态，则执行第②步；若为“边缘”状态或者“修复”状态，则执行第③步。

若{rq_mode=0x02}，表明上一跳Mesh终端节点处于“修复”状态。此时，接收节点可能为Mesh终端节点，也可能为骨干路由节点。若接收节点为Mesh终端时，其处理方式与上述{rq_mode=0x01}时的处理方式相同，即根据本地状态执行步骤②或者步骤③；若接收节点为骨干路由节点时，则执行第④步。

②首先根据RREQ消息更新本地到达源节点S以及上一跳节点的反向路由，然后根据自身到达网关的路由信息，产生一个RREP，并沿反向路径发送给S。

③首先根据RREQ消息更新本地到达源节点S以及上一跳节点的反向路由，然后本地更新RREQ消息中的T、rq_mode、跳数、rt_weight以及相关的地址序列号等信息，并将更新后的RREQ消息向外广播。

④首先根据RREQ消息更新本地到达源节点S以及上一跳节点的反向路由，然后本地更新RREQ消息中的T、跳数、rt_weight以及相关的地址序列号等信息，骨干路由节点不更新rq_mode信息，并将更新后的RREQ消息继续向外广播。

比较图2中的RAODV与AODV的传输路径可知，RAODV路由策略成功减少了Mesh终端模式下矿井应急救援WMN网络中Mesh终端的中继转发任务，有效解决了该模式下的Mesh终端能耗问题。且不难发现，矿井应急救援WMN网络的部署规模越大，越多的Mesh终端可免于承担额外的RREQ广播以及对数据包的路由转发任务，RADOV的节能优势将越明显。仿真结果：

假设矿井应急救援无线Mesh网络的骨干传输网络的传输容量为C，Mesh终端产生的业务量为F。基于Mesh终端模式的矿井应急救援WMN的网络容量包括Mesh终端的传输带宽，所以应急救援WMN的整体容量要高于骨干传输网络的传输容量C。AODV路由协议不区分节点类型，因此从理论上讲，AODV比RAODV更能充分地利用Mesh终端的带宽资源。但是，在实际应用中，利用RAODV的W-URN吞吐性能是否低于采用AODV的网络的吞吐性能呢？针对该问题，仿真中特意设置了F>C与F<C两种不同的通信场景，比较分析了当F>C与F<C时RAODV的传输性能。为验证RAODV的路由恢复能力，仿真中还设置了30秒时刻任意骨干路由节点发生故障的场景。

图5为当采用RAODV路由协议时的网络吞吐量的仿真结果，结果表明，当F>C时，RAODV并不会因为避免使用Mesh终端进行路由中继使网络的吞吐性能降低，相反，由于RAODV减少了RREQ的广播带宽开销，相比AODV使矿井应急救援无线Mesh网络的吞吐量与传输稳定性提高；

图6为当采用RAODV路由协议时网络平均端到端时延的仿真结果。如图所示，当F<C时，RAODV与AODV的时延曲线存在两处明显的差别，即AODV在0秒与30秒时刻其时延曲线出现了两次明显的上跳。0秒与30秒分别为首次进行路由发现与事故后进行路由修复的起始时刻，因此该跳跃时延反应了相应路由策略的路由收敛时间。由仿真结果可知，RAODV的路由收敛时延要远远低于AODV。出现这种差距的原因在于RAODV的RREQ消息主要由Mesh骨干路由节点进行转发，Mesh骨干传输网络的网络复杂度相比整个矿井应急救援Mesh网络的复杂度大大降低，由此有效减少了RREQ消息在广播过程中以及路由应答消息在返回中所遇到的传输干扰，从而使源节点与目的节点之间能够快速建立连接。

图5与图6中的30秒之后的仿真曲线显示了当骨干路由节点发生故障后的网络的吞吐量与平均端到端时延的仿真结果。仿真结果表明，当意外发生后，RAODV的传输稳定性明显高于AODV，尤其当F<C时，RAODV的恢复时延仅为AODV的1/4，具有快速的路由恢复能力。

虽然以上描述了本发明的具体实施方式，但是本领域的技术人员应当理解，这些具体实施方式仅是举例说明，本领域的技术人员在不脱离本发明的原理和实质的情况下，可以对上述方法和系统的细节进行各种省略、替换和改变。例如，合并上述方法步骤，从而按照实质相同的方法执行实质相同的功能以实现实质相同的结果则属于本发明的范围。因此，本发明的范围仅由所附权利要求书限定。

Claims (1)

1.一种混合结构矿井应急救援无线网状网的节能路由算法，其特征在于，包括以下步骤：

步骤1：设置节点类型信息，记为T，并规定T＝1表示Mesh骨干路由节点，T＝2表示无线Mesh终端节点；

步骤2：将Mesh无线终端的通信状态分为了三种类型，即“内部”状态、“边缘”状态以及“修复”状态，所述“内部”状态是指Mesh终端的通信范围内具有可达网关的骨干路由节点的场景；所述“边缘”状态是指Mesh终端的通信范围内不包含任何Mesh骨干路由节点的场景；所述“修复”状态是指Mesh终端的通信范围内包含Mesh骨干路由节点，但是这些骨干路由节点发生了故障或者与网关连接中断的情况；

步骤3：每个Mesh终端节点维护一个Mesh骨干路由节点列表，该列表记录了当前Mesh终端通信范围内的骨干路由节点的地址、有效期以及到达网关的跳数信息；若Mesh终端的Mesh骨干路由节点列表为空时，则说明当前节点为“边缘”状态；若不为空，且具有可达网关的骨干路由邻居节点，则表明当前节点为“内部”状态；否则，说明当前节点处于“修复”状态；

步骤4：若发现第一Mesh终端处于“内部”状态，则直接根据Mesh骨干路由节点列表信息，选择与网关距离最近的邻居骨干路由节点，建立到达网关的路由；

若发现第一Mesh终端处于“边缘”状态，则将启动基于请求-应答方式的路由发现机制，生成RREQ消息并向外广播；

接收到该RREQ信息的第二Mesh终端检查本地状态，若检查结果为“内部”状态，则首先根据RREQ消息更新第二Mesh终端到达 第一Mesh终端以及上一跳节点的反向路由，然后根据自身到达网关的路由信息，产生一个RREP，并沿反向路径发送给第一Mesh终端；若检查结果为“边缘”状态或者“修复”状态，首先根据RREQ消息更新第二Mesh终端到达第一Mesh终端以及上一跳节点的反向路由，然后设置链路类型的路径权重，在第二Mesh终端更新RREQ消息中的节点类型信息、请求类型消息、跳数、链路类型的路径权重以及相关的地址序列号信息，并将更新后的RREQ消息向外广播；若发现第一Mesh终端处于“修复”状态，则将启动基于请求-应答方式的路由发现机制，生成RREQ消息并向外广播；

若接收节点为第二Mesh终端时，接收到该RREQ信息的第二Mesh终端检查本地状态，若检查结果为“内部”状态，则首先根据RREQ消息更新第二Mesh终端到达第一Mesh终端以及上一跳节点的反向路由，然后根据自身到达网关的路由信息，产生一个RREP，并沿反向路径发送给第一Mesh终端；若检查结果为“边缘”状态或者“修复”状态，首先根据RREQ消息更新第二Mesh终端到达第一Mesh终端以及上一跳节点的反向路由，然后设置链路类型的路径权重，在第二Mesh终端更新RREQ消息中的节点类型信息、请求类型消息、跳数、链路类型的路径权重以及相关的地址序列号信息，并将更新后的RREQ消息向外广播；

若接收节点为骨干路由节点时，首先根据RREQ消息更新第二Mesh终端到达第一Mesh终端以及上一跳节点的反向路由，然后在第二Mesh终端更新RREQ消息中的节点类型信息、跳数、链路类型的路径权重以及相关的地址序列号等信息，并将更新后的RREQ消息继续向外广播。