無線傳感器網(wǎng)絡(luò)中多路徑路由的研究.pdf

1、輸出的路徑集合在所有的可能解中具有最小的長度之和?，F(xiàn)有的分布式尋找連接s和t的多條不相交路徑的方法既不能保證答案正確性也不能保證結(jié)果最優(yōu)性。雖然有一些集中式方法可以保證答案正確性和結(jié)果最優(yōu)性,但是它們都需要收集全網(wǎng)的拓?fù)湫畔?從而不適合應(yīng)用在傳感器網(wǎng)絡(luò)中。本文提出了一個高效的完全分布式算法OFDP,通過節(jié)點間交換少量的數(shù)據(jù),就可以找到k條長度之和最小的不相交路徑。OFDP既能保證答案正確性又能保證結(jié)果最優(yōu)性。OFDP不需要從網(wǎng)絡(luò)中收集任

2、何信息,節(jié)點的信息交換也不依賴于任何結(jié)構(gòu)。如果不考慮路徑的長度,通過對OFDP進行簡化,本文還提出了另一個用于解決k不相交路徑問題的分布式算法FDP。實驗結(jié)果驗證了這兩個算法的高效。
　　第三,本文研究了長度受限的不相交路徑問題,即給定兩個節(jié)點s和t以及長度限制L,尋找最多的連接s和t的不相交路徑,使得每條路徑的長度都不大于L。首先考慮每個鏈接的長度都是1的情況。當(dāng)L≥5時,這個問題不但是NP完全問題而且是APX完全問題。因此不存

3、在這個問題的多項式時間近似模式,以常數(shù)近似比來近似這個問題也是非常難的。迄今為止,只有一個關(guān)于這個問題的啟發(fā)式算法被提出,而且該算法采取的是集中式的處理方式。本文提出了這個問題的一個√n近似算法GDA以及GDA的分布式實現(xiàn)。其中,n是網(wǎng)絡(luò)中節(jié)點的數(shù)量。另外,本文還給出了這個問題的一個分布式的啟發(fā)算法OPDA。OPDA可以很好地應(yīng)對每個鏈接都有任意長度的情況。實驗結(jié)果表明,無論是在找到的路徑數(shù)量方面還是在通信效率方面,OPDA都有很高的效

4、率。
　　第四,本文研究了(廣義)非干擾路徑問題,即給定網(wǎng)絡(luò)中的k對節(jié)點{s1, t1},...,{sk, tk},用非干擾路徑來連接最多的節(jié)點對。本文證明了即使當(dāng)k=2時,這個問題也是一個NP難問題。本文還證明了對于任意近似這個問題是NP難的。其中,m是網(wǎng)絡(luò)中鏈接的數(shù)量。因此,√m是可能取得的最好的近似比。本文給出了這個問題的一個貪心算法GSPW,并證明了GSPW的近似比為√m。本文還給出了這個問題的一個在線算法OSBPW,及其