無線可充電傳感器網(wǎng)絡(luò)混合移動充電調(diào)度研究*

張 娜，趙傳信*，陳思光，邵 星，王 楊

(1.安徽師范大學(xué)計算機與信息學(xué)院，安徽 蕪湖 241002；2.南京郵電大學(xué)物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003；3.鹽城工學(xué)院計算機學(xué)院，江蘇 鹽城 22405)

由大量的微小電子設(shè)備組成的無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)在環(huán)境監(jiān)測、工業(yè)智能制造、智慧城市等諸多領(lǐng)域得到廣泛應(yīng)用。然而受限于電池容量，能量問題一直是限制WSN應(yīng)用的難題應(yīng)用的難題[1－3]。為了解決能量受限問題，研究人員設(shè)計節(jié)能路由協(xié)議[4]或網(wǎng)絡(luò)編碼[5]來降低傳感器節(jié)點的能耗，或者利用能量收集器收集周圍的環(huán)境能量(如電磁能、風能、光能等)，并將其轉(zhuǎn)化為電能給電池充電[6]。然而節(jié)能路由等技術(shù)僅能有限延長工作時間，自然可再生資源的捕獲比較困難，且獲取能量并不穩(wěn)定。

近年來，通過無線能量傳輸技術(shù)延長傳感器網(wǎng)絡(luò)壽命已經(jīng)引起國內(nèi)外廣泛關(guān)注，可以通過靜態(tài)部署無線充電器或者移動無線充電器對傳感器節(jié)點進行能量補給[7－8]。靜態(tài)部署無線充電器需要在網(wǎng)絡(luò)中部署較多充電器[9]，移動充電器需要規(guī)劃充電路徑。在多數(shù)移動充電解決方案中，移動充電車定期進行充電巡行，并訪問每個WSNs節(jié)點[10－12]。目前移動充電研究方法主要為周期性充電調(diào)度[13]和按需實時充電[14]。周期性充電在每個周期固定巡游路徑對節(jié)點進行能量補給，按需充電只對發(fā)出請求的節(jié)點進行充電。周期性方案調(diào)度移動充電器定期訪問節(jié)點，為了減少路徑代價，移動充電器通常沿最短的哈密頓環(huán)運行[15]。

Xie等人假設(shè)充電器擁有充足的能量，移動充電器從基站出發(fā)，以確定的路徑對每個傳感器節(jié)點進行無線充電，然后返回基站完成一次旅行[16]。Dai等人考慮部署最小數(shù)量充電器遍歷大規(guī)模傳感器網(wǎng)絡(luò)中所有節(jié)點的問題，利用啟發(fā)式算法調(diào)度多個移動充電器，滿足網(wǎng)絡(luò)的充電需求[17]。Lyu等人考慮移動充電器能量有限約束下，最大化駐停時間，實際上等價于最小化行駛時間[18]。為了解決此問題提出了PSOGA算法調(diào)度移動充電器。Lin等人根據(jù)傳感器節(jié)點的功率狀態(tài)，以最小化充電延遲對移動定向充電器進行調(diào)度，在預(yù)定的周游路線上設(shè)計近似算法優(yōu)化移動充電器的充電方向[19]。我們前面工作中采用周期性路徑調(diào)度與時間分配結(jié)合優(yōu)化充電調(diào)度[20－21]。周期性充電適用于業(yè)務(wù)穩(wěn)定的網(wǎng)絡(luò)，對于實時性業(yè)務(wù)，如果在一個周期調(diào)度完成后發(fā)出的充電請求可能無法及時響應(yīng)，導(dǎo)致急需充電的節(jié)點因等待充電時間過長而能量耗盡。另外一些方案提出了按需充電，實時調(diào)度移動充電器對發(fā)出充電請求的節(jié)點補充能量[22－23]。

對于非周期性充電規(guī)劃，由于傳感器能量消耗的非確定性，需要根據(jù)傳感器節(jié)點充電請求實時做出調(diào)整。He等人提出對充電請求先來先服務(wù)，根據(jù)充電請求的先后次序調(diào)度[24]。該調(diào)度只考慮了時間先后關(guān)系忽略了空間距離，導(dǎo)致充電時延增加很多。為了克服這一缺點，He等人分析了按需調(diào)度的模型，設(shè)計了最近充電工作搶占調(diào)度以滿足實時性需求[25]。當新的請求節(jié)點在距離當前充電節(jié)點更近，優(yōu)先插入最新的節(jié)點進入充電隊列，然而距離較遠的節(jié)點可能會被餓死。Tomar等人提出一種根據(jù)節(jié)點剩余能量、節(jié)點能量消耗率和節(jié)點鄰域能量權(quán)重等多因素決策方案，量化節(jié)點充電調(diào)度優(yōu)先級，提高充電性能[14]。Jiang等人考慮了大規(guī)模傳感器網(wǎng)絡(luò)中的充電問題，將充電補給站部署和充電路徑調(diào)度聯(lián)合優(yōu)化，通過消減多余節(jié)點提高充電效率[26]。Dong等人對請求節(jié)點進行選擇，然后采用模擬退火算法優(yōu)化移動充電路徑提高充電效率[27]。然而單純以效率為目標的優(yōu)化會導(dǎo)致較多的節(jié)點因沒有被充電而餓死，從而影響到網(wǎng)絡(luò)性能。Kaswan考慮多個周期調(diào)度節(jié)點充電，以最小充電延遲為目標建立線性優(yōu)化問題，然后擴展重力搜索算法調(diào)度在不同周期調(diào)度充電器[28]。然而這種調(diào)度方案沒有考慮充電效率。Wang等人在按需調(diào)度基礎(chǔ)上考慮休眠調(diào)度，然后根據(jù)距離和節(jié)點能量狀態(tài)調(diào)節(jié)優(yōu)先權(quán)，調(diào)度節(jié)點充電順序[29]。Tomar等人以最小化駐停時間為目標來提高充電效率，選擇駐停點和優(yōu)化充電路徑[30]。Ye提出最大化網(wǎng)絡(luò)充電效率模型，設(shè)計了在線和離線貪婪的調(diào)度策略指導(dǎo)充電器充電[31]。

