基于混合粒子群優(yōu)化的數據鏈時隙分配算法*

謝佑波 陳正義

（海軍指揮學院 南京 210016）

1 引言

粒子群優(yōu)化（PSO）算法是由Kennedy和Eber?hart在1995年首次提出的一種基于群智能的優(yōu)化算法，是對鳥類覓食的社會行為的模擬。PSO算法的核心思想是，從一組隨機解出發(fā)，通過追隨當前搜索到的“群體最優(yōu)解”和“個體最優(yōu)解”來尋找全局最優(yōu)解，并用合適的適應度函數來評價。該算法不需要待優(yōu)化函數有可導、可微等要求，很容易在計算機上實現。另外PSO算法操作簡單、涉及參數少、收斂速度快，且無需過多的初始信息也能得到較優(yōu)的結果。因此，PSO算法的應用越來越廣，比如函數優(yōu)化、神經網絡訓練、模糊系統(tǒng)控制、求解大規(guī)模組合優(yōu)化問題以及遺傳算法所應用的各個領域，都能用到PSO算法。本文提出一種數據鏈的基于最小調度抖動的混合時隙分配方式，在為節(jié)點的固定報文需求分配時隙時，利用了加入遺傳思想的PSO算法來求解，以保證數據鏈網絡的調度抖動最小，并進行仿真實驗驗證了該算法的可行性。

2 粒子群優(yōu)化算法基本原理

粒子群優(yōu)化算法源于對鳥類覓食過程的研究：一群鳥在固定的區(qū)域內覓食，群內個體并不知道食物具體的位置，但是它們知道當前位置和之前經歷過的最好位置哪個離食物所在的位置更近，并且能通過群體的信息傳遞得知哪只鳥離食物最近，每只鳥就根據自身經歷過的最好位置以及群體中離食物最近的鳥的指引，不斷地調整飛行方向，逐漸向食物所在地靠近，最終群內所有鳥都能在食物附近聚攏［1］。

PSO算法中的一個粒子就對應覓食過程中的一只鳥，解空間就是覓食區(qū)域，最優(yōu)解就是食物所在的位置。鳥類可以感知離食物最近的位置，算法中用適應度函數來實現這種功能。通過適應度函數，粒子當前位置與它經歷過的最好位置進行比較，得出更好的位置；同樣也與群體內所有粒子最好的位置比較，往最好粒子的方向變化，通過反復的迭代運算，可得到所有粒子的最好位置。

用數學語言描述：假設待優(yōu)化問題的解是N維的，則任何一個解向量可表示為Xi=｛xi1，…，xip，…，xiN｝。算法初始，設種群規(guī)模有M個粒子，每個粒子的位置都表示解空間中一個隨機解Xi（t），位置隨著迭代次數t的增加而變化；另外粒子還有一個表示飛行狀態(tài)的速度向量Vi（t），也隨著迭代次數的增加變化著。粒子的初始狀態(tài)Xi（0）和Vi（0）由算法初始隨機生成。其中速度向量Vi（t）受兩個極值影響，一個是個體在t次迭代中經歷過的最優(yōu)位置Pi（t），另一個是群體中所有粒子在迭代中經歷過的最優(yōu)位置G（t），位置的優(yōu)劣由適應度函數計算。

由此，Kennedy和Eberhart提出了原始PSO算法的核心公式：

式中rand（）表示0～1之間的隨機數，C1、C2是學習因子，一般取固定值2，Vmax為位置變化的極值。

然而在時隙分配問題上，粒子向最優(yōu)位置進化是通過不斷調整時隙位置來實現的，傳統(tǒng)的速度向量無法對這一變化做定義，因此必須對其進行改進。

3 改進的混合粒子群在數據鏈時隙分配中的應用

3.1 改進的混合粒子群算法

傳統(tǒng)的PSO算法通過追隨個體極值和群體極值完成最優(yōu)解的搜尋，操作簡單，能較快收斂，但隨著迭代次數的增加，容易陷入局部最優(yōu)解，且對于涉及元素位置交換之類的問題，粒子的速度難以表達，因此引入遺傳算法中的交叉和變異操作來替代傳統(tǒng)PSO算法追隨極值的動作。加入了遺傳思想的混合粒子群優(yōu)化算法流程圖如圖1所示。

