改進人工蜂群算法的WSN覆蓋連通優化

張 浩，龍道銀，覃 濤，王 霄,3，楊 靖,3+

(1.貴州大學 電氣工程學院，貴州 貴陽 550025；2.中國電建集團貴州工程有限公司 創新事業部， 貴州 貴陽 550025；3.貴州省科技廳 互聯網+協同智能制造重點實驗室，貴州 貴陽 550025)

0 引 言

無線傳感網絡(wireless sensor network，WSN)通過節點間的相互協作，可向用戶提供實時的監測數據，目前已被廣泛應用在多個領域[1,2]。節點部署是影響WSN性能的重要環節，其中區域覆蓋率和連通性是節點部署中的兩個重要指標。

當前，群體智能算法在WSN部署優化中得到廣泛應用[3-11]。文獻[3]提出了基于蟻獅算法的節點覆蓋優化策略，利用自適應收縮邊界對算法進行改進，提高了網絡的覆蓋率。文獻[4]提出了一種基于粒子群算法的覆蓋控制策略，考慮了網絡的覆蓋率與能耗，但覆蓋率不夠理想。文獻[5]提出了一種基于生物地理學優化算法的覆蓋連通策略，能有效獲得位置較好的節點部署位置，但算法的復雜度過高。文獻[6]提出一種基于花朵授粉算法的節點覆蓋優化，但節點均勻度不夠理想。文獻[7]利用多策略改進的灰狼算法去提升監測區域的覆蓋率，但存在明顯的覆蓋空洞。文獻[8]提出了一種基于改進鯨魚優化算法的節點覆蓋策略，但算法的復雜度過高。文獻[9]將貝葉斯算法的預測思想引入到人工蜂群算法中，提高了不同監測區域的覆蓋率。文獻[10]利用改進的虛擬力算法增強了無線傳感網絡的覆蓋率，同時利用Delaunay三角檢測覆蓋空洞并進行修復，但網絡的能耗較大。文獻[11]提出了一種節點多目標安全連通部署優化算法，但部分區域的覆蓋率不夠理想。

針對上述問題，為有效兼顧網絡的覆蓋率及連通性，提出了一種基于精英解引導下動態混合搜索人工蜂群算法(dynamic hybrid search based artificial bee colony algorithm，DHSABC)的節點部署策略。將節點的部署過程類比為蜂群尋找最優蜜源的過程，在相同實驗條件下，與其它文獻中的算法進行仿真對比，驗證改進后算法在節點部署上的有效性。

1 問題模型分析

假設在面積為M×L m2的WSN監測區域內，隨機拋撒了n個同構傳感器節點，其中節點集合為S={S1,S2,…Si…,Sn}，Si位置坐標為 (xi,yi)，i=1,2,…,n， 節點的感知半徑均為Rs，通信半徑均為Rc。為簡化計算，將該監測區域離散化為m×l個單位正方形區域，每個子區域的中心坐標就是節點的覆蓋目標中心點的坐標集合為Cj=(xj,yj)，j∈{1,2,…,m×l}。 若中心點Cj與任意一個節點距離小于或等于感知半徑Rs，則認定Cj被節點覆蓋，節點Si與中心點Cj的間距定義為

(1)

節點感知模型為布爾感知模型，中心點Cj=(xj,yj) 被節點Si感知的概率p(Si,Cj) 定義為

(2)

中心點Cj被所有節點聯合感知概率定義為

(3)

該區域的覆蓋率Cov為感知節點集合S所對應的聯合感知概率之和與區域內中心點總數的比值，定義為

(4)

Cov越大表示對區域的覆蓋率越高，對區域監測的性能越好，故可以得到第一個目標函數為

(5)

在無線傳感網絡中節點覆蓋問題中，還應該考慮節點之間的連通性，為了保證網絡連通的可靠性，每個節點至少應與兩個或兩個以上的節點能夠連通。假設兩個節點之間的距離在通信半徑以內，則認定兩節點間能夠連通，故節點Si與節點Sj之間的連通性p(Si,Sj) (i≠j) 可定義為

(6)

無線傳感器網絡中的節點連通度是指在網絡中節點一跳范圍之內能夠與其通信的相鄰節點的數量與網絡中節點總數量二次方的比值。網絡連通度越大，網絡中存在的可能通路就越多，網絡的連通性能越好。故可以得到節點部署的第二個目標函數[11]為

