仲元昌， 陳 鋒， 李發(fā)傳， 孟 普

(重慶大學(xué) 通信工程學(xué)院，重慶 400030)

0 引 言

近年來(lái)，無(wú)線傳感器網(wǎng)絡(luò)(WSNs)在國(guó)防軍事、環(huán)境監(jiān)測(cè)、智能家居、建筑物結(jié)構(gòu)監(jiān)控、機(jī)場(chǎng)安全檢測(cè)等眾多領(lǐng)域中得到越來(lái)越廣泛的應(yīng)用[1,2]，其網(wǎng)絡(luò)覆蓋率是WSNs服務(wù)質(zhì)量的重要衡量標(biāo)準(zhǔn)[3]。

傳統(tǒng)覆蓋優(yōu)化算法一般是基于探測(cè)和圖論[4]，這些算法存在不足之處，探測(cè)算法不能完全保證網(wǎng)絡(luò)的完全覆蓋，只適合較小規(guī)模的WSNs，圖論的基本思想在監(jiān)測(cè)區(qū)域內(nèi)任何一點(diǎn)都可找到一個(gè)傳感器節(jié)點(diǎn)，這與實(shí)際情況不符。文獻(xiàn)[5]采用蟻群算法，雖然具有局部搜索能力強(qiáng)、較強(qiáng)的魯棒性和可擴(kuò)充性，但在求解初期速度較慢，容易出現(xiàn)停滯,收斂速度也較慢，影響網(wǎng)絡(luò)優(yōu)化的實(shí)時(shí)性。文獻(xiàn)[6]采用遺傳算法，需要重新確定操作，在最優(yōu)解附近收斂較慢，求解過(guò)程比較復(fù)雜。文獻(xiàn)[7]分析了完全覆蓋策略下的節(jié)點(diǎn)數(shù)目和不完全覆蓋策略中的節(jié)點(diǎn)數(shù)目，提出了用不完全覆蓋方法來(lái)取代完全覆蓋算法，并提出了一種基于節(jié)點(diǎn)位置的信息和Voronoi 區(qū)域劃分的分布式覆蓋的解決方案。

本文針對(duì)WSNs覆蓋問(wèn)題采用了一種改進(jìn)的人工魚(yú)群算法(ASFA)，并結(jié)合了三峽庫(kù)區(qū)水質(zhì)監(jiān)測(cè)實(shí)際應(yīng)用環(huán)境，提出采用大規(guī)模WSNs構(gòu)建三峽庫(kù)區(qū)水環(huán)境監(jiān)測(cè)系統(tǒng)的解決方案[8]。由于三峽庫(kù)區(qū)面積大、分布廣，涉及26個(gè)區(qū)縣(其中22個(gè)在重慶市轄區(qū)內(nèi))，有些地方至今還是人跡罕至之處，構(gòu)成了長(zhǎng)江三峽這個(gè)特殊的區(qū)域，庫(kù)區(qū)呈現(xiàn)出蜿蜒的樹(shù)狀結(jié)構(gòu)[9]。

1 WSNs覆蓋優(yōu)化模型

1.1 覆蓋模型

(1)

傳感器節(jié)點(diǎn)集C區(qū)域覆蓋面積為所覆蓋的監(jiān)測(cè)點(diǎn)面積之和，記作Aarea(c)

(2)

網(wǎng)絡(luò)有效覆蓋率為

(3)

式中A為待監(jiān)測(cè)區(qū)域總面積。

(4)

1.2 網(wǎng)絡(luò)覆蓋優(yōu)化問(wèn)題

WSNs優(yōu)化覆蓋主要考察2個(gè)目標(biāo)：網(wǎng)絡(luò)覆蓋率和網(wǎng)絡(luò)節(jié)點(diǎn)利用率，在節(jié)點(diǎn)之間保持連通的情況下，使用最少的節(jié)點(diǎn)獲得最大的網(wǎng)絡(luò)覆蓋率，降低節(jié)點(diǎn)覆蓋區(qū)域之間的重復(fù)，節(jié)點(diǎn)分布更加均勻，節(jié)約成本。覆蓋問(wèn)題描述如下：

1)利用式(3)計(jì)算各個(gè)傳感器節(jié)點(diǎn)的覆蓋率。

2)利用式(4)計(jì)算該像素點(diǎn)對(duì)傳感器節(jié)點(diǎn)的利用率。

