基于螢火蟲算法的無線可充電傳感器網絡的充電策略

雷 蕾， 陳宏濱

(桂林電子科技大學 信息與通信學院，廣西 桂林 541004)

無線傳感器網絡(wireless sensor networks，簡稱WSNs)已經得到了廣泛的應用，然而，網絡中每個傳感器節(jié)點通常由能量有限的電池供電[1]，能源是阻礙WSNs部署的障礙之一。盡管以往的研究提出了許多節(jié)能方案[2-3]來解決能量不足這一約束，但網絡壽命仍然受到固有的限制。因此，相關學者又從為傳感器網絡補充能源方面延長網絡的生命周期，主要可以歸納為更換電池、能量搜集方法、無線能量轉換。很多WSNs部署在條件惡劣的野外，更換電池[4]維護成本高。能量搜集方法對環(huán)境敏感，發(fā)電過程不可控制[5-7]。與可再生能源采集技術相比，無線能量傳輸技術能為無線可充電傳感器網絡 (wireless rechargeable sensor networks，簡稱WRSNs)中的傳感器提供更可靠的能量供應?，F(xiàn)有方法側重于使用無線充電設備 (wireless charging equipment，簡稱WCE)，文獻[8]通過WCE對傳感器進行充電，這一技術能為傳感器提供更加穩(wěn)定的能量，文獻[9-10]使用WCE聯(lián)合完成充電和收集數(shù)據(jù)的任務。

近年來，日趨成熟的無線能量傳輸技術為解決傳感器節(jié)點能耗問題帶來曙光，利用WCE來補充傳感器能量引起了研究者的廣泛關注。文獻[11]提出了一種聯(lián)合網絡中路由活動和充電的策略來延長傳感器網絡的生命周期，為網絡補充能量的同時，有效提高了網絡中的能量利用率。文獻[12]考慮WCE周期性地在無線傳感器網絡中移動，并同時對多個傳感器節(jié)點進行充電，通過離散化和新的線性化方法，得到了可證明的近似最優(yōu)解。文獻[13]指出了目前在線充電機制面臨的挑戰(zhàn)：避免待充電節(jié)點由于長時間得不到充電而失效，同時降低充電器的移動消耗，達到饑餓節(jié)點比率與充電器充電代價的平衡。文獻[14]研究了無線傳感器網絡中的按需能量補充問題，并分析了一種簡單而有效的具有搶占機制的最鄰近策略(NJNP)，這種能量只考慮了空間因素，造成該策略的一些性能并不優(yōu)越。但是NJNP策略為按需充電過程的性能奠定了堅實的基礎，其性能在理論上得到了驗證，一直作為評估更高級方案的完美基準。

對于WRSNs的充電策略，不僅要考慮WCE對傳感器節(jié)點的充電順序，而且還要規(guī)劃好WCE對每個待充電節(jié)點的充電時隙。在以往研究中，均著力于固定的充電時隙，但其實每個節(jié)點的能量消耗率都具有動態(tài)性，每次迭代也具有差異性，因此動態(tài)充電時隙的必要性在整個充電過程中顯而易見。文獻[13-14]則是對所有請求充電的節(jié)點充電，直至節(jié)點被充滿為止。

鑒于此，提出一種基于螢火蟲算法的在線充電策略(JCDRE)來滿足網絡中節(jié)點的動態(tài)能耗需求，并設置合理的動態(tài)充電時隙。通過與2個基準非周期充電策略的仿真對比表明，本策略在性能方面優(yōu)于基準方案。

1 系統(tǒng)模型

圖1為無線可充電傳感器網絡模型，在一個L×L平方區(qū)域內隨機部署m個節(jié)點和一個WCE。在WCE與節(jié)點是一對一充電的情況下，該充電方式保證了無線能量傳輸?shù)淖罡咝省?/p>

圖1 無線可充電傳感器網絡模型

1.1 節(jié)點模型

