基于LT码数据分发协议性能分析

收稿日期：2013-09-17

作者简介：张亚昕（1978―），女，河南新郑人，讲师，硕士，研究方向：数据挖掘，无线传感网络。

文章编号：1003-6199(2014)02-0141-04

摘 要：无线传感网络节点数目庞大，能量消耗大，传感器节点的计算和存储能力有限，网络丢包率较为严重。为了设计节能可靠的网络协议，降低节点的能耗，在TinyOS网络平台上设计实现了基于lt码的数据分发协议，在仿真环境TOSSIM上进行了性能分析，仿真结果表明，基于LT码的数据分发协议，更好的展示了LT码的无比率特性，提高了网络数据传输的可靠性，降低的网络负载。

关键词：LT码；分发协议；无线传感网络

中图分类号：TP391文献标识码：A

お

Based on the Analysis of LT Codes Performance Data Distribution Agreement

お

ZHANG Yaxink，LIU Hua

(Xi'an Railway Vocational and Technical College Department of electronic information，Xi'an,Shannxi 710014，China)

Abstract:wireless sensor network node number, energy consumption, limited computing and storage capacity of sensor nodes, network packet loss rate is more serious. In order to design of energy saving and reliable network protocol, reduce the energy consumption of nodes in TinyOS network platform design has realized the data distribution agreement based on LT codes, the performance analysis on the simulation environment TOSSIM, simulation results show that based on the data distribution agreement LT codes, better shows no ratio characteristics of LT codes, to improve the reliability of the network data transmission, reduce the network load.

Key words:LT codes;distribution agreement;wireless sensor network

1 引 言

近年来随着无线传感网络飞速发展，其应用范围也逐渐从军事应用推广到工业，医疗、农业、环境监测等领域［1］。由于无线传感器网络的节点数目庞大,通讯能力较弱,并且传感器节点的计算和存储能力有限，使得网络的丢包率较为严重,一般会达到10%甚至更高。因此为网络提供可靠的传输和存储机制成为了无线传感网络的一个基本问题。

比较简单的方法就是多次发送数据包，但这样发包的数量会大大增加，并且也不能保证数据传输的可靠性，同时还增加了网络的能耗。另一种方法是采用请求重传，即发送端发出的数据包丢失，接收端就会向发送端请求重新发送未接收到的数据包，若数据包再次丢失，发送端还要再次发送。在无线传感网络多使用广播方式，该方法会增加网络负载和传输延迟，如果丢包率稍大，大量的处罚数据包将可能造成整个网络的瘫痪。还有一种文献［2］提出了使用范德蒙德矩阵构造RS纠删码［3］来提高数据的可靠传输,但纠删码运算复杂度较高。喷泉码(Fountain Codes)［4-6］是一种无比率码。一般来说，喷泉码是指原始数据分组像喷泉一样生成任意数量的编码分组 ，接收端只要收到足够多任意组合的编码分组，就可以通过译码以高概率成功恢复全部原始数据分组。这种性质使得它能够在信道多变情况下进行数据传输，几乎不受信道删除率的影响［7-8］。

2 LT编译码原理

2.1 LT编码

假设编码器要编码的数据文件被分为k个数据分组s1,s2,…,sk，编码后生成的编码分组为t1,t2,….tn。当接收端收到一定数量的输出数据后，就可以通过译码以高概率成功恢复全部原始数据分组。LT编码过程如下（如图1）：

ね1 LT编码示意图

1)按照度分布函数为每一个编码分组随机选取一个度d(d

SymbolcB@

k)，d的选择由度概率分布函数ρ(d)决定;

2) 从k个原始数据分组中，等概地随机选择不同的d个;

3) 将这d个原始数据分组进行异或运算，即得到一个编分组;

重复步骤1)、2)、3)即可源源不断地产生编码分组。

显然LT码编码的前提是随机度d的选择，而度概率 ρ(d)是度分布函数设计的关键。既要保证编码器输出的任何一个编码分组sk参与了编码；又要尽量使编码和译码过程异或的次数较少，保证译码能够开始并持续下去。Luby在文献［4］中提出理想孤波分布(Ideal Solition Distribution)，定义为：

