張兆晨，錢寧

(中國(guó)電子科技集團(tuán)公司 第28研究所 信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210007)

0 引言

飛機(jī)編隊(duì)執(zhí)行任務(wù)通常以空中分層網(wǎng)絡(luò)的形式進(jìn)行組網(wǎng)。空中分層網(wǎng)絡(luò)為飛行編隊(duì)間的信息交互提供了通信保障，主要包括一個(gè)拓?fù)湎鄬?duì)穩(wěn)定的骨干網(wǎng)和若干動(dòng)態(tài)移動(dòng)的子網(wǎng)，具有鏈路質(zhì)量不穩(wěn)定、通信距離受限、拓?fù)渥兓靃1]等特點(diǎn)。由于空中分層網(wǎng)絡(luò)受到能量、干擾等內(nèi)外部因素的限制，為保證網(wǎng)絡(luò)的連通性，最有效的手段是增加飛行器作為通信中繼節(jié)點(diǎn)。因此，如何以盡量小的代價(jià)部署中繼節(jié)點(diǎn)并生成中繼航線，成為亟待解決的問題。

從研究對(duì)象、實(shí)現(xiàn)連通性的方法以及針對(duì)的問題等方面看，目前的研究成果還不能滿足空中分層網(wǎng)絡(luò)的連通性需求。一些文獻(xiàn)[2-5]主要針對(duì)拓?fù)涔潭?、不隨時(shí)間變化的無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSN)的中繼節(jié)點(diǎn)放置問題，解決方法通常是調(diào)整節(jié)點(diǎn)發(fā)射功率以實(shí)現(xiàn)拓?fù)渲羞叺倪B通，不能適用于節(jié)點(diǎn)分布區(qū)域廣、通信能源受限的空中分層網(wǎng)絡(luò)。還有一些文獻(xiàn)的研究對(duì)象雖然是空中網(wǎng)絡(luò)，但是由于優(yōu)化目標(biāo)、限制條件等不同，都不能解決航空平臺(tái)拓?fù)潆S時(shí)間快速變化的網(wǎng)絡(luò)連通性問題。例如，文獻(xiàn)[6]提出一種無(wú)人機(jī)群網(wǎng)絡(luò)連通性的實(shí)時(shí)動(dòng)態(tài)規(guī)劃方法，主要關(guān)注中繼節(jié)點(diǎn)的位置對(duì)任務(wù)的滿足程度，沒有給出具體的中繼節(jié)點(diǎn)路徑生成方法；文獻(xiàn)[7]研究了優(yōu)化自組織網(wǎng)絡(luò)連通性的無(wú)人機(jī)部署和移動(dòng)算法，但其目的是保證網(wǎng)絡(luò)的4種連通屬性，沒有考慮采用的無(wú)人機(jī)數(shù)量最?。晃墨I(xiàn)[8]提出了一種WSN網(wǎng)絡(luò)維護(hù)和恢復(fù)算法，雖然尋找到了中繼的最小個(gè)數(shù)和位置，但其目標(biāo)是提高網(wǎng)絡(luò)生存時(shí)間和重建網(wǎng)絡(luò)連接；文獻(xiàn)[9]提出了一種動(dòng)態(tài)環(huán)境下的無(wú)人機(jī)多目標(biāo)協(xié)同路徑規(guī)劃方法，其目標(biāo)是任務(wù)風(fēng)險(xiǎn)和任務(wù)延遲的最小化；文獻(xiàn)[10]對(duì)空中自組織網(wǎng)絡(luò)進(jìn)行了中繼節(jié)點(diǎn)優(yōu)化配置，但是僅在單一時(shí)刻最優(yōu)配置，沒有考慮整個(gè)飛行過程中的全局優(yōu)化；文獻(xiàn)[11]提出了一種無(wú)人機(jī)飛行模型，但主要針對(duì)無(wú)人機(jī)為地面移動(dòng)自組網(wǎng)提供中繼服務(wù)的問題；文獻(xiàn)[12]在中繼個(gè)數(shù)固定的條件下實(shí)現(xiàn)了網(wǎng)絡(luò)連通和中繼運(yùn)動(dòng)距離最小，但沒有考慮中繼個(gè)數(shù)最小化。文獻(xiàn)[13]提出一種增加固定節(jié)點(diǎn)以提高網(wǎng)絡(luò)連通性的算法，但是不能滿足飛行編隊(duì)前出執(zhí)行任務(wù)的通信保障需求。

