自適應(yīng)路由多層衛(wèi)星自適應(yīng)路由策略

多層衛(wèi)星網(wǎng)絡(luò)中的路由策略不同于傳統(tǒng)的靜態(tài)路由。雖然星座拓撲是周期性和確定性的動態(tài)路由能夠動態(tài)地維護路由表并適時地交換路由信息。自適應(yīng)路由策略需要知道網(wǎng)絡(luò)中每條ISL上的長度和通信量，自適應(yīng)地選擇符合有效性和可靠性要求的最優(yōu)路徑。路由計算應(yīng)用離散化的方式在每一個固定時刻t_k計算路由和更新路由表，t_k=kΔt，k=0,1,2,......,K?1并認為在時間區(qū)間Δt內(nèi)網(wǎng)絡(luò)拓撲結(jié)構(gòu)不變，路由恒定采用固定時間切換策略在路由表更新同時發(fā)生切換。

為了進行網(wǎng)絡(luò)分析需要如下假定：

1. 網(wǎng)絡(luò)衛(wèi)星相互獨立；

2. 每顆衛(wèi)星節(jié)點承擔不同業(yè)務(wù)負載按照業(yè)務(wù)模型而定；

3. 每個衛(wèi)星節(jié)點承載的業(yè)務(wù)獨立業(yè)務(wù)量與衛(wèi)星覆蓋的范圍大小和地理位置相關(guān)；

自適應(yīng)路由路由算法

路由算法采用Bellman-Ford后向路由算法最優(yōu)路徑的判則為該路徑的綜合權(quán)重(TPW，totalpathweight)TPW表示了一條路徑的時延和帶寬占用綜合性能，考慮的也是有效和可靠綜合性能。TPW由三部分組成，上行鏈路時延D_u、下行鏈路時延D_d和路徑上每個ISL_wi的鏈路權(quán)重LW_wi，表示路徑上ISL的集合W={w₁,w₂,.......,w_i,......,w_ns-1}，|W|=n_s?1表示該條路徑包含n_s?1條ISL，n_s為該路徑上的衛(wèi)星數(shù)量(包括源衛(wèi)星和目標衛(wèi)星)。其中地面源和目標位置確定之后，采用仰角最大接入方案選定源衛(wèi)星和目標衛(wèi)星。

其中D_wi表示ISL_wi的傳輸時延，W_wi表示平均星上處理和交換時延，f是信息量權(quán)重參數(shù)。D_u、D_d和D_wi的求解只需知道衛(wèi)星空間位置坐標，用鏈路長度除以傳輸速度即可，無需冗。

根據(jù)Jackson原理，針對數(shù)據(jù)包業(yè)務(wù)，可以將每條ISL看成單服務(wù)窗混合制排隊模型M/M/1/m，數(shù)據(jù)包到來的間隔時間服從負指數(shù)分布，參數(shù)為β；服務(wù)時間是參數(shù)為μ為負指數(shù)分布，每條ISL有m個數(shù)據(jù)包排隊容量。當系統(tǒng)中已有m個數(shù)據(jù)包時，新來的數(shù)據(jù)包不再進入排隊。數(shù)據(jù)包被丟棄，有

ρ=β/μ

數(shù)據(jù)包的平均處理和交換時延為

自適應(yīng)路由策略步驟

多層衛(wèi)星網(wǎng)絡(luò)中的路由策略步驟如下：

步驟1設(shè)定基本參數(shù)，網(wǎng)絡(luò)初始化

步驟2固定一個時刻t_k，在該時間區(qū)間t求解衛(wèi)星軌道參量，計算衛(wèi)星位置坐標和ISL長度，建立網(wǎng)絡(luò)拓撲結(jié)構(gòu)

步驟3按照設(shè)定的業(yè)務(wù)模型，計算MLSN的ISL負載

步驟4根據(jù)排隊理論，計算數(shù)據(jù)包星上處理/交換的時延，如式(14)所示

