於晨陽 謝志軍

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

0 引 言

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

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

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

1 系統(tǒng)建模與問題定義

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

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

圖1 網(wǎng)絡(luò)模型

1.2 充電模型

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

(1)

(2)

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

(3)

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

(4)

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

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

(5)

式中:N為能量源個數(shù)。

1.3 充電效用模型

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

(6)

式中:u(si)為傳感器si的充電效用;λ為線性相關(guān)的常數(shù)。將單個傳感器充電效用擴展到整個網(wǎng)絡(luò),全網(wǎng)總的充電效用為:

(7)

1.4 問題定義

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

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

最大化:U(S)

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

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

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

2.1 烏鴉搜索算法

(8)

(9)

2.2 HCSCSA

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

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

(10)

(11)

(12)

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

(13)

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

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

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

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

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

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

4.fori=1 toCmaxdo

5.forj=1 tovdo

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

根據(jù)式(10)第一項等式更新能量源位置,根據(jù)式(11)、式(12)對當(dāng)前能量源部署位置和最佳部署位置執(zhí)行水平交叉,再次計算U(S)保留更好位置,根據(jù)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所示為小規(guī)模部署場景下的一個可視化實例,其中:倒三角為耗電功率為0.000 1的傳感器節(jié)點;星號為耗電功率為0.000 2的節(jié)點;圓點為能量源的部署位置?？梢钥闯鯤CSCSA搜索能力強于其他算法,能夠找到具有更優(yōu)充電效用的部署位置。

(a) CUCKOO (b) MFO

(c) CSA (d) HCSCSA圖4 可視化實例

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

表1 小規(guī)模場景下充電效用

表2 大規(guī)模場景下充電效用

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

圖5 小規(guī)模場景下迭代曲線

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

圖6 大規(guī)模場景下迭代曲線

4 結(jié) 語

本文研究最大化充電效用能量源部署問題,給定能量源數(shù)量、傳感器坐標(biāo)和傳感器的耗電功率,在監(jiān)測區(qū)域內(nèi)尋找能量源的部署位置最大化充電效用,提出一種混合烏鴉搜索算法和交叉算法的新啟發(fā)式算法HCSCSA。在小規(guī)模和大規(guī)模部署場景下HCSCSA的充電效用均優(yōu)于其他啟發(fā)式算法。