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

謝佑波 陳正義

（海軍指揮學院 南京 210016）

1 引言

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

2 粒子群優化算法基本原理

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

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

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

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

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

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

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

3.1 改進的混合粒子群算法

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

圖1 混合PSO算法流程圖

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

1）交叉操作示意

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

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

2）變異操作示意

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

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

3.2 數據鏈系統調度抖動的計算

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

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

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

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

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

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

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

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

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

4 算法實現及仿真

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

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

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

圖2 收斂曲線

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

實驗二：設時幀長度為32個時隙，為4個節點分配時隙，時隙需求分別為5、5、6、6，迭代200次，種群規模為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次，仿真的結果最理想。

若利用二叉樹時隙劃分法，以時隙池形式為節點分配時隙，則一種最好的分配結果為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 結語

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