基于小世界圖無線多跳網(wǎng)絡(luò)的研究

王雪冰

摘 要：將小世界圖的思想應(yīng)用于無線多跳網(wǎng)絡(luò)。通過選擇一小部分節(jié)點并放大它們之間的通信距離來建立一個網(wǎng)絡(luò)模型。理論計算和仿真實驗證明，這種模型可以表現(xiàn)出小世界模型的平均路徑長度和聚類系數(shù)這二大特性。基于這個模型，提出了一個非均勻概率的洪泛算法。仿真結(jié)果表明，在網(wǎng)絡(luò)覆蓋和跳數(shù)這二個方面，小世界無線多跳網(wǎng)絡(luò)大大優(yōu)于一般的無線多跳網(wǎng)絡(luò)模式。

關(guān)鍵詞：小世界圖 無線多跳網(wǎng)絡(luò) 概率泛洪

一、引言

1967年，Milgram做了一個著名實驗，他通過要求參與者傳遞信件，探索路徑長度在相識人群網(wǎng)絡(luò)中的分布。著名的“六度分離”概念正是起源于這個實驗，盡管這個概念并沒有出現(xiàn)在Milgram的著作中。 現(xiàn)代研究表明，在關(guān)系圖中，重新布線或加入一些隨機關(guān)聯(lián)，將會導(dǎo)致常規(guī)圖表有著很低的平均路徑長度和高聚類的特性。我們稱這類圖表為小世界圖。

無線多跳網(wǎng)絡(luò)，包括Ad-hoc和網(wǎng)絡(luò)傳感器，它屬于依靠節(jié)點之間的距離來鏈接的空間圖形類別。實際上，這種網(wǎng)絡(luò)并不被認為是小世界圖，因為它很難在節(jié)點間建立一個大范圍的連接。但是，如果對無線收發(fā)器的通信范圍做一些修改，我們就可以得到更小的平均路徑長度，這樣就可以使無線網(wǎng)絡(luò)具有了小世界特征。本論文中，將介紹一種基于小世界的無線網(wǎng)絡(luò)模型。

此外，泛洪是一種在廣播應(yīng)用和作為其他的路由協(xié)議中必要的消息傳播技術(shù)，例如在DSR（Dynamic Source Route）和ODMRP（On Demand Multicast Route Protocol）路由建設(shè)過程中，泛洪是必不可少的輔助和路由維護技術(shù)。但由于大量的包重播，信道爭用和撞包的影響，簡單的洪泛算法是遠遠不夠的。為了節(jié)約寶貴的帶寬，研究人員已經(jīng)提出了概率泛洪算法。本論文中，將不均勻概率泛洪算法與小世界無線網(wǎng)絡(luò)模型相結(jié)合。仿真結(jié)果表明，這樣的組合會顯現(xiàn)出極高的效率。

我們將建立一個小世界的無線網(wǎng)絡(luò)模型。我們將提出一種基于小世界模型的非均勻概率泛洪算法。我們還將對所建模型和算法做詳細的分析，并將網(wǎng)格網(wǎng)絡(luò)和隨機網(wǎng)絡(luò)與普通的無線多跳網(wǎng)絡(luò)模型進行比較。

二、建立小世界無線網(wǎng)絡(luò)

典型的多跳無線網(wǎng)絡(luò)中，所有的收發(fā)信機都具有相同的通信范圍。當(dāng)節(jié)點之間的距離超過該范圍時，節(jié)點會通過路由對數(shù)據(jù)包進行交換，從而建成一個多跳（multi-hop）網(wǎng)絡(luò)。在該小世界模型，隨機選擇一些節(jié)點并配備可與其他節(jié)點進行雙倍距離通信的發(fā)送機。可以通過降低比特率，建立邏輯鏈路，或者配備多個無線電設(shè)備節(jié)點來建立。仿真表明，只需要將一小部分的節(jié)點變?yōu)閺姽?jié)點就可以顯現(xiàn)出小世界效應(yīng)。

