齊大偉 賀筱媛 胡曉峰 張大永

1.國防大學(xué)信息作戰(zhàn)與指揮訓(xùn)練教研部,北京100091

軍事通信網(wǎng)作為軍事信息系統(tǒng)的信息傳輸平臺,承載了大量的話音、數(shù)據(jù)、圖像等軍事信息傳輸業(yè)務(wù),是信息化條件下軍隊(duì)的“神經(jīng)網(wǎng)絡(luò)”,是奪取信息化戰(zhàn)爭優(yōu)勢的重要保障.為了提高軍事通信網(wǎng)的實(shí)時(shí)性、可靠性,動態(tài)高效規(guī)劃出軍事通信路徑是提高用戶服務(wù)質(zhì)量的重要內(nèi)容[1].然而,在傳統(tǒng)軍事通信模型中,一般假設(shè)網(wǎng)絡(luò)中的所有信息是確定的,而且這些信息與時(shí)間相關(guān)甚少.這些簡化使得許多通信領(lǐng)域的分析結(jié)果與實(shí)際結(jié)果并不相符,并沒有很好地反映軍事通信的特點(diǎn)[2?3].因此,傳統(tǒng)的軍事通信路徑規(guī)劃模型往往建立在網(wǎng)絡(luò)屬性靜態(tài)不變的情況下,難以適用于動態(tài)網(wǎng)絡(luò)的優(yōu)化,需要進(jìn)一步研究與之相應(yīng)的模型及算法來解決動態(tài)通信網(wǎng)絡(luò)路徑規(guī)劃問題.本文針對動態(tài)通信路徑規(guī)劃問題,在借鑒和參考以往成果的基礎(chǔ)上,采用改進(jìn)蟻群算法,建立和設(shè)計(jì)通信路徑規(guī)劃動態(tài)模型和算法,并通過示例分析來驗(yàn)證其有效性.

1 軍事通信路徑動態(tài)規(guī)劃問題描述

軍事通信網(wǎng)是用于軍事目的、保障作戰(zhàn)指揮的通信網(wǎng),通常由多個(gè)交換節(jié)點(diǎn)用傳輸鏈路互聯(lián),以一定的拓?fù)浣Y(jié)構(gòu)構(gòu)成,它緊緊圍繞戰(zhàn)爭這個(gè)特殊的環(huán)境和任務(wù)發(fā)展起來,要求快速、準(zhǔn)確、保密和不間斷.尤其是現(xiàn)代戰(zhàn)爭,對軍事通信的要求越來越高,軍事通信傳輸?shù)膶?shí)時(shí)、準(zhǔn)確與否,直接影響著戰(zhàn)爭的結(jié)局.

在軍事通信過程中,動態(tài)因素主要有以下三種情況:1)通信發(fā)送單元作戰(zhàn)意圖的變動帶來的通信需求的改變,這種情況相當(dāng)于用戶需求發(fā)生了改變.2)通信接收單元作戰(zhàn)要求發(fā)生改變,導(dǎo)致約束條件的變量發(fā)生改變.3)軍事通信網(wǎng)絡(luò)屬性矩陣發(fā)生變化,這種情況是最常見的.因?yàn)檐娛峦ㄐ盘幱跀撤胶妥陨淼碾姶鸥蓴_之中,網(wǎng)絡(luò)的屬性發(fā)生改變是必然的.比如,網(wǎng)絡(luò)節(jié)點(diǎn)遭敵火力摧毀、通信線路擁堵等等,這些問題都反映在網(wǎng)絡(luò)屬性的改變.本文研究的重點(diǎn)是第三種情況,重點(diǎn)關(guān)注網(wǎng)絡(luò)屬性矩陣的改變.