步驟5根據(jù)地面源/目標位置，尋找每個衛(wèi)星層中源衛(wèi)星和目標衛(wèi)星(LEO、MEO和GEO源/目標衛(wèi)星)

步驟6根據(jù)QOS需求和網(wǎng)絡(luò)狀態(tài)，選擇傳輸業(yè)務(wù)的衛(wèi)星層，按照Bellman-Ford路由算法尋找最優(yōu)路徑，缺省的業(yè)務(wù)承載衛(wèi)星層為LEO層，但是如果MEO源/目標衛(wèi)星相同，且LEO源/目標衛(wèi)星不同，執(zhí)行步驟9；如果GEO源/目標衛(wèi)星相同，且LEO和MEO源/目標衛(wèi)星不同，執(zhí)行步驟10；否則執(zhí)行步驟7

步驟7如果該LEO層路徑包含ISL數(shù)量≤ISL_LEO門限，執(zhí)行步驟8；如果該LEO層路徑包含ISL數(shù)量>ISL_LEO門限，且MEO層路徑包含ISL數(shù)量≤ISL_LEO門限執(zhí)行步驟9；否則執(zhí)行步驟10

步驟8建立LEO衛(wèi)星層最優(yōu)通信路徑，完成傳輸任務(wù)

步驟9建立MEO衛(wèi)星層最優(yōu)通信路徑，完成傳輸任務(wù)

步驟10建立GEO衛(wèi)星層最優(yōu)通信路徑，完成傳輸任務(wù)

步驟11統(tǒng)計多層網(wǎng)絡(luò)的特征參量，分析網(wǎng)絡(luò)性能

步驟12更新時間區(qū)間，完成新路由表計算，并完成衛(wèi)星越區(qū)切換

自適應(yīng)路由特征

多層衛(wèi)星網(wǎng)絡(luò)自適應(yīng)路由策略具有如下特征：業(yè)務(wù)通過LEO源衛(wèi)星和目標衛(wèi)星接入衛(wèi)星系統(tǒng)，根據(jù)QOS需要和網(wǎng)絡(luò)狀態(tài)選擇傳輸該業(yè)務(wù)的衛(wèi)星層，如果LEO層網(wǎng)絡(luò)資源不能滿足該業(yè)務(wù)要求，就將該業(yè)務(wù)轉(zhuǎn)到MEO層傳輸甚至GEO層傳輸對于地面源/目標，直接接入MEO或GEO衛(wèi)星情況。因為路由算法實現(xiàn)簡單，所以未作詳細分析。另外仿真結(jié)果所示，LEO層的路徑如果包含6條或7條ISL，時延將大于200ms。這時如果將該業(yè)務(wù)轉(zhuǎn)移到MEO，傳輸時間更短，占用星上資源更少。而且如果地面源和目標位置被同一MEO或GEO衛(wèi)星覆蓋這，時就將該業(yè)務(wù)轉(zhuǎn)到MEO和GEO傳輸，以減少星上資源的占用。該策略考慮時延指標和ISL帶寬占用狀況，最優(yōu)路徑選擇兼顧衛(wèi)星系統(tǒng)有效性和可靠性。

PBFAA算法是一個基于平面的完全自適應(yīng)最短蟲孔路由算法(Planar一BasedFullyAdaptiveAlgorithm，PBFAA)。

人們對直接網(wǎng)絡(luò)中采用蟲孔路由切換技術(shù)的自適應(yīng)路由算法已進行了大量研究，提出了很多算法，但它們或存在自適應(yīng)性受限，或存在代價較大，或存在靈活性不夠等缺點.在已有算法的基礎(chǔ)上，以低通信延遲、高網(wǎng)絡(luò)吞吐率和易VLSI實現(xiàn)為設(shè)計目標，提出了一個可擴展性好、自適應(yīng)性強的基于平面的完全自適應(yīng)路由算法PBFAA。