圖1 混合PSO算法流程圖

設某時幀包含8個時隙，為3個節(jié)點進行分配，節(jié)點編號分別為1、2、3，節(jié)點的時隙需求分別為1、2、3，要求抖動最小，適應度函數就是網絡的調度抖動。該問題的解可用一個8維的向量表示，比如Xi=｛3，1，4，5，7，8，2，6｝，該向量中第1位的3表示給第一個節(jié)點分配的時隙位置，2到3位是給第二個節(jié)點分配的時隙位置，第三個節(jié)點分到的三個時隙位置是分別是5，7，8，還有2和6號時隙空閑。

1）交叉操作示意

個體通過和個體最優(yōu)以及群體最優(yōu)的粒子進行交叉來更新，隨機兩個交叉位置，設交叉位置是2和5，操作如下：

個體中2～5號時隙用極值的2～5號時隙替代，如果新個體有元素重復，則重復的元素用未出現的元素替代：

2）變異操作示意

變異采用個體內部交換元素的方法，隨機選擇兩個變異位，設變異位是3和8，交換第3和第8個元素的位置：

只有產生的新個體適應度更優(yōu)時，才得到保留。

3.2 數據鏈系統(tǒng)調度抖動的計算

在通信系統(tǒng)中，時延抖動反映了通信系統(tǒng)的最差情況，抖動越大，說明通信系統(tǒng)越不穩(wěn)定［2］。在數據鏈傳輸音頻、視頻等多媒體報文時，調度抖動的影響更加明顯，一般抖動大于80ms，就視為此類報文難以正確地被接收并理解。例如在數據鏈支持下的空戰(zhàn)中，戰(zhàn)機之間的信息交互通常是通過語音信號的實時傳輸來實現，抖動過大會導致語言信號產生嚴重偏差，使接收方無法正確理解發(fā)信方的戰(zhàn)術意圖，使戰(zhàn)術數據鏈的優(yōu)勢無法體現。另外，Baruah S等［3］也提到，預警機在完成對特定目標的監(jiān)視任務時，若抖動大于時延的10%，對目標的定位誤差就將超過100m，這對目標識別、跟蹤以及導彈的精確打擊都非常不利。因此，抖動是戰(zhàn)術數據鏈效能研究時不可忽略的因素。

針對數據鏈時隙分配，調度抖動是指分配給同一節(jié)點的所有時隙，相鄰時隙之間距離的方差［4］，表示了時延的變化情況，又稱時延抖動。節(jié)點i在數據鏈網絡中的調度抖動可由下式計算：

式中L為時幀長度，ni為分配給節(jié)點i的時隙數，為第j個相鄰時隙的間隔。

3.3 混合粒子群優(yōu)化算法在數據鏈時隙分配中的應用

Link16數據鏈網絡中的報文根據不同的產生特點，可分為兩類：固定報文和緊急報文。網絡運行期間，固定報文的產生具有一定的規(guī)律，時隙需求也往往可以準確預測，每個報文用來完成諸如作戰(zhàn)單元狀態(tài)報告、武器系統(tǒng)狀態(tài)報告、航跡報告以及戰(zhàn)場態(tài)勢報告等功能。此類報文可在固定時隙分配規(guī)劃階段獲取一定數量的時隙。

用混合粒子群優(yōu)化算法解決固定時隙分配問題時，適應度函數為系統(tǒng)的調度抖動。設時幀長度為L，網絡中m個節(jié)點有固定報文的發(fā)送需求，ni為第i個節(jié)點的固定報文時隙需求量，節(jié)點的總需求量M滿足：

設分給節(jié)點i的ni個時隙在一幀中的位置分別為，則相鄰時隙間的距離為

由式（2）即可算出節(jié)點i的調度抖動γi，網絡的調度抖動為各個節(jié)點調度抖動的平均值，因此適應度函數為