為此，針對(duì)現(xiàn)有空中網(wǎng)絡(luò)連通性實(shí)現(xiàn)方法、中繼節(jié)點(diǎn)部署等問題中存在的不足，本文提出一種面向空中分層網(wǎng)絡(luò)連通性的中繼航線規(guī)劃方法，該方法從整個(gè)航線全局優(yōu)化的角度出發(fā)，以盡可能增加中繼節(jié)點(diǎn)在不同時(shí)間、空間上的復(fù)用率為目標(biāo)，生成中繼節(jié)點(diǎn)的航線，在解決空中分層網(wǎng)絡(luò)通信問題的基礎(chǔ)上，減少了中繼節(jié)點(diǎn)飛行器的使用量。

1 問題分析

空中分層網(wǎng)絡(luò)的骨干網(wǎng)拓?fù)湎鄬?duì)穩(wěn)定，主要為編隊(duì)提供各種信息業(yè)務(wù)支撐，節(jié)點(diǎn)之間通過寬帶鏈路連接；子網(wǎng)拓?fù)渥兓^快，由子網(wǎng)長(zhǎng)機(jī)和子網(wǎng)成員飛機(jī)組成，主要執(zhí)行機(jī)動(dòng)任務(wù)，子網(wǎng)節(jié)點(diǎn)之間以及子網(wǎng)與骨干網(wǎng)節(jié)點(diǎn)之間通過窄帶鏈路連接?？罩蟹謱泳W(wǎng)絡(luò)是飛機(jī)編隊(duì)完成任務(wù)的基礎(chǔ)，航線規(guī)劃[14]要求保證空中分層網(wǎng)絡(luò)拓?fù)渲泄歉删W(wǎng)節(jié)點(diǎn)之間以及骨干網(wǎng)與子網(wǎng)長(zhǎng)機(jī)節(jié)點(diǎn)之間連通，以支持?jǐn)?shù)據(jù)信息的交互。

由于鏈路支持的通信距離與鏈路端機(jī)的發(fā)射功率有關(guān)，而無(wú)限制地增加鏈路端機(jī)的發(fā)射功率不但增加了飛機(jī)的負(fù)擔(dān)，影響續(xù)航時(shí)間，而且往往不可能實(shí)現(xiàn)。因此，保證連通性最有效的方法是增加中繼節(jié)點(diǎn)。飛機(jī)編隊(duì)在飛行前必須依據(jù)任務(wù)進(jìn)行航線規(guī)劃，而任務(wù)航線規(guī)劃的結(jié)果并沒有考慮通信保障問題。本文以任務(wù)航線規(guī)劃的骨干網(wǎng)和子網(wǎng)長(zhǎng)機(jī)節(jié)點(diǎn)的飛行路徑為輸入，面向上述空中分層網(wǎng)絡(luò)的連通性需求，提出一種空中分層網(wǎng)絡(luò)中繼航線規(guī)劃方法，在不改變飛機(jī)編隊(duì)規(guī)劃任務(wù)航線的條件下，生成中繼節(jié)點(diǎn)的航線，并且考慮增加盡量少的中繼節(jié)點(diǎn)，同時(shí)中繼節(jié)點(diǎn)飛行盡量短的距離，以降低通信保障的成本，保證算法的優(yōu)化。

設(shè)任務(wù)航線規(guī)劃結(jié)果中不存在位于相同經(jīng)緯度、不同高度上的節(jié)點(diǎn)，即將本文的規(guī)劃問題簡(jiǎn)化為二維平面網(wǎng)絡(luò)問題。為便于形式化描述本文的方法，定義以下參數(shù)：

(1)t：輸入的任務(wù)航線規(guī)劃時(shí)間點(diǎn)，t=0,1,…,Nt，Nt為任務(wù)航線時(shí)長(zhǎng)；

