滕志軍，張曉旭

(東北電力大學(xué) 信息工程學(xué)院，吉林 吉林 132012)

基于慣性權(quán)重蛙跳算法的WSN布局優(yōu)化

滕志軍，張曉旭

(東北電力大學(xué) 信息工程學(xué)院，吉林 吉林 132012)

摘要：針對傳統(tǒng)混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)易陷入局部極值的問題，在青蛙最差個體的更新策略中引入反正切慣性權(quán)重加以修正，從而使該算法具有更強(qiáng)的全局搜索能力及局部搜索能力。將提出的改進(jìn)型蛙跳算法應(yīng)用到WSN(Wireless Sensor Network，WSN)覆蓋優(yōu)化問題中，通過理論數(shù)據(jù)分析及仿真結(jié)果證明，改進(jìn)的蛙跳算法較傳統(tǒng)的SFLA、PS0、WIS-SFLA對網(wǎng)絡(luò)覆蓋率有較大的提升，是一種較優(yōu)的覆蓋優(yōu)化方法。

關(guān)鍵詞：混合蛙跳算法；覆蓋優(yōu)化；無線傳感器網(wǎng)絡(luò)；布局

無線傳感器網(wǎng)絡(luò)節(jié)點的合理部署能夠有效提升網(wǎng)絡(luò)覆蓋率，降低網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生存周期，是實現(xiàn)無線傳感器網(wǎng)絡(luò)優(yōu)化的核心問題[1-3]。混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)是由Lansey及Eusuff于2003年提出的一種基于全局協(xié)同搜索的群智能優(yōu)化算法[4]。本文提出了一種基于混合蛙跳算法的無線傳感器網(wǎng)絡(luò)覆蓋策略，并通過在青蛙個體的狀態(tài)更新過程中引入反正切函數(shù)慣性權(quán)重來解決傳統(tǒng)混合蛙跳算法的“早熟收斂”問題，改進(jìn)后的蛙跳算法能夠?qū)崿F(xiàn)無線傳感器網(wǎng)絡(luò)的合理化布局，有效提高無線傳感器網(wǎng)絡(luò)的覆蓋率。

1改進(jìn)的蛙跳算法

1.1　基本蛙跳算法

混合蛙跳算法[5-7]是結(jié)合了基于遺傳行為的模因算法及基于社會行為的粒子群算法的優(yōu)點，通過模擬青蛙覓食過程而提出的一種新型仿生智能算法。其基本原理為：在D維搜索空間下，隨機(jī)初始化M只具有相同特性結(jié)構(gòu)的青蛙，將每只青蛙的位置視為優(yōu)化空間中的一個可行解。第i只青蛙在t時刻下的位置為：Xi(t)=(xi1(t)，xi2(t)，…，xiD(t))，計算出每只青蛙的適應(yīng)度函數(shù)值F(Xi)，并依據(jù)適應(yīng)度函數(shù)值的好壞將M只青蛙降序排列，將其劃分為Q個子群，子群規(guī)模為S，其中M，Q，S滿足關(guān)系式M=Q×S。分組規(guī)則為：第1只分配到第1個子群，第2只分配到第2個子群，直到第Q只分配到第Q個子群，然后將第S+1只分配到第1個種群，依次類推，直到將全部青蛙分配完畢為止。在t時刻下，對于每個子群，具有最優(yōu)適應(yīng)度的青蛙個體記為Pb(t)=[pb1(t)，pb2(t)，…，pbD(t)]T，具有最差適應(yīng)度的青蛙個體記為Pw(t)=[pw1(t)，pw2(t)，…，pwD(t)]T，具有全局最優(yōu)適應(yīng)度的青蛙個體記為Pg(t)=[pg1(t)，pg2(t)，…，pgD(t)]T。然后在每個子群中進(jìn)行局部深度搜索，對每個子群中的Pw(t)在(t+1)時刻的位置通過如下更新策略獲得：

Disi(t+1)=rand()·(Pb(t)-Pw(t))，

(1)

每次進(jìn)行更新后，若Pw(t+1)較Pw(t)更優(yōu)，則用Pw(t+1)替換原子群中的最差解。否則，用Pg(t)替換Pb(t)按下式進(jìn)行移動步長計算：

Disi(t+1)=rand()·(Pg(t)-Pw(t))，

(2)

重新按對Pw(t)行更新。若仍未改進(jìn)，則需在定義域內(nèi)隨機(jī)產(chǎn)生一個新解替換原子群內(nèi)的Pw(t)。重復(fù)執(zhí)行以上更新操作直到滿足預(yù)設(shè)的迭代次數(shù)即完成一輪各子群的局部深度搜索。然后對各子群的全部青蛙重新進(jìn)行混合、排序及劃分子群，繼續(xù)執(zhí)行局部深度搜索，如此反復(fù)至達(dá)到預(yù)設(shè)的結(jié)束條件為止。

