李 明， 胡江平

(1.重慶工商大學 計算機科學與信息工程學院 檢測控制集成系統工程實驗室,重慶 400067;2.電子科技大學 自動化工程學院, 四川 成都 611731)

0 引 言

節點部署在無線傳感器網絡(WSNs)應用中起著非常重要的作用，對于傳感器網絡的能量均衡、路由路徑規劃和定位等有重要影響。如何以較小的部署代價來布設節點保證網絡的覆蓋和連通性能以及延長網絡壽命，具有重要的研究意義，受到了廣大研究者的重視[1]。文獻[2]提出一種基于改進人工蜂群算法的覆蓋優化方法延長了網絡的生命周期。張軍等人[3]提出一種利用對固定節點進行Voronoi 多邊形劃分和利用基于反向學習策略的蜂群算法優化混合無線傳感器網絡覆蓋算法。文獻[4]提出了一種改進離散果蠅優化算法對覆蓋問題進行優化。孫澤宇等人[5]提出了一種基于概率模型下四圓無縫對接時有效覆蓋面積的求解過程并給出了概率模型中冗余覆蓋率的求解過程。李明[6]提出了一種基于多重覆蓋算法的異構節點調度機制。文獻[7]提出了一種基于集合覆蓋目標覆蓋算法。以上這些算法大多只考慮覆蓋問題，未考慮網絡連通性的問題，使得算法的適用性受到影響。文獻[8]對概率感知模型下考慮連通性的概率覆蓋進行研究，構建了覆蓋空洞的修補半徑,提出了移動距離和修補半徑的關系模型實現覆蓋增強。梅希薇等人[9]提出了一種基于連通性的無線傳感器網絡覆蓋優化算法。文獻[10]提出了一種面向目標的有向傳感器網絡連通覆蓋算法，但該算法未考慮到系統容錯性的要求以及部署位置不同造成的部署代價不同，限制了算法的適用范圍。

針對這些問題，本文提出了一種最小部署代價的容錯部署算法。該算法在考慮到部署位置不同具有不同的部署的代價、監測目標的多重覆蓋和部署節點的多重連通的條件下，以部署代價最小為優化目標，利用改進的和聲搜索算法IHS來布置傳感器節點，達到增強網絡服務質量的目的。

1 問題模型分析

假定二維平面A內分布有W個監測目標ti(i=1,2,…,W)和M個傳感器節點可部署的位置posi(i=1,2,…,M)。其中，每個監測目標ti的位置已知。部署的傳感器節點參數都相同。

1.1 節點感知模型和連通模型

本文采用布爾感知模型。即若目標ti與節點si的距離小于節點si的感知半徑，則認為目標ti被節點si覆蓋，則認為節點si和節點sj是連通的。

定義1k覆蓋:指在監測區域中，每個監測目標ti(i=1,2,…,W)都至少被k個傳感器節點所覆蓋。

定義2c連通:指部署區域中，每個傳感器節點都至少與c個傳感器節點連通。

1.2 問題描述

在二維平面內如何選擇最少數量的部署位置放置傳感器節點si，使得所有的監測目標ti能夠被k覆蓋(k≥1)和部署的傳感器之間能夠c連通(c≥1)。假定一個部署位置只能放置一個傳感器節點且節點感知半徑、通信半徑和能量等參數都相同。用形式化的語言描述為

(1)

(2)

式中costi為每個部署位置posi的部署代價；

約束(1)含義是每個監測目標至少被k個傳感器節點所覆蓋；約束(2)含義是每個傳感器節點至少與c個傳感器節點連通。

2 改進的和聲搜索算法

2.1 和聲搜索算法

和聲搜索算法是一種通過對藝術家音樂創造的過程進行模擬，將優化問題的決策變量類比于樂器的音調，解向量類比為各種樂器音調的和聲，優化目標類比與評價函數，種群類比于和聲記憶庫，對問題進行優化求解的算法[11]。和聲搜索算法首先對和聲記憶庫( harmony memory，HM)初始化，然后以概率HMCR對新產生的解在HM內取值，并以概率PAR對解局部微調，以參數1—HMCR在變量允許的范圍內取值，生成新的解向量。若新的解向量評價函數優于HM內的最差解，則最差解被新的解向量替換；算法不斷運行直到滿足算法停止的條件為止。由于參數HMCR和參數PAR取值固定且為常數，導致原始和聲搜索算法性能不佳，特別當問題較為復雜時，算法性能會急劇下降。

針對原始和聲搜索算法的存在的缺點，結合學習自動機的學習能力，本文提出了一種基于改進和聲搜索算法IHS解決本文的連通覆蓋問題。

2.2 學習自動機基本原理

學習自動機是一種通過與環境的不斷交互來獲得環境獎勵最大的動作的智能單元[12,13]。一般來說，學習自動機由代表候選動作的集合α，表示環境的反饋集合，與候選動作集 一一對應概率的集合P，代表學習自動機的更新規則G。學習自動機在學習過程中基于以下規則更新其動作概率[12]：

對于有利的響應，依據如式(3)來更新動作概率

(3)

對于不利的響應，則依據式(4)來更新概率

(4)

式中pi(n)為在時刻n對應于動作αi所選取的概率。

2.3 改進和聲搜索IHS算法

