一種基于離散粒子群優(yōu)化的戰(zhàn)場動態(tài)頻譜指配策略

楊 奎

(中國西南電子技術(shù)研究所, 成都610036)

1 引 言

現(xiàn)代戰(zhàn)爭中,電子裝備種類繁多,環(huán)境電磁噪聲和人為干擾并存,多種因素疊加在有限的戰(zhàn)場區(qū)域和受限的電磁頻譜范圍內(nèi),使得戰(zhàn)區(qū)電磁環(huán)境非常復(fù)雜[1]。需要進行實時的戰(zhàn)場頻譜管理,而戰(zhàn)場頻譜管理的一個核心問題便是如何為用頻裝備動態(tài)指配頻率,提高頻譜資源的利用率[2]。

現(xiàn)有的文獻研究中,文獻[3]將粒子群算法應(yīng)用于指派問題的求解,在粒子位置更新時采用了遺傳算法粒子交叉的思想,但該算法在應(yīng)用于較大規(guī)模指配時,易陷入局部最優(yōu),出現(xiàn)早熟收斂;文獻[4]通過改進的粒子群算法求解指配問題,采用處理連續(xù)問題粒子群算法的一般公式,在粒子解更新時通過位置的排序來得到新整數(shù)排列解,這種做法沒有充分考慮到離散型組合優(yōu)化解的特點,因而會有冗余較大的問題;文獻[5-6] 以遺傳算法為基礎(chǔ)設(shè)計了一種戰(zhàn)場頻率分配算法,但其使用的二進制矩陣編碼方式不能夠較好地體現(xiàn)問題本身的特征,而且相對應(yīng)的遺傳算子的設(shè)計也沒有很好地反映搜索空間的結(jié)構(gòu)特點,因此算法不能保證獲得最小化相互干擾的分配方案。

本文通過對戰(zhàn)場頻譜指配主要限制性因素的研究,建立了一種以用頻沖突等級最小為基礎(chǔ)的頻譜動態(tài)指配數(shù)學模型,將頻譜指配問題歸結(jié)為整個戰(zhàn)場用頻裝備體系的沖突等級評價數(shù)學函數(shù)的優(yōu)化問題,并采用一種基于離散粒子群優(yōu)化算法對其進行分析和求解,能夠滿足戰(zhàn)場頻率動態(tài)指配實時高效的需求。

2 基于裝備用頻沖突等級最小的頻譜指配模型

戰(zhàn)場頻率指配問題是指為戰(zhàn)區(qū)內(nèi)所有用頻裝備按需分配頻率,并滿足一定的約束條件和需求特性。本文主要研究的是區(qū)域裝備用頻沖突最小等級頻譜指配問題(M inimum Conflict Grade FAP,MIG-FAP),它屬于Fixed-FAP,其優(yōu)化目標是在指定可用頻譜寬度范圍的基礎(chǔ)上最小化用頻裝備之間的沖突等級。

2.1 沖突等級

在求解M IG-FAP 時主要考慮兩類約束,即站內(nèi)共址約束(Co-site Constraint,CSC)和站間同頻復(fù)用約束(Adjacent-area Frequency Reuse Constraint,AA-FRC)[7],其中,CSC 是指為了保證同一站點內(nèi)的裝備之間的正常工作,裝備之間應(yīng)該間隔最小頻率距離。AA-FRC 是為了提高頻率資源利用率,不同小區(qū)(或扇區(qū))可復(fù)用統(tǒng)一頻率的最小距離間隔。兩類約束主要考慮以下3 種要素:

(1)同頻沖突等級(Same -frequency Conflict Grade,SFCG);

(2)鄰頻沖突等級(Adjacent-frequency Conflict Grade,AFCG);

(3)互調(diào)沖突等級(Intermodulation Conflict Grade,ICG)。

