移動低占空比無線傳感器網絡中低時延的數據持續性提高算法

蔣嬋，李陶深，梁俊斌

?

移動低占空比無線傳感器網絡中低時延的數據持續性提高算法

蔣嬋1,2，李陶深1,2，梁俊斌2

（1. 華南理工大學電子與信息學院，廣東 廣州 510641；2. 廣西大學計算機與電子信息學院 廣西多媒體通信與網絡技術重點實驗室，廣西 南寧 530004）

移動低占空比無線傳感器網絡是近年來出現的新型網絡。在移動低占空比無線傳感器網絡中，由于節點的存儲空間有限，并且節點的移動及睡眠會導致網絡不連通、數據無法及時傳輸等問題，使數據很難被快速分發并存儲，數據持續性較低。為此，提出一種盧比變換碼的分布式數據存儲（LT-MDS, Luby transform codes based mobile distributed storage）算法，該算法采用一種新的傳染病式數據分發方法在節點不斷移動的網絡中分發數據，使數據能以較低的時延被網絡中絕大部分節點接收到，提高了網絡的可靠性；節點在接收到數據的同時，利用盧比變換碼（LTC, Luby transform code）對數據進行編碼存儲，使容量有限的節點可以保存更多的數據信息。理論分析和仿真實驗表明，LT-MDS算法能夠以低時延完成數據分發和存儲，同時獲得較高的數據持續性。

移動低占空比無線傳感器網絡；數據持續性；低時延；傳染病式數據分發；數據存儲

1 引言

無線傳感器網絡[1]（WSN, wireless sensor network）由大量部署在監測區域內的微型傳感器節點構成，是一種能夠長期執行環境監測、事件跟蹤等任務的無線多跳自組織網絡，在國防、軍事、農業、工業等領域具有廣泛的應用。在WSN中，節點通常只有有限的通信、計算和存儲能力，它們的能量水平也較低。移動低占空比無線傳感器網絡[2]（MLDC-WSN, mobile low-duty-cycle wireless sensor network）是近年來出現的新型WSN，它可以把節點部署在移動的物體上，利用物體的移動性來采集范圍更廣且動態的環境信息。例如，在牧場環境監測應用中，節點掛在每只羊的耳朵上，整個羊群組成一個移動的WSN。為了減少能量耗費，它使節點長時間處于睡眠狀態，只在周期性喚醒時工作和通信，可以極大地延長節點的工作壽命。這種工作模式就稱為低占空比模式。

MLDC-WSN一般部署在條件惡劣的環境，節點容易遭到外力破壞而丟失數據。例如，當羊群遇到雷暴雨時，羊身上的節點容易損壞。因此，在MLDC-WSN中，網絡一般沒有固定的Sink來實時收集節點的數據。為了避免節點損壞而丟失數據，一個可行的方法是采用冗余存儲，即一個節點在感知到數據后，立即將該數據發送給網絡中其他節點進行保存。這樣即使這個節點損壞，仍然可以從其他節點獲取它的數據。

但是，網絡中往往有多個節點感知到數據（即存在多個（源）數據），而節點的存儲容量有限，因此，很難存放多個數據。此外，由于節點的移動性，網絡不一定能時刻保持連通，數據分發過程可能被中斷。因此，如何有效地規劃節點分發數據和存儲數據的方式，提高數據持續性，是目前研究的一個挑戰。其中，數據持續性是指網絡在節點隨著工作時間增長而不斷損壞的情況下，全部源數據能夠被恢復出來的能力。

本文提出一種面向MLDC-WSN的基于盧比變換碼[3]（LTC, Luby transform code）的分布數據存儲算法（LT-MDS, Luby transform code based mobile distributed storage），可以快速完成數據分發和存儲，并且增加節點有限存儲空間里的數據量，有效提高數據持續性。其中，LTC是一種網絡編碼，具有較低的編碼和解碼復雜性，利于在計算能力有限的節點上實現。最后，通過理論分析和仿真實驗證明了LT-MDS的有效性。

2 相關工作

