[發明專利]不確定性視角下航空集群機載網絡Group-Oblivious組播路由方法

有效

• 申請號: 202210874612.8
• 申請日: 2022-07-22
• 公開（公告）號: CN115225566B
• 公開（公告）日: 2023-05-23
• 發明（設計）人: 呂娜;潘穎;侯蓓
• 申請（專利權）人: 中國人民解放軍空軍工程大學
• 主分類號: H04L45/16
• 分類號: H04L45/16;H04L47/80;H04L12/46
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.不確定性視角下航空集群機載網絡Group-Oblivious組播路由系統，其特征在于，具體如下：

航空集群機載網絡是由一個骨干網和多個戰術邊緣子網構成的大規模異構網絡；在子網數目為k的航空集群機載網絡中；指揮控制平臺C2平臺位于骨干網中，作為組播源節點，階段性地向戰術邊緣子網中的一組飛機平臺發送任務規劃消息；

SD-ATN的架構包含SDN范式的三個平面，即應用平面、控制平面和數據平面，在SD-ATN中，所有空中平臺節點均具備SDN路由與轉發功能；

假設SD-ATN中所有平臺都配備支持BIER轉發功能的SDN路由器SDR，則每個平臺都能夠建模為一個BFR；SD-ATN將控制平面和數據平面相互分離；在GOR路由策略中，ATN中央控制器制定路由，BFR只負責轉發；控制器根據網絡實時拓撲計算路由、配置BFR，并向其下發BIFT；

GOR將BIER分層部署在SD-ATN中；骨干網絡是BIER子域0，其余k個戰術邊緣網絡分別對應子域1到子域k，k為正整數；

將航空集群機載網絡BIER分層部署系統分為三層：組播上層、BIER層以及路由底層；

組播上層中產生從源節點到一組接收節點的任務規劃消息組播傳輸請求；當任務規劃消息的數據包到達子域0的BFIR節點時，BFIR為數據包封裝指示其目的地的BIER報頭；規定封裝格式如表1所示：BIER報頭按照從高位到低位的順序，依次包括子域SD、集合號SI、位索引字符串BitString、校驗位Check字段；其中，SD字段表示所處BIER子域，SI字段表示序列號，用于擴充BitString長度；BitString為目的節點位串，其置位為1的比特位所對應BFR-ID的路由器即為目的節點；Check字段用于校驗；

表1?任務規劃消息BIER封裝幀格式

BIER層充當點對多點的無狀態轉發隧道，將數據包通過BIER子域轉發到BIER報頭所指示的所有接收路由器；使用HF-BIER分層部署模型，TBFR是在各個子域中選舉出的子域代表；由于任務規劃消息的所有可能接收者都位于戰術邊緣子網中，因此在編號為0的SD中并沒有部署TBFR，并從其它每個SD中各選舉出一個TBFR；TBFR負責中轉傳送發送給它的SD的數據包；在接收到該數據包后，TBFR通過添加BIER報頭的方式重新封裝該數據包并繼續將重新封裝的數據包轉發到SD內的目的節點所對應的正確BFER；當重新封裝的數據包到達正確的BFER時，正確的BFER會從數據包中移除BIER報頭，并將沒有報頭的數據包傳遞給組播上層以進行進一步處理；

路由底層負責在不同的BFR之間建立鄰接關系，為BIER數據包的轉發提供物理拓撲和更合理的路徑，并為BIFT的生成提供參考。

2.不確定性視角下航空集群機載網絡Group-Oblivious組播路由方法，其基于權利要求1所述的不確定性視角下航空集群機載網絡Group-Oblivious組播路由系統，其特征在于，具體包括下列步驟：

step1、問題建模

從源節點到任意一個組播成員的路由分為兩步：將任務規劃消息從C2源節點發送給接收節點所在BIER子域的TBFR；由TBFR轉發至該子域的接收節點，如果TBFR恰好為組播成員則無需進行第二步；底層路由問題轉化為模型求解：在航空集群機載網絡中構建一棵以源節點為根、覆蓋各戰術邊緣子網，且葉節點為TBFR的子樹T，通過最短路由將各戰術邊緣子網TBFR節點與同一戰術邊緣子網中其它節點相連通；