(2)U：骨干網(wǎng)和子網(wǎng)長(zhǎng)機(jī)節(jié)點(diǎn)組成的拓?fù)洌?/p>

(3)dij：節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的距離；

(4)RKDL：寬帶鏈路的可通信距離；

(5)RZDL：窄帶鏈路的可通信距離；

(6)eu(t)：t時(shí)刻點(diǎn)u的連通分量，即t時(shí)刻與點(diǎn)u可以連通的所有點(diǎn)的集合；

(7)Eac：拓?fù)銾的全連通邊的集合，邊的權(quán)重為邊的長(zhǎng)度；

(8)Tmst：拓?fù)銾的MST；

(9)Tadj：優(yōu)選后的拓?fù)銾的生成樹，即選擇的拓?fù)銾的節(jié)點(diǎn)之間的連接邊組成的集合；

(10)Ere：中繼段向量的連接邊的集合；

(11)Econ：優(yōu)選后的中繼段向量的連接邊的集合；

(12)vre：中繼節(jié)點(diǎn)的最大運(yùn)動(dòng)速度。

需要說(shuō)明的是，本文生成樹優(yōu)選只適用于2個(gè)飛機(jī)間添加1個(gè)中繼節(jié)點(diǎn)的情況，因?yàn)楫?dāng)2個(gè)飛機(jī)間距離急劇增大時(shí)，可能會(huì)造成添加中繼節(jié)點(diǎn)個(gè)數(shù)劇增，故假設(shè)本文航線規(guī)劃在2個(gè)飛機(jī)間的最大距離小于等于相應(yīng)鏈路的可通信距離2倍的情況下進(jìn)行。

2 中繼航線規(guī)劃方法

2.1 生成樹優(yōu)選策略

為添加盡量少的中繼節(jié)點(diǎn)，需要盡可能增加中繼節(jié)點(diǎn)在不同時(shí)間、空間上的復(fù)用率。因此，在計(jì)算t時(shí)刻拓?fù)銾的生成樹時(shí)，本文考慮了t-1時(shí)刻中繼節(jié)點(diǎn)的位置。通過比較t時(shí)刻拓?fù)銾的MST邊的頂點(diǎn)的連通分量是否與t-1時(shí)刻相同，來(lái)決定t時(shí)刻生成樹的邊的選擇。若當(dāng)t時(shí)刻MST的一條邊的兩端點(diǎn)的連通分量與t-1時(shí)刻相同，且在t-1時(shí)刻這2個(gè)連通分量由另一條邊通過中繼節(jié)點(diǎn)連接，則選擇t-1時(shí)刻生成樹中連接這2個(gè)連通分量的邊，并入t時(shí)刻的生成樹。

首先，根據(jù)Kruskal算法[15]計(jì)算拓?fù)銾的MST為Tmst，然后對(duì)Tmst進(jìn)行優(yōu)選，生成樹優(yōu)選策略的具體過程如下：

(1) 對(duì)Tmst的每一組邊(u,v)，判斷邊的長(zhǎng)度duv與鏈路的可通信距離R的大小關(guān)系；其中，若邊(u,v)由寬帶鏈路連接時(shí)，則R=RKDL，若邊(u,v)由窄帶鏈路連接時(shí)，則R=RZDL。

(2) 若duv>R，則表示邊(u,v)不可連通，執(zhí)行下一步；否則對(duì)Tmst中的邊(u,v)不作替換。

(3) 計(jì)算點(diǎn)u和v在t時(shí)刻的連通分量eu(t)和ev(t)，若eu(t)=eu(t-1)且ev(t)=ev(t-1)，并且eu(t-1)和ev(t-1)由另一條邊(g,k)通過中繼節(jié)點(diǎn)連接，如圖1所示，則將Tmst中的邊(u,v)替換為邊(g,k)；否則，對(duì)Tmst中的邊(u,v)不作替換。

(4) 判斷是否對(duì)Tmst的每一組邊(u,v)均進(jìn)行過處理，若均進(jìn)行過處理，則得到優(yōu)選后的生成樹Tadj，否則返回步驟(1)。

圖1 生成樹優(yōu)選Fig.1 MST optimization

2.2 確定中繼節(jié)點(diǎn)位置并生成中繼段向量