1.2　蛙跳算法的改進(jìn)

為解決傳統(tǒng)的混合蛙跳算法在尋優(yōu)過程中存在的“早熟收斂”問題，借鑒粒子群算法的更新策略[8]，將反正切函數(shù)慣性權(quán)重w引入混合蛙跳算法步長更新策略中以實現(xiàn)蛙跳算法在尋優(yōu)過程中局部深度搜索與全局信息交換的平衡，提高算法“跳出局部極值”的能力。

改進(jìn)后具體的更新策略如下：

newDisi(t+1)=w·rand()·(Pb(t)-Pw(t))，

(3)

Pw(t+1)=Pw(t)+newDisi(t+1)，

(4)

(5)

其中：ws，we取值是0.9和0.4，分別為慣性權(quán)重因子的初始值及結(jié)束值。ts為子群內(nèi)當(dāng)前迭代次數(shù)，tm為當(dāng)前混合迭代次數(shù)。tmmax為子群內(nèi)迭代次數(shù)的最大值，tsmax為混合迭代次數(shù)最大值。λ是控制因子，取值區(qū)間為[0.4，0.7]，適當(dāng)調(diào)整λ有利于加快算法的收斂速度。

2WSN節(jié)點部署方案

2.1　模型描述

假定在一個大小為A×B的二維平面監(jiān)測區(qū)域T內(nèi)，隨機(jī)部署M個傳感器節(jié)點，所有傳感器節(jié)點均為同構(gòu)節(jié)點。通過傳感器節(jié)點位置的移動，擴(kuò)大無線傳感器網(wǎng)絡(luò)覆蓋面積以實現(xiàn)無線傳感器網(wǎng)絡(luò)覆蓋率的最大化。Ni表示無線傳感器網(wǎng)絡(luò)中的第i個節(jié)點，將該網(wǎng)絡(luò)的傳感器節(jié)點集表示為N={N1，N2，…，NM}，每個傳感器節(jié)點的位置記作ci=(xi，yi)，節(jié)點的感知半徑及通信半徑分別為R和2R。將區(qū)域T離散化為a×b個像素點，像素點pj位置記為pj=(aj，bj)其中j=1，2，…，a×b。

本文采用文獻(xiàn)[1，8]中布爾感知模型來計算無線傳感器網(wǎng)絡(luò)的覆蓋率。在無線傳感器網(wǎng)絡(luò)中任意像素點pj被傳感器節(jié)點ci檢測到的概率可通過下式進(jìn)行計算：

(6)

(7)

無線傳感器網(wǎng)絡(luò)的覆蓋率可表示為被覆蓋的像素點之和與像素點總數(shù)之比，如下式：

(8)

公式(8)即為本文中無線傳感器網(wǎng)絡(luò)節(jié)點部署優(yōu)化方案中的優(yōu)化對象。

2.2　基于改進(jìn)SLFA的部署策略描述

在無線傳感器網(wǎng)絡(luò)中應(yīng)用改進(jìn)后的SFLA，公式(8)將作為該算法的適應(yīng)度函數(shù)。算法具體實現(xiàn)過程如表1所示。

表1　基于改進(jìn)SFLA的部署策略描述

3實驗結(jié)果分析

本文無線傳感器網(wǎng)絡(luò)的監(jiān)測區(qū)域設(shè)置為100 m×100 m的正方形區(qū)域，將其劃分為大小相等、面積為1 m2的100×100個像素點。在監(jiān)測區(qū)域內(nèi)布置25個感知半徑R=10 m，通信半徑為2R=20 m的傳感器節(jié)點且全部傳感器節(jié)點均為同構(gòu)節(jié)點。為了驗證本文中WSN節(jié)點部署策略的有效性，在相同實驗條件下，將分別與采用SFLA算法、基于線性慣性權(quán)重的蛙跳算法對無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方案求解的結(jié)果進(jìn)行比較。其中，圖1為傳感器節(jié)點均勻分布時所達(dá)到的理論最優(yōu)值，此時節(jié)點所覆蓋的面積為監(jiān)測區(qū)域的78.5%。圖2為使用SFLA算法對覆蓋優(yōu)化方案進(jìn)行求解的效果圖。其覆蓋率為60.7%，是理論最優(yōu)值的77.4%。

圖1 最優(yōu)方案節(jié)點覆蓋圖圖2 基于SFLA的節(jié)點覆蓋圖

