基于改進(jìn)黏菌算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋

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

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

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

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

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

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

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

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

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

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

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

2 黏菌算法基本原理

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

2.1 接近食物

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

2.2 包裹食物

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

2.3 獲取食物

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

3 改進(jìn)黏菌算法

3.1 參數(shù)p 的改進(jìn)

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

3.2 混沌精英突變策略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 與原始SMA 對(duì)比

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

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

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

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

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

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

表2 SMA 與ISMA 的覆蓋率對(duì)比

從表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é)點(diǎn)分布比SMA 的均勻。

4.2 與SMA 及其他算法的對(duì)比

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

表3 各算法覆蓋率對(duì)比

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

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

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

5 結(jié)束語(yǔ)

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