無線傳感器網絡中的充電調度算法

曲立軍 黨 鑫 武繼剛

(1.天津工業大學計算機科學與軟件學院 天津 300387)(2.廣東工業大學計算機科學與技術學院 廣州 510006)

無線傳感器網絡中的充電調度算法

曲立軍1黨 鑫1武繼剛2

(1.天津工業大學計算機科學與軟件學院 天津 300387)(2.廣東工業大學計算機科學與技術學院 廣州 510006)

近年來,無線傳感器網絡在監控、檢測等領域扮演著越來越重要的角色。然而,隨著無線傳感器網絡規模的不斷擴大,傳感器節點的電池容量成為制約其生命周期的主要瓶頸。為了解決這種能源瓶頸問題,無線可充電傳感器網絡引起了學者們的廣泛關注。論文研究了動態請求(On-Demand)的可充電傳感器網絡中的充電車任務調度策略。該策略將充電服務池中的節點分為兩類,充電車在任務執行過程中,可以按照傳感器節點充電請求的迫切程度以相應的優先級向其提供充電服務。論文提出的算法用來解決充電車任務調度的問題,該算法可使任務調度系統的充電服務錯失率(Charging Missing Ratio)平均降低94.7%,而平均充電服務吞吐量(Charging Throughput)的損失可控制在9.91%以內。

無線充電; 無線傳感器網絡; 充電調度; 插入法

Class Number TP391

1 引言

無線傳感器網絡(Wireless Sensor Networks)是由部署在監控區域內的大量傳感器以自組織和多跳的方式構成的一種新型網絡[1～2]。傳統傳感器網絡中的傳感器節點是由電池供電的,電池容量決定傳感器節點的可工作時長,所以電池容量成為制約整個傳統傳感器網絡生命周期大小的主要因素之一[3]。為了延長傳統傳感器網絡的生命周期,在過去幾十年里很多的節能措施被提出,以減少傳感器節點的能源消耗或者平衡傳感器節點之間通信的能源消耗[4]。然而,這并沒有從根本上解決傳感器網絡的能源瓶頸問題。

為了解決傳感器網絡的能源瓶頸問題,研究人員利用可再生能源為傳感器節點提供能源供應,例如風能、太陽能等[5～8]。但是,由于自然環境變化的不確定性,可再生能源的收集率不穩定且很難預測,從而無法為整個傳感器網絡保證持續不斷且穩定的能源供應。

近年來,基于強磁共振的無線電力傳輸技術引起了廣泛的關注,研究人員通過利用無線能量補給的方式向傳感器網絡提供能量供應,這種新型的傳感器網絡被稱為可充電無線傳感器網絡(Wireless Rechargeable Sensor Networks,WRSNs)[9～11]。在WRSNs中,一個或多個裝有無線電力傳輸設備的移動充電車(Mobile Charger,MC)定期地向網絡中的傳感器節點提供充電服務,從而使傳感器節點能夠得到穩定持續的能源續航。

文獻[12]已證明利用無線電力傳輸技術,在2～3英尺距離內對功率為60瓦設備的電力傳輸效率可以提高75%。因此,無線充電技術已成為解決無線傳感器網絡能源瓶頸問題的一個有效的措施。文獻[13]分析并解決了可充電傳感器網絡中的移動充電車數據收集與充電路徑問題。文獻[14]通過利用經典的TSP算法找到傳感器網絡中的一條最短哈密頓回路,讓充電車周期性地遍歷這條回路上的傳感器節點。文獻[15]研究了通過多個移動充電車為傳感器網絡提供高效的充電服務,為可充電無線傳感器網絡提出了一種新穎的充電模式,即協同移動充電模式。文獻[16]研究了移動數據收集車問題,在能夠保證傳感器持續工作的條件下,充電車還可以進行數據收集工作。文獻[17]利用經典的K-means算法解決了無線可充電傳感器網絡中的最大化充電服務吞吐量問題。文獻[18]對傳感器每次充電前的剩余電量和移動充電車的充電路徑優化作出了卓越貢獻。文獻[19]研究了基于動態請求(On-Demand)的可充電無線傳感器網絡,與傳統的可充電無線傳感器網絡相比,在動態請求的網絡中,充電車本身可以獨立接收來自傳感器節點的充電請求,并獨立完成充電調度。

