基于分數(shù)階達爾文粒子群的不等間距節(jié)點部署優(yōu)化算法

張 利 峰

(金陵科技學(xué)院計算機工程學(xué)院 江蘇 南京 211169)(金陵科技學(xué)院數(shù)據(jù)科學(xué)與智慧軟件江蘇省重點實驗室 江蘇 南京 211169)

0 引 言

隨著無線傳感技術(shù)的快速發(fā)展，無線傳感網(wǎng)絡(luò)WSN(Wireless Sensor Network)被廣泛應(yīng)用于環(huán)境監(jiān)測、森林防火和農(nóng)業(yè)生產(chǎn)等領(lǐng)域中，節(jié)點部署是無線傳感網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一。但在監(jiān)測區(qū)內(nèi)，節(jié)點的隨機部署往往帶來節(jié)點分布的不均勻等問題[1]。針對該問題，學(xué)者們提出了不同的節(jié)點部署算法。文獻[2]量化了帶狀傳感器網(wǎng)絡(luò)簇內(nèi)節(jié)點數(shù)目關(guān)系，并設(shè)計相應(yīng)的路由協(xié)議，提出了一種非均勻節(jié)點部署策略。文獻[3]提出了一種分布式無線感知網(wǎng)絡(luò)節(jié)點部署算法，提高了分布式無線感知網(wǎng)絡(luò)對目標(biāo)區(qū)域內(nèi)重點區(qū)域的覆蓋率。文獻[4]對網(wǎng)絡(luò)進行區(qū)域劃分，通過分區(qū)估算區(qū)域節(jié)點密度，有針對性的部署節(jié)點。文獻[5]結(jié)合網(wǎng)絡(luò)覆蓋率、節(jié)點數(shù)和節(jié)點間最小距離建立目標(biāo)函數(shù)，提出了一種基于Harmony搜索算法的節(jié)點部署方案。文獻[6]提出了一種基于能耗均衡的分區(qū)節(jié)點部署算法，利用分區(qū)域的節(jié)點移動,減少節(jié)點移動距離,降低移動能耗,提高算法收斂速度。在利用智能優(yōu)化算法進行節(jié)點部署方面也有較深入的研究，文獻[7-11]利用細菌覓食、粒子群、果蠅、狼群、人工蜂群等不同智能優(yōu)化算法，對節(jié)點部署進行最優(yōu)位置尋解。

根據(jù)上面的分析可知，現(xiàn)有的拓撲結(jié)構(gòu)大都是隨機部署，并且都存在能耗不均衡和生命周期短暫等問題。因此，為了解決能耗均衡，節(jié)省節(jié)點能量，本文結(jié)合星型拓撲和鏈?zhǔn)酵負浣Y(jié)構(gòu)的優(yōu)點，利用提出粒子群優(yōu)化的不等間距節(jié)點部署優(yōu)化算法。

1 不等間距拓撲結(jié)構(gòu)及能耗模型

1.1 不等間距拓撲結(jié)構(gòu)

對于小型監(jiān)測區(qū)域，可以簡化部署模型，直接采用不等間距的方法進行節(jié)點部署，此種拓撲結(jié)構(gòu)結(jié)合星型拓撲結(jié)構(gòu)和線型拓撲結(jié)構(gòu)的特點，具有鮮明的層次結(jié)構(gòu)，該部署拓撲結(jié)構(gòu)如圖1所示。

圖1 無線網(wǎng)絡(luò)不等間距拓撲結(jié)構(gòu)

設(shè)l×n個傳感器節(jié)點根據(jù)理論計算的節(jié)點位置被非均勻的部署半徑為r的二維檢測區(qū)域中,一個匯聚節(jié)點(Sink節(jié)點)位于監(jiān)測區(qū)域中央，與傳感器節(jié)點以不等間距方式共同形成多鏈?zhǔn)浇Y(jié)構(gòu)，越靠近匯聚節(jié)點的位置，傳感器節(jié)點之間的間距越小。其中半徑等于r的某一條鏈的監(jiān)測區(qū)域如圖2所示。