對(duì)2.1節(jié)中得到的t時(shí)刻的生成樹Tadj中的每一組邊(u,v)，計(jì)算中繼節(jié)點(diǎn)的位置，并連接生成中繼段向量：

(1) 若R

(2) 查找(u,v)在t-1時(shí)刻是否存在中繼，若不存在中繼，則在(u,v)的中點(diǎn)添加中繼節(jié)點(diǎn)zuv(t)，并執(zhí)行步驟(4)；否則設(shè)(u,v)在t-1時(shí)刻存在中繼節(jié)點(diǎn)zuv(t-1)，并執(zhí)行步驟(3)。

(3) 在(u,v)的中點(diǎn)添加中繼節(jié)點(diǎn)zuv(t)，并將zuv(t-1)到zuv(t)用帶箭頭的直線連接，形成t-1時(shí)刻到t時(shí)刻的中繼段向量Li，如圖2所示。

(4) 判斷是否對(duì)Tadj中的每一組邊(u,v)均進(jìn)行過處理，若均進(jìn)行過處理，則得到拓?fù)銾在t-1時(shí)刻到t時(shí)刻的中繼段向量，否則返回步驟(1)。

圖2 連接中繼段向量Fig.2 Connecting relay segment vector

2.3 基于權(quán)重的中繼段向量連接方法

對(duì)任務(wù)航線時(shí)長(zhǎng)Nt內(nèi)的所有時(shí)刻進(jìn)行2.1和2.2節(jié)所述方法的計(jì)算，若計(jì)算得到的各時(shí)間間隔的中繼段向量首尾連續(xù)，則將它們連接成為一個(gè)向量，從而得到拓?fù)銾在Nt內(nèi)的中繼段向量集合L。下面計(jì)算L中可連接的向量，并優(yōu)選和連接中繼段向量，形成各中繼節(jié)點(diǎn)的航線。為了將盡量多的中繼段向量連接起來(lái)，并耗費(fèi)盡量少的中繼節(jié)點(diǎn)飛行時(shí)間，以減少增加的中繼節(jié)點(diǎn)的數(shù)量和飛行距離，降低保障連通性的成本，本文考慮將L的中繼段向量的頂點(diǎn)的度，以及中繼節(jié)點(diǎn)在2個(gè)中繼段向量間的運(yùn)動(dòng)時(shí)間作為聯(lián)合權(quán)重，優(yōu)先選擇度較小和耗時(shí)較小的邊進(jìn)行連接?；跈?quán)重的中繼段向量連接方法具體過程如下：

(1) 計(jì)算中繼段向量的可連接邊

對(duì)L的任意2個(gè)中繼段向量Li和Lj，進(jìn)行以下處理：

1) 設(shè)Li的起始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)分別為u和v，Lj的起始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)分別為g和k，判斷tk和tu的大小，若tk

圖3 可連接的中繼段向量Fig.3 Relay segment vector can be connected

3) 判斷是否對(duì)L中所有的向量Li和Lj均進(jìn)行過處理，若均進(jìn)行過處理，則得到L的可連接邊的集合Ere，之后執(zhí)行步驟(2)，否則返回步驟1)。

(2) 優(yōu)選可連接邊并連接中繼段向量

對(duì)Ere中的每一條邊(k,u)，將與頂點(diǎn)k和u連接的中繼段向量Lj和Li分別各自進(jìn)行首尾連接并刪除向量，然后進(jìn)行以下處理：

3) 計(jì)算邊(k,u)的權(quán)重：W=w1w2.

4) 判斷是否對(duì)Ere中所有的邊(k,u)均進(jìn)行過處理，若均進(jìn)行過處理，則得到Ere中所有邊的權(quán)重，之后執(zhí)行步驟5)；否則返回步驟1)。

5) 按照權(quán)重由大到小的順序，將Ere中權(quán)重W所對(duì)應(yīng)的邊(k,u)放入邊集合Econ中，并刪除Ere中的邊(k,u)以及與邊(k,u)的頂點(diǎn)k和u存在公共節(jié)點(diǎn)的邊。

6) 判斷Ere中是否還存在邊，若不存在，則根據(jù)Econ將相應(yīng)的中繼段向量連接，得到中繼節(jié)點(diǎn)的航線，否則返回步驟5)。

