范賢志

（合肥學(xué)院先進(jìn)制造工程學(xué)院，安徽 合肥 230000）

無(wú)線傳感器網(wǎng)絡(luò)（WSN）由分布式傳感器構(gòu)成，是一種自組織、多節(jié)點(diǎn)的無(wú)線網(wǎng)絡(luò)[1]。WSN 覆蓋優(yōu)化目標(biāo)是實(shí)現(xiàn)區(qū)域內(nèi)無(wú)空洞覆蓋[2]。通常WSN 所處的監(jiān)測(cè)物理環(huán)境相對(duì)較差，難以借助人為方式進(jìn)行確定性部署[3]。動(dòng)態(tài)節(jié)點(diǎn)能夠適應(yīng)復(fù)雜多變的物理環(huán)境，但其部署不確定性較強(qiáng)，難以均勻、全面的覆蓋監(jiān)測(cè)區(qū)域，覆蓋質(zhì)量通常情況下低于預(yù)期。采用粒子群算法（PSO）能夠顯著提升動(dòng)態(tài)節(jié)點(diǎn)覆蓋率，但覆蓋重疊、局部最優(yōu)等現(xiàn)象依然存在。目前國(guó)內(nèi)眾多學(xué)者研究PSO 的改進(jìn)方法，文獻(xiàn)[4]在基本PSO 的基礎(chǔ)上引入模擬退火方法，替換掉適應(yīng)性不強(qiáng)的粒子，克服了基本PSO 易陷入局部最優(yōu)的劣勢(shì)，同時(shí)更新權(quán)重因子，加快收斂速度。文獻(xiàn)[5]借助虛擬勢(shì)場(chǎng)法的I-PSO，在WSN 節(jié)點(diǎn)之間構(gòu)建虛擬勢(shì)場(chǎng)，降低引力、斥力的波蕩，加快粒子收斂速度。文獻(xiàn)[6]將WSN 劃分為通信范圍大小不等的圓形區(qū)域，建立能耗模型，通過免疫算法和模擬退火粒子群算法相結(jié)合求解優(yōu)化模型，獲取能耗最小的匯聚節(jié)點(diǎn)移動(dòng)路徑。

1 WSN 覆蓋數(shù)學(xué)模型

公式（3）為WSN 覆蓋優(yōu)化模型目標(biāo)函數(shù)。

2 基本粒子群算法

PSO 是一種智能優(yōu)化算法，最早僅作為單目標(biāo)優(yōu)化算法而被應(yīng)用，PSO 不同于生物遺傳計(jì)算中變異、雜交等因子，而是模擬蟻群、蜂群、魚群等生物群體行為完成探索[8]。PSO 本身具備設(shè)置參數(shù)少、使用便捷、并行性號(hào)等優(yōu)勢(shì)。但由于基本PSO 無(wú)法適應(yīng)多目標(biāo)優(yōu)化需求，所以需要不斷對(duì)其進(jìn)行拓展[9]。和多數(shù)進(jìn)化算法相類似，PSO 也具備“進(jìn)化”、“群體”的概念，借助各個(gè)粒子間的競(jìng)爭(zhēng)與合作完成搜索區(qū)域最優(yōu)解的實(shí)現(xiàn)。改進(jìn)后的PSO 算法隱含并行性，一次進(jìn)化能夠求得多組解，十分匹配多目標(biāo)優(yōu)化問題的求解，已經(jīng)廣泛應(yīng)用在工業(yè)生產(chǎn)、能源勘測(cè)、電力運(yùn)輸?shù)阮I(lǐng)域。

PSO 主要借助兩個(gè)迭代公式完成較優(yōu)解的搜尋，公式（4）和公式（5）分別進(jìn)行計(jì)算：

總粒子數(shù)目為N，t 代表PSO 迭代次數(shù)，其中t≤T；i表示當(dāng)前粒子Ni（i=1，2，…，N），n 表示當(dāng)前維度；vNin表示粒子在當(dāng)前維度的速度；e1、e2分別為認(rèn)知、社交因子；Drand1、Drand2是介于0 到1 之間的隨機(jī)數(shù)；Popti為粒子自身計(jì)算所得最優(yōu)解；Gopti 為粒子群計(jì)算所得最優(yōu)解；ω 表示權(quán)重因子，正是由于該因子的存在，才能有效均衡PSO全局、局部搜索能力；ω 數(shù)值越大，PSO 局部搜索能力越弱；ω 數(shù)值越小，PSO 全局搜索能力越弱。

PSO 具體算法流程（圖1）為：

圖1 粒子群算法流程圖

（1）初始化粒子群，設(shè)置參數(shù)有：粒子數(shù)量Ni（i=1,2,…，N）、迭代次數(shù)t、權(quán)重因子ω、認(rèn)知因子e1、社交因子e2及速度上下限值[vmin，vmax]；