如果一個用頻裝備的發(fā)射信號落入另一個使用相同頻率用頻裝備的接收靈敏度范圍內(nèi),則會產(chǎn)生用頻沖突,稱為同頻沖突。設(shè)裝備A 的靈敏度PR min(dBm)和需求信噪比S/Nmin(dB),針對裝備B ,通過電波傳播分析模型,分別獲得其PRmin-S/Nmin-6、PRmin-S/Nmin、PR min -S/Nmin+3、PRmin-S/Nmin+9 的發(fā)射威力分布范圍或區(qū)域,按照如下設(shè)定規(guī)則初步判斷裝備B 對裝備A 的用頻沖突等級εabi:

(1)裝備A 位于PR min-S/N min-6 區(qū)域外,返回沖突等級εab0;

(2)裝備A 位于PRmin-S/Nmin-6 ～PRmin-S/Nmin區(qū)域內(nèi),返回沖突等級εab1;

(3)裝備A 位于PRmin-S/Nmin～PRmin-S/Nmin+3 區(qū)域內(nèi),返回沖突等級εab2;

(4)裝備A 位于PR min -S/N min +3 ～PR min -S/Nmin+9 區(qū)域內(nèi),返回沖突等級εab3;

(5)裝備A 位于PRmin-S/Nmin+9 區(qū)域內(nèi),返回沖突等級εab4。

同樣,可獲取裝備A 對裝備B 的用頻沖突等級εbai。

同理,當裝備A 和裝備B 采用相鄰頻率時,在一定條件下(主要針對CSC)將會產(chǎn)生鄰頻沖突;在Co-site 環(huán)境中,一定條件下還將產(chǎn)生互調(diào)沖突,在此省略。

在進行戰(zhàn)場用頻裝備頻譜指配時,通常可根據(jù)裝備電磁覆蓋方向,結(jié)合地理信息系統(tǒng)(GIS)來對用頻裝備的同頻沖突等級、鄰頻沖突等級和互調(diào)沖突等級的系數(shù)進行初步構(gòu)造。設(shè)裝備i 與裝備j 之間的同頻沖突等級系數(shù)為sij, 鄰頻沖突等級系數(shù)為aij,互調(diào)沖突等級系數(shù)為hij。

2.2 基于裝備間用頻沖突等級最小的頻譜指配模型

假設(shè)作戰(zhàn)區(qū)域內(nèi)一共有n 個用頻裝備,表示為

第i 個用頻裝備可用的頻譜數(shù)為k 個,則用頻裝備構(gòu)成的可用頻譜集合可表示為

式中,i =1,2, …, n;k 為第i 個用頻裝備可用的頻譜數(shù)。

第j 個用頻裝備可用的頻譜數(shù)為l 個,則用頻裝備構(gòu)成的可用頻譜集合可表示為

式中,j=1,2, …, n;l 為第j 個用頻裝備可用的頻譜數(shù)。

則區(qū)域內(nèi)裝備h 可能受到裝備i 和裝備j 產(chǎn)生的互調(diào)沖突的頻譜數(shù)集合為

其中, u±v 一般取值為1、3、5、7。

設(shè)在[ t,t+Δt]時間范圍內(nèi),第i 個裝備受到第j 個裝備的同頻沖突等級系數(shù)為s＊ij,則有:

式中,sij為同頻沖突等級系數(shù),并有:其中,m =1,2, …,l。

可得,第i 個裝備的同頻沖突等級系數(shù)矩陣為

設(shè)在[ t, t+Δt] 時間范圍內(nèi),第j 個裝備對第i個裝備的鄰頻沖突等級系數(shù)為a＊,則有:

式中,aij為鄰頻沖突等級系數(shù),并有:

其中,m =1,2, …,l。

可得,第i 個裝備的鄰頻沖突等級系數(shù)矩陣為

設(shè)在[ t,t+Δt]時間范圍內(nèi),第i 個裝備受到裝備j 和裝備h 產(chǎn)生的互調(diào)沖突等級系數(shù)為h＊jh ,則有:

式中,hij為互調(diào)沖突等級系數(shù),并有:

其中,m =1,2, …,(j+h)。

可得,第i 個裝備受到裝備j 和裝備h 產(chǎn)生的互調(diào)沖突等級系數(shù)矩陣為

