一種無線傳感器網(wǎng)絡(luò)二維目標(biāo)覆蓋的改進(jìn)方法

盧 毅，周 杰，萬連城

(1. 石河子大學(xué) 信息科學(xué)與技術(shù)學(xué)院，新疆維吾爾自治區(qū) 石河子 832003；2. 西安電子科技大學(xué) 期刊中心，陜西 西安 710071)

隨著技術(shù)的進(jìn)步，無線傳感器網(wǎng)絡(luò)越來越多地被用于工業(yè)、農(nóng)業(yè)、國防和教育等社會經(jīng)濟(jì)發(fā)展的方方面面[1-5]。目標(biāo)覆蓋是無線傳感器網(wǎng)絡(luò)部署過程中的一個關(guān)鍵問題，近年來吸引了許多研究人員和研究團(tuán)隊的關(guān)注[6-8]。通過合理的設(shè)置無線傳感器的監(jiān)測目標(biāo)，可以有效增加監(jiān)測水平，提升檢出的目標(biāo)數(shù)[9-14]。

目標(biāo)覆蓋直接決定了無線傳感器網(wǎng)絡(luò)對區(qū)域內(nèi)目標(biāo)的監(jiān)測能力。因為無線傳感器網(wǎng)絡(luò)的覆蓋類別較多，包括定點設(shè)置和空中撒布等，在覆蓋過程中不但需要考慮怎樣借助位置優(yōu)化完成傳感器的目標(biāo)監(jiān)測，還要考慮目標(biāo)被多少個傳感器同時監(jiān)測才能夠完成任務(wù)。在監(jiān)測范圍為二維平面的無線傳感器網(wǎng)絡(luò)中，目標(biāo)覆蓋率是無線傳感器網(wǎng)絡(luò)中的一個關(guān)鍵指標(biāo)，直接影響到對目標(biāo)的監(jiān)測效果。由于傳感器節(jié)點的監(jiān)測范圍有限，每個傳感器通常只能覆蓋一定范圍內(nèi)的有限個目標(biāo)，整個網(wǎng)絡(luò)中的所有節(jié)點需要協(xié)同完成目標(biāo)覆蓋任務(wù)。如何提高無線傳感器網(wǎng)絡(luò)的有效監(jiān)測的目標(biāo)數(shù)，保證對目標(biāo)的監(jiān)測效果，是二維目標(biāo)覆蓋中的一個關(guān)鍵問題。

針對無線傳感器網(wǎng)絡(luò)目標(biāo)覆蓋問題，文獻(xiàn)[15]給出了一種動態(tài)規(guī)劃算法，但并沒有針對被監(jiān)測目標(biāo)進(jìn)行選擇。文獻(xiàn)[16]給出了一種混合遺傳算法，能夠有效避免節(jié)點布置中的路徑暴露問題，但給出的混合遺傳算法容易陷入進(jìn)化停滯，導(dǎo)致得到的解集質(zhì)量較低。文獻(xiàn)[17]給出了一種蟻群算法，能夠有效降低網(wǎng)絡(luò)能耗，但蟻群算法很容易迭代停滯。

筆者給出了一種基于量子退火算法，并與粒子群算法、蟻群算法進(jìn)行了仿真比較。仿真結(jié)果顯示，提出的量子退火算法能夠有效解決二維目標(biāo)覆蓋問題，檢出的目標(biāo)數(shù)較粒子群算法、蟻群算法有較大提高。

1 二維目標(biāo)覆蓋問題的系統(tǒng)模型

擁有N個傳感器節(jié)點和M個被監(jiān)測目標(biāo)的二維無線傳感器網(wǎng)絡(luò)模型用矩陣R可表示為

(1)

在矩陣R中，rm,n為第m個目標(biāo)和第n個節(jié)點的覆蓋關(guān)系，rm,n為1表明被覆蓋。目標(biāo)監(jiān)測矩陣L可表示為

(2)

lm,n=1，表示第m個被監(jiān)測目標(biāo)被第n個傳感器節(jié)點監(jiān)測。二維目標(biāo)覆蓋問題的數(shù)學(xué)模型可以用如下的方程組來表示：

(3)

s.t.lm,n≤rm,n,

(4)

(5)

式(3)中，目標(biāo)函數(shù)fit表示最大化檢出目標(biāo)數(shù)，檢出目標(biāo)至少被G個節(jié)點監(jiān)測。式(4)表示監(jiān)測不能超過覆蓋范圍，式(5)表示由于每個節(jié)點能力有限，最多只能選擇H個目標(biāo)進(jìn)行監(jiān)測。

2 基于量子退火算法的無線傳感器網(wǎng)絡(luò)二維目標(biāo)覆蓋

2.1 解集的量子位編碼

在大規(guī)模無線傳感器網(wǎng)絡(luò)中，感知節(jié)點數(shù)和目標(biāo)數(shù)量較多。為了能夠進(jìn)行多點并行搜索和分布式計算，量子退火算法的解集中包含多個量子位編碼形式的解。在傳統(tǒng)的進(jìn)化算法中，解通常被表示成一個確定的二進(jìn)制字符串，即只能代表解空間中的某個固定狀態(tài)。在量子退火算法的解集中，每個解包含多個量子位，每個量子位可以處于|0〉態(tài)、|1〉態(tài)或|0〉和|1〉態(tài)之間的疊加態(tài)。如果解的長度為s，則每個解能夠同時表示2s個狀態(tài)。在量子退火算法中，每個量子位狀態(tài)可以表示為

|ψ〉=α|0〉+β|1〉 。

(6)

