基于粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化

張紅霞

摘 要： 傳統(tǒng)無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法所選算法的結(jié)構(gòu)不合理，使其覆蓋能力、迭代能力和有效性無(wú)法維系網(wǎng)絡(luò)基本功能，為此提出粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法。通過(guò)構(gòu)建無(wú)線傳感器網(wǎng)絡(luò)認(rèn)知模型，將網(wǎng)絡(luò)覆蓋優(yōu)化工作轉(zhuǎn)化成求取目標(biāo)物體最大覆蓋幾率問(wèn)題，使用粒子群算法對(duì)模型進(jìn)行編碼，利用模型適應(yīng)度函數(shù)給出的約束值對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)位置進(jìn)行更新，實(shí)現(xiàn)對(duì)無(wú)線傳感器網(wǎng)絡(luò)覆蓋率的優(yōu)化。通過(guò)分析仿真實(shí)驗(yàn)結(jié)論可知，與傳統(tǒng)方法相比，該方法具有更強(qiáng)的覆蓋能力、迭代能力和有效性。

關(guān)鍵詞： 粒子群算法； 無(wú)線傳感器網(wǎng)絡(luò)； 覆蓋優(yōu)化方法； 模型適應(yīng)度函數(shù)

中圖分類(lèi)號(hào)： TN711?34； TP212.9 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2017）09?0050?04

Abstract： The algorithm selected by the traditional wireless sensor network coverage optimization method has unreasonable structure， which makes its coverage ability， iteration ability and effectiveness incapable of sustaining the network basic functions， therefore a wireless sensor network coverage optimization method based on particle swarm optimization algorithm is proposed. The cognitive model of the wireless sensor network is constructed to convert the network coverage optimization into the getting of the maximum coverage probability of the target object， and encoded with the particle swarm optimization algorithm. The constraint value given by the model fitness function is used to update the location of network node， so as to optimize the coverage probability of the wireless sensor network. The simulation experiment conclusion indicates， in comparison with the traditional methods， the method has higher coverage ability， iteration ability and effectiveness.

Keywords： particle swarm optimization algorithm； wireless sensor network； coverage optimization method； model fitness function

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)是一種以監(jiān)控為基礎(chǔ)，對(duì)目標(biāo)事物實(shí)施觀察的技術(shù)，對(duì)人類(lèi)生產(chǎn)、生活的各個(gè)方面有著深遠(yuǎn)影響。無(wú)線傳感器網(wǎng)絡(luò)擁有若干節(jié)點(diǎn)，所有節(jié)點(diǎn)上都安裝了微處理芯片和傳感器，為節(jié)點(diǎn)提供數(shù)據(jù)分析和傳輸能力，進(jìn)而獲取到目標(biāo)事物的監(jiān)控?cái)?shù)據(jù)，預(yù)測(cè)事物的發(fā)展方向[1]。但節(jié)點(diǎn)的分析和傳輸能力并非是無(wú)窮的，若使無(wú)線傳感器網(wǎng)絡(luò)能夠更好地達(dá)成其對(duì)目標(biāo)事物的預(yù)測(cè)功能，需要令無(wú)線傳感器網(wǎng)絡(luò)對(duì)目標(biāo)事物實(shí)施完全覆蓋[2]。這一問(wèn)題的提出為學(xué)術(shù)界指引了新的研究方向。

無(wú)線傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化實(shí)際上是在節(jié)點(diǎn)資源有限的條件下，經(jīng)由變更節(jié)點(diǎn)方位、增減節(jié)點(diǎn)布置、改善網(wǎng)絡(luò)性能等方式，優(yōu)化節(jié)點(diǎn)資源劃分的問(wèn)題，其與節(jié)點(diǎn)能量和目標(biāo)事物監(jiān)控等問(wèn)題關(guān)系密切[3]。傳統(tǒng)的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法對(duì)無(wú)線傳感器網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行了深層分析，有效反映了節(jié)點(diǎn)能量和目標(biāo)事物監(jiān)控等信息的流通方向。但由于所選算法的結(jié)構(gòu)不合理，傳統(tǒng)方法的覆蓋能力、迭代能力和有效性均需要得到進(jìn)一步改善[4]。因而，使用粒子群算法的強(qiáng)迭代能力和實(shí)用性，提出一種能夠?qū)崿F(xiàn)節(jié)點(diǎn)資源實(shí)質(zhì)性優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法。

