祝鐿雯,程宗毛

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

0 引 言

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

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

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

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

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

(1)

(2)

式中，v表示W(wǎng)CV的行駛速度，Ec表示節(jié)點(diǎn)的總?cè)萘浚珽i表示節(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è)計充電方案的目標(biāo)是最小化網(wǎng)絡(luò)節(jié)點(diǎn)死亡數(shù)，最大化WCV能量利用率。本文通過節(jié)點(diǎn)的死亡數(shù)Ndead和WCV的充電量Ea來衡量充電策略的性能。Ndead表示W(wǎng)CV到達(dá)充電節(jié)點(diǎn)時電量為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ò)模型下，解決問題的關(guān)鍵是WCV的充電順序。因此，本文提出一種無線充電車能量利用率最大化的綜合權(quán)重調(diào)度算法，即用綜合權(quán)重調(diào)度算法(Comprehensive Weight Scheduling Algorithm，CWSA)來提高網(wǎng)絡(luò)的生存率。首先，利用節(jié)點(diǎn)的綜合權(quán)重規(guī)劃WCV充電主路徑；然后，在WCV充電時，順帶為主路徑周圍充電節(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為一個類內(nèi)的節(jié)點(diǎn)進(jìn)行充電。在每一類內(nèi)，基站通過節(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。

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

通過式(7)計算得出所有充電節(jié)點(diǎn)的綜合權(quán)值，在每一類內(nèi)，將所有充電節(jié)點(diǎn)按權(quán)重由大到小排序，WCV按排序進(jìn)行節(jié)點(diǎn)充電，當(dāng)WCV的剩余電量不能維持WCV回到基站充電時停止充電并返回。每輛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個節(jié)點(diǎn)之間的距離為直徑繪制圓，將圓內(nèi)的節(jié)點(diǎn)選取為可行插入節(jié)點(diǎn)。

假設(shè)主路徑中插入一個節(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)不死亡，也不會導(dǎo)致WCV電量的耗盡以及Ninsert在WCV來到之前不死亡時，Ninsert就是插入節(jié)點(diǎn)。即：

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

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

本文的仿真實(shí)驗(yàn)設(shè)計參考文獻(xiàn)[6]的設(shè)計，設(shè)置如下：(1)網(wǎng)絡(luò)大小為100 m×100 m的正方形區(qū)域，需充電節(jié)點(diǎn)數(shù)為100～300個；(2)WCV能量為5 000 J，行駛速度為1 m/s，移動消耗能量為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算法對網(wǎng)絡(luò)節(jié)點(diǎn)死亡數(shù)的影響，結(jié)果如圖1所示。在不同充電節(jié)點(diǎn)數(shù)量N、不同的WCV數(shù)量M下，CWSA算法對網(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)剩余電量同時增加，節(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ù)和總充電量兩方面對本文提出的CWSA算法和文獻(xiàn)[6]提出的基于最小生成樹的最優(yōu)移動車輛數(shù)算法(Number of Mobile Vehicles，NMV)進(jìn)行比較，結(jié)果如圖3、圖4所示。從圖3可看出：在充電節(jié)點(diǎn)固定時，隨著WCV數(shù)量的增加，運(yùn)用2種算法的網(wǎng)絡(luò)節(jié)點(diǎn)死亡數(shù)都不斷減少，但在CWSA算法下網(wǎng)絡(luò)的死亡節(jié)點(diǎn)數(shù)減少得多。同時，當(dāng)WCV數(shù)量相同時，在CWSA算法下的死亡節(jié)點(diǎn)數(shù)明顯少于NMV算法，甚至少于一半以上。由此說明，在相同的網(wǎng)絡(luò)規(guī)模下，CWSA算法能更好地延長網(wǎng)絡(luò)壽命。從圖4可看出：隨著WCV數(shù)量的增加，在2種算法下網(wǎng)絡(luò)的總充電量不斷增加，但運(yùn)用CWSA算法的總充電量比NMV算法增加得更多。還可看出WCV數(shù)量相同時，運(yùn)用CWSA算法時，網(wǎng)絡(luò)的總充電量明顯高于NMV算法，由此也可以說明在相同的網(wǎng)絡(luò)規(guī)模下CWSA算法能更充分地利用WCV，延長網(wǎng)絡(luò)壽命。

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

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

4 結(jié)束語

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