李琦, 韋道知, 王希,3, 謝家豪

(1. 空軍工程大學(xué)防空反導(dǎo)學(xué)院, 710043, 西安; 2. 中國人民解放軍第93605部隊, 102100, 北京;3. 西安衛(wèi)星測控中心, 710043, 西安)

無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)是通過無線通信建立網(wǎng)絡(luò)連接,將大量目標(biāo)感知傳感器設(shè)備分布式地部署在目標(biāo)監(jiān)測區(qū)域內(nèi)形成的網(wǎng)絡(luò)。因其具有良好的動態(tài)性、可擴展性和靈活性,常被應(yīng)用在戰(zhàn)場偵察、災(zāi)后搜救、跟蹤定位等目標(biāo)監(jiān)測任務(wù)中。隨著高技術(shù)信息化的發(fā)展,其在交通控制、智能家居、智慧農(nóng)業(yè)等領(lǐng)域也發(fā)揮著重要作用[1-2]。然而,在目標(biāo)監(jiān)測任務(wù)中,如果WSNs網(wǎng)絡(luò)對各個傳感器設(shè)備以及整個系統(tǒng)管理不當(dāng),就會出現(xiàn)目標(biāo)分配冗雜、能源消耗多、資源浪費等問題。面對日益復(fù)雜的目標(biāo)屬性和探測環(huán)境,如何利用無線傳感器網(wǎng)絡(luò)中的有限資源,盡可能高效、精確、快速地進行目標(biāo)探測資源優(yōu)化調(diào)度,已成為重要的研究方向[3-4]。

目標(biāo)探測過程中,無線傳感器網(wǎng)絡(luò)資源調(diào)度問題的本質(zhì)是在綜合考慮傳感器設(shè)備自身性能、相互關(guān)聯(lián)、預(yù)期目的等多約束條件下,基于某種原則建立模型并求解最優(yōu)調(diào)度方案的多目標(biāo)優(yōu)化問題[5]。當(dāng)前,國內(nèi)外學(xué)者圍繞此問題開展了廣泛研究。文獻(xiàn) [6-7]提出了基于信息論的算法,并采用信息熵來評價調(diào)度的性能。文獻(xiàn) [8]提出了線性規(guī)劃方法,將調(diào)度建模成由跟蹤精度和匹配傳感器資源矩陣組成的優(yōu)化問題。然而,在不考慮目標(biāo)跟蹤精度的情況下,該方法的檢測性能較差。為提高傳感器資源的跟蹤精度,文獻(xiàn) [9]提出了一種基于后驗克拉美-羅下界和攔截概率因子的傳感器網(wǎng)絡(luò)調(diào)度方法,將傳感器資源的攔截概率控制在閾值域內(nèi),但由于模型中的目標(biāo)函數(shù)是非凸的,直接采用梯度下降法不可行。文獻(xiàn) [10]首先提出了綜合考慮目標(biāo)損失風(fēng)險和傳感器資源輻射風(fēng)險的風(fēng)險評估模型,然后設(shè)計了與該模型相關(guān)的傳感器網(wǎng)絡(luò)調(diào)度方案,但由于目標(biāo)損失風(fēng)險與傳感器資源輻射風(fēng)險的比值是固定的,該方法在目標(biāo)損失風(fēng)險與傳感器資源輻射風(fēng)險比值變化時性能下降明顯。文獻(xiàn) [11]采用隨機分配傳感器對目標(biāo)進行檢測和跟蹤的方法,解決了低信噪比下的多目標(biāo)跟蹤問題。文獻(xiàn) [12]把動態(tài)聯(lián)盟理論引入到無線傳感器網(wǎng)絡(luò)管理當(dāng)中,根據(jù)不同時刻的環(huán)境態(tài)勢組建相應(yīng)時刻的最優(yōu)聯(lián)盟,由該聯(lián)盟完成對目標(biāo)的探測。針對WSNs資源優(yōu)化調(diào)度問題,雖然上述文獻(xiàn)均提出了一些解決方案,但在動態(tài)復(fù)雜環(huán)境下,由于對資源優(yōu)化調(diào)度模型的構(gòu)建要素考慮不全面,過多注重某一單方面性能約束指標(biāo)的影響,缺少任務(wù)效能整體收益考慮,且同時對約束指標(biāo)的定量、權(quán)重考慮不清,因而導(dǎo)致調(diào)度模型缺乏說服力。此外,在實際應(yīng)用中,由于算法本身的隨機特征,存在控制參數(shù)設(shè)置過多、計算復(fù)雜、求解效率不高、容易陷入局部最優(yōu)等缺陷。

