甘娜

摘要：針對(duì)無(wú)線傳感器網(wǎng)絡(luò)覆蓋的問(wèn)題，提出一種求解無(wú)線傳感器網(wǎng)絡(luò)覆蓋問(wèn)題的粒子群智能優(yōu)化算法。該算法在粒子群算法的基礎(chǔ)上，對(duì)PSO算法適應(yīng)度函數(shù)加入選擇算子的關(guān)聯(lián)。通過(guò)無(wú)線傳感器網(wǎng)絡(luò)覆蓋的仿真，實(shí)驗(yàn)結(jié)果表明，該優(yōu)化算法既克服了PSO算法陷入局部最優(yōu)的不足，又提升了收斂精度。在提高傳感器節(jié)點(diǎn)覆蓋率、網(wǎng)絡(luò)負(fù)載均衡等方面有較好的效果。

關(guān)鍵詞：無(wú)線傳感器;網(wǎng)絡(luò)覆蓋;覆蓋度;PSO算法

中圖分類號(hào)：TP393? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）21-0028-02

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

無(wú)線傳感器網(wǎng)絡(luò)覆蓋是根據(jù)被監(jiān)測(cè)目標(biāo)或區(qū)域的分布情況，無(wú)線傳感器節(jié)點(diǎn)間相互通信，采集和處理覆蓋區(qū)域中監(jiān)測(cè)對(duì)象的信息，并發(fā)送給監(jiān)測(cè)者[1]。網(wǎng)絡(luò)覆蓋優(yōu)化目標(biāo)是要保證目標(biāo)區(qū)域盡可能被網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)覆蓋[2]。

粒子群算法（PSO）在求解無(wú)線傳感器網(wǎng)絡(luò)覆蓋問(wèn)題中很難得到最優(yōu)值，針對(duì)以上問(wèn)題，本文在PSO算法的基礎(chǔ)上，適應(yīng)度函數(shù)中加入選擇算子的關(guān)聯(lián)，提出粒子群智能優(yōu)化算法，求解無(wú)線傳感器網(wǎng)絡(luò)覆蓋問(wèn)題中傳感器節(jié)點(diǎn)覆蓋度、負(fù)載均衡等性能指標(biāo)。仿真結(jié)果表明，該算法克服了PSO算法收斂精度較低、陷入局部極值的不足，證明了粒子群智能優(yōu)化算法解決無(wú)線傳感器網(wǎng)絡(luò)覆蓋問(wèn)題的有效性。

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

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

