基于改進(jìn)蟻群算法的無線傳感器網(wǎng)絡(luò)柵欄覆蓋優(yōu)化研究*

毛科技，方 凱，戴國勇，金洪波，鄔錦彬，陳慶章

基于改進(jìn)蟻群算法的無線傳感器網(wǎng)絡(luò)柵欄覆蓋優(yōu)化研究*

毛科技，方 凱，戴國勇，金洪波，鄔錦彬，陳慶章*

（浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州310023）

在無線傳感器網(wǎng)絡(luò)柵欄覆蓋研究中，如何調(diào)度已部署的傳感器節(jié)點(diǎn)構(gòu)建柵欄并延長網(wǎng)絡(luò)生存時(shí)間已成為熱點(diǎn)問題。研究了滿足Poisson分布的靜態(tài)無線傳感器網(wǎng)絡(luò)強(qiáng)K-柵欄覆蓋問題。將部署區(qū)域劃分為a個(gè)子區(qū)域，相鄰子區(qū)域之間形成一定的緩沖區(qū)域，在每個(gè)子區(qū)域利用偏離角蟻群算法構(gòu)建多重柵欄。最后通過調(diào)度算法延長柵欄生存時(shí)間。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的收斂速度快且柵欄生存時(shí)間長等特點(diǎn)。

無線傳感器網(wǎng)絡(luò)；蟻群算法；生存時(shí)間；區(qū)域劃分；緩沖區(qū)域

覆蓋是無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）領(lǐng)域研究的重要問題，柵欄覆蓋（barrier coverage）是WSN中廣泛使用的覆蓋模型之一，其主要研究當(dāng)監(jiān)測目標(biāo)試圖穿越無線傳感器網(wǎng)絡(luò)部署區(qū)域時(shí)能被高效檢測問題。目前柵欄覆蓋技術(shù)得到了廣泛的應(yīng)用，如在生態(tài)方面，將柵欄部署在自然保護(hù)區(qū)邊界可防止外來物種入侵。在林業(yè)保護(hù)方面，將柵欄部署在森林火災(zāi)區(qū)域邊緣，可有動(dòng)態(tài)檢測火災(zāi)蔓延情況。在環(huán)保方面，將柵欄部署在工廠周圍檢測污染物質(zhì)的擴(kuò)散等［1-2］。

柵欄覆蓋在檢測對象、部署區(qū)域、部署方式等多個(gè)方面與傳統(tǒng)覆蓋（點(diǎn)覆蓋、區(qū)域覆蓋）相比具有較大的差別［3］。首先部署區(qū)域是狹長區(qū)域，不要求傳感器覆蓋整個(gè)部署區(qū)域，但需要傳感器間能相互合作形成橫穿部署區(qū)域的柵欄。其次柵欄的部署方式也比較特殊，有正態(tài)隨機(jī)部署、Poisson部署，還有Anwar Saipulla［3］等人提出的line-based部署方式等。根據(jù)部署區(qū)域的環(huán)境，采用不同的部署方法，如在比較方便部署的區(qū)域，可以人為的部署傳感器節(jié)點(diǎn)，此方法構(gòu)建的網(wǎng)絡(luò)比較合理。而在環(huán)境比較惡劣的情況下，節(jié)點(diǎn)可能隨機(jī)的撒向部署區(qū)域，所以節(jié)點(diǎn)的位置并不確定，因此有效的柵欄構(gòu)建算法至關(guān)重要，算法的有效性能增加?xùn)艡跇?gòu)建的數(shù)量，提高傳感器網(wǎng)絡(luò)資源的利用率。

目前對靜態(tài)無線傳感器網(wǎng)絡(luò)柵欄覆蓋的研究已經(jīng)取得了豐厚的成果。Kumar［4］等人首次提出了強(qiáng)K-柵欄覆蓋和弱K-柵欄覆蓋的概念，并設(shè)計(jì)出了判斷部署區(qū)域是否被強(qiáng)K-柵欄覆蓋的算法，以及推導(dǎo)出隨機(jī)部署的傳感器網(wǎng)絡(luò)中存在弱K-柵欄覆蓋的臨界條件。Anwar Saipulla［3］等人又提出了基于權(quán)重有向圖的最大流算法，尋找靜態(tài)無線傳感器網(wǎng)絡(luò)中強(qiáng)柵欄數(shù)量的極限。Habib Mostafaei［5］等人提出了一種分布式的自學(xué)習(xí)算法研究靜態(tài)無線傳感器網(wǎng)絡(luò)強(qiáng)K-柵欄覆蓋問題。Kumar［6］等人還研究了當(dāng)傳感器節(jié)點(diǎn)的生存時(shí)間相同和生存時(shí)間不同這兩種情況下構(gòu)建柵欄的算法以及如何調(diào)度有限的柵欄形成強(qiáng)K-柵欄，延長網(wǎng)絡(luò)的生存時(shí)間，提出了Optimal Sleep-Wakeup算法。Jie Tian［7］等人提出了二維的K-柵欄覆蓋問題，并將部署區(qū)域劃分為多個(gè)子區(qū)域構(gòu)建柵欄的思想。Lei Li和Baoxian Zhang［8］等人研究了弱柵欄覆蓋問題，并分析了弱柵欄的覆蓋率。Balister［2；9］等人研究了可靠的節(jié)點(diǎn)部署密度估計(jì)方法，使得按照密度的估計(jì)值進(jìn)行隨機(jī)部署的傳感器網(wǎng)絡(luò)可以形成1-柵欄覆蓋，并且是s-t連通的。