圖2 單鏈監(jiān)測區(qū)域示意圖

圖2中，di表示的是節(jié)點i+1和節(jié)點i間的間距，ti表示在節(jié)點i功率最小即Pmin下的覆蓋半徑，di=ti+ti+1。

1.2 不等間距拓撲結(jié)構(gòu)能耗模型

本文無線傳感模型的能耗主要由傳感節(jié)點產(chǎn)生，包括數(shù)據(jù)的接收、發(fā)送，以及休眠轉(zhuǎn)收發(fā)時的啟動能耗。因此，本文選擇如圖3所示的無線通信模型，考慮發(fā)送電路、接收電路、放大器以及傳輸?shù)臄?shù)據(jù)字節(jié)數(shù)，一個無線射頻收發(fā)器將k比特數(shù)據(jù)包發(fā)送到距離為d的另外一個無線收發(fā)器。

圖3 無線通信模型

發(fā)送能耗主要由信號發(fā)射電路能耗和放大器電路能耗這兩部分組成，因此，發(fā)送k比特數(shù)據(jù)到距離為d的節(jié)點上的能耗，表示為：

(1)

式中：Etx表示接收單位比特數(shù)據(jù)所需能耗；εamp1、εamp2表示所采用傳輸信道模型中的參數(shù)；β表示路徑損耗常數(shù)，與傳播環(huán)境有關(guān)。當(dāng)d

ERx(k,d)=Erx×d

(2)

對于任何一個節(jié)點i，其發(fā)送kbit數(shù)據(jù)包能耗:

E(i)=ETx(i)+ERx(i)

(3)

假設(shè)節(jié)點i需要接發(fā)數(shù)據(jù)，每條鏈上共有n跳節(jié)點，那么節(jié)點i需(n-i+1)次數(shù)據(jù)發(fā)送和(n-i)次數(shù)據(jù)接收，因此節(jié)點i的能耗如下：

(4)

將上式統(tǒng)一表示為：

Erx·k·(n-i)

(5)

根據(jù)圖1，為了確保Sink節(jié)點為中心的傳感網(wǎng)絡(luò)能耗均勻，滿足以下條件：

E(i)=E(i+1)

(6)

假設(shè)每個節(jié)點的初始能量為Einit，那么整個網(wǎng)絡(luò)的生命周期為：

(7)

假設(shè)Etx=Erx=E，結(jié)合式(5)和式(6)可得：

2E+εamp·diβ=(2E+εamp·diβ)·(n-i+1)+

εamp·diβ

(8)

根據(jù)圖2，若每條鏈上一共有n個節(jié)點，每個節(jié)點在Pmin下的覆蓋范圍為2ti，因此在整條鏈路上應(yīng)該滿足：

(9)

(10)

本文借助粒子群優(yōu)化算法的尋優(yōu)優(yōu)勢來計算不等間距拓撲結(jié)構(gòu)下最優(yōu)的節(jié)點間距di和鏈路節(jié)點數(shù)n以完成節(jié)點的有效部署。將最大網(wǎng)絡(luò)生命周期作為目標(biāo)函數(shù)即maxT，將式(8)-式(10)作為約束條件，得到無線網(wǎng)絡(luò)最大生命周期為優(yōu)化目標(biāo)的數(shù)學(xué)模型：

maxT

(11)

s.t. 2E+εamp·diβ=(2E+εamp·diβ)·(n-i+

1)+εamp·diβ

2 粒子群優(yōu)化算法及其改進