（2）按照函數(shù)或公式對(duì)適應(yīng)度值進(jìn)行計(jì)算；

（3）計(jì)算所得的個(gè)體最優(yōu)解Popti，對(duì)比Ni（i=1，2，…，N）個(gè)粒子對(duì)應(yīng)的個(gè)體最優(yōu)解，直至搜尋得到全局最優(yōu)解Gopti；

（4）按照公式（4）與公式（5）迭代所得當(dāng)前粒子的速度及坐標(biāo)，搜尋更優(yōu)的解，粒子速度不能超過限制，避免超出尋優(yōu)范圍。

（5）是否已經(jīng)為最大迭代次數(shù)或理論最優(yōu)值，若不是則返回步驟2，否則輸出結(jié)果同時(shí)結(jié)束運(yùn)行。

3 自適應(yīng)粒子群優(yōu)化算法（PSO-H）

3.1 進(jìn)化因子與匯聚因子

規(guī)定第t 次迭代的PSO 全局最優(yōu)值尋優(yōu)度為：

3.2 權(quán)重因子的自適應(yīng)調(diào)整

前文提到過，權(quán)重因子的大小直接決定了PSO 全局、局部尋優(yōu)能力的強(qiáng)弱。當(dāng)ω 數(shù)值較大時(shí)，粒子全局尋優(yōu)的能力較強(qiáng)；當(dāng)ω 數(shù)值較小時(shí)，粒子局部尋優(yōu)的能力較強(qiáng)。若進(jìn)化因子很大，PSO 整體進(jìn)化程度不強(qiáng)，需要降低ω 以提升粒子局部尋優(yōu)能力；若進(jìn)化因子很小，PSO 整體進(jìn)化程度較強(qiáng)，需要提升ω 以提升粒子全局尋優(yōu)能力；所以按照粒子當(dāng)前的進(jìn)化狀態(tài)對(duì)權(quán)重因子進(jìn)行調(diào)解能夠保證粒子更快達(dá)到收斂狀態(tài)。本文定義進(jìn)行第t 次迭代后粒子i 的自適應(yīng)ωti可以表達(dá)為：

其中，ω 為權(quán)重因子，a1、a2分別代表進(jìn)化因子、聚合因子調(diào)整系數(shù)，同時(shí)a1∈（0，+∞）、a2∈（-∞，ω），且a1+a2=1。

3.3 選取最優(yōu)粒子

PSO 在對(duì)多目標(biāo)優(yōu)化過程中，選取最優(yōu)粒子直接影響到最終的尋優(yōu)結(jié)果。本文選取粒子建立在解的分配、隨機(jī)原則之上，個(gè)體最優(yōu)粒子為進(jìn)化粒子所支配，當(dāng)前粒子個(gè)體最優(yōu)粒子為進(jìn)化后的解。若進(jìn)化后的解和當(dāng)前個(gè)體最優(yōu)粒子相互不支配，隨機(jī)更新個(gè)體最優(yōu)粒子，不然將維持個(gè)體最優(yōu)粒子的數(shù)量為恒值，以此確保解的非支配性、精確性。多目標(biāo)粒子群的尋優(yōu)過程是一個(gè)逐漸迭代的過程，保證其逐漸逼近真實(shí)值前沿的現(xiàn)象。相對(duì)于整個(gè)粒子群，其得到的非支配解組成的解集對(duì)于目前或從前的全部種群均為非支配，借助層次分析法能夠較為全面的評(píng)判數(shù)個(gè)非支配目標(biāo)。而相對(duì)于全局最優(yōu)粒子，充分借助進(jìn)化過程獲取進(jìn)化信息，選取綜合效用較低的粒子當(dāng)做全局最優(yōu)粒子，以此確保選取全局最優(yōu)粒子的有效性、準(zhǔn)確性。

3.4 外部歸檔集的更新和維護(hù)策略

恰當(dāng)?shù)母峦獠繗w檔集合、維護(hù)方式能夠確保PSO進(jìn)化過程中具備良好的多樣性、分布性，確保了算法的準(zhǔn)確性與可行性。筆者根據(jù)擁擠度的相關(guān)排序策略完成外部歸檔集完成更新和完善，定義表示了解的具體分布，擁擠度值越大表示解的分布性越完善，反之表示其分布性越差。所以在對(duì)外部歸檔集展開修復(fù)、更新的過程中，對(duì)于擁擠度較大的情況能夠予以保留，同時(shí)刪除那些擁擠度較小的狀況，確保其節(jié)點(diǎn)分布性、全面性，具體的擁擠度計(jì)算過程為：

（1）目前外部歸檔集中擁擠度初始化值設(shè)為0，解集大小定義為Ni（i=1，2，…，N），當(dāng)前目標(biāo)為N1，總目標(biāo)數(shù)為M；

