基于最短路徑樹的優化生存時間路由算法*

陳友榮，王章權，程菊花，劉耀林

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

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

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

1 系統假設和鏈路能耗模型

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

典型的無線傳感網節點能耗主要由無線數據收發產生［9］。節點發送模塊的能耗ETx由發送電路電子能耗和信號放大器部分的電子能耗組成。接收模塊的能耗ERx只考慮接收信號時的電路電子能耗。其中，電路電子能耗固定為gEelec，g代表所發送或接收的數據量，Eelec代表收發單位比特數據時電路電子能耗。信號放大器部分的電子能耗與節點發送功率有關。假設節點根據通信距離隨時調整發送功率，于是可定義為與通信距離有關。具體的計算公式如下:

其中dij是發送的距離，dmax是最大通信距離，εfs是放大單位比特信號時所需要的電子能耗。根據式(1)和(2)可知:傳感節點i與節點j之間傳輸g比特數據的能耗取為:

傳感節點i與Sink節點之間傳輸g比特數據的能耗取為:

2 算法的原理

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

假設節點的初始能量為Einital，Ewarning的設定如下:

其中特定正常數δ的作用是確定Ewarning的值。f(x)是一個關于x的函數，x是網絡參數，其設定如下:

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

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

其中，α是能耗因子，θ是發送節點剩余能量因子，β是接收節點剩余能量因子，ηi是節點i類型權重因子，而且這四個因子都是正常數。

在完成此輪網絡權值的更新后，利用最短路徑樹中典型dijkstra算法求源節點到目標節點的最短路徑，輸出算法生成的最優樹。節點一般選擇鏈路能耗小且經過標準節點的路徑發送數據，從而避免警告節點成為樞紐節點，平衡節點能耗，延長網絡生存時間。

3 算法的實現

提出的LORA_SPT是一種集中式路由算法。算法實現主要在Sink節點上完成，其具體的實現步驟如下:

第一步:網絡開始時，每個節點初始化自身的信息。

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

第三步:鄰居節點接收到Sink節點的查詢分組后，將自己的剩余能量Re(i)、所要發送的數據量、位置坐標等信息發送給Sink節點。Sink節點收集所有節點信息(節點位置坐標、剩余能量等)后，啟動LORA_SPT算法。

第四步:根據當前的網絡參數x值，計算f(x)和Ewarning，確定標準節點和警告節點的數量，判斷警告節點數量比例是否大于Ys。大于則x=x+1。

第五步:計算網絡鏈路的權值，通過dijkstra算法計算每個節點的數據發送最短路徑。

第六步:LORA_SPT算法計算完成后，Sink節點以洪泛方式通知網絡中所有節點此時網絡的最短路徑樹。所有節點根據接收到的最短路徑樹，尋找自身到Sink節點的最短路徑，并沿著此路徑發送數據。

第七步:當數據發送一段時間后，重新跳到第二步，Sink節點重新收集各個節點信息，更新網絡鏈路權值。

上述的步驟循環執行，直到傳感節點能量耗盡死亡。具體見如下的LORA_SPT算法偽代碼。

分析LORA_SPT算法的時間復雜性。LORA_SPT算法主要由標準節點和警告節點的確定，鏈路權值的計算和最短路徑的建立三個部分組成。第一部分只需要對所有節點進行判斷，即標準節點和警告節點確定的時間復雜度是Θ(|V|)。第二部分是二層循環計算每個鏈路的權值，即鏈路權值計算的時間復雜度是Θ(|V|2)。第三部分是dijkstra算法，即最短路徑建立的時間復雜度是Θ(|V|2)［11］。總之，LORA_SPT算法的時間復雜度是Θ(|V|2)，和最短路徑dijkstra算法一致。

4 算法的仿真

4.1 仿真參數選擇

由于一般情況下通信能耗遠遠大于其它一些能耗，因此在仿真時，不考慮計算、數據融合、信息查詢分組收發等能耗，也不考慮數據傳輸過程中超時重發、出錯等能耗，只考慮數據無線通信能耗［12］。選擇500×500 m2網絡仿真區域，在該區域內隨機產生均勻分布的30、40、50、60、70、80、90、100 個無線傳感網節點(包括一個Sink節點和其它傳感節點)的位置分布，其中Sink節點固定坐標(250，250)。為了驗證算法的有效性，針對每個固定節點數量的無線傳感網，隨機產生10個不同的節點位置(即不同網絡拓撲結構)，根據表1的仿真參數分別計算這10個網絡拓撲結構不同的無線傳感網生存時間、節點平均能耗和節點平均時延，最后取其平均值作為該節點數量的無線傳感網性能參數的仿真結果值。

表1 仿真參數表

其中，網絡生存時間定義為網絡開始運行到任意一個節點能量耗盡時Sink節點完成的數據收集周期個數(data gathering cycle，DGC)。一個DGC是指網絡中所有節點感知1 000g比特數據，并將數據發送給Sink節點所需要的時間。

節點平均能耗=當一個節點能量耗盡時所有節點的總能耗/(節點數×DGC數)。

節點平均時延=當一個節點能量耗盡時所有節點將數據發送給Sink節點的總跳數/(節點數×DGC數)。

4.2 算法的關鍵參數研究

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

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

4.2.1 α 值的選擇

