陳友榮，任條娟，劉半藤，葛靈曉

(浙江樹人大學信息科技學院，杭州 310015)

無線傳感網(wǎng)通常有一個重要目標——延長網(wǎng)絡(luò)生存時間。由于大部分情況下所有節(jié)點的能量有限，不能補充和更換，一旦節(jié)點能量耗盡，該節(jié)點就會失效，這將影響到網(wǎng)絡(luò)的運行，甚至可能導致網(wǎng)絡(luò)的癱瘓，因此延長網(wǎng)絡(luò)生存時間可以節(jié)省重新部署無線傳感網(wǎng)的巨大開銷［1］。

目前，無線傳感網(wǎng)路由的研究已取得一些成果。文獻［2－3］用分布式的線性規(guī)劃公式表示路由問題，采用對偶分解和次梯度方法求解最優(yōu)路由方案，最大限度提高網(wǎng)絡(luò)生存時間，但是用最優(yōu)化方法研究路由方案的算法復雜，很難在實際硬件環(huán)境中實現(xiàn)。文獻［4］提出LET(Least Energy Tree)算法。它是根據(jù)dijkstra算法構(gòu)建每個節(jié)點到Sink節(jié)點能耗最小的最短路徑樹，最終所有節(jié)點沿著最短路徑樹將數(shù)據(jù)發(fā)送給Sink節(jié)點。文獻［5］在LET算法的基礎(chǔ)上提出了“比例權(quán)值路由算法”Ratio_w(Ratio Weight Routing Algorithm)與“和權(quán)值路由算法”Sum_w(Sum Weight Routing Algorithm)。文獻［6］提出多樹路由，在數(shù)據(jù)發(fā)送過程中從多個樹路徑中選擇當前合適的路徑，最終平衡節(jié)點能耗，提高網(wǎng)絡(luò)生存時間。上述路由算法都假設(shè)Sink節(jié)點能獲得整個網(wǎng)絡(luò)拓撲信息或者節(jié)點能獲知與鄰居節(jié)點的距離，而且節(jié)點可根據(jù)與鄰居節(jié)點的距離自動調(diào)整發(fā)送功率，從而減少鏈路能耗。如果Sink節(jié)點要得到整個網(wǎng)絡(luò)拓撲信息或者節(jié)點要獲知與鄰居節(jié)點的距離，可通過以下兩種方法實現(xiàn)。第1種方法是添加額外硬件模塊，如配置GPS模塊收集每個節(jié)點的位置坐標，或者采用超聲波、紅外等模塊測量節(jié)點間距離，通過定位方法計算每個節(jié)點的位置坐標。第2種方法是不需要添加額外的硬件模塊，根據(jù)節(jié)點間通信的RSSI值，估計兩個節(jié)點的距離，通過3邊定位等定位算法獲得網(wǎng)絡(luò)節(jié)點位置坐標。第1種方法需要添加額外硬件，增加了無線傳感網(wǎng)的硬件成本。第2種方法在實際環(huán)境中，尤其是在惡劣環(huán)境中，RSSI的測量誤差非常大，很難準確測量兩個節(jié)點間距離。

考慮到通過兩節(jié)點間距離(即通信距離)調(diào)整節(jié)點發(fā)送功率不總是可行的，尤其當節(jié)點不增加無線傳感網(wǎng)硬件成本而且節(jié)點很難獲知與鄰居節(jié)點的距離時，針對此類網(wǎng)絡(luò)樞紐節(jié)點能量消耗過快而過早失效，從而減少網(wǎng)絡(luò)生存時間的問題，提出基于最短路徑樹的分布式功率控制路由算法DPCRA_SPT(Distributed Power Control Routing Algorithm Based on Shortest Path Tree)。當節(jié)點很難獲知節(jié)點到鄰居節(jié)點的距離時，該算法隨著節(jié)點剩余能量的減少而自動調(diào)整節(jié)點發(fā)送功率，從而調(diào)整整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。DPCRA_SPT算法還綜合考慮網(wǎng)絡(luò)中傳輸數(shù)據(jù)的能耗、鄰居節(jié)點的剩余能量，引入分布式算法的權(quán)值函數(shù)。每個節(jié)點利用分布式非同步Bellman-Ford算法構(gòu)建最短路徑樹。最終，數(shù)據(jù)沿著當前網(wǎng)絡(luò)拓撲結(jié)構(gòu)下的最短路徑樹匯聚到Sink節(jié)點。

