姚勇濤,　吳　雪,　吳　喆

(華東理工大學(xué)信息科學(xué)與工程學(xué)院,上海 200237)

?

基于改進(jìn)的果蠅優(yōu)化算法的WSN節(jié)點(diǎn)部署設(shè)計(jì)

姚勇濤,吳雪,吳喆

(華東理工大學(xué)信息科學(xué)與工程學(xué)院,上海 200237)

針對非均勻監(jiān)測點(diǎn)的節(jié)點(diǎn)部署問題,設(shè)計(jì)并實(shí)現(xiàn)了一種簡單、實(shí)用的果蠅優(yōu)化算法(WSN-IFOA),構(gòu)造了適用于節(jié)點(diǎn)部署的味道濃度函數(shù)。利用果蠅群體的隨機(jī)尋優(yōu)性,能夠保證部署盡可能少的傳感器節(jié)點(diǎn)使網(wǎng)絡(luò)覆蓋和連通。實(shí)驗(yàn)結(jié)果表明該算法在部署效果上優(yōu)于基本蟻群算法,并證明了算法的可行性和有效性。

節(jié)點(diǎn)部署; 無線傳感器網(wǎng)絡(luò); 果蠅優(yōu)化算法; 覆蓋; 連通

無線傳感器網(wǎng)絡(luò)(WSN)[1]是一種新興的智能化網(wǎng)絡(luò)系統(tǒng),節(jié)點(diǎn)部署設(shè)計(jì)是WSN的關(guān)鍵技術(shù),而優(yōu)化的節(jié)點(diǎn)部署不僅需要考慮網(wǎng)絡(luò)的覆蓋,還要考慮網(wǎng)絡(luò)的連通性。目前的覆蓋技術(shù)主要包括區(qū)域覆蓋、點(diǎn)覆蓋、柵欄覆蓋3種。

本文的研究背景是基于區(qū)域的點(diǎn)覆蓋。網(wǎng)絡(luò)連通則要求整個工作的區(qū)域網(wǎng)絡(luò)是一個整體,不能夠被分割,也就是要求每個部署的傳感器節(jié)點(diǎn)通過單跳或者多跳都必須連接到sink點(diǎn)。優(yōu)化部署的目的就是要求部署盡可能少的傳感器節(jié)點(diǎn)使網(wǎng)絡(luò)覆蓋和連通。

如今,智能優(yōu)化算法[2-3]被越來越多地應(yīng)用于無線傳感器網(wǎng)絡(luò)。智能優(yōu)化算法包括遺傳算法、模擬退火算法、魚群算法、蟻群算法等。文獻(xiàn)[4]提出了在障礙物干擾下的遺傳算法,但是沒有考慮sink點(diǎn)的位置對于節(jié)點(diǎn)部署的影響。文獻(xiàn)[5]提出了基于模擬退火算法的節(jié)點(diǎn)部署方法,但沒有考慮部署節(jié)點(diǎn)之間的連通性。文獻(xiàn)[6]提出了基于粒子群的節(jié)點(diǎn)部署,它將能耗與覆蓋率同時考慮,但能量對于節(jié)點(diǎn)的移動性有很大影響。針對這些算法存在的連通問題和sink點(diǎn)位置問題,本文提出了一種新的簡單、高效的智能算法——果蠅算法。針對無線傳感器網(wǎng)絡(luò)非均勻監(jiān)測點(diǎn)的節(jié)點(diǎn)部署問題,以網(wǎng)格點(diǎn)為背景隨機(jī)地構(gòu)造監(jiān)測點(diǎn),并針對WSN自身特點(diǎn)設(shè)計(jì)出果蠅算法的氣味函數(shù)模型,將覆蓋與連通同時考慮,該算法既能保證高效性又能有效部署較少的傳感器節(jié)點(diǎn)。將本文提出的算法與蟻群算法對無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)部署設(shè)計(jì)進(jìn)行了對比,實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的可行性。

1　網(wǎng)格部署基本概念

