基于改進(jìn)獅群算法的管道傳感器網(wǎng)絡(luò)覆蓋優(yōu)化*

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

(1.桂林理工大學(xué)廣西嵌入式技術(shù)與智能系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 514004；2.北京理工大學(xué)機(jī)電學(xué)院，北京 100081)

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

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

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

1 管道部署模型

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

圖1 管道無(wú)線傳感器網(wǎng)絡(luò)部署模型

2 獅群算法分析及改進(jìn)

2.1 獅群算法

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

獅群算法的原理是:

假設(shè)在D維目標(biāo)搜索空間中有N頭獅子形成一個(gè)組，并且成年獅子的數(shù)量nLeader滿足:

成年獅子的數(shù)量定義為:

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

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

式中:pki為第i個(gè)獅子第k代的歷史最優(yōu)，γ為正態(tài)分布N(0，1)產(chǎn)生的隨機(jī)數(shù)，gk為第k代群體的最優(yōu)位置。

雌獅需要在狩獵過(guò)程中進(jìn)行協(xié)作，并根據(jù)等式(4)調(diào)整它們的位置。

式中:αf為雌獅移動(dòng)范圍擾動(dòng)因子，pkc為從第k代雌獅群中隨機(jī)挑選的一個(gè)捕獵協(xié)作伙伴的歷史最佳位置，T為獅子群體中最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)，step為活動(dòng)范圍內(nèi)移動(dòng)的最大步長(zhǎng)，為獅子活動(dòng)空間范圍內(nèi)的最小值均值，為獅子活動(dòng)空間范圍內(nèi)的最大值均值。

幼獅根據(jù)方程式(7)調(diào)整位置。

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

2.2 改進(jìn)獅群算法設(shè)計(jì)

獅群算法具有多種搜索方式和全局搜索的特點(diǎn)，但是獅群算法容易陷入早熟收斂。例如，在幼獅移動(dòng)步長(zhǎng)和雄獅捕食的移動(dòng)步長(zhǎng)中，由于它們的運(yùn)行步長(zhǎng)是固定值，會(huì)使算法過(guò)早地陷入局部?jī)?yōu)化，降低了算法的全局搜索能力，從而導(dǎo)致算法過(guò)早收斂。鑒于上述問(wèn)題，從初始化、幼獅移動(dòng)步長(zhǎng)和雄獅捕食的移動(dòng)步長(zhǎng)三個(gè)方面進(jìn)行獅群算法改進(jìn)。

①初始化的改進(jìn)

種群的初始位置對(duì)算法的收斂速度和精度有很大影響，甚至可能導(dǎo)致優(yōu)化失敗。在初始化過(guò)程中，搜索空間的隨機(jī)分布會(huì)導(dǎo)致個(gè)體種群分布不均勻，多樣性差。混沌映射是由確定性方程得到的具有隨機(jī)性和遍歷性的隨機(jī)運(yùn)動(dòng)狀態(tài)。因此引入sin映射混沌序列來(lái)初始化獅群的位置，加快算法的收斂速度。

②幼獅移動(dòng)步長(zhǎng)的改進(jìn)

在基本的獅群算法中，幼獅靠自己的記憶向獅王移動(dòng)時(shí)，使用固定的移動(dòng)步長(zhǎng)，這會(huì)降低算法的局部搜索能力和搜索方式的多樣性，并使算法容易過(guò)早地陷入局部?jī)?yōu)化，因此，本文采用Logistic函數(shù)。Logistic函數(shù)是有界、連續(xù)、可導(dǎo)且嚴(yán)格單調(diào)，當(dāng)x接近負(fù)無(wú)窮大時(shí)，y接近零；當(dāng)x接近正無(wú)窮大時(shí)，y接近1；當(dāng)x＝0時(shí)，y＝0.5。如式(11)所示。

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

式中:Tmax為最大迭代次數(shù)，T為當(dāng)前迭代次數(shù)。

③雄獅捕食的移動(dòng)步長(zhǎng)的改進(jìn)

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

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

雄獅捕食的移動(dòng)步長(zhǎng)是隨機(jī)的，并且沒有固定的大小和方向。在搜索迭代過(guò)程中，靠近局部最優(yōu)解使得獅群算法容易跳出局部最優(yōu)解，提高了最優(yōu)解的質(zhì)量，從而雄獅捕食行為增強(qiáng)了算法的搜索能力，奠定了算法全局收斂的基礎(chǔ)。

2.3 改進(jìn)算法復(fù)雜度分析

