基于粒子群優(yōu)化算法的水質(zhì)傳感器優(yōu)化部署研究*

余幸運(yùn)， 孫 茜， 王小藝， 許繼平， 王 立， 張慧妍

(北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，北京 100048)

?

基于粒子群優(yōu)化算法的水質(zhì)傳感器優(yōu)化部署研究*

余幸運(yùn)， 孫 茜， 王小藝， 許繼平， 王 立， 張慧妍

(北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，北京 100048)

針對(duì)不同污染程度的水域提出重點(diǎn)監(jiān)測(cè)區(qū)域的集中性覆蓋監(jiān)測(cè)問題。在重點(diǎn)監(jiān)測(cè)區(qū)域的傳感器網(wǎng)絡(luò)部署之前，對(duì)于監(jiān)測(cè)水域大面積覆蓋監(jiān)測(cè)問題采用一種基于加權(quán)因子調(diào)整的粒子群優(yōu)化(PSO)算法，對(duì)比了不同粒子群數(shù)目對(duì)網(wǎng)絡(luò)覆蓋能力的影響。仿真結(jié)果表明：PSO算法保證在最大覆蓋率的條件下，實(shí)現(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)快速自適應(yīng)均勻部署，運(yùn)算速度快且能夠避免局部最優(yōu)；網(wǎng)絡(luò)覆蓋能力先隨粒子群數(shù)目的增加而增大，當(dāng)粒子群個(gè)數(shù)達(dá)到20后，網(wǎng)絡(luò)覆蓋能力隨之減小；網(wǎng)絡(luò)實(shí)現(xiàn)最大范圍均勻部署之后，能較好地保障重點(diǎn)水域的集中性覆蓋監(jiān)測(cè)，從而保障真實(shí)客觀的水質(zhì)監(jiān)測(cè)數(shù)據(jù)。

傳感器網(wǎng)絡(luò)； 覆蓋部署； 水環(huán)境監(jiān)測(cè)； 粒子群優(yōu)化

0 引 言

