改進二進制粒子群優化的節點選擇算法

魏聲云,張 靜,郭 虹,李 鷗

(解放軍信息工程大學信息與系統工程學院,河南鄭州 450001)

?

改進二進制粒子群優化的節點選擇算法

魏聲云,張 靜,郭 虹,李 鷗

(解放軍信息工程大學信息與系統工程學院,河南鄭州 450001)

摘要:針對無線傳感器網絡多目標跟蹤節點選擇問題,提出了一種最大化跟蹤精度的二進制粒子群優化節點選擇算法.該算法基于目標的預測位置,以費舍爾信息矩陣的跡為精度度量,構建節點優化選擇模型,提出了二進制粒子群優化的改進形式,并用于節點選擇模型的求解.改進的二進制粒子群優化算法采用矢量的二進制編碼方式、約束滿足的循環移位種群初始化方法,帶V型轉換函數的位置更新規則,并設計了引導因子引導粒子群的進化.仿真結果表明,所提出的節點選擇算法能夠有效地應用于多目標跟蹤問題,與基本的二進制粒子群優化算法和遺傳算法相比,改進的二進制粒子群優化算法能夠在全局尋優和局部探索間取得平衡,且能有效地避免局部最優,對較大規模的網絡具有很強的適用性.

關鍵詞:無線傳感器網絡;節點選擇;二進制粒子群優化;費舍爾信息矩陣

無線傳感器網絡(Wireless Sensor Networks,WSN)是集成了監測、控制以及無線通信的網絡系統,在軍事偵察、環境監測、目標跟蹤、空間探索和災難搶險等特殊領域具有廣闊的應用前景.特別是網絡的分布式信息處理、快速展開、抗毀性強等特點,使得機動目標跟蹤成為了WSN最具代表性的應用之一[1].跟蹤的目的是為了獲取目標的運動軌跡,盡量多的節點協同跟蹤目標能夠提高跟蹤性能,但也會帶來更多的能量消耗[2].由于節點選擇問題的組合特性,當網絡規模較大,需要選擇的節點數較多時,節點選擇是一個NP難問題.隨著WSN的廣泛應用,節點選擇問題成為了傳感器管理領域的研究熱點.

近年來,國內外學者針對節點選擇問題提出了眾多的方法和策略.文獻[3-4]均以幾何精度衰減因子為目標函數,采用貪婪策略構建活躍節點.文獻[5]將后驗克拉美羅下界作為傳感器選擇和優化的準則,采用窮舉搜索的方法為單個目標選擇參與跟蹤的節點,該方法在節點數較小的情況下是有效的.而針對大規模的傳感器網絡,文獻[6]提出了一種基于牡丹樹的低能耗的節點休眠調度算法;文獻[7]提出了基于廣義信息增益的目標跟蹤節點選擇算法,算法采用布爾二次規劃理論對優化模型進行求解;文獻[8]研究了面向多目標跟蹤的分布式節點選擇問題,將初始的0-1整數規劃問題松弛處理,轉換成凸優化問題,采用梯度投影搜索算法作為求解策略,獲得原問題的次優解.針對規劃方法計算量隨著網絡規模變大而急劇增加的問題,文獻[9]提出將二進制粒子群優化(Binary Particle Swarm Optimization,BPSO)算法引入節點選擇問題中;文獻[10]提出了基于粒子群算法(Particle Swarm Optimization,PSO)的傳感器調度方法.以上兩類算法面臨的共同問題是:算法容易陷入局部最優,而且,在網絡規模較大時,難以保證算法在可接受的時間范圍內找到滿意解.

筆者研究多目標跟蹤節點選擇算法,以費舍爾信息矩陣的跡[11]為準則,設計了一個基于改進二進制粒子群優化(Modified Binary Particle Swarm Optimization,MBPSO)的多目標跟蹤實時節點選擇算法.其主要貢獻有:構建了通用的目標跟蹤節點選擇閉環體系結構,在此結構下建立了以費舍爾信息矩陣(Fisher Information Matrix,FIM)的跡為精度度量的多目標跟蹤節點選擇模型;對基本BPSO算法從加快收斂速度和避免陷入局部最優兩個方面進行了改進,結合多目標跟蹤節點選擇問題,提出了粒子的矢量編碼方式,并采用循環移位的方法對種群進行初始化,引入V型轉換函數構建粒子的位置更新規則,分析了BPSO陷入局部最優的根本原因,提出了帶引導因子的搜索策略;實現了目標跟蹤過程中的節點實時選擇,并驗證了算法的有效性.

