移动低占空比无线传感器网络中低时延的数据持续性提高算法

蒋婵，李陶深，梁俊斌



移动低占空比无线传感器网络中低时延的数据持续性提高算法

蒋婵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-），男，广西南宁人，博士，广西大学教授，主要研究方向为无线传感器网络。