一種無線mesh網絡下的可靠路由查詢機制

倪仲余，黎忠文，董露陽

(1.西華大學 數學與計算機學院，四川 成都 610039;2.成都大學 計算機學院，四川 成都 610106)

0 引 言

無線mesh 網絡(wireless mesh networks，WMNs)被廣泛認為是解決“最后一公里”問題上非常合適的新型網絡，它結合了WLAN 和ad hoc 網絡的優(yōu)勢，采用多跳的路由轉發(fā)方式來實現數據通信，是一種在傳輸上具有穩(wěn)定、高容量以及高速率的分布式網絡［1］.WMNs 的主要組成部分包括mesh 路由(mesh routers，MRs)和mesh 客戶端(mesh clients，MCs).MRs 一般由處理能力較強的路由器來擔任，它具有數據接收、轉發(fā)和網關功能［2］.而MCs 同樣也具有路由轉發(fā)功能，但相比于MRs，其多接口性和處理能力MCs 則要弱很多，MCs 一般由手機、PDA、PC等設備組成.WMNs 的拓撲結構如圖1 所示.

圖1 WMNs 拓撲結構示意圖

一般情況下，MRs 是靜止且有持續(xù)的電源供應，通常把MR 之間通過無線方式連接形成的網絡結構稱為主干網［3］;MCs 則通過連接主干網的方式來完成所需要的信息服務.這相對于有線網絡鋪設線路長、難度大的缺點來說無疑是巨大的進步.

Chord 協議是對等覆蓋網絡(peer-to-peer，P2P)中應用非常廣泛的算法［4］，其基于分布式哈希表的思路，把網絡中的節(jié)點和信息資源哈希成惟一的節(jié)點標識ID，并按照從小到大以順時針的方式進行排列成一個邏輯環(huán).資源關鍵字KEY 則保存在大于或等于標識符ID 的第一個節(jié)點中，稱為后繼節(jié)點successor(K).Chord 采用貪婪查詢方式對順時針方向上架設在邏輯拓撲環(huán)的節(jié)點關鍵字KEY 進行資源查找和快速定位，從而完成數據通信.目前，對于Chord 算法的研究大多以降低查詢跳數和時延為度量進行研究［5］，但這2 種方案在Chord 中都引入了泛洪機制，對網絡開銷造成一定的浪費［6］.此外，可通過對原始Chord 單路徑的問題進行改進，采用并發(fā)方式的多路徑查詢策略，根據節(jié)點的響應時間選擇相應的下一跳，從而減少查詢時延和提高可靠性［7］，也可通過信譽度來選擇更可靠的節(jié)點完成路由跳轉和通信，并對節(jié)點信譽值的改變更新覆蓋網絡，從而提高節(jié)點對傳輸可靠度［8－10］.在此基礎上，本研究對Chord 的高速率傳輸與可靠性2 個問題進行考量，設計了一種高效的多路徑路由查詢機制，同時，基于Chord 快速查找的優(yōu)點，本研究對所架設的WMNs覆蓋網絡引入Chord 查詢機制來完成資源的快速定位，通過添加反向查詢和可靠多路徑查詢以應對節(jié)點失效或鏈路異常的問題，從而提高在節(jié)點失效或鏈路異常情況下的通信成功率.

1 網絡結構模型

本研究將WMNs 網絡中的MRs 和MCs 進行分層，將主干層的節(jié)點對應于WMNs 覆蓋網絡中的主干網MRs，葉子層由MCs 及其所連接的MR 組成.對于無論是主干層還是葉子層的節(jié)點都基于分布式哈希算法得到其所在空間環(huán)域的惟一標識.在Chord 環(huán)中的每個節(jié)點都會維持在一張路由表(Finger Table)，假設每個標識符大小為m 位，N 為Chord環(huán)中的節(jié)點個數，則其所在的環(huán)域規(guī)模大小為2 m，該環(huán)域中的節(jié)點能夠維護數目為m 的路由表項［11］.Chord 中的節(jié)點在查找目的節(jié)點前首先會檢查自身Finger 表是否有保存該資源的后繼節(jié)點，有則取出數據資源并結束查找;若無，則跳轉至Finger表中離標識符ID 最近的節(jié)點然后重復查找，直到取出數據資源后完成.由于原始Chord 協議是按順時針方向的單向查詢，當節(jié)點處于后半環(huán)時，查詢效率不高.為了提高查詢效率，本研究對Chord 協議進行優(yōu)化，增加其逆時針方向的查詢方法.令C.Finger［i］表示節(jié)點順時針方向上第i 項后繼節(jié)點，B.Finger［i］表示節(jié)點逆時針方向上的第i 項后繼節(jié)點，則Chord 環(huán)的雙向路由表項可表示為，