針對以上問題,本文提出了一種基于任務(wù)效能收益最優(yōu)的WSNs網(wǎng)絡(luò)資源優(yōu)化調(diào)度策略,建立了以WSNs網(wǎng)絡(luò)效能收益最大為目標(biāo)的資源優(yōu)化調(diào)度模型,并采用改進后的象群優(yōu)化算法對模型進行求解,最后通過仿真實驗驗證了模型和算法的有效性。

1 傳感器網(wǎng)絡(luò)資源調(diào)度模型的建立

本文將無線傳感器探測網(wǎng)絡(luò)資源優(yōu)化調(diào)度問題視為具有多約束條件的動態(tài)優(yōu)化過程,從單個傳感器設(shè)備的自身感知性能、工作效率、負(fù)載損耗、任務(wù)優(yōu)先級以及多個傳感器資源相互間的關(guān)聯(lián)出發(fā),動態(tài)分析影響整個WSNs網(wǎng)絡(luò)效能收益的復(fù)雜約束指標(biāo),利用模糊層次分析法對這些評價指標(biāo)進行量化分析,以任務(wù)效能收益最大化為目標(biāo)建立調(diào)度模型。

1.1 約束條件評價指標(biāo)分析

(1)

(2)

(3)

(4)

(5)

(6)協(xié)同覆蓋范圍約束。增大協(xié)同覆蓋范圍,不但能擴大目標(biāo)監(jiān)測區(qū)域,降低傳感器資源之間的交接次數(shù),而且能有效提升目標(biāo)監(jiān)測區(qū)域重合處的探測精度,增強可信度。協(xié)同覆蓋范圍與探測效果成正比,是WSNs資源優(yōu)化調(diào)度的重要約束條件。傳感器之間間距越大且相差越小,協(xié)同探測的效果越好,定義協(xié)同探測范圍q的表達(dá)式如下

(6)

1.2 采用模糊層次分析法確定的約束指標(biāo)權(quán)重

由于WSNs網(wǎng)絡(luò)協(xié)同探測多目標(biāo)過程中,資源優(yōu)化調(diào)度約束評價指標(biāo)難以定量且屬于不同量綱范疇,不能通過直接加權(quán)的方式得到目標(biāo)函數(shù),因此,本文采用模糊層次分析法[15-18]對各指標(biāo)進行量化計算。實現(xiàn)的過程主要包括:分析影響目標(biāo)完成的因素,對影響因素上下層關(guān)系進行劃分并建立評估模型,對同層影響因素進行量化評價并利用判斷矩陣求解。建立的指標(biāo)評估模型如圖1所示。

圖1 探測資源優(yōu)化調(diào)度約束指標(biāo)等級評估模型

根據(jù)圖1所示,將WSNs資源優(yōu)化調(diào)度約束評價指標(biāo)分為A、B、C、D 4層,運用9標(biāo)度法對各指標(biāo)間的權(quán)重作出判斷舉證[19],如表1所示。

表1 9標(biāo)度法參數(shù)

(1)目標(biāo)要素B層對目標(biāo)A層判斷矩陣為

(7)

(2)準(zhǔn)則C層對目標(biāo)要素B層判斷矩陣為

(8)

(3)方案D層對準(zhǔn)則C層判斷矩陣為

(9)

C2=[1]

(10)

C3=[1]

(11)

C4=[1]

(12)

C5=[1]

(13)

(4)約束指標(biāo)權(quán)重計算。定義一致性指標(biāo)I,如下所示

(14)

式中:λmax為判斷矩陣的最大特征根;N為矩陣的階數(shù)。當(dāng)I=0時,判斷矩陣一致;I的值越大,判斷矩陣的一致性越差。

定義一致性比率R,如下所示

(15)

式中:S為平均隨機一致性指標(biāo),通過查找表2可確定其對應(yīng)的數(shù)值[20]。當(dāng)R<0.1時,認(rèn)為判斷矩陣的一致性可以接受,否則需要修正。