通過(guò)對(duì)網(wǎng)絡(luò)覆蓋目標(biāo)函數(shù)和網(wǎng)絡(luò)節(jié)點(diǎn)利用率目標(biāo)函數(shù)進(jìn)行加權(quán)，將其作為算法求解問(wèn)題的適應(yīng)度函數(shù)，具體定義如下

fobj(l)=w1f1(l)+w2(1-f2(l)),

(5)

式中l(wèi)=a1,a2,…,aN;w1,w2為子目標(biāo)函數(shù)的權(quán)值，且w1+w2=1。

為了找到最優(yōu)WSNs覆蓋方案，本文采用人工魚(yú)群算法對(duì)式(5)進(jìn)行求解

2 覆蓋優(yōu)化算法

2.1 基本人工魚(yú)群算法

人工魚(yú)群算法是一種模仿魚(yú)類(lèi)行為方式的優(yōu)化方法，該算法是由李曉磊等人[10]在2002年提出的一種新型的智能優(yōu)化算法，算法通過(guò)魚(yú)群游弋覓食，通過(guò)集體協(xié)作達(dá)到尋優(yōu)目的。

2.1.1 人工魚(yú)的行為描述

人工魚(yú)的個(gè)體狀態(tài)可表示為Xi=(x1,x2,…,xm)，其中xi(i=1,2,…,m)為欲尋優(yōu)的變量，F(xiàn)(Xi)為人工魚(yú)Xi的當(dāng)前食物濃度，人工魚(yú)個(gè)體之間的距離可表示為di,j=‖Xi-Xj‖，將WSNs覆蓋優(yōu)化問(wèn)題抽象為若干條人工魚(yú)探索最大食物濃度的過(guò)程，設(shè)定人工魚(yú)的步長(zhǎng)為step,在其視野visual內(nèi)游動(dòng)，且1≤step≤visual，δ(0<δ<1)表示擁擠因子，其值越大，表示越擁擠,δ用來(lái)限制人工魚(yú)聚群的規(guī)模。

1)覓食行為:設(shè)人工魚(yú)當(dāng)前狀態(tài)為Xi，在其視野范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj，若此狀態(tài)下的食物濃度大于當(dāng)前狀態(tài)，則向該方向前進(jìn)一步；反之,重新選擇狀態(tài)Xj，判斷食物濃度是否大于當(dāng)前狀態(tài)，這樣反復(fù)嘗試try_number次后，如仍不滿足前進(jìn)條件，則隨機(jī)移動(dòng)一步，即

(6)

式中i=1,2,…,k;xi,xj和xi_net分別為人工魚(yú)狀態(tài)向量Xi，Xj和人工魚(yú)下一步狀態(tài)向量Xi/next的第k個(gè)分量；Rand()為(0,1)之間的一個(gè)隨機(jī)數(shù)。

2)聚群行為:人工魚(yú)探測(cè)當(dāng)前鄰域內(nèi)(即di,j≤visual)的伙伴數(shù)目nf和其中心位置Xc，若鄰域中心位置Xc食物濃度較大且不太擁擠，即滿足F(Xc)>F(Xi)和nf/NF<δ(NF為人工魚(yú)總數(shù))，則鄰領(lǐng)域中心方向前進(jìn)一步，即按式(7)執(zhí)行

(7)

否則,執(zhí)行覓食行為。

3)追尾行為:人工魚(yú)在其可視范圍內(nèi)尋找食物濃度最大的伙伴Xi〗max，如周?chē)惶珦頂D，則向該人工魚(yú)的方向前進(jìn)一步，即按式(8)執(zhí)行

ifFmax>δFi,

(8)

否則,執(zhí)行覓食行為。

4)公告板:公告板用于記錄人工魚(yú)最優(yōu)狀態(tài)。人工魚(yú)行動(dòng)后，如果人工魚(yú)自身狀態(tài)由于公告板的狀態(tài)，就將公告板的狀態(tài)改成自身狀態(tài)。

5)隨機(jī)行為:人工魚(yú)在其視野范圍內(nèi)隨機(jī)選擇下一狀態(tài)，然后向該方向移動(dòng)。

2.2 改進(jìn)的人工魚(yú)群算法

2.2.1 混沌系統(tǒng)

為了提高人工魚(yú)群算法的搜索效率，本文引入了混沌系統(tǒng)。混沌具有豐富的時(shí)空動(dòng)態(tài)，系統(tǒng)的動(dòng)態(tài)演變可導(dǎo)致吸引因子的轉(zhuǎn)移，在人工魚(yú)群算法中引入混沌，能夠有效地避免算法長(zhǎng)時(shí)間位于局部極值附近，提高算法的全局收斂性和搜索效率。本文采用的混沌系統(tǒng)是由經(jīng)常用到的Logistic映射產(chǎn)生的，其迭代式如下