粒子群優(yōu)化算法PSO(Partical Swarm Optimization)是一種群體智能全局尋優(yōu)的算法[12]，廣泛應(yīng)用于優(yōu)化組合、和多目標(biāo)尋優(yōu)[13-15],與其他智能優(yōu)化算法一樣，粒子群優(yōu)化算法也易陷入局部最優(yōu)、存在搜索精度不高、收斂慢等問題。針對于此，國內(nèi)外學(xué)者提出了多種改進算法。文獻[16]將達爾文進化理論引入粒子群優(yōu)化算法中，提出了一種達爾文粒子群優(yōu)化算法DPSO(Darwinian Particle Swarm Optimization)。文獻[17]提出了分數(shù)階粒子優(yōu)化算法FOPSO(Fractional Order Particle Swarm Optimization)。學(xué)者Micael提出了分數(shù)階達爾文粒子群算法FODPSO，實驗表明該算法利用分數(shù)階次α來控制計算精度與收斂速度，但過度依賴α的調(diào)解功能，容易引起局部最優(yōu)[18]。

2.1 粒子群算法

在一個M維目標(biāo)空間中，Nnum個粒子組成群落，每個粒子的速度和位置更新公式：

(12)

(13)

第i個粒子位置向量為Xi=(xi1,xi2,…,xiD)，速度向量為Vi=(vi1,vi2,…,viD)，第i個粒子經(jīng)歷過的位置中最優(yōu)位置Wi=(wi1,wi2,…,wiD)，整個粒子群最優(yōu)位置Wg=(wg1,wg2,…,wgD)。式(12)中ω表示慣性系數(shù)，c1、c2為加速系數(shù)，R1d、R2d為[0,1]間的隨機數(shù)，wid表示粒子個體最優(yōu)值，wgd表示粒子群整體最優(yōu)值。

DPSO將自然選擇理論引入算法中，設(shè)置粒子搜索計數(shù)器SC用以追蹤粒子群適應(yīng)值沒有改變次數(shù)。創(chuàng)建新粒子群時，粒子群內(nèi)所有搜索計數(shù)器SC=0，在粒子群適應(yīng)度沒有提高時，其中的粒子被刪除后，該粒子群的搜索計數(shù)器不置為0，而是根據(jù)以下式設(shè)置為與最大計數(shù)值SCmax相近的值：

(14)

式中：Nkill表示粒子群適應(yīng)值沒變化期間被刪除的粒子數(shù)。若一個粒子群中所有粒子被刪除，并且當(dāng)前粒子群數(shù)沒有超過種群設(shè)置數(shù)，則創(chuàng)建新粒子群的概率為：

p=r/Nnum

(15)

式中：r為[0,1]間隨機數(shù)，Nnum表示種群粒子數(shù)。文獻[18]給出了分數(shù)階次α調(diào)整公式：

(16)

通過大量實驗可知分數(shù)階次α在[0.5,0.8]之間時，F(xiàn)ODPSO算法可取的較快的收斂速度。但通過式(16)可以看出：隨著迭代次數(shù)的加大，分數(shù)階次α?xí)€性減小，這勢必會使粒子群陷入局部最優(yōu)和低速收斂。本文通過以下兩小節(jié)對此問題進行改進。

2.2 基于進化信息調(diào)整分數(shù)階次α

(17)

(18)

(19)

(20)

(21)

基于粒子進化因子fev∈[0,1]，利用高斯圖函數(shù)得出分數(shù)階次α的調(diào)整公式：

(22)

通過式(22)可知，分數(shù)階次α的調(diào)整不再依賴迭代次數(shù)，而是依據(jù)粒子自身的進化信息，這可避免算法因分數(shù)階次α線性減小而引起的局部最優(yōu)和收斂緩慢。

設(shè)慣性系數(shù)ω為1，根據(jù)分數(shù)階微分方程的格林瓦德-列特尼科夫(G-L)定義，粒子速度更新策略變?yōu)椋?/p>

(23)

粒子的位置更新依據(jù)式(13)進行，其中加速系數(shù)滿足3≤c1+c2≤4。

2.3 基于Levy飛行特征的局部最優(yōu)

為了克服尋優(yōu)算法早熟收斂，及時跳出局部最優(yōu)，將Levy飛行特性引入改進的分數(shù)階達爾文粒子群算法中，利用Levy飛行特性擴展搜索空間，根據(jù)局部最優(yōu)概率因子popt對算法取得的局部最優(yōu)wg進行位置擾動。

