空間信息網絡中基于LT碼的分布式存儲策略

孔 博 張更新 張 威 程 磊

?

空間信息網絡中基于LT碼的分布式存儲策略

孔 博①張更新*①張 威①程 磊②

①(解放軍理工大學通信工程學院 南京 210007)②(解放軍國防信息學院 武漢 430015)

針對空間信息網絡(Space Information Network, SIN)節點存儲資源嚴重受限及存儲可靠性問題，該文提出一種基于LT(Luby Transform)碼的分布式存儲策略(Distributed Storage Strategy based on LT codes, DSSLT)。采用定向隨機漫步機制，使得源數據包能夠更快地遍歷整個網絡。在信息估計階段利用基于ID的估計方法進行網絡全局信息估計，使所有節點快速獲得網絡全局信息。合理的數據包選擇機制使得最終編碼度分布趨于期望的度分布。分析和仿真結果表明，與具有代表性的分布式存儲策略相比，該方法大幅度減少了數據包傳輸時的隨機漫步步長，同時提高了譯碼性能，簡單易行。

空間信息網絡；分布式存儲；噴泉碼；LT碼

1 引言

縱觀世界范圍內，各類衛星通信系統針對不同的任務需求和服務對象構建，缺乏一般性、通用性和協作的能力，存在重復建設、“煙囪式”發展的不利局面，空間信息網絡(Space Information Network, SIN)概念的提出為解決上述問題提供了有效途

徑[1]。空間信息網絡是以多種空間平臺為載體，通過多種形式的鏈路一體化組網設計，支持海量數據的實時采集、傳輸和處理，實現空間信息體系化應用的網絡系統。相比傳統衛星網絡，空間信息網絡具有體系結構復雜、拓撲動態變化和自組織程度高等特征，網絡某一局部范圍內組網應用方式、拓撲結構的變化都會影響到全網的狀態。結合未來空間信息網絡發展趨勢，按照節點屬性將空間信息網絡劃分為一系列由相似類型節點組成的自治域(Autonomous System, AS)，將整體上是高動態變化的空間信息網解耦合為局部具有弱動態性變化的準靜態子網[2]，從而將整網控制的問題簡單化。

當前，空間信息系統所產生的數據信息呈指數級增長，根據UCS (Union of Concerned Scientists)衛星數據庫預測，2020年數據總量將是2010年的44倍[3]。而空間信息網絡節點資源嚴重受限，無法存儲大量數據，當節點失效或傳輸節點雙方長時間不可見時，會帶來數據丟失問題。因此，如何有效地存儲數據是空間信息網絡面臨的一個巨大挑戰。將存儲技術和網絡技術相結合，即“分布式存儲”是一種行之有效的解決方案，它通過網絡通信技術連接分散的存儲節點，構建持久、高可用的冗余存儲空間，存儲海量數據[4]。數據冗余方法可分為兩類：基于復制冗余策略和基于編碼冗余策略。復制冗余策略易于實現，但會消耗大量的存儲空間，不適用于節點存儲能力有限，以及規模較大的網絡。在基于編碼冗余策略如糾刪碼冗余策略[5]中，先將源文件進行分塊編碼，網絡中單個存儲節點只存儲部分編碼塊，從而減少存儲開銷，目的節點可通過接收一定數量的冗余數據來恢復原始數據。針對糾刪碼修復失效節點時需下載全部原始數據，導致修復帶寬過大的問題，文獻[6]將網絡編碼的思想引入修復過程，提出再生碼[7]概念，優化了修復失效節點的帶寬消耗。作為一類重要的編碼方案，噴泉碼[8]具有無碼率特性，且編譯碼復雜度低。LT (Luby Transform)碼[9]是一種具有實用性的噴泉碼，也是使用最廣泛的噴泉碼，非常適合應用于分布式存儲網絡中。