然而單純考慮實時性需求會降低整體充電效率?？紤]到這兩種典型方案局限性，本文針對可充電無線傳感器網(wǎng)絡(luò)存在多種類型業(yè)務(wù)的特點，設(shè)計了一種混合調(diào)度方案:首先提出了一種軟時間窗約束的充電模型，綜合考慮充電效率和充電時間窗約束設(shè)計合理的目標函數(shù)。整個WSNs工作期間被分為多個連續(xù)的充電周期，在每個周期內(nèi)首先通過改進的人工蜂群算法優(yōu)化調(diào)度派遣移動充電器對傳感網(wǎng)中請求充電的傳感器節(jié)點進行能量補給；然后針對實時充電請求，結(jié)合在線充電節(jié)點插入算法來滿足節(jié)點實時請求，從而滿足WSNs中不同充電業(yè)務(wù)需求，兼顧充電效率和實時性需求。

1 無線傳感器網(wǎng)絡(luò)充電問題描述

可充電無線傳感器網(wǎng)絡(luò)配置有可收集無線電波能量的接收裝置，可以通過無線電接收能量，供給傳感器節(jié)點使用。網(wǎng)絡(luò)工作時間被分為多個連續(xù)的充電周期，在每個周期內(nèi)分派移動充電器對傳感網(wǎng)中發(fā)出請求的傳感器節(jié)點進行補給。充電完成后，移動充電器返回到基站更換電池，過程循環(huán)直到網(wǎng)絡(luò)任務(wù)結(jié)束。節(jié)點能量低于預(yù)定閾值時，將發(fā)送充電請求，然后該節(jié)點被放入充電池中。每個周期開始時根據(jù)充電服務(wù)池中待充電節(jié)點隊列調(diào)度充電車充電。在小車充電過程中有可能新的傳感器節(jié)點需要充電，這些節(jié)點通過動態(tài)算法安排進入小車充電隊列，充電請求模型如圖1所示。

圖1 充電請求與處理流程

1.1 無線傳感器網(wǎng)絡(luò)能量消耗模型

無線可充電傳感器網(wǎng)絡(luò)是由一組分布在二維區(qū)域上傳感器節(jié)點集合V和固定的匯聚節(jié)點S組成的異構(gòu)傳感區(qū)域。假設(shè)n個傳感器節(jié)點V＝{v1，v2，v3，…，vn}隨機部署在二維區(qū)域內(nèi)。傳感器節(jié)點采集數(shù)據(jù)經(jīng)過預(yù)先設(shè)定的路由轉(zhuǎn)發(fā)給匯聚節(jié)點。傳感器節(jié)點通過多跳的方式將實時監(jiān)測產(chǎn)生的感知數(shù)據(jù)傳輸至Sink節(jié)點或者基站，節(jié)點之間采用短距通信(如Zigbee)自組織形成網(wǎng)絡(luò)，基站通過長程通信(如4/5G)與移動充電器通信。每個傳感器節(jié)點接受和發(fā)送的數(shù)據(jù)量不同，在單位時間內(nèi)傳感器節(jié)點vi接受到來自其他傳感器節(jié)點發(fā)來的數(shù)據(jù)為∑vj∈Ai rj，其中Ai表示經(jīng)過傳感器節(jié)點vi轉(zhuǎn)發(fā)數(shù)據(jù)的傳感器節(jié)點集合，單位時間內(nèi)傳感器節(jié)點vi感知的數(shù)據(jù)量為ri，傳感器節(jié)點vi在單位時間內(nèi)發(fā)送的數(shù)據(jù)量如式(1)所示。

根據(jù)傳感器節(jié)點感知數(shù)據(jù)量與傳輸數(shù)據(jù)量，建立可預(yù)測的節(jié)點能耗模型[32]，設(shè)表示節(jié)點vi發(fā)送單位數(shù)據(jù)能耗，表示接受單位數(shù)據(jù)能耗，表示感知單位數(shù)據(jù)能耗，傳感器節(jié)點vi在單位時間內(nèi)消耗的能量ei可以表示為式(2)。

1.2 無線傳感器網(wǎng)絡(luò)充電模型

