DTMSN中基于效用和网络编码的数据传输

周浩慧

（长沙商贸旅游职业技术学院 信息系，湖南 长沙 410004）

0 引言

随着计算机技术和通信技术的快速发展，通信网络与人们的生活联系越来越紧密。为了满足人们对网络应用多元化的需求，近年来出现了很多满足特殊应用的网络，无线传感器网络就是其中的一种。无线传感器网络是能在任何时间、任何地点、任何环境下快速组网并完成一定感知任务的无线自组织网络，如车载传感器网络、气象监测传感器网络、移动水下设备传感器网络以及森林环境监测传感器网络。

然而在一些特殊的环境下应用无线传感器网络时，由于某些原因，网络大部分时间是不连通的，传统的无线传感器网络要求通信的2个节点之间至少存在1条完整的路径，这种特殊的无线传感器网络是通过节点的移动带来的相遇机会实现通信，称之为延迟容忍移动无线传感器网络（Delay Tolerant Mobile Sensor Networks，DTMSN）[1]。随着DTMSN在实际的应用增多，越来越多的研究人员投入到DTMSN的研究中，而且在DTMSN数据传输的研究上取得了一些成果，但仍然不能满足在特殊环境中应用的需求，笔者在DTMSN中引入网络编码[2]，主要研究在DTMSN的数据传输中使用网络编码来优化DTMSN的传输性能。

1 DTMSN和网络编码

1.1 DTMSN

DTMSN由2种节点组成：传感器节点和汇聚节点（Sink），传感器节点放置在随机运动体上并形成一个间歇性连通利用节点移动实现通信的无线传感器网络，汇聚节点是放置在某固定位置或运动体上用来收集数据的超级节点，是所有源传感器节点数据回传的终点。一方面，DTMSN具有传统无线传感器网络[3]的很多特性，如传感器节点的传输距离短、计算能力弱、存储空间和能源非常有限等。另一方面，与传统无线传感器网络相比，DTMSN又具有如下特性：1）随机移动的节点。由于传感器节点或Sink节点是放在随机运动体上，节点的随机运动导致网络的拓扑是动态变化的。2）连通间歇性。DTMSN的连通性比较差，网络中的一些节点之间的连通是偶尔的。3）延迟容忍。DTMSN中数据传输的延迟很高，在使用时要能够容忍延迟。4）较差的可靠性。DTMSN中数据的传输成功率较低，数据交付的可靠性比较差。

目前DTMSN还没有一个比较统一的定义，笔者参照现有一些文献分析DTMSN的特点，给出一个描述性定义：DTMSN是一种不需要传感器节点和汇聚节点之间存在完整链路，利用节点移动带来的相遇机会，实现广泛数据收集的新型无线传感器网络。DTMSN的路由模式是“存储—携带—转发”。图1是DTMSN示意图，t1时刻源传感器节点1希望将数据传输给固定位置的Sink节点，但节点1和Sink节点间没有一条完整的通信链路，因此，1将数据发送给邻居节点2，2再将数据转发给3，由于3没有合适的下一跳可转发，它将数据在本地存储并等待传输机会，过一段时间到达t2时刻，通过运动节点3和节点6相遇，3将存储的数据转发给6，t3时刻，6将数据传输给Sink节点，完成数据传输。

1.2 网络编码

网络编码理论[4]作为21世纪初信息论领域中一大重要突破，是由香港中文大学的Ahlswede等人提出，该理论改变传统中间节点对输入的信息流只进行转发的模式，通过允许中间节点对输入信息流在转发前进行编码，并保证接收节点能正确地恢复源节点所发送的信息，从而达到网络通信的最大容量，最大限度地利用网络现有的资源。网络编码最初是为有线网络而提出的，但经过大量研究却发现无线网络中链路的不可靠性和物理广播特性非常适合网络编码。因此，网络编码被应用去解决各种无线网络问题，并且取得了一定的成果，DTMSN作为无线网络的一种同样适合网络编码。

图2是简单的网络编码示意图，假设每条链路的容量为每单位时间1 bit，源节点S向目标节点D1和D2同时发送2 bit信息a和b。图2a采用传统的组播技术，节点S把信息a和b分别发送给1和2，节点1和2将收到的数据再转发给其他节点。节点1直接得到a，节点2直接得到b。当a和b到达节点3要进行转发时，由于节点3和4之间只有1条链路且链路的容量为1 bit，因此信息a或b必须在节点3处排队等候1个单位时间。如此一来，这2个目标节点在单位时间内接收到的信息为1.5 bit。图2b使用网络编码，中间节点3将收到的信息a和b进行编码，得到a⊕b，然后将编码后的信息转发出去。目标节点D1接收到信息a和编码后的信息a⊕b，通过运算解码出b。同样，在目标节点D2上也通过运算解码出a。这样这2个目标节点在单位时间内接收到的信息接近2 bit。

图2 2种信息处理方式示意图

