基于ISSA的WSN覆蓋優(yōu)化

摘 要：在無線傳感器網(wǎng)絡(luò)（WSN）中，覆蓋優(yōu)化是一個(gè)重要且具有挑戰(zhàn)性的問題。文中提出了一種基于改進(jìn)麻雀搜索算法（ISSA）的WSN覆蓋優(yōu)化方法，旨在優(yōu)化網(wǎng)絡(luò)中節(jié)點(diǎn)的部署，以最大程度提高網(wǎng)絡(luò)覆蓋范圍。首先，利用Tent混沌映射策略對麻雀種群初始分布進(jìn)行優(yōu)化，增加種群多樣性。然后，通過使用柯西變異對算法全局搜索能力與局部搜索精度進(jìn)行平衡。最后，在每一次迭代后期，采用反向?qū)W習(xí)策略提升種群質(zhì)量。將改進(jìn)后的算法用于WSN覆蓋優(yōu)化問題中，并與標(biāo)準(zhǔn)麻雀搜索算法以及其他算法進(jìn)行對比。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的麻雀搜索算法的WSN覆蓋率明顯提升。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；覆蓋優(yōu)化；麻雀搜索算法；混沌映射；柯西變異；反向?qū)W習(xí)

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2024）08-00-04

DOI：10.16667/j.issn.2095-1302.2024.08.013

0 引 言

無線傳感器網(wǎng)絡(luò)（WSN）作為重要的信息采集和傳輸解決方案，已在多領(lǐng)域展現(xiàn)其價(jià)值[1]。然而，在這類網(wǎng)絡(luò)中，節(jié)點(diǎn)的適當(dāng)部署尤為重要，會直接影響網(wǎng)絡(luò)性能和能源消耗等關(guān)鍵指標(biāo)。特別是在需要覆蓋大范圍特定區(qū)域的應(yīng)用場景，例如環(huán)境監(jiān)測、災(zāi)害預(yù)警和智能交通等領(lǐng)域，如何優(yōu)化網(wǎng)絡(luò)覆蓋成為一個(gè)具有挑戰(zhàn)性的核心任務(wù)[2]。

為解決WSN的覆蓋優(yōu)化問題，許多學(xué)者提出了智能優(yōu)化算法[3-6]。文中提出了一種基于多種策略改進(jìn)而成的麻雀搜索算法（Improved Sparrow Search Algorithm， ISSA），旨在通過優(yōu)化網(wǎng)絡(luò)中節(jié)點(diǎn)的部署，最大程度提高網(wǎng)絡(luò)的覆蓋范圍。麻雀搜索算法是由薛建凱等學(xué)者于2020年提出的一種全新群體智能算法[7]。其創(chuàng)意源自麻雀的覓食與反覓食行為，因此具備出色的全局搜索能力與易于實(shí)現(xiàn)等特點(diǎn)。然而，傳統(tǒng)的麻雀搜索算法在處理WSN覆蓋問題中的優(yōu)化效果有限，并且容易陷入局部最優(yōu)，最終的覆蓋優(yōu)化效果并不

理想。

為解決這些問題，文中在ISSA中進(jìn)行了幾處關(guān)鍵改進(jìn)。首先，運(yùn)用Tent混沌映射對種群進(jìn)行初始設(shè)置，以提升種群的多樣性，從而更有效地展開對搜索空間的探索。其次，融入了柯西變異策略，巧妙平衡了算法的整體全局搜索能力和局部搜索的精準(zhǔn)度。算法可以更加全面而又精準(zhǔn)地探索最優(yōu)解空間。最后，在每輪迭代的后期階段，引入了反向?qū)W習(xí)機(jī)制，精心優(yōu)化了種群的質(zhì)量。這一策略的引入，極大避免了種群過早收斂和陷入局部最優(yōu)解。在本研究的框架下，我們將改進(jìn)后的ISSA方法嫁接到WSN覆蓋優(yōu)化問題上，并將其與傳統(tǒng)的麻雀搜索算法以及其他廣泛采用的優(yōu)化算法進(jìn)行了一系列對比實(shí)驗(yàn)。顯而易見，經(jīng)過精心改進(jìn)的ISSA在增強(qiáng)WSN覆蓋能力方面表現(xiàn)出色，與其他算法相比，該算法展現(xiàn)出了更為卓越優(yōu)異的性能。

1 WSN覆蓋模型