算法中將網(wǎng)絡(luò)分成兩個虛擬網(wǎng)VIN0和VI1I，VlN0中的虛通道按平面自適應(yīng)路由策略路由消息，VIN1中的虛通道可完全自適應(yīng)路由消息，由VIN0保證算法的無死鎖性.由于兩個網(wǎng)絡(luò)均具有自適應(yīng)性，故與已有一些較好的算法如（channel）相比，該算法自適應(yīng)性更強，更能充分有效地利用網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)吞吐率，且容錯能力更強一下面用n維mesh網(wǎng)絡(luò)介紹PBFAA算法:

1)算法為每條物理通道設(shè)置4條虛通道，用VC_{dimension，label，direction}來表示，其中dimension表示該虛通道沿哪一維傳遞消息；label表示虛通道的序號，取值0，1，2或3；direction可以為 (表示消息將沿正向傳遞)或-(表示消息將沿著逆向傳遞)。例如VC¨，一表示結(jié)點的第一維上的序號為1的負向虛通道。

2)將網(wǎng)絡(luò)劃分成兩個虛擬網(wǎng)：VIN0和VIN1。在VIN0中使用序號從0至2的虛通道；在VIN1中使用序號為3的虛通道。

3)在VIN0中，按平面自適應(yīng)路由策略選擇趨于目的結(jié)點的虛通道路由消息；在VIN1中，按完全自適應(yīng)最短路徑路由策略選擇趨于目的結(jié)點的虛通道路由消息。在兩虛擬網(wǎng)中按相應(yīng)路由策略可被選擇的虛通道均稱為所需虛通道，空閑的所需虛通道稱為可用虛通道。

4)當一條消息的頭微片到達某一結(jié)點時，如該結(jié)點是目的結(jié)點則消息被接收，否則：

a)若有可用虛通道，則對可用虛通道按最大間距輸出虛通道選擇策略，對相應(yīng)維虛通道提出申請Req；若沒有可用虛通道，則暫停提出申請，等待直至有所需虛通道變?yōu)榭捎迷偻咸岢錾暾垼?

b)若申請被響應(yīng)，則沿相應(yīng)虛通道將消息傳向鄰近結(jié)點；若申請未被響應(yīng)，則在下一拍重新執(zhí)行同上述a)的操作，直至有申請被響應(yīng)后將消息傳向鄰近結(jié)點。在每一中間結(jié)點上都重復(fù)執(zhí)行上述操作，直至將消息傳至目的結(jié)點。所謂最大間距輸出虛通道選擇策略是指在允許訪問的通道中，對所在維的維間距(中間結(jié)點到目的結(jié)點)絕對值最大的虛通道首先提出申請，以縮小尋徑區(qū)域。

VIN0中采用的平面自適應(yīng)路由策略為：在n維mesh網(wǎng)絡(luò)中，對每條物理通道的虛通道進行排序，用C_i,j表示第i維上的所有序號為j的虛通道構(gòu)成的集合，它可分為正向的虛通道集合C_i,j 和逆向的虛通道集合C_i,j-平面自適應(yīng)

路由算法定義n一1個自適應(yīng)平面A₀至A_n-1，每個平面由相鄰二維上的虛通道構(gòu)成：A_i=C_i,0 C_{i 1,1} C_{i 1,2，}0≤i≤n-2。算法可分為兩級(高層和低層)：

1. 高層算法：(在自適應(yīng)平面之間)1) For i=0，i<(m-1)，i do在A平面中自適應(yīng)地路由消息趨近目的結(jié)點(見低層算法)end。2)在上述過程結(jié)束后，若消息還未到達目的結(jié)點，則通過A_n-2=C_n-1,0中的虛通道路由消息至目的結(jié)點。

2. 低層算法(在自適平面內(nèi))：