當節(jié)點剩余能量低于預(yù)警閾值則可以充電[33]，節(jié)點剩余能量低于最低閾值將處于能量耗盡狀態(tài)。節(jié)點充電的時間窗集合TW＝{[st1，dt1]，…，[stn，dtn]}，其中sti表示傳感器節(jié)點vi最早充電時間，dti表示傳感器節(jié)點vi能量耗盡時間。移動充電器以速度sc行駛，單位能耗為p，達到節(jié)點附近以充電速率u補充能量，完成所有被調(diào)度節(jié)點充電后，充電器返回基站更換電池準備下一個周期充電。設(shè)REi(t)表示傳感器節(jié)點vi在t時刻的剩余能量，充電器移動至節(jié)點附近充電，充電率u為常數(shù)，ti表示傳感器節(jié)點vi的充電時間ti＝(Bi－REi)/u[33]。B為節(jié)點電池容量，設(shè)請求充電預(yù)警閾值為Bmax＝0.3 B，能量耗盡最低閾值Bmin＝0.1 B。傳感器節(jié)點的剩余能量REi低于Bmax需要補充能量，若移動充電器晚于傳感器節(jié)點的期望充電最遲時間dti須有相應(yīng)的懲罰。根據(jù)傳感器節(jié)點的剩余能量和能量消耗率可計算時間窗[rti，dti]如式(3)所示。

式中，TCurrent表示當前時間。移動充電器從基站出發(fā)為傳感器節(jié)點補充能量，在充電完成后，返回基站，整個過程花費時間不超過一個充電周期。充電周期T的值固定，即在充電周期T內(nèi)移動充電小車必須完成一輪完整的充電任務(wù)，如(4)所示。

式中，Ttravel表示移動充電器在路徑上行駛消耗的時間，表示在一個周期內(nèi)給傳感器充電的總時間，vc表示被調(diào)度充電的節(jié)點集合。

1.3 無線傳感器網(wǎng)絡(luò)充電調(diào)度模型

在實際網(wǎng)絡(luò)中，充電方案需要兼顧不同目標，將充電路徑能量消耗代價和節(jié)點充電時間窗結(jié)合起來設(shè)計目標函數(shù)。路徑上能量消耗代價可以反應(yīng)整個調(diào)度方案的能量使用效率，時間窗反應(yīng)了節(jié)點充電時間滿足情況。具體的目標描述為:

式中，Etravel表示小車在行駛過程中的能量消耗，其計算公式為:

式中，dist表示移動充電器一個周期內(nèi)行駛路徑總長度，sc表示小車行駛速度，p表示小車行駛單位時間能耗，dis(vi，vj)表示點節(jié)點vi和vj之間的歐式距離。不失一般性，假設(shè)移動充電器站點為v0，一次調(diào)度路徑長度計算公式為:

式中，s(i)表示節(jié)點vi在調(diào)度方案中的充電順序。ptvi表示違反時間窗節(jié)點需要進行懲罰量，其定義為:

式中，fci表示節(jié)點開始充電時間，α表示處罰系數(shù)。ptvi越大則對應(yīng)的懲罰力度越大。規(guī)劃路徑時盡可能減少在充電車在行駛過程的能耗Etravel，盡可能減少避免懲罰現(xiàn)象的發(fā)生從而盡可能為更多急需充電的節(jié)點充電。充電調(diào)度問題建立的數(shù)學(xué)模型P1為:

St:

式(9)表示最小化充電調(diào)度的目標，該目標在式(5)中定義。式(10)～式(13)是模型的約束條件，其中式(10)表示第一個節(jié)點充電開始時間，式(11)表示充電小車行駛路徑的長度，它是由充電路徑調(diào)度序列是s和節(jié)點坐標所決定。約束(12)表明在整個移動充電過程中不能超過一個充電周期T；約束(13)表示充電調(diào)度從需要充電的節(jié)點中選擇節(jié)點進行調(diào)度，Vc表示本輪調(diào)度的充電節(jié)點集合，Vd表示充電池中節(jié)點集合。

2 移動充電器充電調(diào)度和路徑規(guī)劃的優(yōu)化方法

為了便于規(guī)劃充電調(diào)度，將網(wǎng)絡(luò)工作期間分為若干個連續(xù)的充電調(diào)度周期，在每個充電周期內(nèi)對傳感器節(jié)點規(guī)劃充電調(diào)度順序。在每個充電周期開始階段，所有電池能量在本周期低于能量預(yù)警閾值的節(jié)點向基站發(fā)出充電請求，這些節(jié)點被放到充電池中。此外一些實時性任務(wù)可能會導(dǎo)致節(jié)點在本周期負載過重，導(dǎo)致節(jié)點能量處于閾值之下會實時提出充電請求。在充電過程中發(fā)生的實時請求，可以根據(jù)充電負載情況選擇是否插入到充電隊列中。每個周期開始，選擇充電池中節(jié)點并調(diào)度充電順序。因為移動充電調(diào)度屬于典型的TSP問題，顯然屬于NP問題。目前智能算法在解決NP問題上受到廣泛關(guān)注，本節(jié)采用人工蜂群算法(Artificial bee colony algorithm，ABC)調(diào)度每個周期處于充電池中的節(jié)點進行充電，而在充電過程中發(fā)生的充電請求將設(shè)計動態(tài)插入法實時調(diào)度。

2.1 人工蜂群算法搜索策略