本文研究的是動態請求的無線可充電傳感器網絡,主要貢獻如下: 1) 針對動態請求的傳感器網絡,建立了最大化充電服務吞吐量問題的數學模型,并將充電服務池中的節點按請求充電的迫切程度分為兩類,以便充電車能夠按照傳感器節點充電請求的迫切程度以相應的優先級向其提供充電服務。 2) 提出了基于最臨邊插入策略的充電車任務調度近似算法,利用該近似算法可以得到控制充電車任務調度的任務序列。算法將所有屬于高迫切程度類別的節點優先插入到任務序列中,然后再將屬于低迫切程度類別的節點盡量插入到任務序列中。 3) 實驗結果表明,與文獻[19]提出算法相比,本文所提出的算法及調度策略,可使監測周期內充電任務調度系統的充電服務錯失率(Charging Missing Ratio)降低94.7%,而平均充電服務吞吐量的損失可控制在9.91%以內。

2 基本概念與問題描述

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

首先對文中使用的記號給出如下定義。如圖1所示,G(V,BS,MC)表示二維平面區域上的可充電傳感器網絡。其中,V={v1,v2,…,vN}表示網絡中的傳感器節點集合,網絡節點數為N。BS表示網絡中的充電服務站(基站),它負責分析和匯總傳感器節點的監測數據。MC表示一輛裝有無線充電裝置的充電車,初始狀態下,MC位于服務站BS中,當網絡中的部分傳感器因電池電量過低而需要充電時,充電車MC會從服務站BS出發向需要充電的節點提供充電服務,最后再返回服務站BS。

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

Ci表示節點vi的電池容量,當節點vi的剩余電量低于額定閾值Mi=α·Ci(0<α<1)時,會向充電車MC發送充電請求。充電服務池(Charging Service Pool)用來存放請求充電服務的節點,用集合Sv表示。當充電車接收到來自節點vi的充電請求后,會將vi加入到服務池Sv中。

充電車是一種依靠能源提供能量支持的移動充電服務設備,在每次充電任務調度過程中,它都會從服務站BS出發,向充電服務池中的節點提供充電服務,最后返回服務站BS。由于它移動和所提供的充電服務都需要消耗自身的能量,所以規定,充電車必須在固定時間T之內返回服務站BS,即充電車的最大充電服務時間為T。

本文研究的是動態請求的可充電傳感器網絡,充電車在任務執行過程中仍然可以接收來自節點的充電請求,并將新的請求節點加入到服務池中。而新加入的請求充電節點,可能會改變充電車當前的充電任務調度策略。

圖2 充電服務吞吐量求解示例

2.2 充電服務吞吐量

我們延用文獻[17]中定義的充電服務吞吐量(Charging Throughput)來衡量充電車任務調度算法性能。充電服務吞吐量是指在最大服務時間T之內,充電車從服務站出發最后返回服務站期間所提供充電服務的節點數。充電服務吞吐量值越大,表明相應的調度算法性能越佳。因此,充電車任務調度問題的目標可概括為,在最大服務時間內找到一條最佳的充電任務路徑,使得充電車達到最大的充電服務吞吐量。例如在圖2(a)中有9個請求充電的節點,而在最大充電服務時間T之內,充電車最多只能向其中6個節點提供充電服務,所以最大充電服務吞吐量為6。

文獻[19]提出了名為NJNP的調度算法,該算法主要運用了貪心策略,充電車在完成對現節點充電服務后,總是貪心地選擇距離代價最小的請求充電節點作為下一個服務節點,該算法提供的任務調度策略可以達到較優的充電服務吞吐量。文獻[17]提出了一種基于K-means聚類的圖劃分算法,該算法的基本思想是,將傳感器網絡中請求充電的節點劃分成K個不相關的獨立團,選擇其中一個充電代價最小的團,然后對該團中的所有的節點提供充電服務。相比于NJNP算法,該算法在節點密集型傳感器網絡中,能達到較優的充電服務吞吐量。

在動態請求的傳感器網絡中,傳感器節點會在電量過低時發出充電請求。由于網絡規模的龐大和傳感器耗電率的不穩定性,一般的調度策略無法保證對每一個發送充電請求的節點都能提供及時的充電服務。所以部分傳感器會因未及時向其提供充電服務而暫時停止工作,這影響了傳感器網絡工作的整體穩定性。