下面用一個(gè)示例說(shuō)明上述算法，如圖4a)所示，圖中包含4個(gè)中繼段向量和5條可連接邊：

1) 中繼段向量分別各自進(jìn)行首尾連接并刪除向量，計(jì)算圖中各邊的權(quán)重w1，如圖4b)所示。

3) 計(jì)算各邊的權(quán)重W，如圖4d)所示。

4) 依次按照權(quán)重W由大到小，首先在Ere中取出并刪除邊(a,u)，將邊(a,u)放入邊集合Econ中，并且刪除Ere中的邊(k,u)和(c,u)；再在Ere中取出并刪除邊(c,g)，將邊(c,g)放入邊集合Econ中；最后，在Ere中取出并刪除邊(k,b)，將邊(k,b)放入邊集合Econ中；Ere中不存在邊，選擇結(jié)束，得到的Econ中包含的邊為(a,u)，(c,g)，(k,b)；可以看出，原本4個(gè)中繼段向量連接成為1條中繼航線，如圖4e)所示。

圖4 優(yōu)選中繼段向量的連接邊示例Fig.4 Example of optimizing connected edges of relay segment vectors

至此，基于空中分層網(wǎng)絡(luò)的連通性需求，生成了中繼節(jié)點(diǎn)航線，實(shí)現(xiàn)了對(duì)中繼節(jié)點(diǎn)的航線規(guī)劃，同時(shí)保證了算法在降低飛行成本上的優(yōu)化作用。

2.4 中繼航線規(guī)劃流程

中繼航線規(guī)劃方法的流程如圖5所示。在任務(wù)航線時(shí)長(zhǎng)Nt內(nèi)的每個(gè)時(shí)間點(diǎn)，對(duì)拓?fù)銾進(jìn)行2.1和2.2節(jié)所述的生成樹優(yōu)選計(jì)算與中繼節(jié)點(diǎn)位置確定，生成每個(gè)時(shí)間點(diǎn)的中繼段向量。對(duì)得到的任務(wù)航線時(shí)長(zhǎng)Nt內(nèi)的中繼段向量集合L進(jìn)行2.3節(jié)所述的基于權(quán)重的中繼段向量連接，最終生成中繼節(jié)點(diǎn)的航線。

圖5 中繼航線規(guī)劃方法流程Fig.5 Process of the relay route planning method

3 仿真試驗(yàn)與結(jié)果分析

為了驗(yàn)證本文算法的有效性和相較傳統(tǒng)算法的優(yōu)化作用，在基于地圖數(shù)據(jù)的顯示平臺(tái)上進(jìn)行仿真試驗(yàn)，分別對(duì)生成樹優(yōu)選策略和基于權(quán)重的中繼段向量連接方法進(jìn)行功能試驗(yàn)和性能對(duì)比試驗(yàn)。顯示平臺(tái)中用紅色帶箭頭的折線表示骨干網(wǎng)飛機(jī)飛行任務(wù)航線，藍(lán)色帶箭頭的折線表示子網(wǎng)長(zhǎng)機(jī)飛行任務(wù)航線，黃色線段表示同一時(shí)刻2個(gè)任務(wù)航線節(jié)點(diǎn)之間的可連通性，綠色帶箭頭的折線表示本算法生成的中繼節(jié)點(diǎn)的飛行航線。

3.1 功能試驗(yàn)

3.1.1 生成樹優(yōu)選策略

