基于效用最大化的無線可充電傳感器網(wǎng)絡(luò)有向充電調(diào)度方案

王 楊 張 鑫 趙傳信 方 群 艾世成

①(安徽師范大學(xué)計算機(jī)與信息學(xué)院 蕪湖241002)

②(東南大學(xué)計算機(jī)科學(xué)與工程學(xué)院 南京211189)

1 引言

近年來，物聯(lián)網(wǎng)(Internet Of Things,IOT)的發(fā)展如火如荼，作為其核心的無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)已廣泛應(yīng)用于環(huán)境監(jiān)測、目標(biāo)跟蹤、醫(yī)學(xué)和科學(xué)探索等領(lǐng)域[1]。但是傳統(tǒng)的電池供電方式導(dǎo)致了WSNs壽命受限。

為了解決這一問題，研究人員提出了如下3類解決方案。一是設(shè)法提高WSNs的資源利用率，進(jìn)而減少傳感器節(jié)點(diǎn)的能量消耗。例如引入優(yōu)化路由協(xié)議[2]、睡眠調(diào)度機(jī)制[3]、數(shù)據(jù)融合處理[4]、網(wǎng)絡(luò)分簇聚類[5]等策略。這類工作雖能減少網(wǎng)絡(luò)整體能量消耗并延長其壽命，但是難以從根本上解決WSNs的能量受限問題。二是通過能量收集技術(shù)收集傳感器周圍環(huán)境中的能量實(shí)現(xiàn)能量的補(bǔ)給。例如收集太陽能、風(fēng)能和熱能等[6–8]。但是這種方法具有一定的天然不穩(wěn)定性。三是通過磁耦合共振的無線能量傳輸技術(shù)遠(yuǎn)距離對傳感器進(jìn)行無線充電。如Tong等人[9]通過實(shí)驗驗證了無線充電技術(shù)在WSNs中應(yīng)用的可行性。但是在WSNs中如何合理地調(diào)度移動充電器進(jìn)行無線充電成為一個亟待解決的現(xiàn)實(shí)問題。

理論上，無線可充電傳感器網(wǎng)絡(luò)(Wireless Recharging Sensors Networks,WRSNs)可以永久保持工作狀態(tài)。但是，因為充電系統(tǒng)充電能力的局限性，例如：充電器總能量受限[10]，充電周期受限[11]，充電距離的影響[12]等因素，需要結(jié)合具體的充電任務(wù)進(jìn)行調(diào)度規(guī)劃。

根據(jù)充電模型劃分，現(xiàn)有研究成果主要分為一對一[13–15]和一對多兩類充電模型[16–18]。前者往往假設(shè)移動充電器從基站出發(fā)，為沿途的傳感器節(jié)點(diǎn)提供一對一充電服務(wù)，最后返回基站的充電場景。在之前的工作[13]中，本文主要考慮了一對一充電模式下，從移動充電器調(diào)度、傳感器充電時間分配、節(jié)點(diǎn)速率控制協(xié)同優(yōu)化來提高網(wǎng)絡(luò)性能。而Huong等人[14]則以最小化餓死節(jié)點(diǎn)數(shù)量為目標(biāo)，提出了一種基于遺傳算法的充電調(diào)度方案。Zhao等人[15]以充電效率最大化為目標(biāo)，建立了充電調(diào)度和充電時間分配的混合整數(shù)優(yōu)化模型。并設(shè)計了兼顧充電任務(wù)和分配充電時間目標(biāo)優(yōu)化的離線算法。一對一充電方式的缺點(diǎn)主要是充電效率較低，并且在實(shí)施時受限于具體環(huán)境。

