一种基于链路质量的移动自组织网络按需路由方法

摘要

本发明公开了一种基于链路质量的移动自组织网络按需路由方法，针对基于最短条数的移动自组织网络按需路由算法无法发现最可靠的路径的问题，通过将无线链路质量转换成路由发现优先级，进而转换成路由发现时延，源节点和各中间节点根据时延向各自的邻居节点发送路由请求报文，节点第一次收到路由请求报文时转发，对再次收到的路由请求报文直接丢弃，以保证具有最优链路状态的路径能够被选为路由路径。采用本发明的路由发现方法，可以在移动自组织网络中发现最优路由。另外，本发明还在路由发现基础上加入了路由状态维护的方案，可以发现移动自组织网络中的故障节点进和不稳定链路，以便实时更新最优路由。

说明书

技术领域

本发明属于网络路由技术领域，更为具体地讲，涉及一种基于链路质量的移动自组织网络按需路由方法。

背景技术

移动自组织网络是由若干可移动的通信节点构成的无固定设置的、可快速组建的多跳无线通信网络。移动自组织网络具有网络拓扑结构动态变化、自组织无中心节点、无线传输带宽有限等特点。由于移动自组织网络拓扑变化较快，信道带宽有限，网络短暂分裂几率高，常用的以路由条数为准则的路由算法很难适用于移动自组织网络，要实现可靠稳定的无线多跳路由必须研究专用路由协议，现有移动自组织网络的路由协议可分为两大类：按照路由建立的方式不同，可分为先应式（主动）路由协议、按需（被动）路由协议等。

先应式路由协议又称为表驱动(Table-driven)路由协议。在这种路由协议中，采用周期性的路由分组广播的方式来交换路由信息。每个节点无论当前是否需要通信，都要建立和维护一张或多张表格，这些表格包含到达网络中其他所有节点的路由信息。当检测到网络拓扑结构发生变化时，节点在网络中发送更新消息。收到更新消息的节点更新自己的表格，以维护及时、准确的路由信息。不同的先应式路由协议的区别在于拓扑更新消息在网络中传播的方式和需要的存储表的类型不同。先应式路由协议不断地检测链路质量，时刻维护准确的网络拓扑和路由信息。优点是当节点要发送一个数据分组到达另一个节点时，只要路由存在，发送分组的延时就很小；缺点是先应式路由协议需要花费较高的代价，如带宽、电源、CPU等，而且动态变化的拓扑结构又可能使高价得来的路由表中的内容变成无效信息，路由协议始终处于不收敛状态。典型的先应式路由协议有：DSDV（Destination-Sequenced Distance-Vector Routing，目的序列距离矢量路由）协议、WRP（Wireless Routing Protocol，无线路由）协议、OLSR（Optimized Link State Routing，最优链路状态路由）协议、STAR（SourceTree-Adaptive Routing，源树自适应路由）协议和TBRPF（Topology BroadcastBased on Reverse Path Forwarding，基于逆向路径转发的拓扑分发）协议等。

按需路由协议又称为反应式路由协议，是专为Ad Hoc网络而设计的路由协议。按需路由协议根据发送节点的需要，按需地进行路由发现过程，网络拓扑结构信息和路由表内容也是按需建立的，所以其内容可能仅仅是整个网络拓扑结构信息的一部分。按需路由协议的优点是不需要周期性的广播路由信息，节省了有限的网络资源；缺点是在发送数据分组时，若是没有到达目的节点的路由，要启动路由发现过程来寻找路由，所以数据分组需要等待一定时间的延时。另外，由于路由发现和路由维护仅存在于高层应用有需求的时刻，这类路由协议一般只能感知局部的最优链路，却很难感知全局的最优链路。按需的常见路由协议一般是基于距离矢量的，而缺乏一种基于最优链路状态的按需路由协议。

发明内容

本发明的目的在于克服现有技术的不足，提供一种基于链路质量的移动自组织网络按需路由方法，使得到的路由具有最优链路状态。

为实现上述发明目的，本发明基于链路质量的移动自组织网络按需路由方法，其特征在于包括：

S1：每个活动节点i在加入网络之后每隔T₀秒广播一条HELLO消息，包括消息类型和该节点地址，与此同时监听其他节点发送来的HELLO消息；若某节点i在预设时间T_s内收到节点j发出的HELLO消息为N_ij＞0个，则节点j是节点i的邻居节点，在节点i的邻居列表中记录节点j的地址ADD_j和节点i与节点j的链路质量$>q_{\mathrm{ij}}=\frac{T_0{N}_{\mathrm{ij}}}{T_s};$>

