蔣嬋，李陶深，梁俊斌

?

移動低占空比無線傳感器網(wǎng)絡中低時延的數(shù)據(jù)持續(xù)性提高算法

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

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

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

移動低占空比無線傳感器網(wǎng)絡；數(shù)據(jù)持續(xù)性；低時延；傳染病式數(shù)據(jù)分發(fā)；數(shù)據(jù)存儲

1 引言

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

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

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

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

2 相關工作

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

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

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

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

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

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

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

3 系統(tǒng)模型和問題描述

3.1 網(wǎng)絡模型

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

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

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

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

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

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

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

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

網(wǎng)絡中存在可靠的MAC協(xié)議如2-MAC[28]能有效處理多個節(jié)點同時給同一個目標節(jié)點發(fā)送數(shù)據(jù)時的通信沖突。

3.2 問題描述

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

4 算法設計

4.1 算法的基本思想

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

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

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

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

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

4.2 LTC簡介

RSD表示為

4.3 LT-MDS算法的詳細描述

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

算法1 LT-MDS 算法

當數(shù)據(jù)分發(fā)及存儲階段開始時：

1) 設置v的狀態(tài)為“Susceptible”；

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

3) 根據(jù)RSD計算d的值；

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

5)y= x；

6)d= d?1；

7) 設置v的狀態(tài)為“Infected”；

8)v保持喚醒；

9) 設置計時器=；

10) end if

當計時器timer倒數(shù)完成時：

1) 設置v的狀態(tài)為“Susceptible”；

2)v進入占空比工作狀態(tài)。

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

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

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

1) ifv的狀態(tài)為“Infected”并且v沒有發(fā)送接收到的數(shù)據(jù)x給v；

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

3) 記錄x已經(jīng)被發(fā)送給v；

4) end if。

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

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

2)=rand(1)；

4)y= yXORx；

5) end if

6) 設置v的狀態(tài)為“Infected”；

7)v保持喚醒；

8) 設置計時器=；

9) end if

4.4 性能分析

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

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

證明 首先，推算當IDD分發(fā)數(shù)據(jù)完成時，網(wǎng)絡中沒有接收到數(shù)據(jù)的節(jié)點的比率為

得證。

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

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

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

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

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

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

5 模擬實驗

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

5.1 參數(shù)t的選擇

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

圖2 t的取值對接收到數(shù)據(jù)分組的節(jié)點數(shù)量的影響

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

5.2 時延性能

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

圖3 LT-MDS的時延性能

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

5.3 數(shù)據(jù)持續(xù)性

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

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

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

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

6 結束語

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

圖4 數(shù)據(jù)持續(xù)性

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

[1] 劉偉, 劉軍. 時延敏感傳感器網(wǎng)絡中分布式動態(tài)資源管理研究[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] 梁俊斌, 李陶深. 無線傳感網(wǎng)中基于自適應概率廣播的數(shù)據(jù)保存[J]. 計算機研究與發(fā)展, 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-），女，廣西合浦人，華南理工大學博士生，主要研究方向為無線傳感器網(wǎng)絡。

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

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