空間信息網(wǎng)絡(luò)中基于LT碼的分布式存儲(chǔ)策略

孔 博 張更新 張 威 程 磊

?

空間信息網(wǎng)絡(luò)中基于LT碼的分布式存儲(chǔ)策略

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

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

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

空間信息網(wǎng)絡(luò)；分布式存儲(chǔ)；噴泉碼；LT碼

1 引言

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

徑[1]?？臻g信息網(wǎng)絡(luò)是以多種空間平臺(tái)為載體，通過多種形式的鏈路一體化組網(wǎng)設(shè)計(jì)，支持海量數(shù)據(jù)的實(shí)時(shí)采集、傳輸和處理，實(shí)現(xiàn)空間信息體系化應(yīng)用的網(wǎng)絡(luò)系統(tǒng)。相比傳統(tǒng)衛(wèi)星網(wǎng)絡(luò)，空間信息網(wǎng)絡(luò)具有體系結(jié)構(gòu)復(fù)雜、拓?fù)鋭?dòng)態(tài)變化和自組織程度高等特征，網(wǎng)絡(luò)某一局部范圍內(nèi)組網(wǎng)應(yīng)用方式、拓?fù)浣Y(jié)構(gòu)的變化都會(huì)影響到全網(wǎng)的狀態(tài)。結(jié)合未來空間信息網(wǎng)絡(luò)發(fā)展趨勢，按照節(jié)點(diǎn)屬性將空間信息網(wǎng)絡(luò)劃分為一系列由相似類型節(jié)點(diǎn)組成的自治域(Autonomous System, AS)，將整體上是高動(dòng)態(tài)變化的空間信息網(wǎng)解耦合為局部具有弱動(dòng)態(tài)性變化的準(zhǔn)靜態(tài)子網(wǎng)[2]，從而將整網(wǎng)控制的問題簡單化。

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

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

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

2 網(wǎng)絡(luò)模型與問題描述

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

圖1 空間信息網(wǎng)絡(luò)分層自治域劃分

假設(shè)2 節(jié)點(diǎn)存儲(chǔ)能力有限，只存儲(chǔ)一個(gè)大小固定的數(shù)據(jù)包。

假設(shè)3 自治域是連通的，任意2個(gè)節(jié)點(diǎn)能直

圖2 自治域模型

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

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

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

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

3 DSSLT策略

3.1 LT碼

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

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

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

3.2 DSSLT策略

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

3.2.1初始化階段

步驟 4 根據(jù)定向隨機(jī)漫步機(jī)制，每個(gè)數(shù)據(jù)節(jié)點(diǎn)選擇鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)。

3.2.2信息估計(jì)階段 在信息估計(jì)階段，數(shù)據(jù)包根據(jù)定向隨機(jī)漫步機(jī)制在自治域內(nèi)進(jìn)行傳輸，與LTCDS策略利用隨機(jī)漫步的時(shí)間統(tǒng)計(jì)特性估計(jì)全局信息不同，本文提出一種簡單高效的基于ID估計(jì)法，使得所有存儲(chǔ)節(jié)點(diǎn)能夠準(zhǔn)確快速估計(jì)和。具體步驟如下：

步驟 3 根據(jù)定向隨機(jī)漫步機(jī)制，選擇某個(gè)鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)；

步驟 4 根據(jù)定向隨機(jī)漫步機(jī)制，選擇某個(gè)鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)；

3.2.4 存儲(chǔ)階段 在編碼階段，每個(gè)數(shù)據(jù)包至少遍歷自治域內(nèi)所有存儲(chǔ)節(jié)點(diǎn)一次，存儲(chǔ)節(jié)點(diǎn)在選擇異或所有數(shù)據(jù)包之后，在存儲(chǔ)階段存儲(chǔ)更新之后的數(shù)據(jù)包。

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

4 性能分析

4.1 隨機(jī)漫步步長

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

4.2 譯碼成功概率

譯碼成功概率等于每個(gè)節(jié)點(diǎn)滿足其編碼度分布的概率，假設(shè)數(shù)據(jù)包在某次隨機(jī)漫步中已訪問節(jié)點(diǎn)的次數(shù)為，則節(jié)點(diǎn)未異或數(shù)據(jù)包的概

表1 DSSLT策略偽代碼

算法：DSSLT

開始：

/*初始化階段*/

end

end

/*信息估計(jì)階段*/

end

end

end

/*編碼階段*/

end

end

coin=rand(1)；

end

end

end

end