人工蜂群算法通過模擬蜂群采蜜在解空間中尋找最優(yōu)解[34]。蜜源代表D維解空間中可行解集合X，第i個蜜源的位置可記為Xi＝(xi1，xi2，…，xiD)。蜂群根據(jù)分工不同，可分為雇傭蜂、觀察蜂和跟隨蜂。每個雇傭蜂對應(yīng)一個蜜源，雇傭蜂在對應(yīng)的蜜源Xi附近隨機選擇蜜源k，產(chǎn)生候選蜜源βi(Xi－Xk)，βi∈[－1，1]表示均勻分布的隨機數(shù)的擾動幅度。如果候選蜜源優(yōu)于雇傭蜂對應(yīng)蜜源則將原蜜源替換為候選蜜源。觀察蜂在蜂房中等待，根據(jù)雇傭蜂更新后的蜜源適應(yīng)度，計算每個蜜源的選擇概率。根據(jù)選擇概率，利用輪盤賭算法選擇一個蜜源k，更新蜜源候選解，如果候選蜜源優(yōu)于原蜜源則替換。當雇傭蜂在一定代數(shù)后沒有改進，這個可行解對應(yīng)的雇傭蜂在此時就會轉(zhuǎn)化為跟隨蜂，隨機產(chǎn)生一個新的有價值的蜜源。經(jīng)過多輪迭代操作，蜂群搜索到的解逐漸收斂于最優(yōu)解，最終輸出最佳解。

2.2 移動充電路徑規(guī)劃的人工蜂群編碼設(shè)計

無線傳感器網(wǎng)絡(luò)工作時，如果某個周期有較多的傳感器節(jié)點請求充電或者請求充電的節(jié)點位置距離較遠時，可能導(dǎo)致該充電周期內(nèi)無法滿足所有請求充電節(jié)點的需求。為此需要選擇部分節(jié)點在當前周期充電，其余節(jié)點放入下一個充電周期充電。在每個充電周期內(nèi)對已選擇的充電節(jié)點，進行充電調(diào)度及路徑規(guī)劃。假設(shè)有N個節(jié)點參與調(diào)度，充電調(diào)度可以表示為N個節(jié)點序列，因此每個待充電節(jié)點可以用分配N－1的充電次序，在對于當前所有請求充電的節(jié)點設(shè)置一個標志位tagi(取值0或1，1表示該節(jié)點需要在當前周期內(nèi)完成充電操作，0則表示該節(jié)點需要放入下一個充電周期充電)，N個充電節(jié)點的蜜源編碼如圖2所示。

圖2 一個蜜源編碼示意

假設(shè)基站收到2號、4號、5號、8號、10號、13號節(jié)點提出的充電請求，某一充電方案設(shè)置的每一個節(jié)點的標志位依次為:1、0、1、1、0、1，對應(yīng)的充電序列為:4、6、2、3、1、5；可知本充電周期選擇的節(jié)點次序是5號、8號、2號、13號四個傳感器。圖2的編碼方案可將節(jié)點選擇和充電路徑同時編入。一個蜜源編碼相當于一個完整的解決方案，其中優(yōu)秀的解決方案具有更優(yōu)的適應(yīng)度，本文適應(yīng)度可以表示為－f，f在式(5)中定義。

2.3 改進的人工蜂群算法

基本人工蜂群算法只能求解函數(shù)優(yōu)化問題，而充電調(diào)度是典型的整數(shù)優(yōu)化問題，為此提出改進人工蜂群算法(Improve artificial bee colony algorithm，IABC)。改進之處主要體現(xiàn)在蜜源初始化和蜂群對蜜源的更新。蜜源包含選擇標志和充電序列兩個部分，選擇標志采用0/1布爾變量表示對應(yīng)的節(jié)點是否在本輪充電，對于每個節(jié)點的tagi進行初始化如式(14)所示。

式中，rand()表示一個0～1上的隨機數(shù)，sigmoid(x)的定義如式(15)所示。

式中，x表示任意一個實數(shù)，取值范圍是(－∞，＋∞)，因而sigmoid(x)的范圍處于(0，1)。通過式(14)，可以對編碼中的每個節(jié)點獨立執(zhí)行tag初始化。充電序列在初始化時隨機生成不同的序號排列。不同于基本蜂群算法只需要簡單的將每一維變量初始化在上下界即可，充電調(diào)度的充電序列優(yōu)化需要在初始化時隨機生成不同排列。針對每個蜜源獨立進行初始化可以得到初始化的蜜源種群。

由圖2編碼可知，蜜源種群更新需要整體上對調(diào)度排列和標志進行更新操作。為此引入進化算法的交叉和變異操作，結(jié)合交叉變異的原則，對基本人工蜂群算法探索過程進行相應(yīng)的改進。在搜索過程中，對選擇的路徑提出新的交換機制實現(xiàn)了信息共享和交流，從而提高全局搜索能力使具有更優(yōu)的多樣性。具體執(zhí)行流程如下。

①交叉操作:選取單點交叉，即隨機選擇交叉段，然后將父代個體在相同位置上進行交叉替換，如父代個體A(0，1，0，1，1，0｜1，2，3，4，5，6)和個體B(0，0，1，1，1，1｜6，1，3，2，5，4)。采用單點交叉生成兩個子代為C1(0，1，0，1，1，1｜1，2，3，2，5，4)和C2(0，0，1，1，1，0｜6，1，3，4，5，6)，生成子代充電調(diào)度序列出現(xiàn)沖突現(xiàn)象，C1中2重復(fù)，C2中6重復(fù)，對于出現(xiàn)的沖突可采用沖突消解方法，可見，二者交換的基因段為254和456，保持此段不變，對于C1，第一個沖突基因為2，取得2在交換段C1中的位置(4)，將交換段外沖突基因替換為C2中相應(yīng)位置的基因，即4。多次執(zhí)行替換直到?jīng)]有沖突即可。

