基于蝙蝠優(yōu)化器的三維無線傳感器網(wǎng)絡(luò)節(jié)能覆蓋增強策略*

莊海燕

(鐵道警察學院圖像與網(wǎng)絡(luò)偵查系，河南 鄭州450002)

眾所周知，在物聯(lián)網(wǎng)(IoT)中，計算機能夠在沒有人類交互的情況下，自動訪問對象和環(huán)境的相關(guān)數(shù)據(jù)信息。其中，無線傳感器網(wǎng)絡(luò)(WSNs)則是實現(xiàn)物聯(lián)網(wǎng)傳感器節(jié)點感知的關(guān)鍵推動因素，為物聯(lián)網(wǎng)帶來更加豐富的感知和驅(qū)動能力[1]。作為物聯(lián)網(wǎng)的關(guān)鍵場景之一，無線傳感器網(wǎng)絡(luò)會根據(jù)目標的有效覆蓋效果執(zhí)行任務(wù)[2]。目前，無線傳感器網(wǎng)絡(luò)在戰(zhàn)術(shù)監(jiān)視、地震監(jiān)測、輔助導航、污染監(jiān)測等領(lǐng)域得到廣泛應(yīng)用，并因其在物聯(lián)網(wǎng)中的關(guān)鍵作用而逐漸成為物聯(lián)網(wǎng)研究的熱點之一[3]。

對目標的有效監(jiān)測是三維無線傳感器網(wǎng)絡(luò)任務(wù)執(zhí)行的基礎(chǔ)[4]。其中，確保目標區(qū)域能夠被傳感器節(jié)點有效覆蓋是提高三維無線傳感器網(wǎng)絡(luò)監(jiān)控質(zhì)量和網(wǎng)絡(luò)可靠性的關(guān)鍵[5－6]。但是三維無線傳感器網(wǎng)絡(luò)布局受環(huán)境影響較大，尤其在惡劣、偏遠的地區(qū)，由于人為干預(yù)較少，使得網(wǎng)絡(luò)無法對傳感器節(jié)點的電池進行充電或更換，從而降低三維無線傳感器網(wǎng)絡(luò)壽命，導致無法持續(xù)、可靠的完成目標任務(wù)[7－8]。因此研究如何提高三維無線傳感器網(wǎng)絡(luò)節(jié)點的有效能耗，可以有效延長傳感器網(wǎng)絡(luò)壽命，從而提高三維無線傳感器網(wǎng)絡(luò)監(jiān)控覆蓋率。通常，在三維無線傳感器網(wǎng)絡(luò)的重新部署中，會產(chǎn)生大量的傳感器節(jié)點移動和信號傳輸出，使得三維無線傳感器網(wǎng)絡(luò)產(chǎn)生大量的能量消耗，導致網(wǎng)絡(luò)監(jiān)控質(zhì)量和網(wǎng)絡(luò)可靠性不佳[9]。因此如何減少三維無線傳感器網(wǎng)絡(luò)的移動總能量消耗和平衡節(jié)點剩余能量是當前三維無線傳感器網(wǎng)絡(luò)重新部署策略中亟待解決的關(guān)鍵問題[10]。

針對上述問題，國內(nèi)外眾多專家學者開展了大量研究。文獻[11]提出了一種基于協(xié)同進化粒子群算法的無線傳感器網(wǎng)絡(luò)節(jié)能優(yōu)化覆蓋算法，通過優(yōu)化無線傳感器網(wǎng)絡(luò)覆蓋率、剩余能量和冗余程度，構(gòu)建粒子群優(yōu)化模型，運用遺傳算法交叉變異算子提高算法尋優(yōu)能力，延長了網(wǎng)絡(luò)生命周期，并獲得良好的覆蓋率。文獻[12]提出了一種基于遺傳PSO的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化算法，通過運用具有自適應(yīng)交叉變異因子的遺傳算法搜索解空間，增強PSO粒子群全局搜索能力和搜索范圍，強化算法尋優(yōu)能力，從而提高節(jié)點的覆蓋率。但上述研究成果在無線傳感器網(wǎng)絡(luò)隨機部署移動節(jié)點時，存在節(jié)點分布不均勻的問題，從而導致網(wǎng)絡(luò)覆蓋率較低。文獻[13]提出一種基于節(jié)點調(diào)度和路由協(xié)議優(yōu)化算法，通過選擇冗余睡眠節(jié)點來替換死節(jié)點延長網(wǎng)絡(luò)壽命，并通過優(yōu)化匯聚節(jié)點周圍傳感器的數(shù)據(jù)通信方式，構(gòu)建不均勻的群集以平衡能量負載，從而減少冗余傳感器節(jié)點的數(shù)量，并提高數(shù)據(jù)傳輸?shù)哪芰啃省Ｎ墨I[14]提出了一種基于博弈論的節(jié)點功率控制算法，運用剩余能量、發(fā)射功率等要素構(gòu)建功能函數(shù)，并將剩余能量作為下一跳節(jié)點，運用功率博弈算法不斷調(diào)整修正，從而控制節(jié)點傳輸功率，降低網(wǎng)絡(luò)節(jié)點傳輸能耗。文獻[15]提出了一種改進的Bkd-Tree啟發(fā)式節(jié)能群集算法，通過集群策略處理與數(shù)據(jù)流量相關(guān)的節(jié)能問題，可在最小化能量、延遲和抖動的情況下提高網(wǎng)絡(luò)節(jié)點吞吐量，從而有效降低能耗10%以上，使無線傳感器網(wǎng)絡(luò)具有更佳的性能。但上述研究中，無線傳感器網(wǎng)絡(luò)覆蓋存在收斂速度慢、易早熟等問題，且網(wǎng)絡(luò)覆蓋率較低、部署成本高。