定義1 充電服務錯失率(Charging Missing Ratio)是指,在可充電傳感器網絡中,單位時間內發生傳感器因電量耗盡(未及時充電)而停止工作事件的次數。其值越低表明網絡的整體穩定性越高。

文獻[17,19]提出的啟發式算法過于貪心,充電服務錯失率過高,提供的調度策略會遺漏掉那些充電耗費代價大但迫切需要得到充電服務的節點,而這些節點可能會因電量耗盡而停止工作。例如在圖2(b)中,黑色節點和灰色節點都表示當前請求充電的節點。其中,黑色節點在該充電調度周期中必須向其提供充電服務,否則會因電量耗盡而停止工作。而灰色節點的充電優先級相對于黑色節點要低,如果下兩個或兩個以上個充電周期之內不向其提供充電服務,灰色節點將會停止工作。所以,充電車在此次執行任務的過程中,應盡可能地為黑色節點提供充電服務,否則黑色節點很可能在下次充電周期給予充電之前停止工作。所以為了保證整個網絡連續不斷地高效工作,提高網絡整體穩定性,在充電調度策略中,充電車應該對發出迫切請求的節點(黑色節點)優先提供充電服務。相比較于圖2(a),考慮此情況,圖2(b)中充電車最多只能向其中5個請求充電的節點提供充電服務,所以最大充電服務吞吐量為5。

因此,本文研究充電車任務調度策略的目標可概括為,在盡可能保證網絡整體穩定性(低充電服務錯失率)的基礎上,在最大服務時間內找到一條最佳的任務路徑,使得充電車達到最大的充電服務吞吐量。而文獻[17,19]所研究的充電車任務調度策略并沒有考慮充電服務錯失率對網絡整體穩定性的影響。最大化充電服務吞吐量問題的求解數學模型參見第3節。

3 最大化充電服務吞吐量問題的公式化

為了使網絡中請求充電的節點盡量得到及時的充電服務,我們將充電服務池中的節點分為兩類。第一類為迫切請求充電服務的節點(若當前充電周期內不向其提供充電服務,節點很可能會停止工作),用集合Urg(Urgent Charging Request Node)表示該類節點;另一類是普通請求充電服務的節點(若兩個或兩個以上充電周期內不向其提供充電服務,節點很可能會停止工作),用集合Ord(Ordinary Charging Request Node)表示該類節點。Ord與Urg滿足如下關系式:

Urg∩Ord=?

Urg∪Ord=Sv

當節點vi的剩余電量低于額定閾值Bi=β·Mi=α·β·Ci(0<β<1)時,會向充電車發送迫切的充電請求,充電車接收到來自節點vi的迫切充電請求后,會將vi加入到集合Urg中(若vi原本在集合Ord中,將vi從集合Ord中刪除)。而當充電車接收到來自節點vi普通充電請求后,將節點vi加入到集合Ord中。

令充電服務池Sv={v1,v2,…,vn},請求充電的節點數目為n。令v0表示充電服務站BS,充電車對每個節點的充電時間固定為常數C,充電車從節點vi移動到vj所需花費時間為tij。由于回路中的節點數等于邊數,所以這里用充電車所經過的邊數減1表示充電車的充電服務吞吐量:

xi,j∈{0,1};i,j=0,1,…,n

(1)

為了確保充電車每次執行任務必須是從BS出發,最后返回BS,有如下約束條件:

xi,j∈{0,1};i,j=0,1,…,n

(2)

為了確保在任務周期中,只能向請求充電的節點提供至多一次充電服務,并保證任務路徑的連通性,有如下約束條件:

?vk∈Sv;xi,j∈{0,1};i,j=0,1,…,n

(3)

為了確保充電車必須優先考慮對發出迫切請求充電的節點提供充電服務,有如下約束條件:

xi,j∈{0,1};i,j=0,1,…,n

(4)

為了確保充電車每次執行任務的服務時間必須不超過最大服務時間T,有如下約束條件:

xi,j∈{0,1};i,j=0,1,…,n

(5)

最大化充電服務吞吐量問題可以表示為如下非線性0-1整數規劃問題:

4 算法思想及步驟

4.1 算法思想

最鄰邊插入法(Nearest Insertion Method,NIM)是解決TSP問題的一個經典啟發式算法,其算法的基本思想是通過選取插入代價最小的節點,構造一個頂點數依次遞增的序列圈,最后得到一個哈密頓回路即為TSP問題的近似解。