仿真結(jié)果是基于創(chuàng)建400（20*20）個網(wǎng)格網(wǎng)絡(luò)節(jié)點來實現(xiàn)的，對每個節(jié)點而言最多有4個鄰節(jié)點。隨機選擇其中的節(jié)點作為強節(jié)點，可能有8個鄰節(jié)點。隨著強節(jié)點數(shù)量的增多，平均路徑長度和聚類系數(shù)便可以進行計算。沒有強節(jié)點或有400個強節(jié)點是兩個極端的網(wǎng)絡(luò)拓撲結(jié)構(gòu)。通過仿真結(jié)果可以發(fā)現(xiàn)，只需要有20%的強節(jié)點，平均路徑長度和聚類系數(shù)這兩項指標就可以很接近極限。在此基礎(chǔ)上繼續(xù)增加強節(jié)點數(shù)目，并不能明顯提高的效果。

由于強節(jié)點是在仿真網(wǎng)絡(luò)中隨機選取的，因此位于網(wǎng)格邊界上的節(jié)點對長度和聚類的影響很小。如果我們了解并能利用這種網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，那么就有可能在某些應(yīng)用場合下使用全球定位系統(tǒng)，通過有意識地選擇一些特殊的強節(jié)點，便可以得到更高的平均路徑長度和聚類系數(shù)增益。

三、非均勻概率的泛洪算法

對于無線多跳網(wǎng)絡(luò)，我們可以將無線多跳網(wǎng)絡(luò)中的節(jié)點與站點之間的關(guān)系看作類似為滲流理論中的滲流點一樣。Bhaskar對無線Ad-hoc網(wǎng)絡(luò)的相變現(xiàn)象做了詳細的說明。在對概率廣播技術(shù)中的移動Ad-hoc網(wǎng)絡(luò)（MANET）做了更深入的研究。他們得出一個結(jié)論，超過一定束縛的廣播傳送，例如pc，就不能得到很明顯的提高。在這部分，我們將提出一個基于小世界的無線網(wǎng)絡(luò)模式的非均勻的概率洪泛算法，并利用概率泛洪技術(shù)將它的優(yōu)勢與傳統(tǒng)的泛洪無線網(wǎng)絡(luò)算法相比較。

在普通的無線多跳（multi-hop）網(wǎng)絡(luò)模型中，使用的都是概率廣播技術(shù)，所有節(jié)點都有相等的傳輸半徑并有著相同的頻帶。每個節(jié)點都配有一個發(fā)送機和一個接收機，并有著相同的重播概率。

但是在我們所建的小世界無線網(wǎng)絡(luò)模式中，每個節(jié)點配備一個發(fā)射器和兩個接收器。在整體網(wǎng)絡(luò)中有兩個傳輸頻帶，一個用于強節(jié)點，另一個用于普通節(jié)點。所有節(jié)點都可以接收和處理的兩個頻帶的信號。其中強節(jié)點的通信距離是一個普通節(jié)點的兩倍。不僅如此，強節(jié)點比普通節(jié)點具有更大的重播概率，這就是所謂的非均勻概率洪泛算法。

通過一系列的仿真可以比較上述二種不同模型的效果，仿真結(jié)果是基于二種不同網(wǎng)絡(luò)：格形網(wǎng)絡(luò)和隨機網(wǎng)絡(luò)。

1、網(wǎng)格網(wǎng)絡(luò)案例

通過網(wǎng)格仿真：在2000米*2000米的區(qū)域，將400個節(jié)點設(shè)置為20行和20列并分布在此區(qū)域上。節(jié)點的通信半徑設(shè)置為100米，所以在小世界模型中的強節(jié)點將具有200米的覆蓋距離。將節(jié)點坐標為（1000，1000）的位置作為廣播源，其他節(jié)點作為目標節(jié)點。在模擬中，隨著重新發(fā)送的概率增加將會使0變化為1，這樣兩個目標統(tǒng)計就可收集。第一是接收包的節(jié)點的數(shù)目，這將反映一定概率泛洪時所覆蓋的區(qū)域。第二點就是統(tǒng)計跳數(shù)，這將能反映平均路徑長度。與多數(shù)研究類似，我們使用802.11 DCF作為MAC協(xié)議。

