面向智慧園區的WSN路由優化算法

丁偉 ，李樹泉 ，李思維 ，唐良瑞 ，孫丹丹

（1.華北電力大學新能源電力系統國家重點實驗室，北京 102206；2.國家電網公司客戶服務中心，天津 300012；3.北京國電通網絡技術有限公司，北京 100070）

面向智慧園區的WSN路由優化算法

丁偉1，李樹泉2，李思維3，唐良瑞1，孫丹丹3

（1.華北電力大學新能源電力系統國家重點實驗室，北京 102206；2.國家電網公司客戶服務中心，天津 300012；3.北京國電通網絡技術有限公司，北京 100070）

為解決智慧園區中無線傳感器網絡（WSN）的能耗不均衡問題，構建了路由代價函數，并提出了一種新的能耗均衡路由算法。該算法結合智慧園區中無線傳感器網絡的特點，綜合考慮節點地理位置和剩余能量來構建路由代價函數。傳感器節點通過選擇其鄰居節點中路由代價最小的節點進行數據轉發。仿真結果表明，該算法可以有效節約網絡能耗，同時延長了網絡的生命周期。

智慧園區；無線傳感器網絡；路由代價；網絡生命周期

1 引言

隨著國家電網公司提出將國家電網公司客戶服務中心（以下簡稱國網客服中心）南北園區建設為“國家電網能源技術與服務創新園區”的目標，實現對園區各種信息的實時監測，廣泛集成能量、環境等信息變得刻不容緩。在這種情況下，以低功耗、低成本為優勢的無線傳感器網絡（wireless sensor network，WSN）作為其他組網方式的有效補充，逐漸獲得了廣泛應用。無線傳感器網絡是由多個采集節點和匯聚（sink）節點構成的自組織網絡，進而通過多跳轉發的方式將采集到的數據發送到sink節點，由sink節點實現向上傳送和數據存儲［1-2］。而路由算法是WSN網絡層的核心，它直接決定數據分組從源節點到目的節點的路徑，從而直接影響網絡的功耗。因此，對智慧園區中無線傳感器網絡的路由問題進行研究是十分必要的。

由于傳感器節點主要依靠電池供電，節點能量受限，因此需要充分實現節點能耗的有效性。最小能耗（minimum energy consumption，MEC）路由［3］單純追求 節 點傳輸能耗的有效性，但常常導致處于最小能耗路徑上的節點轉發任務重，能量消耗過快而過早死亡，最終引起網絡癱瘓。為了實現能耗的均衡性，在進行路由選擇時必須充分考慮節點的剩余能量因素。但是，過多選擇剩余能量較多的節點作為下一跳會導致數據分組的傳輸路徑過長，不能充分實現節點能量的有效性。因此，在進行路由算法設計時，兼顧網絡能耗的有效性和均衡性，是目前主要的研究方向。ECBR算法［4］綜合考慮下兩跳節點的信息，構建了一種新的能量代價函數，較好地實現了節點能耗的有效性和均衡性；ELACO［5］路由算法綜合考慮了節點的能量和地理位置信息，進而智能地搜索從source節點到sink節點的最優路徑，因而有效地延長了網絡的生命周期，實現了網絡能量的均衡消耗；UCPC算法［6］采取如下策略：將網絡分成不均勻的虛擬塊，并且在簇頭路由時考慮節點位置和剩余能量的影響，構建基于節點位置和剩余能量的隸屬度函數，并將二者進行融合判決，并根據最大隸屬度原則選擇父節點，優化路由選擇。EETMO［7］算法以節點剩余能量和節點到基站的距離兩個特征參量建立隸屬度函數，利用三角模融合算子進行判決。UCRA［8］算法是一種基于權值機制的非均勻分簇路由算法，其采用基于權值的局部競選簇首策略，改善了熱區問題，有效均衡了網絡節點能耗，延長了網絡生存時間。MECT［9］算法基于最小能耗樹，并在構造樹的過程中考慮到節點的剩余能量，在減少能耗的同時保證了能耗均衡。但以上算法或計算復雜度較大，或更多關注節點能耗的均衡性，并不適合應用于智慧園區中的WSN。

基于以上分析，針對智慧園區中WSN的特點，本文提出一種基于路由代價的WSN路由優化算法（optimized routing algorithm based on routing cost，RCOR）。該算法綜合考慮節點的地理位置信息和剩余能量，構建節點的路由代價函數。傳感器節點通過計算其鄰居節點的路由代價，進而選取路由代價最小的鄰居節點作為下一跳節點，進行數據轉發。仿真結果表明，該算法有效節約了網絡能耗，同時延長了網絡的生命周期。

2 系統模型與定義

2.1 網絡模型

