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

曲立軍 黨 鑫 武繼剛

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

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

曲立軍1黨 鑫1武繼剛2

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

近年來,無線傳感器網(wǎng)絡(luò)在監(jiān)控、檢測等領(lǐng)域扮演著越來越重要的角色。然而,隨著無線傳感器網(wǎng)絡(luò)規(guī)模的不斷擴大,傳感器節(jié)點的電池容量成為制約其生命周期的主要瓶頸。為了解決這種能源瓶頸問題,無線可充電傳感器網(wǎng)絡(luò)引起了學(xué)者們的廣泛關(guān)注。論文研究了動態(tài)請求(On-Demand)的可充電傳感器網(wǎng)絡(luò)中的充電車任務(wù)調(diào)度策略。該策略將充電服務(wù)池中的節(jié)點分為兩類,充電車在任務(wù)執(zhí)行過程中,可以按照傳感器節(jié)點充電請求的迫切程度以相應(yīng)的優(yōu)先級向其提供充電服務(wù)。論文提出的算法用來解決充電車任務(wù)調(diào)度的問題,該算法可使任務(wù)調(diào)度系統(tǒng)的充電服務(wù)錯失率(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é)點是由電池供電的,電池容量決定傳感器節(jié)點的可工作時長,所以電池容量成為制約整個傳統(tǒng)傳感器網(wǎng)絡(luò)生命周期大小的主要因素之一[3]。為了延長傳統(tǒng)傳感器網(wǎng)絡(luò)的生命周期,在過去幾十年里很多的節(jié)能措施被提出,以減少傳感器節(jié)點的能源消耗或者平衡傳感器節(jié)點之間通信的能源消耗[4]。然而,這并沒有從根本上解決傳感器網(wǎng)絡(luò)的能源瓶頸問題。

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

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

文獻(xiàn)[12]已證明利用無線電力傳輸技術(shù),在2～3英尺距離內(nèi)對功率為60瓦設(shè)備的電力傳輸效率可以提高75%。因此,無線充電技術(shù)已成為解決無線傳感器網(wǎng)絡(luò)能源瓶頸問題的一個有效的措施。文獻(xiàn)[13]分析并解決了可充電傳感器網(wǎng)絡(luò)中的移動充電車數(shù)據(jù)收集與充電路徑問題。文獻(xiàn)[14]通過利用經(jīng)典的TSP算法找到傳感器網(wǎng)絡(luò)中的一條最短哈密頓回路,讓充電車周期性地遍歷這條回路上的傳感器節(jié)點。文獻(xiàn)[15]研究了通過多個移動充電車為傳感器網(wǎng)絡(luò)提供高效的充電服務(wù),為可充電無線傳感器網(wǎng)絡(luò)提出了一種新穎的充電模式,即協(xié)同移動充電模式。文獻(xiàn)[16]研究了移動數(shù)據(jù)收集車問題,在能夠保證傳感器持續(xù)工作的條件下,充電車還可以進行數(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ò)中,充電車本身可以獨立接收來自傳感器節(jié)點的充電請求,并獨立完成充電調(diào)度。

