張威，張更新，邊東明，茍亮，謝智東

?

基于分層自治域空間信息網(wǎng)絡模型與拓撲控制算法

張威，張更新，邊東明，茍亮，謝智東

（解放軍理工大學通信工程學院，江蘇南京 210007）

針對空間信息網(wǎng)絡結(jié)構(gòu)復雜、拓撲動態(tài)變化以及空間尺度大等特點，提出一種面向空間信息網(wǎng)的分層自治域模型。該模型根據(jù)節(jié)點屬性、鏈路能力、任務特點、分布區(qū)域等不同，將整個網(wǎng)絡劃分為不同的自治域和子自治域，各域內(nèi)可采用相對獨立的控制策略，從而將子網(wǎng)間各動態(tài)因素解耦合。然后，基于該分層自治域模型，提出了一種最小化時延的拓撲控制算法。與現(xiàn)有的集中式和分布式拓撲控制方法不同，該算法采用混合式方法，將控制信息約束在相鄰子自治域范圍內(nèi)，既保證了網(wǎng)絡的連通性，又減少了控制信息的開銷。理論分析表明，若網(wǎng)絡的物理拓撲是連通的，則該算法得到的拓撲控制結(jié)果一定是連通的。仿真結(jié)果驗證了理論分析和所提出算法的有效性。

空間信息網(wǎng)；網(wǎng)絡模型；自治域；拓撲控制

1 引言

縱觀世界范圍內(nèi)，各類衛(wèi)星通信系統(tǒng)的建設仍然表現(xiàn)出各自為陣、獨立建設的局面。各系統(tǒng)針對不同的任務需求和服務對象構(gòu)建，系統(tǒng)缺乏一般性、通用性和相互協(xié)作的能力，形成重復建設、“煙囪式”發(fā)展的不利局面。譬如，僅40oE~180oE的亞太地區(qū)就有120多個GEO軌道位置用于衛(wèi)星移動通信[1,2]，而各類寬帶通信、數(shù)據(jù)中繼、氣象、導航衛(wèi)星更占用了大量軌道資源，并且單個系統(tǒng)針對既定任務設計，系統(tǒng)完成任務后會出現(xiàn)較多空閑狀態(tài)，無法對空間資源進行整體配置。此外，由于頻譜和軌道等資源的限制，各系統(tǒng)的全域覆蓋能力有限，不同的技術體制更導致網(wǎng)絡擴展能力差?？臻g信息網(wǎng)的提出為解決上述問題提供了一種有效途徑，已成為全球范圍的研究熱點[3~6]。

空間信息網(wǎng)絡是以多種空間平臺（如同步衛(wèi)星、中/低軌道衛(wèi)星、平流層氣球和有人/無人駕駛飛機等）為載體，實時獲取、傳輸和處理空間信息的網(wǎng)絡系統(tǒng)。作為國家重要基礎設施，空間信息網(wǎng)絡在服務遠洋航行、應急救援、導航定位、航空運輸、航天測控等重大應用的同時，向下可支持對地觀測的高動態(tài)、寬帶實時傳輸，向上可支持深空探測的超遠程、大時延可靠傳輸，從而將人類科學、文化、生產(chǎn)活動拓展至空間、遠洋乃至深空[7,8]。相比傳統(tǒng)衛(wèi)星網(wǎng)絡，空間信息網(wǎng)絡具有組成結(jié)構(gòu)復雜、拓撲動態(tài)變化、跨越空間尺度大和自組織程度高等明顯特征。因此，如何提高整個空間信息網(wǎng)的管理效率，進行高效、可靠的拓撲控制具有一定的挑戰(zhàn)性。