本文基于網(wǎng)格為背景的模型對節(jié)點(diǎn)部署進(jìn)行建模[7-8]。圖1所示為監(jiān)測點(diǎn)集和有效點(diǎn)集示意圖。圖中的監(jiān)測點(diǎn)為不均勻分布的需要被傳感器節(jié)點(diǎn)覆蓋的點(diǎn)(用◇和□表示); 傳感器節(jié)點(diǎn)是部署設(shè)計(jì)的點(diǎn),目的是將監(jiān)測點(diǎn)完全覆蓋(用■表示); 候選網(wǎng)格點(diǎn)為以sink點(diǎn)和已經(jīng)部署的傳感器節(jié)點(diǎn)為圓心,以通信半徑為半徑畫圓,圓形區(qū)域面積的并集區(qū)域里的網(wǎng)格點(diǎn); 有效點(diǎn)為候選網(wǎng)格區(qū)域中能夠覆蓋未被覆蓋的監(jiān)測點(diǎn)的網(wǎng)格點(diǎn)(用○表示)。

圖1　監(jiān)測點(diǎn)集和有效點(diǎn)集Fig.1 Monitoring and effective nodes collection

在網(wǎng)格背景模型下,所有的點(diǎn),無論是監(jiān)測點(diǎn)還是需要部署的傳感器節(jié)點(diǎn)都屬于網(wǎng)格點(diǎn)。本文的背景是基于區(qū)域的點(diǎn)覆蓋,即在網(wǎng)格上隨機(jī)產(chǎn)生不均勻的監(jiān)測點(diǎn),部署盡可能少的傳感器節(jié)點(diǎn)去完全覆蓋這些監(jiān)測點(diǎn),并保證所有監(jiān)測點(diǎn)和sink點(diǎn)的連通性。

在構(gòu)建的網(wǎng)格點(diǎn)上,首先隨機(jī)產(chǎn)生不均勻分布的監(jiān)測點(diǎn)集,固定sink點(diǎn)在網(wǎng)格上的位置,并確定sink點(diǎn)和待部署的傳感器節(jié)點(diǎn)的通信半徑。本文中節(jié)點(diǎn)通信半徑和傳感器半徑相等。在sink節(jié)點(diǎn)的通信半徑內(nèi),首先按照一定的規(guī)則選擇網(wǎng)格點(diǎn)1作為第1個被部署的傳感器節(jié)點(diǎn),再以sink點(diǎn)和傳感器節(jié)點(diǎn)1所組成的候選網(wǎng)格點(diǎn)內(nèi)繼續(xù)按照一定規(guī)則選擇傳感器節(jié)點(diǎn)2,如此反復(fù),直到完成需要規(guī)劃的目標(biāo)(即覆蓋所有的監(jiān)測點(diǎn)并使它們?nèi)恐苯踊蜷g接連通到sink點(diǎn))為止。

2　基本果蠅算法

果蠅優(yōu)化算法(FOA)[9-10]是一種基于果蠅覓食行為推演出尋求全局優(yōu)化的新方法,被應(yīng)用于金融預(yù)警模式之中。果蠅本身在感官直覺上優(yōu)于其他物種,尤其在視覺與嗅覺上,果蠅的嗅覺可以搜索甚至40 km以外的食物源,當(dāng)發(fā)現(xiàn)離食物的位置更近后,可以利用視覺發(fā)現(xiàn)果蠅群聚集的位置,并往該位置飛去。圖2示出了基本果蠅尋優(yōu)模型示意圖,算法步驟如下:

(1) 隨機(jī)初始化果蠅群體位置initX0,initY0。

(2) 賦予果蠅個體利用嗅覺搜尋食物之隨機(jī)方向與距離如式(1)、式(2)所示。

(1)

(2)

(3) 由于無法得知食物位置,因此先估計(jì)與原點(diǎn)之距離di,再計(jì)算味道濃度判定值si。

(3)

(4)

(4) 將味道濃度判定值si代入味道濃度判定函數(shù),求出該果蠅個體位置的味道濃度,如式(5)。

smell(i)=f(si)

(5)

找出此果蠅群體中味道濃度最高的果蠅(求極大值),如式(6)。

bestsmell=max(smell(i))

(6)

