基于网络编码的延迟容忍移动传感器网络低时延广播传输机制

杨奎武 郭渊博 马 骏 郑康锋

①(解放军信息工程大学电子技术学院 郑州 450004)

②(北京邮电大学网络与交换国家重点实验室信息安全中心 北京 100876)

1 引言

近年来，延迟容忍移动传感器网络(DTMSN)[1]由于其广泛的适用性和广阔的应用前景而备受关注。在DTMSN网络中，由于传感器节点的移动或休眠等原因，使得网络具有间歇连通的特点，即网络中传感器节点之间大多不存在稳定连通路径。因此，节点间的数据传输主要依靠传感器节点移动过程中的机会性连接来实现。同样，广播作为一种重要的网络数据传输方式，在DTMSN中，也必须通过节点间的机会连接来完成，这就使得传统的基于簇[2]、协商[3]、多点中继[4]的广播机制无法适用于DTMSN网络。

当前，针对DTMSN的研究主要集中在路由领域，并取得了较多研究成果[5-7]，而关于 DTMSN广播机制的研究则非常少，主要有直接传输(DT)、泛洪(flood)、k-邻居(k-neighbor)等机制。

DT是DTMSN中最基本的数据传输策略，其基本思想是节点在运动过程中只与 BS进行通信。DT可以用来实现广播数据的传输，但其实际上是利用多次单播来实现广播的目的。由于DT机制中节点只接收 BS的广播数据，因此节点通信开销非常小，但广播时延却很高。

泛洪也是一种基本的数据传输策略，与DT相反，泛洪机制中传感器节点会把自身存储的广播数据转发给所有能够与其通信的其他节点，从而达到有效降低广播延迟的目的，但由此也导致广播通信开销较大。为了降低通信开销，传染路由(epidemic)[8]等机制相继被提出，虽然这些机制能够在一定程度上降低通信开销，但也增加了广播延迟。

为了降低广播过程中的通信开销，文献[9]提出了k-邻居(k-neighbors)机制，该机制的基本思想是在只有在节点最少存在k个邻居的情况下才进行广播数据传输，从而避免了泛洪机制中向每个节点都进行数据传输所带来的通信开销，充分利用了无线信道的广播特性。k越大，通信开销越小。但由于需要有k个以上邻居节点才能进行数据的广播传输，因此广播延迟较高。

网络编码[10]作为一种提高网络吞吐量、降低网络开销的重要手段近年来受到广泛重视。基于网络编码的广播机制的研究也取得了较多的研究成果[11,12]，但目前这些成果基本上都是以静态网络为研究对象，而将网络编码应用于动态的DTMSN广播数据传输的相关研究则没有。

针对当前DTMSN广播数据传输延迟较大的问题，本文提出一种基于随机网络编码的低延迟广播传输(NBT)机制。该机制中，原始数据被分为多个批次，BS以单播的方式向每一个移动到其通信范围内的传感器节点发送需要广播的编码数据，且保证不同传感器节点接收到的同一批次的任意两个编码数据所采用的编码向量互不相关；而传感器节点之间则利用泛洪机制进行编码广播数据的交互。当传感器节点接收到足够多的同一批次的编码数据后便可以通过解码获得原始数据。仿真结果表明，NBT与现有的泛洪(flood)机制、k-邻居(k-neighbors)机制相比有着更好的广播延迟性能。

2 网络模型及知识基础

2.1 网络模型

如图1所示，假设DTMSN初始部署时，M个传感器节点随机分布在一个l×l的正方形区域A内(虚线代表节点通信半径)，基站BS位于区域中心，静止不动。节点通信半径为r，所有节点的移动都遵循Random WayPoint (RWP)[13]运动模型。

图1 DTMSN网络模型

2.2 知识基础

2.2.1随机网络编码[14]假设集合P={p1,p2,…,pl}中含有l个长度相等的待发送原始数据包，在对原始数据包进行广播发送之前，源节点每次随机选择不同的编码向量gi=(gi1,gi2,…,gil)(gij∈GF(2N),j≤l)对l个原始数据包进行编码，如式(1)所示。

