徐躍州，張 欣

（貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽550025）

0 引 言

無線傳感器網(wǎng)絡(luò)［1］節(jié)點(diǎn)的優(yōu)化部署研究可以有效提高傳感器網(wǎng)絡(luò)覆蓋率和降低能耗，增長網(wǎng)絡(luò)壽命。目前，常用的優(yōu)化算法有虛擬力算法 （VFA）、螢火蟲群優(yōu)化（GSO）、粒子群算法 （PSO）、蛙跳算法 （SFLA）等，文獻(xiàn) ［2－5］分別采用VFA、GSO、PSO、SFLA這4種算法對傳感器網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行優(yōu)化部署，提升監(jiān)測區(qū)域的覆蓋率。然而，上述算法卻存在著高復(fù)雜度、低收斂速度和精度等問題。針對這些問題，本文提出一種簡單、高效的混沌果蠅算法 （chaotic fruit fly algorithm，CFOA），并通過仿真驗(yàn)證分析其性能的優(yōu)越性。

1 果蠅算法

果蠅 算 法［6］（fruit fly optimization algorithm，F(xiàn)OA）是2011年臺灣學(xué)者潘文超從果蠅覓食行為中得到啟發(fā)，提出的一種尋求全局優(yōu)化的新方法，是一種新型仿生行為學(xué)智能算法，廣泛運(yùn)用于求解函數(shù)極值、Z－SCORE模型的系數(shù)調(diào)整、向量機(jī)參數(shù)優(yōu)化以及各類廣義回歸神經(jīng)網(wǎng)絡(luò)系數(shù)優(yōu)化等［7］。由于算法提出較晚，F(xiàn)OA的研究仍處于起步階段，理論尚不成熟，如對多維極值復(fù)雜優(yōu)化的問題等。

FOA與VFA、GSO、PSO、SFLA相比，不但算法簡單、收斂速度快 （如SFLA和PSO的優(yōu)化方程為二階微分方程，而FOA的優(yōu)化方程為一階微分方程）、代碼運(yùn)行時(shí)間短，且FOA僅需調(diào)整3個(gè)參數(shù)，算法復(fù)雜度低；而其它仿生算法至少需調(diào)整6、7個(gè)參數(shù)，各個(gè)參數(shù)間的關(guān)系和相互影響十分復(fù)雜，導(dǎo)致分析算法的復(fù)雜度變得異常困難［8］。與此同時(shí)，果蠅算法和上述算法一樣，極易陷入局部最優(yōu)解，以至于后期收斂精度降低、收斂速度變慢，特別是對于高維多極值復(fù)雜優(yōu)化問題。

2 混沌優(yōu)化

混沌優(yōu)化 （chaos optimization，CP）是利用混沌運(yùn)動的隨機(jī)性、遍歷性、規(guī)律性和初值敏感性來提高隨機(jī)優(yōu)化算法的效率［9］，混沌運(yùn)動介于確定性與隨機(jī)性之間，具有豐富的時(shí)空動態(tài)，并且混沌搜索能在一定范圍內(nèi)按其身的“規(guī)律性”不重復(fù)的遍歷所有狀態(tài)。Logistic映射系統(tǒng)是混沌系統(tǒng)中最著名的系統(tǒng)模型之一，其模型如下

當(dāng)u＝4時(shí)，系統(tǒng)處于混沌狀態(tài)。若xi∈［mi，ni］，可由式 （2）、式 （3）對混沌變量xi進(jìn)行往返映射，具體的混沌搜索迭代方法可見文獻(xiàn) ［10］

由于果蠅算法類似于其它智能算法，均為通過對初值的迭代和進(jìn)化尋求最優(yōu)解，初值的選取不當(dāng)極易使算法陷入局部最優(yōu)，而對于傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署，模型及其復(fù)雜，很難找出一個(gè)對初值的評價(jià)標(biāo)準(zhǔn)。為了避免算法陷入局部最優(yōu)，采用混沌優(yōu)化，隨機(jī)生成一個(gè)混沌擾動因子，在每次果蠅群進(jìn)化前進(jìn)行混沌擾動，使果蠅群迅速跳出局部尋優(yōu)，進(jìn)行全局搜索。

3 WSN節(jié)點(diǎn)部署模型

假設(shè)在一個(gè)二維監(jiān)測區(qū)域，區(qū)域被離散化為m＊n個(gè)像素點(diǎn)，每個(gè)像素點(diǎn)表示為（m，n）。在該區(qū)域內(nèi)投入N個(gè)傳感器節(jié)點(diǎn)，其感知半徑為r。傳感器的節(jié)點(diǎn)集表示為式（4），節(jié)點(diǎn)和像素點(diǎn)距離為式 （5）