②變異操作:變異操作是增加蜜源多樣性的關(guān)鍵操作。對執(zhí)行性變異操作的蜜源，隨機選擇標志位tagi修改為tagi＝1－tagi，然后隨機選擇充電序列兩個位置進行交換操作，變異生成蜜源不會產(chǎn)生序列沖突。

改進的人工蜂群算法中雇傭蜂隨機從種群中選擇蜜源進行交叉變異操作，可以有效擴大算法搜索空間，有利于增加蜜源多樣性。觀察蜂根據(jù)輪盤賭選擇蜜源，優(yōu)質(zhì)蜜源更有機會參加下一代交叉變異，即性能較優(yōu)的充電規(guī)劃方案有更高的概率參與下一代進化操作。跟隨蜂則在充電規(guī)劃方案陷入局部解時跳出局部解。基于人工蜂群算法架構(gòu)，結(jié)合進化算法，給出改進蜂群算法過程如下:

根據(jù)算法1可知，行7－行17的復(fù)雜度是O(SN×V)，它是行6－行19的循環(huán)體，故算法復(fù)雜度為O(Maxcycle×SN×V)，這是一個多項式時間復(fù)雜度算法?？紤]到在網(wǎng)絡(luò)中一個周期充電節(jié)點數(shù)量一般規(guī)模有限，多項式復(fù)雜度算法可以在期望時間內(nèi)完成按需充電節(jié)點的調(diào)度。

算法1 改進的人工蜂群無線充電調(diào)度算法(IABC)

3 動態(tài)插入充電調(diào)度

無線傳感網(wǎng)工作過程中，可能會遇到新的業(yè)務(wù)請求導(dǎo)致節(jié)點能耗增加過快，同時轉(zhuǎn)發(fā)路徑上的節(jié)點也可能會低于預(yù)警閾值。這種實時充電需求難以提前預(yù)知，為此需要在充電過程中考慮是否插入節(jié)點到充電隊列中。如圖3所示，經(jīng)過人工蜂群算法調(diào)度的序列為v0→…→vi→vi＋1→…→vj－1→vj＋2→v0，此時有新的節(jié)點j和j＋1需要插入到剩下的充電隊列中，通過貪婪算法選擇到合適的位置進行節(jié)點插入操作，結(jié)果如圖3右邊所示。

圖3 插入節(jié)點的充電路徑

在尚未執(zhí)行充電的待充電隊列中選擇插入新節(jié)點的位置，需要考慮滿足時間和容量的約束，并使得新的充電隊列方案目標函數(shù)仍保持最優(yōu)。如圖4所示，在每個充電周期中，設(shè)置動態(tài)小周期Δt，實時檢測未在充電池中的傳感器節(jié)點能量是否低于充電閾值。如果有傳感器節(jié)點能量低于充電閾值，則加入充電池，通過貪婪算法選擇合適的位置進行節(jié)點插入操作。

圖4 動態(tài)插入充電調(diào)度

傳感器節(jié)點m添加到充電路徑P后增加的目標函數(shù)值可表示為式(16)。

P代表尚未執(zhí)行充電的已調(diào)度隊列，傳感器節(jié)點m表示被添加的緊急節(jié)點，在P隊列首位和中間任一位置，選擇最小Δf(P，m)且滿足式(12)約束條件。將帶充電節(jié)點插入到該位置，完成新節(jié)點的動態(tài)插入。如果沒有可行插入位置，則放棄在本周期對該節(jié)點進行充電。

算法2 動態(tài)充電隊列插入算法(Dynamic Insert Algorithm，DIA)

4:從Vuc取出vcur，將m插入到當前節(jié)點vcur位置前；5:根據(jù)式(12)計算m插入Vuc中后，節(jié)點的充電時間。6:if(約束(12)滿足)7:計算當前插入當前候選節(jié)點的目標函數(shù)f(Pi，m)8:else 9:此條充電路徑不可行；10:end if 11:移動到Vuc中下一個節(jié)點位置；12:end while 13:if(可行的充電路徑)14:輸出適應(yīng)度最佳min f(Pi，m)的充電隊列L；15:else 16:return 0；17:end if

不失一般性，假設(shè)尚未充電節(jié)點數(shù)量為K，尋找插入點需要循環(huán)O(K)，檢查約束是否滿足需要O(N)，因此算法時間復(fù)雜度為O(KN)。在每個充電周期中，動態(tài)插入算法在移動充電車開始工作以后運行，與IABC算法相結(jié)合工作。

4 仿真實驗與分析

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

為了驗證算法的可行性和有效性，設(shè)置不同網(wǎng)絡(luò)規(guī)模的實驗環(huán)境。隨機部署40～200不等數(shù)量的傳感器節(jié)點，節(jié)點路徑預(yù)先確定，移動充電器補給基地位于區(qū)域中心位置。節(jié)點業(yè)務(wù)分周期性和實時性業(yè)務(wù)兩種，周期性業(yè)務(wù)以固定速率采集數(shù)據(jù)向匯聚節(jié)點發(fā)送數(shù)據(jù)，實時業(yè)務(wù)按概率在每個周期隨機產(chǎn)生新的業(yè)務(wù)(每個周期＜3個節(jié)點)。設(shè)充電周期為T＝8 000 s；小車攜帶足夠的電池能量；每個傳感器節(jié)點初始能量不同，傳感器能耗參數(shù)參考CC2430[16]。每個周期開始時通過調(diào)度算法對放在充電池中的節(jié)點進行選擇和調(diào)度。

