基于最短路徑樹的優(yōu)化生存時(shí)間路由算法*

陳友榮，王章權(quán)，程菊花，劉耀林

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

在大部分情況下無線傳感網(wǎng)的所有節(jié)點(diǎn)采用電池供電，被部署在無人看守的惡劣環(huán)境中。而且節(jié)點(diǎn)分布密集、數(shù)量龐大，對(duì)電池的更換是非常困難的，因此節(jié)點(diǎn)存在嚴(yán)重的能量約束［1－2］。電池不能補(bǔ)充和更換，一旦節(jié)點(diǎn)能量耗盡，該節(jié)點(diǎn)就會(huì)失效，這將影響到網(wǎng)絡(luò)的運(yùn)行，甚至導(dǎo)致網(wǎng)絡(luò)出現(xiàn)分裂而縮短網(wǎng)絡(luò)生存時(shí)間。因此，無線傳感網(wǎng)的各個(gè)算法都要從節(jié)能出發(fā)，最大限度地延長整個(gè)網(wǎng)絡(luò)的生存時(shí)間［3－4］，節(jié)省重新部署無線傳感網(wǎng)的巨大開銷。

延長網(wǎng)絡(luò)生存時(shí)間的方法很多，主要從兩點(diǎn)考慮:減少和平衡節(jié)點(diǎn)能耗。減少節(jié)點(diǎn)能耗使得節(jié)點(diǎn)可用能量持續(xù)的時(shí)間更長，從而延長網(wǎng)絡(luò)生存時(shí)間；平衡節(jié)點(diǎn)能耗，避免網(wǎng)絡(luò)樞紐節(jié)點(diǎn)因自身能量消耗過快而縮短網(wǎng)絡(luò)生存時(shí)間。文獻(xiàn)［5］提出PEDAP(power efficient data gathering and aggregation protocol)和PEDAP_PA(power efficient data gathering and aggregation protocol_power aware)，都是基于最小權(quán)重樹的路由算法。在算法中，定義了基于鏈路能耗的權(quán)值函數(shù)，通過Prim算法構(gòu)建最小權(quán)重樹，最終所有節(jié)點(diǎn)沿著最小權(quán)重樹將數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)。但是PEDAP和PEDAP_PA算法在網(wǎng)絡(luò)生存時(shí)間延長方面不是特別理想。文獻(xiàn)［6］提出LET(Least En-ergy Tree)算法。它是根據(jù)dijkstra算法構(gòu)建每個(gè)節(jié)點(diǎn)到Sink節(jié)點(diǎn)能耗最小的最短路徑樹，最終所有節(jié)點(diǎn)沿著最短路徑樹將數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)。LET算法比PEDAP和PEDAP_PA算法好，這是因?yàn)?LET算法利用dijkstra算法，構(gòu)建以Sink節(jié)點(diǎn)為樹根的最短路徑樹。由于dijkstra算法可以得到能耗最小路徑，因而每個(gè)節(jié)點(diǎn)都沿著能耗最小路徑傳輸數(shù)據(jù)，整個(gè)網(wǎng)絡(luò)的能耗也相對(duì)較?。?］。但是LET算法的權(quán)值函數(shù)中存在著一個(gè)缺點(diǎn):它忽視了節(jié)點(diǎn)的剩余能量。往往離Sink節(jié)點(diǎn)近的節(jié)點(diǎn)中存在一些樞紐節(jié)點(diǎn)，只是簡(jiǎn)單考慮鏈路通信能耗的權(quán)值函數(shù)，容易導(dǎo)致這些節(jié)點(diǎn)轉(zhuǎn)發(fā)太多的數(shù)據(jù)，過早消耗能量而死亡。于是在LET算法的基礎(chǔ)上提出了“比例權(quán)值路由算法”(ratio weight routing algorithm，Ratio_w)與“和權(quán)值路由算法”(sum weight routing algorithm，Sum_w)［7］，但是這兩種算法沒有考慮鄰居節(jié)點(diǎn)的剩余能量，網(wǎng)絡(luò)生存時(shí)間也不是最優(yōu)的。因此綜合考慮上述算法的優(yōu)缺點(diǎn)，提出了基于最短路徑樹的優(yōu)化生存時(shí)間路由算法(lifetime optimized routing algorithm based on shortest path tree，LORA_SPT)，延長網(wǎng)絡(luò)的生存時(shí)間。

