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

有效

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

本發明公開了一種利用快速收斂蟻群算法的衛星網絡拓撲生成方法，包括以下步驟：建立衛星網絡模型；建立星間鏈路；基于改進蟻群算法的衛星網絡拓撲生成優化。本發明的蟻群算法在問題空間的多點同時開始進行獨立的解搜索，不僅增加了算法的可靠性，也使得算法具有較強的全局搜索能力。將蟻群算法應用到衛星網絡中，可以獲取全局最優拓撲，并且增強了拓撲的穩定性。本發明用星間鏈路的權值作為蟻群算法的信息素，考慮到了星間鏈路的長度、鏈路連接時間以及鏈路容量這三種因素共同作用對衛星網絡拓撲生成的影響，使生成的衛星網絡拓撲更精確。本發明綜合考慮了三種影響衛星網絡拓撲生成的因素，將其相結合，得出全局最優解。

技術領域

本發明涉及改進的蟻群算法，特別是一種利用快速收斂蟻群算法的衛星網絡拓撲生成方法。

背景技術

衛星網絡具有組成結構復雜、拓撲動態變化、跨越空間尺度大和自組織程度高等特點，這些特點均影響到衛星網絡拓撲的穩定性。穩定的衛星網絡不僅是實現網絡信息交換和資源共享的基礎，而且也是實現網絡管理、協議設計優化、安全控制等的前提。因此，利用可靠的算法進行衛星網絡拓撲生成及優化已經成為國內外的研究熱點。近年來，一些新技術的出現極大促進了衛星網絡的發展，如星上處理(On-board Processing，OBP)、星間鏈路(Inter-satellite Link，ISL)等，這些技術較好地解決了衛星網絡通信時延長，地面通信終端負載過大、功率過小等問題。但這些技術也增加了衛星網絡的部署周期和管理維護成本，同時也增加了衛星節點的復雜性，這無形中增加了衛星網絡拓撲生成的難度。

蟻群算法(Ant Colony Optimization，簡稱ACO)是一種新型的模擬進化算法，其具有很強的魯棒性和搜索更優解的能力，且易于與多種啟發式算法結合，改善算法性能。蟻群算法的核心思想是用螞蟻行走的路徑表示待優化問題的可行解，整個螞蟻群體的所有路徑構成待優化問題的解空間。螞蟻會在走過的路徑釋放信息素，隨著時間的推進，較短的路徑上積累的信息素濃度逐漸增高，選擇該路徑的螞蟻個數也愈來愈多。最終，整個螞蟻會在正反饋的作用下集中到最佳的路徑上。利用蟻群算法進行衛星網絡拓撲生成在時延、衛星節點間鏈路長度以及拓撲的穩定性方面有一定的優勢。

目前，有研究人員提出了一種在保證衛星節點可見性的條件下，采用最短路徑算法生成衛星網絡拓撲。這種算法只考慮了單因素對衛星網絡鏈路的影響，而實際情況下會有多種因素來共同影響衛星網絡的拓撲生成。也有研究人員從影響衛星網絡拓撲結構的多因素出發，提出了一種分布式拓撲生成算法，該算法通過減少鏈路切換次數來改善網絡拓撲的穩定性。但該算法有很大概率陷入局部最優解而非得到全局最優解。

發明內容

為解決現有技術存在的上述問題，本發明要設計一種既能提升衛星網絡拓撲生成的速度以及穩定性，又能得到全局最優解的利用快速收斂蟻群算法的衛星網絡拓撲生成方法。

為了實現上述目的，本發明的技術方案如下：利用快速收斂蟻群算法的衛星網絡拓撲生成方法，其特征在于：包括以下步驟：

A、建立衛星網絡模型

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

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

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

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

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

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

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

A1、建立衛星節點模型

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