1 系統(tǒng)假設(shè)

在DPCRA_SPT算法中，假定傳感節(jié)點(簡稱節(jié)點)隨機分布在一個正方形區(qū)域內(nèi)，周期性地采集周圍環(huán)境信息，并假設(shè)如下:

(1)Sink節(jié)點和所有傳感節(jié)點位置固定不變，都是靜止的，而且Sink節(jié)點不能獲知整個網(wǎng)絡(luò)拓撲結(jié)構(gòu)信息；

(2)所有傳感節(jié)點具有相同的性能(如初始能量、能耗參數(shù)、無線電最大發(fā)送功率、最大通信半徑等)；

(3)所有傳感節(jié)點采用統(tǒng)一的能量模型；

(4)所有傳感節(jié)點都能感知數(shù)據(jù)，并通過直接或多跳的方式將數(shù)據(jù)發(fā)送給Sink節(jié)點；

(5)每個傳感節(jié)點能量受限，但Sink節(jié)點能量不受限制；

(6)所有傳感節(jié)點沒有安裝GPS等模塊，無法獲知自身的位置坐標，也無法獲知節(jié)點到鄰居節(jié)點的距離。

2 鏈路能耗模型

常見的鏈路傳輸模型是根據(jù)發(fā)送節(jié)點與接收節(jié)點之間距離的Friss自由空間模型和多徑衰弱模型。如果發(fā)送節(jié)點與接收節(jié)點之間的距離小于交叉距離dcrossover，則使用Friss自由空間模型(d2衰減)。如果發(fā)送節(jié)點與接收節(jié)點之間的距離大于或等于交叉距離dcrossover，則使用兩線地面?zhèn)鞑ツＰ?d4衰減)［7］。交叉距離dcrossover的定義如下:

其中Ds≥1，與無線傳播的數(shù)據(jù)丟包率有關(guān)，hr與發(fā)送節(jié)點的天線高度有關(guān)，ht與接收節(jié)點的天線高度有關(guān)，b代表電磁波的波長。采用根據(jù)無線通信能量消耗模型部分參數(shù)如下:全向天線，ht=hr=1.5，系統(tǒng)丟失率Ds=1［7］，而且無線傳感網(wǎng)通常采用2.4GHz的無線信號，b=0.125 m，可得dcrossover=226 m。由于交叉距離已經(jīng)大于一般無線傳感網(wǎng)節(jié)點的通信距離，因此鏈路能耗模型選擇Friss自由空間模型，其發(fā)送功率和通信距離的關(guān)系如下

式中:Pi是發(fā)送節(jié)點i的發(fā)送功率，是接收節(jié)點的最小接收功率，是節(jié)點i選擇發(fā)送功率Pi時的最大通信距離。當節(jié)點i采用最大發(fā)送功率發(fā)送數(shù)據(jù)時，節(jié)點j能接收到該數(shù)據(jù)包，則節(jié)點j是節(jié)點i的鄰居節(jié)點，即j∈N(i)，其中N(i)表示節(jié)點i的所有鄰居節(jié)點集合。

典型的無線傳感網(wǎng)節(jié)點能耗主要由無線數(shù)據(jù)收發(fā)產(chǎn)生［8］。節(jié)點發(fā)送模塊的能耗ETx由發(fā)送電路電子能耗ETx-elec和信號放大器部分的電子能耗ETx-amp組成。節(jié)點發(fā)送模塊能耗中的發(fā)送電路電子能耗ETx-elec和接收模塊中的能耗ERx，固定為gEelec，其中g(shù)代表所發(fā)送或接收的數(shù)據(jù)量。信號放大器部分的電子能耗大小與發(fā)送功率Pi有關(guān)。鏈路能耗模型計算公式改為:

根據(jù)式(3)和式(4)可知:傳感節(jié)點i與節(jié)點j之間傳輸g比特數(shù)據(jù)的能耗取為:

傳感節(jié)點i與Sink節(jié)點之間傳輸g比特數(shù)據(jù)的能耗取為:

3 算法的原理

通常把計算從源節(jié)點到目的節(jié)點的最短路徑權(quán)值稱為單源最短路徑問題。目前，解決單源最短路徑的方法有很多，分布式非同步Bellman-Ford算法是其中的一種實現(xiàn)簡單的分布式算法［9］。

該算法在利用分布式非同步Bellman-Ford算法尋找最短路徑問題前需要解決以下兩個問題。