以骨干網(wǎng)飛機(jī)飛行任務(wù)航線為例進(jìn)行生成樹優(yōu)選策略功能試驗(yàn)，其中RKDL=200 km，航線規(guī)劃的實(shí)際時(shí)間間隔為100 s，骨干網(wǎng)飛機(jī)速度為250 m/s。如圖6a)為輸入的骨干網(wǎng)飛行任務(wù)航線，對(duì)該任務(wù)航線進(jìn)行中繼航線規(guī)劃，生成中繼節(jié)點(diǎn)航線。由于飛行航線具有時(shí)序特性，為清楚地表示增加中繼節(jié)點(diǎn)的過程，將任務(wù)航線和中繼航線按照時(shí)序進(jìn)行推演，并在時(shí)刻1和時(shí)刻2進(jìn)行截圖，得到圖6b)和6c)。可以看到，圖6b)時(shí)刻的MST為(1,2),(2,3)，優(yōu)選的生成樹為(1,2),(2,3)；圖6c)時(shí)刻的MST為(1,3),(2,3)，而經(jīng)過優(yōu)選的生成樹仍然為(1,2),(2,3)，因此，本文算法需要添加的中繼節(jié)點(diǎn)個(gè)數(shù)為1。若圖6c)時(shí)刻不進(jìn)行生成樹優(yōu)選，而直接由MST決定增加中繼節(jié)點(diǎn)的位置，則需要在(1,3)之間增加另一個(gè)中繼節(jié)點(diǎn)，由此增加的中繼節(jié)點(diǎn)個(gè)數(shù)為2，故通過本文算法的生成樹優(yōu)選策略能夠?qū)崿F(xiàn)增加中繼個(gè)數(shù)的優(yōu)化。

圖6 生成樹優(yōu)選試驗(yàn)Fig.6 Test of MST optimization

3.1.2 基于權(quán)重的中繼段向量連接方法

以骨干網(wǎng)飛機(jī)飛行任務(wù)航線為例進(jìn)行基于權(quán)重的中繼段向量連接方法功能試驗(yàn)，其中RKDL=600 km，航線規(guī)劃的實(shí)際時(shí)間間隔為1 000 s，骨干網(wǎng)飛機(jī)速度為250 m/s。如圖7a)所示為輸入的骨干網(wǎng)飛行任務(wù)航線為拓?fù)?時(shí)，生成的中繼段向量為R0,R1,R2,R3，通過本文的中繼段向量連接方法得到2條中繼節(jié)點(diǎn)航線。以拓?fù)?的骨干網(wǎng)飛行任務(wù)航線為輸入(拓?fù)?是在拓?fù)?的基礎(chǔ)上添加了骨干網(wǎng)飛行任務(wù)航線5)，進(jìn)行仿真試驗(yàn)得到圖7b)?？梢钥闯觯傻闹欣^段向量為R0,R1,R2,R3,R4，通過本文的中繼段向量連接方法得到2條中繼節(jié)點(diǎn)航線；若按照拓?fù)?中中繼段向量連接方式，將R0,R1,R3連接，則將形成3條中繼節(jié)點(diǎn)航線，故通過本文基于權(quán)重的中繼段向量連接方法，能夠?qū)崿F(xiàn)最終生成的中繼節(jié)點(diǎn)航線個(gè)數(shù)的優(yōu)化。

圖7 生成樹優(yōu)選試驗(yàn)Fig.7 Test of MST optimization

3.2 性能試驗(yàn)

3.2.1 生成樹優(yōu)選策略

由于生成樹優(yōu)選策略只對(duì)添加中繼節(jié)點(diǎn)個(gè)數(shù)不超過1的特定拓?fù)渚哂袃?yōu)化作用，因此，選取5個(gè)典型的拓?fù)錇檩斎耄謩e采用傳統(tǒng)MST算法和生成樹優(yōu)選策略進(jìn)行對(duì)比試驗(yàn)。其中，RKDL=200 km，RZDL=100 km，航線規(guī)劃的實(shí)際時(shí)間間隔為1 000 s，骨干網(wǎng)和子網(wǎng)飛機(jī)速度均為250 m/s，試驗(yàn)結(jié)果如圖8所示，2種算法增加的中繼節(jié)點(diǎn)個(gè)數(shù)對(duì)比如圖9所示?？梢钥闯觯疚牡纳蓸鋬?yōu)選策略相較MST算法，能夠有效減少增加中繼節(jié)點(diǎn)的數(shù)量。

圖9 中繼節(jié)點(diǎn)個(gè)數(shù)對(duì)比Fig.9 Comparison of relay node number

3.2.2 基于權(quán)重的中繼段向量連接方法