在所建立的WMNs 主干層和葉子層網絡上，本研究對不同層次的網絡節(jié)點分別采取不同的命名方式.由于主干網中的MRs 都是葉子層網絡的環(huán)首節(jié)點并擁有優(yōu)秀的處理能力，所以主干層中的MRs 除了要維護自身主干區(qū)域的路由表外，還需要維護與其相關的葉子節(jié)點的路由信息，故環(huán)首節(jié)點將維護2 個路由表.在對葉子層節(jié)點進行哈希分配資源標識的過程中，首先查看葉子節(jié)點屬于哪一個葉子環(huán)，然后結合葉子節(jié)點的實際物理拓撲情況進行分配.對于葉子層上的節(jié)點，其所分配的標識符由2 部分組成:一部分通過對節(jié)點IP 地址前半部一定位數進行哈希分配得到，節(jié)點根據判斷前半部的資源標識可以知道葉子節(jié)點從屬于哪個主干節(jié)點;另一部分則是對IP 地址的后半部進行哈希分配得到，由這部分的標識符來判斷節(jié)點屬于哪個葉子層環(huán)域.對于2 個不同節(jié)點，通過這種分配方式的查看可以得出2個節(jié)點是否屬于同一葉子環(huán).圖2 為分層Chord 簡易模型.

圖2 分層Chord 模型示意圖

2 可靠路由查詢與性能分析

2.1 可靠度描述

在WMNs 中，可把主干網的MRs 當成一個集合E，因為MR 具有穩(wěn)定性和強大的處理能力，所以在網絡中的節(jié)點只要考慮成功連接其中的一個MR 即可有效地完成路由通信.根據這個思路，本研究對呼叫節(jié)點連接到主干網中的任一MR 的可靠度做如下定義.

定義1 1/E 路徑集合P(s，E):從呼叫節(jié)點s到接收節(jié)點集合E 的最小路徑集合，表示為，

P(s，E)=∪{P(s，et)，et∈E}.

定義2 Rel1/E(s，E):呼叫節(jié)點s 連通到集合E中任一MR 的概率.

定理1 s 到et的2-路徑最大可靠度小于或等于1/E 路徑可靠度，當E=1 時等式成立［6］.

證明 當E =1 時，Rel1/E(s，E)與2-路徑可靠度的接收節(jié)點和路徑相同，所以等式成立.當E ＞1時，P(s，et)?P(s，E)，所以P(s，E)可以考慮更多的路徑來計算可靠度，故P(s，E)可靠度更高.

證畢.

2.1.7 鋅。2012年全市葉片鋅平均含量為32.49 mg/kg(表1)，說明鋅的含量在較適中的范圍。鋅在蘋果營養(yǎng)生長和生殖生長中起到調節(jié)激素的作用，同時對花粉管生長起到重要作用，鋅也能影響果樹的抗凍性和花對霜凍的抵抗力。磷/鋅比值應該是100或更低，高 pH、高磷酸鹽、高有機質和低溫均降低土壤鋅的有效性。在缺乏時，葉片噴施螯合態(tài)鋅最有效 。

定理2 假如可用度P(α)≥P(β)≥P(λ)，路徑α 與β 相關鏈路數|α∩β| ＜|α∩λ|，|β| = |λ|，Relαβ=P(α)+P(β)，Relαλ=P(α)+P(λ)，則Relαβ＞Relαλ［11］.

證明 令|α| =p，|β| = |λ| =q，|α∩β| =i，|α∩λ| =j，則i ＜j.因為，0 ＜r ＜1，所以，ri＜rj，得出rp－i＜rp－j.又因為，

Relαλ=P(α)+P(λ)=rp+rq(1－rp－j)，所以，

證畢.

從定理2 可以知道，相同鏈路數的2 條路徑相關性越低則越可靠.

2.2 路由集合選擇

由定理1 與定理2 可知，在搭建的WMNs 覆蓋網絡中選擇路徑時，只需要考慮連接到主干網的任一MR 即可，同時在選擇的路徑集合中盡量選擇相關鏈路最少的路徑作為候選.根據這個條件，假設PN(s，E)表示s 節(jié)點到主干網絡中任一MR 的含N條路徑的集合，E 表示骨干節(jié)點的集合.在葉子層可能存在的節(jié)點異常情況下，通過使用可靠性路由查找完成對主干網絡節(jié)點的可靠連接.路由集合選擇的具體步驟如下:

2)假設L 為得到的路徑總數，且li∈L，(i =1，2，…，N).計算在L 中含有N 條路徑的組合數，每個組合對應一個查詢路集.

3)利用式(3)，對每個組合中的N 條路徑隨機安排順序，進行可靠度計算，

4)把可靠度最高的組合對應的查詢路集作為可靠查找方案.

5)整理查詢路集中的路徑，將可用度最高的路徑設置為第一路徑lh.

6)對于余下的N-1 條路徑，根據定理2 選出與路徑lh鏈路相同且鏈路相關性|ln∩li|由小到大的路徑進行排序.

2.3 路由查詢方案