1 無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問(wèn)題

1.1 無(wú)線傳感器網(wǎng)絡(luò)模型

在無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)數(shù)量以及節(jié)點(diǎn)劃分區(qū)域直接關(guān)系著無(wú)線傳感器網(wǎng)絡(luò)對(duì)目標(biāo)事物覆蓋死角面積，增多節(jié)點(diǎn)數(shù)量能夠提高網(wǎng)絡(luò)覆蓋密度。將節(jié)點(diǎn)更多地劃分在離目標(biāo)事物距離近的區(qū)域內(nèi)，可以增強(qiáng)網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)陌踩院蜏?zhǔn)確性[5]。無(wú)線傳感器網(wǎng)絡(luò)認(rèn)知模型搭建的目的就是對(duì)無(wú)線傳感器網(wǎng)絡(luò)的覆蓋死角進(jìn)行定義和測(cè)量，為此，基于粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法可看成是對(duì)認(rèn)知模型的參數(shù)優(yōu)化問(wèn)題。

傳感器網(wǎng)絡(luò)節(jié)點(diǎn)容易受到噪音和電磁波的擾亂造成傳輸誤差，這些因不可抗拒因素導(dǎo)致的一系列縮減網(wǎng)絡(luò)覆蓋率問(wèn)題被統(tǒng)稱(chēng)為無(wú)效事件[6]。設(shè)無(wú)線傳感器網(wǎng)絡(luò)認(rèn)知模型在起點(diǎn)坐標(biāo)為、終點(diǎn)坐標(biāo)為的節(jié)點(diǎn)上測(cè)量到存在無(wú)效事件的幾率為，降低即可提高覆蓋率。的定義式為：

2 粒子群算法的傳感器網(wǎng)絡(luò)覆蓋優(yōu)化

根據(jù)上述描述，使用粒子群算法優(yōu)化無(wú)線傳感器網(wǎng)絡(luò)覆蓋率，簡(jiǎn)要介紹粒子群算法的基本原理，對(duì)網(wǎng)絡(luò)覆蓋優(yōu)化流程進(jìn)行重點(diǎn)設(shè)計(jì)。

2.1 粒子群算法的工作原理

粒子群算法是進(jìn)化算法的一個(gè)流派，也是生物隨機(jī)索引算法中的一個(gè)分支，是當(dāng)前的研究熱點(diǎn)。粒子群算法的基本原理如圖1所示。

由圖1可知，粒子群算法的實(shí)現(xiàn)非常簡(jiǎn)單，其基本原理就是使用迭代方式得到最優(yōu)解，對(duì)粒子的速度和坐標(biāo)進(jìn)行實(shí)時(shí)更新[7]。算法先初始化粒子，將歷史最優(yōu)解賦予粒子。在算法進(jìn)入迭代流程前，先設(shè)置一個(gè)位置參數(shù)的最大值，即循環(huán)系數(shù)，負(fù)責(zé)控制算法的迭代次數(shù)。每迭代一次，位置參數(shù)的值便增加1，當(dāng)大于循環(huán)系數(shù)，則停止迭代。粒子群算法的迭代工作可得到粒子適應(yīng)度，并以適應(yīng)度為標(biāo)準(zhǔn)依次更新粒子的歷史最優(yōu)解、粒子群最優(yōu)解以及粒子的速度和坐標(biāo)[8]。粒子速度與坐標(biāo)的更新方程為：

式中：是粒子初始設(shè)定值；是粒子群算法的學(xué)習(xí)因子，通常取值為2；是隨機(jī)參數(shù)；是粒子適應(yīng)度約束值。

2.2 無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化流程

基于粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法的優(yōu)化流程如圖2所示。