目前，已經有一些工作研究如何利用網絡編碼存儲數據以提高數據持續性。文獻[4]分析了網絡編碼技術的有效性，通過對比傳統的編碼方式（如RS碼（RSC, reed-solomon code）、隨機線性碼（RLC, random linear code）等）得到以下結論。各種網絡編碼均能實現數據的持續性，但是不同編碼方式要求的存儲空間不同，例如，RSC需要的存儲空間要比RLC的高。增長碼[5]（GC, growth code）是一種具有較低存儲空間要求的網絡編碼，它通過節點與鄰居之間的信息交互，不斷增加存儲的編碼數據的信息量。但是，隨著時間的增長，節點中存儲的編碼數據信息量越來越大，解碼也越來越困難，不利于數據持續性的提高。文獻[6]提出了優先隨機線性碼（PRLC, priority random linear code），通過具有優先級的隨機線性碼來提高重要數據的持續性。它對重要性越高的數據采用越低的編碼率，即減少多個數據合并成一個編碼數據的概率，使重要的數據可以更容易地被恢復出來。文獻[7]提出了地理隨機線性碼（GRLC, geometric random linear code），利用節點的地理信息，使距離事件發生地點越近的區域內，節點存儲的信息越多，這樣便于數據采集者在事件區域附近進行數據恢復和收集。文獻[8]提出了結構化隨機線性碼（SRLC, structured random linear code），利用編碼數據中信息分布的稀疏性，重新設計碼字的結構，可以有效降低解碼復雜性。文獻[9]提出了一種基于RLC且能提供一定容錯率的分布式存儲方案。文獻[10]設計了一種基于壓縮感知（CS, compressive sensing）的編碼方法，進一步減少編碼數據的容量，以此增加網絡中保存的信息量。

以上編碼方式的優點是便于分布式實現，節點只需要和鄰居節點交換信息即可完成數據的編碼存儲。但是，GC、RSC和各種RLC的解碼復雜度仍然較高，達到(3)，影響了數據持續性的提高，其中，是源數據的數量。為了進一步提高數據持續性，需要考慮解碼復雜度更低的編碼方式。噴泉碼（FC, fountain code）是一種具有較低的編碼和解碼復雜性(ln)的編碼方式，目前受到越來越多的關注。LTC是噴泉碼中最典型的實現方式，節點可以根據特定的概率分布選擇需要編碼存儲的數據的數量，然后根據從源數據隨機挑選出相應數量的數據進行異或（XOR）操作即可。

EDFC[11]是第一種基于LTC的數據持續性提高算法，它使源節點通過隨機行走（RW, random walk）向網絡中以多條路徑分發數據并進行存儲。但是，由于隨機行走覆蓋整個網絡需要相當長的時間和大量的數據通信，完成數據分發的時延很大，而且節點的能耗相當大。因此，EDFC并不利于快速實現數據持續性，且能量有效性較低。RCDS[12]針對EDFC進行改進，通過限定隨機行走的長度，減少數據分發時延和節點通信的能耗。此外，在數據分發前，利用低密度奇偶校驗碼[13]（LDPC, low-density parity check code）對數據進行預編碼，降低數據恢復的解碼復雜度。文獻[14]提出了一種多數據副本的分發方案，使源節點可以將多個數據副本隨機分發到附近的鄰居，減少了編碼過程中網絡節點的能量消耗。文獻[15]設計了一種基于速龍碼（RC, raptor code）的數據保存方案。RC也是一種噴泉碼，具有比LTC更低的解碼復雜度，但是它要求對數據進行預處理，需要節點間進行更多的數據交互。

為了進一步降低數據分發時延和節點的能耗，一些研究人員采用廣播（broadcast）來分發數據。文獻[16]提出了一種分布存儲算法（DSA, distributed storage algorithm）。假設網絡中有2種節點：數據（源）節點和存儲節點。源節點將通過廣播，發送自己的數據給通信范圍內的存儲節點進行保存。DSA要求存儲節點具有較大的存儲空間，因此，不利于在存儲容量有限的節點上實現。文獻[17]提出了一種帶隨機能量控制的糾刪碼（ECPC, erasure coding with randomized power control），考慮了網絡斷裂的情況，節點進行數據中繼時，可以預測網絡拓撲的連通性，并根據預測的結果調整廣播的傳輸距離，使數據最終能以高概率被所有節點接收到并進行編碼存儲。文獻[18]提出了一種自適應的基于概率廣播的協議（APBDP, adaptive probabilistic broadcast based protocol），節點可以通過統計鄰居的數量，以概率決定是否轉發數據，不需要網絡中的全局信息，實現完全分布式的數據分發。由于網絡中僅有一小部分節點轉發數據，不僅降低了數據分發時延，還減少了網絡的總能耗。文獻[19]提出了根據節點能量水平來決定數據轉發概率的概率廣播方案，并以此為基礎設計了基于LTC的數據保存機制。