在整個WRSNs中，隨機部署m個節(jié)點，N={n1,n2,…,nm}，這些節(jié)點均為同質節(jié)點，具有相同的結構和性能，位置坐標表示為S={(ai,bi),i∈1,2,…,m}。在監(jiān)測環(huán)境的任務中，記無線傳感器節(jié)點i在t時刻產生數(shù)據(jù)的速率為Ri(t)，在承擔數(shù)據(jù)路由任務時，記無線傳感器節(jié)點通過單跳的方式向基站(base station，簡稱BS)發(fā)送數(shù)據(jù)的速率為gi(t)。節(jié)點i均配備一個最大容量為Emax的電池，節(jié)點i的初始狀態(tài)并非全部都在滿荷狀態(tài)，先假設各個節(jié)點均有部分程度的消耗，節(jié)點的初始能量為ei，i∈1,2,…,m。節(jié)點i在整個工作過程中，數(shù)據(jù)傳輸和數(shù)據(jù)感知會導致能量消耗，感知數(shù)據(jù)的過程中能耗很低，因此研究中忽略感知數(shù)據(jù)產生的能耗[15]。

在整個迭代的工作輪里，節(jié)點i一部分時間用來感知并傳輸數(shù)據(jù)，另一部分時間用來接收WCE的能量補給，以維持自身的生命，對于節(jié)點i可分為ti,transmit、ti,charge兩個時隙，其中ti,transmit為節(jié)點i的傳輸數(shù)據(jù)的時間，ti,charge為節(jié)點i的補充能量時間，二者之間互不影響。

1.2 充電模型

1.2.1 基站

BS具有雙重角色，既可以作為WCE的服務站，調整充電設備的充電策略以及為充電車補充電量，還可以匯集由節(jié)點發(fā)送來的所有消息，其在WRSNs中的初始坐標設為(L/2,L/2)。

1.2.2 WCE

2 問題描述

在提出和分析問題之前，首先提出一些定義：

定義1節(jié)點壽命：對于節(jié)點而言，它有一個最低能量閾值Emin，當節(jié)點的剩余能量因長期未得到補充而達到了最低閾值時，該節(jié)點的生命周期就結束。

定義2網絡生命周期：對于一個WRSNs而言，當節(jié)點死亡率達到比例ε時，存活的節(jié)點無法維持網絡的正常運行，此時認為達到了網絡生命周期。

由上述模型可知，節(jié)點i的數(shù)據(jù)生成率為Ri(t)，發(fā)送給基站的數(shù)據(jù)率為gi(t)，傳輸數(shù)據(jù)的時間為ti,transmit，充電時間為ti,charge，節(jié)點i的能耗為數(shù)據(jù)感知的能量消耗和數(shù)據(jù)傳輸?shù)哪芰肯闹?。既然忽略了感知?shù)據(jù)所造成的能耗，那么節(jié)點i的能耗Ei1就只有傳輸數(shù)據(jù)所消耗的部分，即

Ei1=Pi1ti,transmit,

(1)

節(jié)點i傳輸數(shù)據(jù)能耗功率為

Pi1(t)=uiRi(t)=uigi(t)，

(2)

WCE為節(jié)點i充電的充電功率為U,充電時間為ti,charge，所以節(jié)點i被WCE充電的能量為

Ei,2(t)=ti,chargeU，

(3)

節(jié)點i在t時刻的剩余能量為

Ei,r(t)=ei-Ei,1(t)+Ei,2(t)，

(4)

其中ei為節(jié)點的初始能量。

為保證節(jié)點不死亡，且剩余能量不超過電池容量，有如下約束：

Emin≤Ei,r(t)≤Emax。

(5)

WCE的初始位置為BS的位置(L/2,L/2)，且其電池容量為C。WCE的能耗分為移動的能量消耗E1(t)和為節(jié)點充電的能量消耗E2(t),

(6)

3 JCDRE算法步驟

NJNP(nearest job next with preemption)和FCFS(first come first serve)是被眾多研究者所認可的2種充電策略。NJNP從空間位置考慮請求充電節(jié)點的充電順序，距離WCE最近的請求節(jié)點最先被充電；FCFS從時間角度出發(fā)，最先提出請求充電節(jié)點將會按序被充電。本研究提出一種基于螢火蟲算法的充電策略JCDRE，聯(lián)合考慮WCE與請求充電節(jié)點的位置遠近及節(jié)點實時剩余能量的情況。

請求充電的節(jié)點i對于WCE來說都具有不同程度上的吸引力，節(jié)點i與WCE之間的距離di,W和節(jié)點的剩余能量Ei,r(t)分別為螢火蟲算法的2種吸引力分力。

節(jié)點i對于WCE的吸引力為