國內(nèi)外學者已針對空間信息網(wǎng)的模型做出了一些探索。葛曉虎等[9,10]提出了一種基于三維MESH空間信息網(wǎng)絡模型；呂本偉等[11]在將網(wǎng)絡構(gòu)架分為骨干網(wǎng)及非骨干網(wǎng)的基礎上，提出主服務小區(qū)的概念；Pasquale等[12]提出了一種衛(wèi)星與升空平臺結(jié)合的架構(gòu)，并研究了其路由策略。此外，TSAT系統(tǒng)、Iridium NEXT等計劃中的系統(tǒng)已經(jīng)具備了空間信息網(wǎng)的雛形。TSAT計劃通過Teleport實現(xiàn)與美軍其他衛(wèi)星通信系統(tǒng)的互連互通，形成美國全球信息柵格(GIG)的空間部分[13,14]，為構(gòu)建空間信息網(wǎng)架構(gòu)提供了參考。Iridium NEXT融合了通信、導航增強、對地觀測等多種業(yè)務[15]，為研究空間信息網(wǎng)的業(yè)務多樣化提供了參考。同時，國內(nèi)外大量關于多層衛(wèi)星網(wǎng)（MLSN，multilayered satellite network）的文獻也為研究空間信息網(wǎng)的模型提供參考[16~19]。然而，空間信息網(wǎng)是一個立體多層、異構(gòu)動態(tài)的復雜網(wǎng)絡，網(wǎng)絡某一局部范圍內(nèi)組網(wǎng)應用方式、拓撲結(jié)構(gòu)的變化都會影響到全網(wǎng)的狀態(tài)?，F(xiàn)有文獻很好地解決這一特點下的空間信息網(wǎng)絡拓撲控制問題，所涉及的拓撲控制一般是為了在全網(wǎng)范圍內(nèi)維持相對稀疏且可靠網(wǎng)絡連接的同時，達到減少能量消耗[20~22]、減少端到端時延[23,24]、增加網(wǎng)絡吞吐量[25,26]、確保網(wǎng)絡頑健性[27,28]等目的。其方法一般可以分為集中式拓撲控制[29~31]和分布式拓撲控制[31~33]2種。集中式拓撲控制算法依賴于網(wǎng)內(nèi)能夠獲取全網(wǎng)信息的中心節(jié)點單元，并依靠該單元對全網(wǎng)拓撲進行計算和控制，這種拓撲控制方法一般能夠得到全區(qū)最優(yōu)的拓撲控制結(jié)果。但由于空間信息網(wǎng)絡各自治域中節(jié)點節(jié)點數(shù)量多、網(wǎng)絡跨度大、網(wǎng)絡具有一定動態(tài)性，如果采用集中式的拓撲控制方法，將使網(wǎng)絡中控制信息開銷過大，同時也加重了對中心節(jié)點性能的要求，網(wǎng)絡抗毀能力弱。而分布式算法則通過各自節(jié)點獲取周邊節(jié)點信息，并相互協(xié)同完成全網(wǎng)拓撲控制，不需要核心單元。但由于各節(jié)點獲取的均是局部信息，拓撲控制結(jié)果無法達到最優(yōu)，甚至有時網(wǎng)絡拓撲控制結(jié)果無法保證連通性。

針對上述問題，本文提出了一種分層自治域的空間信息網(wǎng)絡模型。該模型將空間信息網(wǎng)劃分為一系列自治域（AS，autonomous system），每個自治域內(nèi)部可采用獨立的控制策略，不同自治域之間通過邊界節(jié)點實現(xiàn)路由和控制信息的交換，各自治域可根據(jù)需要再進行下一級子自治域的劃分，從而構(gòu)建分層自治域的組網(wǎng)結(jié)構(gòu)。通過這種劃分，將整體上是高動態(tài)變化的空間信息網(wǎng)劃分為一個個局部具有弱動態(tài)性變化的子網(wǎng)絡，從而解決子網(wǎng)間動態(tài)耦合性和整網(wǎng)可控性的問題。在該模型的基礎上，提出了一種自治域內(nèi)的最小化時延的拓撲控制算法。不同于傳統(tǒng)的集中式控制算法[29~31]和分布式控制算法[31~33]，該算法采用混合式的方法，將集中式控制算法和分布式控制算法分別應用到子自治域內(nèi)和子自治域間的拓撲控制中。算法的主要步驟如下：1）AS內(nèi)的節(jié)點自主劃分為sub-AS，并選取中心節(jié)點；2）利用從成員節(jié)點收集的信息，每個中心節(jié)點采用集中控制算法使節(jié)點間的時延最小化，并保持連通性；3）各中心節(jié)點利用邊界節(jié)點獲取的相鄰sub-AS信息，采用分布式的拓撲控制算法計算相鄰sub-AS間的最小時延鏈路，并保證連通性。最后對算法的連通性進行了證明，并分析了算法的消息復雜度。仿真結(jié)果驗證了理論分析和所提出算法的有效性。

2 網(wǎng)絡模型