以上的工作均是在傳統WSN上進行研究的，沒有考慮節點的移動性和低占空比特性，很難在MLDC-WSN中應用。因此，需要考慮新的數據分發方式，并結合網絡編碼的特點，設計新的數據持續性提高算法。

另一方面，針對移動分布式網絡中的數據分發，目前已有大量的工作，如各類廣播、隨機行走、地理路由等，具體可參考文獻[20]。但是，目前的數據分發方法主要針對傳統WSN，很難應用于MLDC-WSN。例如，對于廣播操作，傳統WSN中一個節點收到數據后立即轉發，它的鄰居均可接收到數據；而在MLDC-WSN，如果節點接收到一個數據并立即轉發它，可能鄰居節點均在休眠狀態而無法接收到數據。

在MLDC-WSN中，目前常用的數據分發機制為基于分組的傳送（GT, group-based transmission）[21,22]和概率傳送（PT, probabilistic transmission）[23,24]。其中，GT是使網絡中的節點根據地理距離形成若干分組，然后在每個分組中選擇一個組長，負責將數據逐一分發給其他時刻喚醒的組內節點，而數據將通過組內的邊緣節點擴散到其他分組。但是，這種方法在移動的網絡中維持分組信息并不容易。PT是由數據發送節點根據一定的概率選擇若干個鄰居進行傳送，這些鄰居在收到數據后，將根據自己鄰居的喚醒時刻、是否接收過數據等情況，再以概率選擇若干個鄰居進行轉發，直至在規定時刻內沒有找到合適的接收者為止。概率傳送容易分布式實現，但是它的數據接收率不高，即數據分發結束后，仍然有很多節點未收到數據。

3 系統模型和問題描述

3.1 網絡模型

假設網絡中存在個節點，它們隨機分布在一個大小為′的正方形區域。節點的通信半徑為。如果2個節點之間的地理距離不大于，則它們可以相互通信。但是，網絡不一定保持隨時連通，即2個節點間不一定總是存在一條通信路徑。

節點保持隨機的運動模式。目前有多種隨機運動模型，如隨機位點模型（RWM, random waypoint model）、隨機行走模型（RW, random walk）、隨機方向模型（RDM, random direction model）等。由于RDM與現實世界當中的動物種群運動具有較高相似度[25]，適合本文研究的背景，因此本文主要采用該模型。在隨機方向模型中，節點會周期性地在以其為中心的點上，從(0, 2p)范圍內隨機選擇一個方向，然后再以固定的速度行走指定的時間長度。值得注意的是，無論采用哪種模型，均不會影響本文算法的實現和性能。本文算法可以在任何隨機運動模型上實現。

與文獻[26]和文獻[27]一樣，網絡中的數據收集按輪（round）運行。每輪有固定的時間長度，并且被分為以下3個階段。

1) 數據獲取階段。在該階段，節點處于喚醒狀態，不斷感知外部環境。如果監測到目標事件，則將監測的數據保存在自己的存儲空間。然后，廣播一個短消息通知網絡中其他節點。該階段結束時，網絡中存在個感知到數據的節點（即源節點），而網絡中每個節點均知道的大小。

2) 數據分發及存儲階段。節點進入低占空比狀態，盡可能保存自己的能量。每個源節點需要將數據以能量有效且低時延的方式分發給網絡中的其他節點，而其他節點在接收到數據時將對其進行編碼存儲。該階段是本文重點關注的階段。