在區(qū)域M內(nèi)，布設(shè)傳感器網(wǎng)絡(luò)，每個(gè)傳感器的節(jié)點(diǎn)都具備相同的感知半徑r。然后將整個(gè)監(jiān)測區(qū)域離散化為L×W的網(wǎng)格，其中每個(gè)網(wǎng)格的中心點(diǎn)被視為一個(gè)重要的覆蓋目標(biāo)，并且這些目標(biāo)點(diǎn)的集合被記為P（x， y）。在該網(wǎng)絡(luò)結(jié)構(gòu)中，監(jiān)測效果受制于傳感器節(jié)點(diǎn)的分布格局和其感知范圍的安排。如果每個(gè)傳感器節(jié)點(diǎn)存在一個(gè)覆蓋目標(biāo)點(diǎn)，使得該目標(biāo)點(diǎn)P與該節(jié)點(diǎn)的距離不超過感知半徑r，則認(rèn)為該目標(biāo)點(diǎn)被傳感器覆蓋。

在被監(jiān)測區(qū)域內(nèi)，設(shè)傳感器節(jié)點(diǎn)的集合為S={s1， s2， s3， ...， sn}，則其中第i個(gè)傳感器節(jié)點(diǎn)的位置si（xi， yi）與覆蓋目標(biāo)點(diǎn)Pj的距離為：

（1）

目標(biāo)節(jié)點(diǎn)Pj被感知到的概率為：

（2）

在監(jiān)測區(qū)域內(nèi)的目標(biāo)點(diǎn)能夠被多個(gè)傳感器節(jié)點(diǎn)同時(shí)檢測，那么針對該目標(biāo)點(diǎn)的聯(lián)合測量概率可表述為：

（3）

所有節(jié)點(diǎn)的覆蓋率為：

（4）

文中將Cr作為優(yōu)化WSN網(wǎng)絡(luò)覆蓋的目標(biāo)函數(shù)，求Cr的最大值。

2 基本SSA算法原理

麻雀搜索算法的靈感主要來源于麻雀群體覓食的行為。在覓食過程中，麻雀展示出3種明確的行為策略，分別是發(fā)現(xiàn)者、跟隨者和警戒者。這些行為緊密合作，使整個(gè)麻雀群體能夠高效尋找食物來源。發(fā)現(xiàn)者麻雀擁有較高的適應(yīng)度，會主動(dòng)搜索食物。約有10%～20%的個(gè)體隨機(jī)選擇成為跟隨者，它們緊緊跟隨發(fā)現(xiàn)者，共同分享食物資源。警戒者始終保持潛在警覺，監(jiān)測威脅，必要時(shí)向整個(gè)群體發(fā)出警告，以確保群體的安全。

2.1 種群初始化

初始化麻雀種群位置，n只麻雀在d維空間中的位置如下所示：

（5）

式中：n為麻雀個(gè)體數(shù)量；d為優(yōu)化問題維度。通過當(dāng)前初始化位置可求出初始化種群適應(yīng)度，如式（6）所示：

（6）

式中：f表示適應(yīng)度函數(shù)；F表示適應(yīng)度值。

2.2 發(fā)現(xiàn)者位置更新

在SSA中，發(fā)現(xiàn)者通常由適應(yīng)度較高的麻雀個(gè)體擔(dān)任，這些個(gè)體在搜索過程中會優(yōu)先獲得食物資源。它們致力于尋找食物，并為其他成員提供覓食區(qū)域和前進(jìn)方向的指引。發(fā)現(xiàn)者具有更廣泛的搜索范圍，具有更高概率找到潛在的食物來源。其位置更新公式如下：

（7）

式中：t代表算法當(dāng)前所處的迭代次數(shù)；itermax表示算法需要迭代的總次數(shù)；i代表第i只麻雀個(gè)體；ST是安全閾值；R2為預(yù)警值；α是一個(gè)[0， 1]區(qū)間的隨機(jī)數(shù)；L表示1×d的矩陣，該矩陣中的元素均為1；Q是隨機(jī)數(shù)，其服從正態(tài)分布。當(dāng)R2lt;ST時(shí)，表明種群所處環(huán)境相對安全，周圍沒有發(fā)現(xiàn)捕食者的跡象。這時(shí)，發(fā)現(xiàn)者可以放心地進(jìn)行廣泛搜索，努力尋找更多食物資源，為種群提供豐富的供給。當(dāng)R2≥ST時(shí)，表示群內(nèi)個(gè)體已經(jīng)察覺到可能存在捕食者，并通過發(fā)出警報(bào)來警示其他成員。在這種情況下，群體將采取反捕食行動(dòng)，緊密合作，以保護(hù)自身安全。

