WRSN中一種聚類分簇多跳能量補充策略

張媛媛,馮 勇,付曉東

(昆明理工大學 云南省計算機技術應用重點實驗室,昆明 650500) E-mail:zhyuanAngel@163.com

1 引 言

無線可充電傳感器網絡(Wireless Rechargeable Sensor Networks,WRSN)是部署在監測區域內的若干個傳感器節點的可充電式網絡.節點可通過充電獲取能量,并將收集到的數據以無線的形式發送到基站,再由基站將數據上傳至互聯網.隨著可快速充電網絡的飛速發展,WRSN技術成為了眾多充電研究領域的焦點.傳感器節點使用電池供電,而電池能量是有限的,這會導致在無線通信過程中會消耗大量傳感器節點的能量,因此解決能耗問題成為了該領域研究的關鍵,于是涌現出各種節能的方法以及充電的方法[1],然而節能的方法可能會增加網絡延遲,只能有限延長網絡壽命,緩解耗能的現狀,并不能從根本上解決問題.在充電領域的研究中通常采用的是單跳能量傳輸[2],但這種方式在網絡節點較多的情況下可能會增加充電成本降低充電效率,可見其可擴展性和效率是十分有限的.為了解決這一問題,本文采用多跳能量傳輸方式.除此之外,現有工作中采用多小車充電技術[3].MC是一個具有自主移動能力和計算、通信能力的充電裝置,該充電裝置在本文中統稱為充電小車,它們通過相互配合實現對缺電節點的能量補給,而研究多小車充電技術時需要盡可能地達到讓MC的數量呈現最低值,或者提高MC的充電效率,但是實際環境中MC是相對代價很高的一種設備,為了更有效的降低充電代價,本文將最小化充電裝置個數即采用單小車充電來簡化充電規劃.

本文中還涉及到的另一先進技術是聚類方法[4],其引申出來的分析往往用于從大范圍的數據庫中快速、準確地尋找數據.該技術在社會各行業領域都起到很重要的作用,其中Choi J等人[5]提出將傳感器節點分組成簇是在無線傳感器網絡(WSN)中減少重復信息傳輸的有效方法,并且能準確的預估能量的消耗.本文將傳感器節點抽象成每一個數據點,利用聚類思想為MC尋找合適的簇點.綜上所述,為了解決現有能量補充方案的缺陷,本文創新的提出一種聚類分簇的多跳能量補充策略.

本文組織如下:第二節介紹了相關工作.第三節用網絡模型與問題陳述來描述網絡的能量問題.第四節詳細介紹了該能量補充方案的工作過程.第五部分通過仿真實驗的結果和分析對該算法做出了性能評價.最后在第六節中對全文進行總結.

2 相關工作

在這個部分,我們將回顧現有的使用無線能量補充技術延長網絡壽命的工作,其中分為單跳能量傳輸、多跳能量傳輸以及多小車充電技術這三個方面.

在單跳能量傳輸方面,文獻[6]考慮單跳能量傳輸,M.Ma等人設計出一種貪婪算法,找到一個充電序列,能夠使用移動充電裝置最大限度的提高網絡的生命周期,但該文獻提出來的優化技術和充電算法是基于單節點的充電模型,具有非常有限的可擴展性.文獻[7]提出賦予移動充電裝置更廣的用途,不僅可以補充聚合及轉發節點(AFN),還能夠在選定的AFN節點處采集數據.該文獻綜合考慮數據傳輸方式、無線電功率以及流量選擇方式這三種因素,提出一種啟發式算法來解決為節點補充能量的優化問題.為了提高網絡生命周期,文獻[8]提出了一種新的路由選擇指標,能夠形成具有最佳充電性能的路由.在文獻[9]中,Peng等人提出了一個由固定的傳感器節點,MC和基站(BS)組成的三層架構來監視MC和傳感器的能量狀態.傳感器周期性地發送有關其電池狀態的信息,并由基站計算充電序列并將信息發送給MC.