第1個問題是鏈路權(quán)值的設(shè)定會影響網(wǎng)絡(luò)的生存時間。考慮到DPCRA_SPT算法是分布式算法，每個節(jié)點發(fā)送數(shù)據(jù)前需要根據(jù)周圍局部信息選擇鄰居節(jié)點，但是節(jié)點自身剩余能量不影響鄰居節(jié)點的選擇，因此DPCRA_SPT算法簡化鏈路權(quán)值，只考慮鏈路能耗(式(5)和(6))和鄰居節(jié)點的剩余能量，路由應(yīng)該選擇鄰居節(jié)點剩余能量大而且鏈路能耗小的鄰居節(jié)點發(fā)送數(shù)據(jù)。以Re(i)表示節(jié)點i的剩余能量，以Cij表示鏈路L(i，j)的能耗，以wij表示鏈路L(i，j)的權(quán)值。在DPCRA_SPT算法中，取

其中α是“能耗因子”，β是“接收剩余能量因子”，而且這兩個因子都是正常數(shù)。

第2是如何根據(jù)當前局部信息，調(diào)整節(jié)點發(fā)送功率，從而改變網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，其具體算法見下一節(jié)功率控制算法。

確定節(jié)點的發(fā)送功率后，即網(wǎng)絡(luò)拓撲結(jié)構(gòu)確定，DPCRA_SPT算法采用分布式非同步Bellman-Ford算法找到一顆樹根在Sink節(jié)點的最短路徑樹。所有節(jié)點沿著最短路徑樹，將數(shù)據(jù)傳送到Sink節(jié)點，從而各個節(jié)點均以最小能耗將數(shù)據(jù)發(fā)送到Sink節(jié)點。

3.1 功率控制算法

由于節(jié)點不能獲知與鄰居節(jié)點的距離，但是節(jié)點可獲知自身剩余能耗信息，因此DPCRA_SPT算法根據(jù)節(jié)點剩余能量調(diào)整發(fā)送功率，改變網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，避免該節(jié)點能量過早消耗而死亡。如圖1所示，網(wǎng)絡(luò)剛開始運行時，1號節(jié)點的剩余能量充裕，發(fā)送功率大，它可與實線內(nèi)的所有節(jié)點(2～8號節(jié)點)通信，與其它節(jié)點組成到Sink節(jié)點的數(shù)據(jù)發(fā)送路徑，較多的參與數(shù)據(jù)路由；隨著節(jié)點剩余能量的減少，1號節(jié)點為避免能量過快消耗，減少自身發(fā)送功率，只能與虛線內(nèi)的節(jié)點(2～5號節(jié)點)通信；當1號節(jié)點的發(fā)送功率降到最小要求功率(能與距離最近的2號節(jié)點通信的最低發(fā)送功率)時，不再改變其發(fā)送功率。如果網(wǎng)絡(luò)中樞紐節(jié)點能量消耗過快，該方法減少發(fā)送功率，減少能量消耗，因此能提高網(wǎng)絡(luò)的生存時間［10］。

圖1 發(fā)送功率調(diào)整示意圖

由上述內(nèi)容可知，DPCAOL_SPT算法調(diào)整節(jié)點的發(fā)送功率，改變網(wǎng)絡(luò)拓撲結(jié)構(gòu)，以下給出具體的發(fā)送功率衰減模型。圖2是節(jié)點發(fā)送功率隨著剩余能量變化的線性功率衰減曲線圖。定義［0－1］區(qū)間的兩個參數(shù) γl1和 γl2，如圖 2所示，F(xiàn)點位置是(γl1Emax，γl2(Pmax－Pmin(i))+Pmin(i))，功率衰減曲線主要是經(jīng)過F點的兩條線段組成。每個節(jié)點根據(jù)剩余能量和衰減曲線，改變節(jié)點發(fā)送功率。

圖2 線性功率衰減曲線

從式(8)可知，線性衰減可出現(xiàn)3種情況。當γl1=0時，F(xiàn)點在x=0的縱坐標上，該節(jié)點衰減的曲線是經(jīng)過(Emax，Pmax)和F點的線段。當γl1=1時，F(xiàn)點在x=Emax的縱坐標上，該節(jié)點衰減曲線是經(jīng)過(0，Pmin(i))和F點的線段。當0＜γl1＜1時，該節(jié)點衰減曲線由兩條線段組成，分別是經(jīng)過(Emax，Pmax)和F點的線段和經(jīng)過(0，Pmin(i))和F點的線段。

