改進型蟻群算法融合混沌優(yōu)化的pSPIEL算法的無線傳感器布局優(yōu)化

段宇君，王耀力，常 青*，劉 鑫

（1. 太原理工大學信息與計算機學院，太原030024； 2.32152部隊網(wǎng)絡(luò)中心，石家莊050000）

（*通信作者電子郵箱wfei7788@gmail.com）

0 引言

無線傳感網(wǎng)絡(luò)的布局安全是準確獲得相關(guān)信息的首要前提［1］。由于受到通信成本等因素的限制，傳感器布局不能過于密集，同時因無線信號傳播距離有限，故傳感器布局不能過于稀疏［2］，因此如何在滿足監(jiān)測要求的前提下合理規(guī)劃傳感器布局成為研究熱點。

下一位置確定后，根據(jù)式（15）對螞蟻走過路徑（i，j）信息素進行更新；當所有螞蟻走到終點，根據(jù)式（16）更新全局信息素，清空禁忌表。

IHACA-CpSPIEL流程如圖1所示。

圖1 IHACA-CpSPIEL流程Fig. 1 Flow chart of IHACA-CpSPIEL

3 實驗驗證

3.1 參數(shù)設(shè)置

為了驗證本文所提算法綜合性能，采用Matlab 仿真軟件進行仿真實驗，并與貪婪算法、文獻［4］所提pSPIEL 算法、蟻群算法、IHACA 進行對比實驗。本文將監(jiān)測區(qū)域離散為|V|=86 個位置點，選擇一子集A?V部署傳感器。實驗參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置Tab. 1 Parameter settings

3.2 結(jié)果與分析

1）局部性參數(shù)r對分簇數(shù)量影響。

利用混沌算子使得r在[rmin，rmax]范圍內(nèi)進行遍歷，從而確定最佳分簇個數(shù)，其中rmin=1.30 m，rmax=71.01 m。由圖2 可以看出，在指定范圍內(nèi)，通過加入混沌算子并進行200 次迭代對r的取值狀態(tài)進行全部遍歷，不同r值對應(yīng)不同的簇數(shù)，并且共獲得8 個分簇結(jié)果。r值過小，分得的簇小且多，簇間相關(guān)性開始增加，對于尋找相關(guān)性小的簇會更加困難；r值過大，容易只分一個簇，則此算法沒有過多效用。將pSPIEL 算法和IHCA-CpSPIEL 均進行5 次實驗，每次實驗都迭代200 次。由表2可以看出傳統(tǒng)的pSPIEL算法在每次實驗中找到的簇數(shù)都不一樣，只有在第3 次實驗中遍歷到所有簇數(shù)，因此其未能保證在200 次實驗中遍歷所有簇數(shù)。而IHACA-CpSPIEL 在5 次實驗中均能遍歷所有簇數(shù)，即1～8 種簇數(shù)。由圖3 可以看出，本文算法在3 個簇時可獲得最佳通信成本，因此，在后面的實驗中，r值均選取3.1 m，分簇個數(shù)均選取為3。

圖2 r值和簇的個數(shù)的關(guān)系Fig. 2 Relationship between r value and cluster number

表2 兩種算法迭代200次的簇數(shù)對比Tab. 2 Cluster numbers comparison of two algorithms after iterating 200 times

圖3 簇的個數(shù)和通信成本的關(guān)系Fig. 3 Relationship between cluster number and communication cost

2）搜索速度對比。

迭代次數(shù)對算法的效率影響突出，分別采用ACA、IHACA以及本文所提算法對傳感器進行布局優(yōu)化。圖4 顯示了各算法為達到0.17 的互信息量時的傳感器節(jié)點部署，迭代次數(shù)與通信成本的關(guān)系。采用同一算法時，通信成本隨著迭代次數(shù)的增加而減少。IHACA-CpSPIEL 在第27 次迭代次數(shù)時達到最低通信成本，IHACA 在第51 次達到最低，而傳統(tǒng)蟻群算法在66次時達到最低通信成本。IHACA 改進了啟發(fā)函數(shù)，避免了傳統(tǒng)蟻群算法搜索的盲目性，因此搜索速度比傳統(tǒng)蟻群算法快；而又將全局和局部信息素更新機制結(jié)合，避免蟻群算法陷入局部值，因此IHACA 搜索的解比其更優(yōu)。由于本文將CpSPIEL 算法求得的最優(yōu)簇首直接作為IHACA 的尋優(yōu)初值，因此搜索速度更快且求得的通信成本最低。