首先對(duì)模型進(jìn)行編碼，其目的是固定節(jié)點(diǎn)位置，粒子群算法的編碼是一種二進(jìn)制百兆數(shù)據(jù)碼，編碼長(zhǎng)度與無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量相等。當(dāng)模型中節(jié)點(diǎn)參數(shù)滿足為獲取的最大值，粒子群算法的編碼結(jié)果應(yīng)滿足下式：

式（6）中的元素取值為0或1，0表示傳感器節(jié)點(diǎn)可以被重新安置，1表示固定節(jié)點(diǎn)。

適應(yīng)度是評(píng)價(jià)最優(yōu)解質(zhì)量的函數(shù)，在粒子群算法進(jìn)行迭代工作前，需要提前設(shè)置適應(yīng)度函數(shù)并計(jì)算出無(wú)線傳感器網(wǎng)絡(luò)認(rèn)知模型的初始適應(yīng)度，方便對(duì)迭代結(jié)果進(jìn)行對(duì)比，輸出最合適的節(jié)點(diǎn)優(yōu)化位置，實(shí)現(xiàn)對(duì)無(wú)線傳感器網(wǎng)絡(luò)覆蓋率的最佳優(yōu)化。

在式（6）給出的編碼基礎(chǔ)上，使用式（7）計(jì)算模型適應(yīng)度：

式中：無(wú)線傳感器網(wǎng)絡(luò)覆蓋率瞬時(shí)值可通過(guò)式（4）進(jìn)行求取；和分別表示在無(wú)線傳感器網(wǎng)絡(luò)中的初始權(quán)重和實(shí)際權(quán)重。

當(dāng)式（7）滿足時(shí)，可達(dá)最大值。因此，粒子群算法迭代工作的目標(biāo)就是令。實(shí)現(xiàn)迭代目標(biāo)后，基于粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法需要對(duì)無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)位置進(jìn)行更新，并輸出優(yōu)化后的無(wú)線傳感器網(wǎng)絡(luò)覆蓋率。

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)利用計(jì)算機(jī)仿真技術(shù)給出一個(gè)半徑為3 m的無(wú)線傳感器網(wǎng)絡(luò)。仿真實(shí)驗(yàn)初期，無(wú)線傳感器網(wǎng)絡(luò)的初始覆蓋率為21%。在此基礎(chǔ)上對(duì)本文提出的基于粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法進(jìn)行仿真實(shí)驗(yàn)。同時(shí)，對(duì)文獻(xiàn)[4]和文獻(xiàn)[7]中的方法也分別進(jìn)行仿真實(shí)驗(yàn)。將三種方法下的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，確定出本文方法的覆蓋能力、迭代能力和有效性是否能夠超越傳統(tǒng)方法。

提升無(wú)線傳感器網(wǎng)絡(luò)覆蓋率是文獻(xiàn)[4，7]以及本文方法提出的基本目標(biāo)。在最大化提升覆蓋率的同時(shí)，方法的迭代性能也不容忽視。迭代性能是保證無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法能夠持續(xù)提升覆蓋率的基礎(chǔ)，迭代性能不強(qiáng)的方法，即便在某一節(jié)點(diǎn)上的覆蓋率很高，也無(wú)法長(zhǎng)期維持無(wú)線傳感器網(wǎng)絡(luò)的穩(wěn)定運(yùn)行[9]。圖3，圖4分別是三種方法的覆蓋率、迭代次數(shù)與無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)感知半徑的關(guān)系圖。

由圖3可知，文獻(xiàn)[4，7]、本文方法的覆蓋率在仿真實(shí)驗(yàn)開(kāi)始初期就出現(xiàn)了較大的分歧，并且，文獻(xiàn)[4]的初期覆蓋率最低，本文方法最高。隨著節(jié)點(diǎn)感知半徑的增大，文獻(xiàn)[4]的覆蓋率增長(zhǎng)迅速，最后穩(wěn)定在85%左右。文獻(xiàn)[7]在節(jié)點(diǎn)感知半徑為3 m時(shí)的覆蓋率較高，為92%，并仍存在增長(zhǎng)趨勢(shì)。本文方法在節(jié)點(diǎn)感知半徑為3 m時(shí)的覆蓋率最高，為98%，也存在增長(zhǎng)趨勢(shì)。

