基于分數階達爾文粒子群的不等間距節點部署優化算法

張 利 峰

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

0 引 言

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

根據上面的分析可知，現有的拓撲結構大都是隨機部署，并且都存在能耗不均衡和生命周期短暫等問題。因此，為了解決能耗均衡，節省節點能量，本文結合星型拓撲和鏈式拓撲結構的優點，利用提出粒子群優化的不等間距節點部署優化算法。

1 不等間距拓撲結構及能耗模型

1.1 不等間距拓撲結構

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

圖1 無線網絡不等間距拓撲結構

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

圖2 單鏈監測區域示意圖

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

1.2 不等間距拓撲結構能耗模型

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

圖3 無線通信模型

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

(1)

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

ERx(k,d)=Erx×d

(2)

對于任何一個節點i，其發送kbit數據包能耗:

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

(3)

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

(4)

將上式統一表示為：

Erx·k·(n-i)

(5)

根據圖1，為了確保Sink節點為中心的傳感網絡能耗均勻，滿足以下條件：

E(i)=E(i+1)

(6)

假設每個節點的初始能量為Einit，那么整個網絡的生命周期為：

(7)

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

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

εamp·diβ

(8)

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

(9)

(10)

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

maxT

(11)

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

1)+εamp·diβ

2 粒子群優化算法及其改進

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

2.1 粒子群算法

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

(12)

(13)

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

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

(14)

式中：Nkill表示粒子群適應值沒變化期間被刪除的粒子數。若一個粒子群中所有粒子被刪除，并且當前粒子群數沒有超過種群設置數，則創建新粒子群的概率為：

p=r/Nnum

(15)

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

(16)

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

2.2 基于進化信息調整分數階次α

(17)

(18)

(19)

(20)

(21)

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

(22)

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

設慣性系數ω為1，根據分數階微分方程的格林瓦德-列特尼科夫(G-L)定義，粒子速度更新策略變為：

(23)

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

2.3 基于Levy飛行特征的局部最優

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

定義局部最優概率因子popt：

(24)

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

(25)

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

3 仿真實驗與分析

3.1 節點部署尋優流程

將無線網絡最大生命周期目標函數作為改進分數階達爾文粒子群算法的目標函數，搜索最優的節點間距di和鏈路節點數n以部署網絡，尋優流程如下：

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

Step2對粒子群中每個粒子進行適應度評估，將粒子個體的最優值wid設為當前位置，全局最優值wgd設為群體最優粒子位置。

Step3開始迭代，迭代次數加1。

Step4計算每個粒子的目標值，找出最優粒子位置；并根據式(17)-式(20)計算粒子平均進化狀態信息。

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

Step6更新粒子適應度值，與當前個體極值進行對比，若粒子當前適應度值優于個體極值，將wid設為該粒子位置；若所有粒子中個體極值最優者優于全局極值，則將該粒子的位置設為wgd。

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

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

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

Step10輸出全局最優值，算法結束。

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

3.2 尋優效果對比分析

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

表1 四個基準函數

表2 參數設置

圖4為三種智能優化算法對表1四個標準函數的尋優收斂曲線。

(a) 三種算法對Rastrigin函數的尋優曲線(b) 三種算法對Ackley函數的尋優曲線

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

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

3.3 節點部署效果對比分析

為了檢驗節點部署性能，無線網絡中網絡參數設置如表3所示，粒子群參數設置詳見表2。

表3 網絡參數初始值

本文利用粒子群優化算法，在以監測區域半徑分別為50 m、100 m、150 m、200 m和250 m不同情況下，分析網絡節點數與網絡生命周期間的關系,如圖5所示。

圖5 不同區域半徑下節點個數與網絡生命周期曲線

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

表4 節點間最優間距

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

3.3.1無線網絡覆蓋率對比

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

(26)

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

圖6 各節點部署算法的覆蓋率曲線

3.3.2節點剩余能量對比

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

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

(27)

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

Erx·k·(n-i)

(28)

圖7 各算法的節點剩余能量曲線

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

4 結 語

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