基于LT喷泉码的WSNs抗WLAN干扰的实验研究

杨 凯，施伟斌，吕 涛

（上海理工大学光电信息与计算机工程学院，上海 200093）

0 引言

目前，无线传感器网络（WSNs）主要基于IEEE 802.15.4协议，通常工作在2.4 GHz的ISM频段，然而室内环境中已有的大量基于IEEE 802.11协议的无线局域网（WiFi）设备也使用该频段。有研究显示［1］，当WiFi网络和WSNs部署在同一环境中，且WiFi信道与WSNs信道重叠时，WiFi通信会对WSNs产生较大干扰，严重影响WSNs的可靠性，在最坏的情况下，WSNs的丢包率将高于90%。

鉴于WSNs在同WiFi共存时丢包率较高，且通常MAC层使用CRC校验的原因，有损坏的数据包便会被简单丢弃。因此，在这种情况下，本文将无线信道看成类似BEC的二进制删除信道。在二进制删除信道上实现可靠传输的通常做法是采用自动请求重传（ARQ）的方式。该方法工作时虽然无需预先知道信道的删除概率，但需要较多的反馈以致会产生反馈内爆问题［2］。还有一种方法是采用传统的纠删码编码方式，如RS纠删码［3］，但RS码的码率固定，而WiFi无线信道链路质量动态变化的特性使得发送端无法预先确定信道的删除概率，从而无法确定使用RS码的发送端的码率。RS码编解码算法复杂，不适宜在资源有限的传感器节点上实现。喷泉码是一种无码率码，即发送端可以对原始信息源源不断地编码。只要接收端收到足够的编码信息就可以恢复出原信息。相比ARQ的反馈重传和RS码需根预先据信道删除情况而确定固定码率的方式，显然喷泉码的灵活性更大，能够适应WiFi信道多变时的数据传输。

1 LT码的编译码算法

1998年，Luby M和Byers J等人首次提出了数字喷泉码的概念。LT［4］码和 Raptor［5］码是目前典型的 2 种实用喷泉码。鉴于Raptor码需经过预编码，且算法复杂较大，考虑到WSNs中传感器节点运算能力有限，本文使用LT码来设计并实现可靠传输协议。

1.1 喷泉码的基本思想

源端无限制地随机从待发送的符号（symbol）中选择部分符号进行异或编码，然后发送出去，用户只要接收到一定数量的编码符号，即可成功恢复源端发送的符号信息，若不能全部恢复，则继续接收至所有符号都恢复为止。

1.2 度与度分布函数的定义

假设现有K个符号（symbol）待发送。这里每个符号可以是1 bit，也可以是一个数据包（packet）。由于实验中采用的是包级别的LT编码，所以，本文的符号特指数据包。

定义1 度（d）:生成一个LT编码包所需的原始数据包的个数。

定义2 度分布函数（ρ（d））:对于所有的d，ρ（d）表示该LT编码包中出现度为d的概率。

1.3 LT码的编码算法

1）从度分布函数ρ（d）中随机选取LT编码数据包的度d。

2）等概率地从K个原始数据包中随机选取d个不同的原始数据包。

3）将这d个原始数据包互相异或产生一个LT编码包。以图1为例，从LT度分布函数中按照概率分布，某次恰取得d=3，然后从K个原始数据包中等概率地选取3个，这里是t1，t3，tK，接着将这3个数据包互相异或就得到了一个LT数据包。

4）重复步骤（1），（2），（3），N次得到N个编码包。

上述编码过程非常简单，关键是度分布函数的设计，具体设计方法参见文献［4］。

图1 某个LT编码包的生成Fig 1 Generation of a LT encoding packet

1.4 LT码的译码2种算法

1）高斯消元（Gaussian elimination）算法［6］

高斯消元法适用于所有喷泉吗的解码，它在数学上实际就是解线性方程组。LT码解码端的任务就是从T=GS中通过矩阵求逆恢复出S矩阵，这里S是原始数据包矩阵，T表示收到的LT编码包的矩阵。原始数据包和LT编码包的关系可用B×K的生成矩阵G来表示，这里K是原始数据包的个数，N是发送端生成的LT编码包的个数。若矩阵满秩，则译码成功;否则，不能够恢复原始数据包，那么就需要接收更多的LT编码包。