(7)

因此，以區域覆蓋率和節點連通度定義的目標函數為

(8)

其中，α為限制的區域覆蓋率，p(Si,Sj)≥2表示每個感知節點至少可以與兩個及兩個以上的節點形成通路，當節點的其中一條通路斷開時，節點的信息可由其它通路傳輸，可保證網絡的穩定性，經過多次實驗，本文中ω1與ω2的取值分別為0.8和0.2。

2 人工蜂群算法

人工蜂群算法[12]由土耳其學者Karaboga為優化代數問題而提出。根據蜜蜂在活動中扮演的角色，將其歸納為觀察蜂、雇傭蜂以及偵查蜂3種類型。蜂群中主要有3個關鍵要素：食物源、被雇傭的蜜蜂和未被雇傭的蜜蜂；最基本的行為模型是尋找適應度最高的蜜源，ABC算法的實現過程主要由下面幾個階段組成。

初始化階段：按照式(9)隨機生成初始種群SN，即SN個具有D維變量的解

xi,j=xmin,j+rand(0,1)(xmax,j-xmin,j)

(9)

式中：i=1,2,…,SN，j=1,2,…,D，xmax,j和xmin,j為搜索空間的上界和下界。每個解xi,j代表一個D維向量。

雇傭蜂階段：雇傭蜂通過式(10)產生一個新的蜜源vi,j， 并按照式(8)和式(11)計算新蜜源的適應度，若新蜜源優于原位置xi,j， 則替換掉原來的蜜源。當全部雇傭蜂在完成搜索后，將保留下來的食物源信息與觀察蜂進行分享

vi,j=xi,j+φi,j(xi,j-xk,j)

(10)

(11)

式中：k,j是隨機選擇的下標，且有k∈{1,2,…SN}，j∈(1,2,…,D)，k不等于i，φi,j為[-1,1]之間的隨機數。

觀察蜂階段：觀察蜂根據式(12)計算每個食物源被選擇的概率，然后通過輪盤賭機制選擇一個食物源，采用與式(10)相同的搜索策略，并且與原食物源進行比較，擇優保留

(12)

偵查蜂階段：如果一個食物源在循環limit代后仍沒有得到更新，表示該食物源對應的偵查蜂可能陷入局部最優，此時將該食物源所對應的雇傭蜂轉換為偵查蜂，并按照式(9)隨機生成新解。

3 改進的人工蜂群算法-DHSABC

基本人工蜂群算法的探索與開發性能受到了其搜索策略的限制[13]。在算法初期，雇傭蜂階段應側重探索能力，在算法初期應該在更大的區域進行探索，更有可能發現最優解；隨著迭代次數逐漸增大，較小的變異步長有益于算法迅速收斂，并在最優蜜源附近進行搜索。觀察蜂階段可根據雇傭蜂階段產生的精英解信息來調整自己的搜索策略，有利于快速找到最優解。

為了提升人工蜂群算法的性能，達到探索與開發能力的平衡，提出了精英解引導下的動態混合搜索策略，使算法能更好地適用于WSN部署問題。在算法初始化階段引入Tent映射，以提高種群的多樣性；在雇傭蜂階段，提出了基于柯西分布與正態分布的混合搜索策略，同時引入動態權重系數k1、k2，用來平衡算法的探索能力與開發能力；觀察蜂在添加動態混合搜索策略的同時引入雇傭蜂階段的精英解信息，使觀察蜂在精英解周圍進行開發。

3.1 Tent混沌映射

初始化種群的優劣性會影響到算法的求解精度，多樣性好的初始化種群會提升算法的性能。混沌映射的隨機性和遍歷性能豐富初始化種群的多樣性，有利于算法跳出局部最優，增強全局尋優的能力。其中Tent映射作為一種經典的混沌模型，已經被驗證了在算法性能提升上的有效性[14]。故本文取Tent映射去初始化種群，假設種群規模為 {1,2,…i…,SN}， 算法的空間維數為 {1,2,…j…,D}， 經過多次測試，文中選取的Tent混沌映射函數如下

(13)

