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

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

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

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

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