面向連通性的空中分層網絡中繼航線規(guī)劃方法*

張兆晨，錢寧

(中國電子科技集團公司 第28研究所 信息系統(tǒng)工程重點實驗室，江蘇 南京 210007)

0 引言

飛機編隊執(zhí)行任務通常以空中分層網絡的形式進行組網?？罩蟹謱泳W絡為飛行編隊間的信息交互提供了通信保障，主要包括一個拓撲相對穩(wěn)定的骨干網和若干動態(tài)移動的子網，具有鏈路質量不穩(wěn)定、通信距離受限、拓撲變化快[1]等特點。由于空中分層網絡受到能量、干擾等內外部因素的限制，為保證網絡的連通性，最有效的手段是增加飛行器作為通信中繼節(jié)點。因此，如何以盡量小的代價部署中繼節(jié)點并生成中繼航線，成為亟待解決的問題。

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

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

1 問題分析

空中分層網絡的骨干網拓撲相對穩(wěn)定，主要為編隊提供各種信息業(yè)務支撐，節(jié)點之間通過寬帶鏈路連接；子網拓撲變化較快，由子網長機和子網成員飛機組成，主要執(zhí)行機動任務，子網節(jié)點之間以及子網與骨干網節(jié)點之間通過窄帶鏈路連接。空中分層網絡是飛機編隊完成任務的基礎，航線規(guī)劃[14]要求保證空中分層網絡拓撲中骨干網節(jié)點之間以及骨干網與子網長機節(jié)點之間連通，以支持數據信息的交互。

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

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

(1)t：輸入的任務航線規(guī)劃時間點，t=0,1,…,Nt，Nt為任務航線時長；

(2)U：骨干網和子網長機節(jié)點組成的拓撲；

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

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

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

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

(7)Eac：拓撲U的全連通邊的集合，邊的權重為邊的長度；

(8)Tmst：拓撲U的MST；

(9)Tadj：優(yōu)選后的拓撲U的生成樹，即選擇的拓撲U的節(jié)點之間的連接邊組成的集合；

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

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

(12)vre：中繼節(jié)點的最大運動速度。

需要說明的是，本文生成樹優(yōu)選只適用于2個飛機間添加1個中繼節(jié)點的情況，因為當2個飛機間距離急劇增大時，可能會造成添加中繼節(jié)點個數劇增，故假設本文航線規(guī)劃在2個飛機間的最大距離小于等于相應鏈路的可通信距離2倍的情況下進行。

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

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

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

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

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

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

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

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

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

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

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

(1) 若R

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

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

(4) 判斷是否對Tadj中的每一組邊(u,v)均進行過處理，若均進行過處理，則得到拓撲U在t-1時刻到t時刻的中繼段向量，否則返回步驟(1)。

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

2.3 基于權重的中繼段向量連接方法

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

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

對L的任意2個中繼段向量Li和Lj，進行以下處理：

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

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

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

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

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

3) 計算邊(k,u)的權重：W=w1w2.

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

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

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

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

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

3) 計算各邊的權重W，如圖4d)所示。

4) 依次按照權重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中不存在邊，選擇結束，得到的Econ中包含的邊為(a,u)，(c,g)，(k,b)；可以看出，原本4個中繼段向量連接成為1條中繼航線，如圖4e)所示。

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

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

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

中繼航線規(guī)劃方法的流程如圖5所示。在任務航線時長Nt內的每個時間點，對拓撲U進行2.1和2.2節(jié)所述的生成樹優(yōu)選計算與中繼節(jié)點位置確定，生成每個時間點的中繼段向量。對得到的任務航線時長Nt內的中繼段向量集合L進行2.3節(jié)所述的基于權重的中繼段向量連接，最終生成中繼節(jié)點的航線。

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

3 仿真試驗與結果分析

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

3.1 功能試驗

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

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

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

3.1.2 基于權重的中繼段向量連接方法

以骨干網飛機飛行任務航線為例進行基于權重的中繼段向量連接方法功能試驗，其中RKDL=600 km，航線規(guī)劃的實際時間間隔為1 000 s，骨干網飛機速度為250 m/s。如圖7a)所示為輸入的骨干網飛行任務航線為拓撲1時，生成的中繼段向量為R0,R1,R2,R3，通過本文的中繼段向量連接方法得到2條中繼節(jié)點航線。以拓撲2的骨干網飛行任務航線為輸入(拓撲2是在拓撲1的基礎上添加了骨干網飛行任務航線5)，進行仿真試驗得到圖7b)?？梢钥闯?，生成的中繼段向量為R0,R1,R2,R3,R4，通過本文的中繼段向量連接方法得到2條中繼節(jié)點航線；若按照拓撲1中中繼段向量連接方式，將R0,R1,R3連接，則將形成3條中繼節(jié)點航線，故通過本文基于權重的中繼段向量連接方法，能夠實現最終生成的中繼節(jié)點航線個數的優(yōu)化。

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

3.2 性能試驗

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

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

圖9 中繼節(jié)點個數對比Fig.9 Comparison of relay node number

3.2.2 基于權重的中繼段向量連接方法

選取5個典型的拓撲為輸入，在本文生成樹優(yōu)選策略的基礎上，分別采用隨機連接中繼段向量方法和本文的基于權重的中繼段向量連接方法，對中繼航線規(guī)劃進行對比試驗。其中，拓撲1的RKDL=600 km，RZDL=600 km，拓撲2,3,4,5的RKDL=600 km，RZDL=500 km，航線規(guī)劃的實際時間間隔均為1 000 s，骨干網和子網飛機速度均為250 m/s，試驗結果如圖10所示，2種中繼段向量連接方法增加的中繼節(jié)點個數對比如圖11所示。可以看出，本文基于權重的中繼段向量連接方法相較隨機連接中繼段向量方法，能夠有效減少增加中繼節(jié)點的數量。

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

圖11 中繼節(jié)點個數對比Fig.11 Comparison of relay node number

4 結束語

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

[1] 趙悅,陳雷,程子傲,等.車載自組織網絡中基于蟻群算法的簇路由協(xié)議[J].計算機測量與控制,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é)點放置問題研究[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é)點以修復大面積網絡損壞的能量均衡算法[J].微型電腦應用,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] 陳凌,梁加紅,胡志偉,等.無人飛行器Ad Hoc網絡中基于容錯的中繼節(jié)點配置[J].系統(tǒng)工程與電子技術,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] 徐贊新,袁堅,王鉞,等.一種支持移動自組網通信的多無人機中繼網絡[J].清華大學學報：自然科學版,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] 李杰,宮二玲,孫志強,等.航空自組網中面向容錯的中繼節(jié)點速度控制[J].國防科技大學學報,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] 張臻,王光磊.基于改進蟻群算法的飛行器航跡規(guī)劃[J].指揮信息系統(tǒng)與技術,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] 王桂平,王衍,任嘉辰.圖論算法理論、實現及應用[M].北京:北京大學出版社,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.