本文通過分析無線傳感器網(wǎng)絡(luò)柵欄部署的特點(diǎn)，將傳統(tǒng)蟻群算法做出相應(yīng)的改進(jìn)，使之適用于柵欄部署問題。改進(jìn)后的蟻群算法不僅加快了算法的收斂速度而且很好的解決了算法局部最優(yōu)問題。同時(shí)為了有序的構(gòu)建柵欄且提高蟻群算法構(gòu)建柵欄的效率，本文將部署區(qū)域劃分為若干子區(qū)域，相鄰子區(qū)域間設(shè)立一定寬度的緩沖區(qū)域。利用緩沖區(qū)域解決相鄰子區(qū)域邊界柵欄構(gòu)建的沖突問題。最后采用最佳調(diào)度算法延長柵欄的生存時(shí)間。

1 系統(tǒng)模型

1.1 相關(guān)定義

定義1 穿越路徑（Crossing Path）檢測目標(biāo)的起點(diǎn)和終點(diǎn)在監(jiān)測區(qū)域A的上下邊界，且在區(qū)域A內(nèi)起點(diǎn)和終點(diǎn)間的任意曲線稱為穿越路徑。

定義2 強(qiáng)K-柵欄覆蓋（strong k-barrier coverage）當(dāng)監(jiān)測目標(biāo)沿任意穿越路徑穿越部署區(qū)域A時(shí)至少能被k個(gè)傳感器節(jié)點(diǎn)感知，則稱區(qū)域A為強(qiáng)K-柵欄覆蓋。

定義3 交叉強(qiáng)K-柵欄覆（intersectional strong k-barrier coverage）首先滿足定義2，即在監(jiān)測目標(biāo)沿穿越路徑穿越部署區(qū)域時(shí)至少能被k個(gè)傳感器節(jié)點(diǎn)感知到。其次存在無公共傳感器節(jié)點(diǎn)的相交柵欄，則稱區(qū)域A為交叉強(qiáng)K-柵欄覆蓋。

定義4 部署方向 部署傳感器過程中，在部署區(qū)域A內(nèi)從已部署傳感器節(jié)點(diǎn)區(qū)域指向未部署傳感器節(jié)點(diǎn)區(qū)域的方向。

定義5 偏離角 形成同一柵欄的兩個(gè)相鄰的傳感器節(jié)點(diǎn)的連線與部署方向所成的夾角。

二元感知模型：在平面上任意一點(diǎn)m，節(jié)點(diǎn)n能感知到點(diǎn)m的概率為

式（1）中，Dis（n,m）為點(diǎn)n和m間的歐式距離，R為感知半徑。

本文的研究基于傳感器的二元感知模型，傳感器感知范圍是一個(gè)以傳感器節(jié)點(diǎn)為圓心，感知半徑為半徑的圓。為形象說明定義2、定義3，現(xiàn)假設(shè)監(jiān)測區(qū)域A為2-柵欄覆蓋，則區(qū)域A中至少存在2條無公共節(jié)點(diǎn)的柵欄。當(dāng)監(jiān)測目標(biāo)試圖穿越部署區(qū)域時(shí)至少會被這2條柵欄感知到。這2條柵欄的狀態(tài)可能相交也可能不相交。強(qiáng)K-柵欄覆蓋如圖1所示，交叉強(qiáng)K-柵欄覆蓋如圖2所示。從圖2可以看出即使柵欄在相交的情況下，當(dāng)有監(jiān)測目標(biāo)沿任意路徑穿越部署區(qū)域時(shí)依然能被至少k個(gè)傳感器感知到。因此交叉強(qiáng)K-柵欄屬于強(qiáng)K-柵欄。本文提出的算法構(gòu)建的K-柵欄包括交叉強(qiáng)K-柵欄。

圖1 強(qiáng)2-柵欄覆蓋示意圖

圖2 交叉強(qiáng)2-柵欄覆蓋示意圖

