基於反向傳播的衛星分布式路由算法的改進方法
2023-08-09 20:54:06
專利名稱：基於反向傳播的衛星分布式路由算法的改進方法
技術領域：
本發明涉及衛星路由算法領域，特別是針對基分布式路由算法的負載均衡優化領域，具體是指一種基於反向傳播的衛星分布式路由算法的改進方法。
背景技術：
在單層衛星網絡中，研究對象主要集中在單層圓極軌道低軌道(Low EarthOrbit, LEO)衛星網上。這種採用圓極軌道布星的星座，衛星節點組成一個規則的網狀結構。由於衛星軌道的平行分布，相鄰軌道間的星間鏈路可以繼續保持，極大地減少了網絡中的鏈路切換和重建路由次數，降低了協議涉及的複雜度。目前已經提出的單層LEO衛星網絡路由協議算法有 DRA(Distributed Routing Algorithm)、MASSR(distributedSoft routing algorithm combined with mult1-agent system)、CGR(Contact GraphRouting) > X-YBRA(X-Y Boundary Routing Algorithm)等多種。然而，衛星網絡仍然面臨不少問題。隨著全球業務與日俱增，業務種類也在不斷擴展，使得對服務質量的要求也日益提高。另外，城市業務密集，鄉村業務稀疏，甚至在佔地球表面積達到75%的海洋地區幾乎沒有業務，這將導致全 球部分區域上空的衛星出現擁塞，而部分衛星利用率過低的現象。如何合理地設計衛星路由，儘可能地減少網絡擁塞、增加對全局負載的考慮，提高網絡資源利用率是衛星路由算法亟待解決的難題。在上述的眾多LEO層的路由算法中，由Ekici E等人提出的DRA算法具有能動態選路、適應時變網絡拓撲等優點，得到了廣泛應用。但該算法缺乏對全局負載的考慮，並且整個網絡路由狀態具有不穩定性。具體表現為通信連結時的不穩定性，可能造成不必要的報文丟失，甚至嚴重時鏈路中斷。
發明內容
本發明的目的是提出一種基於反向傳播(Back Propagation, BP)的衛星分布式路由算法的改進方法，對DRA算法進行了負載均衡的優化，增加了發送概率、修正概率的參量，用以衡量衛星以及衛星星群是否處於過載狀態，通過反饋修正概率修改發送概率，利用發送概率來控制發送報文方向，延長過載衛星處理擁塞信息的時間，使改進後的路由算法(BP-DRA)增加對全局負載的考慮，更好地服務於衛星通信。首先給出相關定義:(I)為衛星周圍每個方向添加I個修正概率。對於單個報文，只用到當前首要方向的修正概率Pp修正概率預測了該方向上下一跳衛星負載情況，負載越重，修正概率越大。(2)對某一報文，送入相應方向輸出緩衝區之前，計算其首要方向和次要方向的發送概率P t，報文會根據發送概率以擁塞的方式送入首要方向或次要方向，例如，當某方向修正概率為80%時，以該方向為首要方向的報文，每10個報文中會有8個送入該方向，而2個送入報文的次要方向。下式中A1為首要方向發送概率，八為次要方向發送概率，為首要方向的修正概率。
P、='-P,A2=Ofpr(3)當衛星發現首要方向和次要方向都擁塞，或者各個方向的修正概率都超過警戒線的狀態，稱為過載。過載的作用是讓附近的衛星儘量避免轉發報文至該衛星。當前衛星的各個方向修正概率表明了各個方的擁塞情況，當其均超過警戒線時，要儘量避免報文進入當前衛星。可見，在無修正概率的時候，報文只會送入首要方向。添加了修正概率的基於BP的反向修正流程，如圖1所示。步驟110:路由算法開始。步驟120:衛星A向衛星B發送報文。步驟130:檢測衛星B是否過載，當衛星B過載時執行步驟140 ;否則執行步驟150。步驟140:對於新到達的報文回傳一個過載信號給前一衛星A，過載信號包括該報文的兩個可選方向；然後執行步驟160。步驟150:沿用DRA算法；然後跳轉步驟180。步驟160:未收到過載信號的衛星A，根據之前的修正概率來計算發送概率，並發送報文。收到過載信號的衛星A，先分析信號信息，得知原先報文的兩個可選方向。步驟170:衛星A將回傳衛星B的方向修正概率增加1%，並將另一個可選方向的修正概率減少1%。步驟180:每個一段時間，將衛星A各個方向的修正概率下調1%。步驟190:等待下一條信號，重新開始算法。這樣，對於首要方向處於過載的衛星B的報文，其內就減小了，而A2則增加了。發向過載區域的報文減少了，則收到過載信號的頻率也會降低，修正概率增加的速度也逐漸減緩。但是修正概率的增加不是無止盡的，當不再有過載信號傳回(意味著前方通信狀況好轉)時，修正概率就不會變化了。另外，如果相鄰方向過載，也會減少該方向的修正概率。這樣，每個方向的修正概率最後會達到一種動態均衡，以儘可能避免進入過載區域，並充分利用相鄰路徑。( 4 )為了防止大範圍擁塞減緩後，各方修正概率不下降，導致報文不選擇最少跳數路徑的情況，衛星每隔一定時間將所有方向的修正概率按幅度1%遞減直至O。顯然，如果前方依舊過載，這個減小量很快就會被抵消。如果前方正常通信，衛星也會在一段時間後恢復到選擇最短路徑的方案。
圖1基於BP的反向修正流程；圖2基於BP-DRA方案記憶過程一；圖3基於BP-DRA方案記憶過程二 ；圖4基於BP-DRA方案記憶過程三。
具體實施方式
下面結合附圖對本發明做進一步說明。本發明的目的是基於反向傳播的衛星分布式路由算法的改進方法。具體為當衛星B沒有過載時，不做出其它動作，沿用DRA算法。當衛星B過載時，對於新到達的報文回傳一個過載信號給前一衛星A。過載信號包括該報文的兩個可選方向。對於未收到過載信號的衛星A，根據之前的修正概率來計算發送概率，並發送報文。對於收到過載信號的衛星A，先分析信號信息，得知原先報文的兩個可選方向。將回傳衛星B修正概率增加1%，並將另一個可選方向的修正概率減少1%。最後為了防止大範圍擁塞減緩後，各方修正概率不下降，導致報文不選擇最少跳數路徑的情況，衛星每隔一定時間將所有方向的修正概率按幅度1%遞減直至O。顯然，如果前方依舊過載，這個減小量很快就會被抵消。如果前方正常通信，衛星也會在一段時間後恢復到選擇最短路徑的方案。假設:( I)為使過載情況不再惡化，所有衛星對A送入的數據最大處理能力為每時隙8個報文，並且除了接收中心衛星的報文，沒有其他任務。(2)上方衛星初始狀態為過載。(3)衛星A發送的報文首要方向都是上方，次要方向都是右方。如圖2所示，第I時隙時，衛星A送出了 10個報文，根據內=1_0%=1，所以10個報
文送入上方，超過處理能力，每個報文都在過載狀態，傳回10個過載信號，上方的修正概率變為10%。在圖3所示，第2時隙時，衛星A送出了 10個報文，根據所以其中
9個報文送入上方，超過處理 能力。我們可以發現，當上方衛星已經處在過載狀態時，再以每時隙9個報文送入數據，必將導致每個報文都在過載狀態，這樣就會傳回9個過載信號，上方修正概率變為19%。I個報文送入右方,無過載信號傳回。如圖4所示，第3時隙時，衛星A送出了 10個報文，此時修正概率為19%，根據A1 =1_19%=0.81，所以其中8個送入上方，由於剛好符合處理能力，報文不再處於過載狀態，
也就不回傳過載信號，上方修正概率保持為0.81，2個報文送入右方，無過載信號傳回。第4時隙及以後，可見最佳非過載分配方案是10個報文中8個發向上方，而2個報文發向右方。若負載情況不變，則一直不會再有過載信號，衛星A也就記住並維持該方案。在此說明書中，本發明已參照特定的實施實例做了描述。但是，很顯然仍可以做出各種修改和變換而不背離本發明的精神和範圍。因此，說明書和附圖應被認為是說明性的而非限制性的。
權利要求
1.一種基於反向傳播的衛星分布式路由算法的改進方法，其特徵在於:(1)為分布式算法加入了反向修正的步驟，增加了對全局負載的考慮；(2)針對衛星分布式路由算法，提出了修正概率、發送概率的計算方法，使得報文的發送受到負載均衡的控制；(3)為修正概率之間創建了聯繫，讓報文在各個方向的發送得以相互關聯，適應網絡的動態變化。
2.根據權利要求1所述的基於反向傳播的衛星分布式路由算法的改進方法，其特徵在於:當衛星收到報文並對其選擇轉發方向時，首要和次要方向均擁塞，即過載情況時，會向該報文的上一跳發送一個過載信號，提示上一跳衛星。
3.根據權利要求1所述的基於反向傳播的衛星分布式路由算法的改進方法，其特徵在於:收到過載信號的衛星會增加該方向的修正概率Pd這樣，修正概率就能體現路徑前方的負載情況，對於以該方向為首要方向的報文，其首要方向的發送概率A1 =1-A，其次要方向發送概率A =0^P,，報文的發送受到了前方負載的控制。
4.根據權利要求1所述的基於反向傳播的衛星分布式路由算法的改進方法，其特徵在於:當衛星增加某一 方向的修正概率P ^時，同時也會減少其相鄰方向的修正概率。
全文摘要
本發明提供一種基於反向傳播的衛星分布式路由算法的改進方法。具體為(1)為分布式算法加入了反向修正的步驟，增加了對全局負載的考慮；(2)針對衛星分布式路由算法，提出了修正概率、發送概率的計算方法，使得報文的發送受到負載均衡的控制；(3)為修正概率之間創建了聯繫，讓報文在各個方向的發送得以相互關聯，適應網絡的動態變化。本方法既保持了分布式路由算法的特性，如無需考慮拓撲變化、對星上存儲要求較小等特點，又有效地避免了全局負載的不平衡導致的鏈路利用率和端到端時延等路由指標的下降。
文檔編號H04L12/721GK103236987SQ20131016269
公開日2013年8月7日 申請日期2013年5月7日 優先權日2013年5月7日
發明者廖勇, 周穎佳, 李延甲, 孫邈, 魏海波 申請人:重慶大學