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

謝佑波 陳正義

（海軍指揮學(xué)院 南京 210016）

1 引言

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

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

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

PSO算法中的一個(gè)粒子就對(duì)應(yīng)覓食過(guò)程中的一只鳥(niǎo)，解空間就是覓食區(qū)域，最優(yōu)解就是食物所在的位置。鳥(niǎo)類(lèi)可以感知離食物最近的位置，算法中用適應(yīng)度函數(shù)來(lái)實(shí)現(xiàn)這種功能。通過(guò)適應(yīng)度函數(shù)，粒子當(dāng)前位置與它經(jīng)歷過(guò)的最好位置進(jìn)行比較，得出更好的位置；同樣也與群體內(nèi)所有粒子最好的位置比較，往最好粒子的方向變化，通過(guò)反復(fù)的迭代運(yùn)算，可得到所有粒子的最好位置。

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

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

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

然而在時(shí)隙分配問(wèn)題上，粒子向最優(yōu)位置進(jìn)化是通過(guò)不斷調(diào)整時(shí)隙位置來(lái)實(shí)現(xiàn)的，傳統(tǒng)的速度向量無(wú)法對(duì)這一變化做定義，因此必須對(duì)其進(jìn)行改進(jìn)。

3 改進(jìn)的混合粒子群在數(shù)據(jù)鏈時(shí)隙分配中的應(yīng)用

3.1 改進(jìn)的混合粒子群算法

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

圖1 混合PSO算法流程圖

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

1）交叉操作示意

個(gè)體通過(guò)和個(gè)體最優(yōu)以及群體最優(yōu)的粒子進(jìn)行交叉來(lái)更新，隨機(jī)兩個(gè)交叉位置，設(shè)交叉位置是2和5，操作如下：

個(gè)體中2～5號(hào)時(shí)隙用極值的2～5號(hào)時(shí)隙替代，如果新個(gè)體有元素重復(fù)，則重復(fù)的元素用未出現(xiàn)的元素替代：

2）變異操作示意

變異采用個(gè)體內(nèi)部交換元素的方法，隨機(jī)選擇兩個(gè)變異位，設(shè)變異位是3和8，交換第3和第8個(gè)元素的位置：

只有產(chǎn)生的新個(gè)體適應(yīng)度更優(yōu)時(shí)，才得到保留。

3.2 數(shù)據(jù)鏈系統(tǒng)調(diào)度抖動(dòng)的計(jì)算

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

針對(duì)數(shù)據(jù)鏈時(shí)隙分配，調(diào)度抖動(dòng)是指分配給同一節(jié)點(diǎn)的所有時(shí)隙，相鄰時(shí)隙之間距離的方差［4］，表示了時(shí)延的變化情況，又稱(chēng)時(shí)延抖動(dòng)。節(jié)點(diǎn)i在數(shù)據(jù)鏈網(wǎng)絡(luò)中的調(diào)度抖動(dòng)可由下式計(jì)算：

式中L為時(shí)幀長(zhǎng)度，ni為分配給節(jié)點(diǎn)i的時(shí)隙數(shù)，為第j個(gè)相鄰時(shí)隙的間隔。

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

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

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

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

由式（2）即可算出節(jié)點(diǎn)i的調(diào)度抖動(dòng)γi，網(wǎng)絡(luò)的調(diào)度抖動(dòng)為各個(gè)節(jié)點(diǎn)調(diào)度抖動(dòng)的平均值，因此適應(yīng)度函數(shù)為

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

4 算法實(shí)現(xiàn)及仿真

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

實(shí)驗(yàn)一：以對(duì)Link16數(shù)據(jù)鏈時(shí)隙池分配為例在1536個(gè)時(shí)隙當(dāng)中為一個(gè)節(jié)點(diǎn)分配5個(gè)時(shí)隙。

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

圖2 收斂曲線(xiàn)

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

實(shí)驗(yàn)二：設(shè)時(shí)幀長(zhǎng)度為32個(gè)時(shí)隙，為4個(gè)節(jié)點(diǎn)分配時(shí)隙，時(shí)隙需求分別為5、5、6、6，迭代200次，種群規(guī)模為20個(gè)粒子。

進(jìn)行10次仿真，調(diào)度抖動(dòng)分別為0.4144、0.3311、0.6478、1.0311、0.6811、0.8478、0.3144、0.7978、0.3527、0.4811。最大值1.0311在第4次出現(xiàn)，可見(jiàn)第4次仿真的結(jié)果最差；最小值0.3144出現(xiàn)在第7次，仿真的結(jié)果最理想。

若利用二叉樹(shù)時(shí)隙劃分法，以時(shí)隙池形式為節(jié)點(diǎn)分配時(shí)隙，則一種最好的分配結(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）計(jì)算可得到調(diào)度抖動(dòng)為4.736。

10次仿真結(jié)果中即便是最差的那次，也遠(yuǎn)遠(yuǎn)比二叉樹(shù)分配得到的結(jié)果好。可見(jiàn)，這種基于混合粒子群算法的固定時(shí)隙分配方式，對(duì)調(diào)度抖動(dòng)的降低效果顯著。

5 結(jié)語(yǔ)

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