最臨邊插入法的插入代價的計算方法如圖3所示,D節點插入序列(A,B,C,A)的代價為3+3-3=3,E節點插入序列(A,B,C,D)的代價為3+3-5=1,而1<3,所以優先將D節點插入序列(A,B,C,A)中得到序列(A,D,B,C,A)。

圖3 最臨邊插入法插入策略示例

本文以最鄰邊插入法的算法思想為基礎,提出了名為RECHA的最臨邊插入法,該算法所提供的充電任務調度策略,相對于文獻[19]提出的NJNP算法,不僅可以保證具有相近的充電服務吞吐量,而且能夠大大降低充電車任務執行過程中的充電服務錯失率,提高傳感器網絡整體穩定性。

RECHA算法由兩個子過程構成,第一個子過程名為SCIM,該過程用來得到充電車的初始任務序列,第二個子過程名為DCIM,該過程用來得到充電車動態任務序列。SCIM與DCIM過程具體描述詳見4.2及4.3節。RECHA算法具體描述及其時間復雜度分析詳見4.4節。

在本文提出的RECHA算法所提供的調度策略中,充電車一直存儲著一個有序序列,該序列被稱為充電決策序列。充電車總是按照充電決策序列提供的充電順序向序列中的節點提供充電服務,該序列是動態變化的,且滿足以下兩點規律:

1) 充電車總是將迫切請求節點優先插入到充電決策序列中。

2) 充電車在任務執行過程中,接收到了來自某節點迫切充電請求,若此時充電決策序列已滿,則會按算法所提供的策略替換掉充電決策序列中的某個普通請求節點。

本文提出的算法遵循如下三點合理且現實可行的基本假設:

1) 充電車完成對某節點的充電服務后,發現充電決策序列中已無可充電節點且此時充電車的剩余電量仍充足,則充電車一直會在該點停留,直至接收到新的充電請求或者充電車剩余任務時間只能支持充電車返回到服務站后才會離開該點。

2) 充電車執行完一趟任務返回服務站BS后,執行下一趟充電任務所需的準備時間可忽略不計。

3) 節點電量過低時,會向服務站發送充電請求,當服務站接收到來自節點的充電請求時,會將該條充電請求轉發給充電車,此請求過程可視為節點直接向充電車發送充電請求。

4.2 SCIM過程

當充電車準備從服務站出發執行充電任務前一刻,SCIM過程用來生成一個初始的充電決策序列L,SCIM過程具體描述如下:

Procedure.1: SCIM

/*static classification insertion method*/

Input:Urg、Ord、T

Output:L

Step1:在Urg中選取距離v0時間代價最小的節點vi,將vi從Urg中刪除(若Urg為空,從Ord中選取),構建序列L=(v0,vi,v0)。

Step2:若Urg為空,執行Step6,否則執行Step3。

Step3:確定一點vk(vk∈Urg)和兩點vi,vj(vi,vj是L中任意連續兩點)使得插入代價(tik+tkj-tij)最小。將vk插入到vi與vj之間,得到序列(…,vi,vk,vj,…)。

Step4:判斷序列(…,vi,vk,vj,…)的執行時間是否大于T。若大于T,執行Step6;否則執行Step5。

Step5:更新L=(…,vi,vk,vj,…),令Urg=Urg/vk,并返回Step2;

Step6:若Ord為空退出;否則執行Step7。

Step7:確定一點vk(vk∈Ord)和兩點vi,vj(vi,vj是L中任意連續的兩點)使得插入代價(tik+tkj-tij)最小。將vk插入到vi與vj間得到序列(…,vi,vk,vj,…)。

Step8:判斷序列(…,vi,vk,vj,…)的執行時間是否大于T。若大于T,退出;否則執行Step9。

Step9:更新L=(…,vi,vk,vj,…),Ord=Ord/vk,并返回Step6。

SCIM算法對應的流程圖如圖4所示。

圖4 SCIM過程流程圖

4.3 DCIM過程

本文研究的是動態請求的無線傳感器網絡,在充電車任務執行過程中,仍然可以接收到來自節點的充電請求,新加入的充電請求節點,很可能會導致當前充電決策序列的改變。

當充電車完成了對某點的充電服務后,會將該點從充電決策序列中刪除,并更新任務剩余時間和當前充電決策序列。令L′表示當前充電決策序列,T′表示當前剩余時間。

