基于粒子群算法的wsn覆蓋優(yōu)化研究

基于粒子群算法的wsn覆蓋優(yōu)化研究

0wsn覆蓋優(yōu)化方法無線傳感器網(wǎng)絡(luò)（wsd）由大量廉價微型傳感器節(jié)點組成，通過無線通信完成目標監(jiān)控和信息采集任務(wù)。對網(wǎng)絡(luò)覆蓋的測量能夠使人們了解監(jiān)測區(qū)域的網(wǎng)絡(luò)覆蓋狀況,重新調(diào)整傳感器節(jié)點分布或者指導(dǎo)在將來添加傳感器節(jié)點時可采取的改進措施,保證測量數(shù)據(jù)的可靠性,減少資源浪費,延長網(wǎng)絡(luò)壽命。近年來,國內(nèi)外學(xué)者在WSN覆蓋控制方面進行了大量研究,取得了一定進展。暴露穿越覆蓋控制算法采用分布式執(zhí)行方式,從而得到精度不同的暴露路徑。最壞與最佳情況覆蓋算法,在最佳與最差兩種度量條件下分別得到了臨界的網(wǎng)絡(luò)路徑規(guī)劃結(jié)果,指導(dǎo)網(wǎng)絡(luò)節(jié)點的配置。在國內(nèi),劉永生等人用隨機調(diào)度子集劃分最優(yōu)解的方法優(yōu)化覆蓋率;Wang等人提出了兩種移動節(jié)點的部署方法;周彤等人提出了基于虛擬力的混合感知網(wǎng)絡(luò)節(jié)點部署方法。標準粒子群算法在空間搜索時,粒子向自身歷史最佳位置或群體歷史最佳位置聚集,限制了粒子的搜索范圍。為了避免陷入早熟,就要增加種群的粒子數(shù)或者減弱粒子對當(dāng)前種群搜索到的全局最優(yōu)位置的追逐,而增加粒子數(shù)將導(dǎo)致算法復(fù)雜度加大,減弱粒子對全局最優(yōu)點的追逐使得算法不易收斂。本文所提出的基于碰撞理論的分簇粒子群覆蓋優(yōu)化策略(CCPSO)是在標準粒子群算法的基礎(chǔ)上,采用分簇思想和碰撞策略調(diào)整傳感器節(jié)點,使整個網(wǎng)絡(luò)覆蓋性能得到優(yōu)化。1無線傳感器網(wǎng)絡(luò)系統(tǒng)的模型和問題描述1.1基于多個傳感器節(jié)點同時測量目標的方法假設(shè)二維平面監(jiān)測區(qū)域P被數(shù)字離散化為m×n個像素,該目標在該區(qū)域上參數(shù)相同的傳感器節(jié)點數(shù)目為N,每個節(jié)點的坐標均已知,感知半徑均為r。傳感器節(jié)點集表示C={c1,c2,c3,…,cN},點A被ci所覆蓋的事件發(fā)生的概率ρcov(x,y,ci)表示為其中:ci=(xi,yi,r)表示以節(jié)點坐標(xi,yi)為圓心,感知半徑為r的圓;為像素點A(x,y)與ci之間的距離。基于二元感知模型,文獻提出了一種采用多個傳感器節(jié)點同時測量監(jiān)測目標的方法來提高監(jiān)測目標的測量概率。其中ρcov(C)為節(jié)點集聯(lián)合測量概率。1.2基于區(qū)域覆蓋率對于區(qū)域覆蓋率的研究,文獻提到將目標區(qū)域離散為許多格點,用所有格點被傳感器節(jié)點覆蓋的覆蓋率來代表目標區(qū)域的區(qū)域覆蓋率,從而將區(qū)域覆蓋率的問題轉(zhuǎn)換為點覆蓋的問題。由于節(jié)點集C的區(qū)域覆蓋率R(C)為節(jié)點集C的覆蓋面積與監(jiān)測區(qū)域P的總面積之比,監(jiān)測區(qū)域P被數(shù)字離散化為m×n個像素。用節(jié)點集聯(lián)合測量概率衡量每個像素點是否被傳感器節(jié)點集所覆蓋,得到節(jié)點集C的區(qū)域覆蓋率:基于以上理論,得出區(qū)域覆蓋率的計算步驟如下:a)根據(jù)式(1)計算一個像素點對每個傳感器節(jié)點的覆蓋率。b)根據(jù)式(2)計算一個像素點對傳感器節(jié)點集合的聯(lián)合覆蓋率。c)重復(fù)步驟a)和b)計算監(jiān)測區(qū)域每一個像素點對傳感器節(jié)點集C的聯(lián)合覆蓋率。d)根據(jù)式(3)計算傳感器節(jié)點集C的區(qū)域覆蓋率R(C),并將R(C)作為以后覆蓋優(yōu)化算法的優(yōu)化目標函數(shù)。2基于沖突理論的集群顆粒群算法2.1u3000無線傳感器網(wǎng)絡(luò)的局部尋優(yōu)算法粒子群算法(PSO)是目前普遍應(yīng)用的用于解決多目標優(yōu)化問題的經(jīng)典算法之一。其基本思想是隨機初始化一群沒有體積、沒有質(zhì)量的粒子,將每個粒子視為優(yōu)化問題的一個可行解,粒子的好壞由一個事先設(shè)定的適應(yīng)度函數(shù)來確定。每個粒子在搜索空間中以一定的速度飛行,并根據(jù)對個體和群體的飛行經(jīng)驗綜合分析來動態(tài)調(diào)整速度。每一代中,粒子將跟蹤兩個極值,一個是粒子本身迄今為止找到的最優(yōu)解,另一個是整個群體迄今為止找到的最優(yōu)解。假設(shè)一個由m個粒子組成的群體在n維搜索空間以一定的速度飛行,粒子i在t時刻的狀態(tài)屬性設(shè)置如下:第i個粒子在n維空間的當(dāng)前位置為Xi=(Xi1,Xi2,Xi3,…,Xin),第i個粒子在n維空間的當(dāng)前飛行速度為Vi=(Vi1,Vi2,Vi3,…,Vin),第i個粒子經(jīng)歷的最好位置為Pi=(Pi1,Pi2,Pi3,…,Pin),也是微粒i所經(jīng)歷的具有最好適應(yīng)值的位置,稱為個體最好位置pbest。設(shè)f(x)為最大化的目標函數(shù),根據(jù)優(yōu)化目標不同f(x)也有不同定義。在無線傳感器網(wǎng)絡(luò)中,f(x)通常是指傳感器節(jié)點的覆蓋率,則微粒i的當(dāng)前最好位置由下式確定:該群體所有m個粒子中經(jīng)歷過的最好位置為Pg(t),即全局最好位置gbest,滿足粒子在t+1時刻的位置更新通過下式獲得:其中:i表示第i個粒子,j表示粒子所搜索空間的維數(shù);t表示迭代次數(shù);c1是粒子自身加速度權(quán)重系數(shù),c2是全局加速度權(quán)重系數(shù),通常取c1=c2=2;r1、r2為均勻分布在(0,1)區(qū)間的隨機數(shù);w為慣性權(quán)重系數(shù),計算公式為其中:t為當(dāng)前迭代次數(shù),tmax為算法的總迭代次數(shù)。Shi指出較大的權(quán)重有利于展開全局尋優(yōu),較小的權(quán)重有利于局部尋優(yōu)。式(8)使粒子群算法在初期有良好的全局搜索性能,后期具有良好的局部搜索性能。2.2基于約束彈離的分簇粒子群算法為了克服粒子群早熟現(xiàn)象,避免算法過度復(fù)雜化,本文將搜索空間劃分為多個簇,并根據(jù)粒子的位置判定其屬于哪個簇。每次對粒子位置和速度進行更新的時候,用簇中心來代替簇內(nèi)粒子的全局最佳位置。算法對各簇中的粒子群進行獨立優(yōu)化,使其在追逐個體最佳位置的同時向簇中心靠攏;同時為了避免簇內(nèi)粒子覆蓋重疊,設(shè)計了碰撞彈離策略。粒子a、b的距離可以由歐式距離公式算出:其中:Δr為本文設(shè)定的閾值,Xa、Xb、Va、Vb分別為a、b的位置和速度。當(dāng)d(Xa,Xb)<Δr時,就判定這兩個粒子即將碰撞,采用彈離策略將其彈開。彈離距離大小為該方向上速度乘以一個隨機因子:其中:k=1,2,…,n;rand為0~1的隨機數(shù)。彈開后的粒子a、b的位置更新為粒子與邊界的碰撞原理與此類似,如果粒子下一次更新的位置超過了目標區(qū)域,就判斷粒子與邊界發(fā)生了碰撞。按照反向彈離策略,也朝原運動方向反向彈離一段距離,粒子c與邊界發(fā)生了碰撞,位置更新為其中:Δd(Xck)=Vck×rand,k=1,2,…,n。基于碰撞理論的分簇粒子群算法進行覆蓋優(yōu)化的基本過程如下:a)在目標區(qū)域初始化m個傳感器節(jié)點,隨機產(chǎn)生每個傳感器節(jié)點的位置和速度,并且將目標區(qū)域劃分成若干個簇。b)通過粒子坐標判斷其屬于哪個簇。c)對每個簇中的各個粒子,按式(6)~(8)更新速度和位置。d)對各個粒子,判斷其位置是否越界,如果該粒子位置Xi離開了目標區(qū)域,則粒子位置不更新并且按照式(11)反向彈離一段距離。e)對m個傳感器節(jié)點分別計算兩兩節(jié)點間的距離,判斷是否發(fā)生碰撞,如果滿足碰撞條件,按照式(9)(10)更新其位置。f)根據(jù)優(yōu)化目標函數(shù)計算每個傳感器節(jié)點的覆蓋率。g)根據(jù)優(yōu)化目標函數(shù)計算該傳感器節(jié)點集的區(qū)域覆蓋率。h)更新后的傳感器節(jié)點集的區(qū)域覆蓋率與節(jié)點集最好位置矩陣pbest的區(qū)域覆蓋率相比較,如果較好,則重新設(shè)置pbest。i)如果達到停止條件(預(yù)設(shè)最大迭代次數(shù))停止運算,返回結(jié)果;否則返回步驟b)繼續(xù)運行。3根據(jù)沖突理論，集群顆粒聯(lián)合算法的覆蓋優(yōu)化實驗3.1仿真結(jié)果分析為了考察分簇數(shù)對無線傳感器網(wǎng)絡(luò)覆蓋性能的影響,對改進的粒子群覆蓋算法進行仿真。仿真環(huán)境為MATLAB7,參數(shù)設(shè)置為:邊長100m的正方形測量區(qū)域中布置30個無線傳感節(jié)點,傳感節(jié)點感知半徑r=13m,,碰撞閾值為7m,最大迭代次數(shù)為300。粒子群分簇數(shù)分別為1、4、9、16。圖1~8及表1顯示了不同分簇數(shù)時的仿真結(jié)果。以上仿真結(jié)果顯示,當(dāng)分簇數(shù)為1時,雖然碰撞理論在一定程度上避免了群體粒子對全局最優(yōu)位置的追逐,從圖1看,粒子覆蓋的重疊性依然較高,覆蓋率僅有90%;分簇數(shù)為4后,將目標區(qū)域內(nèi)粒子網(wǎng)格化,每個網(wǎng)格獨立優(yōu)化,減弱了整個目標區(qū)域內(nèi)所有粒子的快速趨同,圖3中無線傳感器網(wǎng)絡(luò)節(jié)點分布更加均勻,圖4覆蓋率曲線比圖2提高了4%;繼續(xù)增加簇數(shù)到9簇,圖6顯示覆蓋率沒有明顯提高,這是因為簇數(shù)變大一方面提高了算法的復(fù)雜度,增加了迭代次數(shù),另一方面,粒子碰撞的空間減小,碰撞性能發(fā)揮不佳;簇數(shù)為16時,圖7顯示重疊度增加,圖8顯示覆蓋率只有89.5%,這是因為粒子活動范圍更促狹,粒子向簇內(nèi)的全局最優(yōu)位置靠攏。基于以上仿真條件和結(jié)果,選定分簇數(shù)為4時最優(yōu)。3.2仿真結(jié)果分析通過改變不同的閾值對傳感器節(jié)點的布局以及覆蓋率進行研究,分析碰撞閾值Δr對傳感器節(jié)點覆蓋率的影響。在邊長100m的正方形測量區(qū)域中隨機布置30個無線傳感節(jié)點,傳感節(jié)點感知半徑為r=13m,c1=c2=2,最大迭代次數(shù)為300,分簇數(shù)為4。圖9~22及表2顯示不同Δr值的仿真結(jié)果。由表2看出,當(dāng)碰撞閾值Δr從4m變化到7m時,傳感器覆蓋圓分布均勻,覆蓋率從82.5%增大到94%,迭代次數(shù)減少了20次。碰撞閾值Δr從7m變化到10m時,傳感器覆蓋范圍變化不明顯,而迭代次數(shù)增加了85次,影響了算法的執(zhí)行效率。由于傳感器網(wǎng)絡(luò)節(jié)點壽命有限,從優(yōu)化覆蓋和節(jié)約系統(tǒng)資源兩方面綜合考慮,選取Δr=7m比較合適。3.3節(jié)點重疊區(qū)的表征基于碰撞理論的分簇粒子群算法覆蓋與標準粒子群算法覆蓋性能比較如圖23、24所示。圖23中,傳感器節(jié)點分布不是十分均勻,節(jié)點重復(fù)嚴重,目標區(qū)域邊界吸附著很多節(jié)點,較多的區(qū)域沒有被覆蓋。這是由于標準粒子群算法沒有限制粒子之間的距離和粒子與邊界的距離,標準粒子群算法對全局最優(yōu)位置的追逐容易導(dǎo)致早熟,形成多節(jié)點重疊區(qū)。圖24中,傳感器節(jié)點分布均勻,靠近邊界的的節(jié)點較少,粒子重復(fù)覆蓋部分較少。這是由于基于碰撞理論的分簇粒子群覆蓋算法采用了分簇的思想,獨立優(yōu)化每個網(wǎng)格內(nèi)的粒子群,減弱了早熟的趨勢。碰撞策略的引入限制了粒子的過度重疊及靠近邊界。本文提出的基于碰撞理論的分簇PSO算法(CCPSO)與標準粒子群算法(SPSO)、文獻中的粒子進化的多粒子群算法(MPSO)、擬物力導(dǎo)向的粒子群算法(VMFPSO),以及文獻中的傳統(tǒng)遺傳算法(CGA)、新量子遺傳算法(VMFPSO)在相同條件下覆蓋性能比較如表3所示。從表3的比較可以得出,本文所提出的CCPSO算法在覆蓋性能方面比基本粒子群算法提高了30%,比粒子進化的多粒子群算法提高了4.5%,比擬物力導(dǎo)向的的粒子群算法提高了3%、比傳統(tǒng)遺傳算法提高了6%,比新量子遺傳算