如圖1所示，空間信息網(wǎng)包含衛(wèi)星、升空平臺、傳感器、用戶等多種異構(gòu)節(jié)點，其任務、功能、地位和分布空間具有明顯的差異，同時，衛(wèi)星的軌道運動、升空平臺隨氣流的運動、多種用戶終端的復雜運動、網(wǎng)絡節(jié)點的增減等都會引起網(wǎng)絡拓撲的動態(tài)變化，網(wǎng)絡某一局部范圍內(nèi)組網(wǎng)應用方式、業(yè)務流量和流向、拓撲結(jié)構(gòu)、信號傳播環(huán)境等變化都會影響到全網(wǎng)的狀態(tài)。如果對全網(wǎng)采用統(tǒng)一的網(wǎng)絡管理與控制，將會使網(wǎng)絡的運行效率極其低下，甚至因控制信息過多消耗帶寬而難以正常運轉(zhuǎn)。

因此，結(jié)合未來空間信息網(wǎng)中節(jié)點種類多、立體多層分布、異構(gòu)特性明顯、動態(tài)差異性大等特征，根據(jù)節(jié)點屬性將空間信息網(wǎng)劃分為一系列自治域，每個自治域內(nèi)部采用獨立的控制策略，不同自治域之間通過邊界節(jié)點實現(xiàn)控制信息的交換，各自治域可根據(jù)需要再進行下一級子自治域的劃分，從而構(gòu)建分層自治域的組網(wǎng)結(jié)構(gòu)。通過這種劃分，將整體上是高動態(tài)變化的空間信息網(wǎng)解耦合為一個個局部具有弱動態(tài)性變化，由相似類型節(jié)點組成的準靜態(tài)子網(wǎng)絡，從而將整網(wǎng)控制的復雜問題簡單化。如圖2所示，將空間信息網(wǎng)劃分為4個自治域，包括由各類衛(wèi)星組成的AS-1、由高空平臺站組成的AS-2、由低空飛機組成的AS-3以及地面各類節(jié)點組成的AS-4。AS-1中的節(jié)點動態(tài)性高，且運動具有規(guī)律性，其拓撲控制問題主要體現(xiàn)為衛(wèi)星星座的設計，本文暫不討論AS-1的拓撲控制。AS-2/3/4的特點類似，自治域中的節(jié)點移動速度較慢，并通過自組織組網(wǎng)。本文主要討論AS-2/3/4的拓撲控制。

考慮到自治域內(nèi)的節(jié)點屬性類似，為了便于分析，這里不妨假設經(jīng)過劃分后的自治域內(nèi)節(jié)點是同構(gòu)的。它們具有相同的最大傳輸距離。用圖表示一個自治域內(nèi)的拓撲結(jié)構(gòu)，其中，是節(jié)點（頂點）的集合，而是鏈路（邊）的集合。是節(jié)點和之間的距離。每個節(jié)點根據(jù)其屬性（例如MAC地址）被賦予一個唯一的ID。這里，是一般圖，即如果，則和能夠相互交換信息。此外，假設所有的鏈路是對稱和不受遮擋的，節(jié)點能夠通過一定途徑獲取自己的位置信息（如GPS）。在下述的定義中，為圖，而和分別為子圖。

3 算法描述

空間信息網(wǎng)絡是一個大尺度網(wǎng)絡，盡管對其進行了自治域劃分，但自治域中相當比例的鏈路仍具有較高的時延。若保留這些高時延鏈路不僅會影響整網(wǎng)業(yè)務信息傳輸?shù)臅r效性，而且會降低控制信息的傳輸效率。同時，高時延鏈路往往具有較長的傳播距離，意味著更高的信號發(fā)射功率，而空間信息網(wǎng)中部分節(jié)點的能量資源是受限的，采用短時延鏈路也有助于整網(wǎng)的能量利用效率的提高。因此，在提出的算法中，采用Min-Max的準則，優(yōu)化自治域內(nèi)的時延，同時保持自治域內(nèi)拓撲的連通性。Min-Max是將任意一對節(jié)點之間的端到端最大時延最小化準則。該算法不需要某個單元獲取自治域拓撲的完整信息，相反，算法依靠的是AS內(nèi)自組織生成的sub-AS。在sub-AS中采用集中控制算法，而在sub-AS之間采用分布式控制算法。算法的具體過程分為以下3個階段。

