陶李

（吉林警察學(xué)院 信息工程系，吉林 長春 130000）

無線mesh網(wǎng)多路徑路由協(xié)議的設(shè)計(jì)

陶李

（吉林警察學(xué)院 信息工程系，吉林 長春 130000）

多路徑路由是一種較新的路由策略，相對于傳統(tǒng)的單路徑有很多優(yōu)勢.本文在原有路由的基礎(chǔ)上提出一種新的多路徑路由算法，首先，通過該算法實(shí)現(xiàn)了查詢路徑的方式和計(jì)算路徑的數(shù)量，其次，通過該算法實(shí)現(xiàn)了獨(dú)立路徑模型的構(gòu)建和路徑可靠性模型，最終完成在傳輸過程中，充分挖掘可靠性較高的多條傳輸路徑來完成節(jié)點(diǎn)間的通信，解決因節(jié)點(diǎn)具有動態(tài)特征等原因造成的斷路和擁塞，實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的負(fù)載均衡及數(shù)據(jù)的可靠傳輸.

無線Mesh網(wǎng)；路由協(xié)議；多路徑路由；可靠傳輸

無線Mesh網(wǎng)作為一種新型寬帶無線接入技術(shù)備受學(xué)術(shù)界關(guān)注，逐漸成為下一代無線互聯(lián)網(wǎng)的核心技術(shù)[1-2].在WMN網(wǎng)絡(luò)中節(jié)點(diǎn)可以進(jìn)行信號的發(fā)送和接收，是無線Mesh網(wǎng)的核心思想.通過這種思想解決了傳統(tǒng)的WLAN中健壯性差，可伸縮性低等一系列問題.在無線Mesh網(wǎng)中通過多路徑路由實(shí)現(xiàn)了傳輸可靠性，利用帶寬解決突發(fā)流量等問題.源目標(biāo)和目的目標(biāo)通過多路徑路由實(shí)現(xiàn)了多條路徑的建立，并且需要多個(gè)主機(jī)實(shí)現(xiàn)路由任務(wù)，通過多路徑路解決了減輕流量擁塞問題.分布流量通過不同的路徑進(jìn)行傳輸，通過多條好路徑實(shí)現(xiàn)對單條好路徑的替代[3-4].多路徑路由一般由二個(gè)種類組成，一種是通過多條路徑進(jìn)行傳輸，也叫并行多路徑，另外一種是同一時(shí)刻路徑只能進(jìn)行單一流量的鏈接，若出現(xiàn)故障可以通過其他路徑連接，也叫備份多路徑.[5-6]；另外還有很多關(guān)于安全多路徑路由方面的研究.多路的正確使用可以為不同的服務(wù)質(zhì)量要求提供不同的路徑，還可以提高網(wǎng)絡(luò)的利用率[7-8].本文在此研究領(lǐng)域提出一種獨(dú)特的多路徑算法.

1 無線Mesh網(wǎng)多路徑路由算法

1.1 數(shù)據(jù)從A節(jié)點(diǎn)發(fā)送到B節(jié)點(diǎn)，首先通過對廣播包RREQ進(jìn)行發(fā)送，實(shí)現(xiàn)查找路徑，廣播包RREQ主要包含，源節(jié)點(diǎn)，目的節(jié)點(diǎn)地址，廣播，源節(jié)點(diǎn)序列號和傳輸時(shí)間數(shù)組等.一般初始化情況下，對路徑軌跡記錄當(dāng)前時(shí)刻源節(jié)點(diǎn)編號.

1.2 通過RREQ分組每個(gè)節(jié)點(diǎn)操作如下：通過軌跡數(shù)組記錄下節(jié)點(diǎn)標(biāo)識；通過RREQ分組和記錄的當(dāng)前時(shí)刻對鏈路進(jìn)行傳輸時(shí)間的計(jì)算，在RREQ分組中記錄傳輸時(shí)間.

1.3 通過RREQ分組從節(jié)點(diǎn)A傳輸?shù)焦?jié)點(diǎn)B，依據(jù)傳輸時(shí)間t進(jìn)行路由請求的接收，若接收條件達(dá)到要求，可通過軌跡數(shù)組記錄節(jié)點(diǎn)序號；軌跡數(shù)組把傳輸時(shí)間相加，可得出路由耗時(shí).若通過其他方式收到RREQ請求，可分別計(jì)算路由耗時(shí).