充電車在執行任務的過程中接收到來自節點vk的充電請求時,判斷vk能否插入或替換到當前充電決策序列L′中,只需調用一次DCIM過程。DCIM過程具體描述如下:

Procedure.2: DCIM

/*dynamic classification insertion method*/

Input:Urg、Ord、T′、L′、vk

Output:L′

Step1:若vk∈Urg,執行Step2;若vk∈Ord,執行Step9。

Step2:在序列L′中確定連續的兩點vi,vj,使得插入代價(tik+tkj-tij)最小。將vk插入到vi與vj之間,得到任務序列(…,vi,vk,vj,…)。

Step3:判斷序列(…,vi,vk,vj,…)的執行時間是否大于T′。若大于T′,執行Step5;否則執行Step4。

Step4:更新L′=(…,vi,vk,vj,…),令Urg=Urg/vk,退出。

Step5:若L′中只有迫切請求充電的節點,算法退出;否則執行Step6。

Step6:在L′中確定連續的三點vi,vh,vj(其中vh為普通請求充電節點),使得替換代價(tik+tkj-tih-thj)最小。將vh與vk替換,得到序列(…,vi,vk,vj,…)。

Step7:判斷序列(…,vi,vk,vj,…)的執行時間是否大于T′。若大于T′退出,否則執行Step8。

Step8:更新L′=(…,vi,vk,vj,…),Urg=Urg/vk,并將vh加入Ord中,然后退出。

Step9:在序列L′中確定連續的兩點vi,vj,使得插入代價(tik+tkj-tij)最小,將vk插入到vi與vj之間,得到序列(…,vi,vk,vj,…)。

Step10:判斷序列(…,vi,vk,vj,…)的執行時間是否大于T′。若大于T′退出,否則執行Step11。

Step11:更新L′=(…,vi,vk,vj,…),并更新Ord=Ord/vk,退出。

SCIM算法對應的的流程圖如圖5所示。

4.4 主算法及其復雜度分析

在任務執行過程中,充電車總是選取當前充電決策序列L′中的第一個節點作為它的下一個服務節點,而當充電車對現節點充電完成時,會將該節點從L′中刪除。通過調用4.2與4.3中的兩個子過程,RECHA算法的具體描述如下:

Algorithm:RECHA

Input:Urg、Ord、T、vk

Output:charging_tour

Step1:充電車在執行任務前一刻(此時位于服務站中),調用SCIM(Urg,Ord,T)生成初始的充電決策序列L。

圖5 DCIM過程流程圖

Step2:令當前充電決策序列L′=L,剩余時間T′=T,同時充電車從服務站出發執行本輪充電任務。

Step3:充電車執行任務。若充電決策序列L′中已無請求充電節點且剩余時間T′只夠支持充電車返回到服務站,執行Step5。若充電車接收到來自某節點新的充電請求,執行Step4。

Step4:令vk表示該請求充電節點,調用DCIM(Urg,Ord,T′,L′,vk)判斷是否將vk插入或替換到序列L′中,返回Step3。

Step5:將充電車此次任務所經過節點按順序存儲到序列charging_tour中,退出。

=O(m3+n3+l2)

若m,n,l三者之和為N,則RECHA算法時間復雜度上界為O(N3)。

RECHA算法提供的充電車調度策略不僅具有較優的充電服務吞吐量而且具有良好的網絡整體穩定性。在第5節中,本文將RECHA算法與先來先服務算法和NJNP算法的性能進行對比。

5 實驗結果與分析

5.1 實驗環境

本文的實驗模型來自文獻[19]中的實驗模型,可充電無線傳感器網絡的規模為100m×100m的區域內隨機分布100～300個傳感器節點,充電服務站BS位于網絡的中心位置,其坐標為(50,50)。網絡中有一臺移動充電車MC,初始位于服務站BS中,其最大充電服務時間為T,移動速度為1m/s。傳感器的電池容量C=100,充電車對傳感器的充電時間為固定時間10s,傳感器維持工作每秒所需耗費的電量取0.01～0.02間的隨機值,而轉發或發送一條消息需耗費0.02的電量。