定義一：感知模型。假設(shè)傳感器節(jié)點(diǎn)[Si0

傳感器節(jié)點(diǎn)[Si]感知范圍：

[RSi=x-xi2+y-yi2]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）

其中[RSi≤ri]。

定義二：鄰居節(jié)點(diǎn)。傳感器節(jié)點(diǎn)[Si]的通信范圍是以[rj]為通信半徑的圓。當(dāng)兩個(gè)傳感器節(jié)點(diǎn)的距離小于或等于節(jié)點(diǎn)的[rj]時(shí)，這兩個(gè)節(jié)點(diǎn)互為鄰居節(jié)點(diǎn)。

傳感器節(jié)點(diǎn)[Si]的鄰居節(jié)點(diǎn)為：

[NSi=xi-xj2+yi-yj2]? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

其中[RSi≤rj]。

定義三：覆蓋率。

網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域覆蓋率：

[Npk=1n1≤i≤n1-1≤i≤n1-xi-xj2+yi-yj2]? ? ? （3）

1.2 無(wú)線傳感器網(wǎng)絡(luò)覆蓋目標(biāo)約束函數(shù)

1.2.1 覆蓋度目標(biāo)約束函數(shù)

當(dāng)傳感器節(jié)點(diǎn)正確地覆蓋監(jiān)測(cè)區(qū)域，網(wǎng)絡(luò)才能夠順利獲取監(jiān)測(cè)的數(shù)據(jù)，完成監(jiān)測(cè)任務(wù)[3]。覆蓋率[Np]為監(jiān)測(cè)區(qū)域內(nèi)所有節(jié)點(diǎn)覆蓋的面積與監(jiān)測(cè)區(qū)域面積之比，覆蓋率優(yōu)化問(wèn)題的目標(biāo)函數(shù)的定義如下：

[Np=Npkm×n]? ? ? ? ? ? ? ? ? ? ? ? ? （4）

1.2.2網(wǎng)絡(luò)性能分析目標(biāo)約束函數(shù)

負(fù)載均衡關(guān)系到是否可以合理分配傳感器節(jié)點(diǎn)源，提升網(wǎng)絡(luò)的監(jiān)測(cè)能力和質(zhì)量[4]，提升傳感器節(jié)點(diǎn)的利用率。因此，負(fù)載均衡也是無(wú)線傳感器網(wǎng)絡(luò)覆蓋中重要的優(yōu)化目標(biāo)。優(yōu)化需求可以轉(zhuǎn)化為目標(biāo)約束函數(shù)，如下：

[factor=1-Si-averageSilastSi+averageSilast]? ? ? ? ? ? ? ? ? ? ? ? （5）

其中，[averageSilast]表示傳感器節(jié)點(diǎn)[Si]在上一次迭代中的平均執(zhí)行時(shí)間。

傳感器節(jié)點(diǎn)的負(fù)載均衡因子factor越高，則傳感器節(jié)點(diǎn)的綜合能力越強(qiáng)。

負(fù)載均衡目標(biāo)函數(shù)如下：

[load_balance=n/i=1mj=1nSim]? ? ? ? ? ? ? ? ? ? ? ? ? ?（6）

其中，[i=1nj=1mSi]表示完成任務(wù)集所需的執(zhí)行時(shí)間。由式（6）可知，[load_balance]的值越大，則傳感器節(jié)點(diǎn)利用率越高，負(fù)載越均勻。

2? 粒子群智能優(yōu)化算法

2.1標(biāo)準(zhǔn)粒子群算法

假設(shè)搜索空間為[d]維，粒子總數(shù)為[n]，粒子[i]在時(shí)刻[t（t>0）]在搜索空間中所處的位置為[Xidt]，粒子在搜索空間中運(yùn)動(dòng)速度為[Vidt]，代表飛行的方向和速度[5-6]。在搜索過(guò)程中，粒子[i]（[1≤i≤n]）按公式（7）（8）來(lái)更新其速度和位置：

[Xidt=Xidt+Vidt]? ? ? ? ? ? ? ? ? ? （8）

其中[C1]、[C2]為粒子的學(xué)習(xí)因子，表示粒子對(duì)個(gè)體經(jīng)驗(yàn)與群體經(jīng)驗(yàn)的依賴程度，[w]是慣性權(quán)重，[t]為迭代次數(shù)，[r1]、[r2]為均勻分布在區(qū)間[0，1]上的隨機(jī)數(shù)。

飛行歷史中粒子的個(gè)體最優(yōu)位置為[Pidt]，整個(gè)種群中所找到的全局最優(yōu)位置[Pgdt]為所有粒子的[Pidt]中的極值，通過(guò)公式（9）（10）更新個(gè)體最優(yōu)[Pidt]和全局最優(yōu)[Pgdt]，向最優(yōu)位置搜索移動(dòng)。

[Pgdt=argminPidtfPidt]? ? ? ? ? ? ? ? ? （10）

2.2粒子群智能優(yōu)化算法

為了克服PSO算法求解無(wú)線傳感器網(wǎng)絡(luò)覆蓋問(wèn)題，陷入局部極值及收斂精度較低等缺點(diǎn)[7-8]，本文設(shè)計(jì)了一種粒子群智能優(yōu)化算法，對(duì)PSO算法適應(yīng)度函數(shù)加入選擇算子的關(guān)聯(lián)，以提升算法的收斂精度，克服PSO算法易陷入局部最優(yōu)的不足。算法改進(jìn)和優(yōu)化主要體現(xiàn)在兩個(gè)方面：

第一，為避免過(guò)早陷入局部最優(yōu)的問(wèn)題，采用實(shí)數(shù)編碼的方式，產(chǎn)生一群更適應(yīng)問(wèn)題環(huán)境的種群;

第二，為避免收斂精度較低的問(wèn)題，對(duì)適應(yīng)度函數(shù)中引入選擇算子，選擇適應(yīng)度值較好的粒子，進(jìn)行更精細(xì)的局部搜索，獲取問(wèn)題的最優(yōu)解。

通過(guò)改進(jìn)后的公式（11）選擇適應(yīng)度值最優(yōu)的粒子：

式中[Pgdt]為下一代種群的個(gè)體，[Vgdt]是目前為止最優(yōu)個(gè)體，[Ogdt-1]是目前為止適應(yīng)值較好的個(gè)體。

3 算法流程

Step1：編碼。優(yōu)化數(shù)值，產(chǎn)生一群更適應(yīng)問(wèn)題環(huán)境的種群。

實(shí)數(shù)編碼方式如下：

[ρ=12nt=1n2tbi]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（12）

其中[ρ]為編碼實(shí)數(shù)，[n]為二進(jìn)制編碼位數(shù)，[bi]為第[i]位的二進(jìn)制值。

Step2：產(chǎn)生初始種群。設(shè)置搜索空間為[D]維，粒子的數(shù)量為[M]，設(shè)置最大迭代次數(shù)，搜索最優(yōu)解;其中第[i]個(gè)粒子位置[χ]，第[i]個(gè)粒子的飛行速度[υ]，獲取學(xué)習(xí)因子[c1]，[c2]，[c3]和慣性權(quán)重[ω];

Step3：對(duì)粒子的優(yōu)化問(wèn)題進(jìn)行求解。初始化粒子群，粒子數(shù)量變量取值范圍內(nèi)隨機(jī)初始化粒子的速度和初始位置，根據(jù)粒子速度和位置函數(shù)（7）（8）算出粒子所經(jīng)歷的最好位置;

Step4：評(píng)價(jià)粒子群中每個(gè)粒子的適應(yīng)度值，找出各個(gè)粒子的適應(yīng)度最佳值和群體適應(yīng)度最佳值。根據(jù)覆蓋率適應(yīng)度函數(shù)（11）算出粒子的適應(yīng)度最佳值，更新各個(gè)粒子的速度與位置，算出粒子各自的適應(yīng)度值;繼續(xù)下一次迭代，而適應(yīng)度值低的粒子被舍棄;

Step5：根據(jù)問(wèn)題的目標(biāo)函數(shù)更新粒子適應(yīng)度值，更新個(gè)體最優(yōu)位置和領(lǐng)域內(nèi)的最優(yōu)位置;

Step6：將種群最優(yōu)粒子組成一個(gè)群體，進(jìn)入下一次迭代，更新局部最優(yōu)解和全局最優(yōu)解;

Step7：將粒子群中最優(yōu)粒子組成一個(gè)群體，判斷是否最大迭代次數(shù)？條件為真，則輸出最優(yōu)值，算法結(jié)束。條件為假，則轉(zhuǎn)到Step 4，進(jìn)行下一次迭代。

4? 數(shù)值仿真與性能分析

本文將PSO算法與粒子群優(yōu)化算法在無(wú)線傳感器網(wǎng)絡(luò)覆蓋中的應(yīng)用進(jìn)行仿真實(shí)驗(yàn)結(jié)果對(duì)比。實(shí)驗(yàn)使用式（4）和式（6）作為算法中所需要評(píng)價(jià)的目標(biāo)函數(shù)，通過(guò)Matlab仿真平臺(tái)來(lái)模擬無(wú)線傳感器網(wǎng)絡(luò)覆蓋過(guò)程，評(píng)價(jià)傳感器節(jié)點(diǎn)覆蓋度、負(fù)載均衡程度等指標(biāo)。

本實(shí)驗(yàn)假設(shè)監(jiān)測(cè)區(qū)域[30×30m]、傳感器節(jié)點(diǎn)數(shù)目為40的情況下，進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化。粒子群優(yōu)化算法參數(shù)設(shè)置如下：設(shè)定粒子群的初始規(guī)模為250，主群最小規(guī)模限制為50，粒子維度5，學(xué)習(xí)因子0.5～2.5，慣性權(quán)重0.4～1.0，最大迭代次數(shù)200。

無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方案中，在不同傳感器節(jié)點(diǎn)數(shù)目的情況下，從圖1可以看出，在傳感器節(jié)點(diǎn)覆蓋度方面，粒子群智能算法優(yōu)于PSO算法。

從圖2可以分析出，粒子群智能算法傳感器節(jié)點(diǎn)的負(fù)載均衡程度高于PSO算法。該算法克服了陷入局部最優(yōu)解，具有較好的全局搜索能力。

5? 結(jié)論

本文將粒子群智能算法應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問(wèn)題中，設(shè)計(jì)了一種粒子群智能優(yōu)化算法，對(duì)PSO算法適應(yīng)度函數(shù)加入選擇算子的關(guān)聯(lián)，利用感知模型，以區(qū)域覆蓋率和負(fù)載均衡程度為目標(biāo)函數(shù)，算法收斂精度高，克服PSO算法易陷入局部最優(yōu)的不足，提高傳感器網(wǎng)絡(luò)覆蓋的質(zhì)量和效果，優(yōu)化無(wú)線傳感器網(wǎng)絡(luò)性能。

參考文獻(xiàn)：

[1]范興剛，楊靜靜，王恒.一種無(wú)線傳感器網(wǎng)絡(luò)的概率覆蓋增強(qiáng)算法[J].軟件學(xué)報(bào)，2016，27（2）：418-431.

[2] 周杰.基于進(jìn)化算法的大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)覆蓋關(guān)鍵技術(shù)研究[D].北京：北京郵電大學(xué)，2015.

[3] 神顯豪，李軍，奈何.感知受限的移動(dòng)傳感器節(jié)點(diǎn)掃描覆蓋優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2017，37（1）：60-64，102.

[4] 王偉，朱娟娟，萬(wàn)家山，等.基于混沌量子粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].傳感技術(shù)學(xué)報(bào)，2016，29（2）：290-296.

[5] 馬發(fā)民，張林，王錦彪.粒子群算法的改進(jìn)及其在優(yōu)化函數(shù)中的應(yīng)用[J].計(jì)算機(jī)與數(shù)字工程，2017，45（7）：1252-1255，1293.

[6] 林詩(shī)潔，董晨，陳明志，等.新型群智能優(yōu)化算法綜述[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（12）：1-9.

[7] 吳定會(huì)，高聰，紀(jì)志成.混合粒子群算法在微電網(wǎng)經(jīng)濟(jì)優(yōu)化運(yùn)行的應(yīng)用[J].控制理論與應(yīng)用，2018，35（4）：457-467.

[8] Arora S，Singh H，Sharma M，et al.A new hybrid algorithm based on grey wolf optimization and crow search algorithm for unconstrained function optimization and feature selection[J].IEEE Access，2019，7：26343-26361.

【通聯(lián)編輯：唐一東】