基于概率洪泛算法的異構(gòu)無線自組網(wǎng)研究

劉 穎

（中國石油大學(xué)勝利學(xué)院 信息與計(jì)算科學(xué)系，山東 東營257000）

自組網(wǎng)又稱Ad hoc網(wǎng)，由一組配備無線收發(fā)器的節(jié)點(diǎn)組成，節(jié)點(diǎn)可以通過無線信道互相通信。在整個(gè)自組網(wǎng)中，不存在固定的基礎(chǔ)設(shè)施，節(jié)點(diǎn)通過分散的、自組織的方式獨(dú)立于其他節(jié)點(diǎn)，并以任意方式保持節(jié)點(diǎn)間的相互聯(lián)系。每個(gè)節(jié)點(diǎn)充當(dāng)路由器將網(wǎng)絡(luò)中的數(shù)據(jù)包轉(zhuǎn)發(fā)到目的地。在典型的自組網(wǎng)中網(wǎng)絡(luò)架構(gòu)是均勻的，即網(wǎng)絡(luò)中的所有節(jié)點(diǎn)具有相同的廣播覆蓋范圍和平等的地位，稱為同構(gòu)體系結(jié)構(gòu)。在網(wǎng)絡(luò)模型中各節(jié)點(diǎn)通信范圍互不相同的結(jié)構(gòu)被稱為異構(gòu)體系結(jié)構(gòu)。在同構(gòu)自組網(wǎng)中平均路徑長度較大、聚類系數(shù)較低，導(dǎo)致網(wǎng)絡(luò)中大量的跳躍計(jì)數(shù)、端到端的較長延遲和大量的電力消耗等問題。針對這些問題，筆者設(shè)計(jì)基于異構(gòu)網(wǎng)絡(luò)體系結(jié)構(gòu)的概率洪泛算法。該算法不僅能用于獨(dú)立的信息傳播技術(shù)，也可作為輔助工具用于其他路由算法，來進(jìn)行路由發(fā)現(xiàn)和路由維護(hù)，利用該算法可以大大地減少信道爭用和沖突。由于在該算法中網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間傳輸概率并不是均勻分配的，所以將其稱為不均勻概率洪泛算法。將這種不均勻概率洪泛算法應(yīng)用于異構(gòu)網(wǎng)絡(luò)，會使網(wǎng)絡(luò)性能得到較大的提高。

1 異構(gòu)網(wǎng)絡(luò)的架構(gòu)

在自組網(wǎng)中存在很多重要性能指標(biāo)，如覆蓋范圍、連通性、移動性等，平均路徑長度和聚類系數(shù)是其中兩個(gè)非常重要的特征度量。

平均路徑長度是網(wǎng)絡(luò)中所有節(jié)點(diǎn)對之間的平均最短距離。在自組網(wǎng)絡(luò)中，平均路徑長度L為所有節(jié)點(diǎn)間最短路徑長度的算術(shù)平均值，即

式中，dji為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最短路徑；N為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量。

平均路徑長度L描述了網(wǎng)絡(luò)規(guī)模，是網(wǎng)絡(luò)中任意兩點(diǎn)間最短路徑長度的平均值。平均路徑長度越短，端到端流量包的傳輸延遲和代價(jià)也就越小，它是衡量網(wǎng)絡(luò)轉(zhuǎn)發(fā)能力的重要參數(shù)。

聚類系數(shù)描述了網(wǎng)絡(luò)節(jié)點(diǎn)的聚類效果。一個(gè)節(jié)點(diǎn)i的聚類系數(shù)，被定義為節(jié)點(diǎn)i的所有鄰界邊數(shù)除以它們之間可能存在的最大邊緣數(shù)，即：

式中，Ei為節(jié)點(diǎn)i與相鄰節(jié)點(diǎn)間存在的邊緣的數(shù)量；ki為相鄰節(jié)點(diǎn)數(shù)。

整個(gè)網(wǎng)絡(luò)的聚類系數(shù)定義為平均值Ci，是節(jié)點(diǎn)中兩個(gè)任意臨界節(jié)點(diǎn)仍互為鄰居的平均概率，應(yīng)滿足基本條件0≤C≤1。一個(gè)完整的隨機(jī)圖，如E-R圖［1］的聚類系數(shù)C＝O（N-1），但在實(shí)際網(wǎng)絡(luò)中聚類系數(shù)的值會更大。

通常在一個(gè)典型的自組網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都配備有一對收發(fā)器，其發(fā)射功率和通信范圍相同，這種同構(gòu)網(wǎng)絡(luò)架構(gòu)可以被建模為隨機(jī)幾何圖［2］。在該模式中，只要節(jié)點(diǎn)間的距離小于通信覆蓋范圍就可以互相溝通，這取決于收發(fā)器的發(fā)射功率。

