可充電無線傳感網絡能量均衡路由算法

謝小軍，于 浩，陶 磊，張信明

(1.國家電網安徽省電力公司 信息通信分公司， 合肥 230061； 2.中國科學技術大學 計算機科學與技術學院，合肥 230027)

可充電無線傳感網絡能量均衡路由算法

謝小軍1，于 浩1，陶 磊2，張信明2*

(1.國家電網安徽省電力公司 信息通信分公司， 合肥 230061； 2.中國科學技術大學 計算機科學與技術學院，合肥 230027)

(*通信作者電子郵箱xinming@ustc.edu.cn)

針對可充電無線傳感網絡中的能量均衡路由問題，提出在穩定功率無線充電和監測數據收集網絡場景下的多路徑路由算法和機會路由算法，以實現網絡的能量均衡。首先，通過電磁傳播理論構建了無線傳感節點的充電和接收功率關系模型；然后,考慮網絡中無線傳感節點的發送能耗和接收能耗, 基于上述充電模型將網絡能量均衡的路由問題轉化為網絡節點運行時間的最大最小化問題，通過線性規劃得到的各鏈路流量用以指導路由中數據流量分配；最后，考慮一種更加現實的低功耗的場景，并提出了一種基于機會路由的能量均衡路由算法。實驗結果表明，與最短路徑路由(SPR)和期望周期最短路由(EDC)算法相比較，所提出的兩種路由算法均能有效提高采集能量的利用率和工作周期內的網絡生命周期。

能量均衡路由；可充電無線傳感網絡；機會路由；低功耗傳感網絡

0 引言

無線傳感器網絡(Wireless Sensor Network, WSN)是由大規模的微型、智能傳感器節點組成無線自組織網絡系統，網絡中的節點通過相互協作將監測到的數據信息傳送至網關(sink)節點進行處理。無線傳感網中的節點能量有限，為了提升節點的運行時間和網絡壽命，為無線傳感節點配備能量捕獲模塊和可充電電池，稱為可充電無線傳感節點。當可充電無線傳感節點能夠捕獲的能量有限時，節點在能量耗盡前進行網絡中的數據采樣、接收和傳輸等正常操作，在能量耗盡后進入低功耗模式睡眠狀態，此時，能量均衡路由關系到網絡中節點的可運行時間，即網絡生命周期，仍然是該網絡中需要關注的重要問題。本文研究可充電無線傳感網絡能量均衡路由問題。

關于能量均衡路由，文獻[1]提出了一種基于混合傳輸的能量均衡方法避免無線傳感網中的能量空洞。混合傳輸指網絡中節點的無線收發器具有不同傳輸功率。在數據收集傳感網網絡中，靠近sink節點的無線傳感器由于接收更多的來自遠處傳感節點的數據會更快地耗盡能量，文獻[1]提出增大遠處的節點的傳輸功率，同時概率地選擇傳輸的接收節點，減小離sink較近節點的通信負載，推遲能量空洞的出現，延長網絡壽命。文獻[2]提出一種簇規模自適應調節的能量均衡分簇路由協議，協議改進了低能耗自適應集簇分層(Low Energy Adaptive Clustering Hierarchy, LEACH)算法[3]，根據節點離匯聚點的距離、剩余能量及分布密度來構造規模不等的簇，避免了低能量節點被選為簇首，達到網絡能量均衡。文獻[4]提出一種基于學習自動機的能量均衡分簇算法：綜合考慮節點剩余能量和節點密度,利用學習自動機與周圍環境進行信息交互和動作獎懲，選擇出相對較優的簇頭；根據簇首與基站距離和其節點密度構造大小非均勻的簇，實現不同位置不同網絡疏密程度下簇內和簇間能耗互補均衡，構造了基于簇首剩余能量、簇內節點密度和傳輸距離的評價函數，并運用貪婪算法選擇出最優中轉簇首進行多跳傳輸。文獻[5]構造了一種全局能量優化函數，并考慮網絡中節點的剩余能量情況，建立路由能耗和路由剩余能量的優化度函數來評估對目標函數的優化程度，通過構造優化度函數的評價函數來求解多目標優化問題，得到能量均衡的最優路徑。

