基于改進獅群算法的管道傳感器網絡覆蓋優化*

神顯豪，馬雪皎，牛少華，張烈平，謝曉蘭

(1.桂林理工大學廣西嵌入式技術與智能系統重點實驗室，廣西 桂林 514004；2.北京理工大學機電學院，北京 100081)

無線傳感器網絡[1](Wireless Sensor Network，WSN)是由大量的、低成本的傳感器節點與具有通信、感測和計算能力的傳感器節點部署在監控區域內部或外部的一種智能測控網絡。各種應用在WSN中的新領域由于傳感器節點成本的降低應運而生，并受到人們的廣泛關注，其中包括在工業、商業、人體、軍事、醫療保健等相關領域，以及面向管道檢測的領域也有新的研究。通過無線傳感器網絡的節點部署技術對節點進行有效的部署，可以提高網絡的覆蓋率。將該技術應用到管道中，能夠及時發現管道的缺陷，減少能源損失和降低維修成本。管道系統輸送大量的液體和氣體(例如石油、天然氣、自來水、污水和化工產品等)，它是最經濟的方式，與其他的運送方式(例如鐵路、高速公路、船舶)相比，優點顯而易見，具有成本低、運量大等優點，而且管道系統還是國民經濟發展的基礎設施。盡管它的優勢特別明顯，但隨著管道長度的不斷增加，對管道的檢測和管理增加了許多壓力，嚴重影響了管道安全和輸送效率。無線傳感器網絡以其低成本、可持續、不間斷、安全、高效的特點為管道系統提供監控和管理，極大地提高了管道系統的管理水平和經濟社會效益[2]。

一旦部署了WSN，頻繁更換傳感器節點中的電源可能不可行或不經濟。因此，在部署WSN的同時，最關鍵和最具挑戰性的任務之一是有效地部署傳感器節點，以使部署的網絡是長壽命的、能耗最低的。WSN的主要研究挑戰包括節點布局、覆蓋、拓撲、路由、生存期優化和能源效率。Elnaggar等人[3]使用了受自然啟發的技術，對專門用于石油管道監測的線性無線傳感器網絡進行節點布置和壽命優化。討論了在給定傳感器節點初始能量和消息緩沖限制的情況下，要部署的傳感器的最佳數量問題。作者使用了兩種進化算法來解決部署問題，即遺傳算法(GA)和蟻群優化(ACO)。Kaur等人[4]使用混合元啟發式技術為無線傳感器網絡設計節能協議。文獻[5]提出了延長穩定選舉協議(P-SEP)以在霧支持的WSN中的異構節點之間選舉CH，以增加網絡的壽命。文獻[6]利用模擬退火技術通過最大化WSN的網絡覆蓋和壽命作為目標函數來控制拓撲。Laouid等人[7]設計了一種方法，根據每個傳感器節點的跳數和剩余能量選擇最佳路線，以最大限度地延長網絡的壽命。文獻[8]提出地下管道檢測機器人傳感器網絡中傳感器節點定位算法，網絡由機器人攜帶的傳感器節點和中繼節點組成，用于信息感知和通信，通過考慮傳感器節點的動力學，測量傳感器節點的速度和地上中繼節點接收到的無線電信號的強度，確定傳感器節點的位置。

本文提出了一種基于改進獅群算法的管道傳感器網絡覆蓋優化算法，該算法通過每次迭代獲取所有傳感器中的最優節點，并以每次最優解的節點為中心進行收斂，獲取該范圍內的最優解，從而更好地收斂到全局最優。本文考慮到多個管道，并且從多個不同的方向通過傳感器節點將數據傳送到基站，解決基站傳輸數據成功率的問題。該算法能夠直接有效地應用于管理管道，并使用最少的節點數建立傳感器網絡，從而以安全、可靠的方式覆蓋整個區域，并將數據傳輸到基站。為了解決傳輸數據的有效性問題，本文設計了一種基于獅群算法的節點部署優化方法，該方法使用最少數量的傳感器節點，仍然可以覆蓋最大面積，數據還可以以最小延遲傳輸到基站。通過仿真實驗驗證改進獅群算法部署優化能有效地解決數據傳輸問題，不僅延長了傳感器網絡壽命，而且還適用于長距離管道相互交叉的傳感器節點部署問題。