在異構(gòu)模式中，隨機(jī)挑選一些節(jié)點(diǎn)，為其配備其他節(jié)點(diǎn)兩倍通信距離遠(yuǎn)的發(fā)射器。為區(qū)別于普通節(jié)點(diǎn)，這些節(jié)點(diǎn)被稱為特殊節(jié)點(diǎn)。為了檢測特殊節(jié)點(diǎn)的設(shè)置對網(wǎng)絡(luò)性能的影響，將其中一小部分節(jié)點(diǎn)作為特殊節(jié)點(diǎn)進(jìn)行仿真試驗(yàn)。

仿真設(shè)置：將400個(gè)節(jié)點(diǎn)布置于平面上，以形成陣列的20行和20列中的數(shù)組。每個(gè)普通節(jié)點(diǎn)的通信范圍要保證它最多有4個(gè)鄰接節(jié)點(diǎn)。一個(gè)特殊節(jié)點(diǎn)的通信范圍被設(shè)定為一個(gè)普通節(jié)點(diǎn)的兩倍，因此，每個(gè)特殊節(jié)點(diǎn)將有8個(gè)鄰接節(jié)點(diǎn)。在開始時(shí)，沒有設(shè)置特殊的節(jié)點(diǎn)，此時(shí)形成的是一個(gè)同構(gòu)網(wǎng)絡(luò)（圖1（a）），將特殊節(jié)點(diǎn)逐個(gè)添加（圖1（b）），直到所有節(jié)點(diǎn)成為特殊節(jié)點(diǎn)（圖1（c））。當(dāng)所有的節(jié)點(diǎn)都成為特殊節(jié)點(diǎn)時(shí)，此時(shí)的網(wǎng)絡(luò)再次變成了同構(gòu)網(wǎng)絡(luò)。

圖1 仿真節(jié)點(diǎn)的設(shè)置

平均路徑長度和聚類系數(shù)隨特殊節(jié)點(diǎn)數(shù)量的變化見圖2和圖3。在網(wǎng)絡(luò)中特殊節(jié)點(diǎn)從0增加到80的過程中，統(tǒng)計(jì)的數(shù)據(jù)顯示平均路徑長度和聚類系數(shù)發(fā)生了明顯的改善。而從特殊節(jié)點(diǎn)80個(gè)開始，進(jìn)一步增加特殊節(jié)點(diǎn)也不再帶來進(jìn)一步的改善。借助物理術(shù)語，這種現(xiàn)象稱為相變［3］。相變現(xiàn)象表明，只有在網(wǎng)絡(luò)中將特殊節(jié)點(diǎn)設(shè)定在總節(jié)點(diǎn)20%（80個(gè)）的范圍內(nèi)，才能夠起到減少平均路徑長度和增加聚類系數(shù)的效果。該試驗(yàn)的過程是實(shí)現(xiàn)在網(wǎng)格網(wǎng)絡(luò)上，在隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)模型中可得到相同的結(jié)論。

圖2 異構(gòu)網(wǎng)絡(luò)模型的平均路徑長度

圖3 異構(gòu)網(wǎng)絡(luò)模型的聚類系數(shù)

2 不均勻概率洪泛算法

概率洪泛算法由約阿夫薩森［4］最早提出，被證明是存在于自組網(wǎng)絡(luò)中的一種有效的信息傳播技術(shù)。傳統(tǒng)的洪泛算法要求移動廣播消息要盡可能快地到達(dá)目的地，但這種方式將會產(chǎn)生大量數(shù)據(jù)包的碰撞。在傳統(tǒng)洪泛方法中將節(jié)點(diǎn)接收到廣播消息的概率值設(shè)置為1，而在概率洪泛算法策略中節(jié)點(diǎn)接收到廣播消息的概率為0＜P＜1。根據(jù)滲流理論，當(dāng)P增加時(shí)，數(shù)據(jù)包傳送率將經(jīng)歷一個(gè)從0到1的突然過渡。這就是說，會存在一個(gè)臨界值Pc，當(dāng)洪泛概率超過該值時(shí)，傳播的速度將不會再有明顯提高。

接下來將針對異構(gòu)網(wǎng)絡(luò)模型設(shè)計(jì)一個(gè)新的概率洪泛算法。在異構(gòu)模型中，為每個(gè)節(jié)點(diǎn)配置一個(gè)發(fā)射器和兩個(gè)接收器。有兩個(gè)傳輸?shù)念l帶可覆蓋整個(gè)網(wǎng)絡(luò)，為特殊節(jié)點(diǎn)配置一種發(fā)射器，針對其他普通節(jié)點(diǎn)配置一種發(fā)射器。所有節(jié)點(diǎn)都可以接收和處理兩個(gè)頻帶的信號。將特殊節(jié)點(diǎn)的發(fā)射機(jī)的功率設(shè)置為普通節(jié)點(diǎn)通信距離的2倍，同時(shí)賦予給特殊節(jié)點(diǎn)比普通節(jié)點(diǎn)大的傳輸概率，因此這種算法被稱為不均勻概率洪泛算法。為將一般的概率洪泛算法的性能與不均勻概率洪泛算法進(jìn)行比較，在進(jìn)行仿真的試驗(yàn)過程中，利用OPNET軟件來模擬網(wǎng)絡(luò)仿真環(huán)境。

