基于最短路徑樹(shù)的分布式功率控制路由算法*

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

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

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

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

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

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

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

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

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

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

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

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

(6)所有傳感節(jié)點(diǎn)沒(méi)有安裝GPS等模塊，無(wú)法獲知自身的位置坐標(biāo)，也無(wú)法獲知節(jié)點(diǎn)到鄰居節(jié)點(diǎn)的距離。

2 鏈路能耗模型

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

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

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

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

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

傳感節(jié)點(diǎn)i與Sink節(jié)點(diǎn)之間傳輸g比特?cái)?shù)據(jù)的能耗取為:

3 算法的原理

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

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

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

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

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

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

3.1 功率控制算法

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

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

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

圖2 線性功率衰減曲線

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

4 算法的實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

5 算法的仿真

5.1 仿真參數(shù)選擇

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

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

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

表1 仿真參數(shù)表

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

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

5.2.1 α 和 β值的選擇

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

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

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

圖4 α因子對(duì)節(jié)點(diǎn)平均能耗的影響

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

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

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

圖6 β因子對(duì)節(jié)點(diǎn)平均能耗的影響

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

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

5.2.2 γl1和 γl2值的選擇

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

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

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

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

根據(jù)5.2節(jié)的參數(shù)研究，得出能較好延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的參數(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階二項(xiàng)式衰減模型的Bellman-Ford 算法(記為 BFPAM)［13］進(jìn)行比較。

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

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

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

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

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

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

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

6 總結(jié)

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

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

［1］朱藝華，楊晨曦，吳萬(wàn)登，等.無(wú)線傳感器網(wǎng)絡(luò)權(quán)衡生存時(shí)間與數(shù)據(jù)分組跳數(shù)的分流路由算法［J］.傳感技術(shù)學(xué)報(bào)，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àn)登，等.無(wú)線傳感器網(wǎng)絡(luò)優(yōu)化生存時(shí)間的動(dòng)態(tài)路由算法［J］.電子學(xué)報(bào)，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ú)線傳感網(wǎng)優(yōu)化生存時(shí)間的分布式功率控制［J］.傳感技術(shù)學(xué)報(bào)，2011，24(12):1787－1793.

［12］潘晏濤.傳感器網(wǎng)絡(luò)生存時(shí)間優(yōu)化問(wèn)題研究［D］.國(guó)防科學(xué)技術(shù)大學(xué)，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).