取Tent混沌序列的初始值z(0)=0.47， 種群的規模SN=10，空間維數D=160，圖1為Tent映射在[0,1]之間的分布直方圖，每個區間值的個數都集中在30～35之間，數值在每個區間上的分布相對均勻。

將式(13)產生的混沌序列映射到解空間后得到初始化種群，種群個體xi,j如下

xi,j=xmin,j+zi,j(xmax,j-xmin,j)

(14)

其中，i=1,2,…,SN，j=1,2,…,D，xmax,j和xmin,j為搜索空間的上界和下界，zi,j為混沌值，將混沌值引入到搜索空間中，能產生更加均勻的初始種群，有利于算法搜索到更優的解。

3.2 基于動態混合變異的搜索策略

在初始人工蜂群算法中，雇傭蜂的食物源由式(10)產生 ，φi,j在[-1,1]之間隨機選擇，連續性較差，易錯過最優解，為此提出一種動態混合搜索策略，如式(15)所示

(15)

式中：k,j是隨機選擇的下標且滿足k∈{1,2,…,SN}, 其中k不等于i，j∈(1,2,…,D)，β是調節系數，T為最大迭代次數，t為當前迭代次數，C(0,1) 為服從標準柯西分布的變異因子，N(0,1) 為服從正態分布的變異因子。

圖2為正態分布和柯西分布的概率密度函數對比圖。

由圖2可知，標準柯西分布相對于正態分布來說形狀更加的平緩且逼近0的過程中更加的平滑，在原點附近的分布相對于正態分布更小，數值變化連續性強，所以柯西分布的變異尺度要大于正態分布。在算法前期，動態權重系數k1隨著迭代次數的增加而降低，柯西分布具有更大的變異步長且權重系數較大，搜索的區域更加廣泛，利于算法跳出局部最優；在算法后期，正態分布變異尺度較小且動態權重k2隨著迭代次數的增大而增大，以保證蜂群在最優蜜源附近搜索。

3.3 精英解引導的搜索策略

在基本人工蜂群算法中，觀察蜂的搜索方式存在一定的缺陷，即沒有利用到觀察蜂所搜索到的精英解信息[15]，將雇傭蜂階段所獲得的精英解信息用來引導觀察蜂的搜索，從而提高算法的開發能力。對其蜜源的搜索方式進行調整，具體如式(16)所示

(16)

式中：xbest,j是從雇傭蜂中選擇的精英解，hi,j是觀察蜂搜索的起點，考慮到使用精英解會降低算法的探索能力，所以將雇傭蜂中的精英解與原始解和的1/2作為搜索的起始點，引入精英解的同時也保留原始選擇的蜜源。從而在增強算法開發能力的同時也維持算法的探索能力。

4 基于DHSABC算法的覆蓋優化設計

4.1 DHSABC覆蓋優化算法步驟

本文將蜂群尋找最佳蜜源的過程類比為尋找最佳的節點部署的過程，每一個蜜源代表一個節點覆蓋方案，基于DHSABC的節點覆蓋優化算法步驟如下所示。

輸入：WSN監測區域、節點數目及位置和DHSABC算法相關參數。

輸出：最優節點位置、覆蓋率及連通度。

(1)按式 (13) 和式 (14) 初始化種群, 其中每個個體代表一種部署方案

(2)t=1 and limit=1