4 算法的實現(xiàn)

提出的DPCRA_SPT是一種分布式功率控制算法。每個節(jié)點根據(jù)剩余能量調(diào)整發(fā)送功率，接收鄰居節(jié)點信息，采用分布式Bellman-Ford算法找到到Sink節(jié)點的最優(yōu)路徑，具體的實現(xiàn)步驟如下:

第1步 網(wǎng)絡(luò)啟動時，節(jié)點為了獲知與鄰居節(jié)點通信的最低發(fā)送功率，其發(fā)送功率從0 W開始遞增發(fā)送Hello信號。鄰居節(jié)點第一次收到該節(jié)點的Hello數(shù)據(jù)包，則反饋一個Ack包。

第2步 該節(jié)點接收到鄰居節(jié)點的Ack包后，添加該鄰居節(jié)點通信的最低要求功率到節(jié)點鄰居信息表中。

第3步 當節(jié)點將發(fā)送功率遞增到最大發(fā)送功率后，對鄰居節(jié)點發(fā)送路徑預(yù)測信息分組(包括節(jié)點ID，到Sink節(jié)點的最短路徑權(quán)值預(yù)測值Di、節(jié)點剩余能量E(i))。鄰居節(jié)點收到這些信息后添加到鄰居信息表中。

第4步 節(jié)點根據(jù)當前剩余能量，執(zhí)行相應(yīng)的公式計算當前的發(fā)送功率Pi。節(jié)點采用發(fā)送功率Pi發(fā)送數(shù)據(jù)。

第5步 如果發(fā)送功率變換，更新相應(yīng)的鏈路權(quán)值。節(jié)點根據(jù)鄰居信息表中信息，執(zhí)行Bellman-Ford公式計算其最短路徑權(quán)值Dij。如果最短路徑權(quán)值發(fā)生變化，向鄰居節(jié)點發(fā)送路徑預(yù)測信息分組(包括節(jié)點ID，到Sink節(jié)點的最短路徑權(quán)值預(yù)測值Di、節(jié)點剩余能量E(i))。

第6步 根據(jù)鄰居節(jié)點的信息，節(jié)點選擇通信的最低發(fā)送功率小于當前發(fā)送功率且在最小權(quán)值路徑上的鄰居節(jié)點發(fā)送數(shù)據(jù)。

第7步 發(fā)送完若干比特數(shù)據(jù)后，跳到第4步，更新當前的發(fā)送功率。

經(jīng)過上述步驟的循環(huán)，直到網(wǎng)絡(luò)死亡，即出現(xiàn)一個節(jié)點能量耗盡或數(shù)據(jù)不能到達Sink節(jié)點。在實現(xiàn)過程中，節(jié)點不時向其所有鄰居節(jié)點發(fā)送最新預(yù)測信息分組。鄰居節(jié)點獲得信息分組，更新鄰居信息表，執(zhí)行Bellman-Ford公式，選擇最小路徑權(quán)值的節(jié)點發(fā)送數(shù)據(jù)。如果一段時間內(nèi)，沒有接收到鄰居節(jié)點的最新預(yù)測信息分組或發(fā)送數(shù)據(jù)后沒有接收到反饋分組，則認為該鏈路出現(xiàn)故障，在鄰居信息表中刪去該鄰居信息。

節(jié)點i的偽代碼如下:

分析DPCRA_SPT算法的時間復雜性，假設(shè)節(jié)點發(fā)送預(yù)測信息分組的頻率是Hi。考慮最好的情況即所有鄰居節(jié)點Dj不變化，此時它的時間復雜度Θ(N(i))?？紤]最壞的情況，即所有鄰居節(jié)點Dj都變化，每次變化都需要重新計算到Sink節(jié)點的最短路徑權(quán)值，此時它的時間復雜度是Θ(HiN(i))。

5 算法的仿真

5.1 仿真參數(shù)選擇