上述工作主要考慮自組織網絡中的能量均衡路由問題，另一些研究將能量均衡路由和無線傳感節點的可充電特性結合起來考慮，如：文獻[6]提出了一種移動充電模型和路由方法實現網絡中節點的成功數據上傳和能量均衡；文獻[7]提出另一種數據收集模型，當移動sink移動到無線傳感節點附近時通過單跳或多跳的方式傳輸數據，綜合考慮了路徑規劃、數據路由和能量均衡問題提出了一種綜合解決方案。

現有的相關工作關于能量均衡路由算法中，基于分簇的解決方案通常采用分布式算法，無法實現全局最優；同時，某些能量模型[1,5]只考慮了節點傳輸能耗而忽略了接收能耗；路由算法計算的是最優路徑，忽視了多路徑路由的可能性。針對上述模型和算法中存在的問題，本文結合考慮了一種無線能量采集場景，提出基于鏈路流量分配多路徑路由算法和機會路由[10-11]算法，實現可充電傳感網絡的能量均衡，主要的工作在于：

1)在可預測的能量補充流的基礎上實現能量均衡路由；

2)利用機會路由應對無線傳感網絡信道時變和丟失特性和其天然的負載均衡特性，達到能量均衡路由的目的；

3)使用更加精確的能量模型，考慮節點傳輸及接收能耗；

4)能量均衡路由算法是全局最優的。

1 網絡模型與能量均衡問題

1.1 可充電無線傳感器能量傳播模型

本文研究的基于高壓電線取電的可充電無線傳感器網絡中，取電、能量發射和接收裝置的原理如圖1所示，其中能量接收裝置與距離能量發射的距離由無線充電的方式所決定。不同的無線充電方式的傳輸距離、功率、頻率和充電效率也不相同。本文研究基于無線電波的充電方式，其有效充電距離可達數十米，適用于分布距離較大的無線傳感器網絡。首先研究單個取電-充電裝置對于多個無線傳感器節點的充電模型。在電能發射裝置通過連續發射電磁波給節點無線充電的過程中，由于電磁波在空間傳播時會產生衰減，這種衰減與發電裝置和傳感節點間的距離、傳播空間環境相關。

根據電磁傳播理論中的Friis傳輸公式，可以得到電磁波在理想空間中的傳輸特性。空間中任意一點處的電磁波功率P1與電磁波發射源發射功率P0的關系式如下：

P1=G1G0P0(λ/(4πd))2

(1)

其中：G1和G0分別表示接收天線和發射天線的增益；d表示接收點離發射源的距離；λ是傳輸的電磁波的波長。

圖1 能量獲取和發射裝置

1.2 無線傳感網絡機會路由模型

機會路由是一種適用于不可靠網絡的路由技術，它利用多個可能提供相似傳輸質量的下一跳節點，可以顯著提高網絡吞吐量、減少傳輸次數和網絡能量消耗，并具有天然的負載均衡特性[10-11]。機會路由根據介質訪問控制(MediumAccessControl,MAC)協議的不同實現方式也有所變化，但最關鍵的部分是候選集的選擇。

候選集是由算法指定的有資格轉發數據包的下一跳節點集合。在非低功耗場景下，由于候選集中的節點收到數據包的概率大于一個節點收到數據包的概率，因此機會路由可利用無線網絡的廣播特性來提高數據包投遞的成功概率。在低功耗場景下，特別是節點的睡眠調度周期很長時[10]，節點很少在同一時段處于活躍狀態，此時發送方通過依次單播給候選集中的節點需要傳輸的數據包，直到該跳傳輸成功為止。

1.3 可充電無線傳感網絡模型

假設一個基于周期性數據收集可充電無線傳感網絡G=(N,A,R),其中：N是所有無線傳感節點的集合，包括N-1個常規節點和1個網關節點，也稱為sink節點用于數據匯總和上傳至互聯網；A是所有節點間鏈路的集合，稱兩個無線傳感節點間有一條鏈路當且僅當它們互相在對方的傳輸范圍內，此時這兩個節點也同時稱為對方的鄰居；R是電能采集和發射設備的集合。

1.4 問題