3.1 階段1：sub-AS的生成

階段1的主要目的是在AS中生成最少數(shù)量的sub-AS，每個sub-AS有一個中心節(jié)點和若干成員節(jié)點，成員節(jié)點和中心節(jié)點之間一跳互連。各個中心節(jié)點是整個算法的主要執(zhí)行者。

步驟1 廣播hello信息。算法開始后，AS內(nèi)的各節(jié)點在范圍廣播hello信息使相鄰節(jié)點獲取彼此信息。hello信息的格式為。具體為：1）：節(jié)點的唯一ID；2）：節(jié)點的位置信息；3）：該節(jié)點當前連接的中心節(jié)點的ID，若沒有連接中心節(jié)點，則值為0，若本身是中心節(jié)點，則用自身ID；4）：節(jié)點的連接度（相連節(jié)點的個數(shù)）；5）：與相鄰節(jié)點交換信息的時延。

步驟2 中心節(jié)點的選取。中心節(jié)點的選取在廣播hello信息后等待一段時間進行，該等待時間應保證AS內(nèi)每個節(jié)點從其相鄰節(jié)點至少接收到一輪hello信息。在該步驟中，自治域內(nèi)的每個節(jié)點選擇成為中心節(jié)點或成員節(jié)點。各節(jié)點在接收到hello信息后根據(jù)當前狀態(tài)計算值，用于判斷自身角色。度量應與算法的優(yōu)化目標一致，這里選取作為。這里采用是為了避免出現(xiàn)相同的值。的計算函數(shù)為，同時，為了平衡和，如式(2)所示。其中，是和之間的平衡因子。

(3)

因此，當某節(jié)點在其相鄰節(jié)點中具有最大的值，則選擇其作為中心節(jié)點，每個中心節(jié)點對應一個sub-AS。經(jīng)過該步驟，AS中的第一批中心節(jié)點被選出，則相應的hello信息隨之更新。

步驟4 優(yōu)化和保持?？紤]到節(jié)點的移動性，同時為了保證中心節(jié)點的數(shù)量最小，當中心節(jié)點檢測到其范圍內(nèi)有其他中心節(jié)點（通過周期性的hello信息），判斷自身是否具有最大的值。如果不是，則將不再作為中心節(jié)點，并成為對比過程中具有最大值節(jié)點的成員節(jié)點。其成員節(jié)點變?yōu)闊o父節(jié)點，并轉(zhuǎn)到步驟3。最終，AS中只有2種節(jié)點，即中心節(jié)點和成員節(jié)點。該步驟將監(jiān)測整個AS的狀態(tài)。例如，當有新節(jié)點加入AS中，將其作為無父節(jié)點，并轉(zhuǎn)向步驟3。

3.2 階段2：sub-AS內(nèi)拓撲控制

在sub-AS內(nèi)部，本文采用集中控制算法。中心節(jié)點負責計算sub-AS內(nèi)各成員之間的相互連接關系，從而達到優(yōu)化目標（Min-Max時延準則并保證連通）。算法1給出了sub-AS內(nèi)拓撲控制的具體過程。其中采用表示AS，而（sub-AS）是的分割。

算法1 sub-AS內(nèi)拓撲控制

Output:

Begin:

end if

end for

3.3 階段3：sub-AS間拓撲控制

為了使相鄰sub-AS獲取彼此信息，各節(jié)點繼續(xù)周期性廣播階段1中的hello信息。當節(jié)點收到與其不同sub-AS的節(jié)點的信息（與具有不同的），將的信息添加到其邊界列表中，并將該邊界列表發(fā)送給其父節(jié)點。當中心節(jié)點收集到所有成員節(jié)點發(fā)送的邊界列表后，執(zhí)行算法2中的操作。其中，采用表示AS，而（sub-AS）是的分割。

在算法2中，假設相鄰sub-AS為和，sub-AS的中心節(jié)點采用文獻[34]中的算法（）檢測和之間是否存在條獨立鏈路，即利用雙向圖（bipartite graph）計算最大匹配，算法中的雙向圖頂點分別屬于和。

如果小于最大匹配的數(shù)量，則中心節(jié)點從中選取條滿足Min-Max時延準則的鏈路。當不存在條獨立鏈路時（僅存在條獨立鏈路），則中心節(jié)點從中選取條滿足Min-Max時延準則的鏈路，保持連通性。需要說明的是，此時和之間只有連通，但當算法2結(jié)束后，由于其他相鄰sub-AS之間連通性的保持，整個AS內(nèi)是連通的。這點將在附錄中進行證明。

