基于分層自治域空間信息網(wǎng)絡(luò)模型與拓?fù)淇刂扑惴?/h1>
2016-07-18 11:50:52張威張更新邊東明茍亮謝智東
通信學(xué)報(bào) 2016年6期 關(guān)鍵詞：信息
張威，張更新，邊東明，茍亮，謝智東
?
基于分層自治域空間信息網(wǎng)絡(luò)模型與拓?fù)淇刂扑惴?/p>
張威，張更新，邊東明，茍亮，謝智東
（解放軍理工大學(xué)通信工程學(xué)院，江蘇南京 210007）
針對空間信息網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜、拓?fù)鋭討B(tài)變化以及空間尺度大等特點(diǎn)，提出一種面向空間信息網(wǎng)的分層自治域模型。該模型根據(jù)節(jié)點(diǎn)屬性、鏈路能力、任務(wù)特點(diǎn)、分布區(qū)域等不同，將整個(gè)網(wǎng)絡(luò)劃分為不同的自治域和子自治域，各域內(nèi)可采用相對獨(dú)立的控制策略，從而將子網(wǎng)間各動態(tài)因素解耦合。然后，基于該分層自治域模型，提出了一種最小化時(shí)延的拓?fù)淇刂扑惴?。與現(xiàn)有的集中式和分布式拓?fù)淇刂品椒ú煌撍惴ú捎没旌鲜椒椒?，將控制信息約束在相鄰子自治域范圍內(nèi)，既保證了網(wǎng)絡(luò)的連通性，又減少了控制信息的開銷。理論分析表明，若網(wǎng)絡(luò)的物理拓?fù)涫沁B通的，則該算法得到的拓?fù)淇刂平Y(jié)果一定是連通的。仿真結(jié)果驗(yàn)證了理論分析和所提出算法的有效性。
空間信息網(wǎng)；網(wǎng)絡(luò)模型；自治域；拓?fù)淇刂?/p>
1 引言
縱觀世界范圍內(nèi)，各類衛(wèi)星通信系統(tǒng)的建設(shè)仍然表現(xiàn)出各自為陣、獨(dú)立建設(shè)的局面。各系統(tǒng)針對不同的任務(wù)需求和服務(wù)對象構(gòu)建，系統(tǒng)缺乏一般性、通用性和相互協(xié)作的能力，形成重復(fù)建設(shè)、“煙囪式”發(fā)展的不利局面。譬如，僅40oE~180oE的亞太地區(qū)就有120多個(gè)GEO軌道位置用于衛(wèi)星移動通信[1,2]，而各類寬帶通信、數(shù)據(jù)中繼、氣象、導(dǎo)航衛(wèi)星更占用了大量軌道資源，并且單個(gè)系統(tǒng)針對既定任務(wù)設(shè)計(jì)，系統(tǒng)完成任務(wù)后會出現(xiàn)較多空閑狀態(tài)，無法對空間資源進(jìn)行整體配置。此外，由于頻譜和軌道等資源的限制，各系統(tǒng)的全域覆蓋能力有限，不同的技術(shù)體制更導(dǎo)致網(wǎng)絡(luò)擴(kuò)展能力差?？臻g信息網(wǎng)的提出為解決上述問題提供了一種有效途徑，已成為全球范圍的研究熱點(diǎn)[3~6]。
空間信息網(wǎng)絡(luò)是以多種空間平臺（如同步衛(wèi)星、中/低軌道衛(wèi)星、平流層氣球和有人/無人駕駛飛機(jī)等）為載體，實(shí)時(shí)獲取、傳輸和處理空間信息的網(wǎng)絡(luò)系統(tǒng)。作為國家重要基礎(chǔ)設(shè)施，空間信息網(wǎng)絡(luò)在服務(wù)遠(yuǎn)洋航行、應(yīng)急救援、導(dǎo)航定位、航空運(yùn)輸、航天測控等重大應(yīng)用的同時(shí)，向下可支持對地觀測的高動態(tài)、寬帶實(shí)時(shí)傳輸，向上可支持深空探測的超遠(yuǎn)程、大時(shí)延可靠傳輸，從而將人類科學(xué)、文化、生產(chǎn)活動拓展至空間、遠(yuǎn)洋乃至深空[7,8]。相比傳統(tǒng)衛(wèi)星網(wǎng)絡(luò)，空間信息網(wǎng)絡(luò)具有組成結(jié)構(gòu)復(fù)雜、拓?fù)鋭討B(tài)變化、跨越空間尺度大和自組織程度高等明顯特征。因此，如何提高整個(gè)空間信息網(wǎng)的管理效率，進(jìn)行高效、可靠的拓?fù)淇刂凭哂幸欢ǖ奶魬?zhàn)性。
國內(nèi)外學(xué)者已針對空間信息網(wǎng)的模型做出了一些探索。葛曉虎等[9,10]提出了一種基于三維MESH空間信息網(wǎng)絡(luò)模型；呂本偉等[11]在將網(wǎng)絡(luò)構(gòu)架分為骨干網(wǎng)及非骨干網(wǎng)的基礎(chǔ)上，提出主服務(wù)小區(qū)的概念；Pasquale等[12]提出了一種衛(wèi)星與升空平臺結(jié)合的架構(gòu)，并研究了其路由策略。此外，TSAT系統(tǒng)、Iridium NEXT等計(jì)劃中的系統(tǒng)已經(jīng)具備了空間信息網(wǎng)的雛形。TSAT計(jì)劃通過Teleport實(shí)現(xiàn)與美軍其他衛(wèi)星通信系統(tǒng)的互連互通，形成美國全球信息柵格(GIG)的空間部分[13,14]，為構(gòu)建空間信息網(wǎng)架構(gòu)提供了參考。Iridium NEXT融合了通信、導(dǎo)航增強(qiáng)、對地觀測等多種業(yè)務(wù)[15]，為研究空間信息網(wǎng)的業(yè)務(wù)多樣化提供了參考。同時(shí)，國內(nèi)外大量關(guān)于多層衛(wèi)星網(wǎng)（MLSN，multilayered satellite network）的文獻(xiàn)也為研究空間信息網(wǎng)的模型提供參考[16~19]。然而，空間信息網(wǎng)是一個(gè)立體多層、異構(gòu)動態(tài)的復(fù)雜網(wǎng)絡(luò)，網(wǎng)絡(luò)某一局部范圍內(nèi)組網(wǎng)應(yīng)用方式、拓?fù)浣Y(jié)構(gòu)的變化都會影響到全網(wǎng)的狀態(tài)?，F(xiàn)有文獻(xiàn)很好地解決這一特點(diǎn)下的空間信息網(wǎng)絡(luò)拓?fù)淇刂茊栴}，所涉及的拓?fù)淇刂埔话闶菫榱嗽谌W(wǎng)范圍內(nèi)維持相對稀疏且可靠網(wǎng)絡(luò)連接的同時(shí)，達(dá)到減少能量消耗[20~22]、減少端到端時(shí)延[23,24]、增加網(wǎng)絡(luò)吞吐量[25,26]、確保網(wǎng)絡(luò)頑健性[27,28]等目的。其方法一般可以分為集中式拓?fù)淇刂芠29~31]和分布式拓?fù)淇刂芠31~33]2種。集中式拓?fù)淇刂扑惴ㄒ蕾囉诰W(wǎng)內(nèi)能夠獲取全網(wǎng)信息的中心節(jié)點(diǎn)單元，并依靠該單元對全網(wǎng)拓?fù)溥M(jìn)行計(jì)算和控制，這種拓?fù)淇刂品椒ㄒ话隳軌虻玫饺珔^(qū)最優(yōu)的拓?fù)淇刂平Y(jié)果。但由于空間信息網(wǎng)絡(luò)各自治域中節(jié)點(diǎn)節(jié)點(diǎn)數(shù)量多、網(wǎng)絡(luò)跨度大、網(wǎng)絡(luò)具有一定動態(tài)性，如果采用集中式的拓?fù)淇刂品椒ǎ瑢⑹咕W(wǎng)絡(luò)中控制信息開銷過大，同時(shí)也加重了對中心節(jié)點(diǎn)性能的要求，網(wǎng)絡(luò)抗毀能力弱。而分布式算法則通過各自節(jié)點(diǎn)獲取周邊節(jié)點(diǎn)信息，并相互協(xié)同完成全網(wǎng)拓?fù)淇刂?，不需要核心單元。但由于各?jié)點(diǎn)獲取的均是局部信息，拓?fù)淇刂平Y(jié)果無法達(dá)到最優(yōu)，甚至有時(shí)網(wǎng)絡(luò)拓?fù)淇刂平Y(jié)果無法保證連通性。
針對上述問題，本文提出了一種分層自治域的空間信息網(wǎng)絡(luò)模型。該模型將空間信息網(wǎng)劃分為一系列自治域（AS，autonomous system），每個(gè)自治域內(nèi)部可采用獨(dú)立的控制策略，不同自治域之間通過邊界節(jié)點(diǎn)實(shí)現(xiàn)路由和控制信息的交換，各自治域可根據(jù)需要再進(jìn)行下一級子自治域的劃分，從而構(gòu)建分層自治域的組網(wǎng)結(jié)構(gòu)。通過這種劃分，將整體上是高動態(tài)變化的空間信息網(wǎng)劃分為一個(gè)個(gè)局部具有弱動態(tài)性變化的子網(wǎng)絡(luò)，從而解決子網(wǎng)間動態(tài)耦合性和整網(wǎng)可控性的問題。在該模型的基礎(chǔ)上，提出了一種自治域內(nèi)的最小化時(shí)延的拓?fù)淇刂扑惴?。不同于傳統(tǒng)的集中式控制算法[29~31]和分布式控制算法[31~33]，該算法采用混合式的方法，將集中式控制算法和分布式控制算法分別應(yīng)用到子自治域內(nèi)和子自治域間的拓?fù)淇刂浦?。算法的主要步驟如下：1）AS內(nèi)的節(jié)點(diǎn)自主劃分為sub-AS，并選取中心節(jié)點(diǎn)；2）利用從成員節(jié)點(diǎn)收集的信息，每個(gè)中心節(jié)點(diǎn)采用集中控制算法使節(jié)點(diǎn)間的時(shí)延最小化，并保持連通性；3）各中心節(jié)點(diǎn)利用邊界節(jié)點(diǎn)獲取的相鄰sub-AS信息，采用分布式的拓?fù)淇刂扑惴ㄓ?jì)算相鄰sub-AS間的最小時(shí)延鏈路，并保證連通性。最后對算法的連通性進(jìn)行了證明，并分析了算法的消息復(fù)雜度。仿真結(jié)果驗(yàn)證了理論分析和所提出算法的有效性。
2 網(wǎng)絡(luò)模型
如圖1所示，空間信息網(wǎng)包含衛(wèi)星、升空平臺、傳感器、用戶等多種異構(gòu)節(jié)點(diǎn)，其任務(wù)、功能、地位和分布空間具有明顯的差異，同時(shí)，衛(wèi)星的軌道運(yùn)動、升空平臺隨氣流的運(yùn)動、多種用戶終端的復(fù)雜運(yùn)動、網(wǎng)絡(luò)節(jié)點(diǎn)的增減等都會引起網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化，網(wǎng)絡(luò)某一局部范圍內(nèi)組網(wǎng)應(yīng)用方式、業(yè)務(wù)流量和流向、拓?fù)浣Y(jié)構(gòu)、信號傳播環(huán)境等變化都會影響到全網(wǎng)的狀態(tài)。如果對全網(wǎng)采用統(tǒng)一的網(wǎng)絡(luò)管理與控制，將會使網(wǎng)絡(luò)的運(yùn)行效率極其低下，甚至因控制信息過多消耗帶寬而難以正常運(yùn)轉(zhuǎn)。
因此，結(jié)合未來空間信息網(wǎng)中節(jié)點(diǎn)種類多、立體多層分布、異構(gòu)特性明顯、動態(tài)差異性大等特征，根據(jù)節(jié)點(diǎn)屬性將空間信息網(wǎng)劃分為一系列自治域，每個(gè)自治域內(nèi)部采用獨(dú)立的控制策略，不同自治域之間通過邊界節(jié)點(diǎn)實(shí)現(xiàn)控制信息的交換，各自治域可根據(jù)需要再進(jìn)行下一級子自治域的劃分，從而構(gòu)建分層自治域的組網(wǎng)結(jié)構(gòu)。通過這種劃分，將整體上是高動態(tài)變化的空間信息網(wǎng)解耦合為一個(gè)個(gè)局部具有弱動態(tài)性變化，由相似類型節(jié)點(diǎn)組成的準(zhǔn)靜態(tài)子網(wǎng)絡(luò)，從而將整網(wǎng)控制的復(fù)雜問題簡單化。如圖2所示，將空間信息網(wǎng)劃分為4個(gè)自治域，包括由各類衛(wèi)星組成的AS-1、由高空平臺站組成的AS-2、由低空飛機(jī)組成的AS-3以及地面各類節(jié)點(diǎn)組成的AS-4。AS-1中的節(jié)點(diǎn)動態(tài)性高，且運(yùn)動具有規(guī)律性，其拓?fù)淇刂茊栴}主要體現(xiàn)為衛(wèi)星星座的設(shè)計(jì)，本文暫不討論AS-1的拓?fù)淇刂?。AS-2/3/4的特點(diǎn)類似，自治域中的節(jié)點(diǎn)移動速度較慢，并通過自組織組網(wǎng)。本文主要討論AS-2/3/4的拓?fù)淇刂啤?/p>
考慮到自治域內(nèi)的節(jié)點(diǎn)屬性類似，為了便于分析，這里不妨假設(shè)經(jīng)過劃分后的自治域內(nèi)節(jié)點(diǎn)是同構(gòu)的。它們具有相同的最大傳輸距離。用圖表示一個(gè)自治域內(nèi)的拓?fù)浣Y(jié)構(gòu)，其中，是節(jié)點(diǎn)（頂點(diǎn)）的集合，而是鏈路（邊）的集合。是節(jié)點(diǎn)和之間的距離。每個(gè)節(jié)點(diǎn)根據(jù)其屬性（例如MAC地址）被賦予一個(gè)唯一的ID。這里，是一般圖，即如果，則和能夠相互交換信息。此外，假設(shè)所有的鏈路是對稱和不受遮擋的，節(jié)點(diǎn)能夠通過一定途徑獲取自己的位置信息（如GPS）。在下述的定義中，為圖，而和分別為子圖。
3 算法描述
空間信息網(wǎng)絡(luò)是一個(gè)大尺度網(wǎng)絡(luò)，盡管對其進(jìn)行了自治域劃分，但自治域中相當(dāng)比例的鏈路仍具有較高的時(shí)延。若保留這些高時(shí)延鏈路不僅會影響整網(wǎng)業(yè)務(wù)信息傳輸?shù)臅r(shí)效性，而且會降低控制信息的傳輸效率。同時(shí)，高時(shí)延鏈路往往具有較長的傳播距離，意味著更高的信號發(fā)射功率，而空間信息網(wǎng)中部分節(jié)點(diǎn)的能量資源是受限的，采用短時(shí)延鏈路也有助于整網(wǎng)的能量利用效率的提高。因此，在提出的算法中，采用Min-Max的準(zhǔn)則，優(yōu)化自治域內(nèi)的時(shí)延，同時(shí)保持自治域內(nèi)拓?fù)涞倪B通性。Min-Max是將任意一對節(jié)點(diǎn)之間的端到端最大時(shí)延最小化準(zhǔn)則。該算法不需要某個(gè)單元獲取自治域拓?fù)涞耐暾畔ⅲ喾?，算法依靠的是AS內(nèi)自組織生成的sub-AS。在sub-AS中采用集中控制算法，而在sub-AS之間采用分布式控制算法。算法的具體過程分為以下3個(gè)階段。
3.1 階段1：sub-AS的生成
階段1的主要目的是在AS中生成最少數(shù)量的sub-AS，每個(gè)sub-AS有一個(gè)中心節(jié)點(diǎn)和若干成員節(jié)點(diǎn)，成員節(jié)點(diǎn)和中心節(jié)點(diǎn)之間一跳互連。各個(gè)中心節(jié)點(diǎn)是整個(gè)算法的主要執(zhí)行者。
步驟1 廣播hello信息。算法開始后，AS內(nèi)的各節(jié)點(diǎn)在范圍廣播hello信息使相鄰節(jié)點(diǎn)獲取彼此信息。hello信息的格式為。具體為：1）：節(jié)點(diǎn)的唯一ID；2）：節(jié)點(diǎn)的位置信息；3）：該節(jié)點(diǎn)當(dāng)前連接的中心節(jié)點(diǎn)的ID，若沒有連接中心節(jié)點(diǎn)，則值為0，若本身是中心節(jié)點(diǎn)，則用自身ID；4）：節(jié)點(diǎn)的連接度（相連節(jié)點(diǎn)的個(gè)數(shù)）；5）：與相鄰節(jié)點(diǎn)交換信息的時(shí)延。
步驟2 中心節(jié)點(diǎn)的選取。中心節(jié)點(diǎn)的選取在廣播hello信息后等待一段時(shí)間進(jìn)行，該等待時(shí)間應(yīng)保證AS內(nèi)每個(gè)節(jié)點(diǎn)從其相鄰節(jié)點(diǎn)至少接收到一輪hello信息。在該步驟中，自治域內(nèi)的每個(gè)節(jié)點(diǎn)選擇成為中心節(jié)點(diǎn)或成員節(jié)點(diǎn)。各節(jié)點(diǎn)在接收到hello信息后根據(jù)當(dāng)前狀態(tài)計(jì)算值，用于判斷自身角色。度量應(yīng)與算法的優(yōu)化目標(biāo)一致，這里選取作為。這里采用是為了避免出現(xiàn)相同的值。的計(jì)算函數(shù)為，同時(shí)，為了平衡和，如式(2)所示。其中，是和之間的平衡因子。
(3)
因此，當(dāng)某節(jié)點(diǎn)在其相鄰節(jié)點(diǎn)中具有最大的值，則選擇其作為中心節(jié)點(diǎn)，每個(gè)中心節(jié)點(diǎn)對應(yīng)一個(gè)sub-AS。經(jīng)過該步驟，AS中的第一批中心節(jié)點(diǎn)被選出，則相應(yīng)的hello信息隨之更新。
步驟4 優(yōu)化和保持。考慮到節(jié)點(diǎn)的移動性，同時(shí)為了保證中心節(jié)點(diǎn)的數(shù)量最小，當(dāng)中心節(jié)點(diǎn)檢測到其范圍內(nèi)有其他中心節(jié)點(diǎn)（通過周期性的hello信息），判斷自身是否具有最大的值。如果不是，則將不再作為中心節(jié)點(diǎn)，并成為對比過程中具有最大值節(jié)點(diǎn)的成員節(jié)點(diǎn)。其成員節(jié)點(diǎn)變?yōu)闊o父節(jié)點(diǎn)，并轉(zhuǎn)到步驟3。最終，AS中只有2種節(jié)點(diǎn)，即中心節(jié)點(diǎn)和成員節(jié)點(diǎn)。該步驟將監(jiān)測整個(gè)AS的狀態(tài)。例如，當(dāng)有新節(jié)點(diǎn)加入AS中，將其作為無父節(jié)點(diǎn)，并轉(zhuǎn)向步驟3。
3.2 階段2：sub-AS內(nèi)拓?fù)淇刂?/p>
在sub-AS內(nèi)部，本文采用集中控制算法。中心節(jié)點(diǎn)負(fù)責(zé)計(jì)算sub-AS內(nèi)各成員之間的相互連接關(guān)系，從而達(dá)到優(yōu)化目標(biāo)（Min-Max時(shí)延準(zhǔn)則并保證連通）。算法1給出了sub-AS內(nèi)拓?fù)淇刂频木唧w過程。其中采用表示AS，而（sub-AS）是的分割。
算法1 sub-AS內(nèi)拓?fù)淇刂?/p>
Output:
Begin:
end if
end for
3.3 階段3：sub-AS間拓?fù)淇刂?/p>
為了使相鄰sub-AS獲取彼此信息，各節(jié)點(diǎn)繼續(xù)周期性廣播階段1中的hello信息。當(dāng)節(jié)點(diǎn)收到與其不同sub-AS的節(jié)點(diǎn)的信息（與具有不同的），將的信息添加到其邊界列表中，并將該邊界列表發(fā)送給其父節(jié)點(diǎn)。當(dāng)中心節(jié)點(diǎn)收集到所有成員節(jié)點(diǎn)發(fā)送的邊界列表后，執(zhí)行算法2中的操作。其中，采用表示AS，而（sub-AS）是的分割。
在算法2中，假設(shè)相鄰sub-AS為和，sub-AS的中心節(jié)點(diǎn)采用文獻(xiàn)[34]中的算法（）檢測和之間是否存在條獨(dú)立鏈路，即利用雙向圖（bipartite graph）計(jì)算最大匹配，算法中的雙向圖頂點(diǎn)分別屬于和。
如果小于最大匹配的數(shù)量，則中心節(jié)點(diǎn)從中選取條滿足Min-Max時(shí)延準(zhǔn)則的鏈路。當(dāng)不存在條獨(dú)立鏈路時(shí)（僅存在條獨(dú)立鏈路），則中心節(jié)點(diǎn)從中選取條滿足Min-Max時(shí)延準(zhǔn)則的鏈路，保持連通性。需要說明的是，此時(shí)和之間只有連通，但當(dāng)算法2結(jié)束后，由于其他相鄰sub-AS之間連通性的保持，整個(gè)AS內(nèi)是連通的。這點(diǎn)將在附錄中進(jìn)行證明。
當(dāng)階段3完成后，中心節(jié)點(diǎn)將鏈路列表分發(fā)給各成員節(jié)點(diǎn)，成員節(jié)點(diǎn)按照鏈路列表更新連接關(guān)系。同時(shí)，各節(jié)點(diǎn)以一定的周期廣播hello信息以適應(yīng)拓?fù)涞膭討B(tài)性，維護(hù)拓?fù)涞膬?yōu)化目標(biāo)。
算法2 sub-AS間拓?fù)淇刂?/p>
Output:
Begin:
end for
else
end for
end if
end for
then
end if
end for
4 控制消息復(fù)雜度分析
這里通過計(jì)算拓?fù)淇刂七^程中3個(gè)階段的控制消息交換量對控制消息復(fù)雜度進(jìn)行分析。令表示AS中的總節(jié)點(diǎn)數(shù)量，表示AS中劃分的sub-AS數(shù)目，表示sub-AS中的平均節(jié)點(diǎn)數(shù)量，即。令表示sub-AS中節(jié)點(diǎn)成為邊界節(jié)點(diǎn)的平均概率，。令表示sub-AS周圍相鄰sub-AS的平均個(gè)數(shù)，。
表1給出了在各sub-AS中算法各階段為完成拓?fù)淇刂扑枰牡钠骄?shù)量。表1將各階段劃分為主要步驟，給出了消耗的消息數(shù)量。則從表1中可以得到，在整個(gè)AS中，所需要的控制消息數(shù)量為。進(jìn)一步化簡為，其最壞情況為。
表1 對于一個(gè)sub-AS算法各階段的消息復(fù)雜度
5 仿真結(jié)果與性能分析
由于所提出的算法是混合了中心式和分布式的混合控制算法，這里將其與典型的中心控制算法[31]以及分布式算法[31]做對比。選擇這2個(gè)算法進(jìn)行對比的原因是，其優(yōu)化準(zhǔn)則和本文算法同是Min-Max準(zhǔn)則。仿真結(jié)果利用NS2軟件仿真得到。
對于每次AS拓?fù)淇刂品抡妫紤]如下參數(shù)。
3) 1 000次重復(fù)統(tǒng)計(jì)。
本文提出的混合式算法，在其階段1 sub-AS生成的過程中，中心節(jié)點(diǎn)和成員節(jié)點(diǎn)之間均是1跳連接。對應(yīng)于AS區(qū)域中不同節(jié)點(diǎn)數(shù)目，階段1算法生成的各sub-AS中平均節(jié)點(diǎn)數(shù)目分別為6.68、7.67、8.64、9.69和10.15（1 000次統(tǒng)計(jì)結(jié)果）。需注意的是，通過AS區(qū)域中取不同的節(jié)點(diǎn)數(shù)目，并保持其他參數(shù)（如區(qū)域大小、節(jié)點(diǎn)的最大信息收發(fā)距離等）不變，實(shí)際上調(diào)整了算法中的節(jié)點(diǎn)連接度。
圖3給出了在一次仿真統(tǒng)計(jì)過程中，所提出算法的各階段實(shí)際拓?fù)淇刂平Y(jié)果。
圖4給出了相同仿真條件下，3種算法拓?fù)淇刂平Y(jié)果中節(jié)點(diǎn)間最大（max）和平均（avg）時(shí)延的統(tǒng)計(jì)結(jié)果。需指出，仿真過程中，僅考慮了鏈路傳播時(shí)延（實(shí)際中還可能存在處理、傳輸時(shí)延）。仿真條件中，節(jié)點(diǎn)的最大信息收發(fā)距離是350 km，對應(yīng)的信息傳播時(shí)延為1.167 ms。當(dāng)時(shí)，本文算法將節(jié)點(diǎn)數(shù)目為125時(shí)的最大時(shí)延降至0.864 ms，將節(jié)點(diǎn)數(shù)目為225時(shí)的最大時(shí)延降至0.577 ms。相比經(jīng)典的分布式算法，最大時(shí)延低9.5%~18.1%，相比中心式算法高10.9%~ 18.9%。對于平均時(shí)延，當(dāng)節(jié)點(diǎn)數(shù)為125時(shí)，本文算法結(jié)果中節(jié)點(diǎn)間平均時(shí)延為0.524 ms，當(dāng)節(jié)點(diǎn)數(shù)為225時(shí)低至0.354 ms。相比算法，平均時(shí)延低9.0%~12.1%，相比平均時(shí)延高10.8%~ 13.2%。
可以看出，本文算法統(tǒng)計(jì)得到的鏈路時(shí)延優(yōu)化性能在中心式算法和分布式算法中間。這種結(jié)果是能預(yù)期的，因?yàn)楸疚乃惴ㄊ且环N混合了中心式和分布式的算法。盡管中心式控制算法具有更好的鏈路時(shí)延優(yōu)化性能（約10.8%~20.8%），但中心式控制算法并不適合空間信息網(wǎng)這種大尺度網(wǎng)絡(luò)。因?yàn)橹行目刂扑惴ㄐ枰粋€(gè)功能強(qiáng)大的中心實(shí)體獲取并計(jì)算AS內(nèi)所有節(jié)點(diǎn)的控制信息，同時(shí)控制消息需要經(jīng)過多跳、長時(shí)延的收發(fā)，網(wǎng)絡(luò)的控制效率低下。相反，本文算法中拓?fù)淇刂葡⒈患s束在各sub-AS及其相鄰周圍，網(wǎng)絡(luò)控制效率高，同時(shí)其鏈路時(shí)延優(yōu)化效果優(yōu)于純分布式的算法。因此，對于空間信息網(wǎng)的拓?fù)淇刂疲疚奶岢龅乃惴ň哂懈玫尼槍π院瓦m用性。
圖5給出了本文算法的平均節(jié)點(diǎn)度。相比無拓?fù)淇刂频那闆r，顯然本文算法中節(jié)點(diǎn)的連接度不取決于網(wǎng)絡(luò)的規(guī)模和節(jié)點(diǎn)的密度。圖6給出了完成本文算法平均每節(jié)點(diǎn)的消息交互數(shù)量。根據(jù)消息復(fù)雜度的分析，本文算法的消息復(fù)雜度是。對于每個(gè)節(jié)點(diǎn)，平均要求消息數(shù)量為。圖6中的仿真統(tǒng)計(jì)結(jié)果驗(yàn)證了分析，當(dāng)AS中的節(jié)點(diǎn)數(shù)目從125增加到225，平均每節(jié)點(diǎn)的消息交互數(shù)量并未有明顯增加。綜上，本文算法具有較高的效率，可用性高。
6 結(jié)束語
本文提出了空間信息網(wǎng)的一種分層自治域網(wǎng)絡(luò)模型，根據(jù)節(jié)點(diǎn)屬性將網(wǎng)絡(luò)劃分為不同的自治域和子自治域，將網(wǎng)內(nèi)各動態(tài)因素解耦合，從而簡化了整網(wǎng)控制的復(fù)雜問題。在該模型的基礎(chǔ)上，提出一種最小化時(shí)延的自治域拓?fù)淇刂扑惴?。與現(xiàn)有的集中式和分布式拓?fù)淇刂品椒ú煌撍惴ú捎没旌鲜降姆椒?，其控制信息被約束在相鄰子自治域范圍內(nèi)，控制信息開銷少，更適用于空間信息網(wǎng)這樣的大尺度網(wǎng)絡(luò)。此外，本文還對所提出算法的強(qiáng)連通性進(jìn)行了證明，仿真結(jié)果驗(yàn)證了理論分析和所提出算法的效率。
附錄 算法1和算法2的k連通性證明
為了對所提出的算法1和算法2的連通性進(jìn)行證明，證明結(jié)果采用如下定理1和定理2表示。
1) 算法1的連通性證明
最后，對定理1的正確性進(jìn)行證明。
2) 算法2的連通性
為了證明定理2的正確性，首先證明如下3條引理。
證明 由定理1，sub-AS內(nèi)部的各節(jié)點(diǎn)之間是連通的。這里把sub-AS看做一個(gè)節(jié)點(diǎn)，也即是將圖表示為，其中，，。實(shí)際上，邊應(yīng)該至少包含和之間的條獨(dú)立路徑。令表示將中的sub-AS看作節(jié)點(diǎn)后圖，其中，。用表示中的sub-AS是因?yàn)檫@里不需要考慮sub-AS內(nèi)的拓?fù)浣Y(jié)構(gòu)（無論和均是連通的）。由于假設(shè)sub-AS均為節(jié)點(diǎn)，那么認(rèn)為和表示相同的邊。算法2中，每個(gè)邊均有一個(gè)值。
定理2證明 由定理1可知，算法1結(jié)束后，每個(gè)sub- AS均滿足。將這些sub-AS劃分為集合，其中各個(gè)集合包含的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] 國家自然科學(xué)基金委員會. 空間信息網(wǎng)絡(luò)基礎(chǔ)理論與關(guān)鍵技術(shù)重大研究計(jì)劃2015 [R]. NSFC 2015年度項(xiàng)目指南. 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] 葛曉虎, 劉應(yīng)狀, 董燕, 等. 一種基于 MESH 結(jié)構(gòu)的空天信息網(wǎng)絡(luò)模型[J]. 微電子學(xué)與計(jì)算機(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]. 計(jì)算機(jī)技術(shù)與發(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)絡(luò)路由算法[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
國家自然科學(xué)基金資助項(xiàng)目（No.91338201, No.91438109, No.61571464）
The National Natural Science Foundation of China (No.91338201, No.91438109, No.61571464)
張威（1987-），男，河南商丘人，解放軍理工大學(xué)博士生，主要研究方向?yàn)樾l(wèi)星通信、空間信息網(wǎng)絡(luò)等。
張更新（1967-），男，浙江平湖人，博士，解放軍理工大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾l(wèi)星通信、空間信息網(wǎng)絡(luò)、深空通信等。
邊東明（1975-），男，山東鄆城人，博士，解放軍理工大學(xué)副教授，主要研究方向?yàn)樾l(wèi)星通信、深空通信等。
茍亮（1981-），男，湖北枝江人，解放軍理工大學(xué)博士生，主要研究方向?yàn)樾l(wèi)星通信、深空通信、網(wǎng)絡(luò)編碼等。
謝智東（1984-），男，甘肅通渭人，博士，解放軍理工大學(xué)講師，主要研究方向?yàn)樾l(wèi)星通信、空間信息網(wǎng)絡(luò)、深空通信等。
猜你喜歡
訂閱信息中華手工(2017年2期)2017-06-06 23:00:31 展會信息中外會展(2014年4期)2014-11-27 07:46:46 信息超市大眾創(chuàng)業(yè)(2009年10期)2009-10-08 04:52:00 展會信息數(shù)字社區(qū)&智能家居(2009年7期)2009-09-29 08:16:48 展會信息數(shù)字社區(qū)&智能家居(2009年11期)2009-06-25 04:30:34 展會信息數(shù)字社區(qū)&智能家居(2009年3期)2009-04-21 03:09:04 展會信息數(shù)字社區(qū)&智能家居(2009年2期)2009-03-27 04:33:44 展會信息數(shù)字社區(qū)&智能家居(2009年12期)2009-02-03 07:50:48 信息建筑創(chuàng)作(2001年3期)2001-08-22 18:48:14 健康信息祝您健康(1987年3期)1987-12-30 09:52:32
張威，張更新，邊東明，茍亮，謝智東
?
基于分層自治域空間信息網(wǎng)絡(luò)模型與拓?fù)淇刂扑惴?/p>
張威，張更新，邊東明，茍亮，謝智東
（解放軍理工大學(xué)通信工程學(xué)院，江蘇南京 210007）
針對空間信息網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜、拓?fù)鋭討B(tài)變化以及空間尺度大等特點(diǎn)，提出一種面向空間信息網(wǎng)的分層自治域模型。該模型根據(jù)節(jié)點(diǎn)屬性、鏈路能力、任務(wù)特點(diǎn)、分布區(qū)域等不同，將整個(gè)網(wǎng)絡(luò)劃分為不同的自治域和子自治域，各域內(nèi)可采用相對獨(dú)立的控制策略，從而將子網(wǎng)間各動態(tài)因素解耦合。然后，基于該分層自治域模型，提出了一種最小化時(shí)延的拓?fù)淇刂扑惴?。與現(xiàn)有的集中式和分布式拓?fù)淇刂品椒ú煌撍惴ú捎没旌鲜椒椒?，將控制信息約束在相鄰子自治域范圍內(nèi)，既保證了網(wǎng)絡(luò)的連通性，又減少了控制信息的開銷。理論分析表明，若網(wǎng)絡(luò)的物理拓?fù)涫沁B通的，則該算法得到的拓?fù)淇刂平Y(jié)果一定是連通的。仿真結(jié)果驗(yàn)證了理論分析和所提出算法的有效性。
空間信息網(wǎng)；網(wǎng)絡(luò)模型；自治域；拓?fù)淇刂?/p>
1 引言
縱觀世界范圍內(nèi)，各類衛(wèi)星通信系統(tǒng)的建設(shè)仍然表現(xiàn)出各自為陣、獨(dú)立建設(shè)的局面。各系統(tǒng)針對不同的任務(wù)需求和服務(wù)對象構(gòu)建，系統(tǒng)缺乏一般性、通用性和相互協(xié)作的能力，形成重復(fù)建設(shè)、“煙囪式”發(fā)展的不利局面。譬如，僅40oE~180oE的亞太地區(qū)就有120多個(gè)GEO軌道位置用于衛(wèi)星移動通信[1,2]，而各類寬帶通信、數(shù)據(jù)中繼、氣象、導(dǎo)航衛(wèi)星更占用了大量軌道資源，并且單個(gè)系統(tǒng)針對既定任務(wù)設(shè)計(jì)，系統(tǒng)完成任務(wù)后會出現(xiàn)較多空閑狀態(tài)，無法對空間資源進(jìn)行整體配置。此外，由于頻譜和軌道等資源的限制，各系統(tǒng)的全域覆蓋能力有限，不同的技術(shù)體制更導(dǎo)致網(wǎng)絡(luò)擴(kuò)展能力差?？臻g信息網(wǎng)的提出為解決上述問題提供了一種有效途徑，已成為全球范圍的研究熱點(diǎn)[3~6]。
空間信息網(wǎng)絡(luò)是以多種空間平臺（如同步衛(wèi)星、中/低軌道衛(wèi)星、平流層氣球和有人/無人駕駛飛機(jī)等）為載體，實(shí)時(shí)獲取、傳輸和處理空間信息的網(wǎng)絡(luò)系統(tǒng)。作為國家重要基礎(chǔ)設(shè)施，空間信息網(wǎng)絡(luò)在服務(wù)遠(yuǎn)洋航行、應(yīng)急救援、導(dǎo)航定位、航空運(yùn)輸、航天測控等重大應(yīng)用的同時(shí)，向下可支持對地觀測的高動態(tài)、寬帶實(shí)時(shí)傳輸，向上可支持深空探測的超遠(yuǎn)程、大時(shí)延可靠傳輸，從而將人類科學(xué)、文化、生產(chǎn)活動拓展至空間、遠(yuǎn)洋乃至深空[7,8]。相比傳統(tǒng)衛(wèi)星網(wǎng)絡(luò)，空間信息網(wǎng)絡(luò)具有組成結(jié)構(gòu)復(fù)雜、拓?fù)鋭討B(tài)變化、跨越空間尺度大和自組織程度高等明顯特征。因此，如何提高整個(gè)空間信息網(wǎng)的管理效率，進(jìn)行高效、可靠的拓?fù)淇刂凭哂幸欢ǖ奶魬?zhàn)性。
國內(nèi)外學(xué)者已針對空間信息網(wǎng)的模型做出了一些探索。葛曉虎等[9,10]提出了一種基于三維MESH空間信息網(wǎng)絡(luò)模型；呂本偉等[11]在將網(wǎng)絡(luò)構(gòu)架分為骨干網(wǎng)及非骨干網(wǎng)的基礎(chǔ)上，提出主服務(wù)小區(qū)的概念；Pasquale等[12]提出了一種衛(wèi)星與升空平臺結(jié)合的架構(gòu)，并研究了其路由策略。此外，TSAT系統(tǒng)、Iridium NEXT等計(jì)劃中的系統(tǒng)已經(jīng)具備了空間信息網(wǎng)的雛形。TSAT計(jì)劃通過Teleport實(shí)現(xiàn)與美軍其他衛(wèi)星通信系統(tǒng)的互連互通，形成美國全球信息柵格(GIG)的空間部分[13,14]，為構(gòu)建空間信息網(wǎng)架構(gòu)提供了參考。Iridium NEXT融合了通信、導(dǎo)航增強(qiáng)、對地觀測等多種業(yè)務(wù)[15]，為研究空間信息網(wǎng)的業(yè)務(wù)多樣化提供了參考。同時(shí)，國內(nèi)外大量關(guān)于多層衛(wèi)星網(wǎng)（MLSN，multilayered satellite network）的文獻(xiàn)也為研究空間信息網(wǎng)的模型提供參考[16~19]。然而，空間信息網(wǎng)是一個(gè)立體多層、異構(gòu)動態(tài)的復(fù)雜網(wǎng)絡(luò)，網(wǎng)絡(luò)某一局部范圍內(nèi)組網(wǎng)應(yīng)用方式、拓?fù)浣Y(jié)構(gòu)的變化都會影響到全網(wǎng)的狀態(tài)?，F(xiàn)有文獻(xiàn)很好地解決這一特點(diǎn)下的空間信息網(wǎng)絡(luò)拓?fù)淇刂茊栴}，所涉及的拓?fù)淇刂埔话闶菫榱嗽谌W(wǎng)范圍內(nèi)維持相對稀疏且可靠網(wǎng)絡(luò)連接的同時(shí)，達(dá)到減少能量消耗[20~22]、減少端到端時(shí)延[23,24]、增加網(wǎng)絡(luò)吞吐量[25,26]、確保網(wǎng)絡(luò)頑健性[27,28]等目的。其方法一般可以分為集中式拓?fù)淇刂芠29~31]和分布式拓?fù)淇刂芠31~33]2種。集中式拓?fù)淇刂扑惴ㄒ蕾囉诰W(wǎng)內(nèi)能夠獲取全網(wǎng)信息的中心節(jié)點(diǎn)單元，并依靠該單元對全網(wǎng)拓?fù)溥M(jìn)行計(jì)算和控制，這種拓?fù)淇刂品椒ㄒ话隳軌虻玫饺珔^(qū)最優(yōu)的拓?fù)淇刂平Y(jié)果。但由于空間信息網(wǎng)絡(luò)各自治域中節(jié)點(diǎn)節(jié)點(diǎn)數(shù)量多、網(wǎng)絡(luò)跨度大、網(wǎng)絡(luò)具有一定動態(tài)性，如果采用集中式的拓?fù)淇刂品椒ǎ瑢⑹咕W(wǎng)絡(luò)中控制信息開銷過大，同時(shí)也加重了對中心節(jié)點(diǎn)性能的要求，網(wǎng)絡(luò)抗毀能力弱。而分布式算法則通過各自節(jié)點(diǎn)獲取周邊節(jié)點(diǎn)信息，并相互協(xié)同完成全網(wǎng)拓?fù)淇刂?，不需要核心單元。但由于各?jié)點(diǎn)獲取的均是局部信息，拓?fù)淇刂平Y(jié)果無法達(dá)到最優(yōu)，甚至有時(shí)網(wǎng)絡(luò)拓?fù)淇刂平Y(jié)果無法保證連通性。
針對上述問題，本文提出了一種分層自治域的空間信息網(wǎng)絡(luò)模型。該模型將空間信息網(wǎng)劃分為一系列自治域（AS，autonomous system），每個(gè)自治域內(nèi)部可采用獨(dú)立的控制策略，不同自治域之間通過邊界節(jié)點(diǎn)實(shí)現(xiàn)路由和控制信息的交換，各自治域可根據(jù)需要再進(jìn)行下一級子自治域的劃分，從而構(gòu)建分層自治域的組網(wǎng)結(jié)構(gòu)。通過這種劃分，將整體上是高動態(tài)變化的空間信息網(wǎng)劃分為一個(gè)個(gè)局部具有弱動態(tài)性變化的子網(wǎng)絡(luò)，從而解決子網(wǎng)間動態(tài)耦合性和整網(wǎng)可控性的問題。在該模型的基礎(chǔ)上，提出了一種自治域內(nèi)的最小化時(shí)延的拓?fù)淇刂扑惴?。不同于傳統(tǒng)的集中式控制算法[29~31]和分布式控制算法[31~33]，該算法采用混合式的方法，將集中式控制算法和分布式控制算法分別應(yīng)用到子自治域內(nèi)和子自治域間的拓?fù)淇刂浦?。算法的主要步驟如下：1）AS內(nèi)的節(jié)點(diǎn)自主劃分為sub-AS，并選取中心節(jié)點(diǎn)；2）利用從成員節(jié)點(diǎn)收集的信息，每個(gè)中心節(jié)點(diǎn)采用集中控制算法使節(jié)點(diǎn)間的時(shí)延最小化，并保持連通性；3）各中心節(jié)點(diǎn)利用邊界節(jié)點(diǎn)獲取的相鄰sub-AS信息，采用分布式的拓?fù)淇刂扑惴ㄓ?jì)算相鄰sub-AS間的最小時(shí)延鏈路，并保證連通性。最后對算法的連通性進(jìn)行了證明，并分析了算法的消息復(fù)雜度。仿真結(jié)果驗(yàn)證了理論分析和所提出算法的有效性。
2 網(wǎng)絡(luò)模型
如圖1所示，空間信息網(wǎng)包含衛(wèi)星、升空平臺、傳感器、用戶等多種異構(gòu)節(jié)點(diǎn)，其任務(wù)、功能、地位和分布空間具有明顯的差異，同時(shí)，衛(wèi)星的軌道運(yùn)動、升空平臺隨氣流的運(yùn)動、多種用戶終端的復(fù)雜運(yùn)動、網(wǎng)絡(luò)節(jié)點(diǎn)的增減等都會引起網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化，網(wǎng)絡(luò)某一局部范圍內(nèi)組網(wǎng)應(yīng)用方式、業(yè)務(wù)流量和流向、拓?fù)浣Y(jié)構(gòu)、信號傳播環(huán)境等變化都會影響到全網(wǎng)的狀態(tài)。如果對全網(wǎng)采用統(tǒng)一的網(wǎng)絡(luò)管理與控制，將會使網(wǎng)絡(luò)的運(yùn)行效率極其低下，甚至因控制信息過多消耗帶寬而難以正常運(yùn)轉(zhuǎn)。
因此，結(jié)合未來空間信息網(wǎng)中節(jié)點(diǎn)種類多、立體多層分布、異構(gòu)特性明顯、動態(tài)差異性大等特征，根據(jù)節(jié)點(diǎn)屬性將空間信息網(wǎng)劃分為一系列自治域，每個(gè)自治域內(nèi)部采用獨(dú)立的控制策略，不同自治域之間通過邊界節(jié)點(diǎn)實(shí)現(xiàn)控制信息的交換，各自治域可根據(jù)需要再進(jìn)行下一級子自治域的劃分，從而構(gòu)建分層自治域的組網(wǎng)結(jié)構(gòu)。通過這種劃分，將整體上是高動態(tài)變化的空間信息網(wǎng)解耦合為一個(gè)個(gè)局部具有弱動態(tài)性變化，由相似類型節(jié)點(diǎn)組成的準(zhǔn)靜態(tài)子網(wǎng)絡(luò)，從而將整網(wǎng)控制的復(fù)雜問題簡單化。如圖2所示，將空間信息網(wǎng)劃分為4個(gè)自治域，包括由各類衛(wèi)星組成的AS-1、由高空平臺站組成的AS-2、由低空飛機(jī)組成的AS-3以及地面各類節(jié)點(diǎn)組成的AS-4。AS-1中的節(jié)點(diǎn)動態(tài)性高，且運(yùn)動具有規(guī)律性，其拓?fù)淇刂茊栴}主要體現(xiàn)為衛(wèi)星星座的設(shè)計(jì)，本文暫不討論AS-1的拓?fù)淇刂?。AS-2/3/4的特點(diǎn)類似，自治域中的節(jié)點(diǎn)移動速度較慢，并通過自組織組網(wǎng)。本文主要討論AS-2/3/4的拓?fù)淇刂啤?/p>
考慮到自治域內(nèi)的節(jié)點(diǎn)屬性類似，為了便于分析，這里不妨假設(shè)經(jīng)過劃分后的自治域內(nèi)節(jié)點(diǎn)是同構(gòu)的。它們具有相同的最大傳輸距離。用圖表示一個(gè)自治域內(nèi)的拓?fù)浣Y(jié)構(gòu)，其中，是節(jié)點(diǎn)（頂點(diǎn)）的集合，而是鏈路（邊）的集合。是節(jié)點(diǎn)和之間的距離。每個(gè)節(jié)點(diǎn)根據(jù)其屬性（例如MAC地址）被賦予一個(gè)唯一的ID。這里，是一般圖，即如果，則和能夠相互交換信息。此外，假設(shè)所有的鏈路是對稱和不受遮擋的，節(jié)點(diǎn)能夠通過一定途徑獲取自己的位置信息（如GPS）。在下述的定義中，為圖，而和分別為子圖。
3 算法描述
空間信息網(wǎng)絡(luò)是一個(gè)大尺度網(wǎng)絡(luò)，盡管對其進(jìn)行了自治域劃分，但自治域中相當(dāng)比例的鏈路仍具有較高的時(shí)延。若保留這些高時(shí)延鏈路不僅會影響整網(wǎng)業(yè)務(wù)信息傳輸?shù)臅r(shí)效性，而且會降低控制信息的傳輸效率。同時(shí)，高時(shí)延鏈路往往具有較長的傳播距離，意味著更高的信號發(fā)射功率，而空間信息網(wǎng)中部分節(jié)點(diǎn)的能量資源是受限的，采用短時(shí)延鏈路也有助于整網(wǎng)的能量利用效率的提高。因此，在提出的算法中，采用Min-Max的準(zhǔn)則，優(yōu)化自治域內(nèi)的時(shí)延，同時(shí)保持自治域內(nèi)拓?fù)涞倪B通性。Min-Max是將任意一對節(jié)點(diǎn)之間的端到端最大時(shí)延最小化準(zhǔn)則。該算法不需要某個(gè)單元獲取自治域拓?fù)涞耐暾畔ⅲ喾?，算法依靠的是AS內(nèi)自組織生成的sub-AS。在sub-AS中采用集中控制算法，而在sub-AS之間采用分布式控制算法。算法的具體過程分為以下3個(gè)階段。
3.1 階段1：sub-AS的生成
階段1的主要目的是在AS中生成最少數(shù)量的sub-AS，每個(gè)sub-AS有一個(gè)中心節(jié)點(diǎn)和若干成員節(jié)點(diǎn)，成員節(jié)點(diǎn)和中心節(jié)點(diǎn)之間一跳互連。各個(gè)中心節(jié)點(diǎn)是整個(gè)算法的主要執(zhí)行者。
步驟1 廣播hello信息。算法開始后，AS內(nèi)的各節(jié)點(diǎn)在范圍廣播hello信息使相鄰節(jié)點(diǎn)獲取彼此信息。hello信息的格式為。具體為：1）：節(jié)點(diǎn)的唯一ID；2）：節(jié)點(diǎn)的位置信息；3）：該節(jié)點(diǎn)當(dāng)前連接的中心節(jié)點(diǎn)的ID，若沒有連接中心節(jié)點(diǎn)，則值為0，若本身是中心節(jié)點(diǎn)，則用自身ID；4）：節(jié)點(diǎn)的連接度（相連節(jié)點(diǎn)的個(gè)數(shù)）；5）：與相鄰節(jié)點(diǎn)交換信息的時(shí)延。
步驟2 中心節(jié)點(diǎn)的選取。中心節(jié)點(diǎn)的選取在廣播hello信息后等待一段時(shí)間進(jìn)行，該等待時(shí)間應(yīng)保證AS內(nèi)每個(gè)節(jié)點(diǎn)從其相鄰節(jié)點(diǎn)至少接收到一輪hello信息。在該步驟中，自治域內(nèi)的每個(gè)節(jié)點(diǎn)選擇成為中心節(jié)點(diǎn)或成員節(jié)點(diǎn)。各節(jié)點(diǎn)在接收到hello信息后根據(jù)當(dāng)前狀態(tài)計(jì)算值，用于判斷自身角色。度量應(yīng)與算法的優(yōu)化目標(biāo)一致，這里選取作為。這里采用是為了避免出現(xiàn)相同的值。的計(jì)算函數(shù)為，同時(shí)，為了平衡和，如式(2)所示。其中，是和之間的平衡因子。
(3)
因此，當(dāng)某節(jié)點(diǎn)在其相鄰節(jié)點(diǎn)中具有最大的值，則選擇其作為中心節(jié)點(diǎn)，每個(gè)中心節(jié)點(diǎn)對應(yīng)一個(gè)sub-AS。經(jīng)過該步驟，AS中的第一批中心節(jié)點(diǎn)被選出，則相應(yīng)的hello信息隨之更新。
步驟4 優(yōu)化和保持。考慮到節(jié)點(diǎn)的移動性，同時(shí)為了保證中心節(jié)點(diǎn)的數(shù)量最小，當(dāng)中心節(jié)點(diǎn)檢測到其范圍內(nèi)有其他中心節(jié)點(diǎn)（通過周期性的hello信息），判斷自身是否具有最大的值。如果不是，則將不再作為中心節(jié)點(diǎn)，并成為對比過程中具有最大值節(jié)點(diǎn)的成員節(jié)點(diǎn)。其成員節(jié)點(diǎn)變?yōu)闊o父節(jié)點(diǎn)，并轉(zhuǎn)到步驟3。最終，AS中只有2種節(jié)點(diǎn)，即中心節(jié)點(diǎn)和成員節(jié)點(diǎn)。該步驟將監(jiān)測整個(gè)AS的狀態(tài)。例如，當(dāng)有新節(jié)點(diǎn)加入AS中，將其作為無父節(jié)點(diǎn)，并轉(zhuǎn)向步驟3。
3.2 階段2：sub-AS內(nèi)拓?fù)淇刂?/p>
在sub-AS內(nèi)部，本文采用集中控制算法。中心節(jié)點(diǎn)負(fù)責(zé)計(jì)算sub-AS內(nèi)各成員之間的相互連接關(guān)系，從而達(dá)到優(yōu)化目標(biāo)（Min-Max時(shí)延準(zhǔn)則并保證連通）。算法1給出了sub-AS內(nèi)拓?fù)淇刂频木唧w過程。其中采用表示AS，而（sub-AS）是的分割。
算法1 sub-AS內(nèi)拓?fù)淇刂?/p>
Output:
Begin:
end if
end for
3.3 階段3：sub-AS間拓?fù)淇刂?/p>
為了使相鄰sub-AS獲取彼此信息，各節(jié)點(diǎn)繼續(xù)周期性廣播階段1中的hello信息。當(dāng)節(jié)點(diǎn)收到與其不同sub-AS的節(jié)點(diǎn)的信息（與具有不同的），將的信息添加到其邊界列表中，并將該邊界列表發(fā)送給其父節(jié)點(diǎn)。當(dāng)中心節(jié)點(diǎn)收集到所有成員節(jié)點(diǎn)發(fā)送的邊界列表后，執(zhí)行算法2中的操作。其中，采用表示AS，而（sub-AS）是的分割。
在算法2中，假設(shè)相鄰sub-AS為和，sub-AS的中心節(jié)點(diǎn)采用文獻(xiàn)[34]中的算法（）檢測和之間是否存在條獨(dú)立鏈路，即利用雙向圖（bipartite graph）計(jì)算最大匹配，算法中的雙向圖頂點(diǎn)分別屬于和。
如果小于最大匹配的數(shù)量，則中心節(jié)點(diǎn)從中選取條滿足Min-Max時(shí)延準(zhǔn)則的鏈路。當(dāng)不存在條獨(dú)立鏈路時(shí)（僅存在條獨(dú)立鏈路），則中心節(jié)點(diǎn)從中選取條滿足Min-Max時(shí)延準(zhǔn)則的鏈路，保持連通性。需要說明的是，此時(shí)和之間只有連通，但當(dāng)算法2結(jié)束后，由于其他相鄰sub-AS之間連通性的保持，整個(gè)AS內(nèi)是連通的。這點(diǎn)將在附錄中進(jìn)行證明。
當(dāng)階段3完成后，中心節(jié)點(diǎn)將鏈路列表分發(fā)給各成員節(jié)點(diǎn)，成員節(jié)點(diǎn)按照鏈路列表更新連接關(guān)系。同時(shí)，各節(jié)點(diǎn)以一定的周期廣播hello信息以適應(yīng)拓?fù)涞膭討B(tài)性，維護(hù)拓?fù)涞膬?yōu)化目標(biāo)。
算法2 sub-AS間拓?fù)淇刂?/p>
Output:
Begin:
end for
else
end for
end if
end for
then
end if
end for
4 控制消息復(fù)雜度分析
這里通過計(jì)算拓?fù)淇刂七^程中3個(gè)階段的控制消息交換量對控制消息復(fù)雜度進(jìn)行分析。令表示AS中的總節(jié)點(diǎn)數(shù)量，表示AS中劃分的sub-AS數(shù)目，表示sub-AS中的平均節(jié)點(diǎn)數(shù)量，即。令表示sub-AS中節(jié)點(diǎn)成為邊界節(jié)點(diǎn)的平均概率，。令表示sub-AS周圍相鄰sub-AS的平均個(gè)數(shù)，。
表1給出了在各sub-AS中算法各階段為完成拓?fù)淇刂扑枰牡钠骄?shù)量。表1將各階段劃分為主要步驟，給出了消耗的消息數(shù)量。則從表1中可以得到，在整個(gè)AS中，所需要的控制消息數(shù)量為。進(jìn)一步化簡為，其最壞情況為。
表1 對于一個(gè)sub-AS算法各階段的消息復(fù)雜度
5 仿真結(jié)果與性能分析
由于所提出的算法是混合了中心式和分布式的混合控制算法，這里將其與典型的中心控制算法[31]以及分布式算法[31]做對比。選擇這2個(gè)算法進(jìn)行對比的原因是，其優(yōu)化準(zhǔn)則和本文算法同是Min-Max準(zhǔn)則。仿真結(jié)果利用NS2軟件仿真得到。
對于每次AS拓?fù)淇刂品抡妫紤]如下參數(shù)。
3) 1 000次重復(fù)統(tǒng)計(jì)。
本文提出的混合式算法，在其階段1 sub-AS生成的過程中，中心節(jié)點(diǎn)和成員節(jié)點(diǎn)之間均是1跳連接。對應(yīng)于AS區(qū)域中不同節(jié)點(diǎn)數(shù)目，階段1算法生成的各sub-AS中平均節(jié)點(diǎn)數(shù)目分別為6.68、7.67、8.64、9.69和10.15（1 000次統(tǒng)計(jì)結(jié)果）。需注意的是，通過AS區(qū)域中取不同的節(jié)點(diǎn)數(shù)目，并保持其他參數(shù)（如區(qū)域大小、節(jié)點(diǎn)的最大信息收發(fā)距離等）不變，實(shí)際上調(diào)整了算法中的節(jié)點(diǎn)連接度。
圖3給出了在一次仿真統(tǒng)計(jì)過程中，所提出算法的各階段實(shí)際拓?fù)淇刂平Y(jié)果。
圖4給出了相同仿真條件下，3種算法拓?fù)淇刂平Y(jié)果中節(jié)點(diǎn)間最大（max）和平均（avg）時(shí)延的統(tǒng)計(jì)結(jié)果。需指出，仿真過程中，僅考慮了鏈路傳播時(shí)延（實(shí)際中還可能存在處理、傳輸時(shí)延）。仿真條件中，節(jié)點(diǎn)的最大信息收發(fā)距離是350 km，對應(yīng)的信息傳播時(shí)延為1.167 ms。當(dāng)時(shí)，本文算法將節(jié)點(diǎn)數(shù)目為125時(shí)的最大時(shí)延降至0.864 ms，將節(jié)點(diǎn)數(shù)目為225時(shí)的最大時(shí)延降至0.577 ms。相比經(jīng)典的分布式算法，最大時(shí)延低9.5%~18.1%，相比中心式算法高10.9%~ 18.9%。對于平均時(shí)延，當(dāng)節(jié)點(diǎn)數(shù)為125時(shí)，本文算法結(jié)果中節(jié)點(diǎn)間平均時(shí)延為0.524 ms，當(dāng)節(jié)點(diǎn)數(shù)為225時(shí)低至0.354 ms。相比算法，平均時(shí)延低9.0%~12.1%，相比平均時(shí)延高10.8%~ 13.2%。
可以看出，本文算法統(tǒng)計(jì)得到的鏈路時(shí)延優(yōu)化性能在中心式算法和分布式算法中間。這種結(jié)果是能預(yù)期的，因?yàn)楸疚乃惴ㄊ且环N混合了中心式和分布式的算法。盡管中心式控制算法具有更好的鏈路時(shí)延優(yōu)化性能（約10.8%~20.8%），但中心式控制算法并不適合空間信息網(wǎng)這種大尺度網(wǎng)絡(luò)。因?yàn)橹行目刂扑惴ㄐ枰粋€(gè)功能強(qiáng)大的中心實(shí)體獲取并計(jì)算AS內(nèi)所有節(jié)點(diǎn)的控制信息，同時(shí)控制消息需要經(jīng)過多跳、長時(shí)延的收發(fā)，網(wǎng)絡(luò)的控制效率低下。相反，本文算法中拓?fù)淇刂葡⒈患s束在各sub-AS及其相鄰周圍，網(wǎng)絡(luò)控制效率高，同時(shí)其鏈路時(shí)延優(yōu)化效果優(yōu)于純分布式的算法。因此，對于空間信息網(wǎng)的拓?fù)淇刂疲疚奶岢龅乃惴ň哂懈玫尼槍π院瓦m用性。
圖5給出了本文算法的平均節(jié)點(diǎn)度。相比無拓?fù)淇刂频那闆r，顯然本文算法中節(jié)點(diǎn)的連接度不取決于網(wǎng)絡(luò)的規(guī)模和節(jié)點(diǎn)的密度。圖6給出了完成本文算法平均每節(jié)點(diǎn)的消息交互數(shù)量。根據(jù)消息復(fù)雜度的分析，本文算法的消息復(fù)雜度是。對于每個(gè)節(jié)點(diǎn)，平均要求消息數(shù)量為。圖6中的仿真統(tǒng)計(jì)結(jié)果驗(yàn)證了分析，當(dāng)AS中的節(jié)點(diǎn)數(shù)目從125增加到225，平均每節(jié)點(diǎn)的消息交互數(shù)量并未有明顯增加。綜上，本文算法具有較高的效率，可用性高。
6 結(jié)束語
本文提出了空間信息網(wǎng)的一種分層自治域網(wǎng)絡(luò)模型，根據(jù)節(jié)點(diǎn)屬性將網(wǎng)絡(luò)劃分為不同的自治域和子自治域，將網(wǎng)內(nèi)各動態(tài)因素解耦合，從而簡化了整網(wǎng)控制的復(fù)雜問題。在該模型的基礎(chǔ)上，提出一種最小化時(shí)延的自治域拓?fù)淇刂扑惴?。與現(xiàn)有的集中式和分布式拓?fù)淇刂品椒ú煌撍惴ú捎没旌鲜降姆椒?，其控制信息被約束在相鄰子自治域范圍內(nèi)，控制信息開銷少，更適用于空間信息網(wǎng)這樣的大尺度網(wǎng)絡(luò)。此外，本文還對所提出算法的強(qiáng)連通性進(jìn)行了證明，仿真結(jié)果驗(yàn)證了理論分析和所提出算法的效率。
附錄 算法1和算法2的k連通性證明
為了對所提出的算法1和算法2的連通性進(jìn)行證明，證明結(jié)果采用如下定理1和定理2表示。
1) 算法1的連通性證明
最后，對定理1的正確性進(jìn)行證明。
2) 算法2的連通性
為了證明定理2的正確性，首先證明如下3條引理。
證明 由定理1，sub-AS內(nèi)部的各節(jié)點(diǎn)之間是連通的。這里把sub-AS看做一個(gè)節(jié)點(diǎn)，也即是將圖表示為，其中，，。實(shí)際上，邊應(yīng)該至少包含和之間的條獨(dú)立路徑。令表示將中的sub-AS看作節(jié)點(diǎn)后圖，其中，。用表示中的sub-AS是因?yàn)檫@里不需要考慮sub-AS內(nèi)的拓?fù)浣Y(jié)構(gòu)（無論和均是連通的）。由于假設(shè)sub-AS均為節(jié)點(diǎn)，那么認(rèn)為和表示相同的邊。算法2中，每個(gè)邊均有一個(gè)值。
定理2證明 由定理1可知，算法1結(jié)束后，每個(gè)sub- AS均滿足。將這些sub-AS劃分為集合，其中各個(gè)集合包含的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] 國家自然科學(xué)基金委員會. 空間信息網(wǎng)絡(luò)基礎(chǔ)理論與關(guān)鍵技術(shù)重大研究計(jì)劃2015 [R]. NSFC 2015年度項(xiàng)目指南. 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] 葛曉虎, 劉應(yīng)狀, 董燕, 等. 一種基于 MESH 結(jié)構(gòu)的空天信息網(wǎng)絡(luò)模型[J]. 微電子學(xué)與計(jì)算機(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]. 計(jì)算機(jī)技術(shù)與發(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)絡(luò)路由算法[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
國家自然科學(xué)基金資助項(xiàng)目（No.91338201, No.91438109, No.61571464）
The National Natural Science Foundation of China (No.91338201, No.91438109, No.61571464)
張威（1987-），男，河南商丘人，解放軍理工大學(xué)博士生，主要研究方向?yàn)樾l(wèi)星通信、空間信息網(wǎng)絡(luò)等。
張更新（1967-），男，浙江平湖人，博士，解放軍理工大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾l(wèi)星通信、空間信息網(wǎng)絡(luò)、深空通信等。
邊東明（1975-），男，山東鄆城人，博士，解放軍理工大學(xué)副教授，主要研究方向?yàn)樾l(wèi)星通信、深空通信等。
茍亮（1981-），男，湖北枝江人，解放軍理工大學(xué)博士生，主要研究方向?yàn)樾l(wèi)星通信、深空通信、網(wǎng)絡(luò)編碼等。
謝智東（1984-），男，甘肅通渭人，博士，解放軍理工大學(xué)講師，主要研究方向?yàn)樾l(wèi)星通信、空間信息網(wǎng)絡(luò)、深空通信等。
猜你喜歡
中華手工(2017年2期)2017-06-06 23:00:31
中外會展(2014年4期)2014-11-27 07:46:46
大眾創(chuàng)業(yè)(2009年10期)2009-10-08 04:52:00
數(shù)字社區(qū)&智能家居(2009年7期)2009-09-29 08:16:48
數(shù)字社區(qū)&智能家居(2009年11期)2009-06-25 04:30:34
數(shù)字社區(qū)&智能家居(2009年3期)2009-04-21 03:09:04
數(shù)字社區(qū)&智能家居(2009年2期)2009-03-27 04:33:44
數(shù)字社區(qū)&智能家居(2009年12期)2009-02-03 07:50:48
建筑創(chuàng)作(2001年3期)2001-08-22 18:48:14
祝您健康(1987年3期)1987-12-30 09:52:32
