曲立軍 黨 鑫 武繼剛

(1.天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院 天津 300387)(2.廣東工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 廣州 510006)

無線傳感器網(wǎng)絡(luò)中的充電調(diào)度算法

曲立軍1黨 鑫1武繼剛2

(1.天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院 天津 300387)(2.廣東工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 廣州 510006)

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

無線充電; 無線傳感器網(wǎng)絡(luò); 充電調(diào)度; 插入法

Class Number TP391

1 引言

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

為了解決傳感器網(wǎng)絡(luò)的能源瓶頸問題,研究人員利用可再生能源為傳感器節(jié)點(diǎn)提供能源供應(yīng),例如風(fēng)能、太陽能等[5～8]。但是,由于自然環(huán)境變化的不確定性,可再生能源的收集率不穩(wěn)定且很難預(yù)測,從而無法為整個(gè)傳感器網(wǎng)絡(luò)保證持續(xù)不斷且穩(wěn)定的能源供應(yīng)。

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

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

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

2 基本概念與問題描述

2.1 無線可充電傳感器網(wǎng)絡(luò)模型

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

圖1 無線可充電傳感器網(wǎng)絡(luò)

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

充電車是一種依靠能源提供能量支持的移動充電服務(wù)設(shè)備,在每次充電任務(wù)調(diào)度過程中,它都會從服務(wù)站BS出發(fā),向充電服務(wù)池中的節(jié)點(diǎn)提供充電服務(wù),最后返回服務(wù)站BS。由于它移動和所提供的充電服務(wù)都需要消耗自身的能量,所以規(guī)定,充電車必須在固定時(shí)間T之內(nèi)返回服務(wù)站BS,即充電車的最大充電服務(wù)時(shí)間為T。

本文研究的是動態(tài)請求的可充電傳感器網(wǎng)絡(luò),充電車在任務(wù)執(zhí)行過程中仍然可以接收來自節(jié)點(diǎn)的充電請求,并將新的請求節(jié)點(diǎn)加入到服務(wù)池中。而新加入的請求充電節(jié)點(diǎn),可能會改變充電車當(dāng)前的充電任務(wù)調(diào)度策略。

圖2 充電服務(wù)吞吐量求解示例

2.2 充電服務(wù)吞吐量

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

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

在動態(tài)請求的傳感器網(wǎng)絡(luò)中,傳感器節(jié)點(diǎn)會在電量過低時(shí)發(fā)出充電請求。由于網(wǎng)絡(luò)規(guī)模的龐大和傳感器耗電率的不穩(wěn)定性,一般的調(diào)度策略無法保證對每一個(gè)發(fā)送充電請求的節(jié)點(diǎn)都能提供及時(shí)的充電服務(wù)。所以部分傳感器會因未及時(shí)向其提供充電服務(wù)而暫時(shí)停止工作,這影響了傳感器網(wǎng)絡(luò)工作的整體穩(wěn)定性。

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

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

因此,本文研究充電車任務(wù)調(diào)度策略的目標(biāo)可概括為,在盡可能保證網(wǎng)絡(luò)整體穩(wěn)定性(低充電服務(wù)錯(cuò)失率)的基礎(chǔ)上,在最大服務(wù)時(shí)間內(nèi)找到一條最佳的任務(wù)路徑,使得充電車達(dá)到最大的充電服務(wù)吞吐量。而文獻(xiàn)[17,19]所研究的充電車任務(wù)調(diào)度策略并沒有考慮充電服務(wù)錯(cuò)失率對網(wǎng)絡(luò)整體穩(wěn)定性的影響。最大化充電服務(wù)吞吐量問題的求解數(shù)學(xué)模型參見第3節(jié)。

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

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

Urg∩Ord=?

Urg∪Ord=Sv

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

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

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

(1)

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

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

(2)

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

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

(3)

為了確保充電車必須優(yōu)先考慮對發(fā)出迫切請求充電的節(jié)點(diǎn)提供充電服務(wù),有如下約束條件:

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

(4)

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

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

(5)

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

4 算法思想及步驟

4.1 算法思想

最鄰邊插入法(Nearest Insertion Method,NIM)是解決TSP問題的一個(gè)經(jīng)典啟發(fā)式算法,其算法的基本思想是通過選取插入代價(jià)最小的節(jié)點(diǎn),構(gòu)造一個(gè)頂點(diǎn)數(shù)依次遞增的序列圈,最后得到一個(gè)哈密頓回路即為TSP問題的近似解。

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

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

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