由于無線傳感網(wǎng)是應(yīng)用相關(guān)的網(wǎng)絡(luò)，即不同的應(yīng)用背景對無線傳感網(wǎng)的要求不同，所以研究者沒有統(tǒng)一網(wǎng)絡(luò)生存時間的度量方法。如果網(wǎng)絡(luò)中一個節(jié)點能量耗盡就會影響到網(wǎng)絡(luò)的正常運行，甚至導致網(wǎng)絡(luò)出現(xiàn)分裂，此時網(wǎng)絡(luò)生存時間的度量方法可定義為網(wǎng)絡(luò)開始運行到任意一個節(jié)點能量耗盡時的這一段時間，也可定義為網(wǎng)絡(luò)開始運行到網(wǎng)絡(luò)中任意一個節(jié)點數(shù)據(jù)不能達到Sink節(jié)點時的這一段時間［11］。它也可以定義為當某個網(wǎng)絡(luò)參數(shù)指標(如生存節(jié)點占總節(jié)點數(shù)量的比例、存活數(shù)據(jù)流占總數(shù)據(jù)流的比例、數(shù)據(jù)包到達率，或覆蓋度等)達到某一預(yù)先設(shè)定的閥值時，判斷網(wǎng)絡(luò)生存時間終止。但是對于不同的應(yīng)用，甚至同一類應(yīng)用的不同實例，網(wǎng)絡(luò)參數(shù)指標很難做出定量的判斷，過多地強調(diào)參數(shù)指標，反而使得網(wǎng)絡(luò)生存時間缺乏統(tǒng)一標準［12］。因此在仿真中，生存時間的度量值采用網(wǎng)絡(luò)開始到網(wǎng)絡(luò)中出現(xiàn)任意一個節(jié)點能量耗盡或節(jié)點數(shù)據(jù)不能達到Sink節(jié)點的這一段時間。

同時在仿真時，不考慮計算、數(shù)據(jù)融合、信息查詢分組收發(fā)等能耗，也不考慮數(shù)據(jù)傳輸過程中超時重發(fā)、出錯等能耗，只考慮數(shù)據(jù)無線通信能耗。選擇500 m×500 m網(wǎng)絡(luò)仿真區(qū)域，在該區(qū)域內(nèi)隨機產(chǎn)生均勻分布的30、40、50、60、70、80、90、100 個無線傳感網(wǎng)節(jié)點(包括一個Sink節(jié)點)的位置分布，其中Sink節(jié)點固定坐標(250，250)。為了驗證算法的有效性，針對每個固定節(jié)點數(shù)量的無線傳感網(wǎng)，隨機產(chǎn)生10個不同的節(jié)點位置(即不同網(wǎng)絡(luò)拓撲結(jié)構(gòu))。根據(jù)表1的仿真參數(shù)分別計算這10個不同拓撲結(jié)構(gòu)的無線傳感網(wǎng)生存時間、平均能耗和平均時延，最后取其平均值。

定義網(wǎng)絡(luò)生存時間的值為網(wǎng)絡(luò)開始運行到任意一個節(jié)點能量耗盡時Sink節(jié)點完成的數(shù)據(jù)收集周期個數(shù)DGC(Data Gathering Cycle)。一個DGC是指網(wǎng)絡(luò)中所有節(jié)點感知1 000g比特數(shù)據(jù)，并將數(shù)據(jù)發(fā)送給Sink節(jié)點所需要的時間。節(jié)點平均能耗=當一個節(jié)點能量耗盡時所有節(jié)點的總能耗/(節(jié)點數(shù)×DGC數(shù))。節(jié)點平均時延=當一個節(jié)點能量耗盡時所有節(jié)點將數(shù)據(jù)發(fā)送給Sink節(jié)點的總跳數(shù)/(節(jié)點數(shù)×DGC數(shù))。

表1 仿真參數(shù)表

5.2 算法的關(guān)鍵參數(shù)研究

算法的關(guān)鍵參數(shù)是影響鏈路權(quán)值的α和β值，影響衰減模型的參數(shù)γl1，γl2，以下就是各個參數(shù)的選擇。

5.2.1 α 和 β值的選擇

研究式(7)中α和β值參數(shù)，在參數(shù)研究過程中采用窮舉法獲得仿真數(shù)據(jù)。選擇30、40、50、60、70、80、90、100個節(jié)點的無線傳感網(wǎng)，采用線性衰減模型，α 和 β 參數(shù)分別選擇{0.1，0.4，0.7，1，3，5}集合中的值，循環(huán)獲得所有可能的網(wǎng)絡(luò)生存時間和平均節(jié)點能耗。分析仿真數(shù)據(jù)可知:當DPCRA_SPT算法中的某個參數(shù)固定，另一參數(shù)可選擇{0.1，0.4，0.7，1，3，5}集合中的任意值進行仿真，仿真結(jié)果能顯示該參數(shù)的取值規(guī)律。為了方便說明，以其中一種典型數(shù)據(jù)為例分析參數(shù)取值規(guī)律，具體分析如下。