水質(zhì)監(jiān)測(cè)是用科學(xué)的方法監(jiān)測(cè)和檢測(cè)反映水體質(zhì)量的變化趨勢(shì)及污染的來(lái)龍去脈，是監(jiān)視和測(cè)定水體中污染物種類、各類污染物濃度及變化趨勢(shì)，評(píng)價(jià)水質(zhì)狀況的過程。由于近幾年內(nèi)生活廢水、工業(yè)廢水和惡劣氣象條件對(duì)水環(huán)境的劇烈影響，致使不同水域的污染程度各不相同，希望對(duì)于污染嚴(yán)重的區(qū)域進(jìn)行實(shí)時(shí)監(jiān)控，以保障水質(zhì)信息的全面真實(shí)可靠。由于在實(shí)際的水環(huán)境監(jiān)測(cè)系統(tǒng)中，水質(zhì)監(jiān)測(cè)往往通過傳感器網(wǎng)絡(luò)監(jiān)測(cè)獲得水質(zhì)參數(shù)數(shù)據(jù)，合理部署傳感器節(jié)點(diǎn)的位置使網(wǎng)絡(luò)的覆蓋范圍最大，那么獲得數(shù)據(jù)實(shí)時(shí)可靠性也就越大，水質(zhì)狀況的信息越完整。傳統(tǒng)的水環(huán)境監(jiān)測(cè)系統(tǒng)一般采用大規(guī)模投放傳感器的方式，這樣的投放方式快速卻很難一次性地將傳感器節(jié)點(diǎn)放置在合適位置，很容易形成感知重疊區(qū)和盲區(qū)。另外一種方式是將監(jiān)測(cè)水域平均分割為固定大小的網(wǎng)格，并在每個(gè)網(wǎng)格的中心位置布測(cè)點(diǎn)，這種方法簡(jiǎn)單易行，但往往會(huì)導(dǎo)致相鄰斷面出現(xiàn)水質(zhì)監(jiān)測(cè)結(jié)果相近，造成監(jiān)測(cè)資源浪費(fèi)。文獻(xiàn)[1]針對(duì)無(wú)線傳感器網(wǎng)絡(luò)(WSNs)節(jié)點(diǎn)定位問題，闡述了WSNs的分布迭代式定位方法，仿真證明了該方法能有效提高了節(jié)點(diǎn)定位精度；文獻(xiàn)[2]提出了一種近鄰點(diǎn)聯(lián)合測(cè)距修正粒子群優(yōu)化(PSO)的定位算法，仿真證明了修正定位算法能有效提高定位精度和穩(wěn)定性；文獻(xiàn)[3]采用多目標(biāo)優(yōu)化的二進(jìn)制粒子群算法對(duì)節(jié)點(diǎn)部署進(jìn)行多目標(biāo)優(yōu)化，選取不同傳感器對(duì)不同區(qū)域進(jìn)行覆蓋監(jiān)測(cè)；文獻(xiàn)[4]提出蟻群算法實(shí)現(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的非均勻覆蓋，雖然結(jié)果中對(duì)比了幾種算法對(duì)覆蓋率的影響，但對(duì)實(shí)驗(yàn)過程沒有很好的說(shuō)明；文獻(xiàn)[5]通過模擬魚群行為，并結(jié)合擁擠度控制，使節(jié)點(diǎn)自主趨向并覆蓋事件，但沒有說(shuō)明在整片監(jiān)測(cè)水域中傳感器節(jié)點(diǎn)的布置情況；文獻(xiàn)[6]提出一種約束PSO的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法，提高節(jié)點(diǎn)的定位精度，但沒有說(shuō)明網(wǎng)絡(luò)覆蓋能力的問題；文獻(xiàn)[7，8]采用PSO算法實(shí)現(xiàn)傳感器網(wǎng)絡(luò)的覆蓋增強(qiáng)，但是沒有說(shuō)明網(wǎng)絡(luò)的分布情況；文獻(xiàn)[9]將聚集度指標(biāo)作為判定條件應(yīng)用于PSO中，實(shí)現(xiàn)參數(shù)的自適應(yīng)調(diào)整，仿真證明了該算法能提高網(wǎng)絡(luò)覆蓋率。

為克服以上問題，本文采用加權(quán)因子調(diào)整的PSO算法對(duì)傳感器節(jié)點(diǎn)進(jìn)行自適應(yīng)部署，通過更新節(jié)點(diǎn)的位置快速計(jì)算每次迭代的最優(yōu)解，并提高收斂速度。本文考慮到水下環(huán)境復(fù)雜多變，監(jiān)測(cè)區(qū)域動(dòng)態(tài)性較強(qiáng)等因素的影響，利用傳感器節(jié)點(diǎn)可移動(dòng)性好的特點(diǎn)，采用粒子群智能部署算法，以適應(yīng)值為最終優(yōu)化目標(biāo)，綜合鄰居節(jié)點(diǎn)信息實(shí)現(xiàn)傳感器節(jié)點(diǎn)的自適應(yīng)均勻部署，在實(shí)現(xiàn)重點(diǎn)區(qū)域監(jiān)測(cè)之前保障最大覆蓋范圍，部署方式快速且可靠性高。

1 網(wǎng)絡(luò)覆蓋率度量標(biāo)準(zhǔn)

本文在監(jiān)測(cè)水域的二維平面上用PSO算法進(jìn)行節(jié)點(diǎn)自動(dòng)部署，以區(qū)域最大覆蓋和重點(diǎn)區(qū)域的覆蓋監(jiān)測(cè)為目標(biāo)，針對(duì)不同區(qū)域進(jìn)行不同程度的覆蓋，從而保證監(jiān)測(cè)數(shù)據(jù)的真實(shí)客觀性并克服了傳統(tǒng)部署的資源浪費(fèi)問題，同樣的方法也可以推廣到三維空間上?，F(xiàn)假設(shè)工廠將處理未達(dá)排放標(biāo)準(zhǔn)的污染廢水排向附近水域，在這片水域中進(jìn)行傳感器節(jié)點(diǎn)的部署，使網(wǎng)絡(luò)覆蓋率最大并對(duì)受影響較大的區(qū)域進(jìn)行實(shí)時(shí)重點(diǎn)監(jiān)測(cè)。在100 m×100 m的水域內(nèi)部署傳感器節(jié)點(diǎn)，每2 m劃分一個(gè)網(wǎng)格，如圖1所示，圖中的方框內(nèi)表示需要重點(diǎn)監(jiān)測(cè)的區(qū)域。覆蓋率的計(jì)算方式采用網(wǎng)格點(diǎn)實(shí)現(xiàn)，定義為受到監(jiān)測(cè)的區(qū)域大小與整個(gè)監(jiān)測(cè)目標(biāo)區(qū)域大小的比值。圖1中所產(chǎn)生的網(wǎng)格點(diǎn)記為K，區(qū)域內(nèi)的網(wǎng)格點(diǎn)總數(shù)記作KK，第K個(gè)網(wǎng)格點(diǎn)被一個(gè)傳感器監(jiān)測(cè)到的概率記為c。本文采用布爾感知模型完成傳感器的覆蓋監(jiān)測(cè)，模型的數(shù)學(xué)表達(dá)式如下

(1)

(2)

統(tǒng)計(jì)檢測(cè)概率等于1的網(wǎng)格數(shù)量，進(jìn)而計(jì)算出目標(biāo)區(qū)域的覆蓋率。

圖1 監(jiān)測(cè)水域模型示意圖Fig 1 Schematic diagram of monitoring water area model

2 算法設(shè)計(jì)

2.1 PSO基本原理

假設(shè)在一個(gè)二維平面上，需要監(jiān)測(cè)的區(qū)域?yàn)镾，在解的D維搜索空間里有n個(gè)粒子作為預(yù)備解，隨機(jī)部署m個(gè)傳感器節(jié)點(diǎn)，則群體中的第i個(gè)粒子位置為si=(xi1,yi1;xi2,yi2;xi3,yi3;…;xim,yim)，其中，每一個(gè)傳感器節(jié)點(diǎn)在更新過程中有一個(gè)速度向量，用于更新當(dāng)前速度和位置。每個(gè)粒子在自動(dòng)更新過程中，會(huì)經(jīng)歷一個(gè)表征個(gè)體最優(yōu)解的位置和一個(gè)表征全局最優(yōu)解的位置。首先是每個(gè)傳感器節(jié)點(diǎn)根據(jù)當(dāng)前的速度和自身位置以及鄰居節(jié)點(diǎn)的位置更新當(dāng)前的速度，進(jìn)而更新當(dāng)前的位置，所有傳感器節(jié)點(diǎn)的當(dāng)前速度和當(dāng)前位置得到更新之后就計(jì)算一次適應(yīng)值，粒子則通過新的適應(yīng)值不斷跟蹤個(gè)體最優(yōu)解Pid=(pi1,pi2,pi3,…,piD)和全局最優(yōu)解Pg=(pg1,pg2,pg3,……,pgd)進(jìn)行搜索，以最優(yōu)適應(yīng)值為目標(biāo)更新自己。適應(yīng)值由傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)位置所確定的覆蓋率大小決定，每次更新之后的覆蓋率應(yīng)當(dāng)大于上次更新之后的覆蓋率，在達(dá)到最終條件或最大迭代次數(shù)時(shí)終止。