針對上述研究存在的相關(guān)問題，本文提出了一種基于蝙蝠優(yōu)化器的三維無線傳感器網(wǎng)絡(luò)節(jié)能覆蓋增強策略。首先，通過截角八面體將覆蓋增強和能量優(yōu)化問題轉(zhuǎn)化為將節(jié)點移動到截角八面體的任務(wù)分配問題；運用蝙蝠優(yōu)化器實現(xiàn)無線傳感器網(wǎng)絡(luò)的最小化總能耗和平衡剩余能量的多目標優(yōu)化。最后，通仿真對比分析驗證所提策略的有效性與可靠性。

1 問題闡述

通常，三維監(jiān)控區(qū)域由包含K個網(wǎng)格的三維空間表示。其中，每個傳感器在三維空間中都有一個球形范圍，球心代表傳感器節(jié)點，半徑代表節(jié)點感應(yīng)范圍。對于具有K個網(wǎng)格的三維空間Ω，當滿足條件d i，j≤K時，S i可以檢測到G j。其中，S i是第i個具有坐標(x si，y s i，z s i)的傳感器節(jié)點，G j是坐標為(x g j，y gj，z gj)的第j個網(wǎng)格的質(zhì)心，R為傳感器節(jié)點的感知半徑，d i，j為S i與G j之間的歐式距離。

由于三維無線傳感器網(wǎng)絡(luò)覆蓋控制的主要研究內(nèi)容是利用最少的節(jié)點來增強網(wǎng)絡(luò)覆蓋效果，因此假設(shè)傳感器節(jié)點能夠獲取其位置信息，所有傳感器節(jié)點具有相同的感知半徑，且暫時忽略由于環(huán)境的復雜性導致的聲通道路徑損耗、端間延遲和數(shù)據(jù)包丟失率。如果最終達到完全覆蓋效果，則將該策略定義為最有效的覆蓋增強策略，如圖1所示為截角八面體的切割過程。

圖1 截角八面體切割過程

如圖2所示，為截角八面體的堆疊間隔圖，其中的箭頭表示傳感器節(jié)點的感知半徑，即為截角八面體的外接球體半徑。根據(jù)圖1所示切割過程的幾何關(guān)系，其堆疊間隔是長度的兩倍。

圖2 截角八面體的堆疊間隔

因此，可根據(jù)位置關(guān)系將用于無縫堆疊Ω的所有截角八面體分為兩類。其中，假設(shè)Ω的長、寬、高分別為L1、L2和L3，并令δ＝4 5R/5為堆疊間隔，質(zhì)心分別為(0，0，0)和(2 5R/5，2 5R/5，2 5R/5)，可將第一類截角八面體的質(zhì)心坐標表示為式(1)所示:

因此，無縫地堆疊Ω所需的最小截角八面體數(shù)可以通過式(3)計算:

其堆疊效果如圖3所示，使用外球面半徑為R的截角八面體無縫地堆疊Ω后，將節(jié)點移動到截角八面體的質(zhì)心，可最大程度地提高最終覆蓋率，并使節(jié)點數(shù)量最小化。但是要提高節(jié)點覆蓋率仍需要解決以下三方面問題。

圖3 堆疊效應(yīng)

①移動能耗模型

剩余能量E i，j的數(shù)學表達如式(4)所示:

式中:E o i為S i的初始能量；e為S i移動1ft時的能量消耗；d i，j為S i與G j之間的歐幾里德距離。其中，節(jié)點剩余能量的均勻性如式(5)所示:

式中:N為節(jié)點數(shù)；E i，j為移動到G j后S i的剩余能量。通常，無線傳感器網(wǎng)絡(luò)的生命周期由最先衰亡的節(jié)點生命周期表示，因此重新部署過程中，能量優(yōu)化的關(guān)鍵是降低網(wǎng)絡(luò)總移動能耗，平衡節(jié)點的剩余能量。

②能量消耗優(yōu)化

將重新部署問題轉(zhuǎn)換為任務(wù)分配問題，當其滿足式(3)中所述條件時，該任務(wù)將N個節(jié)點移到N個截斷的八面體質(zhì)心。

如圖4所示，為任務(wù)分配的二分圖模型。其中，d i，j為二分圖邊緣的權(quán)重，其距離矩陣如式(6)所示:

圖4 任務(wù)分配問題的二分圖模型

問題的目標函數(shù)如式(7)所示:

式中:f1和f2是考慮了總移動距離和分移動距離的均勻性適應(yīng)度函數(shù)；w1和w2分別是適應(yīng)度函數(shù)f1和f2的權(quán)重。其中，f1和f2的數(shù)學表達如式(8)所示:

其約束條件定義如式(9)所示:

2 基于蝙蝠優(yōu)化器的節(jié)能覆蓋算法

2.1 蝙蝠優(yōu)化器

自然界中，蝙蝠會根據(jù)自身的口味、饑餓程度、獵物的血量以及狩獵的風險分析目標。然后，根據(jù)興趣程度選擇目標獵物并參加捕食競爭，這種現(xiàn)象被稱為蝙蝠的利己行為。

受蝙蝠利己行為和利他行為的啟發(fā)，本文提出了一種蝙蝠優(yōu)化器(VBO)，以最大化所有蝙蝠的收益。最終，將VBO用于優(yōu)化重新部署期間節(jié)點的能耗。其中，VBO的構(gòu)建步驟如下:

步驟1:找到每個蝙蝠的最佳獵物

首先，初始化各蝙蝠對獵物的興趣值、風險值和蝙蝠的基因值。將第i個蝙蝠和第j個獵物視為b i和p j，并將b i在p j中的興趣值、b i的基因值以及在第t次迭代中的狩獵風險值視為

計算每個蝙蝠捕獲每個獵物的收益，b i在第t次迭代中捕獲p j時的收益計算如式(10)所示:

將第t次迭代中b i的最佳獵物定義如式(11)所示:

步驟2:捕食比賽

在所有蝙蝠都擁有不再沖突的最佳獵物前，掠奪性競爭不會消失，所有蝙蝠的利益也無法最大化。在發(fā)生捕食沖突的情況下，在第t次迭代中被多個蝙蝠搶劫的獵物表示為中搶劫獵物所涉及的蝙蝠表示為集合然后遍歷中的所有獵物和相應(yīng)的蝙蝠，更新興趣矩陣并返回步驟1。

步驟3:回送

至此，整個蝙蝠種群的利益已實現(xiàn)最大化，蝙蝠開始吸收血液。定義每個蝙蝠吸收的血液量如式(13)所示:

式中:τ1和τ2分別是衡量饑餓差異和b i與b j間遺傳相似程度的閾值。若多個蝙蝠滿足回送條件，那么b j的適應(yīng)性值最大，則可以將b j定義為b i的最佳輸血目標，其適合度值如式(14)所示:

式中:w1和w2分別是饑餓差異的權(quán)重以及b i和b j之間的遺傳相似程度。一旦沒有蝙蝠需要輸血，回送過程立即結(jié)束，此時各蝙蝠抽取的血量可得到有效平衡。

2.2 使用VBO優(yōu)化節(jié)點的能耗

本文將節(jié)點移動到截角八面體質(zhì)心的任務(wù)分配問題視為蝙蝠的狩獵問題，并用VBO解決多目標優(yōu)化，該問題可最大程度地減少總能耗，并平衡節(jié)點的剩余能量，其過程如下:

步驟1:找到每個傳感器節(jié)點的最佳目標

鑒于VBO步驟2用于最大化整個蝙蝠種群的利益與重新部署過程中傳感器總能耗的最小化相反。因此，從傳感器節(jié)點到截角八面體的相對距離被認為是蝙蝠捕獵時的最優(yōu)距離。為確定傳感器節(jié)點的最佳移動目標，可以通過式(15)確定第t次迭代中S i的最佳移動目標。

移動任務(wù)矩陣的數(shù)學表達如式(11)所示:

步驟2:競爭