當階段3完成后，中心節(jié)點將鏈路列表分發(fā)給各成員節(jié)點，成員節(jié)點按照鏈路列表更新連接關系。同時，各節(jié)點以一定的周期廣播hello信息以適應拓撲的動態(tài)性，維護拓撲的優(yōu)化目標。

算法2 sub-AS間拓撲控制

Output:

Begin:

end for

else

end for

end if

end for

then

end if

end for

4 控制消息復雜度分析

這里通過計算拓撲控制過程中3個階段的控制消息交換量對控制消息復雜度進行分析。令表示AS中的總節(jié)點數(shù)量，表示AS中劃分的sub-AS數(shù)目，表示sub-AS中的平均節(jié)點數(shù)量，即。令表示sub-AS中節(jié)點成為邊界節(jié)點的平均概率，。令表示sub-AS周圍相鄰sub-AS的平均個數(shù)，。

表1給出了在各sub-AS中算法各階段為完成拓撲控制所需要消耗的平均消息數(shù)量。表1將各階段劃分為主要步驟，給出了消耗的消息數(shù)量。則從表1中可以得到，在整個AS中，所需要的控制消息數(shù)量為。進一步化簡為，其最壞情況為。

表1 對于一個sub-AS算法各階段的消息復雜度

5 仿真結(jié)果與性能分析

由于所提出的算法是混合了中心式和分布式的混合控制算法，這里將其與典型的中心控制算法[31]以及分布式算法[31]做對比。選擇這2個算法進行對比的原因是，其優(yōu)化準則和本文算法同是Min-Max準則。仿真結(jié)果利用NS2軟件仿真得到。

對于每次AS拓撲控制仿真，考慮如下參數(shù)。

3) 1 000次重復統(tǒng)計。

本文提出的混合式算法，在其階段1 sub-AS生成的過程中，中心節(jié)點和成員節(jié)點之間均是1跳連接。對應于AS區(qū)域中不同節(jié)點數(shù)目，階段1算法生成的各sub-AS中平均節(jié)點數(shù)目分別為6.68、7.67、8.64、9.69和10.15（1 000次統(tǒng)計結(jié)果）。需注意的是，通過AS區(qū)域中取不同的節(jié)點數(shù)目，并保持其他參數(shù)（如區(qū)域大小、節(jié)點的最大信息收發(fā)距離等）不變，實際上調(diào)整了算法中的節(jié)點連接度。

圖3給出了在一次仿真統(tǒng)計過程中，所提出算法的各階段實際拓撲控制結(jié)果。

圖4給出了相同仿真條件下，3種算法拓撲控制結(jié)果中節(jié)點間最大（max）和平均（avg）時延的統(tǒng)計結(jié)果。需指出，仿真過程中，僅考慮了鏈路傳播時延（實際中還可能存在處理、傳輸時延）。仿真條件中，節(jié)點的最大信息收發(fā)距離是350 km，對應的信息傳播時延為1.167 ms。當時，本文算法將節(jié)點數(shù)目為125時的最大時延降至0.864 ms，將節(jié)點數(shù)目為225時的最大時延降至0.577 ms。相比經(jīng)典的分布式算法，最大時延低9.5%~18.1%，相比中心式算法高10.9%~ 18.9%。對于平均時延，當節(jié)點數(shù)為125時，本文算法結(jié)果中節(jié)點間平均時延為0.524 ms，當節(jié)點數(shù)為225時低至0.354 ms。相比算法，平均時延低9.0%~12.1%，相比平均時延高10.8%~ 13.2%。

可以看出，本文算法統(tǒng)計得到的鏈路時延優(yōu)化性能在中心式算法和分布式算法中間。這種結(jié)果是能預期的，因為本文算法是一種混合了中心式和分布式的算法。盡管中心式控制算法具有更好的鏈路時延優(yōu)化性能（約10.8%~20.8%），但中心式控制算法并不適合空間信息網(wǎng)這種大尺度網(wǎng)絡。因為中心控制算法需要一個功能強大的中心實體獲取并計算AS內(nèi)所有節(jié)點的控制信息，同時控制消息需要經(jīng)過多跳、長時延的收發(fā)，網(wǎng)絡的控制效率低下。相反，本文算法中拓撲控制消息被約束在各sub-AS及其相鄰周圍，網(wǎng)絡控制效率高，同時其鏈路時延優(yōu)化效果優(yōu)于純分布式的算法。因此，對于空間信息網(wǎng)的拓撲控制，本文提出的算法具有更好的針對性和適用性。

