基于SPSO算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋可行性分析

鄭涵文

摘要：從誕生之初，無(wú)線傳感器網(wǎng)絡(luò)（WSNs）作為一種新的測(cè)控網(wǎng)絡(luò)，在民用領(lǐng)域與軍事領(lǐng)域的應(yīng)用前景非常廣闊，這得益于它的多樣性和廣泛性。又因WSNs拓?fù)浣Y(jié)構(gòu)變化繁雜，節(jié)點(diǎn)使用周期短，又常處于比較極端惡劣的環(huán)境中運(yùn)用，所以怎樣改善網(wǎng)絡(luò)節(jié)點(diǎn)分布，提高部署效率是當(dāng)前的迫切問(wèn)題。目前，WSNs節(jié)點(diǎn)分布的方法研究還在探索的階段，所以尋找一種較為高效的優(yōu)化算法是當(dāng)前重中之重。本文首次提出基于SPSO算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋方案，探討其在WSNs領(lǐng)域的可行性。

關(guān)鍵詞：SPSO算法；無(wú)線傳感網(wǎng)絡(luò)；覆蓋優(yōu)化

一.研究意義

在關(guān)于WSNs的各項(xiàng)應(yīng)用與研究里，傳感器節(jié)點(diǎn)的部署問(wèn)題一直困擾著研究人員。其原因是WSNs通常有拓?fù)浣Y(jié)構(gòu)的復(fù)雜變化，節(jié)點(diǎn)生命周期短，數(shù)量大，同時(shí)進(jìn)行工作的環(huán)境又往往極端惡劣等特點(diǎn)。因而，常用的算法與協(xié)議、傳統(tǒng)的網(wǎng)絡(luò)技術(shù)都可能因WSNs的這些現(xiàn)實(shí)情況，而較難用于WSNs上。這就有了一個(gè)亟待解決的問(wèn)題：怎樣在WSNs布局中，找到減少傳感器節(jié)點(diǎn)的能源損耗，并且能夠平衡以延長(zhǎng)網(wǎng)絡(luò)壽命為目的的能量損耗優(yōu)化方案，同時(shí)提高傳感器節(jié)點(diǎn)的群體智能的協(xié)作能力與認(rèn)知能力。

為了有效降低網(wǎng)絡(luò)的構(gòu)建周期，讓監(jiān)測(cè)區(qū)域滿足迅速覆蓋，且讓W(xué)SNs的拓?fù)浣Y(jié)構(gòu)能擁有高的適應(yīng)性，同時(shí)使網(wǎng)絡(luò)通過(guò)協(xié)調(diào)控制能夠有效地增長(zhǎng)使用時(shí)長(zhǎng)，一個(gè)合適、可行的WSNs節(jié)點(diǎn)部署方案非常重要。所以為了讓節(jié)點(diǎn)覆蓋達(dá)到最優(yōu)化效果，必須提出一種高效的控制算法對(duì)WSNs節(jié)點(diǎn)進(jìn)行部署。

二.仿真模型

傳感器節(jié)點(diǎn)感知模型及每個(gè)節(jié)點(diǎn)的位置分布與WSNs的覆蓋問(wèn)題往往聯(lián)系緊密。換句話說(shuō)，傳感器節(jié)點(diǎn)感知模型確定的空間位置和節(jié)點(diǎn)的物理位置關(guān)系被視作度量感知函數(shù)的服務(wù)好壞的標(biāo)準(zhǔn)。由于感知模型的種類繁多，所以模型的改變是依照具體的應(yīng)用環(huán)境而進(jìn)行多種變化的。

1.二元感知模型

將監(jiān)測(cè)區(qū)域平面化，節(jié)點(diǎn)的覆蓋范圍指的是以傳感節(jié)點(diǎn)位置為中心，RS為半徑的圓形面積。該圓形區(qū)域叫做傳感器節(jié)點(diǎn)的“感知圓盤”，RS表示傳感器節(jié)點(diǎn)的感知半徑，其值由節(jié)點(diǎn)感知設(shè)備的物理性質(zhì)確定。假定傳感節(jié)點(diǎn)S的位置坐標(biāo)是（XS，YS），存在平面上一點(diǎn)坐標(biāo)為P（XP，YP），則在二元感知模型中，節(jié)點(diǎn)S成功檢測(cè)到位置P的概率Pr：為Pr（s，p）當(dāng)d（s，p） ≤Rs時(shí)，反之則為0。

在概率公式中， 為節(jié)點(diǎn)S和P之間的歐氏距離。同樣的，節(jié)點(diǎn)在三維世界里的感知范圍與二元感知模型內(nèi)類似，都是以一個(gè)節(jié)點(diǎn)位置為圓心，RS是半徑的球形區(qū)域。

2.傳感網(wǎng)絡(luò)問(wèn)題模型

假設(shè)監(jiān)測(cè)范圍D是m×n的矩形區(qū)域，在該區(qū)域中隨機(jī)播撒參數(shù)相同的固定傳感節(jié)點(diǎn)和移動(dòng)傳感節(jié)點(diǎn)，兩種傳感節(jié)點(diǎn)數(shù)量都為N。每個(gè)節(jié)點(diǎn)的監(jiān)測(cè)區(qū)域都是以節(jié)點(diǎn)位置為中心、r是半徑的圓形范圍。在問(wèn)題模型中，采用的是節(jié)點(diǎn)的二元感知模型。通信范圍的半徑為R。為了保障無(wú)線網(wǎng)絡(luò)的連通性，往往將節(jié)點(diǎn)通信半徑設(shè)置感知半徑的兩倍以上，即R≥2r。