在上述模型描述的可充電無線傳感器網絡中，由于無線傳感器的位置相對固定，在給定的各充電裝置的發射功率下，各傳感節點在每個觀察窗口內能夠采集的能量可以預測且相對穩定。在這種情況下，如果對于該數據收集的傳輸路徑設置不當，容易造成網絡中的無線傳感器能量失衡。本文研究可充電無線傳感網中的傳輸(路由)問題，以達到網絡能量的均衡，其重要性體現在：

1) 傳輸、接收數據包所消耗的能量與從無線電波中采集的能量均衡。如果消耗的能量速率大于采集能量速率，那么節點將會在有限的時間內死亡；反之，節點的能量將會一直處于電池容量上限，浪費了充電設備所發射的能量。

2) 網絡中各無線傳感節點之間的能量均衡。

如果上述條件無法滿足，則考慮如何最小化節點間的能量凈消耗速率，延長網絡的生存周期。

2 能量均衡分析模型和路由算法

根據1.1節的充電損耗模型式(1)，假設網絡內的每個無線傳感節點i在同一時刻只能由同一個充電設備為其充電，并令i在每個周期t內選擇對其充電功率最大的為其充電。記傳感節點i和充電發射裝置r間的距離為di,k，則i在時段t內的充電功率可通過式(2)推導得到：

(2)

即節點i轉發的流量是自身產生的流量和轉發其他節點的流量之和。其數據流速率的形式為：

(3)

其中候選中繼集合Si代表i轉發數據的鄰居節點集合。數據流量均衡模型如圖2所示。

圖2 數據流量均衡模型

本文假設無線傳感節點以低功耗和頻率采集監測數據，故忽略不計節點的數據采集功耗，則在t內i的能量消耗速率為：

(4)

(5)

(6)

易知問題一是一個關于變量qji(t)具有等式約束條件的max-min線性規劃(LinearProgramming,LP)問題，求解問題一可以利用Matlab中現有的線性規劃工具fminimax。

3 低功耗傳感網能量均衡

在無線傳感網絡中，為了進一步降低網絡能耗、延長網絡生存周期，通常采用低功耗MAC協議使得節點在非活躍狀態關閉無線收發器以減少不必要的空閑偵聽能耗。在可充電傳感網中，節點采用低功耗協議能夠在相同的情況下相比不采用低功耗協議的場景減少充電頻率。本章研究在可充電低功耗傳感網中的能量均衡路由問題。

3.1 低功耗模式和機會路由

現有研究表明，傳感節點在無線通信模塊發送、接收、空閑、休眠狀態中平均消耗的能量占總耗能的80%以上[8]。低功耗模式指無線傳感節點能夠在空閑時段關閉無線通信模塊，進入睡眠模式，故低功耗模式在數據傳輸非密集型的無線傳感網中能夠顯著減少網絡能量消耗。節點只能夠在活躍的狀態下發送、接收或監聽到數據包。周期性睡眠調度是指節點周期性、定時地睡眠、醒來，在這種睡眠調度機制下睡眠時間和調度周期的比值稱為節點低功耗模式的占空比。

在占空比較低的情況下，節點同時醒來的概率很低，發送方為了成功傳輸數據包，需要持續發送引言包直到一個接收方醒來并回復確認包(ACKnowledgement,ACK)。如果發送方只選擇一個下一跳節點，那么當該接收節點的一個活躍周期結束，發送方需要等待一個調度周期發送剩余的數據包，在不可靠鏈路傳感網中甚至需要等待多個調度周期，增加了端到端時延。機會路由允許一個發送方選擇一個鄰居候選集而不只是一個下一跳以轉發數據包，在低占空比情景下，候選集中的節點依次醒來，發送方按照其醒來次序分別傳送數據包直到發送成功為止。

3.2 能量均衡候選集選擇

機會路由能夠有效降低等待延時，減少成功傳輸一個數據包所需的傳輸次數。參照第2章的算法，本文嘗試利用流量分配以實現能量均衡路由，然而低功耗傳感網中睡眠調度和機會路由帶來的挑戰在于，當一個發送方的候選節點集確定后，經過該發送方的數據流的分配也同時確定，這與候選集中節點的醒來次序、發送方到候選集中各節點的鏈路質量相關。因此本文研究在無法實現最優能量均衡的路由策略情況下，如何為網絡中的每個節點確定轉發候選集以達到較優的網絡均衡。

