基于小世界圖無線多跳網絡的研究

王雪冰

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

關鍵詞：小世界圖 無線多跳網絡 概率泛洪

一、引言

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

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

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

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

二、建立小世界無線網絡

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

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

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

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

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

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

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

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

1、網格網絡案例

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

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

2、隨機網絡案例

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

=NπR2S-1

（1）

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

（1）覆蓋效益

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

（2）功耗效益

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

PrPt=GtGrλ4πd2

（2）

（3）多跳效益

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

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

四、結論

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