网络编码作为信息论和网络技术的融合，在提高网络吞吐量、节约能耗、增强可靠性和安全性等方面表现突出，但同时也增加了节点的计算开销。由于近几十年计算机技术的快速发展，现在网络传输的瓶颈不是计算量而是网络带宽和服务质量。网络编码的核心就是利用计算机强大的计算能力换取在网络带宽方面的提高以及安全性和可靠性方面的增强。

2 基于效用和网络编码的数据传输

在DTMSN中加入其他技术和设计出适合的数据传输策略来提高DTMSN的性能，已经成为DTMSN研究中的重要内容。基于网络编码的数据传输是将待传输的数据通过某种编码方法编码成相互冗余的数据消息，目的节点只要收到一定数量编码后的数据消息就可以通过运算恢复出原数据。基于复制的数据传输是在网络中注入大量冗余信息，提高了数据传输的成功率，但却加大了整个网络的负担。基于效用的数据传输能在一定程度上避免节点之间数据转发的盲目性，减少数据传输次数，提高数据传输成功率，可是却加重了部分节点的负担，造成了某些链路的严重拥塞。而基于效用和网络编码的数据传输能在提高数据传输成功率的同时很好地均衡网络开销，有效减少数据传输次数和传输延迟，最终实现DTMSN性能的最大化。

2.1 SF数据传输策略

Spray and Focus（SF）[5]是一种基于效用的数据传输策略，该策略改进了基于复制的Spray and Wait（SW）[6]数据传输策略的Wait阶段。SF分为Spray和Focus 2个阶段，在Spray阶段，源节点生成1个数据后产生该数据的L（L＞1）份副本，使用某种分发策略将这L份副本分发给其他没有缓存该数据的中继节点，当分发任务完成后，节点进入Focus阶段，在Focus阶段，每个节点都与其相遇的节点维持1个效用值，这样网络中的数据不断从效用值较低的节点经“存储—携带—转发”传送到效用值高的节点，直到与目标节点相遇完成数据的传输。假如节点的效用值在网络中分布适当，SF可在很大程度上提高网络的传输性能。

2.2 SF-NC数据传输策略

1）定义1[7]

平均连接频率（ACF）fi,j是指节点i和节点j在单位时间内联系的次数，公式为

式中：T指预先定义的固定时长，Ni,j是指在T时间内节点i和j联系的次数。

2）定义2[8]

Ci是指节点i在一段时间内与网路内其他节点的连接次数不小于1的节点数，公式为

式中：N是网络中的节点数，T指预先定义的固定时长，如果在T时间段内Ni,j不小于1，那么ET(i,j)=1，否则ET(i,j)=0。

2.2.1 策略描述

在DTMSN中，假设每个节点都有1个唯一的ID且每个节点都与其相遇的节点维持1个C值并与Sink节点维持1个ACF值，每T时间内更新节点的ACF值和C值。SF-NC中的Spray阶段采用C-Binary分发策略，该分发策略改进了SF中Spray阶段副本扩散的局部性弊端，并且为网络编码提供了好的编码环境，源传感器节点生成1个数据后产生该数据的L（L＞1）份副本，使用交换机制分发给未缓存该数据的中继节点，在分发过程中，当遇到未缓存该数据的节点时，就将数据的1份副本给它，然后这2个节点按一定比例来分配当前剩余副本的分发任务，这个比例就是这2个节点C的比值，C-Binary分发策略能很好地将同一个数据的副本在网络中扩散开。当分发任务完成后，节点进入Focus阶段，在Focus阶段使用网络编码，采用以下2个机制触发编码器：1）缓存队列满时。2）遇到比自己ACF值高的节点要转发数据时。中间节点将编码后的数据消息广播，只有ACF值比该节点ACF大的节点才接收此数据消息，并放入缓存队列中等待，Sink节点的ACF值可看成是无穷大，T可根据网络的实际情况来设定。

2.2.2 策略中数据消息在节点的处理过程

随机线性网络编码[9-11]是指每个消息都对应1个在有限域中随机选取的编码系数，这些消息和其对应的编码系数通过加和乘运算组成线性组合的一种编码方法。策略使用离散时间模型[12]，把在源传感器节点的数据产生分成离散的时间段，这里称时间段为“代”，每“代”产生的数据有1个相同的标识，只有拥有相同标识的数据才能进行编码。每个节点都将收到的相同标识的信息向量和对应的编码向量放在1个解码矩阵中存储。Sink节点按“代”将收到的数据消息分别放入解码矩阵中，当单个信息向量包含的源数据个数等于解码矩阵的秩时，能解码出对应的源数据。例如，中间节点A，B1，B2，…，Bn，目的节点为Sink节点，则fA表示节点A的ACF值，GAr表示节点A的r代解码矩阵，fBi表示节点Bi的ACF值表示节点Bi的r代解码矩阵。(gAr(t),yAr(t))表示A节点在t时刻发出的编码向量和信息向量的元组，GAr(t)表示节点A在t时刻r代的解码矩阵，Rr(t)是1个在有限域中随机取的不为0的系数向量。假设则算法为：

1）在t时刻，假如节点A满足以上2种触发机制中的任何一种就触发编码器进行编码，得到