圖5給出了本文算法的平均節(jié)點度。相比無拓撲控制的情況，顯然本文算法中節(jié)點的連接度不取決于網(wǎng)絡的規(guī)模和節(jié)點的密度。圖6給出了完成本文算法平均每節(jié)點的消息交互數(shù)量。根據(jù)消息復雜度的分析，本文算法的消息復雜度是。對于每個節(jié)點，平均要求消息數(shù)量為。圖6中的仿真統(tǒng)計結(jié)果驗證了分析，當AS中的節(jié)點數(shù)目從125增加到225，平均每節(jié)點的消息交互數(shù)量并未有明顯增加。綜上，本文算法具有較高的效率，可用性高。

6 結(jié)束語

本文提出了空間信息網(wǎng)的一種分層自治域網(wǎng)絡模型，根據(jù)節(jié)點屬性將網(wǎng)絡劃分為不同的自治域和子自治域，將網(wǎng)內(nèi)各動態(tài)因素解耦合，從而簡化了整網(wǎng)控制的復雜問題。在該模型的基礎上，提出一種最小化時延的自治域拓撲控制算法。與現(xiàn)有的集中式和分布式拓撲控制方法不同，該算法采用混合式的方法，其控制信息被約束在相鄰子自治域范圍內(nèi)，控制信息開銷少，更適用于空間信息網(wǎng)這樣的大尺度網(wǎng)絡。此外，本文還對所提出算法的強連通性進行了證明，仿真結(jié)果驗證了理論分析和所提出算法的效率。

附錄 算法1和算法2的k連通性證明

為了對所提出的算法1和算法2的連通性進行證明，證明結(jié)果采用如下定理1和定理2表示。

1) 算法1的連通性證明

最后，對定理1的正確性進行證明。

2) 算法2的連通性

為了證明定理2的正確性，首先證明如下3條引理。

證明 由定理1，sub-AS內(nèi)部的各節(jié)點之間是連通的。這里把sub-AS看做一個節(jié)點，也即是將圖表示為，其中，，。實際上，邊應該至少包含和之間的條獨立路徑。令表示將中的sub-AS看作節(jié)點后圖，其中，。用表示中的sub-AS是因為這里不需要考慮sub-AS內(nèi)的拓撲結(jié)構(gòu)（無論和均是連通的）。由于假設sub-AS均為節(jié)點，那么認為和表示相同的邊。算法2中，每個邊均有一個值。

定理2證明 由定理1可知，算法1結(jié)束后，每個sub- AS均滿足。將這些sub-AS劃分為集合，其中各個集合包含的sub-AS之間在中是多跳連通的，也即是，，有。這里再定義集合，其中，。由引理5可知，對于各，，有。將看作的子圖，，其中，，。由于僅包含多跳連通子圖，由推論1可知，是連通的。又由推論2，可知是連通的。最終可得，定理2得證。

[1] 數(shù)字通信世界. 亞太地區(qū)衛(wèi)星資源指南2014[EB/OL]. http://www. dcw.org.cn/images/cover /1-1.jpg.

Digital Communication World. Satellite resource guide of ASIA-pacific area in 2014[EB/OL].http://www.dcw.org.cn/ images/cover /1-1.jpg.

[2] Union of concerned scientists, UCS satellite database[EB/OL]. http://www.ucsusa.org/nuclear_weapons_and_global_security/solutions/space-weapons/ucs-satellite-database.html.

[3] MUKHERJEE J, RAMAMURTHY B. Communication technologies and architectures for space network and interplanetary internet[J]. IEEE Communication Surveys & Tutorials, 2012, 15(2): 881-897.

[4] BHASIN K B, HAYDEN J K. Architecting communication network of networks for space system of systems[C]//IEEE System of Systems Engineering Conference. c2008: 1-7.

[5] HU H F, LIU Y A. A feasible mesh-based architecture and protocol model of space information network[C]//IEEE Geoscience and Remote Sensing Conference. c2010: 529-531.