3)數據收集階段。節點進入睡眠狀態，只有當移動數據收集器經過它附近并喚醒它時，它才重新啟動并發送自己的數據給數據收集器。數據發送完畢，節點又重新睡眠。該階段的時間長度遠遠大于第一和第二階段，具體由應用場景決定。在本階段，部分節點會被損壞而丟失數據。而移動數據收集器可以在任意時刻，從任意地點進入網絡并訪問仍然完好的節點。

節點進入低占空比狀態時，將自己的時間劃分為多個固定長度的周期，每個周期中包含個固定長度的時間單元（time unit）。節點隨機選擇一個時間單元喚醒，而在其他時間單元保持睡眠。由于不同的節點進入低占空比狀態的時間不一樣，它們之間的通信是異步的。由于網絡中的節點是可移動的，因此，網絡拓撲不斷在變化。此外，由于在任意時刻網絡中均有大量節點處于睡眠狀態，因此節點很難通過信息交互而獲知鄰居的情況（如數量、喚醒時間等）。

每個節點在每輪感知到的數據大小為bit，而節點的存儲空間只能保存一個數據。不同節點感知到的數據之間沒有相關性，不同的數據不能進行匯聚和融合操作。此外，節點也沒有足夠的計算能力將數據進行壓縮。如果需要保存多個數據，節點可以通過異或（XOR）操作將它們合并為一個編碼數據。

網絡中存在可靠的MAC協議如2-MAC[28]能有效處理多個節點同時給同一個目標節點發送數據時的通信沖突。

3.2 問題描述

本文研究的主要問題是給定一個具有個節點的MLDC-WSN，假設在數據獲取階段有個節點感知到了數據，則在數據分發及存儲階段，這個源節點如何以能量有效且低時延的方式，分發數據給網絡中的其他節點進行編碼存儲。本文目標是在數據收集階段，移動數據收集器只要訪問盡量少的節點，就能恢復出全部的源數據。

4 算法設計

4.1 算法的基本思想

提高數據持續性主要包括2個主要操作：數據分發和編碼存儲。因此，本文提出的分布數據存儲算法LT-MDS的基本思想如下。

1) 針對MLDC-WSN，由于節點不斷移動可能會導致網絡斷裂或部分節點無法接收到數據，提出一種新的傳染病式數據分發（IDD, infectious data dissemination）方法。IDD的基本思想是采用被動式廣播操作，即每個節點喚醒時通知其附近的轉發節點（有數據需要發送的節點），轉發節點進而判斷該節點是否接收過它的數據，如果沒有則將數據發送給該節點。被動式廣播不需要轉發節點記錄鄰居節點的情況（如喚醒的時刻），也不需要通信的同步，適合在異步的移動網絡中分發數據。

2) 在數據分發過程中，本文將有數據需要發送的節點看作感染對象（IO, infectious object），而沒有數據需要發送的節點看作易受感染的對象（SO, susceptible object）。一個SO根據自己的占空比被喚醒時，將發送一個消息通知自己的鄰居。如果鄰居中存在一個IO，則該IO判斷是否以前將數據發送給過這個SO，如果沒有則進行數據發送，否則，不做任何操作。SO接收到數據后，則被傳染，它轉變為IO并保持喚醒狀態一段時間。時間過后，IO恢復為SO，稱為康復（recover）。SO可重新進入占空比狀態。當網絡中沒有IO時，則數據分發過程結束。

3) 節點在第一次接收到一個數據時，將根據LTC進行存儲。但是，LTC要求編碼數據由個源數據產生，而節點的存儲容量有限，不可能在接收到全部源數據后再編碼存儲。因此，本文根據概率選擇需要保存的源數據。該概率由LTC及源數據的數量共同決定。

下面，將詳細介紹算法的設計與實現，并分析它的性能。

4.2 LTC簡介

RSD表示為

4.3 LT-MDS算法的詳細描述

LT-MDS是一種完全分布式的算法，在每個節點i上獨立運行。網絡中的節點將通過消息通信來完成相互之間的協作。算法的具體實現如算法1所示。

算法1 LT-MDS 算法

當數據分發及存儲階段開始時：

1) 設置v的狀態為“Susceptible”；

2) 初始化v的編碼數據y=“”；

