一種智能電網中基于優先充電機制的節能匯聚路由方案

談

(南京信息工程大學 計算機與軟件學院,南京 210044)

0 概述

在智能電網中,安全性、可靠性和高效性是電力服務的目標,無線傳感器網絡(Wireless Sensor Network,WSN)在監測范圍、成本、監測粒度、魯棒性等方面都能很好地滿足需求,但其存在無線傳感器節點電池能量受限的問題。要將無線傳感器網絡應用于智能電網中,就需要研究能量效率和能量捕獲的相關技術。

能量捕獲技術對智能電網的長期發展具有重要意義。但智能電網中的主電源很難直接被無線傳感器節點使用。目前有很多文獻針對無線傳感器網絡的節能問題提出了解決方案。在能量捕獲方面的研究包括利用風能、太陽能、震動能量、射頻(Radio Frequency,RF)能量等實現能量轉換[1-4]。考慮到能量轉換的便利性和無線傳感器節點的特性,RF能量捕獲技術理論上可以為節點永久性供能,對能量捕獲中的溢出情況進行監測[5],提高智能電網的自主性并用于對其進行長期監測[6]。

在利用RF給無線傳感器網絡充電的研究方面,文獻[7]研究了RFID標簽充電時最小化網絡中的靜態閱讀器數量問題。文獻[8]論述了在RF充電器訪問每個節點時,如何實現該類功率發射器的最優路徑問題。在文獻[9]研究的移動充電器方案中,在有魯棒性充電要求時實現了訪問移動充電器的地標數最小化。以上文獻尚未綜合考慮數據傳輸效率和RF能量捕獲的優先機制問題。

在RF能量捕獲技術中,無線傳感器網絡中節點的部署及傳輸中的路由選擇會影響到能量捕獲及數據傳輸效果。在多跳路由拓撲中,每個中繼節點都會因為負載增加而受影響,能量開銷將比其源頭節點更大,因此,需要為其設計能量優化策略。構建數據匯聚樹可以讓無線傳感器網絡的數據傳輸更加節能和高效,尤其是在節點需要通過RF捕能方式來充電的場合,更需要對路由進行優化。

在WSN中利用數據匯聚來延長網絡壽命是一種常見的優化方法[10],這類方法主要分為2類:基于樹型結構的方法和基于簇狀結構的方法。前者的典型案例是TAG協議,后者的典型案例是LEACH或改進的LEACH算法[11-12]。另外還可以利用數據匯聚樹來提升服務質量,如在保持網絡壽命優勢的同時減小數據延遲[13-14]。如何在能量捕獲過程中構建數據匯聚樹,文獻[15]提出了一種提高網絡生存期的數據匯聚樹構造策略,但沒有考慮數據傳輸率和充電的實際情況。本文在此基礎上,針對智能電網的無線傳感器網絡布網特點,設計一種基于優先充電機制的數據匯聚型節能路由方案,綜合考慮路由優化、RF充電與數據傳輸率之間的關系。

1 網絡模型

在無線能量捕獲的能量轉換中,徑損主要取決于信號頻率。為了簡化問題,本文所討論的智能電網監測網絡將采用自由空間徑損模型。該模型是無線電波傳播最簡單的模型,無需考慮衰減和多徑等問題,比較適合無線路由建模。在直徑R的圓形范圍內,相應的接收功率為:

其中,Gr是接收方的線性天線增益,PtGt是發射功率,λ是波長。實際捕獲到的功率是接收功率經過一定的電路損耗之后的函數。

從式(1)可以看出功率傳輸范圍很小,僅利用蜂窩基站(在智能電網中是主電源降壓后的設備)補充能量,將不足以為傳感器節點充電。因此,除了主供電設備外,本文將進一步利用移動式備選供能節點為匯聚路由中數據傳輸任務較重的捕能節點提供優先充電,這些供能節點的成本比主設備(基站)低得多。在本文所提出的支撐樹節能路由算法中,這些供能節點不參與數據匯聚樹的構建和數據傳輸。

優先充電網絡模型如圖1所示,網絡包括一個主電源(扮演基站B的角色)、能量轉換設備,這里扮演供能節點(Energy Providing Node,EPN)的角色;傳輸節點包括捕能節點(Energy Harvesting Node,EHN)和普通節點(Ordinary Node,ON),其中供能節點僅與捕能節點通信。由于備選供能節點不需要提前在全網部署且分配靈活,因此在圖1中并未體現。

圖1 優先充電網絡模型

