郭 彥 于 錢 張世偉
(1.海軍航空兵學院 葫蘆島 125001)(2.92941部隊95分隊 葫蘆島 125001) (3.海軍工程大學 武漢 430033)
?
基于遺傳算法的艦艇編隊通信組網(wǎng)拓撲結(jié)構(gòu)優(yōu)化研究*
郭彥1于錢2張世偉3
(1.海軍航空兵學院葫蘆島125001)(2.92941部隊95分隊葫蘆島125001) (3.海軍工程大學武漢430033)
針對當前海上艦艇編隊作戰(zhàn)力量多元化以及作戰(zhàn)環(huán)境復雜多變等特點,通過分析艦艇編隊通信的實際需求,分別構(gòu)建了拓撲結(jié)構(gòu)模型、優(yōu)化目標模型以及問題模型,并提出基于遺傳算法的艦艇編隊通信組網(wǎng)拓撲結(jié)構(gòu)優(yōu)化方法,從而解決了通信節(jié)點間的拓撲結(jié)構(gòu)編碼困難和優(yōu)化效率低等問題,實現(xiàn)了艦艇編隊通信組網(wǎng)拓撲結(jié)構(gòu)的優(yōu)化。實例應用表明:遺傳算法能夠很好地解決艦艇編隊通信網(wǎng)絡拓撲結(jié)構(gòu)優(yōu)化問題,且優(yōu)化結(jié)果好于傳統(tǒng)拓撲結(jié)構(gòu)方案。方法的研究有利于提升艦艇編隊的綜合作戰(zhàn)保障能力,對探索信息化條件下艦艇編隊通信組網(wǎng)方式具有重要的參考價值。
艦艇編隊; 通信組網(wǎng); 拓撲結(jié)構(gòu); 優(yōu)化方法; 遺傳算法
Class NumberTP301.6; TN915
隨著信息化海戰(zhàn)的迅速發(fā)展,現(xiàn)有通信保障方式已不能滿足艦艇編隊實際作戰(zhàn)需求。同時,當前新型數(shù)據(jù)鏈通信裝備的研發(fā)和應用為艦艇編隊通信組網(wǎng)優(yōu)化方法的研究創(chuàng)造了條件。針對當前艦艇編隊合同作戰(zhàn)樣式,綜合分析作戰(zhàn)區(qū)域中的各水面艦艇平臺、艦載機平臺等各個通信節(jié)點的實際通信需求及特點,對艦艇編隊多層次通信網(wǎng)絡拓撲結(jié)構(gòu)進行優(yōu)化研究,以實現(xiàn)時隙的空間復用,降低對中心節(jié)點通信設備支持節(jié)點數(shù)的需求,同時增強信息傳輸?shù)膶崟r性和可靠性,使得優(yōu)化后的通信網(wǎng)絡拓撲結(jié)構(gòu)更適合于艦艇編隊合同作戰(zhàn)的實際應用需求。
用于拓撲結(jié)構(gòu)優(yōu)化的方法可以分為兩類:傳統(tǒng)優(yōu)化方法和智能優(yōu)化方法。傳統(tǒng)優(yōu)化方法主要有數(shù)學規(guī)劃法、枚舉法、變分法等[1~3]。傳統(tǒng)優(yōu)化方法需要有嚴格的理論基礎或者一定工程經(jīng)驗與直覺,在一定條件下能收斂到最優(yōu)解,但它要求問題能顯式表示,大多數(shù)還要求變量、目標函數(shù)和約束條件連續(xù),而實際工程結(jié)構(gòu)優(yōu)化很難滿足要求。對于大型拓撲結(jié)構(gòu)優(yōu)化問題,該類方法的收斂性差,計算時間長,優(yōu)化效率低,在實際應用上具有較大的局限性?;谏镞M化理論的智能優(yōu)化算法主要有粒子遺傳算法、群優(yōu)化算法、神經(jīng)網(wǎng)絡算法等[4~6],該類算法適用于解決大型復雜的拓撲結(jié)構(gòu)優(yōu)化問題[7]。艦艇編隊通信網(wǎng)絡復雜多變,其拓撲結(jié)構(gòu)優(yōu)化是一個NP難問題,因此應采用智能優(yōu)化算法解決艦艇編隊通信組網(wǎng)拓撲結(jié)構(gòu)優(yōu)化問題。
針對艦艇編隊通信節(jié)點分布的特點,以兩兩節(jié)點間是否建立通信鏈路的布爾值獲取二進制編碼,建立遺傳個體模型,并以通信時延、綜合互通性、抗毀性為目標,采用遺傳優(yōu)化算法對艦艇編隊通信組網(wǎng)拓撲結(jié)構(gòu)進行優(yōu)化,以實現(xiàn)艦艇編隊通信組網(wǎng)的精確化、實時化和高效化。
2.1拓撲結(jié)構(gòu)模型
對于艦艇編隊通信網(wǎng)絡拓撲結(jié)構(gòu)而言,各水面艦艇以及艦載機將根據(jù)任務需求被部署到指定位置,各通信節(jié)點的位置是確定的,因此通信網(wǎng)絡拓撲結(jié)構(gòu)中的節(jié)點位置是固定的,需要解決的問題是通信鏈路的建立。
為了方便拓撲結(jié)構(gòu)模型的建立,通信網(wǎng)絡節(jié)點和通信連接使用圖的結(jié)構(gòu)表示:
G=(V,A)
(1)
其中V={c1,c2,…,cn}表示通信節(jié)點的集合,節(jié)點包括普通節(jié)點和中心節(jié)點兩種;A={(i,j)|i,j∈V}表示通信鏈路的集合。除了中心節(jié)點外(子網(wǎng)內(nèi)所有節(jié)點均與中心節(jié)點建立通信鏈路),在其他通信節(jié)點間選擇建立通信鏈路。
2.2目標模型
艦艇編隊通信組網(wǎng)優(yōu)化目標主要有通信時延(多跳導致)、綜合互通性、抗毀性等[8~9]。增大時延可提高資源利用率,而過大的時延則會降低網(wǎng)絡的抗毀性,影響正常通信。另外,對于艦艇編隊協(xié)同通信組網(wǎng),節(jié)點的連通是完成通信組網(wǎng)的基礎,而抗毀性是軍事通信網(wǎng)絡安全的基本保證。
1) 通信時延
在通信網(wǎng)絡結(jié)構(gòu)中,距離較遠的兩個通信節(jié)點間的通信需要通過一個或多個中繼節(jié)點才能完成,因此在通信過程中經(jīng)過的中繼節(jié)點越多通信時延越大。通信時延對通信的實時性有較大影響,是艦艇編隊通信組網(wǎng)的重要指標。通信時延表示為
(2)
式中,Pdelay為所有時延的總和,delay(ci)表示通信節(jié)點ci的通信時延,即通信節(jié)點ci與其他建立通信關系的節(jié)點的總時延。
這里不考慮由時隙分配產(chǎn)生的通信時延,只考慮通由通信設備性能產(chǎn)生的時延。因此,通過節(jié)點的鏈路數(shù)來計算通信時延,節(jié)點作為中繼產(chǎn)生的時延表示為
delay(ci)=tci·dci
(3)
式中,tci表示通信節(jié)點ci存在通信鏈路的數(shù)量,dci表示通信節(jié)點ci作為中繼節(jié)點的平均通信時延。
2) 連通度
為了保證信息的暢通和共享,關鍵是要保證節(jié)點間通信鏈路的連通。綜合連通度用來衡量所有節(jié)點兩兩間的通信能力,數(shù)學表示如下
(4)
(5)
式中,Pconnect∈(0,1),表示通信網(wǎng)絡的綜合連通度。connect(ci,cj)表示節(jié)點ci與節(jié)點cj的連通性。
3) 抗毀性
抗毀性是指當某個通信節(jié)點遭到破壞時,整個通信網(wǎng)絡維持正常通信的能力??箽耘c可維持通信的節(jié)點的數(shù)量有關,數(shù)學表示為
(6)
(7)
destroy(cj,ck)=1-connect(cj,ck)
(8)
式中,Pdestroy∈(0,1)表示抗毀性,其值越大表示抗毀能力越強;des(ci)表示節(jié)點ci遭到破壞后無法通信的程度。
2.3問題模型
通過在各節(jié)點間選擇建立通信鏈路使得以上各目標達到最佳優(yōu)化,通信建立的約束為節(jié)點的距離,超過通信設備限制通信距離的節(jié)點間將不能建立通信鏈路。艦艇編隊通信組網(wǎng)拓撲結(jié)構(gòu)優(yōu)化問題模型可表示為
minf(A)=minf(Pdelay,Pconnect,Pdestroy)
(9)
(10)
其中,minf(Pdelay,Pconnect,Pruin)表示目標優(yōu)化函數(shù),dis(i,j)表示節(jié)點i與節(jié)點j的距離,dmax表示通信設備所允許的最大通信距離;cp為中心節(jié)點,cq為普通節(jié)點。
艦艇編隊通信網(wǎng)絡的拓撲結(jié)構(gòu)是一個有中心與無中心相結(jié)合的多鏈路復雜網(wǎng)狀結(jié)構(gòu)。在距離滿足通信要求的情況下,任意兩個節(jié)點之間均可根據(jù)需要建立通信鏈路。因此,在建立通信鏈路時,不僅要考慮各個目標的優(yōu)化情況,還要考慮各節(jié)點間的通信距離,并根據(jù)距離確定通信中心節(jié)點。
由于通信節(jié)點的位置已經(jīng)根據(jù)作戰(zhàn)需任務被確定,因此只需要解決通信組網(wǎng)的中心節(jié)點的確定和通信鏈路的建立問題。首先根據(jù)各通信節(jié)點間的距離和通信節(jié)點的特性選定中心節(jié)點,并找出不能建立通信鏈路的節(jié)點。節(jié)點間的通信鏈路建立情況用“0-1”模型表示,剛好與遺傳算法的二進制編碼相一致[10],使得遺傳編碼更加簡單。
3.1基于遺傳算法的拓撲結(jié)構(gòu)優(yōu)化方法
以兩兩節(jié)點間是否建立通信鏈路的布爾值為單位進行染色體編碼,完成遺傳個體的建模。由于在通信組網(wǎng)拓撲結(jié)構(gòu)建立過程中,有些節(jié)點間不能建立通信鏈路,所以在染色體編碼的時候要將這些基因的值置為“0”。但染色體在進化(選擇、交叉和變異)過程中,難以保證這些特殊的基因符合值為“0”的要求。因此,對于不符合要求的染色體將采取淘汰機制。
方法在確定中心節(jié)點的基礎上,使用遺傳算法完成拓撲結(jié)構(gòu)的優(yōu)化。在變異過程中,如果產(chǎn)生不符合要求的個體,將繼續(xù)選擇個體進行交叉,直到產(chǎn)生個體的數(shù)量達到種群規(guī)模。
3.2算法設計
1) 距離計算
計算各節(jié)點間的距離,統(tǒng)計超過通信距離的節(jié)點。根據(jù)通信節(jié)點間距離和通信節(jié)點的分布特點,選定中心節(jié)點,并為節(jié)點進行編號。艦艇編隊艦空協(xié)同通信根據(jù)任務需要,中心節(jié)點一般被預先設定。
2) 遺傳編碼
將所用通信節(jié)點進行兩兩匹配,建立通信鏈路用“1”表示,未建立通信鏈路用“0”表示,從而用一個二進制字符串表示所有節(jié)點的匹配結(jié)果,如圖1所示。
圖1染色體編碼
其中ek∈{0,1},cicj表示節(jié)點i和節(jié)點j建立通信鏈路。每個染色體表示通信網(wǎng)絡拓撲結(jié)構(gòu)的一種組網(wǎng)方案。
3) 遺傳操作
在遺傳算法中,通過編碼組成初始種群后,遺傳操作就是根據(jù)對環(huán)境的適應度對染色體施加一定的操作,從而實現(xiàn)優(yōu)勝劣汰的進化。遺傳操作包括三個遺傳算子:選擇、交叉和變異。
(1)選擇操作
選擇操作建立在適應度評價的基礎上,用來實現(xiàn)對群體中個體的優(yōu)勝劣汰操作,即適應度高的個體被遺傳到下一代群體中的概率大。最常見的選擇算法為輪盤賭算法,輪盤賭又稱比例選擇算子[70]。在輪盤賭算法中,各個體被選中的概率與適應值(適應值為正)大小成正比。設群體規(guī)模為M,個體i的適應度為fi,則個體i被選中(染色體基因被遺傳到下一代)的概率為
(11)
(2)交叉操作
交叉是遺傳算法的核心算子,這里對染色體采取1-top交換操作(單點交叉)[11]。選擇一個交叉點(基因位),子代染色體在交叉點前面的基因從一個父代基因得到,而后面的部分則從另一個父代基因那里得到。1-top交叉示意如圖2所示。
圖2 交叉操作
(3)變異操作
通過變異算子增強遺傳算法的全局搜索能力,防止算法因過早收斂而錯過全局最優(yōu)解。變異操作示意圖如圖3所示。
圖3 變異操作
4) 適應度評價
通過適當權(quán)重,綜合考慮各個優(yōu)化目標,構(gòu)造適應度函數(shù)。其中pconnect,Pdestroy∈(0,1),為了量綱對適應度函數(shù)的影響,需要將Pdelay限制在區(qū)間(0,1),做如下處理:
(12)
Ptotal為通信資源總量,構(gòu)造一個拓撲結(jié)構(gòu)的最小優(yōu)化的適應度函數(shù)如下
(13)
3.3算法流程
在選定中心節(jié)點的基礎上,利用遺傳算法的編碼簡單和尋優(yōu)效率高的特點,提出基于遺傳算法的艦艇編隊通信網(wǎng)絡拓撲結(jié)構(gòu)優(yōu)化方法,算法流程如圖4所示。
圖4 算法流程
步驟1:選定中心節(jié)點。如果在布置任務中未指定中心節(jié)點,則在獲取各節(jié)點間距離的基礎上,根據(jù)通信最大限制距離,選定中心節(jié)點;
步驟2:遺傳編碼。將通信網(wǎng)絡節(jié)點間是否建立鏈路的布爾值作為遺傳算法的二進制編碼值;
步驟3:算法初始化。根據(jù)實際問題對算法參數(shù)進行初始化;
步驟4:產(chǎn)生初始種群。根據(jù)問題規(guī)模設定初始種群,并隨機初始化,種群規(guī)模一般設置為10至20;
步驟5:計算種群個體適應度。通過適應度函數(shù)計算種群個體的適應度,并記錄最優(yōu)個體;
步驟6:選擇操作。使用輪盤賭算法在種群中選取2個個體;
步驟7:交叉操作。隨機生成交叉位置,進行交叉生成子代個體;
步驟8:變異操作。對子代個體的某個基因進行隨機變異,對不滿足要求的個體執(zhí)行步驟6;
步驟9:生成子種群。經(jīng)過步驟6、步驟7和步驟8獲取的個體達到種群規(guī)模,則結(jié)束遺傳操作,否則轉(zhuǎn)至步驟6;
步驟10:求出最優(yōu)解。通過迭代次數(shù)控制算法結(jié)束,迭代次數(shù)達到預設則從當前種群中選取最優(yōu)個體作為最終解,否則轉(zhuǎn)至步驟5。
4.1仿真實例
實例可抽象描述為:假設在某次海上作戰(zhàn)中,根據(jù)任務需求,出動9個作戰(zhàn)平臺(包括艦載直升機和水面艦艇,均視為通信節(jié)點)執(zhí)行任務,其中8個作戰(zhàn)平臺被分成4個編組,1架直升機為預警直升機,作為中心節(jié)點。受實際通信距離限制,其中節(jié)點1與節(jié)點7、節(jié)點1與節(jié)點8、節(jié)點2與節(jié)點7、節(jié)點2與節(jié)點8不能進行通信。各節(jié)點存在的通信時延如表1所示,設中心節(jié)點時延為8。
圖5 通信節(jié)點分布實例示意圖
節(jié)點通信時延節(jié)點通信時延節(jié)點通信時延18457327548103669
4.2傳統(tǒng)組網(wǎng)拓撲結(jié)構(gòu)
傳統(tǒng)拓撲結(jié)構(gòu)相對簡單,各節(jié)點按照編組進行組網(wǎng),編組間的通信則通過中心節(jié)點來完成,其拓撲結(jié)構(gòu)如圖6所示。
圖6 傳統(tǒng)組網(wǎng)拓撲結(jié)構(gòu)
按2.2節(jié)中目標的計算方法,得到傳統(tǒng)組網(wǎng)拓撲結(jié)構(gòu)方案的通信總時延為210,綜合連通度為1.0,抗毀性為0.125。
4.3拓撲結(jié)構(gòu)優(yōu)化
首先根據(jù)節(jié)點分布和距離,以預警機為中心節(jié)點。其他節(jié)點均與中心節(jié)點通信,中心節(jié)點與水面艦艇通信,得到主要通信鏈路。拓撲結(jié)構(gòu)優(yōu)化主要解決除節(jié)點之外的節(jié)點之間如何建立通信鏈路的問題。
1) 遺傳編碼
e=[e11,e12,…,e18,e23,e24,…,e28,…,e78]
(14)
eij∈{0,1},對應節(jié)點ci與節(jié)點cj之間的組合。其中,e17=e18=e27=e28=0。
2) 初始化
目標權(quán)重由作戰(zhàn)指揮員根據(jù)實際情況來確定,一般給出大致重要程度,再根據(jù)優(yōu)化結(jié)果進行微調(diào)。這里假設目標權(quán)重WS=(0.45,0.15,0.40),種群規(guī)模N=10,進化代數(shù)E=500。初始染色體種群由系統(tǒng)隨機初始化獲取。
3) 優(yōu)化結(jié)果
算法經(jīng)過500次進化,得到最優(yōu)染色體如圖7所示。對染色體進行解碼,得到拓撲結(jié)構(gòu)方案如圖8所示。
圖9為全局最優(yōu)適應度隨進化次數(shù)變化曲線,圖10為各代種群中最優(yōu)適應度的波動曲線。由圖可知適應函數(shù)值經(jīng)過多次優(yōu)化,種群最優(yōu)適應度波動范圍逐漸變小,算法逐漸收斂。
圖7 最優(yōu)染色體
圖8 優(yōu)化后拓撲結(jié)構(gòu)
圖9 全局最優(yōu)適應度變化曲線
圖10 種群最優(yōu)適應度變化曲線
優(yōu)化得到最優(yōu)適應度為0.1414。通信時延優(yōu)化結(jié)果為104,加上中心節(jié)點的通信時延得到總時延為176,綜合連通度為1.0,網(wǎng)絡抗毀性為0.8750。
4.4結(jié)果分析
通過與傳統(tǒng)組網(wǎng)拓撲結(jié)構(gòu)方案對比可知,遺傳算法能夠解決艦艇編隊通信組網(wǎng)優(yōu)化問題,且優(yōu)化效果較好??偼ㄐ艜r延低于傳統(tǒng)組網(wǎng)(176<210),這是由于傳統(tǒng)通信網(wǎng)絡在通信過程中很多節(jié)點間無法進行直接通信,需要多次通過中心節(jié)點作為中繼節(jié)點完成通信,導致通信時延增大。傳統(tǒng)組網(wǎng)方式得到的組網(wǎng)方案的抗毀性遠遠低于使用優(yōu)化算法優(yōu)化后的組網(wǎng)方案(0.125<0.875),由于傳統(tǒng)組網(wǎng)只注重節(jié)點編組內(nèi)通信而忽略了編組間通信,因此導致了組網(wǎng)抗毀能力偏弱,一旦某個節(jié)點遭到破壞,可能導致多個節(jié)點間無法通信。
通過分析艦艇編隊通信網(wǎng)絡拓撲結(jié)構(gòu)特點,將遺傳算法應用到艦艇編隊通信組網(wǎng)中,實現(xiàn)了艦艇編隊通信網(wǎng)絡拓撲結(jié)構(gòu)的優(yōu)化。通過實例仿真與對比,證明了方法的有效性和優(yōu)越性。論文將遺傳算法在艦艇編隊通信組網(wǎng)中進行嘗試應用,取得了較好的效果,為艦艇編隊通信組網(wǎng)優(yōu)化提供了新的研究方向,對海上作戰(zhàn)信息化建設具有重要意義。
[1] Trietsch F, Hogan J. A family of methods for preliminary highway alignment[J]. Transportation Science,1987,21(1):17-25.
[2] Easa, S.M. Selection of roadway grades that minimize earthwork cost using linear programming[J]. Transportation Reseach,1988,22(2):121-136.
[3] Howard B E, Brmmick Z, Shaw J.FB. Optinum curvature principle in highway routing[J]. Journal of the Highway Division, ASCE94, 1968:61-82.
[4] 包希日莫,高光來,張璟.基于遺傳算法的聲學模型拓撲結(jié)構(gòu)優(yōu)化[J].計算機工程與應用,2014,50(14):5-8.
BAO Xirimo, GAO Guanglai, ZHANG Jing. Genetic algorithm based optimization of acoustic model topologies[J]. Computer Engineering and Applications,2014,50(14):5-8.
[5] 郭蘊華,王曉宗.基于改進量子粒子群算法的無人機路徑規(guī)劃[J].船海工程,2016,45(1):99-102.
GUO Yunhua, WANG Xiaozong. UVA Path Planning Based on Improved Quantum-behaved Particle Swarm Optimization Algorithm[J]. SHIP & OCEAN ENGINEERING,2016,45(1):99-102.
[6] 任謝楠.基于遺傳算法的BP神經(jīng)網(wǎng)絡的優(yōu)化研究及MATLAB仿真[D].天津:天津師范大學,2014.
XIE Nan. Study on Optimization of BP Neural Network Based on Genetic Algorithm and MATLAB Simulation[D]. Tianjin: Tianjin Normal University,2014.
[7] 李京濤.基于改進遺傳算法的桁架結(jié)構(gòu)拓撲優(yōu)化研究[D].邯鄲:河北工程大學,2010.
LI Jingtao. The Topology optimal Study of Truss Structures based on Improved Genetic Algorithm[D]. Handan: Hebei University of Egineering,2010.
[8] 吳東海.軍用通信網(wǎng)系統(tǒng)可靠性評估及其仿真方法研究[D].成都:電子科技大學,2012.
WU Donghai. Research on reliability evaluation and simulation method of military communication system[D]. Chengdu: University of Electronic Science and Technology of China,2012.
[9] 侯綠林.作戰(zhàn)模擬系統(tǒng)中軍事通信網(wǎng)絡建模研究[D].長沙:國防科技大學,2010.
HOU Lulin. Research on Military Communication Network Modeling in Warfare Simulation System[D]. Changsha: School of National University of Defense Technology,2010.
[10] 劉煥淋,鄧朗,薛湘,等.改進遺傳算法優(yōu)化光組播網(wǎng)絡編碼鏈路數(shù)目[J].光電子·激光,2014,25(8):1488-1493.
LIU Huanlin, DENG Lang, XUE Xiang. Improved genetic algorithm to optimize the number of network coding links for optical multicast[J]. Journal of Optoelectronics·Laser,2014,25(8):1488-1493.
[11] Srinivas M, Patnaik L. M. Adaptive Probabilities of crossover and mutation in genetic algorithms[J]. IEEE Trans. On Systems,Man and Cybernetics,1994,24(24):656-667.
Communication Networking Topology Structure Optimization of Warship Formation Based on Genetic Algorithm
GUO Yan1YU Qian2ZHANG Shiwei3
(1. Naval Aviation Academy, Huludao125001)(2. Unit 95, No. 92941 Troops of PLA, Huludao125001) (3. Naval University of Engineering, Wuhan430033)
According to the characteristics of multiple war forces and complex war environment of sea warship formation, topology structure model, optimization target model and problem model are established by analyzing the actual requirement of warship formation communication networking. And the topology structure optimization method of warship formation communication networking based on genetic algorithm is put forward, so that the problem of hard topology coding and low optimization efficiency is solved, and the topology structure optimization of warship formation communication networking is realized. The case application shows that the genetic algorithm can solve the topology optimization problem of warship formation communication networking, and the solution is better than traditional topology’s. The study of de method is beneficial to improve comprehensive support capability of the warship formation, and has importance preference value for exploring the method of warship formation communication networking under the condition of informatization.
warship formation, communication networking, topology structure, optimization method, genetic algorithm
2016年4月20日,
2016年5月30日
郭彥,女,碩士研究生,研究方向:軍事通信、航空電子、高等教育等。于錢,男,碩士研究生,研究方向:智能優(yōu)化技術、通信安全、衛(wèi)星導航等。張世偉,男,碩士研究生,研究方向:軍事通信、信息安全等。
TP301.6; TN915
10.3969/j.issn.1672-9722.2016.10.004