俞立春， 呂紅芳， 何 力， 李俊甫

(上海電機(jī)學(xué)院 電氣學(xué)院， 上海 201306)

無線可充電傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)之間收集和傳遞數(shù)據(jù)都需要消耗能量，大部分傳感器節(jié)點(diǎn)體積都很小，并且電池的能量密度也不高，導(dǎo)致節(jié)點(diǎn)所攜帶的電量有限，所以存在節(jié)點(diǎn)能量耗盡而停止工作，從而影響整個(gè)無線傳感器網(wǎng)絡(luò)的生命周期。目前很多學(xué)者把降低網(wǎng)絡(luò)的維護(hù)成本，延長(zhǎng)網(wǎng)絡(luò)生命周期，設(shè)計(jì)快速有效的充電方式，當(dāng)成保持網(wǎng)絡(luò)節(jié)點(diǎn)正常運(yùn)行的一項(xiàng)重要研究任務(wù)。文獻(xiàn)[1]在解決無線可充電傳感器網(wǎng)絡(luò)中使充電車充電服務(wù)吞吐量最大化的問題上，采用了K-means算法來解決。文獻(xiàn)[2]利用貪心思想有效地解決了無線可充電傳感器網(wǎng)絡(luò)中的充電車信息收集以及充電路徑優(yōu)化問題。文獻(xiàn)[3]為優(yōu)化無線可充電傳感器網(wǎng)絡(luò)節(jié)點(diǎn)在充電前的剩余能量以及充電車的充電路徑的問題上作出了卓越貢獻(xiàn)。文獻(xiàn)[4]在研究傳統(tǒng)網(wǎng)絡(luò)基礎(chǔ)上研究了基于動(dòng)態(tài)請(qǐng)求的無線可充電傳感器網(wǎng)絡(luò)，移動(dòng)充電車自身可傳遞和收集網(wǎng)絡(luò)節(jié)點(diǎn)的充電請(qǐng)求信息，并獨(dú)立完成充電任務(wù)。文獻(xiàn)[5]考慮所有無線可充電傳感器網(wǎng)絡(luò)節(jié)點(diǎn)不因能量耗盡而停止工作的前提下，把網(wǎng)絡(luò)節(jié)點(diǎn)的路由以及充電車的充電路徑結(jié)合在一起，研究了無線可充電傳感器網(wǎng)絡(luò)中的通信系統(tǒng)以及充電調(diào)度系統(tǒng)的總能耗最小化問題。文獻(xiàn)[6]研究了基于動(dòng)態(tài)請(qǐng)求式的無線可充電傳感器網(wǎng)絡(luò)中，存在一輛攜帶可接收無線信號(hào)裝置的充電車，具備實(shí)時(shí)的接收網(wǎng)絡(luò)節(jié)點(diǎn)的充電請(qǐng)求命令，且可以實(shí)時(shí)動(dòng)態(tài)的給出相應(yīng)的充電任務(wù)策略。文獻(xiàn)[7-8]通過無線認(rèn)證感知平臺(tái)(Wireless Identification and Sensing Platform,WISP)研究了無線可充電傳感器網(wǎng)絡(luò)的充電調(diào)度問題，在無線射頻識(shí)別信號(hào)范圍之內(nèi)，充電車可以為網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行充電服務(wù)。

本文研究的是無線可充電傳感器網(wǎng)絡(luò)在靜態(tài)模式下，以充電車電池所攜帶的能量和周期作為限制條件，使充電車電池能量利用率達(dá)到最大化，建立單輛充電車的充電模型，將能量利用率最大化問題轉(zhuǎn)換成最優(yōu)路徑的問題，提出基于精英策略的蛙跳算法對(duì)充電路徑進(jìn)行優(yōu)化，并利用Matlab仿真工具進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證算法的有效性。

1 問題描述

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

將無線可充電傳感器網(wǎng)絡(luò)看成1個(gè)二維平面[9]，布置1個(gè)固定的基站S，能夠收集網(wǎng)絡(luò)中各節(jié)點(diǎn)的信息，有n個(gè)隨機(jī)分布的傳感器節(jié)點(diǎn)，任意兩個(gè)節(jié)點(diǎn)之間的邊看成1個(gè)樹杈，1個(gè)節(jié)點(diǎn)可以生成多個(gè)樹杈，如圖1所示。