定義局部最優(yōu)概率因子popt：

(24)

wgd=wgd(1+levy(ξ)tanh(fev))

(25)

式中，Levy(ξ)是隨機搜索路徑，步長的大小通過levy分布隨機數(shù)產(chǎn)生且1≤ξ≤3，0≤fev≤1，0≤tanh(·)≤1。

3 仿真實驗與分析

3.1 節(jié)點部署尋優(yōu)流程

將無線網(wǎng)絡(luò)最大生命周期目標(biāo)函數(shù)作為改進分數(shù)階達爾文粒子群算法的目標(biāo)函數(shù)，搜索最優(yōu)的節(jié)點間距di和鏈路節(jié)點數(shù)n以部署網(wǎng)絡(luò)，尋優(yōu)流程如下：

Step1初始化粒子群，隨機生成粒子速度Vi和位置Xi，確定種群個數(shù)Nnum，目標(biāo)空間維數(shù)M，最大迭代次數(shù)Tmax，加速系數(shù)c1、c2等參數(shù)。

Step2對粒子群中每個粒子進行適應(yīng)度評估，將粒子個體的最優(yōu)值wid設(shè)為當(dāng)前位置，全局最優(yōu)值wgd設(shè)為群體最優(yōu)粒子位置。

Step3開始迭代，迭代次數(shù)加1。

Step4計算每個粒子的目標(biāo)值，找出最優(yōu)粒子位置；并根據(jù)式(17)-式(20)計算粒子平均進化狀態(tài)信息。

Step5根據(jù)式(23)、式(12)和式(13)更新粒子的位置和速度。

Step6更新粒子適應(yīng)度值，與當(dāng)前個體極值進行對比，若粒子當(dāng)前適應(yīng)度值優(yōu)于個體極值，將wid設(shè)為該粒子位置；若所有粒子中個體極值最優(yōu)者優(yōu)于全局極值，則將該粒子的位置設(shè)為wgd。

Step7對比粒子群的適應(yīng)度，對粒子群適應(yīng)度變優(yōu)的增加其壽命，對粒子群適應(yīng)度變差的刪除粒子，并按式(14)重置搜索計數(shù)器。若創(chuàng)建新的粒子群，根據(jù)式(16)計算概率，否則，執(zhí)行下一步。

Step8根據(jù)式(24)計算局部最優(yōu)概率因子popt，若局部最優(yōu)概率因子popt大于隨機產(chǎn)生的隨機數(shù)，則按式(25)進行Levy飛行擾動；否則，執(zhí)行下一步。

Step9判斷算法是否達到收斂或達到最大迭代次數(shù)，若是，執(zhí)行下一步；否則，執(zhí)行Step 3。

Step10輸出全局最優(yōu)值，算法結(jié)束。

從兩個方面驗證改進算法的優(yōu)越性：一是利用四種測試函數(shù)對比尋優(yōu)效果；二是利用最優(yōu)解部署無線網(wǎng)絡(luò)對比分析部署效果。編程平臺為：Windows 7 Microsoft VS2013，仿真平臺為：MATLAB 2014a,CPU：i7-7500U@2.7 G Hz,RAM:4 GB。

3.2 尋優(yōu)效果對比分析

將本文算法、文獻[17](FOPSO)和文獻[18](FODPSO)在表1所示的四個基準(zhǔn)函數(shù)上[18]對比尋優(yōu)效果。三種粒子群優(yōu)化算法的參數(shù)設(shè)置如表2所示。種群規(guī)模設(shè)為50，最大迭代次數(shù)為1 000次。三種粒子群優(yōu)化算法運行100次取平均。

表1 四個基準(zhǔn)函數(shù)

表2 參數(shù)設(shè)置

圖4為三種智能優(yōu)化算法對表1四個標(biāo)準(zhǔn)函數(shù)的尋優(yōu)收斂曲線。