將圖4代入到圖3中進(jìn)行分析可知，在相同的仿真實(shí)驗(yàn)條件下，本文方法能夠以最少的迭代次數(shù)獲取最高的覆蓋率。綜合來(lái)講，與傳統(tǒng)方法相比，本文方法具有更強(qiáng)的覆蓋能力和迭代能力。

無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法的有效性表現(xiàn)在相同覆蓋率條件下傳感器的運(yùn)轉(zhuǎn)數(shù)量，數(shù)量越少，方法的資源利用率和適應(yīng)度越高，有效性就越強(qiáng)。仿真實(shí)驗(yàn)在無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)上安裝了80個(gè)傳感器，在不斷變更覆蓋率的條件下，將三種方法下傳感器的運(yùn)轉(zhuǎn)數(shù)量記錄于表1中。

由表1可以得出，從傳感器運(yùn)轉(zhuǎn)數(shù)量的平均值、極大值和極小值來(lái)看，文獻(xiàn)[4，7]的傳感器運(yùn)轉(zhuǎn)數(shù)量都要多于本文方法，驗(yàn)證出本文方法能夠合理利用無(wú)線傳感器網(wǎng)絡(luò)資源，適應(yīng)度高，有效性強(qiáng)。

4 結(jié) 語(yǔ)

本文提出基于粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法，構(gòu)建了無(wú)線傳感器網(wǎng)絡(luò)認(rèn)知模型，對(duì)網(wǎng)絡(luò)覆蓋優(yōu)化的具體流程進(jìn)行重點(diǎn)設(shè)計(jì)，并在仿真實(shí)驗(yàn)中對(duì)方法的覆蓋能力、迭代能力和有效性進(jìn)行驗(yàn)證。結(jié)果表明，與傳統(tǒng)方法相比，本文方法具有更強(qiáng)的覆蓋能力、迭代能力和有效性，能夠?qū)崿F(xiàn)對(duì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)資源的實(shí)質(zhì)性優(yōu)化。

參考文獻(xiàn)

[1] 林威建，郝泳濤.基于改進(jìn)粒子群的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].電腦知識(shí)與技術(shù)，2015，11（28）：36?39.

[2] 王改云，胡錦艷.基于BP神經(jīng)網(wǎng)絡(luò)和蟻群的WSN分簇算法的研究[J].現(xiàn)代電子技術(shù)，2015，38（17）：45?48.

[3] 彭大志，王艷.基于混合粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議[J].測(cè)控技術(shù)，2014，33（7）：93?97.

[4] CLARKE D P， AL?ABDELI Y M， KOTHAPALLI G. The impact of using particle swarm optimization on the operational characteristics of a stand?alone hydrogen system with on?site water production [J]. International journal of hydrogen energy， 2014， 39（28）： 15307?15319.

[5] 馮秀芳，呂淑芳.基于RSSI和分步粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].控制與決策，2014，29（11）：1966?1972.

[6] 劉明偉，張曉濱，楊東山.移動(dòng)環(huán)境下多情景源用戶情景序列的提取[J].西安工程大學(xué)學(xué)報(bào)，2015，29（6）：746?750.

[7] 馮琳，冉曉旻，梅關(guān)林.基于改進(jìn)粒子群算法的無(wú)線傳感網(wǎng)絡(luò)覆蓋優(yōu)化[J].太赫茲科學(xué)與電子信息學(xué)報(bào)，2015，13（3）：486?490.

[8] 汪華斌，曾少寧，羅偉.基于粒子群優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].惠州學(xué)院學(xué)報(bào)，2014，34（3）：67?70.

[9] 張亞明，高曉丁.基于PID控制技術(shù)的供水網(wǎng)控制系統(tǒng)設(shè)計(jì)[J].西安工程大學(xué)學(xué)報(bào)，2015，29（5）：578?582.

[10] 魏全增，陳機(jī)林，高強(qiáng)，等.基于遺傳優(yōu)化RBF神經(jīng)網(wǎng)絡(luò)的電動(dòng)負(fù)載模擬器控制[J].現(xiàn)代電子技術(shù)，2015，38（21）：113?117.