2.3 跟隨者位置更新

跟隨者總是能夠搜索到食物的來源和所處區(qū)域，這些來源由發(fā)現(xiàn)者發(fā)現(xiàn)并指引，而跟隨者與發(fā)現(xiàn)者的身份可能隨時(shí)會發(fā)生轉(zhuǎn)變。跟隨者的位置更新公式如下所示：

（8）

式中：XP為占據(jù)的最優(yōu)位置；Xw為最差位置；A為1×d維的矩陣，該矩陣中每個(gè)元素隨機(jī)賦值為1或-1，其中A+=AT（AAT）-1。當(dāng)igt;n/2時(shí)，表示適應(yīng)性較差的第i個(gè)跟隨者沒有得到足夠的食物，需要去其他位置尋找能量來源；當(dāng)i≤n/2時(shí)，跟隨者仍然保持在發(fā)現(xiàn)者附近，并與其他更高級的捕食者競爭食物。

2.4 警戒者位置更新

警戒者是種群中隨機(jī)選擇的個(gè)體，當(dāng)感知到危險(xiǎn)時(shí)會發(fā)出信號讓其他麻雀逃離，其位置更新如式（9）所示：

（9）

式中：Xbt表示當(dāng)前全局最佳位置；K為[-1， 1]的隨機(jī)數(shù)；β表示步長控制，它是一個(gè)服從正態(tài)分布的隨機(jī)數(shù)；fi表示麻雀個(gè)體的適應(yīng)度值；fg表示全局最佳適應(yīng)度值；fw表示全局最差適應(yīng)度值；ε是防止分母為0的最小實(shí)數(shù)。

3 ISSA算法

3.1 Tent混沌映射

混沌映射常被作為改進(jìn)智能算法的手段，它有助于提高群體多樣性并增強(qiáng)算法的探索能力。相比于Logistic映射，Tent映射[8]具有一些利于優(yōu)化算法初始化的特點(diǎn)，例如結(jié)構(gòu)簡單、分布較為均勻以及遍歷性良好等，使其在優(yōu)化算法中有著廣泛的應(yīng)用。借助Tent映射方法對麻雀種群進(jìn)行初始設(shè)置，能夠使種群在搜索空間中分布更為均勻。這種初始分布的設(shè)計(jì)有助于引導(dǎo)算法全面探索搜索空間，進(jìn)而提升SSA在尋優(yōu)過程中的全局搜索能力和收斂速度。綜上所述，通過引入Tent映射策略，有效解決了麻雀搜索算法在優(yōu)化過程中可能遇到的多樣性不足和局部最優(yōu)問題，從而顯著增強(qiáng)算法的性能。Tent混沌映射表達(dá)式如下：

（10）

式中：α∈（0， 1），本文取值0.5。

3.2 柯西變異

柯西分布與標(biāo)準(zhǔn)正態(tài)分布有諸多相似之處，并且這兩種分布都屬于連續(xù)的概率分布。不過，相比標(biāo)準(zhǔn)正態(tài)分布，柯西分布在原點(diǎn)附近取值更小一些，而在兩端則呈現(xiàn)長尾特點(diǎn)，所以該分布能夠產(chǎn)生的擾動(dòng)幅度更大。通過應(yīng)用柯西分布的變異來擾動(dòng)麻雀的位置，能夠有效擴(kuò)展麻雀算法的搜索范圍，從而增強(qiáng)算法克服局部最優(yōu)解的能力。在跟隨者位置更新中引入柯西變異策略，改進(jìn)后的跟隨者位置更新如下：

（11）

式中：cauchy（0， 1）為柯西函數(shù)分布；表示相乘?？挛髯儺惡瘮?shù)為：

（12）

3.3 反向?qū)W習(xí)

反向?qū)W習(xí)是通過計(jì)算當(dāng)前解的反向解來擴(kuò)大搜索范圍的一種優(yōu)化策略[9]，在本算法中可以有效提高搜索性能。在算法每一次迭代后期使用反向?qū)W習(xí)來提高搜索效率，進(jìn)一步提升種群質(zhì)量，反向解可定義為：