1.2 緩沖區(qū)域劃分模型

部署區(qū)域?yàn)殚Ll、寬h的矩形。記該區(qū)域?yàn)锳。以部署區(qū)域左下角為坐標(biāo)原點(diǎn)o（0,0）建立坐標(biāo)系。假設(shè)節(jié)點(diǎn)位置已通過GPS或者節(jié)點(diǎn)定位技術(shù)獲知，所以節(jié)點(diǎn)i在部署區(qū)域的位置坐標(biāo)可表示為ni（xi,yi），節(jié)點(diǎn)的數(shù)量為M 。節(jié)點(diǎn)感知半徑為R。在靜態(tài)無線傳感器網(wǎng)絡(luò)中構(gòu)建K-柵欄時(shí)，我們將部署區(qū)域A均勻的劃分為k等份，表示為A=Group（A1,A2,A3,…,AK）。每個(gè)子區(qū)域 Ai的寬為Wa=h/k，子區(qū)域Ai的長和部署區(qū)域A相同。

本文利用基于偏離角的蟻群算法為每個(gè)子區(qū)域Ai構(gòu)建柵欄。然而強(qiáng)硬的將部署區(qū)域A分割成k個(gè)子區(qū)域會造成一定程度上資源的浪費(fèi)。如圖3中很多傳感器節(jié)點(diǎn)靠近子區(qū)域Ai的上下邊界，并不能在子區(qū)域Ai構(gòu)建柵欄的過程中被應(yīng)用，但是在子區(qū)域Ai+1或Ai-1構(gòu)建柵欄過程中所需要。針對上述問題，本文提出了緩沖區(qū)域分割方法。該方法對部署區(qū)域劃分不再是用線條強(qiáng)硬的分割，而是采用緩沖帶對部署區(qū)域A進(jìn)行分割。具體分割方法如圖4所示，緩沖帶寬度為Wb。蟻群算法在構(gòu)建柵欄的過程中優(yōu)先選擇子區(qū)域Ai內(nèi)的傳感器節(jié)點(diǎn)，當(dāng)Ai內(nèi)不存在滿足條件的節(jié)點(diǎn)時(shí)，算法會考慮在緩沖帶內(nèi)是否存在滿足要求的傳感器節(jié)點(diǎn)。緩沖區(qū)節(jié)點(diǎn)被選擇后將被標(biāo)記，下一個(gè)相鄰的子區(qū)域Ai構(gòu)建柵欄時(shí)不會重復(fù)選取該被標(biāo)記的節(jié)點(diǎn)，具體過程如圖5所示。

圖3 部署區(qū)域劃分圖

圖4 緩沖分割法示意圖

圖5 緩沖帶柵欄構(gòu)建圖

使用緩沖分割方法將部署區(qū)域劃分為k個(gè)子區(qū)域需要k-1條緩沖帶，表示為Buffer（b1,b2,b3,…,bk-1）。每個(gè)子區(qū)域Ai的寬度也發(fā)生變化，其中A1、Ak的寬為Wa=h/k-Wb/2，其余子區(qū)域的寬為Wa=h/k-Wb。

2 蟻群算法構(gòu)建柵欄

2.1 基本蟻群算法介紹

蟻群算法來源于螞蟻覓食的優(yōu)化方式，蟻群系統(tǒng)是分布式的生物系統(tǒng)，螞蟻之間相互協(xié)作能完成單個(gè)螞蟻無法完成的艱巨任務(wù)［10］。

式（2），啟發(fā)信息ηij（t）=1/dij，dij表示城市i、j間的距離。allowedk=City-Tabuk表示螞蟻k下一步允許選擇的城市。α、β分別表示信息素濃度和啟發(fā)信息的重要程度。當(dāng)所有城市都被螞蟻遍歷一次，即完成一次迭代。接著需要對各城市間路徑的信息素更新，更新規(guī)則如下式：

式中：ρ表示信息素?fù)]發(fā)系數(shù)，ρ∈（0,1），經(jīng)過一次迭代，路徑b（i,j）上的信息素會按系數(shù) ρ揮發(fā)，從而防止蟻群算法早熟。

式（4）表示m只螞蟻經(jīng)過路徑b（i,j）時(shí)留下的信息素總和。

式（5）中Q表示一只螞蟻?zhàn)疃嗄茚尫诺男畔⑺亓?，Lk表示螞蟻k在本次迭代中走過的路徑長度。

上述為蟻群算法的一次迭代過程，當(dāng)算法多次迭代后，某條路徑上的信息素趨于穩(wěn)定，而其他路徑上信息素非常少。最后會選出最優(yōu)路徑［11］。

2.2 蟻群算法改進(jìn)