/*存儲(chǔ)階段*/

end

率為

在DSSLT策略中，數(shù)據(jù)包之間獨(dú)立進(jìn)行隨機(jī)漫步，則在隨機(jī)漫步結(jié)束時(shí)，節(jié)點(diǎn)異或的數(shù)據(jù)包個(gè)數(shù)等于期望度分布的概率為

5 仿真結(jié)果

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

5.1 數(shù)據(jù)包覆蓋實(shí)驗(yàn)

數(shù)據(jù)包采用隨機(jī)漫步的方式在自治域內(nèi)傳輸，根據(jù)式(6)，當(dāng)隨機(jī)漫步的步數(shù)時(shí)，數(shù)據(jù)包以能夠極大的概率遍歷網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)，覆蓋率近似達(dá)到100%。數(shù)據(jù)包遍歷整個(gè)自治域步長越小，網(wǎng)絡(luò)通信能耗就越小。我們比較簡單隨機(jī)漫步和定向隨機(jī)漫步對數(shù)據(jù)包覆蓋性能的影響，仿真次數(shù)為500次。

5.2 全局信息估計(jì)實(shí)驗(yàn)

在全局信息估計(jì)實(shí)驗(yàn)中，比較分別采用基于ID估計(jì)法和LTCDS策略中的估計(jì)法時(shí)，自治域內(nèi)所有存儲(chǔ)節(jié)點(diǎn)正確估計(jì)自治域全局信息和時(shí)，定向隨機(jī)漫步所需步長，蒙特卡洛仿真次數(shù)為500次。作為比較，給出采用簡單隨機(jī)漫步時(shí)全局信息估計(jì)性能。

表2所示為分別取100和300，即不同網(wǎng)絡(luò)規(guī)

表2 全局信息估計(jì)實(shí)驗(yàn)所需隨機(jī)漫步步長

表2所示為分別取100和300，即不同網(wǎng)絡(luò)規(guī)

網(wǎng)絡(luò)規(guī)模估計(jì)方法定向隨機(jī)漫步簡單隨機(jī)漫步 估計(jì)值估計(jì)值估計(jì)值估計(jì)值 =100,=10ID估計(jì)法 8.44 23.90 11.04 60.40 LTCDS估計(jì)法20.54 456.30 44.591752.60 =300,=30ID估計(jì)法 78.76 145.23130.20 188.60 LTCDS估計(jì)法249.051482.50582.474790.60

圖3 數(shù)據(jù)包覆蓋實(shí)驗(yàn)

5.3 數(shù)據(jù)包恢復(fù)實(shí)驗(yàn)

在數(shù)據(jù)包恢復(fù)實(shí)驗(yàn)中，我們通過仿真來比較DSSLT策略與LTCDS策略性能。比較成功譯碼概率與數(shù)據(jù)包查詢比率之間的關(guān)系，與LTCDS策略相同，成功譯碼概率定義為在次試驗(yàn)中，所有個(gè)數(shù)據(jù)包成功恢復(fù)的次數(shù)所占的比例，即；數(shù)據(jù)包查詢比率定義為查詢節(jié)點(diǎn)數(shù)與數(shù)據(jù)節(jié)點(diǎn)之間的比值，即。在仿真中，數(shù)據(jù)包采用定向隨機(jī)漫步進(jìn)行傳輸，存儲(chǔ)節(jié)點(diǎn)采用基于ID法估計(jì)全局信息。令,，即，蒙特卡洛仿真次數(shù)為500次，即。

6 結(jié)束語

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

圖4 數(shù)據(jù)包恢復(fù)性能 圖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] 王娟, 王萍. 一種自適應(yīng)數(shù)據(jù)逐層分解的Reed-Solomon碼迭代糾錯(cuò)方法及應(yīng)用[J]. 電子與信息學(xué)報(bào), 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]. 電子與信息學(xué)報(bào), 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年生，博士生，研究方向?yàn)樾l(wèi)星通信、空間信息網(wǎng)絡(luò)、網(wǎng)絡(luò)編碼理論及其應(yīng)用.

張更新： 男，1967年生，教授，博士，博士生導(dǎo)師，研究方向?yàn)樾l(wèi)星通信、深空通信.

張 威： 男，1987年生，博士生，研究方向?yàn)榭臻g信息網(wǎng)絡(luò)、拓?fù)淇刂啤⒕W(wǎng)絡(luò)容量.

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；網(wǎng)絡(luò)出版：2016-02-18

張更新 kbvx_123@163.com

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