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

韓最蛟，袁國(guó)賢，柳國(guó)光

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

?

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

韓最蛟，袁國(guó)賢，柳國(guó)光

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

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

關(guān)鍵詞：WSN；網(wǎng)絡(luò)編碼；信息交換；點(diǎn)對(duì)點(diǎn)

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

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

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

1問題建模

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

(1)

(2)

(3)

滿足以下條件：

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

(4)

(5)

(6)

(7)

(8)

E∈Z+

(9)

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

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

表1　符號(hào)表

2算法設(shè)計(jì)

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

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

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

(10)

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

(11)

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

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

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

3仿真分析

(12)

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

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

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

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

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

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

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

4結(jié)語

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

參考文獻(xiàn)：

[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

作者簡(jiǎn)介：韓最蛟(1963—)，男，副教授，從事計(jì)算機(jī)應(yīng)用技術(shù)、電子政務(wù)、遙感技術(shù)、應(yīng)用物理等應(yīng)用研究。

中圖分類號(hào)：TP212.9

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-4210-(2016)03-099-08