第1.2節(jié)將部署區(qū)域A劃分成K個(gè)子區(qū)域，本節(jié)對子區(qū)域Ai設(shè)計(jì)蟻群算法構(gòu)建柵欄。然而傳統(tǒng)的蟻群算法存在收斂速度慢，計(jì)算量大，易陷入局部最優(yōu)等問題［12-13］，并不適用于存在大量節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)柵欄部署問題。而且部署區(qū)域A是個(gè)狹長的區(qū)域，傳統(tǒng)的蟻群算法在這種情況下極易陷入局部最優(yōu)問題。為有效解決上述問題，我們從限制螞蟻的移動(dòng)能力以及啟發(fā)因子兩個(gè)方面改進(jìn)，使之適用于無線傳感器網(wǎng)絡(luò)柵欄部署。

2.2.1 限制螞蟻移動(dòng)能力

圖6 節(jié)點(diǎn)間距離示意圖

在強(qiáng)柵欄中相鄰傳感器節(jié)點(diǎn)間的感知范圍存在重疊部分。為構(gòu)建強(qiáng)柵欄，我們將蟻群算法中螞蟻的移動(dòng)能力限制在2R以內(nèi)，即節(jié)點(diǎn)間存在邊s∈E，以確保蟻群算法構(gòu)建的柵欄是強(qiáng)柵欄。

2.2.2 啟發(fā)因子改進(jìn)

①能見度

在傳統(tǒng)蟻群算法解決TSP問題中，能見度為ηij（t）=1/dij。因?yàn)樵赥SP問題中希望尋找到一條經(jīng)過所有城市的最短路徑，因此螞蟻選擇下個(gè)城市

因此對能見度做如下改進(jìn)：

式中：die表示當(dāng)前節(jié)點(diǎn)到部署區(qū)域A右邊界的距離，die=l-xi，其中xi為節(jié)點(diǎn)i的橫坐標(biāo)。如圖7所示。

圖7 能見度改進(jìn)圖

②偏離角度

式中：偏離角θ∈（0,π）。狀態(tài)轉(zhuǎn)移概率Pkij（t）做如下

更改：

式（8）中ε表示角度啟發(fā)信息γij（t）的重要程度。

圖8 偏離角度圖

圖9 柵欄構(gòu)建示意圖

2.3 柵欄構(gòu)建過程及調(diào)度算法

2.3.1 改進(jìn)的蟻群算法構(gòu)建柵欄

改進(jìn)后的蟻群算法適用于WSN柵欄部署問題，本小節(jié)介紹如何用改進(jìn)后的蟻群算法對子區(qū)域Ai構(gòu)建柵欄。強(qiáng)柵欄要求柵欄左右兩端節(jié)點(diǎn)的感知圓與部署區(qū)域左右邊界有交叉，即傳感器節(jié)點(diǎn)橫坐標(biāo)xi≤R或xi≥l-R，如圖9所示。假設(shè)節(jié)點(diǎn)感知圓與部署子區(qū)域 Ai左邊界相交的節(jié)點(diǎn)數(shù)量為s1、與部署子區(qū)域Ai右邊界相交的節(jié)點(diǎn)數(shù)量為s2，則在部署區(qū)域 Ai中能構(gòu)建的柵欄數(shù) barrier≤min（s1,s2）。當(dāng)s1＜s2則蟻群算法的螞蟻出發(fā)節(jié)點(diǎn)為與左邊界相交的某個(gè)節(jié)點(diǎn)開始，如圖中Start L表示螞蟻從左邊界出發(fā)的節(jié)點(diǎn)。當(dāng)螞蟻從部署區(qū)域A的一邊搜尋到另一邊，但還是沒有達(dá)到終止條件時(shí)，會繼續(xù)反方向搜尋，直到滿足終止條件。蟻群算法總共迭代次數(shù)為N，螞蟻數(shù)量為m。改進(jìn)后蟻群算法搜尋柵欄的迭代過程如圖10所示。

圖10 迭代過程

2.3.2 柵欄調(diào)度算法

在WSN柵欄覆蓋中節(jié)點(diǎn)調(diào)度算法已被普遍使用。根據(jù)需要喚醒或休眠傳感器節(jié)點(diǎn)，使得網(wǎng)絡(luò)生存時(shí)間得以延長是調(diào)度算法的主要作用。在文獻(xiàn)［6］中提出了最佳調(diào)度算法。該算法使得柵欄的生存時(shí)間被充分利用，不存在資源的浪費(fèi)。本文基于文獻(xiàn)［6］的最佳調(diào)度算法，結(jié)合1.2小節(jié)提出的緩沖區(qū)域劃分方法，給出了本文的柵欄調(diào)度算法。該方法如下：當(dāng)每個(gè)子區(qū)域Ai中構(gòu)建的柵欄數(shù)量相同，則在每個(gè)子區(qū)域Ai中各喚醒一條柵欄，形成K-柵欄，其他節(jié)點(diǎn)進(jìn)入休眠模式節(jié)約電量。如果每個(gè)子區(qū)域Ai的柵欄數(shù)量不同，則調(diào)度方法比較復(fù)雜，具體調(diào)度方法如圖11所示。