為了進(jìn)一步提高移動充電器的充電效率，一對多充電調(diào)度方案應(yīng)運(yùn)而生。Liu等人[16]提出了一種多節(jié)點(diǎn)的時空域局部充電算法(Multi-node Temporal Spatial Partial Charging,MTSPC)。本算法首先構(gòu)建一個盡可能滿足充電請求的充電方案，然后采用生成的充電方案來提高能源使用效率。而Zhang等人[17]提出了一種多節(jié)點(diǎn)可充電算法(Multi-node Rechargeable Algorithm,MRA)。該算法使用移動充電器定期訪問WRSNs中的每個對接站點(diǎn)并對覆蓋范圍內(nèi)的節(jié)點(diǎn)充電。通過減少停靠點(diǎn)的數(shù)量并優(yōu)化移動充電器的行駛路徑，從而提高充電效率。此外呂增威等人[18]則提出了一種基于多目標(biāo)優(yōu)化的WRSNs移動充電和數(shù)據(jù)收集聯(lián)合優(yōu)化方案。上述方案僅僅假設(shè)移動充電器的充電模型為全向覆蓋，并沒有考慮有向天線情形。本文主要在現(xiàn)有研究工作的基礎(chǔ)上提出了一種基于充電效用最大化的有向充電方案。

2 系統(tǒng)模型和問題描述

2.1 網(wǎng)絡(luò)系統(tǒng)模型

2維平面中的無線可充電傳感器網(wǎng)絡(luò)可以表示為G=(V′,E)，其中V′=(V ∪S)。V是平面內(nèi)隨機(jī)分布的傳感器節(jié)點(diǎn)，每個傳感器均配有容量為B的可充電電池，S代表網(wǎng)絡(luò)中的Sink節(jié)點(diǎn)。本文主要考慮通過一個移動有向充電器為WRSNs中傳感器進(jìn)行周期性巡游充電的場景。網(wǎng)絡(luò)中心處放置一個基站v0，為巡游后的移動充電器補(bǔ)充能量以保證在下一個周期T內(nèi)能夠完成充電任務(wù)。網(wǎng)絡(luò)系統(tǒng)模型如圖1。

2.2 充電模型

充電模型中的有向充電器采用一個5元組來描述：C j={(X j,Y j,A,θj,D)|j∈M}。其中Xj,Y j為有向充電器在2維平面中的錨點(diǎn)位置，θj為有向充電器朝向角度，A是有向充電器最大覆蓋角度，D為有向充電器最大充電半徑，M為有向充電器停車錨點(diǎn)集合。同時，采用二進(jìn)制數(shù)Q c j,v i表示網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)vi是否被Cj覆蓋到，如式(1)

其中，θ(C j,v i)為有向充電器與傳感器vi的夾角，

圖1 網(wǎng)絡(luò)系統(tǒng)模型

2.3 問題描述

本文試圖解決的問題是如何通過一個移動的有向充電器為WRSNs中多個傳感器節(jié)點(diǎn)同時充電。移動充電器從基站v0出發(fā)，沿著一條閉環(huán)的巡游路徑行駛，最終回到v0。在巡游過程中可能存在多個停車錨點(diǎn)使移動充電器停止移動，進(jìn)行無線充電。假設(shè)這樣的錨點(diǎn)集合是M，并且據(jù)此規(guī)劃移動充電器的行駛路線。然后根據(jù)每個有向覆蓋集合內(nèi)節(jié)點(diǎn)能量、位置等變量為每個錨點(diǎn)的覆蓋集合分配充電時間τ(t j){j∈M}，目標(biāo)是使移動充電器充電效用最大化。

3 MUC調(diào)度方案

在MUC調(diào)度方案中，充電效用最大化問題被分解為3個階段優(yōu)化：覆蓋集合的提取、覆蓋子集的篩選、充電時間的分配。

圖2 有向充電模型

3.1 覆蓋集合的提取

3.2 覆蓋子集的篩選

圖3 覆蓋集合提取示例圖

為了更直觀看出電池獲能過程，圖4模擬了剩余能量不同的兩個傳感器節(jié)點(diǎn)隨時間充電的獲能情況。

圖4分別為電池容量B=10000J，初始節(jié)點(diǎn)能量E R=0時，即節(jié)點(diǎn)能量從0開始充電的函數(shù)圖像；B=10000J, E R=2000J時，即節(jié)點(diǎn)能量從 2000 J開始充電的函數(shù)圖像。不難發(fā)現(xiàn)在相同充電時間下，剩余能量較少的節(jié)點(diǎn)充電獲能較多。

在覆蓋子集篩選上，將網(wǎng)絡(luò)中充電增益最大的覆蓋集合依次篩選出來直到全覆蓋。式(5)表示單個傳感器在覆蓋范圍內(nèi)的充電增益

圖4 電池充電獲能圖