(3)while(t

(4)根據式 (15) 計算新解vi,j

(5)根據式 (8) 和式 (11) 計算新解vi,j覆蓋率、 連通度及對應的適應度

(6)ifF(vi,j)

(7)根據適應度值得到精英解xbest,j

(8)按照式 (12) 計算選擇概率

(9)跟隨蜂根據概率選擇蜜源。 按照式 (16) 搜索蜜源

(10)按照式 (8) 和式 (11) 計算覆蓋率與連通度，并得到對應的適應度

(11)ifF(vi,j)

(12)if limit>50， 則按照式 (13) 和式 (14) 產生新的食物源

(13)t=t+1

(14)End while

4.2 DHSABC算法時間復雜度分析

在不同節點數目下對DHSABC算法與ABC算法的運行時間做了對比分析，結果見表1。

表1 不同節點數目下的運行時間

由表1可知，在節點數目為60、70、80、90、100的時候，DHSABC算法的運行時間都小于ABC算法，運行時間平均減少了1.95 s，改進后的算法相對于ABC算法來說具備更高的求解效率。

5 仿真實驗與分析

5.1 相關參數設置

為驗證DHSABC算法在無線傳感器網絡節點部署問題中的有效性，選取不同文獻中的算法進行對比實驗，具體的算法見表2，實驗參數的設置與相應文獻一致。

表2 對比算法

仿真實驗環境：Win10操作系統，AMD Ryzen5 2500U with Radeon Vega Mobile Gfx @2.00 Ghz主頻，8 G內存，MATLAB 2016a，DHSABC算法參數見表3。

表3 算法參數設置

5.2 網絡覆蓋率

5.2.1 DHSABC算法的覆蓋率分析

為了驗證DHSABC算法對ABC算法性能上的提升，將改進后的算法與ABC算法、PSO算法、GABC算法在相同的實驗條件下進行比較，實驗參數設置見表4。

表4 實驗1參數設置

表5給出了ABC算法、PSO算法、GABC 算法、DHSABC算法運行10次后的平均覆蓋率。

表5 不同算法下的節點覆蓋率

由表5可知，DHSABC具有最高的覆蓋率，其中DHSABC算法相對于GABC算法在覆蓋率上提高了5.07%，相對于ABC算法提升了8.2%，相對于PSO算法提升了14.33%。

節點采取隨機部署的形式，節點初始覆蓋如圖3(a)所示，監測區域內存在著明顯的覆蓋空洞，利用ABC算法對節點部署進行優化，優化后實驗結果如圖3(b)所示，節點的分布相對均勻，監測區域內的覆蓋率得到了有效的提升，但仍然存在部分覆蓋空洞；GABC算法下的節點覆蓋如圖3(c)所示，從圖中可以看出某些區域內節點的冗余度過高；基于DHSABC算法的無線傳感網絡部署效果如圖3(d)所示，從圖中可以看出某些區域內節點的冗余度過高；相比于上述兩種算法覆蓋更加均勻。

圖4是ABC、GABC與DHSABC算法的節點覆蓋率收斂曲線圖。

由圖4可知，DHSABC算法在相同的迭代次數下覆蓋率幾乎都優于ABC和GABC算法，說明引入精英解信息和混沌初始種群增強了算法的尋優能力，在相同迭代次數下具備更高的覆蓋率。迭代次數達到400代以后，ABC與DHSABC算法都趨于收斂，但ABC算法的覆蓋率僅維持在90%附近，而DHSABC算法通過采用動態混合策略，能跳出局部最優，搜索到更好的解，在400代時覆蓋率達到了98%，相對于ABC算法提升了8%左右。

5.2.2 與IGWO、MS-ALO算法對比

實驗參數設置與文獻[3]和文獻[7]相同，具體參數見表6。

表7為節點初始部署、ABC算法、MS-ALO算法、IGWO算法、DHSABC算法的覆蓋率對比。

由表7可知，本文提出的算法覆蓋率達到96.58%，相對于ABC算法、IGWO算法、MS-ALO算法，覆蓋率分別提升了5.12%、2.3%、0.13%，對區域的覆蓋的空洞更少，說明改進后的算法具有更強的尋優能力。

圖5(a)和圖5(b)分別是ABC算法和DHSABC算法優化后的節點覆蓋情況。

對比圖5(a)與圖5(b)，可以看出DHSABC算法下節點的分布更加均勻，具有更高的覆蓋率。

表6 實驗2參數設置

表7 實驗2優化結果對比

5.2.3 與BPABC、IWOA算法對比

實驗參數設置與文獻[8]和文獻[9]相同，具體參數見表8。

表9為ABC算法、IWOA算法、BPABC算法、DHSABC算法的覆蓋率對比；圖6(a)和圖6(b)分別是DHSABC算法在節點數為60和43優化后的節點覆蓋圖。

從表9可知，在同等的實驗條件下，DHSABC算法的覆蓋率達到99.90%，覆蓋效果如圖6(a)所示，相對于ABC算法、BPABC算法、IWOA算法，覆蓋率分別提升了4.76%、2.56%、0.69%。

表8 實驗3參數設置

表9 實驗3優化結果對比

經多次實驗驗證，DHSABC算法只需43個節點，就能達到BPABC算法60個節點時的所達到的覆蓋率，覆蓋效果如圖6(b)所示，從圖中可以看出節點分布相對均勻，因此在適當降低覆蓋率的要求下，DHSABC可有效降低節點的冗余度。

5.2.4 算法在不同節點數目下的覆蓋率對比

部署節點數量過多會導致網絡中的冗余度增加，部署代價提高。在相同的節點數目下，網絡的覆蓋率越高，對監測區域的覆蓋效果更好，本文分析對比了4種算法在不同節點數目下的覆蓋率，如圖7所示。

從圖7可知，在相同節點數量的情況下，DHSABC算法相比于其它幾種算法都具有更高的覆蓋率，節點分布更加均勻，說明了改進后的人工蜂群算法增強了算法的尋優能力，提升了傳感器網絡的覆蓋率。

5.3 節點連通度

5.3.1 連通度分析

將改進后的算法與ABC算法、PSO算法、GABC算法在相同的實驗條件下比較連通度，實驗參數設置與表4相同。

為降低數據隨機性對實驗分析的影響，將是ABC算法、PSO算法、GABC 算法、DHSABC算法在相同條件運行20次后的平均連通度進行對比，結果見表10。

表10 不同算法下的節點連通度

由表10可知，DHSABC具有最高的連通度，其中DHSABC算法相對于ABC算法在連通度上提高了0.0068，相對于GABC算法提升了0.0051，相對于PSO算法提升了0.0145。

節點采取隨機部署的形式，節點的初始狀態如圖8(a)所示，由圖可知監測區域內節點冗余度過高，節點之間的連通效果不理想；利用ABC算法對節點部署進行優化，實驗結果如圖8(b)所示，相對于圖8(a)來說，節點分布更加的均勻，但仍然有部分節點處于單連通狀態；圖8(c)是GABC算法下的節點連通度，相對于ABC算法來說，具備更高的連通性，但依然有較大的提升空間；基于DHSABC算法的節點連通狀態如圖8(d)所示，節點的分布較好，且每個節點都至少可以與兩個或兩個以上的節點連接。綜上，DHSABC算法改善了ABC、GABC算法下網絡連通性弱的不足。

圖9是ABC、GABC、DHSABC算法的連通度收斂曲線圖。

從圖9可知，初始狀態時節點分布比較集中，所以連通度很高，但此時的節點冗余度也很高，隨著迭代的進行，節點逐漸分散，連通度出現下降趨勢后由于算法收斂又趨于穩定。其中DHSABC算法在相同的迭代次數下的連通度幾乎都優于ABC算法與GABC算法，說明改進后的算法具備更強的尋優能力，節點之間的連通性更好；且從收斂曲線可以看出，由于在雇傭蜂階段引入了精英解信息，DHSABC算法的曲線更加穩定。

5.3.2 不同節點數下的連通數目對比

在相同的節點數目下，網絡中的連通數目越多，網絡的穩定性更好，圖10是4種算法在不同節點數下的連通數目對比。

由圖10可知，DHSABC算法相對于其它幾種算法具有更高的節點連通數目，網絡具有更好的連通性。在一定范圍內，每增加5個節點，網絡中節點的可連接數目會增加19個左右，因此在對節點連通度有需求時，通過預測出所需的傳感器節點，在節點預測值附近初始化種群的維度，可提高部署的效率。

6 結束語

針對WSN覆蓋中的覆蓋率與節點連通度優化問題，提出了一種基于改進人工蜂群算法的節點部署策略，通過構建基于節點的連通度和網絡覆蓋率的目標函數來引導蜂群搜索最優蜜源。首先，針對人工蜂群算法尋優能力較差的不足，利用Tent映射初始化種群，并將動態混合搜索策略引入到雇傭蜂和觀察蜂階段，增強蜂群對搜索空間的遍歷性和尋優能力；其次，在觀察蜂階段將精英解和原始解的1/2作為搜索的起點，以平衡算法的全局探索與開發能力；最后將改進后的算法應用到WSN節點部署問題中。仿真結果表明，相對于其它算法，改進后的人工蜂群算法能達到更高的覆蓋率和節點連通度。