圖4 通信成本和迭代次數(shù)關(guān)系Fig. 4 Relationship between communication cost and iteration number

3）通信成本及傳感器使用數(shù)量對比。

圖5～7 及表3 可以看出本文所提算法較之貪婪算法、pSPIEL 算法、IHACA，在通信成本最低、使用傳感器數(shù)量最少時達到和其他算法相同的布局要求。從圖5 可以看出，在相同互信息量下，較之貪婪算法、pSPIEL 算法、IHACA，IHACACpSPIEL 的通信成本最低。由于傳感器節(jié)點部署問題具有子模性，為了滿足0.15 的信息量，布置傳感器數(shù)量較少，則每次加入傳感器時，獲得的子模效益較大，且通信成本相比pSPIEL 算法減小了24.0%；為了滿足較高的信息量0.20 時，由于布置的傳感器數(shù)量較多，每次加入新的傳感器時，獲得的子模效益較小，則通信成本相比pSPIEL 算法最少減小了6.5%。

圖6 互信息量和傳感器數(shù)量關(guān)系Fig. 6 Relationship between mutual information and sensor quantity

從圖6 可以看出，互信息量隨著傳感器數(shù)量的增大而變大，即傳感器布局效果越好。在傳感器數(shù)量少時，加入新的傳感器，子模效益增量較大；隨著傳感器數(shù)量增加，再加入新的傳感器時，子模效益的增量開始減少。本文所提算法使用最少傳感器最先達到要求的子模效益。由表3 可以看出，本文算法使用10 個傳感器達到了pSPIEL 算法使用15 個傳感器和改進啟發(fā)式蟻群算法使用13 個傳感器的子模效益，且通信成本相比貪婪算法減小了28.3%，相比pSPIEL 算法減小了11.3%，相比IHACA 減小了6.8%。本文根據(jù)貪婪算法、pSPIEL 算 法、IHACA 及IHACA-CpSPIEL 分 別 求 得 在 達 到0.17信息量下的傳感器節(jié)點部署解，如圖7所示，黑色圓點為86個候選位置點，白色方塊為已選觀測點。

表3 4種算法運行結(jié)果對比Tab. 3 Running results comparison for four algorithms

圖7 4種算法的傳感器布局Fig. 7 Sensor deployment of four algorithms

4）性價比對比。

4種算法的性價比即效用/成本比（F(A)/C(A)）如圖8所示。從圖中可以看出，在0.15～0.20的互信息量下，IHACA-CpSPIELL的性價比高于貪婪算法、pSPIEL算法及IHACA。通過分析可得:IHACA-CpSPIEL可達到最佳的成本-效益權(quán)衡。

圖8 效用/成本比和互信息量關(guān)系Fig. 8 Relationship between utility/cost ratio and mutual information

4 結(jié)語

為了能夠獲得最優(yōu)的傳感器節(jié)點部署方案以及最低的通信成本，本文提出了IHACA-CpSPIEL。通過引入互信息的方式來描述觀測點與未觀測點的相關(guān)性，用圖論的邊來表示通信成本。通過混沌算子增強pSPIEL 算法尋優(yōu)能力，并融合改進啟發(fā)函數(shù)和信息素更新機制的蟻群算法尋找最優(yōu)路徑，進一步解決了在通信成本約束下的傳感器布局問題。通過實驗表明，本文所提算法具有較優(yōu)的傳感器布局能力，在降低通信成本、減少傳感器數(shù)量方面也表現(xiàn)出一定的優(yōu)勢。