表2 平均隨機一致性指標(biāo)

經(jīng)計算,各判斷矩陣的權(quán)重、λmax及R分別為

(16)

(17)

WB2=[1]T;λmaxB2=1;R=0

(18)

(19)

WC2=[1]T;λmaxC2=1;R=0

(20)

WC3=[1]T;λmaxC3=1;R=0

(21)

WC4=[1]T;λmaxC4=1;R=0

(22)

WC5=[1]T;λmaxC4=1;R=0

(23)

式中:W為對應(yīng)矩陣的正規(guī)化特征向量?？梢钥闯?所有的R值均小于0.1,符合一致性檢驗,因此,判斷矩陣的特征向量可作為資源優(yōu)化調(diào)度的權(quán)向量。方案元素層約束指標(biāo)權(quán)重如表3所示。

表3 方案元素層約束指標(biāo)權(quán)重

1.3 基于最大效能收益的WSNs資源調(diào)度方案

(24)

(25)

(26)

(27)

(28)

2 傳感器網(wǎng)絡(luò)資源調(diào)度算法設(shè)計

在構(gòu)建WSNs資源優(yōu)化調(diào)度模型后,需要采用優(yōu)化算法對模型進行求解,才能得到最終的資源優(yōu)化調(diào)度方案。

近年來,一種新的群智能算法被引入,即受大象放牧行為啟發(fā)的大象放牧優(yōu)化算法。該算法由Wang等于2015年提出[21],因具有良好的收斂特性和尋找最優(yōu)解的潛力,能夠探索比許多其他自然啟發(fā)算法更好的最優(yōu)解[22-23]?；谙笕核惴ㄈ謨?yōu)化能力強、控制參數(shù)少、實現(xiàn)策略簡單等優(yōu)點,本文在其基礎(chǔ)上進行改進,為WSNs資源調(diào)度提供穩(wěn)定可靠的求解算法。當(dāng)采用象群算法求解資源優(yōu)化調(diào)度方案時,一個大象位置即一種資源調(diào)度方案,由于該調(diào)度方案為0-1矩陣,因此在對大象進行搜索時,產(chǎn)生新位置的方式可看作是以該調(diào)度矩陣為基礎(chǔ)生成新矩陣,且新矩陣與原有矩陣之間僅有少數(shù)元素不同,其適應(yīng)度為資源優(yōu)化調(diào)度目標(biāo)函數(shù)相關(guān)的函數(shù)。

2.1 基本象群算法(EHO)

基本象群優(yōu)化算法(elephant herding optimization algorithm,EHO)主要包括部落更新操作和部落分離操作2個過程。

(1)部落更新操作。來自不同部落的大象在其女族長的領(lǐng)導(dǎo)下一起生活,其他大象的位置都根據(jù)女族長和自身的位置進行更新,位置更新公式如下所示

xnew,ci,j,d=xci,j,d+α(xbest,ci,d-xci,j,d)γ

(29)

式中:xnew,ci,j,d和xci,j,d分別為大象j在部落(ci)中第d個維度的新位置和舊位置,其中1≤d≤D,D為搜索空間的總維數(shù);xbest,ci,d為女族長的位置;α代表部落中女族長對大象個體的影響因子,取值范圍為α∈[0,1];γ用來增加每一代的種群多樣性,γ∈[0,1]。

女族長的位置根據(jù)部落中心的位置進行更新,如下所示

xbest,ci,d=βxcenter,ci,d

(30)

式中:β為0和1之間的隨機數(shù),控制著部落中心對女族長位置的影響。其中,部落中心位置定義為

(31)

式中:nci為部落中大象的數(shù)量。

(2)部落分離操作。當(dāng)部落中適應(yīng)度最差的個體(公象αi)成熟時,它將遠(yuǎn)離部落,此時需在空間中進行隨機搜索以增加全局搜索性能,其位置更新表達(dá)式為

xworst,ci,d=xmin+(xmax-xmin+1)p

(32)

式中:xmax和xmin分別為種群中大象搜索位置的上、下限;p為0到1之間的隨機數(shù)。

2.2 改進象群算法(ASCEHO)

