基于网络编码的无线传感网F-CS n汇播增益的研究

赵东标

（温州大学 物理与电子信息工程学院，浙江 温州 325035）

无线传感器网络（WSNs）现在越来越受到重视，被应用到很多领域。这主要依靠于低功耗无线网络技术的进步以及嵌入式计算技术的快速发展。然而，WSNs中的各个相互协调独立工作的节点都是靠有限电量的电池供电并且很难给他充电或者更换电池。除此之外，WSNs中的无线链路在传输中经常会传送失败从而需要不断的重传，最终导致加速了能量的消耗。据我们所知WSNs节点发送数据占据了能量消耗的主要部分。因此，如何提高能量的利用率和传输的可靠性成为了无线传感器网络的主要工作。

Ahlswede[1]提出通过在中间节点[1-2]结合来自不同输入链路的数据的网络编码技术。很多应用采用这一种网络编码技术能够增加网络的吞吐量和减少能量消耗。WSNs的节点都具有广播特性的通信交流方式[3-4]，这为使用网络编码技术提供了天然的条件。网络编码的优点和使用条件都满足于WSNs的需要，所以应用网络编码技术在WSNs中是很有价值的。当前大部分人的研究概括为网络编码辅助的多播和单播，具体应用有在线重编程[5]、分布式数据存储与获取[6]、可靠数据传输[7]等等。据我们所知，网络编码在汇播中的研究还有很大的空间。WSNs中汇播模式的典型应用就是在一大片区域内布置传感器节点，这些节点独立的监测数据经过多跳之后汇聚给Sink节点，，这Sink节点和源节点中间的节点就可以把收到的数据进行编码之后再发送给Sink节点。该典型应用如图1所示。

图1 WSNs中汇播模型Fig.1 The convergecast mode in WSNs

Tang等[8]在文献中介绍了在汇播中引入线性网络编码的可能性，并从理论上证明了在CSn结构中应用线性网络编码能够产生可靠性增益。本文在此基础上，提出了一种更具有普遍性、适用性的F-CSn模型，并证明了该模型比CSn模型具有更多的可靠性增益。接下来的内容按以下顺序给出。第一部分介绍一种F-CSn汇播模型网络（完全型）并理论推导其编码增益以及仿真验证推导结果。第二部分将和CSn汇播模型网络（非完全型）结论进行比较和探讨。最后第三部分给出结论和总结。

1 F-CS n汇播网络模型的增益分析和仿真验证

1.1 F-CS n汇播模型（完全型）介绍

先说明下文中要用到的一些符号含义：Sn发送数据的源节点、Cn编码数据的中间节点、实线表示发送目的节点、虚线表示能够侦听到的节点、CSn为不完全侦听模型、F-CSn为完全侦听模型、Pn为对应的n阶不完全模型的Sink节点完全译码的概率、FPn为对应的n阶完全模型的Sink节点完全译码的概率。NPn为不采用网络编码技术传输时对应的n阶网络的Sink节点能全部接收数据的概率。具体网络模型如图2所示。

图2 F-CS n和CS n模型Fig.2 The mode of F-CS n and CS n

由图 4可以看出CSn不完全型网络模型的编码节点只能侦听到它的子节点的邻居节点，对于子节点的邻居节点以外的节点侦听不到数据，从而不能把更多的数据进行组合编码。但是Tang等理论推导出CSn的完全接收数据的概率，证明了该模型采用网络编码比不采用网络编码是有增益的。然而，在现实无线传感器网络中节点的侦听范围通常不只是邻居节点，它能够侦听到更多的发送数据。考虑这种情况我们试想如果发送节点的数据都能够被编码节点给侦听到并且进行编码，从而Sink节点完全解码出所有数据的概率会更高。所以我们提出了具有完全侦听模式的F-CSn模型网络。接下来我们便是证明F-CSn模型网络采用网络编码是有增益的并且增益比CSn模型网络更多。

1.2 网络编码增益分析和仿真验证

具体为：

以上是n阶通用的网络编码数学方程，当且仅当编码系数矩阵M满秩时，Sink节点才能完全译码出所有数据。本文中采用确定的编码系数机制，其编码规则为：编码节点C1对n个发送数据X的对应编码系数矩阵为：[1 2 3 4 5… n]，Cn把Cn-1（n≥2）的最后一个编码码系数作为自己的第一个编码系数并且把Cn-1的第一个至第n-1个编码系数作为自己的第二个至第n个编码系数。按此规则编码得具体编码矩阵M为：

很显然矩阵Mn×n的秩等于n，它表明采用该规则编码Sink 节点是可以完全译码的。 当 n=2、3、4 时，M2×2、M3×3、M4×4分别为：

由于WSNs经常所处的传输环境不好，所以每条链路LSj-Ci都有可能发送失败。假设每条链路LSj-Ci的成功传送率为r（0

接下来要具体求 Sn×n（i）

当 i∈[0，n-1]时，满秩的矩阵数量 Sn×n（i）=Cin×n。 当 i∈[n×n-n-1，n×n-n]时，相当于矩阵只有n个元素不为0和n+1个元素不为0。令矩阵Mn×n的每一行每一列只有一个元素：则第一行有n种选择、第二行有（n-1）种选择、…第n行只有1种选择。所以总共有n！种含有n个元素的最基本的满秩矩阵，并且这n！种矩阵相互之间至少有两个元素不相同。所以有n个元素不为0时有n！种满秩矩阵。有n+1个元素不为0时有种满秩矩阵。所以式（3）可以进一步化为式 （4）如下：

