一种分布式多径路由修复方法

摘要

本发明公开了一种分布式多径路由修复方法，包括步骤：收到RRER报文的节点发起路由查找；中间节点判断收到的RREQ报文；中间节点转发带链路参数的RREQ报文；目的节点对带参数RREQ报文进行路径选择；目的节点回送RREP报文，建立修复路由。本发明的方法针对Ad hoc网络中不同链路的传输特征并结合承载业务的QoS需求，在多条可选修复路径中，选择既能满足承载业务QoS需求，同时具有最小修复开销的多条传输路径实现网络修复，有效提升了修复收益和已修复网络的抗毁性。

主权项

一种分布式多径路由修复方法，具体包括如下步骤：S1：当网络的一条通信链路中间的某个节点发生故障，该故障节点向着源方向的上游节点发送RRER报文，收到RRER报文的节点发起路由广播报文RREQ，寻找到达故障节点方向的下游节点的路由；S2：对中间节点收到的RREQ报文进行判断，如果该RREQ报文为节点自己发送出去的报文或者该RREQ报文的源地址和请求ID出现在中间节点的历史记录中，则丢弃该报文；如果该RREQ报文的源地址和请求ID未出现在该中间节点的历史记录中，则将该源地址和请求ID写到历史记录中，查找通往该报文目的地址的路径，转步骤S3；S3：若找到的路径的目的序列号大于RREQ报文中的目的序列号，则表明找到了一条路径，在RREQ报文的修复路由参数中填写该节点与其上游节点之间的链路的参数信息，向所存储目的节点的下一跳节点转发RREQ报文；同时该中间节点提取RREQ报文中的信息，用来构建逆向路由表，以保证该路径被选中时数据包可以沿着所选路的相反方向进行传输，等待一定的时间ΔT，如果超时则删除逆向路由表；所述一定的时间ΔT应能保证RREQ报文能够穿过整个网络并产生一个发送到源节点的RREP报文；S4：目的节点接收到RREQ报文分组后，等待至少ΔT秒的时间，在ΔT秒的时间内，对从不同路径到达的报文进行QoS参数以及修复路由参数进行提取，进行路由选路，对选择后的路由信息构建相应的RREP报文，最后目的节点单播这些RREP报文；各个RREP报文按照不同的逆向路由表回送给源节点，每经过一个中间节点，则跳计数加1并记录该报文的信息，为各条业务流建立前向路由表作为修复成功后节点使用的路由表；S5：每个RREP报文按照中间节点的顺序逐跳回到源节点，每经过一个中间节点，RREP报文的跳计数加1，同时每个中间节点提取RREP报文的相关信息，构建前向路由表；所述RREQ报文包括QoS参数和修复路由参数；所述QoS参数包含当前各个业务流的时延、带宽、丢包率，所述修复路由参数为从修复发起节点到修复目的节点之间所有相邻节点之间的链路的时延、带宽、丢包率；步骤S4所述的进行路由选路的具体过程如下：S41：目的节点将各条链路的QoS参数与业务流的QoS参数进行对比，选出可用的流，构建带宽流量分配矩阵 C = c 11 c 12 . . . c 1 n c 21 c 22 . . . c 2 n . . . . . . . . . . . . c m 1 c m 2 . . . c mn , m代表可选路的数目，n代表业务流的数目，矩阵的每一行代表一条链路，每一列代表一条业务流，cij表示第i条链路向第j列业 务流分配带宽的开销，如果链路的带宽资源大于业务流的带宽需求量，则设置一条虚拟业务流来吸收多于的资源，其开销设为0，对于不能给业务流分配的链路带宽，将其开销设为无穷大；S42：用最小元素法求出初始的分配方案：在构成的带宽流量分配矩阵中，首先在最小开销费用cij对应的链路i和业务流j之间进行带宽流量分配，分配的带宽流量值取路径带宽和业务需求带宽的最小值。若路径的带宽流量已经分配完毕则删除该行对应的开销费用，若业务流的带宽已经分配完毕则删除该列对应的开销费用，然后在未被划去的开销费用中寻找最小值，并作带宽流量分配，直到全部的流量分配完毕，此时形成了一个初始的分配方案；S43：用位势法求非基变量的检验数：构造一个(m+1)×(n+1)的矩阵 C ′ = c 11 ′ c 12 ′ . . . c 1 n ′ u 1 c 21 ′ c 22 ′ . . . c 2 n ′ u 2 . . . . . . . . . . . . . . . c m 1 ′ c m 2 ′ . . . c mn ′ u m v 1 v 2 . . . v n 0 , 令vn=0，对于每个基格有c'ij=ui+vj，其中c'ij为开销，利用初始条件vn=0，求出所有的ui、vj，计算非基变量的检验数σij=c'ij‑(ui+vj)，若满足σij≥0，则当前分配方案就是最优分配方案，计算停止，否则转步骤S44；S44：取一个检验数最小的非基变量作进基变量，其对应的格为进基格，以进基格为起始点作出一个其余顶点均为基格的闭回路，在闭回路上从所有偶数号格点的带宽流量中选出最小值θ作为调整量，该格即为离基格，对应的变量为离基变量，θ=min{xij，(i,j）为闭回路中的偶数格点}，其中，xij为基变量；S45：对闭回路上的带宽流量作出调整：所有奇数号格的运量加上调整量θ，所有偶数号格的运量减去调整量θ，得到一个新的带宽流量分配方案，转步骤S43。