葉苗，王宇平，代才，王曉麗

?

無線傳感器網(wǎng)絡(luò)中新的最小暴露路徑問題及其求解算法

葉苗1,2,3,4，王宇平1，代才1，王曉麗1

(1. 西安電子科技大學(xué)計算機學(xué)院，陜西西安 710071；2．桂林理工大學(xué)信息科學(xué)與工程學(xué)院，廣西桂林 541004； 3. 桂林電子科技大學(xué)廣西云安全與云服務(wù)工程技術(shù)研究中心，廣西桂林 541104；4. 陜西師范大學(xué)計算機科學(xué)學(xué)院，陜西西安 710062 )

無線傳感器網(wǎng)絡(luò)中原始的最小暴露路徑問題沒有考慮對路徑的實際限制條件，提出一種要求經(jīng)過某一特別保護區(qū)域部分邊界的最小暴露路徑問題。由于無法建立相應(yīng)的圖模型，原有求解最小暴露路徑問題的經(jīng)典方法（網(wǎng)格法和維諾圖法）對提出的新問題不再起效。先將該問題轉(zhuǎn)化成帶約束條件的優(yōu)化問題，然后針對轉(zhuǎn)化后的數(shù)學(xué)模型高度非線性、高維度而不好用確定性優(yōu)化方法的特點，結(jié)合問題實際背景設(shè)計出混合人工蜂群求解算法。通過在多種情況下的仿真實驗發(fā)現(xiàn)，設(shè)計的帶約束條件優(yōu)化模型和混合人工蜂群求解算法能有效解決提出的最小暴露路徑問題。

無線傳感器網(wǎng)絡(luò)；最小暴露路徑；保護區(qū)域；混合人工蜂群算法

1 引言

無線傳感器網(wǎng)絡(luò)(WSN, wireless sensor networks)由具備感知、數(shù)據(jù)處理以及無線通信功能的大量傳感器節(jié)點組成。因為其具有成本低廉和易于擴展的優(yōu)點，在商業(yè)與軍事領(lǐng)域內(nèi)都得到了廣泛應(yīng)用（如環(huán)境監(jiān)控、地震與氣象預(yù)報、地下與深水探測等）。對WSN的研究與應(yīng)用也已引起了眾多研究者和廠商的高度關(guān)注。

覆蓋是傳感器網(wǎng)絡(luò)的關(guān)鍵性基礎(chǔ)技術(shù)之一，它反映了傳感器網(wǎng)絡(luò)對被監(jiān)測區(qū)域的感知能力。覆蓋質(zhì)量的好壞直接影響著監(jiān)測系統(tǒng)的性能，而它的度量有助于描述出整個網(wǎng)絡(luò)對被監(jiān)測目標（靜止或運動目標）的覆蓋情況，有助于指導(dǎo)傳感器節(jié)點部署的調(diào)整與優(yōu)化。目前，已經(jīng)有很多關(guān)于其覆蓋檢測目標能力的度量的討論[1,2]，基本集中在柵欄覆蓋這類問題的討論上。從被監(jiān)控對象的特征[1]看，傳感器網(wǎng)絡(luò)中的覆蓋問題可以分為區(qū)域覆蓋、掃描覆蓋和柵欄覆蓋。柵欄覆蓋的研究目的就是找到連接起點與終點的一條或多條路徑，使這些路徑在不同覆蓋質(zhì)量定義下提供對移動目標感知/監(jiān)視質(zhì)量的描述?！氨┞洞┰絒2,3]”同時考慮了“目標暴露”的時間因素和傳感器節(jié)點對于目標的“感應(yīng)強度”的空間因素，在數(shù)學(xué)上可以將其表示為感應(yīng)強度在時間上沿穿越路徑的曲線積分，以此來衡量布置的傳感器節(jié)點對暴露路徑的覆蓋質(zhì)量，這種覆蓋模型符合實際環(huán)境[2,3]，是柵欄覆蓋問題中討論最早也是最多的一種度量方式。最小暴露穿越對應(yīng)的路徑稱之為最小暴露路徑，這對應(yīng)了數(shù)學(xué)中極值曲線問題[4]（也是數(shù)學(xué)中泛函極值的變分問題[5]）。數(shù)學(xué)中求解變分問題的常用方法是求解其對應(yīng)的歐拉—拉格朗日微分方程[5]，理論上求解這個微分方程就可以求出這條路徑的精確表達式。但在多傳感器節(jié)點場景下對應(yīng)的歐拉—拉格朗日微分方程高度非線性難于表達更難于求解，因此即使發(fā)現(xiàn)了這一問題的數(shù)學(xué)本質(zhì)[6~8]，還是沒有辦法求出其精確解析，文獻[6]僅僅是給出了在單個傳感器節(jié)點情形下的精確解析解。目前只能討論通常情況下最小暴露路徑問題的近似解。目前解決暴露穿越問題中的近似求解方法主要有基于網(wǎng)格劃分的路徑搜索方法和基于Voronoi圖的計算幾何方法。Meguerdichian等[9]最早基于網(wǎng)格思想設(shè)計出求解暴露穿越問題的方法，該方法先對傳感器區(qū)域進行正方形網(wǎng)格剖分，再根據(jù)節(jié)點分布情況計算網(wǎng)格各邊的暴露度，最后使用Dijkstra算法等最短路徑算法找到一條穿越感知區(qū)域且暴露度最小的路徑；基于Voronoi圖的計算幾何方法是由Veltri和Huang等[10]較早提出，通過使用Voronoi圖分析移動目標下一候選位置點集合，同時將移動對象在某一時間間隔內(nèi)沿路徑移動的暴露度定義為移動對象沿途所收集到的傳感器節(jié)點的感應(yīng)強度。后續(xù)出現(xiàn)了對這2種方法的改進和不同場景下的應(yīng)用：文獻[6,7]將維諾圖法與單傳感器節(jié)點情形下的歐拉—拉格朗日微分方程結(jié)合提出了一種改進方法，文獻[8]將網(wǎng)格法運用在異向傳感器節(jié)點的最小暴露路徑的求解上,這些都屬于網(wǎng)格法和維諾圖法的變種和一些特定場合下的應(yīng)用。