分析仿真數(shù)據(jù)可知(以 β=1，γl1=0.5，γl2=0.5為例，如圖3和圖4):在節(jié)點數(shù)給定后，當α≥1時，如果α偏向于5，網(wǎng)絡(luò)過多地考慮鏈路能耗在權(quán)值函數(shù)式(7)中的作用，著重考慮鏈路能耗，忽略了節(jié)點剩余能量參數(shù)，節(jié)點直接選擇鏈路能耗最小的路徑。由于此時容易產(chǎn)生樞紐節(jié)點導致能量消耗過快，因此網(wǎng)絡(luò)生存時間隨著α的增大而減小。當α≤1時，α 4種不同取值的網(wǎng)絡(luò)生存時間差別不大，但是從具體數(shù)據(jù)分析，當α=0.7時，網(wǎng)絡(luò)生存時間相對較大。雖然α≤1時網(wǎng)絡(luò)平均能耗變化不明顯，但是當α≥1時網(wǎng)絡(luò)平均能耗隨著α的增大而降低。這是因為當α≥1時，過多地忽略了節(jié)點剩余能量則導致當前發(fā)送路徑不理想，網(wǎng)絡(luò)生存時間下降明顯。由于計算平均能耗時需除以網(wǎng)絡(luò)生存時間，因此節(jié)點平均能耗也增加。

圖3 α因子對網(wǎng)絡(luò)生存時間的影響

圖4 α因子對節(jié)點平均能耗的影響

總之，在DPCRA_SPT算法中，選擇適當?shù)摩量梢匝娱L網(wǎng)絡(luò)生存時間。

分析仿真數(shù)據(jù)可知(以 α=0.7，γl1=0.5，γl2=0.5為例，如圖5和圖6):當β≥1時，β≥3的網(wǎng)絡(luò)生存時間比β=1時略微增加。這是因為:在β≥3時，權(quán)值函數(shù)式(7)中鄰居節(jié)點剩余能量對權(quán)值函數(shù)的影響已經(jīng)足夠大，這導致節(jié)點直接選擇剩余能量大的鄰居節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，此時β值的變化基本不影響最短路徑選擇，從而使網(wǎng)絡(luò)生存時間相差很小。由于只是選擇剩余能量大的鄰居節(jié)點，基本上不考慮節(jié)點的鏈路能耗。當β≥1時，隨著β的數(shù)量增大，節(jié)點平均能耗增大。當β≤1時，在節(jié)點數(shù)給定后，β越接近于1，網(wǎng)絡(luò)生存時間越大。這是因為:β越小，權(quán)值函數(shù)過少地考慮節(jié)點剩余能量作用，權(quán)值函數(shù)偏向于鏈路能耗，因此網(wǎng)絡(luò)生存時間變小。由于幾個主干節(jié)點(即樞紐節(jié)點)轉(zhuǎn)發(fā)過多的數(shù)據(jù)，過早消耗能量而失效，但是其它節(jié)點能量消耗不大。因此當0.3≤β≤1時，網(wǎng)絡(luò)平均能耗相差不大。由于當β=0.1時，網(wǎng)絡(luò)生存時間下降太快，此時平均能耗偏大。

圖5 β因子對網(wǎng)絡(luò)生存時間的影響

圖6 β因子對節(jié)點平均能耗的影響

總之，在DPCRA_SPT算法中，選擇適當?shù)摩驴梢匝娱L網(wǎng)絡(luò)生存時間。

綜上所述，在DPCRA_SPT算法中，選擇適當?shù)膮?shù)如α=0.7、β=1可以延長網(wǎng)絡(luò)生存時間、保持平均能耗在較低水平。

5.2.2 γl1和 γl2值的選擇

研究式(8)中γl1和γl2兩個參數(shù)，在參數(shù)研究過程中采用窮舉法來獲得仿真數(shù)據(jù)。在參數(shù)研究過程中選擇100節(jié)點的線性功率衰減模型，α=0.7，β=1，γl1和 γl2分別取值 0，0.1，0.2，…，1，二層循環(huán)得到網(wǎng)絡(luò)生存時間的仿真數(shù)據(jù)，獲得三維圖7。分析圖中網(wǎng)絡(luò)生存時間可知，當γl1固定值，剛開始網(wǎng)絡(luò)生存時間隨著γl2的增加而增加。當γl1和γl2兩個參數(shù)差不多時，網(wǎng)絡(luò)生存時間達到峰值，此后隨著γl2的增加而減少。