本文仿真實(shí)驗(yàn)針對(duì)相同的基準(zhǔn)函數(shù)和WSN監(jiān)測(cè)區(qū)域進(jìn)行優(yōu)化，為了簡(jiǎn)便計(jì)算，改進(jìn)算法以種群規(guī)模N和最大迭代次數(shù)T作為時(shí)間復(fù)雜度標(biāo)準(zhǔn)。根據(jù)iLSO改進(jìn)節(jié)點(diǎn)部署，引入Logistic函數(shù)和Levy飛行進(jìn)行部署優(yōu)化，增加了算法的時(shí)間復(fù)雜度為O(T×N)，因此，iLSO的最高時(shí)間復(fù)雜度為O(T×N)。

3 WSN覆蓋優(yōu)化

傳感器節(jié)點(diǎn)的數(shù)量被認(rèn)為是獅子的數(shù)量，獅子包括獅子王和流浪者?；颈徽J(rèn)為是所有其他獅子(傳感器節(jié)點(diǎn))接近的獵物，管道的節(jié)點(diǎn)圍繞著基站，距離基站最近的一個(gè)節(jié)點(diǎn)被認(rèn)為是與基站直接連接的領(lǐng)導(dǎo)節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)開始向基站傳輸數(shù)據(jù)時(shí)，獅子王開始進(jìn)行狩獵行為。

假設(shè)管道的長(zhǎng)度為L(zhǎng)。任意給定長(zhǎng)度中使用的節(jié)點(diǎn)數(shù)可由式(16)計(jì)算。此過(guò)程需要以2R的距離部署傳感器節(jié)點(diǎn)，使網(wǎng)絡(luò)即使在傳感器節(jié)點(diǎn)出現(xiàn)故障的情況下仍然可以保持傳感器連通。

式中:R為每個(gè)節(jié)點(diǎn)的通訊范圍，MinNo_nodes為傳輸期間產(chǎn)生連接網(wǎng)絡(luò)所需的最小節(jié)點(diǎn)數(shù)。通過(guò)使用放置在管道中距離為2×R的備份節(jié)點(diǎn)來(lái)完成。則有式(17)表示:

用于備份通信的備份節(jié)點(diǎn)。如果發(fā)生反向流動(dòng)，則節(jié)點(diǎn)可能會(huì)改變其角色。附近的節(jié)點(diǎn)(領(lǐng)導(dǎo)節(jié)點(diǎn))發(fā)送其信息并從不同節(jié)點(diǎn)發(fā)送大多數(shù)已接收消息的信息，發(fā)送的傳感器的壽命取決于接收器附近節(jié)點(diǎn)的活力。同時(shí)，發(fā)送的節(jié)點(diǎn)受到支持空間很小的影響，無(wú)法訪問(wèn)備用空間，消息可能會(huì)被丟棄，因此接收器附近的節(jié)點(diǎn)會(huì)消耗大量的能量，所以志愿者節(jié)點(diǎn)被放置在接收器節(jié)點(diǎn)的附近。無(wú)線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)定位優(yōu)化的對(duì)應(yīng)適應(yīng)度函數(shù)可以由式(18)和式(19)表示。

式中:dist為節(jié)點(diǎn)到上一個(gè)節(jié)點(diǎn)的距離，delay為端到端的延遲，drop_ratio為丟包數(shù)與發(fā)送的包總數(shù)之比。以最小延遲和丟包率作為目標(biāo)函數(shù)，把傳感器節(jié)點(diǎn)以最大步長(zhǎng)放置在不同長(zhǎng)度的輸油管道上進(jìn)行部署優(yōu)化。在兩種情況下執(zhí)行優(yōu)化功能:一種是正常模式，另一種是在忽略鄰居節(jié)點(diǎn)后的當(dāng)前節(jié)點(diǎn)，兩次擬合函數(shù)的平均值用作決策因子。

本文基于獅群算法，利用Logistic函數(shù)和Levy飛行，提出了一種基于獅群的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法。該算法在管道上部署n個(gè)節(jié)點(diǎn)，通信范圍為R，每端都有一個(gè)基站BS，基站和傳感器節(jié)點(diǎn)位置將由所提出的算法決定。iLSO應(yīng)用于傳感器網(wǎng)絡(luò)覆蓋優(yōu)化的目標(biāo)為求解網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域內(nèi)傳感器節(jié)點(diǎn)定位的最大值；輸入為監(jiān)測(cè)區(qū)域參數(shù):管道長(zhǎng)度L、傳感器節(jié)點(diǎn)數(shù)n、通訊范圍R等，以及iLSO參數(shù):種群規(guī)模N、最大迭代次數(shù)T；輸出為目標(biāo)函數(shù)F最優(yōu)適應(yīng)度值以及dist、delay、drop_ratio。iLSO求解無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化的具體算法步驟如下:

Input:節(jié)點(diǎn)的數(shù)量n，通訊范圍R Output:dist、delay、drop_ratio 1.計(jì)算網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)n＝L/(2R)2.初始化網(wǎng)絡(luò)3.P′nodes＝Pnodes 4.初始化基站的位置PBS 5.計(jì)算dist、delay、drop_ratio 6.計(jì)算F F＝α1 dist ＋α2×delay＋α3×drop_ratio 7.從BS發(fā)送一條hello信號(hào)，no_of_leader＝確認(rèn)收到信號(hào)的數(shù)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.將數(shù)據(jù)從節(jié)點(diǎn)傳輸?shù)紹S，并計(jì)算dist、delay、drop_ratio 10.計(jì)算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 實(shí)驗(yàn)仿真與結(jié)果分析

4.1 基準(zhǔn)函數(shù)優(yōu)化實(shí)驗(yàn)

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

表1 基準(zhǔn)函數(shù)表

為了保證測(cè)試實(shí)驗(yàn)的公平性，將IWO、BBO、GSA、HuS、BA、WWO和iLSO對(duì)每個(gè)基準(zhǔn)函數(shù)均獨(dú)立運(yùn)行50次，取最優(yōu)適應(yīng)度的標(biāo)準(zhǔn)方差進(jìn)行比較。同時(shí)，每個(gè)算法設(shè)置相同的種群規(guī)模N＝50、最大迭代次數(shù)T＝50和測(cè)試維度D＝30，并且將功能評(píng)估的最大數(shù)量設(shè)置為停止條件。表2描述了通過(guò)響應(yīng)面分析法(Response Surface Methodology，RSM)調(diào)整提出算法的參數(shù)[17]。

表2 比較算法的參數(shù)值

在單峰基準(zhǔn)函數(shù)條件下，從表3中可以看出，iLSO在函數(shù)f1、f2和f3上相比于其他的算法提供了更好的性能，對(duì)于函數(shù)f1已經(jīng)取得了理論的最優(yōu)值，而對(duì)于函數(shù)f2、f3性能表現(xiàn)的不顯著，且相比其他對(duì)比算法也有較大程度的提高，更優(yōu)的標(biāo)準(zhǔn)差值表明該算法具有更好的優(yōu)化質(zhì)量和魯棒性。

表3 單峰基準(zhǔn)函數(shù)標(biāo)準(zhǔn)方差比較結(jié)果

在多峰基準(zhǔn)函數(shù)條件下，由于存在大量的局部最優(yōu)，因此很難找到較好的解決方法，并避免局部最優(yōu)。從表4中可以看出，iLSO表現(xiàn)出顯著的性能，相比于其他幾個(gè)算法，提供了更好的結(jié)果。iLSO對(duì)函數(shù)f4的收斂精度略高于BA，但相比其他對(duì)比算法有較大的提升，較小的標(biāo)準(zhǔn)差值也表明該算法具有較好的穩(wěn)定性。

表4 多峰基準(zhǔn)函數(shù)標(biāo)準(zhǔn)方差比較結(jié)果

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

圖2 混合基準(zhǔn)函數(shù)優(yōu)化收斂曲線

表5 混合基準(zhǔn)函數(shù)標(biāo)準(zhǔn)方差比較結(jié)果

在合成基準(zhǔn)函數(shù)條件下，從表6中可以看出，iLSO在大多數(shù)性能上較好，但在f24、f28和f29上，iLSO的性能較弱，從圖3中可以看出，iLSO在迭代不到20次時(shí)實(shí)現(xiàn)了收斂，表明改進(jìn)后的方法能夠有效提高算法合成基準(zhǔn)函數(shù)的收斂速度。iLSO提升合成優(yōu)化性能，從而對(duì)函數(shù)f25和f30均取得了其理論最優(yōu)值?？偠灾琲LSO在單峰、多峰、混合和合成函數(shù)上與其他六種啟發(fā)式算法相比是最好的。

表6 合成基準(zhǔn)函數(shù)標(biāo)準(zhǔn)方差比較結(jié)果

圖3 合成基準(zhǔn)函數(shù)優(yōu)化收斂曲線

綜上所述，通過(guò)在不同形態(tài)函數(shù)上的仿真優(yōu)化結(jié)果，可以明顯看出，改進(jìn)獅群算法收斂精度更高、收斂速度更快和魯棒性更好。

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

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

表7 比較算法的參數(shù)值

圖4和圖5為iLSO節(jié)點(diǎn)部署和ESCA、COBFO節(jié)點(diǎn)部署的網(wǎng)絡(luò)覆蓋率比較。使用相同數(shù)量的傳感器節(jié)點(diǎn)，與文獻(xiàn)[21]、[22]的網(wǎng)絡(luò)覆蓋優(yōu)化做比較，iLSO節(jié)點(diǎn)部署比ESCA、COBFO節(jié)點(diǎn)部署的網(wǎng)絡(luò)覆蓋效果要好，在相同網(wǎng)絡(luò)覆蓋率的情況下，管道的長(zhǎng)度不同，則使用的傳感器節(jié)點(diǎn)的數(shù)量不同，但iLSO算法使用傳感器節(jié)點(diǎn)的數(shù)量最少。當(dāng)管道長(zhǎng)度為1 500 m時(shí)，iLSO覆蓋率與其他兩種算法的覆蓋率差值最大，管道超過(guò)1 500 m，覆蓋率的變化趨于穩(wěn)定。

