基于充電車能量利用率的充電優(yōu)化策略

祝鐿雯,程宗毛

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

0 引 言

無(wú)線可充電傳感器網(wǎng)絡(luò)(Wireless Rechargeable Sensor Networks，WRSNs)中的充電問(wèn)題是一個(gè)熱門研究問(wèn)題，即無(wú)線充電車(Wireless Chargeable Vehicle，WCV)如何為節(jié)點(diǎn)供電[1]。前期的充電方案大多數(shù)將充電問(wèn)題轉(zhuǎn)化成旅行商問(wèn)題，利用哈密頓回路的解來(lái)規(guī)劃充電路徑。文獻(xiàn)[2-3]分別采用點(diǎn)對(duì)點(diǎn)的充電模型和點(diǎn)對(duì)多的充電模型，利用哈密頓回路的解來(lái)規(guī)劃充電路徑，確保傳感器網(wǎng)絡(luò)持續(xù)運(yùn)行。保證了WCV行駛距離最短，但忽略了節(jié)點(diǎn)充電的緊急性。文獻(xiàn)[4]提出一種新的充電規(guī)則，即WCV每次選擇離它最近的節(jié)點(diǎn)充電，這種反復(fù)移動(dòng)增加了移動(dòng)距離，不僅浪費(fèi)能量，而且忽略了節(jié)點(diǎn)充電的緊急性。文獻(xiàn)[5]先通過(guò)哈密頓回路的解來(lái)制定主節(jié)點(diǎn)的充電路徑，再在主節(jié)點(diǎn)周圍選擇可行的路過(guò)節(jié)點(diǎn)，將其插入到充電路徑中。這種機(jī)制只在選取路過(guò)節(jié)點(diǎn)時(shí)考慮節(jié)點(diǎn)充電的緊急性，在主節(jié)點(diǎn)選取時(shí)仍忽略了節(jié)點(diǎn)充電的緊急性，造成急需充電節(jié)點(diǎn)的死亡。文獻(xiàn)[6]將傳感器節(jié)點(diǎn)的緊急優(yōu)先級(jí)和距離優(yōu)先級(jí)合并為混合優(yōu)先級(jí)，根據(jù)混合優(yōu)先級(jí)生成最小生成樹，使用最少數(shù)量的WCV維持傳感器網(wǎng)絡(luò)運(yùn)行，但是，基于最小生成樹方法只能保證根節(jié)點(diǎn)到其他節(jié)點(diǎn)的路徑是最短的，不能保證其他節(jié)點(diǎn)之間的路徑最短，從而導(dǎo)致WCV在路上消耗更多的能量。受上述方法的啟發(fā)，本文針對(duì)大規(guī)模WRSNs按需充電體系，研究多無(wú)線充電車充電調(diào)度優(yōu)化問(wèn)題。在已知充電節(jié)點(diǎn)數(shù)和節(jié)點(diǎn)剩余電量的前提下，提出一種無(wú)線充電車能量利用率最大化的綜合權(quán)重調(diào)度算法，進(jìn)而得到最小化網(wǎng)絡(luò)死亡節(jié)點(diǎn)數(shù)的充電優(yōu)化方案。

1 網(wǎng)絡(luò)模型

在一個(gè)矩形區(qū)域內(nèi)，基站位于幾何區(qū)域中心，傳感器節(jié)點(diǎn)隨機(jī)部署在矩形區(qū)域內(nèi)，節(jié)點(diǎn)固定不動(dòng)。WCV配有GPS定位系統(tǒng)，基站負(fù)責(zé)收集傳感器和WCV的相關(guān)數(shù)據(jù)，管理傳感器網(wǎng)絡(luò)，規(guī)劃充電路徑和調(diào)度WCV。當(dāng)傳感器節(jié)點(diǎn)剩余能量低至閾值時(shí)，傳感器節(jié)點(diǎn)從有電節(jié)點(diǎn)變成充電節(jié)點(diǎn)，向基站發(fā)送充電請(qǐng)求，基站通過(guò)傳感器節(jié)點(diǎn)的剩余能量和地理位置規(guī)劃充電策略，派出WCV進(jìn)行充電。為了把充電策略的重點(diǎn)放在充電調(diào)度和方案整體性能上，本文算法簡(jiǎn)化了充電模型，假設(shè)傳感器在合理時(shí)間內(nèi)將充電請(qǐng)求發(fā)送給基站，其中的短暫延遲不影響方案的整體性能。