本文把通信路徑看成網(wǎng)絡(luò)資源,通信路徑規(guī)劃問題就轉(zhuǎn)換為通信目標(biāo)對網(wǎng)絡(luò)資源的需求優(yōu)化問題.為了進(jìn)一步研究通信路徑規(guī)劃問題,分析抽象出可計(jì)算的網(wǎng)絡(luò)拓?fù)鋱D,借用圖論的表示方法,采用三元組表示G=(V,E,W),其中:V={v,v1,v2···,vn}是拓?fù)涔?jié)點(diǎn)集,E代表邊集,WWW代表邊的屬性矩陣.用ω表示用戶通信質(zhì)量的集合,包括通信帶寬ωQ、通信時(shí)間ωT、通信可靠性ωR,即問題描述為:從源點(diǎn)v到目標(biāo)點(diǎn)vn,如何在用戶通信質(zhì)量要求和網(wǎng)絡(luò)屬性矩陣動態(tài)變化條件下,規(guī)劃出最優(yōu)通信路徑[4].

2 軍事通信路徑動態(tài)規(guī)劃數(shù)學(xué)模型

2.1 軍事通信網(wǎng)絡(luò)屬性矩陣

在軍事通信網(wǎng)絡(luò)中,數(shù)據(jù)傳播是以光速進(jìn)行的,傳播時(shí)間是毫秒級的.戰(zhàn)場上通信占優(yōu)的一方取得勝利的可能性更大.因此,研究通信網(wǎng)絡(luò)本身的屬性直接關(guān)系到通信路徑的規(guī)劃.比如,交通網(wǎng)絡(luò)中最常用的屬性是距離、時(shí)間、可靠性、費(fèi)用等,本文研究的軍事網(wǎng)絡(luò)屬性主要是指網(wǎng)絡(luò)單元的帶寬、時(shí)延、可靠性等[5].

2.1.1 帶寬

帶寬是網(wǎng)絡(luò)性能的重要指標(biāo)參數(shù),是路徑規(guī)劃需要重點(diǎn)關(guān)注的信息.是指單位時(shí)間內(nèi)可傳輸?shù)臄?shù)據(jù)量,即是在網(wǎng)絡(luò)中傳遞數(shù)據(jù)的能力,用bps(字節(jié)/秒)表示.帶寬分三類:吞吐量、鏈路帶寬和可用帶寬.因?yàn)橥掏铝颗c網(wǎng)絡(luò)協(xié)議有關(guān),本文研究路徑規(guī)劃暫未考慮網(wǎng)絡(luò)間的協(xié)議,因此,吞吐量暫不考慮.按照OSI七層體系構(gòu)架,帶寬可以分為網(wǎng)絡(luò)層的帶寬和數(shù)據(jù)鏈路層的帶寬.網(wǎng)絡(luò)層帶寬測量技術(shù)較為成熟,使用較多,本文僅考慮網(wǎng)絡(luò)層帶寬.數(shù)據(jù)鏈路層的帶寬測量仍然不成熟,是個(gè)比較前沿的課題,測量的標(biāo)準(zhǔn)和結(jié)果也不盡統(tǒng)一.因此,使用的可用帶寬指網(wǎng)絡(luò)層的帶寬,即可用帶寬,它是一個(gè)動態(tài)的概念,和網(wǎng)絡(luò)能力的概念有點(diǎn)相似,其量化指標(biāo)用ωq表示[6?7].

2.1.2 時(shí)延

時(shí)間延遲分為雙向網(wǎng)絡(luò)延遲和單向網(wǎng)絡(luò)延遲,本文研究源點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑,更傾向于單向網(wǎng)絡(luò)延遲,后面默認(rèn)延遲為單向時(shí)延.導(dǎo)致網(wǎng)絡(luò)時(shí)延的因素很多,一般包括發(fā)送延遲、傳遞延遲、路由延遲和訪問延遲,其中:

發(fā)送延遲ds(Send delay)是指數(shù)據(jù)流從處理器到內(nèi)存到物理鏈路的時(shí)延,其數(shù)值在毫秒級,隨著處理器和內(nèi)存的處理速度而變化,具有動態(tài)性.

傳遞延遲dt(Transmission delay)是指數(shù)據(jù)流在物理鏈路上傳播的延遲,其大小等于物理鏈路的長度與傳遞速度的比值,對于固定的物理鏈路,其數(shù)值一般是固定不變的.

路由延遲dr(Route delay)是指數(shù)據(jù)流通過路由器的延遲,通常包括在路由器排隊(duì)等待的時(shí)間和處理器對數(shù)據(jù)流報(bào)頭處理的時(shí)間兩部分.這兩部分和路由器的性能相關(guān),具有動態(tài)變化性.