考虑矩阵的行和列的对称特性我们得出图4。

图3 特征矩阵Fig.3 The Characteristic matrix

图4 各阶矩阵类型Fig.4 The style of each order matrix

在具体求解过程中按照图4中从上到下的顺序写出算式并且下面的要减去和所有上面相同的种数，先从2阶开始求解。

化简之后得

P4×4（R（M4×4）=4）=

r16+16r15（1-r）1+120r14（1-r）2+560r13（1-r）3+1 812r12（1-r）4+4 272r11（1-r）5+7 432r10（1-r）6+9 312r9（1-r）7+8 081r8（1-r）8+4 464r7（1-r）9+1 416r6（1-r）10+288r5（1-r）11+24r4（1-r）12（14）

FP4=P4×4（R（M4×4）=4）×r4=

r20+16r19（1-r）1+120r18（1-r）2+560r17（1-r）3+1 812r16（1-r）4+4 272r15（1-r）5+7 432r14（1-r）6+9 312r13（1-r）7+8 081r12（1-r）8+4 464r11（1-r）9+1416r10（1-r）10+288r9（1-r）11+24r8（1-r）12（15）

很显然当网络不采用网络编码技术传输时的各阶完全接收的概率为：NP2=r2×2、NP3=r2×3、NP4=r2×4。 本文还对 F-CS2、FCS3、F-CS4模型分别进行了100万次的仿真试验，分别统计了其完全译码的概率。下面将给出F-CSn模型仿真结果和FCSn模型理论推导结果比较图（图5）、F-CSn模型和采用传统传输技术比较图（图6）、F-CSn模型相对于采用传统传输技术

图5 仿真和理论比较Fig.5 Comparison between simulation and theory

2 F-CS n和CS n模型网络编码完全解码的概率比较和探讨

如图 8所示是F-CSn和CSn的完全译码概率比较图。

从图8我们发现在同样的传送率 r下，F-CSn型完全解码的概率要高于CSn型。当n=2时，由于网络模型相同所以结果也相同。由图 5、图 6、图8、我们不难看出在相同的传送率r下，网络模型的阶数n越大网络完全接收数据的概率就越低，这主要是由因子rn决定的。由图7可以看出网络模型的阶数n越大采用网络编码的增益就越高，这是由于编码节点具有更多的侦听机会。然而我们现实网络中编码节点不可能侦听无限个发送节点也就是说n不是越大越好，在实际应用中要根据需要去确定网络规模从而带来更高的性价比。

图6 采用网络编码和不采用比较Fig.6 Comparison between With NCand No NC

图7 编码增益Fig.7 The benefit of network coding

图8 完全模型和不完全模型比较Fig.8 Comparison between full-cs n and cs n

3 结束语

本文通过提出F-CSn汇播网络模型，理论推导F-CS2、FCS3、F-CS4全部成功译码的概率，并仿真验证理论推导结果的准确性。而且和不采用网络编码技术传输时进行比较并证明了该模型采用网络编码可以提高网络的传输可靠性，减少传输次数从而节约了节点能量。最后还和CSn模型比较，从而证明了该模型采用网络编码时具有更多的编码增益，并且该模型更具有普遍性和适用性。网络编码带来增益的同时也使得节点的能量开销增加，接下来的工作就是找到节点的能量消耗和采用网络编码产生的增益之间的一个平衡点。

[1]Ahlswede R，Cai N，Li S-Y.R，et al.Network information flow[J].IEEE Transactions on InformationTheory，2000，46（4）：1204-1216.

[2]Tracey H，Muriel M，Jun S，et al.On randomized network coding [C]//in The 41st Annual Allerton Conference on Communication， Control，and Computing，2003（41）：11-20.

[3]Chachulski S，Jennings M，Katti S，et al.Trading structure for randomness in wireless opportunistic routing[C]//in the 2007 Conference on Applications，Technologies， Architectures，and Protocols for Computer Communications，2007:169-180.

[4]Katti S，Rahul H，Hu W，et al.Xors in the air:practical wireless network coding[C]//in The 2006 conference on Applications，technologies， architectures， and protocols for computer communications，2006:243-254.

[5]Hou I H，Yu-En T，Abdelzaher T F，et al.Adapcode:Adaptive network coding for code updates in wireless sensor networks[C]//in The IEEE 27th Conference on Computer Communications，2008：1517-1525.

[6]Wang D，Zhang Q，Liu J.Partial network coding:Concept，performance，and application for continuous data collection in sensor networks [J].ACM Transactions on Sensor Networks，2008，4（3）：111-135.

[7]Yang Y，Zhong C，Sun Y，et al.Network coding based reliable disjoint and braided multipath routing for sensor networks[J].Network and Computer Applications，2010，33（4）：422-432.

[8]Tang Z，Wang H，Hu Q，et al.How Network Coding Benefits Converge-Cast in Wiress Sensor Network [J].KSII Transactions on Internet and information Systems，2013，7（5）:1180-1197.