在WRSNs中，基站表示為N0，充電節(jié)點(diǎn)表示為Ni(i=1,2,…,n)，節(jié)點(diǎn)Ni到節(jié)點(diǎn)Nj之間的距離為di,j，當(dāng)i=0時(shí)，d0,j表示基站到充電節(jié)點(diǎn)Nj的距離。WRSNs中的充電問(wèn)題主要有2個(gè)基本約束。

(1)節(jié)點(diǎn)的能量約束：節(jié)點(diǎn)的剩余電量在WCV到達(dá)之前大于0，否則節(jié)點(diǎn)死亡。

通過(guò)迭代法計(jì)算出WCV的到達(dá)時(shí)間ti和逗留時(shí)間τi分別為

(1)

(2)

式中，v表示W(wǎng)CV的行駛速度，Ec表示節(jié)點(diǎn)的總?cè)萘?，Ei表示節(jié)點(diǎn)Ni的剩余電量，qc表示W(wǎng)CV為節(jié)點(diǎn)充電的速率。

節(jié)點(diǎn)的能量約束表示為：

Ei-piti>0,i=1,2,…,n

(3)

式中，pi表示節(jié)點(diǎn)Ni的消耗速率。

(2)WCV的能量約束：WCV完成一輪充電任務(wù)后要有足夠的電量回到基站。

(4)

本文設(shè)計(jì)充電方案的目標(biāo)是最小化網(wǎng)絡(luò)節(jié)點(diǎn)死亡數(shù)，最大化WCV能量利用率。本文通過(guò)節(jié)點(diǎn)的死亡數(shù)Ndead和WCV的充電量Ea來(lái)衡量充電策略的性能。Ndead表示W(wǎng)CV到達(dá)充電節(jié)點(diǎn)時(shí)電量為0節(jié)點(diǎn)的數(shù)目，Ea表示W(wǎng)CV為所有充電節(jié)點(diǎn)充電的總電量。

(5)

(6)

式中，I(Ei-piti=0)表示示性函數(shù)，優(yōu)化目標(biāo)為minNdead，maxEa。

2 模型求解

在按需充電網(wǎng)絡(luò)模型下，解決問(wèn)題的關(guān)鍵是WCV的充電順序。因此，本文提出一種無(wú)線充電車能量利用率最大化的綜合權(quán)重調(diào)度算法，即用綜合權(quán)重調(diào)度算法(Comprehensive Weight Scheduling Algorithm，CWSA)來(lái)提高網(wǎng)絡(luò)的生存率。首先，利用節(jié)點(diǎn)的綜合權(quán)重規(guī)劃WCV充電主路徑；然后，在WCV充電時(shí)，順帶為主路徑周圍充電節(jié)點(diǎn)充電。

2.1 主路徑規(guī)劃

在大規(guī)模的WRSNs中，有M輛WCV為充電節(jié)點(diǎn)進(jìn)行充電。首先根據(jù)充電節(jié)點(diǎn)的坐標(biāo)位置，利用K均值聚類算法將網(wǎng)絡(luò)中的充電節(jié)點(diǎn)聚成M類，每輛WCV為一個(gè)類內(nèi)的節(jié)點(diǎn)進(jìn)行充電。在每一類內(nèi)，基站通過(guò)節(jié)點(diǎn)的綜合權(quán)值規(guī)劃WCV的充電路徑。

綜合權(quán)重主要包括距離權(quán)重、急迫性權(quán)重以及節(jié)點(diǎn)度數(shù)權(quán)重。

(7)

式中，系數(shù)λ1，λ2，λ3表示距離權(quán)重、急迫性權(quán)重以及節(jié)點(diǎn)度數(shù)權(quán)重的重要程度，系數(shù)和為1，根據(jù)實(shí)際需求選擇系數(shù)大小。