1 目標跟蹤節點選擇問題

圖1 目標跟蹤節點選擇閉環體系結構

目標跟蹤節點選擇是指利用有限的傳感器資源,以網絡效能為目標函數,在每個采樣時間動態地選擇合理的傳感器組合對目標進行跟蹤.節點選擇的核心問題是建立節點選擇的優化模型,并采用高效的求解方法對模型進行求解,目標跟蹤節點選擇閉環體系結構如圖1所示.

2 節點的優化選擇模型

以最大化所有目標的跟蹤精度為目標,采用基于FIM的機制對跟蹤精度進行度量.目標跟蹤的目的是在每一時間步長內對目標進行精確的定位,定位的精度與任務節點集的觀測信息密切相關,FIM越大,表明觀測信息對定位精度的貢獻越大[12],因此,最大化跟蹤精度可以轉化成最大化FIM.在建立節點選擇優化模型之前,首先給出兩個相關的二進制變量的定義.

對目標k的任務節點集Gk(t)的FIM表示為

其中,(dk,i,φk,i)表示與目標k預測位置(px,k,py,k)相關的節點i的極坐標位置,由于FIM為矩陣形式,不方便后續的優化分析,文獻[13]證明了對Jk和對det{Jk}的優化問題是等價的,且最大化det{Jk}與最小化1det{Jk}是等價的,因此,1det{Jk}可以反映定位均方誤差(Mean Square Error,MSE)的大小.

因此,跟蹤精度與參與跟蹤的節點數目、目標與節點間的距離、角度分集以及觀測噪聲有關.

為了保證跟蹤質量,假設同一時刻跟蹤每個目標的節點數為m,一個節點同一時刻最多只能跟蹤一個目標.因此,目標跟蹤節點選擇問題的優化模型為

節點選擇實際完成的是多個目標與多個節點的配對,目標函數是復雜且非線性的,同時,具有多個約束條件.當網絡規模較大時,節點選擇是NP難的組合優化問題,特別是在實時性要求高的目標跟蹤系統中,傳統的搜索算法很難在可接受的時間范圍內找到滿意解,因此引入群智能算法對問題進行求解.

3 基于MBPSO的節點選擇算法

面向目標跟蹤的節點選擇是一個離散空間的尋優問題.由于節點選擇需要在較短的時間內完成,因此,對算法尋優速度和穩定性要求很高,與其他搜索算法相比,BPSO具有收斂速度較快、易于實現等優點,在已有的離散空間尋優問題研究中[14],證明了具有較好的尋優效果.

3.1 基本BPSO算法

BPSO是基于種群和適應度兩個基本概念的尋優算法,每個粒子代表問題的一個可行解,具有速度和位置兩個描述量.采用一組參數和符號描述BPSO算法,可以表示為

在基本BPSO算法中,隨著迭代的進行,粒子的隨機游走現象增加,使得算法收斂速度變慢,容易陷入局部最優[15].為了將BPSO算法應用于求解多目標跟蹤節點選擇問題,筆者提出的MBPSO算法分別從加快收斂速度和避免陷入局部最優兩個方面對算法進行改進.

3.2 MBPSO算法及其在節點選擇問題中的應用

圖2 粒子的編碼結構

3.2.1 粒子編碼方式和初始化方法

為了降低粒子群的維數,避免矩陣編碼導致粒子的搜索空間過大的問題,利用節點感知范圍有限這個約束條件,得到目標暴露范圍內的節點數Nk,對目標與節點對應關系矩陣進行稀疏處理,采用矢量的方式對粒子進行編碼,粒子的編碼結構如圖2所示.