1 系統(tǒng)假設(shè)和鏈路能耗模型

在提出的路由算法中，假設(shè)［8］:①所有傳感節(jié)點(diǎn)和Sink節(jié)點(diǎn)的位置是固定不變或是緩慢變化的，不影響節(jié)點(diǎn)間的相互位置和拓?fù)浣Y(jié)構(gòu)，且Sink節(jié)點(diǎn)有整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息；②所有傳感節(jié)點(diǎn)具有相同的性能(如初始能量、能耗參數(shù)、節(jié)點(diǎn)最大發(fā)送功率、最大通信半徑等)；③所有傳感節(jié)點(diǎn)發(fā)送功率可根據(jù)通信距離變化；④每個(gè)傳感節(jié)點(diǎn)能量受限，但Sink能量不受限制；⑤網(wǎng)絡(luò)中所有傳感節(jié)點(diǎn)都需要感知和發(fā)送數(shù)據(jù)，即同時(shí)承擔(dān)數(shù)據(jù)采集和中繼任務(wù)，并通過直接或多跳的方式將數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)。

典型的無線傳感網(wǎng)節(jié)點(diǎn)能耗主要由無線數(shù)據(jù)收發(fā)產(chǎn)生［9］。節(jié)點(diǎn)發(fā)送模塊的能耗ETx由發(fā)送電路電子能耗和信號(hào)放大器部分的電子能耗組成。接收模塊的能耗ERx只考慮接收信號(hào)時(shí)的電路電子能耗。其中，電路電子能耗固定為gEelec，g代表所發(fā)送或接收的數(shù)據(jù)量，Eelec代表收發(fā)單位比特?cái)?shù)據(jù)時(shí)電路電子能耗。信號(hào)放大器部分的電子能耗與節(jié)點(diǎn)發(fā)送功率有關(guān)。假設(shè)節(jié)點(diǎn)根據(jù)通信距離隨時(shí)調(diào)整發(fā)送功率，于是可定義為與通信距離有關(guān)。具體的計(jì)算公式如下:

其中dij是發(fā)送的距離，dmax是最大通信距離，εfs是放大單位比特信號(hào)時(shí)所需要的電子能耗。根據(jù)式(1)和(2)可知:傳感節(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ù)的能耗取為:

2 算法的原理

LET、Ratio_w和Sum_w算法的鏈路權(quán)值函數(shù)只考慮自身能量的大小，而鄰居節(jié)點(diǎn)的剩余能量在鏈路選擇時(shí)同樣有利于避免剩余能量小的節(jié)點(diǎn)過早失效，因此考慮鄰居節(jié)點(diǎn)的剩余能量是有必要的。同時(shí)為了避免網(wǎng)絡(luò)樞紐節(jié)點(diǎn)能耗過快損耗，根據(jù)剩余能量將節(jié)點(diǎn)劃分成標(biāo)準(zhǔn)節(jié)點(diǎn)和警告節(jié)點(diǎn)兩種不同類型的節(jié)點(diǎn)［10］。權(quán)值函數(shù)中，不同類型的節(jié)點(diǎn)剩余能量權(quán)重因子是不一樣的。具體說明如下:①標(biāo)準(zhǔn)節(jié)點(diǎn):如果節(jié)點(diǎn)剩余能量值大于Ewarning，則是標(biāo)準(zhǔn)節(jié)點(diǎn)。網(wǎng)絡(luò)中偏向于選擇這些節(jié)點(diǎn)參與數(shù)據(jù)的轉(zhuǎn)發(fā)。標(biāo)準(zhǔn)節(jié)點(diǎn)周圍的鏈路權(quán)值不考慮類型權(quán)重因子，即是1。②警告節(jié)點(diǎn):如果節(jié)點(diǎn)剩余能量值小于Ewarning，則是警告節(jié)點(diǎn)。在傳輸數(shù)據(jù)的時(shí)候盡量避開該類型的節(jié)點(diǎn)。此時(shí)警告節(jié)點(diǎn)周圍的鏈路權(quán)值需要考慮類型權(quán)重因子，提高鏈路權(quán)值。