定義1(距離權(quán)重)：Pi(d)表示傳感器節(jié)點(diǎn)Ni的距離權(quán)重，距離越遠(yuǎn)權(quán)重越小，由節(jié)點(diǎn)Ni到節(jié)點(diǎn)Nj的距離表示，即Pi(d)=-dij。

對(duì)于節(jié)點(diǎn)度數(shù)的計(jì)算，需確定距離閾值Di，本文Di選取是Ni周圍充電節(jié)點(diǎn)與Ni距離的1/4中位數(shù)。節(jié)點(diǎn)度數(shù)保證了WCV盡可能多地將電量利用在節(jié)點(diǎn)充電上，減少了行駛電量的消耗。

通過(guò)式(7)計(jì)算得出所有充電節(jié)點(diǎn)的綜合權(quán)值，在每一類內(nèi)，將所有充電節(jié)點(diǎn)按權(quán)重由大到小排序，WCV按排序進(jìn)行節(jié)點(diǎn)充電，當(dāng)WCV的剩余電量不能維持WCV回到基站充電時(shí)停止充電并返回。每輛WCV按綜合權(quán)重排序?qū)Τ潆姽?jié)點(diǎn)充電的順序即為每輛WCV的充電主路徑。

2.2 選擇插入節(jié)點(diǎn)

在充電主路徑確定之后，進(jìn)行插入節(jié)點(diǎn)的選取。插入節(jié)點(diǎn)的選擇規(guī)則主要是如何選擇出可行的插入節(jié)點(diǎn)，本文采用“繪制輔助圓”的方法[5]，以主路徑上2個(gè)節(jié)點(diǎn)之間的距離為直徑繪制圓，將圓內(nèi)的節(jié)點(diǎn)選取為可行插入節(jié)點(diǎn)。

假設(shè)主路徑中插入一個(gè)節(jié)點(diǎn)Ninsert，則WCV行駛距離將增加：

Δdinsert=di,insert+dinsert,i+1-di,i+1

(8)

WCV消耗電量將增加：

ΔEinsert=qmΔdinsert+qcτinsert

(9)

當(dāng)節(jié)點(diǎn)Ninsert滿足主路徑節(jié)點(diǎn)不死亡，也不會(huì)導(dǎo)致WCV電量的耗盡以及Ninsert在WCV來(lái)到之前不死亡時(shí)，Ninsert就是插入節(jié)點(diǎn)。即：

為簡(jiǎn)化計(jì)算，每個(gè)圓內(nèi)只選擇一個(gè)插入節(jié)點(diǎn)。當(dāng)圓內(nèi)有多個(gè)節(jié)點(diǎn)符合要求時(shí)，通過(guò)計(jì)算每個(gè)節(jié)點(diǎn)的綜合權(quán)值，選取權(quán)值最大的節(jié)點(diǎn)。在主路徑中每2個(gè)充電節(jié)點(diǎn)都可插入滿足條件的插入節(jié)點(diǎn)，由此形成新的充電路徑。在新的充電路徑上再按照插入規(guī)則選擇插入節(jié)點(diǎn)，不斷循環(huán)，直至WCV的剩余電量不能維持其回到基站充電時(shí)停止，最終得到最優(yōu)充電路徑。

3 仿真實(shí)驗(yàn)

本文的仿真實(shí)驗(yàn)設(shè)計(jì)參考文獻(xiàn)[6]的設(shè)計(jì)，設(shè)置如下：(1)網(wǎng)絡(luò)大小為100 m×100 m的正方形區(qū)域，需充電節(jié)點(diǎn)數(shù)為100～300個(gè)；(2)WCV能量為5 000 J，行駛速度為1 m/s，移動(dòng)消耗能量為12 J/s，充電速度為8 J/s；(3)傳感器節(jié)點(diǎn)能量為100 J，節(jié)點(diǎn)的消耗速率為0.01～0.03 J/s。