首先考慮發送方需要發送一個數據包的情況，在流量分配策略中考慮多個數據包的情況。發送方s的轉發候選集按其醒來次序遞增排序記為集合fS={n1,n2,…,nK}，到候選集節點的鏈路質量分別記為p1,p2,…,pK，則最終候選集中第i個節點的理論期望轉發概率為：

(7)

即s到前i-1個接收方的數據傳輸都沒成功并在第i個節點處成功傳輸。然而在實際環境中，傳感節點的時鐘并不同步，隨著時間增加，時鐘之間可能產生漂移。當時間足夠長時，可以將固定周期調度的各節點間的鄰居發現時延近似為隨機均勻分布，此時，候選集中第i個節點的期望被選中的概率只與發送方到自己的鏈路質量相關[9]，有：

(8)

考慮經過s的流量為Qs，則在s的轉發候選集策略為fs的情況下，根據式(4)，其候選集中第i個節點ni的期望流量為：

Qni=P(i)·Qs

(9)

此時將問題一轉化為一個最優求解問題：如何在可充電無線傳感網絡的每個周期中為每一個節點i選擇一個最優轉發候選集fi(t)，以實現機會路由下的最優網絡能量均衡。形式化地表示該問題為問題二：

(10)

在問題二中，與求解問題一最大的不同在于問題二中的流量分配是由機會路由下的候選集選擇、節點醒來時間和優先級考慮下的流量期望決定，而不是確定的多徑路由分配。這種不確定性是由機會路由的屬性所決定的。與第2章同理，使用LP可以解決該問題。

4 實驗結果與分析

4.1 實驗設置

本節中采用以Matlab為平臺的仿真實驗驗證能量均衡路由協議在普通可充電傳感網中和低功耗可充電傳感網中的效果，在500m×500m的場地中隨機布置n-1個可充電無線傳感節點，網關節點位于坐標(0,0)，采用自由空間傳播損耗模型模擬不可靠鏈路。考慮一種一對一的簡單充電場景：每個充電設備位于平均高度h=20 m的高壓電線上以恒定功率在每個周期為各傳感節點提供能量，能量獲取由式(2)計算得出。數據包傳輸和接收單位數據包能耗計算式分別為erx=eR和etx=eT+εamp·dα。在低功耗場景下設置節點的調度周期和占空比分別為1s和50%。實驗的具體參數設置參考表1。本文提出的能量均衡路由協議和低功耗場景下的分別記為能量均衡路由(EnergyBalancedRouting,EBR)和低功耗能量均衡路由(EBRforLowpowerWSN,EBR-L)，設置的實驗對比對象分別為最短路徑路由(ShortestPathRouting,SPR)和期望周期最短路由(ExpectedDuty-Cycledwakeupsminimalrouting,EDC)[9]。在SPR中，節點選擇以節點剩余能量占電池最大電量比重倒數為基準(metric)的到達網關節點的最短路徑，以實現能量均衡路由；在EDC中，考慮了低功耗和機會路由的影響，選擇期望時延最小的候選集。

表1 實驗參數

4.2 評價標準

本文以歸一化網絡生命周期為評價標準評估路由以網絡能量均衡為目標的策略好壞，歸一化網絡生命周期定義為網絡中所有節點的平均工作時長和總周期長度的比值(不計充電周期)，以圖3為例具體解釋：節點i在第一個觀察周期[0,t]的前1/3充電，電量從0升至E0，隨后進行數據傳輸、轉發操作，在t1時間消耗完能量，提前結束了工作周期；在第二個觀察周期中，i獲得了E1能量并消耗了E1-E2能量，在此周期結束時仍有電量剩余。則i在前兩個周期的歸一化網絡生命周期為(t1-t/3+2t/3)/(4t/3)。

圖3 節點i的電池能量周期