(a) 三種算法對Rastrigin函數(shù)的尋優(yōu)曲線(b) 三種算法對Ackley函數(shù)的尋優(yōu)曲線

(c) 三種算法對Rosenbrock函數(shù)的尋優(yōu)曲線(d) 三種算法對Sphere函數(shù)的尋優(yōu)曲線圖4 三種粒子群優(yōu)化算法尋優(yōu)收斂曲線

由圖4各算法的尋優(yōu)曲線可以看出：FOPSO和FODPSO對Rastrigin標(biāo)準(zhǔn)函數(shù)的尋優(yōu)效果一般，過早陷入了局部最優(yōu)；隨著迭代次數(shù)的增加，F(xiàn)OPSO和FODPSO在多峰Ackley函數(shù)、單峰Sphere、Rosenbrock函數(shù)上，收斂速度緩慢，尋優(yōu)精度不精。而本文改進算法無論是對Sphere、Rosenbrock兩種單峰函數(shù)還是對Rastrigin、Ackley多峰函數(shù)都能在若干次迭代后迅速從局部最優(yōu)中跳出，并快速搜尋到最優(yōu)值，擴大了對最優(yōu)值的全局搜索能力。

3.3 節(jié)點部署效果對比分析

為了檢驗節(jié)點部署性能，無線網(wǎng)絡(luò)中網(wǎng)絡(luò)參數(shù)設(shè)置如表3所示，粒子群參數(shù)設(shè)置詳見表2。

表3 網(wǎng)絡(luò)參數(shù)初始值

本文利用粒子群優(yōu)化算法，在以監(jiān)測區(qū)域半徑分別為50 m、100 m、150 m、200 m和250 m不同情況下，分析網(wǎng)絡(luò)節(jié)點數(shù)與網(wǎng)絡(luò)生命周期間的關(guān)系,如圖5所示。

圖5 不同區(qū)域半徑下節(jié)點個數(shù)與網(wǎng)絡(luò)生命周期曲線

從圖5可以看出在檢測區(qū)域半徑分別為50 m、100 m、150 m、200 m和250 m，節(jié)點個數(shù)分別為7、13、18、24、30時無線網(wǎng)絡(luò)的生命周期最長，當(dāng)超過最優(yōu)節(jié)點數(shù)目，監(jiān)測區(qū)域的生命周期持平開始下降并最終趨于穩(wěn)定。當(dāng)監(jiān)測半徑為200 m時得到的最優(yōu)節(jié)點數(shù)為13個。根據(jù)粒子群尋優(yōu)算法，我們得到節(jié)點間的最優(yōu)間距如表4所示。

表4 節(jié)點間最優(yōu)間距

為了驗證所提節(jié)點部署優(yōu)化算法性能，這里固定節(jié)點個數(shù)為13，其他參數(shù)詳見表3。將本文算法與文獻[7]、文獻[10]、文獻[20]在MATLAB2014a平臺上進行仿真對比，分析各算法節(jié)點部署后的覆蓋率和節(jié)點剩余能量。

3.3.1無線網(wǎng)絡(luò)覆蓋率對比

在節(jié)點部署過程中，覆蓋率是無線網(wǎng)絡(luò)能夠工作的基本要求，只有保證高覆蓋率，節(jié)點才能逐跳進行數(shù)據(jù)的傳輸，最終到達匯聚節(jié)點。覆蓋率通常定義為節(jié)點覆蓋總面積與目標(biāo)監(jiān)測面積之比，其中節(jié)點覆蓋總面積為無線網(wǎng)絡(luò)中所有節(jié)點覆蓋面積的并集[19]。若節(jié)點i的覆蓋面積為Ai，區(qū)域總面積為A，則覆蓋率為：

(26)