2）置信传递（belief propagation）算法

a.根据LT编码包和原始数据包的对应关系建立二分图。

b.在译码的每一阶段，都在LT编码包集合中寻找度为1的包，显然，这些LT编码包对应相连的原始数据包可以直接译出。

c.译码器将每一个译出的原始数据包与所有跟它相连的LT编码包相异或，异或后的值覆盖对应LT编码包的以前的值，同时删去这个译出的原始数据和对应的LT编码包的联系（二分图的边），从而使得这些编码包的度数减1，这样就会产生新的度数为1的编码包。

d.重复上述过程（b），（c），直到译码结束或者没有度数为1的编码包，迭代过程停止。如果所有LT编码包被成功恢复，则译码成功;否则，译码失败。

以上2种译码算法各有优缺点:GE算法译码复杂度为O（K3）pj，复杂度较高，但只要G矩阵满秩，必然可以译码成功。由于度分布函数的精细设计，使得G矩阵是稀疏矩阵，所以，BP算法显然比GE算法复杂度低，但BP译码过程的延续需要每一步都存在度为1的LT编码包，故即使生成矩阵G是满秩的，采用BP译码也可能造成译码失败。考虑到TinyOS系统定义的数据包的data部分最大为28个字节，故采用GE算法的复杂度可以接受，同时，采用GE算法的译码成功率又比BP算法要高。所以，设计的LT喷泉码的译码采用高斯消元算法。

2 WSNs中实现LT喷泉码的具体问题

2.1 LT喷泉码度分布函数的选取

传统的LT喷泉码主要用于大数据包或大文件的编码，以保持很好的统计特性，所以，现有的较成熟得度分布函数［4］:全“1”分布、理想孤波分布、均匀分布和鲁棒孤波分布均不适用于以短数据包通信的WSNs中。

通过研究比较和实验仿真，本文采用意大利普渡大学Rossi Michele设计的度分布函数［7］，如表1所示。

2.2 LT喷泉码生成矩阵的重构

当接收端使用收到的LT编码包来恢复原始数据包时，需要知道每个LT编码包的度和该LT编码包究竟是由哪几个原始数据包异或而成的，其实就是重构发送端的生成矩阵G。显然，将发送端的生成矩阵G整体发送给接收端一方面增加了网络负载，另一方面由于受无线信道干扰，有些LT编码包会被破坏，这样接收端要从整个G中选择收到的LT编码包中获得上述信息，增加了译码的复杂度。

表1 采用的度分布函数Tab 1 Adopted degree distribution function

本文采用的方法是:在收发两端采用相同的随机数生成器，且将随机数种子跟随LT编码包一起由发送端发送出去，接收端接收到编码包后取出其中的种子放入自己的随机数生成器中，这样就又重新知道了收到的该LT编码包究竟是由哪几个原始数据包异或而成的，循环往复即可重构出生成矩阵G。

2.3 LT编码包结构

本文所进行的实验基于TinyOS—2.x操作系统，其帧结构message_t由包头、数据区、包尾、元数据四部分构成，其中主要设置的是数据区部分。LT编码包结构如图2所示。

图2 LT编码包结构Fig 2 Structure of LT encoding packet

数据区的前2个字节用于存放随机数种子，之后的负载区域的25个字节是根据随机选取的度数而将某几个源消息包异或而成的。

3 WSNs中基于LT喷泉码的单跳信息分发协议

3.1 基本思想

发送节点源源不断地发送LT编码包，各个接收节点译码成功后均发送停止消息，发送节点收到所有邻居节点的停止消息后，则停止发送LT编码包。

3.2 4 种消息

1）ADV消息:由发送节点发出该消息，用于通知邻居的接收节点准备接收文件;

2）REQ消息:由接收节点广播该消息，以告知发送节点本节点已准备好接收;