圖4描述了網絡的平均歸一化生命周期隨著節點數目的變化，隨著節點數目的增加，EBR和SPR的歸一化生命周期都表現出遞減趨勢，這是由于節點數目的增加導致了距離網關節點更近的節點增加了更多的轉發任務，導致這些節點的每個周期內工作周期減少，進而降低了網絡的平均生命周期。EBR的歸一化生命周期總是優于SPR，因為SPR雖然選擇能量剩余多的節點作為轉發節點，在一定程度上緩解了網絡負載不均衡，但是EBR更多地考慮了多個轉發節點的負載分配對于網絡均衡的影響而不僅僅是單個下一跳，故EBR能夠實現更好的能量均衡。

4.3 結果分析

圖5描述了低功耗場景下的網絡平均歸一化生命周期隨著節點數目的變化，與圖4相似呈遞減趨勢。EBR-L優于EDC的原因是后者更多地考慮了時延而非能量均衡。值得注意的是，與圖4相比，EBR-L的歸一化生命周期均優于EBR，這是因為EBR的場景從廣義上來說是多路徑路由而不是機會路由，而在低功耗的機會路由下，EBR-L在沒有任務時可以進入休眠狀態，從而節約了空閑偵聽的能量。

圖4 歸一化生命周期隨節點數目變化

圖 5 低功耗場景歸一化生命周期隨節點數目變化

對比圖4～5，可以發現EBR比EBR-L在相同的配置下具有更長的網絡生命周期，這是因為首先本文在實驗中只考慮收發數據包的能耗，其次從信息論角度考慮，EBR使用全局網絡信息進行優化，而EBR-L是分布式的路由算法，前者比后者擁有更多的信息故更優。

考慮兩種算法的復雜度，EBR采用線性規劃算法，時間復雜度為n的多項式級別；EBR-L在前者的基礎上增加了關于轉發候選集的約束條件，搜索空間大于EBR，但仍為n的多項式級別時間復雜度。

5 結語

為解決可充電無線傳感網絡中的能量均衡路由問題，分別針對非低功耗場景和低功耗場景，本文提出基于多路徑路由和機會路由的路由協議。前者根據充電速率、自身電池剩余電量、接收和發送數據包的單位能耗等信息，通過全網的線性規劃為每個參與轉發的節點的候選集規劃鏈路流量；后者為每個轉發者選擇一個能耗最優的候選集，在機會路由框架下延長網絡壽命。實驗結果表明，提出的兩種路由算法能夠有效地實現網絡均衡。接下來將針對復雜移動場景下的可充電無線傳感網絡的路由問題進行研究。

)

[1] 夏先進,李士寧,張羽,等.一維傳感網中混合數據傳輸的能量均衡[J].軟件學報,2015,26(8):1983-2006.(XIAXJ,LISN,ZHANGY,etal.Energybalanceofmixeddatatransmissionin1Dsensornetworks[J].JournalofSoftware, 2015, 26(8): 1983-2006.)

[2] 吳華君,張自力,李衛.一種適用于煤礦井下無線傳感網的能量均衡路由協議[J].計算機科學,2011,38(4):145-150.(WUHJ,ZHANGZL,LIW.Energy-balancedroutingprotocolforwirelesssensornetworksincoalmine[J].ComputerScience, 2011, 38(4): 145-150.)

[3]HEINZELMANWR,CHANDRAKASANA,BALAKRISHNANH.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworks[C]//HICSS’00:Proceedingsofthe33rdHawaiiInternationalConferenceonSystemSciences.Washington,DC:IEEEComputerSociety, 2000: 8020.

[4] 曹立志,陳瑩.基于學習自動機的無線傳感網能量均衡分簇算法[J].傳感技術學報,2013,26(11):1590-1596.(CAOLZ,CHENY.Energybalancedclusteringalgorithmbasedonlearningautomataforwirelesssensornetwork[J].ChineseJournalofSensorsandActuators, 2013, 26(11): 1590-1596.)

[5] 米志超,周建江.一種能量均衡的無線傳感網絡生命期優化算法[J].系統工程與電子技術,2008,30(12):2477-2480.(MIZC,ZHOUJJ.Energy-balancedoptimizationalgorithmformaximizingnetworklifetimeinwirelesssensornetworks[J].SystemsEngineeringandElectronics, 2008, 30(12): 2477-2480.)