文獻[10]提出將分布式噴泉碼用于無線傳感器網絡，使用簡單隨機漫步(Simple Random Walk, SRW)[11]來傳輸數據包，每個存儲節點根據節點總數和數據包數，利用Metropolis算法計算隨機漫步步長，使得所有數據包達到穩態分布，提高數據的持久性，其編解碼過程類似集中式LT碼。該方案需要已知網絡全局信息(等)，并且需要計算節點概率轉移矩陣，復雜度較大。文獻[12]利用監聽機制來傳輸數據包，優先選擇沒有轉發過某數據包的鄰居節點進行傳輸，提高了數據包傳遞效率，但需要已知存儲節點數，且每個節點需要維護一個緩存隊列，大大增加了存儲量。與本文工作類似的是文獻[13]提出的LTCDS (LT-Codes based Distributed Storage)策略，LTCDS利用簡單隨機漫步的時間統計特性來估計網絡全局信息()，但估計時需要大幅增加隨機漫步步長(實際步長10倍以上)，增加了通信損耗，同時簡單隨機漫步會對局部簇產生影響，即數據包集中在某一區域進行重復地傳輸。

本文以空間信息網絡自治域內信息存儲為背景，以提高能量效率和可靠性為目標，提出了一種基于LT碼的分布式數據存儲策略(Distributed Storage Strategy based on LT codes, DSSLT)，采用定向隨機漫步(Directional Random Walk, DRW)機制來傳輸數據包；在信息估計階段，利用基于ID估計法來估計網絡全局信息()，減少了數據包遍歷自治域所需傳輸次數；合理的數據包選擇機制使得編碼度分布趨于期望的度分布。理論分析和仿真表明，與具有代表性的LTCDS策略相比，DSSLT策略能改進傳輸效率，同時提高譯碼成功率。

2 網絡模型與問題描述

空間信息網絡包含衛星、升空平臺、傳感器、用戶等多種異構節點，其任務、功能、地位和分布空間具有明顯的差異。結合未來空間信息網絡節點種類多、立體多層分布、動態差異性大等特征，根據節點屬性將空間信息網絡劃分為一系列自治域，如圖1所示。每個自治域采用獨立的控制策略，不同自治域之間通過邊界節點實現控制信息的交換，從而將整體上是高動態變化的空間信息網絡劃分為一個個局部具有弱動態性變化的子網絡，解決了子網間動態耦合性和整網可控性的問題。

圖1 空間信息網絡分層自治域劃分

假設2 節點存儲能力有限，只存儲一個大小固定的數據包。

假設3 自治域是連通的，任意2個節點能直

圖2 自治域模型

接或間接通信，且所有的鏈路是對稱和不受遮擋的。

定義 2 隨機漫步(RW)定義為按某一隨機序列訪問隨機圖節點的過程，在隨機漫步中，下一步要訪問的節點是從當前訪問節點的鄰居節點中選取的；若該選取過程是從所有鄰居節點中等概率隨機選取，則該隨機漫步稱為簡單隨機漫步(SRW)。

定義 3 定向隨機漫步(DRW)[14]定義為按如下兩步選取下一步訪問節點的過程：

相比簡單隨機漫步，定向隨機漫步需要記錄所有節點的訪問次數，且每一步需要在2個備選節點之間進行選擇，這會消耗額外的內存和通信能耗。但在LTCDS策略以及下節給出的DSSLT策略中，編碼過程中都需要記錄節點訪問次數，這為采用定向隨機漫步機制提供了便利條件。且文獻[14]證明，定向隨機漫步能夠平均化漫步過程中所有節點的訪問次數，實現網絡內節點的負載均衡，減少系統資源消耗，從而增加系統可用性。因此，本文采用定向隨機漫步機制來傳輸數據包。

3 DSSLT策略

3.1 LT碼

噴泉碼是一種無速率碼，編碼器可以按照某種概率分布獨立地產生任意數量的碼字，具有碼率不受限的特征。LT碼是第1種具有實用性的噴泉碼，被廣泛應用在無線多媒體、文件分發、衛星廣播等領域[15]。在LT碼中，每個編碼包由隨機選取的原始數據包異或而成，編碼包中所包含的原始數據包的個數稱為該編碼包的度，用表示，根據度分布函數得到[8]。