圖1 無線充電傳感器網(wǎng)絡(luò)示意圖

(1)

式中：Eelec為接收或發(fā)送單位數(shù)據(jù)消耗的能量；εfs為自由空間模型中功率放大器能耗參數(shù)；εmp為多路徑衰減模型中功率放大器能耗參數(shù)；d0為事先設(shè)定的兩種模型的傳輸距離的閾值。

接收k比特消耗的能量為

ERx=kEelec

(2)

則傳感器節(jié)點(diǎn)xi的能耗為

(3)

1.2 充電模型

在無線可充電傳感器網(wǎng)絡(luò)中，所有的網(wǎng)絡(luò)節(jié)點(diǎn)帶有一塊可充電電池作為能量接收裝置[12]，其能量有限，最大存儲(chǔ)量Gi，傳感器節(jié)點(diǎn)在信息來回傳遞過程中都會(huì)消耗能量，假設(shè)Emin為節(jié)點(diǎn)能量的臨界閾值，當(dāng)節(jié)點(diǎn)剩余能量值降低到Emin以下時(shí)，則會(huì)向基站S發(fā)出充電請(qǐng)求指令M，M={xi,tri,ER,pi,Gi}，其中xi是申請(qǐng)需求的節(jié)點(diǎn)，tri是節(jié)點(diǎn)發(fā)送充電請(qǐng)求的時(shí)刻，ER是節(jié)點(diǎn)的剩余能量，pi是節(jié)點(diǎn)能耗功率，Gi是節(jié)點(diǎn)能量的最大存儲(chǔ)量。當(dāng)基站收到節(jié)點(diǎn)充電申請(qǐng)時(shí)，會(huì)立即派遣一輛充電車去給節(jié)點(diǎn)充電，直到把節(jié)點(diǎn)能量充滿為止。若是有其他節(jié)點(diǎn)在當(dāng)前充電過程中發(fā)出充電請(qǐng)求，小車會(huì)自行收集信息，依次為下一節(jié)點(diǎn)充電，最后回到基站補(bǔ)充能量，此為一個(gè)充電調(diào)度。

在保證所有申請(qǐng)節(jié)點(diǎn)不停止工作的前提下，使充電車能量利用率最大化。能量利用率最大相當(dāng)于在行駛中充電車行駛路徑最短，建立一個(gè)單充電車為無線可充電傳感器網(wǎng)絡(luò)的充電模型如圖2所示。假設(shè)小車攜帶一個(gè)容量為Em的電池，可供自身行駛和為節(jié)點(diǎn)充電，小車可以為網(wǎng)絡(luò)中的節(jié)點(diǎn)依次充電，行駛速度為vc(勻速)，為節(jié)點(diǎn)充電的功率為pn，行駛過程中的消耗功率為pm，由于小車自身攜帶的能量是有限的，所以小車最大一次的充電返程時(shí)間看作一個(gè)充電周期為T。

圖2 充電模型

考慮在靜態(tài)模式下的傳感器網(wǎng)絡(luò)中，經(jīng)常出現(xiàn)部分傳感器節(jié)點(diǎn)由于未及時(shí)充電，而暫停工作，影響網(wǎng)絡(luò)的穩(wěn)定性。因此,本文考慮在基站收到部分節(jié)點(diǎn)充電申請(qǐng)，小車再為這些節(jié)點(diǎn)充電，在小車能量有限的情況下，給予所需節(jié)點(diǎn)最大化充電，同時(shí)選擇最優(yōu)路徑，使得充電車能量利用率最高。

1.3 最大化能量利用率公式化

將傳感器網(wǎng)絡(luò)看成一個(gè)賦予權(quán)值的無向樹圖Z=(X,Y)，充電車的電池總能量Em，靜態(tài)模式下，要使充電車的能量利用率最大化問題就是求解一條最優(yōu)的充電路徑Dc問題，小車所充過電的節(jié)點(diǎn)的集合為Vc(Vc∈V)，小車根據(jù)充電路線逐次為節(jié)點(diǎn)充電，最后回到基站補(bǔ)充能量，并使得充電車電池的能量利用率達(dá)到最大，且充電車給節(jié)點(diǎn)所充的總能量和小車行駛所需要的能量之和不能超過小車自身攜帶的電池能量,則該問題優(yōu)化目標(biāo)為