通過圖6各節(jié)點部署算法的覆蓋率曲線可以看出，本文節(jié)點部署優(yōu)化算法在同樣的監(jiān)測半徑內(nèi)，以相同的節(jié)點對無線網(wǎng)絡(luò)進行構(gòu)建，采用節(jié)點間最優(yōu)距離對節(jié)點進行有效部署，實現(xiàn)節(jié)點數(shù)據(jù)傳輸?shù)挠行Ц采w，覆蓋率達95%；文獻[20]以最大覆蓋率為目標(biāo)函數(shù)，通過改進魚群算法尋優(yōu)最佳解，雖取得了大約86%的覆蓋率但比本文的覆蓋率還是稍低，并且算法的收斂較本文算法也稍有緩慢；文獻[7]以節(jié)點探測概率近似于節(jié)點的覆蓋率，分配一定的權(quán)值作為最終目標(biāo)函數(shù)中的一項進行求解，能得到大約82%的覆蓋率，但這要受制于權(quán)值的分配；文獻[10]是以保證射頻標(biāo)簽最大覆蓋率為前提來降低節(jié)點間的干擾，最優(yōu)節(jié)點部署是為了保證節(jié)點通信的高效性而非節(jié)點數(shù)據(jù)傳輸?shù)母采w率，得到了大約80%的覆蓋率。本文算法的覆蓋率較其他算法至少提高了11.46%，并且收斂速度還快于其他算法。

圖6 各節(jié)點部署算法的覆蓋率曲線

3.3.2節(jié)點剩余能量對比

本文無線網(wǎng)絡(luò)的拓撲結(jié)構(gòu)是基于不等間距優(yōu)化部署結(jié)構(gòu)，而在前人研究中很多是基于隨機或等間距結(jié)構(gòu)，本小節(jié)選取節(jié)點隨機優(yōu)化結(jié)構(gòu)和等間距兩種部署結(jié)構(gòu)與本文所提的不等間距部署結(jié)構(gòu)進行節(jié)點剩余能量對比，以驗證本文不等間距優(yōu)化部署結(jié)構(gòu)的優(yōu)越性。

文獻[21]提出一種等間距部署模型，模型只考慮了d

(27)

式中，Est和Esr分別表示發(fā)送啟動能量和接收啟動能量。因此，等間距部署下節(jié)點i的能耗如下：

Erx·k·(n-i)

(28)

圖7 各算法的節(jié)點剩余能量曲線

通過圖7的各節(jié)點部署算法節(jié)點剩余能量曲線可以看出，本文算法以最大網(wǎng)絡(luò)生命周期為目標(biāo)函數(shù)，采用不等間距對節(jié)點進行有效部署，在滿足無線通信的前提下，減少了節(jié)點的能耗，延長了無線網(wǎng)絡(luò)的壽命，隨著迭代次數(shù)的增加節(jié)點剩余能量先降低后平穩(wěn)，且節(jié)點剩余能量都多于其他兩種隨機部署和等距部署算法；文獻[21]為等間距節(jié)點部署，在這種部署模式下，越靠近匯聚節(jié)點，剩余能量越少，最靠近匯聚節(jié)點的一個幾點最先能量消耗殆盡，從上圖7中可看出，隨著迭代次數(shù)的增多，節(jié)點的剩余能量快速降低并最終所剩無幾；文獻[7]通過混沌序列優(yōu)化細菌覓食算法將節(jié)點均勻部署在無線監(jiān)測區(qū)，降低了節(jié)點部署的冗余度，減少了節(jié)點不必要的通信能耗，一定程度上降低了節(jié)點的能耗，節(jié)點的剩余能量有一定的提高。

4 結(jié) 語

本文通過對分數(shù)階次、局部最優(yōu)位置等方面對分數(shù)階達爾文粒子群算法進行改進，以優(yōu)化粒子群算法的計算精度和收斂速度。并利用改進后的尋優(yōu)算法求解不等間距，實現(xiàn)節(jié)點的有效部署。仿真結(jié)果表明，改進后的粒子群算法不僅提高了跳出局部最優(yōu)的能力還加快了收斂速度。與其他節(jié)點部署算法相比，本文節(jié)點部署算法無論是在節(jié)點剩余能量還是在網(wǎng)絡(luò)覆蓋率上都有明顯的優(yōu)勢。