將監(jiān)測(cè)范圍D分割成個(gè)像素點(diǎn)，每個(gè)真實(shí)的地理位置都用像素點(diǎn)表示，像素點(diǎn)p的坐標(biāo)為（X，Y），用表示Di傳感器節(jié)點(diǎn)i（xi，yi）覆蓋像素點(diǎn)p發(fā)生的事件，Pr（Di）表示該事件發(fā)生的概率，值取1或者0。當(dāng)像素點(diǎn)位于節(jié)點(diǎn)的感知范圍內(nèi)，則Pr（Di）取1，否則取0。

三.算法原理

1.PSO算法

基本PSO算法的原理是通過(guò)模仿對(duì)大自然中魚群捕食與鳥群捕食的過(guò)程，隨機(jī)產(chǎn)生鳥群在一定空間內(nèi)，而群體通過(guò)獨(dú)立個(gè)體間的探索與協(xié)作最后成功獲得食物所在的區(qū)域?？梢詷?gòu)造這樣的一個(gè)場(chǎng)景圖，一群獨(dú)立的鳥在自行不干涉的進(jìn)行尋找食物，它們無(wú)法確定食物所處的精確區(qū)域，但有一個(gè)潛在的規(guī)則使得獨(dú)立的鳥知曉其相距食物的路徑長(zhǎng)度（比如：食物氣味的大小，食物發(fā)出聲響音量等等）。在這種情況下，每個(gè)獨(dú)立的小鳥會(huì)在搜尋的期間內(nèi)不斷地刷新與存檔其曾經(jīng)過(guò)距離食物最近的方位，同時(shí)還間斷地跟著鳥群中全體個(gè)體所存在過(guò)的最近方位進(jìn)行刷新。所以，鳥群通過(guò)參考本身的歷史最優(yōu)位置與種群的歷史最優(yōu)位置不停地刷新其所在方位與前進(jìn)的速度，最后讓群體匯聚在食物的位置。PSO算法的進(jìn)化方程為：

2.SPSO算法

SPSO算法繼承了基本PSO算法的優(yōu)點(diǎn)，而對(duì)其容易陷入局部收斂的問(wèn)題，SPSO算法對(duì)算法過(guò)程進(jìn)行了改進(jìn)。首先去掉粒子中飛行速度記憶力以增加算法局部收斂能力，然后通過(guò)在搜索空間中隨機(jī)產(chǎn)生停止粒子來(lái)退出局部收斂，同時(shí)可以擁有較高的收斂速度。當(dāng)慣性系數(shù)w=0時(shí)，粒子的探索速度只由粒子的實(shí)時(shí)位置、歷史最好位置與粒子群的目前最好位置來(lái)決定，探索速度不存在記憶性。所以，當(dāng)粒子在種群最好位置上的會(huì)立刻不再探索，同時(shí)別的粒子會(huì)想著與的加權(quán)中心而趨近。換句話說(shuō)，群體將緊縮至目前的，類似一個(gè)局部算法；若是，則讓粒子能夠具有擴(kuò)展搜索空間的勢(shì)頭，也就是有能力滿足全局搜索。同時(shí)w越大意味著全局搜索能力就越強(qiáng)。

四.可行性分析

基本PSO算法是通過(guò)隨機(jī)產(chǎn)生粒子群進(jìn)行迭代，尋找最優(yōu)解。而WSNs網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋初始化正符合隨機(jī)性這一特點(diǎn)，所以使得兩者可以有效的結(jié)合起來(lái)。雖然和PSO算法相比，SPSO算法取消了慣性系數(shù)，使得粒子本身沒有速度記憶性，以致降低了全局搜索能力。然而這也讓種群在進(jìn)化時(shí)，每一代都能夠滿足有一個(gè)粒子由于處于粒子群的歷史最優(yōu)位置而不再進(jìn)化，通過(guò)停止進(jìn)化的粒子改進(jìn)全局搜索能力是SPSO算法的中心思路。因此SPSO算法可以有效保障全局收斂性，

本文構(gòu)建了監(jiān)測(cè)范圍為D的傳感網(wǎng)絡(luò)仿真模型，采用了二元感知模型，將粒子維度控制在二維上，設(shè)定節(jié)點(diǎn)數(shù)目，將覆蓋率作為優(yōu)化的適應(yīng)度函數(shù)。使得現(xiàn)實(shí)中的WSNs網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋問(wèn)題可以轉(zhuǎn)換為一個(gè)尋優(yōu)問(wèn)題。通過(guò)對(duì)比SPSO算法和PSO算法的全局收斂性，可以推測(cè)出SPSO算法在WSNs網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋問(wèn)題具有更強(qiáng)的收斂性。

同時(shí)SPSO算法帶有一定的隨機(jī)性，特別是對(duì)粒子長(zhǎng)度較長(zhǎng)，維度較低的尋優(yōu)問(wèn)題，隨機(jī)性更容易跳出PSO算法所產(chǎn)生的局部收斂。因此在適用性上，SPSO算法比PSO算法更適合WSNs網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋問(wèn)題。

五.總結(jié)語(yǔ)

本文在研究了無(wú)線傳感器網(wǎng)絡(luò)的結(jié)構(gòu)和特征以及傳感節(jié)點(diǎn)部署的工作原理后，分析SPSO算法作為傳感節(jié)點(diǎn)部署問(wèn)題控制算法的適應(yīng)性，并且提出了采用SPSO算法解決節(jié)點(diǎn)覆蓋最大化問(wèn)題的設(shè)想，還分析其優(yōu)于PSO算法的可行性。在以后的深入研究中，將通過(guò)仿真實(shí)驗(yàn)對(duì)該方案進(jìn)行驗(yàn)證。