3) 根據RSD計算d的值；

4) ifv在數據獲取階段感知到了一個源數據x

5)y= x；

6)d= d?1；

7) 設置v的狀態為“Infected”；

8)v保持喚醒；

9) 設置計時器=；

10) end if

當計時器timer倒數完成時：

1) 設置v的狀態為“Susceptible”；

2)v進入占空比工作狀態。

當v在它的工作周期中喚醒時：

發送一個短消息wakeup(v)給自己的鄰居。

當接收到一個鄰居v發送來的短消息wakeup(v)：

1) ifv的狀態為“Infected”并且v沒有發送接收到的數據x給v；

2) 發送一個消息Sensed_data(x)給v；

3) 記錄x已經被發送給v；

4) end if。

當接收到一個消息Sensed_data(x)時：

1) if (x是第一次被接收到)

2)=rand(1)；

4)y= yXORx；

5) end if

6) 設置v的狀態為“Infected”；

7)v保持喚醒；

8) 設置計時器=；

9) end if

4.4 性能分析

在隨機方向模型中，一個狀態為“Infected”的節點在時間內通信的區域如圖1所示，其中，為節點的通信半徑，為節點的速度。

圖1 “Infected”節點在t時間的通信范圍

證明 首先，推算當IDD分發數據完成時，網絡中沒有接收到數據的節點的比率為

得證。

定理3 在一個具有個節點的MLDC-WSN中，利用算法LT-MDS對個數據進行分發及存儲。如果節點的感染時間充分大，則在數據收集階段，數據采集者可以通過獲得+個編碼數據，以1?的概率恢復出全部的源數據。

從定理1可以看到，當充分大時，網絡中接收到數據的節點的比率近似于1，即幾乎全部節點接收過源數據。因此，，由此可得

即算法結束時，節點保存的編碼數據的實際代碼度非常接近于RSD。根據4.2節LTC的性質，解碼時只需要獲得+個編碼數據，就能夠以1?的概率恢復出全部的源數據，可以很容易得到結論。得證。

定理4 算法LT-MDS的時間復雜度為(1)，消息復雜度為()。

證明 由算法1的過程可以看到，在LT-MDS中沒有出現循環語句，每一步驟的執行均為算術運算。因此，算法可以在(1)時間內完成。

在算法執行過程中，一個源數據的分發需要()個節點進行轉發。每次轉發時，接收節點需要發送一個短消息，而發送節點需要發送數據，一共需要2次廣播。因此，一個源數據分發到全網，需要()次廣播。由于網絡中有個源數據，因此，一共需要()次廣播。得證。

5 模擬實驗

本文利用Matlab 7開發模擬實驗平臺。假設網絡為一個正方形區域，大小為100 m′100 m，網絡中有個隨機分布的節點。節點的工作周期=100 s，被劃分為100個時間單元，每個時間單元為1 s。節點只在其中一個隨機選擇的時間單元內醒來，而在其他時間單元則保持睡眠狀態。節點喚醒時，采用隨機方向模型進行運動，每次均從(0, 2p)范圍內隨機選擇一個方向，然后再以固定的速度=1 m/s行走一個時間單元。節點的通信半徑=25 m。節點間的通信存在MAC層機制以保證可靠性，即如果2個節點間的距離小于，則它們可以相互收到對方發送的數據分組。假設網絡中有=0.1個節點感知到了數據，即網絡中有個源節點。數據分組的大小為1 000 bit，節點發送1 bit數據的單位能耗為t=100 nJ/bit，而接收1 bit數據的單位能耗為r=50 nJ/bit。選擇目前最有代表性的分布式數據持續性方案EDFC和APBDP來和本文算法進行對比。

5.1 參數t的選擇

根據第4節的分析，參數的大小會影響數據分發過程中接收到某個數據分組的節點的數量。因此，本文分別在=100和=500的網絡中，測試數據分發結束時，不同的值對接收到數據的節點數量的影響，實驗結果如圖2所示。

圖2 t的取值對接收到數據分組的節點數量的影響