但是在實際的傳感器網(wǎng)絡(luò)覆蓋問題中，覆蓋區(qū)域中各個位置的重要性有可能不同，比如中間某些區(qū)域更加敏感，同時由于客觀條件的限制（如高溫或環(huán)境惡劣、或是危險敏感區(qū)域）無法達到，無法事先在這樣區(qū)域內(nèi)布置傳感器節(jié)點，只能在其周圍布置傳感器節(jié)點來保護這個區(qū)域。移動目標從固定的起點出發(fā)，到達這個敏感區(qū)域后只能沿著這個區(qū)域的邊界移動，再到達固定的終點。如圖1所示的路徑中有連續(xù)的一小段是這個敏感區(qū)域的部分邊界，這時需要定量地給出傳感器網(wǎng)絡(luò)對移動目標沿著某條路徑達到從起點到終點時的監(jiān)視能力，并在此前提下找出具有最小暴露度的路徑。為方便描述，這樣的敏感區(qū)域在本文中稱為特別保護區(qū)域，和文獻[2,3]討論的問題對應(yīng)，所求的這條路徑稱為帶特別保護區(qū)域邊界條件約束的最小暴露路徑。數(shù)學(xué)中對應(yīng)這種問題的原型為擬極值曲線問題[4]也稱為泛函極值中的單側(cè)變分問題[4,5]。同前面的介紹一樣，無法通過數(shù)學(xué)上求解歐拉—拉格朗日偏微分方程的辦法來求解。又由于有保護區(qū)域邊界條件的限制，無法建立相應(yīng)的帶權(quán)圖模型，前面介紹的網(wǎng)格法和基于Voronoi圖的計算幾何方法這2種基本的近似求解方法也不再適用。為解決這類問題，本文先將帶特別保護區(qū)域邊界條件約束的最小暴露路徑問題抽象為一個帶約束的多元最小值的優(yōu)化問題，該最優(yōu)化問題是一個高維且高度非線性復(fù)雜問題，傳統(tǒng)的數(shù)學(xué)優(yōu)化方法很難找到其全局最優(yōu)解，在人工蜂群算法的框架下，本文結(jié)合問題特點設(shè)計出混合人工蜂群求解算法。通過系列的實驗證實了所設(shè)計的模型和求解算法能很好地求解這種新的最小暴露路徑問題。

2 問題描述

2.1 暴露度及最小暴露路徑

文獻[2,3]首次給出了暴露度的定義。假設(shè)在感應(yīng)區(qū)域范圍內(nèi)分布有個傳感器用于監(jiān)測穿越區(qū)域范圍內(nèi)的移動目標，這些傳感器節(jié)點可以通過某些定位機制獲取自己的位置信息[11~13]，并且可以通過某些機制[14~16]保證這些節(jié)點對周圍區(qū)域覆蓋的可靠性。移動目標從某一固定出發(fā)點出發(fā)沿著某條路徑穿越區(qū)域到達某一固定終點，文獻[2,3]給出的暴露度的數(shù)學(xué)定義為

最小暴露路徑問題后文又為原始最小暴露路徑問題，就是求出在所有連接起點和終點的路徑中使暴露度最小的那條路徑。假設(shè)路徑可以表示成函數(shù)=()的形式，則關(guān)于暴露度的定義式(1)就是函數(shù)()的函數(shù)，可以用數(shù)學(xué)中泛函[6~8]描述為

(2)

這時最小暴露路徑問題就可以表示為

2.2 帶特別保護區(qū)域邊界條件約束的最小暴露路徑問題

在實際應(yīng)用場合中，感應(yīng)區(qū)域中某個區(qū)域是需要重點保護的。但由于客觀條件的限制，比如地理空間限制或者環(huán)境惡劣、或危險敏感區(qū)域無法到達，從而無法在保護區(qū)域內(nèi)布置傳感器節(jié)點，只能事先在這個區(qū)域的周圍布置傳感器節(jié)點來保護這個特別保護區(qū)域；移動目標無法進入該區(qū)域內(nèi)，在固定起點接近該區(qū)域后只能沿著該區(qū)域的邊界移動，然后在邊界的某點離開后到達固定終點。比如在圖1中，曲線(,)=0內(nèi)的區(qū)域是敏感區(qū)域，需要重點保護，由于客觀條件的限制，區(qū)域(,)<0內(nèi)部無法布置傳感器節(jié)點，只能在(,)>0的區(qū)域外布置傳感器節(jié)點來保護(,)<0的區(qū)域。移動目標從點出發(fā)，沿著某路徑達到保護區(qū)域上的某點，然后沿著邊界到達某點，再沿某條路徑從達到終點。在所有這樣的路徑中，找出暴露度值最小的那條路徑。這就是帶特別保護區(qū)域邊界條件約束的最小暴露路徑問題，對應(yīng)數(shù)學(xué)中擬極值曲線問題[4]。

