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

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

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

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

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

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

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

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

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