張康榮 林基明 鄭 霖

（桂林電子科技大學(xué)信息與通信工程學(xué)院 桂林 541004）

1 引言

在應(yīng)急的移動(dòng)多跳無線網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)可能有幾個(gè)相鄰節(jié)點(diǎn)［1］。網(wǎng)絡(luò)中的節(jié)點(diǎn)必須通過允許并發(fā)傳輸和調(diào)整傳輸功率來決定最優(yōu)的通信鏈路。而選擇用于建立鏈路的鄰居節(jié)點(diǎn)子集則是多跳網(wǎng)絡(luò)拓?fù)淇刂频闹饕繕?biāo)［2～3］。

已有文獻(xiàn)基于同時(shí)滿足最優(yōu)傳輸范圍和減少干擾對(duì)多跳網(wǎng)絡(luò)的拓?fù)淇刂七M(jìn)行了研究。研究成果表明較低傳輸功率的移動(dòng)節(jié)點(diǎn)將導(dǎo)致網(wǎng)絡(luò)被分割，而較高傳輸功率的移動(dòng)節(jié)點(diǎn)又通常會(huì)引起通信干擾，影響整體網(wǎng)絡(luò)容量［4～5］。因此需要對(duì)移動(dòng)節(jié)點(diǎn)的拓?fù)溥B接進(jìn)行必要控制。目前在拓?fù)淇刂浦械拇蠖鄶?shù)研究都沒有考慮到節(jié)點(diǎn)遷移，而是使用了一個(gè)用于網(wǎng)絡(luò)分析的靜態(tài)拓?fù)淠Ｐ停?］。

文獻(xiàn)［7］中提出了一種基于方向信息的多跳無線網(wǎng)絡(luò)的分布式拓?fù)淇刂扑惴?。該算法基于相鄰?jié)點(diǎn)進(jìn)行了傳輸功率的優(yōu)化控制，降低了干擾，提高了可靠性。但是該算法并沒有解決網(wǎng)絡(luò)拓?fù)淇刂频膯栴}。文獻(xiàn)［8］針對(duì)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)根據(jù)局部鄰域和信道傳播模型信息計(jì)算出了強(qiáng)連通的拓?fù)?。文獻(xiàn)［9］對(duì)靜態(tài)網(wǎng)絡(luò)拓?fù)淇刂扑惴ㄟM(jìn)行了改進(jìn)，使其能夠適應(yīng)移動(dòng)。文獻(xiàn)［10］提出了鏈接信息無拓?fù)洌↙INT），LINT算法利用節(jié)點(diǎn)度信息自適應(yīng)地調(diào)整傳輸范圍，保持了靜態(tài)網(wǎng)絡(luò)中的連通性和雙連接性，但是該算法不能有效對(duì)節(jié)點(diǎn)的傳輸功率進(jìn)行調(diào)節(jié)。

基于上述問題，本文提出一個(gè)提高應(yīng)急多跳無線網(wǎng)絡(luò)的接入移動(dòng)節(jié)點(diǎn)的能力的方法。首先針對(duì)節(jié)點(diǎn)遷移導(dǎo)致網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化的問題，通過利用非隨機(jī)移動(dòng)模式，使得每個(gè)節(jié)點(diǎn)都可以預(yù)測(cè)鄰域拓?fù)涞奈磥頎顟B(tài)，從而達(dá)到每個(gè)鄰居所需的最小傳輸能力。其次基于單跳鄰居的估計(jì)最小功率信息的最優(yōu)傳輸功率選擇產(chǎn)生具有較強(qiáng)抗干擾性能的網(wǎng)絡(luò)拓?fù)?。這種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是通過多跳通信保持連通性并因此保持網(wǎng)絡(luò)的整體覆蓋區(qū)域的拓?fù)浣Y(jié)構(gòu)。最后通過仿真測(cè)試對(duì)所提出的算法在保持有效傳輸功率的同時(shí)是否能夠可靠保持移動(dòng)節(jié)點(diǎn)的連通性進(jìn)行驗(yàn)證。

2 基于移動(dòng)節(jié)點(diǎn)感知的拓?fù)淇刂扑悸?/h2>

基于移動(dòng)節(jié)點(diǎn)感知的拓?fù)淇刂扑惴ǚ譃閮蓚€(gè)步驟。首先，每個(gè)節(jié)點(diǎn)通過最大傳輸功率（Pmax）發(fā)送HELLO數(shù)據(jù)包，以了解鄰居拓?fù)涞奈磥頎顟B(tài)。信息包包含節(jié)點(diǎn)的預(yù)測(cè)位置，以及在稍后的某個(gè)時(shí)間點(diǎn)與它的單跳鄰居通信所需的最小傳輸能力列表［11～12］。其次，每個(gè)節(jié)點(diǎn)選擇一個(gè)最優(yōu)的功率級(jí)（Poptimal），這樣就可以通過一個(gè)要求更低的傳輸功率級(jí)來達(dá)到要求更高的傳輸功率的鄰居［13～14］。