多跳能量傳輸[10]更適合網絡節點較多的情況,該方式已在眾多研究中被證實可使得充電效率有所提升.現有工作通常采用諧振中繼器實現多跳能量傳輸,其涉及的磁共振無線能量傳輸耦合是一種很前沿的傳感器能量補充技術[11].該技術在每個傳感器上的線圈周圍產生一個能夠傳輸電力的磁場,當充電裝置對其進行充電時,會將自身的發射線圈與傳感器接收線圈調成同一個振動頻率,這時能量就會以電流形式傳輸出去,方便實現一對多充電,因此采用諧振中繼器可以有效提高充電效率.文獻[12]中Xie等人提出具有擴展性的網絡部署,將整個網絡按邊長在MC充電范圍內的正六邊形進行劃分,分割后以正六邊形的中心點作為錨點,采用離散化和線性化技術對整個網絡規劃哈密頓回路,讓MC周期性的沿規定的路線進行能量傳輸.該文獻雖然開發了一個可證明的近似達到高期望精度水平的最優解,但卻不能很好的適應節點能耗的動態性,屬于當前能量補充技術中的離線充電方式.文獻[13]中Xiang等人提出了距離最近優先充電方法作為充電策略,對所提出的移動充電策略進行了對比實驗分析,除此之外還考慮一種多跳能量流問題,并針對問題制定研究方案,為了優化該能量流問題設計出合適的算法.

對于多小車充電的研究,文獻[14]提出一種新型框架,采用相鄰交叉耦合諧振中繼器為多跳無線充電問題提供方案.為了達到能量消耗與節電延遲之間的平衡,Wang C等人提出了一種混合數據收集策略,收集時間敏感數據和時間不敏感數據.為了最大限度的減少充電成本,該文獻提出了兩步近似算法,首先確定一組具有代表性的傳感器位置記作錨點,并采用多小車充電方案,利用近似算法的旅行商問題為多小車分配一個完整的最優路徑.為了進一步降低系統成本,用后優化算法迭代地添加移動充電小車的位置來改善充電結果.文獻[15]中考慮了充電過程中的節點能量需求和節點能耗問題,提出一種多跳無線充電優化算法.首先利用Dijkstra算法[16]找到最短路徑樹,然后采用混合整數線性算法(MILP)來尋找充電小車的最小數量.分析表明充電小車的最小數量取決于充電樹的最大高度以及充電小車的電量.但是該文獻解決方案沒有考慮到節點的充電時間和總能量,并且采用多小車充電會導致充電成本的增加.

本文就上述問題提出了無線可充電傳感器中一種聚類分簇的多跳能量補充策略.本策略采用了聚類算法分配簇點,提出計算節點密度電量比動態分配充電優先級,并通過對比實驗評估該策略的網絡性能.

3 網絡模型與問題陳述

3.1 基礎網絡模型

本文構建的基礎網絡由三部分組成.分別是基站(Base Station,BS)、網絡傳感器節點(Sensor)以及移動充電裝置(Mobile Charger,MC),具體網絡模型如圖1所示.在本文中,假設BS有足夠的能量和通信能力使其能夠直接向MC發送信息.BS從節點接收充電請求消息,并直接將收到的消息轉發給MC.MC具有從服務池動態獲取各個傳感器的充電信息和位置信息的計算能力,并根據充電優先級找到下一個目標節點.具體的參數符號如表1所示.

圖1 網絡模型Fig.1 Network model

3.2 問題公式

在本節中,為了降低充電成本,提高充電效率,首先給出能量消耗公式,然后給出能量傳輸的效率公式.

3.2.1 能量消耗公式

無線通信模型中提出一個距離閾值d0,其值與實際環境相關.當節點不位于充電服務池時,假設發送節點a與接收節點b的距離的距離不小于閾值時,即dab≥d0時,文獻[17]中證明了收發數據消耗的能量與距離之間的四次冪關系.因此基于發送節點與接收節點之間的距離,可以計算發送數據所消耗的能量值.舉個例子,節點a′向距離d以外的另一節點b′發送k個字節的數據,該過程消耗的能量Ec可由公式(1)計算得到.

Ec(k,d)=Eelec(k)+Eamp(k,d)

=kEelec+kε-mpd4

(1)

其中Eelec表示節點發送與接收數據所消耗的能量,Eamp表示放大器消耗的能量,其大小取決于可接受的位錯誤率ε-mp以及發送節點與接收節點之間的距離.

表1 參數符號表
Table 1 Parameter symbol

參數符號參數意義N傳感器個數Rs傳感器通信范圍S充電服務池Es節點的剩余電量Ec發送/接收數據包的能量消耗Et能量閾值VmMC的移動速度RrMC的充電范圍

3.2.2 能量傳輸效率