ρ(d)=1kd=11d(d－1),d=2,3,…k(1)

对于这种度分布k个编码分组的度的平均度值近似为ln k。但是，由于理想孤波分布度值选取是随机的，造成在实际应用中很不稳定，稍有波动就可能导致在译码时在某些点没有度为1编码分组出现，造成译码失败。为了提高译码成功率，Luby在理想孤波分布之上进行了改进，提出了鲁棒孤波分布(Robust Soliton distribution，RSD)：

τ(d)=sk1d d=1,2,3,…(k/s)－1sklog (s/δ)d=k/s0d＞k/s(2)

将理想孤波分布ρ(•)与τ(•)相加，得到改进后的度概率密度分布函数μ(d)：

μ(d)=ρ(d)+τ(d)Z (3)

计算技术与自动化2014年6月

第33卷第2期张亚昕等：基于LT码数据分发协议性能分析

其中c为大于0的常数，取值范围为0,1，δ为译码失败的概率。s=c•ln (k/δ)k表示编码分组度为1的数目。

2.2 LT译码

开始时原始数据分组均未恢复，当接收端收到一定数量的编码分组后开始译码。译码器在每一步都利用部分已经译码的数据在剩余的数据中解出一部分新的源数据,如此不断的反复迭代直到所有的数据都被恢复出来。译码过程如下：

1）根据已有的原始数据和编码分组的对应关系建立双向图；

2）任意选取一个度为1的编码分组，如果存在,即可恢复与其相连的原始数据，并将该编码分组从双向图中移除;如果不存在,则译码停止；

3）对已恢复的数据,将其从其他参与异或的编码分组中移除，从而使输出数据的的度减1；

4）重复步骤2）和3）,直至所有数据都被恢复,则译码成功；否则,译码失败,需接收更多的编码分组才能继续译码。

3 LT码数据分发协议的设计

在分析了LT码编译原理后，可知LT码数据包的数量一般不受限制，但为了进行LT编码数据包数量、数据包号、每个包对应的度需要知道。数据包结构一般包括四部分：Head、Data、Footer、Dataelement。其中Data是主要部分，最大长度为29个字节，如果接收方不知道发包数量和码率,Data还要设置原始数据包数(Sour-num)和编码后的数据包数(Codenum)。其余三部分与硬件相关。LT传输数据包结构如图2所示：

ね2 LT码的数据包结构图オ

由于LT码的码率无关性，发送端产生的编码序列可以是无限的，接收端只要收到足够的编码分组就可以恢复全部原始数据，不需要关心中间节点之间的链路关系。一般为了减少能量消耗，缩短传输延迟，接收端只要成功译码，发送端将停止编码。图3是LT码数据分发协议编解码的具体过程:

Notations:

rec_pkt:receive queueε:decoding inefficiency factor

Information Dissemination Protocol Based LT Erasure Codes

Upon entering Encode Phase

if (TOS_NODE_ID == Sender) then

call Encode() and Send()

end if

Upon entering Forward Phase

if(TOS_NODE_ID != Sender

&& TOS_NODE_ID != Receiver) then

call Forward()

end if

Upon entering Decode Phase

if(TOS_NODE_ID ==Receiver) then

if( len(receive_packet) >=(1 +ε)*k) then

call Decode()and flush rec_pkt

else

Store the message in rec_pkt

end if

end if

/*The following is for Encode*/

Encode()

See encoding process of LT codes in section 2

Decode()

See decoding process of LT codes in section 2

图3 LT码数据分发协议オ

其中Forward()的设计是关键，最容易实现的方法就是泛洪法，发送方不断重复发送数据包，满足不同的网络丢包率，接收方也以同样的方式转发数据包。但该方法会增加网络负载，因此设计尽量减少数据包的发送次数。但是对路由协议的效果不是很明显。

4 性能仿真与分析