圖11 調(diào)度算法圖

3 仿真實(shí)驗(yàn)

本文實(shí)驗(yàn)的硬件平臺采用core i3 CPU、2.3-GHz、4G RAM的計(jì)算機(jī)。實(shí)驗(yàn)的軟件平臺采用MATLAB8.1。仿真實(shí)驗(yàn)中部署區(qū)域A為100 m×2 km的矩形區(qū)域。傳感器節(jié)點(diǎn)采用二元圓形感知模型，所有傳感器節(jié)點(diǎn)感知半徑相同且為R。節(jié)點(diǎn)在部署區(qū)域A中滿足Poisson分布，且傳感器節(jié)點(diǎn)無移動(dòng)能力。實(shí)驗(yàn)中改進(jìn)的蟻群算法的相關(guān)參數(shù)設(shè)置如下：α=1.0、β=2.0、ε=2.0、總信息量Q=100、揮發(fā)系數(shù) ρ= 0.5。下文的實(shí)驗(yàn)結(jié)果都是20次隨機(jī)實(shí)驗(yàn)的平均值。

3.1 傳感器節(jié)點(diǎn)自身因素對構(gòu)建柵欄的影響

當(dāng)部署的傳感器節(jié)點(diǎn)數(shù)量增加，能構(gòu)建的柵欄數(shù)量也相應(yīng)的會增加。本次仿真實(shí)驗(yàn)研究改進(jìn)的蟻群算法在不同傳感器節(jié)點(diǎn)數(shù)量的情況下構(gòu)建柵欄數(shù)量。傳感器節(jié)點(diǎn)數(shù)量從400增加到1 400，每次以200個(gè)節(jié)點(diǎn)為梯度增加。傳感器的感知半徑R=30 m。實(shí)驗(yàn)結(jié)果如圖12所示，從實(shí)驗(yàn)結(jié)果可以看出部署傳感器節(jié)點(diǎn)的數(shù)量和構(gòu)建的柵欄數(shù)量呈正相關(guān)。因?yàn)樵诓渴饏^(qū)域一定的情況下部署傳感器節(jié)點(diǎn)的數(shù)量越多，則傳感器節(jié)點(diǎn)間感知范圍存在重疊的概率也就越大，因此能構(gòu)建更多的強(qiáng)柵欄。

圖12 節(jié)點(diǎn)數(shù)量和柵欄數(shù)量關(guān)系圖

傳感器節(jié)點(diǎn)的感知半徑R對柵欄構(gòu)建至關(guān)重要，首先在不同感知半徑R情況下，傳感器節(jié)點(diǎn)數(shù)量從400增加到1 400，每次以200個(gè)節(jié)點(diǎn)為梯度增加，利用改進(jìn)的蟻群算法構(gòu)建柵欄。實(shí)驗(yàn)結(jié)果如圖13所示。其次研究在傳感器數(shù)量一定的情況下，不同感知半徑R對改進(jìn)的蟻群算法構(gòu)建柵欄數(shù)量的影響。實(shí)驗(yàn)中傳感器節(jié)點(diǎn)數(shù)量Num=500，實(shí)驗(yàn)結(jié)果如圖14所示。

從圖13、圖14可以看出當(dāng)傳感器節(jié)點(diǎn)數(shù)量和部署區(qū)域面積都確定的情況下，傳感器的感知半徑R越大，構(gòu)建的柵欄數(shù)量也越多。因?yàn)楦兄霃絉越大，傳感器節(jié)點(diǎn)感知范圍存在重疊的概率也越大，因此在實(shí)驗(yàn)中隨著感知半徑R增大，構(gòu)建的柵欄數(shù)量也相應(yīng)增加，并且從實(shí)驗(yàn)結(jié)果可知感知半徑R與構(gòu)建柵欄的數(shù)量呈正相關(guān)。

圖13 不同感知半徑關(guān)系圖

圖14 感知半徑與柵欄數(shù)量關(guān)系圖

3.2 改進(jìn)后蟻群算法與傳統(tǒng)蟻群算法比較

本實(shí)驗(yàn)將改進(jìn)后的蟻群算法和普通蟻群算法相比較。首先比較兩種算法構(gòu)建柵欄的長度，兩種算法都在部署區(qū)域A內(nèi)構(gòu)建一條柵欄，在相同傳感器數(shù)量的情況下實(shí)驗(yàn)結(jié)果如圖15所示。從圖5中可以看出改進(jìn)后的算法能構(gòu)建更短的柵欄。