圖3為使用權(quán)重改進(jìn)的蛙跳算法[9](Weight Improved Shuffled frog Algorithm，WIS-SLFA)算法對覆蓋優(yōu)化方案進(jìn)行求解的效果圖，其覆蓋率為66.2%是理論最優(yōu)值的84.3%。圖4為本文中改進(jìn)的蛙跳算法(Arctangent Function Weight Shuffled Frog Leaping Algorithm，ASFLA)求解無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方案的效果圖，其覆蓋率為70.3%，是理論最優(yōu)值的89.5 %。

通過對比發(fā)現(xiàn)，本文所提出的ASFLA算法具有更強(qiáng)的尋優(yōu)能力，尋優(yōu)結(jié)果明顯優(yōu)于采用SFLA算法及WIS-SLFA算法的覆蓋優(yōu)化方案，具有更高的覆蓋率，節(jié)點的分布更均勻，覆蓋率可達(dá)89.5%。

圖3 基于WIS-SFLA的節(jié)點覆蓋圖圖4 基于ASFLA的節(jié)點覆蓋圖

4結(jié)論

無線傳感器的優(yōu)化覆蓋是無線傳感器網(wǎng)絡(luò)的關(guān)鍵問題之一。本文提出了一種基于改進(jìn)的混合蛙跳算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方案。在傳統(tǒng)蛙跳算法中引入反正切函數(shù)慣性權(quán)重，使其克服了在尋優(yōu)過程中的“早熟收斂”等問題。實驗結(jié)果表明，相同實驗條件下，本文中的節(jié)點部署方案可以獲得更為理想的網(wǎng)絡(luò)覆蓋率，但該方案并沒有將無線傳感器網(wǎng)絡(luò)的能耗考慮進(jìn)去，能耗問題將成為下一步的研究方向。

參考文獻(xiàn)

[1]Kimberley W.Lighter weight leads to fuel savings[J].Automotive engineer，2004，29(9)：30-31.

[2]Chang J H，Tassiulas L.Energy conserving routing in wireless ad-hoc networks[J].Proceedings of IEEE INFOCOM，2000,1：22-24.

[3]王震宇.基于WSN會聚點部署及捆塞控制策略[J].東北電力大學(xué)學(xué)報，2009,29(1)：81-83.

[4]Eusuff MM，Lansey KE.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Journal of Water Resources Planning and Management.2003，129(3)：210-25.

[5]Niknam T，Azad Farsani E.A hybrid self-adaptive particle swarm optimization and modified shuffled frog leaping algorithm for distribution feeder reconfiguration[J].Engineering Applications of Artificial Intelligence,2010,23(8)：1340-1349.

[6]Amiri B，F(xiàn)athian M，Maroosi A.Application of shuffled frog-leaping algorithm on clustering[J]..The International Journal of Advanced Manufacturing Technology，2009，45(1/2)：199-209.

[7]劉洪濤，肖廣明，劉俊濤.基于粒子群優(yōu)化灰色模型的電力系統(tǒng)負(fù)荷預(yù)測[J].東北電力大學(xué)學(xué)報，2009,29(2)：69-72.

[8]李莉，牛奔.粒子群優(yōu)化算法[M].北京：冶金工業(yè)出版社，2010：52-55.

[9]劉悅婷.權(quán)重改進(jìn)的蛙跳算法優(yōu)化PID參數(shù)[J].工業(yè)儀表與自動化裝置，2014，(2)：7-10.

The Layout Optimization of WSN Based on Inertia Weight Shuffled Frog Leaping Algorithm

TENG Zhi-jun，ZHANG Xiao-xu

(Department of Information Engineering，Northeast Dianli University，Jilin Jilin 132012)

Abstract：To solve basic shuffled frog leaping algorithm(SFLA)’s easiness of trapping into local optional solution，an improved shuffled frog leaping algorithm based on arc tangent function was proposed.The local search capability and the global search capability of the advanced algorithm is enhanced efficiently.The advanced algorithm is applied to optimal coverage problem of wireless sensor network(WSN) to find a better solution.The theoretical analysis and simulation result show this algorithom can improve network coverage effectively compared with PSO、SFLA、and WIS-SFLA.

Key words：SFLA；Coverage optimization；WSN；Layout

中圖分類號：TN99

文獻(xiàn)標(biāo)識碼：A

文章編號：1005-2992(2015)06-0066-04

作者簡介：滕志軍(1973-)，男，吉林省吉林市人，東北電力大學(xué)信息工程學(xué)院教授，博士，主要研究方向：無線通信技術(shù).

收稿日期：2015-09-12