無線mesh網多路徑路由協議的設計

2017-03-03 10:50:06陶李

赤峰學院學報·自然科學版 2017年1期

陶李

（吉林警察學院信息工程系，吉林長春 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在發送數據包時將自己當前時刻的時間存入傳輸耗時數組中，各中間節點在收到數據包時也將當前時刻存入包中.

源節點通過選擇合適的路徑把數據傳輸到目的節點.通過流量分配機制解決了如何在多路徑間的數據分配的問題.其中分配粒度是選擇的關鍵，可以把報文的信息分配到一條路徑，也可分到多個路徑中.