算法主要思路如圖1所示。

圖1 拓?fù)淇刂扑惴ㄖ饕^程

在圖1（a）中，描繪了在某個(gè)任意時(shí)刻（t0）的初始拓?fù)浣Y(jié)構(gòu)。此時(shí)HELLO數(shù)據(jù)包以最大的發(fā)射功率在鄰居之間交換。圖1（b）顯示了節(jié)點(diǎn)在時(shí)間（t0+α）的預(yù)測(cè)未來位置。節(jié)點(diǎn)5、4、3和2可以直接相互到達(dá)。圖1（c）表示了傳輸功率調(diào)整后的拓?fù)浣Y(jié)構(gòu)。其中每個(gè)節(jié)點(diǎn)調(diào)整了到達(dá)其鄰居所需的功率，以保持其連通性。例如，節(jié)點(diǎn)2計(jì)算節(jié)點(diǎn)5、4、3和1所需的功率，并依據(jù)計(jì)算結(jié)構(gòu)建立了與節(jié)點(diǎn)3和1的鏈路。

3 拓?fù)淇刂坪妥顑?yōu)功率算法

3.1 拓?fù)漕A(yù)測(cè)和傳輸功率計(jì)算

在t0時(shí)刻，每個(gè)節(jié)點(diǎn)計(jì)算在t0+α?xí)r刻到達(dá)下一跳鄰居所需的最小傳輸功率的列表。t0和t0+α分別表示當(dāng)前時(shí)間和下一跳時(shí)間，其中α是以s為單位的單位時(shí)間增量。下面對(duì)最小傳輸功率列表的計(jì)算方法進(jìn)行闡述。

一個(gè)節(jié)點(diǎn)用以下兩個(gè)方程來基于當(dāng)前位置、速度和方向預(yù)測(cè)其的未來位置：

其中（x(t0+α)，y(t0+α)）表示一個(gè)節(jié)點(diǎn)在 t0+α?xí)r刻的位置，s是以某個(gè)最大值為界的當(dāng)前速度，θ是節(jié)點(diǎn)的移動(dòng)方向。

接下來，使用式（3）計(jì)算其與下一跳鄰居在t0+α?xí)r刻的距離。假設(shè)有兩個(gè)相鄰節(jié)點(diǎn)，即節(jié)點(diǎn)A和節(jié)點(diǎn)B，則：

最后，我們可以利用雙射線地面路徑損耗模型來預(yù)測(cè)基于無線傳播模型的任意兩個(gè)節(jié)點(diǎn)間隔距離上的平均信號(hào)強(qiáng)度Pr：

假設(shè)發(fā)射功率Pt和節(jié)點(diǎn)A、節(jié)點(diǎn)B之間的預(yù)測(cè)距離d( )t0+αAB是已知的，則使用式（4）可以計(jì)算出節(jié)點(diǎn)A與節(jié)點(diǎn)B之間的所需的最小傳輸功率。

3.2 最佳功率選擇

在接收HELLO數(shù)據(jù)包時(shí)，每個(gè)節(jié)點(diǎn)對(duì)拓?fù)溆成溥M(jìn)行預(yù)測(cè)，以確定與下一跳鄰居進(jìn)行連接所需的最小傳輸功率。每個(gè)節(jié)點(diǎn)通過維護(hù)兩個(gè)數(shù)據(jù)結(jié)構(gòu)來構(gòu)造這個(gè)拓?fù)溆成洌?）局部視圖列表L包含兩個(gè)字段：下一跳鄰居的標(biāo)識(shí)和最小的功率；2）擴(kuò)展視圖列表E包括下一跳鄰居的標(biāo)識(shí)、下兩跳鄰居的標(biāo)識(shí)和估計(jì)的傳輸功率［15～16］。

算法利用局部視圖和擴(kuò)展視圖列表，選擇了一個(gè)最優(yōu)的功率Poptimal，這樣就可以通過一個(gè)中間鄰居節(jié)點(diǎn)來達(dá)到要求更高傳輸功率的鄰居。通過比較節(jié)點(diǎn)自身的傳輸功率和最近鄰的傳輸功率，實(shí)現(xiàn)了對(duì)Poptimal的選擇。如果最近的鄰居不覆蓋遠(yuǎn)處的鄰居，算法會(huì)搜索另一個(gè)具有較高傳輸能力的鄰居，這樣所有鄰居之間的連通性就會(huì)被保留。尋找最優(yōu)功率的算法流程如圖2所示。

