無線可充電傳感器網絡能量源部署方法研究

2023-06-07 09:43:00於晨陽謝志軍

計算機應用與軟件 2023年5期

於晨陽謝志軍

(寧波大學信息科學與工程學院浙江寧波 315211)

0 引言

無線傳感器網絡[1](Wireless Sensor Network,WSN)已廣泛應用于多個領域,例如智慧城市、工業系統、環境監測等[2-5]。由于大多數現有的傳感器網絡均由電池供電,電池能量有限,更換節點的電池既昂貴又困難,特別是在人無法進入的環境中。由此可見,無線傳感器網絡中能量問題是亟待解決的關鍵問題。由于近年來無線能量傳輸(Wireless Power Transmission,WPT)[6]技術的發展,提高了能量傳輸質量,可以利用WPT技術為傳感器節點補充能量。這引起了研究者們對無線可充電傳感器網絡(Wireless Rechargeable Sensor Network,WRSN)的廣泛關注和深入研究。

無線可充電傳感器網絡由能量源和可充電傳感器節點組成,使用靜態或者移動的能量源,利用WPT技術為可充電傳感器節點補充能量從而延長網絡壽命。由于靜態部署能量源相比于移動能量源調度更為可靠和穩定,不少研究人員對此進行了研究。Ding等[7]研究最小化能量源的部署成本問題,他們分別考慮全向充電和定向充電兩種場景,給定一組用于部署能量源的候選位置,每個位置部署成本不同,在滿足網絡充電效用的前提下最小化能量源的部署成本,首先證明了該部署問題是NP-Hard,然后提出了一種基于貪心算法的能量源部署方法。Zhang等[8]研究能量源放置和功率分配問題,給定一組放置能量源的候選位置,根據功率預算,找到能量源放置和相應的功率分配以最大化充電質量。He等[9]研究能量源的覆蓋問題,將能量源部署在等邊三角形的頂點上實現了監測區域全覆蓋,并有效減少了能量源的部署數量。Yu等[10]研究了無線能量源的連接問題。給定固定數量的定向無線能量源和候選位置,在無線能量源的連接性約束下確定每個充電器的放置位置和定向角度,以使整體充電效用最大化。文獻[7-8,10]中的能量源部署研究中,能量源的部署位置都是從給定的一組候選位置中選取的,而實際中候選位置未知。文獻[9]采用部署能量源覆蓋整個監測區域的方式,然而該方式成本要求太高并且區域中節點數量有限并不需要覆蓋所有區域。區別于上述研究,本文研究候選位置未知情況下,在監測區域內尋找能量源的部署位置,旨在最大化整個網絡的充電效用,將其定義為最大化充電效用能量源部署優化問題。

本文首先建模該最大化充電效用充電器部署問題,為解決該問題提供理論基礎。該問題是一個非線性且非凸的優化問題,而基于群體的啟發式算法能夠有效地解決此類問題。存在一些研究證明[11-13]烏鴉搜索算法在許多優化領域比其他算法例如粒子群、蟻群算法等具有更好的性能。為了獲得更優的充電器部署位置,本文對烏鴉搜索算法進行改進,提出一種混合烏鴉搜索算法和交叉算法的啟發式部署方法HCSCSA(Hybrid Crossover Search Crow Search Algorithm)。HCSCSA改進了烏鴉搜索算法的隨機跟隨策略,并在烏鴉搜索算法的基礎上引入水平交叉[14]選擇兩個不同個體在所有維度上進行算術交叉增強全局搜索能力減少無法搜索到盲點,引入垂直交叉所有個體隨機選擇兩個維度進行算術交叉增強跳出局部最優的能力。最后,通過仿真實驗證明本文算法優于其他啟發式算法。

1 系統建模與問題定義

1.1 網絡模型

集合S={s1,s2,…,sm}為在長度為L×L的2維監測區域內放置的用于感知數據或監測特定事件的m個靜止的可充電傳感器節點。E={e1,e2,…,em}為每個傳感器的耗電功率。將監測區域長度作為x軸,寬度作為y軸,傳感器si的坐標可以表示為(xi,yi)。能量源可以為其充電半徑范圍內的傳感器提供能量,部署后位置無法改變。網絡模型如圖1所示。

圖1 網絡模型

1.2 充電模型

在本文中,使用基于Friis公式[15-16]改進的充電模型如下:

(1)

(2)

式中:pr為傳感器端接收功率也就是充電功率;pt為能量源端發射功率;Gs為發送天線增益;Gr為接收天線增益;λ為波長;d為傳感器節點與能量源之間的歐氏距離,其中傳感器的坐標為(xi,yi),能量源坐標為(Xj,Yj);β為短距離傳感的調節參數避免距離為零時充電功率無限大。可將式(1)簡化為如下形式:

(3)

式中:a代表式(1)中其他參數的影響。當d太大時,充電功率幾乎為0,式(3)可以改進為以下公式:

(4)

式中:R為能量源的充電半徑。

能量源充電范圍內可以存在多個傳感器節點,傳感器節點可以被多個能量源覆蓋可以獲得來自多個能量源的能量,傳感器si其總充電功率可以表示如下:

(5)

式中:N為能量源個數。

1.3 充電效用模型

由于硬件限制或者實際充電需求,當傳感器使用恒定功率充電時,當充電功率大于其耗電功率時多余的能量無法存儲,相應的充電效用也不會增加,因此使用如下線性有界模型作為充電效用模型[10]:

(6)

式中:u(si)為傳感器si的充電效用;λ為線性相關的常數。將單個傳感器充電效用擴展到整個網絡,全網總的充電效用為:

(7)

1.4 問題定義

本文研究最大化充電效用能量源部署問題,目標是優化能量源的部署位置,提高網絡的充電效用。給定能量源數量N、傳感器坐標(xi,yi)和耗電功率E,最大化充電效用U(S),可以建模為如下優化問題:

給定:N,E,S,(xi,yi),i=1,2,…,m

最大化:U(S)

變量:(Xj,Yj),j=1,2,…,N

該優化問題的解空間無限,是一個非線性和非凸的優化問題。本文提出一種混合烏鴉搜索算法和交叉算法的新啟發式算法HCSCSA解決該問題。

2 基于HCSCSA的能量源部署方法

2.1 烏鴉搜索算法

(8)

(9)

2.2 HCSCSA

圖2 飛行距離小于1時烏鴉的飛行路線

圖3 飛行距離大于1時烏鴉的飛行路線

(10)

(11)

(12)

接下來進行垂直交叉,垂直交叉是烏鴉個體本身在不同位置維度上進行算術交叉,垂直交叉能夠避免在搜索過程中陷入局部最優。選擇烏鴉i根據式(13)進行垂直交叉。

(13)

HCSCSA引入了水平交叉和垂直交叉操作故對其時間復雜度分析,標準烏鴉搜索算法的復雜度為O(Cmax·v·w),水平交叉的操作復雜度為O(v·w),垂直交叉的操作復雜度為O(v),適應度計算的操作復雜度為O(v·w)。由此可知,引入的水平交叉和垂直交叉后,算法的時間復雜度還是O(Cmax·v·w),沒有增加額外的計算成本。

針對本文的能量源部署位置優化問題,定義烏鴉個體Qi為N個能量源的坐標,即Q=(X1,Y1,X2,Y2,…,XN,YN),Qi的適應度函數為網絡的充電效用fitness=U(S)。根據HCSCSA的優化策略尋找能量源的部署位置,最大化網絡的充電效用。具體的部署過程如下:

輸入:能量源數量N,節點耗電功率E,傳感器坐標(xi,yi),i=1,2,…,m。

輸出:充電效用U(S),能量源位置(X1,Y1,X2,Y2,…,XN,YN)。

2.為種群大小為v的每只烏鴉在監測區域中隨機初始化能量源位置。

3.根據初始能量源位置計算充電效用U(S),使能量源的最佳部署位置為初始位置。

4.fori=1 toCmaxdo

5.forj=1 tovdo

6.每只烏鴉根據式(10)更新能量源位置

根據式(10)第一項等式更新能量源位置,根據式(11)、式(12)對當前能量源部署位置和最佳部署位置執行水平交叉,再次計算U(S)保留更好位置,根據Ph判斷是否進行垂直交叉,如滿足概率按照式(13)對能量源位置進行垂直交叉,計算U(S)保留更好位置,否則不進行垂直交叉。

8.end

9.else

10.隨機生成一個能量源部署位置并計算充電效用U(S)

11.end

12.end

13.更新個體、群體最佳能量源部署位置

14.end

15.outputU(S),(X1,Y1,X2,Y2,…,XN,YN)

3 實驗仿真

如圖4所示為小規模部署場景下的一個可視化實例,其中:倒三角為耗電功率為0.000 1的傳感器節點;星號為耗電功率為0.000 2的節點;圓點為能量源的部署位置。可以看出HCSCSA搜索能力強于其他算法,能夠找到具有更優充電效用的部署位置。

(a) CUCKOO (b) MFO

表1、表2分別為小規模場景下和大規模場景下的充電效用結果,兩個場景下HCSCSA的最差值、平均值、最優值皆高于其他算法表明該算法具有更優的性能。

表1 小規模場景下充電效用

表2 大規模場景下充電效用

圖5所示為小規模場景下的平均充電效用迭代曲線,可以看出隨著迭代進行HCSCSA的平均充電效用始終高于其他啟發式算法,展現出其極強的尋優能力。迭代到16次時,HCSCSA已實現收斂,表明HCSCSA具備良好的收斂能力。

圖5 小規模場景下迭代曲線

圖6所示為大規模場景下的平均充電效用迭代曲線,大規模場景下由于搜索空間的擴大和傳感器節點個數的增多算法極易陷入局部最優如CUCKOO算法所示,而CSA本身具備良好的跳出局部最優的能力再加上HCSCSA的增強使其具有極強的跳出局部最優的能力,如迭代50次至60次所示。HCSCSA在小規模場景和大規模場景下的充電效用均優于其他啟發式算法,不僅顯示了其尋優能力還表現出極強的適應性。