无线mesh网多路径路由协议的设计

陶李

（吉林警察学院 信息工程系，吉林 长春 130000）

无线mesh网多路径路由协议的设计

陶李

（吉林警察学院 信息工程系，吉林 长春 130000）

多路径路由是一种较新的路由策略，相对于传统的单路径有很多优势.本文在原有路由的基础上提出一种新的多路径路由算法，首先，通过该算法实现了查询路径的方式和计算路径的数量，其次，通过该算法实现了独立路径模型的构建和路径可靠性模型，最终完成在传输过程中，充分挖掘可靠性较高的多条传输路径来完成节点间的通信，解决因节点具有动态特征等原因造成的断路和拥塞，实现整个网络的负载均衡及数据的可靠传输.

无线Mesh网；路由协议；多路径路由；可靠传输

无线Mesh网作为一种新型宽带无线接入技术备受学术界关注，逐渐成为下一代无线互联网的核心技术[1-2].在WMN网络中节点可以进行信号的发送和接收，是无线Mesh网的核心思想.通过这种思想解决了传统的WLAN中健壮性差，可伸缩性低等一系列问题.在无线Mesh网中通过多路径路由实现了传输可靠性，利用带宽解决突发流量等问题.源目标和目的目标通过多路径路由实现了多条路径的建立，并且需要多个主机实现路由任务，通过多路径路解决了减轻流量拥塞问题.分布流量通过不同的路径进行传输，通过多条好路径实现对单条好路径的替代[3-4].多路径路由一般由二个种类组成，一种是通过多条路径进行传输，也叫并行多路径，另外一种是同一时刻路径只能进行单一流量的链接，若出现故障可以通过其他路径连接，也叫备份多路径.[5-6]；另外还有很多关于安全多路径路由方面的研究.多路的正确使用可以为不同的服务质量要求提供不同的路径，还可以提高网络的利用率[7-8].本文在此研究领域提出一种独特的多路径算法.

1 无线Mesh网多路径路由算法

1.1 数据从A节点发送到B节点，首先通过对广播包RREQ进行发送，实现查找路径，广播包RREQ主要包含，源节点，目的节点地址，广播，源节点序列号和传输时间数组等.一般初始化情况下，对路径轨迹记录当前时刻源节点编号.

1.2 通过RREQ分组每个节点操作如下：通过轨迹数组记录下节点标识；通过RREQ分组和记录的当前时刻对链路进行传输时间的计算，在RREQ分组中记录传输时间.

1.3 通过RREQ分组从节点A传输到节点B，依据传输时间t进行路由请求的接收，若接收条件达到要求，可通过轨迹数组记录节点序号；轨迹数组把传输时间相加，可得出路由耗时.若通过其他方式收到RREQ请求，可分别计算路由耗时.

1.4 通过RREP分组把目的节点进行封装，主要封装包含，目的节点序列号，源节点，目的节点地址，路径的轨迹数组等.封装进行后，通过RREP分组将路径传给源节点.

1.5 通过RREP分组把B节点传送给源节点A，根据公式得出路径可靠度.依据下面原则实现路由集合：

(1)如果路径之间存在公共链路时，那么选择较大的路径，把较小路径作为未来的替补路径.

(2)如果路径之间可靠度相近，那么对路径轨迹数组跳数进行比较，把较大的路径作为未来的替补路径

(3)如果存在跳数和可靠度一样，那么存在路由耗时，把较大的路径作为未来的替补路径.

至此，路由发现过程结束.图1为算法的流程图：

图1 多路径路由算法流程图

2 无线Mesh网多路径路由协议算法实验分析

2.1 多路径的选择

目的，源节点通过路径发现实现多条路径的搜索，通过路径的特征一般有交叉和非交叉路径组成.非交叉路径是由无共享链路和无共享节点组成.无共享节点主要特征是没有共用节点，无共享链路主要特征是没有共用链路，有可能存在共用节点.原则上，由于无共享节点路径没有共享链路和节点，所以无共享节点实现了累计资源.无公共链路具有容错能力，并且能提供较多资源.

交叉路径特征是对路径搜索约束条件少.一般网络交叉路径存在较多，因为非交叉路径一般易发现，并且冗余小.经过实验说明，网络中，不同节点之间会存在少数非交叉路径.因为在不同节点间会存在很少的瓶颈链路.对于非交叉路径和交叉路径非交叉路径是无公共链路.所以，对所有路径搜索后，得出无公共链路.

2.2 路由发现过程实例

协议图G(V1,PV,E1,PE)：通过G(V1,E1)在路由协议中表达网络拓扑结构.其中，节点集合用V1表示，V1在网络中表示网络接入点，边集合用EI表示，EI是无线链路，在网络的实际应用中，链路，节点之间在不同的环境总会出现失效，所以为了满足实际的需求，在协议图G中给边，节点赋概率值，形成协议图G.

传输路径Ak：目的，源点之间进行传输的通信链路.

路径独立性：若Aj和Ai不存在公共传输链路，那么Aj和Ai是相互独立的路径.

路径轨迹Lk[s…d]：网络传输中记录的节点序号.传输时间数组Tk[tij]：在路径的传输过程中，开始从节点I出发，到节点J为止，然后通过节点J进行转发，最后得到的时间.

Tk[tij]=在RREQ中传输时间+在RREQ中处理时间.