根據(jù)粒子的自動(dòng)移動(dòng)特點(diǎn)，速度和位置的更新公式為

(3)

(4)

2.2 重點(diǎn)區(qū)域監(jiān)測(cè)

經(jīng)過PSO運(yùn)算后的傳感器節(jié)點(diǎn)位置是使網(wǎng)絡(luò)覆蓋均勻且覆蓋率最大的最優(yōu)位置，考慮到受污染嚴(yán)重的區(qū)域需要更多的傳感器進(jìn)行監(jiān)測(cè)，本文運(yùn)用傳感器節(jié)點(diǎn)可以自由移動(dòng)的特點(diǎn)，將距離重點(diǎn)監(jiān)測(cè)區(qū)域小于傳感器半徑的節(jié)點(diǎn)，部署到重點(diǎn)監(jiān)測(cè)區(qū)域內(nèi)，實(shí)現(xiàn)對(duì)污染嚴(yán)重區(qū)域的實(shí)時(shí)重點(diǎn)監(jiān)測(cè)。

3 仿真結(jié)果

本文采用PSO算法對(duì)傳感器節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域內(nèi)進(jìn)行網(wǎng)絡(luò)覆蓋率最大化的最優(yōu)部署，在100m×100m的水域內(nèi)，以2m為邊長(zhǎng)劃分網(wǎng)格以計(jì)算覆蓋率。設(shè)定傳感器半徑為10m，最大迭代次數(shù)為300，最小覆蓋率為50 %，粒子速度更新加權(quán)因子采用線性變化的調(diào)節(jié)方式，粒子速度更新的加權(quán)常數(shù)c1和c2設(shè)定為2。迭代計(jì)算中，當(dāng)?shù)螖?shù)大于最大迭代次數(shù)或者覆蓋率小于最小覆蓋率，則計(jì)算停止，保存最優(yōu)結(jié)果退出粒子更新過程。為了選取最合適的粒子群數(shù)目，本文首先進(jìn)行了多組不同粒子群數(shù)目的實(shí)驗(yàn)仿真，結(jié)果如圖2，實(shí)驗(yàn)結(jié)果表明，隨著粒子群數(shù)目的增大，網(wǎng)絡(luò)覆蓋率先增大后減小，當(dāng)粒子群數(shù)目為20時(shí)，網(wǎng)絡(luò)覆蓋率最大。