則像素點(diǎn)（mi，ni）被節(jié)點(diǎn)ci監(jiān)測到的概率為

所以，該像素點(diǎn)被節(jié)點(diǎn)集C聯(lián)合監(jiān)測到的概率為

綜上，傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)覆蓋率［11］為

4 混沌果蠅算法的應(yīng)用和性能分析

本文在借鑒文獻(xiàn) ［12］的基礎(chǔ)上，提出混沌果蠅算法，具體算法如下：

步驟1 隨機(jī)初始化N個(gè)果蠅位置，Smellbest＝0，步長h；果蠅位置為： （Init X（i），Init Y（i）），其中i∈（1，N）；

步驟2 根據(jù)式 （8）、式 （9），求出覆蓋率最大的果蠅及其位置

步驟3 記錄果蠅位置和覆蓋率，所有果蠅飛向該位置，如式 （10）所示

步驟4 根據(jù)果蠅步長h，每個(gè)果蠅隨機(jī)向4周搜尋食物，如式 （11），其中K為節(jié)點(diǎn)個(gè)數(shù)

步驟5 重復(fù)步驟2；

步驟6 對當(dāng)前覆蓋率最大的果蠅進(jìn)行混沌搜索，隨機(jī)生成兩個(gè)n維變量

根據(jù)混沌模型可得式 （13），將得到的 （a2，b2）各個(gè)分量載波到混沌擾動范圍［－d，d］，則擾動量為式 （14），此時(shí)新位置坐標(biāo)為式 （15）

計(jì)算新老位置的覆蓋率f＊、f，若f＊＞f，則

若f＊＜f，則果蠅位置與bestSmell不變，混沌搜索迭代M次。

步驟7 重復(fù)步驟3。

步驟8 迭代步驟4～步驟7，直至迭代結(jié)束，得到最優(yōu)分簇 （X＿axis，Y＿axis）和最優(yōu)解Smellbest。

從上述算法流程可以看出，CFOA每次迭代時(shí)，所有果蠅均聚集到當(dāng)前最優(yōu)位置進(jìn)行尋優(yōu)，相對于其它智能算法各個(gè)因子從當(dāng)前位置移動向最優(yōu)位置尋優(yōu)，具有更好的收斂速度；對于智能算法 “早熟”問題，CFOA每次迭代時(shí)，對當(dāng)前的最優(yōu)位置進(jìn)行混沌擾動，及時(shí)跳出 “早熟收斂”，進(jìn)行全局尋優(yōu)。顯然，混沌果蠅算法具有更高的收斂速度和收斂精度。

5 仿真結(jié)果及分析

假定在邊長為50 m的正方形監(jiān)測區(qū)域中放置25個(gè)同一性能的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)，節(jié)點(diǎn)額監(jiān)測半徑r＝5 m。當(dāng)粒子數(shù)為待測區(qū)域面積的0.25%至4%時(shí)，偏差約為0.1%至0.5%，綜合分析，本文均勻選取2500個(gè)粒子，使實(shí)驗(yàn)結(jié)果具有較小的偏差性。為了分析CFOA中果蠅算法的參數(shù)選擇，本文從不同果蠅種群，不同初始覆蓋率以及不同迭代步長3個(gè)方面進(jìn)行仿真研究，挑選出合適的參數(shù)應(yīng)用于混沌果蠅算法，如圖1～圖3所示。所有算法均在MATLAB2012上進(jìn)行仿真模擬。

圖1 種群數(shù)目不同的網(wǎng)絡(luò)覆蓋率

圖2 初始覆蓋率不同的網(wǎng)絡(luò)覆蓋率

如圖1所示，選取固定的果蠅群 （初始覆蓋率為58.3%），步長h＝1，迭代200次。從圖1中可以看出數(shù)量大的果蠅群 （（N＝100））在算法前期體現(xiàn)出良好的收斂性和收斂精度，但隨著算法迭代，數(shù)量小的果蠅群 （N＝50）和數(shù)量大的果蠅群在收斂精度上漸漸趨于一致。

圖3 步長不同的網(wǎng)絡(luò)覆蓋率

如圖2所示，選取不同的果蠅群 （初始覆蓋率為59%、63%），步長h＝1，迭代200次，果蠅種群數(shù)量N＝50。從圖2中可看出初始覆蓋率為63%的果蠅算法全局收斂性和收斂精度均遠(yuǎn)高于初始覆蓋率為59%的果蠅算法。這表明果蠅算法的初始布局直接影響傳感器網(wǎng)絡(luò)最終布局的優(yōu)劣。

