韓最蛟，袁國賢，柳國光

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

?

WSN中基于網(wǎng)絡編碼的協(xié)同點對點信息交換算法研究

韓最蛟，袁國賢，柳國光

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

摘要：針對無線傳感器中的節(jié)點調(diào)度傳輸問題，提出了一種基于網(wǎng)絡編碼的協(xié)同點對點信息交換算法。由于該算法不僅能夠充分利用無線信道的廣播特性，而且使用了協(xié)同點對點信息交換，從而有效地彌補了PIE算法在數(shù)據(jù)包的個數(shù)大于節(jié)點數(shù)目的情況下，性能不理想的缺陷，實現(xiàn)了傳輸次數(shù)的減少。仿真結(jié)果表明，所提算法的傳輸有效性明顯地優(yōu)于PIE算法和最少優(yōu)先算法。

關鍵詞：WSN；網(wǎng)絡編碼；信息交換；點對點

網(wǎng)絡編碼技術[1]允許不同信息流在有限域內(nèi)進行編碼操作以提高網(wǎng)絡的性能。網(wǎng)絡編碼的主要應用包括：端到端網(wǎng)絡中的數(shù)據(jù)分發(fā)和流媒體服務[2]，網(wǎng)絡拓撲設計[3]，保密[4]和無線網(wǎng)絡中的信息傳送[5]。網(wǎng)絡編碼同上述應用相結(jié)合所帶來的好處有：能效的提升[6]，吞吐量的提高[7]，時延的減少[8]、傳輸可靠性的提升[9]和安全性的改善[10]。

近些年來，在互聯(lián)網(wǎng)中點對點(Peer-to-Peer，簡稱P2P)的文件共享是最受歡迎的應用之一[11]。而在WSN中，如何高效地實現(xiàn)點對點的文件共享仍然有待研究。由于無線信道的半雙工的傳輸特性，不同的傳輸序列和調(diào)度算法對網(wǎng)絡性能有直接的影響。在有些情況下，最優(yōu)的和最差的性能之間差距很大。在本文中，把如何選擇發(fā)送節(jié)點的問題稱為節(jié)點調(diào)度問題。也就是說，節(jié)點調(diào)度問題是在一組可能的發(fā)送節(jié)點中通過某種調(diào)度算法來選取最優(yōu)的發(fā)送節(jié)點以實現(xiàn)有限的無線資源的最大利用率。但是根據(jù)文獻[12]，在傳統(tǒng)的網(wǎng)絡中，一般的調(diào)度問題被證明是NP問題。目前，最少優(yōu)先算法(Rarest First Algorithm)[13]一般被用于解決節(jié)點調(diào)度問題，但是在大多數(shù)情況下，最少優(yōu)先算法的性能并不是很理想。

隨后，文獻[14]提出了點對點的信息交換(Peer-to-Peer Information Exchange，簡稱PIE)算法。在PIE算法中，網(wǎng)絡編碼首次被應用于解決節(jié)點調(diào)度問題。雖然PIE算法的性能比最少優(yōu)先算法的性能要好，但是，當數(shù)據(jù)包的個數(shù)遠大于節(jié)點數(shù)時，PIE算法的性能并不是很理想。為了解決這個問題和設計更有效的算法，本章提出了基于網(wǎng)絡編碼的協(xié)同點對點信息交換(Network-Coding-based Cooperative Peer-to-Peer Information Exchange，簡稱NCPIE)算法。同最少優(yōu)先算法只考慮包的稀有度和PIE算法考慮節(jié)點的新鮮度而言，NCPIE算法不僅考慮了節(jié)點收益——節(jié)點收益是指有在一次傳輸過程中有多少節(jié)點能夠收到有用的信息，而且分別考慮了每個節(jié)點緩存的未編碼的數(shù)據(jù)包個數(shù)和編碼的數(shù)據(jù)包個數(shù)。定量分析和仿真結(jié)果都證明了NCPIE算法的有效性和可靠性。

1問題建模

假設一個WSN是由N個傳感器節(jié)點和一個簇頭節(jié)點組成。該WSN可以進一步抽象為由N個接收節(jié)點和一個信源節(jié)點S組成。接收節(jié)點表示為pi(1≤i≤N)，pi與pj之間的距離用dij表示。同時，對于每個pi，其通信范圍與干擾范圍分別定義為ci和ri(ci≤ri)。接收節(jié)點集用G表示，邊集l和l′的定義如下：

(1)

(2)

(3)

滿足以下條件：

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

(4)

(5)

(6)

(7)

(8)

E∈Z+

(9)

條件(4)保證了在發(fā)送節(jié)點干擾范圍內(nèi)的所有節(jié)點都不發(fā)送數(shù)據(jù)。條件(5)確保了接收節(jié)點在發(fā)送節(jié)點的通信范圍內(nèi)。條件(6)意味著如果節(jié)點在多個發(fā)送節(jié)點的干擾范圍內(nèi)，那么這個節(jié)點不能成功地接收到數(shù)據(jù)包。條件(7)表示在狀態(tài)E，所有的節(jié)點都收齊了M個相互獨立的數(shù)據(jù)包。條件(8)和(9)是整性約束。

為了不失一般性，假設在信息交換階段，節(jié)點都能夠正確地譯出其它節(jié)點發(fā)送的數(shù)據(jù)包，并且選取的發(fā)送節(jié)點總是發(fā)送一個全編碼的數(shù)據(jù)包，同時假設有限域足夠大，那么每一個全編碼的數(shù)據(jù)包都是相互獨立的。表1給出了本文用到的符號。

表1　符號表

2算法設計

圖2給出了NCPIE算法流程圖。NCPIE算法包含4個部分：預處理(Pre-processing)，調(diào)度(Scheduling)，更新(Refreshing)和結(jié)束(End)。下面對各個部分進行詳細地闡述。