假設(shè)節(jié)點(diǎn)的初始能量為Einital，Ewarning的設(shè)定如下:

其中特定正常數(shù)δ的作用是確定Ewarning的值。f(x)是一個(gè)關(guān)于x的函數(shù)，x是網(wǎng)絡(luò)參數(shù)，其設(shè)定如下:

其中|V|指網(wǎng)絡(luò)中總節(jié)點(diǎn)數(shù)，x初始值是1，其具體計(jì)算方法如下:統(tǒng)計(jì)傳感節(jié)點(diǎn)剩余能量值低于當(dāng)前Ewarning值的節(jié)點(diǎn)數(shù)和警告節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中所占的比例Yc。設(shè)定一個(gè)閾值Ys(0＜Ys＜1)，如果Yc＞Ys時(shí)，則表示x=x+1，更新Ewarning值。從式(6)可以看出，f(x)函數(shù)為遞增函數(shù)，f(x)值隨x的增大而增大，且f(x)的增加幅度也隨x的增大而增大，當(dāng)x趨近于|V|時(shí)，f(x)無窮大。因此，可以推斷出當(dāng)x增大時(shí)，Ewarning隨之減小，而且當(dāng)Ewarning減少到一定值時(shí)，某些警告節(jié)點(diǎn)又重新變成標(biāo)準(zhǔn)節(jié)點(diǎn)，繼續(xù)參與數(shù)據(jù)的路由。當(dāng)x趨近于|V|時(shí)，Ewarning趨近于零，把低于Ewarning的節(jié)點(diǎn)認(rèn)為是能量耗盡的失效節(jié)點(diǎn)。Ewarning的遞減規(guī)律符合傳感節(jié)點(diǎn)能量的實(shí)際情況，開始節(jié)點(diǎn)能量比較充足，Ewarning的遞減速度相對(duì)較快，但當(dāng)節(jié)點(diǎn)能量普遍較低的情況，Ewarning遞減的幅度就變慢。

綜上所述，考慮鄰居節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)剩余能量，引入節(jié)點(diǎn)分類概念，建立新的鏈路權(quán)值函數(shù)，提出了LORA_SPT算法。Re(i)表示節(jié)點(diǎn)i的剩余能量，Re(j)表示節(jié)點(diǎn)j的剩余能量，wij表示鏈路(i，j)的權(quán)值，Cij(g，d)表示傳感節(jié)點(diǎn)i與節(jié)點(diǎn)j之間傳輸g比特?cái)?shù)據(jù)的能量消耗，dij表示節(jié)點(diǎn)i與節(jié)點(diǎn)j的距離。在LORA_SPT算法中，取

其中，α是能耗因子，θ是發(fā)送節(jié)點(diǎn)剩余能量因子，β是接收節(jié)點(diǎn)剩余能量因子，ηi是節(jié)點(diǎn)i類型權(quán)重因子，而且這四個(gè)因子都是正常數(shù)。

在完成此輪網(wǎng)絡(luò)權(quán)值的更新后，利用最短路徑樹中典型dijkstra算法求源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑，輸出算法生成的最優(yōu)樹。節(jié)點(diǎn)一般選擇鏈路能耗小且經(jīng)過標(biāo)準(zhǔn)節(jié)點(diǎn)的路徑發(fā)送數(shù)據(jù)，從而避免警告節(jié)點(diǎn)成為樞紐節(jié)點(diǎn)，平衡節(jié)點(diǎn)能耗，延長網(wǎng)絡(luò)生存時(shí)間。

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

提出的LORA_SPT是一種集中式路由算法。算法實(shí)現(xiàn)主要在Sink節(jié)點(diǎn)上完成，其具體的實(shí)現(xiàn)步驟如下:

第一步:網(wǎng)絡(luò)開始時(shí)，每個(gè)節(jié)點(diǎn)初始化自身的信息。

第二步:Sink節(jié)點(diǎn)開始收集算法所需要的節(jié)點(diǎn)信息。Sink節(jié)點(diǎn)以洪泛方式向周圍所有的鄰居節(jié)點(diǎn)發(fā)送信息查詢分組。