無線傳感器網絡主要應用于南北園區內各種信息的監測采集，將各種信息采集終端視為傳感器網絡的普通節點，將就地控制中心視為sink節點，網絡中大量的普通節點和sink節點則構成了智慧園區的信息采集網。

本文所研究的無線傳感器網絡均假設具有以下特點：

·某個區域內隨機部署了多個完全相同的傳感器節點，每個節點都具有功率控制能力，并調節至某一固定發送半徑R；

·唯一的sink節點部署在固定位置，且能量不受限制；

·所有的傳感器節點初始能量有限且相同，并且能實時獲取自己的剩余能量；

·每個傳感器節點可通過接收信號的強度估算自己到相鄰節點的距離。

2.2 能耗模型

本文采用如下的無線通信能量消耗模型［7］，當傳感器節點在傳輸l bit數據且傳送距離為d時，發送端所消耗的能量為：

接收端所消耗的能量為：

其中，Eelec表示發射機和接收機電路處理單位比特數據所消耗的能量；d0為功率放大損耗采用不同模型時的距離閾值當傳輸距離小于距離閾值d0時，采用自由空間模型，Efs是自由空間模型下功率放大的能量消耗；當傳輸距離大于距離閾值d0時，采用多徑衰減傳輸模型，Emp是多徑衰減模型下功率放大的能量消耗。

為了更清楚地描述路由算法，下面給出鄰居節點以及前向鄰居節點的定義。

定義1 （鄰居節點）節點i的鄰居節點集定義為：

其中，d（i，j）為節點 i和 j之間的距離。

定義2 （前向鄰居節點）節點i的前向鄰居節點集定義為：

其中，d（i，s）、d（j，s）分別表示節點 i、j到 sink 節點的距離。該節點集包含了與節點i直接通信的所有鄰居節點，而且排除了節點i后向傳輸的可能，從而保證了不會有環路出現。

3 路由代價

在進行WSN路由算法設計時，只關注節點能耗的有效性，極易導致最小能耗路徑上的節點產生擁塞，進而導致網絡生命周期降低。反之，只追求節點能量的均衡消耗，將導致數據分組轉發路徑過長，降低節點能耗的有效性。因此，為節約網絡能耗并實現能耗的均衡性，必須合理匹配節點能耗的有效性和均衡性。基于以上需求，本文提出了前向傳輸節點這一概念，并在該條件下定義了一種新的路由代價函數，綜合考慮了節點位置和剩余能量兩個因素，從而保證了能量的高效利用，實現網絡能耗的均衡。

3.1 節點靠近最短路徑程度

考慮節點傳輸范圍有限等原因，大多數節點通常不能直接與sink節點進行通信，而需要依靠其余節點采用多跳轉發的方式進行數據傳輸。為此，從降低節點能耗的角度出發，建立數據分組在WSN中的發送路徑，保證了當前節點轉發數據分組給下一跳節點時所消耗的能量較少。

由最小能耗模型知，如果數據分組的每一個轉發節點都在源節點到sink節點的連線上，則數據分組在傳輸過程中消耗的總能量最少。然而實際上各節點的鄰居節點并不都是在該連線上，因此節點靠近最短路徑的程度可作為衡量節點能耗的重要指標。節點位置示意如圖1所示，源節點i的數據分組要想到達sink節點，需要被轉發至i的鄰居節點。節點靠近最短路徑程度的定義如下：

其中，d（i，j）、d（i，sink）、d（j，sink）分別表示節點 i到節 點 j的距離、節點i到sink節點的距離以及節點j到sink節點的距離。由式（5）可知，節點i通過節點j進行數據轉發時，CD（j）越大，表示節點j越靠近最小能耗路徑，即被選為下一跳節點的可能性越大，從而節約節點能耗。

圖1 節點位置示意

3.2 前進距離

在無線傳感器網絡中，數據分組在向前傳輸時始終是向sink節點靠近的，也即每一跳向sink節點靠近的距離越大，越有利于節約網絡能耗。由于各節點到sink節點距離大不相同，因此需對其進行統一處理，進而在進行下一跳節點的選擇時，定義數據分組的前進距離如下：

由式（6）可知，節點數據分組單跳前進距離越大，越有利于降低網絡能耗。

3.3 節點剩余能量

在式（5）和式（6）的作用下，數據分組總是沿著能耗近似最小的路徑進行轉發，這會導致處于轉發路徑上的某些節點轉發任務過重，節點能量消耗過快，甚至節點死亡。為此，本文從能量均衡的角度出發，基于節點剩余能量構建節點剩余能量函數，以均衡網絡的能耗，實現網絡能耗的均衡性。

其中，Er（j）是節點 j的剩余能量，Eini是節點 j的初始能量。

根據式（7），節點j的剩余能量越多，其被選作下一跳轉發節點的可能性越大，越有助于均衡網絡的能耗，據此可以為節點i進行路由選擇提供依據。