(4)

約束條件為

en(c)+Ec≤Em

(5)

式中：en(c)為充電過程中所有節(jié)點(diǎn)所充能量的總和；Ec為充電車在給節(jié)點(diǎn)充電過程中行駛所消耗的總能量。

eni=Gi-ER

(6)

式中：eni為單個(gè)節(jié)點(diǎn)需要充的能量。

(7)

(8)

一次充電往返過程的時(shí)間限制在周期T以內(nèi)

(9)

式中:eni/pn為充電車為節(jié)點(diǎn)xi充電的時(shí)間。

節(jié)點(diǎn)不會(huì)因?yàn)槟芰坑帽M而失效，所以有

tri≤ti≤tdi

(10)

式中：ti為小車開始給節(jié)點(diǎn)xi充電的時(shí)刻。

tdi節(jié)點(diǎn)在能量耗盡前小車為節(jié)點(diǎn)開始充電的最大時(shí)間

tdi=tri+ER/pi

(11)

所充電的節(jié)點(diǎn)集合應(yīng)該屬于整個(gè)傳感器節(jié)點(diǎn)的集合為

Vc?V

(12)

根據(jù)以上的約束條件來求出一條最優(yōu)路徑，而一般多約束條件求解充電車最優(yōu)充電路徑問題都是較難的旅行商問題(Travelling Salesman Problem，TSP)[13]。因此,本文基于精英策略的蛙跳算法求解出一條最優(yōu)的路徑。

2 算法概述

2.1 蛙跳算法

蛙跳算法[14-16](Shuffled Frog Leaping Algorithm，SFLA)是一種模擬青蛙覓食行為的過程，通過群體之間的相互合作與競(jìng)爭(zhēng)，來實(shí)現(xiàn)群體進(jìn)化的目的。以函數(shù)的最小值為例來說明SFLA的基本步驟，設(shè)群體青蛙的種群規(guī)模為M，并且在D維空間中第i個(gè)個(gè)體的坐標(biāo)假設(shè)為:xi=(xi1,xi2,…,xiD),計(jì)算個(gè)體的適應(yīng)值。接著從大到小依次排列，然后把整個(gè)種群劃分為G個(gè)局部子群，每個(gè)局部子群里面有N只青蛙，種群規(guī)模表示M=G×N,在降序排列的過程中，平均分配排列好的個(gè)體到G個(gè)局部子群中去，在指定的局部迭代數(shù)Ne內(nèi)完成搜索，若滿足全局最大迭代次數(shù)，則完成此次的搜索，輸出全局最優(yōu)值，否則將全部青蛙混合重新計(jì)算。

2.1 算法的改進(jìn)策略

在傳統(tǒng)SFLA中，局部子群的最差青蛙只會(huì)向局部子群最優(yōu)的青蛙學(xué)習(xí)，本文為了使最差的青蛙也向周圍的較好的青蛙學(xué)習(xí)，提高了搜索速度，并且在學(xué)習(xí)的過程中保證了自身的不退化。因此,本文引入了精英策略，即改進(jìn)的蛙跳算法(Accelerated Shuffled Frog Leaping Algorithm ，ACSFLA)，表示為

D(t)=η·rand()·[Xb(t)-Xw(t)]

(13)

式中：D(t)為更新的步長(zhǎng);η為變異算子;rand()為[0,1]之間的隨機(jī)數(shù)；Xb(t)為局部子群里最優(yōu)適應(yīng)解;

(14)

(15)

rmax為最差青蛙到本組較好青蛙的搜索距離；θ為(0°,360°)之間的隨機(jī)數(shù)。