當節(jié)點選擇最佳移動目標時，等效于蝙蝠狩獵的相互沖突，節(jié)點目標的競爭過程與VBO的步驟2相似。在發(fā)生沖突的情況下，將沖突的目標視為感興趣目標，將沖突的傳感器視為活動的傳感器，表示為集合然后遍歷所有感興趣的目標和相應(yīng)的傳感器，以更新利益矩陣并返回步驟1。

步驟3:交換移動任務(wù)

假設(shè)所有傳感器節(jié)點都按照步驟2之后的移動任務(wù)立即移動，則每個傳感器節(jié)點的移動距離將存在顯著差異，等效于掠奪性競爭結(jié)束后每個蝙蝠吸收的血液量不同，將導致某些傳感器節(jié)點的移動難以實現(xiàn)。

競爭后，所有傳感器節(jié)點開始尋找其他節(jié)點交換任務(wù)，并根據(jù)任務(wù)交換定理交換節(jié)點S i和S m的移動任務(wù)。

任務(wù)交換條件:對于節(jié)點S i及其移動目標G i，以及節(jié)點S m及其移動目標G n，任務(wù)交換條件如式(18)所示:

等效于判斷蝙蝠間的遺傳相似度和饑餓度的差異是否滿足式(13)中所述的回送條件。

任務(wù)交換定理:如果節(jié)點S i和S m滿足任務(wù)交換條件，則可通過任務(wù)交換平衡它們的移動距離，其數(shù)學表達如式(19)所示:

任務(wù)交換定理:根據(jù)任務(wù)交換定理，如果有K個滿足任務(wù)交換條件的節(jié)點，即可得到K個方案。如果S m的適應(yīng)性值最大，則將S m定義為S i的最佳可交換節(jié)點，并通過式(19)交換S i和S m的任務(wù)。節(jié)點S m的適應(yīng)度值如式(20)所示:

式中:μ1和μ2分別是交換移動任務(wù)后S i和S m移動距離之和和移動距離之差的權(quán)重。當沒有傳感器節(jié)點滿足任務(wù)交換定理時，即認為交換任務(wù)過程結(jié)束。

3 實驗結(jié)果與分析

3.1 參數(shù)設(shè)置

為了驗證本文算法的性能，在相同實驗條件下將本文算法與三維虛擬力算法(3DVFA)、虛擬力導向粒子群優(yōu)化算法(VFPSO)、匈牙利算法(HA)進行對比試驗。其中，VBO的主要參數(shù)如表1所示。

表1 VBO的仿真參數(shù)

3.2 仿真比較

如圖5所示為VBO設(shè)置的傳感器節(jié)點的初始位置。如圖6所示為四種算法的傳感器節(jié)點的最終位置和最終覆蓋效果對比圖。由圖6可知，VBO和HA在最終覆蓋效果和傳感器節(jié)點的移動距離方面優(yōu)于3DVFA和VFPSO算法。

圖5 四種算法節(jié)點的初始位置

圖6 比較四種算法的移動和最終覆蓋效果

圖7 所示為四種算法的運動軌跡，由圖7可知，VBO和HA的移動軌跡比3DVFA和VFPSO短，且HA算法中移動距離較長的節(jié)點移動任務(wù)已在VBO中進行了優(yōu)化。

圖7 比較四種算法的運動軌跡的三視圖

如圖8所示，為四種算法的覆蓋率比較結(jié)果。由圖8(a)可知，HA和VBO的最終覆蓋率均達到100%，而VFPSO和3DVFA僅達到96.42%和98.07%。假設(shè)四種算法的最終覆蓋范圍不同，因此圖8(b)中比較了四種算法都達到95%覆蓋率時的總能耗。由圖可知，3DVFA和VFPSO的總能耗分別為9.1123×104J和5.5642×104J，比VBO算法少253.86%和116.08%。但是當達到完全覆蓋范圍時，VBO消耗了4.1231×104J的能量，比HA低6.76%，犧牲了將總能耗降至最低的性能。由此可知，在剩余能量的均勻性和最大能耗節(jié)點能耗方面，VBO的表現(xiàn)明顯優(yōu)于其他算法。

圖8 四種算法的覆蓋率比較

如圖9所示，為四種算法每個節(jié)點的能耗。由圖可知，在同時考慮總能耗和節(jié)點能耗均勻性的情況下VBO表現(xiàn)性能最佳，3DFVA表現(xiàn)最差，VFPSO略優(yōu)于3DVFA，HA明顯優(yōu)于3DVFA和VFPSO。與HA相比，VBO最大能耗節(jié)點的能耗和均勻性都得到了有效降低，這是由于在步驟3中交換了長短移動距離節(jié)點任務(wù)，而3DVFA和VFPSO僅將最終覆蓋范圍作為優(yōu)化的目標，忽略了能耗的優(yōu)化，從而導致了性能差異。