圖15 柵欄長度比較圖

因?yàn)閭鹘y(tǒng)的蟻群算法更傾向于選擇距離比較近的節(jié)點(diǎn)作為下一個(gè)待選節(jié)點(diǎn)而不顧及節(jié)點(diǎn)是否更適合構(gòu)建柵欄，因此容易陷入局部最優(yōu)問題，但是改進(jìn)后的蟻群算法結(jié)合了偏離部署方向的角度和距離部署邊界的距離，因此選擇的下一個(gè)節(jié)點(diǎn)更適合構(gòu)建柵欄，且不會陷入局部最優(yōu)問題。所以改進(jìn)后的蟻群算法比傳統(tǒng)的蟻群算法能構(gòu)建更短的柵欄。

其次比較兩種算法收斂時(shí)需要迭代的次數(shù)。同樣在相同傳感器數(shù)量的情況下實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖16所示。我們希望能在部署區(qū)域兩邊界間構(gòu)建比較直的柵欄而非彎曲的柵欄，因此改進(jìn)后的蟻群算法優(yōu)先選擇偏離角度小的節(jié)點(diǎn)，當(dāng)待選節(jié)點(diǎn)的偏離角度過大時(shí)算法能盡早排除。所以改進(jìn)后的蟻群算法能大幅度減少迭代次數(shù)，提高蟻群算法構(gòu)建柵欄的效率。

圖16 迭代次數(shù)對比圖

實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)后的蟻群算法不管在收斂速度還是在尋找最短路徑方面都優(yōu)于傳統(tǒng)的蟻群算法。

本次實(shí)驗(yàn)研究改進(jìn)的蟻群算法在部署區(qū)域A中構(gòu)建一條最短柵欄需要傳感器節(jié)點(diǎn)的數(shù)量。實(shí)驗(yàn)中傳感器節(jié)點(diǎn)數(shù)量從100增加至400，每次以50個(gè)節(jié)點(diǎn)為梯度遞增。傳感器感知半徑R=60。最后利用普通蟻群算法、最佳部署方法做比較。其中最佳部署方法構(gòu)建一條柵欄需要的節(jié)點(diǎn)數(shù)量Num=■ ■l/2R。實(shí)驗(yàn)結(jié)果如圖17所示。改進(jìn)后的蟻群算法構(gòu)建一條柵欄所需要的傳感器節(jié)點(diǎn)數(shù)量比傳統(tǒng)的蟻群算法少。因?yàn)閺纳蟼€(gè)實(shí)驗(yàn)可以知道改進(jìn)后蟻群算法不會陷入局部最優(yōu)問題，在相同條件下能構(gòu)建更短的柵欄，所以構(gòu)建一條柵欄所需要的傳感器節(jié)點(diǎn)數(shù)量會比傳統(tǒng)蟻群算法需要的更少。且當(dāng)部署區(qū)域內(nèi)節(jié)點(diǎn)數(shù)量增加時(shí)，構(gòu)建一條柵欄需要的節(jié)點(diǎn)數(shù)量相應(yīng)減少，因?yàn)楫?dāng)節(jié)點(diǎn)數(shù)量增加，有更大的機(jī)會構(gòu)建更短更直的柵欄，所以構(gòu)建一條柵欄需要的傳感器節(jié)點(diǎn)數(shù)量減少。

圖17 節(jié)點(diǎn)數(shù)量圖

3.3 柵欄生存時(shí)間比較

本次實(shí)驗(yàn)設(shè)立寬為20 m的緩沖帶將部署區(qū)域A劃分為兩個(gè)子區(qū)域A1、A2。在區(qū)域A中部署傳感器節(jié)點(diǎn)的數(shù)量從200增至1 400，以200為梯度遞增。傳感器的感知半徑R=30，假設(shè)傳感器節(jié)點(diǎn)的生存時(shí)間相同且為1 680 h（10周）。實(shí)驗(yàn)選取最大流算法、基本的蟻群算法、RIS［4］算法構(gòu)建柵欄，并與改進(jìn)的蟻群算法（Improve-ACO）比較，最后通過最佳調(diào)度算法比較不同算法構(gòu)建的強(qiáng)2-柵欄生存時(shí)間。其中本文給出的結(jié)合區(qū)域劃分方法的最佳調(diào)度算法如圖10所示。