這時帶必經(jīng)區(qū)域邊界的最小暴露路徑問題就可以表示為

圖1 帶特別保護區(qū)域邊界條件約束的最小暴露路徑問題

3 帶特別保護區(qū)域邊界條件約束的最小暴露路徑問題的多元最優(yōu)化模型

對原始最小暴露度路徑問題[2,3]，常見的求解方法有網(wǎng)格法[9]和維諾圖法[10]，這二者方法最終都是將問題抽象成一種圖模型進行求解。然而，網(wǎng)格法對本文提出的帶必經(jīng)區(qū)域邊界條件約束的最小暴露路徑問題并不起作用，原因在于約束條件的存在會導(dǎo)致約束區(qū)域邊界位置對應(yīng)的網(wǎng)格節(jié)點的權(quán)值無法計算，從而不能建立對應(yīng)的帶權(quán)圖模型。維諾圖法對于本文提到的帶特別保護區(qū)域邊界條件約束的最小暴露路徑問題維諾圖法也是無效的，原因也是在于約束條件的存在破壞了保護區(qū)域邊界與維諾頂點之間連接關(guān)系，無法建立對應(yīng)的帶權(quán)圖模型。在引言中已經(jīng)確定了帶特別保護區(qū)域邊界條件約束的最小暴露路徑問題式(5)實質(zhì)是一個帶約束條件的泛函極值問題，也不能用求解泛函極值問題的變分法求其精確解[6~8]。

綜合以上考慮和分析，本文用到了數(shù)學(xué)上求解泛函極值的一種間接方法——有限差分法的思路[5]。圖2是對圖1中的路徑用有限差分法離散化以后的示意圖，表示將區(qū)間進行等分，和對應(yīng)的值組成的系列點坐標可以近似的表示路徑。為方便描述，令，則可以表示為

(6)

，(7)

4 混合人工蜂群求解算法

對最優(yōu)化問題式(7)，在數(shù)學(xué)上有很多求解這類問題的確定性優(yōu)化方法，如最速下降法[17]、插值法[18]、填充函數(shù)法[19]等，但這些方法都需要利用函數(shù)的導(dǎo)數(shù)等信息，只可用在性質(zhì)較好的函數(shù)全局優(yōu)化問題中，很難用于復(fù)雜的工程優(yōu)化問題中。式(7)中要優(yōu)化的目標函數(shù)的導(dǎo)數(shù)形式非常復(fù)雜，連續(xù)變量的維數(shù)比較高，因此不適于用經(jīng)典確定性優(yōu)化方法來求解最優(yōu)化問題如式(5)。

相比以上提到的確定性優(yōu)化方法，隨機性優(yōu)化方法對函數(shù)的要求較低，只需利用函數(shù)值，對目標函數(shù)的性質(zhì)(可導(dǎo)性、連續(xù)性等)沒有太多要求，可用于大多數(shù)優(yōu)化問題的求解，適應(yīng)面寬，適用于復(fù)雜的工程優(yōu)化問題。

人工蜂群算法是近年由Karaboga提出的一種比較新的智能優(yōu)化算法[20~23]，屬于隨機性優(yōu)化方法中的一種。相比遺傳算法、粒子群等其他智能仿生優(yōu)化算法，人工蜂群算法中涉及到的參數(shù)更少，更加適合高維復(fù)雜問題的求解[24~26]，正適合用于最優(yōu)化問題式(5)的求解。在人工蜂群算法中，一個蜜源位置就對應(yīng)了一個優(yōu)化問題的可行解，蜜源的花蜜數(shù)量就對應(yīng)了相關(guān)問題的適應(yīng)度函數(shù)值。這種算法模擬的是蜂群采蜜的行為，在蜜蜂采蜜時，整個蜂群中的蜜蜂會扮演3種角色：雇傭蜂、跟隨蜂和偵查蜂。一般蜂群中的一半個體組成雇傭蜂，另一半個體組成跟隨蜂。雇傭蜂負責(zé)搜尋可開采的蜜源并向其他蜜蜂提供蜜源信息。跟隨蜂可以依據(jù)雇傭蜂提供的蜜源信息對蜜源進行進一步的搜索。當(dāng)搜索到的蜜源質(zhì)量在連續(xù)多次沒有提高的時候，該蜜蜂個體就會轉(zhuǎn)變成偵查蜂并在蜂巢附近進行新的初始化搜索。