S2：当数据源节点x需要向目的节点y发送数据时，如果源节点x和目的节点y之间已存在有效路由，则直接发送数据，如果不存在有效路由，进入步骤S3进行路由发现；

S3：源节点x构造路由请求RREQ消息，包括消息类型、跳数、路由请求标识、路由请求发起节点地址、路由请求目的节点地址、上一跳节点地址，此时跳数值为0，上一跳节点地址为源节点地址；源节点将RREQ消息延迟发送给源节点的所有邻居节点m₁,m₁＝1,2,3,...,N_x，邻居节点m₁的延迟时间为秒，其中A为预设的负数参数，为邻居节点m₁与源节点x的链路质量，N_x为源节点x邻居列表中所存放的邻居数；

S4：当网络中某个节点接收到RREQ消息时，提取路由请求标识和路由请求发起节点地址，判断本节点路由表中是否已存在该路由请求标识和路由请求发起节点地址，如果存在，则将该RREQ消息抛弃；如果不存在，进入步骤S5；

S5：本节点在路由表中建立一个新的路由表项，其目的地址为RREQ消息中的路由请求发起节点地址，下一跳节点地址为RREQ消息中的上一跳节点地址，标识号为RREQ消息中的路由请求标识，距离值为RREQ消息中的跳数值；判断路由请求目的节点地址是否为本节点地址，如果是，进入步骤S7，如果不是，进入步骤S6；

S6：将RREQ消息中的跳数值加1，上一跳节点地址更改为本节点地址，再将RREQ消息延迟转发给本节点邻居节点m₂,m₂＝1,2,3,...,N_z中除上一跳以外的其他邻居节点，节点m₂延迟时间为秒，其中为节点m₂与本节点的链路质量，N_z为本节点邻居列表中所存放的邻居数；返回步骤S4；

S7：目的节点y根据路由表向源节点x回复路由回复RREP消息，包括消息类型、跳数、路由回复标识、路由回复发起节点地址、路由回复目的节点地址、上一跳节点地址，此时跳数值为0，上一跳节点地址为目的节点地址，路由回复目的节点地址为源节点地址；

S8：当某节点接收到RREP消息，在路由表中建立一个新的路由表项，其目的地址为RREP消息中的路由回复发起节点地址，下一跳节点地址为RREP消息中的上一跳节点地址，标识号为RREP消息中的路由回复标识，距离值为RREP消息中的跳数值，进入步骤S9；

S9：判断路由回复节点地址是否是本节点地址，如果是，进入步骤S11，如果不是，进入步骤S10；

S10：将RREP消息中的跳数值加1，上一跳节点地址更改为本节点地址，根据路由表转发给指向路由回复目的节点地址的下一跳节点地址，返回步骤S8；

S11：路由发现结束，源节点根据得到的有效路由向目的节点发送数据。

进一步地，本发明基于链路质量的移动自组织网络按需路由方法还包括步骤S12：每个节点分别为每个路由表项维护一个计时器，当有数据包使用某个路由表项时则将相应计时器清0，当计时器数值达到预设值T_over时，则将相应路由表项删除。

进一步地，本发明基于链路质量的移动自组织网络按需路由方法，还包括路由维护，路由维护方法包括以下步骤：

S2.1：有效路由建立后，目的节点持续向源节点以周期T₁重复回复RREP消息，源节点和中间节点中的每个节点l均监听RREP消息，分别统计预设时间T_r内接收到的来自目的节点的RREP消息个数，连续统计n个T_r内的RREP消息个数M_l,t,t＝1,2,…,n，n为预设参数，根据以下公式计算路由质量：

$>p_{l,t}=\frac{T_1{M}_{l,r}}{T_s}$>

其中下标越小表示数据越新；

S2.2：每个节点l均判断是否p_l,1＞λmin(p_l,2,p_l,3,…,p_l,n)，λ,0＜λ＜1为预设参数，如果p_l,1＞λmin(p_l,2,p_l,3,…,p_l,n)，返回步骤S2.1继续监听RREP消息；如果p_l,1≤λmin(p_l,2,p_l,3,…,p_l,n)，该路由不稳定，进入步骤S2.3；

