WSN中基于网络编码的协同点对点信息交换算法研究

韩最蛟，袁国贤，柳国光

(四川行政学院，四川 成都 610072)



WSN中基于网络编码的协同点对点信息交换算法研究

韩最蛟，袁国贤，柳国光

(四川行政学院，四川 成都 610072)

摘要：针对无线传感器中的节点调度传输问题，提出了一种基于网络编码的协同点对点信息交换算法。由于该算法不仅能够充分利用无线信道的广播特性，而且使用了协同点对点信息交换，从而有效地弥补了PIE算法在数据包的个数大于节点数目的情况下，性能不理想的缺陷，实现了传输次数的减少。仿真结果表明，所提算法的传输有效性明显地优于PIE算法和最少优先算法。

关键词：WSN；网络编码；信息交换；点对点

网络编码技术[1]允许不同信息流在有限域内进行编码操作以提高网络的性能。网络编码的主要应用包括：端到端网络中的数据分发和流媒体服务[2]，网络拓扑设计[3]，保密[4]和无线网络中的信息传送[5]。网络编码同上述应用相结合所带来的好处有：能效的提升[6]，吞吐量的提高[7]，时延的减少[8]、传输可靠性的提升[9]和安全性的改善[10]。

近些年来，在互联网中点对点(Peer-to-Peer，简称P2P)的文件共享是最受欢迎的应用之一[11]。而在WSN中，如何高效地实现点对点的文件共享仍然有待研究。由于无线信道的半双工的传输特性，不同的传输序列和调度算法对网络性能有直接的影响。在有些情况下，最优的和最差的性能之间差距很大。在本文中，把如何选择发送节点的问题称为节点调度问题。也就是说，节点调度问题是在一组可能的发送节点中通过某种调度算法来选取最优的发送节点以实现有限的无线资源的最大利用率。但是根据文献[12]，在传统的网络中，一般的调度问题被证明是NP问题。目前，最少优先算法(Rarest First Algorithm)[13]一般被用于解决节点调度问题，但是在大多数情况下，最少优先算法的性能并不是很理想。

随后，文献[14]提出了点对点的信息交换(Peer-to-Peer Information Exchange，简称PIE)算法。在PIE算法中，网络编码首次被应用于解决节点调度问题。虽然PIE算法的性能比最少优先算法的性能要好，但是，当数据包的个数远大于节点数时，PIE算法的性能并不是很理想。为了解决这个问题和设计更有效的算法，本章提出了基于网络编码的协同点对点信息交换(Network-Coding-based Cooperative Peer-to-Peer Information Exchange，简称NCPIE)算法。同最少优先算法只考虑包的稀有度和PIE算法考虑节点的新鲜度而言，NCPIE算法不仅考虑了节点收益——节点收益是指有在一次传输过程中有多少节点能够收到有用的信息，而且分别考虑了每个节点缓存的未编码的数据包个数和编码的数据包个数。定量分析和仿真结果都证明了NCPIE算法的有效性和可靠性。

1问题建模

假设一个WSN是由N个传感器节点和一个簇头节点组成。该WSN可以进一步抽象为由N个接收节点和一个信源节点S组成。接收节点表示为pi(1≤i≤N)，pi与pj之间的距离用dij表示。同时，对于每个pi，其通信范围与干扰范围分别定义为ci和ri(ci≤ri)。接收节点集用G表示，边集l和l′的定义如下：

(1)

(2)

(3)

满足以下条件：

tri=1⟹trj=0，∀(i，j)∈l′

(4)

(5)

(6)

(7)

(8)

E∈Z+

(9)

条件(4)保证了在发送节点干扰范围内的所有节点都不发送数据。条件(5)确保了接收节点在发送节点的通信范围内。条件(6)意味着如果节点在多个发送节点的干扰范围内，那么这个节点不能成功地接收到数据包。条件(7)表示在状态E，所有的节点都收齐了M个相互独立的数据包。条件(8)和(9)是整性约束。

为了不失一般性，假设在信息交换阶段，节点都能够正确地译出其它节点发送的数据包，并且选取的发送节点总是发送一个全编码的数据包，同时假设有限域足够大，那么每一个全编码的数据包都是相互独立的。表1给出了本文用到的符号。

表1　符号表

2算法设计

图2给出了NCPIE算法流程图。NCPIE算法包含4个部分：预处理(Pre-processing)，调度(Scheduling)，更新(Refreshing)和结束(End)。下面对各个部分进行详细地阐述。

图2　基于网络编码的协同点对点信息交换算法流程

