Ganesan D, Govindan R, Shenker S, et al. Highly-resilient, energy-efficient multipath routing in wireless sensor networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2001, 5(4): 11-25.
文章題目可以翻譯為：無(wú)線傳感器網(wǎng)絡(luò)中高彈性、節(jié)能的多徑路徑

在多徑中一般希望找到的多條路徑之間都是互斥的，這樣可以避免擁塞，也能提升抗毀性，但是本文找到的每條路徑都和主路徑幾乎只有一兩個(gè)節(jié)點(diǎn)的差異，這樣有效地保證了備用路徑的長(zhǎng)度不會(huì)遠(yuǎn)超主路，而且在單節(jié)點(diǎn)毀壞的情況下有更高的抗毀性（也就是本文提到的彈性）。本文還提出了一種本地的算法來(lái)遞歸的找到從匯點(diǎn)到源點(diǎn)的（非理想化）多徑，這種方案巧妙地利用了回溯發(fā)送強(qiáng)化消息的想法。

不過(guò)本文只提出了路徑尋找的方案，并未給出多條路徑之間包分配的方案，似乎備用路徑并不會(huì)同時(shí)和主路徑啟動(dòng)，只有主路徑毀壞后才會(huì)在備用路徑中選擇新路進(jìn)行傳輸，所以是個(gè)假的多徑

第一次接觸相關(guān)內(nèi)容，所以進(jìn)行了比較詳細(xì)的翻譯，詳細(xì)的文章內(nèi)容可以看下面

abstract

以前提出的傳感器網(wǎng)絡(luò)中數(shù)據(jù)的傳播方案需要周期性的低速率的數(shù)據(jù)洪泛來(lái)實(shí)現(xiàn)失敗的恢復(fù)?？紤]建設(shè)兩種多徑來(lái)實(shí)現(xiàn)當(dāng)源和目的之間鏈路失敗時(shí)能低能耗的恢復(fù)。不相交的多徑在以前已經(jīng)研究過(guò)，我們提出一種新穎的編織（braided）多徑方案，將會(huì)獲得一些局部不相交的多徑。發(fā)現(xiàn)這種方案在單點(diǎn)失效和局部失效中都是一種節(jié)能的恢復(fù)方案。

1. introduction

傳感器網(wǎng)絡(luò)被認(rèn)為是小型網(wǎng)絡(luò)傳感器節(jié)點(diǎn)如Rene組成的大規(guī)模網(wǎng)絡(luò)。這樣的節(jié)點(diǎn)可能會(huì)有一個(gè)或者多個(gè)傳感器并且在被感知的環(huán)境中會(huì)被密集的部署來(lái)最大化生存時(shí)間，并同時(shí)處理動(dòng)態(tài)和失效。

大規(guī)模傳感器網(wǎng)絡(luò)部署的三個(gè)法則是：可擴(kuò)展性（網(wǎng)絡(luò)可能包含成千節(jié)點(diǎn)）、節(jié)能（尤其是無(wú)線通信引發(fā)比計(jì)算更嚴(yán)重的能耗）以及魯棒性（對(duì)環(huán)境的影響以及節(jié)點(diǎn)的失效抵抗性較強(qiáng)）

這些網(wǎng)絡(luò)可能需要新奇的路由策略來(lái)可擴(kuò)展、魯棒的數(shù)據(jù)傳輸，如直接擴(kuò)散。更引人注意的是路徑強(qiáng)化的概念：網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)可能會(huì)做出本地決定（可能基于感知到的流量特點(diǎn)）來(lái)從一個(gè)或多個(gè)鄰居而不是從其他鄰居優(yōu)先提取數(shù)據(jù)，我們交這種路徑設(shè)置技術(shù)為本地化算法。

本文提出一種多路徑路由可以提升節(jié)點(diǎn)失效的彈性。我們探索了兩種不同的構(gòu)造兩節(jié)點(diǎn)之間多徑的本地算法。一種是基于以前工作的傳統(tǒng)的節(jié)點(diǎn)不相交多徑方案，這里備用路徑不會(huì)影響原始路徑。另一種方案放棄了不相交路徑的需求，而是建立了編織路徑。在編織路徑下，幾乎沒有完全不相交的路徑，但又很多局部不相交的備用路徑。

使用兩個(gè)重要的度量方案來(lái)判斷這些方法的性能：彈性和保持的開銷，且二者之間有一個(gè)內(nèi)在的權(quán)衡。更好的彈性一般都會(huì)消耗更高的能源。本文將調(diào)查提出的兩個(gè)路由算法的權(quán)衡。