1 管道部署模型

為了管道的安全并節省資源，需要建立一個傳感器網絡。設置傳感器網絡的主要目的是以某種方式沿著管道部署傳感器節點，從而可以最大化網絡壽命，將感應到的數據以最小延遲發送到最近的基站。場景設置在長度為L的管道，這些管道以縱橫交錯的方式放置，形成如圖1所示的結構。在每個管道的兩端均放置基站，傳感器節點S(S1，S2，S3，…，Sn)部署在管道上。由于傳感器節點在電池電量和范圍具有一定的限制，因此，將這些節點利用改進獅群算法放置在可以最大程度地延長網絡壽命和增加吞吐量，并可以減少端到端延遲的位置。由于管道通常是以直線鋪設，標準管內直徑為250 mm，而長度可以長達千米。本文針對直線鋪設管道部署做出的假設條件:管道長度為L，節點通訊半徑為R，網絡規模為N(普通節點總數)，其中普通節點具有相同的初始能量、通信和計算能力。

圖1 管道無線傳感器網絡部署模型

2 獅群算法分析及改進

2.1 獅群算法

獅群算法(Lion Swarm Optimization，LSO)的主要思想是[9]:從要優化的搜索空間的任意初始位置開始，將具有最佳適應性值的獅子作為獅子王，然后將一定比例的獅子選為狩獵獅子，它們合作狩獵。一旦發現更好的獵物，獅子王將會獲得獵物的位置。幼獅與雌獅一起學習狩獵或者在獅子王附近覓食。當它們性成熟后，幼獅將被趕出群居，成為游牧獅子。為了生存，游牧獅子試圖靠近它記憶中的最佳位置。因此，根據獅群的分工與合作，目標函數的最優值是由獅子不斷搜索行為數據得到的。在獅群算法中，幼獅的行為增強了算法的局部優化能力，雄獅的捕食行為為該算法的全局收斂奠定了基礎。

獅群算法的原理是:

假設在D維目標搜索空間中有N頭獅子形成一個組，并且成年獅子的數量nLeader滿足:

成年獅子的數量定義為:

式中:β是成年獅子所占比例因子。

在狩獵過程中，不同類型的獅子以不同的方式移動，而獅子王則在最佳食物區以較小的范圍移動，以確保自己的特權并根據式(3)更新其位置。

式中:pki為第i個獅子第k代的歷史最優，γ為正態分布N(0，1)產生的隨機數，gk為第k代群體的最優位置。

雌獅需要在狩獵過程中進行協作，并根據等式(4)調整它們的位置。

式中:αf為雌獅移動范圍擾動因子，pkc為從第k代雌獅群中隨機挑選的一個捕獵協作伙伴的歷史最佳位置，T為獅子群體中最大迭代次數，t為當前迭代次數，step為活動范圍內移動的最大步長，為獅子活動空間范圍內的最小值均值，為獅子活動空間范圍內的最大值均值。

幼獅根據方程式(7)調整位置。

式中:αc為幼獅移動范圍擾動因子，gkm為幼獅跟隨雌獅的第k代歷史最佳位置，q為均勻分布U[0，1]產生的均勻隨機值，ˉgk為第k頭幼獅被驅逐的位置。

2.2 改進獅群算法設計

獅群算法具有多種搜索方式和全局搜索的特點，但是獅群算法容易陷入早熟收斂。例如，在幼獅移動步長和雄獅捕食的移動步長中，由于它們的運行步長是固定值，會使算法過早地陷入局部優化，降低了算法的全局搜索能力，從而導致算法過早收斂。鑒于上述問題，從初始化、幼獅移動步長和雄獅捕食的移動步長三個方面進行獅群算法改進。

①初始化的改進