基于PSO的網(wǎng)絡(luò)覆蓋率優(yōu)化的最終仿真結(jié)果如圖3～圖6，圖3表示在設(shè)有重點(diǎn)監(jiān)測(cè)區(qū)域的水域內(nèi)隨機(jī)部署傳感器節(jié)點(diǎn)的位置，一般應(yīng)用于傳感器網(wǎng)絡(luò)的初始部署，監(jiān)測(cè)水域內(nèi)部的方框內(nèi)需要重點(diǎn)監(jiān)測(cè)的區(qū)域。圖4是節(jié)點(diǎn)隨機(jī)部署經(jīng)過PSO算法迭代更新后的最優(yōu)位置，此時(shí)網(wǎng)絡(luò)節(jié)點(diǎn)實(shí)現(xiàn)均勻部署且覆蓋率取得最大。

圖2 粒子群數(shù)目對(duì)網(wǎng)絡(luò)覆蓋率的影響Fig 2 Effect of particle swarm number on network coverage

圖3 傳感器網(wǎng)絡(luò)隨機(jī)部署Fig 3 Random deployment of sensor networks

圖4 傳感器網(wǎng)絡(luò)均勻優(yōu)化部署Fig 1 Acoustic field of two different probes in oil pipeline

圖5是PSO下覆蓋率的更新變化過程，可見傳感器的初始隨機(jī)部署下的覆蓋率并不是很大，這反映出在傳統(tǒng)部署中，隨機(jī)拋灑傳感器節(jié)點(diǎn)的部署方式?jīng)]有經(jīng)過PSO后的部署方式覆蓋范圍大。經(jīng)過PSO的傳感器網(wǎng)絡(luò)覆蓋率在全局和局部上都可以提高到0.837 6，說(shuō)明PSO 的優(yōu)化性能有很高的有效性和可靠性，且不容易陷入局部最優(yōu)。圖6是在傳感器網(wǎng)絡(luò)滿足目標(biāo)函數(shù)的最優(yōu)部署前提下，利用傳感器節(jié)點(diǎn)可移動(dòng)的特點(diǎn)，將重點(diǎn)監(jiān)測(cè)區(qū)域周邊，距離小于傳感器半徑的節(jié)點(diǎn)移動(dòng)到重點(diǎn)監(jiān)測(cè)區(qū)域內(nèi)，實(shí)現(xiàn)實(shí)時(shí)重點(diǎn)監(jiān)測(cè)，其他區(qū)域仍可保證均勻最大范圍的部署方式。

圖5 網(wǎng)絡(luò)覆蓋率更新過程Fig 5 Network coverage update process

圖6 傳感器網(wǎng)絡(luò)對(duì)重點(diǎn)監(jiān)測(cè)區(qū)域的有效部署Fig 6 Sensor network to optimize the final deployment

4 結(jié)束語(yǔ)