S2.3：节点l根据其路由表生成路由错误RRER消息，包括不稳定路由的目的节点地址、当前节点地址和当前节点与源节点之间的跳数，发送给源节点，源节点重新发起一次对目的节点的路由发现；

S2.4：当中间节点和源节点收到RERR消息后，提取出RERR消息中的跳数值Hops，计算等待时间T_w＝T_h×(Hops+Dist)，其中T_h为一跳传输所需要的时间，Dist为从源节点到目的节点的跳数；在等待时间内中间节点或源节点不允许发送与该目的节点相关的RERR消息；如果在等待时间内能收到来自目的节点的RREP消息，中间节点或源节点不作任何操作，否则将该路由表项置为无效。

本发明基于链路质量的移动自组织网络按需路由方法，针对基于最短条数的移动自组织网络按需路由算法无法发现最可靠的路径的问题，通过将无线链路质量转换成路由发现优先级，进而转换成路由发现时延，源节点和各中间节点根据时延向各自的邻居节点发送路由请求报文，节点第一次收到路由请求报文时转发，对再次收到的路由请求报文直接丢弃，以保证具有最优链路状态的路径能够被选为路由路径。采用本发明的路由发现方法，可以在移动自组织网络中发现最优路由。另外，本发明还在路由发现基础上加入了路由状态维护的方案，可以发现移动自组织网络中的故障节点进和不稳定链路，以便实时更新最优路由，提高移动自组织网络对故障的反应速度，实现对路由的跟踪维护。

附图说明

图1是实施例中基于TCP/IP协议的移动自组织网络的拓扑图；

图2是HELLO消息数据包结构示意图；

图3是RREQ消息数据包结构示意图；

图4是RREP消息数据包结构示意图；

图5是RERR消息数据包结构示意图。

具体实施方式

下面结合附图对本发明的具体实施方式进行描述，以便本领域的技术人员更好地理解本发明。需要特别提醒注意的是，在以下的描述中，当已知功能和设计的详细描述也许会淡化本发明的主要内容时，这些描述在这里将被忽略。

在本专利说明书中，链路特指网络中两相邻节点之间的逻辑通信链路；路由是指网络中任意两个节点进行通信时数据包所经过的所有链路集合，路由是由这些链路上的所有节点中的路由表来表示，其中每个路由表项包含6个属性：标识号、目的地址、指向目的地址的下一跳地址、到目的地址的跳数、路由状态和有效期。链路质量则是指一条链路的数据包递送率。

实施例

图1是实施例中基于TCP/IP协议的移动自组织网络的拓扑图。本实施例中，移动自组织网络包括4个节点，每个圆代表一个节点，其中数字代表节点号，每个边代表一条直达链路，其中的数值代表数据包递送率。可见在本实施例中，节点1的相邻节点为2、3，节点2的相邻节点为1、3，节点3的相邻节点为1、2、4，节点4的相邻节点为3。

下面基于图1所示的移动自组织网络对本发明基于链路质量的移动自组织网络按需路由方法进行详细描述，本发明包括以下步骤：

S1：每个活动节点i在加入网络之后每隔T₀秒广播一条HELLO消息，包括消息类型和该节点地址，与此同时监听其他节点发送来的HELLO消息；若某节点i在预设时间T_s内收到节点j发出的HELLO消息为N_ij＞0个，则节点j是节点i的邻居节点，在节点i的邻居列表中记录节点j的地址ADD_j和节点i与节点j的链路质量$>q_{\mathrm{ij}}=\frac{T_0{N}_{\mathrm{ij}}}{T_s}.$>

本实施例中，HELLO消息的广播周期T₀＝1s，接收统计时间T_s＝5s。如图1所示，本实施例中各节点间的链路质量分别为q₁₂＝q₂₁＝0.8、q₁₃＝q₃₁＝0.2、q₂₃＝q₃₂＝0.8、q₃₄＝q₄₃＝0.6。

图2是HELLO消息数据包结构示意图。如图2所示，本实施例中，类型为0，保留为0。类型字段的作用是将传输的消息类型进行区分。

S2：当数据源节点x需要向目的节点y发送数据时，如果源节点x和目的节点y之间已存在有效路由，则直接发送数据，如果不存在有效路由，进入步骤S3进行路由发现。有效路由的判断可直接判断源节点x中是否存在指向目的节点y的路由表项，或者源节点x在一定时间内是否能收到目的节点y回复的RREP消息，等等。

