無線傳感器網(wǎng)絡(luò)不相交多路徑容錯路由研究.pdf

1、因環(huán)境惡劣、能量受限和無線信道不可靠等特性，無線傳感器網(wǎng)絡(luò)經(jīng)常出現(xiàn)節(jié)點損壞、通信鏈路中斷等故障，使得數(shù)據(jù)傳輸?shù)男瘦^低，難以滿足實際的應(yīng)用需求，因此容錯(Fault Tolerance)能力是衡量無線傳感器網(wǎng)絡(luò)性能的一個重要指標(biāo)。傳統(tǒng)網(wǎng)絡(luò)的容錯技術(shù)由于沒有綜合無線傳感器網(wǎng)絡(luò)的上述特性，因而難以應(yīng)用于無線傳感器網(wǎng)絡(luò)的實際。無線傳感器網(wǎng)絡(luò)的容錯性是指當(dāng)部分節(jié)點或鏈路失效后，能夠進(jìn)行傳輸數(shù)據(jù)的恢復(fù)或者網(wǎng)絡(luò)結(jié)構(gòu)自愈。當(dāng)前對無線傳感器網(wǎng)絡(luò)的容錯技

2、術(shù)的研究主要集中在以下五個方面:硬件容錯、覆蓋容錯、路由容錯、事件容錯和應(yīng)用容錯。其中，路由容錯是無線傳感器網(wǎng)絡(luò)容錯研究的基礎(chǔ)和重點。
　　多路徑容錯路由是路由容錯的主要方式，相比于單路徑路由機(jī)制，它在傳輸可靠性、均衡負(fù)載、容錯恢復(fù)等方面具有明顯的優(yōu)勢。但是，在多路徑路由機(jī)制中，從源節(jié)點到目的節(jié)點的多條路徑中可能包含公共節(jié)點（鏈路），公共節(jié)點（鏈路）的失效會造成多條路徑的傳輸失敗。而不相交多路徑路由機(jī)制可以有效避免公共節(jié)點（鏈路）

3、的出現(xiàn)，從而顯著提升多路徑路由的容錯性能。
　　不相交多路徑容錯路由機(jī)制面臨的主要難題有三個:一是公共節(jié)點（鏈路）避免問題，即通過何種路徑規(guī)劃機(jī)制實現(xiàn)從源節(jié)點到目的節(jié)點的多條路徑的不相交;二是不相交多路徑選優(yōu)問題，即在路徑不相交的約束下，如何優(yōu)化路徑選擇過程以達(dá)到節(jié)省能量和提高容錯性能;三是節(jié)點移動帶來的路徑斷裂問題，即在網(wǎng)絡(luò)拓?fù)洚a(chǎn)生變化的情況下，如何以最小的代價實現(xiàn)不相交多路徑的快速恢復(fù)。本文針對上述問題，基于數(shù)據(jù)冗余和路徑冗余

4、方法，對無線傳感器網(wǎng)絡(luò)的不相交多路徑容錯路由機(jī)制進(jìn)行了研究。本文的研究主要立足于五個方面:(1)網(wǎng)絡(luò)的多路徑不相交約束模型;(2)中心計算方式的不相交多路徑規(guī)劃和維護(hù)機(jī)制;(3)分布式計算方式的不相交多路徑規(guī)劃和維護(hù)機(jī)制;(4)節(jié)點移動情況下的不相交多路徑規(guī)劃和維護(hù)機(jī)制;(5)有負(fù)載均衡要求情況下的不相交多路徑規(guī)劃和維護(hù)機(jī)制。本文取得的研究成果包括如下幾個方面:
　　1.中心計算的2-不相交路徑容錯路由算法:針對某些工業(yè)應(yīng)用中網(wǎng)絡(luò)

5、拓?fù)浔容^穩(wěn)定，sink節(jié)點運算存儲能力較強(qiáng)等特點，利用全網(wǎng)信息計算出從源節(jié)點到sink節(jié)點的近似最優(yōu)2-節(jié)點（鏈路）不相交路徑，然后生成微路由表并下傳到每個節(jié)點，采用中心調(diào)度的自適應(yīng)機(jī)制提高路徑維護(hù)的靈活性。
　　2.面向不相交多路徑的multi-routing tree拓?fù)浣Y(jié)構(gòu):提出了一種面向不相交多路徑的multi-routing tree拓?fù)浣Y(jié)構(gòu)，由一個唯一的根節(jié)點和一組特殊的子樹構(gòu)成。該組子樹滿足如下三個約束:一是任意子樹

6、都是點可相交的，二是任意子樹都是邊不相交的，三是連接任一節(jié)點與其子節(jié)點的邊必屬于同一子樹。在該樹結(jié)構(gòu)下，從源節(jié)點沿不同子樹到達(dá)根節(jié)點的路徑是不相交的。
　　3.基于multi-routing tree的不相交多路徑容錯路由算法:采用集中式和分布式兩種算法在網(wǎng)絡(luò)中實現(xiàn)multi-routing tree，提出一種能量消耗與容錯性能的平衡模型:定制冗余模型，為源數(shù)據(jù)實現(xiàn)三種模式的定制冗余:重發(fā)冗余、路徑冗余和混合冗余。
　　4.

7、采用HSV色彩空間分離模型的不相交多路徑容錯路由算法:針對節(jié)點移動帶來的路徑斷裂問題，采用HSV色彩空間模型為每條鏈路建立數(shù)值化的(h，s，v)三元組，并分離使其屬于不同的色彩平面，按照不同色彩平面構(gòu)造從源節(jié)點到目的節(jié)點的多條節(jié)點不相交路徑，設(shè)計基于可變時間間隔鏈路接收信號強(qiáng)度指示值探測的不相交多路徑維護(hù)機(jī)制。
　　5.采用區(qū)域分割模型的不相交多路徑容錯路由算法:基于地理位置信息，將網(wǎng)絡(luò)部署區(qū)域分割成若干組互不重疊的元區(qū)域鏈，使得

8、源節(jié)點沿不同的元區(qū)域鏈可以生成到目的節(jié)點的多條不相交路徑，通過化“移動節(jié)點”為“靜止區(qū)域”的思想解決移動無線傳感器網(wǎng)絡(luò)的不相交多路徑容錯路由問題。
　　6.基于路徑代理的負(fù)載均衡不相交多路徑容錯路由算法:基于路徑代理思想設(shè)計，根據(jù)“一個鄰居一個路徑代理服務(wù)，不同鄰居不同路徑代理服務(wù)”的路由選擇原理，算法獲得的從源節(jié)點到sink節(jié)點的多條路徑是鏈路不相交的。提出了一種負(fù)載均衡模型，將數(shù)據(jù)流量均衡地覆蓋到多條路徑中，以延長網(wǎng)絡(luò)生存期。