多徑路由的文獻(xiàn)很多，我們不打算綜合總結(jié)相關(guān)工作。據(jù)我們所知，我們的算法是第一個(gè)在無(wú)線傳感的多徑路由中嘗試評(píng)估能源/彈性的權(quán)衡的。我們的一些設(shè)計(jì)選擇受到分三路有和ad-hoc網(wǎng)絡(luò)的多徑的影響。

2. 不相交和編織路徑

傳統(tǒng)多徑的提出是兩個(gè)原因：負(fù)載均衡和魯棒性。負(fù)載均衡的基礎(chǔ)就是需要消耗能源，因此這不是本文在傳感器網(wǎng)絡(luò)中的重點(diǎn)，我們更像使用多徑路由快速找到備用路徑。我們的基本原理是：假定從應(yīng)用的角度，期望的目標(biāo)是通過(guò)主路徑的也就是最好的路徑傳遞數(shù)據(jù)。但是，為了可擴(kuò)展的從失效的主路徑恢復(fù)（而不需要通過(guò)泛洪重新尋找路徑），我們構(gòu)造并保持一小部分備用路徑。但保持這部分路徑需要發(fā)送低速率的數(shù)據(jù)包來(lái)保證路徑的活性且不能妨礙路徑出現(xiàn)問題。

我們考慮兩種設(shè)計(jì)：
2.1的不相交設(shè)計(jì)和2.2的編織設(shè)計(jì)。這兩種方案的能源-彈性權(quán)衡將會(huì)通過(guò)仿真來(lái)探索。

2.1 不相交多徑

構(gòu)造備用路徑，他們與主路徑以及彼此之間都是節(jié)點(diǎn)不相交的。因此這些路徑不會(huì)被主路徑的失效影響，但可能不如主路徑的效果（如時(shí)延）好。

理想化的k節(jié)點(diǎn)不相交多徑的定義是：對(duì)第i條節(jié)點(diǎn)不相交的路徑，選擇與當(dāng)前路徑節(jié)點(diǎn)不相交的最好的路徑，這將會(huì)得到理想的k不相交節(jié)點(diǎn)多徑

有一種本地算法來(lái)構(gòu)造不相交路徑。假定某個(gè)時(shí)間一些低速樣本初始化泛洪到這個(gè)網(wǎng)絡(luò)，匯點(diǎn)根據(jù)經(jīng)驗(yàn)將知道哪個(gè)鄰居能提供最高質(zhì)量的數(shù)據(jù)（低丟包或者低時(shí)延），它將會(huì)向這個(gè)鄰居發(fā)送一個(gè)主路徑（primary-path）強(qiáng)化，然后根據(jù)一開始擴(kuò)散的方案，該鄰居也將決定它面向源點(diǎn)的最優(yōu)質(zhì)的鄰居發(fā)送消息。

不久，匯點(diǎn)向次優(yōu)鄰居發(fā)送一個(gè)備用路徑強(qiáng)化。由于每個(gè)節(jié)點(diǎn)只能接受一次強(qiáng)化，備用路徑可以保證不相交。收到多個(gè)強(qiáng)化的節(jié)點(diǎn)會(huì)拒絕第一個(gè)以外的強(qiáng)化。這個(gè)方案基本上可以獲取k個(gè)不相交路徑

這叫做本地不相交多徑。這可能受限于本地知識(shí)產(chǎn)生比理想抓概況更長(zhǎng)的備用路徑，然后導(dǎo)致兩條路徑之間有性能的差異。

2.2 編織多徑

盡管不相交路徑的彈性很大，但因?yàn)橐恍┞窂娇赡鼙戎髀窂介L(zhǎng)，因此對(duì)能源消耗是不友好的。編織多徑放寬了節(jié)點(diǎn)不相交的需求。一個(gè)編織中的備用路徑只與主路徑有局部不同，而不是所有節(jié)點(diǎn)都不同。

如圖1，編織多徑的結(jié)構(gòu)性定義為：對(duì)主路徑中的每個(gè)節(jié)點(diǎn)，找到從源節(jié)點(diǎn)到目的節(jié)點(diǎn)中不包含該節(jié)點(diǎn)的最優(yōu)路徑。這個(gè)備用路徑不需要與主路徑完全不同。我們將這個(gè)路徑集合稱為理想編織多徑。如名字所示，組成編織的鏈路要么在主路徑上，要么離主鏈路很近。直覺上，備用路徑組成的編織耗費(fèi)的能源與主路徑相當(dāng)。

接下來(lái)提出一個(gè)生成編織的本地方案。匯點(diǎn)向最優(yōu)質(zhì)的鄰居發(fā)送一個(gè)主路徑強(qiáng)化，同時(shí)向次優(yōu)鄰居發(fā)送備用路徑強(qiáng)化。主路徑上的其他節(jié)點(diǎn)遞歸地產(chǎn)生一個(gè)備用路徑強(qiáng)化到它的下一個(gè)最優(yōu)鄰居。這樣每個(gè)節(jié)點(diǎn)都會(huì)嘗試在主路徑最接近的鄰居附近路由。當(dāng)非主路徑上的節(jié)點(diǎn)收到備用路徑強(qiáng)化，它會(huì)傳播到最優(yōu)鄰居那里。而主路徑上的節(jié)點(diǎn)收到備用路徑強(qiáng)化時(shí)，就不需要傳遞這個(gè)強(qiáng)化了。

