微粒群導(dǎo)向虛擬力算法在優(yōu)化垃圾處理站點(diǎn)的應(yīng)用

范漪萍

摘 要 北京市是我國的首都和人口聚集地，巨大的城市規(guī)模和人口規(guī)模給北京市帶來大量的生產(chǎn)生活垃圾，在現(xiàn)有的垃圾站點(diǎn)部署形勢下，由于站點(diǎn)分布密度的不合理造成了區(qū)域垃圾處理能力冗余或匱乏的情況。本文針對此問題，結(jié)合微粒群算法提出了一種基于微粒群導(dǎo)向虛擬力的站點(diǎn)部署策略，通過算法仿真分析可以看出該算法優(yōu)化了站點(diǎn)的部署，提高了站點(diǎn)的覆蓋率。

關(guān)鍵詞 微粒群；虛擬力；垃圾站點(diǎn)

中圖分類號：TP2 文獻(xiàn)標(biāo)識碼：A 文章編號：1671-7597（2014）16-0071-01

近些年來，隨著城市規(guī)模和人口規(guī)模的不斷擴(kuò)大，給城市環(huán)衛(wèi)工作帶來了巨大的壓力和挑戰(zhàn)，特別是對于垃圾站點(diǎn)的處理能力。據(jù)了解，北京市現(xiàn)有的垃圾站點(diǎn)在實(shí)際應(yīng)用中存在諸多問題，其中最主要的問題就是在規(guī)劃建設(shè)時(shí)，站點(diǎn)部署不合理，有的地方站點(diǎn)過多，部署密度過大，造成垃圾處理能力冗余，而有的地方垃圾站點(diǎn)較少，根本不能滿足片區(qū)的垃圾處理需求。針對以上問題，本文提出了一種基于算法控制的站點(diǎn)部署方案。

1 部署策略

垃圾站點(diǎn)在實(shí)際部署時(shí)經(jīng)常出現(xiàn)覆蓋盲點(diǎn)或是站點(diǎn)分布不均勻?qū)е碌恼军c(diǎn)資源浪費(fèi)和局部過于飽和等問題。因此為了解決以上問題，本文提出了基于虛擬力導(dǎo)向微粒群的站點(diǎn)部署

算法。

虛擬力算法：虛擬力算法的算法思想首先是基于粒子抽象的，在城市垃圾站點(diǎn)部署中，虛擬力算法則是將垃圾站部署網(wǎng)絡(luò)中的單位站點(diǎn)抽象成粒子，站點(diǎn)的部署區(qū)域抽象成復(fù)雜的勢力場，粒子會在此勢力場中根據(jù)場力作用，達(dá)到一個勢力場平衡的位置，在垃圾站部署網(wǎng)絡(luò)中，站點(diǎn)所受的虛擬力是整個勢力場的矢量值，單位站點(diǎn)在矢量勢力的作用下到達(dá)區(qū)域的某一位置，使得站點(diǎn)能夠均勻分布。

假設(shè)垃圾站站點(diǎn)所受到的虛擬力為，和分別指站點(diǎn)對的作用力和障礙物對站點(diǎn)的作用力，在本文的仿真研究中，忽略障礙物對站點(diǎn)部署的影響。在虛擬力的作用下，站點(diǎn)由原位置到達(dá)新的位置。設(shè)定是垃圾站站點(diǎn)的最大移動距離（垃圾站站點(diǎn)的能量有限），是作用于站點(diǎn)的虛擬力，和分別是虛擬力作用于兩條軸上的分量，是虛擬力閥值，當(dāng)垃圾站站點(diǎn)所受到的虛擬力小于該值時(shí)，則不移動。

從上述過程中可以看出，虛擬力算法雖然能夠?qū)崿F(xiàn)站點(diǎn)的均勻分布，但是其缺陷在于它不能夠?qū)崿F(xiàn)站點(diǎn)的全局優(yōu)化，即在指定區(qū)域內(nèi)，虛擬力算法不能夠掌握站點(diǎn)的分布數(shù)量，同時(shí)，虛擬力算法中，視所有站點(diǎn)均為可移動的站點(diǎn)，這在實(shí)際應(yīng)用中是不現(xiàn)實(shí)的。

微粒群算法是一種以實(shí)現(xiàn)全局優(yōu)化的覆蓋算法，微粒群算法的思想是假設(shè)n維搜索空間中存在數(shù)量為m的微粒群，微粒i的位置為Xi，粒子運(yùn)動速度為Vi，Pi為微粒所經(jīng)過的最佳位置，c1，c2為加速因子，分別用于調(diào)節(jié)微粒向局部最優(yōu)和全局最優(yōu)的進(jìn)化步長，r1j，r2j為獨(dú)立隨機(jī)數(shù)，其閾值范圍為

