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

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

0 引 言

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

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

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

1 問題模型分析

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

(1)

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

(2)

中心點Cj被所有節(jié)點聯(lián)合感知概率定義為

(3)

該區(qū)域的覆蓋率Cov為感知節(jié)點集合S所對應的聯(lián)合感知概率之和與區(qū)域內(nèi)中心點總數(shù)的比值，定義為

(4)

Cov越大表示對區(qū)域的覆蓋率越高，對區(qū)域監(jiān)測的性能越好，故可以得到第一個目標函數(shù)為

(5)

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

(6)

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

(7)

因此，以區(qū)域覆蓋率和節(jié)點連通度定義的目標函數(shù)為

(8)

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

2 人工蜂群算法

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

初始化階段：按照式(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)產(chǎn)生一個新的蜜源vi,j， 并按照式(8)和式(11)計算新蜜源的適應度，若新蜜源優(yōu)于原位置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]之間的隨機數(shù)。

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

(12)

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

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

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

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

3.1 Tent混沌映射

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

(13)

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

將式(13)產(chǎn)生的混沌序列映射到解空間后得到初始化種群，種群個體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為混沌值，將混沌值引入到搜索空間中，能產(chǎn)生更加均勻的初始種群，有利于算法搜索到更優(yōu)的解。

3.2 基于動態(tài)混合變異的搜索策略

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

(15)

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

圖2為正態(tài)分布和柯西分布的概率密度函數(shù)對比圖。

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

3.3 精英解引導的搜索策略

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

(16)

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

4 基于DHSABC算法的覆蓋優(yōu)化設(shè)計

4.1 DHSABC覆蓋優(yōu)化算法步驟

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

輸入：WSN監(jiān)測區(qū)域、節(jié)點數(shù)目及位置和DHSABC算法相關(guān)參數(shù)。

輸出：最優(yōu)節(jié)點位置、覆蓋率及連通度。

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

(2)t=1 and limit=1

(3)while(t

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

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

(6)ifF(vi,j)

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

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

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

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

(11)ifF(vi,j)

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

(13)t=t+1

(14)End while

4.2 DHSABC算法時間復雜度分析

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

表1 不同節(jié)點數(shù)目下的運行時間

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

5 仿真實驗與分析

5.1 相關(guān)參數(shù)設(shè)置

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

表2 對比算法

仿真實驗環(huán)境：Win10操作系統(tǒng)，AMD Ryzen5 2500U with Radeon Vega Mobile Gfx @2.00 Ghz主頻，8 G內(nèi)存，MATLAB 2016a，DHSABC算法參數(shù)見表3。

表3 算法參數(shù)設(shè)置

5.2 網(wǎng)絡覆蓋率

5.2.1 DHSABC算法的覆蓋率分析

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

表4 實驗1參數(shù)設(shè)置

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

表5 不同算法下的節(jié)點覆蓋率

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

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

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

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

5.2.2 與IGWO、MS-ALO算法對比

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

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

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

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

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

表6 實驗2參數(shù)設(shè)置

表7 實驗2優(yōu)化結(jié)果對比

5.2.3 與BPABC、IWOA算法對比

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

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

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

表8 實驗3參數(shù)設(shè)置

表9 實驗3優(yōu)化結(jié)果對比

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

5.2.4 算法在不同節(jié)點數(shù)目下的覆蓋率對比

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

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

5.3 節(jié)點連通度

5.3.1 連通度分析

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

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

表10 不同算法下的節(jié)點連通度

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

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

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

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

5.3.2 不同節(jié)點數(shù)下的連通數(shù)目對比

在相同的節(jié)點數(shù)目下，網(wǎng)絡中的連通數(shù)目越多，網(wǎng)絡的穩(wěn)定性更好，圖10是4種算法在不同節(jié)點數(shù)下的連通數(shù)目對比。

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

6 結(jié)束語

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