本文研究的是動態(tài)請求的無線可充電傳感器網(wǎng)絡(luò),主要貢獻(xiàn)如下: 1) 針對動態(tài)請求的傳感器網(wǎng)絡(luò),建立了最大化充電服務(wù)吞吐量問題的數(shù)學(xué)模型,并將充電服務(wù)池中的節(jié)點按請求充電的迫切程度分為兩類,以便充電車能夠按照傳感器節(jié)點充電請求的迫切程度以相應(yīng)的優(yōu)先級向其提供充電服務(wù)。 2) 提出了基于最臨邊插入策略的充電車任務(wù)調(diào)度近似算法,利用該近似算法可以得到控制充電車任務(wù)調(diào)度的任務(wù)序列。算法將所有屬于高迫切程度類別的節(jié)點優(yōu)先插入到任務(wù)序列中,然后再將屬于低迫切程度類別的節(jié)點盡量插入到任務(wù)序列中。 3) 實驗結(jié)果表明,與文獻(xiàn)[19]提出算法相比,本文所提出的算法及調(diào)度策略,可使監(jiān)測周期內(nèi)充電任務(wù)調(diào)度系統(tǒng)的充電服務(wù)錯失率(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é)點集合,網(wǎng)絡(luò)節(jié)點數(shù)為N。BS表示網(wǎng)絡(luò)中的充電服務(wù)站(基站),它負(fù)責(zé)分析和匯總傳感器節(jié)點的監(jiān)測數(shù)據(jù)。MC表示一輛裝有無線充電裝置的充電車,初始狀態(tài)下,MC位于服務(wù)站BS中,當(dāng)網(wǎng)絡(luò)中的部分傳感器因電池電量過低而需要充電時,充電車MC會從服務(wù)站BS出發(fā)向需要充電的節(jié)點提供充電服務(wù),最后再返回服務(wù)站BS。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Urg∩Ord=?

Urg∪Ord=Sv

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

令充電服務(wù)池Sv={v1,v2,…,vn},請求充電的節(jié)點數(shù)目為n。令v0表示充電服務(wù)站BS,充電車對每個節(jié)點的充電時間固定為常數(shù)C,充電車從節(jié)點vi移動到vj所需花費時間為tij。由于回路中的節(jié)點數(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é)點提供至多一次充電服務(wù),并保證任務(wù)路徑的連通性,有如下約束條件:

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

(3)

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

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

(4)

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

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

(5)

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

4 算法思想及步驟

4.1 算法思想

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

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

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

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

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

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

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

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

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

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

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

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

4.2 SCIM過程

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

Procedure.1: SCIM

/*static classification insertion method*/

Input:Urg、Ord、T

Output:L

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

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

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

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

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

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

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

Step8:判斷序列(…,vi,vk,vj,…)的執(zhí)行時間是否大于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é)點的充電請求,新加入的充電請求節(jié)點,很可能會導(dǎo)致當(dāng)前充電決策序列的改變。

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

充電車在執(zhí)行任務(wù)的過程中接收到來自節(jié)點vk的充電請求時,判斷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ù)的兩點vi,vj,使得插入代價(tik+tkj-tij)最小。將vk插入到vi與vj之間,得到任務(wù)序列(…,vi,vk,vj,…)。

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

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

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

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

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

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

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

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

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

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

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

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

Algorithm:RECHA

Input:Urg、Ord、T、vk

Output:charging_tour

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

圖5 DCIM過程流程圖

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

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

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

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

=O(m3+n3+l2)

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

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

5 實驗結(jié)果與分析

5.1 實驗環(huán)境

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

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

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

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

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

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

5.3 算法性能描述

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

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

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

如圖6所示,在最大服務(wù)時間T為1000s,傳感器節(jié)點個數(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ù)時間T為1000s,傳感器節(jié)點個數(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時RECHA算法與FCFS算法性能對比

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

如圖8所示,在最大服務(wù)時間為2000s,傳感器節(jié)點個數(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%。

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

6 結(jié)語

本文研究了可充電傳感器網(wǎng)絡(luò)中充電車任務(wù)調(diào)度問題。針對網(wǎng)絡(luò)動態(tài)請求式的特點,將充電服務(wù)池中的節(jié)點按請求充電的迫切程度分為兩類并建立了最大充電服務(wù)吞吐量問題的數(shù)學(xué)模型,提出一種基于最臨邊插入策略的近似算法,實驗結(jié)果表明,該算法可使監(jiān)測周期內(nèi)充電任務(wù)調(diào)度系統(tǒng)的充電服務(wù)錯失率平均降低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);廣東省科技計劃應(yīng)用專項基金(編號:2015B010129014)資助。

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

TP391

10.3969/j.issn.1672-9722.2017.02.022