陳晶晶，陳虹微，林坤智，白奧烔

(龍巖學(xué)院 福建龍巖 364000)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)涵蓋的應(yīng)用領(lǐng)域極其廣泛，同時也是物聯(lián)網(wǎng)不可替代的關(guān)鍵性技術(shù)。它包含自然災(zāi)害預(yù)警、品質(zhì)監(jiān)控、健康醫(yī)療、倉庫管理、智能家居等應(yīng)用[1]。網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)負(fù)責(zé)收集和處理監(jiān)控區(qū)域內(nèi)傳感對象的信息，并將信息發(fā)送給基站[2]。

能量一直在WSN中扮演著非常重要的角色。由于傳感器節(jié)點(diǎn)體積小，能裝載的電池容量有限，通過更換電池來延長無線傳感器網(wǎng)絡(luò)的生命周期比較困難。已有的研究大多數(shù)通過平衡電源消耗負(fù)載[3]、移動的數(shù)據(jù)收集方式[4]等方式來減緩能量的消耗速度，但是這些方式還是會耗盡電池能量從而減短了網(wǎng)絡(luò)的生存周期。

由于無線充電技術(shù)(WET)發(fā)展迅速且極具優(yōu)勢，許多學(xué)者考慮采用WET技術(shù)為WSN補(bǔ)充能量。無線可充電傳感器網(wǎng)絡(luò)(WRSN)就是指利用無線充電技術(shù)為WSN中的傳感器節(jié)點(diǎn)充電的網(wǎng)絡(luò)。據(jù)了解，近幾年的研究熱點(diǎn)就是WRSN中采用移動無線充電車(WCV)為節(jié)點(diǎn)充電。

關(guān)于無線充電車的研究主要分為確定性或非確定性方法。在確定性方法中，WCV按照固定的調(diào)度路線進(jìn)行周期性移動給傳感器節(jié)點(diǎn)充電。但是由于節(jié)點(diǎn)消耗能量的不確定性，該方法缺少靈活性。在非確定性方法中，一旦節(jié)點(diǎn)的能量水平低于預(yù)先設(shè)定的閾值時，節(jié)點(diǎn)自身就會向基站發(fā)送充電請求?；窘邮盏竭@些充電請求會按所設(shè)計方案依次對小車進(jìn)行充電調(diào)度[5]。過去的相關(guān)方案具有局限性，只考慮節(jié)點(diǎn)的剩余時間及節(jié)點(diǎn)在區(qū)域的地理位置這兩個因素。由于網(wǎng)絡(luò)具有復(fù)雜性，且充電調(diào)度不但受到節(jié)點(diǎn)的剩余時間制約而且受到節(jié)點(diǎn)的位置制約。以前的調(diào)度方法在性能方面并不理想，能夠服務(wù)的充電請求節(jié)點(diǎn)數(shù)量有限，當(dāng)網(wǎng)絡(luò)繁忙時，容易因?yàn)椴糠止?jié)點(diǎn)得不到及時充電而導(dǎo)致網(wǎng)絡(luò)中止。以前的研究從未從全局角度出發(fā)來考慮WCV總的移動成本。因此，本文從全局出發(fā)，首先提出優(yōu)先考慮WCV的剩余充電成本。通過全局計算剩余充電成本可以適當(dāng)減少WCV的移動距離，得到優(yōu)化的充電調(diào)度。

本文在過去研究的基礎(chǔ)上[6-7]進(jìn)一步設(shè)計了三種不同的剩余區(qū)域規(guī)劃模型來計算全局預(yù)估剩余成本。并在該模型的基礎(chǔ)上設(shè)計相應(yīng)的充電調(diào)度算法。該算法不僅考慮時間和空間因素，還考慮剩余預(yù)估成本因素。最后，對這三種模型進(jìn)行了大量的仿真，從而根據(jù)仿真結(jié)果分析和比較這三種模型的優(yōu)缺點(diǎn)。

1 符號說明、網(wǎng)絡(luò)模型及問題的定義

1.1 符號和說明

文中使用的相關(guān)符號及相關(guān)說明如表1所示。

表1 符號及其說明

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