隨機初始化種群方法雖然操作簡單,但是,初始種群中單個粒子的位置矢量中為1的位數可能會遠遠大于期望的數量,這會導致初始的適應度函數值過大,從而影響算法的收斂速度.為了減小粒子群初始的搜索空間,同時增加初始種群的多樣性,文中設計了一種與約束條件相適應的種群初始化方法(Constraint-Adaptive Population Initialization,CAPI).CAPI實現過程為:首先,通過隨機生成的方式,使種群中第一個粒子x01中元素1的個數等于m Na,與約束條件相適應;然后,通過循環移位操作,產生種群中剩余個體的位置,得到初始的種群位置.循環移位操作的數學描述為

3.2.2 考慮粒子絕對速度的位置更新規則

WSN目標跟蹤的實時性與搜索算法的收斂速度息息相關.在粒子實際迭代過程中,粒子的絕對速度越大,粒子遠離全局最優位置的概率就越大,而S型轉換函數并未體現這一規律[16].因此,MBPSO采用V型轉換函數以適應粒子的進化,粒子根據自身當前的位置、速度、到自身最佳位置的距離以及到全局最優位置的距離來完成速度和位置的更新,以保證節點選擇能夠在可行的時間內完成.更新規則如下:

3.2.3 帶引導因子的搜索策略

搜索算法擺脫局部最優的能力能夠直接反應任務節點執行跟蹤任務的質量,局部搜索能力越強,跟蹤精度越高.當BPSO算法陷入局部最優時,種群的進化處于停滯狀態,若粒子群最終的位置為G*,如果粒子群在進化過程中沒有找到比Gbest更優的位置,則所有的粒子將向G*聚攏,但此時的G*并不是全局最優位置.這種聚攏現象是導致BPSO算法陷入局部最優的根本原因.為了使BPSO中的粒子擺脫局部最優,有如下兩種方法:使粒子在向G*聚攏的過程中,找到比Gbest更優的位置;改變當前的Glbest,使向G*聚攏的粒子改變搜索方向,尋找新的搜索空間,從而提高算法的局部搜索能力.針對方法,文獻[17]提出了帶極值擾動的簡化PSO算法,然而,針對不同的問題,添加擾動的停滯步數閾值很難確定,閾值過小,可能影響粒子群的正常進化;閾值過大,算法擺脫局部最優的效果不明顯.同時,極值擾動具有很強的隨機性,粒子的運動空間越大,種群跳出局部最優的可能性越小.筆者針對第種方法,受蝙蝠算法[18]中的局部搜索策略的啟發,設計了帶引導因子的粒子群搜索策略.該策略的基本思想是:定義全局搜索引導因子和局部搜索引導因子,在粒子向G*聚攏的過程中,根據兩個引導因子,在Glbest附近進行隨機搜索,以加快收斂速度和避免局部最優.以下給出兩個引導因子的定義及更新方式.

其中,α為全局搜索引導因子,表示粒子群搜索方向改變的概率,α在算法的前期具有較大的值,使粒子的搜索空間具有多樣性,保證粒子群的全局搜索能力,而在算法的中后期逐漸變小.β為局部搜索引導因子,表示粒子進行局部搜索的概率,β在算法的前期具有較小的值,而后逐漸變大,以增強粒子局部搜索的能力,α0p和βmax分別為全局引導因子的初值和局部引導因子的最大值.

3.2.4 帶懲罰因子的適應度函數設計

由于節點選擇是一個具有約束條件的優化問題,目標函數不能直接作為適應度函數.采用不依賴種群進化的靜態罰函數法將約束問題轉化成無約束問題,將增加了懲罰項的目標函數作為適應度函數,定義懲罰因子ξ1和ξ2.則目標跟蹤節點選擇問題的適應度函數表達式為

3.2.5 算法步驟

步驟1 初始化WSN和MBPSO算法的參數.

步驟2 采用二進制方式對每個粒子進行編碼,并利用CAPI方法初始化粒子群.

步驟5 判斷循環是否終止.若終止,執行步驟6;否則,執行步驟3.

步驟6 輸出全局最優位置Gbest,構建任務節點集.

4 仿真實驗與結果分析