第三步:鄰居節(jié)點(diǎn)接收到Sink節(jié)點(diǎn)的查詢分組后，將自己的剩余能量Re(i)、所要發(fā)送的數(shù)據(jù)量、位置坐標(biāo)等信息發(fā)送給Sink節(jié)點(diǎn)。Sink節(jié)點(diǎn)收集所有節(jié)點(diǎn)信息(節(jié)點(diǎn)位置坐標(biāo)、剩余能量等)后，啟動(dòng)LORA_SPT算法。

第四步:根據(jù)當(dāng)前的網(wǎng)絡(luò)參數(shù)x值，計(jì)算f(x)和Ewarning，確定標(biāo)準(zhǔn)節(jié)點(diǎn)和警告節(jié)點(diǎn)的數(shù)量，判斷警告節(jié)點(diǎn)數(shù)量比例是否大于Ys。大于則x=x+1。

第五步:計(jì)算網(wǎng)絡(luò)鏈路的權(quán)值，通過dijkstra算法計(jì)算每個(gè)節(jié)點(diǎn)的數(shù)據(jù)發(fā)送最短路徑。

第六步:LORA_SPT算法計(jì)算完成后，Sink節(jié)點(diǎn)以洪泛方式通知網(wǎng)絡(luò)中所有節(jié)點(diǎn)此時(shí)網(wǎng)絡(luò)的最短路徑樹。所有節(jié)點(diǎn)根據(jù)接收到的最短路徑樹，尋找自身到Sink節(jié)點(diǎn)的最短路徑，并沿著此路徑發(fā)送數(shù)據(jù)。

第七步:當(dāng)數(shù)據(jù)發(fā)送一段時(shí)間后，重新跳到第二步，Sink節(jié)點(diǎn)重新收集各個(gè)節(jié)點(diǎn)信息，更新網(wǎng)絡(luò)鏈路權(quán)值。

上述的步驟循環(huán)執(zhí)行，直到傳感節(jié)點(diǎn)能量耗盡死亡。具體見如下的LORA_SPT算法偽代碼。

分析LORA_SPT算法的時(shí)間復(fù)雜性。LORA_SPT算法主要由標(biāo)準(zhǔn)節(jié)點(diǎn)和警告節(jié)點(diǎn)的確定，鏈路權(quán)值的計(jì)算和最短路徑的建立三個(gè)部分組成。第一部分只需要對(duì)所有節(jié)點(diǎn)進(jìn)行判斷，即標(biāo)準(zhǔn)節(jié)點(diǎn)和警告節(jié)點(diǎn)確定的時(shí)間復(fù)雜度是Θ(|V|)。第二部分是二層循環(huán)計(jì)算每個(gè)鏈路的權(quán)值，即鏈路權(quán)值計(jì)算的時(shí)間復(fù)雜度是Θ(|V|2)。第三部分是dijkstra算法，即最短路徑建立的時(shí)間復(fù)雜度是Θ(|V|2)［11］。總之，LORA_SPT算法的時(shí)間復(fù)雜度是Θ(|V|2)，和最短路徑dijkstra算法一致。

4 算法的仿真

4.1 仿真參數(shù)選擇

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

表1 仿真參數(shù)表

其中，網(wǎng)絡(luò)生存時(shí)間定義為網(wǎng)絡(luò)開始運(yùn)行到任意一個(gè)節(jié)點(diǎn)能量耗盡時(shí)Sink節(jié)點(diǎn)完成的數(shù)據(jù)收集周期個(gè)數(shù)(data gathering cycle，DGC)。一個(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ù))。

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