在不考慮同頻沖突等級、鄰頻沖突等級、互調(diào)沖突等級相關(guān)權(quán)重的情況下,可得在[ t, t +Δt] 時間內(nèi),區(qū)域內(nèi)其他裝備對第i 個裝備總的沖突等級系數(shù)可表示為

假設(shè)需重新對區(qū)域內(nèi)用頻裝備的頻譜進行指配,可將裝備i 的全部可用頻譜看作變量,將式(7)看作裝備i 的用頻沖突等級評價函數(shù),則使式(7)的值達到最小就是對裝備i 進行頻譜指配的目標,從而將頻譜指配問題轉(zhuǎn)化為沖突等級評價函數(shù)的優(yōu)化問題。

MIG-FAP 的優(yōu)化目標是找到一種相互間沖突等級程度最小的可行分配方案,若不考慮頻譜指配中的約束條件,通過上述頻率分配的數(shù)學模型進一步總結(jié)優(yōu)化,整個區(qū)域頻譜指配的數(shù)學模型為

3 基于離散粒子群的指配算法

3.1 離散粒子群優(yōu)化算法(DPSO)

粒子群優(yōu)化算法[8]的靈感源于對鳥類捕食行為的研究。基本的PSO 算法中的粒子尋優(yōu)可用如下兩個公式表示:

其中,w 為慣性因子;r1、r2是[0,1] 之間服從均勻分布的隨機數(shù);c1、c2為學習因子,表示群體認知系數(shù),一般取(0,2)之間的隨機數(shù);k 代表迭代的次數(shù);xki為迭代k 次時粒子的空間位置;vki為迭代k 次時粒子i 的速度;pbestki表示粒子本身從初始到當前迭代次數(shù)搜索產(chǎn)生的個體極值;gbestki表示整個種群初始到當前迭代次數(shù)搜索產(chǎn)生的全局極值。

基本粒子群算法及其改進算法主要用于求解連續(xù)性問題。2004 年,Clerc[9]首次對離散問題將粒子群算法的更新公式進行修改,并指出離散粒子群算法(DPSO)的關(guān)鍵是為問題域定義與DPSO 算法相關(guān)的數(shù)學對象及其運算規(guī)則。

3.2 基于DPSO 的頻譜指配算法

在文獻[6-7,10]的基礎(chǔ)上,本文設(shè)計了用于求解戰(zhàn)場頻譜動態(tài)指配問題的DPSO 算法。

3.2.1 粒子的編碼方式

結(jié)合頻譜指配問題涉及的要素和特點,設(shè)在[ t,t+Δt]周期內(nèi),區(qū)域內(nèi)有N 個用頻裝備,每個裝備對應(yīng)一個頻率fi(i =1,2, …,N),個體用正整數(shù)序列表示, 代表一種頻譜指配方案:f =(f1, f2, …,fN)。我們采用數(shù)字符號編碼的方式, 即對每一個用頻裝備個體可用的頻譜進行編碼,如:可用頻譜數(shù)為36 個,則第1 個個體的解就是由1 ～36 個正整數(shù)組成的,編號按照頻率值從小到大的方向進行編碼。例如,對于長度為6 的個體,可用頻譜對應(yīng)向量D=(3,11,5,8,1,7)表示用頻裝備編號為1 ～6 分別對應(yīng)頻譜編號為3、11、5、8、1 和7。

這樣,對于一種頻譜指配方案,可以編碼的方式表示,同時,一種指配方案也可看成是一個粒子。這種編碼具有以下優(yōu)點:一是解碼簡潔,因為在個體所用頻譜與用頻裝備編號(即頻譜指配的解)之間存在簡單的一一對應(yīng)關(guān)系;二是清晰,對算法的運算過程便于研究和理解。

因為頻譜指配受到同頻沖突、鄰頻沖突、互調(diào)沖突以及地理位置等諸多條件的約束,因此,對于每個粒子并不一定能夠滿足要求的可行解,應(yīng)在粒子初始化時適當進行調(diào)整。

3.2.2 初始化方法