表1 網(wǎng)絡(luò)和節(jié)點參數(shù)設(shè)置

此外在充電過程中，若新的傳感器節(jié)點因能量低于充電閾值發(fā)出充電請求，在滿足本充電周期約束條件的情況下插入后繼充電調(diào)度隊列，其余節(jié)點放回充電池，分配至下一個充電周期。在這里將設(shè)置不同的傳感器網(wǎng)絡(luò)規(guī)模場景，并依次進行測試與比較。

為了衡量算法的性能，將本文所提出的方案IABC＋DIA算法與EDF算法[26]和近似算法[33]進行比較，為了簡潔，下文中IABC表示IABC＋DIA方案。EDF算法采用基本先來先服務(wù)策略調(diào)度，無法滿足的節(jié)點直接放到下一個周期；近似算法采用貪婪策略選擇節(jié)點調(diào)度，其他節(jié)點放到后繼周期充電。設(shè)置四種不同規(guī)模的傳感器網(wǎng)絡(luò)，傳感器節(jié)點隨機初始電量，每個傳感器節(jié)點能耗與網(wǎng)絡(luò)拓撲結(jié)構(gòu)有關(guān)。在不同規(guī)模場景下，比較三種算法并從饑餓節(jié)點個數(shù)、充電路徑的長度，充電周期總能耗等幾個指標來衡量不同算法的性能。饑餓的節(jié)點個數(shù)表示不能在達到最低閾值前補充能量節(jié)點數(shù)量，充電路徑長度表示一次充電小車移動路徑和，充電總能耗表示每個周期充電器在移動與充電上消耗的總能量，充電效率表示每個周期充電過程中對傳感器節(jié)點充電的總能量占移動充電器在充電和行駛消耗總能量的百分比。IABC算法參數(shù)設(shè)置為種群規(guī)模NP＝100(雇傭蜂數(shù)量＋觀察蜂數(shù)量)，交叉率80%，變異率2%，limit值為20代，循環(huán)周期為500次。

4.2 實驗結(jié)果與分析

4.2.1 不同算法同一調(diào)度周期結(jié)果比較

首先比較三種算法在同一充電周期充電路徑，充電路徑是充電車移動的軌跡。如圖5表示的是傳感器節(jié)點數(shù)量為5(a)～5(c)的場景下第18周期充電節(jié)點的選擇和充電規(guī)劃路徑。圖5(a)表示的是EDF算法的路徑規(guī)劃。圖5(b)表示的是近似算法的路徑規(guī)劃。圖5(c)表示的是IABC算法的路徑規(guī)劃。圖5(d)～5(f)表示的是傳感器節(jié)點的個數(shù)為200的場景第8周期，移動充電器對需要充電傳感器節(jié)點的選擇及路徑規(guī)劃。圖5(d)～5(f)表示的路徑分別是EDF算法、近似算法和IABC算法在第8周期規(guī)劃的結(jié)果三種算法規(guī)劃的路徑。通過圖中觀察可知，EDF算法完全按照節(jié)點能量耗盡時間先后順序充電，充電車移動路徑?jīng)]有規(guī)律；近似算法與IABC充電路徑考慮到了路徑代價，但是受到充電節(jié)點時間窗要求限制，充電路徑并不是完全以路徑最短為標準。

圖5 兩種網(wǎng)絡(luò)規(guī)模下同一周期的不同算法規(guī)劃路徑比較

進一步增加節(jié)點規(guī)模為90和120個節(jié)點的網(wǎng)絡(luò)，分別對不同算法在同一周期內(nèi)對充電結(jié)果的各性能參數(shù)對比，結(jié)果如表2所示。

表2 三種算法特定周期性能比較

通過四種不同場景比較，可以發(fā)現(xiàn)IABC能夠獲得更短的路徑長度，EDF算法調(diào)度路徑長度最長，是IABC算法的2.01到4.47倍，近似算法調(diào)度路徑長度是IABC算法的1.54到2.55倍。IABC饑餓節(jié)點的數(shù)量少于兩種對比算法，其中EDF算法饑餓節(jié)點數(shù)量最多，是IABC算法的2.13到4.38倍。近似算法饑餓節(jié)點數(shù)量是IABC算法的1到2倍。從實驗可以看出，EDF雖然在周期內(nèi)為傳感器節(jié)點補充了更多的能量，但是路徑長度過長，導(dǎo)致整體的充電效率低下；而近似算法雖然充電效率有所提高，但給傳感器節(jié)點補充能量總數(shù)相對減少了，同時沒有充分考慮節(jié)點能量較少的節(jié)點；IABC算法整體優(yōu)化，減少路徑消耗的同時盡最大可能為更多節(jié)點的補充能量。

4.2.2 不同算法多個調(diào)度周期性能比較