所采用的WRSN模型如圖1所示。該模型組成包括，數(shù)個傳感器節(jié)點(diǎn)其分布具有隨機(jī)性，一部充電小車，以及安置在區(qū)域的左下角的一個基站。并且針對該網(wǎng)絡(luò)模型，本文做出如下假設(shè)。

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

(1)每一個傳感器節(jié)點(diǎn)的性能都相同，其位置都是隨機(jī)分布在感測區(qū)域內(nèi)。一旦節(jié)點(diǎn)其剩余能量低于預(yù)設(shè)閾值時，節(jié)點(diǎn)會直接向基站發(fā)送充電請求。

(2)無線充電小車在感測區(qū)域中可以無限制自由移動，但是只能單節(jié)點(diǎn)充電作業(yè)。每次執(zhí)行新的充電任務(wù)時小車都必須從基站出發(fā)，當(dāng)且僅當(dāng)?shù)竭_(dá)節(jié)點(diǎn)附近才能服務(wù)該節(jié)點(diǎn)作業(yè)，并且完成服務(wù)作業(yè)后需要返回基站進(jìn)行電池的更換。

(3)基站知道每個節(jié)點(diǎn)的坐標(biāo)，能夠迅速為小車規(guī)劃出相關(guān)充電調(diào)度。

1.3 全局充電成本預(yù)估模型

本小節(jié)提出一種全新的全局充電成本預(yù)估數(shù)學(xué)模型。利用該模型可以估算出小車的剩余充電移動成本CR?？紤]利用給定的剩余面積[6-7]來預(yù)估充電移動成本。本節(jié)首先將回顧剩余面積的概念，然后設(shè)計三個不同的數(shù)學(xué)預(yù)估模型，具體如下所示。

(1)剩余面積計算公式

剩余面積的定義就是剩余的未被選中服務(wù)的節(jié)點(diǎn)所圍成的區(qū)域。小車在小的區(qū)域范圍內(nèi)移動，所產(chǎn)生的成本較低，反之，較高。因此，剩余面積越小，所產(chǎn)生的剩余預(yù)估成本就越小。如圖2所示，節(jié)點(diǎn)A被選為小車調(diào)度的第一個要執(zhí)行的充電任務(wù)時(即，V={A})，圖中虛線圍起來的區(qū)域就是剩余面積W-V;如果節(jié)點(diǎn)B被選中(即，V={B})，紅色實(shí)線圍起來的區(qū)域就是剩余面積W-V。由圖2可知，AR(W-{A})比AR(W-{B})小[6-7]，所以會優(yōu)先考慮先給節(jié)點(diǎn)A充電。

圖2 剩余面積的示意圖

(2)預(yù)估模型一：區(qū)域用凸多邊形面積近似，內(nèi)部劃分為圓形

該預(yù)估模型的計算過程如圖3所示。除節(jié)點(diǎn)A以外的剩余充電需求節(jié)點(diǎn)連起來，形成一個凸多邊形。那么就可以根據(jù)公式(1)中計算凸多邊形面積的方法來計算AR(W-{A})的值。然后，根據(jù)剩余節(jié)點(diǎn)數(shù)N的值對此凸多邊形進(jìn)行區(qū)域劃分，平均分為N個大小相同的圓形圖形。

圖3 區(qū)域用凸多邊形面積近似，內(nèi)部劃分為圓形

接著，預(yù)估小車的剩余移動成本。具體計算過程如圖4所示：兩個相鄰節(jié)點(diǎn)間的距離約是圓半徑的兩倍。從節(jié)點(diǎn)A的剩余面積的劃分當(dāng)中可以看出，充電小車在剩余面積中的移動路徑就是從一個圓的圓心移動到相鄰圓的圓心。剩余節(jié)點(diǎn)有N個，則充電小車在這些節(jié)點(diǎn)間移動需要N-1次，所以，在剩余的面積中充電小車的移動成本為圓的半徑2(N-1)倍。則圓半徑的計算方法如公式(2)所示。

圖4 用圓覆蓋節(jié)點(diǎn)A的剩余面積

(1)

其中(xi，yi)是W-{A}的凸包中的節(jié)點(diǎn)坐標(biāo)。

