賈鶴鳴，施宇鋮，劉俊良，力尚龍，饒洪華

（三明學(xué)院 信息工程學(xué)院，福建 三明 365004）

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network, WSN）是在監(jiān)測區(qū)域內(nèi)部署擁有感知信息能力和通信能力的傳感器節(jié)點， 通過自組織形成一種大規(guī)模分布式網(wǎng)絡(luò)，實現(xiàn)對監(jiān)測區(qū)域內(nèi)聲音、溫度等數(shù)據(jù)的采集，把采集到的信息發(fā)至管理中心，最后服務(wù)于用戶。目前，無線傳感器網(wǎng)絡(luò)已廣泛應(yīng)用于醫(yī)療、工業(yè)和軍事等領(lǐng)域［1-3］。

在無線傳感器網(wǎng)絡(luò)中， 網(wǎng)絡(luò)覆蓋率決定了網(wǎng)絡(luò)的性能。為了實現(xiàn)網(wǎng)絡(luò)覆蓋率的最大化，通常先將監(jiān)控區(qū)域分成多個單元格， 再計算每個單元格的邊界點是否被覆蓋， 最后統(tǒng)計被覆蓋的點并計算監(jiān)測區(qū)域的網(wǎng)絡(luò)覆蓋率。如何部署移動節(jié)點，避免節(jié)點分布不均勻以及降低部署成本等都是實現(xiàn)無線傳感器網(wǎng)絡(luò)節(jié)點優(yōu)化部署的重要課題。

近年來， 一些學(xué)者對無線傳感器網(wǎng)絡(luò)節(jié)點優(yōu)化部署問題進行了深入而廣泛的研究。 李守玉等［4］利用改進的平衡優(yōu)化器算法， 通過加入環(huán)繞反向?qū)W習(xí)和circle 混沌映射等對平衡器算法進行了改進，降低了部署成本，提高了網(wǎng)絡(luò)監(jiān)測質(zhì)量。 張微微等［5］提出了能優(yōu)化傳感器網(wǎng)絡(luò)節(jié)點覆蓋的改進人工魚群算法，利用Map/Reduce 工作機制解決了無線傳感器網(wǎng)絡(luò)節(jié)點部署存在的問題。 劉寬等［6］分析了WSN 感知節(jié)點的抽象化模型， 用數(shù)學(xué)方法論證了實現(xiàn)感知范圍全覆蓋的算法， 使用六邊形網(wǎng)格劃分法對確定的平面區(qū)域中節(jié)點進行了全覆蓋部署， 實現(xiàn)了節(jié)點覆蓋效率的最大化。

2020 年，LI S. M.等提出了一種新型群體智能優(yōu)化算法，即黏菌算法（Slime Mould Algorithm, SMA）［7］，通過建立粗細不一的食物網(wǎng)模擬了黏菌的捕食行為。 此算法具有較強的全局探索能力，已廣泛應(yīng)用于優(yōu)化應(yīng)用領(lǐng)域。 唐雄［8］利用改進SMA 研究了網(wǎng)絡(luò)入侵問題，已取得了令人滿意的結(jié)果。 針對黏菌算法在無線傳感器網(wǎng)絡(luò)覆蓋上存在的不足， 我們提出了一種改進的黏菌算法。 首先，對參數(shù)p 進行了改進，更好地平衡了局部搜索的能力和全局搜索的能力，借助混沌精英突變策略［9］提高算法的尋優(yōu)能力；其次，將改進的黏菌算法與其他優(yōu)化算法進行對比實驗，得出ISMA 具有更好的尋優(yōu)能力，能有效減少節(jié)點冗余，提高無線傳感器網(wǎng)絡(luò)的覆蓋率的結(jié)論。

1 傳感器網(wǎng)絡(luò)節(jié)點覆蓋模型

假設(shè)監(jiān)控區(qū)域是一個長方形， 其長為L， 寬為W，面積為S=L×W。在監(jiān)控區(qū)域里隨機部署n 個傳感器節(jié)點，這n 個節(jié)點構(gòu)成的集合［10］為

每個節(jié)點的感知半徑都為R，通信半徑都為r。

為計算上的方便，把監(jiān)控區(qū)域離散為L×W 個大小相等的單元點， 每個單元點代表所要監(jiān)控的目標(biāo)點，其集合為

圖1 節(jié)點感知模型

2 黏菌算法基本原理

