基于不同預估模型的充電調度算法的性能比較

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

(龍巖學院 福建龍巖 364000)

無線傳感器網絡(Wireless Sensor Networks，WSN)涵蓋的應用領域極其廣泛，同時也是物聯網不可替代的關鍵性技術。它包含自然災害預警、品質監控、健康醫療、倉庫管理、智能家居等應用[1]。網絡中的傳感器節點負責收集和處理監控區域內傳感對象的信息，并將信息發送給基站[2]。

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

由于無線充電技術(WET)發展迅速且極具優勢，許多學者考慮采用WET技術為WSN補充能量。無線可充電傳感器網絡(WRSN)就是指利用無線充電技術為WSN中的傳感器節點充電的網絡。據了解，近幾年的研究熱點就是WRSN中采用移動無線充電車(WCV)為節點充電。

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

本文在過去研究的基礎上[6-7]進一步設計了三種不同的剩余區域規劃模型來計算全局預估剩余成本。并在該模型的基礎上設計相應的充電調度算法。該算法不僅考慮時間和空間因素，還考慮剩余預估成本因素。最后，對這三種模型進行了大量的仿真，從而根據仿真結果分析和比較這三種模型的優缺點。

1 符號說明、網絡模型及問題的定義

1.1 符號和說明

文中使用的相關符號及相關說明如表1所示。

表1 符號及其說明

1.2 網絡模型

所采用的WRSN模型如圖1所示。該模型組成包括，數個傳感器節點其分布具有隨機性，一部充電小車，以及安置在區域的左下角的一個基站。并且針對該網絡模型，本文做出如下假設。

圖1 WRSN網絡模型

(1)每一個傳感器節點的性能都相同，其位置都是隨機分布在感測區域內。一旦節點其剩余能量低于預設閾值時，節點會直接向基站發送充電請求。

(2)無線充電小車在感測區域中可以無限制自由移動，但是只能單節點充電作業。每次執行新的充電任務時小車都必須從基站出發，當且僅當到達節點附近才能服務該節點作業，并且完成服務作業后需要返回基站進行電池的更換。

(3)基站知道每個節點的坐標，能夠迅速為小車規劃出相關充電調度。

1.3 全局充電成本預估模型

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

(1)剩余面積計算公式

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

圖2 剩余面積的示意圖

(2)預估模型一：區域用凸多邊形面積近似，內部劃分為圓形

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

圖3 區域用凸多邊形面積近似，內部劃分為圓形

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

圖4 用圓覆蓋節點A的剩余面積

(1)

其中(xi，yi)是W-{A}的凸包中的節點坐標。

(2)

A節點的預估充電移動成本CR(A)通過公式(3)來計算。

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

(3)

(3)預估模型二：區域用方形面積近似，內部劃分為圓形

如圖5所示，首先將節點A剩余面積形成一個方形，則該預估模型的剩余面積計算步驟如下所示。

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

a=|x1-x2|

(4)

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

b=|y1-y2|

(5)

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

AR(W-{A})=ab

(6)

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

(4)預估模型三：區域用方形面積近似，內部劃分為正方形

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

圖6 區域為方形，內部用方形劃分的模型

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

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

(7)

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

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

(8)

1.4 算法設計

算法1 小車調度算法

本小節在充電小車的調度算法設計上采用剩余預估成本的概念，全局地考慮充電小車的調度問題，其算法描述如下所示。

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

2 仿真結果

本小節通過大量的仿真來評估這三種預估模型的性能。

2.1 仿真設定

仿真的設計內容如下所示，將100個靜態可充電節點隨機部署到600 m×600 m的方形區域內。將基站置于區域的左上角，坐標為(0，0)。其他仿真參數的設置如表2所示。

表2 仿真參數

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

2.2 性能比較與分析

所謂的WRSN的生存周期就是死亡結點第一次出現的時間，這是評估調度算法性能的一項十分重要的指標。仿真結果如圖7所示。從圖7中可以看出，任何一種模型的生存周期在網絡空閑的時候都比其他兩種網絡狀態時間要長。當能量閥值設置在(500±100) s時，三種模型的生存周期會有細微區別，但是區別不大。因為當能量閾值設置在(700±100) s或者更高以上的范圍時，因為三種類型模型的生存周期都能夠達到一樣。所以三種算法均能夠滿足節點所有的充電請求。

圖7 網絡的生存周期

本文將能夠在固定的時間段內滿足發送充電請求的節點數，用成功充電的節點數來表示。若小車的充電消耗要求越低，充電節點的數目就必須越多。仿真結果如圖8所示。從圖8可以看出，在網絡繁忙狀態下，三種模型的充電節點數可以達到九十幾個。在適中和空閑狀態，充電的節點數可以達到100個。

圖8 成功充電節點數

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

圖9 平均充電移動距離

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

圖10 相對誤差圖

3 結論

本文在按需充電的架構的基礎上提出三種不同的預估模型。首先提出剩余預估成本的概念，并在此基礎上設計三種不同的預估模型，在這三種模型的基礎上設計了相關的充電調度算法。最后通過大量的實驗仿真分析和比較這三種模型的網絡性能和相關預估誤差值。從仿真結果可以看出，三種模型的性能一樣，但是區域用方形面積近似，內部劃分為圓形這一模型的相對誤差最小。

盡管文中的模型提出了令人振奮的新觀點，但是我們仍然需要做更多的研究工作。作為未來研究工作的一部分，將對模型進行進一步細化和證明。