采用主頻為2.4 GHz的PC機在MATLAB環境下對算法進行一系列的仿真.采用k-means算法使WSN中節點均勻分布于200 m×200 m的正方形區域內,參考文獻[3-4,10],實驗參數設置如下:rs=50 m;考慮網絡中的目標數為2,目標的初始位置分別為(45,45)和(145,145),節點數默認為90,且σ2w=0.05;目標采用CV模型,濾波算法采用無跡卡爾曼濾波,目標的初始狀態為[43,43,2,2]以及[152,152,-2,-2],初始協方差矩陣均為0.001×diag[1,1,0,0];c1=c2=2,nop=30,Max_Iter=200,wmax=0.9,wmin=0.4,α0p=0.5,βmax=0.3,ξ1=ξ2=200.GA的參數設置為:種群規模設置為nop=30,精英個體數為4,最大循環次數Max_Iter=200,交叉概率和變異概率分別為0.7和0.02.實驗次數n=50,且每次實驗獨立進行,實驗結果取多次實驗的平均值.

4.2 仿真結果分析

圖3是m值和節點數量對MBPSO性能的影響.由圖3(a)可知,隨著m值的增加,平均適應度函數值變小,這是因為觀測節點數越多,任務節點集獲取關于目標的信息量增加,跟蹤精度變高.然而,適應度函數值的增量是逐漸變小的,這是由于m值增大到一定數值時,節點獲得信息逐漸變得冗余.因此,綜合考慮精度、能量消耗和通信負載等因素,文中選取m=3.由圖3(b)可知,隨著節點數量的增加,平均適應度函數值變小,這是由于網絡中節點密度變大,可供選擇的節點數增加,有利于提高目標跟蹤精度.此外,隨著m值和節點數量的增加,MBPSO算法的收斂速度并沒有變慢,這表明算法的適應性較強.

圖4為GA、BPSO-CSP[9]、IBPSO[19]和MBPSO的收斂性能對比結果.由圖可知,BSPO前期收斂速度

4.1 性能評價指標與仿真環境設置

為了驗證筆者所提算法的有效性,在目標跟蹤體系結構下,針對節點的優化選擇問題,將所提的MBPSO算法與遺傳算法(Genetic Algorithm,GA)和文獻[9]算法(記為BPSO-CSP)進行對比和分析.并采用收斂性能、平均百分偏差和跟蹤誤差3個指標對算法進行評價.其中,平均百分偏差表示n次實驗在截止時刻獲得的解ft(i)與客觀最優解ft0間的偏差(實驗分析中的ft0由大量的仿真實驗得到),其值越小,算法的性能越好.跟蹤誤差采用均方根誤差(Root-Mean-Square Error,RMSE)來度量.平均百分偏差的計算式為最快,容易陷入局部最優,這是由于BPSO-CSP在迭代過程中,粒子容易出現聚集現象,導致種群進化停滯.GA前期收斂速度最慢,后期也容易陷入早熟,這是因為GA中的變異操作雖然能夠以一定的概率使算法跳出局部最優,但是,需要經過較多的迭代次數.MBPSO在20～50次迭代中,平均適應度函數大于BPSOCSP,這是算法在前期依然有一定的概率進行局部搜索,對前期的平均收斂速度有一定的影響,但是,MBPSO在全局尋優和局部搜索間取得了較好的平衡.在循環數為50次和100次左右時,MBPSO獲得了BPSO-CSP和GA在200次迭代所獲得的適應度函數值,如果采用平均適應度函數來評價算法的復雜度,那么,MBPSO的時間復雜度為BPSO-CSP的1/4,GA和IBPSO的1/2.

圖3 m值和節點數對算法性能的影響

圖4 不同算法的收斂曲線　

圖5 不同節點數下算法的平均百分偏差

圖5是循環數l=200時,3個算法的平均百分偏差的比較結果.由圖可知,隨著節點數的增加,GA、IBPSO和BPSO-CSP的平均百分偏差均變大,但是MBPSO的平均百分偏差基本未變,始終保持在2%以內.這表明,隨著網絡規模的增大,MBPSO始終能夠找到優質的解.