当目的节点接收到任意l个编码包组成的集合C={C1,C2,…,Cl}后，若其对应的编码矩阵G={g1,g2,…,gl}各编码向量线性无关(满秩)，则可根据式(2)进行译码并恢复出原始数据集合P。

图2给出了在N,l取不同值的情况下，随机编码矩阵G满秩的概率。从图中可以看出，随着N,l的增大，编码矩阵G满秩的概率也随机增大，当取N＞5 时，目的节点在接收到l个编码包后基本上能够以接近1的概率进行译码。同样，Ho等人[15]也相应地证明，在N等于16的网络中采用随机网络编码时，目的节点可以最低以 99.6%的概率进行译码，实际应用中取N=8即可。

2.2.2节点数据相关度

定义 任意两节点i,j的数据相关度是指i,j具有的相同数据包的数量与他们全部数据包(不包括重复)数量的比，我们用ρij表示。

图2 编码矩阵满秩概率

例如，节点i有8个数据包，j有10个数据包，其中相同的数据包数量为6，则节点i,j的数据相关度为ρij=6 /(8 + 1 0 - 6)=0 .5。ρij越大，表示节点具有相同数据包的比例越高，因此能够相互交换的数据也就越少。

3 NBT广播传输机制

3.1 NBT基本原理

非编码广播机制如图3(a)所示，假设BS有a～h共8个数据需要广播，节点A,B,C在各自运动过程中由于信道等原因仅从BS分别获得了4,6,4个广播数据，即节点A携有数据a,b,c,d，节点B携有数据a,b,c,e,f,g，节点C携有数据e,f,g,h。由于网络中节点是动态的，在节点A沿图中虚线继续运动过程中，当A与B发生连接时，节点A,B都无法从对方处获得全部自身需要广播数据包，即A,B发生连接后A,B节点都因缺少数据h而无法获得全部广播数据；只有在节点A与C发生连接后，A才能将广播数据获取完整。因此在A沿虚线运动这一时段内，仅有A,C获取了全部广播数据。

采用编码广播机制时(如图3(b)),BS利用随机选取的不相关的编码向量将8个广播数据编码后发送。同样，我们假设A,B,C在各自运动过程中分别获得了4,6,4个广播数据，即节点A携有编码数据1,2,3,4，节点B携有编码数据5,6,7,8,9,10，节点C携有编码数据11,12,13,14。当节点A沿虚线继续运动过程中，当A与B发生连接时，节点A,B都能够从对方获取到自身没有的编码数据并以非常高的成功率进行译码(参见2.2.1节)，从而获得全部广播数据。在A与C发生连接后，同样C节点也能够成功译码。因此在A沿虚线运动这一时间内，A,B,C都能够以较高的概率获取全部广播数据，相比非编码机制降低了广播的延迟。

3.2 原始数据编码

BS在广播原始数据前，首先需要根据原始数据的大小将其分为若干个批次，每个批次包含长度相等的l个原始数据包。当有传感器节点移动到BS通信范围内时，BS针对每一批次的原始数据包随机选择编码向量对其进行编码，并将编码后的编码包以单播形式发送给传感器节点。BS对同一批次的数据包每进行一次编码都需要将编码包的序号加 1。需要指出的是，为了提高节点编码包的不相关度，任意两个不同序号的编码包使用的编码向量是不相关的，BS可以将选择的编码向量同历史编码向量相比较来实现这一目的。同样，BS以单播形式对编码数据进行传输也是为了降低节点间编码包的不相关度。广播包的格式及所在层次如图4所示，可以看出广播包的包头处于 MAC层之上，其中 PACK_TYPE代表报文类型(这里为广播数据包)，B_ID为本次广播的标识，BATCH_NUM 代表本次广播包含批次的数量，BATCH_NO为广播数据的批次号，CPACK_NO是编码包的序号，CODE_VECTOR为编码向量。

图3 非编码广播和编码广播机制比较图

图4 编码广播数据包格式

3.3 节点间广播数据交互