Zk+1=f(μZk)=μZk(1-Zk),

Zk∈(0,1),k=0,1,2,….

(9)

式中 μ為系統(tǒng)的擾動(dòng)參數(shù)，Zk為變量Z在k次迭代得到的數(shù)值；研究表明，當(dāng)μ=4是“單片”混沌，即系統(tǒng)處于完全混沌狀態(tài)，此時(shí)系統(tǒng)可以無(wú)重復(fù)。Zk幾乎遍歷(0,1)之間的所有狀態(tài)。

2.2.2 混沌人工魚(yú)群優(yōu)化算法

基本人工魚(yú)群算法較其他算法有諸多的自身優(yōu)越性，但其自身不足仍可導(dǎo)致陷入局部值，收斂效率低，由于初始化過(guò)程是隨機(jī)的，雖然大多數(shù)情況下人工魚(yú)可保證分布均勻，但對(duì)于個(gè)體質(zhì)量不能保證，解群有一部分遠(yuǎn)離最優(yōu)解。如果能得到較好的初始解群，將有利于求解效率和解的質(zhì)量，采用混沌初始化能得到較好的初始化解群。具體實(shí)現(xiàn)如下：

為了驗(yàn)證此改進(jìn)的魚(yú)群算法的有效性和可行性，Sinc函數(shù)作為優(yōu)化目標(biāo)函數(shù)，用Matlab編程進(jìn)行試驗(yàn)，具體如下:Sinc函數(shù)如下

x1≥-10,x2≤10.

(10)

此函數(shù)為一多峰函數(shù)，在其搜索范圍x1≥-10,x2≤10內(nèi)的(0,0)處有最大值1。

設(shè)定人工魚(yú)群規(guī)模Np=50，最大迭代次數(shù)為300，算法運(yùn)行50次，擁擠因子δ=0.618，平均步長(zhǎng)step=0.3，Try_number=20。以20次實(shí)驗(yàn)中的最好值、最差值、平均值為參考量來(lái)對(duì)2種算法進(jìn)行比較，如表1所示。

表1 仿真試驗(yàn)結(jié)果

通過(guò)表1中實(shí)驗(yàn)數(shù)據(jù)可以看出本文提出的算法，在設(shè)定相同迭代次數(shù)下最差值、最好值及其平均值遠(yuǎn)遠(yuǎn)優(yōu)于基本魚(yú)群算法，在其尋優(yōu)精度上也優(yōu)于基本人工魚(yú)群算法。

2.3 覆蓋優(yōu)化策略

1)產(chǎn)生初始化群體：在控制變量可行域內(nèi)混沌產(chǎn)生N條人工魚(yú)，從中選出Np(NP>N)條較優(yōu)個(gè)體作為初始化魚(yú)群，設(shè)置初始迭代次數(shù) 。

2)公告板賦初值：計(jì)算初始化魚(yú)群中個(gè)體當(dāng)前的食物濃度，并比較大小，將其最大食物濃度和這個(gè)人工魚(yú)記入公告板。

4)公告板:每條人工魚(yú)在在執(zhí)行一次行為后，都將檢查自身的食物濃度是否優(yōu)于公告板的食物濃度，若優(yōu)于公告板，則用自身取代公告板上的值。

5)結(jié)束條件判斷:判斷迭代次數(shù)是否達(dá)到最大值Gmax或最優(yōu)解是否在誤差范圍內(nèi)，如滿足條件，則轉(zhuǎn)向步驟(6);否則,G=G+1，轉(zhuǎn)向步驟(3)，進(jìn)行下一次優(yōu)化過(guò)程。

6)算法結(jié)束，輸出結(jié)果。

3 仿真與分析

為了對(duì)改進(jìn)的魚(yú)群算法覆蓋優(yōu)化性能進(jìn)行測(cè)試，算法通過(guò)Matlab軟件進(jìn)行仿真。假設(shè)WSNs監(jiān)測(cè)區(qū)域?yàn)?00 m×100 m范圍內(nèi)，首先隨機(jī)拋撒60個(gè)智能傳感器節(jié)點(diǎn)分布在監(jiān)測(cè)區(qū)域，在隨機(jī)播散20個(gè)傳感器節(jié)點(diǎn)，如圖1(a)。設(shè)定節(jié)點(diǎn)感知半徑Rs=10 m，通信半徑Rc=10 m，人工魚(yú)個(gè)數(shù)為100，人工魚(yú)視野為5 m，擁擠因子δ=0.6，步長(zhǎng)為5 m，重復(fù)次數(shù)try_number=3，最大迭代次數(shù)300。