象群算法同其他智能算法一樣,也存在一定的局限性。主要包括:①種群多樣性差?；綞HO算法在初始化種群時采用的是隨機方式,但這種方式并沒有基于先驗知識,因而導(dǎo)致種群出現(xiàn)多樣性差的問題。而種群多樣性差必然會影響后續(xù)的全局搜索尋優(yōu)過程,也會對最優(yōu)解的質(zhì)量有一定影響。②容易陷入局部最優(yōu)?；綞HO算法在迭代過程中容易早熟,導(dǎo)致經(jīng)常出現(xiàn)在局部最優(yōu)解附近搜索求解的情況;與此同時,現(xiàn)有的改進方法并不能有效避免全局和局部尋優(yōu)的盲目性。因此,為改善基本象群算法的尋優(yōu)能力,本文提出了3點改進措施。

(1)混沌映射策略。初始種群在解空間中分布越均勻,算法搜索到最優(yōu)值的概率就越大?；煦缬成洳呗砸蚱浔闅v性、非重復(fù)性等特點被廣泛用于群智能優(yōu)化算法的初始種群生成中[24]。Tent混沌映射的公式表達(dá)如下

(33)

式中:Zk為隨機產(chǎn)生的初始值;Zk+1為混沌映射后產(chǎn)生的初始值。

將得到的混沌序列映射到搜索空間中,得到

xci,j,d=L+(U-L)Zci,j,d

(34)

式中:xci,j,d為部落中第j只大象在d維的位置;U、L分別為搜索空間的上、下界;Zci,j,d為式(33)產(chǎn)生的混沌序列。

圖2(a)和2(b)分別給出了初始種群規(guī)模為30時,隨機生成和基于Tent混沌映射2種方法得到的種群分布。由圖可見,采用基于Tent映射初始化方法得到的種群在搜索空間范圍內(nèi)的分布更均勻。

(a)隨機初始化種群分布

(2)正余弦算法。正余弦算法(sine cosine algorithm,SCA)是Mirjalili于2016年提出的、利用正余弦函數(shù)的數(shù)學(xué)模型使解震蕩性地趨于最優(yōu)解的一種方法。該算法根據(jù)正余弦函數(shù)與單位圓的關(guān)系進行迭代,通過正余弦函數(shù)遍歷單位圓模擬算法尋優(yōu)過程,其遍歷性特點可以防止算法陷入局部最優(yōu)[25]。本文在搜索階段融入正余弦算法更新搜索位置,在該階段,大象以正余弦方式移動,融入SCA算法的全局搜索位置更新模型如下

xnew,ci,j,d=

(35)

式中:γ2∈(0,2π)、γ3∈(0,2)、γ4∈(0,1)為均勻分布的隨機數(shù);xbest,ci,j,d為當(dāng)前最優(yōu)解個體的位置;γ1為控制參數(shù),可寫為

(36)

式中:a為常數(shù);t為當(dāng)前迭代次數(shù);Tmax為最大迭代次數(shù)。

(3)自適應(yīng)權(quán)重因子。在算法的開發(fā)階段通過引入自適應(yīng)權(quán)重因子,以提高局部尋優(yōu)能力,并將自適應(yīng)權(quán)重因子應(yīng)用于改進象群算法開發(fā)階段的全部方程中。自適應(yīng)權(quán)重因子的計算公式如下所示

(37)

因此,開發(fā)階段最差個體位置更新如下所示

(38)

式中:xworst,ci,d為部落中適應(yīng)度最差個體的位置。

2.3 算法流程圖

基于改進后象群優(yōu)化算法的多傳感器資源調(diào)度求解流程如圖3所示。

圖3 改進象群優(yōu)化算法流程圖

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

3.1 仿真條件

為驗證本文所提算法的有效性,分別從算法性能優(yōu)勢以及調(diào)度方案求解兩個方面進行仿真對比。仿真參數(shù)設(shè)置如下:偵察衛(wèi)星8顆,X波段地基雷達(dá)1個,L波段球載雷達(dá)1個,空基預(yù)警機1個。仿真環(huán)境為64位Windows 11操作系統(tǒng),采用的軟件為Matlab R2019a。ASCEHO算法參數(shù)設(shè)置為:種群容量N=50,最大迭代次數(shù)Tmax=100,上界U=5,下界L=-5,無線傳感器網(wǎng)絡(luò)部署及感知能力如表4 所示。