为了降低广播延迟，传感器节点之间在彼此进行编码广播数据传输时采用泛洪的机制。当任意两个传感器节点进入彼此通信范围内时，节点间首先通过交换各自的消息索引向量SV(Summary Vector)来确定自身能够提供给对方的编码数据包及其数量，然后将编码数据包发送给对方。假设a为节点i某批次所缺少编码包数量，而b为邻居节点j能够提供的该批次不同序号编码包的数量，则节点j向i传输编码包的数量为min(a,b)。实际传输中由于受到信道不确定性的影响，对丢失的广播数据包需要进行重传，NBT采用简单自动请求重传机制，最高重传次数设定为m。

向量SV格式及任意两节点间通信过程如图5(a)和5(b)所示。其中BATCH_NUM表示节点自身具有批次的数量，SV_LEN给出了该 SV的长度，BATCH_NO是批次的编号，其后的 CPACK_NUM 表示节点具有该批次编码消息的数量，而CPACK_NO则给出节点具体有该批次的哪些编码包。当传感器节点与基站BS相遇时，BS也需要根据节点提供的SV来进行广播数据的传输。

3.4 节点译码

由于节点的移动性，DTMSN中节点间保持连接的时间通常较短，为了在有限的时间内尽量多地进行数据传输，在NBT机制中节点并不是每接收到一个新的编码数据包后就试图解码，而是在获取足够多的编码数据包后才进行解码操作，具体为：节点接收到一个新的编码数据包后，首先判断该批次中自身已有的编码包数量是否达到l，如果编码包数量达到l，则提取l个编码向量并利用高斯消去法判断编码矩阵是否满秩，满秩则进行解码；否则将冗余向量对应的编码数据包删除，重新向对方请求序号为其它值的本批次编码包。

由于 NBT中序号不同的编码包采用的编码向量是不同的，因此节点只要接收到l个序号不同的编码包就能以很高的概率进行译码，这种对编码包添加序号的方法能够大大节省传感器节点的计算开销和时间，从而保证在较短的连接时间内尽量完成数据传输。我们在TI公司CC2430片上系统上设计实现了8

GF(2)上的8个数据包的编解码算法，实验得出平均编码时间为 10.8 ms，解码时间为 70.08 ms，因此可以看出 NBT完全可以用于资源受限的DTMSN当中。

图5 索引向量SV格式及通信过程

不失一般性地，我们假定Γ={(i,n)|i＞0,n＞0}为传感器节点内编码数据包所对应的批次号和编码序号二元组的集合，其中i为批次号，n为序号。代表传感器节点所包含的批次为i的各编码数据包所对应的编码向量的集合，为编码包的编码向量，C(φ)表示集合φ中元素的个数。则传感器节点在接收到某一编码向量为的编码包后译码算法如表1所示。

表1 译码算法伪码

表2 模拟实验参数

4 仿真实验及性能分析

根据表2的实验参数，本文使用 ONE(Opportunistic Networking Environment)模拟器，在RWP移动策略下，通过修改EpidemicRouter路由包仿真实现了泛洪、k-邻居(k=2),NBT 3种广播传输机制，并在网络中90%的节点收到全部广播数据包情况下，从广播数据包总量、数据包传输延时两方面对以上机制进行了比较，同时分析了不同实验参数对各种传输机制造成的影响。

仿真实验中，传感器节点运行区域A为100 m× 1 00 m的正方形区域， BS位于区域中心。由于DTMSN通常部署在信道条件比较恶劣的环境当中，因此数据通信过程中，设定节点间的数据传输成功率为0.5~0.75之间的随机值，广播重传次数为1。其他具体实验参数参见表2。所有实验结果均为100次独立运行结果的均值。

4.1 节点数据相关度

针对泛洪、k-邻居(k=2),NBT 3种广播机制，当30%,50%,70%,90%的传感器节点接收到全部广播数据包时，接收到广播数据包的节点之间平均数据相关度仿真结果如图6所示。从图中可以看出，随着接收到全部广播数据包的节点比例的提高，3种机制的数据相关度都呈增长趋势，其主要原因是越来越多的节点收到了所有的广播数据，因此相关度越来越高。而3种机制中，NBT机制的相关度最低，而其他两种方法的相关度则比较接近，这主要是由于NBT机制中BS每次都将不同的编码数据包发送给传感器节点，由此降低了节点彼此之间的数据相关度。