圖2是使用本地算法得到的編織。n(k+1)發(fā)出的備用路徑在加入主路徑的n(k-2)以前向n(k)附近的a(i)和a(i-1)發(fā)送了備用路徑強(qiáng)化。實(shí)際應(yīng)用中，本方案并不能保證備用路徑在主路徑周圍迂回。它的效果與節(jié)點(diǎn)密度以及其他的因素密切相關(guān)

3. 評(píng)估方案

本章節(jié)精確定義評(píng)估多徑性能的兩個(gè)度量值：保持開銷和彈性。我們還描述了我們?cè)u(píng)估多路徑機(jī)制彈性的失效模型。最后討論了實(shí)驗(yàn)方案并列出了影響多徑的參數(shù)

3.1 保持開銷

保持開銷說(shuō)的是為了保持一個(gè)備用路徑需要階段性的發(fā)送keepalive包所帶來(lái)的能源耗費(fèi)。假定源節(jié)點(diǎn)在一段時(shí)間T內(nèi)會(huì)向主路徑傳播r個(gè)事件。假定εr個(gè)時(shí)間是通過(guò)備用路徑發(fā)送的，每個(gè)備用路徑要收到等比例多的keep-alive流。維持備用路徑需要的能源與備用路徑的長(zhǎng)度（也就是跳數(shù)）是成比例的。因此保持開銷為$(L_a?L_p)/L_p$, 其中$L_a$是備用路徑的平均長(zhǎng)度，$L_p$是主路徑的平均長(zhǎng)度。

3.2 失效

給出兩種不同的失效模型：單節(jié)點(diǎn)失效以及地理位置相關(guān)失效

單點(diǎn)失效（isolated failure）：在一個(gè)時(shí)間段T內(nèi)，每個(gè)節(jié)點(diǎn)有$p_i$的概率失效。定義單點(diǎn)失效的彈性為：假定主路徑上至少有一個(gè)節(jié)點(diǎn)失效時(shí)，在時(shí)間段T內(nèi)至少有一個(gè)備用路徑有效的概率。

局部失效（patterned failure）：局部失效為在一個(gè)半徑為$R_p$的圓內(nèi)所有節(jié)點(diǎn)都失效。圓位置的選取是隨意的但希望能模型化一個(gè)理想的物理情形的波傳播。這個(gè)模型的粗略解釋是，在一個(gè)地理區(qū)域內(nèi)持續(xù)的活動(dòng)或環(huán)境影響(如降雨消失)可以導(dǎo)致這種相關(guān)的失敗。
假定圓中心是隨機(jī)分布的。由于缺乏實(shí)際模型，假定在T時(shí)間內(nèi)局部失效是泊松分布的，參數(shù)為λ_p。
對(duì)每個(gè)多徑方案，對(duì)局部失效的保持開銷可以定義為：時(shí)間T，源匯之間至少有一條備用路徑的概率，假定至少有一個(gè)節(jié)點(diǎn)在局部失效的范圍內(nèi)。

3.3 方案細(xì)節(jié)

在ns-2使用類似于802.11的MAC仿真。最優(yōu)鄰居設(shè)定為第一個(gè)傳遞到消息的鄰居。實(shí)驗(yàn)中傳感器節(jié)點(diǎn)均勻分布在一個(gè)400平方米的平面上，傳播半徑為40m。

為計(jì)算單點(diǎn)失效的彈性，重復(fù)下面的步驟:
1. 每個(gè)節(jié)點(diǎn)失效的概率為$p_i$
2. 當(dāng)主路徑節(jié)點(diǎn)失效時(shí)，如果集合中有可替代路徑那么分配數(shù)字1，否則分配0
單點(diǎn)失效的彈性設(shè)置為值的平均值。調(diào)整實(shí)驗(yàn)的運(yùn)行次數(shù)和每次運(yùn)行中的集合數(shù)，以獲得可接受的95%置信區(qū)間。

局部失效的彈性計(jì)算重復(fù)下面的步驟：
1. 在參數(shù)為λ_p的泊松分布中選取一個(gè)整數(shù)n
2. 隨機(jī)向平面上放置n個(gè)點(diǎn)
3. 將半徑$R_p$內(nèi)所有節(jié)點(diǎn)都失效
4. 如果主路徑失效，當(dāng)有替代路徑可用設(shè)為1，否則設(shè)為0
局部失效的彈性設(shè)置為值的平均值。調(diào)整實(shí)驗(yàn)的運(yùn)行次數(shù)和每次運(yùn)行中的集合數(shù)，以獲得可接受的95%置信區(qū)間。

