談

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

0 概述

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

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

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

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

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

1 網(wǎng)絡模型

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

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

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

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

圖1 優(yōu)先充電網(wǎng)絡模型

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

2 節(jié)能路由方案

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

2.1 初始模型

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

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

圖2 充電型數(shù)據(jù)匯聚樹基本模型

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

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

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

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

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

(2)

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

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

2.2 基于優(yōu)先充電機制的節(jié)能路由算法

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

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

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

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

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

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

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

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

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

圖6 繼續(xù)合并節(jié)點并基于最小權重定邊后的最終結果

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

圖7 拆分節(jié)點并確定相應邊的示意圖

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

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

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

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

2.3 算法復雜度分析

算法復雜度分析步驟為:

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

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

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

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

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

3 仿真與結果分析

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

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

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

圖9 節(jié)點數(shù)與網(wǎng)絡壽命的關系

圖10 網(wǎng)絡傳輸密度與網(wǎng)絡壽命的關系

圖11 EHN節(jié)點百分比與網(wǎng)絡壽命的關系

仿真結果表明,網(wǎng)絡壽命T與K、ρ以及R都有關系?？傮w情況為:當K增加時,T會下降;當網(wǎng)絡傳輸密度ρ上升時,T也同步提升。但當ρ增長到一定程度時,T幾乎不再增加;當R上升時,T也增長,但R必須達到足夠的百分比才能體現(xiàn)出其優(yōu)勢。這說明在匯聚路由算法中,隨著傳輸距離增加(對應傳輸密度ρ),網(wǎng)絡中能夠及時找到足夠的下游節(jié)點進行數(shù)據(jù)傳輸,確保了數(shù)據(jù)傳輸?shù)挠行浴?/p>

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

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

4 結束語

為提高智能電網(wǎng)監(jiān)測網(wǎng)絡的數(shù)據(jù)傳輸有效性并延長網(wǎng)絡壽命,本文提出了一種具有能量捕獲功能的無線傳感器網(wǎng)絡節(jié)能匯聚路由數(shù)據(jù)傳輸方案,并設計了一種基于優(yōu)先充電機制的數(shù)據(jù)匯聚樹路由算法。利用整型線性編碼和最小權重捕獲支撐樹路由算法實現(xiàn)節(jié)能的數(shù)據(jù)傳輸,并對重載捕能節(jié)點進行優(yōu)先充電,從而實現(xiàn)網(wǎng)絡壽命延長和有效數(shù)據(jù)傳輸?shù)哪康摹Ｔ撀酚煞桨妇哂休^小的算法復雜度,仿真結果表明,其能夠提高數(shù)據(jù)傳輸?shù)挠行?優(yōu)先充電機制也能更合理地提高網(wǎng)絡壽命。

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