（2）設(shè)置N1、NN粒子的擁擠度無(wú)窮大，對(duì)j=1 目標(biāo)展開降序排列；

（3）除N1外，其余粒子根據(jù)公式（14）對(duì)擁擠度距離進(jìn)行計(jì)算：

（4）判斷粒子是否大于N=1，若不是，則跳回執(zhí)行步驟3；若是，則繼續(xù)執(zhí)行步驟5；

（5）令i=i+1，判斷當(dāng)前粒子是否大于N，若不是，則跳回執(zhí)行步驟2；若是，則程序終止。

4 仿真結(jié)果驗(yàn)證

本文用MATLAB 作為仿真驗(yàn)證工具，對(duì)本文自適應(yīng)粒子群算法（PSO-H）進(jìn)行仿真驗(yàn)證，對(duì)其性能分別和PSO、蟻群算法（ACO）進(jìn)行對(duì)比。為了保證測(cè)試的精準(zhǔn)性，能夠充分體現(xiàn)PSO-H 算法優(yōu)勢(shì)，同時(shí)確保各個(gè)算法實(shí)驗(yàn)參數(shù)一致性。在進(jìn)行算法覆蓋范圍的仿真、比較過程中，取算法運(yùn)行10 次的平均值來(lái)作為最終體現(xiàn)其覆蓋性能的依據(jù)，具體仿真參數(shù)見表1。

表1 仿真參數(shù)

為了驗(yàn)證自適應(yīng)粒子群效果，若在同構(gòu)網(wǎng)絡(luò)中WSN覆蓋半徑為5 米，仿真結(jié)果如圖2 至圖5 所示。圖2 為WSN 初始節(jié)點(diǎn)分布圖；圖3 為PSO 仿真節(jié)點(diǎn)覆蓋圖；圖4 為ACO 仿真節(jié)點(diǎn)覆蓋圖；圖5 為PSO-H 仿真節(jié)點(diǎn)覆蓋圖。圖中矩形區(qū)域表示W(wǎng)SN 待監(jiān)測(cè)區(qū)域，圓形區(qū)域代表WSN 節(jié)點(diǎn)覆蓋范圍。如圖，在監(jiān)測(cè)區(qū)域隨機(jī)散落WSN節(jié)點(diǎn)，在基本參數(shù)完全一致的情況下，分別采用PSO、ACO 和PSO-H 對(duì)節(jié)點(diǎn)覆蓋進(jìn)行優(yōu)化。通過對(duì)比4 張節(jié)點(diǎn)覆蓋圖的變化進(jìn)行分析，PSO、ACO 較初始節(jié)點(diǎn)分布在監(jiān)測(cè)范圍內(nèi)取得了一定改善，但是監(jiān)測(cè)區(qū)域仍然存在大量的覆蓋重疊和空洞現(xiàn)象，在經(jīng)過自適應(yīng)粒子群算法進(jìn)行優(yōu)化后，節(jié)點(diǎn)分布更加均勻，重疊區(qū)域、空洞現(xiàn)象大幅度降低。

圖2 WSN 初始節(jié)點(diǎn)分布

圖3 基本PSO 節(jié)點(diǎn)覆蓋圖

圖4 基本ACO 節(jié)點(diǎn)覆蓋圖

圖5 PSO-H 節(jié)點(diǎn)覆蓋圖

PSO 在算法運(yùn)行85 次迭代后趨于收斂，ACO 在算法運(yùn)行90 次迭代后趨于收斂，PSO 算法覆蓋率59.7%，無(wú)效覆蓋率為34.2%；ACO 算法覆蓋率63.4%，無(wú)效覆蓋率為31.7%。

仿真結(jié)果顯示，粒子數(shù)量、迭代次數(shù)完全一致的情況下，PSO-H 相較于基本粒子群算法和蟻群算法，對(duì)覆蓋區(qū)域面積有著更大、覆蓋效果更優(yōu)的優(yōu)勢(shì)。

5 結(jié)論

為了確保WSN 部署的有效性，增強(qiáng)WSN 在相同節(jié)點(diǎn)下的覆蓋質(zhì)量。本文研究分析，在基本粒子群中引入進(jìn)化因子、匯聚因子，同時(shí)自適應(yīng)調(diào)整權(quán)重因子，及時(shí)更新粒子選取、外部歸檔集更新及維護(hù)策略，增強(qiáng)算法尋找最優(yōu)解的能力。同時(shí)經(jīng)過仿真驗(yàn)證，分別和PSO、ACO算法進(jìn)行比較，從覆蓋性能、無(wú)效覆蓋率進(jìn)行分析。PSO-H 收斂速度更快、覆蓋率更高，極大的避免了算法早熟陷入局部最優(yōu)的情況，增強(qiáng)了WSN 節(jié)點(diǎn)部署能力。