度分布函數是影響LT碼性能的關鍵，好的度分布函數能夠盡可能地恢復所有的原始數據包，且擁有較低的譯碼復雜度。最初，文獻[9]提出了理想孤立子分布(Ideal Soliton Distribution, ISD)，如式(3)：

ISD譯碼開銷很小，但是成功譯碼所需編碼包的數目遠遠大于。文獻[9]通過增加預處理集的初始大小來減小譯碼失敗的概率，給出了魯棒孤立子分布(Robust Soliton Distribution, RSD)。如式(4)：

3.2 DSSLT策略

本節給出DSSLT策略具體方案，在DSSLT中，數據包采用定向隨機漫步機制在自治域內傳輸，隨機漫步步長上界為,包括兩部分：和，其中能夠保證每個節點正確估計網絡全局信息(),使得數據包在編碼階段至少遍歷自治域內所有節點一次。在隨機漫步開始前，在每個數據包包頭增加一個初始值為0的計數器，該數據包每訪問一個節點，計數器值加1，當計數器的值為時，隨機漫步結束。節點利用基于ID估計法來估計全局信息。DSSLT策略的實施分為4個階段：初始化、信息估計、編碼及存儲階段。

3.2.1初始化階段

步驟 4 根據定向隨機漫步機制，每個數據節點選擇鄰居節點發送數據。

3.2.2信息估計階段 在信息估計階段，數據包根據定向隨機漫步機制在自治域內進行傳輸，與LTCDS策略利用隨機漫步的時間統計特性估計全局信息不同，本文提出一種簡單高效的基于ID估計法，使得所有存儲節點能夠準確快速估計和。具體步驟如下：

步驟 3 根據定向隨機漫步機制，選擇某個鄰居節點發送數據；

步驟 4 根據定向隨機漫步機制，選擇某個鄰居節點發送數據；

3.2.4 存儲階段 在編碼階段，每個數據包至少遍歷自治域內所有存儲節點一次，存儲節點在選擇異或所有數據包之后，在存儲階段存儲更新之后的數據包。

DSSLT策略偽代碼如表1所示。

4 性能分析

4.1 隨機漫步步長

由3.2小節可知，隨機漫步步長由兩部分組成：信息估計階段和編碼階段，即，其中使得所有存儲節點在信息估計階段能夠正確估計網絡全局信息(和)，使得數據包在編碼階段至少遍歷自治域內所有節點一次。的取值在下節通過仿真說明，本節分析遍歷所有節點所需步長。

4.2 譯碼成功概率

譯碼成功概率等于每個節點滿足其編碼度分布的概率，假設數據包在某次隨機漫步中已訪問節點的次數為，則節點未異或數據包的概

表1 DSSLT策略偽代碼

算法：DSSLT

開始：

/*初始化階段*/

end

end

/*信息估計階段*/

end

end

end

/*編碼階段*/

end

end

coin=rand(1)；

end

end

end

end

/*存儲階段*/

end

率為

在DSSLT策略中，數據包之間獨立進行隨機漫步，則在隨機漫步結束時，節點異或的數據包個數等于期望度分布的概率為

5 仿真結果

為了驗證DSSLT策略的性能，我們通過蒙特卡洛仿真，從3個方面對其進行仿真分析，首先測試覆蓋率與隨機漫步步長之間的關系，稱為數據包覆蓋實驗；其次測試全局信息估計性能與隨機漫步步長的關系，稱為全局信息估計實驗；最后測試成功譯碼概率與訪問節點個數之間的關系，稱為數據包恢復實驗。在仿真過程中，個節點均勻隨機分布在的區域中，其中數據節點的比例為10%，即，自治域內每個節點的通信半徑滿足條件km。

5.1 數據包覆蓋實驗

數據包采用隨機漫步的方式在自治域內傳輸，根據式(6)，當隨機漫步的步數時，數據包以能夠極大的概率遍歷網絡中每個節點，覆蓋率近似達到100%。數據包遍歷整個自治域步長越小，網絡通信能耗就越小。我們比較簡單隨機漫步和定向隨機漫步對數據包覆蓋性能的影響，仿真次數為500次。