圖4 網(wǎng)絡(luò)覆蓋率(節(jié)點(diǎn)通訊范圍50 m)

圖5 網(wǎng)絡(luò)覆蓋率(節(jié)點(diǎn)通訊范圍100 m)

由于在ESCA節(jié)點(diǎn)部署優(yōu)化和COBFO節(jié)點(diǎn)部署優(yōu)化中，節(jié)點(diǎn)在管道中分布不均、節(jié)點(diǎn)冗余性和覆蓋面重復(fù)較大，而改進(jìn)獅群算法使無(wú)線傳感器節(jié)點(diǎn)在管道監(jiān)測(cè)區(qū)域中均勻分布，覆蓋度大的節(jié)點(diǎn)幾乎不產(chǎn)生節(jié)點(diǎn)冗余，并且覆蓋率平均能夠到99.08%，幾乎沒有覆蓋空洞。當(dāng)節(jié)點(diǎn)通訊范圍為50 m時(shí)，通過(guò)改進(jìn)獅群算法得到節(jié)點(diǎn)部署優(yōu)化網(wǎng)絡(luò)覆蓋率提高了1.99%，當(dāng)節(jié)點(diǎn)通訊范圍為100 m時(shí)，通過(guò)改進(jìn)獅群算法得到節(jié)點(diǎn)部署優(yōu)化網(wǎng)絡(luò)覆蓋率提高了1.42%，傳感器節(jié)點(diǎn)在管道監(jiān)測(cè)區(qū)域中分布得更加均勻，重復(fù)覆蓋的區(qū)域會(huì)更少，節(jié)點(diǎn)的冗余性也會(huì)降低，以此達(dá)到改進(jìn)獅群算法優(yōu)化覆蓋的目的，并且該算法能夠以較少的節(jié)點(diǎn)有效覆蓋監(jiān)控區(qū)域，從而節(jié)省節(jié)點(diǎn)置換成本并延長(zhǎng)無(wú)線傳感器的監(jiān)控時(shí)間。

圖6和圖7中顯示了iLSO與ACO、GA和貪婪算法之間端到端延遲的比較，從仿真結(jié)果可以明顯看出，所使用的iLSO優(yōu)于貪婪算法，并且表現(xiàn)出略好于GA和ACO的性能。當(dāng)傳感器節(jié)點(diǎn)的通信范圍增加時(shí)，端到端延遲正在減小，這是因?yàn)閭魉蛿?shù)據(jù)分組所需的中間節(jié)點(diǎn)的數(shù)量減少了。貪婪方法的延遲隨著管道長(zhǎng)度的增加而增加，而在使用其他三種元啟發(fā)式技術(shù)的情況下，這種趨勢(shì)并不一致。這種現(xiàn)象的一個(gè)可能原因是，當(dāng)管道長(zhǎng)度增加時(shí)，節(jié)點(diǎn)的數(shù)量也會(huì)增加。

圖6 端到端延遲(節(jié)點(diǎn)通訊范圍50 m)

圖7 端到端延遲(節(jié)點(diǎn)通訊范圍100 m)

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

圖8 吞吐量(節(jié)點(diǎn)通訊范圍50 m)

圖9 吞吐量(節(jié)點(diǎn)通訊范圍100 m)

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

圖10 網(wǎng)絡(luò)壽命(節(jié)點(diǎn)通訊范圍50 m)

圖11 網(wǎng)絡(luò)壽命(節(jié)點(diǎn)通訊范圍100 m)

當(dāng)增加傳感器節(jié)點(diǎn)的通信范圍時(shí)，對(duì)于所有算法，網(wǎng)絡(luò)壽命都會(huì)略有增加。盡管每個(gè)數(shù)據(jù)包消耗的能量與傳感器節(jié)點(diǎn)的通信范圍成正比，但是由于中間節(jié)點(diǎn)數(shù)量的減少，傳輸數(shù)據(jù)包的總能量需求減少。因此，歸一化網(wǎng)絡(luò)壽命在增加傳感器節(jié)點(diǎn)的通信范圍時(shí)顯示出改善。綜上所述，通過(guò)在不同性能上的比較，驗(yàn)證了iLSO覆蓋優(yōu)化的有效性及優(yōu)越性。

5 結(jié)論

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