采用PSO算法以最大覆蓋率為最優(yōu)目標(biāo)對(duì)傳感器節(jié)點(diǎn)進(jìn)行最優(yōu)部署，使網(wǎng)絡(luò)在監(jiān)測(cè)水域上達(dá)到最大范圍的覆蓋，從而測(cè)量到最完整準(zhǔn)確的水質(zhì)信息，并針對(duì)重點(diǎn)監(jiān)測(cè)水域進(jìn)行了集中性的實(shí)時(shí)覆蓋監(jiān)測(cè)。本文仿真結(jié)果說(shuō)明了算法的有效性，對(duì)傳感器網(wǎng)絡(luò)的重點(diǎn)區(qū)域的集中性監(jiān)測(cè)也使本文的研究具有重要的實(shí)際意義。值得注意的是，粒子群數(shù)目的選取需要根據(jù)經(jīng)驗(yàn)和實(shí)驗(yàn)判斷，選取最優(yōu)的參數(shù)值，能夠保證得到最好的仿真結(jié)果。

[1] 趙 吉，紀(jì)志成.基于量子行為粒子群優(yōu)化算法的定位技術(shù)研究[J].傳感器與微系統(tǒng)，2012，31(5):58-61.[2] 王 哲，李 平.近鄰點(diǎn)聯(lián)合測(cè)距修正粒子群優(yōu)化定位算法[J].傳感器與微系統(tǒng)，2016,35(8):130-133.

[3] 冀文娟，石為人，李 明，等.異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中多目標(biāo)優(yōu)化節(jié)點(diǎn)部署策略[J].傳感器與微系統(tǒng)，2012，31(3):29-31.

[4] 彭麗英.改進(jìn)的蟻群算法網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋優(yōu)化研究[J].計(jì)算機(jī)仿真，2011，28(9):151-153.

[5] 夏 娜，王長(zhǎng)生，鄭 榕，等.魚群?jiǎn)l(fā)的水下傳感器節(jié)點(diǎn)布置[J].自動(dòng)化學(xué)報(bào)，2012，38(2):295-302.

[6] 歐陽(yáng)丹彤，何金勝，白洪濤.一種約束粒子群優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].計(jì)算機(jī)科學(xué)，2011，38(7):46-50.

[7] 顧曉燕，孫力娟，郭 劍，等.一種有向傳感器網(wǎng)絡(luò)改進(jìn)粒子群覆蓋增強(qiáng)算法[J].重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2011，23(2):214-219.

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

[9] 仲元昌，趙貞貞，王 恒，等.無(wú)線傳感器網(wǎng)絡(luò)中的覆蓋優(yōu)化算法[J].計(jì)算機(jī)工程， 2012，38(8):57-60.

孫 茜，通訊作者，E—mail:sunqian0403@hotmail.com。

Research on optimization deployment of water quality sensor based on particle swarm optimization algorithm*

YU Xing-yun, SUN Qian, WANG Xiao-yi, XU Ji-ping, WANG Li, ZHANG Hui-yan

(School of Computer and Information Engineering,Beijing Technology and Business University,Beijing 100048,China)

It is desirable to propose a centralized coverage method when monitoring key areas under different pollution levels.Particle swarm optimization(PSO)algorithm based on weighted factors adjustment is used,and compare effect of particle numbers on network coverage ability.According to the simulation results,the sensor nodes can achieve fast-adaptive and well-distributed deployment,as well as avoiding local optimal.With the increase of swarm size,coverage ability of the sensor network is becoming larger,however decreasing after 20.It is of high importance that key water area is covered by sensor nodes after uniformly deployment,hence ensuring the reliability of the water quality data.

sensor network; covering deployment; water environment monitoring; particle swarm optimization(PSO)

10.13873/J.1000—9787(2016)12—0030—03

2016—10—19

北京市市屬高校創(chuàng)新能力提升計(jì)劃資助項(xiàng)目(PXM2014—014213—000033)；2014年度北京市市屬高校青年拔尖人才培育計(jì)劃資助項(xiàng)目(CIT&TCD201404031)；北京工商大學(xué)青年教師科研啟動(dòng)基金資助項(xiàng)目(QNJJ2015—20)

TP 212.9

A

1000—9787(2016)12—0030—03

余幸運(yùn)(1992-)，女，重慶人，碩士研究生，研究方向?yàn)樗h(huán)境監(jiān)測(cè)技術(shù)、傳感器網(wǎng)絡(luò)技術(shù)。