圖6為文中算法與經典的全局節點選擇(Global Node Selection,GNS)算法[4]、GA和BPSO-CSP的跟蹤平均RMSE結果.由圖可知,基于MBPSO的節點選擇算法性能是最優的,這是因為基于MBPSO的節點選擇算法能夠以最大的概率找到最適合跟蹤目標的任務節點集,使跟蹤誤差最小.

圖6 不同采樣周期的平均RMSE

5 結束語

針對無線傳感器網絡多目標跟蹤的節點選擇問題,構建了通用的節點選擇閉環體系結構,提出了一種基于改進二進制粒子群優化的實時節點選擇算法.該算法以最大化跟蹤精度為目標,采用FIM跡的形式構建優化模型,引入群智能方法對模型進行了求解.分析了BPSO算法容易陷入局部最優的原因,提出了BPSO的改進形式.MBPSO采用了矢量編碼方式,結合約束條件,利用循環移位操作初始化種群,壓縮了粒子的搜索空間,增加了種群的多樣性;同時,設計了帶引導因子的搜索策略.仿真結果表明,筆者所提的基于MBPSO的節點選擇算法是有效的,該算法能夠在全局尋優和局部探索間取得平衡,且有效地避免了局部最優,對較大規模的網絡具有很強的適用性.下一步的研究工作重點是分布式跟蹤結構下,考慮跟蹤精度、能量均衡和能量消耗的節點選擇算法.

參考文獻:

[1]AKYILDIZ I F,SU W,SANKARASUBRAMANIAM Y,et al.Wireless Sensor Network:a Survey[J].Computer Networks,2002,38(4):393-422.

[2]DEMIGHA O,HIDOUCI W K,AHMED T.On Energy Efficiency in Collaborative Target Tracking in Wireless Sensor Network:a Review[J].IEEE Communications Surveys& Tutorials,2013,15(3):1210-1221.

[3]ZOGHI M,KAHAEI M H.Adaptive Sensor Selection in Wireless Sensor Networks for Target Tracking[J].IET Signal Processing,2010,4(5):530-536.

[4]KAPLAN L M.Global Node Selection for Localization in a Distributed Sensor Network[J].IEEE Transactions on Aerospace and Electronic Systems,2006,42(1):113-135.

[5]楊小軍.基于性能邊界和量化數據的WSN目標跟蹤傳感器選擇算法[J].電子學報,2014,42(6):1081-1085.YANG Xiaojun.Sensor Selection for Target Tracking in Wireless Sensor Networks Based on Performance Bounds and Quantized Data[J].Acta Electronica Sinica,2014,42(6):1081-1085.

[6]齊小剛,陸贊贊,鄭耿忠,等.一種低能耗低時延的休眠調度算法[J].西安電子科技大學學報,2015,42(1):125-129.QI Xiaogang,LU Zanzan,ZHENG Gengzhong,et al.Low-power and Low-delay Sleep Scheduling Algorithm Based on the Data Aggregation Tree[J].Journal of Xidian University,2015,42(1):125-129.

[7]SHEN X J,VARSHNEY P K.Sensor Selection Based on Generalized Information Gain for Target Tracking in Large Sensor Networks[J].IEEE Transactions on Signal Processing,2014,62(2):363-375.

[8]FU Y Y,LING Q,TIAN Z.Distributed Sensor Allocation for Multi-target Tracking in Wireless Sensor Networks[J].IEEE Transactions on Aerospace and Electronic Systems,2012,48(4):3538-3552.

[9]NAEEM M,PAREEK U,LEE D C.Swarm Intelligence for Sensor Selection Problems[J].IEEE Sensors Journal,2012,12(8):2577-2585.

[10]李國輝,馮明月,易先清.基于分群粒子群的傳感器調度方法[J].系統工程與電子技術,2010,32(3):598-602.LI Guohui,FENG Mingyue,YI Xianqing.Sensor Scheduling Method Based on Grouping Particle Swarm Optimization [J].Systems Engineering and Electronics,2010,32(3):598-602.