雖然相比其他智能優(yōu)化算法，基本的人工蜂群算法具有一定的全局搜索的能力（體現(xiàn)在雇傭蜂和跟隨蜂搜索機制上）和跳出局部最優(yōu)的能力（體現(xiàn)在偵查蜂搜索機制），但如果直接套用基本的人工蜂群算法求解最優(yōu)化問題式(7)還是不會有非常好的求解效果，原因是式(7)不但維數(shù)高，而且由于有項的存在，式(7)還是一個高度非線性復(fù)雜的優(yōu)化問題。直接運用人工蜂群算法的話，路徑呈鋸齒狀跳躍現(xiàn)象，并且隨著迭代次數(shù)的增加這樣的現(xiàn)象沒有明顯改進，這表明基本的人工蜂群算法對最優(yōu)化問題式(7)這樣的高維非線性復(fù)雜優(yōu)化問題缺乏很好的局部尋優(yōu)能力。為解決這樣的困難，本文設(shè)計了如下的混合人工蜂群算法，具體分析和設(shè)計過程如下。

4.1 適應(yīng)度值函數(shù)

好的適應(yīng)度函數(shù)才能引導(dǎo)算法向好的方向搜索，人工蜂群算法作為一種迭代搜索算法，良好的適應(yīng)度函數(shù)形式的設(shè)計就顯得非常的關(guān)鍵。對本文的優(yōu)化問題式(7)，要優(yōu)化的連續(xù)變量為，維數(shù)為?1。如果直接取式(4)表示的暴露度計算值作為適應(yīng)度函數(shù)，為方便描述，記，這并不能很好地反映路徑跳躍的程度，在跳躍比較大的線段上，感應(yīng)強度值變化非常大，從而帶來較大計算偏差；如果令表示點與之間的距離，則可以反映出路徑鋸齒狀跳躍的程度，該值越小越好。理想情況是既希望折線段上的感應(yīng)強度值變化盡可能得小，又希望跳躍現(xiàn)象盡可能得少。綜合這2個因素的考慮，本文將適應(yīng)度值函數(shù)修改為，其中，第一個求和項是取感應(yīng)強度值在該線段上的上界代替的值，表示對第一個因素的懲罰，第二個求和項表示對第二個因素的懲罰，就是路徑的長度，鋸齒狀跳躍程度越大，值也越大，乘以路徑長度后得到的懲罰就越大。這樣的設(shè)計思路是懲罰函數(shù)的設(shè)計思想，但和通常的懲罰函數(shù)方法相比可以減少對懲罰參數(shù)C的討論，既考慮了暴露度值的擬合程度，又考慮了減輕路徑鋸齒狀跳躍現(xiàn)象的發(fā)生，可以幫助個體向好的方向進化。

4.2 編碼及約束條件的處理

在最優(yōu)化問題式(5)中要優(yōu)化的變量有?1維的連續(xù)變量，依據(jù)前面有關(guān)限制條件的分析，限制條件可以表示為:當(dāng)時，滿足。因此，要優(yōu)化的變量除了外，還包括整數(shù)和對此可以采用混合編碼,其中，和為1到?1之間的整數(shù)，且，連續(xù)變量可行域為當(dāng)時，，其余的在感應(yīng)區(qū)域內(nèi)取值。

4.3 初始化及搜索方式

4.4 局部搜索算子

除了以上保證算法全局搜索能力的搜索方程的設(shè)計，還必須保證算法能具有局部探索尋優(yōu)的能力。而對高維并且是高度非線性復(fù)雜的適應(yīng)度值函數(shù)，由于懲罰項因子的存在，要設(shè)計出實際可用的局部搜索算子是非常困難的。對連續(xù)分量，當(dāng)時，，考慮其余連續(xù)分量的局部最優(yōu)值。為了找到這些連續(xù)分量局部最優(yōu)值，避開對復(fù)雜的函數(shù)形式的分析，轉(zhuǎn)而考慮簡單函數(shù)形式，設(shè)計了如下的2種針對連續(xù)分量局部搜索算子，具體分析和步驟如下。

4.4.1 單維局部搜索

(10)

4.5 混合人工蜂群算法

綜合以上設(shè)計的各個要點，針對帶必經(jīng)區(qū)域邊界的最小暴露路徑問題的多元最優(yōu)化模型，本文設(shè)計的混合人工蜂群求解算法可以表示如下。

算法1 混合人工蜂群求解算法

1) 參數(shù)初始化。初始化種群大小，最大進化世代數(shù)，偵查蜂行為參數(shù)，維搜索參數(shù)中分量個數(shù)和搜索范圍值。

3) 引領(lǐng)蜂搜索。對當(dāng)前種群()中個體，選取個體適應(yīng)度值最好的一半構(gòu)成引領(lǐng)蜂群，其余的一半作為跟隨蜂群。對每個引領(lǐng)蜂，隨機選擇引領(lǐng)蜂群中另一個個體，采用式(9)得到新的個體并計算新個體的適應(yīng)度值，如果新產(chǎn)生的引領(lǐng)蜂個體比原個體好則替換原個體，否則保留原有的引領(lǐng)蜂個體。

4) 跟隨蜂搜索。對跟隨蜂中的每個個體，依據(jù)概率選擇方式從新的引領(lǐng)蜂群體中概率選擇較優(yōu)個體，采用式(9)得到新的個體并計算新個體的適應(yīng)度值，采取擇優(yōu)保留的方式組成新的跟隨蜂群體。新的跟隨蜂群體與引領(lǐng)蜂群體組成新的種群群體(+1)。

5) 偵查蜂搜索。對當(dāng)前種群(+1)中的每個個體，判斷是否超過行為參數(shù)值沒有改進，如果經(jīng)過代進化仍沒有改進，則依據(jù)式(9)的方式重新對該個體進行初始化，并記錄下當(dāng)前種群的最優(yōu)個體。