為了該算法的有效性，利用Matlab進(jìn)行2種模式下的仿真實(shí)驗(yàn)，即基本魚(yú)群算法和本文改進(jìn)的算法。在相同的仿真環(huán)境下，分別進(jìn)行30組實(shí)驗(yàn)，2種算法的覆蓋優(yōu)化仿真結(jié)果分別如圖1(b)和圖1(c)。

圖1 隨機(jī)分布的節(jié)點(diǎn)和兩種算法的仿真結(jié)果

由仿真結(jié)果圖分析可得:基本魚(yú)群算法對(duì)監(jiān)測(cè)區(qū)域進(jìn)行覆蓋優(yōu)化平均使用47個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)利用率為58.75 %，平均覆蓋率為78.9 %；而利用改進(jìn)的魚(yú)群算法平均使用43個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)利用率為53.75 %，平均覆蓋率為94.22 %，達(dá)到了覆蓋優(yōu)化的目地，而且使用了更少的節(jié)點(diǎn)，節(jié)約了成本，提高了網(wǎng)絡(luò)的生存時(shí)間；同時(shí)，改進(jìn)的算法優(yōu)化后的網(wǎng)絡(luò)節(jié)點(diǎn)更加均勻地分布滿了整個(gè)監(jiān)測(cè)區(qū)域，能在更短的時(shí)間內(nèi)使用更少的網(wǎng)絡(luò)節(jié)點(diǎn)來(lái)達(dá)到網(wǎng)絡(luò)的覆蓋要求，減少了節(jié)點(diǎn)的冗余，具有更高效的求解近似最優(yōu)覆蓋。

4 結(jié)束語(yǔ)

本文針對(duì)基本人工魚(yú)群算法存在局部最優(yōu)、后期收斂速度慢等缺陷，將混沌理論引入魚(yú)群算法應(yīng)用到WSNs覆蓋優(yōu)化中。仿真結(jié)果表明:改進(jìn)的算法有更強(qiáng)的搜索能力和探索速度，提高了求解的精度，能有效地實(shí)現(xiàn)WSNs覆蓋優(yōu)化。

參考文獻(xiàn):

[1] Yick Jennifer,Mukherjee Biswanath ,Ghosal Dipak.Wireless sensor networks survey[J].Computer Networks,2008,52:2292-2330.

[2] 朱紅松，孫利民.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)發(fā)展現(xiàn)狀[J].中興通訊技術(shù),2009,15(5)：1-5，15.

[3] 任彥，張思東，張宏科.無(wú)線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法[J].軟件學(xué)報(bào)，2006，17(3)：422-433.

[4] 汪學(xué)清，楊永田，孫 亭，等.無(wú)線傳感器網(wǎng)絡(luò)中基于網(wǎng)格的覆蓋問(wèn)題研究[J].計(jì)算機(jī)科學(xué)，2006，33(11)：38-39，78.

[5] 彭麗英.改進(jìn)的蟻群算法網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋優(yōu)化研究[J].計(jì)算機(jī)仿真，2011，28(9)：151-153，255.

[6] 殷衛(wèi)莉，陳 巍.遺傳算法在無(wú)線傳感器網(wǎng)絡(luò)覆蓋中仿真研究[J].計(jì)算機(jī)仿真，2010，27(10)：120-123.

[7] Carbunar B,Grama A,Vitek J,et al,Redundancy and coverage detection in sensor networks [J].ACM Transactions on Sensor Networks,2006，2(1)：98-128.

[8] 仲元昌,郭開(kāi)林,徐寶桂,等 面向三峽庫(kù)區(qū)水環(huán)境監(jiān)測(cè)的混合網(wǎng)絡(luò)構(gòu)建[J].世界科技研究與發(fā)展，2010，32(6)：737-740.

[9] 季富政.長(zhǎng)江三峽地區(qū)概貌[J].重慶建筑,2010(9):1-7.

[10] 李曉磊，邵之江，錢(qián)積新.一種基于動(dòng)物自治體的尋優(yōu)模式：魚(yú)群算法[J].系統(tǒng)工程理論與實(shí)踐，2002，22(11)：32-38.