（13）

式中：Xi， j為當(dāng)前迭代的原始種群；X'i， j為當(dāng)前迭代種群的反向解；Ubi， j和Lbi， j分別為對應(yīng)種群個(gè)體的上限和下限。然后通過對比2個(gè)種群所對應(yīng)的適應(yīng)度值，選取最優(yōu)種群進(jìn)入下一次迭代。

3.4 ISSA算法流程

改進(jìn)后的麻雀搜索算法流程如下：

（1）設(shè)置初始參數(shù)，主要包括最大迭代次數(shù)、種群數(shù)量等參數(shù)；

（2）使用Tent混沌映射策略初始化麻雀種群位置，計(jì)算個(gè)體的適應(yīng)度并排序，分別確定最優(yōu)和最差個(gè)體；

（3）更新發(fā)現(xiàn)者位置；

（4）將柯西變異融入到跟隨者位置更新的策略中，使其不斷與發(fā)現(xiàn)者拉近距離；

（5）如果警戒者發(fā)現(xiàn)危險(xiǎn)，則迅速更新位置，尋找安全的食物源；

（6）使用反向?qū)W習(xí)策略生成當(dāng)前每個(gè)個(gè)體的反向解，并計(jì)算相應(yīng)適應(yīng)度值，留下最優(yōu)的個(gè)體；

（7）對麻雀個(gè)體適應(yīng)度進(jìn)行大小排序；

（8）判斷當(dāng)前迭代次數(shù)是否滿足終止條件，若滿足，則進(jìn)行下一步，否則跳轉(zhuǎn)至步驟（3）；

（9）程序結(jié)束，輸出最優(yōu)的種群位置及適應(yīng)度值。

在WSN覆蓋優(yōu)化過程中，文中的優(yōu)化對象是式（4），通過不斷更新種群位置使得傳感器節(jié)點(diǎn)部署達(dá)到更廣的覆蓋范圍。

4 仿真實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

采用MATLAB R2022a平臺對所提方法進(jìn)行仿真，并對ISSA算法的優(yōu)化性能進(jìn)行了測試。將基于ISSA算法的WSN覆蓋效果與基于PSO[10]、基于WOA[11]以及基于SSA的WSN覆蓋方法進(jìn)行對比，實(shí)驗(yàn)結(jié)果清楚展示了文中算法在WSN覆蓋優(yōu)化方面的顯著優(yōu)越性。為確保算法的公平性，在實(shí)驗(yàn)過程中保持了一致的參數(shù)設(shè)置，具體參數(shù)見表1所列。

4.2 仿真結(jié)果與分析

按照表1中的參數(shù)進(jìn)行仿真實(shí)驗(yàn)，圖1～圖6為實(shí)驗(yàn)仿真結(jié)果。其中，圖1為節(jié)點(diǎn)的隨機(jī)初始化覆蓋效果，圖2為基于PSO的WSN覆蓋效果，圖3為基于WOA的WSN覆蓋效果，圖4為基于SSA的WSN覆蓋效果，圖5為基于ISSA的覆蓋效果，圖6為4種算法在各迭代次數(shù)中覆蓋率的變化曲線。

從圖1中可以看出，隨機(jī)WSN覆蓋效果比較混亂，節(jié)點(diǎn)分布不均且覆蓋率低，因此需要使用算法對其優(yōu)化，以保證較高的覆蓋率。將圖5分別與圖2、圖3、圖4對比發(fā)現(xiàn)，基于ISSA的WSN覆蓋優(yōu)化效果比基于PSO、WOA、SSA的WSN覆蓋優(yōu)化效果更好，節(jié)點(diǎn)分布更加均勻，并且分布效果圖中沒有出現(xiàn)較大的未被覆蓋的空白區(qū)域。

從圖6可以對比出隨著迭代次數(shù)的不斷增加，4種算法對應(yīng)的WSN覆蓋率變化曲線如何變化。在迭代結(jié)束后，基于PSO的WSN覆蓋算法的覆蓋率最低，最終的覆蓋率僅達(dá)到了79.8%；基于WOA的WSN覆蓋算法的覆蓋率達(dá)到了86.4%；相比于前兩種算法，基于SSA的WSN覆蓋算法的覆蓋率較高，達(dá)到了90.2%；而基于ISSA的WSN覆蓋算法的覆蓋率在SSA的基礎(chǔ)上有了較為明顯的提升，最終達(dá)到了94.8%，提升了4.6個(gè)百分點(diǎn)。綜上可知，基于ISSA的WSN覆蓋優(yōu)化具有更好的覆蓋效果，有效提升了WSN隨機(jī)覆蓋時(shí)的整體覆蓋范圍。