8) 終止條件。令=+1，如果當(dāng)前進化世代數(shù)達到最大進化世代數(shù)，將記錄的種群最優(yōu)個體就作為全局最優(yōu)解的近似解輸出，否則跳轉(zhuǎn)至3) 繼續(xù)執(zhí)行。

5 實驗及結(jié)果

為了驗證所設(shè)計算法能有效解決帶保護區(qū)域的最小暴露路徑問題，本文設(shè)計了一系列的仿真實驗，包括保護區(qū)域外的傳感器節(jié)點確定性分布和隨機性分布，大規(guī)模節(jié)點分布等實驗場景。

測試平臺使用的計算機配置為：Pentium(R) Dual-Core CPU E5500 @ 2.8 GHz ,2 GB的RAM內(nèi)存，Win XP(SP3)操作系統(tǒng), 測試的仿真軟件為Matlab 7.6.0。分別建立傳感器節(jié)點確定性分布、隨機性均勻性分布（包括大規(guī)模節(jié)點隨機分布）等實驗場景進行測試，節(jié)點的實驗參數(shù)取值為，，無特別指出時，感應(yīng)強度模型采用最大感應(yīng)的感應(yīng)強度模型。對于算法設(shè)計中的參數(shù)設(shè)置為：種群大小為50，最大進化代數(shù)為150~300，如果節(jié)點個數(shù)小于200，設(shè)置為150代，如果節(jié)點個數(shù)大于200，否則進化代數(shù)為300代?？紤]曲線擬合的效果，平均每個傳感器節(jié)點占用的編碼長度至少為5比較合適，因此設(shè)置混合編碼中中連續(xù)分量的編碼長度取值為附近的一個整數(shù)，其中，為傳感器節(jié)點個數(shù)；至于維局部搜索中的值的選取非常關(guān)鍵，如果該值太小，則多維局部搜索的效果會很弱；當(dāng)時就變成了一維局部搜索，從而影響收斂的速度；如果該值太大，算法很容易陷入局部最優(yōu)。通常，合適的取值為~的一個整數(shù)。

5.1 傳感器節(jié)點確定性位置的布置場景及實驗結(jié)果

對傳感器節(jié)點位置確定性分布，設(shè)計了保護區(qū)域外傳感器節(jié)點成等邊三角形和正方形確定性布置實驗場景，具體如下。

場景1 感應(yīng)區(qū)域大小為10 m×10 m的正方形區(qū)域，保護區(qū)域為一條拋物線。在保護區(qū)域外確定性布置31個傳感器節(jié)點，在保護區(qū)域內(nèi)沒有傳感器節(jié)點的布置。在保護區(qū)域外的相鄰傳感器節(jié)點位置呈正方形關(guān)系，路徑起點坐標(0,5)，終點坐標(10,3)，具體場景如圖3(a)所示（在以后的場景中相同圖例的含義不再重復(fù)敘述）。星號標識出傳感器節(jié)點位置，加號和點虛線表示求解的最小暴露路徑，在路徑上每隔5個點標出了路徑坐標點的編號（在以后的場景中相同圖例的含義不再重復(fù)敘述），虛線標識出傳感器節(jié)點對應(yīng)的Voronoi圖的邊（通常稱為Voronoi邊），由于傳感器節(jié)點成正方形分布，其對應(yīng)的Voronoi邊為正方形網(wǎng)格。算法中相關(guān)參數(shù)取值為：個體編碼長度為56，群體大小為50，偵查蜂控制行為參數(shù)=10，維局部搜索的參數(shù)Δ=2,=10，最小暴露路徑如圖3(a)虛線所示，可以發(fā)現(xiàn)，除了在保護區(qū)域邊界上的最小暴露路徑部分，區(qū)域外的最小暴露路徑幾乎都是沿著Voronoi邊前進，這和傳統(tǒng)最小暴露路徑問題中的結(jié)論[1,9,10]是一致的，求得的最終適應(yīng)度值結(jié)果為93.382 4。圖3(b)中的曲線分別給出了第1代(虛線帶“×”)、第10代(點劃線帶“◆”)、第20代(雙劃線帶“×”)、第40代(實線帶“×”)、第75代(虛線帶“+”)和第150代(實線帶“+”)種群中最優(yōu)路徑隨進化代數(shù)演變的過程(后續(xù)場景中的曲線圖例與此圖中的相同)。

(a) 節(jié)點布置及最終路徑結(jié)果

(b) 最優(yōu)路徑進化過程

圖3 場景1為31個傳感器節(jié)點在區(qū)域外成正方形的確定性分布

場景2 在10 m×10 m區(qū)域范圍內(nèi)確定性布置30個傳感器節(jié)點，相鄰傳感器節(jié)點位置呈正三角形關(guān)系，路徑起點坐標(0,1.5)，終點坐標(10,6)。保護區(qū)域邊界為一條拋物線。在保護區(qū)域內(nèi)沒有傳感器節(jié)點布置，具體場景如圖4(a)所示。由于保護區(qū)域外的傳感器節(jié)點成正三角形的布置，相應(yīng)Voronoi圖為正六邊形的網(wǎng)格。算法中相關(guān)參數(shù)取值為：個體編碼長度為64，群體大小為50，偵查蜂控制行為參數(shù)=10，維局部搜索的參數(shù)Δ=1.851 6,=10。同樣，求解得到的最小暴露路徑幾乎都是沿著Voronoi邊前進，和傳統(tǒng)最小暴露路徑問題中的結(jié)論[1,9,10]一致，求得的最終適應(yīng)度值結(jié)果為77.982 1。圖4(b)中的曲線分別給出了第1代、第10代、第20代、第40代、第75代和第150代種群中最優(yōu)路徑隨進化代數(shù)演變的過程。

