一種基于離散粒子群優化的戰場動態頻譜指配策略

楊 奎

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

1 引 言

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

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

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

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

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

2.1 沖突等級

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

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

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

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

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

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

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

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

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

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

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

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

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

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

假設作戰區域內一共有n 個用頻裝備,表示為

第i 個用頻裝備可用的頻譜數為k 個,則用頻裝備構成的可用頻譜集合可表示為

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

第j 個用頻裝備可用的頻譜數為l 個,則用頻裝備構成的可用頻譜集合可表示為

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

則區域內裝備h 可能受到裝備i 和裝備j 產生的互調沖突的頻譜數集合為

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

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

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

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

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

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

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

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

設在[ t,t+Δt]時間范圍內,第i 個裝備受到裝備j 和裝備h 產生的互調沖突等級系數為h＊jh ,則有:

式中,hij為互調沖突等級系數,并有:

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

可得,第i 個裝備受到裝備j 和裝備h 產生的互調沖突等級系數矩陣為

在不考慮同頻沖突等級、鄰頻沖突等級、互調沖突等級相關權重的情況下,可得在[ t, t +Δt] 時間內,區域內其他裝備對第i 個裝備總的沖突等級系數可表示為

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

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

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

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

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

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

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

3.2 基于DPSO 的頻譜指配算法

在文獻[6-7,10]的基礎上,本文設計了用于求解戰場頻譜動態指配問題的DPSO 算法。

3.2.1 粒子的編碼方式

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

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

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

3.2.2 初始化方法

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

3.2.3 適應度函數

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

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

其中, ω1、ω2、ω3為對應的系數權值,其和等于1;f1、f2、f 3分別是滿足同頻沖突等級、鄰頻沖突等級和互調沖突等級系數的適應度函數。

3.2.4 粒子位置的更新

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

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

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

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

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

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

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

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

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

3.2.5 局部搜索策略

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

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

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

4 仿真分析

算法使用C++編碼實現,平臺環境為Windows XP Professional SP3 操作系統,開發環境為Microsoft Visual Studio 2010 ver10.0.30319.1 RTMRel。

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

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

圖3 仿真結果Fig.3 The simulation result

從圖3 中可以看出:

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

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

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

5 結束語

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

[1] 王汝群.戰場電磁環境[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] 高尚,楊靜宇, 吳小俊.求解指派問題的交叉粒子群優化算法[ J] .計算機工程與應用, 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] 談文芳,趙強,余勝陽,等.改進粒子群優化算法求解任務指派問題[J] .計算機應用,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] 陳自衛,石雄.基于遺傳算子的粒子群算法在戰場頻率分配中的應用[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] 于江,張磊.一種基于遺傳算法的戰場頻率分配方法[ J] .電訊技術, 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] 孫曉雅,林焰.一種新的離散粒子群算法在指派問題中的應用[ J] .計算機應用研究,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)