[發明專利]利用快速收斂蟻群算法的衛星網絡拓撲生成方法

有效

• 申請號: 201810239605.4
• 申請日: 2018-03-22
• 公開（公告）號: CN108540204B
• 公開（公告）日: 2020-10-23
• 發明（設計）人: 楊力;劉蘊;魏德賓;蔡睿妍
• 申請（專利權）人: 大連大學
• 主分類號: H04B7/185
• 分類號: H04B7/185;H04W84/06;H04W40/24
• 代理公司: 大連智高專利事務所(特殊普通合伙) 21235
• 代理人: 李猛

1.利用快速收斂蟻群算法的衛星網絡拓撲生成方法，其特征在于：包括以下步驟：

A、建立衛星網絡模型

衛星網絡由眾多的衛星節點和星間鏈路構成，且具有以下特點：

(1)網絡各節點位置以及節點間的相對距離都是以時間為變量的函數；

(2)節點的鄰居狀況具有周期性；

(3)網絡節點總數不會發生變化；

(4)衛星網絡各個節點間的距離不能忽略；

(5)網絡的拓撲關系呈周期變化；

根據上述五個特點，建立衛星網絡模型如下：

A1、建立衛星節點模型

對于衛星節點，考慮其節點編號、衛星節點的連接度以及潛在鏈路個數，即：

Sat＝{num,degree,latent} (1)

式中，Sat表示衛星節點；num表示衛星節點編號；degree為衛星節點的連接度；latent表示此節點存在潛在鏈路的個數；衛星節點編號采用v_i，i＝1,2,…,N的形式；定義網絡中某一節點與其他節點建立鏈路的條數為該節點的連接度；衛星節點的潛在鏈路是指某顆衛星可能與其周圍的衛星存在鏈路的情況，只要衛星節點在可視范圍且有連接時間，就認為它們之間存在潛在鏈路；

A2、建立星間鏈路模型

星間鏈路模型描述為：

Link＝{L(v_i,v_j),T_(i,j),d_(i,j),B_(i,j)} (2)

其中，Link表示星間鏈路；L(v_i,v_j)表示這條星間鏈路是由編號為v_i和v_j的衛星所構成的；T_(i,j)為連接時間，由于衛星處于時刻運動狀態，所以衛星網絡的拓撲具有時變性，因此星間鏈路的狀態會在通斷之間頻繁切換，規定從兩顆衛星可視到不可視的這一時間段為連接時間；d_(i,j)表示此鏈路的長度；B_(i,j)為鏈路容量，單位Mbps；

A3、建立衛星網絡動態模型

衛星網絡是一個各邊權值都是以時間為變量的周期函數的無向圖，其中若兩節點不相鄰，其邊的權值定義為∞；因此，引用圖論的知識，用G(N,E,W_ij(t))來表示衛星網絡拓撲結構；其中，N＝{v₁,v₂,…,v_n}是有限節點集，表示網絡的節點；E是有限邊集，W_ij(t)是節點v_i與節點v_j在時刻t的權值函數，規定衛星與自身的權值函數為0，因此，用矩陣B表示星間鏈路的權值；其表達形式如下：

由于W_ij(t)與W_ji(t)表示的是同一條鏈路的權值，因此W_ij(t)＝W_ji(t)；

B、建立星間鏈路

星間鏈路是衛星網絡的重要組成部分，它在不依賴地面設備的情況下實現所有網絡節點的連接，將各顆衛星有機地聯結為一個整體；對影響星間鏈路建立的兩個鏈路基本屬性進行分析，即兩顆衛星建立的最大可見鏈路長度和兩顆衛星建立的最小連接時間；其建立連接滿足以下兩點：一是兩顆衛星連接的長度小于其最大可見鏈路長度；二是兩顆衛星連接的時間大于其最小連接時間；

B1、分析星間鏈路可見性

每顆衛星節點均處于高速運動狀態，由于衛星在其軌道內運行會受到地球和大氣層的遮擋，所以兩顆衛星所形成的鏈路長度存在一個最大值，即最大可見鏈路長度，用d_AB表示：

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

同時，推出最大地心角表示為：

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

B2、分析星間鏈路連接時間

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

T_Link＝T_end-T_start (7)

其中T_start和T_end分別表示建立鏈路的時刻和鏈路斷開的時刻；為了減小星間鏈路頻繁切換，這里定義最小連接時間T_min，只有當T_Link＞T_min時，才具備建立鏈路的條件；

B3、分析星間鏈路權值

星間鏈路的權值考慮以下三個參數：星間鏈路的長度(d_(i,j))、鏈路連接時間(t_(i,j))以及鏈路容量(B_(i,j))；但是，在實際的衛星網絡參數優化中，很難使多個參數同時達到最優值，只能在它們中間進行協調和折中處理，使各個參數都盡可能的達到最優化；這里采用歸一化的思想，針對多參數目標進行處理，最終得出優化權值；在衛星網絡中，鏈路的容量B_(i,j)由以下公式計算得出：

B_(i,j)＝RS(1+α)×TTL (8)

其中，RS為衛星網絡中的符號率，α為滾降系數，TTL為往返時延；因此，根據衛星網絡的實際情況按照公式(8)計算出鏈路容量的最小值B_min；