每個EHN至少配置一個EPN進行充電,對于路由中承擔更大量數據傳輸任務的EHN,增加PEPN實現優先充電。該PEPN為移動式工作,可根據匯聚樹中的路由變化及數據傳輸率情況而做相應的位置調整,實現基于動態優先充電的節能匯聚路由。本文利用ILP模型實現全網ON節點的子節點數最小化,假設所有的供能節點發射范圍都一樣。

2 節能路由方案

利用上述3類節點,即普通節點(ON)、供能節點(EPN)和捕能節點(EHN),首先在網絡中部署初始的ON和EHN,在EHN周圍設置至少一個EPN。采用整數線性規劃(Integer Linear Programming,ILP)和最小權重捕獲支撐樹路由算法實現節能的數據傳輸。這里的ILP即最小-最大模型,用以實現普通節點的下游節點上限的最小化(數據匯聚自下游節點往上游節點)。最小權重捕獲支撐樹路由算法旨在加速匯聚樹構建的速度,并降低其復雜度。對構建好的匯聚拓樸樹再進行回溯,直至找到最優匯聚拓樸樹。為了實現優化充電,對其中的重載EHN,通過增加EPN提高捕能的便利性和有效性。

2.1 初始模型

匯聚路由在文獻[15]的基礎上改進。本文簡化了匯聚過程,并增加優先充電環節。匯聚路由主要基于圖論方法,構建一棵最小權重支撐樹,要求路由中不含閉合環,因此,需要實現從帶環到去環的過程。

構建的數據匯聚樹基本模型如圖2所示,其中不包含EPN和PEPN。

圖2 充電型數據匯聚樹基本模型

該模型描述為:在網絡中一共有K個節點,其中基站為B,整個樹中有n個頂點,最多有n-1條邊。而匯聚路由中進入B的數據流有K-1條(這也要求構建的樹中有向邊的數量不應該小于該數)邊集合M中所有的邊是由2個能直接通信的節點之間的連線構成。EHN節點集H?N,ON節點集O,也即N{H∪S}。為了簡化問題,EPN節點不在N中體現,也即數據匯聚樹中并不出現EPN。

由于各捕能節點的傳輸數據率不同,對能量需求不同,因此在構建好的匯聚樹中,在較重傳輸任務的捕能節點旁增加一個備選的供能節點。該供能節點僅為捕能節點提供RF能量,對匯聚路由不產生影響。構建了該拓撲樹后,圖2可以抽象為有向拓撲形式,其中忽略了非直接通信的節點之間的邊。

假設每個待匯聚拓撲樹中的節點可以處理從其子節點接收到的全部數據包,在此基礎上再生成一個自身的數據包。為了節省能量,節點僅在有數據收發活動時才激活射頻。因此,子節點的數量對網絡壽命會產生重要影響。考慮到EHN節點可以進行RF能量補充,網絡壽命主要受ON節點的影響,需要在全網中實現ON節點的最大子節點數最小化。

基于IPL的匯聚路由(Aggressive Routing-IPL,AR-ILP)旨在減少ON的子節點數,以增加WSN壽命。AR-ILP模型構建如下:模型的有向拓撲圖源于基站B,每個節點有一個權重,定義ON權重為1,其他節點(EHN節點和B)權重為0。設置一個決策布爾變量X,若節點i(不含B)選擇j作為父節點(即數據匯聚的上游節點),則Xij=1。整型流矩陣Fij表示從i到j的數據流構成的矩陣,若Xij為0,則Fij亦為0。通過Fij進行優化后將獲得一個連接拓撲。假定每個節點(除B之外)有且僅有一個父節點,在WSN中所有ON節點的孩子數最少可以表示為:

s.t. ?(i,j)∈M,i∈N-{S},0≤Fij≤K-1

(2)

其中,n(j)是節點i射頻范圍內的所有通信節點。

假設到基站B的所有數據流有K-1條,從基站B只有流入的數據流,沒有流出的數據流,B為整棵樹的根。每個數據流都有單一的傳輸方向,在樹中,每個最下游的葉節點發送一個數據包,中繼節點在收到的數據包基礎上再加一個包,最終所有數據到達B,WSN的數據傳輸基于該匯聚樹完成路由過程。

2.2 基于優先充電機制的節能路由算法