首先，進(jìn)行架構(gòu)在同構(gòu)網(wǎng)絡(luò)基礎(chǔ)上的普通概率洪泛算法仿真試驗(yàn)，在平面尺寸為2 000m×2 000 m的范圍上隨機(jī)設(shè)置400個(gè)節(jié)點(diǎn)，將節(jié)點(diǎn)的通信半徑設(shè)定為200m。區(qū)域中心（1 000，1 000）附近的一個(gè)節(jié)點(diǎn)被選定為廣播源點(diǎn)而其他節(jié)點(diǎn)作為目的地。在仿真試驗(yàn)中，傳輸概率從0到1逐漸增加，對目標(biāo)數(shù)據(jù)進(jìn)行收集。對節(jié)點(diǎn)收到的數(shù)據(jù)包的數(shù)量和跳數(shù)進(jìn)行統(tǒng)計(jì)，用以測試網(wǎng)絡(luò)的覆蓋區(qū)域和平均路徑長度。

其次，進(jìn)行架構(gòu)在異構(gòu)網(wǎng)絡(luò)基礎(chǔ)上的不均勻概率洪泛算法的仿真設(shè)置，在本次仿真試驗(yàn)中，共設(shè)置了80個(gè)特殊節(jié)點(diǎn)，占總結(jié)點(diǎn)數(shù)的20%。將特殊節(jié)點(diǎn)的通信范圍設(shè)定為300m，而將普通節(jié)點(diǎn)的通信范圍設(shè)置為150m，仿真試驗(yàn)結(jié)果見圖4和圖5。

圖4 數(shù)據(jù)包投遞率的比較

圖5 跳數(shù)的比較

對試驗(yàn)結(jié)果進(jìn)行分析。首先，在不均勻概率洪泛算法與異構(gòu)網(wǎng)絡(luò)模型相結(jié)合的仿真試驗(yàn)中，用0.2的傳輸概率獲得了90%的網(wǎng)絡(luò)廣播覆蓋，但架構(gòu)在同構(gòu)網(wǎng)絡(luò)基礎(chǔ)上的普通概率洪泛算法仿真試驗(yàn)則需要超過0.6的傳輸概率才能實(shí)現(xiàn)同樣范圍的廣播覆蓋。其次，前一種模型中的跳數(shù)要遠(yuǎn)遠(yuǎn)小于后者，這就意味著短的傳輸延遲。最后，在異構(gòu)模型中，320個(gè)普通節(jié)點(diǎn)其通信半徑是150m，80個(gè)特殊節(jié)點(diǎn)的通信半徑為300m。而同構(gòu)模型中的所有節(jié)點(diǎn)都是200m的通信距離。通過無線傳輸計(jì)算公式可以得出，在自由空間損耗前者比后者約小13.75%。

試驗(yàn)表明，將不均勻概率洪泛算法與異構(gòu)網(wǎng)絡(luò)模型相結(jié)合，其性能要優(yōu)于架構(gòu)在同構(gòu)網(wǎng)絡(luò)基礎(chǔ)上的普通概率洪泛算法。

3 結(jié)束語

基于概率洪泛算法的異構(gòu)網(wǎng)絡(luò)模型的明顯優(yōu)點(diǎn)主要體現(xiàn)在平均路徑長度和聚類系數(shù)這兩項(xiàng)主要指標(biāo)上，另外在成本比較上其耗電量只有傳統(tǒng)網(wǎng)絡(luò)的20%，能減少廣播碰撞，實(shí)現(xiàn)短的傳輸延遲，并減少功率消耗。這種新算法的實(shí)現(xiàn)簡單，易于實(shí)現(xiàn)低成本的控制，同時(shí)應(yīng)該指出的是，由于特殊節(jié)點(diǎn)的存在，需為特殊節(jié)點(diǎn)配備專用發(fā)射功率的收發(fā)器。

［1］BOLLOBAS B.Random graphs［M］.Cambridge：Cambridge U-niversity Press，2001：143-147.

［2］PENROSE M.Random geometric graphs［M］.Oxford：Oxford University Press，2003：22-45.

［3］KRISHNAMACHARI B，WICKER S B ，BEJAR R.Phase transition phenomena in wireless Ad hoc networks［J］.Global Telecommunications Conference，2001（5）：2921-2925.

［4］SASSON Y，CAVIN D，SCHIPER A.Probabilistic broadcast for flooding in wireless mobile Ad hoc networks［J］.2003IEEE Wireless Communications and Networking Conference Record（Cat No 03TH8659），2003（2）：1124-1130.