如圖3所示，選取固定的果蠅群，相同的迭代次數(shù)，不同的步長h。從圖3中可以看出，步長為兩個(gè)單位的果蠅群在前期收斂速度很快，但后期步長小的果蠅群收斂速度和精度卻漸漸超過步長大的果蠅群。這說明選擇合適果蠅步長將直接提升算法的性能。

如圖4～圖7所示，選取近些年深入研究的蛙跳和虛擬力算法與混沌果蠅算法作比較，蛙跳算法參數(shù)為：種群分組數(shù)m＝8，模因組青蛙數(shù)n＝8，組內(nèi)最大迭代數(shù)Ne＝8；虛擬力算法參數(shù)為：距離閾值dth＝10 m，Max＿Step＝2.5 m；混沌果蠅算法參數(shù)為：N＝100，h＝1，M＝50。圖4～圖7是4種算法的節(jié)點(diǎn)覆蓋圖，在邊長為50m的正方形監(jiān)測區(qū)域，25個(gè)傳感器節(jié)點(diǎn)理論最優(yōu)覆蓋率為78.5%。圖4為蛙跳算法200輪后節(jié)點(diǎn)覆蓋圖，占62.5%，達(dá)到最優(yōu)覆蓋率的79.6%；圖5為虛擬力算法200輪后節(jié)點(diǎn)覆蓋圖，占67.3%，達(dá)到最優(yōu)覆蓋率的85.7%；圖6為果蠅算法200輪后覆蓋圖，占72.7%，達(dá)到最優(yōu)覆蓋率的92.6%；圖7為混沌果蠅算法200輪后覆蓋圖，占76.4%，達(dá)到最優(yōu)覆蓋率的97.3%。仿真結(jié)果表明，果蠅算法和改進(jìn)果蠅算法要明顯優(yōu)于蛙跳和虛擬力算法，改進(jìn)果蠅算法更易于擺脫局部極值解，尋求全局最優(yōu)解。

如圖8所示，混沌果蠅算法和果蠅算法在收斂速度和收斂精度上遠(yuǎn)優(yōu)于虛擬力算法和蛙跳算法，更適用于WSN節(jié)點(diǎn)布局優(yōu)化。果蠅算法在前期性能較好，但在后期隨著網(wǎng)絡(luò)布局的穩(wěn)定漸漸收斂，陷于局部極值解；而混沌果蠅算法能夠在果蠅進(jìn)化時(shí)進(jìn)行混沌擾動，跳出局部搜索，進(jìn)行全局尋優(yōu)，具有更好的網(wǎng)絡(luò)布局優(yōu)化性能。

6 結(jié)束語

本文針對WSN傳統(tǒng)算法覆蓋率低、算法復(fù)雜高的問題，提出一種簡單、高效的混沌果蠅算法，并應(yīng)用于無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)布局。該算法通過在果蠅算法每次進(jìn)化時(shí)對當(dāng)前最優(yōu)解進(jìn)行混沌擾動，保證果蠅群在下輪迭代時(shí)具有一個(gè)更好的初始值。

圖4 蛙跳算法節(jié)點(diǎn)覆蓋

圖5 虛擬力算法節(jié)點(diǎn)覆蓋

圖6 果蠅算法節(jié)點(diǎn)覆蓋

圖7 混沌果蠅算法節(jié)點(diǎn)覆蓋

圖8 4種算法性能比較

通過MATLAB仿真結(jié)果表明，混沌果蠅算法能夠迅速跳出局部極值解，進(jìn)行全局搜索。相對于其它智能算法，混沌果蠅算法具有更高的網(wǎng)絡(luò)覆蓋率、更快的收斂速度以及更低的算法復(fù)雜度，更適應(yīng)于當(dāng)前的傳感器網(wǎng)絡(luò)布局優(yōu)化。隨著WSN發(fā)展迅速，應(yīng)用廣泛，下一步將重點(diǎn)研究傳感器節(jié)點(diǎn)基于混沌果蠅算法的動態(tài)半徑規(guī)劃。

［1］WANG Chengliang，WANG Qiang.Activity－aware ＆energy balance based routing protocol for wireless sensor networks［J］.Journal of Beijing University of Aeronautics and Astronautics，2014，40 （1）：10－17 （in Chinese）.［汪成亮，王強(qiáng).基于活動預(yù)測和能耗均衡的WSN路由算法 ［J］.北京航空航天大學(xué)學(xué)報(bào).2014，40 （1）：10－17.］