分析仿真數據可知(以θ=1、β=1為例，如圖1和圖2):當α≥1時，α值越大，節點平均能耗越大，網絡生存時間越小。這是因為:在α≥1時，α值越大，權值函數(7)越加強通信能耗的作用，從而降低其它二個參數(節點剩余能量和鄰居剩余能量)的作用，路徑選擇時會選擇鏈路能耗小但鄰居節點剩余能量也小的鏈路，從而降低了網絡生存時間，也增加了平均能耗。當α＜1時，α值越小，網絡生存時間越小，網絡平均能耗越大。這是因為:當α＜1時，α值越小，權值函數(7)越削弱通信能耗的作用，相應加強其它兩個參數的作用，從而導致鏈路的能耗被忽視，使一些節點直接往剩余能量大但鏈路能耗也大的鄰居節點發送數據，這樣增大了平均能耗，降低了網絡生存時間。

圖1 α對網絡生存時間(DGC)的影響

圖2 α對節點平均能耗的影響

綜上所述，在LORA_SPT算法中，選擇適當的α可以延長網絡生存時間。

4.2.2 θ值的選擇

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

圖3 θ對網絡生存時間(DGC)的影響

圖4 θ對節點平均能耗的影響

綜上所述，在LORA_SPT算法中，選擇適當的θ可以延長網絡生存時間。

4.2.3 β 值的選擇

綜上所述，在LORA_SPT算法中，選擇適當的β可以延長網絡生存時間。

圖5 β對網絡生存時間(DGC)的影響

圖6 β對節點平均能耗的影響

4.3 算法仿真結果比較

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

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

圖7比較了各算法的網絡生存時間，從圖中可知:LORA_SPT算法的網絡生存時間(DGC個數)比LET、PEDAP_PA、Ratio_w和 Sum_w算法更大，是最優的，其次是Ratio_w算法。這是因為該算法綜合考慮鏈路能耗，自身節點能耗和鄰居節點能耗，同時引入類型權重因子，避免剩余能量較小的節點(警告節點)過多參與數據的路由而過早死亡，因此在網絡生存時間方面，LORA_SPT延長了網絡生存時間。

圖7 各算法的網絡生存時間比較圖

圖8比較了各算法的節點平均能耗。從圖中可知:LORA_SPT、LET、Sum_w和Ratio_w算法的節點平均能耗相差不大，但是這四個算法的平均能耗遠低于PEDAP_PA算法。這是因為要避免樞紐節點過早能量耗盡而死亡，LORA_SPT算法在一些路徑選擇上避免該樞紐節點而選擇能耗相對較大的路徑，因此，在能耗方面，LORA_SPT算法在一定程度上將能耗保持在較低的水平。

圖8 各算法的平均節點能耗比較圖

圖9比較了網絡某一個節點能量耗盡時其它節點的平均剩余能量。從圖中可知:LORA_SPT算法平均剩余能量最低、Ratio_w和PEDAP次之，但這三個算法高于LET和Sum_w。這是因為LORA_SPT算法把節點分成兩類節點(標準節點和警告節點)。警告節點的類型權重因子小，周圍鏈路權值變大。在路徑選擇時就盡量避免選擇警告節點，從而每個節點根據剩余能量選擇性參與網絡路由，均衡能量消耗。因此，在能耗方面，LORA_SPT算法均衡了網絡各個節點的能耗。

圖9 各算法的平均節點剩余能量比較圖

圖10比較了各算法的網絡平均時延(跳數)。從圖中可知:LORA_SPT算法的網絡平均時延最小，LET、Sum_w和 Ratio_w算法的網絡平均時延比LORA_SPT算法較大，但這四個算法的平均時延遠低于PEDAP_PA。這是因為LORA_SPT算法考慮了新的權值函數，優化的網絡生存時間，在路徑選擇上節點選擇比較優化的路徑，從一定程序上減低了節點到Sink節點的平均跳數。因此在網絡時延方面，LORA_SPT算法降低了網絡的時延。

圖10 各算法的網絡平均時延(跳數)比較圖

總之，LORA_SPT算法降低了網絡平均時延(跳數)，將節點平均能耗保持在較低的水平，均衡了網絡各個節點的能耗，提高了延長網絡生存時間，比LET、PEDAP_PA、Sum_w和Ratio_w算法更優。

5 總結

LORA_SPT算法構造了基于能耗因子、自身節點剩余能量因子、鄰居節點剩余能量因子和類型權重因子等因子的權值函數，針對不同類型的節點采用不同的權重因子，最后利用dijkstra算法完成最短路徑樹。

LORA_SPT算法是集中式路由算法，需要節點把自身信息匯聚到Sink節點，Sink節點處理完再通知其它節點網絡拓撲結構。集中式路由算法能夠被應用在靜態網絡中，但是不能很好地適應具有動態拓撲特性的無線傳感網。于是下一步工作的重點是研究動態拓撲的無線傳感網分布式路由算法。

［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］劉鐵流，巫詠群.基于能量優化的無線傳感器網絡分簇路由算法研究［J］.傳感技術學報，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］朱藝華，沈丹丹，吳萬登，等.無線傳感器網絡優化生存時間的動態路由算法［J］.電子學報，2009，37(5):1041－1045.

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

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

［10］班艷麗.基于能量有效的ZigBee網絡路由算法研究［D］.山東大學，碩士學位論文，2009.

［11］Dimitri Bertsekas，Robert Gallager.盧剛，王康，譯.數據網絡(第二版)［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.