圖7 γl1和γl2對網(wǎng)絡(luò)生存時間的影響

總之，選擇適當?shù)摩胠1和γl2值，DPCRA_SPT算法可以較好地反映網(wǎng)絡(luò)生存時間。

5.3 仿真結(jié)果和分析

根據(jù)5.2節(jié)的參數(shù)研究，得出能較好延長網(wǎng)絡(luò)生存時間的參數(shù)如 α=0.7，β=1，γl1=0.5 和 γl2=0.5，將DPCRA_SPT算法的鏈路權(quán)值公式改為:

為了反映算法的有效性，選擇采用固定最大發(fā)送功率的Ratio_w算法(記為Ratio_w_FTP)，采用固定最大發(fā)送功率的 Bellman-Ford算法(記為BFFTP)，采用階梯衰減模型的Bellman-Ford算法(記為 BFSAM)［13］，采用 γn階二項式衰減模型的Bellman-Ford 算法(記為 BFPAM)［13］進行比較。

圖8比較了各算法的網(wǎng)絡(luò)生存時間。如圖可知:當節(jié)點數(shù)量是30時，由于網(wǎng)絡(luò)節(jié)點分布比較稀疏，一般節(jié)點通信需要最大發(fā)送功率，此時功率衰減模型反而降低了網(wǎng)絡(luò)生存時間，因此 BFSAM、BFPAM和DPCRA_SPT 3個算法的網(wǎng)絡(luò)生存時間比Ratio_w_FTP和BFFTP低，但是從數(shù)據(jù)上看BFFTP比Ratio_w_FTP略高。當節(jié)點數(shù)量大于30時，DPCRA_SPT的網(wǎng)絡(luò)生存時間最高，BFPAM次之，BFSAM第三，但這3個算法的網(wǎng)絡(luò)生存時間比Ratio_w_FTP和BFFTP高。這是因為當節(jié)點數(shù)量大于30時，隨著節(jié)點數(shù)量的增加，節(jié)點分布相對密集，此時節(jié)點不需要太大的發(fā)送功率，功率衰減模型體現(xiàn)出其價值，調(diào)整網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，從而延長網(wǎng)絡(luò)生存時間。節(jié)點分布越密集，延長網(wǎng)絡(luò)生存時間的效果越明顯?？傊?，當節(jié)點分布密集時，DPCRA_SPT算法，能延長網(wǎng)絡(luò)生存時間。

圖8 各算法的網(wǎng)絡(luò)生存時間比較圖

圖9比較了各算法的節(jié)點平均能耗。如圖可知:BFSAM的能耗最低，DPCRA_SPT算法次之，BFPAM算法第三，但是這3個算法都比Ratio_w_FTP和BFFTP算法低，而BFFTP算法和Ratio_w_FTP算法平均能耗基本一樣。這是因為:BFSAM、BFPAM和DPCRA_SPT這3個算法根據(jù)節(jié)點剩余能量的變化隨時改變自身的發(fā)送功率，調(diào)整網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，從而降低了節(jié)點的能耗?？傊?，DPCRA_SPT降低了節(jié)點的平均能耗，將能耗保持在較低的水平。

圖9 各算法的節(jié)點平均能耗比較圖

圖10比較了各個算法的節(jié)點平均時延(跳數(shù))。如圖可知:BFSAM、BFPAM和DPCRA_SPT三個算法的網(wǎng)絡(luò)平均時延(跳數(shù))波動很大，而且比BFFTP算法和Ratio_w_FTP算法高。這是因為，隨著節(jié)點剩余能量的減少，節(jié)點相對應(yīng)減少了發(fā)送功率，可通信的范圍變小，此時數(shù)據(jù)到達Sink節(jié)點的跳數(shù)，即網(wǎng)絡(luò)平均時延增加?？傊?，BFSAM、BFPAM和DPCRA_SPT算法不能降低網(wǎng)絡(luò)平均時延(跳數(shù))。

圖10 各算法的節(jié)點平均時延(跳數(shù))比較圖

綜上所述，當節(jié)點分布密集時，DPCRA_SPT算法可以延長網(wǎng)絡(luò)生存時間，將能耗保持在較低的水平，比 Ratio_w_FTP、BFFTP、BFSAM、BFPAM 算法更優(yōu)。

