面向多目標探測的無線傳感器網絡資源調度方法

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

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

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

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

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

1 傳感器網絡資源調度模型的建立

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

1.1 約束條件評價指標分析

(1)

(2)

(3)

(4)

(5)

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

(6)

1.2 采用模糊層次分析法確定的約束指標權重

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

圖1 探測資源優化調度約束指標等級評估模型

根據圖1所示,將WSNs資源優化調度約束評價指標分為A、B、C、D 4層,運用9標度法對各指標間的權重作出判斷舉證[19],如表1所示。

表1 9標度法參數

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

(7)

(2)準則C層對目標要素B層判斷矩陣為

(8)

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

(9)

C2=[1]

(10)

C3=[1]

(11)

C4=[1]

(12)

C5=[1]

(13)

(4)約束指標權重計算。定義一致性指標I,如下所示

(14)

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

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

(15)

式中:S為平均隨機一致性指標,通過查找表2可確定其對應的數值[20]。當R<0.1時,認為判斷矩陣的一致性可以接受,否則需要修正。

表2 平均隨機一致性指標

經計算,各判斷矩陣的權重、λ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為對應矩陣的正規化特征向量。可以看出,所有的R值均小于0.1,符合一致性檢驗,因此,判斷矩陣的特征向量可作為資源優化調度的權向量。方案元素層約束指標權重如表3所示。

表3 方案元素層約束指標權重

1.3 基于最大效能收益的WSNs資源調度方案

(24)

(25)

(26)

(27)

(28)

2 傳感器網絡資源調度算法設計

在構建WSNs資源優化調度模型后,需要采用優化算法對模型進行求解,才能得到最終的資源優化調度方案。

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

2.1 基本象群算法(EHO)

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

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

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為搜索空間的總維數;xbest,ci,d為女族長的位置;α代表部落中女族長對大象個體的影響因子,取值范圍為α∈[0,1];γ用來增加每一代的種群多樣性,γ∈[0,1]。

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

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

(30)

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

(31)

式中:nci為部落中大象的數量。

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

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

(32)

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

2.2 改進象群算法(ASCEHO)

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

(1)混沌映射策略。初始種群在解空間中分布越均勻,算法搜索到最優值的概率就越大。混沌映射策略因其遍歷性、非重復性等特點被廣泛用于群智能優化算法的初始種群生成中[24]。Tent混沌映射的公式表達如下

(33)

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

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

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

(34)

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

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

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

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

xnew,ci,j,d=

(35)

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

(36)

式中:a為常數;t為當前迭代次數;Tmax為最大迭代次數。

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

(37)

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

(38)

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

2.3 算法流程圖

基于改進后象群優化算法的多傳感器資源調度求解流程如圖3所示。

圖3 改進象群優化算法流程圖

3 仿真實驗結果與分析

3.1 仿真條件

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

表4 無線傳感器網絡部署及感知能力

3.2 算法改進前后優化結果對比

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

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

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

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

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

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

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

圖8 不同算法的適應度值對比

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

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

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

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

3.3 算法改進前后優化結果對比分析

(1)傳感器網絡探測跟蹤目標數量對比。為進一步驗證本文所提ASCEHO算法在求解優化調度模型中的有效性,將ASCEHO算法與EHO算法、SCAEHO算法、ADEHO算法、LMEHO算法得到的探測跟蹤目標數量進行對比分析,結果如圖10所示。

圖10 不同算法下探測跟蹤目標數對比

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

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

表5 多目標探測過程中WSNs資源優化調度方案

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

4 結 論

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

(1)基于傳感器資源相互關聯約束指標建立調度模型,一定程度上提高了資源優化調度模型的可靠性和說服力,通過合理的調度,能夠有效解決無線傳感器網絡資源利用率低的問題,并提高目標監測系統的探測效果。

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