圖2 最優(yōu)功率算法

一個(gè)基于最大傳輸功率的拓?fù)湟约盎谒岢龅淖顑?yōu)功率選擇算法構(gòu)建的傳輸拓?fù)渚W(wǎng)絡(luò)的示例如圖3所示。

圖3 最優(yōu)功率算法的效果

圖3中示例中基于二維地面反射模型在512×512m2區(qū)域上均勻分布的25個(gè)節(jié)點(diǎn)。圖3（a）描述了最大功率（18dBm）的拓?fù)浣Y(jié)構(gòu)，其近似傳輸距離為170m，即在沒有拓?fù)淇刂频那闆r下，每個(gè)節(jié)點(diǎn)的鄰居密度平均為8.08。圖3（b）是基于最優(yōu)功率構(gòu)建的拓?fù)淇刂凭W(wǎng)絡(luò)，其平均傳輸功率為12.07dBm，平均鄰域密度為4.88，因此在保持網(wǎng)絡(luò)連通性的前提下，該拓?fù)渚哂休^低的局部鄰域密度和傳輸功率。顯然，圖2（b）所示拓?fù)渚W(wǎng)絡(luò)中的節(jié)點(diǎn)需要更少的傳輸功率。

4 仿真驗(yàn)證

使用網(wǎng)絡(luò)模擬器NS2實(shí)現(xiàn)本文上述算法，并將本文算法與純洪泛算法（無發(fā)射功率控制）和局部信息無拓?fù)渌惴ǎ↙INT）進(jìn)行比較。

洪水算法使用默認(rèn)的傳輸功率級(jí)（即24.5 dBm）。另一方面，在節(jié)點(diǎn)度的基礎(chǔ)上進(jìn)行傳輸功率調(diào)整。如果鄰居的數(shù)量少于6個(gè)，我們就會(huì)在全功率下運(yùn)行LINT算法，隨著節(jié)點(diǎn)度的增加逐漸減少傳輸功率。移動(dòng)節(jié)點(diǎn)被設(shè)置為有6個(gè)功率級(jí)，分別為 24dBm、21dBm、18dBm、13dBm、7dBm和-3dBm，這些功率級(jí)分別對(duì)應(yīng)250m、210m、170m、130m、90m和50m的傳輸距離。表1總結(jié)了NS2中使用的所有參數(shù)的值。

表1 網(wǎng)絡(luò)模擬器NS2的參數(shù)設(shè)置

利用兩種非隨機(jī)網(wǎng)絡(luò)遷移模型，即確定性和半確定性的移動(dòng)模型。1）在確定性遷移模型中，節(jié)點(diǎn)運(yùn)動(dòng)的偏差設(shè)置為零。2）在半確定移動(dòng)模型中，偏差從-15°變化到+15°，因此節(jié)點(diǎn)運(yùn)動(dòng)在30°的柱狀寬度上變化。基于對(duì)CMU版本的NS2程序的修改，以生成仿真實(shí)驗(yàn)的模擬場(chǎng)景。

4.1 仿真環(huán)境

在仿真模型中，節(jié)點(diǎn)被隨機(jī)放置在1000×1000m2的網(wǎng)格中。所有節(jié)點(diǎn)從1m/s移動(dòng)到最大速度為20m/s，暫停時(shí)間設(shè)置為0。整個(gè)模擬持續(xù)時(shí)間為300s。在仿真實(shí)驗(yàn)中，網(wǎng)絡(luò)大小從50個(gè)增加到150個(gè)，每增加25個(gè)節(jié)點(diǎn)。在性能評(píng)估中使用了以下指標(biāo)：1）平均開銷，定義為每個(gè)節(jié)點(diǎn)每個(gè)數(shù)據(jù)傳輸接收的數(shù)據(jù)包的數(shù)量。2）平均傳輸功率，為總傳輸功率與網(wǎng)絡(luò)大小之比，其中，HELLO數(shù)據(jù)包僅包含在本文算法和LINT中。3）延遲，是指從源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)和預(yù)期目的地接收到的數(shù)據(jù)之間的時(shí)間。

4.2 仿真結(jié)果

首先對(duì)網(wǎng)絡(luò)中廣播數(shù)據(jù)包的開銷進(jìn)行監(jiān)測(cè)。圖4（a）和（b）分別繪制了每個(gè)節(jié)點(diǎn)傳輸?shù)钠骄_銷，并將節(jié)點(diǎn)的總數(shù)量作為確定的和半確定性移動(dòng)模型的網(wǎng)絡(luò)大小的函數(shù)。其中圖4（a）是移動(dòng)模型下的不同節(jié)點(diǎn)數(shù)量的無線網(wǎng)絡(luò)的廣播數(shù)據(jù)包的平均開銷；圖4（b）則是半移動(dòng)模型下的平均開銷。