很容易就能看出，相比較普通模型，小世界模型有更廣闊的覆蓋區(qū)域，即使小世界模型采用了比較小的重傳概率。此外，小世界模型的跳數(shù)還遠小于一般模型。伴隨而來的是，相變現(xiàn)象也會出現(xiàn)在一般模型中。

2、隨機網(wǎng)絡(luò)案例

隨機網(wǎng)絡(luò)仿真設(shè)置與網(wǎng)格網(wǎng)絡(luò)相類似，不同之處只是將400個節(jié)點隨機分布到2000*2000米的表面上。選擇一個在（1000，1000）附近的節(jié)點為廣播源。

=NπR2S-1

（1）

無線多跳網(wǎng)絡(luò)的連通性與平均節(jié)點度相關(guān)，如等式1所定義，其中N表示節(jié)點的數(shù)目，S表示區(qū)域面積，R為通信半徑 。當(dāng)平均節(jié)點度超過了6，ad-hoc網(wǎng)絡(luò)的連接的概率將達到95%以上。如果上面提到的隨機網(wǎng)絡(luò)中節(jié)點使用的通信半徑為100m，那么平均節(jié)點度只有2.14 ，所以的連接性非常脆弱的。為了減少未連接網(wǎng)絡(luò)的影響，我們將一般的無線Ad-hoc網(wǎng)絡(luò)的通信半徑擴展到200米。相比之下，在小世界模型中，普通節(jié)點使用150米半徑和強節(jié)點為300米。接下來我們將看到，盡管小世界模型比一般模型使用較短的覆蓋距離，但是它的性能卻優(yōu)于后者。在網(wǎng)格網(wǎng)絡(luò)中使用相同的統(tǒng)計方式。從仿真結(jié)果來看，可以總結(jié)出，小世界模型比普通模型更優(yōu)越。

（1）覆蓋效益

小世界模型的使用0.2的重傳的概率就相當(dāng)于大約390個節(jié)點所能達到的傳播覆蓋范圍，而對于普通模型將需要采用0.6的重傳概率。較大重傳概率，將會導(dǎo)致更多沖撞和更多的電力成本。

（2）功耗效益

正如我們上面提到的小世界模型中，通信半徑為150m的320個節(jié)點和半徑為300m的80節(jié)點。但是在一般模型中的所有節(jié)點都將使用200米的通信距離。根據(jù)在自由空間的傳輸公式（見方程2），可以計算出，為獲得相同的接收功率Pr，小世界模型與普通模型相比，總發(fā)送功率大約可以節(jié)省13.75%。

PrPt=GtGrλ4πd2

（2）

（3）多跳效益

小世界模型的跳數(shù)明顯低于同類中一般模型。一方面，小的跳數(shù)意味著更小的傳輸延遲，這對實時應(yīng)用是非常重要的，另一方面，小的跳數(shù)是相當(dāng)于更短的路徑長度，這也正是小世界曲線圖的特性。

應(yīng)當(dāng)指出，盡管小世界模型的總消耗功率小于一般的模型，但強節(jié)點的功率消耗卻是非常大的。為了解決這個問題，可以通過對每個節(jié)點裝備雙收發(fā)器，并周期性的隨機選擇強節(jié)點。

四、結(jié)論

非均勻概率的洪泛算法，如基本的泛洪技術(shù)，是非常簡單并易于實現(xiàn)的。它不需要任何控制成本。在模擬仿真中，小世界無線網(wǎng)絡(luò)模型和非均勻概率洪泛算法的結(jié)合，可顯示出優(yōu)異的性能。由于普通節(jié)點使用重傳的概率非常小，所以它可以顯著的減少轉(zhuǎn)播和碰撞量。優(yōu)異的網(wǎng)絡(luò)覆蓋范圍，對純洪泛算法而言，它是一個非常好的替代者。小跳數(shù)可以使小世界模型能夠適應(yīng)低延時的要求，如語音通信。雖然我們不得不消耗更多的收發(fā)器和無線信道，但是相對于上述它的價值來說，尤其是對于無線多跳網(wǎng)絡(luò)中省電這個重要目標來說是非常有價值的。