(7)

3.1 充電請求級別

當節(jié)點i在t時刻的剩余能量達到Er1時，節(jié)點i發(fā)出一級充電請求，其發(fā)送請求給基站的內容及格式為Si=〈Di,Ei,r(t),t1(i,j),charge1〉,其中Di包含請求充電節(jié)點i的序號及位置坐標，Ei,r(t)為剩余能量，t1(i,j)為節(jié)點i第j次發(fā)送一級請求的時間，charge1為發(fā)送一級充電請求的標志，用于區(qū)別節(jié)點發(fā)送給基站的數(shù)據(jù)，存儲在充電池H1中。

當節(jié)點i在t時刻的剩余能量達到Er2時，節(jié)點i發(fā)出二級充電請求，其請求的內容及格式為Si=〈Di,Ei,r(t),t2(i,j),charge2〉,其中:t2(i,j)為節(jié)點i第j次發(fā)送二級請求的時間，charge2為充電請求的標志，存儲在充電池H2中。另外，記Er1=θ1Emax，Er2=θ2Emax，其中θ1>θ2。

3.2 吸引力級別

(8)

二級瀕危節(jié)點的吸引力為

(9)

其中Ψ、λ1、λ2均為常數(shù)，且Ψ>1，1>λ2>λ1>0。

3.3 仿真示例

如圖2所示，節(jié)點1～8的初始能量設置為E1 r(t)

圖2 WCE移動軌跡圖

1)WCE從基站BS出發(fā)，為節(jié)點1充滿電后，下一個充電節(jié)點選擇的是節(jié)點2，因為節(jié)點2的剩余能量最低，且為二級饑餓節(jié)點，剩余能量的權重因子較大，使得節(jié)點2對WCE的吸引力最大；

3.4 充電時隙

充電時隙的設置對于整個充電策略也至關重要，需要綜合考慮被充電節(jié)點和待充電節(jié)點的實際情況做出策略改變，在選中下一個充電節(jié)點的序號后，使其在充電一段時間后，更新充電池H1和H2，若該節(jié)點值得繼續(xù)被充電，則WCE仍在原處為該節(jié)點充電，但若有另一個節(jié)點更值得被充電，即其吸引力大于該節(jié)點，則WCE會在未給它充滿的情況下離開，去下一個請求節(jié)點。這將使得等待充電的節(jié)點減小了充電延遲，同時也有效地減小了節(jié)點的死亡率。同時，對于H1和H2里的節(jié)點，它們的充電時隙也應該是不同的。H1里瀕危節(jié)點的充電時隙為

(10)

H2里瀕危節(jié)點的充電時隙為

(11)

其中，ξ1、ξ2為常量，且ξ1<ξ2。t1i、t2i都是與剩余能量相關的變量，剩余能量越低，被充電時間越多。

3.5 算法步驟

輸入：節(jié)點數(shù)，節(jié)點的隨機坐標，各節(jié)點初始化能量、動態(tài)數(shù)據(jù)率，WCE的坐標、移動速度及載能，BS的坐標。

輸出：待充電節(jié)點序號及充電時隙。

1) 根據(jù)式(1)～(4)計算所有節(jié)點的剩余能量。

2) 判斷是否有節(jié)點達到瀕危及分別是幾級瀕危狀態(tài)，放入對應充電池。

3) 分別計算瀕危節(jié)點到WCE的距離。

4) 根據(jù)式(8)、(9)，相應地由距離和剩余能量的狀況綜合決定待充電節(jié)點。

5)判斷被選中待充電節(jié)點的剩余能量是否能夠滿足WCE移動到此處，若滿足，則執(zhí)行步驟6)，否則，在該節(jié)點的充電池刪除該節(jié)點，并返回步驟2)。

6)相應地根據(jù)式(10)、(11)得到充電時隙。

7)更新WCE坐標，并判斷是否有死亡節(jié)點，其中死亡節(jié)點不再被充電。

算法流程如圖3所示。

圖3 算法流程

4 仿真分析

4.1 參數(shù)分析

在式(9)中，參數(shù)Ψ是針對一級瀕危節(jié)點和二級瀕危節(jié)點而言吸引力的差距，不包括剩余能量和距離這2種吸引力分力帶來的差異。