根據SD-ATN控制器提供的網絡實時拓撲圖，將集群成員及其間通信鏈路分別對應節點集合V和邊的集合E，則航空集群機載網絡可以用圖G(V，E)表示；記圖G(V，E)中節點數目|V|＝n，邊的數目|E|＝m；記骨干網節點集合為S₀，其余k個子網則代表戰術子網，編號為S₁到S_k；若兩個節點v_i，v_j間存在可行通信鏈路，則以兩節點為端點的邊e存在；定義反映鏈路通信時延大小的代價函數c：E→R⁺，R⁺表示正的自然數全集；將邊e的權值定義為該邊對應函數值c(e)，抽象出航空集群機載網絡對應圖G(V，E)；

假設隨機到達無線信道的消息近似服從M/M/1排隊模型，根據排隊論相關理論，該信道上某個時刻的通信時延c(x_e)表示為函數

其中，u_e為邊e所對應信道帶寬，x_e表示信道當前實際負載量；當帶寬u_e為定值時，隨著負載量的增大，時延增加；考慮負載量不超過鏈路帶寬的情況，定義相對負載z_e為

當0＜x_e＜u_e時，0＜z_e＜1；將(2)代入公式(1)，得到時延代價函數c(e)的表達式為

記C2平臺在圖G中所對應節點為根節點r∈V，求圖G(V，E)的一棵最小代價子樹T(V_t，E_t)，使得樹T的節點集合V_t能夠覆蓋k個子網S₁，S₂，...，S_k，即：對于任意1≤i≤k，都至少存在一個節點v∈S_i，且滿足在樹圖T中該節點v與節點r之間存在一條路徑；

step2、算法設計

具體步驟如下：

定義C表示圖G(V，E)中所有邊的權重之和，即

C＝∑_eEEc(e)；??(4)

對于圖G的每個子網S_i，在其中人工添加一個輔助頂點q_i，同時添加一系列邊(v，q_i)將輔助頂點q_i與子網中所有節點v(v∈S_i)分別相連；將新添加的點集和邊集分別記為Q和R；形成新的圖G′(V′，E′)，其中V′、E′分別為圖G′的點集和邊集，且有

按下式所述代價函數計算新的圖G′(V′，E′)中各邊代價值：

其中，u表示圖G′中任意節點、d(u，v)表示節點u與節點v之間的圖上距離，e＝(v，q_i)表示在k個子網中添加的邊(v，q_i)；

將新添加的邊(v，q_i)代價定義為該邊的端點v和與v位于同一子網S_i中的其它節點之間的最長圖上距離加上C；邊(v，q_i)的權值越大，表示若將節點v部署為TBFR節點可能導致的組播時延越高；

得到一個新的圖G′(V′，E′)；為在多項式時間內找到一個以節點r為根的最小代價樹，將新的圖G′(V′，E′)中的斯坦納樹問題用一個虛擬的最小費用流問題等效近似求解，具體如下式：

其中，f(e)表示各邊e上的虛擬流量大小，c′(e)按公式(6)計算，f(u，v)表示邊(u，v)上的虛擬流大小、k為子網個數、w表示新的圖G′(V′，E′)上的任意節點、V′表示新的圖G′(V′，E′)節點全集、Q表示前述人工添加的輔助節點集合、{r}表示由這個根節點r構成的集合、q_i表示人工添加的某個輔助頂點；在該最小費用流問題中，供給量和各邊容量均等于整數k，則公式(7)所述問題存在各元素均為整數的最優解流量向量其中f(e₁)...f(e_|G|)分別表示圖G′(V′，E′)上各邊流量大小，G′表示圖G′(V′，E′)；將整數解流量向量非零元素所對應邊的集合記為E_t′，t′表示對應于樹形圖T′(V_t′，E_t′)，由E_t′構成的樹形圖T′(V_t′，E_t′)即為圖G′(V′，E′)上的最小代價斯坦納樹問題的解；

去除樹形圖T′(V_t′，E_t′)中的人工輔助點集Q和邊集R后得到樹形圖T，該樹形圖T包含每個子網S_i中至少一個節點，即為原圖G(VE)上組群斯坦納樹問題的可行解；按此樹形結構分層部署BIER，將樹形圖T的葉節點配置為對應TBFR，即可保證組播時延最小化。