自適應(yīng)平面A包含虛通道集合C_i,0，C_{i 1,1}和C_{i 1,2}在A內(nèi)消息在第i維和第i 1維上趨近目的結(jié)點，自適應(yīng)地路由。為避免死鎖，將消息分為兩類，一類是在路由過程中需增加第i維地址的稱為增向消息，另一類需減小第i維地址的稱為減向消息。同時，將A中的虛通道分成兩個單獨的虛擬子網(wǎng)：增向子網(wǎng)(包括虛通道集合C_i,0 和C_{i 1,1})和減向子網(wǎng)(包括虛通道集合C_i,0-和C_{i 1,2})。這樣，增向消息在增向子網(wǎng)上路由，減向消息在減向子網(wǎng)上路由，每一消息都能在相應(yīng)子網(wǎng)中自適應(yīng)地趨近于目的結(jié)點。當消息到達的中間結(jié)點的第i維地址與目的結(jié)點的第i維地址相等時，在A內(nèi)的路由過程結(jié)束，轉(zhuǎn)向下一個高層步驟。

互連網(wǎng)絡(luò)路由器是大規(guī)模并行處理機(MassivelyParallelProeessors，MPP)系統(tǒng)的關(guān)鍵部件，其性能優(yōu)劣直接影響系統(tǒng)性能，因而其如何高效、簡潔地設(shè)計和實現(xiàn)對整個系統(tǒng)起著關(guān)鍵作用。

路由器根據(jù)其所采用的路由算法可分為確定性和自適應(yīng)路由器兩種，確定性路由器唯一確定路徑、不受網(wǎng)絡(luò)狀態(tài)影響，因而實現(xiàn)簡單，已在很多商用MPP中采用，典型的如IntelParagon中采用的2Dmesh路由器、CrayT3D中采用的3Dtorus路由器等；自適應(yīng)路由器對于一對源和目的結(jié)點，視網(wǎng)絡(luò)的工作狀態(tài)，可有多條路徑可選，因而有靈活性好、網(wǎng)絡(luò)的通道利用率高和網(wǎng)絡(luò)容錯能力強等優(yōu)點，正逐步為新一代的MPP系統(tǒng)所采用，但其工程實現(xiàn)難度較大，僅在少數(shù)商用MPP系統(tǒng)中得以實現(xiàn)(如CaryT3E)中實現(xiàn)了完全自適應(yīng)的路由器)，對它的研究一直是國內(nèi)外的熱點。

路由器設(shè)計中的中心問題是路由算法、切換技術(shù)和流控策略。確定性路由算法實現(xiàn)簡單，但網(wǎng)絡(luò)利用率低，阻塞嚴重。

自適應(yīng)路由算法，尤其是完全自適應(yīng)路由算法消除了這種缺陷，減少了網(wǎng)絡(luò)的阻塞延遲，提高了網(wǎng)絡(luò)的利用率，但實現(xiàn)難度較大。蟲孔路由(Wormholeoruting)是當今MPP系統(tǒng)中普遍采用的切換技術(shù)，在源結(jié)點處將要傳送的消息報文劃分成多個微片(Filt)，消息頭微片帶路由信息，當頭微片所需某通道空閑時，頭微片經(jīng)其向前傳送，通道被消息報文所占用，后續(xù)數(shù)據(jù)微片以流水方式尾隨頭微片經(jīng)其向前傳送，直到尾微片經(jīng)其傳送后釋放該通道;當頭微片所需某通道被占用而受阻時，后續(xù)微片也被阻塞、存儲在路徑中各相應(yīng)路由器的緩沖器中。虛通道流控策略是當今普遍采用的流控方式，能有效提高網(wǎng)絡(luò)利用率，同時避免死鎖，綜合采用虛通道流控與一些特殊的仲裁策略能有效提高網(wǎng)絡(luò)性能。

自適應(yīng)構(gòu)件是跟隨建筑信息模型（BIM）概念而產(chǎn)生的理念，作為某些特性參數(shù)可變的部件，貫穿于整個設(shè)計項目的CAD和CAE過程。自適應(yīng)構(gòu)件主要表現(xiàn)為Revit族，主要應(yīng)用于建筑設(shè)計和水電供暖行業(yè)。但隨著建筑信息模型（BIM）的深化及普及，自適應(yīng)構(gòu)件將更廣泛的應(yīng)用于如勘測、土木工程、規(guī)劃等眾多領(lǐng)域。