[11]THARMARASA R,KIRUBARAJAN T,HERNANDEZ M L,et al.PCRLB-based Multisensor Array Management for Multitarget Tracking[J].IEEE Transactions on Aerospace and Electronic Systems,2007,43(2):539-555.

[12]YANG Z Y,SHI X F,CHEN J M.Optimal Coordination of Mobile Sensors for Target Tracking Under Additive and Multiplicative Noises[J].IEEE Transactions on Industrial Electronics,2014,61(7):3459-3468.

[13]BISHOPK A N,JENSFELT P.An Optimality Analysis of Sensor-Target Geometries for Signal Strength Based Localization[C]//Proceedings of the 5th International Conference on Intelligent Sensors,Sensor Networks and Information Processing.Piscataway:IEEE Computer Society,2009:127-132.

[14]郭文忠,蘇金樹,陳澄宇,等.無線傳感器網絡中帶復雜聯盟的自適應任務分配算法[J].通信學報,2014,35(3):1-10.GUO Wenzhong,SU Jinshu,CHEN Dengyu,et al.Self-adapted Task Allocation Algorithm with Complicated Coalition in Wireless Sensor Network[J].Journal on Communications,2014,35(3):1-10.

[15]YANG J,ZHANG H S,LING Y,et al.Task Allocation for Wireless Sensor Network Using Modified Binary Particle Swarm Optimization[J].IEEE Sensor Journal,2014,14(3):882-891.

[16]MIRJALILI S,LEWIS A.S-shaped versus V-shaped Transfer Functions for Binary Particle Swarm Optimization[J].Swarm and Evolutionary Computation,2013(9):1-14.

[17]胡旺,李志蜀.一種更簡化而高效的粒子群優化算法[J].軟件學報,2007,18(14):861-868.HU Wang,LI Zhishu.A Simpler and More Effective Particle Swarm Optimization Algorithm[J].Journal of Software,2007,18(14):861-868.

[18]YANG X S.A New Metaheuristic Bat-inspired Algorithm[C]//Proceedings of Nature Inspired Cooperative Strategies for Optimization.Berlin:Springer-Verlag,2010:65-74.

[19]徐春義,肖人彬.一種改進的二進制粒子群算法[J].模式識別與人工智能,2007,20(6):789-793.XU Chunyi,XIAO Renbin.An Improved Binary Particle Swarm Optimizer[J].Pattern Recognition and Artificial Intelligence,2007,20(6):789-793.

(編輯:王 瑞)

Sensor selection algorithm based on modified binary particle swarm optimization

WEI Shengyun,ZHANG Jing,GUO Hong,LI Ou
(Institute of Information System Engineering,Information Engineering Univ.of PLA,Zhengzhou 450001,China)

Abstract:Considering the problem of sensor selection for multi-target tracking in wireless sensor networks (WSN),a sensor selection algorithm based on binary particle swarm optimization(PSO)is proposed to maximize the tracking accuracy.The predicted coordinate of the target and the determinant of the Fisher information matrix(FIM)is used for sensor selection.A modified form of binary particle swarm optimization(MBPSO)is proposed to solve the model,which is designed by employing the binary vector coding manner,constraint satisfaction cyclic shift population initialization method,particle position updating rules with the V-shaped transfer function and guidance factor.Simulation results show that the proposed sensor selection algorithm can be efficiently applied in the multi-target tracking problem.Compared to the basic particle swarm optimization algorithm and genetic algorithm(GA),the modified algorithm achieves a balance between global optimization and local exploration,and can effectively avoid the local optimum.Moreover,the proposed algorithm is suitable for large-scale networks.

Key Words:wireless sensor networks;sensor selection;binary particle swarm optimization;Fisher information matrix

作者簡介:魏聲云(1989-),男,解放軍信息工程大學碩士研究生,E-mail:junyun1002@126.com.

基金項目:國家自然科學基金資助項目(61201380);國家科技重大專項資助項目(2014ZX03006003)

收稿日期:2014-12-19 網絡出版時間:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.026

中圖分類號:TP393

文獻標識碼:A

文章編號:1001-2400(2016)02-0150-07

網絡出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.023.html