圖4 節(jié)點(diǎn)廣播的平均開銷對(duì)比

由圖4可知，本文算法的平均開銷始終低于基本算法和LINT算法。如前一節(jié)所述，應(yīng)用拓?fù)淇刂频男Ч@著降低了局部節(jié)點(diǎn)的平均密度，從而減少了相鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包的結(jié)果。這也有助于降低節(jié)點(diǎn)傳輸?shù)墓β剩驗(yàn)樗ǔ?huì)轉(zhuǎn)發(fā)較少數(shù)量的中間節(jié)點(diǎn)的包。LINT算法也是利用傳輸功率優(yōu)化調(diào)整實(shí)現(xiàn)多跳無線網(wǎng)絡(luò)的拓?fù)淇刂?，但是該算法只要監(jiān)測(cè)到網(wǎng)絡(luò)連接性變差，節(jié)點(diǎn)就會(huì)轉(zhuǎn)向最大功率傳輸模式。因此兩種移動(dòng)模型的開銷在較大規(guī)模的無線網(wǎng)絡(luò)中是接近的。

圖5（a）和（b）表示兩種移動(dòng)模型的平均傳輸功率。其中圖5（a）是移動(dòng)模型下的不同節(jié)點(diǎn)數(shù)量的無線網(wǎng)絡(luò)在保持節(jié)點(diǎn)連通性前提下的平均傳輸功率；圖5（b）則是半移動(dòng)模型下的平均傳輸功率。

圖5 節(jié)點(diǎn)平均傳輸功率的對(duì)比

圖6 節(jié)點(diǎn)平均延時(shí)的對(duì)比

由圖5可知，本文所提出的算法能夠以最小的功率保持與在傳輸范圍邊界上的節(jié)點(diǎn)的連通性，而LINT在這種情況下運(yùn)行在更高的傳輸功率級(jí)。對(duì)于較小的網(wǎng)絡(luò)，LINT必須增加一些孤立節(jié)點(diǎn)的能力。半確定性移動(dòng)模型的功耗比確定性模型要高，這是為了補(bǔ)償相鄰節(jié)點(diǎn)的有限偏差。

圖6（a）和（b）為本文算法和其他算法分別在移動(dòng)模型和半移動(dòng)模型下的平均延遲。

由圖6可知，兩種移動(dòng)模型的延時(shí)在所有的算法中都是相似的，并且在節(jié)點(diǎn)數(shù)量較少的網(wǎng)絡(luò)中本文算法的延時(shí)相對(duì)較高。在網(wǎng)絡(luò)密集的情況下，所有算法的延遲時(shí)間都相對(duì)較高。而在適度的流量負(fù)載下，非拓?fù)淇刂凭W(wǎng)絡(luò)的延時(shí)相對(duì)較低，因?yàn)榕c拓?fù)淇刂频木W(wǎng)絡(luò)相比，在網(wǎng)絡(luò)中傳播數(shù)據(jù)包需要較少的跳數(shù)。

5 結(jié)語

本文提出了一種新的基于移動(dòng)節(jié)點(diǎn)的拓?fù)淇刂扑惴?。我們的方案利用非隨機(jī)節(jié)點(diǎn)移動(dòng)模式來預(yù)測(cè)網(wǎng)絡(luò)拓?fù)涞奈磥頎顟B(tài)。每個(gè)節(jié)點(diǎn)都運(yùn)行一個(gè)分布式算法來估計(jì)成功地與每個(gè)鄰居進(jìn)行通信所需的最小功耗。最后，節(jié)點(diǎn)將其傳輸功率調(diào)整到最優(yōu)級(jí)以實(shí)現(xiàn)魯棒拓?fù)?。仿真結(jié)果表明，本文算法支持節(jié)點(diǎn)間的多跳通信，以有效地利用有限的系統(tǒng)資源，如動(dòng)態(tài)無線環(huán)境中的功率和帶寬。此外，由于我們的協(xié)議運(yùn)行在一組離散的功率級(jí)別上，因此位置信息不需要非常精確。本文算法的基礎(chǔ)是一個(gè)單跳的HELLO數(shù)據(jù)包，因此網(wǎng)絡(luò)中的節(jié)點(diǎn)必須定期發(fā)送附加的鄰居信息的數(shù)據(jù)包，這對(duì)網(wǎng)絡(luò)負(fù)載會(huì)產(chǎn)生一定影響。