(5) 保留最佳味道濃度值與坐標(biāo),此時果蠅群體利用視覺往該位置飛去,進(jìn)入迭代尋優(yōu)并判斷味道濃度是否優(yōu)于前一迭代味道濃度,若是,則果蠅群體飛往新位置,如此反復(fù),直到達(dá)到需要規(guī)劃的目標(biāo)為止。

圖2　基本果蠅尋優(yōu)模型示意圖Fig.2　Scheme of basic FOA model

3　WSN-IFOA算法的節(jié)點(diǎn)部署設(shè)計(jì)

本文以網(wǎng)格為WSN背景模型建模,對果蠅算法的氣味函數(shù)進(jìn)行改進(jìn),使其應(yīng)用于無線傳感器網(wǎng)絡(luò)的非均勻點(diǎn)監(jiān)測的節(jié)點(diǎn)部署,在保證整個網(wǎng)絡(luò)覆蓋和連通的前提下,設(shè)計(jì)能夠高效部署節(jié)點(diǎn)的優(yōu)化算法。

設(shè)傳感器節(jié)點(diǎn)的通信半徑為rs,監(jiān)測點(diǎn)(x′,y′)與傳感器節(jié)點(diǎn)(xi,yi)的距離為D(i),則

(7)

當(dāng)D(i)≤rs時,監(jiān)測點(diǎn)(x′,y′)可以被傳感器節(jié)點(diǎn)(xi,yi)覆蓋。

在果蠅算法中,果蠅群體中的每一個個體會根據(jù)自身所處的位置與初始位置的關(guān)系,計(jì)算出它們各自的味道濃度判定函數(shù)值,得到最佳的味道濃度,從而確定下一步的位置?；镜墓壦惴ㄎ兜罎舛扰卸ㄖ凳腔诰嚯x的,本文考慮的是基于區(qū)域的點(diǎn)覆蓋,在WSN-IFOA中,通過計(jì)算動態(tài)的候選網(wǎng)格點(diǎn)集合中果蠅隨機(jī)選擇的各個網(wǎng)格點(diǎn)的味道濃度判定函數(shù)值的最大值作為下一個部署的傳感器節(jié)點(diǎn)。味道濃度由以下兩部分因素組成:

(8)

(9)

smell(vi)=w1f1+w2(1-f2)

(10)

其中:w1和w2表示權(quán)重,0

將式(8)、式(9)代入式(10),得

(11)

將WSN-IFOA算法應(yīng)用于無線傳感器網(wǎng)絡(luò)的非均勻監(jiān)測點(diǎn)的節(jié)點(diǎn)部署設(shè)計(jì)中,算法步驟如下:

(1) 固定sink點(diǎn)的位置,將果蠅群體的初始位置放于sink節(jié)點(diǎn)的通信半徑內(nèi)。

(2) 賦予每個果蠅個體在候選網(wǎng)格點(diǎn)集合范圍內(nèi),隨機(jī)的方向和距離。

(3) 計(jì)算各個目標(biāo)網(wǎng)格點(diǎn)覆蓋的監(jiān)測點(diǎn)個數(shù),進(jìn)一步計(jì)算得到各個點(diǎn)的味道濃度判定值。

(4) 將味道濃度判定值帶入氣味函數(shù),如式(11),計(jì)算出下一跳味道濃度判定函數(shù)最大的目標(biāo)網(wǎng)格點(diǎn),記下該位置,果蠅群體飛向該位置。

(5) 利用貪婪法循環(huán)迭代此步驟,判斷味道濃度是否優(yōu)于前一次的味道濃度,若不是,則返回上一跳節(jié)點(diǎn)。

(6) 直到所有的監(jiān)測點(diǎn)被完全覆蓋,則算法結(jié)束。

WSN-IFOA算法流程圖如圖3所示。

圖3　WSN-IFOA算法流程圖Fig.3　Flow chat of WSN-IFOA algorithm

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

4.1不同的通信半徑對算法的影響

圖4示出了不同的通信半徑對節(jié)點(diǎn)部署的影響。其中圖4(a)設(shè)定網(wǎng)格點(diǎn)規(guī)模為10×10,圖4(b)設(shè)定網(wǎng)格點(diǎn)規(guī)模為20×20,網(wǎng)格邊長均為24。