種群的初始位置對算法的收斂速度和精度有很大影響，甚至可能導致優化失敗。在初始化過程中，搜索空間的隨機分布會導致個體種群分布不均勻，多樣性差。混沌映射是由確定性方程得到的具有隨機性和遍歷性的隨機運動狀態。因此引入sin映射混沌序列來初始化獅群的位置，加快算法的收斂速度。

②幼獅移動步長的改進

在基本的獅群算法中，幼獅靠自己的記憶向獅王移動時，使用固定的移動步長，這會降低算法的局部搜索能力和搜索方式的多樣性，并使算法容易過早地陷入局部優化，因此，本文采用Logistic函數。Logistic函數是有界、連續、可導且嚴格單調，當x接近負無窮大時，y接近零；當x接近正無窮大時，y接近1；當x＝0時，y＝0.5。如式(11)所示。

幼獅靠自己的記憶向獅王移動時，隨著距離的減小逐漸縮短游走的長度，緩慢地向獅王移動。通過Logistic函數，可以將運行步長轉換為變量并映射到間隔(0，1)，使運行步長在(0，1)中減小，從而可以更準確地搜索最優解。改進幼獅移動步長如式(12)所示。

式中:Tmax為最大迭代次數，T為當前迭代次數。

③雄獅捕食的移動步長的改進

自然界中的許多鳥類會跟隨Levy飛行，特別是在大空間中搜索目標且搜索者有限的情況下，Levy飛行是最有效的搜索方式之一。在獅群算法的捕食行為中，固定的捕食步長會降低算法的搜索能力。捕食初期的大步長用于尋找目標，從而擴大了搜索范圍，避免算法陷入局部最優。捕食后期的小步長用于精確搜索，使在獅群中被驅趕出來的幼獅可以在小范圍內搜索全局最優解。改進獅群算法(improved Lion Swarm Optimization，iLSO)的雄獅捕食行為移動步長如式(13)所示，式中運算符?表示張量積。

式中:Xi(T)為第i代雄獅捕食在第t代中的位置，Xbest(T)為當前雄獅捕食的最佳位置，s為Leavy飛行的隨機步長，μ、ν符合正態分布，μ～N(0，σ2)，ν～N(0，1)。

雄獅捕食的移動步長是隨機的，并且沒有固定的大小和方向。在搜索迭代過程中，靠近局部最優解使得獅群算法容易跳出局部最優解，提高了最優解的質量，從而雄獅捕食行為增強了算法的搜索能力，奠定了算法全局收斂的基礎。

2.3 改進算法復雜度分析

本文仿真實驗針對相同的基準函數和WSN監測區域進行優化，為了簡便計算，改進算法以種群規模N和最大迭代次數T作為時間復雜度標準。根據iLSO改進節點部署，引入Logistic函數和Levy飛行進行部署優化，增加了算法的時間復雜度為O(T×N)，因此，iLSO的最高時間復雜度為O(T×N)。

3 WSN覆蓋優化

傳感器節點的數量被認為是獅子的數量，獅子包括獅子王和流浪者。基站被認為是所有其他獅子(傳感器節點)接近的獵物，管道的節點圍繞著基站，距離基站最近的一個節點被認為是與基站直接連接的領導節點。當節點開始向基站傳輸數據時，獅子王開始進行狩獵行為。

假設管道的長度為L。任意給定長度中使用的節點數可由式(16)計算。此過程需要以2R的距離部署傳感器節點，使網絡即使在傳感器節點出現故障的情況下仍然可以保持傳感器連通。

式中:R為每個節點的通訊范圍，MinNo_nodes為傳輸期間產生連接網絡所需的最小節點數。通過使用放置在管道中距離為2×R的備份節點來完成。則有式(17)表示:

用于備份通信的備份節點。如果發生反向流動，則節點可能會改變其角色。附近的節點(領導節點)發送其信息并從不同節點發送大多數已接收消息的信息，發送的傳感器的壽命取決于接收器附近節點的活力。同時，發送的節點受到支持空間很小的影響，無法訪問備用空間，消息可能會被丟棄，因此接收器附近的節點會消耗大量的能量，所以志愿者節點被放置在接收器節點的附近。無線傳感器網絡中傳感器節點定位優化的對應適應度函數可以由式(18)和式(19)表示。