實(shí)驗(yàn)結(jié)果如圖18所示。實(shí)驗(yàn)中選取的最大流算法結(jié)合最佳調(diào)度算法是靜態(tài)無線傳感器網(wǎng)絡(luò)柵欄部署的最佳算法。從實(shí)驗(yàn)結(jié)果可以看出本文提出的算法非常接近最佳算法，且網(wǎng)絡(luò)生存時(shí)間比RIS算法長很多。因?yàn)楸疚牡乃惴ㄍㄟ^合理的劃分與調(diào)度，能有序的構(gòu)建柵欄，而不是隨機(jī)的激活柵欄，從而能延長柵欄的生存時(shí)間。而且從上面的實(shí)驗(yàn)我們可以知道改進(jìn)后的蟻群算法在構(gòu)建柵欄方面比傳統(tǒng)蟻群算法優(yōu)秀很多，在相同條件下改進(jìn)的蟻群算法構(gòu)建的柵欄數(shù)量比傳統(tǒng)蟻群算法多，所以根據(jù)柵欄最佳調(diào)度算法，網(wǎng)絡(luò)的生存時(shí)間也會比傳統(tǒng)蟻群算法構(gòu)建的柵欄長。RIS算法是隨機(jī)的激活2條柵欄形成強(qiáng)2-柵欄。該方法具有較大的隨機(jī)性，不能保證已經(jīng)構(gòu)建的所有柵欄被充分利用，因此柵欄的生存時(shí)間大大減少。

圖18 網(wǎng)絡(luò)生存時(shí)間圖

3.4 緩沖區(qū)域?qū)挾葘艡跇?gòu)建的影響

分割部署區(qū)域的緩沖帶寬度Wb對柵欄構(gòu)建存在很大的影響，如果Wb過小，則不能發(fā)揮緩沖帶的作用，如果Wb太大，緩沖帶內(nèi)的傳感器節(jié)點(diǎn)會存在浪費(fèi)現(xiàn)象。本次實(shí)驗(yàn)在部署區(qū)域A內(nèi)部署500個(gè)傳感器節(jié)點(diǎn)，傳感器節(jié)點(diǎn)感知半徑R=30 m，部署區(qū)域被劃分為兩個(gè)子區(qū)域，即A=Group（A1,A2），

緩沖帶寬度Wb從3 m增加到24 m，以3 m為梯度遞增。實(shí)驗(yàn)采用最大流算法與本文方法比較，最大流算法是解決靜態(tài)無線傳感器網(wǎng)絡(luò)柵欄部署問題的最佳算法。實(shí)驗(yàn)結(jié)果如圖19所示。從實(shí)驗(yàn)結(jié)果可得，當(dāng)緩沖帶寬度太小，不能有效的解決子區(qū)域邊界沖突問題。當(dāng)緩沖帶寬度過大，會對傳感器節(jié)點(diǎn)造成一定的浪費(fèi)，同樣對柵欄構(gòu)建不利。只有當(dāng)Wb在8 m左右時(shí)能最好的發(fā)揮緩沖帶的作用，不但能解決兩個(gè)子區(qū)域邊界構(gòu)建柵欄的沖突問題，還能增加傳感器節(jié)點(diǎn)的利用率。但是從實(shí)驗(yàn)結(jié)果我們可以知道利用緩沖區(qū)域結(jié)合改進(jìn)后的蟻群算法構(gòu)建柵欄的數(shù)量和最大流算法還是存在微小的差距，因?yàn)槔镁彌_區(qū)域雖然能一定程度上提高節(jié)點(diǎn)的利用率，但是還是存在一小部分節(jié)點(diǎn)被浪費(fèi)。

圖19 緩沖區(qū)域?qū)挾刃Ч麍D

4 總結(jié)

目前雖然已經(jīng)出現(xiàn)了移動(dòng)節(jié)點(diǎn)，但是由于部署環(huán)境的復(fù)雜性，大部分無線傳感器網(wǎng)絡(luò)都是靜態(tài)網(wǎng)絡(luò)。如何設(shè)計(jì)有效的傳感器柵欄部署算法變的十分關(guān)鍵。本文提出的柵欄構(gòu)建算法和柵欄調(diào)度方法，通過實(shí)驗(yàn)證明了其有效性和可靠性。但是仍然有很多方面存在不足，例如該算法是集中式算法且復(fù)雜度比較高。后續(xù)工作將針對靜態(tài)傳感器網(wǎng)絡(luò)基于本文提出的算法進(jìn)一步研究分布式的K-柵欄構(gòu)建算法。

［1］Chen A，Kumar S，Lai T H.Designing Localized Algorithms for Barrier Coverage［C］//Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking.ACM，2007：63-74.

［2］ 班冬松，溫俊，蔣杰，等.移動(dòng)無線傳感器網(wǎng)絡(luò)k-柵欄覆蓋構(gòu)建算法［J］.Journal of Software，2011，22（9）：2089-2103.

［3］ Saipulla A，Westphal C，Liu B，et al.Barrier Coverage of Line-Based Deployed Wireless Sensor Networks［C］//INFOCOM 2009，IEEE.IEEE，2009：127-135.