選取5個(gè)典型的拓?fù)錇檩斎?，在本文生成樹?yōu)選策略的基礎(chǔ)上，分別采用隨機(jī)連接中繼段向量方法和本文的基于權(quán)重的中繼段向量連接方法，對(duì)中繼航線規(guī)劃進(jìn)行對(duì)比試驗(yàn)。其中，拓?fù)?的RKDL=600 km，RZDL=600 km，拓?fù)?,3,4,5的RKDL=600 km，RZDL=500 km，航線規(guī)劃的實(shí)際時(shí)間間隔均為1 000 s，骨干網(wǎng)和子網(wǎng)飛機(jī)速度均為250 m/s，試驗(yàn)結(jié)果如圖10所示，2種中繼段向量連接方法增加的中繼節(jié)點(diǎn)個(gè)數(shù)對(duì)比如圖11所示?？梢钥闯?，本文基于權(quán)重的中繼段向量連接方法相較隨機(jī)連接中繼段向量方法，能夠有效減少增加中繼節(jié)點(diǎn)的數(shù)量。

圖10 中繼段向量連接方法試驗(yàn)Fig.10 Test of relay segment vector connection method

圖11 中繼節(jié)點(diǎn)個(gè)數(shù)對(duì)比Fig.11 Comparison of relay node number

4 結(jié)束語(yǔ)

飛行編隊(duì)前出必須基于任務(wù)進(jìn)行航線規(guī)劃，空中分層網(wǎng)絡(luò)的航線規(guī)劃需要滿足連通性需求，為飛機(jī)編隊(duì)協(xié)同完成任務(wù)提供通信保障。本文以飛行編隊(duì)任務(wù)航線規(guī)劃結(jié)果為輸入，通過在骨干網(wǎng)和子網(wǎng)的任務(wù)飛機(jī)節(jié)點(diǎn)之間添加中繼節(jié)點(diǎn)的方式，實(shí)現(xiàn)空中分層網(wǎng)絡(luò)的連通性。本文在MST算法的基礎(chǔ)上考慮了相鄰時(shí)刻生成樹的變化對(duì)中繼節(jié)點(diǎn)個(gè)數(shù)的影響，實(shí)現(xiàn)了生成樹優(yōu)選；以中繼段向量的度和中繼節(jié)點(diǎn)的飛行時(shí)間為權(quán)重，達(dá)到了將盡量多的中繼段向量連接的目的。仿真結(jié)果驗(yàn)證了該方法能夠有效減少使用的中繼節(jié)點(diǎn)個(gè)數(shù)?？罩蟹謱泳W(wǎng)絡(luò)可能具有各種復(fù)雜的拓?fù)浣Y(jié)構(gòu)，本文的方法只適用于兩點(diǎn)之間的中繼節(jié)點(diǎn)個(gè)數(shù)不超過1個(gè)的特定拓?fù)涞倪B通性規(guī)劃，適用性受限。后續(xù)研究應(yīng)當(dāng)關(guān)注在航線之間的距離較遠(yuǎn)的情況下，如何保障網(wǎng)絡(luò)連通性并實(shí)現(xiàn)解決方案的優(yōu)化。

[1] 趙悅,陳雷,程子傲,等.車載自組織網(wǎng)絡(luò)中基于蟻群算法的簇路由協(xié)議[J].計(jì)算機(jī)測(cè)量與控制,2016,24(10):259-262. ZHAO Yue,CHEN Lei,CHENG Zi-ao,et al.Ant Colony Algorithm Based Cluster Routing Protocol Vehicular Ad Hoc Network[J].Computer Measurement & Control,2016,24(10):259-262.