式中:dist為節點到上一個節點的距離，delay為端到端的延遲，drop_ratio為丟包數與發送的包總數之比。以最小延遲和丟包率作為目標函數，把傳感器節點以最大步長放置在不同長度的輸油管道上進行部署優化。在兩種情況下執行優化功能:一種是正常模式，另一種是在忽略鄰居節點后的當前節點，兩次擬合函數的平均值用作決策因子。

本文基于獅群算法，利用Logistic函數和Levy飛行，提出了一種基于獅群的無線傳感器網絡覆蓋優化算法。該算法在管道上部署n個節點，通信范圍為R，每端都有一個基站BS，基站和傳感器節點位置將由所提出的算法決定。iLSO應用于傳感器網絡覆蓋優化的目標為求解網絡監測區域內傳感器節點定位的最大值；輸入為監測區域參數:管道長度L、傳感器節點數n、通訊范圍R等，以及iLSO參數:種群規模N、最大迭代次數T；輸出為目標函數F最優適應度值以及dist、delay、drop_ratio。iLSO求解無線傳感器網絡覆蓋優化的具體算法步驟如下:

Input:節點的數量n，通訊范圍R Output:dist、delay、drop_ratio 1.計算網絡中的節點數n＝L/(2R)2.初始化網絡3.P′nodes＝Pnodes 4.初始化基站的位置PBS 5.計算dist、delay、drop_ratio 6.計算F F＝α1 dist ＋α2×delay＋α3×drop_ratio 7.從BS發送一條hello信號，no_of_leader＝確認收到信號的數8.if(no_of_leader＞1) Pavg＝∑Pnodes n P′nodes＝PBS＋rand×(Pavg-Pnodes) else P′nodes i＝Pnodes i rand＞pri RAND其他{ pri＝0.1＋min 0.5，(Pi-Bestpi)Bestp■■■■■■■■ i＝1，2，…， P′nodes＝P′BS＋rand×(Pavg-Pnodes) P′BS＝PBS＋rand×pri×(PBS-Pnodes)9.將數據從節點傳輸到BS，并計算dist、delay、drop_ratio 10.計算F′ F′＝α1 dist ＋α2×delay＋α3×drop_ratio 11.if(F′＜F) PBS＝P′BS Pnodes＝P′nodes 12.if(｜F′＜F｜＜0.01) end else go to step 3

4 實驗仿真與結果分析

4.1 基準函數優化實驗

為了驗證改進獅群算法(iLSO)在無線傳感器網絡覆蓋優化的有效性，從文獻[10]中選擇了2014 CEC競賽的30套基準函數，基準函數如表1所示。本文通過MATLAB仿真，與六種啟發式算法進行比較，包括入侵性雜草優化算法(Invasive Weed Optimization，IWO)[11]、基于生物地理的優化算法(Biogeography Based Optimization，BBO)[12]、重力搜索算法(Gravitational Search Algorithm，GSA)[13]、狩獵搜索算法(Hunting Search，HuS)[14]、蝙蝠算法(Bat Algorithm，BA)[15]、水波優化算法(Water Wave Optimization，WWO)[16]。

表1 基準函數表

為了保證測試實驗的公平性，將IWO、BBO、GSA、HuS、BA、WWO和iLSO對每個基準函數均獨立運行50次，取最優適應度的標準方差進行比較。同時，每個算法設置相同的種群規模N＝50、最大迭代次數T＝50和測試維度D＝30，并且將功能評估的最大數量設置為停止條件。表2描述了通過響應面分析法(Response Surface Methodology，RSM)調整提出算法的參數[17]。

表2 比較算法的參數值

在單峰基準函數條件下，從表3中可以看出，iLSO在函數f1、f2和f3上相比于其他的算法提供了更好的性能，對于函數f1已經取得了理論的最優值，而對于函數f2、f3性能表現的不顯著，且相比其他對比算法也有較大程度的提高，更優的標準差值表明該算法具有更好的優化質量和魯棒性。

表3 單峰基準函數標準方差比較結果

在多峰基準函數條件下，由于存在大量的局部最優，因此很難找到較好的解決方法，并避免局部最優。從表4中可以看出，iLSO表現出顯著的性能，相比于其他幾個算法，提供了更好的結果。iLSO對函數f4的收斂精度略高于BA，但相比其他對比算法有較大的提升，較小的標準差值也表明該算法具有較好的穩定性。

表4 多峰基準函數標準方差比較結果

在混合基準函數條件下，將變量隨機分為一些子組件，然后將不同的基本函數用于不同的子組件，這會導致算法的性能顯著降低。從表5中可以看出，iLSO對函數f17-f22的結果比其他算法都要好，iLSO的總體性能在這些基準函數上與其他算法顯著不同，從圖2中可以看出，iLSO在迭代不到10次時已經實現了收斂，表明改進后的算法能夠有效提高算法混合基準函數的收斂速度。

圖2 混合基準函數優化收斂曲線

表5 混合基準函數標準方差比較結果

在合成基準函數條件下，從表6中可以看出，iLSO在大多數性能上較好，但在f24、f28和f29上，iLSO的性能較弱，從圖3中可以看出，iLSO在迭代不到20次時實現了收斂，表明改進后的方法能夠有效提高算法合成基準函數的收斂速度。iLSO提升合成優化性能，從而對函數f25和f30均取得了其理論最優值。總而言之，iLSO在單峰、多峰、混合和合成函數上與其他六種啟發式算法相比是最好的。

表6 合成基準函數標準方差比較結果

圖3 合成基準函數優化收斂曲線

綜上所述，通過在不同形態函數上的仿真優化結果，可以明顯看出，改進獅群算法收斂精度更高、收斂速度更快和魯棒性更好。

4.2 仿真結果與分析

將改進獅群算法與現有的不同算法進行了比較，本文通過MATLAB仿真，所考慮的參數已匯總在表7中，與蟻群算法(Ant Colony Optimization，ACO)[18]、遺傳算法(Genetic Algorithm，GA)[19]和貪婪算法(Greedy Algorithm)[20]進行端到端延遲、吞吐量(單位時間內成功地傳送數據的數量)和網絡壽命(節點能量損耗——在網絡中大部分節點不能提供信息時，此時將該區域的節點退出網絡)的比較，與改進正弦余弦算法(Enhanced Sine Cosine Algorithm，ESCA)[21]、混沌優化細菌覓食算法(COBFO)[22]進行網絡覆蓋率的比較，充分驗證改進獅群算法應用在無線傳感器網絡覆蓋優化的有效性。實驗中，設置iLSO的種群規模N＝30，最大迭代次數T＝50，每組實驗獨立運行50次，取第50次優化的節點情況進行對比結果展示。

表7 比較算法的參數值

圖4和圖5為iLSO節點部署和ESCA、COBFO節點部署的網絡覆蓋率比較。使用相同數量的傳感器節點，與文獻[21]、[22]的網絡覆蓋優化做比較，iLSO節點部署比ESCA、COBFO節點部署的網絡覆蓋效果要好，在相同網絡覆蓋率的情況下，管道的長度不同，則使用的傳感器節點的數量不同，但iLSO算法使用傳感器節點的數量最少。當管道長度為1 500 m時，iLSO覆蓋率與其他兩種算法的覆蓋率差值最大，管道超過1 500 m，覆蓋率的變化趨于穩定。

圖4 網絡覆蓋率(節點通訊范圍50 m)

圖5 網絡覆蓋率(節點通訊范圍100 m)

由于在ESCA節點部署優化和COBFO節點部署優化中，節點在管道中分布不均、節點冗余性和覆蓋面重復較大，而改進獅群算法使無線傳感器節點在管道監測區域中均勻分布，覆蓋度大的節點幾乎不產生節點冗余，并且覆蓋率平均能夠到99.08%，幾乎沒有覆蓋空洞。當節點通訊范圍為50 m時，通過改進獅群算法得到節點部署優化網絡覆蓋率提高了1.99%，當節點通訊范圍為100 m時，通過改進獅群算法得到節點部署優化網絡覆蓋率提高了1.42%，傳感器節點在管道監測區域中分布得更加均勻，重復覆蓋的區域會更少，節點的冗余性也會降低，以此達到改進獅群算法優化覆蓋的目的，并且該算法能夠以較少的節點有效覆蓋監控區域，從而節省節點置換成本并延長無線傳感器的監控時間。

圖6和圖7中顯示了iLSO與ACO、GA和貪婪算法之間端到端延遲的比較，從仿真結果可以明顯看出，所使用的iLSO優于貪婪算法，并且表現出略好于GA和ACO的性能。當傳感器節點的通信范圍增加時，端到端延遲正在減小，這是因為傳送數據分組所需的中間節點的數量減少了。貪婪方法的延遲隨著管道長度的增加而增加，而在使用其他三種元啟發式技術的情況下，這種趨勢并不一致。這種現象的一個可能原因是，當管道長度增加時，節點的數量也會增加。

圖6 端到端延遲(節點通訊范圍50 m)

圖7 端到端延遲(節點通訊范圍100 m)

圖8和圖9中顯示了iLSO與ACO、GA和貪婪算法之間吞吐量的比較。從仿真結果可以明顯看出，iLSO算法在吞吐量方面優于貪婪算法。此外，iLSO算法在吞吐量方面略好于其他兩種算法，即GA和ACO。在所提出的方法中，位置已根據丟包率和延遲進行了優化，這個因素是該算法吞吐量更好的原因。對于所有算法，隨著傳感器節點通信范圍的增加，吞吐量都會增加。雖然隨著管道長度的增加，吞吐量呈現上升趨勢，但是iLSO算法的吞吐量最大，當管道長度為1 500 m時，吞吐量趨于穩定。

圖8 吞吐量(節點通訊范圍50 m)

圖9 吞吐量(節點通訊范圍100 m)

圖10和圖11中顯示了iLSO與ACO、GA和貪婪算法之間網絡壽命的比較。從仿真結果可以明顯看出，在每種情況下，iLSO具有不同管道長度的網絡壽命要好于ACO、GA和貪婪算法。當管道長度為1 500 m時，iLSO網絡壽命與其他兩種算法的網絡壽命差值最大，管道超過1 500 m，網絡壽命的變化也在增大，不過變化的趨勢在減小。當管道長度為1 500 m時，其性能明顯優于其他三種算法，因此iLSO適用于較長的管道。

圖10 網絡壽命(節點通訊范圍50 m)

圖11 網絡壽命(節點通訊范圍100 m)

當增加傳感器節點的通信范圍時，對于所有算法，網絡壽命都會略有增加。盡管每個數據包消耗的能量與傳感器節點的通信范圍成正比，但是由于中間節點數量的減少，傳輸數據包的總能量需求減少。因此，歸一化網絡壽命在增加傳感器節點的通信范圍時顯示出改善。綜上所述，通過在不同性能上的比較，驗證了iLSO覆蓋優化的有效性及優越性。

5 結論

本文提出了一種改進算法，該算法通過改進獅群算法來建立相互交叉管道的傳感器網絡。將不同長度的管道用改進獅群算法與其他啟發式算法相比較，傳感器節點在采用改進獅群算法的管道上具有更好的網絡覆蓋、端與端之間的延遲、網絡壽命和吞吐量。從仿真結果可以看出，改進獅群算法在性能和傳感器網絡覆蓋優化的有效性上得到了更好的驗證，當管道長度為1 500 m時，其性能明顯優于ACO、GA和貪婪算法，因此該算法適合用于較長距離的、相互交叉的管道中傳感器網絡節點的部署。