為了進一步加速該匯聚樹過程,可以讓B發揮更大的作用,基于該匯聚樹根B構建反向支撐樹,數據流的方向與數據傳輸方向相反,采取從B起始一直到葉節點的方式。在構建反向匯聚支撐樹的過程中,利用反向拓撲控制、權重控制和破環法使ON節點的子節點數最小化過程更快。其基本思路為:按照與匯聚樹中數據流相反的方向,從B出發,把進入B的邊全部去掉,進一步找出其他每個節點的入邊和出邊。邊的選擇根據節點的權重進行。B和EHN節點的權重為0,ON節點的權重為1。有向邊的權重設為出發節點的權重。每個節點選擇最小權重的入邊來構建樹(使ON及EHN節點更多地選擇B和EHN節點作為父節點)。這樣便構建起初始時的反向匯聚支撐樹,同時檢查其中是否有環路(環主是由NHN節點造成,因其既有入邊,又有出邊)。若存在環路,則利用將涉及環路的EHN節點合并的方式將環打破,再重新確定樹中的邊(規則與前文一樣)。檢查新圖中的含環情況,若有環,繼續用合并EHN節點的方式破環,直到樹中無環為止。最后把合并節點拆開,再次確定樹中的邊,形成無環的反向支撐樹。將這棵反向匯聚支撐樹再恢復成正常數據傳輸的匯聚樹只要將反向支撐樹中邊的方向取反即可。

在上述加速的反向支撐樹匯聚路由中,個別ON的子節點數可能會不穩定,其原因是在建樹過程中最初基于最小權重選擇邊的過程不唯一,而破環過程中合并節點時基于最小權重選擇邊的過程也不唯一。因為在權重相等且存在有向邊時,并沒有限定必須選擇哪個ON節點作為父節點,這就導致了一些ON節點的孩子數超過1。因此,對這種非最優拓撲樹需要反復進行邊的優化選擇操作,直至找到最優數據匯聚路由。該加速過程是本文的重要創新點,能夠給節能處理帶來更高的效率。

反向支撐樹匯聚路由原始拓撲如圖3所示。其中,EHN節點用雙線圓圈表示,B為基站,其他節點為ON節點。

圖3 反向支撐樹匯聚路由原始拓撲

下面結合圖例給出具體的算法步驟。

步驟1在所有ON節點、EHN節點、B節點構成的無向圖中構造出帶權有向圖,并在其中找到每個節點。權重設置為:ON節點權重為1,EHN節點及B節點權重為0,若u為ON節點,以u為起點、連接u和v的有向邊權重設置為w[u,v]=1,若u為EHN節點或B節點,則對應w[u,v]=0。這種設置保證了從EHN和B節點出發的有向邊權重為0,更有利于ON將其選為入射邊,因為數據匯聚樹基于最小權重選擇有向邊。在構建反向支撐匯聚樹的過程中,基站B的優先級最高,其他節點選擇入射邊時以B作為入射邊首選。作為整棵樹的根,基站B只有出射邊,其入射邊全部去掉。規定每個EHN節點至少要有一條入射邊,而ON節點有多條入射邊備選。該過程所形成的拓撲不唯一,圖4給出了某次選擇的結果。

圖4 初步構造的帶權有向圖

步驟2檢查上一步結果中的含環情況。若無環,直接得到反向數據匯聚拓撲樹。進入步驟4。若存在環,對其進行破壞。將包含在環中的EHN節點進行合并,形成一個新的合并節點。再次,基于最小權重選擇每個節點(含合并節點)的入射邊,構成一個新的最小權重拓撲樹。重復該步驟的操作,檢查新樹中包含環的情況并進行相應的處理,直至最后的樹中不含環。破環的過程如圖5、圖6所示。

圖5 合并節點基于最小權重定邊的結果

圖6 繼續合并節點并基于最小權重定邊后的最終結果

步驟3分離上一步的合并節點,并確定圖中每個節點(除B)的入射邊,得到相應的反向匯聚拓撲樹,如圖7所示。該過程形成的拓撲樹不唯一。

圖7 拆分節點并確定相應邊的示意圖

步驟4將反向支撐匯聚拓撲樹的各邊進行反向處理,得到與數據傳輸一致的支撐樹匯聚路由,如圖8所示。

圖8 反向確定支持匯聚路由的拓撲樹

步驟5重復步驟1～步驟4,獲取其他可能的支撐樹匯聚路由,并進行對比,以期得到最優數據匯聚路由。

為了使模型更具可行性,在智能電網的監測網絡實際運行時,該監測網絡壽命與傳輸范圍、部署區域、ON節點周圍的節點密度、EPN節點和EHN節點的部署、RF能量搜集的效率有密切的關系,并不能按理想方式(比如每個節點僅產生一個數據包并將其傳輸給其上游節點)來傳輸。因此,要區別對待EHN,在構造的最優數據匯聚路由中,對那些傳輸任務較重的EHN節點給予更高的優先級,利用移動式EPN,在這些重載EHN節點旁設置一個PEPN節點。