黏菌算法是基于黏菌覓食行為的一種優(yōu)化算法。 在覓食過程中， 黏菌發(fā)現(xiàn)食物時會發(fā)生振蕩收縮。 另外，在多個食物源之間，會形成粗細不一的靜脈網(wǎng)絡(luò)，靜脈網(wǎng)絡(luò)的粗細與食物源的質(zhì)量有關(guān)。而黏菌在獲取食物時，仍有可能對未知區(qū)域進行搜索。黏菌的行為主要有3 種，即接近食物、包裹食物和獲取食物［7］。

2.1 接近食物

黏菌在發(fā)現(xiàn)食物時，會發(fā)生收縮，其收縮模式可描述為

2.2 包裹食物

根據(jù)上述分析，黏菌位置的更新可表示為

2.3 獲取食物

黏菌依靠生物振蕩器產(chǎn)生的波改變靜脈中的細胞質(zhì)流動，使其處于食物濃度較高的位置。為了模擬黏菌具體靜脈寬度的變化， 我們使用W、vb 和vc 描述黏菌的行為。通過模擬黏菌的振蕩頻率，使黏菌找到優(yōu)質(zhì)食物時可更快地接近食物。 當(dāng)食物濃度較低時，黏菌接近食物的速度較慢，可以提高黏菌選擇最佳食物源的效率。 vb 在［-a, a］內(nèi)并且隨著迭代次數(shù)的增加逐漸接近零。 vc 在［-1, 1］之間振蕩，最終趨于零。vb 和vc 之間的協(xié)同作用模擬了黏菌的選擇行為。 為了找到更好的食物來源，黏菌會分離一些有機物，用于探索其他領(lǐng)域，以試圖找到更高質(zhì)量的食物。

3 改進黏菌算法

3.1 參數(shù)p 的改進

在SMA 中，參數(shù)p 決定了黏菌的探索和開發(fā)能力，由式（6）可知，當(dāng)最優(yōu)個體與其他個體的適應(yīng)度大于4 時，p 的取值接近1，使用公式（11）更新黏菌的位置。 對于WSN 覆蓋問題，最優(yōu)個體的適應(yīng)度與其他個體的適應(yīng)度相差較小， 容易陷入局部最優(yōu)而無法尋找到更優(yōu)的解。為了使開發(fā)和探索更加平衡，對p 進行重構(gòu)，其表達式為

3.2 混沌精英突變策略

在原始SMA 中，種群的位置需要通過最優(yōu)位置和隨機位置引導(dǎo)， 雖然這種算法有利于增大候選解跳出局部最優(yōu)的可能性， 但隨機數(shù)的不確定性導(dǎo)致SMA 的收斂速度變慢。 為了改善算法依靠隨機位置和最優(yōu)位置的問題，提高算法的收斂速度，本文考慮到混沌序列的隨機性、遍歷性和整體穩(wěn)定的特點，對最優(yōu)解進行混沌精英突變，具體實現(xiàn)過程如下。

將最優(yōu)解的位置向量從解空間降維映射到區(qū)間［-1, 1］，即可得混沌變量

3.3 基于改進黏菌算法的WSN 覆蓋實現(xiàn)步驟

綜上所述，我們提出一種改進的黏菌算法，通過對參數(shù)p 的改進，使開發(fā)和探索的能力更加平衡。 通過引入混沌精英突變策略避免算法對最優(yōu)解過度依賴，提高算法的尋優(yōu)能力。

對于WSN 覆蓋問題，最優(yōu)個體的適應(yīng)度與其他個體的適應(yīng)度相差較小， 容易陷入局部最優(yōu)而無法尋找到更優(yōu)的解， 而改進后的黏菌算法能解決該問題。 利用ISMA 求解WSN 節(jié)點部署的優(yōu)化流程如圖2 所示。

圖2 利用ISMA 求解WSN 節(jié)點部署的優(yōu)化流程

利用ISMA 求最優(yōu)覆蓋率的步驟表示如下：

步驟1：初始化參數(shù)，將黏菌種群的規(guī)模設(shè)定為N，空間維度為dim，最大迭代次數(shù)為Tmax，對參數(shù)z 賦值。

步驟2：初始化種群，將黏菌種群隨機分布在空間中，并設(shè)置初始迭代次數(shù)t 為1。

步驟3：通過式（1）～（4）計算種群個體的WSN覆蓋率，并按覆蓋率的大小排序，記錄最優(yōu)覆蓋率的個體位置。

步驟4：根據(jù)式（8）更新權(quán)重W。