權(quán)值函數(shù)中的節(jié)點(diǎn)類型權(quán)重因子η是區(qū)分標(biāo)準(zhǔn)節(jié)點(diǎn)和警告節(jié)點(diǎn)的周圍鏈路權(quán)值。警告節(jié)點(diǎn)的周圍鏈路權(quán)值大，路徑選擇時(shí)優(yōu)先考慮選擇標(biāo)準(zhǔn)節(jié)點(diǎn)。但是η值也不宜取的過小，否則導(dǎo)致節(jié)點(diǎn)能量在權(quán)值函數(shù)中的影響過大，因此定義標(biāo)準(zhǔn)節(jié)點(diǎn)的η值是1，警告節(jié)點(diǎn)的η值是0.25。以下主要是研究α、θ和β取值對(duì)網(wǎng)絡(luò)生存時(shí)間和節(jié)點(diǎn)能耗的影響。由于式(7)中存在多個(gè)參數(shù)，在參數(shù)研究過程中采用窮舉法來獲得仿真數(shù)據(jù)。選擇30、40、50、60、70、80、90、100 個(gè)無線傳感節(jié)點(diǎn)，3 個(gè)參數(shù)分別選擇{0.1，0.4，0.7，1，3，5}集合中的值，三層循環(huán)獲得所有可能的仿真數(shù)據(jù)。分析仿真數(shù)據(jù)可知:當(dāng)研究LORA_SPT算法中的任一參數(shù)時(shí)，其它2個(gè)參數(shù)可選擇{0.1，0.4，0.7，1，3，5}集合中的任意值進(jìn)行仿真，仿真結(jié)果能顯示該參數(shù)的取值規(guī)律。為了方便說明，以其中一種典型數(shù)據(jù)為例分析參數(shù)取值規(guī)律，具體分析如下。

偉人毛澤東，在政治家、軍事家、思想家、哲學(xué)家外，還有詩人、雜文家之稱！“兼得”如此多，仍可用“三雜”來詮釋：學(xué)識(shí)雜、文體雜自不必說，閱歷雜亦毋庸贅言。

4.2.1 α 值的選擇

分析仿真數(shù)據(jù)可知(以θ=1、β=1為例，如圖1和圖2):當(dāng)α≥1時(shí)，α值越大，節(jié)點(diǎn)平均能耗越大，網(wǎng)絡(luò)生存時(shí)間越小。這是因?yàn)?在α≥1時(shí)，α值越大，權(quán)值函數(shù)(7)越加強(qiáng)通信能耗的作用，從而降低其它二個(gè)參數(shù)(節(jié)點(diǎn)剩余能量和鄰居剩余能量)的作用，路徑選擇時(shí)會(huì)選擇鏈路能耗小但鄰居節(jié)點(diǎn)剩余能量也小的鏈路，從而降低了網(wǎng)絡(luò)生存時(shí)間，也增加了平均能耗。當(dāng)α＜1時(shí)，α值越小，網(wǎng)絡(luò)生存時(shí)間越小，網(wǎng)絡(luò)平均能耗越大。這是因?yàn)?當(dāng)α＜1時(shí)，α值越小，權(quán)值函數(shù)(7)越削弱通信能耗的作用，相應(yīng)加強(qiáng)其它兩個(gè)參數(shù)的作用，從而導(dǎo)致鏈路的能耗被忽視，使一些節(jié)點(diǎn)直接往剩余能量大但鏈路能耗也大的鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)，這樣增大了平均能耗，降低了網(wǎng)絡(luò)生存時(shí)間。

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

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

綜上所述，在LORA_SPT算法中，選擇適當(dāng)?shù)摩量梢匝娱L網(wǎng)絡(luò)生存時(shí)間。

4.2.2 θ值的選擇

分析仿真數(shù)據(jù)可知(以參數(shù)α=1、β=1為例，如圖3和圖4):當(dāng)θ＜1時(shí)，θ越接近于1，網(wǎng)絡(luò)生存時(shí)間越大，但平均能耗也越大。這是因?yàn)?當(dāng)θ＜1時(shí)，θ越小，權(quán)值函數(shù)(7)越削弱節(jié)點(diǎn)剩余能量的作用。此時(shí)網(wǎng)絡(luò)過少考慮節(jié)點(diǎn)剩余能量導(dǎo)致部分樞紐節(jié)點(diǎn)(樹中主干節(jié)點(diǎn))過多的參與數(shù)據(jù)的轉(zhuǎn)發(fā)，能量消耗過快而失效，網(wǎng)絡(luò)生存時(shí)間越小。由于只是部分節(jié)點(diǎn)消耗過多的能量，其它節(jié)點(diǎn)能量消耗不大，因此θ越小，節(jié)點(diǎn)平均能耗也越小。當(dāng)θ≥1時(shí)，θ對(duì)網(wǎng)絡(luò)生存時(shí)間影響不大，但能耗隨著θ的增大而增大。這是因?yàn)?當(dāng)θ≥1時(shí)，節(jié)點(diǎn)剩余能量對(duì)權(quán)值函數(shù)(7)的影響足夠大，權(quán)值函數(shù)中節(jié)點(diǎn)剩余能量占主要因素，于是網(wǎng)絡(luò)生存時(shí)間基本已達(dá)到頂峰。但是在最短路徑樹的建立過程中，部分節(jié)點(diǎn)會(huì)選擇剩余能量大但是鏈路通信能耗也大的鄰居節(jié)點(diǎn)作為父節(jié)點(diǎn)，導(dǎo)致節(jié)點(diǎn)平均能耗隨著θ的增大而增大。

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

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