原始和聲搜索算法中參數HMCR和PAR的取值是一組固定的參數，無法滿足算法性能對控制參數的特殊要求。本文提出一種基于學習自動機的參數自適應的和聲搜索進化算法。

輸入：控制參數pari

輸出：經過學習自動機優化的控制參數pari

將控制參數pari候選的取值范圍均分成Ni個離散的取值點{par1,par2,…,parNi}

為控制參數pari配備一個候選動作個數為Ni的學習自動機LAi，該自動機每個候選動作的概率為1/Ni

While 結束條件不滿足時

利用輪轉法得到某個候選動作的概率aactive

根據候選動作概率aactive得到對應的控制參數值paractive

將控制參數的值paractive代入差分進化算法中

If 種群中適應度改善的個體總數超出閾值

按照式(3)獎勵aactive，相應地懲罰其他的候選動作概率

Else

按照式(4) 懲罰aactive，相應地獎勵其他的候選動作概率

End if

End while

3 基于IHS的連通覆蓋算法

對于傳感器網絡的連通覆蓋問題，將其轉化為目標優化問題，采用本文提出的IHS算法進行求解。

3.1 問題編碼

種群中的每個個體代表要求解問題的一個候選解，本文染色體編碼示意圖如圖1所示。

圖1 染色體編碼示意

其中，染色體中每個位置posi為第i個候選位置里放置傳感器節點的狀態，0為未放置節點，1為放置節點。

3.2 適應度函數設計

針對在滿足k覆蓋和c連通條件的基礎上使得在給定的候選位置上網絡部署的傳感器節點數目最少問題。本文優化的3個目標分別為

其中，

S為選擇的部署位置的個數，即部署的傳感器節點總數。

對于F1,F2和F3這三個優化目標，采用加權的方法將多目標轉化為單目標函數進行適應度評價。即

F=λ1×f1+λ2×f2+λ3×f3

4 基于貪婪算法的連通覆蓋算法

為了驗證提出的IHS的連通覆蓋算法的性能，提出一種基于貪婪算法的連通覆蓋算法作為比較算法。貪婪算法的主要步驟為：

1)對算法運行所需的參數進行初始化，包括候選位置posj(j=1,2,…,M)和監測目標ti(i=1,2,…,W)的信息，覆蓋度要求k和連通度要求c，以及放置在每個候選位置posj(j=1,2,…,M)的節點sj的coveri,j和connecti,j的值，|connecti,j|的初值為1并設置一個存放結果的集合R={}。

2)對每個候選位置posj(j=1,2,…,M)計算|covi,j|×|coni,j|/costj的值,并進行排序。

3)當存在監測目標ti(i=1,2,…,W)不滿足k覆蓋和部署節點不滿足c連通的條件時，選擇具有最大值的|coveri,j|×|connecti,j|/costj候選位置posj，并將 放入集合R中，即R=R∪{posj}。

4)將posj從候選位置去除，繼續執行步驟(3)，否則，執行步驟(5)。

5)返回集合R。

5 仿真分析

5.1 仿真參數設置

假設在200 m×200 m區域內隨機分布75個監測目標，有400個候選位置可以放置傳感器節點，每個部署位置的代價為[1,10]之間的隨機數。傳感器節點的感知半徑均為40 m，通信半徑為80 m。對于候選位置的設置，本文設置2個場景，場景1為候選位置在部署區域內隨機分布；場景2為將部署區域劃分成10 m×10 m小方格，候選位置為每個小方格的中心點。和聲搜索算法中種群數目為50，HMCR為0.8，PAR為0.4，迭代次數為400，其他參數設置同文獻[15]；IHS算法參數的設置為HMCR的取值范圍為[0.6,0.8]，PAR的取值范圍為[0.05,0.3]，以0.05為間距，將取值區間分別劃分為5個和6個離散的值。學習自動機的參數a=b=0.01。

為驗證改進算法IHS算法的性能，下面設計了一系列實驗，每一個實驗的實驗結果均為50次實驗結果的平均值。

5.2 仿真結果與分析

1)適應度比較

為比較改進算法IHS和原始HS算法的性能，對兩種算法分別在預設的兩種情景求解過程中的平均適應度進行比較。算法的參數同3.1節設置，k和c分別設為2和2。結果如圖2所示。從圖中可以看出，隨著迭代次數的增加，原始HS算法和IHS算法都逐漸趨于收斂，且IHS算法的適應度優于原始HS算法，證明了IHS算法改進方案的有效性。

圖2 二種場景算法平均適應度比較

2)與其他算法性能比較

在傳感器網絡連通覆蓋優化問題上，將本文提出的IHS算法、貪婪算法和原始的HS算法分別在情景1和情景2兩種情景下進行實驗仿真，算法中的可放置節點候選位置數目為200，得到的仿真結果如圖3所示。其中，橫坐標(k,c)表示覆蓋度和連通度要求。從這兩個圖中可以看出，在相同的覆蓋和連通要求的條件下，改進算法IHS均優于原始HS算法和提出的貪婪算法，證明了算法的有效性。

圖3 二種場景中不同的覆蓋和連通條件下算法性能比較

6 結 論

本文提出了一種解決在給定位置集合中選擇代價最小的位置來部署傳感器節點達到容錯部署目標的算法。下一步的工作在于，將節點的異構性引入部署算法中，對異構條件下的節點的容錯部署算法進行研究。