RECHA算法由兩個(gè)子過程構(gòu)成,第一個(gè)子過程名為SCIM,該過程用來得到充電車的初始任務(wù)序列,第二個(gè)子過程名為DCIM,該過程用來得到充電車動態(tài)任務(wù)序列。SCIM與DCIM過程具體描述詳見4.2及4.3節(jié)。RECHA算法具體描述及其時(shí)間復(fù)雜度分析詳見4.4節(jié)。

在本文提出的RECHA算法所提供的調(diào)度策略中,充電車一直存儲著一個(gè)有序序列,該序列被稱為充電決策序列。充電車總是按照充電決策序列提供的充電順序向序列中的節(jié)點(diǎn)提供充電服務(wù),該序列是動態(tài)變化的,且滿足以下兩點(diǎn)規(guī)律:

1) 充電車總是將迫切請求節(jié)點(diǎn)優(yōu)先插入到充電決策序列中。

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

本文提出的算法遵循如下三點(diǎn)合理且現(xiàn)實(shí)可行的基本假設(shè):

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

2) 充電車執(zhí)行完一趟任務(wù)返回服務(wù)站BS后,執(zhí)行下一趟充電任務(wù)所需的準(zhǔn)備時(shí)間可忽略不計(jì)。

3) 節(jié)點(diǎn)電量過低時(shí),會向服務(wù)站發(fā)送充電請求,當(dāng)服務(wù)站接收到來自節(jié)點(diǎn)的充電請求時(shí),會將該條充電請求轉(zhuǎn)發(fā)給充電車,此請求過程可視為節(jié)點(diǎn)直接向充電車發(fā)送充電請求。

4.2 SCIM過程

當(dāng)充電車準(zhǔn)備從服務(wù)站出發(fā)執(zhí)行充電任務(wù)前一刻,SCIM過程用來生成一個(gè)初始的充電決策序列L,SCIM過程具體描述如下:

Procedure.1: SCIM

/*static classification insertion method*/

Input:Urg、Ord、T

Output:L

Step1:在Urg中選取距離v0時(shí)間代價(jià)最小的節(jié)點(diǎn)vi,將vi從Urg中刪除(若Urg為空,從Ord中選取),構(gòu)建序列L=(v0,vi,v0)。

Step2:若Urg為空,執(zhí)行Step6,否則執(zhí)行Step3。

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

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

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

Step6:若Ord為空退出;否則執(zhí)行Step7。

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

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

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

SCIM算法對應(yīng)的流程圖如圖4所示。

圖4 SCIM過程流程圖

4.3 DCIM過程

本文研究的是動態(tài)請求的無線傳感器網(wǎng)絡(luò),在充電車任務(wù)執(zhí)行過程中,仍然可以接收到來自節(jié)點(diǎn)的充電請求,新加入的充電請求節(jié)點(diǎn),很可能會導(dǎo)致當(dāng)前充電決策序列的改變。

當(dāng)充電車完成了對某點(diǎn)的充電服務(wù)后,會將該點(diǎn)從充電決策序列中刪除,并更新任務(wù)剩余時(shí)間和當(dāng)前充電決策序列。令L′表示當(dāng)前充電決策序列,T′表示當(dāng)前剩余時(shí)間。

充電車在執(zhí)行任務(wù)的過程中接收到來自節(jié)點(diǎn)vk的充電請求時(shí),判斷vk能否插入或替換到當(dāng)前充電決策序列L′中,只需調(diào)用一次DCIM過程。DCIM過程具體描述如下:

Procedure.2: DCIM

/*dynamic classification insertion method*/

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

Output:L′

Step1:若vk∈Urg,執(zhí)行Step2;若vk∈Ord,執(zhí)行Step9。

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

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

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

Step5:若L′中只有迫切請求充電的節(jié)點(diǎn),算法退出;否則執(zhí)行Step6。

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

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

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

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

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

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

SCIM算法對應(yīng)的的流程圖如圖5所示。

4.4 主算法及其復(fù)雜度分析

在任務(wù)執(zhí)行過程中,充電車總是選取當(dāng)前充電決策序列L′中的第一個(gè)節(jié)點(diǎn)作為它的下一個(gè)服務(wù)節(jié)點(diǎn),而當(dāng)充電車對現(xiàn)節(jié)點(diǎn)充電完成時(shí),會將該節(jié)點(diǎn)從L′中刪除。通過調(diào)用4.2與4.3中的兩個(gè)子過程,RECHA算法的具體描述如下:

Algorithm:RECHA

Input:Urg、Ord、T、vk

Output:charging_tour

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

圖5 DCIM過程流程圖

