改進二進制粒子群優(yōu)化的節(jié)點選擇算法

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

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

?

改進二進制粒子群優(yōu)化的節(jié)點選擇算法

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

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

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

關鍵詞:無線傳感器網(wǎng)絡;節(jié)點選擇;二進制粒子群優(yōu)化;費舍爾信息矩陣

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

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

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

1 目標跟蹤節(jié)點選擇問題

圖1 目標跟蹤節(jié)點選擇閉環(huán)體系結(jié)構(gòu)

目標跟蹤節(jié)點選擇是指利用有限的傳感器資源,以網(wǎng)絡效能為目標函數(shù),在每個采樣時間動態(tài)地選擇合理的傳感器組合對目標進行跟蹤.節(jié)點選擇的核心問題是建立節(jié)點選擇的優(yōu)化模型,并采用高效的求解方法對模型進行求解,目標跟蹤節(jié)點選擇閉環(huán)體系結(jié)構(gòu)如圖1所示.

2 節(jié)點的優(yōu)化選擇模型

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

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

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

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

為了保證跟蹤質(zhì)量,假設同一時刻跟蹤每個目標的節(jié)點數(shù)為m,一個節(jié)點同一時刻最多只能跟蹤一個目標.因此,目標跟蹤節(jié)點選擇問題的優(yōu)化模型為

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

3 基于MBPSO的節(jié)點選擇算法

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

3.1 基本BPSO算法

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

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

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

圖2 粒子的編碼結(jié)構(gòu)

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

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

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

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

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

3.2.3 帶引導因子的搜索策略

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

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

3.2.4 帶懲罰因子的適應度函數(shù)設計

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

3.2.5 算法步驟

步驟1 初始化WSN和MBPSO算法的參數(shù).

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

步驟5 判斷循環(huán)是否終止.若終止,執(zhí)行步驟6;否則,執(zhí)行步驟3.

步驟6 輸出全局最優(yōu)位置Gbest,構(gòu)建任務節(jié)點集.

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

采用主頻為2.4 GHz的PC機在MATLAB環(huán)境下對算法進行一系列的仿真.采用k-means算法使WSN中節(jié)點均勻分布于200 m×200 m的正方形區(qū)域內(nèi),參考文獻[3-4,10],實驗參數(shù)設置如下:rs=50 m;考慮網(wǎng)絡中的目標數(shù)為2,目標的初始位置分別為(45,45)和(145,145),節(jié)點數(shù)默認為90,且σ2w=0.05;目標采用CV模型,濾波算法采用無跡卡爾曼濾波,目標的初始狀態(tài)為[43,43,2,2]以及[152,152,-2,-2],初始協(xié)方差矩陣均為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的參數(shù)設置為:種群規(guī)模設置為nop=30,精英個體數(shù)為4,最大循環(huán)次數(shù)Max_Iter=200,交叉概率和變異概率分別為0.7和0.02.實驗次數(shù)n=50,且每次實驗獨立進行,實驗結(jié)果取多次實驗的平均值.

4.2 仿真結(jié)果分析

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

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

4.1 性能評價指標與仿真環(huán)境設置

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

圖3 m值和節(jié)點數(shù)對算法性能的影響

圖4 不同算法的收斂曲線　

圖5 不同節(jié)點數(shù)下算法的平均百分偏差

圖5是循環(huán)數(shù)l=200時,3個算法的平均百分偏差的比較結(jié)果.由圖可知,隨著節(jié)點數(shù)的增加,GA、IBPSO和BPSO-CSP的平均百分偏差均變大,但是MBPSO的平均百分偏差基本未變,始終保持在2%以內(nèi).這表明,隨著網(wǎng)絡規(guī)模的增大,MBPSO始終能夠找到優(yōu)質(zhì)的解.

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

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

5 結(jié)束語

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

參考文獻:

[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]楊小軍.基于性能邊界和量化數(shù)據(jù)的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]齊小剛,陸贊贊,鄭耿忠,等.一種低能耗低時延的休眠調(diào)度算法[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]李國輝,馮明月,易先清.基于分群粒子群的傳感器調(diào)度方法[J].系統(tǒng)工程與電子技術(shù),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]郭文忠,蘇金樹,陳澄宇,等.無線傳感器網(wǎng)絡中帶復雜聯(lián)盟的自適應任務分配算法[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]胡旺,李志蜀.一種更簡化而高效的粒子群優(yōu)化算法[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 網(wǎng)絡出版時間:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.026

中圖分類號:TP393

文獻標識碼:A

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

網(wǎng)絡出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.023.html