在路由查詢過程中，每個節(jié)點通過保存的Finger 表信息來進行資源定位和路由跳轉.采用雙向的查詢模式可以讓節(jié)點根據資源標識在所處的環(huán)域中更快地獲取.同時，對于節(jié)點異?；蜴溌肥У惹闆r將觸發(fā)可靠度機制繼續(xù)查詢.由于主干網中MRs 具有強大的資源存儲與處理能力，所以在查詢過程只要能夠成功地連接到主干網即可完成查詢.本路由查詢算法的具體步驟如下:

1)當網絡中的節(jié)點s 請求呼叫查詢時，首先判斷所要查詢的信息是否處于所屬MR 中.

2)啟用Chord 雙向路由查詢模式尋找所屬MR，并確認是否成功收到應答消息，若成功轉步驟3);否則轉步驟5).

3)若查詢資源處于所屬MR，則取出資源，轉步驟6);否則轉步驟4).

4)在主干網絡中利用Chord 雙向路由查詢定位存儲該資源的MR，轉步驟6).

5)觸發(fā)可靠度多路徑選擇機制，進入主干網絡.判斷是否成功，是則轉步驟8);否則轉步驟7).

6)完成查找，不做任何更新.

7)查找失敗，轉步驟8).

8)更新網絡.

2.4 性能分析

由于原始Chord 協議構建的邏輯環(huán)中未考慮到實際物理拓撲結構，造成網絡中相鄰的節(jié)點需要完成更多的路由跳轉來實現通信，浪費不必要的開銷.所以本研究通過改進的Chord 協議在所架設的WMNs 覆蓋網絡中考慮到實際的物理拓撲結構，將本地物理相近的節(jié)點保存到邏輯Chord 環(huán)的路由表中，避免相近節(jié)點在查詢過程中出現繞路的情況.同時，基于原始Chord 只能在順時針方向上對邏輯環(huán)中節(jié)點進行查找的不足，增加逆時針方向節(jié)點的查詢策略，使得當查詢節(jié)點處于后半環(huán)時也能完成快速地定位.這樣的改進能很好地降低時間復雜度O(log2N)，在規(guī)模較大的網絡具有更高效的數據傳輸.

在WMNs 中，節(jié)點的性能與處理能力影響著節(jié)點傳輸的成功率，節(jié)點的崩潰和鏈路異常等情況使得擁有單路徑傳輸的Chord 協議無法完成可靠的路由跳轉.在原始Chord 協議中添加可靠的多路徑查詢可以有效地彌補實時查詢的缺點，而路徑的相關性則能夠優(yōu)化可靠路集中路徑順序的排列，提高路集的可靠度，增加數據傳輸的成功率.所以改進的機制相比原始Chord 協議更具有優(yōu)越性，能夠很好地適用于WMNs 覆蓋網絡實現高效的數據傳輸.

3 結 論

將P2P 的查詢模式應用于無線mesh 網絡已經成為了一種趨勢.本研究基于Chord 協議，設計了分層次和雙向查找的模式，并針對無線mesh 網絡節(jié)點、鏈路易失效的問題加入了可靠多路徑查詢方式，提高了節(jié)點的查詢效率和查詢可靠度.在下一步的研究工作中，如何有效地平衡網絡查詢過程中的QoS，從而使數據傳輸獲得高效性和可靠性將是無線mesh 網絡需要致力于解決的問題.

［1］Akyildiz I F，Wang X D.A survey on wireless mesh networks［J］.IEEE Radio Communications，2005，47(4):445－487.

［2］Wang X D，Lin A O.IEEE 802.11s wireless mesh networks:Framework and challenges［J］.Ad Hoc Networks，2008，6(6):970－984.

［3］Karrer R P，Botta A，Pescape A.High-speed backhaul networks:myth or reality?［J］.Computer Communications，2008，31(8):1540－1550.

［4］張震，王曉明.對等網中Chord 資源查找算法的研究［J］.計算機工程與應用，2006，41(11):147－153.

［5］龍建輝，陳靖，朱清超，等.LPDSR:基于Chord 算法的MANET 分級路由模型［J］.計算機工程與設計，2014，35(9):2981－2985.

［6］李文翔，沈元平，吳靜，等.無線mesh 網中可靠SIP 呼叫連接的選路技術［J］.計算機科學，2011，38(4):130－132.

［7］宗平，徐鴿.基于DHT 的Chord 路由算法改進［J］.計算機技術與發(fā)展，2012，22(9):139－142.

［8］王宏林，朱艷琴.基于信任管理的對等網絡路由選擇［J］.計算機應用，2009，29(3):669－674.

［9］汪發(fā)寶.P2P 網絡Chord 協議的分析與研究［D］.成都:西南交通大學，2010.

［10］Brito P H，de Lemos R，Rubira C M，et al，Architecting fault tolerance with exception handing:verification and validation［J］.Journal of Computer Science and Technology，2009，24(2):212－237.

［11］胡建軍，王學毅，范彬.一種網路可靠性的多路徑路由算法［J］.小型微型計算機系統(tǒng)，2014，35(8):1780－1783.