訪問延遲da(Access delay)是指網(wǎng)絡(luò)節(jié)點(diǎn)訪問數(shù)據(jù)的時(shí)延,由于訪問競爭的原因,其數(shù)值也具有動態(tài)性.

因此,網(wǎng)絡(luò)延遲的公式如下:d=ds+dt+dr+da其量化指標(biāo)用ωt表示.

2.1.3 可靠性

可靠性是指在平時(shí)和戰(zhàn)時(shí)條件下,網(wǎng)絡(luò)在各種突發(fā)和意外情況下,在限定時(shí)間內(nèi)完成規(guī)定任務(wù)的能力,可以分為物理可靠性和應(yīng)用可靠性.

一是基于路徑存在的物理可靠性,在一定條件下和一定時(shí)間內(nèi)網(wǎng)絡(luò)保持通暢的能力,是對網(wǎng)絡(luò)在非作戰(zhàn)條件下的物理特性的基本要求,直接關(guān)系到通信過程中數(shù)據(jù)流是否能夠及時(shí)到達(dá),關(guān)系著網(wǎng)絡(luò)通信的成敗.物理可靠性和網(wǎng)絡(luò)的初始狀態(tài)密切相關(guān),如果網(wǎng)絡(luò)連通程度高,組網(wǎng)方式靈活,能夠有多條備選路徑,就意味著網(wǎng)絡(luò)物理可靠性高,網(wǎng)絡(luò)連通能力強(qiáng).

二是基于路徑性能的應(yīng)用可靠性,在一定條件和一定時(shí)間內(nèi),網(wǎng)絡(luò)傳輸了任務(wù)要求的數(shù)據(jù)流的能力.在通信過程中,網(wǎng)絡(luò)是高度動態(tài)變化的,如果再用基于路徑連通的物理可靠性這一靜態(tài)指標(biāo)就顯得不盡合理,因此,引入了基于路徑性能的應(yīng)用可靠性這一動態(tài)指標(biāo).在作戰(zhàn)條件下,網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)可能出現(xiàn)級聯(lián)失效導(dǎo)致網(wǎng)絡(luò)性能的急劇下降,這種情況就更需要應(yīng)用可靠性.

文獻(xiàn)[8]給出了通信網(wǎng)絡(luò)的可靠性評估方法,建立了可靠性指標(biāo)體系和測量標(biāo)準(zhǔn),最后基于模糊評價(jià)方法給出可靠性具體評價(jià)方法,量化指標(biāo)ωr用表示.

2.2 目標(biāo)函數(shù)和約束條件

假設(shè)P是源點(diǎn)v0到目標(biāo)點(diǎn)vn所有路徑集合,P?是服務(wù)用戶通信要求的可行路徑集合,其中只有一條路徑p∈P?,使得目標(biāo)路徑最優(yōu).因此,數(shù)學(xué)模型的約束條件如下:

:表示網(wǎng)絡(luò)路徑p上任意網(wǎng)絡(luò)邊e的帶寬;

wt(p):表示網(wǎng)絡(luò)路徑p通信時(shí)延;

wt(e):表示網(wǎng)絡(luò)路徑p網(wǎng)絡(luò)邊e上通信時(shí)延;

wr(p):表示網(wǎng)絡(luò)路徑p通信可靠性;

wQ,wT,wR分別表示通信用戶的通信質(zhì)量要求.

約束條件包含有3個(gè)方面的約束:

1)網(wǎng)絡(luò)路徑p上任意網(wǎng)絡(luò)邊e的帶寬必須大于等于用戶要求的帶寬wQ;

2)通信時(shí)延滿足用戶在保障實(shí)效性方面的服務(wù)質(zhì)量要求,在用戶要求的通信時(shí)間wT內(nèi),即路徑p上所有網(wǎng)絡(luò)邊的通信時(shí)延累計(jì)不超過用戶通信時(shí)間wT;

3)通信可靠性滿足用戶在保障安全方面的服務(wù)質(zhì)量要求,要確保通過該路徑通信安全可靠,即路徑上所有邊的通信可靠性累乘不低于用戶通信可靠性wR;