在算法初期先確定粒子數目，對其按以上方法進行編碼，各個粒子初始化，即對解向量中的元素進行隨機排序。根據式（3）和（5）計算各粒子的適應度，選取適應度最優(yōu)的粒子作為群體最優(yōu)粒子，對各個粒子進行交叉、變異操作，產生新粒子與原粒子適應度值比較，保留適應度值更優(yōu)的粒子，更新粒子群，一次迭代結束。當適應度值滿足一定的要求，或者迭代次數達到一定值，即可結束迭代，輸出時隙分配的結果。

4 算法實現及仿真

本文用Matlab軟件編寫固定時隙分配的程序，程序的運行方式是在命令窗口輸入［xm，fv］=PSO（@fitness，M，N，L，n），這里M表示迭代次數，N表示粒子數目，L就是時幀長度，n是一個矩陣，輸入形式為［n1n2…nN］，ni表示節(jié)點i固定報文的時隙需求。

實驗一：以對Link16數據鏈時隙池分配為例在1536個時隙當中為一個節(jié)點分配5個時隙。

迭代次數為500次，粒子數取50。得到5個時隙分別為260、558、858、1184和1500。數字表示所分配的時隙在時幀中的位置。收斂曲線如圖2所示。

圖2 收斂曲線

算法在250次左右的時候，調度抖動降到了138.56，遠遠優(yōu)于用時隙池方式所分配的結果。從收斂曲線可看出，多數的迭代，調度抖動并沒有變化，是因為在1536個時隙中進行交叉變異操作，而對粒子適應度值有影響的就5個時隙，很有可能所作的操作正好沒有影響這5個被選時隙的位置，即便影響到了，也可能因為適應度值沒有更優(yōu)而放棄該變化。若繼續(xù)增加迭代次數，這5個時隙位置變動的機會就更大，能得到更優(yōu)的解。理論上最優(yōu)的時隙間隔應該是307、307、307、307和308，調度抖動為0.16，隨著迭代次數的增加，會一直往這個數值靠攏。然而在實際應用中，適度的抖動對信息的理解并無影響，保留一定程度的調度抖動同樣可以完成數據鏈通信任務，反之若追求最理想的解，往往花費更多的時間在迭代的運算上，很可能導致信息無法及時發(fā)送，造成數據丟失。另外，在給多個節(jié)點同時分配時隙時，人工計算就很難在短時間內得到一個較優(yōu)的解，無法滿足數據鏈報文的實時性需求，借助計算機，設置最大的迭代次數，通過該算法就能在短時間內得到一個較優(yōu)的解。

實驗二：設時幀長度為32個時隙，為4個節(jié)點分配時隙，時隙需求分別為5、5、6、6，迭代200次，種群規(guī)模為20個粒子。

進行10次仿真，調度抖動分別為0.4144、0.3311、0.6478、1.0311、0.6811、0.8478、0.3144、0.7978、0.3527、0.4811。最大值1.0311在第4次出現，可見第4次仿真的結果最差；最小值0.3144出現在第7次，仿真的結果最理想。

若利用二叉樹時隙劃分法，以時隙池形式為節(jié)點分配時隙，則一種最好的分配結果為X1=｛1，5，9，17，25｝，X2=｛2，6，10，18，26｝，X3=｛3，7，11，15，19，27｝，X4=｛4，8，12，16，20，28｝。由式（1）計算可得到調度抖動為4.736。

10次仿真結果中即便是最差的那次，也遠遠比二叉樹分配得到的結果好?？梢?，這種基于混合粒子群算法的固定時隙分配方式，對調度抖動的降低效果顯著。

5 結語

針對數據鏈時隙分配方法，本文提出了一種基于改進混合粒子群算法數據鏈時隙分配方法。該方法引入遺傳算法中的交叉和變異操作來替代傳統(tǒng)PSO算法追隨極值的動作，對混合粒子群算法進行優(yōu)化，使得數據鏈調度抖動大大降低，提高數據鏈的戰(zhàn)技術性能。仿真結果證明提出的分配方法能夠有效降低數據鏈調度抖動。