图6 3种广播机制节点相关度

4.2 数据完全接收条件下节点平均连接数

节点间数据相关度小，说明节点之间能够进行交换的数据数量较大，因此节点便可以经过较少的连接就接收到所有广播数据包。在表2参数条件下，通过仿真，我们给出了在完全接收到广播数据时，3种机制中每个节点所经历的平均连接数(如表3所示)。从表3我们可以看出k-邻居机制由于需要在邻居数大于2的情况下才能进行数据传输，因此连接次数最多，而NBT机制所需要的连接则最少。

表3 节点平均连接数

4.3 3种机制性能比较分析

在表2给定的默认参数条件下，当90%节点收到全部广播数据包时，3种广播机制的具体性能见表4。从表中可以看出NBT机制的传输时延最低，只有72.1 s，其次是泛洪机制，为79.2 s，广播延迟降低接近 10%；由于k-邻居(k.=2)机制只有在节点有2个以上邻居的情况下才能进行数据传输，因此传输时延较长。NBT广播时延较低的主要原因是节点中编码数据的相关度较低，节点可以用更少的连接次数便可获取全部广播数据。另外，从通信开销的角度来看，NBT和泛洪机制的广播数据包总量基本相同，开销较大，其主要原因在于二者都采用泛洪机制进行数据传输；而k-邻居机制利用信道的广播特性节省了开销。这里需要指出的是在k-邻居机制中，当k=1时，该机制同泛洪机制相同，k越大广播延迟越高。

4.4 节点密度对性能的影响

图7(a),7(b)分别给出了在节点密度变化条件下，3种机制的广播时延和广播数据量的仿真结果。从图7(a)中我们可以看出，随着节点数量的增多，节点间连接发生的时间间隔也随之降低，因此3种机制的广播时延都呈下降趋势，其中NBT机制时延最小，k-邻居(k=2)机制时延最大。而由于节点数量的增多，需要传输的广播数据包的数量也相应增加，因此从图7(b)中可以看出，广播数据量与节点数量基本呈线性增长的关系，其中k-邻居机制的通信开销最小，NBT机制小于泛洪机制，开销较大。

表4 默认参数下仿真性能

4.5 节点速度对性能的影响

图8(a),8(b)分别给出了在RWP模型中节点最大运行速度变化条件下，3种机制的广播时延和广播数据量的仿真结果。由于在节点密度不变的条件下，节点移动速度越快，同等时间内节点移动所覆盖的区域越大，也就能够与更多节点产生连接，从而降低了广播时延。因此从图8(a)中可以看出，3种机制随着速度的增大，广播时延是逐渐降低的，其中NBT机制的时延最小。而由于节点数量基本不变，因此需要广播的数据包总量也不变，因此3种机制广播数据量在节点速度变化的情况基本平稳，起伏不大，如图8(b)所示。

4.6 节点通信半径对性能的影响

图9(a),9(b)分别给出了在节点通信半径变化条件下，3种机制的广播时延和广播数据量的仿真结果。由于节点通信半径的增加，节点通信半径覆盖范围内其他节点出现的概率也将随之增加，因此节点间能够进行数据交换的机会也将变大，从而降低了广播时延。因此图9(a)中3种机制的广播时延随着通信半径的增加都呈下降趋势，其中k-邻居 (k=2)广播时延下降最快，而NBT时延最小。由于泛洪、NBT机制采用泛洪进行数据通信，因此节点数量不变的情况下广播数据量也基本不变；而k-邻居机制由于通信半径的增加提高广播机会，通信量呈下降趋势，具体如图9(b)所示。

4.7 参数l对性能的影响

NBT机制中参数l代表每一批次当中包含的原始数据包数量，也就是每次参与编码的原始数据包数量。在表2实验参数条件下，l也代表需要广播的原始数据包的数量。从图10(a)中可以看出，随着l的增大，3种机制的广播时延呈现缓慢上升趋势，升幅不大，说明在广播数量较小，通信带宽足够的情况下，3种机制的广播时延主要取决于节点间连接发生的时间间隔。从图10(b)中可以看出，随着l的增大，也即需要广播的原始数据的增加，广播数据量也基本呈线性增长的趋势，符合实际情况。

