一种移动自组织网络中基于多Qos路由选择方法

摘要

本发明涉及一种移动自组织网络中基于多Qos路由选择方法，属于移动通信技术领域。该方法包括以下步骤：路由请求消息的产生：包括查询自身路由表，若无可达路由，发起路由发现过程，复制路由表中目的节点序列号到路由请求消息分组的目的节点序列号域，源节点广播路由请求消息到邻居节点；路由请求消息的处理和转发：包括对接入准则的判断，对接入准则判断结果进行相应处理，根据路由转发表信息判断节点是否收到相同ID和相同源节点IP地址的路由请求消息分组，并对判断结果做相应处理；路由应答消息的产生及处理：包括目的节点产生路由应答，中间节点产生路由应答，中间节点对路由应答消息的处理，无路由应答路径的处理。该方法避免了性能瓶颈节点，节省了路由开销，提高了系统性能。

说明书

技术领域

本发明属于移动通信技术领域，涉及一种移动自组织网络中基于多Qos路由选择 方法。

背景技术

随着无线通信和移动计算技术的快速发展，以及无线通信装置(如手持数字装置、 可佩戴计算机及车载无线设备)的迅速增长，用户既可快速接入网络，访问网络资源，又能 随时随地组网，共享信息。

根据组网控制方式的不同，无线通信网络一般分为集中式和无中心自组织式两 类。集中式网络(如蜂窝移动通信系统、有线骨干网)需要预先已部署好的基站、交换中心等 固定网络设施。然而某些特殊场合(如战场上的通信、地震后的救援、野外科学考查、偏远地 区的临时会议等)通常不会有已部署的固定设施，因此能够临时快速组网的MAENT便在这些 情况下应运而生。

词语“AdHoc”来源于拉丁语，意思为“特定的、专用的”，也可称为“自组织网”或“无 固定设施网”。IEEE802.11标准委员会最初采用“AdHoc网络”一词来描述这种自组织网络， 国际互联网工程任务组(TheInternetEngineeringTaskForce,IETF)将AdHoc网络称 为MANET。网络中的节点能否直接通信取决于节点最大通信范围及两节点间的距离，不在直 接通信范围内的节点，需要中继节点转发，因此MANET也被称为无线多跳网络。

随着移动自组织网络应用的广泛和深入，多媒体大流量数据及实时应用迫切需要 能够准确可靠快速地传输，这些都对MANET的QoS性能提出了较高要求，需要路由协议能够 提供一定的QoS保证。网络中节点能量、网络带宽等资源有限，使MANET路由研究变得困难和 复杂。

因此，研究并实现如何利用有限的网络资源寻找源节点与目的节点之间的具有较 高QoS保证的路由方法成为了研究的难点，具有重要的现实意义。

发明内容

有鉴于此，本发明的目的在于提供一种移动自组织网络中基于多Qos路由选择方 法，具体包括以下步骤：

S1：路由请求消息的产生：包括查询自身路由表，若无可达路由，发起路由发现过 程，复制路由表中目的节点序列号到路由请求消息分组的目的节点序列号域，源节点广播 路由请求消息到邻居节点；

S2：路由请求消息的处理和转发：包括对接入准则的判断，对接入准则判断结果进 行相应处理，根据路由转发表信息判断节点是否收到相同路由请求消息ID<RREQ_ID>和相 同源节点IP地址的路由请求消息分组，并对判断结果做相应处理；

S3：路由应答消息的产生及处理：包括目的节点产生路由应答，中间节点产生路由 应答，中间节点对路由应答消息的处理，无路由应答路径的处理。

进一步，在步骤S1中，若无法获得该目的节点的序列号，则将路由请求消息<RREQ> 分组中“U”域置1，目的节点序列号标记为未知；将该RREQ消息中的源节点序列号设为该节 点自己的当前序列号加1，RREQ_ID域设为当前节点使用的RREQ_ID加1，将该RREQ消息中的 跳数域置零。

进一步，在步骤S1中，源节点广播RREQ消息到邻居节点，源节点将该RREQ消息的 RREQ_ID和源节点IP地址缓存一段时间，该时间长度等于路径寻找时间；当该源节点接收到 其相邻节点发送的该RREQ分组时，丢弃该RREQ分组。

进一步，在步骤S2中，所述路由请求消息的处理和转发，中间节点收到路由请求消 息分组后，首先进行接入准则判断，判断节点缓存区队列长度是否低于最大队列长度的 80％，节点剩余能量是否大于初始能量的10％。

进一步，在步骤S2中，分为两种情况：

1)若节点不满足接入准则，则该节点收到的路由请求消息分组不再继续转发，节 点无法接入路径；