本实施例，节点1需要向节点4发送数据，假设此时节点1与节点4之间不存在有效路由，此时对节点1到节点4的路由进行路由发现。

S3：源节点x构造RREQ消息，包括消息类型、跳数、路由请求标识、路由请求发起节点地址、路由请求目的节点地址、上一跳节点地址，此时跳数值为0，上一跳节点地址为源节点地址；源节点将RREQ消息延迟发送给源节点的所有邻居节点m₁,m₁＝1,2,3,...,N_x，邻居节点m₁的延迟时间为秒，其中A为预设的负数参数，为邻居节点m₁与源节点x的链路质量，N_x为源节点x邻居列表中所存放的邻居数。

图3是RREQ消息数据包结构示意图。如图3所示，本实施例中，节点1构建RREQ消息，其中类型为1，跳数为0，路由请求标识为0，路由请求发起节点地址为节点1的IP地址，路由请求目的节点地址为节点4的IP地址。路由请求标识用于区分网络中存在的RREQ消息。构建完成RREQ消息之后封装在UDP协议中，延迟发送给节点1的所有邻居节点2、3。参数A的取值范围一般为-1～-10，本实施例中设置参数A＝-1，因此对节点2、3的延迟时间分别为T_1v＝-ln(q_1v),v＝2,3，则T₁₂＝-ln(0.8)＝0.2231s，T₁₃＝-ln(0.2)＝1.6094s。

S4：当网络中某个节点接收到RREQ消息时，提取路由请求标识和路由请求发起节点地址，判断本节点路由表中是否已存在该路由请求标识和路由请求发起节点地址，如果存在，则将该RREQ消息抛弃；如果不存在，进入步骤S5。

当节点1广播RREQ消息后，节点2的延迟比节点3小，因此节点2先收到RREQ消息。

S5：本节点在路由表中建立一个新的路由表项，其目的地址为RREQ消息中的路由请求发起节点地址，下一跳节点地址为RREQ消息中的上一跳节点地址，标识号为RREQ消息中的路由请求标识，距离值为RREQ消息中的跳数值；判断路由请求目的节点地址是否为本节点地址，如果是，说明本节点为目的节点进入步骤S7，如果不是，进入步骤S6。

节点2在其路由表建立一个新的路由表项，其目的地址为RREQ消息中的路由请求发起节点地址，即节点1的IP地址；下一跳节点地址为RREQ消息中的上一跳节点地址，即节点1的IP地址；标识号为RREQ消息中的路由请求标识，即0；距离值为RREQ消息中的跳数值，即0。可见，本发明中建立的路由表项为反向路由表项。可以判断出节点2地址不是路由请求目的节点地址，因此进入步骤S6。

S6：将RREQ消息中的跳数值加1，上一跳节点地址更改为本节点地址，再将RREQ消息延迟转发给本节点邻居节点m₂,m₂＝1,2,3,...,N_z中除上一跳以外的其他邻居节点，节点m₂延迟时间为其中为节点m₂与本节点的链路质量，N_z为本节点邻居列表中所存放的邻居数；返回步骤S4。

由于对于节点2来说，除上一跳节点1以外的邻居节点仅有节点3。所以将RREQ消息中的跳数值加1之后，并将上一跳节点地址更改为节点2的IP地址后，将RREQ消息延迟转发给3节点，延迟时间为T₂₃＝-ln(0.8)＝0.2231s。

返回步骤4，即由节点3对RREQ消息进行处理，在节点3中建立路由表项并延迟转发给除上一跳节点2的邻居节点4。期间由于T₁₂+T₂₃＜T₁₃，因此当节点3收到直接来自节点1的RREQ消息时，节点3已经接收过由节点2转发过来的携带有相同路由请求标识和路由请求发起节点地址的RREQ消息，所以3节点将来自节点1的RREQ消息做抛弃处理。

返回步骤4，即由节点4对RREQ消息进行处理，在节点4中建立路由表项，判断可知节点4即为该RREQ消息中的目的节点，因此进行步骤S7。

S7：目的节点y根据路由表向源节点x回复RREP消息，包括类型、跳数、路由回复标识、路由回复发起节点地址、路由回复目的节点地址、上一跳节点地址，此时跳数值为0，上一跳节点地址为目的节点地址，路由回复目的节点地址为源节点地址。