從圖2可以看到，在=100的網絡，需要≥0.6才能使超過90%的節點均能接收到數據分組。而在=500的網絡，只需要≥0.3就能使超過90%的節點均能接收到數據分組。這是因為在節點密度小的網絡中，一個受到感染的節點需要保持喚醒較長時間，才能遇到另一個未受到感染且喚醒的節點。而在節點密度大的網絡，受感染節點與未受感染節點相遇的概率較大，更容易在短時間內傳染其他節點。此外，雖然在部分網絡中，≥0.6時仍然有少部分節點無法接收到數據，但是5.3節將通過實驗證明LT-MDS仍然能取得近似最優的性能。

5.2 時延性能

本節將測試算法分發數據所需的時延，即從源節點開始分發數據，到網絡中沒有任何節點在廣播數據時的時間間隔。對于LT-MDS，選擇=0.6，這樣既能獲得較高的接收節點率（即分發過程結束時，網絡中接收到數據的節點比率），又不用節點長時間保持喚醒而耗費大量能量。分別在=100、150、200、250、300的網絡中測試算法的性能。實驗結果如圖3所示。

圖3 LT-MDS的時延性能

從圖3(a)可以看到，LT-MDS的時延略高于APBDP的時延，而遠遠低于EDFC的時延。這是因為LT-MDS中節點有可能被多次感染而延長數據分發的廣播過程。APBDP采用概率廣播來分發數據，只有少部分節點需要轉發數據，所以數據分發會較早結束。EDFC采用多個數據副本以隨機行走的方式進行分發，需要經過較大的額定步長才能完成全部過程，所以時延最大。另一方面，從圖3(b)可以看到，雖然APBDP的時延最小，但是接收到數據的節點比率是最低的，而LT-MDS擁有最高的接收節點率。因此，綜合而言，LT-MDS分發數據時具有較低的時延和較高的接收節點率。

5.3 數據持續性

為了測試算法的數據持續性（即算法運行完后，如果網絡中部分節點死亡，則移動Sink訪問部分仍然存活的節點后，全部源數據仍然能被恢復出來的概率），定義以下指標。

定義2 訪問率是指被移動Sink訪問并采集編碼數據的節點與源節點的數量比值。

本文實驗的結果是執行20次以后的平均值，即a=20。對比的結果如圖4所示。

從圖4可以看到，LT-MDS獲得的數據持續性要高于EDFC和APBDP。這是因為LT-MDS有效地完成了數據分發和編碼存儲，使最后移動Sink可以訪問數量較少的節點就能恢復出全部的源數據。而EDFC和APBDP的節點接收率較低，使節點中保存的編碼數據存在信息缺失，因此，成功解碼率較低。

6 結束語

本文對MLDC-WSN中如何有效提高數據持續性的問題進行研究。MLDC-WSN具有節點占空比低、網絡無法保持持續連通等特點，傳統的數據分發及存儲算法很難應用。為此，提出了一種分布式算法LT-MDS來解決以上問題。首先，綜合考慮MLDC-WSN網絡的特點，采用一種新的傳染病式數據分發方法來分發數據。該方法不需要任何全局信息的支持，節點只需根據接收到的鄰居信息來決定是否轉發數據，適用于節點不斷移動的動態網絡。此外，該方法可以使數據以較低的時延被網絡中絕大部分節點接收到，具有較高的可靠性。然后，基于該數據分發方法，使節點在接收到數據的同時，利用LTC對數據進行編碼存儲。理論分析和仿真實驗均表明，LT-MDS能夠以低時延完成數據分發和存儲，同時具有較高的數據持續性。

圖4 數據持續性

下一步將結合更實際的應用場景，考慮動態性更強的網絡條件，例如，鏈路存在不可靠性和嚴重沖突、網絡的節點受到外力可能突然大面積死亡等情況，研究具有更高的可靠性、更強的網絡抗毀能力并且同時具有更低時延和能耗的分布式數據分發方法。此外，還將研究滿足不同應用需求且具有低編/解碼復雜度的數據編碼保存方法，可以根據不同的優先級或時—空關系對數據進行分類存儲，使重要的數據能夠獲得更高的數據持續性。

[1] 劉偉, 劉軍. 時延敏感傳感器網絡中分布式動態資源管理研究[J]. 通信學報, 2017, 38(7): 70-77.