如圖4所示,無論網(wǎng)格規(guī)模大小,當(dāng)通信半徑等于網(wǎng)格對角線長時,實(shí)驗(yàn)結(jié)果比通信半徑等于網(wǎng)格邊長時的效果要好得多。在后期的實(shí)驗(yàn)中也證明,通信半徑必須大于網(wǎng)格的對角線長,才會表現(xiàn)出比較好的效果。因?yàn)閺睦碚摲治錾现v,所部署的傳感器節(jié)點(diǎn)必須是在網(wǎng)格點(diǎn)集中選取的,所以通信半徑等于甚至小于網(wǎng)格邊長的話,則可以選取的網(wǎng)格點(diǎn)就會很少,算法將會受到很大制約。

4.2不同的網(wǎng)格規(guī)模對算法的影響

圖5示出了不同的網(wǎng)格規(guī)模對節(jié)點(diǎn)部署的影響。

圖4　不同的通信半徑對于節(jié)點(diǎn)部署的影響Fig.4　Influence of different communication radii for node deployment

圖5　不同的網(wǎng)格規(guī)模對節(jié)點(diǎn)部署的影響Fig.5　Influence of different mesh dimensions for node deployment

圖5(a)設(shè)定網(wǎng)格規(guī)模為9×9,網(wǎng)格邊長為24,傳感器節(jié)點(diǎn)的通信半徑為24; 圖5(b)設(shè)定網(wǎng)格點(diǎn)規(guī)模為9×9,網(wǎng)格邊長為24,傳感器節(jié)點(diǎn)的通信半徑為48; 圖5(c)設(shè)定網(wǎng)格點(diǎn)規(guī)模為17×17,網(wǎng)格邊長為12,傳感器節(jié)點(diǎn)的通信半徑為48; 圖5(d)設(shè)定網(wǎng)格點(diǎn)規(guī)模為33×33,網(wǎng)格邊長為6,傳感器節(jié)點(diǎn)的通信半徑為48。圖中實(shí)心點(diǎn)表示不均勻分布的監(jiān)測點(diǎn)集,監(jiān)測點(diǎn)個數(shù)均為60個,并且相對位置相同?？招狞c(diǎn)代表部署的傳感器節(jié)點(diǎn)。

由圖5可以看出,圖5(a)部署的傳感器節(jié)點(diǎn)數(shù)為31,圖5(b)為17,圖5(c)為14,圖6(d)為15。比較圖5(a)和圖5(b)可知,在網(wǎng)格規(guī)模和監(jiān)測點(diǎn)相同的情況下,傳感器節(jié)點(diǎn)的通信半徑越大,則部署的傳感器節(jié)點(diǎn)越少。比較圖5(b)、5(c)、5(d)可知,傳感器節(jié)點(diǎn)的通信半徑相等,在監(jiān)測點(diǎn)相對位置相同的情況下,并不是網(wǎng)格規(guī)模越大,所需要部署的傳感器節(jié)點(diǎn)越少。當(dāng)網(wǎng)格規(guī)模增加到一定程度后,所部署的傳感器節(jié)點(diǎn)數(shù)基本變化不大。

4.3sink點(diǎn)位置不同對算法的影響

圖6示出了sink點(diǎn)位置不同對節(jié)點(diǎn)部署的影響。圖6中網(wǎng)格點(diǎn)的規(guī)模為20×20,網(wǎng)格的邊長為24。圖6(a)中傳感器節(jié)點(diǎn)的通信半徑為48,圖6(b)中傳感器節(jié)點(diǎn)的通信半徑為72。將sink點(diǎn)分別固定在區(qū)域的中心和邊緣進(jìn)行比較。

圖6　sink點(diǎn)位置不同對節(jié)點(diǎn)部署的影響Fig.6　Influence of different sink node position for node deployment