Pre-processing：在NCPIE算法中，每个节点在共享的信道中广播各自的PRV和NRV，并且假设所有的节点都能够正确地接收到这些消息，每个节点根据收到的PRV和NRV，补齐PRM和NRM。接着，每个节点计算系统增益(SGM)。SGM的计算如下所示：

(10)

SGMij表示如果节点pi在第j次发送操作作为发送节点，能够收到有用信息的节点的数目。PRVi是PRM的第i行的行向量。指示函数的定义如下：

(11)

其中，PRVim是向量PRVi的第m个元素。例如，SGMij=3意味着如果在第j次发送操作，选择节点pi作为发送节点，那么有3个节点可以从本次发送操作中恢复出有用的信息。

接着判断在N个节点中是否有节点收齐了M个独立的数据包。如果存在这样的节点，那么其中一个pn被选为发送节点，在后续的信息交换过程中，pn一直作为发送节点，直到剩下的所有节点收齐了M个独立的数据包。可以看出，如果pn作为发送节点，那么每次的发送操作，除了已经收齐M个独立的数据包的节点外，剩下的节点都能够收到有用的信息。换句话说，同其他算法相比较，NCPIE算法保证了每次传输操作BAPj值最大，因此，NCPIE算法下的TSN更接近理论下限。

Algorithm1:SchedulingAlgorithmInput:PRM,NRM,SGMOutput:sending_peerbegin PSHSG←peershavingthehighestsystemgaininSGM ifPSHSG=1then sending_peer←theuniquememberofPSHSG else PSMUP←thepeersinPSHSGwiththemostuncodedpackets ifPSMUP=1then sending_peer←theuniquememeberofPSMUP else PSMP←thepeersinPSMUPwiththemostpackets ifPSMP=1then sending_peer←theuniquememeberofPSMP else PSMEP←thepeersinPSMPwiththemostencodedpackets sending_peer←thefirstmemberofPSMEP end end endend

Scheduling：调度算法在算法1中进行了描述。首先，有着最大系统增益的节点被从SGM中选出放在节点集PSHSG(Peer Set with Highest System Gain)中。如果在PSHSG中只有一个元素，那么发送节点就是这个唯一的节点。否则的话，从PSHSG中选择拥有最多无编码数据包的节点放进节点集PSMUP(Peer Set with Most Uncoded Packets)中。节点pi拥有的无编码的数据包的个数等于行向量PRVi中元素1的个数。如果PSMUP中只有一个元素，那么发送节点就是这个唯一的节点。否则的话，从PSMUP中选择拥有最多数据包的节点放进节点集PSMP(Peer Set with Most Packets)中。节点pi拥有的数据包的个数等于NRMi，例如，NRMi=3说明节点pi收到了3个独立的数据包。如果PSMP中只有一个元素，那么发送节点就是这个唯一的节点。否则，从PSMP中选择拥有最大编码包的节点放进节点集PSMEP(Peer Set with Most Encoded Packets)中。节点pi拥有的编码包的个数等于NRMi减去PRVi中元素1的个数。最后PSMEP中的第一个元素被选为发送节点。

Algorithm2:RefreshingAlgorithmInput:sending_peer,PRM,NRMOutput:PRM,NRMbegin send_packet←acodedblockofthesending_peer fori=1:Ndo ifsend_packetisnovelforpeeri NRMi=NRMi+1; PRM(i,:)-- end endend

End：当所有的节点都收齐了Γ，交换过程结束。如果这些节点还有其它的数据用于交换，它们可以重复上述过程。

3仿真分析

(12)

其中，Et为传输有效性，TSN是仿真结果。

图3给出了稀有度为0.3的情况下，传输有效性随数据包的个数的变化情况。从图3可以看出，NCPIE算法的性能要优于PIE算法和最少优先算法。并且随着数据包个数的增加，3种算法的性能都有所下降，但NCPIE算法的性能下降是最慢的。此外，从图3可以看出，NCPIE算法的传输有效性始终大于95%。

图3　传输有效性 vs. 数据包的个数

图4给出了稀有度为0.3的情况下，传输有效性随节点数的变化情况。从图4可以看出，NCPIE算法的传输有效性是最高的。并且随着节点数目的增加，3种算法的传输有效性都有所上升。这是因为随着节点数目的增加，节点收齐M个独立的数据包的概率增大。此外，在图4中，NCPIE算法始终保持着超过97%的传输有效性。

图4　传输有效性 vs. 节点数

