無線mesh網(wǎng)絡(luò)中一種路由算法及其容錯性的研究

《無線mesh網(wǎng)絡(luò)中一種路由算法及其容錯性的研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、lSSN1o09—3O44E—mail：info@CCCC．net．enComputerKnowledgeandTechnology電腦知識與技術(shù)http：／／www．dnzs．net．CllVo1．6，No．28，October2010，PP．7988-7989Tel：+86—551-56909635690964無線Mesh網(wǎng)絡(luò)中一種路由算法及其容錯性的研究龍艷(貴陽學(xué)院計算機科學(xué)系，貴州貴陽550005)摘要：該文研究了無線網(wǎng)狀網(wǎng)絡(luò)(WMN)中的路由算法及其容錯性能?？紤]到網(wǎng)絡(luò)中位置固定的節(jié)點，我們建議采

2、用準(zhǔn)固定式的路由。這是一個基于并行計算，其魯棒性和性能都優(yōu)于傳統(tǒng)Ad—hoc路由協(xié)議的路由形式我們還討論了傳輸權(quán)力控制以及網(wǎng)絡(luò)連接問題和網(wǎng)關(guān)的選擇。關(guān)鍵詞：無線網(wǎng)狀網(wǎng)絡(luò)(WMN)；無線Mesh網(wǎng)絡(luò)：路由算法：容錯性中圖分類號：TP301文獻標(biāo)識碼：A文章編號：1009—3044(2010)28—7988—02隨著移動設(shè)備，諸如筆記本電腦，蜂窩電話和掌上電腦存互聯(lián)網(wǎng)中的廣泛應(yīng)用，無線接人已經(jīng)成為一個重要的需求。無線局域網(wǎng)已引起產(chǎn)業(yè)界和學(xué)術(shù)界的極大關(guān)注。各種標(biāo)準(zhǔn)已經(jīng)建立起來了，尤其足IEEE802．11，還有一些

3、標(biāo)準(zhǔn)仍在制定中。在IEEE802．11標(biāo)準(zhǔn)中，有兩個無線接入方式：基礎(chǔ)結(jié)構(gòu)模式和Ad—Hoc模式。在前一個模式中，局域網(wǎng)有一個集中的網(wǎng)絡(luò)設(shè)備，我們稱為接入點．它使用有線介質(zhì)直接連接到互聯(lián)網(wǎng)(通常是以太網(wǎng)雙絞線)，它作為互聯(lián)網(wǎng)各個節(jié)點問數(shù)據(jù)包收發(fā)的一個無線接口。而在Ad—hoc的模式中則沒有這種集中化的設(shè)備，全部站或節(jié)點都以對等模式運行，并且爭奪共享的無線帶寬。通過這種方式，它們在所屬區(qū)域內(nèi)能夠相互進行交流，但卻無法訪問外部網(wǎng)絡(luò)。在實際使用中，另一種情況會出現(xiàn)：在區(qū)域網(wǎng)絡(luò)中的所有用戶需要在本地嘗試連接到互聯(lián)網(wǎng)，

4、但其中有一些又超出了接人點一跳傳輸?shù)姆秶?。這種情況通常發(fā)生在有線上網(wǎng)太貴以至于網(wǎng)絡(luò)難以覆蓋，像利用率低或布線費用高等種種情形之下。在這種情況下，已經(jīng)接人Internet的接人點由于頻繁的被訪問更類似于網(wǎng)關(guān)，這種網(wǎng)絡(luò)就被稱為無線網(wǎng)狀網(wǎng)絡(luò)(WMN)。無線網(wǎng)狀網(wǎng)絡(luò)是一種網(wǎng)絡(luò)中的節(jié)點可通過一個或者多個網(wǎng)關(guān)接人互聯(lián)網(wǎng)的移動Ad—hoc網(wǎng)絡(luò)。盡管傳統(tǒng)的那些像DSR和AODV協(xié)議等Ad—hoe路由算法可在無線網(wǎng)狀網(wǎng)絡(luò)中使用，但其性能比通常不夠理想。其存在的問題是這些算法中的假設(shè)在WMN中不是正確的。而且這些假設(shè)在無線網(wǎng)狀網(wǎng)

5、絡(luò)環(huán)境中對傳輸性能導(dǎo)致了明顯的弊端。1WMN中的路由分析我們可以采用準(zhǔn)XY無線網(wǎng)狀網(wǎng)絡(luò)路由算法。xY路由通常使用計算機網(wǎng)或環(huán)面拓?fù)湟员苊庀x洞路由的死鎖iJjc在使用這類網(wǎng)格拓?fù)浣Y(jié)構(gòu)的無線網(wǎng)狀網(wǎng)絡(luò)中，每個節(jié)點直接路由至其鄰節(jié)點。例如，圖l中的一個節(jié)點(x，Y)，其直接的相鄰節(jié)點為x一1，y)，(x+1，y)，(x，y-1)，x，y+1)，每個節(jié)點都為其相鄰節(jié)點與網(wǎng)關(guān)執(zhí)行數(shù)據(jù)包收發(fā)的任務(wù)。分組延遲是由于多種原因造成的，然而在WMN中最關(guān)鍵的原因是路徑長度。在相同流量條件下，一個較小的數(shù)日的跳數(shù)能夠?qū)е螺^短的包延遲

6、。對于在網(wǎng)格網(wǎng)絡(luò)中S(x，ys)和D(xyo)兩個節(jié)點，其最短路徑如下：d=Ixs—xd+lys—yDI(1)為了盡量減少包的延遲，我們希望使用最短路徑。然而這必須在最小范圍的碰撞內(nèi)，因為作為最短路徑的高競爭路徑往往不一定是理想的。因此，我們提出了一個最短路徑負(fù)荷平衡的不同路由。我們的協(xié)議如下：Step1：如果下一跳是網(wǎng)關(guān)，則傳輸與之競爭：否則：Step2：確定相鄰節(jié)點的負(fù)荷：Step3：選擇其中較輕負(fù)荷的路徑為下一跳路徑并傳輸：Step4：回到Step1。通過這種方式我們的協(xié)議實現(xiàn)了不同的路由。可用的路徑數(shù)

7、量的確定可以根據(jù)下列定理得出：定理1：在WMN中，對于任何給定的兩個節(jié)點S(x，ys)和D(xD，Yo)，都存在：Sllll如圖1中不同路徑都有距離dO)。證明：我們通過歸納來證明定理。如果沒有一般性的損失，假設(shè)XS≤x。andY≤y．，。3jStep1：由于S(xs，ys)到xs'。)只有唯一一條路徑，同樣S(xs，Ys)~lJ(xys)也只有唯一一3l0l5jl條路徑，則S(xs,ys)到xys+。)的最短路徑數(shù)為2；3556Step2：假設(shè)從S到T(XT,yT)，最短路徑數(shù)目為：l15∞l姑l62l56

8、l2652．(等]D又假設(shè)xs≤XTandys≤YT圖1互異路由計算收稿日期：2010—08-177988，·網(wǎng)絡(luò)■訊硬安全本欄目責(zé)任編輯：馮蕾第6卷第28期(2010年10月)ComputerKnowledgeandTechnology電腦知識與技術(shù)Step3：從SN(XT+，yT)，最短路徑數(shù)目可被遞歸計算得：一Xs+1+—sI一Xs+1ilsyr—Ysj!從SN(x-r．y)，路徑數(shù)為：‘一X