種群中的每一個個體均通過隨機的方式生成,根據(jù)需求,一個個體的每位數(shù)值從相應(yīng)的頻率編號范圍內(nèi)隨機選取。為了在粒子群初始化時分散度較好且盡量減少頻譜變更的次數(shù),我們利用先驗知識指導(dǎo)初始化過程,即初始化時盡量保證每個裝備的頻率編號各不相同(首先盡量排除同頻沖突);其次,相鄰裝備之間頻率編號間隔盡量選擇較大(盡量排除鄰頻沖突),并在初始化分配時,檢查互調(diào)沖突hij的存在性,形成一個可行解,并且在后面的所有操作中,都需保證滿足該要求。按照規(guī)定數(shù)量的粒子要求進行重復(fù)構(gòu)造,得到初始粒子群。

3.2.3 適應(yīng)度函數(shù)

在評估個體適應(yīng)度時,首先需要根據(jù)輸入的用頻裝備的數(shù)目、用途、工作模式等需求對個體進行解碼,從而獲得相對應(yīng)的分配方案,然后根據(jù)實際的沖突大小計算該頻譜指配方案的沖突等級,即公式(8)中的G。

為了將該問題轉(zhuǎn)換成最大化問題,設(shè)xi為一個可行的指配方案,X 為全部可行的指配方案的集合X =(x1, x2, …, xi),我們可以構(gòu)建下面所示適應(yīng)度函數(shù):

其中, ω1、ω2、ω3為對應(yīng)的系數(shù)權(quán)值,其和等于1;f1、f2、f 3分別是滿足同頻沖突等級、鄰頻沖突等級和互調(diào)沖突等級系數(shù)的適應(yīng)度函數(shù)。

3.2.4 粒子位置的更新

為了使得粒子在進行位置更新后所得到的新粒子法新[的1x1ki]操仍中作是交以一叉第種定頻位k 譜的代指策的配略第方[i12案 個-13粒,]本。子文我x引 們ki 為入對例一粒進種子行遺位描傳置述算更,主要操作流程如下。

(1)xki 首先與gbestki 進行交叉定位操作,產(chǎn)生新粒子Q1與Q2。為使粒子以各種不同的形式以及方向向群體最優(yōu)解趨近,我們進行粒子與群體最優(yōu)粒子的交叉操作,具體步驟如下:

首先,在初始可行解向量D 的序列中隨意抽取兩個位置點,記為P1、P2,且P2大于等于P1,設(shè)S1表示xk中從第一個元素至xk中(P1 -1)的元素, S2表示xk中從P2至xk中最后的元素,并用S3表示把pbestk中與S1、S2重復(fù)的元素剔除后剩下的元素,最后用Q1表示將S1、S2、S3合在一起構(gòu)成的新粒子;

其次,設(shè)S 4表示pbestk中從第一個元素至pbestk中(P1-1)個元素,設(shè)S5表示pbestk中從P 2至xk中最后的元素,并用S 6表示xk中與S1、S 2重復(fù)的元素剔除后剩下的元素然,最后用Q2表示將S4、S5、S 6合在一起構(gòu)成的新粒子。

設(shè)有10 個用頻裝備,可用頻譜數(shù)為10 個,編號為1 ～10,則交叉的示意圖如圖1 所示。

圖1 粒子的位置更新交叉示意圖Fig.1 Cross updating of the particle′s positions

(2)將xk與pbestk進行交叉定位操作,產(chǎn)生新粒子Q3與Q4。為使粒子以各種不同的形式以及方向向個體最優(yōu)解趨近,將粒子與個體最優(yōu)粒子進行交叉操作,相應(yīng)的操作同第1 步。

(3)為了避免粒子運算中陷入局部最優(yōu)解,對xk進行變異操作,可得到新粒子Q5與Q6。變異操作需要首先在可解碼的空間中隨機生成一個新粒子Qnew,然后再將Qnew與xk進行交叉,相應(yīng)的操作同第1 步。