2)若满足接入准则，则再根据路由转发列表判断节点是否已经接收过具有相同路 由请求消息ID和源节点IP地址的路由请求消息分组；

若节点满足接入准则，分两种情况：

21)若相同，则丢弃该RERQ分组；

22)若不同，说明RREQ经不同路径到达该节点，则保存RREQ分组中所携带信息，建 立反向路由；第一次接收到的RREQ分组中的跳数加1，将IP报头中的TTL域减1，更新RREQ中 路径质量域C_path。

进一步，在步骤S3中，所述目的节点产生路由应答：包括目的节点接收到RREQ分组 后，判断RREQ分组的目的节点序列号，若RREQ分组中的目的节点序列号大于目的节点当前 序列号，更新目的节点当前序列号；目的节点等待一定时间RRL(路由应答延迟，Routing ReplyDelay)，以便接收到更多RREQ分组；分为两种情况：

1)若RREQ分组只探寻到一条从源节点到目的节点的路径，则目的节点构建RREP分 组，沿该路径的反向路由，进行路由应答；

2)若RREQ分组探寻到多条从源节点到目的节点的路径，计算路径评价函数值，选 择最优路径进行路由应答，路径评价函数如式：

$V_{path(S,D)}=\frac{C_{path(S,D)}}{H_{path(S,D)}}$

其中：为路径的质量，H_path(S,D)∈[1,H_max]为跳数

其中：$\min \left(C_{link(i,j)}\right)=\min \left(\frac{Q_m-Q_j}{Q_m}\right)·\min \left(\frac{E_j}{E_0}\right)=0.02,\max \left(C_{link(i,j)}\right)=\underset{E_j\to E_0}{\underset{Q_j\to 0}{\lim }}\left(C_{link(i,j)}\right)=1,$

可知：

0.02≤C_path(S,D)＜1；

式中，C_path(S，D)为路径的质量，H_path(S,D)为跳数，C_link(i,j)为从节点i到节点j的链路 质量，Q_m为节点可承受的最大节点队列长度，Q_j为节点的队列长度，E_j为当期节点的剩余能 量，E₀为节点的初始能量；

根据路径评价函数计算从源节点到达该节点的所有路径的评价函数值，选择最优 路径进行路由应答。

进一步，在步骤S3中，所述中间节点产生路由应答，中间节点查询反向路由表，分 两种情况：1)若只存在一条反向路径，则直接进行路由应答；2)若存在多条路径，则根据所 述路径评价函数计算从源节点到达该节点的所有路径的评价函数值，选择最优路径进行路 由应答，中间节点将其知道的目的节点序列号复制到RREP分组中，并将路由条目中的期满 时间减去当前时间。

进一步，在步骤S3中，所述中间节点对路由应答(RREP)消息的处理：包括中间节点 收到路由应答RREP分组时，从路由转发列表RFT中查看存储的相应RREQ的数目N；分两种情 况：

1)若N＝1，中间节点直接转发RREP给RFT中的前一跳节点；

2)若N＞1，说明从源节点到达当前节点的存在多条路径，中间节点根据RFT中存储 的路径信息，根据所述路径评价函数计算从源节点到达该节点的所有路径的评价函数值， 选择最优路径进行路由应答；如果节点发生较大移动，中间节点不存在可达源节点的路径， 则本地发起到源节点的寻路过程。

进一步，在步骤S3中，所述无路由应答路径的处理：如果在网络传输时间内没有找 到路由，重新广播RREQ消息寻找路由；重新进行一次广播时，增大和更新RREQID，并设置IP 头的TTL域，以便控制该RREQ分组的传播范围。

进一步，在步骤S3中，所述无路由应答路径的处理：重新广播RREQ消息寻找路由仍 然没有找到可达路径，则将缓存区中相应目的节点的所有数据分组丢弃，然后向应用层发 送一条目的节点不可达消息。

本发明的有益效果在于：本发明所述方法能够在满足基本路径QoS参数保障的同 时，考虑路径中的节点剩余能量和节点队列长度，并对下一跳节点进行接入判断，避免了性 能瓶颈节点，尽量选择较稳定路径，减少路由发现频率；将该方法用于改进路由方法的路由 发现过程，增加了消息返回时反向路由表中节点移动时的处理，多QoS路由选择方法在分组 投递率、路由开销及路由发现频率等方面性能都有所提高。同时，在节点暂停时间较长或网 络负载较大的环境中，多Qos路由选择方法的QoS性能也有所提高。

附图说明

为了使本发明的目的、技术方案和有益效果更加清楚，本发明提供如下附图进行 说明：

图1为节点执行多QoS选路方法流程图；

图2为路由请求消息格式；

图3为路由应答消息格式。

具体实施方式

下面将结合附图，对本发明的优选实施例进行详细的描述。

