倪仲余，黎忠文，董露陽

(1.西華大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，四川 成都 610039;2.成都大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都 610106)

0 引 言

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

圖1 WMNs 拓?fù)浣Y(jié)構(gòu)示意圖

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

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

1 網(wǎng)絡(luò)結(jié)構(gòu)模型

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

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

圖2 分層Chord 模型示意圖

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

2.1 可靠度描述

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

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

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

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

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

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

證畢.

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

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

證明 令|α| =p，|β| = |λ| =q，|α∩β| =i，|α∩λ| =j，則i ＜j.因?yàn)椋? ＜r ＜1，所以，ri＜rj，得出rp－i＜rp－j.又因?yàn)椋?/p>

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

證畢.

從定理2 可以知道，相同鏈路數(shù)的2 條路徑相關(guān)性越低則越可靠.

2.2 路由集合選擇

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

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

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

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

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

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

2.3 路由查詢方案

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

1)當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)s 請求呼叫查詢時，首先判斷所要查詢的信息是否處于所屬M(fèi)R 中.

2)啟用Chord 雙向路由查詢模式尋找所屬M(fèi)R，并確認(rèn)是否成功收到應(yīng)答消息，若成功轉(zhuǎn)步驟3);否則轉(zhuǎn)步驟5).

3)若查詢資源處于所屬M(fèi)R，則取出資源，轉(zhuǎn)步驟6);否則轉(zhuǎn)步驟4).

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

5)觸發(fā)可靠度多路徑選擇機(jī)制，進(jìn)入主干網(wǎng)絡(luò).判斷是否成功，是則轉(zhuǎn)步驟8);否則轉(zhuǎn)步驟7).

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

7)查找失敗，轉(zhuǎn)步驟8).

8)更新網(wǎng)絡(luò).

2.4 性能分析

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

在WMNs 中，節(jié)點(diǎn)的性能與處理能力影響著節(jié)點(diǎn)傳輸?shù)某晒β?，?jié)點(diǎn)的崩潰和鏈路異常等情況使得擁有單路徑傳輸?shù)腃hord 協(xié)議無法完成可靠的路由跳轉(zhuǎn).在原始Chord 協(xié)議中添加可靠的多路徑查詢可以有效地彌補(bǔ)實(shí)時查詢的缺點(diǎn)，而路徑的相關(guān)性則能夠優(yōu)化可靠路集中路徑順序的排列，提高路集的可靠度，增加數(shù)據(jù)傳輸?shù)某晒β?所以改進(jìn)的機(jī)制相比原始Chord 協(xié)議更具有優(yōu)越性，能夠很好地適用于WMNs 覆蓋網(wǎng)絡(luò)實(shí)現(xiàn)高效的數(shù)據(jù)傳輸.

3 結(jié) 論

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

［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］張震，王曉明.對等網(wǎng)中Chord 資源查找算法的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2006，41(11):147－153.

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

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

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

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

［9］汪發(fā)寶.P2P 網(wǎng)絡(luò)Chord 協(xié)議的分析與研究［D］.成都:西南交通大學(xué)，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］胡建軍，王學(xué)毅，范彬.一種網(wǎng)路可靠性的多路徑路由算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2014，35(8):1780－1783.