圖9 四種算法每個節(jié)點的能耗比較

如圖10所示，為四種最大能量消耗節(jié)點的能量消耗和剩余能量的均勻性比較結(jié)果。圖10(a)為四種算法的最大能耗節(jié)點的能耗比較結(jié)果，由圖可知，四種算法的最大能耗節(jié)點在運動20、24、32和51輪后達到最佳位置，其能耗分別為340.67 J，405.59 J，545.40 J，以及891.84 J，表明在該性能指標上，VBO的效果均優(yōu)于其他三種算法，分別為61.80%、37.54%和16.01%。如圖10(b)所示，3DVFA，HA，VFPSO和VBO運動后的剩余能量均勻度為173.28 J，107.99 J，81.42 J和69.43 J，表明3DVFA，HA和VFPSO的性能表現(xiàn)分別比VBO低59.93%、35.71%和14.72%。

圖10 最大能量消耗節(jié)點的能量消耗和剩余能量均勻性比較結(jié)果

為評估VBO的性能，在傳感器節(jié)點的不同初始位置使用2.5 GHz頻率和8 GB內(nèi)存的計算機進行多次獨立仿真，以提高相同條件下實驗結(jié)果的可靠性。如圖11所示為3DVFA、VFPSO、HA和VBO在200個獨立實驗中最終覆蓋范圍的性能比較結(jié)果。由圖可知，3DVFA的性能最差，其上下浮動約為95%，VFPSO的最終覆蓋率平均值約為97.5%，略高于3DVFA。而HA和VBO的性能相同，且每個實驗的最終覆蓋率均可達到100%。

圖11 200個獨立實驗下四種算法的最終覆蓋率

如圖12所示，為通過200個獨立實驗比較下的四種算法的能耗對比結(jié)果。其中，圖12(a)為通過200個實驗完成四種算法移動任務(wù)后的總能量消耗對比。由圖可知，其中3DVFA和VFPSO算法分別在9.5×104J和8.5×104J附近波動，而VBO的平均值接近6.8×104J，比HA略低，但明顯優(yōu)于3DVFA和VFPSO算法結(jié)果。圖12(b)和圖12(c)分別為通過200個獨立實驗顯示的四種算法的最大能耗節(jié)點能耗和剩余能量均勻性性能比較結(jié)果，由圖可知VBO的性能明顯優(yōu)于其他三種算法。

圖12 200個獨立實驗比較四種算法的能耗

將200次實驗下四種算法的性能差異平均化，得到表2與圖13中所示結(jié)果。由表2和圖13可知，與其他算法相比，VBO策略可將節(jié)點的剩余能量的平衡效果分別提高32.03%、43.44%和30.53%，最大能耗節(jié)點能耗降低了16.06%、39.78%和29.55%。同時，與3DVFA和VFPSO相比，VBO算法可將節(jié)點的總能耗降低30.04%和22.79%。此外，在最終覆蓋率和時間消耗方面，所提VBO算法也具有良好表現(xiàn)。由此，經(jīng)上述對比分析論證可知，所提VBO算法具有良好的可靠性與準確性。

表2 200次實驗下平均結(jié)果的性能比較

圖13 200次實驗的平均結(jié)果的性能比較

4 結(jié)論

針對復雜和惡劣環(huán)境下，三維無線傳感器網(wǎng)絡(luò)傳感器節(jié)點電池充電和恢復受阻的問題，提出了一種基于蝙蝠優(yōu)化器的三維無線傳感器網(wǎng)絡(luò)節(jié)能覆蓋增強策略，并通過仿真對比實驗得出以下結(jié)論:①提出了一種基于蝙蝠優(yōu)化器的能量優(yōu)化算法，將網(wǎng)絡(luò)節(jié)點覆蓋增強和能量優(yōu)化的問題轉(zhuǎn)化為將節(jié)點移動到截角八面體形心的任務(wù)分配問題，簡化了計算方式，提高了計算精度。②與傳統(tǒng)的3DVFA、VFPSO、HA策略相比，所提基于VBO的策略能使節(jié)點剩余能量的均勻性分別提高30.53%、43.44%和32.03%，且在總能量消耗、最終覆蓋率和時間消耗等方面均優(yōu)于對比策略，表現(xiàn)出優(yōu)良的可靠性與準確性。③本文研究尚缺乏對傳感器節(jié)點相同感知半徑約束的考慮，因此在后續(xù)研究中，將針對傳感器節(jié)點相同感知半徑約束開展進一步研究。