[2] 周濤,邢凱,劉剛,等.利用協(xié)作通信的中繼節(jié)點(diǎn)放置問題研究[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(11):2508-2512. ZHOU Tao,XING Kai,LIU Gang,et al.Research on Relay Node Placement via Cooperative Communication[J].Journal of Chinese Computer Systems,2013,34(11):2508-2512.

[3] 黃健文,倪衛(wèi)明.一種通過加入中繼節(jié)點(diǎn)以修復(fù)大面積網(wǎng)絡(luò)損壞的能量均衡算法[J].微型電腦應(yīng)用,2013,29(4):58-61. HUANG Jian-wen,NI Wei-ming.An Energy-Efficient Healing Algorithm for Connectivity Restoration in Wireless Sensor Networks through Relay Node Placement[J].Microcomputer Applications,2013,29(4):58-61.

[4] AZIZ A A,SEKERCIOGLU Y A,FITZPATRICK P,et al.A Survey on Distributed Topology Control Techniques for Extending the Lifetime of Battery Powered Wireless Sensor Networks[J].IEEE Communications Surveys & Tuyorials,2013,15(1):121-144.

[5] NIGAM A,AGARWAL Y K.Optimal Relay Node Placement in Delay Constrained Wireless Sensor Network Design[J].European Journal of Operational Research,2014,233(1):220-233.

[6] Andrew N Kopeikin,Sameera S Ponda,Luke B Johnson,et al.Real-Time Dynamic Planning to Maintain Network Connectivity in a Team of Unmanned Air Vehicles[J].IEEE Globecom Workshops,2011,12(1):1303-1307.

[7] ZHU Han,A Lee Swindlehurst,LIU K J R.Optimization of MANET Connectivity Via Smart Deployment/Movement of Unmanned Air Vehicles[J].IEEE Transactions on Vehicular Technology,2009,58(7):3533-3546.

[8] Ahmed S Ibrahim ,Karim G Seddik,LIU K J R.Connectivity-Aware Network Maintenance and Repair via Relays Deployment[J].IEEE Transactions on wireless communications,2009,8(1):356-366.

[9] Manisha Mishra,XU Han,David Sidoti,et al.Multi-Objective Coordinated Path Planning for a Team of UAVs in a Dynamic Environment:19th ICCRTS,2014[C]∥Command and Control Research Program,Washington D.C,USA,June 16-19,2014:30-45.

[10] 陳凌,梁加紅,胡志偉,等.無(wú)人飛行器Ad Hoc網(wǎng)絡(luò)中基于容錯(cuò)的中繼節(jié)點(diǎn)配置[J].系統(tǒng)工程與電子技術(shù),2012,34(1):179-184. CHEN Ling,LIANG Jia-hong,HU Zhi-wei,et al.Fault Tolerant Relay Node Placement in UAVs Ad Hoc Networks[J].Systems Engineering and Electronics,2012,34(1):179-184.

[11] 徐贊新,袁堅(jiān),王鉞,等.一種支持移動(dòng)自組網(wǎng)通信的多無(wú)人機(jī)中繼網(wǎng)絡(luò)[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版,2011,51(2):150-155. XU Zan-xin,YUAN Jian,WANG Yue,et al.UAV Relay in Network to Provide Communications Mobile Ad Hoc Networks[J].Journal of Tsinghua University:Natural Science ed,2011,51(2):150-155.

[12] 李杰,宮二玲,孫志強(qiáng),等.航空自組網(wǎng)中面向容錯(cuò)的中繼節(jié)點(diǎn)速度控制[J].國(guó)防科技大學(xué)學(xué)報(bào),2015,37(4):158-164. LI Jie,GONG Er-ling,SUN Zhi-qiang,et al.Relay Speed Control for Realization of Fault-Tolerant Aeronautical Ad Hoc Networks[J].Journal of National University of Defense Technology,2015,37(4):158-164.

[13] Morteza Romoozi,VAHIDIPOUR S M,Hamideh Babaei.Improvement of Connectivity in Mobile Ad-Hoc Networks by Adding Static Nodes Based on a Realistic Mobility Model[C]∥The Second International Conference on Machine Vision,Washington D.C,USA,December 28-30,2009:138-142.

[14] 張臻,王光磊.基于改進(jìn)蟻群算法的飛行器航跡規(guī)劃[J].指揮信息系統(tǒng)與技術(shù),2011,2(3):30-34. ZHANG Zhen,WANG Guang-lei.Aircraft Route Planning Based on Improved Ant Colony Algorithm[J].Command Information System and Technology,2011,2(3):30-34.

[15] 王桂平,王衍,任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用[M].北京:北京大學(xué)出版社,2012:88-109. WANG Gui-ping,WANG Yan,REN Jia-chen. Algorithm Theory,Implementation and Application of Graph Theory[M].Beijing:Peking University Press,2012:88-109.