在BIM項目設(shè)計過程中，使用自適應(yīng)構(gòu)件功能，可以在整個設(shè)計項目的任意過程中，創(chuàng)立擁有變量參數(shù)的自適應(yīng)構(gòu)件。在隨后的設(shè)計過程中，如需要變動，可直接修改某個參數(shù)，在不影響項目進程的情況下，修改成新的方案。

使用自適應(yīng)構(gòu)件功能，可以輕松的自行創(chuàng)建內(nèi)建族文件，這些文件可沿用到另外的項目當中，而不必重新設(shè)立參數(shù)。

路由選擇方法的精確描述，屬于網(wǎng)路軟件的一部分。對它的要求是正確、簡單、可靠、穩(wěn)定、公平和優(yōu)化。

路由選擇算法可分為自適應(yīng)型和非自適應(yīng)型兩大類。自適應(yīng)型的特點在于它的路由選擇能在一定程度上隨網(wǎng)路運行狀態(tài)（如流量和拓撲）而改變，可避開出現(xiàn)異態(tài)的節(jié)點或鏈路。非自適應(yīng)型采用靜態(tài)路由選擇算法。常見的非自適應(yīng)型有擴散式、隨機式、固定式等；而自適應(yīng)型有集中式、孤立式、分布式等。

固定式是一種應(yīng)用范圍比較廣的非自適應(yīng)型路由選擇算法。它是根據(jù)網(wǎng)路拓撲和信息流量的統(tǒng)計模型事先確定各節(jié)點的路由表，每個節(jié)點的路由表指明從該節(jié)點出發(fā)到某個目的節(jié)點所應(yīng)該選擇的輸出鏈路以及下一節(jié)點。路由表由算法確定，而在固定式中是事先預(yù)定的。

最短路徑算法為最常用的算法，它尋求在源節(jié)點和目的節(jié)點之間能沿著長度最短的路徑來傳送分組。這里所指的“長度”賦于特別含義，既可以是實際距離，也可以是平均時延或者鏈路費用。長度參數(shù)是路由表的依據(jù)，如果參數(shù)值來自網(wǎng)路運行的當前狀態(tài)，路由表變?yōu)閯討B(tài)生成，這樣的路由選擇算法就屬于自適應(yīng)型。

Dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時標號的方式。注意該算法要求圖中不存在負權(quán)邊。

首先，引進一個輔助向量D，它的每個分量D[i]表示當前所找到的從始點v到每個終點vi的的長度：如D[3]=2表示從始點v到終點3的路徑相對最小長度為2。這里強調(diào)相對就是說在算法過程中D的值是在不斷逼近最終結(jié)果但在過程中不一定就等于長度。它的初始狀態(tài)為：若從v到vi有弧，則D為弧上的權(quán)值；否則置D為∞。顯然，長度為 D[j]=Min{D | vi∈V} 的路徑就是從v出發(fā)的長度最短的一條。此路徑為(v,vj)。 那么，下一條長度次短的是哪一條呢？假設(shè)該次短路徑的終點是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權(quán)值，或者是D[j]和從vj到vk的弧上的權(quán)值之和。 一般情況下，假設(shè)S為已求得的終點的集合，則可證明：下一條最短路徑（設(shè)其終點為X）或者是弧(v,x)，或者是中間只經(jīng)過S中的頂點而最后到達頂點X的路徑。因此，下一條長度次短的的長度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的權(quán)值，或者是D[k](vk∈S)和弧(vk,vi)上的權(quán)值之和。

算法描述如下：

1）arcs表示弧上的權(quán)值。若不存在，則置arcs為∞。S為已找到從v出發(fā)的的終點的集合，初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點vi可能達到的度的初值為D=arcs[Locate Vex(G,v),i] vi∈V

2）選擇vj，使得D[j]=Min{D | vi∈V-S} 3）修改從v出發(fā)到集合V-S上任一頂點vk可達的最短路徑長度。