針對(duì)SFLA進(jìn)化過程中，全局最優(yōu)的青蛙幾乎不進(jìn)化的問題，并且大量的實(shí)驗(yàn)表明在進(jìn)化過程中，全局最優(yōu)的地位會(huì)保持很多代，使算法的尋優(yōu)速度變慢，且易出現(xiàn)早熟的現(xiàn)象。因此,本文在進(jìn)化過程中，引入了Minkowski距離，使全局最優(yōu)的青蛙不僅向局部子群最優(yōu)青蛙學(xué)習(xí)，也向局部子群除了最差青蛙以外的其他青蛙學(xué)習(xí)，并且在學(xué)習(xí)過程中會(huì)向著多個(gè)方向，保證最優(yōu)青蛙的質(zhì)量，同時(shí)加快了尋優(yōu)速度:

Xg(t)=c·rand()·M(Xg(t),Xi(t))

(16)

式中：Xg(t)為全局最優(yōu)解;c為更新的權(quán)值,c為[0,1]的隨機(jī)數(shù)，是全局最優(yōu)青蛙向局部子群中其他青蛙和局部子群中最優(yōu)青蛙的學(xué)習(xí)因子；Xi(t)為局部子群內(nèi)最優(yōu)青蛙和局部子群內(nèi)除了最差青蛙以外的青蛙。

2.2 算法求解路徑流程

假設(shè)事先知道所有提出申請(qǐng)的網(wǎng)絡(luò)節(jié)點(diǎn)的位置、距離和能量等信息，讓小車在能量約束的條件下，陸續(xù)給需要的節(jié)點(diǎn)充電，最后能夠回到基站，且將充電車的行駛時(shí)間控制在T以內(nèi)，使得充電車的電池利用率最大化。通過改進(jìn)的蛙跳算法對(duì)充電路徑進(jìn)行優(yōu)化，其算法步驟如下。

(1) 初始化n個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)坐標(biāo)，計(jì)算各個(gè)節(jié)點(diǎn)之間的距離，生成距離矩陣。

(2) 設(shè)置算法參數(shù)，產(chǎn)生初始種群，將種群中的每個(gè)青蛙個(gè)體看成一條遍歷的路徑。

(3) 對(duì)于每個(gè)個(gè)體青蛙的好壞程度用適應(yīng)度函數(shù)值來評(píng)價(jià)，本文中將充電車的遍歷路徑長(zhǎng)度當(dāng)作適應(yīng)度函數(shù)值。

(4) 計(jì)算局部最優(yōu)值和最差值，調(diào)整最差值，將最差青蛙向其他種群最優(yōu)青蛙學(xué)習(xí)，根據(jù)式(14)～(15)對(duì)個(gè)體進(jìn)行更新。

(5) 局部達(dá)到預(yù)定的迭代次數(shù)之后，輸出局部最優(yōu)值，并與其他種群中的局部最優(yōu)值進(jìn)行對(duì)比。達(dá)到全局迭代次數(shù)之后，輸出最優(yōu)值，從而得到一條最優(yōu)的路徑。

算法程序流程如圖3所示。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

本文設(shè)計(jì)的無線可充電傳感器網(wǎng)絡(luò)規(guī)模為100 m×100 m，在此區(qū)域內(nèi)隨機(jī)分布40～200個(gè)傳感器節(jié)點(diǎn)，基站S位于網(wǎng)絡(luò)中心(50,50)。網(wǎng)絡(luò)中有一輛移動(dòng)充電車，充電車電池總能量為50 kJ，周期值為1 000 s，充電車的行駛速度為3 m/s，充電車的充電效率為10 J/s，小車行駛平均消耗的功率為5 J/s，每一個(gè)節(jié)點(diǎn)最大的能量值為300 J，節(jié)點(diǎn)的Emin=80 J，發(fā)送數(shù)據(jù)能量消耗100 nJ/bit，接受數(shù)據(jù)能量消耗100 nJ/bit。

圖3 程序流程圖