步驟5：在［0, 1］內(nèi)產(chǎn)生一個隨機數(shù)r，并與z 比較。 如果r＜z,就利用式（10）更新黏菌個體位置，否則，繼續(xù)在［0, 1］內(nèi)生成一個隨機數(shù)r1。 比較r1是否小于由式（13）得出的p，如果是，就利用式（11）更新黏菌個體的位置，否則利用式（12）更新黏菌個體的位置。

步驟6：利用式（14）、式（15）和式（17）求出變量φ（t）和H，再利用式（16）求出更新后的位置X*，計算更新后位置所對應(yīng)的覆蓋率。 與原位置的覆蓋率進行比較，如果比原先覆蓋率大，就替換原來位置及對應(yīng)的覆蓋率。

步驟7： 判斷迭代次數(shù)t 是否達到最大迭代次數(shù)，如果達到迭代次數(shù)，就輸出全局最優(yōu)值并結(jié)束運算，否則，進行下一次迭代。

4 仿真實驗與分析

將ISMA 與改進灰狼算法 （Improved Grey Wolf Optimization, IGWO）［12］、 改 進 的 粒 子 群 優(yōu) 化 算 法（Particle Swarm Optimization, PSO-H）［13］、改進鯨魚優(yōu)化算法（Improved Whale Optimization Algorithm, IWOA）［14］及原始SMA 進行比較。 實驗軟件為MATLAB R2021b。

4.1 與原始SMA 對比

為了比較原始SMA 和優(yōu)化ISMA 的計算效果，我們設(shè)計了3 組實驗， 實驗種群的規(guī)模為30， 最大迭代次數(shù)為500，其他所需參數(shù)如表1 所示。

表1 實驗分組及參數(shù)設(shè)置

表2 給出SMA 和ISMA 在每個組下的覆蓋率。圖3 給出了該環(huán)境下SMA 和ISMA 的優(yōu)化節(jié)點分布，圖4、圖5 和圖6 分別給出了該環(huán)境下每個組的WSN 覆蓋率隨迭代次數(shù)的變化情況。

圖3 SMA 和ISMA 在每一組下的優(yōu)化節(jié)點分布

圖5 組2 的WSN 覆蓋率隨迭代次數(shù)的變化情況

圖6 組3 的WSN 覆蓋率隨迭代次數(shù)的變化情況

表2 SMA 與ISMA 的覆蓋率對比

從表2 可以看出， 在第1 組、 第2 組和第3 組中，ISMA 的優(yōu)化覆蓋率比SMA 分別高出15.08%、11.76%和8.02%。 從圖3、圖4、圖5 和圖6 可以看出：在探索全局最優(yōu)解方面，ISMA 比SMA 更容易跳出局部最優(yōu)， 得到更佳的覆蓋率；ISMA 的節(jié)點分布比SMA 的均勻。

4.2 與SMA 及其他算法的對比

假設(shè)監(jiān)測區(qū)域為20 m×20 m 的正方形平面，種群規(guī)模為30，傳感器節(jié)點個數(shù)為24，感知半徑為2.5 m，通信半徑為5 m，最大迭代次數(shù)為500。在該環(huán)境下，將ISMA 與PSO-H、IWOA、IGWO、SMA 進行對比，結(jié)果見表3。 從表3 可以看出，由ISMA 得出的WSN 覆蓋率分別比其他算法高出了0.117 5%、0.080 0%、0.062 5%和0.182 %。這說明ISMA 能有效提高WSN覆蓋率。

表3 各算法覆蓋率對比

圖7 給出了該環(huán)境下ISMA 與其他算法的WSN覆蓋率隨迭代次數(shù)的變化情況， 圖8 給出了該環(huán)境下ISMA 與其他算法的優(yōu)化節(jié)點分布。 從圖7 和圖8可以看出，ISMA 的WSN 覆蓋率高于其他算法，優(yōu)化節(jié)點分布也比其他算法更均勻。

圖7 WSN 覆蓋率隨迭代次數(shù)變化折線圖

圖8 各算法優(yōu)化節(jié)點分布

5 結(jié)束語

為了實現(xiàn)最大化無線傳感器網(wǎng)絡(luò)覆蓋， 我們首先引入了改進的黏菌算法， 并在原始黏菌算法的基礎(chǔ)上通過更改參數(shù)p 平衡了局部搜索能力和全局搜索能力；其次引入了混沌精英突變策略，通過擇優(yōu)選擇保留了最好的位置；最后通過仿真實驗得出了ISMA能有效提高WSN 覆蓋率， 使節(jié)點分布更均勻的結(jié)論。 ISMA 的運用不但減少了節(jié)點數(shù)量，而且降低了部署成本。