本发明提供的一种移动自组织网络中基于多Qos路由选择方法，该方法包括如下 步骤：路由请求消息的产生，路由请求消息的处理和转发，路由应答消息的产生及处理。所 述路由请求消息的产生包括查询自身路由表，若无可达路由，发起路由发现过程，复制路由 表中目的节点序列号到路由请求消息分组的目的节点序列号域，源节点广播路由请求消息 到邻居节点；所述路由请求消息的处理和转发包括对接入准则的判断，对接入准则判断结 果进行相应处理，根据路由转发表信息判断节点是否收到相同路由请求消息ID<RREQ_ID> 和相同源节点IP地址的路由请求消息分组，并对判断结果做相应处理；所述路由应答消息 的产生及处理，包括目的节点产生路由应答，中间节点产生路由应答，中间节点对路由应答 消息的处理，无路由应答路径的处理。同时，本发明提供一种移动自组织网络中基于多Qos 路由选择方法，考虑了路径中的节点剩余能量和节点队列长度，并对下一跳节点进行接入 判断，避免了性能瓶颈节点，尽量选择较稳定路径，减少路由发现频率；将该方法用于改进 路由方法的路由发现过程，增加了消息返回时反向路由表中节点移动时的处理，多QoS路由 选择方法在分组投递率、路由开销及路由发现频率等方面性能都有所提高。同时，在节点暂 停时间较长或网络负载较大的环境中，多Qos路由选择方法的QoS性能也有所提高。

本发明本着决策因素全面性的原则，综合考虑现有移动自组织网络QoS路由选择 方法在决策因素选择上的缺陷，重点考虑动态决策因素，通过对动态决策因素的处理实现 最优接入网络的选择，本发明选择的用于QoS路由选择的相关决策因素表如下所示：

表1QoS路由选择的决策因素表

节点初始能量E₀有限，如果某个节点发送大量数据，可能使其能量消耗殆尽，造成 路径失效。节点的初始能量是影响路径稳定性的重要因素。

数据包数量是影响节点缓冲区的关键因素，在节点缓冲区中，等待发送的数据包 的数目通常被定义为节点队列长度，节点的发送缓冲区拥塞程度可以表示为：

其中，Q_i表示节点的队列长度，Q_m表示节点可承受的最大节点 队列长度，由上述可知，在一定条件下，当节点缓冲区中数据包数量越多，缓冲区拥塞程度 越大，当节点队列剩余空间长度与节点总缓存队列长度的比在(0,0.2]区间范围内时，节点 发生严重拥塞；当处于(0.2,0.5]之间时，节点发生轻度拥塞；当大于0.5时，认为节点没有 出现拥塞状况。

节点发包速率是影响网络负载的主要因素，发包速率提高时，网络负载增加，路由 方法的分组投递率下降，当网络负载较大时，丢包率较高，网络开销增大，路由发现频率增 加。

本方法综合考虑节点能量信息、节点队列长度、节点发包速率等信息，提出多QoS 选路方法，该方法对节点执行接入准则判断，避开拥塞和能量瓶颈节点，同时对路径性能进 行评价，选择相对较优路径。将多QoS选路算法，改进多QoS路由选择方法，得到一种具有QoS 保障的单路径路由方法。该方法所选择路径在保证基本QoS性能的基础上，具有较长生命 期，避免频繁的路由发现，降低了路径失效概率。该方法在分组投递率、路由开销及路由发 现频率等方面，在节点暂停时间较长或网络负载较大的环境中，性能均有所提高。

一种移动自组织网络中基于多Qos路由选择方法，包括三大步骤：路由请求消息的 产生，路由请求消息的处理和转发，路由应答消息的产生及处理。路由请求消息的产生包括 查询自身路由表，若无可达路由，发起路由发现过程，复制路由表中目的节点序列号到路由 请求消息分组的目的节点序列号域，源节点广播路由请求消息到邻居节点；路由请求消息 的处理和转发包括对接入准则的判断，对接入准则判断结果进行相应处理，根据路由转发 表信息判断节点是否收到相同ID和相同源节点IP地址的路由请求消息分组，并对判断结果 做相应处理；路由应答消息的产生及处理包括目的节点产生路由应答，中间节点产生路由 应答，中间节点对路由应答消息的处理，无路由应答路径的处理。通过这几个模块对路由进 行更新及处理，以提高路由方法的有效性和可靠性。

图1为节点执行多QoS选路方法流程图，如图所示：

步骤一：如图1所示当节点收到路由请求消息分组后，首先进行接入准则判断，判 断节点缓存区队列长度是否低于最大队列长度的80％，节点剩余能量是否大于初始能量的 10％，分两种情况：