［2］LI Qiangyi，MA Dongqian，ZHANG Juwei.Nodes deployment algorithm based on perceived probability of wireless sensor network ［J］.Computer Measurement ＆ Control，2014，22（2）：643－645 （in Chinese）. ［李強(qiáng)懿，馬冬前，張聚偉.基于感知概率的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署算法 ［J］.計(jì)算機(jī)測量與控制，2014，22 （2）：643－645.］

［3］LIU Cuiping，ZHANG Haitao，BAI Ge.Node deployment of wireless sensor network based on glowworm swarm optimization algorithm ［J］.Journal of Computer Applications，2013，33（4）：905－907 （in Chinese）. ［劉翠蘋，張海濤，白舸.基于螢火蟲群優(yōu)化算法的無線傳感器節(jié)點(diǎn)部署 ［J］.計(jì)算機(jī)應(yīng)用，2013，33 （4）：905－907.］

［4］SONG Mingzhi，YANG Le.Improving coverage of wireless sensor network using enhanced adaptive PSO algorithm ［J］.Application Research of Computers，2013，30 （11）：3472－3475（in Chinese）.［宋明智，楊樂.基于改進(jìn)自適應(yīng)PSO算法的WSN覆蓋優(yōu)化方法 ［J］.計(jì)算機(jī)應(yīng)用研究，2013，30（11）：3472－3475.］

［5］LONG Teng，SUN Hui，ZHAO Jia.Research of mobile node deployment in WSN based on improved frog leaping algorithm［J］.Computer Engineering，2012，38 （5）：96－98 （in Chinese）.［龍騰，孫輝，趙嘉.基于改進(jìn)蛙跳算法的 WSN移動節(jié)點(diǎn)部署研究 ［J］.計(jì)算機(jī)工程，2012，38 （5）：96－98.］

［6］PAN Wenchao.Using fruit fly optimization algorithm optimized general regression neural network to construct the operating performance of enterprises model ［J］.Journal of Taiyuan University of Technology，2011，29 （4）：1－5 （in Chinese）. ［潘文超.應(yīng)用果蠅優(yōu)化算法優(yōu)化廣義回歸神經(jīng)網(wǎng)絡(luò)進(jìn)行企業(yè)經(jīng)營績效評估 ［J］.太原理工大學(xué)學(xué)報(bào)，2011，29 （4）：1－5.］

［7］CHENG Hui，LIU Chengzhong.Mixed fruit fly optimization algorithm based on chaotic mapping ［J］.Computer Enginee－ring，2013，39 （5）：218－221 （in Chinese）. ［程慧，劉成忠.基于混沌映射的混合果蠅優(yōu)化算法 ［J］.計(jì)算機(jī)工程，2013，39 （5）：218－221.］

［8］HAN Junying，LIU Chengzhong.Fruit fly optimization algorithm with adaptive mutation ［J］.Application Research of Computers，2013，30 （9）：2641－2644 （in Chinese）. ［韓俊英，劉成忠.自適應(yīng)變異的果蠅優(yōu)化算法 ［J］.計(jì)算機(jī)應(yīng)用研究，2013，30 （9）：2641－2644.］

［9］LIU Changping，YE Chunming.Firefly algorithm with chaotic search strategy ［J］.Journal of Systems ＆ Management，2013，22 （4）：538－543 （in Chinese）. ［劉長平，葉春明.具有混沌搜索策略的螢火蟲優(yōu)化算法 ［J］.系統(tǒng)管理學(xué)報(bào)，2013，22 （4）：538－543.］

［10］ZHAN Mengmeng.Reactive power optimization of distribution network based on modified chaos genetic algorithm ［D］.Hangzhou：Hangzhou Dianzi University，2013：19－21 （in Chinese）.［詹萌萌.基于改進(jìn)混沌遺傳算法的配電網(wǎng)無功優(yōu)化 ［D］.杭州：杭州電子科技大學(xué)，2013：19－21.］

［11］LI Li.Strategy of WSN coverage optimization by improved artificial fish swarm algorithm ［J］.Microelectronics ＆ Computer，2013，30 （2）：83－86 （in Chinese）. ［李麗.基于改進(jìn)魚群算法的WSN覆蓋優(yōu)化策略 ［J］.微電子學(xué)與計(jì)算機(jī)，2013，30 （2）：83－86.］

［12］PAN Wenchao.A new fruit fly optimization algorithm：Taking the financial distress model as an example ［J］.Knowledge－Based Systems，2012，26：69－74.