根據(jù)以上設(shè)置的參數(shù)，進(jìn)行仿真實(shí)驗(yàn)。仿真實(shí)驗(yàn)在win10系統(tǒng)、intel酷睿系列的CPU;8 GB內(nèi)存、500 GB硬盤的電腦上的MATLAB 2014b下仿真，以SFLA和ACSFLA作對(duì)比。除此之外，再與蟻群算法[17](Ant Colony Optimization, ACO)比較。ACO是一種模仿螞蟻在覓食過程中的行為，其算法思想為在充電車選擇充電節(jié)點(diǎn)的過程中，任意選擇一條路徑并留下信息素，信息素的濃度越高，螞蟻選擇這條路徑概率也越大，如此反復(fù)從而選擇出最優(yōu)的路徑，是較早的路徑優(yōu)化智能算法。

3.2 性能指標(biāo)

針對(duì)ACSFLA，本文采用兩個(gè)標(biāo)準(zhǔn)來驗(yàn)證算法的有效性，其中一個(gè)為本文的優(yōu)化目標(biāo)，另外一個(gè)為能量利用率。

在一次充電過程中，充電車對(duì)節(jié)點(diǎn)充電的總能量與充電過程中所消耗的總能量之比即能量利率用為

Δ=en(c)/[Ec+en(c)]

(17)

3.3 仿真結(jié)果分析

通過對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的點(diǎn)位隨機(jī)分布，對(duì)40～200節(jié)點(diǎn)區(qū)域進(jìn)行多次仿真實(shí)驗(yàn)。為了讓求解的最優(yōu)值更加有效性，取多組優(yōu)化后最優(yōu)值的平均值。以下為仿真結(jié)果分析。

圖4為節(jié)點(diǎn)數(shù)的40～200時(shí)SFLA,ACO和ACSFLA優(yōu)化后的路徑距離曲線圖， 從曲線變化上面來看，在節(jié)點(diǎn)數(shù)量少的時(shí)候，SFLA和ACSFLA表現(xiàn)都很優(yōu)越，但在節(jié)點(diǎn)數(shù)增大，明顯看出SFLA所求得結(jié)果并不是很理想，當(dāng)節(jié)點(diǎn)數(shù)增加到140個(gè)之后，SFLA求解的充電路徑最長(zhǎng)，而ACSFLA求解的路徑一直都比其他兩種要短。

圖4 優(yōu)化后充電路徑曲線圖

圖5為SFLA與ACSFLA在節(jié)點(diǎn)數(shù)為40～200時(shí)充電車能量利用率的變化曲線。從圖中可以直觀看出，隨著傳感器節(jié)點(diǎn)的增加，充電車能夠?yàn)楦嗟墓?jié)點(diǎn)提供充電服務(wù)。因此,充電車能量利用率也不斷的變高。

圖5 能量利用率變化曲線

在節(jié)點(diǎn)數(shù)很少時(shí)，ACO優(yōu)化后的充電車的利用率最低，隨著節(jié)點(diǎn)數(shù)量增加，曲線變化逐漸趨近于ACSFLA。120節(jié)點(diǎn)和200節(jié)點(diǎn)3種算法的優(yōu)化后的能量利用率比較見表1。在節(jié)點(diǎn)數(shù)增加到120時(shí)，ACSFLA相較于SFLA能量利用率提升了3.1%，而ACO優(yōu)化結(jié)果依然不理想。當(dāng)節(jié)點(diǎn)數(shù)增加到200時(shí)，ACSFLA相較于ACO的能量利用率提高了7.1%，而此時(shí)SFLA能量利用率最低，這是由于SFLA后期時(shí)，陷入了局部最優(yōu)，導(dǎo)致尋優(yōu)的精度不高。而ACSFLA優(yōu)化后的能量利用率始終比其他兩種算法高。綜上所述，驗(yàn)證了本文改進(jìn)算法的有效性。

表1 3種算法優(yōu)化后的能量利用率比較

4 結(jié) 語

本文研究了無線可充電傳感器網(wǎng)絡(luò)中充電調(diào)度問題，針對(duì)實(shí)際情況，考慮到充電車攜帶的能量有限，在研究過程中將充電車的電池能量利用率轉(zhuǎn)換成求解最短路徑，利用ACSFLA對(duì)其進(jìn)行優(yōu)化。在小規(guī)模網(wǎng)絡(luò)中，用SFLA,ACO和ACSFLA進(jìn)行仿真，結(jié)果表明，通過ACSFLA得到的路徑最短，能量利用率最高。