綜上所述，在LORA_SPT算法中，選擇適當(dāng)?shù)摩瓤梢匝娱L網(wǎng)絡(luò)生存時(shí)間。

4.2.3 β 值的選擇

綜上所述，在LORA_SPT算法中，選擇適當(dāng)?shù)摩驴梢匝娱L網(wǎng)絡(luò)生存時(shí)間。

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

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

4.3 算法仿真結(jié)果比較

根據(jù)4.2部分的參數(shù)研究，得出生存時(shí)間延長效果較好的參數(shù)如 α=1，θ=1，β=0.7時(shí)。將 LORA_SPT算法的鏈路權(quán)值公式改為:

為了反映算法的有效性，將LET、PEDAP_PA、Ratio_w、Sum_w和LORA_SPT等算法進(jìn)行比較。

圖7比較了各算法的網(wǎng)絡(luò)生存時(shí)間，從圖中可知:LORA_SPT算法的網(wǎng)絡(luò)生存時(shí)間(DGC個(gè)數(shù))比LET、PEDAP_PA、Ratio_w和 Sum_w算法更大，是最優(yōu)的，其次是Ratio_w算法。這是因?yàn)樵撍惴ňC合考慮鏈路能耗，自身節(jié)點(diǎn)能耗和鄰居節(jié)點(diǎn)能耗，同時(shí)引入類型權(quán)重因子，避免剩余能量較小的節(jié)點(diǎn)(警告節(jié)點(diǎn))過多參與數(shù)據(jù)的路由而過早死亡，因此在網(wǎng)絡(luò)生存時(shí)間方面，LORA_SPT延長了網(wǎng)絡(luò)生存時(shí)間。

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

圖8比較了各算法的節(jié)點(diǎn)平均能耗。從圖中可知:LORA_SPT、LET、Sum_w和Ratio_w算法的節(jié)點(diǎn)平均能耗相差不大，但是這四個(gè)算法的平均能耗遠(yuǎn)低于PEDAP_PA算法。這是因?yàn)橐苊鈽屑~節(jié)點(diǎn)過早能量耗盡而死亡，LORA_SPT算法在一些路徑選擇上避免該樞紐節(jié)點(diǎn)而選擇能耗相對(duì)較大的路徑，因此，在能耗方面，LORA_SPT算法在一定程度上將能耗保持在較低的水平。

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

圖9比較了網(wǎng)絡(luò)某一個(gè)節(jié)點(diǎn)能量耗盡時(shí)其它節(jié)點(diǎn)的平均剩余能量。從圖中可知:LORA_SPT算法平均剩余能量最低、Ratio_w和PEDAP次之，但這三個(gè)算法高于LET和Sum_w。這是因?yàn)長ORA_SPT算法把節(jié)點(diǎn)分成兩類節(jié)點(diǎn)(標(biāo)準(zhǔn)節(jié)點(diǎn)和警告節(jié)點(diǎn))。警告節(jié)點(diǎn)的類型權(quán)重因子小，周圍鏈路權(quán)值變大。在路徑選擇時(shí)就盡量避免選擇警告節(jié)點(diǎn)，從而每個(gè)節(jié)點(diǎn)根據(jù)剩余能量選擇性參與網(wǎng)絡(luò)路由，均衡能量消耗。因此，在能耗方面，LORA_SPT算法均衡了網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)的能耗。

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