3）DATA消息:由发送节点广播该消息，该消息包含将源数据包经过LT编码后的编码包;

4）STOP消息:由接收节点广播该消息，告知发送端本节点已成功解码。

3.3 系统工作过程

系统开始，发送节点广播ADV消息，通知邻居的接收节点准备接收文件。ADV消息中包含此次传输的文件的大小。当接收节点收到发送节点的ADV消息后，广播REQ消息，以告知发送节点本节点已准备好接收 DATA消息。当发送节点收到所有邻居节点的REQ消息后，将源数据包经过LT编码后广播出去，每一个LT编码包对应一个DATA消息。当接收节点收到足够多的DATA消息而解码成功后，须广播STOP消息，告知发送端本节点已成功解码，不再需要LT编码包。当发送节点收到所有邻居节点的STOP消息后，表明所有接收节点已成功恢复源数据，则发送端停止发送DATA消息，系统停止。

整个节点程序流程图如图3所示。

图3 LT喷泉码的单跳信息分发协议流程图Fig 3 Flow chart of single-hop information distribution protocol of LT fountain codes

其中，时间段T表示数据包往返收发两端的最长时间，从发送端成功发送出ADV消息开始计时。N为接收节点个数，K为源数据包的个数，ε为译码开销。

4 实验方法

实验的主要目的是测试WSNs中基于LT喷泉码的单跳信息分发协议能否正常工作和工作性能。以往很多研究都是采用仿真的方法测试LT喷泉码的性能和效果［8］，但仿真测试不能模拟环境中存在的各种干扰，尤其是WLAN链路质量的动态变化会造成不同的干扰影响。

4.1 实验平台与环境

实验系统的硬件由8个以CC2430为核心的WSNs节点，一个网关板和一台PC机构成。节点软件采用TinyOS系统的NesC语言开发，上位机软件采用串口通信程序。

实验在6.3 m×5.7 m的实验室内进行。节点分布如图4所示。其中1#节点是发送节点，通过串口与主机相连，其余节点均是接收节点。2#和7#点旁边各有一台主机，4#节点附近是无线路由器。

图4 实验室节点分布图Fig 4 Node distribution in lab

实验室无线路由器固定占用遵从IEEE 802.11 b/g标准的11信道。根据WSNs使用的信道和WLAN使用的信道是否重叠，将实验测试条件分为2种:

条件 1:WSNs使用 11信道，从图 5可知［9］，此时，WSNs和WLAN使用的信道无重叠。

条件2:WSNs使用信道22，从图5可知，此时，接近无线路由器11信道的中心频率，即WSNs和WLAN使用的信道重叠。

图5 IEEE 802.15.4 和 IEEE 802.11b/g 在2.4 GHz频段的频率范围Fig 5 Frequency range of IEEE 802.15.4 and IEEE 802.11 b/g in 2.4 GHz band

4.2 实验步骤

首先，将相同的TinyOS源程序烧写到所有节点上，节点通过判断自身的节点号是否为1来选择到底是发送还是接收文件。

然后，将连接节点1的主机通过串口通信程序向1#节点发送一个800字节的文件。1#节点收到该文件后立即开始广播ADV消息。

接着，如果是在环境1中进行实验，省略这一步。如果是在环境2中进行实验，则在图4中3台主机上通过WLAN互传大小为2 G左右的大文件。文件传输速度为2～3 Mbps。

最后，观察节点板的黄灯是否闪烁，若闪烁，则代表本节点已成功解码，恢复出源数据;反之，则没有。还可以将每一个节点通过串口连接到主机上，通过串口通信程序显示本节点的一系列评价指标。

4.3 实验结果分析

根据文献［10］所得结论，将接收节点开始解码所需的包个数设置为36，几乎可100%地保证解码成功。因此，为提高解码的成功率，减少多次解码的时间浪费，实验中，将该值设置为36。

在条件1中，实验结果如表2所示。

表2 条件1中实验结果图Tab 2 Experimental results in condition 1

在条件2中，实验结果如表3所示。