(a) 節(jié)點布置及最終路徑結(jié)果

(b) 最優(yōu)路徑進化過程

圖4 場景2為30個傳感器節(jié)點在區(qū)域外成三角形的確定性分布

以上2種場景求解得到的最小暴露路徑在保護區(qū)域外都是沿著Voronoi邊前進，這符合文獻[1,9,10]中的結(jié)論。證實了在傳感器節(jié)點位置確定布置性的場景下，本文中所設(shè)計的求取最小暴露路徑的正確性和可靠性。

5.2 傳感器節(jié)點均勻隨機布置

為產(chǎn)生傳感器節(jié)點均勻隨機性布置的效果，本文通過對二維平面坐標的水平分量和豎直分量生成均勻隨機數(shù)來產(chǎn)生每個傳感器節(jié)點的位置坐標，總共模擬產(chǎn)生了如下4種場景。

場景3 在10 m×10 m區(qū)域范圍內(nèi)，特別保護區(qū)域為一條拋物線。在特別保護區(qū)域外確定性布置28個傳感器節(jié)點，在特別保護區(qū)域內(nèi)沒有傳感器節(jié)點的布置。起點坐標(0,4.1)，終點坐標(10,6.5)，群體大小為50，=56，總共進化代數(shù)為150，偵查蜂行為參數(shù)=10，搜索區(qū)間Δ=0.870 39，=10，最終適應(yīng)度值結(jié)果為61.207 1，具體場景如圖5所示。

場景4 在100 m×100 m區(qū)域范圍內(nèi)分別隨機分布了160個傳感器，起點坐標(0,40)，終點坐標(100,50)，群體大小為50，=121，總共進化代數(shù)為150，偵查蜂行為參數(shù)=10，搜索區(qū)間Δ=8.485 3，=20，最終適應(yīng)度值結(jié)果為918.354 5，具體場景如圖6所示。

場景5 在100 m×100 m區(qū)域范圍內(nèi)分別隨機分布了200個傳感器，起點坐標(0,40)，終點坐標(100,50)，群體大小為50，=121，總共進化代數(shù)為300，偵查蜂行為參數(shù)=10，搜索區(qū)間Δ=7.589 5，=24，最終適應(yīng)度值結(jié)果為640.522 3，具體場景如圖7所示。

場景6 在100 m×100 m區(qū)域范圍內(nèi)分別隨機分布了400個傳感器，起點坐標(0,40)，終點坐標(100,50)，群體大小為50，=181，總共進化代數(shù)為300，偵查蜂行為參數(shù)=10，搜索區(qū)間Δ=5.366 6，=32，最終適應(yīng)度值結(jié)果為532.257 7，具體場景如圖8所示。

(a) 節(jié)點布置及最終路徑結(jié)果

(b) 最優(yōu)路徑進化過程

圖5 場景3為28個傳感器節(jié)點在區(qū)域外隨機性分布

(a) 節(jié)點布置及最終路徑結(jié)果

(b) 最優(yōu)路徑進化過程

圖6 場景4為160個傳感器節(jié)點在區(qū)域外隨機性分布

(a) 節(jié)點布置及最終路徑結(jié)果

(b) 最優(yōu)路徑進化過程

圖7 場景5為200個傳感器節(jié)點在區(qū)域外隨機性分布

(a) 節(jié)點布置及最終路徑結(jié)果

(b) 最優(yōu)路徑進化過程

圖8 場景6為400個傳感器節(jié)點在區(qū)域外隨機性分布

以上4種傳感器節(jié)點隨機性布置的場景，節(jié)點規(guī)模逐漸增加，包括了小規(guī)模和大規(guī)模傳感器節(jié)點隨機性布置的情況，而且對應(yīng)的模型式(5)的維數(shù)也逐漸增加，在場景4~場景6中的連續(xù)分量的維數(shù)達到了100以上，問題的維數(shù)（個體編碼長度）已經(jīng)非常高，設(shè)計的算法同樣可以很好地解決問題的求解。在保護區(qū)域外，求解得到的最小暴露路徑仍然是幾乎沿著Voronoi邊前進，這和文獻[1,9,10]中的結(jié)論是吻合的。

5.3 算法收斂速度

考慮到篇幅限制，這里只給出了場景3和場景6的算法收斂效果。圖9中的曲線分別表示對應(yīng)場景3、場景6的最佳個體適應(yīng)度值與進化代數(shù)進化的變化關(guān)系?？梢钥吹綀D9中曲線都是快速地下降并收斂到平穩(wěn)狀態(tài)，證實了設(shè)計的算法收斂到全局最優(yōu)解的速度很快，效率很高。另外，圖9(a)中的曲線可以明顯發(fā)現(xiàn)當(dāng)種群進化到20代左右時適應(yīng)度值增加后又開始快速地下降，由此可以看出算法確實具有跳出局部最優(yōu)的能力。