該數(shù)學(xué)模型建立了用戶通信質(zhì)量和網(wǎng)絡(luò)屬性之間的約束關(guān)系,可行路徑不是唯一的,并且只是通過該路徑通信能夠滿足用戶服務(wù)要求.從通信網(wǎng)絡(luò)資源利用的角度來看,可行路徑不一定是對網(wǎng)絡(luò)資源的最有效的利用.根據(jù)用戶的特殊通信需求,對網(wǎng)絡(luò)資源進(jìn)行優(yōu)化,尋找最優(yōu)路徑是很有必要的.比如,以通信時(shí)間為最優(yōu)目標(biāo),在滿足用戶其他服務(wù)要求的條件下,盡可能尋找通信時(shí)間最短的路徑.因此,以通信時(shí)間為優(yōu)化目標(biāo)的通信路徑規(guī)劃模型描述如下:

目標(biāo)函數(shù):

響應(yīng)譜分析一般作為結(jié)構(gòu)的抗震分析，在得知當(dāng)?shù)氐牡卣痦憫?yīng)譜曲線后，根據(jù)結(jié)構(gòu)進(jìn)行抗震計(jì)算，計(jì)算結(jié)構(gòu)在指定的地震加速度曲線下是否存在較大的應(yīng)力、彎矩及位移，從而通過對結(jié)構(gòu)進(jìn)行局部的加強(qiáng)來增加結(jié)構(gòu)的穩(wěn)定性。

約束條件:

通信時(shí)延函數(shù)主要反映通信在各種干擾下時(shí)延動態(tài)變化,其函數(shù)表達(dá)式如下[9]:

其中,wt0(e)表示無干擾情況下的通信時(shí)延;μ是外界干擾參數(shù),取值大于等于0,推薦值μ=0.3;φ是自身干擾參數(shù),取值大于等于0,推薦值φ=2.

3 軍事通信路徑動態(tài)規(guī)劃算法

3.1 蟻群算法概述

蟻群算法通過模擬螞蟻群體覓食行為的群體智能,采用正反饋并行自催化機(jī)制,具有較強(qiáng)的魯棒性、優(yōu)良的分布計(jì)算機(jī)制和易于與其他方法結(jié)合等優(yōu)點(diǎn).特別適合于在離散優(yōu)化問題的解空間進(jìn)行多點(diǎn)非確定性搜索,成為求解組合優(yōu)化等NP問題的一種很有潛力的演化算法.尤其是對于動態(tài)問題的求解,可以在迭代過程中,通過修改參數(shù)實(shí)時(shí)規(guī)劃最優(yōu)路徑,能夠很好解決動態(tài)條件下通信路徑規(guī)劃.蟻群算法得到的結(jié)果序列與路徑節(jié)點(diǎn)序列存在關(guān)聯(lián)性,且可以通過對結(jié)果序列的限制很好地解決路徑規(guī)劃中的必經(jīng)點(diǎn)問題,因此,蟻群算法比較適于對通信路徑規(guī)劃問題的求解.但由于基本蟻群算法搜索時(shí)間長,易陷入局部最優(yōu)解,本文嘗試以改進(jìn)的蟻群算法來提高尋優(yōu)能力.

改進(jìn)蟻群算法主要由狀態(tài)轉(zhuǎn)移概率、信息素更新策略、信息素啟發(fā)因子決定,設(shè)n表示路徑節(jié)點(diǎn)數(shù),m為螞蟻總數(shù),對于第k只螞蟻來說,其狀態(tài)轉(zhuǎn)移概率公式如下:

(t)為t時(shí)刻選擇路徑(i,j)的狀態(tài)轉(zhuǎn)移概率;

τij(t)為t時(shí)刻路徑(i,j)上的信息量;

ηij(t)為信息素啟發(fā)函數(shù);

allowedk={1?tabuk}表示螞蟻k下一步允許選擇的節(jié)點(diǎn)集合;

s為螞蟻可以選擇的節(jié)點(diǎn)集合;

tabuk表示第k只螞蟻已經(jīng)走過的路徑集合;

α為信息啟發(fā)式因子,表示軌跡的相對重要性;