圖4為參數(shù)Ψ對于網絡中節(jié)點死亡率的影響。死亡率是指WRSNs所有能量低于死亡閾值的死亡節(jié)點占所有節(jié)點的比例，且設定WRSNs規(guī)模為100個節(jié)點隨機部署在100 m×100 m的范圍內。從圖4可看出，JCDRE充電策略明顯優(yōu)于基準策略NJNP、FCFS。2種基準算法從一開始就有一部分節(jié)點由于充電不及時導致能量耗盡而死亡，隨后死亡率持續(xù)增高，且明顯高于JCDRE充電策略。此外，當Ψ取值為2.5時，死亡率也低于Ψ取其他值的情況。因此，仿真時將參數(shù)Ψ取值為2.5。

圖4 參數(shù)Ψ對死亡率的影響

4.2 仿真結果

為了更好地展現(xiàn)JCDRE算法與基準算法NJNP、FCFS的對比，將WRSNs中節(jié)點的初始能量進行了設定，始終使得網絡在初始狀態(tài)時存在5%的瀕危節(jié)點，且在100 m×100 m的網絡內分別部署了100、120、140、160、180、200個節(jié)點，分別進行仿真。參數(shù)設置如表1所示。

表1 參數(shù)設置

圖5為不同節(jié)點數(shù)下出現(xiàn)首個死亡節(jié)點的時間。從圖5可看出，相同環(huán)境下，隨著節(jié)點數(shù)的增多，出現(xiàn)首個死亡節(jié)點的時間越早，因為節(jié)點數(shù)越多，單個WCE要執(zhí)行的能量補充越多，導致能量最低的節(jié)點越早地因得不到能量補充而死亡，且JCDRE明顯優(yōu)于基準策略NJNP、FCFS，首個死亡節(jié)點的出現(xiàn)時間始終最遲，且在100個節(jié)點的規(guī)模中性能優(yōu)勢最明顯。

圖5 出現(xiàn)首個死亡節(jié)點的時間

圖6為不同節(jié)點數(shù)下的網絡生命周期。從圖6可看出，相同環(huán)境下，隨著節(jié)點數(shù)的增多，網絡的生命周期變短，這因為單個WCE需要為更多節(jié)點提供能量補充，導致很多節(jié)點因長時間未得到充電而達到死亡閾值，因而更早達到網絡生命周期。同時，JCDRE在此性能上較其他2種基準策略有明顯優(yōu)勢，其網絡生命周期始終大于基準策略。

圖6 網絡生命周期

圖7為以100個節(jié)點為例的充電延遲tlatency變化趨勢。從圖7可看出，隨著時間增大，WRSNs的充電延遲持續(xù)增加，而JCDRE的充電延遲低于基準策略，這表明JCDRE充電策略使得網絡中請求充電節(jié)點盡可能早地得到能量補充，以降低因能量耗盡而達到死亡閾值的風險。

圖7 充電延遲

圖8為不同節(jié)點數(shù)下WRSNs在生命周期內收集到的有效數(shù)據(jù)。從圖8可看出，隨著節(jié)點數(shù)的增多，數(shù)據(jù)收集量并未增多，因為節(jié)點數(shù)增多會導致網絡過早地進入癱瘓狀態(tài)，導致有效的生命周期內無法采集到更多有效數(shù)據(jù)，且JCDRE策略收集到的有效數(shù)據(jù)量明顯高于其他2種基準算法。

圖8 有效數(shù)據(jù)

5 結束語

考慮到WRSNs中各個節(jié)點數(shù)據(jù)率不同，不適于周期性離線充電策略，提出了一種基于螢火蟲算法的在線充電策略，以延長網絡的生命周期。本充電策略聯(lián)合考慮節(jié)點的實時剩余能量與節(jié)點和WCE之間的動態(tài)距離，并分別作為螢火蟲算法的2種吸引力分力，綜合時間和空間2個方面的因素，尋找最佳的待充電節(jié)點，并為待充電節(jié)點設定與剩余能量相關的動態(tài)充電時隙。為了盡量減少WCE連續(xù)在瀕危的2個節(jié)點之間來回充電，此策略將距離導致的吸引力設置得比重較大，以減少WCE過多移動導致性能降低。仿真結果表明，本充電策略在網絡生命周期、充電延遲、有效數(shù)據(jù)收集等性能上比其他2種基準充電策略都更好。