(a) 場景3

(b) 場景6

圖9 場景3和場景6最佳個體適應(yīng)度值與進化代數(shù)進化的變化關(guān)系

6 結(jié)束語

原始最小暴露路徑問題討論的是從固定起點到達固定終點，路徑中間環(huán)節(jié)沒有任何的約束，本文提到最小暴露路徑問題帶有路徑上的約束條件，這來自于客觀條件（比如高溫或環(huán)境惡劣或危險敏感區(qū)域）的限制無法達到某些區(qū)域，無法事先在這些區(qū)域內(nèi)布置傳感器節(jié)點，只能在其周圍布置傳感器節(jié)點來保護這個區(qū)域，移動目標也只能從固定的起點出發(fā)，到達這個敏感區(qū)域后只能沿著這個區(qū)域的邊界移動，再到達固定的終點。本文所提出和討論的問題是原始最小暴露路徑的變種和延續(xù)?？紤]到原有方法失效，將提出的問題抽象成優(yōu)化模型，針對模型維數(shù)高、高度非線性難于求解的困難，設(shè)計的混合人工蜂群算法能有效地完成求解。以上討論的帶有限制約束的最小暴露路徑還是在同構(gòu)節(jié)點的前提下，在感知方式和感知距離不同的異構(gòu)節(jié)點布置條件下，如何求解；以及根據(jù)找到的最小暴露路徑結(jié)合節(jié)點的成本、異同構(gòu)等特性進行下一步改善覆蓋質(zhì)量的傳感器節(jié)點的再部署，這些都是本文后續(xù)進一步開展的工作。

[1] MEGERIAN S, KOUSHANFAR F, POTKONJAK M. Worst and best-case coverage in sensor networks[J]. IEEE Trans on Mobile Computing, 2005, 4(1):84-92.

[2] MEGUERDICHIAN S, KOUSHANFAR F, QU G. Exposure in wireless ad hoc sensor networks[C]//Proc of MobiCom 2001. Rome, Italy, c2001: 139-150.

[3] CLOUQUEUR T, PHIPATANASUPHORN V, RAMANATHAN P, et al. Sensor deployment strategy for detection of targets traversing a region[J]. Mobile Network. 2003, 8(4):453-461 .

[4] GELFAND I M, FOMIN S N. Calculus of Variationd[R]. Dove publisher, 2000, 1-14.

[5] AUBIN J P. Applide Functional Analysis(2nd)[R]. New York, John Wiley, 2000, 31-41.

[6] HRISTO N. DJIDJE V. Approximation algorithms for computing minimum exposure paths in a sensor field[J]. ACM Transactions on Sensor Networks, 2010, 7(23):1-23.

[7] HRISTO N, DJIDJEV L. Efficient computation of minimum exposure paths in a sensor network field[C]//DCOSS 2007. Santa Fe, NM, USA. c2007: 295-308.

[8] LIU L, ZHANG X, MA H. Minimal exposure path algorithms for directional sensor networks[C]//Global Telecommunications Conference. c2009: 1-6.

[9] MEGERIAN S, KOUSHANFAR F, QU G, et al. Exposure in wireless sensor networks: theory and practical solutions[J]. Wireless Network. 2002, 8(5): 443-454.

[10] VELTRI G, HUANG Q, QU G, et al. Minimal and maximal exposure path algorithms for wireless embedded sensor networks[C]//ACM Int’l Conf on Embedded Networked Sensor Systems (SenSys) Akyildiz IF, Estion D. c2003: 40-50.

[11] LIU D, NING P, LIU A, et al .Attack-resistant location estimation in wireless sensor networks[J]. ACM Transactions on Information and System Security, 2008, 11(4):1-39 .

[12] JINGFANG JIANG, GUANGJIE HAN, CHUNAN ZHU, et al. Secure localization in wireless sensor networks: a survey[J]. Journal on Communications, 2011, 6(6):460-470.

[13] 王福豹, 史龍, 任豐. 無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報, 2005, 16(5): 857-858.

WANG F B, SHI L, REN F. Self-Localization Systems and Algorithms for Wireless Sensor Network[J]. Journal of Software, 2005, 16(5): 857-858.

[14] WANG X, MA J J, WANG S. Prediction based dynamic power optimization in wireless sensor networks[J] . Sensors, 2007, 7 (3): 251-266.

[15] WANG L M, GUO Y B, ZHAN Y Z. Security topology control method for wireless sensor networks with node-failure tolerance based on self-regeneration[J]. Eurasip Journal of Wireless Communications and Networking, 2010,(1):1-11.

[16] 宋超, 劉明, 龔海剛, 等. 基于蟻群優(yōu)化解決傳感器網(wǎng)絡(luò)中的能量洞問題[J]. 軟件學(xué)報, 2009,20(10):2729-2743. SONG C, LIU M, GONG H G, et al. ACO-based algorithm for solving energy hole problems in wireless sensor networks[J]. Journal of Software, 2009,20(10):2729-2743.

[17] 李青劍, 王永, 陳紹青, 等. 一種方向優(yōu)化最小均方算法[J]. 電子學(xué)報, 2014,36(6):1348-1354. LI Q J, WANG Y, CHEN S Q,et al. A direction optimization least mean square algorithm[J]. Journal of Electronics & Information Technology, 2014,36(6):1348-1354.