(4)通過計算得到粒子Q1～Q6的適應(yīng)度分別為f 1-f 6,我們選擇其中最小適應(yīng)度的粒子Q min,并用Qmin去更新pbestki和gbestki。若Qmin的適應(yīng)度f min小于pbestki,則pbestki+1等于Qmin;若f min小于gbestki,則gbestki+1等于Qmin。

3.2.5 局部搜索策略

PSO 算法在尋找全局最優(yōu)時容易陷入局部最優(yōu)解,即出現(xiàn)早熟收斂的問題。因此,為避免粒子陷入局部極值,可以適當通過將粒子的多樣性增加,使粒子能夠跳出局部最優(yōu)。本文采用一種基于粒子群局部的搜索策略,改進3.2.4 節(jié)中位置更新后的粒子xk,主要的方法是:基于粒子位置的向量長度,選取若干對隨機位置點,再交換每對位置點的值,可得到作為下一次迭代是新的粒子位置xki+1。如對一個向量長度為10 的粒子進行局部搜索,我們選取兩對隨機位置點,同時交換兩對隨機位置點的值,即得到新的粒子位置,如圖2 所示。

圖2 粒子的局部搜索策略Fig.2 The searching policies of particle

也可隨機從6 個新粒子Q1 ～Q6中選擇1 個作為下一次迭代的粒子位置xki+1。實驗證明,采用局部搜索策略可以增加粒子群解的多樣性,使算法運行不容易出現(xiàn)早熟收斂而陷入局部最優(yōu)解。

4 仿真分析

算法使用C++編碼實現(xiàn),平臺環(huán)境為Windows XP Professional SP3 操作系統(tǒng),開發(fā)環(huán)境為Microsoft Visual Studio 2010 ver10.0.30319.1 RTMRel。

設(shè)區(qū)域內(nèi)有30 個臺站,每個臺站內(nèi)有1 ～3 臺用頻裝備等到指配頻率,即種群大小為N=30。裝備之間的限制關(guān)系已知,設(shè)可使用的頻譜數(shù)為90個,分別表示為f1、f2、f3、…、f90,則可用如下方法進行初始指配:分別取F1 =f 1, f 31, …, f61、F2 =f 2,f32, …,f62、…、F30=f30, f60, …, f90,這樣即完成30組不同頻譜向不同用頻裝備的初始指配,因此,臺站內(nèi)部可避免同頻沖突的限制。而對于用頻裝備之間的鄰頻沖突、互調(diào)沖突等,需要基于相關(guān)用頻分析算法將沖突的約束數(shù)降到最低。

測試時,臺站數(shù)目分別設(shè)為20、40 和60,且均是從某區(qū)域內(nèi)的實際用頻裝備站中隨機選出的站點。可分配的波道按照頻率從小到大依次編號為1 至200,且預(yù)設(shè)每個臺站統(tǒng)一配置3 個用頻裝備。最終指配結(jié)果表明,算法成功找到了滿足EMC 的無相互用頻沖突的分配方案,從而驗證了算法的有效性。若以算法迭代的次數(shù)來衡量找到最優(yōu)解耗費的時間,則當種群數(shù)目分別為20、40 和60 時,算法分別迭代了3 次、15 次和26 次找到最優(yōu)解,說明在有限的頻譜情況下,需求頻率越多則需要越長的時間找到最優(yōu)解。算法仿真得到的結(jié)果如圖3 所示。

圖3 仿真結(jié)果Fig.3 The simulation result

從圖3 中可以看出:

(1)當算法迭代至約50 次時,整個區(qū)域的用頻沖突等級已趨近最低,可見算法的收斂速度迅速提高;

(2)由于實際工程中,存在各種互調(diào)、鄰頻干擾,要將整個區(qū)域內(nèi)的用頻沖突完全消除將是很困難的;從圖中可看出,當運行到100 代時,其沖突等級系數(shù)仍然達不到0,但可獲得[ t, t+Δt]時間周期內(nèi)區(qū)域最小的用頻沖突等級,滿足最優(yōu)的頻譜指配需求;