在不同充電節(jié)點(diǎn)數(shù)量N、不同閾值δ下，CWSA算法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)死亡數(shù)的影響，結(jié)果如圖1所示。在不同充電節(jié)點(diǎn)數(shù)量N、不同的WCV數(shù)量M下，CWSA算法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)死亡數(shù)的影響如圖2所示。從圖1可以看出：在部署的節(jié)點(diǎn)數(shù)相同情況下，增加WCV數(shù)量能夠明顯降低節(jié)點(diǎn)死亡數(shù)量。從圖2可看出：在部署的節(jié)點(diǎn)數(shù)相同情況下，隨著閾值的增加，網(wǎng)絡(luò)的節(jié)點(diǎn)死亡數(shù)量也得到降低。這是由于隨著閾值的增加，節(jié)點(diǎn)剩余電量同時(shí)增加，節(jié)點(diǎn)死亡數(shù)量隨之降低。從圖1、圖2還可以看出：節(jié)點(diǎn)死亡數(shù)都隨著充電節(jié)點(diǎn)數(shù)的增加而降低。

圖1 不同小車數(shù)量下死亡的節(jié)點(diǎn)數(shù)

圖2 不同閾值下死亡的節(jié)點(diǎn)數(shù)

從網(wǎng)絡(luò)節(jié)點(diǎn)死亡數(shù)和總充電量?jī)煞矫鎸?duì)本文提出的CWSA算法和文獻(xiàn)[6]提出的基于最小生成樹的最優(yōu)移動(dòng)車輛數(shù)算法(Number of Mobile Vehicles，NMV)進(jìn)行比較，結(jié)果如圖3、圖4所示。從圖3可看出：在充電節(jié)點(diǎn)固定時(shí)，隨著WCV數(shù)量的增加，運(yùn)用2種算法的網(wǎng)絡(luò)節(jié)點(diǎn)死亡數(shù)都不斷減少，但在CWSA算法下網(wǎng)絡(luò)的死亡節(jié)點(diǎn)數(shù)減少得多。同時(shí)，當(dāng)WCV數(shù)量相同時(shí)，在CWSA算法下的死亡節(jié)點(diǎn)數(shù)明顯少于NMV算法，甚至少于一半以上。由此說(shuō)明，在相同的網(wǎng)絡(luò)規(guī)模下，CWSA算法能更好地延長(zhǎng)網(wǎng)絡(luò)壽命。從圖4可看出：隨著WCV數(shù)量的增加，在2種算法下網(wǎng)絡(luò)的總充電量不斷增加，但運(yùn)用CWSA算法的總充電量比NMV算法增加得更多。還可看出WCV數(shù)量相同時(shí)，運(yùn)用CWSA算法時(shí)，網(wǎng)絡(luò)的總充電量明顯高于NMV算法，由此也可以說(shuō)明在相同的網(wǎng)絡(luò)規(guī)模下CWSA算法能更充分地利用WCV，延長(zhǎng)網(wǎng)絡(luò)壽命。

圖3 無(wú)線充電車數(shù)目與節(jié)點(diǎn)死亡數(shù)關(guān)系

圖4 無(wú)線充電車數(shù)目與充電量關(guān)系

4 結(jié)束語(yǔ)

在大規(guī)模的WRSNs按需充電體系下，本文研究傳感器節(jié)點(diǎn)的多無(wú)線充電車調(diào)度優(yōu)化問(wèn)題，開發(fā)一種基于無(wú)線充電車能量利用率最大化的綜合權(quán)重調(diào)度算法，得到最小化網(wǎng)絡(luò)節(jié)點(diǎn)死亡數(shù)的充電優(yōu)化方案。可將此方案運(yùn)用到實(shí)際應(yīng)用中，用更低的成本維持網(wǎng)絡(luò)的運(yùn)行。本文的研究針對(duì)充電節(jié)點(diǎn)數(shù)目確定且不變的情況，但在實(shí)際應(yīng)用中，隨著時(shí)間的變化，充電節(jié)點(diǎn)數(shù)不斷增加，后續(xù)將對(duì)這種場(chǎng)景下的多無(wú)線充電車調(diào)度優(yōu)化問(wèn)題展開進(jìn)一步研究。