LIU W, LIU J. Study on distributed and dynamic resource management for delay-sensitive sensor network[J]. Journal on Communications, 2017, 38(7):70-77.

[2] CHEN L Y, GU Y, GUO S, et al. Group-based discovery in low-duty-cycle mobile sensor networks[C]//2012 9th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON). 2012: 542-550.

[3] LUBY M. LT codes[C]//The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002). 2002: 271-280.

[4] ACEDANSKI S, DEB S, MEDARD M, et al. How good is random linear coding based distributed networked storage[C]//First Workshop on Network Coding, Theory, and Applications (NetCod 2005). 2005: 1-6.

[5] KAMRA A, MISRA V, FELDMAN J, et al. Growth codes: maximizing sensor network data persistence[C]//The 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM 2006).2006: 1-12.

[6] LIN Y F, LI B C, LIANG B. Differentiated data persistence with priority random linear codes[C]//27th International Conference on Distributed Computing Systems (ICDCS 2007). 2007: 47-54.

[7] LIN Y F, LIANG B, LI B C. Geometric random linear codes in sensor networks[C]//2008 IEEE International Conference on Communications (ICC 2008).2008: 2298-2303.

[8] MATSUZONO K, ROCA V, ASAEDA H. Structured random linear codes (SRLC): bridging the gap between block and convolutional codes[C]//2014 IEEE Global Communications Conference (Globecom 2014). 2014: 1211-1217.

[9] AL-AWAMI L, HASSANEIN H. Distributed data storage systems for data survivability in wireless sensor networks using decentralized erasure codes[J]. Computer Networks, 2016, 97(3): 113-127.

[10] TALARI A, RAHNAVARD N. CStorage: decentralized compressive data storage in wireless sensor networks[J]. Ad Hoc Networks, 2016, 37(2): 475-485.

[11] LIN Y F, LIANG B, LI B. Data persistence in large-scale sensor networks with decentralized fountain codes[C]//26th IEEE International Conference on Computer Communications (INFOCOM 2007).2007: 1658-1666.

