無線可充電傳感器網絡充電路徑優化

2018-09-04 11:32:54俞立春呂紅芳李俊甫

上海電機學院學報 2018年4期

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

(上海電機學院電氣學院，上海 201306)

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

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

1 問題描述

1.1 網絡模型

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

圖1 無線充電傳感器網絡示意圖

(1)

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

接收k比特消耗的能量為

ERx=kEelec

(2)

則傳感器節點xi的能耗為

(3)

1.2 充電模型

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

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

圖2 充電模型

考慮在靜態模式下的傳感器網絡中，經常出現部分傳感器節點由于未及時充電，而暫停工作，影響網絡的穩定性。因此,本文考慮在基站收到部分節點充電申請，小車再為這些節點充電，在小車能量有限的情況下，給予所需節點最大化充電，同時選擇最優路徑，使得充電車能量利用率最高。

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

將傳感器網絡看成一個賦予權值的無向樹圖Z=(X,Y)，充電車的電池總能量Em，靜態模式下，要使充電車的能量利用率最大化問題就是求解一條最優的充電路徑Dc問題，小車所充過電的節點的集合為Vc(Vc∈V)，小車根據充電路線逐次為節點充電，最后回到基站補充能量，并使得充電車電池的能量利用率達到最大，且充電車給節點所充的總能量和小車行駛所需要的能量之和不能超過小車自身攜帶的電池能量,則該問題優化目標為

(4)

約束條件為

en(c)+Ec≤Em

(5)

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

eni=Gi-ER

(6)

式中：eni為單個節點需要充的能量。

(7)

(8)

一次充電往返過程的時間限制在周期T以內

(9)

式中:eni/pn為充電車為節點xi充電的時間。

節點不會因為能量用盡而失效，所以有

tri≤ti≤tdi

(10)

式中：ti為小車開始給節點xi充電的時刻。

tdi節點在能量耗盡前小車為節點開始充電的最大時間

tdi=tri+ER/pi

(11)

所充電的節點集合應該屬于整個傳感器節點的集合為

Vc?V

(12)

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

2 算法概述

2.1 蛙跳算法

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

2.1 算法的改進策略

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

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

(13)

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

(14)

(15)

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

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

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

(16)

式中：Xg(t)為全局最優解;c為更新的權值,c為[0,1]的隨機數，是全局最優青蛙向局部子群中其他青蛙和局部子群中最優青蛙的學習因子；Xi(t)為局部子群內最優青蛙和局部子群內除了最差青蛙以外的青蛙。

2.2 算法求解路徑流程

假設事先知道所有提出申請的網絡節點的位置、距離和能量等信息，讓小車在能量約束的條件下，陸續給需要的節點充電，最后能夠回到基站，且將充電車的行駛時間控制在T以內，使得充電車的電池利用率最大化。通過改進的蛙跳算法對充電路徑進行優化，其算法步驟如下。

(1) 初始化n個網絡節點坐標，計算各個節點之間的距離，生成距離矩陣。

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

(3) 對于每個個體青蛙的好壞程度用適應度函數值來評價，本文中將充電車的遍歷路徑長度當作適應度函數值。

(4) 計算局部最優值和最差值，調整最差值，將最差青蛙向其他種群最優青蛙學習，根據式(14)～(15)對個體進行更新。

(5) 局部達到預定的迭代次數之后，輸出局部最優值，并與其他種群中的局部最優值進行對比。達到全局迭代次數之后，輸出最優值，從而得到一條最優的路徑。

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

3 實驗結果與分析

3.1 實驗環境

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

圖3 程序流程圖

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

3.2 性能指標

針對ACSFLA，本文采用兩個標準來驗證算法的有效性，其中一個為本文的優化目標，另外一個為能量利用率。

在一次充電過程中，充電車對節點充電的總能量與充電過程中所消耗的總能量之比即能量利率用為

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

(17)

3.3 仿真結果分析

通過對網絡節點的點位隨機分布，對40～200節點區域進行多次仿真實驗。為了讓求解的最優值更加有效性，取多組優化后最優值的平均值。以下為仿真結果分析。

圖4為節點數的40～200時SFLA,ACO和ACSFLA優化后的路徑距離曲線圖，從曲線變化上面來看，在節點數量少的時候，SFLA和ACSFLA表現都很優越，但在節點數增大，明顯看出SFLA所求得結果并不是很理想，當節點數增加到140個之后，SFLA求解的充電路徑最長，而ACSFLA求解的路徑一直都比其他兩種要短。

圖4 優化后充電路徑曲線圖

圖5為SFLA與ACSFLA在節點數為40～200時充電車能量利用率的變化曲線。從圖中可以直觀看出，隨著傳感器節點的增加，充電車能夠為更多的節點提供充電服務。因此,充電車能量利用率也不斷的變高。

圖5 能量利用率變化曲線

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