基于改進的果蠅優化算法的WSN節點部署設計

姚勇濤,　吳　雪,　吳　喆

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

?

基于改進的果蠅優化算法的WSN節點部署設計

姚勇濤,吳雪,吳喆

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

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

節點部署; 無線傳感器網絡; 果蠅優化算法; 覆蓋; 連通

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

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

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

1　網格部署基本概念

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

圖1　監測點集和有效點集Fig.1 Monitoring and effective nodes collection

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

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

2　基本果蠅算法

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

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

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

(1)

(2)

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

(3)

(4)

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

smell(i)=f(si)

(5)

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

bestsmell=max(smell(i))

(6)

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

圖2　基本果蠅尋優模型示意圖Fig.2　Scheme of basic FOA model

3　WSN-IFOA算法的節點部署設計

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

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

(7)

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

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

(8)

(9)

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

(10)

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

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

(11)

將WSN-IFOA算法應用于無線傳感器網絡的非均勻監測點的節點部署設計中,算法步驟如下:

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

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

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

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

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

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

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

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

4　仿真實驗

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

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

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

4.2不同的網格規模對算法的影響

圖5示出了不同的網格規模對節點部署的影響。

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

圖5　不同的網格規模對節點部署的影響Fig.5　Influence of different mesh dimensions for node deployment

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

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

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

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

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

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

4.4果蠅種群的數量對算法的影響

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

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

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

4.5尋優性能比較

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

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

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

監測點數尋優時間/s本文方法蟻群算法監測點數尋優時間/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時完成尋優所需時間

5　結　論

本文提出了一種基于改進果蠅優化的算法(WSN-IFOA)用于節點的部署設計,該算法構建了適用于節點部署的氣味函數模型,可以有效地在隨機產生的不同數量的監測點集的情況下進行傳感器節點的部署設計。實驗結果表明了不同網格規模和不同果蠅種群數量對于該算法的影響。在與傳統蟻群算法的比較中可以看出,在相同規模網格點的情況下,無論是在監測點多還是少的情況下,該算法均表現出比較好的部署效果。

[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-),女,安徽合肥人,碩士生,研究方向為無線傳感器網絡。E-mail:947096217@qq.com

通信聯系人：吳 雪,E-mail:wuxue@ecust.edu.cn

TP391

A