图7 节点数量变化对广播时延和广播数据量的影响

图8 节点速度变化对广播时延和广播数据量的影响

图9 通信半径变化对广播时延和广播数据量的影响

图10 参数l变化对广播时延和广播数据量的影响

5 结束语

本文提出的基于网络编码的低时延广播传输机制NBT，能够较好的完成DTMSN数据的广播传输功能。其主要贡献有：(1)首次将随机网络编码引入到DTMSN广播通信当中，使得在拓扑结构时变的网络中也能应用网络编码技术，拓展了网络编码的应用领域。(2)通过BS对相同原始数据包的多次随机编码来降低广播数据相关度，从而降低了数据广播过程中所需要的平均连接次数，提高了广播时延性能。(3)在广播通信开销基本相同的前提下，找到一种比泛洪机制具有更好时延性能的广播传输机制。

虽然NBT机制有着较好的广播时延性能，但该机制也存在着广播开销较大的缺点，这也是我们下一步研究过程中将着重解决的问题。

[1]Leguay J,Friedman T,and Conan V.DTN routing in a mobility pattern space[C].In ACM Workshop on Delay Tolerant Networking and Related Topics (SIGCOMM 2005),New York,NY,USA,2005: 276-283.

[2]Cheng L,Das S K,Di Francesco M,et al..Scalable and energy-efficient broadcasting in multi-hop cluster-based wireless sensor network[C].The 2011 IEEE International Conference on Communications (ICC 2011),Kyoto,Japan,2011: 1-5.

[3]Huang T,Lin Y,and Tang L.Neighbor-aware gossip-based broadcasting scheme for wireless sensor networks[C].2010 International Conference on Communications and Mobile Computing,Shenzhen,China,2010: 293-297.

[4]Montolio-Aranda P,García-Alfaro J,and Megías D.Improved flooding of broadcast messages using extended multipoint relaying[J].JNetwork and Computer Applications,2011,34(2): 542-550.

[5]Wang Y and Wu H.Delay/Fault-tolerant mobile sensor network (DFT-MSN): a new paradigm for pervasive information gathering[J].IEEE Transactions on Mobile Computing,2006,6(8): 1021-1034.

[6]Xu X,Luo J,and Zhang Q.Delay tolerant event collection in sensor networks with mobile sink[C].In 2010 Proceedings IEEE INFOCOM,San Diego,California,USA,2010: 1-9.

[7]Talipov E and Cha H.Communication capacity-based message exchange mechanism for delay-tolerant networks[J].Computer Network,2011,55(15): 3408-3422.

[8]Vahdat A and Becker D.Epidemic routing for partially connected Ad hoc networks[R].Technical Report CS-200006,Duke University,Apr.2000.

[9]Goundan A,Coe E,and Raghavendra C.Efficient Broadcasting in Delay Tolerant Networks[C].Proc.GLOBECOM,New Orleans,Louisiana,USA,2008: 523-527.

[10]Ahlswede R,Cai N,Li S Y R,et al..Network information flow[J].IEEE Transactions on Information Theory,2000,46(4): 1204-1216.

[11]Fragouli C,Widmer J,and Boudec J L.Efficient broadcasting using network coding[J].Presented at IEEE/ACM Transactions on Networking,2008,16(2): 450-463.

[12]Widmer J and Boudec J L.Network coding for efficient communication in extreme networks[C].In Proceedings of the ACM SIGCOMM Workshop on Delay-Tolerant Networking,Philadelphia,PA,USA,2005: 284-291.

[13]Bettstetter C,Hartenstein H,and Prez-Costa X.Stochastic properties of Random Waypoint mobility model[J].Wireless Networks,2004,10(5): 555-567.

[14]Ho T,Koetter R,Médard M,et al..The benefits of coding over routing in a randomized setting[C].Proceedings of IEEE International Symposium on Information Theory,Yokohama,Japan,2003: 442-447.

[15]Ho T,Médard M,Shi J,et al..On randomized network coding[C].41st Annual Allerton Conference on Communication Control and Computing,Monticello,IL,USA,2003: 11-20.