表3 条件2中实验结果图Tab 3 Experimental results in condition 2

对实验结果进行分析，可以得到如下结论:

1）当WSNs和WLAN使用的信道不重叠时，WSNs中的丢包率很小，约为0.34%。如表2所示，除5#节点收到的第36个包的序列号是37外，其余节点收到的第36个包的的序列号均为36。当WSNs和WLAN使用的信道重叠，且WLAN使用的信道被大文件传输而占用时，WSNs中的丢包率很高，约为79%。

2）当WSNs和WLAN使用的信道不重叠时，接收节点成功接收一个800字节的文件平均需要2.68 s。当WSNs和WLAN使用的信道重叠，且WLAN使用的信道被大文件传输而占用时，接收节点成功接收一个800字节的文件平均需要14.37s，相较于条件1中的3.17s大大增加;究其原因:一是由于条件2中WSNs的信道常被WLAN中传输的文件所占用，导致WSNs中的编码包很难获得信道;二是由于WSNs和WLAN同时使用信道时数据包的碰撞而致WSNs发送的DATA包被破坏，故发送端需要传输更多的编码包，这样自然增加了通信时间。

3）根据表3中每个节点收到的第36个DATA包的序列号不同可知，虽然这些节点都处在同一实验室内，但各节点所受干扰却各有差异:2#节点受干扰最严重，发送节点发送给2#节点时丢包率达83%。3#节点受干扰影响最小，发送节点发送给3#节点时丢包率为72%。表3中2#，7#节点受干扰较重是因为它们旁边的主机和1#节点的主机正在无线传输大文件，而3#和5#节点因为远离无线路由器和主机，所以，受干扰也较小。

5 结束语

本文提出了一种采用纠删码——LT喷泉码编码来保证可靠传输的方法，并在以CC2430为核心的平台上设计并实现了基于LT喷泉码的单跳信息分发协议。该方法在有较强WiFi干扰的情况下可以正常工作，实现大数据量的可靠传输。

［1］Sikora A，Groza V F.Coexistence of IEEE 802.15.4 with other systems in the 2.4 GHz-ISM-band［C］//Proceedings of the IEEE Instrumentation ＆ Measurement Technology Conference，Ottawa，Canada，2005:1786-1791.

［2］Nonnenmacher J，Biersack E W，Towsley D.Parity-based loss recovery for reliable multicast transmission［J］.IEEE/ACM Trans on Networking，1998，6（4）:349-361.

［3］Reed I S，Solomon G.Polynomial codes over certain finite fields［J］.Journal of the Society for Industrial and Applied Mathematics，1960，8（2）:300-304.

［4］Luby M.LT codes［C］//Proc of the 43rd Annual IEEE Symposium on Foundation of Computer Science，Washington DC，USA，2002:271-280.

［5］Shokrollahi A.Raptor codes［J］.IEEE Transactions on Information Theory，2006，52（6）:2551-2567.

［6］Pishro-Nik H，Fekrii F.On decoding of low density parity-check codes over binary erasure channel［J］.IEEE Transactions on Information Theory，2004，50（3）:439-454.

［7］Rossi M，Zanca G，Stabellini L，et al.SYNAPSE:A network reprogramming protocol for wireless sensor networks using fountain codes［C］//Proc of IEEE Comm Soc Conf on Sensor，Mesh and Ad Hoc Comm and Networks（SECON），San Francisco，USA，2008:188-196.

［8］刘 惠，李晓军，杜军朝，等.基于LT喷泉码的无线传感器网络信息分发协议性能评价［J］.微电子学与计算机，2010，27（8）:100-102.

［9］Musaloiu E R，Terzis A.Minimising the effect of WiFi，interference in 802.15.4 wireless sensor networks［J］.International Journal of Sensor Networks，2007，3（1）:43-54.

［10］Rossi M，Bui N，Zanca G，et al.SYNAPSE++:Code dissemination in wireless sensor networks using fountain codes［J］.IEEE Transactions on Mobile Computing，2010，9（12）:1749-1765.