無(wú)線(xiàn)可充電傳感器網(wǎng)絡(luò)能量源部署方法研究

於晨陽(yáng) 謝志軍

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

0 引 言

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

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

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

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

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

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

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

1.2 充電模型

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

(1)

(2)

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

(3)

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

(4)

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

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

(5)

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

1.3 充電效用模型

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

(6)

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

(7)

1.4 問(wèn)題定義

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

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

最大化:U(S)

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

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

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

2.1 烏鴉搜索算法

(8)

(9)

2.2 HCSCSA

圖2 飛行距離小于1時(shí)烏鴉的飛行路線(xiàn)

圖3 飛行距離大于1時(shí)烏鴉的飛行路線(xiàn)

(10)

(11)

(12)

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

(13)

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

針對(duì)本文的能量源部署位置優(yōu)化問(wèn)題,定義烏鴉個(gè)體Qi為N個(gè)能量源的坐標(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ò)的充電效用。具體的部署過(guò)程如下:

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

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

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

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

4.fori=1 toCmaxdo

5.forj=1 tovdo

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

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

8.end

9.else

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

11.end

12.end

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

14.end

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

3 實(shí)驗(yàn)仿真

如圖4所示為小規(guī)模部署場(chǎng)景下的一個(gè)可視化實(shí)例,其中:倒三角為耗電功率為0.000 1的傳感器節(jié)點(diǎn);星號(hào)為耗電功率為0.000 2的節(jié)點(diǎn);圓點(diǎn)為能量源的部署位置。可以看出HCSCSA搜索能力強(qiáng)于其他算法,能夠找到具有更優(yōu)充電效用的部署位置。

(a) CUCKOO (b) MFO

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

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

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

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

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

圖5 小規(guī)模場(chǎng)景下迭代曲線(xiàn)

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

圖6 大規(guī)模場(chǎng)景下迭代曲線(xiàn)

4 結(jié) 語(yǔ)

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