1.4 通過RREP分組把目的節(jié)點(diǎn)進(jìn)行封裝，主要封裝包含，目的節(jié)點(diǎn)序列號，源節(jié)點(diǎn)，目的節(jié)點(diǎn)地址，路徑的軌跡數(shù)組等.封裝進(jìn)行后，通過RREP分組將路徑傳給源節(jié)點(diǎn).

1.5 通過RREP分組把B節(jié)點(diǎn)傳送給源節(jié)點(diǎn)A，根據(jù)公式得出路徑可靠度.依據(jù)下面原則實(shí)現(xiàn)路由集合：

(1)如果路徑之間存在公共鏈路時(shí)，那么選擇較大的路徑，把較小路徑作為未來的替補(bǔ)路徑.

(2)如果路徑之間可靠度相近，那么對路徑軌跡數(shù)組跳數(shù)進(jìn)行比較，把較大的路徑作為未來的替補(bǔ)路徑

(3)如果存在跳數(shù)和可靠度一樣，那么存在路由耗時(shí)，把較大的路徑作為未來的替補(bǔ)路徑.

至此，路由發(fā)現(xiàn)過程結(jié)束.圖1為算法的流程圖：

圖1 多路徑路由算法流程圖

2 無線Mesh網(wǎng)多路徑路由協(xié)議算法實(shí)驗(yàn)分析

2.1 多路徑的選擇

目的，源節(jié)點(diǎn)通過路徑發(fā)現(xiàn)實(shí)現(xiàn)多條路徑的搜索，通過路徑的特征一般有交叉和非交叉路徑組成.非交叉路徑是由無共享鏈路和無共享節(jié)點(diǎn)組成.無共享節(jié)點(diǎn)主要特征是沒有共用節(jié)點(diǎn)，無共享鏈路主要特征是沒有共用鏈路，有可能存在共用節(jié)點(diǎn).原則上，由于無共享節(jié)點(diǎn)路徑?jīng)]有共享鏈路和節(jié)點(diǎn)，所以無共享節(jié)點(diǎn)實(shí)現(xiàn)了累計(jì)資源.無公共鏈路具有容錯(cuò)能力，并且能提供較多資源.

交叉路徑特征是對路徑搜索約束條件少.一般網(wǎng)絡(luò)交叉路徑存在較多，因?yàn)榉墙徊媛窂揭话阋装l(fā)現(xiàn)，并且冗余小.經(jīng)過實(shí)驗(yàn)說明，網(wǎng)絡(luò)中，不同節(jié)點(diǎn)之間會存在少數(shù)非交叉路徑.因?yàn)樵诓煌?jié)點(diǎn)間會存在很少的瓶頸鏈路.對于非交叉路徑和交叉路徑非交叉路徑是無公共鏈路.所以，對所有路徑搜索后，得出無公共鏈路.

2.2 路由發(fā)現(xiàn)過程實(shí)例

協(xié)議圖G(V1,PV,E1,PE)：通過G(V1,E1)在路由協(xié)議中表達(dá)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).其中，節(jié)點(diǎn)集合用V1表示，V1在網(wǎng)絡(luò)中表示網(wǎng)絡(luò)接入點(diǎn)，邊集合用EI表示，EI是無線鏈路，在網(wǎng)絡(luò)的實(shí)際應(yīng)用中，鏈路，節(jié)點(diǎn)之間在不同的環(huán)境總會出現(xiàn)失效，所以為了滿足實(shí)際的需求，在協(xié)議圖G中給邊，節(jié)點(diǎn)賦概率值，形成協(xié)議圖G.

傳輸路徑Ak：目的，源點(diǎn)之間進(jìn)行傳輸?shù)耐ㄐ沛溌?

路徑獨(dú)立性：若Aj和Ai不存在公共傳輸鏈路，那么Aj和Ai是相互獨(dú)立的路徑.