[6] REN F, FAN J L. An adaptive distributed certificate management scheme for space information network[J]. IET Information Security, 2013, 7(4): 318-326.

[7] ZHANG G X, ZHANG W, ZHANG H, et al. A novel proposal of architecture and network model for space communication networks[C]// IAF 65th International Astronautical Congress. c2014: 1-7.

[8] 國家自然科學基金委員會. 空間信息網(wǎng)絡基礎理論與關鍵技術重大研究計劃2015 [R]. NSFC 2015年度項目指南. 2015.

National Natural Science Foundation of China. Major research program on the basic theory and key technology in space information network[R]. NSFC Annual Program Guidelines in 2015. 2015.

[9] 葛曉虎, 劉應狀, 董燕, 等. 一種基于 MESH 結(jié)構(gòu)的空天信息網(wǎng)絡模型[J]. 微電子學與計算機, 2008, 25(5): 39-42.

GE X H, LIU Y Z, DONG Y, et al. A space-sky information network model based on MESH architecture[J]. Microelectronics and Computer, 2008, 25(5): 39-42.

[10] 張登銀, 劉升升. 基于 Mesh 的空間信息網(wǎng)體系結(jié)構(gòu)研究[J]. 計算機技術與發(fā)展, 2009, 19(8): 69-73.

ZHANG D Y, LIU S S. Research on mesh-based architecture for space information network[J]. Computer Technology and Development, 2009, 19(8): 69-73.

[11] 呂本偉, 劉元安, 胡鶴飛, 等. AIR: 基于QoS保障的空天信息網(wǎng)絡路由算法[J]. 中國科技論文在線, 2010:1-6.

LV B W, LIU Y A, HU H F, et al. AIR: QoS routing algorithm for aerospace information network[J]. Science Paper Online, 2010: 1-6.

[12] PASQUALE P, et al. Routing and scalability issues for multi-layered satellite-HAPs networks[C]//ICASSC2010. c2010:64-69.

[13] PULLIAM J, ZAMBRZ Y, ARMARKER A, et al. TSAT network architecture[C]//MILCOM 2008 IEEE. c2008: 1-7.

[14] COOK K L B. Current wideband MILSATCOM infrastructure and the future of bandwidth availability[J]. IEEE Aerospace and Electronic System Magazine, 2010, 25(12):23-28.

[15] Discover the Iridium NEXT program[EB/OL]. http://www.iridium. com/About/Iiridum NEXT.aspx.

[16] NISHIYAMA H, TADA Y, KATO N, et al. Toward optimized traffic distribution for efficient network capacity utilization in two-layered satellite networks[J]. IEEE Transactions on Vehicular Technology, 2013, 62(3): 1303-1313.

[17] LI Y J, ZHAO S H, WU J L, et al. Designing of a novel optical two-layered satellite network[C]//IEEE Computer Science and Software Engineering Conference. c2008: 976-979.

[18] YIN Z Z, ZHANG L, ZHOU X W, et al. Qos-aware multicast routing protocol for triple-layered LEO/HEO/GEO satellite IP network[C]// IEEE Global Mobile Congress. c2010: 1-6.

[19] TALEB T, FADLULLAH Z M, TAKAHASHI T, et al. Tailoring ELB for multi-layered satellite network[C]//IEEE Communications Conference. c2009: 1-5.

[20] GUO B, GUAN Q, YU F, et al. Energy-efficient topology control with selective diversity in cooperative wireless ad hoc networks: a game-theoretic approach[J]. IEEE Transactions on Wireless Communications, 2014, 13(11): 6484-6495.

[21] SHANG D, ZHANG B, YAO Z, et al. An energy efficient localized topology control algorithm for wireless multihop networks[J]. IEEE Journal of Communication and Networks, 2014, 16(4): 371-377.

[22] SARDELLITTI S, BARBAROSSA S, SWAMI A. Optimal topology control and power allocation for minimum energy consumption in consensus networks[J]. IEEE Transactions on Signal Processing, 2012, 60(1): 383-399.

[23] ZHANG X, ZHANG Y, YAN F, et al. Interference-based topology control algorithm for delay-constrained mobile ad hoc networks[J]. IEEE Transactions on Mobile Computing, 2015, 14(4): 742-754.