6 總結(jié)

如果節(jié)點不能測量到鄰居節(jié)點的距離，通過兩節(jié)點間距離調(diào)整發(fā)送功率就不可行，因此提出根據(jù)節(jié)點剩余能量改變自身發(fā)送功率的DPCRA_SPT算法。首先，詳細闡述鏈路能耗模型和系統(tǒng)假設(shè)。其次，考慮網(wǎng)絡(luò)中鏈路通信的能耗和鄰居節(jié)點的剩余能量，引入新的權(quán)值函數(shù)和功率線性衰減模型。運用分布式非同步Bellman-Ford算法構(gòu)建最短路徑樹，所有節(jié)點沿著最短路徑樹將數(shù)據(jù)匯聚到Sink節(jié)點。最后，仿真分析權(quán)值函數(shù)式(7)和線性衰減模型中相關(guān)參數(shù)對網(wǎng)絡(luò)生存時間和平均能耗的影響，仿真比較DPCRA_SPT算法對網(wǎng)絡(luò)生存時間、平均能耗和平均時延的影響。

DPCRA_SPT算法適用于節(jié)點密集分布的無線傳感網(wǎng)，而且只是根據(jù)自身的剩余能量信息修改發(fā)送功率，當節(jié)點發(fā)送功率降低一定程度時容易造成網(wǎng)絡(luò)的分裂。因此下一步研究的工作是節(jié)點如何根據(jù)鄰居節(jié)點的信息，確定當前拓撲下的全局最優(yōu)發(fā)送功率。

［1］朱藝華，楊晨曦，吳萬登，等.無線傳感器網(wǎng)絡(luò)權(quán)衡生存時間與數(shù)據(jù)分組跳數(shù)的分流路由算法［J］.傳感技術(shù)學報，2009，22(2):273－279.

［2］Manan R，Lall S.Distributed Algorithms for Maximum Lifetime Routing in Wireless Sensor Network［J］.IEEE Transactions on Wireless Communications，2006，5(8):2185－2193.

［3］He Y F，Lee I，Guan L.Distributed Algorithms for Network Lifetime Maximization in Wireless Visual Sensor Networks［J］.IEEE Transactions on Circuits and System for Video Technology，2009，19(5):704－718.

［4］Zhu Y H，Wu W D，Victor C M，et al.Energy-Efficient tree-Based Message Ferrying Routing Schemes for Wireless Sensor Networks［C］//Thirteen International Conference on Communications and Networking in China.Hangzhou，China，2008:25－28.

［5］朱藝華，沈丹丹，吳萬登，等.無線傳感器網(wǎng)絡(luò)優(yōu)化生存時間的動態(tài)路由算法［J］.電子學報，2009，37(5):1041－1045.

［6］Fariborzi H，Moghavvemi M.EAMTR:Energy Aware Multi-Tree Routing for Wireless Sensor Networks［J］.Special Issue on Wireless Ad-Hoc Networks，2009，3(5):733－739.

［7］Wendi B H.Application-Specific Protocol Architectures for Wireless Networks［D］.Boston:Massachusetts Institute of Technology，2000.

［8］Gatzianas M A，Georgiadis L G.A Distributed Algorithm for Maximum Lifetime Routing in Sensor Networks with Mobile Sink［J］.IEEE Transactions on Wireless Communications，2007，7(3):984－994.

［9］Bertsekas D，Gallager R.數(shù)據(jù)網(wǎng)絡(luò)(第二版)［M］.盧剛，王康，譯.北京:人民郵電出版社，2004.

［10］Minhas R M，Gopalakrishnan S，Leung V C M.An Online Multipath Routing Algorithm for Maximizing Lifetime in Wireless Sensor Networks［C］//2009 Sixth International Conference on Information Technology.New Generations，2009:581－586.

［11］陳友榮，劉半藤，程菊花，等.無線傳感網(wǎng)優(yōu)化生存時間的分布式功率控制［J］.傳感技術(shù)學報，2011，24(12):1787－1793.

［12］潘晏濤.傳感器網(wǎng)絡(luò)生存時間優(yōu)化問題研究［D］.國防科學技術(shù)大學，2006.

［13］Chen Y R，Lu Y W，Cheng J H，et al.L.Distributed Power Control Algorithms for Wireless Sensor Networks［J］.Lecture Notes in E-lectrical Engineering，2011，98(2):319－326(EI).