2.3 算法復雜度分析

算法復雜度分析步驟為:

步驟1確定樹中的頂點權重(復雜度為O|N|)和每條邊的權重(復雜度為O|M|),以及在所有有向邊中移除到基站B的邊(復雜度為O|M|))。

步驟2分析得到遞歸的破環過程復雜度為O(Nlog|N|+|M|)。

步驟3合并節點的分離,因為破環和合并節點的思路與Edmond有向最小支撐樹算法思路相近,借鑒其有向最小支撐樹算法所得到的結果,其復雜度為O(|N|-1),即O|N|。

由以上分析得出算法總的復雜度為O(3|M|+Nlog|N|+2|N|)。

對比文獻[14]的APAL算法,本文算法增加了優先充電和加速過程,算法復雜度沒有明顯增加,在節點數量中等及以下時,可以得到更好的復雜度性能。

3 仿真與結果分析

為了驗證本文算法的性能,本節進行仿真實驗并分析結果。主要考察網絡壽命,以第1個ON節點耗盡電池的時間為準,利用Matlab和開源的整數規劃工具Ipsolve進行混合編程,通過Matlab調用Ipsolve解決IPL最優化問題,其求解效率較高。其他IPL求解工具有的是商業軟件,如GPLEX,有的操作復雜,如GLPK。

設計3個仿真過程。第1個實驗設計為當ρ和R不變時(分別設置為20和20%),改變K值,觀察網絡壽命T的變化情況;第2個實驗設計為當K和R不變時(分別設置為400和20%),改變K值,觀察網絡壽命T的變化情況;第3個實驗設計為當ρ和K不變時(分別設置為20和400),改變K值,觀察網絡壽命T的變化情況。為了研究優先充電機制的性能,增加能耗排在前10%(假設能耗僅與傳輸連接數相關)的EHN節點作為優先充電節點。在以上3種實驗條件下比較具有優先充電機制和沒有優先充電機制的節能匯聚路由方案在網絡壽命方面的性能。

圖9～圖11分別給出了3個實驗的仿真結果,并對2種方案進行了橫向對比。

圖9 節點數與網絡壽命的關系

圖10 網絡傳輸密度與網絡壽命的關系

圖11 EHN節點百分比與網絡壽命的關系

仿真結果表明,網絡壽命T與K、ρ以及R都有關系。總體情況為:當K增加時,T會下降;當網絡傳輸密度ρ上升時,T也同步提升。但當ρ增長到一定程度時,T幾乎不再增加;當R上升時,T也增長,但R必須達到足夠的百分比才能體現出其優勢。這說明在匯聚路由算法中,隨著傳輸距離增加(對應傳輸密度ρ),網絡中能夠及時找到足夠的下游節點進行數據傳輸,確保了數據傳輸的有效性。

而優先充電節點增加了備用供能節點后,網絡性能發生了一定變化,主要表現為:在第1個實驗中,網絡壽命T的下降趨勢有所緩和,會更早進入T的穩定狀態;在第2個實驗中,備用供能節點為NHN提供的優先充電效果在r較小時更明顯,此時ON節點需要更多的EHN用于中繼,因此,需要消耗更多的能量;在第3個實驗中,當EHN節點增加時,優先充電機制能夠使其更好地工作,網絡壽命T的優勢也更明顯。這說明具有優先充電機制的匯聚路由算法在節能和延長網絡壽命方面具有更好的性能表現。

在為智能電網監控服務的無線傳感器網絡中,由于監控流量變化不大,因此重負載捕能節點數量也相對較少,其對優先供能節點的需求保持在一個較小的范圍,優先充電的額外成本可控。各個節點的傳輸距離在較小的條件下,可以更好地協調好數據傳輸效率和網絡壽命的性能。

4 結束語

為提高智能電網監測網絡的數據傳輸有效性并延長網絡壽命,本文提出了一種具有能量捕獲功能的無線傳感器網絡節能匯聚路由數據傳輸方案,并設計了一種基于優先充電機制的數據匯聚樹路由算法。利用整型線性編碼和最小權重捕獲支撐樹路由算法實現節能的數據傳輸,并對重載捕能節點進行優先充電,從而實現網絡壽命延長和有效數據傳輸的目的。該路由方案具有較小的算法復雜度,仿真結果表明,其能夠提高數據傳輸的有效性,優先充電機制也能更合理地提高網絡壽命。

在下一步的研究中將重點考慮如何甄選優先充電的重載EHN節點,以及提高EHN節點和優先充電節點在所有節點中的比例。