表4 無線傳感器網(wǎng)絡(luò)部署及感知能力

3.2 算法改進前后優(yōu)化結(jié)果對比

圖4給出了在搜索階段采用不同算法更新搜索位置的仿真結(jié)果。從圖中可以看出,采用正余弦算法更新搜索階段位置的EHO算法的適應(yīng)度值高于基本EHO算法,同時收斂速度也更快。圖5給出了搜索階段采用不同更新算法得到的迭代次數(shù)、運行時間和求解精度對比圖,從圖中可以看出,ASCEHO算法在迭代次數(shù)、運行時間和求解精度3個方面均優(yōu)于EHO算法,其主要原因是大象以正余弦方式移動尋找食物,在每一次迭代中根據(jù)式(35)中γ1、γ2、γ3的值來更新全局搜索的距離和方向,進一步縮小搜索區(qū)域,優(yōu)化了全局搜索階段的優(yōu)化速度和求解質(zhì)量。仿真結(jié)果進一步驗證了采用正余弦算法更新搜索階段種群位置的優(yōu)越性。

圖4 不同更新算法在搜索階段的適應(yīng)度值對比

圖5 不同更新算法在搜索階段的迭代次數(shù)、運行時間和求解精度對比

圖6給出了在開發(fā)階段引入自適應(yīng)權(quán)重因子后2種算法的適應(yīng)度值曲線對比。從圖中可以看出,在開發(fā)階段引入自適應(yīng)權(quán)重因子后,ASCEHO算法的適應(yīng)度值與EHO算法相比有所提高,且經(jīng)過較少的迭代次數(shù)便能達(dá)到最優(yōu)值,因此收斂速度也優(yōu)于EHO算法。

圖7給出了開發(fā)階段2種算法的迭代次數(shù)、運行時間和求解精度對比圖,從圖中可以看出,在開發(fā)階段引入自適應(yīng)權(quán)重因子后,ASCEHO算法的迭代次數(shù)、算法運行時間和算法求解精度均優(yōu)于EHO算法,這是因為將自適應(yīng)權(quán)重因子應(yīng)用于ASCEHO算法開發(fā)階段的全部方程中,在為種群注入足夠多樣性的同時,也避免了任何解停滯的可能性。

圖7 不同更新算法在開發(fā)階段的迭代次數(shù)、運行時間和求解精度對比

為進一步說明本文所提ASCEHO算法的優(yōu)越性,采用本文算法與基本象群算法(EHO)、長期記憶象群算法(LMEHO)、基于自適應(yīng)合作覓食與分散覓食策略的象群算法(ADEHO)、鯨魚算法(WOA)、粒子群算法(PSO)進行求解,對比了目標(biāo)價函數(shù)的適應(yīng)度值和算法的迭代次數(shù)、運行時間以及求解精度。圖8給出了采用上述不同算法求解目標(biāo)函數(shù)的適應(yīng)度值對比曲線。圖9給出了不同算法的迭代次數(shù)、運行時間和求解精度對比曲線。

圖8 不同算法的適應(yīng)度值對比

圖9 不同算法迭代次數(shù)、運行時間和求解精度對比

由圖8可見,盡管所有的算法最終都能收斂到定值,但收斂速度和最終收斂值存在一定差異。相比于其他算法,ASCEHO算法能更快地得到最優(yōu)解,即收斂速度最快,且最終收斂值為0.98,表明了ASCEHO算法的優(yōu)越性。EHO算法收斂速度最慢,且最終收斂值為0.68。這是因為改進后的算法對每個階段存在的劣勢都進行了改進,從而優(yōu)化了解的質(zhì)量。

從圖9中不同算法的迭代次數(shù)、運行時間和求解精度對比結(jié)果可見,ASCEHO算法的迭代次數(shù)、運行時間和求解精度均優(yōu)于其他算法,與EHO算法相比,迭代次數(shù)減少了41次,求解精度提高了124%,運行時間減少了57%。其主要原因是采用Tent混沌序列對種群進行初始化,初始化效果優(yōu)于隨機初始化結(jié)果,這就使得算法在后續(xù)搜索和開發(fā)階段能夠重點關(guān)注搜索空間中的信息區(qū)域以選擇基本特征,避免了不相關(guān)特征。