進一步比較三種算法在連續(xù)多個工作周期的性能差異，分別從路徑長度，饑餓節(jié)點數(shù)量和充電效率三個方面進行比較。首先比較充電路徑的長度，如圖6表示的是移動小車不同周期行駛的路徑長度。圖6(a)～(d)分別表示40、90、120和200個節(jié)點的不同周期路徑長度的比較。隨著傳感器節(jié)點數(shù)目的增多，請求的傳感器節(jié)點相繼增多，從而使得充電器行駛的路徑長度逐漸增大。EDF算法和近似算法的波動幅度相似，IABC算法充電的路徑長度波動幅度比較低。在四種場景下，EDF算法的平均路徑長度為IABC算法的2.03～2.95倍，近似算法的平均路徑長度為IABC算法的1.53～2.30倍。隨著節(jié)點數(shù)量的增加，不同算法規(guī)劃的充電路徑長度都有所增長。從圖中可以看出，不同算法之間的差距并不是隨節(jié)點規(guī)模擴大而線性增加。節(jié)點數(shù)目為90個時，不同算法之間的差距最大，EDF算法的平均路徑長度是IABC算法的2.95倍，近似算法的平均路徑長度是IABC算法的2.30倍。在不同規(guī)模的傳感器網(wǎng)絡(luò)下，由于網(wǎng)絡(luò)動態(tài)性，部分周期IABC算法調(diào)度的路徑長度不一定最短，但是平均充電路徑行駛的距離顯著低于兩個對比算法，說明IABC算法在優(yōu)化路徑方面具有優(yōu)勢。

圖6 多個充電周期內(nèi)充電小車行駛路徑長度

其次比較不同充電周期總能耗，如圖7分別表示的是不同周期三種算法下總能耗的比較。如圖7(a)～(d)分別表示部署40、90、120和200個節(jié)點的場景下，三種算法的總耗能?？梢钥闯鲭S著節(jié)點規(guī)模的擴大，三種算法的總能耗都有所升高。在傳感器數(shù)量較小的情況下，IABC在少數(shù)周期的總能耗會大于另外兩種算法，但隨著傳感器節(jié)點增多，IABC算法的總能耗相對較優(yōu)。在4種場景IABC算法平均充電總能耗為EDF算法的67.37%～87.89%，為近似算法的47.33%～83.90%。IABC算法的總能耗相對較優(yōu)的原因是在行駛路徑過程中，與其他兩個算法相比行駛的路徑較短，從而行駛能耗較少。

圖7 多個充電周期內(nèi)總能耗

再次比較饑餓節(jié)點個數(shù)。為保證節(jié)點可以得到及時供電，每個充電節(jié)點設(shè)置時間窗，盡可能避免節(jié)點違反時間窗受到懲罰。分別對比四種場景下，在每個充電周期中三種算法饑餓節(jié)點個數(shù)，從而比較算法的有效性。圖8(a)～(d)分別表示40、90、120和200個節(jié)點不同周期中饑餓節(jié)點數(shù)目。由圖看出在每個充電周期中，隨著請求節(jié)點數(shù)量增加，饑餓的節(jié)點數(shù)目也隨之增加。EDF算法下，饑餓的節(jié)點個數(shù)相對較多。IABC算法平均饑餓節(jié)點數(shù)目為EDF算法的22.50%～29.68%，為近似算法的46.46%～71.05%。顯然，IABC算法饑餓節(jié)點的個數(shù)在三個算法中最少。EDF算法根據(jù)傳感器節(jié)點的響應(yīng)先后，并不考慮路徑長度，造成饑餓節(jié)點個數(shù)最多。近似算法雖然考慮了充電效率，但是基于貪婪的策略容易限于局部最優(yōu)。同時可以看出，隨著節(jié)點數(shù)目增多，IABC饑餓節(jié)點數(shù)目波動較小，而另兩種算法波動較大?？傮w而言，通過多個連續(xù)周期比較可以發(fā)現(xiàn)，IABC算法可以有效優(yōu)化充電路徑，降低能耗成本，提高了充電效率。

圖8 多個充電周期內(nèi)饑餓節(jié)點數(shù)目

4.2.3 不同網(wǎng)絡(luò)參數(shù)對算法性能評估

為了衡量不同網(wǎng)絡(luò)參數(shù)對算法的影響，在同一規(guī)模下配置不同參數(shù)，比較不同參數(shù)值對充電路徑長度、充電周期總能耗及饑餓節(jié)點數(shù)目的影響。

為合理設(shè)置目標函數(shù)中懲罰系數(shù)中的參數(shù)α，在同樣規(guī)模的實驗環(huán)境下，利用本文所提出的方案IABC算法進行實驗。如圖9(a)表示的是傳感器節(jié)點數(shù)量為120的場景下，設(shè)置不同參數(shù)α，每周期產(chǎn)生饑餓節(jié)點的數(shù)目。如圖9(b)表示的是傳感器節(jié)點數(shù)量為120的場景下，設(shè)置不同參數(shù)α，每周期移動充電器所消耗的總能量。

根據(jù)以上實驗結(jié)果，當參數(shù)α設(shè)置為0.01時，懲罰系數(shù)最為合理。此時每周期產(chǎn)生的饑餓節(jié)點數(shù)目較為均衡且總體低于參數(shù)α為0.001、0.005、0.05、0.1時每周期產(chǎn)生的饑餓節(jié)點數(shù)目。傳感器節(jié)點得到了有效及時的能量補充。同時，圖9(b)顯示當參數(shù)α設(shè)置為0.01時，多個周期的充電總能耗總體低于參數(shù)α設(shè)置為其他數(shù)值時，充電效果較好。所以，本文實驗均在懲罰系數(shù)中參數(shù)α為0.01的基礎(chǔ)上進行。

