[發明專利]基于拉格朗日松弛的衛星網絡時隙分配與路由規劃方法

有效

• 申請號: 202010821890.8
• 申請日: 2020-08-15
• 公開（公告）號: CN111970044B
• 公開（公告）日: 2022-03-08
• 發明（設計）人: 馬若飛;曹坤梅;劉功亮;王瑞松;康文靜;鐘志聰
• 申請（專利權）人: 哈爾濱工業大學（威海）
• 主分類號: H04B7/185
• 分類號: H04B7/185;H04L45/30;H04L47/2425
• 代理公司: 威海科星專利事務所 37202
• 代理人: 初姣姣

1.一種基于拉格朗日松弛的衛星網絡時隙分配方法，在設置權重的時候，定義w_ij(t)為在時隙t衛星i與衛星j建鏈的權重值，定義d(i,j,t)為在時隙t衛星i與衛星j之間的距離；定義s(i,t)表示在時隙t與衛星i建鏈的衛星，如果沒有任何衛星與其建鏈，則s(i,t)＝0，定義o(i)表示衛星i所處的軌道，其特征在于，包括以下步驟：

步驟1：獲取待處理衛星網絡中的以下數據：初始的權重矩陣，拉格朗日乘子，時間長度T，最大迭代次數I_max，門限值ε，衛星可見性分析表；

步驟2：根據步驟1所獲取的數據輸出每個時隙的衛星匹配建鏈表；

步驟3：更新權重矩陣，t取值為1至T，q取值范圍為1至I_max，具體包括四種不同情況：

步驟3-1：不重復鏈路建立，最終權重賦值數學表達為：

其中a是一個正常數來表示時間的范圍；

步驟3-2：跨軌道建鏈權重賦值規則表示如下：

步驟3-3：短距離建鏈權重賦值數學表示如下：

步驟3-4：持續建鏈規則權重賦值數學表示如下：

其中g是一個正常數；

步驟4：計算時隙分配結果：

步驟5：計算目標函數值F(q)，若|F(q)-F(q-1)|/||F(q)||＜ε，停止迭代，否則根據式(20)更新拉格朗日乘子，

其中表示y與0的最大值；α_j(k)＞0表示步長并且需要滿足下面的約束；

步驟6：根據公式(22)，計算新的權重矩陣β，新的權重矩陣

其中

步驟7：根據公式(23)，對結果進行處理，

若存在衛星尚未匹配，對權重矩陣刪除已匹配衛星對應的行與列，形成新的權重矩陣；

步驟8：執行步驟3至步驟6，獲得新的匹配結果，并更新匹配表，直至匹配表不再變化輸出最終匹配表；

其中，對于每個時隙而言，每個衛星接收到的數據量加上上一時隙緩存下來的數據量應該等于當前時隙發送出去的數據量加上未發送而儲存在節點中的數據量；因此，給出以下的約束：

對于任務f_kl的起始點來說，任務的發出總量應該等于當前時隙任務成功發送出去的數據量加上儲存在節點的數據量，具體地，

對于任務f_kl的目的節點來說，任務只允許到達目的節點并存儲，而不允許再次發送，因此需要將目的節點的發送量設為0，

由于資源的限制，對每個時隙而言，即使每個衛星可能與多個衛星可見，但是每個衛星只能與一個衛星進行建鏈，也就是說，

考慮到網絡傳輸機制的特殊性，每條鏈接都是一個雙向鏈接，相應地，在圖中也就是無向邊，因此有下面的約束：

考慮到鏈路資源的限制，對于給定的時隙，如果兩個節點建立鏈路，則傳輸的總數據量不能超出鏈路最大傳輸能力；如果兩個節點沒有建立鏈路，則不能傳輸數據，對于這一限制，通過下面的約束來表示：

其中表示在第t個時隙，鏈路的最大傳輸能力。