由圖6可以看出,sink點(diǎn)固定在區(qū)域中心相對于固定在區(qū)域邊緣所需要部署的傳感器節(jié)點(diǎn)的浮動變化曲線較為平滑,但是傳感器節(jié)點(diǎn)數(shù)量的最大值與最小值的差值區(qū)間較大。如圖6(a)中,當(dāng)sink點(diǎn)固定在區(qū)域邊緣時傳感器節(jié)點(diǎn)數(shù)量的最大值為63,即當(dāng)監(jiān)測點(diǎn)為20時所部署的傳感器節(jié)點(diǎn)數(shù)量的最小值為51,差值為12; 當(dāng)sink點(diǎn)固定在區(qū)域中心時差值為24。傳感器節(jié)點(diǎn)的通信半徑越大,則部署傳感器節(jié)點(diǎn)的個數(shù)越少,而且差值區(qū)間的變化也相對比較小。

4.4果蠅種群的數(shù)量對算法的影響

圖7示出了果蠅種群的數(shù)量對節(jié)點(diǎn)部署的影響。圖7中網(wǎng)格點(diǎn)的規(guī)模為20×20,網(wǎng)格的邊長為24。圖7(a)中傳感器節(jié)點(diǎn)的通信半徑為48,圖7(b)中傳感器節(jié)點(diǎn)的通信半徑為72,sink點(diǎn)均固定在網(wǎng)格點(diǎn)的中心。在均將果蠅的初始位置置于sink點(diǎn)的通信半徑內(nèi)的條件下,分別取果蠅種群為50和100進(jìn)行比較。

圖7　果蠅種群數(shù)量對于節(jié)點(diǎn)部署的影響Fig.7　Influence of fruit fly population for node deployment

由圖7可以看出,果蠅種群數(shù)量為100的果蠅群平均所用的傳感器節(jié)點(diǎn)數(shù)少于果蠅種群為50的果蠅群。但是果蠅種群數(shù)量等于50時,比數(shù)量等于100時的果蠅群相對所部署的傳感器節(jié)點(diǎn)數(shù)量的波動要小,即曲線相對穩(wěn)定。當(dāng)監(jiān)測點(diǎn)達(dá)到一定數(shù)量時,部署的傳感器節(jié)點(diǎn)變動的幅度不大。傳感器節(jié)點(diǎn)的通信半徑越大,則部署傳感器節(jié)點(diǎn)的個數(shù)越少。

4.5尋優(yōu)性能比較

設(shè)定網(wǎng)格的規(guī)模為20×20,網(wǎng)格的邊長為24,傳感器節(jié)點(diǎn)的通信半徑分別為48和72,sink點(diǎn)固定在網(wǎng)格的中心,果蠅種群的數(shù)量為40。圖8示出了WSN-IFOA算法和基本蟻群算法(Easidesign)尋優(yōu)性能的比較結(jié)果。

由圖8可以看出,監(jiān)測點(diǎn)數(shù)目不同,部署的傳感器節(jié)點(diǎn)數(shù)目也不同。在兩種通信半徑條件下,WSN-IFOA算法的穩(wěn)定性明顯比Easidesign算法好,平均所部署的傳感器節(jié)點(diǎn)數(shù)也要少。尤其在監(jiān)測點(diǎn)稀疏的條件下,Easidesign算法很不穩(wěn)定,并且沒有得到比較好的解。當(dāng)監(jiān)測點(diǎn)比較多時,兩者的差距較小。在效率上,WSN-IFOA算法比傳統(tǒng)方法節(jié)省更多的CPU計(jì)算時間,比較結(jié)果見表1、表2。由此可以看出,本文算法的復(fù)雜度更低?？傊?無論是在監(jiān)測點(diǎn)多還是少的情況下,本文算法都能夠保證能夠找到比較好的傳感器節(jié)點(diǎn)解集。

圖8　WSN-IFOA與Easidesign的尋優(yōu)性能比較Fig.8　Comparison of WSN-IFOA and Easidesign optimization 表1　R=48時完成尋優(yōu)所需時間 Table 1　CPU times of the optimization (R=48)