3.4 路由代價函數

式（5）和式（6）從降低傳輸能耗的角度出發，轉發節點越靠近最短路徑，數據分組單跳前進距離越大，到下一跳可選節點傳輸能耗越低，說明其越適合承擔數據的轉發。式（7）從均衡網絡能耗的角度出發，考慮轉發節點當前的剩余能量，其更直接地反映了該節點進行數據轉發的能力，可以直接用來選擇下一跳節點。為此，合理地將以上3個因素進行融合，可作為數據分組路由的依據。為此定義如下的路由代價函數：

由式（8）可知，路由代價不僅保證數據分組選擇鄰居節點中向sink節點最短路徑方向上的節點作為下一跳，而且保證在避免路由回傳、環路的情況下繞過低能量節點進行數據轉發，既有效地節約了網絡能量，又充分實現了網絡能耗的均衡性。

4 算法實現

面向智慧園區的WSN路由優化算法主要包括以下幾個步驟。

（1）鄰居發現：在網絡初始階段，所有傳感器節點首先估算自身到sink節點的距離，然后傳感器節點以最大通信半徑R為通信半徑，確定其鄰居節點，進而根據式（4）確定前向鄰居節點。

（2）能量代價計算：基于鄰居節點信息表（包括節點的前進距離、節點靠近最短路徑程度、節點的剩余能量），根據式（8）計算每個前向鄰居節點的路由代價。

（3）路由選擇：當節點進行數據轉發時，若sink節點位于轉發節點的通信半徑范圍外，則選擇前向鄰居節點中路由代價最小的節點作為下一跳；若sink節點位于節點的鄰居節點范圍內，則直接將數據發送給sink節點。

由本文的路由算法可知，傳感器節點無需掌握整個網絡的拓撲結構與狀態參數，僅需要鄰居節點的信息即可做出路由決策，路由算法具有較小的實現開銷和更好的可擴展性［10］，適用于大規模網絡。

5 仿真實驗

為了驗證算法的有效性，本文采用MATLAB對RCOR算法進行了實驗仿真，同時將RCOR算法與最小能耗（MEC）路由算法和最大剩余能量（MREBR）［11］算法進行了對比。仿真中，節點隨機均勻分布在正方形區域中，所有節點一旦放置就不再移動。仿真參數設置見表1。

表1 仿真參數設置

表2是不同節點死亡率下3種算法所經過輪數的對比情況。可以看出，RCOR算法在不同節點死亡率的情況下，其運行的輪數都高于另外2種算法，有效地延長了網絡的生命周期。這是因為MEC算法只考慮從源節點構建到sink節點的最短路徑，導致某些節點轉發任務重，能量消耗過快，節點過早死亡，因而經過輪數最短。MREBR算法只是單純考慮節點剩余能量因素進行路由選擇，導致路由路徑過長，因此其經過的輪數較長。RCOR算法綜合考慮節點位置和剩余能量，有效地實現了節點能耗有效性和均衡性的結合，因此其網絡生命周期最長。

表2 網絡生命周期對比

圖2為MEC、RCOR和 MREBR 3種算法節點的端到端平均能耗隨網絡規模的變化情況對比。不難看出，MEC算法的端到端平均能耗在不同節點數量下始終最低。MREBR算法因單純考慮節點的剩余能量以均衡網絡的能耗，故其路由路徑較長，最終導致其端到端平均能耗最高。而本文算法實現了能耗有效性和均衡性的平衡，故端到端平均能耗介于MEC算法和MREBR算法之間。

圖2 端到端平均能耗對比

圖3 節點平均剩余能量對比

圖3對網絡中最開始有節點死亡時傳感器節點的平均剩余能量進行了對比。由圖3可知，MEC算法平均剩余能量最高，RCOR算法次之，而MREBR算法最低。這是因為MREBR算法以節點剩余能量最多為依據來確定轉發節點，以均衡網絡的能量消耗，故其平均剩余能量最低。而RCOR算法除了考慮節點剩余能量外，還將節點位置考慮在內，實現了網絡能耗有效性和均衡性的結合，故性能次優。MEC算法只考慮建立最短路徑，使得最短路徑上的節點過早死亡，因此其平均剩余能量指標最高。

6 結束語

結合智慧園區中WSN的特點，針對現有路由算法的不足，提出了一種新的基于路由代價的無線傳感器網絡路由算法。該算法以降低和均衡網絡能耗為目標，綜合考慮節點地理位置和剩余能量，并構建了路由代價函數。傳感器節點依據路由代價最小原則，從前向鄰居節點中選擇下一跳節點進行數據轉發。仿真結果表明，該路由算法能夠有效節約網絡的能耗，延長網絡的生存時間。

［1］REN F，ZHANG J，HE T，et al.EBRP：energy-balanced routing protocol for data gathering in wireless sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2011，22（12）：2108-2125.