圖2　基于網(wǎng)絡編碼的協(xié)同點對點信息交換算法流程

Pre-processing：在NCPIE算法中，每個節(jié)點在共享的信道中廣播各自的PRV和NRV，并且假設所有的節(jié)點都能夠正確地接收到這些消息，每個節(jié)點根據(jù)收到的PRV和NRV，補齊PRM和NRM。接著，每個節(jié)點計算系統(tǒng)增益(SGM)。SGM的計算如下所示：

(10)

SGMij表示如果節(jié)點pi在第j次發(fā)送操作作為發(fā)送節(jié)點，能夠收到有用信息的節(jié)點的數(shù)目。PRVi是PRM的第i行的行向量。指示函數(shù)的定義如下：

(11)

其中，PRVim是向量PRVi的第m個元素。例如，SGMij=3意味著如果在第j次發(fā)送操作，選擇節(jié)點pi作為發(fā)送節(jié)點，那么有3個節(jié)點可以從本次發(fā)送操作中恢復出有用的信息。

接著判斷在N個節(jié)點中是否有節(jié)點收齊了M個獨立的數(shù)據(jù)包。如果存在這樣的節(jié)點，那么其中一個pn被選為發(fā)送節(jié)點，在后續(xù)的信息交換過程中，pn一直作為發(fā)送節(jié)點，直到剩下的所有節(jié)點收齊了M個獨立的數(shù)據(jù)包?？梢钥闯?，如果pn作為發(fā)送節(jié)點，那么每次的發(fā)送操作，除了已經(jīng)收齊M個獨立的數(shù)據(jù)包的節(jié)點外，剩下的節(jié)點都能夠收到有用的信息。換句話說，同其他算法相比較，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：調(diào)度算法在算法1中進行了描述。首先，有著最大系統(tǒng)增益的節(jié)點被從SGM中選出放在節(jié)點集PSHSG(Peer Set with Highest System Gain)中。如果在PSHSG中只有一個元素，那么發(fā)送節(jié)點就是這個唯一的節(jié)點。否則的話，從PSHSG中選擇擁有最多無編碼數(shù)據(jù)包的節(jié)點放進節(jié)點集PSMUP(Peer Set with Most Uncoded Packets)中。節(jié)點pi擁有的無編碼的數(shù)據(jù)包的個數(shù)等于行向量PRVi中元素1的個數(shù)。如果PSMUP中只有一個元素，那么發(fā)送節(jié)點就是這個唯一的節(jié)點。否則的話，從PSMUP中選擇擁有最多數(shù)據(jù)包的節(jié)點放進節(jié)點集PSMP(Peer Set with Most Packets)中。節(jié)點pi擁有的數(shù)據(jù)包的個數(shù)等于NRMi，例如，NRMi=3說明節(jié)點pi收到了3個獨立的數(shù)據(jù)包。如果PSMP中只有一個元素，那么發(fā)送節(jié)點就是這個唯一的節(jié)點。否則，從PSMP中選擇擁有最大編碼包的節(jié)點放進節(jié)點集PSMEP(Peer Set with Most Encoded Packets)中。節(jié)點pi擁有的編碼包的個數(shù)等于NRMi減去PRVi中元素1的個數(shù)。最后PSMEP中的第一個元素被選為發(fā)送節(jié)點。

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：當所有的節(jié)點都收齊了Γ，交換過程結(jié)束。如果這些節(jié)點還有其它的數(shù)據(jù)用于交換，它們可以重復上述過程。

3仿真分析

(12)

其中，Et為傳輸有效性，TSN是仿真結(jié)果。

圖3給出了稀有度為0.3的情況下，傳輸有效性隨數(shù)據(jù)包的個數(shù)的變化情況。從圖3可以看出，NCPIE算法的性能要優(yōu)于PIE算法和最少優(yōu)先算法。并且隨著數(shù)據(jù)包個數(shù)的增加，3種算法的性能都有所下降，但NCPIE算法的性能下降是最慢的。此外，從圖3可以看出，NCPIE算法的傳輸有效性始終大于95%。

圖3　傳輸有效性 vs. 數(shù)據(jù)包的個數(shù)

圖4給出了稀有度為0.3的情況下，傳輸有效性隨節(jié)點數(shù)的變化情況。從圖4可以看出，NCPIE算法的傳輸有效性是最高的。并且隨著節(jié)點數(shù)目的增加，3種算法的傳輸有效性都有所上升。這是因為隨著節(jié)點數(shù)目的增加，節(jié)點收齊M個獨立的數(shù)據(jù)包的概率增大。此外，在圖4中，NCPIE算法始終保持著超過97%的傳輸有效性。

圖4　傳輸有效性 vs. 節(jié)點數(shù)

圖5中給出了在不同的節(jié)點數(shù)目(N=10,15)和不同的數(shù)據(jù)包個數(shù)(M=5,15,20)的情況下，傳輸有效性隨稀有度的變化情況。從圖5可以看出，在各種情況下，NCPIE算法的有效性都要要優(yōu)于PIE算法和最少優(yōu)先算法的，并且NCPIE算法的有效性都超過97%，因此，NCPIE算法是最優(yōu)的。

圖5　傳輸有效性 vs.稀有度

4結(jié)語

本文提出了一種基于網(wǎng)絡編碼的協(xié)同點對點信息交換算法來解決無線傳感器網(wǎng)絡中的節(jié)點調(diào)度問題。該算法通過節(jié)點之間的協(xié)同傳輸來提高網(wǎng)絡吞吐量，減少傳輸延遲，改善傳輸有效率。實驗表明，本文所提算法的性能明顯地優(yōu)于PIE算法和最少優(yōu)先算法。

參考文獻：

[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