式(6)表示如果需要對系統(tǒng)的狀態(tài)進(jìn)行觀測，系統(tǒng)將坍縮為一個確定的狀態(tài)。當(dāng)對量子態(tài)進(jìn)行測量時，|0〉態(tài)被觀測到的概率是|α|2，|1〉態(tài)被觀測到的概率為|β|2，兩者滿足的歸一化條件為

|α|2+|β|2=1 。

(7)

(8)

其中，t代表退火溫度；j代表解在解集中的序號；M×N代表解中的量子位個數(shù)，分別對應(yīng)如式(2)所示的目標(biāo)監(jiān)測矩陣L中的M×N個元素{l1,1,l1,2,…,lM,N}。

2.2 初始解集的生成

為了保證生成解的均勻隨機(jī)性，量子退火中每個量子位上對應(yīng)態(tài)|0〉和態(tài)|1〉的概率幅度χk+1由Chebyshev混沌映射生成，可表示為

χk+1=cos(φarccosχk),k=0,1,…,M×N,

(9)

其中，φ為Chebyshev混沌映射的階數(shù)，當(dāng)φ>2時，映射具有正的李雅普諾夫(Lyapunov)指數(shù)，能夠生成隨機(jī)的混沌序列，在文中取φ=6。在生成初始解集的過程中，首先需要選擇一個(-1,1)之間的隨機(jī)數(shù)作為初始值χ0，以保證隨機(jī)性。在文中，Chebyshev混沌映射的初始值χ0=0.9。然后，按照式(9)所示的迭代方式生成余下的M×N個初始化值，并按如下公式完成量子位的初始化：

(10)

2.3 量子位狀態(tài)的測量

(11)

2.4 目標(biāo)函數(shù)值的計算

lm,n=z(m-1)×N+n，m=1,2,…,M,n=1,2,…,N。

(12)

在二維目標(biāo)覆蓋問題中，優(yōu)化目標(biāo)為最大化檢出的目標(biāo)數(shù)。將式(2)中的矩陣L根據(jù)規(guī)則式(12)替換矩陣Z的形式，則目標(biāo)函數(shù)可表示為

(13)

在計算目標(biāo)函數(shù)值時，首先驗證生成的解是否滿足約束條件式(4)和式(5)。如果不滿足約束條件，則應(yīng)當(dāng)運用貪婪算法等方式對矩陣Z中元素進(jìn)行相應(yīng)調(diào)整，使之符合兩個約束條件。

2.5 解集的量子旋轉(zhuǎn)門更新

(14)

表1 量子旋轉(zhuǎn)門中旋轉(zhuǎn)角查詢表

在表1中，φ為量子旋轉(zhuǎn)門中旋轉(zhuǎn)角與當(dāng)前溫度值的比例參數(shù)，文中取參數(shù)φ=0.000 1π/℃。

3 仿真及結(jié)果分析

仿真中設(shè)置傳感器及目標(biāo)隨機(jī)分布在600 m×600 m的范圍內(nèi)，每個節(jié)點最多可以監(jiān)測5個目標(biāo)，而單個目標(biāo)需要被3個節(jié)點監(jiān)測。量子退火算法的初溫為600 ℃，退火系數(shù)設(shè)置為0.8。粒子群算法和蟻群算法中個體數(shù)目均設(shè)置為50，算法重復(fù)次數(shù)為100。

圖1為節(jié)點感知半徑為80 m時獲得的單次運行仿真結(jié)果。從圖1可以看出，蟻群算法的運行陷入了早熟收斂，導(dǎo)致最終檢出的目標(biāo)數(shù)不高。粒子群算法比蟻群算法稍好，但迭代后不久即出現(xiàn)進(jìn)化停滯現(xiàn)象，導(dǎo)致檢出的目標(biāo)數(shù)較低。量子退火算法根據(jù)Metropolis規(guī)則動態(tài)調(diào)整旋轉(zhuǎn)角方向，避免了進(jìn)化停滯問題，在50次迭代后就尋找到了較優(yōu)解，相比其他兩種方法有效地提高了檢出的目標(biāo)數(shù)，增強(qiáng)了監(jiān)測效果。

圖2為在傳感器節(jié)點數(shù)為200時，不同半徑的情況下，粒子群算法、蟻群算法和量子退火算法目標(biāo)檢出率隨待檢測目標(biāo)數(shù)的變化曲線圖，仿真結(jié)果為50次運行的均值。如圖2所示，蟻群算法由于未動態(tài)調(diào)整參數(shù)，收斂較慢，導(dǎo)致檢出率較低。粒子群算法的運行結(jié)果優(yōu)于蟻群算法的，但由于存在進(jìn)化停滯現(xiàn)象，導(dǎo)致最終的檢出率少于量子退火算法的。量子退火算法相比其他兩種啟發(fā)式算法有效地提高了目標(biāo)檢出率，增強(qiáng)了無線傳感器網(wǎng)絡(luò)的監(jiān)測效果。

4 結(jié)束語

文中提出了一種量子退火算法來解決二維目標(biāo)覆蓋問題，設(shè)計了相應(yīng)的系統(tǒng)模型，并給出了二維目標(biāo)覆蓋優(yōu)化的目標(biāo)函數(shù)。針對二維目標(biāo)覆蓋問題，將基于量子退火算法的方法與粒子群算法、蟻群算法進(jìn)行了仿真比較。仿真結(jié)果顯示，提出的量子退火算法能夠有效解決二維目標(biāo)覆蓋問題，檢出的目標(biāo)數(shù)較粒子群算法、蟻群算法有較大提高。