图4是RREP消息数据包结构示意图。如图4所示，本实施例中，节点4构建RREP消息，其中Type为2，跳数为0，路由回复标识与RREP消息中的路由请求标识同样为0，路由回复发起节点地址为节点4的IP地址，路由回复目的节点地址为节点1的IP地址，上一跳节点地址为节点4的IP地址。RREP消息的回复周期T₁＝1s。由于在节点2、3、4中均已经建立了以节点1为目的地址的有效路由表项，因此节点4回复的RREP消息按照这些路由表项被转发至源节点1。

S8：当某节点接收到RREP消息，在路由表中建立一个新的路由表项，其目的地址为RREP消息中的路由回复发起节点地址，下一跳节点地址为RREP消息中的上一跳节点地址，标识号为RREP消息中的路由回复标识，距离值为RREP消息中的跳数值，进入步骤S9。

S9：判断路由回复节点地址是否是本节点地址，如果是，进入步骤S11，如果不是，进入步骤S10；

S10：将RREP消息中的跳数值加1，上一跳节点地址更改为本节点地址，根据路由表转发给指向路由回复目的节点地址的下一跳节点地址，返回步骤S8。

可见，本实施例中，当节点1、2、3收到RREP消息时，在各自路由表中建立一个指向节点4的路由表项。当节点2、3对路由表项建立完毕后，进入步骤S10，对RREP消息进行处理后转发给指向节点1的下一跳节点。节点1对路由表项建立完毕后，进入步骤S11。

S11：路由发现结束，源节点根据得到的有效路由向目的节点发送数据。

此时，移动自组织网络中已经建立起从节点1到节点4的有效路由。

由于移动自组织网络拓扑会动态变化，因此路由的变动也非常频繁。因此通常情况下，每个节点还需要对其路由表中每个路由表项进行监控，当有数据使用时保留，没有数据使用时删除，去除路由表中的无效路由表项。因此本发明还包括：

S12：每个节点分别为每个路由表项维护一个计时器，当有数据使用某个路由表项时则将相应计时器清0，当计时器数值达到预设值T_over时，则将相应路由表项删除。预设值T_over取值范围通常为5～10s。

除此之外，本发明还提供一种路由维护方法，可以发现移动自组织网络中的故障节点进和不稳定链路，以便实时更新最优路由，提高移动自组织网络对故障的反应速度，实现对路由的跟踪维护。路由维护方法包括以下步骤：

S2.1：有效路由建立后，目的节点持续向源节点以周期T₁重复回复RREP消息，源节点和中间转发节点的每个节点l均监听RREP消息，分别统计预设时间T_r内接收到的来自目的节点的RREP消息个数，连续统计n个T_r内的RREP消息个数M_l,t,t＝1,2,…,n，n为预设参数，根据以下公式计算路由质量：

$>p_{l,t}=\frac{T_1{M}_{l,r}}{T_s}$>

其中下标越小表示数据越新。

可以看出，需要预设参数n≥2。本实施例中，n＝4，即每次使用4个路由质量p_l,1,p_l,2,p_l,3,p_l,4。RREP消息的回复周期T₂＝1s，统计时间T_r＝5s。

S2.2：每个节点l均判断是否p_l,1＞λmin(p_l,2,p_l,3,…,p_l,n)，λ,0＜λ＜1为预设参数，如果p_l,1＞λmin(p_l,2,p_l,3,…,p_l,n)，返回步骤S2.1继续监听RREP消息；如果p_l,1≤λmin(p_l,2,p_l,3,…,p_l,n)，该路由不稳定，进入步骤S2.3。一般情况下，λ＝0.8。

S2.3：节点l根据其路由表生成RRER消息，包括不稳定路由的目的节点地址、当前节点地址和当前节点与源节点之间的跳数，发送给源节点，源节点重新发起一次对目的节点的路由发现。

图5是RERR消息数据包结构示意图。如图5所示，本实施例中，RERR消息的类型为3，路由不可达节点地址即为该不稳定路由的目的节点地址。

S2.4：当中间节点和源节点收到RERR消息后，提取出RERR消息中的跳数值Hops，计算等待时间T_w＝T_h×(Hops+Dist)，其中T_h为一跳传输所需要的时间，Dist为从源节点到目的节点的跳数；在等待时间内中间节点或源节点不允许发送与该目的节点相关的RERR消息；如果在等待时间内能收到来自目的节点的RREP消息，即此时该路由已经被修复，中间节点或源节点不作任何操作，否则节点将该路由表项置为无效。

尽管上面对本发明说明性的具体实施方式进行了描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保护之列。