[0，1]，為慣性因子，隨著迭代次數(shù)的增大而減小。

從上述過程可知，微粒群算法原則是實(shí)現(xiàn)覆蓋率的最大化，同時(shí)，微粒群算法其算法思想中，可以接受固定粒子的存在，因此就消除了固定粒子對算法的影響。但另一方面，微粒群算法的計(jì)算復(fù)雜度較高，算法計(jì)算耗時(shí)較大。

因此，本文結(jié)合虛擬力算法和微粒群算法，提出了一種基于虛擬力導(dǎo)向微粒群的站點(diǎn)部署優(yōu)化策略，在此算法中，虛擬力算法能夠高效地完成區(qū)域站點(diǎn)的散布過程，微粒群算法對全局進(jìn)行優(yōu)化并消除固定站點(diǎn)對于站點(diǎn)部署的限制，同時(shí)為加快微粒群算法收斂速度，指導(dǎo)微粒向全局最優(yōu)進(jìn)化，虛擬力導(dǎo)向微粒群優(yōu)化策略在各粒子的速度進(jìn)化中加入虛擬力的影響，是用于調(diào)節(jié)虛擬力影響的加速因子，是與和相互獨(dú)立的隨機(jī)數(shù)，其中，各元素的上角標(biāo)表示粒子序號和元素序號，下角標(biāo)則對應(yīng)虛擬力在相應(yīng)坐標(biāo)軸的分量。

2 算法仿真

2.1 算法原則

1）由于站點(diǎn)部署不受障礙物影響，因此假設(shè)障礙物不啟用，在算法編寫中障礙物設(shè)置為0；2）部署區(qū)域的形狀和面積，考慮到北京市主要監(jiān)控區(qū)域的地理規(guī)則呈現(xiàn)為正方形，由于考慮到算法仿真的可執(zhí)行性，將部署區(qū)域設(shè)置為1000單位的正方形；3）垃圾站站點(diǎn)的覆蓋能力，規(guī)定單站點(diǎn)覆蓋半徑為60；4）固定站點(diǎn)設(shè)置，虛擬力導(dǎo)向微粒群算法中需要設(shè)置固定站點(diǎn)用以判斷站點(diǎn)間的距離與閥值關(guān)系，固定站點(diǎn)控制參數(shù)為0，可移動站點(diǎn)控制參數(shù)為1。

2.2 算法仿真

1）對正方形區(qū)域內(nèi)的固定站點(diǎn)網(wǎng)絡(luò)布局進(jìn)行初始化；2）對區(qū)域內(nèi)所有站點(diǎn)進(jìn)行布局初始化；3）調(diào)用虛擬力導(dǎo)向微粒群函數(shù)進(jìn)行站點(diǎn)移動，站點(diǎn)控制參數(shù)為0則不參與移動，并以此迭代；4）當(dāng)站點(diǎn)控制參數(shù)均為0時(shí)停止迭代；5）計(jì)算覆蓋率并繪制收斂曲線。

3 仿真分析

從第二和第三圖可以看出，經(jīng)過虛擬力導(dǎo)向微粒群算法優(yōu)化后的網(wǎng)絡(luò)布局在區(qū)域內(nèi)的分布更為合理，經(jīng)過多次迭代后站點(diǎn)部署覆蓋率達(dá)到了95%，因此可以看出此算法對于站點(diǎn)的部署優(yōu)化效果是十分明顯的。

3 結(jié)束語

通過仿真分析可以發(fā)現(xiàn)，本文提出的微粒群導(dǎo)向虛擬力算法對北京市站點(diǎn)部署的優(yōu)化效果是非常明顯的，但是在實(shí)際部署過程中，考慮到地理位置和區(qū)域環(huán)境的影響，算法的實(shí)施性不一定能達(dá)到最優(yōu)，在后續(xù)的工作中，本文的研究方向?qū)⒕唧w結(jié)合北京市的具體情況，研究在本文算法的指導(dǎo)下，實(shí)際環(huán)境中的站點(diǎn)部署方案。

參考文獻(xiàn)

[1]王雪，王晟，馬俊杰.無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)位置并行微粒群優(yōu)化策略[J].計(jì)算機(jī)學(xué)報(bào)，2007（4）

[2]Qu Yu-Gui，Zhai Yu-Jia，Lin Zhi-Ting et al. A novel sensordeployment model in wireless sensor network. Journal of Bei-jing University of Posts and Telecommunications，2004，27（6）：1-5（in Chinese）.

[3]黃劉生，汪煬.無線傳感網(wǎng)絡(luò)定位技術(shù)[J].中國科學(xué)技術(shù)大學(xué)，2007（4）.

[4]陳維克，李文鋒，首晰，袁兵.基于Rssl的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法[J].武漢理工大學(xué)學(xué)報(bào)，2006，30（2）.endprint