［2］CHIANG S S，HUANG C H，CHANG K C.A minimum hop routing protocol for home security systems using wireless sensor networks［J］.IEEE Transactions on Consumer Electronics，2007，53（4）：1483-1489.

［3］SINGS S，WOO M，RAGHAVENDRA C S.Power-aware routing in mobile Ad Hoc networks ［J］.The Proc of Mobicom，1998，23（3）：181-190.

［4］江海峰，錢建生，孫彥景，等.WSN中基于能量代價的能量優化路由算法［J］.計算機科學，2012，39（1）：73-76.JIANG H F，QIAN J S，SUN Y J，et al.Energy cost based energy optimized routing algorithm in WSN ［J］.Computer Science，2012，39（1）：73-76.

［5］王小明，安小明.具有能量和位置意識基于ACO的WSN路由算法［J］.電子學報，2010，38（8）：1763-1769.WANG X M，AN X M.An energy and location aware ACO based routing algorithm for wireless sensor networks ［J］.Acta Electronica Sinica，2010，38（8）：1763-1769.

［6］孫毅，盧可，唐良瑞.面向用電信息采集的WSN非均勻分簇多跳路由算法 ［J］. 電力系統保護與控制，2013，41（10）：56-61.SUN Y，LU K，TANG L R.An uneven clustering multi-hop routing algorithm for power information collection ［J］.Power System Protection and Control，2013，41（10）：56-61.

［7］唐良瑞，馮森.WSN中基于三角模融合算子的路由算法［J］.計算機工程，2012，38（12）：60-63.TANG L R，FENG S.Routing algorithm based on triangle module fusion operator in WSN ［J］.Computer Engineering，2012，38（12）：60-63.

［8］喬學工，王哲，王華倩，等.基于權值的分均勻分簇路由算法［J］.傳感技術學報，2014，27（1）：107-112.QIAO X G，WANG Z，WANG H Q，et al.An uneven cluster routing algorithm based weight［J］.Chinese Journal of Sensors and Actuators，2014，27（1）：107-112.

［9］彭煜，張華忠，魏曉鎮.WSN中一種基于最小能耗樹的路由協議［J］.計算機工程與應用，2011，47（6）：109-112.PENG Y，ZHANG H Z，WEI X Z.Routing protocol based on minimum energy consumption tree for wireless sensor networks［J］.Computer Engineering and Applications，2011，47（6）：109-112.

［10］張德干，趙晨鵬，李光，等.一種基于前向感知因子的WSN能量均衡路由方法［J］.電子學報，2014，42（1）：113-118.ZHANG D G，ZHAO C P，LI G，et al.A kind of routing protocol based on forward-aware factor for energy balance ［J］.Acta Electronica Sinica，2014，42（1）：113-118.

［11］HAN K H，KO Y B，K J H.A novel gradient approach for efficient data dissemination in wireless sensor networks ［C］／／IEEE 60th Vehicular Technology Conference，September 26-29，2004，Washington，USA.New Jersey：IEEE Press，2004：2979-2983.

An optimized routing algorithm in WSN for smart park

DING Wei1，LI Shuquan2，LI Siwei3，TANG Liangrui1，SUN Dandan3
1.State Key Laboratory of Alternate Electrical Power System with Renewable Energy Sources，North China Electric Power University，Beijing 102206，China 2.State Grid Customer Services Center，Tianjin 300012，China 3.Beijing GuoDianTong Network Technology Co.，Ltd.，Beijing 100070，China

To solve the energy problem in wireless sensor networks used for smart park，an optimized routing algorithm based on routing cost in WSN was proposed.According to the characteristics of smart park，the algorithm took a comprehensive consideration of the remaining energy and geographical location of nodes and exploited a new routing cost function.The sensor nodes selected the node with the minimum routing cost to forward the packets.Simulation results show that the algorithm significantly reduces the energy consumption of the network and extends the network lifetime effectively.

smart park，wireless sensor network，routing cost，network lifetime

TN 915.853

A

10.11959／j.issn.1000-0801.2016070

2015-09-20；

2016-02-01

丁偉（1991-），男，華北電力大學碩士生，主要研究方向為無線傳感器網絡路由和電力系統通信。

李樹泉（1964-），男，國家電網公司客戶服務中心高級工程師，主要從事電力工程、能源互聯、低碳節能等方面的研究工作。

李思維（1988-），男，北京國電通網絡技術有限公司工程師，主要從事智能微電網、用電及需求側等相關工作。

唐良瑞（1968-），男，華北電力大學教授、博士生導師，主要研究方向為電力系統通信、無線通信以及光纖通信。

孫丹丹（1991-），女，現就職于北京國電通網絡技術有限公司，主要研究方向為電力信息通信、信息安全。