盧 毅，周 杰，萬連城

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

(5)

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

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

2.1 解集的量子位編碼

在大規(guī)模無線傳感器網(wǎng)絡中，感知節(jié)點數(shù)和目標數(shù)量較多。為了能夠進行多點并行搜索和分布式計算，量子退火算法的解集中包含多個量子位編碼形式的解。在傳統(tǒng)的進化算法中，解通常被表示成一個確定的二進制字符串，即只能代表解空間中的某個固定狀態(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)進行觀測，系統(tǒng)將坍縮為一個確定的狀態(tài)。當對量子態(tài)進行測量時，|0〉態(tài)被觀測到的概率是|α|2，|1〉態(tài)被觀測到的概率為|β|2，兩者滿足的歸一化條件為

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

(7)

(8)

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

2.2 初始解集的生成

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

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

(9)

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

(10)

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

(11)

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

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

(12)

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

(13)

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

2.5 解集的量子旋轉門更新

(14)

表1 量子旋轉門中旋轉角查詢表

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

3 仿真及結果分析

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

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

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

4 結束語

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