當鏈路容量B_(i,j)≥B_min時，星間鏈路正常工作；由此，得到權值(W_ij(t))：

其中，d_max為兩顆衛星間最大可見鏈路長度，t_min為兩顆衛星間最短連接時間，d_max在不同的時刻取值并不相同，即為兩顆衛星間當前時刻的歸一化距離；同理得兩顆衛星間當前時刻的歸一化連接時間以及鏈路容量和將各個因素歸一化處理后，更加客觀公平地反映出各條鏈路的代價；

C、基于改進蟻群算法的衛星網絡拓撲生成優化

將各條星間鏈路的權值定義為星間鏈路上的信息素，鏈路權值的大小定義為信息素的濃度；可達性矩陣T利用鄰接矩陣D來計算；可達性矩陣T表示為：

T＝D¹+D²+…+Dⁿ (10)

計算完成后將可達性矩陣T中不為0的元素均用1替換，以保證可達性矩陣T中所有的元素均為0和1；根據可達性矩陣T，將節點i的總路徑定義為：

t_i＝∑t_ij(j＝1,…,n) (11)

其中，t_ij表示可達性矩陣T中的元素；t_i表示拓撲中i節點到達所有節點的直接和非直接路徑的總和，即節點i的總路徑；n為衛星節點的總數；所以，各個衛星節點的可達性由以下公式計算：

引用鏈路介數的定義：

對于鏈路的重要程度用鏈路介數n_bet[L(v_i,v_j)]來表示，介數越大，鏈路越重要；鏈路介數用公式：

表示；其中，N_lm為節點v_l和v_m之間的最優鏈路條數，N_lm(L(v_i,v_j))表示節點v_l和v_m之間的最優鏈路經過L(v_i,v_j)的條數；

同時，還定義以下變量：為衛星節點v_i與v_j構成的星間鏈路的信息素濃度；adjoin(v_i)為與衛星節點v_i相鄰的衛星節點集；表示從衛星節點v_i跳到衛星節點v_j的概率；m為循環的次數；具體步驟如下：

C1、從編號為1的衛星節點開始，當該衛星節點與其他衛星節點滿足建立潛在鏈路條件時，則在這兩個衛星節點之間建立潛在鏈路，否則不建立潛在鏈路；依次建立各衛星節點與其他衛星節點的潛在鏈路，直到所有節點遍歷完成；

C2、創建人工螞蟻，并將螞蟻平均分配到各個衛星節點上；確保每一個螞蟻都會維護一張鏈路狀態表，鏈路狀態表包含表項1、表項2、表項3、表項4和表項5，分別代表源節點、下一跳節點集、到下一跳節點的概率、下一跳禁忌節點和最優鏈路；

表中源節點為螞蟻每一跳的初始節點，螞蟻從源節點出發存在多個下一跳節點，故表項2設定為下一跳節點集；螞蟻依據概率選擇下一跳的節點，其公式表示為：

其中，為從源節點v_i到目的節點v_j的概率；W_ij(t)表示衛星節點v_i,v_j間鏈路的權值；∑W_ij(t)表示從源節點v_i起始，與所有可能的下一跳節點構成的鏈路的權值之和；在每次完成下一跳動作后，將源節點加入表項4中的下一跳禁忌節點中，以防止螞蟻再次返回源節點，確保螞蟻正向前進；表項5中記錄的是以v_i為初始節點的各條潛在鏈路中的最優值，即為權值最大的鏈路；

C3、將編號為1的衛星節點作為初始節點，依次對與編號為2-n的衛星節點之間的星間鏈路進行蟻群算法優化；螞蟻在兩個衛星節點間按照概率隨機選擇路徑；由于每條鏈路的權值由計算得到，則權值大的鏈路被選擇的概率就越大；螞蟻每經過一條鏈路到達下一跳節點后都使每條鏈路上的信息素濃度發生變化，信息素濃度變化表示為:

其中，為第m+1跳時衛星節點v_i與v_j構成的星間鏈路的信息素濃度，為第m跳時衛星節點v_i與v_j構成的星間鏈路的信息素濃度，ρ為信息素濃度揮發系數，β為信息素濃度增量系數，為信息素濃度增量；此時分為兩種情況：

C31、螞蟻所經過的鏈路恰好為表項5所存儲的最優鏈路，那么所有鏈路上的信息素濃度按照公式(15)進行更新，最優鏈路的β值取1，其余鏈路取0；

C32、螞蟻所經過的鏈路不是最優鏈路，這種情況下該鏈路的β值取ρ，其余鏈路取0；

當螞蟻遍歷過其余所有節點時，更新信息素濃度；

C4、分別以編號為2-n的衛星節點為初始節點，重復步驟C3，直到所有衛星節點遍歷完成后轉到步驟C5；

C5、根據步驟C4的結果，如果存在衛星節點維持的星間鏈路數目大于4條的情況，則需要刪除多余的星間鏈路；刪除鏈路的依據是在衛星節點的整體可達性不變的情況下刪除權值最小的鏈路；如果存在兩條可刪除的鏈路權值相同，則刪除鏈路介數最小的鏈路；如果一個衛星節點存在的鏈路數目小于4，則建立權值最大的潛在鏈路，以確保任意兩個衛星節點間的星間鏈路的數目均等于衛星節點的度。