路由耗时Tk：到达传输路径一共消耗的时间.每项指标相加得到最后的耗时时间.

接收时限t：在RREQ中发送源节点s，并且对发送的当前时刻ts进行记录，然后在RREQ中对ts进行封装，记录下封装时刻td.如果td-ts＜t，那么对RREQ进行接收，否则，不考虑接收RREQ.由于路径直接的传输，在不同的节点之间进行通信会受到距离和带宽等影响.及时信息发送成功，但是延时时间太长.

单路径的可靠度，在协议图G中，目的和源节点通常采用单路径传输，边与节点之间乘积定义为单路径可靠度.即：

多路径分配：设存在n条路径，在存在的多条路径中，依据路径耗时Tk实现各个路径传送的信息量：

通过图1说明多路径算法的过程，对每个链路节点进行设置，G=0.75，每个链路一般G=0.7，如果节点d接收到节点s发送到数据后，首先在RREQ中进行广播，；通过节点s对邻节点a和e进行请求后，对相应的请求信息进行修改，然后把修改后的信息进行广播.若在RREQ中收到节点d数据后，在 RREQ中 s-e-g-f-d,s-a-b-c-f-d,s-a-b-d和,s-e-c-f-d等满足时限t的条件要求，在RREQ依据节点d收到的信息，对路由耗时T1，T2进行计算，把节点序号记录到轨迹数组Lk[s…d]中.最后，在RREQ中把收到节点d信息进行封装，在RREQ中通过路由耗时把最小的路径传送给源节点s.

在RREP中，收到节点s数据后，依据公式1对每个路径的可靠度进行计算：

路径s-a-b-d:A1=0.857*0.74=0.6341

路径s-a-b-c-f-d:A2=0.858*0.75=0.6435

路径s-e-g-f-d:A3=0.856*0.74=0.6344

路径s-e-c-f-d:A4=0.856*0.74=0.6344

图2 多路径路由协议示意图

通过公共链路a-b形成A1与A2的路径，因为针对可靠度方面A2较低，所以选择A2为替补路由；如果A3和A4在跳数和可靠度方面一样，那么，需要通过路由耗时对A3和A4路径进行判断，如果T3＜T4，那么选择A4为替补路由.最后通过A1和A3路径进行数据传输，选择A2和A4路经为替补路由.

这些路径传输的数据确定后，依据公式2对A3和A4路径进行信息量分配，然后开始数据传送.

在数据传送中，A2和A4路经的传输状态通过目的节点d进行返回，如果A2和A4路经在传输过程中出现问题时，选择A2和A4路径为替补路径，继续进行数据传输，最后所有信息传输完毕后结束.

2.3 多路径间的比较与选择

前面查找到的原始路径多而杂，不一定全部满足要求，在具体的应用中，节点之间的移动性由于不断变化，并且路径开销，路径质量等问题的干扰等问题，多路径的不同环境下处理问题会相对复杂，若对路径不能进行合理的选择，那么选择多路径的方法就没有达到效果.所以多路径的选择通过可靠度来决定是必要的.合适路径的必须通过选择才能确定，采用可靠度的方式来对合适的路径进行必要的选择.如果不同路径直接连接是独立存在的，那么每条路径上链路可靠度就是路径的可靠度，在路径中边和节点的可靠度乘积通过目的节点d和源节点s可靠度定义.

路径轨迹数组中记录的是每个节点的位置，即存储每条路径的跳数.

传输耗时在实现上表示为：源节点S在发送数据包时将自己当前时刻的时间存入传输耗时数组中，各中间节点在收到数据包时也将当前时刻存入包中.

源节点通过选择合适的路径把数据传输到目的节点.通过流量分配机制解决了如何在多路径间的数据分配的问题.其中分配粒度是选择的关键，可以把报文的信息分配到一条路径，也可分到多个路径中.

3 结束语

本文介绍了一种新的多路径路由算法，来解决由于单路径传输容易造成的传输易中断的问题.并对多路径的查找选择的算法进行了详细地描述，并最终得出一个路径集合，可用于由主路径和候选路径搭配传输，或由多条选出可靠度高的路径共同来完成传输任务.

〔1〕尚硕.无线Mesh网络多路径路由协议研究[D].吉林大学,2015.

〔2〕周春月.无线Mesh网络的多信道多路径路由协议研究[D].西安电子科技大学,2014.

〔3〕伍小双.无线mesh网多路径路由研究[D].电子科技大学,2014.

〔4〕符琦.一种具有业务感知的多路径QoS路由策略[J].计算机学报,2014（10）:2153-2164.

〔5〕赵海青.无线Mesh网中基于负载平衡的多路径路由协议[J].微计算机信息,2011（02）:225-227.

〔6〕沈华.基于混合架构无线Mesh网的多路径路由协议[J].武汉理工大学学报(信息与管理工程版), 2011（06）:913-916.

〔7〕闫茜,杨金程.结合混合式信道分配的Mesh多路径路由协议[J].计算机应用,2010（09）:2505-2508.

〔8〕黄钱飞,卢威.无线mesh网络中多路径路由协议研究[J].电脑与电信,2013（03）:39-42.

TP301.6

A

1673-260X（2017）01-0012-03

2016-10-12

2016年度吉林省高校科学技术和人文社会科学研究规划项目（2016ZCY266）