3.3 充電時間的分配

當(dāng)確定了有向覆蓋子集后，需要采用智能算法確定一條最短巡游路徑。假定移動充電器能量有限，且在固定周期T內(nèi)需要回到基站進(jìn)行能量補(bǔ)給。因此需要對移動充電器的充電時間進(jìn)行合理分配。事實(shí)上，傳感器充電時間分配問題可以通過式(7)描述

4 實(shí)驗及結(jié)果分析

本節(jié)通過實(shí)驗驗證和分析MUC調(diào)度方案的性能。

4.1 參數(shù)設(shè)置

實(shí)驗參數(shù)如表1所示。

4.2 基線算法

(1)本文采用以下兩種不同充電時間優(yōu)化算法用于性能比較：

(a)固定能量充電(Fixed Energy Charging,FEC)算法：將有向覆蓋范圍內(nèi)的所有節(jié)點(diǎn)能量充到某個閾值(60%)，隨后移動充電器巡游至下一錨點(diǎn)充電。

(b)平均能量充電(Average Energy Charging,AEC)算法：在能夠巡游覆蓋所有節(jié)點(diǎn)的前提下，將可用的充電時間平均分配給每個覆蓋集合。

(2)本文采用以下兩種不同覆蓋子集篩選算法用于性能比較：

(a)最多節(jié)點(diǎn)覆蓋(Maximum Node Coverage,MNC)算法：篩選出網(wǎng)絡(luò)中有向覆蓋節(jié)點(diǎn)最多的集合，直到覆蓋到每個節(jié)點(diǎn)。

(b)最大平均增益覆蓋(Maximum Average Gain Coverage,MAGC)算法篩選出網(wǎng)絡(luò)中有向覆蓋平均節(jié)點(diǎn)增益最大的集合，直到覆蓋到每個節(jié)點(diǎn)。

4.3 實(shí)驗結(jié)果及分析

傳感器節(jié)點(diǎn)隨機(jī)分布在150 m×150 m范圍內(nèi)，初始能量隨機(jī)分配在0～B之間。

圖5是在不同節(jié)點(diǎn)規(guī)模下充電算法的充電效用對比圖。MUC算法比AEC算法提高13.7%，比FEC算法提高32.7%。在一定范圍內(nèi)，MUC算法的充電效用隨節(jié)點(diǎn)規(guī)模的增加而提高，這是因為節(jié)點(diǎn)規(guī)模的增加會提高增益覆蓋子集篩選的多樣性。圖6是在不同節(jié)點(diǎn)規(guī)模下充電算法餓死節(jié)點(diǎn)數(shù)對比圖。MUC算法在不同節(jié)點(diǎn)規(guī)模下餓死節(jié)點(diǎn)數(shù)都明顯少于其他兩種算法。

表1 參數(shù)設(shè)置

圖7為參數(shù)p對充電算法的影響。p是與電池充電相關(guān)的參數(shù)。在p較大時電池充電效率較高；較小時充電效率較低。從圖7可以看出，在p變化范圍內(nèi)，MUC算法充電效用優(yōu)于FEC算法和AEC算法。這是因為MUC算法可以將移動充電器可用充電時間合理分配給傳感器節(jié)點(diǎn)。

圖8反映的是不同節(jié)點(diǎn)分布對充電算法的影響。在3種節(jié)點(diǎn)分布中，密集分布的充電效果最優(yōu)。這是因為在密集分布的網(wǎng)絡(luò)中，巡游的移動充電器停車錨點(diǎn)數(shù)較少，移動能耗較低，傳感器可以分配到更多的可用充電能量。

圖5 不同規(guī)模下算法充電效用對比圖

圖6 不同節(jié)點(diǎn)規(guī)模下充電算法餓死節(jié)點(diǎn)數(shù)對比圖

圖7 參數(shù)p 對不同充電算法的影響