[6]ANGELOPOULOSCM,NIKOLETSEASS,RAPTISTP,etal.Efficientenergymanagementinwirelessrechargeablesensornetworks[C]//MSWiM’12:Proceedingsofthe15thACMInternationalConferenceonModeling,AnalysisandSimulationofWirelessandMobileSystems.NewYork:ACM, 2012: 309-316.

[7]MAOSB,CHEUNGMH,WONGVWS.Jointenergyallocationforsensingandtransmissioninrechargeablewirelesssensornetworks[J].IEEETransactionsonVehicularTechnology, 2014, 63(6): 2862-2875.

[8] 杜欣.WSN低功耗算法在電力系統中的應用[J].電力系統通信,2012,33(4):62-66.(DUX.ApplicationofWSNtechnologybasedlow-powerconsumptionalgorithmsinpowersystem[J].TelecommunicationsforElectricPowerSystem, 2012, 33(4): 62-66.)

[9]GHADIMIE,LANDSIEDELO,SOLDATIP,etal.Opportunisticroutinginlowduty-cyclewirelesssensornetworks[J].ACMTransactionsonSensorNetworks, 2014, 10(4):ArticleNo. 67.

[10]GUY,HET.Dynamicswitching-baseddataforwardingforlowduty-cyclewirelesssensornetworks[J].IEEETransactionsonMobileComputing, 2011, 10(12): 1741-1754.

[11] 趙燦明,李祝紅,閆凡,等.電力通信網絡中負載均衡的路由協議[J].計算機應用,2016,36(11):3028-3032.(ZHAOCM,LIZH,YANF,etal.Loadbalancedroutingprotocolinelectricpowercommunicationnetworks[J].JournalofComputerApplication, 2016, 36(11): 3028-3032.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61379130, 61672485).

XIE Xiaojun, born in 1975, M. S., engineer. His research interests include electric power communication system.

YU Hao, born in 1975, M. S., engineer. His research interests include electric power communication system.

TAO Lei, born in 1992, Ph. D. candidate. His research interests include wireless network, smart grid.

ZHANG Xinming, born in 1964. Ph. D., professor. His research interests include wireless network, smart grid.

Energy-balanced routing algorithm in rechargeable wireless sensor networks

XIE Xiaojun1, YU Hao1, TAO Lei2, ZHANG Xinming2*

(1.DivisionofInformationCommunication,StateGridAnhuiElectricPowerCompany,HefeiAnhui230061,China; 2.SchoolofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,HefeiAnhui230027,China)

Aiming at energy-balanced routing problem in rechargeable Wireless Sensor Network (WSN), a new multi-path routing algorithm and an opportunistic routing algorithm were proposed in the scenario of wireless charging with stable power and monitoring data collection network, so as to achieve the energy balance of the network. Firstly, the relationship model between the charging power and the receiving power of wireless sensor nodes was constructed by the theory of electromagnetic propagation. Then, considering the sending and receiving energy consumptions of wireless sensor nodes in the network, the energy-balanced routing problem was transformed into the max-min optimization lifetime problem of the network nodes. The link traffic obtained by the linear programming was used to guide the data flow allocation in the routing. Finally, considering a more realistic scenario of low power WSN, an energy-balanced routing algorithm based on opportunistic routing was proposed. The experimental results show that, compared with the Shortest Path Routing (SPR) and Expected Duty-Cycled wakeups minimal routing (EDC) algorithms, the proposed two routing algorithms can effectively improve the utilization ratio of the energy collection and the network lifetime in the working period.

energy-balanced routing; rechargeable Wireless Sensor Network (WSN); opportunistic routing; low power sensor network

2016- 11- 17;

2017- 02- 04。 基金項目:國家自然科學基金資助項目(61379130,61672485)。

謝小軍(1975—)，男，安徽涇縣人，工程師，碩士，主要研究方向：電力通信系統； 于浩(1975—)，男，安徽臨泉人，工程師，碩士，主要研究方向：電力通信系統； 陶磊(1992—)，男，安徽和縣人，博士研究生，主要研究方向：無線網絡、智能電網； 張信明(1964—)，男，安徽天長人，教授，博士，CCF高級會員，主要研究方向：無線網絡、智能電網。

1001- 9081(2017)06- 1545- 05

10.11772/j.issn.1001- 9081.2017.06.1545

TP393.03

A