(2)

A節(jié)點(diǎn)的預(yù)估充電移動成本CR(A)通過公式(3)來計算。

CR(A)=2(N-1)r+dAS+dNBS

(3)

(3)預(yù)估模型二：區(qū)域用方形面積近似，內(nèi)部劃分為圓形

如圖5所示，首先將節(jié)點(diǎn)A剩余面積形成一個方形，則該預(yù)估模型的剩余面積計算步驟如下所示。

首先，首先找出橫坐標(biāo)最大的兩個點(diǎn)B(x1,y1)，C(x2,y2)，計算出圖5中方形的底邊如下所示：

a=|x1-x2|

(4)

其次，再找出縱坐標(biāo)最大的兩個點(diǎn)D(x3,y3)，E(x4,y4)。計算出方形的高如下所示：

b=|y1-y2|

(5)

則所構(gòu)成的剩余面積如公式(6)所示。

AR(W-{A})=ab

(6)

由于節(jié)點(diǎn)A的剩余面積的內(nèi)部單元同模型一類似，也是采用N個以剩余節(jié)點(diǎn)為圓心，半徑相等的圓來劃分的，因此節(jié)點(diǎn)A的剩余預(yù)估成本采用公式(2)、(3)計算。

(4)預(yù)估模型三：區(qū)域用方形面積近似，內(nèi)部劃分為正方形

如圖6所示，首先將節(jié)點(diǎn)A剩余面積形成一個方形。則該預(yù)估模型的剩余面積計算步驟按模型二中公式(4)、(5)、(6)進(jìn)行計算。

圖6 區(qū)域?yàn)榉叫?，?nèi)部用方形劃分的模型

然后，將方形區(qū)域均等劃分成N個形狀大小統(tǒng)一的單元。其中剩余的面積AR(W-{A})中的節(jié)點(diǎn)的數(shù)目用N表示。每個單元均是一個以節(jié)點(diǎn)作為中心點(diǎn)，且各邊長相等的正方形圖形。

如圖6所示，節(jié)點(diǎn)A的剩余面積中，每兩個節(jié)點(diǎn)間的平均距離約等于正方形的邊長。從一個正方形的中心點(diǎn)移到相鄰的正方形的中心點(diǎn)就是充電小車在剩余面積中的移動路徑。所以，充電小車需要移動的次數(shù)為N-1次，充電小車在剩余的面積移動的成本相當(dāng)于是正方形圖形邊長的N-1倍。該正方形圖形邊長的計算方法如公式(7)所示。

(7)

優(yōu)先級和剩余的預(yù)估成本二者具有因果關(guān)系，較少的預(yù)估成本會產(chǎn)生較高的優(yōu)先級。因此，剩余的預(yù)估成本可用公式(8)計算。

CR(A)=(N-1)a+dAS+dNBS

(8)

1.4 算法設(shè)計

算法1 小車調(diào)度算法

本小節(jié)在充電小車的調(diào)度算法設(shè)計上采用剩余預(yù)估成本的概念，全局地考慮充電小車的調(diào)度問題，其算法描述如下所示。

該算法的第一步，計算節(jié)點(diǎn)的時間以及空間的優(yōu)先權(quán)，第二步計算節(jié)點(diǎn)集中每一個節(jié)點(diǎn)的CR(i)值，進(jìn)而根據(jù)CR(i)值的大小從中選擇CR值最小的節(jié)點(diǎn)將其從U中移出并且將其加入到V中。不斷重復(fù)地執(zhí)行上述過程，一直到U為空集停止，從而小車的充電調(diào)度路徑也被計算出來。

2 仿真結(jié)果

本小節(jié)通過大量的仿真來評估這三種預(yù)估模型的性能。

2.1 仿真設(shè)定

仿真的設(shè)計內(nèi)容如下所示，將100個靜態(tài)可充電節(jié)點(diǎn)隨機(jī)部署到600 m×600 m的方形區(qū)域內(nèi)。將基站置于區(qū)域的左上角，坐標(biāo)為(0，0)。其他仿真參數(shù)的設(shè)置如表2所示。

表2 仿真參數(shù)