路徑軌跡Lk[s…d]：網(wǎng)絡(luò)傳輸中記錄的節(jié)點(diǎn)序號.傳輸時(shí)間數(shù)組Tk[tij]：在路徑的傳輸過程中，開始從節(jié)點(diǎn)I出發(fā)，到節(jié)點(diǎn)J為止，然后通過節(jié)點(diǎn)J進(jìn)行轉(zhuǎn)發(fā)，最后得到的時(shí)間.

Tk[tij]=在RREQ中傳輸時(shí)間+在RREQ中處理時(shí)間.

路由耗時(shí)Tk：到達(dá)傳輸路徑一共消耗的時(shí)間.每項(xiàng)指標(biāo)相加得到最后的耗時(shí)時(shí)間.

接收時(shí)限t：在RREQ中發(fā)送源節(jié)點(diǎn)s，并且對發(fā)送的當(dāng)前時(shí)刻ts進(jìn)行記錄，然后在RREQ中對ts進(jìn)行封裝，記錄下封裝時(shí)刻td.如果td-ts＜t，那么對RREQ進(jìn)行接收，否則，不考慮接收RREQ.由于路徑直接的傳輸，在不同的節(jié)點(diǎn)之間進(jìn)行通信會受到距離和帶寬等影響.及時(shí)信息發(fā)送成功，但是延時(shí)時(shí)間太長.

單路徑的可靠度，在協(xié)議圖G中，目的和源節(jié)點(diǎn)通常采用單路徑傳輸，邊與節(jié)點(diǎn)之間乘積定義為單路徑可靠度.即：

多路徑分配：設(shè)存在n條路徑，在存在的多條路徑中，依據(jù)路徑耗時(shí)Tk實(shí)現(xiàn)各個(gè)路徑傳送的信息量：

通過圖1說明多路徑算法的過程，對每個(gè)鏈路節(jié)點(diǎn)進(jìn)行設(shè)置，G=0.75，每個(gè)鏈路一般G=0.7，如果節(jié)點(diǎn)d接收到節(jié)點(diǎn)s發(fā)送到數(shù)據(jù)后，首先在RREQ中進(jìn)行廣播，；通過節(jié)點(diǎn)s對鄰節(jié)點(diǎn)a和e進(jìn)行請求后，對相應(yīng)的請求信息進(jìn)行修改，然后把修改后的信息進(jìn)行廣播.若在RREQ中收到節(jié)點(diǎn)d數(shù)據(jù)后，在 RREQ中 s-e-g-f-d,s-a-b-c-f-d,s-a-b-d和,s-e-c-f-d等滿足時(shí)限t的條件要求，在RREQ依據(jù)節(jié)點(diǎn)d收到的信息，對路由耗時(shí)T1，T2進(jìn)行計(jì)算，把節(jié)點(diǎn)序號記錄到軌跡數(shù)組Lk[s…d]中.最后，在RREQ中把收到節(jié)點(diǎn)d信息進(jìn)行封裝，在RREQ中通過路由耗時(shí)把最小的路徑傳送給源節(jié)點(diǎn)s.

在RREP中，收到節(jié)點(diǎn)s數(shù)據(jù)后，依據(jù)公式1對每個(gè)路徑的可靠度進(jìn)行計(jì)算：

路徑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 多路徑路由協(xié)議示意圖

通過公共鏈路a-b形成A1與A2的路徑，因?yàn)獒槍煽慷确矫鍭2較低，所以選擇A2為替補(bǔ)路由；如果A3和A4在跳數(shù)和可靠度方面一樣，那么，需要通過路由耗時(shí)對A3和A4路徑進(jìn)行判斷，如果T3＜T4，那么選擇A4為替補(bǔ)路由.最后通過A1和A3路徑進(jìn)行數(shù)據(jù)傳輸，選擇A2和A4路經(jīng)為替補(bǔ)路由.

這些路徑傳輸?shù)臄?shù)據(jù)確定后，依據(jù)公式2對A3和A4路徑進(jìn)行信息量分配，然后開始數(shù)據(jù)傳送.