假如是第1种机制触发，编码后再存储，假如是第2种机制触发，就转发元组(gAr(t),yAr(t))。

2）假如不能触发编码器，则再等待t1时间，即t+=wait(t1)，返回 1）。Bi节点收到(gAr(t),yAr(t))后将其插到自己的解码矩阵GBir中，如果插入后增加了解码矩阵的秩就存储，否则忽略。为快速解码源数据，一般使用高斯消元法让解码矩阵保持简化形式。

3 仿真和性能分析

使用NS2进行仿真，仿真环境为：将60个传感器节点放在60个运动体上，然后在1个3 000 m×3 000 m的区域内随机部署，1个Sink节点固定在1 500 m×1 500 m处，每个节点的通信范围是80 m，在其中选5个节点作为源传感器节点向Sink节点发送信息，源传感器节点和Sink节点之间几乎不存在完整的链路，传感器节点的移动模型为Random-Waypoint，设定SF-NC算法中随机线性网络编码的编码向量是基于有限域GF（28）。

笔者模拟实现了SF-NC，FAD和泛洪算法，分别将它们在传感器节点不同移动速度和不同存储队列长度下，对数据的传输成功率和平均传输时间进行比较。仿真结果如图3和图4所示。

在DTMSN实际环境中，为了提高数据传输的成功率，不得不向网络中注入大量冗余信息，因此网络相对比较繁忙，网络越繁忙传感器节点存储受限问题就越突出，但此却非常适合进行网络编码，使用网络编码经1次编码就可以完成多次发送任务，而基于效用值的传输能很好地控制副本的数量。这样就很大程度上缓解了节点存储受限问题，而且大大提高了传输效率，减轻了网络的负荷，减少了节点的能量消耗，缩短了数据传输的时延。

可以看到SF-NC数据传输策略能以较低的数据传输延迟获得较高的数据传输成功率。由于该策略能有效利用局部连通机会，通过网络编码使节点间以最有效的方式传输数据，减轻网络的拥塞，节省传感器节点的存储空间，让节点存储的数据能在有限的相遇时间内以最快的方式转发出去。这样既减少了传输次数，又充分利用了节点间难得的相遇机会，当节点的ACF值在网络中分布适当并且L的值适合时，SF-NC能极大地提高DTMSN的传输性能。

4 小结

笔者把网络编码引入到DTMSN中，结合基于效用的SF数据传输策略，设计出了SF-NC数据传输策略，相比DTMSN中现有的几种数据传输策略，在整体性能上有很大的提升。网络编码作为通信领域的重大突破，随着对网络编码研究的不断深入，将给无线网络的发展带来革命性的变化，DTMSN作为一种新型的无线自组织网络，把它与网络编码结合对DTMSN的发展将产生具有深远意义的影响。下一步将更加深入地研究网络编码在DTMSN中的应用。

[1]WANG Yu，LIN Feng，WU Hongyi.Efficient data transmission in delay fault tolerant mobile sensor networks（DFT-MSN）[EB/OL].[2010-12-20].http：//www.ieee-icnp.org/2005/Posters/Wang.pdf.

[2]罗峰.基于网络编码的P2P网络系统研究[J].电视技术，2007，31（2）：60-63.

[3]孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005：4-57.

[4]AHLSWEDE R，CAI N，LI S Y R，et a1.Network information flow[J].IEEE Trans.Information Theory，2000，46（4）：1204-1216.

[5]SPYROPOULOS T，PSOUNIS K，RAGHAVENDRA C S.Spray and Focus：efficient mobility-assisted routing for heterogeneous and correlated mobility[EB/OL].[2010-12-20].http：//citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.5674＆rep=rep1＆type=pdf.

[6]SPYROPOULOS T，PSOUNIS K，RAGHAVENDRA C S.Spray and Wait：an efficient routing scheme for intermittently connected mobile networks[EB/OL].[2010-12-20].http：//conferences.sigcomm.org/sigcomm/2005/paper-SpyPso.pdf.

[7]WANG Yong，JAIN S，MARTONOSI M，et al.Erasure-coding based routing for opportunistic networks[EB/OL].[2010-12-20].http：//citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.364＆rep=rep1＆type=pdf.

[8]王建新，朱敬，刘耀.基于副本限制和社会性的延迟容忍网络路由算法[J].华南理工大学学报：自然科学版，2009（5）：84-89.

[9]HO T，MEDARD M，KOETTER R，et al.A random linear network coding approach to multicast[J].IEEE Trans.Information Theory，2006，52（10）：4413-4430.

[10]LI S Y R，YEUNG R W，CAI Ning.Linear network coding[J].IEEE Trans.Information Theory，2003，49（2）：371-381.

[11]WANG D，ZHANG Q，LIU J.Partial network coding：concept，performance，and application for continuous data collection in sensor networks[EB/OL].[2010-12-20].http：//www4.comp.polyu.edu.hk/～csdwang/Publication/TOSN-PNC.pdf.

[12]WIDMER J，BOUDEC J L.Network coding for efficient communication in extreme networks[EB/OL].[2010-12-20].http：//citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.5368＆rep=rep1＆type=pdf.