仿真中用節(jié)點(diǎn)持續(xù)進(jìn)行工作的時間值來表示節(jié)點(diǎn)能量的閾值。WRSN在繁忙時會導(dǎo)致節(jié)點(diǎn)產(chǎn)生更多的能量的消耗，基站會頻繁接收到來自節(jié)點(diǎn)的充電請求。因此，根據(jù)節(jié)點(diǎn)的充電請求的頻率，設(shè)置空閑、適度、繁忙這三種類型網(wǎng)絡(luò)仿真環(huán)境。在仿真實(shí)驗(yàn)中，三種類型都隨時產(chǎn)生了100個充電請求，并且設(shè)置了5個能量閾值的范圍(單位：s)，即500±100，700±100，...和1300±100。為了讓預(yù)估模型更準(zhǔn)確，仿真數(shù)據(jù)均為100次仿真實(shí)驗(yàn)結(jié)果的平均值。

2.2 性能比較與分析

所謂的WRSN的生存周期就是死亡結(jié)點(diǎn)第一次出現(xiàn)的時間，這是評估調(diào)度算法性能的一項(xiàng)十分重要的指標(biāo)。仿真結(jié)果如圖7所示。從圖7中可以看出，任何一種模型的生存周期在網(wǎng)絡(luò)空閑的時候都比其他兩種網(wǎng)絡(luò)狀態(tài)時間要長。當(dāng)能量閥值設(shè)置在(500±100) s時，三種模型的生存周期會有細(xì)微區(qū)別，但是區(qū)別不大。因?yàn)楫?dāng)能量閾值設(shè)置在(700±100) s或者更高以上的范圍時，因?yàn)槿N類型模型的生存周期都能夠達(dá)到一樣。所以三種算法均能夠滿足節(jié)點(diǎn)所有的充電請求。

圖7 網(wǎng)絡(luò)的生存周期

本文將能夠在固定的時間段內(nèi)滿足發(fā)送充電請求的節(jié)點(diǎn)數(shù)，用成功充電的節(jié)點(diǎn)數(shù)來表示。若小車的充電消耗要求越低，充電節(jié)點(diǎn)的數(shù)目就必須越多。仿真結(jié)果如圖8所示。從圖8可以看出，在網(wǎng)絡(luò)繁忙狀態(tài)下，三種模型的充電節(jié)點(diǎn)數(shù)可以達(dá)到九十幾個。在適中和空閑狀態(tài)，充電的節(jié)點(diǎn)數(shù)可以達(dá)到100個。

圖8 成功充電節(jié)點(diǎn)數(shù)

本文將小車移動的總距離除以完成充電請求的節(jié)點(diǎn)數(shù)定義為小車的平均移動距離。如果平均移動距離越短，就代表算法自身的性能越好。仿真結(jié)果如圖9所示。從圖9可以看出，三種模型充電的平均距離基本一致，這三種模型都能較好地預(yù)估剩余移動成本。

圖9 平均充電移動距離

三種預(yù)估模型的誤差如圖10所示。從圖10可以看出，模型二的相對誤差最小，這說明模型二的精度更高一些。

圖10 相對誤差圖

3 結(jié)論

本文在按需充電的架構(gòu)的基礎(chǔ)上提出三種不同的預(yù)估模型。首先提出剩余預(yù)估成本的概念，并在此基礎(chǔ)上設(shè)計三種不同的預(yù)估模型，在這三種模型的基礎(chǔ)上設(shè)計了相關(guān)的充電調(diào)度算法。最后通過大量的實(shí)驗(yàn)仿真分析和比較這三種模型的網(wǎng)絡(luò)性能和相關(guān)預(yù)估誤差值。從仿真結(jié)果可以看出，三種模型的性能一樣，但是區(qū)域用方形面積近似，內(nèi)部劃分為圓形這一模型的相對誤差最小。

盡管文中的模型提出了令人振奮的新觀點(diǎn)，但是我們?nèi)匀恍枰龈嗟难芯抗ぷ鳌Ｗ鳛槲磥硌芯抗ぷ鞯囊徊糠?，將對模型進(jìn)行進(jìn)一步細(xì)化和證明。