1)多跳能量傳輸:文獻[18]提出一個節點既可以傳輸能量也可以接收能量,并且相鄰節點之間能夠交換能量.對此,有文獻[5]提出當能量從MC通過多跳傳輸至其他節點時,在整個充電路徑中會存在能量丟失的情況.我們給出一個中心節點a,一個中間節點b和一個最終節點c,那么總的能量分配Etotal是:

圖2 簇點個數Fig.2 Number of clusters

Etotal=Echarge+Ea+Eb+Ec

(2)

Echarge=2λcharge|Ab|2

(3)

其中Ea,Eb,Ec表示節點a,b,c的能量消耗,可由公式(1)求得.|Ab|表示當給節點b充電時,節點b的接收功率.λcharge是充電過程中能量消耗的速率.我們假設傳輸到中間節點的所有能量將被用于從中間節點到最終節點的能量傳輸.也就是說,電池在充放電過程中沒有能量損失,從而得到充電效率為:

λcharge|Ab|2=λb|Ab|2+2λc|Ac|2

(4)

(5)

2)單跳能量傳輸:基于上述表達式,我們給出節點a的單跳能量傳輸效率公式,為了提高充電效率和網絡生存周期,我們需要盡可能地使ηcharge變大:

Echarge=λcharge|Aa|2

(6)

λcharge|Aa|2=λa|Aa|2

(7)

(8)

4 能量補充算法

本節將詳細描述在無線可充電傳感器網絡中一種聚類分簇多跳能量補充算法.

4.1 簇點初始化算法

4.1.1 簇點個數的確定

圖3 孤立點個數Fig.3 Number of isolated nodes

實際環境中的錨節點即簇點,在下文中統稱簇點.假設簇點的大小是固定的,文獻[19]給出了覆蓋區域Ω所需最小節點數量n的公式,其半徑為傳感器通信半徑Rs:

(9)

圖4 簇點初始化Fig.4 Cluster point initialization

定義1.?(x1,y1)∈Ω,定義它的一個鄰域為:

(10)

(11)

(12)

(13)

由上述公式可得不同節點數相對應的簇點個數如圖2所示.

4.1.2 簇點初始化過程

對于簇點的初始位置確定,本文在研究初始位置的最初階段時采用隨機初始化方式確定固定個數的簇點的初始位置,即RI-CB MWRN算法(Random Initialization-Clustering Based Multi-hop Wireless Rechargeable Network).在初始化簇點位置之后,采用聚類的簇點生成算法以及相應的優先級算法來完成整個網絡的充電過程.具體的算法過程將后面一節中詳細介紹.而后對于簇點位置的隨機初始化這一部分進行了進一步的更改,我們提出通過節點的連通度來實現.算法具體過程為:首先定義通信范圍內的節點互為鄰居節點,那么擁有鄰居節點的個數即為節點的連通度.其次把所有節點的連通度放在集合δ中,將δ中的最大值記作δmax.當|δmax|≤k時,找到距MC最近的點i放入簇點集合Α中,然后對每一個δ中的節點j到i的距離記作dij,進行冒泡排序后優先選擇dij最大的節點放入Α中,否則取下一個δmax,直到Α中簇點個數為k.通過比較隨機分布和節點連通度分布得到的聚類初始位置,可以看出最終聚類后產生的孤立點個數明顯不同.從圖3可以看出,隨機初始化節點分布導致的孤立節點數量總體上大于節點度數初始化分布導致的孤立節點數量.當孤立節點數量增加時,MC的移動距離將增加,從理論上講,充電成本會明顯增加,不利于實現更好的實驗結果.在這里,如圖4所示給出了簇點初始化的樣例圖.

算法1.初始化簇點算法的偽代碼

Input:sensor nodesN,the number of clustersk,set of degreeδ,δmax

Output:set of initialize anchors Α0

1:Initialize:Α0=null

2:considerifromδmaxas a candidate anchorαi,Α0←Α0∪αi

3:while Α0≠null do

4: calculate dijofδmax

5: by Bubble sort,add dijto arrayφ

6: for(j=0;j<φ.length;j++)

7: Α0←Α0∪αj

8: if |Α0|≤k then

9:δmax=δmax-1

10: end if

11: else break

12: end for

13:end while

4.2 HNDLE-CB 算法

基于上述工作內容,下面將詳細描述HNDLE-CB算法的實現步驟.首先網絡工作過程為:MC檢查傳感器節點剩余的電池能量Es.當傳感器節點Es≤Et時,會向BS發送充電請求,并放入服務池,然后將其置于休眠狀態.