5 結(jié) 語

文中針對WSN覆蓋優(yōu)化問題，提出采用ISSA算法對其覆蓋效果進(jìn)行優(yōu)化，該算法利用Tent混沌映射策略對種群進(jìn)行初始化，用柯西變異來平衡算法的全局搜索能力與局部搜索精度，通過反向?qū)W習(xí)策略優(yōu)化種群質(zhì)量，然后將ISSA算法應(yīng)用于WSN覆蓋優(yōu)化中。通過仿真實(shí)驗(yàn)將文中所提方法分別與基于PSO的WSN覆蓋優(yōu)化、基于WOA的WSN覆蓋優(yōu)化、基于SSA的WSN覆蓋優(yōu)化進(jìn)行對比分析。仿真結(jié)果顯示，文中所提算法在WSN覆蓋優(yōu)化問題上展現(xiàn)出了更加卓越的性能。優(yōu)化后，WSN的覆蓋率顯著提升，進(jìn)一步驗(yàn)證了算法的有效性。

注：本文通訊作者為馮鋒。

參考文獻(xiàn)

[1]李建中，高宏.無線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)

展，2008，51（1）：1-15.

[2]范星澤，禹梅.改進(jìn)灰狼算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].計(jì)算機(jī)科學(xué)，2022，49（z1）：628-631.

[3]宋婷婷，張達(dá)敏，王依柔，等.基于改進(jìn)鯨魚優(yōu)化算法的WSN覆蓋優(yōu)化[J].傳感技術(shù)學(xué)報(bào)，2020，33（3）：415-422.

[4]張浩，龍道銀，覃濤，等.改進(jìn)人工蜂群算法的WSN覆蓋連通優(yōu)化[J].計(jì)算機(jī)工程與設(shè)計(jì)，2022，43（10）：2701-2710.

[5]李斐，朱曉磊.多策略增強(qiáng)樽海鞘算法下的WSN覆蓋優(yōu)化[J].計(jì)算機(jī)時(shí)代，2023，41（1）：26-29.

[6]齊薇，虞慧群，范貴生，等.基于自適應(yīng)粒子群的WSN覆蓋優(yōu)化

[J].計(jì)算機(jī)科學(xué)，2020，47（7）：243-249.

[7] XUE J，SHEN B. A novel swarm intelligence optimization approach： sparrow search algorithm [J]. Systems science amp; control engineering，2020，8（1）：22-34.

[8]呂鑫，慕曉冬，張鈞，等.混沌麻雀搜索優(yōu)化算法[J].北京航空航天大學(xué)學(xué)報(bào)，2021，47（8）：1712-1720.

[9] TIZHOOSH H R. Opposition-based learning： a new scheme for machine intelligence [C]// International Conference on Computational Intelligence for Modelling，Control and Automation and International Conference on Intelligent Agents，Web Technologies and Internet Commerce（CIMCA-IAWTIC’06）. [S.l.]：[s.n.]，IEEE，2005：695-701.

[10] KENNEDY J，RUSSELL E. Particle swarm optimization [C]// Proceedings of ICNN’95-International Conference on Neural Networks. [S.l.]：[s.n.]，1995：771-779.

[11] MIRJALILI S，LEWIS A. The whale optimization algorithm [J]. Advances in engineering software，2016，95：51-67.

收稿日期：2023-08-18 修回日期：2023-09-25

基金項(xiàng)目：寧夏重點(diǎn)研發(fā)計(jì)劃重點(diǎn)項(xiàng)目（2022BEG02016）；寧夏自然科學(xué)基金重點(diǎn)項(xiàng)目（2021AAC02004）

作者簡介：高懿（2002—），男，研究方向?yàn)槲锫?lián)網(wǎng)技術(shù)及應(yīng)用。

李 振（1998—），男，研究方向?yàn)槲锫?lián)網(wǎng)技術(shù)及應(yīng)用。

馮 鋒（1971—），男，博士，教授，研究方向?yàn)樾畔⑾到y(tǒng)工程、物聯(lián)網(wǎng)技術(shù)及應(yīng)用。