5.2 全局信息估計實驗

在全局信息估計實驗中，比較分別采用基于ID估計法和LTCDS策略中的估計法時，自治域內所有存儲節點正確估計自治域全局信息和時，定向隨機漫步所需步長，蒙特卡洛仿真次數為500次。作為比較，給出采用簡單隨機漫步時全局信息估計性能。

表2所示為分別取100和300，即不同網絡規

表2 全局信息估計實驗所需隨機漫步步長

表2所示為分別取100和300，即不同網絡規

網絡規模估計方法定向隨機漫步簡單隨機漫步 估計值估計值估計值估計值 =100,=10ID估計法 8.44 23.90 11.04 60.40 LTCDS估計法20.54 456.30 44.591752.60 =300,=30ID估計法 78.76 145.23130.20 188.60 LTCDS估計法249.051482.50582.474790.60

圖3 數據包覆蓋實驗

5.3 數據包恢復實驗

在數據包恢復實驗中，我們通過仿真來比較DSSLT策略與LTCDS策略性能。比較成功譯碼概率與數據包查詢比率之間的關系，與LTCDS策略相同，成功譯碼概率定義為在次試驗中，所有個數據包成功恢復的次數所占的比例，即；數據包查詢比率定義為查詢節點數與數據節點之間的比值，即。在仿真中，數據包采用定向隨機漫步進行傳輸，存儲節點采用基于ID法估計全局信息。令,，即，蒙特卡洛仿真次數為500次，即。

6 結束語

本文對空間信息網絡分層自治域內信息存儲問題進行了研究，提出了一種簡單高效的分布式存儲策略DSSLT。分析和仿真結果表明，與同類方法相比，該策略具有傳輸效率高、簡單易行、譯碼性能優的特點。因此，DSSLT策略可以在保證較高譯碼性能的同時減少自治域內節點通信能耗，使空間信息網絡整網管理控制得到優化，具有很高的應用價值。

圖4 數據包恢復性能 圖5 編碼度分布情況

[1] DONG Feihong, Huang Qinfei, LI Hongjun,. A novel M2M backbone network architecture[J]., 2015, 15(11): 1-10. doi: 10.1155/2015/512321.

[2] ZHANG Wei, ZHANG Gengxin, GOU Liang,. A hierarchical autonomous system based topology control algorithm in space information network[J]., 2015, 9(9): 3572-3593. doi: 10.3837/tiis.2015.09.016.

[3] ZHANG Gengxin, ZHANG Wei, and ZHANG Hua. A novel proposal of architecture and network model for space communication networks[C]. Proceeding of the 65th International Astronautical Congress, Toronto, Canada, 2014: 147-153.

[4] LI Bo, WANG Mengdi, ZHAO Yongxin,. Modeling and verifying Google file system[C]. Proceeding of the 16th IEEE International Symposium on High Assurance Systems Engineering (HASE), Daytona Beach Shores, FL, 2015: 207-214.

[5] 王娟, 王萍. 一種自適應數據逐層分解的Reed-Solomon碼迭代糾錯方法及應用[J]. 電子與信息學報, 2015, 37(5): 1173-1179. doi: 10.11999/JEIT140907.

WANG Juan and WANG Ping. An adaptive Reed-Solomon iterative correction method based on data layer-wise decomposition and its application[J].&, 2015, 37(5): 1173-1179. doi: 10.11999/JEIT140907.

[6] Dimakis A G, Godfrey P B, Wainwright M,. Network coding for distributed storage systems[J]., 2010, 56(9): 4539-4551. doi: 10.1109 /TIT.2010.2054295.

[7] Toni E. Codes between MBR and MSR points with exact repair property[J]., 2014, 60(11): 6993-7005. doi: 10.1109/TIT.2014. 2351252.