傳感器節點的剩余電量低于α·C時會向充電車發送一條充電請求,剩余電量低于α·β·C時會向充電車發送一條迫切的充電請求。實驗中,傳感器之間信息傳送的通信路徑是一棵以服務站BS為根節點的最小生成樹。這里取α=0.044(文獻[19]通過實驗已論證)。實驗的inspection cycle為50000s,本文模擬實驗所評估出的結果均為10次模擬實驗的平均值。

5.2 參數β設定

為了得到合適的參數β值,將β分別取0,0.05,0.10,…,0.90,0.95,最大任務執行時間T取1000s,在節點數為100的網絡中進行10次模擬實驗,不同β值所對應的充電任務錯失率平均值如表1所示。

通過表1中的實驗結果表明,β值取0.35時,可以使得整個監測周期內的充電服務錯失率最小(相比于其它19組數據)。所以在本文的算法性能評估試驗中,將參數β值設定為0.35。

表1 參數β的取值對充電服務錯失率的影響

5.3 算法性能描述

由于監測周期(50000s)較長,所以監測周期內充電車所服務的節點數(所有任務回路的充電服務吞吐量之和)數值較大。為了更直觀表現出RECHA算法性能的優越性,在實驗中用平均充電服務吞吐量來衡量算法的性能。平均充電服務吞吐量(Average Charging Throughput)是指監測周期內所有任務回路充電服務吞吐量的平均值,可由下面的表達式求得:

圖6 RECHA算法與FCFS平均充電服務吞吐量對比

先來先服務算法(First Come First Serve,FCFS)是計算機操作系統中一個經典的任務調度算法,應用在充電車任務調度問題中,其算法基本思想是,充電車總是在充電服務池中選擇一個最早請求服務的節點作為它的下一個充電目標。

如圖6所示,在最大服務時間T為1000s,傳感器節點個數分別為100、150、200、250、300的五種不同規模的可充電傳感器網絡中,RECHA算法所提供的任務調度策略與FCFS算法相比:平均充電服務吞吐量(Average Charging Throughput)分別提高40.75%、68.11%、87.45%、106.92%、129.21%,平均提高86.49%。

如圖7所示,在最大服務時間T為1000s,傳感器節點個數為100、150、200、250、300的五種不同規模的傳感器網絡中,RECHA算法所提供的任務調度策略與NJNP算法相比:平均充電服務吞吐量分別下降9.91%、9.29%、8.86%、8.87%、8.37%,平均下降9.1%;充電丟失率分別提高84%、87.8%、95.4%、104.4%、111.1%,平均提高96.5%。

圖7 T=1000s時RECHA算法與FCFS算法性能對比

圖8 T=2000s時RECHA算法與FCFS算法性能對比

如圖8所示,在最大服務時間為2000s,傳感器節點個數為100、150、200、250、300的五種不同規模的傳感器網絡中,RECHA算法所提供的任務調度策略與NJNP算法相比:平均充電服務吞吐量分別下降8.72%、8.44%、8.82%、8.11%、7.98%,平均下降8.41%;充電丟失率分別提高74.67%、87.53%、93.06%、100.4%、108.93%,平均提高92.91%。

實驗結果[19]表明:RECHA算法與FCFS算法相比,平均狀況下充電服務吞吐量可提高86.49%;RECHA算法與文獻所提出的NJNP充電服務錯失率算法相比,雖然平均狀況下充電服務吞吐量下降8.75%(最多下降9.91%),但是平均狀況下降低了94.7%。

6 結語

本文研究了可充電傳感器網絡中充電車任務調度問題。針對網絡動態請求式的特點,將充電服務池中的節點按請求充電的迫切程度分為兩類并建立了最大充電服務吞吐量問題的數學模型,提出一種基于最臨邊插入策略的近似算法,實驗結果表明,該算法可使監測周期內充電任務調度系統的充電服務錯失率平均降低94.7%,而平均充電服務吞吐量的損失可控制在9.91%以內。

[1] J. Yick, B. Mukherjee, D. Ghosal. Wireless sensor network survey[J]. Computer Networks,2008,52:2292-2330.

[2] Li. X, Mao. Y, Liang. Y. A survey on topology control in wireless sensor networks[C]//ICARCV,2008:251-255.

[3] C. M. Angelopoulos, S. Nikoletseas, T. P. Raptis, et al. Efficient energy management in wireless rechargeable sensor networks[C]//Proc. of MSWim, IEEE,2012:21-25.