β為期望啟發(fā)式因子.

信息素更新策略是信息素隨著時(shí)間的推移逐漸淡化,t+1時(shí)刻在路徑(i,j)上的信息量可以按照下列公式進(jìn)行調(diào)整:

ρ是自適應(yīng)調(diào)節(jié)信息素?fù)]發(fā)因子,在蟻群算法的初始階段,較大的ρ值可以幫助螞蟻進(jìn)行路徑選優(yōu),防止產(chǎn)生局部最優(yōu)解.但是如果ρ值較小,就會導(dǎo)致部分路徑信息素堆積過多,不會得到全局最優(yōu)解.因此,ρ必須取值在一定范圍內(nèi),才能使算法更優(yōu)化.

在Ant-Cycle模型中,

Q是各路段初始信息量;

Tk是指螞蟻在本次周游中所選擇路徑的通信時(shí)延;在全局更新過程中,則代表可行路徑中通信時(shí)延最小的路徑.

信息素啟發(fā)因子ηij(t)是當(dāng)前節(jié)點(diǎn)到鄰接點(diǎn)之間的路徑映射到屬性矩陣上非線性路徑長度的倒數(shù),即:

該信息素啟發(fā)因子使螞蟻在選擇路徑時(shí),盡可能選擇在屬性矩陣上非線性距離比較小的鄰接邊.

3.2 基于改進(jìn)蟻群算法的通信路徑動態(tài)規(guī)劃算法

該算法以通信時(shí)延為優(yōu)化目標(biāo),根據(jù)算法基本思想,通信路徑規(guī)劃算法基本步驟如下[10]:輸入:軍事通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和屬性矩陣輸出:軍事通信路徑序列算法:

Begin

1)初始化參數(shù).

2)采用枝剪法消除網(wǎng)絡(luò)帶寬約束.根據(jù)用戶通信帶寬wQ,除去帶寬不滿足約束條件的網(wǎng)絡(luò)邊,即是剪除帶寬小于wQ的網(wǎng)絡(luò)邊,如出現(xiàn)孤立節(jié)點(diǎn),則刪除節(jié)點(diǎn).

3)把通信可靠性轉(zhuǎn)換成可加性屬性,對通信可靠性屬性取自然對數(shù),轉(zhuǎn)換成可加性度量參數(shù),注意是負(fù)相關(guān)屬性.

4)把m只螞蟻置于源點(diǎn),每次釋放一只螞蟻,按照式(5)給出的策略選擇下一節(jié)點(diǎn),并把該節(jié)點(diǎn)加入禁忌表,防止產(chǎn)生回路.如果符合通信質(zhì)量要求,繼續(xù)選擇下一節(jié)點(diǎn);如果不符合通信質(zhì)量要求或沒有可供選擇的節(jié)點(diǎn),則螞蟻死亡.

5)第k只螞蟻到達(dá)目標(biāo)節(jié)點(diǎn),完成一次循環(huán)后,按照式(6)更新信息素濃度.

6)對m只螞蟻重復(fù)步驟(4)、步驟(5).

7)從m螞蟻找到的所有可行路徑中選擇通信時(shí)延最小的路徑,然后按照式(8)使用信息素全局更新規(guī)則,對該路徑上的信息素進(jìn)行更新.

8)重復(fù)步驟(4)～步驟(7),直到完成給定的迭代次數(shù)或者獲得滿意的結(jié)果.

9)若存在滿意路徑,則輸出該路徑序列.End

4 實(shí)驗(yàn)分析

為了驗(yàn)證算法的有效性,本節(jié)進(jìn)行了仿真示例分析.搭建的實(shí)驗(yàn)平臺為:CPU:3.4GHz,RAM:4GB,操作系統(tǒng):Windows 7,開發(fā)工具:Microsoft Visual Studio 2010.為了便于比較,兩次實(shí)驗(yàn)分別設(shè)置靜態(tài)和動態(tài)兩種情況.參數(shù)選擇文獻(xiàn)[11?12]給定的參數(shù)組合α=2,β=5,ρ=0.6,=100,m=100,迭代次數(shù)50;該組參數(shù)具有較好的搜索性能和效率.本文對某類戰(zhàn)場軍事通信網(wǎng)絡(luò)進(jìn)行提取,去除邊緣節(jié)點(diǎn),得到主干網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖如圖1所示,通信路徑規(guī)劃從源點(diǎn)1到達(dá)目標(biāo)點(diǎn)7,用戶通信服務(wù)質(zhì)量要求ω=(10,90,0.85),即帶寬要求不低于10(單位),時(shí)延不超過90(單位),通信可靠性不低于0.85.