[18] 李彥, 王麗娜. 基于時間序列的時空插值算法改進研究[J] 2014,41(6):414-418. LI Y, WANG L N. Research of spato-temporal interpolation algorithm based on time series[J]. Computer Science, 2014,41(6):414-418.

[19] HONGWEI LIN, YUPING WANG, LEI FAN, et al. A new discrete filled funciton method for finding global minimizer of the integer programiming[J]. Applied Mathematics and Computation, 2012, 219: 4371-4378.

[20] KARABOGA D. An Idea Based on Honey Bee Swarm for Numerical Optimization[R]. Erciyes Univ, Kayseri, Turkey, Tech Rep-TR06, 2005.

[21] KARABOGA D, OZTURK C. Neural networks training by artificial bee colony algorithm on pattern classification[J]. Neural Network World, 2009,19(3): 279-292.

[22] KARABOGA D, OZTURK C. A novel clustering approach: Artificial bee colony (ABC) algorithm[J]. Applied Soft Computing, 2011, 11(1):652-657.

[23] OZTURK C, KARABOGA D, GORKEMLI B. Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algorithm[J]. Sensors, 2011,11(6):6056-6065.

[24] LEUNG Y W, WANG Y. An orthogonal genetic algorithm with quantization for global numerical optimization[J]. IEEE Transaction on Evolutionary Computing, 2001, 5(1):41-53.

[25] WANG Y P, DANG C Y. An evolutionary algorithm for global optimization based on level-set evolution and latin squares[J]. Transaction on Evolutionary Computing, 2007,11(5):579-595.

[26] SHANG Y W, QIU Y H. A note on the extended rosenbrock function[J]. Evolutionary Computing, 2006,14(1):119-126.

[27] SINGIRESU S, RAO S. Engineering Optimization: Theory and Practice[M]. New Jersy,John Wiley & Sons Inc, 2009.

[28] WOODFOR C, PHILLIPS C. Numerical Methods with Worked Examples: Matlab Edition(Second Edtion)[M]. Springer Dordrecht Heidelberg, 2011.

[29] WENYU S, YAXIANG Y. Optimization Theory and Methods: Nonlinear Programming[M]. New York: Springer Science Business Media, 2006.

New minimum exposure path problem and its solving algorithm in wireless sensor networks

YE Miao1,2,3,4, WANG Yu-ping1, DAI Cai1, WANG Xiao-li1

(1. School of Computer Science and Technology, Xidian University, Xi’an 710071, China; 2. College of Information Science and Engineering, Guilin University of Technology, Guilin 541004, China;3. Guangxi Cloud Security and Cloud Services Engineering Technology Research Center, Guilin University of Electronic Technology, Guilin 541104, China;4. College of Computer Science, Shaanxi Normal University, Xi'an 710062, China)

Due to the original minimum exposure path (MEP) problem in wireless sensor network without considering the constrained conditions for paths in practice, a new MEP problem with the request along a part of the boundary of the special protection area (BPA-MEP) was put forwand. As unable to set up the corresponding graph model, the classic methods (such as grid-based method and Voronoi-based method) in solving MEP problem would no longer work to BPA-MEP problem. To solve BPA-MEP problem, a optimization modelwith constraints as a highly nonlinear and higher dimensional problem was tailored and established and then taking the characteristic of the distribution of the sensor nodes, a hybrid artificial bee algorithm was proposed to solve this complex optimization model. The results of the proposed model and the designed algorithm, when implemented in many aspects, show that they can solve BPA-MEP problem effectively.

wireless sensor networks, minimum exposure path, protect area, hybrid artificial bee algorithm

TP393; TP212

A

10.11959/j.issn.1000-436x.2016007

2014-12-16；

2015-08-06

國家自然科學(xué)基金資助項目(No.61262075, No.61472297, No.61563012)；廣西自然科學(xué)基金資助項目(No.014GXNSFAA118370)；廣西自動檢測技術(shù)與儀器重點實驗室基金資助項目(No.YQ14204, No.YQ14104)；廣西教育廳基金資助項目(No.YB2014148)

The National Natural Science Foundation of China(No.61262075, No.61472297, No. 61563012), The Natural Science Foundation of Guangxi (No.2014GXNSFAA118370), The Key Laboratory of Automatic Detecting Technology and Instruments of Guangxi (No.YQ14204, No.YQ14104), The General Programs of the Scientific Research Project of Guangxi Educational Committee (No.YB2014148)

葉苗（1977-），男，廣西桂林人，西安電子科技大學(xué)博士生，桂林理工大學(xué)副教授，主要研究方向為網(wǎng)絡(luò)計算、進化算法、人工智能。

王宇平（1961-），男，陜西西安人，西安電子科技大學(xué)教授、博士生導(dǎo)師，主要研究方向為人工智能、網(wǎng)絡(luò)和工程設(shè)計中的優(yōu)化方法、最優(yōu)化理論、數(shù)據(jù)挖掘。

代才（1984），男，安徽阜陽人，西安電子科技大學(xué)博士生，主要研究方向為多目標優(yōu)化、進化算法、人工智能。

王曉麗（1987-），女，山東濰坊人，西安電子科技大學(xué)講師，主要研究方向為并行與分布式環(huán)境下的任務(wù)調(diào)度、工程優(yōu)化等。