[4] G. Sudevalayam, P. Kulkarni. Energy harvesting sensor nodes: survey and implication[J]. IEEE Communications Surveys & Tutorials,2011,13:443-461.

[5] K.-W. Fan, Z. Zheng, P. Sinha. Steady and fair rate allocation for rechargeable sensors in perpetual sensor networks[C]//Proc. of SenSys’08, ACM,2008:239-252.

[6] W. Liang, X. Ren, X. Jia, et al. Monitoring quality maximization through fair rate allocation in harvesting sensor networks[J]. IEEE Transaction on Parallel and Distribution Systems,2013,24(9):1827-1840.

[7] X. Ren, W. Liang. Delay-tolerant data gathering in energy harvesting sensor networks with a mobile sink[C]//Proc. of GLOBECOM, IEEE,2012:93-99.

[8] X. Ren, W. Liang. The use of a mobile sink for quality data collection in energy harvesting sensor networks[C]//IEEE Wireless Communications and Networking Conference,2013:1145-1150.

[9] A. Kurs, A. Karalis, R. Moffatt, et al. Wireless power transfer via strongly coupled magnetic resonances[J]. Science,2007,317:83-86.

[10] H. Dai, Y. Liu, G. Chen, et al. Safe Charging for Wireless Power Transfer[C]//IEEE INFOCOM,2014:1105-1113.

[11] K. S. Rekha, T. H. Sreenivas, Infrastructure establishment for a reconfigurable network in wireless sensor networks[C]//IEEE ICCIC,2015:1-8.

[12] Intel. Wireless resonant energy link (wrel) demo[EB/OL]. http://software.intel.com/en-us/videos/wireless-resonant-energy-link-wrel-demo

[13] M. Zhao, J. Li, Y. Yang. Joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks[C]//IEEE ITC,2011:238-245.

[14] Xie L. G., Shi Y., Hou Y. T. Making sensor networks immortal: An energy-renewal approach with wireless power transfer[J]. IEEE ACM T Network,2012,20:1748-1761.

[15] S. Zhang, J. Wu, S. Lu. Collaborative Mobile Charging[J]. IEEE Transactions on Computers,2015:654-667.

[16] L. Xie, Y. Shi, Y. Hou. A mobile platform for wireless charging and ata collection in sensor networks[J]. IEEE Journal on Selected Areas in Communications,2015:1521-1533.

[17] X. Ren, W. Liang, W. Xu. Maximizing charging throughput in rechargeable sensor networks[C]//Proc of ICCCN,2014:1-8.

[18] C. M. Angelopoulos, S. Nikoletseas, T. P. Raptis. Efficient wireless recharging in sensor Networks[C]//IEEE DCSS,2013:298-300.

[19] L. He, L. Kong, Y. Gu, et al. Evaluating the on-demand mobile charging in wireless sensor networks[J]. IEEE Transaction on Mobile Computer,2015,14(9):1861-1875.

Efficient Scheduling Strategy in Wireless Rechargeable Sensor Networks

QU Lijun1DANG Xin1WU Jigang2

(1. School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300387) (2. School of Computing Science and Technology, Guangdong University of Technology, Guangzhou 510006)

With the development of wireless sensor networks, the limited battery capacity of sensor nodes has become one of energy bottleneck problems that dominates the wide application of wireless sensor networks. In recent years, wireless rechargeable sensor networks have attracted much attention due to their potential in solving the energy bottleneck problem. In this paper, the scheduling strategy of mobile charger in the on-demand mobile charging wireless sensor networks is studied. The proposed strategy can divide the sensor nodes of service pool into two categories. Mobile charger can provide charging service in some priority according to the degree of charging request urgency during the charging tour. Our proposed algorithm can reduce charging missing ratio by 89 percent, and it can keep charging throughput decline rate less than 9.91 percent.

wireless recharging, wireless sensor network, charging scheduling, insertion method

2016年8月11日,

2016年9月27日

國家自然基金(編號:61572144);廣東省科技計劃應用專項基金(編號:2015B010129014)資助。

曲立軍，男，碩士研究生，研究方向：可充電傳感器網絡。黨鑫，男，博士，講師，研究方向：嵌入式系統，高性能體系結構，機器學習。武繼剛，男，教授，博士生導師，研究方向：計算機科學，高性能體系結構。

TP391

10.3969/j.issn.1672-9722.2017.02.022