［4］ Kumar S，Lai T H，Arora A.Barrier Coverage with Wireless Sensors ［C］//Proceedings of the 11th Annual International Conference on MobileComputingandNetworking.ACM，2005：284-298.

［5］ Mostafaei H，Meybodi M R.An Energy Efficient Barrier Coverage Algorithm for Wireless Sensor Networks［J］.Wireless Personal Communications，2014，77（3）：2099-2115.

［6］ Kumar S，Lai T H，Posner M E，et al.Optimal Sleep-Wakeup Algorithms for Barriers of Wireless Sensors［C］//Broadband Communications，Networks and Systems，2007.BROADNETS 2007.Fourth International Conference on.IEEE，2007：327-336.

［7］ Tian J，Zhang W，Wang G，et al.2D k-Barrier Duty-Cycle Scheduling for Intruder Detection in Wireless Sensor Networks［J］.Computer Communications，2014，43：31-42.

［8］ Li L，Zhang B，Shen X，et al.A Study on the Weak Barrier Coverage Problem in Wireless Sensor Networks［J］.Computer Net-works，2011，55（3）：711-721.

［9］ Balister P，Bollobas B，Sarkar A，et al.Reliable Density Estimates for Coverage and Connectivity in Thin Strips of Finite Length［C］//Proceedings of the 13th annual ACM International Conference on MobileComputingandNetworking.ACM，2007：75-86.

［10］童孟軍，關(guān)華丞.基于蟻群算法的能量均衡多路徑路由算法的研究［J］.傳感技術(shù)學(xué)報(bào)，2013，26（3）：425-434.

［11］李擎，張超，陳鵬，等.一種基于粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法［J］.控制與決策，2013，28（6）：873-878.

［12］鮑榮，潘浩，董齊芬，等.基于信息素?cái)U(kuò)散模型蟻群算法的無線傳感網(wǎng)路由研究［J］.傳感技術(shù)學(xué)報(bào)，2012，24（11）：1644-1648.

［13］楊中秋，張延華.改進(jìn)蟻群算法在交通系統(tǒng)最短路徑問題的研究［J］.現(xiàn)代電子技術(shù)，2009，32（8）：76-78.

［14］Saipulla A，Liu B，Wang J.Barrier Coverage with Airdropped WirelessSensors［C］//Military Communications Conference，2008.MILCOM 2008.IEEE.IEEE，2008：1-7.

［15］Saipulla A，Liu B，Xing G，et al.Barrier Coverage with Sensors of Limited Mobility［C］//Proceedings of the eleventh ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM，2010：201-210.

毛科技（1979-），男，漢族，浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院講師，博士，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)，數(shù)據(jù)挖掘，maokeji@zjut.edu.cn；

戴國勇（1983-），男，講師，博士研究生，主要研究方向是無線傳感器網(wǎng)絡(luò)、網(wǎng)絡(luò)安全等；

方 凱（1992-），男，碩士研究生，主要研究方向是無線傳感器網(wǎng)絡(luò)；

陳慶章（1956-），男，教授，博士生導(dǎo)師，主要研究方向是無線傳感器網(wǎng)絡(luò)、分布式處理與協(xié)同工作等，qzchen@zjut.edu.cn。

Research on Optimization of Barrier Coverage for Wireless Sensor Network Using Improved Ant Colony Algorithm*

MAO Keji，F(xiàn)ANG Kai，DAI Guoyong，JIN Hongbo，WU Jingbin，CHEN Qingzhang*
（Zhejiang University of Technology College of Computer Science&Technology，Hangzhou 310023，China）

Barrier coverage has attracted a lot of interests in the area of wireless sensor networks.Researches mainly focus on building barriers effectively with energy efficiency to prolong the network lifetime.K-barrier coverage problem in static wireless sensor networks is studied.We divide the whole deployment area into sub-regions and barriers are built in each sub-region respectively using improved ant colony algorithm.Buffer zones between any two adjacent sub-regions are considered to effectively utilize those sensors located in near the borders.Furtherly，an optimal schedule algorithm is employed to schedule the built barriers to conserve energy and prolong the network lifetime.Some simulations are conducted and the results show that the proposed algorithm has a good performance.

WSN；ant colony algorithm；lifetime；region division；buffer zone EEACC：7230；6150P；6210C

TP393

A

1004-1699（2015）07-1058-08

10.3969/j.issn.1004-1699.2015.07.020

項(xiàng)目來源：國家自然科學(xué)基金面上項(xiàng)目（61379023）；浙江省公益性技術(shù)應(yīng)用研究計(jì)劃項(xiàng)目（2015C31066）

2015-01-05 修改日期：2015-04-16