仿真实验环境采用TOSSIM［9］，数据分发协议是在TinyOS［10］平台上实现的。在TOSSIM中可以设置无线传感器网络中每条链路的信噪比，用来模拟真实的无线传感器网络链路通信，TOSSIM提供的噪声源来自真实噪声，使仿真更接近现实。本文用来模拟的无线传感网络图（如图4）是随机生成的，其中0节点用于分发数据，其余63个是转发数据节点，接收端在收到编码数据包后，首先检查是否收到该包，若没有收到则以相同的方式转发，否则直接丢弃。接收端在收到数据包后，由于没有相应的应答方式，故是否停止发送数据包完全由接收方控制。

ね4 模拟无线传感器网络图オ

图5所示，LT编码数据包数对译码性能的影响。从图中可以看到数据包数k为10000译码成功率比k为100时要高，所以只有数据包数量达到一定程度时，LT译码才能达到良好的性能，满足一定的统计规律。

ね5 数据包数对LT译码性能的影响オ

图6所示发送数据包数为100的单跳网络中，LT码与RS纠删码的时间比较曲线。从图中可见LT编解码所需时间略长于RS码，但RS码是有比率码，编解码基于矩阵的有限域运算，数据量大时需将数据分块编码发送，运算复杂度较高，突发事件时不能实时的改变码率，LT码则能适应信道多变的情况，不受信道删除率的影响。

图7中给出了发送数据包数为100，网络丢包率为25%，LT码与RS纠删码的收包率比较曲线。从图可见RS码实际发送数据包数大于接收到的编码包数时，由于编码数据矩阵的不可逆性，因此解码出的包数为0，收包率为0。只有发送数据包数小于接收到的包数时，RS码才能解码成功。LT码中随着发送数据报数的增收包率也会随之增加，只要接收端收到足够多的编码分分组就能成功译码，且不受网络好坏的影响。

ね6 LT码的编解码时间比较曲线オ

ね7 LT码和RS码的收包率比较曲线オ

5 结 论

本文研究了LT码编译码原理，在TinyOS网络操作平台上设计并实现了在无线传感网络基于LT码的数据分发协议。在单跳网络中通过TOSSIM仿真实验，比较了LT码与RS码的编解码时间和包接受率。仿真结果表明，RS码运算复杂度高，需要将数据分块编码发送，突发事件不能实时改变码率。而基于LT码的数据分发协议，更好的展示了LT码的无比率特性，提高了网络数据传输的可靠性。

参考文献

［1］ SONG W,WANG B,ZHOU Y B. Technology and application of wireless sensor network ［M］. Bei jing:Electronics Industrial Publisher, 2007:2-6.

［2］ HO T,KOETTER R，EDARD M M’,D.Karger,and .Effros.The benefits of coding over routing in a randomized setting［C］// PaeifieoYokoharna.In Proc.IEEE ISIT.JaPan:2003: 227-234.

［3］ 王新梅,肖国镇.纠错码-原理与方法［M］.西安:西安电子科技大学出版社,2001.

［4］ LUBY M.LTcodes［C］// in Proceedings of the ACM Symposium on Foundations of Computer Science . 2002:271-282.

［5］ JANSHID ABOUEI ，DAVID BROWN J,KONSTANTIONS N. Plataniotis. On the Energy Efficiency of LT Codes in Proactive Wireless Sensor Networks ［J］．IEEE Transactions On Signal Processing, 2011, 59(3):：1116-1127 ．

［6］ 朱宏杰.喷泉码编译码技术与应用研究［D］．北京：清华大学,2008．

［7］ 慕建君,焦晓鹏,曹训志.数字喷泉码及其应用的研究进展和发展［J］.电子学报2009,37(7):1571-1577.

［8］ BYERS J W,LUBY M,MITZENMACHERM.Adigital folultain approach to asynchronous reliable multicast［J］.IEEE Journal on Seleeted Areas in Conlnlunieations,2002,20(8):1528-1540.

［9］ LEVIS P,MADDENS，GAYD,POLASTRE J,SZEWCZYK R,WOOA,BREWER E,CULLERD. The emergence of networking abstractions and techniques in tinyos ［C］//Proceedings of the First USENIX/ACM Networked System Design and Implementation 2004:1-14.

［10］ALEVIS P,LEEN,WELSHM,CULLERD.TOSSIM: Accurate and scalable simulation of entire tinyos applications ［C］// Proceedings of the 1st international conference on Embedded networked sensor system2003: 126-137.