[24] ESLAMLU G, SABAEI M, FEREYDOONI M. Delay-constraint load-aware topology control in wireless sensor networks[C]// Telecommunications and Signal Processing. c2012: 27-31.

[25] LI D, WANG B, JIA X. Topology control for throughput optimization in wireless mesh networks[C]//Mobile Ad-hoc and Sensor Networks. c2008: 161-168.

[26] TAO W, CHEN C, YANG B, et al. Adaptive topology control for throughput optimization in wireless sensor networks[C]//IEEE Communication Technology. c2010: 1299-1302.

[27] LI M, LI Z, VASILAKOS A. A survey on topology control in wireless sensor networks: taxonomy, comparative study[J]. Proceedings of the IEEE, 2013, 101(12): 2538-2557.

[28] LIU L, LIU Y, ZHANG N. A complex network approach to topology control problem in underwater acoustic sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(12): 3046-3055.

[29] RAMANATHAN R, ROSALES-HAIN R. Topology control of multihop wireless networks using transmit power adjustment[C]//IEEE INFOCOM. c2000: 404-413.

[30] YU J, ROH H, LEE W, et al. Topology control in cooperative wireless ad-hoc networks[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(9): 1771-1779.

[31] LI N, HOU J C. Localized fault-tolerant topology control in wireless ad hoc networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(4): 307-320.

[32] WATTENHOFER R, LI L, BAHL P, et al. Distributed topology control for power efficient operation in multihop wireless ad hoc networks[C]//IEEE INFOCOM. c2001: 1388-1397.

[33] CHIWEWE T M, HANCKE G P. A distributed topology control technique for low interference and energy efficiency in wireless sensor networks[J]. IEEE Transactions on Industrial Informatics, 2012, 8(1): 11-19.

[34] AZAD A, HALAPPANAVAR M, RAJAMANICKAM S, et al. Multithreaded algorithms for maximum matching in bipartite graphs[C]// IEEE Parallel and Distributed Processing Symposium. c2012: 860-872.

Network model and topology control algorithm based on hierarchical autonomous system in space information network

ZHANG Wei, ZHANG Geng-xin, BIAN Dong-ming, GOU Liang, XIE Zhi-dong

(College of Communication Engineering, PLA University of Science and Technology, Nanjing 210007, China)

Due to the distinguishing characteristics of space information network (SIN) such as large scale, high component complexity and dynamic, a novel network model based on hierarchical autonomous system (AS) was proposed. This model divided the complex SIN into simpler AS and sub-AS networks according to node properties, link capabilities, task features, distribution areas, etc. In these AS or sub-AS networks, different control strategies could be adopted. In this way, the dynamic network was decoupled into semi-static sub-networks, and the high dynamic coupling problem among sub-networks was solved. Then, an AS network topology control algorithm based on the hierarchical autonomous system model was proposed to minimize the time delay in the SIN. Compared with most existing approaches for SIN where either the purely centralized or the purely distributed control method was adopted, the proposed algorithm was a hybrid control method. In order to reduce the cost of control, the control message exchange was constrained among neighboring sub-AS networks. It is proved that the proposed algorithm achieve logical-connectivity on the condition that the original physical topology is-connectivity. Simulation results validate the theoretical analysis and effectiveness of the algorithm.

space information network, network model, autonomous system, topology control

TN927

A

10.11959/j.issn.1000-436x.2016120

2015-05-15；

2016-05-11

國家自然科學基金資助項目（No.91338201, No.91438109, No.61571464）

The National Natural Science Foundation of China (No.91338201, No.91438109, No.61571464)

張威（1987-），男，河南商丘人，解放軍理工大學博士生，主要研究方向為衛(wèi)星通信、空間信息網(wǎng)絡等。

張更新（1967-），男，浙江平湖人，博士，解放軍理工大學教授、博士生導師，主要研究方向為衛(wèi)星通信、空間信息網(wǎng)絡、深空通信等。

邊東明（1975-），男，山東鄆城人，博士，解放軍理工大學副教授，主要研究方向為衛(wèi)星通信、深空通信等。

茍亮（1981-），男，湖北枝江人，解放軍理工大學博士生，主要研究方向為衛(wèi)星通信、深空通信、網(wǎng)絡編碼等。

謝智東（1984-），男，甘肅通渭人，博士，解放軍理工大學講師，主要研究方向為衛(wèi)星通信、空間信息網(wǎng)絡、深空通信等。