Step2:令當(dāng)前充電決策序列L′=L,剩余時(shí)間T′=T,同時(shí)充電車從服務(wù)站出發(fā)執(zhí)行本輪充電任務(wù)。

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

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

Step5:將充電車此次任務(wù)所經(jīng)過節(jié)點(diǎn)按順序存儲到序列charging_tour中,退出。

=O(m3+n3+l2)

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

RECHA算法提供的充電車調(diào)度策略不僅具有較優(yōu)的充電服務(wù)吞吐量而且具有良好的網(wǎng)絡(luò)整體穩(wěn)定性。在第5節(jié)中,本文將RECHA算法與先來先服務(wù)算法和NJNP算法的性能進(jìn)行對比。

5 實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)環(huán)境

本文的實(shí)驗(yàn)?zāi)Ｐ蛠碜晕墨I(xiàn)[19]中的實(shí)驗(yàn)?zāi)Ｐ?可充電無線傳感器網(wǎng)絡(luò)的規(guī)模為100m×100m的區(qū)域內(nèi)隨機(jī)分布100～300個(gè)傳感器節(jié)點(diǎn),充電服務(wù)站BS位于網(wǎng)絡(luò)的中心位置,其坐標(biāo)為(50,50)。網(wǎng)絡(luò)中有一臺移動充電車MC,初始位于服務(wù)站BS中,其最大充電服務(wù)時(shí)間為T,移動速度為1m/s。傳感器的電池容量C=100,充電車對傳感器的充電時(shí)間為固定時(shí)間10s,傳感器維持工作每秒所需耗費(fèi)的電量取0.01～0.02間的隨機(jī)值,而轉(zhuǎn)發(fā)或發(fā)送一條消息需耗費(fèi)0.02的電量。

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

5.2 參數(shù)β設(shè)定

為了得到合適的參數(shù)β值,將β分別取0,0.05,0.10,…,0.90,0.95,最大任務(wù)執(zhí)行時(shí)間T取1000s,在節(jié)點(diǎn)數(shù)為100的網(wǎng)絡(luò)中進(jìn)行10次模擬實(shí)驗(yàn),不同β值所對應(yīng)的充電任務(wù)錯(cuò)失率平均值如表1所示。

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

表1 參數(shù)β的取值對充電服務(wù)錯(cuò)失率的影響

5.3 算法性能描述

由于監(jiān)測周期(50000s)較長,所以監(jiān)測周期內(nèi)充電車所服務(wù)的節(jié)點(diǎn)數(shù)(所有任務(wù)回路的充電服務(wù)吞吐量之和)數(shù)值較大。為了更直觀表現(xiàn)出RECHA算法性能的優(yōu)越性,在實(shí)驗(yàn)中用平均充電服務(wù)吞吐量來衡量算法的性能。平均充電服務(wù)吞吐量(Average Charging Throughput)是指監(jiān)測周期內(nèi)所有任務(wù)回路充電服務(wù)吞吐量的平均值,可由下面的表達(dá)式求得:

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

先來先服務(wù)算法(First Come First Serve,FCFS)是計(jì)算機(jī)操作系統(tǒng)中一個(gè)經(jīng)典的任務(wù)調(diào)度算法,應(yīng)用在充電車任務(wù)調(diào)度問題中,其算法基本思想是,充電車總是在充電服務(wù)池中選擇一個(gè)最早請求服務(wù)的節(jié)點(diǎn)作為它的下一個(gè)充電目標(biāo)。

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

如圖7所示,在最大服務(wù)時(shí)間T為1000s,傳感器節(jié)點(diǎn)個(gè)數(shù)為100、150、200、250、300的五種不同規(guī)模的傳感器網(wǎng)絡(luò)中,RECHA算法所提供的任務(wù)調(diào)度策略與NJNP算法相比:平均充電服務(wù)吞吐量分別下降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時(shí)RECHA算法與FCFS算法性能對比

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

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

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

6 結(jié)語

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

[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);廣東省科技計(jì)劃應(yīng)用專項(xiàng)基金(編號:2015B010129014)資助。

曲立軍，男，碩士研究生，研究方向：可充電傳感器網(wǎng)絡(luò)。黨鑫，男，博士，講師，研究方向：嵌入式系統(tǒng)，高性能體系結(jié)構(gòu)，機(jī)器學(xué)習(xí)。武繼剛，男，教授，博士生導(dǎo)師，研究方向：計(jì)算機(jī)科學(xué)，高性能體系結(jié)構(gòu)。

TP391

10.3969/j.issn.1672-9722.2017.02.022