李 明， 胡江平

(1.重慶工商大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院 檢測控制集成系統(tǒng)工程實(shí)驗(yàn)室,重慶 400067;2.電子科技大學(xué) 自動化工程學(xué)院, 四川 成都 611731)

0 引 言

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

針對這些問題，本文提出了一種最小部署代價的容錯部署算法。該算法在考慮到部署位置不同具有不同的部署的代價、監(jiān)測目標(biāo)的多重覆蓋和部署節(jié)點(diǎn)的多重連通的條件下，以部署代價最小為優(yōu)化目標(biāo)，利用改進(jìn)的和聲搜索算法IHS來布置傳感器節(jié)點(diǎn)，達(dá)到增強(qiáng)網(wǎng)絡(luò)服務(wù)質(zhì)量的目的。

1 問題模型分析

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

1.1 節(jié)點(diǎn)感知模型和連通模型

本文采用布爾感知模型。即若目標(biāo)ti與節(jié)點(diǎn)si的距離小于節(jié)點(diǎn)si的感知半徑，則認(rèn)為目標(biāo)ti被節(jié)點(diǎn)si覆蓋，則認(rèn)為節(jié)點(diǎn)si和節(jié)點(diǎn)sj是連通的。

定義1k覆蓋:指在監(jiān)測區(qū)域中，每個監(jiān)測目標(biāo)ti(i=1,2,…,W)都至少被k個傳感器節(jié)點(diǎn)所覆蓋。

定義2c連通:指部署區(qū)域中，每個傳感器節(jié)點(diǎn)都至少與c個傳感器節(jié)點(diǎn)連通。

1.2 問題描述

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

(1)

(2)

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

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

2 改進(jìn)的和聲搜索算法

2.1 和聲搜索算法

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

針對原始和聲搜索算法的存在的缺點(diǎn)，結(jié)合學(xué)習(xí)自動機(jī)的學(xué)習(xí)能力，本文提出了一種基于改進(jìn)和聲搜索算法IHS解決本文的連通覆蓋問題。

2.2 學(xué)習(xí)自動機(jī)基本原理

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

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

(3)

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

(4)

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

2.3 改進(jìn)和聲搜索IHS算法

原始和聲搜索算法中參數(shù)HMCR和PAR的取值是一組固定的參數(shù)，無法滿足算法性能對控制參數(shù)的特殊要求。本文提出一種基于學(xué)習(xí)自動機(jī)的參數(shù)自適應(yīng)的和聲搜索進(jìn)化算法。

輸入：控制參數(shù)pari

輸出：經(jīng)過學(xué)習(xí)自動機(jī)優(yōu)化的控制參數(shù)pari

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

為控制參數(shù)pari配備一個候選動作個數(shù)為Ni的學(xué)習(xí)自動機(jī)LAi，該自動機(jī)每個候選動作的概率為1/Ni

While 結(jié)束條件不滿足時

利用輪轉(zhuǎn)法得到某個候選動作的概率aactive

根據(jù)候選動作概率aactive得到對應(yīng)的控制參數(shù)值paractive

將控制參數(shù)的值paractive代入差分進(jìn)化算法中

If 種群中適應(yīng)度改善的個體總數(shù)超出閾值

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

Else

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

End if

End while

3 基于IHS的連通覆蓋算法

對于傳感器網(wǎng)絡(luò)的連通覆蓋問題，將其轉(zhuǎn)化為目標(biāo)優(yōu)化問題，采用本文提出的IHS算法進(jìn)行求解。

3.1 問題編碼

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

圖1 染色體編碼示意

其中，染色體中每個位置posi為第i個候選位置里放置傳感器節(jié)點(diǎn)的狀態(tài)，0為未放置節(jié)點(diǎn)，1為放置節(jié)點(diǎn)。

3.2 適應(yīng)度函數(shù)設(shè)計(jì)

針對在滿足k覆蓋和c連通條件的基礎(chǔ)上使得在給定的候選位置上網(wǎng)絡(luò)部署的傳感器節(jié)點(diǎn)數(shù)目最少問題。本文優(yōu)化的3個目標(biāo)分別為

其中，

S為選擇的部署位置的個數(shù)，即部署的傳感器節(jié)點(diǎn)總數(shù)。

對于F1,F2和F3這三個優(yōu)化目標(biāo)，采用加權(quán)的方法將多目標(biāo)轉(zhuǎn)化為單目標(biāo)函數(shù)進(jìn)行適應(yīng)度評價。即

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

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

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

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

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

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

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

5)返回集合R。

5 仿真分析

5.1 仿真參數(shù)設(shè)置

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

為驗(yàn)證改進(jìn)算法IHS算法的性能，下面設(shè)計(jì)了一系列實(shí)驗(yàn)，每一個實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果均為50次實(shí)驗(yàn)結(jié)果的平均值。

5.2 仿真結(jié)果與分析

1)適應(yīng)度比較

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

圖2 二種場景算法平均適應(yīng)度比較

2)與其他算法性能比較

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

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

6 結(jié) 論

本文提出了一種解決在給定位置集合中選擇代價最小的位置來部署傳感器節(jié)點(diǎn)達(dá)到容錯部署目標(biāo)的算法。下一步的工作在于，將節(jié)點(diǎn)的異構(gòu)性引入部署算法中，對異構(gòu)條件下的節(jié)點(diǎn)的容錯部署算法進(jìn)行研究。