[12] KONG Z, ALY S, SOLJANIN E. Decentralized coding algorithms for distributed storage in wireless sensor networks[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(2): 261-267.

[13] LIU K K, EL-KHAMY M, LEE J. Finite-length algebraic spatially-coupled quasi-cyclic LDPC codes[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(2): 329-344.

[14] AL-AWAMI L, HASSANEIN H. Robust decentralized data storage and retrieval for wireless networks[J]. Computer Networks, 2017, 128(9): 41-50.

[15] KONB B, ZHANG G, ZHANG W, et al. Data persistence in planetary surface network using raptor codes and probabilistic broadcasting[J]. International Journal of Distributed Sensor Networks, 2016, 12(10): 1-13.

[16] AZIMI N H, GUPTA H, HOU X X, et al. Data preservation under spatial failures in sensor networks[C]//The Eleventh ACM International Symposium on Mobile Ad Hoc Networking and Ccomputing (MobiHoc 2010). 2010: 171-180.

[17] XU M, SONG W Z, HEO D, et al. ECPC: preserve downtime data persistence in disruptive sensor networks[C]//2013 IEEE 10th International Conference on Mobile Ad Hoc and Sensor Systems (MASS 2013). 2013: 281-289.

[18] 梁俊斌, 李陶深. 無線傳感網中基于自適應概率廣播的數據保存[J]. 計算機研究與發展, 2012, 49(10): 2229-2240.

LIANG J B, LI T S. An adaptive probability broadcast-based data preservation in wireless sensor networks[J]. Journal of Computer Research and Development, 2012, 49(10): 2229-2240.

[19] KONB B, ZHANG G X, ZHANG W, et al. Efficient distributed storage for space information network based on fountain codes and probabilistic broadcasting[J]. KSII Transactions on Internet and Information Systems, 2016, 10(6): 2606-2626.

[20] RUIZ P, BOUVRY P. Survey on broadcast algorithms for mobile ad hoc networks[J]. ACM Computing Surveys, 2015, 48(1): 1-35.

[21] CHEN L Y, SHU Y C, GU Y, et al. Group-based neighbor discovery in low-duty-cycle mobile sensor networks[J]. IEEE Transactions on Mobile Computing, 2016, 15(8): 1996-2009.

[22] CHEN P P, CHEN Y, GAO S, et al. Efficient group-based discovery for wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2017, 13(7): 1-12.

[23] CHAKCHOUK N. A survey on opportunistic routing in wireless communication networks[J]. IEEE Communications Surveys & Tutorials, 2015, 17(4): 2214-2241.

[24] SO J M, BYUN H J. Load-balanced opportunistic routing for duty-cycled wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2017, 16(7): 1940-1955.

[25] CAMP T, BOLENG J, DAVIES V. A survey of mobility models for ad hoc network research[J]. Wireless Communications and Mobile Computing, 2002, 2(5): 483-502.

[26] WU Y, MAO Z J, FAHMY S, et al. Constructing maximum-lifetime data-gathering forests in sensor networks[J]. IEEE/ACM Transactions on Networking, 2010, 18(5): 1571-1584.

[27] KUI X Y, ZHANG S G, WANG J X, et al. An energy-balanced clustering protocol based on dominating set for data gathering in wireless sensor networks[C]//2012 IEEE International Conference on Communications (ICC).2012: 193-197.

[28] MIAO G W, AZARI A, HWANG T W. E2-MAC: energy efficient medium access for massive M2M communications[J]. IEEE Transactions on Communications, 2016, 64(11): 4720-4735.

[29] GROENEVELT R, NAIN P, KOOLE G. The message delay in mobile ad hoc networks[J]. Performance Evaluation, 2005, 62(1-4): 210-228.

Low-latency algorithm for improving data persistencein mobile low-duty-cycle wireless sensor network

JIANG Chan1,2, LI Taoshen1,2, LIANG Junbin2

1. School of Electronic and Information Engineering, South China University of Technology, Guangzhou 510641, China 2. Guangxi Key Laboratory of Multimedia Communications and Network Technology, School of Computer and Electronics Information, Guangxi University, Nanning 530004, China

Mobile low-duty-cycle wireless sensor network (MLDC-WSN) are a kind of new ad hoc networks that are appeared in recent years. In MLDC-WSN, the nodes only have limited storage spaces. Moreover, the nodes would move or sleep from time to time. Therefore, these networks have some problems such as connectivity is hard to be maintained and data are hard to be transmitted to their destinations for storage in time. As a result, data persistence (i.e., the probability that all data can be recovered after some nodes die in the networks) is low. A distributed algorithm named LT-MDS for improving data persistence in MLDC-WSN was proposed. The algorithm used a new infectious data dissemination method to transmit the data, which enabled the data to be received by almost all the mobile nodes in a network with low latency and improved the reliability of the network. When a node receives the data, it would use LT (Luby transform) codes to encode and save them. By this way, the nodes with limited storage spaces can save more data information. Theoretical analyses and simulations show that LT-MDS can complete the process of data dissemination and preservation with low latency, and it can achieve high data persistence.

mobile low-duty-cycle wireless sensor network, data persistence, low latency, infectious data dissemination, data preservation

TP393

A

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

2017-09-15；

2018-01-21

國家自然科學基金資助項目（No.61562005, No.61762010, No.61363067）；廣西自然科學基金資助項目（No.2015GXNSFAA139286）；廣西高等學校千名中青年骨干教師培育計劃資助項目（桂教人(2017)No.49）

The National Natural Science Foundation of China (No.61562005, No.61762010, No.61363067), The Natural Science Foundation of Guangxi Zhuang Autonomous Region (No.2015GXNSFAA139286), The Cultivation Plan For Thousands of Young and Middle-Aged Backbone Teachers in Guangxi Higher Education School (Guangxi Education People (2017) No. 49)

蔣嬋（1980-），女，廣西合浦人，華南理工大學博士生，主要研究方向為無線傳感器網絡。

李陶深（1957-），男，廣西南寧人，博士，廣西大學教授，主要研究方向為分布式系統、無線網絡。

梁俊斌（1979-），男，廣西南寧人，博士，廣西大學教授，主要研究方向為無線傳感器網絡。