圖10比較了各算法的網(wǎng)絡(luò)平均時(shí)延(跳數(shù))。從圖中可知:LORA_SPT算法的網(wǎng)絡(luò)平均時(shí)延最小，LET、Sum_w和 Ratio_w算法的網(wǎng)絡(luò)平均時(shí)延比LORA_SPT算法較大，但這四個(gè)算法的平均時(shí)延遠(yuǎn)低于PEDAP_PA。這是因?yàn)長ORA_SPT算法考慮了新的權(quán)值函數(shù)，優(yōu)化的網(wǎng)絡(luò)生存時(shí)間，在路徑選擇上節(jié)點(diǎn)選擇比較優(yōu)化的路徑，從一定程序上減低了節(jié)點(diǎn)到Sink節(jié)點(diǎn)的平均跳數(shù)。因此在網(wǎng)絡(luò)時(shí)延方面，LORA_SPT算法降低了網(wǎng)絡(luò)的時(shí)延。

圖10 各算法的網(wǎng)絡(luò)平均時(shí)延(跳數(shù))比較圖

總之，LORA_SPT算法降低了網(wǎng)絡(luò)平均時(shí)延(跳數(shù))，將節(jié)點(diǎn)平均能耗保持在較低的水平，均衡了網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)的能耗，提高了延長網(wǎng)絡(luò)生存時(shí)間，比LET、PEDAP_PA、Sum_w和Ratio_w算法更優(yōu)。

5 總結(jié)

LORA_SPT算法構(gòu)造了基于能耗因子、自身節(jié)點(diǎn)剩余能量因子、鄰居節(jié)點(diǎn)剩余能量因子和類型權(quán)重因子等因子的權(quán)值函數(shù)，針對(duì)不同類型的節(jié)點(diǎn)采用不同的權(quán)重因子，最后利用dijkstra算法完成最短路徑樹。

LORA_SPT算法是集中式路由算法，需要節(jié)點(diǎn)把自身信息匯聚到Sink節(jié)點(diǎn)，Sink節(jié)點(diǎn)處理完再通知其它節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。集中式路由算法能夠被應(yīng)用在靜態(tài)網(wǎng)絡(luò)中，但是不能很好地適應(yīng)具有動(dòng)態(tài)拓?fù)涮匦缘臒o線傳感網(wǎng)。于是下一步工作的重點(diǎn)是研究動(dòng)態(tài)拓?fù)涞臒o線傳感網(wǎng)分布式路由算法。

［1］Akyildiz I F，Su W L，Sankarasubramaniam Y，et al.A Survey on Sensor Networks［J］.IEEE Communications Magazine，2002，40(10):2－116.

［2］Yick J，Mukherjee B，Ghosal D.Wireless Sensor Network Survey［J］.Computer Networks，2008，52(12):2292－2330.

［3］Wu X Y，Cassandras C G.A Maximum Time Optimal Control Approach to Routing in Sensor Networks［A］.Proceedings of the 44th IEEE Conference on Decision and Control，and the European Control Conference［C］//Spain:IEEE Computer Press，2005:1137－1142.

［4］劉鐵流，巫詠群.基于能量優(yōu)化的無線傳感器網(wǎng)絡(luò)分簇路由算法研究［J］.傳感技術(shù)學(xué)報(bào)，2011，24(5):764－770.

［5］Tan H O，Korpeoglu I.Power Efficient Data Gathering and Aggregation in Wireless Sensor Networks［J］.SIGMD Record，2003，32(4):66－71.

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

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

［8］陳友榮，俞立，董齊芬，等.基于近鄰算法的無線傳感器網(wǎng)絡(luò)功率控制［J］.浙江大學(xué)學(xué)報(bào)(工學(xué)版)，2010，44(7):1321－1326.

［9］董齊芬，俞立，陳友榮，等.移動(dòng)無線傳感網(wǎng)中的迭代蒙特卡羅定位算法研究［J］.傳感技術(shù)學(xué)報(bào)，2010，23(12):1803－1809.

［10］班艷麗.基于能量有效的ZigBee網(wǎng)絡(luò)路由算法研究［D］.山東大學(xué)，碩士學(xué)位論文，2009.

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

［12］Chen Y R，Yu L，Dong Q F，et al.Distributed Lifetime Optimized Routing Algorithm for Wireless Sensor Networks［J］.Applied Mechanics and Materials，2011，40－41:448－452.