[8] 郭曉, 張更新, 徐任暉, 等. 一種用于RaptorQ碼的降維快速譯碼算法[J]. 電子與信息學報, 2015, 37(6): 1310-1316. doi: 10.11999/JEIT141037.

GUO Xiao, ZHANG Gengxin, XU Renhui,. Fast decoding algorithm for RaptorQ code using matrix dimensionality reduction[J].&, 2015, 37(6): 1310-1316. doi: 10. 11999/JEIT141037.

[9] Byers J W, Luby M, and Mitzenmacher M A. Digital fountain approach to asynchronous reliable multicast[J]., 2002, 20(3): 1528-1540. doi: 10.1109/JSAC.2002.803996.

[10] LIN Yunfeng, LIANG Ben, and LI Baochun. Data persistence in large-scale sensor networks with decentralized fountain codes[C]. Proceeding of the 26th IEEE International Conference on Computer Communications (INFOCOM), Anchorage, AK, 2007: 1658-1666.

[11] Tzeveleksa L, Oikonomou K, and Stavrakakis I. Random walk with jumps in large-scale random geometric graphs[J]., 2010, 33(13): 1505-1514. doi: 10.1016/j.comcom.2010.01.026.

[12] LIANG Junbin, WANG Jianxin, and CHEN Jianer. An overhearing-based scheme for improving data persistence in wireless sensor networks[C]. Proceeding of the IEEE International Conference on Communications (ICC), Cape Town, South Africa, AK, 2010: 1-5.

[13] KONG Zhenning, Aly S A, and Soljanin E. Decentralized coding algorithms for distributed storage in wireless sensor networks[J]., 2010, 28(2): 261-267. doi: 10.1109/JSAC. 2010.100215.

[14] Avin C and Krishnamachari B. The power of choice in random walks: an empirical study[J]., 2008, 52(1): 44-60. doi: 10.1016/j.comnet.2007.09.012.

[15] Abdulhussein A, Oka A, and Nguyen T T. Rateless coding for hybrid free-space optical and radio-frequency communications[J]., 2010, 9(3): 907-913. doi: 10.1109/TWC. 2010.03.090108.

[16] Gianini G and Damiani E. The cover time of neighbor- avoiding gossiping on geometric random networks[C]. Proceeding of the 7th IEEE International Conference on Digital Ecosystems and Technologies (DEST), Menlo Park, CA, 2013: 7-12.

孔 博： 男，1987年生，博士生，研究方向為衛星通信、空間信息網絡、網絡編碼理論及其應用.

張更新： 男，1967年生，教授，博士，博士生導師，研究方向為衛星通信、深空通信.

張 威： 男，1987年生，博士生，研究方向為空間信息網絡、拓撲控制、網絡容量.

Foundation Items: The National Natural Science Foundation of China (91338201, 91438109, 61401507, 61571464)

Distributed Storage Strategy Based on LT Codes in Space Information Network

KONG Bo①ZHANG Gengxin①ZHANG Wei①CHENG Lei②

①(College of Communication Engineering, PLA University of Science and Technology, Nanjing 210007, China)②(PLA Academy of National Defense Information, Wuhan 430015, China)

To solve the limited storage resource and the data storage reliability problem of Space Information Network (SIN), a novel Distributed Storage Strategy based on Luby Transform (LT) codes (DSSLT) is proposed. According to the proposed strategy, source data packets are transmitted quickly to every node in the network based on directional random walk. The ID-based estimation method is used to estimate the global information at the information estimation phase, the values are obtained without excessive random walks. The procedure of XORing packets is reasonable so that the distribution of code degree tends to the desired degree distribution. As presented by the analyses and simulations, random walk steps are greatly reduced compared with a representative distributed storage strategy, while improving the decoding performance.

Space Information Network (SIN); Distributed storage; Fountain codes; Luby Transform (LT) codes

TP393

A

1009-5896(2016)04-0787-08

10.11999/JEIT150674

2015-05-15；改回日期：2015-12-08；網絡出版：2016-02-18

張更新 kbvx_123@163.com

國家自然科學基金(91338201, 91438109, 61401507, 61571464)