1)簇點生成算法.首先我們需要初始化一組數據點.這里給出一個無標記的數據集合[20]X={X(1),X(2),…,X(m)}.初始化的過程是選取節點度數最大的數據點.其次我們將互為鄰居節點的點用虛線連接,節點擁有的線條數量即為它的度數.對于每一個傳感器節點X(i),需要找到離它最近的簇點j,且X(i)必須包含在簇點j的充電范圍R內,這時將X(i)分配給簇點j,否則將重新尋找不在充電范圍R內的X(i)距離最近的一個簇點j′.如果沒有滿足條件的簇點j′,則將不在充電范圍R內的節點視作孤立點.對于這一步,我們要做的是選擇離傳感器節點最近的且符合條件的簇點并分配給X(i).最后將簇點重新分配,它的新位置就是該簇點包含的所有點的平均值.其中,簇點j距離X(i)最近的判斷所用的是歐式空間[21]中兩點之間的直線距離,即平面上兩點A=(a1,b1)和B=(a2,b2)之間的歐式距離公式為:

(14)

具體簇點生成算法過程如圖5所示.

2)優先級分配算法.在第一步找到簇點集合Α以后,MC接收到充電請求后,每隔T個時間檢查服務池內的請求記錄集合,這些記錄主要包括請求節點的剩余能量Es以及節點的位置L.初始時將MC的狀態設為空閑,并將其位于所有Sensor的中心點處.當接收節點的充電請求時,MC會更新服務池,并計算服務池中節點的節點密度電量比Ψ.我們首先定義剩余能量大于閾值的節點i的服務池集合Si.充電序列可以表示為r=(1,2,…,i,…,k),其中簇點i∈Α,k=|Α|,MC需找到他們所屬的簇點.當服務池里節點數量為?時,?=|Si|,MC會從?中得到每一個節點的Es,以及節點同屬同一個簇點的節點個數為:

(15)

為了方便分析,我們提出一個計算節點密度電量比Ψ的能量補充算法.其中Ψ滿足以下公式:

(16)

MC將移動到與Ψmin相對應的簇點處充電.實際上,該HNDLE-CB算法是選擇β越大Es越小的節點優先充電.

算法2.HNDLE-CB算法的偽代碼.

Input:set of initialize anchorsA0,recharge sensorsSi,sensor nodesN,coverage radiusRr,

Output:set of anchors A,recharging sequence r

1:while(！convergence)do

