[發明專利]一種基于改進蜂群算法的衛星網絡重構方法

有效

• 申請號: 201910244025.9
• 申請日: 2019-03-28
• 公開（公告）號: CN109889255B
• 公開（公告）日: 2021-03-02
• 發明（設計）人: 潘成勝;蔡睿妍;楊力;李金
• 申請（專利權）人: 大連大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04B7/185
• 代理公司: 大連智高專利事務所(特殊普通合伙) 21235
• 代理人: 李猛

1.一種基于改進蜂群算法的衛星網絡重構方法，其特征在于：包括以下步驟：

A、定義衛星網絡模型以及相關評價指標

A1、本發明著眼于衛星節點和鏈路所組成的衛星網絡拓撲重構優化設計問題，暫不考慮地面固定衛星站、地面移動衛星站、地面控制中心對衛星網絡拓撲結構抗毀性的影響；因此，衛星網絡模型表示為：

G＝{Sat,Link}

其中，Sat代表衛星網絡中衛星節點的集合，Link表示衛星網絡中鏈路的集合；

A2、將衛星節點模型表示為：

Sat＝{s,degree,latent}

其中，s表示衛星節點編號、s∈[1,2...,n]；degree為衛星節點的連接度；latent表示此衛星節點存在潛在鏈路的個數；在衛星網絡的背景下，衛星節點攜帶天線數目受其表面積的約束，故衛星節點鏈路連接度是衛星網絡的重要約束條件之一；潛在鏈路的發現取決于可見性和鏈路的連接時間，具體定義如下：

定義1：每顆衛星節點均處于高速運動狀態，由于衛星在其軌道內運行受到地球和大氣層的遮擋，所以兩顆衛星所形成的鏈路長度存在一個最大值，即最大可見鏈路長度；兩顆衛星節點之間的星間鏈路長度表示為如下公式：

其中，R為地球半徑；h_A、h_B分別為衛星A與衛星B所在的軌道高度；ξ為地心角；但在實際情況中，由于星間鏈路受到地球的遮擋，故任意兩顆處于不同軌道的衛星在某一時刻，它們之間的星間鏈路長度存在一個最大值，即為最大可見鏈路長度；此時，衛星A與衛星B之間的鏈路長度d_AB為其最大可見鏈路長度d_max，用下式表示：

進一步求出最大地心角ζ_max為：

即：當兩顆衛星間鏈路長度d_AB滿足d_AB≤d_max，地心角ξ滿足ξ≤ξ_max時，兩顆衛星可見；否則，兩顆衛星不可見，即不存在潛在鏈路；

定義2：由于衛星網絡拓撲具有時變性，所以星間鏈路在連接和斷開兩個狀態間頻繁切換；若要建立穩定的衛星網絡結構，則需對星間鏈路連接時間加以分析；鏈路連接時間T_Link(i,j)是指衛星節點i和衛星節點j從建立鏈路開始，到鏈路斷開的這一段時間，用以下公式表示：

T_Link(i,j)＝T_end(i,j)-T_start(i,j)

其中，T_start(i,j)和T_end(i,j)分別表示衛星節點i和衛星節點j之間鏈路的建立時刻和鏈路斷開的時刻；為了減小星間鏈路頻繁切換，定義最小連接時間T_min，只有當T_Link(i,j)≥T_min時才具備建立鏈路的條件；

A3、衛星網絡結構拓撲圖R中w_ij表示衛星節點i和衛星節點j之間的邊權值，其中邊權值表示衛星節點之間信息流通的難易程度，數值越小信息流通越容易，衛星網絡傳輸效率越高；定義邊權值為兩衛星節點之間最短路徑上的邊數，用d表示；

網絡效率指標E定義為：

其中

d_ij＝min{∑w_ij}

對d_ij取倒數避免衛星節點在不連通情況下衛星網絡中衛星節點距離為∞的情況；

B、建立多目標約束模型

將衛星網絡的拓撲重構問題描述為：給定衛星網絡模型G(Sat,Link)和正整數q，如何合理的選擇有限衛星節點集Sat`，添加有限邊集使得重構后的衛星網絡模型G`(Sat,Link∪Link`)具有最優可生存性，其中衛星網絡可生存性指標用Q表示，即使Q(G`)取得最大值：

Max Q(G`(Sat,Link∪Link`)) (1)

s.t.Link`＝{(u₁,v₁),(u₂,v₂),...,(u_s,v_s)}

(a)

(b)degree≤Max_degree

(c)d_AB≤d_max

(d)ξ≤ξ_max

(e)C_(i,j)≥C_min

(f)0≤Q≤1

其中，可生存性指標Q描述了衛星節點移除對衛星網絡通信效率的影響，反映了衛星通信系統維持信息傳輸功能、適應環境變化的能力，在重構鏈路時必須滿足上述約束關系式(a)-(e)；

C、基于改進蜂群算法的拓撲重構

根據多目標約束模型生成調度方案并計算目標函數，采用人工智能算法對調度方案進行尋優，具體步驟如下：

C1、當衛星網絡拓撲中發生衛星節點失效的情況時，衛星網絡局部鏈路的時延會急劇上升；將涉及鏈路的衛星節點編號為s，其中s∈[1,2...,n]，從s＝1開始、以R_max為半徑搜索區域內可達衛星節點集合作為蜂群待求解食物源，并以鏈路連接條件作為限制條件篩選衛星節點，確立編號為1的種群規模m_s、最大迭代次數L_max，初始化l_s用于記錄遍歷次數，令全局變量v＝1；依次建立剩余編號衛星的待求解衛星節點集合，直到所有衛星節點遍歷完成；

其中，R_max代表該衛星節點的最大搜索半徑，具體表示為：

R_max＝k·T_max·v

式中，k為調節系數，v為衛星網絡中衛星節點移動速度的平均值，T_max為最大工作時間；

C2、在種群的m_s/2中隨機選取一個蜜源x，作為初始解，令v＝v+1，計算并記錄該解的適應度值；

C3、進行鄰域搜尋，為種群中每個解生成一個鄰域解x`<sub>i</sub>；并做如下判斷：如果f(x`_i)＞f(x_best)，則設置x_best＝x`_i，否則x_best不變，令l_s＝l_s+1；蜂群算法適應度函數定義為：

其中，當衛星節點k被移除網絡后，與衛星節點k相連的衛星節點空余出連通度，成為待重構衛星節點；采用隨機故障的方式，故p_k＝1/N，N表示衛星網絡中衛星節點的個數；代表移除衛星節點k后網絡的魯棒性；

C4、判斷每個解連續無更新鄰域搜索次數是否超過規定值L_max；如果l_s＞L_max，則放棄x_i，在剩余m_s/2中隨機取得一個新解加入種群中，且置l_s＝0；更新變量v＝v+1；若v＝m_s/2，算法結束；否則轉到步驟C2繼續執行鄰域搜索操作；

C5、將x_best作為本次算法得到的最優解，對應的鏈路連接作為本次重構最優鏈路選擇；

C6、判斷當前衛星編號是否等于N，若等于N則執行下一步，否則令s＝s+1，然后轉到步驟C2；

C7、連接度判斷，根據步驟C5重構結果判斷當前衛星網絡中的衛星節點連接度是否滿足定義條件；如果存在衛星節點維持的星間鏈路數目大于4條的情況，則刪除多余的星間鏈路，刪除鏈路的依據是根據適應度大小刪除對應鏈路。