基于改進的果蠅優(yōu)化算法的WSN節(jié)點部署設計

姚勇濤,　吳　雪,　吳　喆

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

?

基于改進的果蠅優(yōu)化算法的WSN節(jié)點部署設計

姚勇濤,吳雪,吳喆

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

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

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

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

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

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

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

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

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

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

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

2　基本果蠅算法

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

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

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

(1)

(2)

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

(3)

(4)

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

smell(i)=f(si)

(5)

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

bestsmell=max(smell(i))

(6)

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

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

3　WSN-IFOA算法的節(jié)點部署設計

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

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

(7)

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

在果蠅算法中,果蠅群體中的每一個個體會根據(jù)自身所處的位置與初始位置的關系,計算出它們各自的味道濃度判定函數(shù)值,得到最佳的味道濃度,從而確定下一步的位置。基本的果蠅算法味道濃度判定值是基于距離的,本文考慮的是基于區(qū)域的點覆蓋,在WSN-IFOA中,通過計算動態(tài)的候選網(wǎng)格點集合中果蠅隨機選擇的各個網(wǎng)格點的味道濃度判定函數(shù)值的最大值作為下一個部署的傳感器節(jié)點。味道濃度由以下兩部分因素組成:

(8)

(9)

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

(10)

其中:w1和w2表示權重,0

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

(11)

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

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

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

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

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

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

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

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

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

4　仿真實驗

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

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

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

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

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

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

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

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

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

4.3sink點位置不同對算法的影響

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

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

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

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

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

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

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

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

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

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

圖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)測點數(shù)尋優(yōu)時間/s本文方法蟻群算法監(jiā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　結　論

本文提出了一種基于改進果蠅優(yōu)化的算法(WSN-IFOA)用于節(jié)點的部署設計,該算法構建了適用于節(jié)點部署的氣味函數(shù)模型,可以有效地在隨機產(chǎn)生的不同數(shù)量的監(jiān)測點集的情況下進行傳感器節(jié)點的部署設計。實驗結果表明了不同網(wǎng)格規(guī)模和不同果蠅種群數(shù)量對于該算法的影響。在與傳統(tǒng)蟻群算法的比較中可以看出,在相同規(guī)模網(wǎng)格點的情況下,無論是在監(jiā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-),女,安徽合肥人,碩士生,研究方向為無線傳感器網(wǎng)絡。E-mail:947096217@qq.com

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

TP391

A