(1)若节点不满足接入准则，则该节点收到的路由请求消息分组不再继续转发，节 点无法接入路径。

(2)若满足接入准则，则再根据路由转发列表判断节点是否已经接收过具有相同 路由请求消息ID和源节点IP地址的路由请求消息分组，分两种情况：

①若相同，则丢弃该RERQ分组；

②若不同，说明RREQ经不同路径到达该节点，则保存RREQ分组中所携带信息，建立 反向路由。第一次接收到的RREQ分组中的跳数加1，将IP报头中的TTL域减1，更新RREQ中路 径质量域C_path。

步骤二：如图1所示，分组满足接入准则，判断当前节点是否为目的节点，当目的节 点接收到RREQ分组后，判断RREQ分组的目的节点序列号，若RREQ分组中的目的节点序列号 大于目的节点当前序列号，更新目的节点当前序列号。目的节点等待一定时间RRL(路由应 答延迟，RoutingReplyDelay)，以便接收到更多RREQ分组。分两种情况：

(1)若RREQ分组只探寻到一条从源节点到目的节点的路径，则目的节点构建RREP 分组，沿该路径的反向路由，进行路由应答；

(2)若RREQ分组探寻到多条从源节点到目的节点的路径，计算路径评价函数值，选 择最优路径进行路由应答，路径评价函数如式：

$V_{path(S,D)}=\frac{C_{path(S,D)}}{H_{path(S,D)}}$

其中：为路径的质量，H_path(S,D)∈[1,H_max]为跳数

其中：$\min \left(C_{link(i,j)}\right)=\min \left(\frac{Q_m-Q_j}{Q_m}\right)·\min \left(\frac{E_j}{E_0}\right)=0.02,\max \left(C_{link(i,j)}\right)=\underset{E_j\to E_0}{\underset{Q_j\to 0}{\lim }}\left(C_{link(i,j)}\right)=1,$

可知，

0.02≤C_path(S,D)＜1；

式中，C_path(S，D)——路径的质量

H_path(S,D)——跳数

C_link(i,j)——从节点i到节点j的链路质量

Q_m——节点可承受的最大节点队列长度

Q_j——节点的队列长度

E_j——当期节点的剩余能量

E₀——节点的初始能量

根据路径评价函数计算从源节点到达该节点的所有路径的评价函数值，选择最优 路径进行路由应答。

图2为路由请求消息格式：

如图2所示，各字段的意义如下：

Type——类型,长度为8比特，取值为1；

2.J——“加入”标志，长度1比特，保留用于多目标传输；

3.R——“修复”标志，长度1比特，保留用于多目标传输；

4.G——无请求RREP标志，长度1比特，表示是否需要按照单目标方式将一个无请 求RREP分组发送至目的节点IP地址域确定的节点，置1表示需要，置0表示不需要；

5.D——单目的节点传输标志,长度1比特；

6.U——未知序列号，长度1比特，表示不知道目的节点序列号；

7.Reserved——保留,长度11比特；

8.HopCount——跳数,长度8比特，表示从源节点IP地址到达处理本条RREQ消息 的节点之间的转发跳数；

9.RREQID——路由请求识别码,这是一个序列号，运用RREQID与源节点IP地址 能够唯一识别一条RREQ消息；

10.DestinationIPAddress——目的节点IP地址，该地址是必须存在的，表示一 条路由的目的节点地址；

11.DestinationSequenceNumber——目的节点序列号，源节点已经接收到的该 目的节点最新序列号；

12.OriginatorIPAddress——源节点IP地址，产生本条RREQ消息的节点IP地址；

13.OriginatorSequenceNumber——源节点序列号，该条目指向本条RREQ消息的 源节点目前正在使用的序列号；

14.C_path——路径质量。

图3为路由应答消息格式：

如图3所示，各字段的意义如下：

(1)Type——类型，长度8比特，取值为3；

(2)N——非删除标志，长度1比特，。当节点完成对链路的本地修复的时，将N置为 “1”，其上行节点不删除本条路由；

(3)DestCount——不可达目的节点计数器，长度8比特，表示不可达目的节点的数 量，本域的值必须至少等于1，对于单目标通信，DestCount的值为1；

(4)UnreachableDestinationIPAddress——不可达目的节点IP，由于链路中断 而受影响已变成不可达的目的节点的序列号；

(5)UnreachableDestinationSequenceNumber——不可达目的节点序列号，表 示本域前一域列出的不可达目的节点的序列号。

最后说明的是，以上优选实施例仅用以说明本发明的技术方案而非限制，尽管通 过上述优选实施例已经对本发明进行了详细的描述，但本领域技术人员应当理解，可以在 形式上和细节上对其作出各种各样的改变，而不偏离本发明权利要求书所限定的范围。