監(jiān)測點(diǎn)數(shù)尋優(yōu)時間/s本文方法蟻群算法監(jiān)測點(diǎn)數(shù)尋優(yōu)時間/s本文方法蟻群算法201.833149.471202.864115.662401.621133.0211403.159109.251602.955159.3281603.35582.063802.748131.321803.41695.0211002.612119.3642003.511109.251

表2　R=72時完成尋優(yōu)所需時間

5　結(jié)　論

本文提出了一種基于改進(jìn)果蠅優(yōu)化的算法(WSN-IFOA)用于節(jié)點(diǎn)的部署設(shè)計(jì),該算法構(gòu)建了適用于節(jié)點(diǎn)部署的氣味函數(shù)模型,可以有效地在隨機(jī)產(chǎn)生的不同數(shù)量的監(jiān)測點(diǎn)集的情況下進(jìn)行傳感器節(jié)點(diǎn)的部署設(shè)計(jì)。實(shí)驗(yàn)結(jié)果表明了不同網(wǎng)格規(guī)模和不同果蠅種群數(shù)量對于該算法的影響。在與傳統(tǒng)蟻群算法的比較中可以看出,在相同規(guī)模網(wǎng)格點(diǎn)的情況下,無論是在監(jiān)測點(diǎn)多還是少的情況下,該算法均表現(xiàn)出比較好的部署效果。

[1]CURIAC DANIEL-IOAN.A survey on redundancy and its applications in wireless sensor networks[J].WSEAS Transactions on Computers,2009,8(4):705-714.

[2]CORMEN T H,CHARLES E L,RONALD L R,etal.Introduction to Algorithms[M].Second Edition.Massachusetts:The MIT Press,2001.

[3]WEI L,LI C.Ant based approach to the optimal deployment in wireless sensor networks[J].Journal on Communications,2009,30:25-33.

[4]JOURDAN D B,DE WECK O L.Layout optimization for a wireless sensor network using a multi-objective genetic algorithm[C]//2004 IEEE 59th Vehicular Technology Conference.USA:IEEE,2004:2466-2470.

[5]LIN F,CHIU P L.A near-optimal sensor placement algorithm to achieve complete coverage-discrimination in sensor networks[J].IEEE Communications Letters,2005,9(1):43-45.

[6]AZIZ N A A,MOHEMMED A W,ZHANG M.Particle swarm optimization for coverage maximization and energy conservation in wireless sensor networks[C]//Applications of Evolutionary Computation.UK:Springer Berlin Heidelberg,2010:51-60.

[7]KHAN S U.Approximate optimal sensor placements in grid sensor fields[C]//2007 IEEE 65th Vehicular Technology Conference.USA:IEEE,2007:248-251.

[8]JOURDAN D B,DE WECK O L.Layout optimization for a wireless sensor network using a multi-objective genetic algorithm[C]//2004 IEEE 59th Vehicular Technology Conference.USA:IEEE,2004:2466-2470.

[9]PAN W T.A new fruit fly optimization algorithm:Taking the financial distress model as an example[J].Knowledge-Based Systems,2012,26:69-74.

[10]HAN Junying,LIU Chengzhong.Fruit fly optimization algorithm with adaptive mutation[J].Application Research of Computers,2013,30(9):2641-2644.

Wireless Sensor Network Node Deployment Design Based on Improved Fruit Fly Optimization Algorithm

YAO Yong-tao,WU Xue,WU Zhe

(School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

Aiming at the problem of non-uniform monitoring node deployment,this paper proposes an improved fruit fly algorithm,WSN-IFOA,by constructing the flavor concentration function suitable for deployment of nodes.The proposed algorithm utilizes the stochastic optimization of fruit fly group to ensure the coverage and communication of network by means of sensor node as few as possible.It is shown from experiment results that the proposed algorithm is superior to the classical ant colony algorithm and is feasible and effective.

node deployment; wireless sensor network; fruit fly optimization algorithm; coverage; connection

1006-3080(2016)04-0545-07

10.14135/j.cnki.1006-3080.2016.04.016

2015-10-30

姚勇濤(1989-),女,安徽合肥人,碩士生,研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。E-mail:947096217@qq.com

通信聯(lián)系人：吳 雪,E-mail:wuxue@ecust.edu.cn

TP391

A