圖9為不同覆蓋算法下的覆蓋子集篩選圖。圖9(a)MNC算法試圖尋找網(wǎng)絡(luò)中覆蓋節(jié)點(diǎn)最多的覆蓋集合，并依次將集合加入覆蓋子集中，直到覆蓋所有節(jié)點(diǎn)。因此該算法的停車錨點(diǎn)數(shù)最少，路徑能量消耗最低；圖9(b)MUC算法試圖尋找網(wǎng)絡(luò)中覆蓋節(jié)點(diǎn)充電增益最大的覆蓋集合，直到覆蓋所有的節(jié)點(diǎn)。與MNC算法相比，停車錨點(diǎn)數(shù)目和移動充電器路徑能量消耗均增加，但是該算法可以更加合理地分配移動充電器的能量；圖9(c)MAGC算法試圖尋找網(wǎng)絡(luò)中覆蓋集合內(nèi)平均節(jié)點(diǎn)增益最大的覆蓋集合。該算法在尋找覆蓋集合上趨向于單個節(jié)點(diǎn)或幾個節(jié)點(diǎn)充電以保證其覆蓋集合內(nèi)平均節(jié)點(diǎn)增益最大。

圖8 不同節(jié)點(diǎn)分布對充電算法的影響

圖10為不同節(jié)點(diǎn)分布下覆蓋子集篩選圖。50個傳感器節(jié)點(diǎn)分別采用圖10(a)隨機(jī)分布、圖10(b)均勻分布、圖10(c)密集分布進(jìn)行MUC覆蓋子集篩選。圖10表明，隨機(jī)與均勻分布不僅導(dǎo)致移動充電器移動軌跡較長且停車錨點(diǎn)數(shù)較多：分別為14個和19個。而密集分布方式下，不僅移動軌跡較短，而且停車錨點(diǎn)數(shù)較少：為11個，同時移動路徑的能耗也較低。

圖11為不同節(jié)點(diǎn)規(guī)模下子集篩選算法充電效用對比圖。MUC算法相比于MAGC算法提高了35.9%；相比于MNC算法在50節(jié)點(diǎn)，80節(jié)點(diǎn)時充電效用略低。這是由于在移動充電器行駛與充電過程中，根據(jù)真實(shí)采樣比例單位時間內(nèi)行駛能量消耗遠(yuǎn)大于單位時間內(nèi)充電能量消耗。同時MNC算法的停車錨點(diǎn)數(shù)也少于其他兩種算法的。如圖9所示，MUC算法是24個停車錨點(diǎn)，MNC算法是22個停車錨點(diǎn)，而MAGC算法是85個停車錨點(diǎn)。所以在網(wǎng)絡(luò)規(guī)模較小時MNC充電效用最高。當(dāng)節(jié)點(diǎn)規(guī)模達(dá)到110,140,170時，本文MUC算法充電效用也高于MNC。這是因為網(wǎng)絡(luò)中覆蓋子集的多樣性使移動充電器的充電能量最大化，而彌補(bǔ)路徑能量消耗較大的不足，MUC算法平均充電效用比MNC算法提高4.4%。

圖12是3種算法下網(wǎng)絡(luò)餓死節(jié)點(diǎn)數(shù)的對比情況。圖12表明，相比于其他兩種算法，MUC覆蓋算法餓死節(jié)點(diǎn)數(shù)明顯較少。

圖9 不同覆蓋算法下覆蓋子集篩選圖

圖10 不同節(jié)點(diǎn)分布下覆蓋子集篩選圖

圖11 不同節(jié)點(diǎn)規(guī)模下子集篩選算法充電效用對比圖

圖12 不同節(jié)點(diǎn)規(guī)模下子集篩選算法餓死節(jié)點(diǎn)數(shù)對比圖

5 結(jié)束語

本文提出了一種基于充電效用最大化的無線可充電傳感網(wǎng)絡(luò)有向充電調(diào)度方案。該方案首先根據(jù)網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)能量和位置信息進(jìn)行有向覆蓋子集篩選，然后將覆蓋區(qū)域的傳感器作為整體，優(yōu)化其分配的充電時間以使充電效用最大化。本文算法主要適用于中小規(guī)模無線可充電傳感網(wǎng)絡(luò)。

在大規(guī)模無線可充電傳感網(wǎng)絡(luò)中，由于存在多節(jié)點(diǎn)同時發(fā)出能量請求的情形，此時單移動充電器的部署模式難以滿足現(xiàn)實(shí)需求。未來的工作中，將考慮大規(guī)模無線可充電傳感器網(wǎng)絡(luò)中多充電小車的有向充電調(diào)度問題。