圖1 通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

表1 各網(wǎng)絡(luò)邊屬性矩陣

如果輸入初始屬性矩陣,得到的最優(yōu)路徑是1-2-5-7,通信時(shí)延是45,可靠性是0.951;如果輸入動態(tài)變化后的屬性矩陣,得到的最優(yōu)路徑是1-3-7,其通信時(shí)延是83.6,可靠性是0.875.

考慮網(wǎng)絡(luò)屬性在初始和動態(tài)變化后的兩種情況,發(fā)現(xiàn)得出的最優(yōu)路徑不一樣,網(wǎng)絡(luò)屬性動態(tài)變化后規(guī)劃出的路徑更符合戰(zhàn)場環(huán)境下的軍事通信.并且,如果不考慮網(wǎng)絡(luò)屬性的動態(tài)變化,規(guī)劃出的通信路徑可能并不符合戰(zhàn)場通信的實(shí)際情況.

更改用戶通信服務(wù)質(zhì)量要求,通信帶寬要求分別為5,8,10,15,20,其他要求不變,得出不同通信帶寬要求下的通信路徑規(guī)劃方案,如表2所示.

以用戶通信服務(wù)質(zhì)量帶寬wQ為橫坐標(biāo),通信時(shí)延wT、通信可靠性wR分別為橫坐標(biāo),建立ωQ?ωT坐標(biāo)系、ωQ?ωR坐標(biāo)系,如圖2、圖3所示.

表2 不同通信帶寬要求下路徑規(guī)劃方案

圖2 用戶帶寬要求與通信時(shí)延的關(guān)系

圖3 用戶帶寬要求與通信可靠性的關(guān)系

由圖可以看出,隨著用戶通信帶寬要求的增加,更多網(wǎng)絡(luò)邊因通信帶寬增加而被刪除,軍事通信不得不選擇時(shí)延更長、可靠性更低的網(wǎng)絡(luò)路徑.同時(shí),通信時(shí)延隨著帶寬要求的增加呈指數(shù)式連續(xù)增加,通信可靠性隨著帶寬要求的增加呈跳躍式增加.因?yàn)閳D2中各條邊的通信時(shí)延是隨著帶寬要求變化而變化的,導(dǎo)致了整體通信時(shí)延連續(xù)變化.但是,本文沒有考慮通信可靠性隨著帶寬要求變化而變化,圖3中通信可靠性呈現(xiàn)跳躍式變化.因此,兩圖對比形成反差,更能體現(xiàn)出動態(tài)路徑規(guī)劃必須考慮網(wǎng)絡(luò)屬性的動態(tài)變化,并在此基礎(chǔ)上實(shí)時(shí)合理規(guī)劃最優(yōu)路徑.

5 結(jié)論

本文以改進(jìn)蟻群算法為工具,考慮到路徑中網(wǎng)絡(luò)屬性的動態(tài)變化,建立了動態(tài)條件下通信網(wǎng)絡(luò)路徑規(guī)劃的模型,并進(jìn)行了實(shí)驗(yàn)驗(yàn)證.實(shí)驗(yàn)結(jié)果表明:隨著用戶服務(wù)質(zhì)量要求的變化,導(dǎo)致通信網(wǎng)絡(luò)屬性發(fā)生動態(tài)變化,因此,軍事通信路徑規(guī)劃必須立足于動態(tài)變化的網(wǎng)絡(luò)屬性,實(shí)時(shí)合理規(guī)劃軍事通信路徑.當(dāng)然,該問題的研究還有許多值得深入的地方,比如多屬性動態(tài)變化、用戶通信要求動態(tài)變化等問題,這些都將是下一步研究的方向.