3.4 定性比較

使用圖3中的理想化模型來(lái)進(jìn)行直觀上的理解分析。

備用不相交路徑的耗費(fèi)取決于網(wǎng)絡(luò)的密度。低密度情況下備用路徑遠(yuǎn)長(zhǎng)于且耗費(fèi)高于主路徑。高密度下找到不相交且路徑較短的備用路徑的幾率上升。但編織中的備用路徑的能源耗費(fèi)與主路徑相當(dāng)，和密度關(guān)系不大，因此在低密度情況下保持開銷的差距很大

不相交路徑中路徑是完全獨(dú)立的，但單節(jié)點(diǎn)的失效將會(huì)導(dǎo)致整個(gè)路徑的失效。編織路徑中備用路徑并不是獨(dú)立的，主路徑上的故障組合可能切斷所有備用路徑。但替代路徑的數(shù)量明顯比路徑上的節(jié)點(diǎn)數(shù)多，這帶來(lái)了很大的彈性。

局部失效對(duì)不相交路徑和編織路徑的影響不同。主路徑的局部失效會(huì)影響主路徑附近替代路徑的失效，較遠(yuǎn)的替代路徑則不會(huì)被影響。由于編織路徑鼓勵(lì)就近備用，因此不相交路徑可能彈性更高一些。

4. 仿真結(jié)果

仿真的目標(biāo)是對(duì)比不同多徑方案的能源/彈性權(quán)衡、對(duì)網(wǎng)絡(luò)密度的依賴性，以及對(duì)理想化模型的驗(yàn)證。圖4是能源/彈性權(quán)衡的一個(gè)示例。可以看到對(duì)單點(diǎn)失效，2-不相交理想多徑相較于理想編織多徑彈性很差，且開銷更高。對(duì)局部失效，兩者彈性幾乎相同，但不相交多徑的保持開銷更高。在本地算法中有著相同的表現(xiàn)

顯然，圖4沒有展示所有的結(jié)果，我們做了很多驗(yàn)證看各參數(shù)的改變對(duì)度量值的變化，并總結(jié)了最突出的結(jié)果。

保持開銷：總體上，理想化方案中，編織多徑需要的開銷要低于2-不相交多徑，在低密度時(shí)差距尤其明顯。本地算法中，低密度區(qū)的編織方案并未和理想化模型中展示相同的特點(diǎn)，但在高密度時(shí)仍接近。在保持開銷上，高密度區(qū)的2-不相交多徑幾乎是一個(gè)數(shù)量級(jí)的高于編織方案。也就是說(shuō)，構(gòu)造低開銷的編織方案比不相交路徑方案可能更簡(jiǎn)單

單點(diǎn)失效時(shí)的彈性：總體而言，理想方案中編織方案比不相交方案更有彈性，在高密度區(qū)差距更加明顯。本地方案比理想化方案彈性稍差，因?yàn)樗鼈兊谋镜胤桨付紩?huì)找到比理想方案更長(zhǎng)的路徑

區(qū)域失效時(shí)的彈性：理想方案中，相較于2-不相交和3-不相交方案，編織方案的彈性更強(qiáng)。在本地方案中，編制方案的彈性隨密度變化強(qiáng)度比理想方案更距離。隨著失效頻率的增加或者失效半徑的增加，彈性降低，其中失效半徑的影響更明顯。增加不相交路徑的數(shù)量只會(huì)給出適度的彈性收益，但消耗極大。

5. 結(jié)論

我們證明多徑路由可以在無(wú)線傳感網(wǎng)絡(luò)中用來(lái)高能源有效的路徑恢復(fù)。我們探索并仿真了一種新穎的編織方案設(shè)計(jì)，方案有很大的前景

編織多徑與不相交多徑在局部失效中恢復(fù)能力相當(dāng)，而在單點(diǎn)失效中比不相交多徑高50%，而維護(hù)開銷僅有三分之一。

我們相信設(shè)計(jì)一種本地的低能耗的方案來(lái)生成不相交替代路徑更加困難，因?yàn)楸镜厮惴ㄈ狈ψ銐虻男畔?lái)找到低時(shí)延的替代路徑。

最后，增加不相交路徑的確會(huì)提升彈性，但是也會(huì)帶來(lái)更高的能源耗費(fèi)。少量的能量消耗并不能顯著地提高不相交路徑的彈性。

總結(jié)

以上是生活随笔為你收集整理的Highly-Resilient, Energy-Effificient Multipath Routing in Wireless Sensor Networks阅读报告的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。