图5中给出了在不同的节点数目(N=10,15)和不同的数据包个数(M=5,15,20)的情况下，传输有效性随稀有度的变化情况。从图5可以看出，在各种情况下，NCPIE算法的有效性都要要优于PIE算法和最少优先算法的，并且NCPIE算法的有效性都超过97%，因此，NCPIE算法是最优的。

图5　传输有效性 vs.稀有度

4结语

本文提出了一种基于网络编码的协同点对点信息交换算法来解决无线传感器网络中的节点调度问题。该算法通过节点之间的协同传输来提高网络吞吐量，减少传输延迟，改善传输有效率。实验表明，本文所提算法的性能明显地优于PIE算法和最少优先算法。

参考文献：

[1]R.Ahlswede，N.Cai，S.-Y.Li，et al. Network Information Flow[J].IEEE Trans.Inf.Theory，2000，46(4)：1204-1216.

[2]Huicheng Chi，Qian Zhang，Juncheng Jia，et al.Efficient Search and Scheduling in P2P-based Media-on-Demand Stream Service[J].IEEE J.Sel.Area Commun，2007，25(1)：119-130.

[3]Kaikai Chi，XIaohong Jiang，Susumu Horiguchi，et al.Topology Design of Network-Coding-Baded Multicast Networks[J].IEEE T.PARALL DISTR，2008，19(5)：627-640.

[4]Denis Charles，Kamal Jain，KristinLauter.Signatures for Network Coding[J].Int.J.Information and Coding Theory，2009，(1)：3-14.

[5]C.Fragouli，J.Widmer，J.-Y.Le Boudec.Efficient Broadcasting Using Network Coding[J] .IEEE/ACM Trans.Networking，2008，16(2)：450-463.

[6]Yu Wang，Ian D.Henning.Low-Complexity Network Coding Algorithms for Energy Efficient Information Exchange[J].2008，10(4)：396-402.

[7]Ali Al-Bashabsheh, Abbas Yongacoglu. Average Throughput with Linear Network Coding over Finite Fields: the Combination Network Case[J]. EURASIP Journal on Wireless Communications and Networking, 2008, 1(1):1-10.

[8]Eryilmaz，A.Ozdaglar，A.Medard，etal.On the Delay Throughput Gains of Coding in Unreliable Networks[J].2008，54(12)P：5511-5524.

[9]IgorStanojev，Osvaldo Simeone，Yeheskel Bar-Ness，etal.Performance of Multi-Relay Collaborative Hybrid-ARQ Protocols over Fading Channels[J].2006，10(7)：522-524.

[10]Yaping Li, Hongyi Yao, Minghua Chen, etal. RIPPLE Authentication for Network Coding[C]. San Diego : 2010 Proceedings IEEE INFOCOM, 2010.

[11]Androutsellis-Theotokis S, Spinellis D. A survey of peer-to-peer content distribution technologies[J]. Acm Computing Surveys, 2004, 3(36):335-371.

[12]Saqib Raza, Danjue Li, Chen-Nee Chuah, etal.Cooperative Peer-to-Peer Repair for Wireless Multime dia Broadcast[C]. Beijing:2007 IEEE International Con ference on Multimedia and Expo, 2007.

[13]Legout A, Urvoy-Keller G, Michiardi P. Rarest First and Choke Algorithms are Enough[J]. Computer Science, 2006, 3(6):203-216.

[14]Yanfei Fan，Yixin Jiang，Haojin Zhu.PIE：Cooperative Peer-to-Peer Information Excchange in Network Coding Enabled Wireless Networks[J].IEEE Transactions on Wireless Communicaitions[J].2010，9(3)：945-950.

Collaborative Peer-to-Peer Information Exchange Algorithm in WSN Based on Network Coding

HAN Zui-jiao, YUAN Guo-xian, LIU Guo-guang

(Sichuan Administration College,Chengdu 610072,China)

Abstract:Aiming at the peer scheduling problem in wireless sensor network,a cooperative peer-to-peer information exchange algorithm based on network coding is proposed.This proposed algorithm not only makes full use of broadcasting characteristics of wireless channel,but also uses cooperative peer-to-peer information exchange,so it can effectively make up for the shortages of PIE algorithm and reduce the number of transmissions.Experimental results demonstrate that the performance of the proposed algorithm is better than that of PIE algorithm and rarest first algorithm.

Key words:WSN;network coding;information exchange;peer-to-peer

doi:10.3969/j.issn.1009-4210.2016.03.014

收稿日期：2016-04-07

作者简介：韩最蛟(1963—)，男，副教授，从事计算机应用技术、电子政务、遥感技术、应用物理等应用研究。

中图分类号：TP212.9

文献标志码：A

文章编号：1009-4210-(2016)03-099-08