圖9 不同參數(shù)α對饑餓節(jié)點的影響

其次分析傳感器節(jié)點數(shù)據(jù)率r對性能影響。如圖10(a)表示不同節(jié)點數(shù)據(jù)率r，同周期中充電行駛路徑的比較。如圖10(b)表示不同節(jié)點數(shù)據(jù)率r下，同一周期中充電總能耗的比較。如圖10(c)表示不同節(jié)點數(shù)據(jù)率r下，同一周期中饑餓節(jié)點數(shù)目的比較。可以看出，節(jié)點數(shù)據(jù)率r＝2 000 bit/s時，充電小車行駛路徑、充電周期總能耗以及饑餓節(jié)點數(shù)目，普遍低于r＝3 000 bit/s時，饑餓節(jié)點數(shù)目平均從0.55個增加到5.25個。r＝3 000 bit/s時充電小車行駛路徑、充電周期總能耗以及饑餓節(jié)點數(shù)目也普遍低于r＝4 000 bit/s時，特別是饑餓節(jié)點數(shù)目平均從5.25個增加到7.95個。節(jié)點數(shù)據(jù)率r的增高對充電小車行駛路徑、充電周期總能耗以及饑餓節(jié)點數(shù)目有負面影響。這是由于節(jié)點能耗由傳感器感知和傳輸?shù)臄?shù)據(jù)量決定，當數(shù)據(jù)率增加時，節(jié)點能耗增加，從而導(dǎo)致充電需求也相應(yīng)增加。

圖10 傳感器節(jié)點數(shù)據(jù)率對充電性能的影響

再次分析充電小車行駛速度sc對IABC算法性能影響，在行駛路徑長度相同的情況下，小車行駛速度sc決定了小車行駛的時間，從而影響小車在行駛過程中所消耗的能量及充電周期中實際的充電時間。圖11(a)表示不同小車行駛速度下充電行駛路徑的比較，隨行駛速度增加，sc＝2 m/s平均路徑長度為1 105.90 m，sc＝8 m/s平均路徑長度為1 042.35 m和sc＝20 m/s平均路徑長度為772.55 m。圖11(b)表示不同小車行駛速度下充電總能耗的比較，sc＝2 m/s平均總能耗為10 076.85 J，sc＝8 m/s平均總能耗為為8 907.45 J和sc＝20 m/s平均總能耗為7 644.00 J。圖11(c)表示不同小車行駛速度饑餓節(jié)點數(shù)目的比較，平均饑餓節(jié)點數(shù)目分別為7.85個、5.25個和4.15個。可以看出，隨著小車行駛速度值的增大，充電小車行駛路徑、充電周期總能耗以及饑餓節(jié)點數(shù)目等普遍降低。這是由于小車加快行駛速度，可以節(jié)約充電時間，在一個周期充電節(jié)點數(shù)量得以增加，從而減少后繼周期充電壓力。

圖11 充電小車行駛速度對充電性能的影響

再次分析充電速率對充電性能的影響。充電速率分別設(shè)置為u＝8 J/s，u＝18 J/s和u＝30 J/s。圖12(a)表示不同充電速率充電行駛路徑的比較，隨充電速度增加，平均充電路徑從u＝8 J/s時1 151.35 m降到u＝18 J/s時1 042.35 m和u＝30 J/s時511.95 m。如圖12(b)表示不同u充電總能耗的比較，u＝8 J/s時平均充電總能耗為8 860.55 J，u＝18 J/s時平均充電總能耗為8 907.45 J和u＝30 J/s時平均充電總能耗為5 793.80 J。充電速率u的取值對充電能量有一定的影響且波動幅度在一定的范圍，原因在于充電的速率越快，充電時間越小，消耗的能量也相對減少。圖12(c)表示不同充電速率下饑餓節(jié)點數(shù)目的比較，在三種充電速度下，饑餓的節(jié)點平均數(shù)量分別為5.6個、5.25個和2.85個。充電速率的取值對饑餓節(jié)點數(shù)目有一定的影響，但波動幅度在一定的范圍，主要由于充電的速率越快，充電時間越小，可以滿足更多充電節(jié)點的充電需求。

圖12 充電速率對充電性能的影響

5 總結(jié)

能量補給是有效延長傳感器網(wǎng)絡(luò)生命期的關(guān)鍵技術(shù)之一，無線能量補給已經(jīng)成為潛在的有效方法。通過將周期性和按需調(diào)度相結(jié)合，文中設(shè)計了一種面向混合業(yè)務(wù)的混合調(diào)度算法。通過仿真實驗比較，在充電路徑、充電總能耗和饑餓節(jié)點數(shù)目方面顯著優(yōu)于對比算法。在饑餓節(jié)點數(shù)目的關(guān)鍵指標上，在四種不同場景中所提混合算法平均優(yōu)于EDF算法4.11倍和近似算法1.87倍。在另外兩個指標上也優(yōu)于對比算法，顯示所提出的算法具有較好性能，適合無線可充電傳感器網(wǎng)絡(luò)充電調(diào)度。當網(wǎng)絡(luò)規(guī)模更大時，單個小車可能無法滿足充電需求，從而導(dǎo)致饑餓節(jié)點顯著增加，下一步將要考慮大規(guī)模網(wǎng)絡(luò)中多充電器的混合調(diào)度算法。