2: for(i=0;i

3: for(j=0;j

4: ifi∈Α0andLij

5:jbelongs toi

7: end if

8: end for

9: end for

10:end while

11: if there is node m,dmi>Rr

12: m as isolated node

14: end if

15: ?=|Si|

16:while (t≤Τ and ?!=null) do

17: for(i=0;i

19: Ψj=Es(j)/β

20:byBubble sort , array[j]←Ψj

21: end for

22: add array tor

23:end while

5 性能分析

本文構建了無線可充電傳感器網絡應用場景的仿真環境,選取了一塊 30m×30m 的區域,并隨機布置基站和25～200個傳感器節點,將MC部署在所有傳感器節點位置的中心處,所有傳感器節點都具有相同的數據接受能力,并且節點與MC擁有相同的諧振頻率,可接受MC發送的能量.假設每一個傳感器節點的初始電量為10000(unit),在收發消息的能量消耗過程中,當剩余能量達到了閾值250(unit)時,這些傳感器節點會被放入充電服務池中,并依次向MC發送充電請求.MC計算服務池中節點的密度電量比Ψ作為充電優先級,依次給節點充電,這是HNDLE-CB算法的實驗過程.詳細的仿真參數如表2所示.本文基于C#仿真平臺對HNDLE-CB算法進行性能分析,并把Cellular MWRN[12]算法與本文4.1.2節中描述的隨機初始化簇點的RI-CB MWRN算法進行性能對比.我們從錨點個數、節點的失效率、網絡的生存時間以及充電成本這四個指標來對上述三種算法進行性能分析.

圖5 簇點生成算法Fig.5 Cluster point generation algorithm

表2 仿真參數
Table 2 Simulation parameters

參數名參數值監測區域30m×30m傳感器初始電量10000(unit)節點個數[25,200]通信半徑20mMC覆蓋半徑[3,5] MC的移動速度5m/s數據包大小100bytes充電速率[100,300]能量閾值250(unit)網絡覆蓋概率0.8

5.1 錨點個數

本組實驗討論各算法分別產生的錨點個數的情形.從圖6(a)可以清楚地看到,隨著節點數量的增加,錨節點數量也隨之增加.理論上,錨點的數量可能會導致MC充電成本的增加.本文提出的HNDLE-CB算法產生的錨點個數始終低于其他兩種算法產生的錨點個數.這是因為本算法通過網絡覆蓋率以及節點的度數合理的規劃出錨點的生成過程.從圖6(b)中可以看到隨著覆蓋半徑的增大,錨點個數呈現下降的趨勢.這是因為諧振中繼器的覆蓋半徑越大,覆蓋的節點個數越多,所需要的錨點就會越少.

5.2 節點失效率

本組實驗討論各算法分別產生的節點失效率的情形.從圖6(c)可以清楚地看到,當節點個數從25到200呈現線性增長時,節點的失效率也隨之增長.這是因為節點數量增多時,在一段時間內節點缺電個數的幾率會增大,這時會向MC提出更多的充電請求,使得MC的充電負擔過重,一旦超過MC的服務能力時,死亡節點的數量便會增加,因此各算法所得的節點失效率都是呈增長趨勢.而本文提出的HNDLE-CB算法的節點失效率相較于Cellular MWRN、RI-CB MWRN始終更低.這是由于本策略會提出一種充電優先級算法,會優先選擇密度較為集中并且缺電情形較為嚴重的節點充電,極大的避免了節點快速陷入饑餓狀態甚至死亡,因此該算法能最大程度減少網絡中缺電節點的死亡數量.如圖6(d)所示,當充電效率提高時,MC有更多的時間去給缺電節點充電,因此失效率會下降.

圖6 3種算法在4個不同指標的性能對比Fig.6 Performance comparison of three algorithms in four different indicators

5.3 充電成本

本組實驗討論各算法分別導致的充電成本的情形.圖6(e)展示了節點數量與充電成本之間的關系.當節點個數為達到125時,充電成本呈增長趨勢,而當節點個數超過125時充電成本有所下降.出現這種現象的原因是當節點個數較少時,提出充電請求的節點的分布比較稀疏,導致有些節點距離MC的位置較遠,MC為各種節點充電的過程中將大量的工作花費在移動,使得MC的移動距離增大,從而增加MC的充電成本.而當節點個數達到一定程度時,缺電節點的個數相應也會增加,導致服務池中排滿了許多需要充電的節點,但MC此時只能在較近的距離內發現滿足條件的缺電節點,來不及響應距離較遠的待充電節點,一旦等待時間變久即失效,于是MC一直在為自己附近的缺電節點充電,使得MC的移動總距離減小,因而充電成本下降.而圖6(f)中,三種算法的充電成本都會隨著充電效率的增加而增大.因為充電效率的提高,MC為節點充電的速度就越快.那么為完成更多的充電請求MC的移動總距離就會越大.

5.4 網絡生存時間

本組實驗討論各算法的網絡生存時間的情形.從圖6(g)中可以看出,隨著節點個數的增加,網絡生存時間也在相應降低.該圖證明了當節點數量增多時,網絡的生存周期呈遞減趨勢的現象.這是由于隨著節點數量增多時,MC無法滿足目標節點的充電請求,使得節點死亡個數增多從而導致網絡停止工作.在圖6(h)中,隨著充電速率的遞增,網絡生存周期不斷增長.這是因為當充電速率增加時,MC為節點的充電效率得到提升,可以在同樣的時間內為請求節點提供高效的充電服務,因此節點的死亡率會下降,從而增加了網絡的生存周期.

6 結 語

無線充電技術可以達到延長網絡的生命周期,能夠有效處理現階段傳感器節點能量不足的問題.為了達到更優的效果,本文研究如何基于聚類進行分簇尋找錨節點并提出一種高效的HNDLE-CB多跳能量補充策略.該策略根據網絡覆蓋率計算簇點個數,結合節點的連通度初始化簇點位置,聚類迭代得到簇點的最終位置,通過節點密度電量比率Ψ計算傳感器節點的充電優先級,按照這樣的充電方式優先為分布密集且容易失效的節點充電,能夠適應動態的網絡變化,滿足正常充電的需求.廣泛的仿真結果證明了HNDLE-CB策略與其他策略相比,能夠在一定程度上有效降低節點失效率,提高網絡充電效率.