(3)通過交叉、變異等離散算法的優(yōu)化及搜索策略的優(yōu)化,不但增加了粒子的多樣性,避免了陷入局部最優(yōu)解,同時算法解的收斂速度得到了大大提高,從而進一步提高了離散粒子群算法的搜索效率,且不必設(shè)置較多的參數(shù)。

5 結(jié)束語

本文針對實際戰(zhàn)場頻譜指配問題,提出了一種基于離散粒子群優(yōu)化算法的求解方法,算法迭代中采用粒子交叉定位策略,同時引入局部搜索策略更新粒子位置,這樣既保證了粒子位置可行性又增加了粒子的多樣性,避免了算法早熟收斂、陷入局部最優(yōu)解。結(jié)合實例仿真分析,證明了本文的離散粒子群算法具有較好的收斂性。針對不同的問題實例,將存在最優(yōu)的參數(shù)配置,可將算法的權(quán)重系數(shù)進行適度的調(diào)整,以取得更好的收斂效果,對于參數(shù)的優(yōu)化將在后續(xù)工作中進行。

[1] 王汝群.戰(zhàn)場電磁環(huán)境[M] .北京:解放軍出版社,2006:56.

WANG Ru-qun.Battlefield Electromagnetic Environment[M] .Beijing:Publishing Company of PLA,2006:56.(in Chinese)

[2] 王宇飛.無線電頻譜分配新概念[ J] .艦船電子工程,2007,27(3):17-19

WANG Yu-fei.A New Method of Spectrum Access[J] .Ship Electronic Engineering,2007, 27(3):17-19.(in Chinese)

[ 3] 高尚,楊靜宇, 吳小俊.求解指派問題的交叉粒子群優(yōu)化算法[ J] .計算機工程與應(yīng)用, 2004, 40(8):54-55.

GAO Shang,YANG Jing-yu,WU Xiao-jun.Using Particle Swarm Optimization Algorithm with Crossover to Solve Assignment Problem[ J] .Computer Engineering and Applications,2004,40(8):54-55.(in Chinese)

[ 4] 談文芳,趙強,余勝陽,等.改進粒子群優(yōu)化算法求解任務(wù)指派問題[J] .計算機應(yīng)用,2007,27(12):2892-2895.

TAN Wen-fang, ZHAO Qiang, YU Sheng -yang, et al.Solving task assignment problem based on improved particle swarm optimization algorithm[ J] .Journal of Computer Applications, 2007, 27(12):2892-2895.(in Chinese)

[ 5] 陳自衛(wèi),石雄.基于遺傳算子的粒子群算法在戰(zhàn)場頻率分配中的應(yīng)用[J] .艦船電子工程,2010,30(3):73-76.

CHEN Zi-wei, SHI Xiong.Application of Particle Swarm Optimization Based on Genetic Operator in Frequency Assignment on Battlefield[ J] .Ship Electronic Engineering, 2010,30(3):73-76.(in Chinese)

[ 6] 于江,張磊.一種基于遺傳算法的戰(zhàn)場頻率分配方法[ J] .電訊技術(shù), 2011, 51(7):90-96.

YU Jiang, ZHANG Lei.A Battlefield Frequency Assignment Method Based on Genetic Algorithm[ J] .Telecommunication Engineering, 2011, 51(7):90-96.(in Chinese)

[7] Smith D H, Taplin R K,Hurley S.Frequency Assignment with Complex Co-Site Constraints[ J] .IEEE Transactions on Electromagnetic Compatibility,2001,43(2):210-218.

[8] Eberhartr R C, Kenndy J.A new optim izier using particle swarm theory[C]//Proceedings of the 6th International Symposium on Micro Machine and Human Science.New York:IEEE, 1995:39-43.

[9] Clerc M.Discrete particle swarm optimization[ M] .Berlin:Springer Verlag,2004:219-240.

[10] 孫曉雅,林焰.一種新的離散粒子群算法在指派問題中的應(yīng)用[ J] .計算機應(yīng)用研究,2009,26(11):4091-4094.

SUN Xiao-ya, LIN Yan.Using new DPSO algorithm to solve assignment problem[J] .Application Research of Computers,2009,26(11):4091-4094.(in Chinese)