綜上所述,ASCEHO算法通過正余弦算法在搜索階段對種群的位置進行更新,在開發(fā)階段引入自適應(yīng)權(quán)重因子更新位置方程來不斷尋找新的有前景的區(qū)域,有助于防止算法陷入局部最優(yōu),改進了基本EHO算法的局部搜索。

3.3 算法改進前后優(yōu)化結(jié)果對比分析

(1)傳感器網(wǎng)絡(luò)探測跟蹤目標(biāo)數(shù)量對比。為進一步驗證本文所提ASCEHO算法在求解優(yōu)化調(diào)度模型中的有效性,將ASCEHO算法與EHO算法、SCAEHO算法、ADEHO算法、LMEHO算法得到的探測跟蹤目標(biāo)數(shù)量進行對比分析,結(jié)果如圖10所示。

圖10 不同算法下探測跟蹤目標(biāo)數(shù)對比

從圖10可以看出,不同算法下探測跟蹤目標(biāo)數(shù)量存在差異,總體來看,采用ASCEHO算法時,每個傳感器設(shè)備探測跟蹤的目標(biāo)數(shù)較為均衡,不存在某一個傳感器空載過久或者一直過載的情況,每個傳感器平均負(fù)責(zé)探測跟蹤2.7個目標(biāo),無線傳感器網(wǎng)絡(luò)負(fù)載較小,因此能效較高。而采用其他算法時,有的存在某一傳感器執(zhí)行對所有目標(biāo)的探測跟蹤,有的探測跟蹤1個目標(biāo)后停止工作,均會造成目標(biāo)探測跟蹤數(shù)量的不均衡,導(dǎo)致目標(biāo)探測網(wǎng)絡(luò)的能耗增加,負(fù)載較大。

(2)WSNs資源優(yōu)化調(diào)度方案對比。在對探測跟蹤目標(biāo)數(shù)量開展分析后,進一步分析了不同算法下目標(biāo)探測WSNs的資源調(diào)度方案,將本文提出的ASCEHO算法與EHO算法、SCAEHO算法、ADEHO算法、LMEHO算法得到的資源優(yōu)化調(diào)度方案進行對比分析,結(jié)果如表5所示。

表5 多目標(biāo)探測過程中WSNs資源優(yōu)化調(diào)度方案

從表5可見,ASCEHO算法在求解優(yōu)化調(diào)度方案時具有明顯優(yōu)勢。采用ASCEHO算法生成的方案對目標(biāo)進行探測跟蹤,資源的使用較為均衡,每個目標(biāo)均有5個傳感器進行探測跟蹤。而在其他改進EHO算法生成的調(diào)度方案中,探測資源的利用率極不均衡,如ADEHO算法中對某一個目標(biāo)的探測跟蹤過程中存在傳感器重復(fù)利用的情況,造成了資源的浪費,以及LMEHO算法生成的調(diào)度方案中存在傳感器資源利用率較低的情況。

4 結(jié) 論

本文從目標(biāo)探測過程中的無線傳感器資源優(yōu)化調(diào)度問題出發(fā),綜合考慮了單傳感器資源效能約束和多傳感器資源相互關(guān)聯(lián)約束等評價指標(biāo),并基于模糊層次分析法對評價指標(biāo)進行量化,建立了以目標(biāo)探測的WSNs網(wǎng)絡(luò)綜合效能收益最大為準(zhǔn)則的資源優(yōu)化調(diào)度模型,最后基于改進象群算法對模型求解,并通過仿真實驗進行驗證,得到以下主要結(jié)論。

(1)基于傳感器資源相互關(guān)聯(lián)約束指標(biāo)建立調(diào)度模型,一定程度上提高了資源優(yōu)化調(diào)度模型的可靠性和說服力,通過合理的調(diào)度,能夠有效解決無線傳感器網(wǎng)絡(luò)資源利用率低的問題,并提高目標(biāo)監(jiān)測系統(tǒng)的探測效果。

(2)所提算法有效改善了算法容易陷入局部最優(yōu)的問題,提高了計算效率,并使資源優(yōu)化調(diào)度問題能夠在有限時間內(nèi)獲得最優(yōu)解。