在數(shù)據(jù)傳送中，A2和A4路經(jīng)的傳輸狀態(tài)通過目的節(jié)點(diǎn)d進(jìn)行返回，如果A2和A4路經(jīng)在傳輸過程中出現(xiàn)問題時(shí)，選擇A2和A4路徑為替補(bǔ)路徑，繼續(xù)進(jìn)行數(shù)據(jù)傳輸，最后所有信息傳輸完畢后結(jié)束.

2.3 多路徑間的比較與選擇

前面查找到的原始路徑多而雜，不一定全部滿足要求，在具體的應(yīng)用中，節(jié)點(diǎn)之間的移動性由于不斷變化，并且路徑開銷，路徑質(zhì)量等問題的干擾等問題，多路徑的不同環(huán)境下處理問題會相對復(fù)雜，若對路徑不能進(jìn)行合理的選擇，那么選擇多路徑的方法就沒有達(dá)到效果.所以多路徑的選擇通過可靠度來決定是必要的.合適路徑的必須通過選擇才能確定，采用可靠度的方式來對合適的路徑進(jìn)行必要的選擇.如果不同路徑直接連接是獨(dú)立存在的，那么每條路徑上鏈路可靠度就是路徑的可靠度，在路徑中邊和節(jié)點(diǎn)的可靠度乘積通過目的節(jié)點(diǎn)d和源節(jié)點(diǎn)s可靠度定義.

路徑軌跡數(shù)組中記錄的是每個(gè)節(jié)點(diǎn)的位置，即存儲每條路徑的跳數(shù).

傳輸耗時(shí)在實(shí)現(xiàn)上表示為：源節(jié)點(diǎn)S在發(fā)送數(shù)據(jù)包時(shí)將自己當(dāng)前時(shí)刻的時(shí)間存入傳輸耗時(shí)數(shù)組中，各中間節(jié)點(diǎn)在收到數(shù)據(jù)包時(shí)也將當(dāng)前時(shí)刻存入包中.

源節(jié)點(diǎn)通過選擇合適的路徑把數(shù)據(jù)傳輸?shù)侥康墓?jié)點(diǎn).通過流量分配機(jī)制解決了如何在多路徑間的數(shù)據(jù)分配的問題.其中分配粒度是選擇的關(guān)鍵，可以把報(bào)文的信息分配到一條路徑，也可分到多個(gè)路徑中.

3 結(jié)束語

本文介紹了一種新的多路徑路由算法，來解決由于單路徑傳輸容易造成的傳輸易中斷的問題.并對多路徑的查找選擇的算法進(jìn)行了詳細(xì)地描述，并最終得出一個(gè)路徑集合，可用于由主路徑和候選路徑搭配傳輸，或由多條選出可靠度高的路徑共同來完成傳輸任務(wù).

〔1〕尚碩.無線Mesh網(wǎng)絡(luò)多路徑路由協(xié)議研究[D].吉林大學(xué),2015.

〔2〕周春月.無線Mesh網(wǎng)絡(luò)的多信道多路徑路由協(xié)議研究[D].西安電子科技大學(xué),2014.

〔3〕伍小雙.無線mesh網(wǎng)多路徑路由研究[D].電子科技大學(xué),2014.

〔4〕符琦.一種具有業(yè)務(wù)感知的多路徑QoS路由策略[J].計(jì)算機(jī)學(xué)報(bào),2014（10）:2153-2164.

〔5〕趙海青.無線Mesh網(wǎng)中基于負(fù)載平衡的多路徑路由協(xié)議[J].微計(jì)算機(jī)信息,2011（02）:225-227.

〔6〕沈華.基于混合架構(gòu)無線Mesh網(wǎng)的多路徑路由協(xié)議[J].武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版), 2011（06）:913-916.

〔7〕閆茜,楊金程.結(jié)合混合式信道分配的Mesh多路徑路由協(xié)議[J].計(jì)算機(jī)應(yīng)用,2010（09）:2505-2508.

〔8〕黃錢飛,盧威.無線mesh網(wǎng)絡(luò)中多路徑路由協(xié)議研究[J].電腦與電信,2013（03）:39-42.

TP301.6

A

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

2016-10-12

2016年度吉林省高?？茖W(xué)技術(shù)和人文社會科學(xué)研究規(guī)劃項(xiàng)目（2016ZCY266）