基于網(wǎng)絡(luò)編碼的無線傳感網(wǎng)F-CS n匯播增益的研究

趙東標

（溫州大學 物理與電子信息工程學院，浙江 溫州 325035）

無線傳感器網(wǎng)絡(luò)（WSNs）現(xiàn)在越來越受到重視，被應(yīng)用到很多領(lǐng)域。這主要依靠于低功耗無線網(wǎng)絡(luò)技術(shù)的進步以及嵌入式計算技術(shù)的快速發(fā)展。然而，WSNs中的各個相互協(xié)調(diào)獨立工作的節(jié)點都是靠有限電量的電池供電并且很難給他充電或者更換電池。除此之外，WSNs中的無線鏈路在傳輸中經(jīng)常會傳送失敗從而需要不斷的重傳，最終導致加速了能量的消耗。據(jù)我們所知WSNs節(jié)點發(fā)送數(shù)據(jù)占據(jù)了能量消耗的主要部分。因此，如何提高能量的利用率和傳輸?shù)目煽啃猿蔀榱藷o線傳感器網(wǎng)絡(luò)的主要工作。

Ahlswede[1]提出通過在中間節(jié)點[1-2]結(jié)合來自不同輸入鏈路的數(shù)據(jù)的網(wǎng)絡(luò)編碼技術(shù)。很多應(yīng)用采用這一種網(wǎng)絡(luò)編碼技術(shù)能夠增加網(wǎng)絡(luò)的吞吐量和減少能量消耗。WSNs的節(jié)點都具有廣播特性的通信交流方式[3-4]，這為使用網(wǎng)絡(luò)編碼技術(shù)提供了天然的條件。網(wǎng)絡(luò)編碼的優(yōu)點和使用條件都滿足于WSNs的需要，所以應(yīng)用網(wǎng)絡(luò)編碼技術(shù)在WSNs中是很有價值的。當前大部分人的研究概括為網(wǎng)絡(luò)編碼輔助的多播和單播，具體應(yīng)用有在線重編程[5]、分布式數(shù)據(jù)存儲與獲取[6]、可靠數(shù)據(jù)傳輸[7]等等。據(jù)我們所知，網(wǎng)絡(luò)編碼在匯播中的研究還有很大的空間。WSNs中匯播模式的典型應(yīng)用就是在一大片區(qū)域內(nèi)布置傳感器節(jié)點，這些節(jié)點獨立的監(jiān)測數(shù)據(jù)經(jīng)過多跳之后匯聚給Sink節(jié)點，，這Sink節(jié)點和源節(jié)點中間的節(jié)點就可以把收到的數(shù)據(jù)進行編碼之后再發(fā)送給Sink節(jié)點。該典型應(yīng)用如圖1所示。

圖1 WSNs中匯播模型Fig.1 The convergecast mode in WSNs

Tang等[8]在文獻中介紹了在匯播中引入線性網(wǎng)絡(luò)編碼的可能性，并從理論上證明了在CSn結(jié)構(gòu)中應(yīng)用線性網(wǎng)絡(luò)編碼能夠產(chǎn)生可靠性增益。本文在此基礎(chǔ)上，提出了一種更具有普遍性、適用性的F-CSn模型，并證明了該模型比CSn模型具有更多的可靠性增益。接下來的內(nèi)容按以下順序給出。第一部分介紹一種F-CSn匯播模型網(wǎng)絡(luò)（完全型）并理論推導其編碼增益以及仿真驗證推導結(jié)果。第二部分將和CSn匯播模型網(wǎng)絡(luò)（非完全型）結(jié)論進行比較和探討。最后第三部分給出結(jié)論和總結(jié)。

1 F-CS n匯播網(wǎng)絡(luò)模型的增益分析和仿真驗證

1.1 F-CS n匯播模型（完全型）介紹

先說明下文中要用到的一些符號含義：Sn發(fā)送數(shù)據(jù)的源節(jié)點、Cn編碼數(shù)據(jù)的中間節(jié)點、實線表示發(fā)送目的節(jié)點、虛線表示能夠偵聽到的節(jié)點、CSn為不完全偵聽模型、F-CSn為完全偵聽模型、Pn為對應(yīng)的n階不完全模型的Sink節(jié)點完全譯碼的概率、FPn為對應(yīng)的n階完全模型的Sink節(jié)點完全譯碼的概率。NPn為不采用網(wǎng)絡(luò)編碼技術(shù)傳輸時對應(yīng)的n階網(wǎng)絡(luò)的Sink節(jié)點能全部接收數(shù)據(jù)的概率。具體網(wǎng)絡(luò)模型如圖2所示。

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

由圖 4可以看出CSn不完全型網(wǎng)絡(luò)模型的編碼節(jié)點只能偵聽到它的子節(jié)點的鄰居節(jié)點，對于子節(jié)點的鄰居節(jié)點以外的節(jié)點偵聽不到數(shù)據(jù)，從而不能把更多的數(shù)據(jù)進行組合編碼。但是Tang等理論推導出CSn的完全接收數(shù)據(jù)的概率，證明了該模型采用網(wǎng)絡(luò)編碼比不采用網(wǎng)絡(luò)編碼是有增益的。然而，在現(xiàn)實無線傳感器網(wǎng)絡(luò)中節(jié)點的偵聽范圍通常不只是鄰居節(jié)點，它能夠偵聽到更多的發(fā)送數(shù)據(jù)。考慮這種情況我們試想如果發(fā)送節(jié)點的數(shù)據(jù)都能夠被編碼節(jié)點給偵聽到并且進行編碼，從而Sink節(jié)點完全解碼出所有數(shù)據(jù)的概率會更高。所以我們提出了具有完全偵聽模式的F-CSn模型網(wǎng)絡(luò)。接下來我們便是證明F-CSn模型網(wǎng)絡(luò)采用網(wǎng)絡(luò)編碼是有增益的并且增益比CSn模型網(wǎng)絡(luò)更多。

1.2 網(wǎng)絡(luò)編碼增益分析和仿真驗證

具體為：

以上是n階通用的網(wǎng)絡(luò)編碼數(shù)學方程，當且僅當編碼系數(shù)矩陣M滿秩時，Sink節(jié)點才能完全譯碼出所有數(shù)據(jù)。本文中采用確定的編碼系數(shù)機制，其編碼規(guī)則為：編碼節(jié)點C1對n個發(fā)送數(shù)據(jù)X的對應(yīng)編碼系數(shù)矩陣為：[1 2 3 4 5… n]，Cn把Cn-1（n≥2）的最后一個編碼碼系數(shù)作為自己的第一個編碼系數(shù)并且把Cn-1的第一個至第n-1個編碼系數(shù)作為自己的第二個至第n個編碼系數(shù)。按此規(guī)則編碼得具體編碼矩陣M為：

很顯然矩陣Mn×n的秩等于n，它表明采用該規(guī)則編碼Sink 節(jié)點是可以完全譯碼的。 當 n=2、3、4 時，M2×2、M3×3、M4×4分別為：

由于WSNs經(jīng)常所處的傳輸環(huán)境不好，所以每條鏈路LSj-Ci都有可能發(fā)送失敗。假設(shè)每條鏈路LSj-Ci的成功傳送率為r（0

接下來要具體求 Sn×n（i）

當 i∈[0，n-1]時，滿秩的矩陣數(shù)量 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中從上到下的順序?qū)懗鏊闶讲⑶蚁旅娴囊獪p去和所有上面相同的種數(shù)，先從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）

很顯然當網(wǎng)絡(luò)不采用網(wǎng)絡(luò)編碼技術(shù)傳輸時的各階完全接收的概率為：NP2=r2×2、NP3=r2×3、NP4=r2×4。 本文還對 F-CS2、FCS3、F-CS4模型分別進行了100萬次的仿真試驗，分別統(tǒng)計了其完全譯碼的概率。下面將給出F-CSn模型仿真結(jié)果和FCSn模型理論推導結(jié)果比較圖（圖5）、F-CSn模型和采用傳統(tǒng)傳輸技術(shù)比較圖（圖6）、F-CSn模型相對于采用傳統(tǒng)傳輸技術(shù)

圖5 仿真和理論比較Fig.5 Comparison between simulation and theory

2 F-CS n和CS n模型網(wǎng)絡(luò)編碼完全解碼的概率比較和探討

如圖 8所示是F-CSn和CSn的完全譯碼概率比較圖。

從圖8我們發(fā)現(xiàn)在同樣的傳送率 r下，F(xiàn)-CSn型完全解碼的概率要高于CSn型。當n=2時，由于網(wǎng)絡(luò)模型相同所以結(jié)果也相同。由圖 5、圖 6、圖8、我們不難看出在相同的傳送率r下，網(wǎng)絡(luò)模型的階數(shù)n越大網(wǎng)絡(luò)完全接收數(shù)據(jù)的概率就越低，這主要是由因子rn決定的。由圖7可以看出網(wǎng)絡(luò)模型的階數(shù)n越大采用網(wǎng)絡(luò)編碼的增益就越高，這是由于編碼節(jié)點具有更多的偵聽機會。然而我們現(xiàn)實網(wǎng)絡(luò)中編碼節(jié)點不可能偵聽無限個發(fā)送節(jié)點也就是說n不是越大越好，在實際應(yīng)用中要根據(jù)需要去確定網(wǎng)絡(luò)規(guī)模從而帶來更高的性價比。

圖6 采用網(wǎng)絡(luò)編碼和不采用比較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 結(jié)束語

本文通過提出F-CSn匯播網(wǎng)絡(luò)模型，理論推導F-CS2、FCS3、F-CS4全部成功譯碼的概率，并仿真驗證理論推導結(jié)果的準確性。而且和不采用網(wǎng)絡(luò)編碼技術(shù)傳輸時進行比較并證明了該模型采用網(wǎng)絡(luò)編碼可以提高網(wǎng)絡(luò)的傳輸可靠性，減少傳輸次數(shù)從而節(jié)約了節(jié)點能量。最后還和CSn模型比較，從而證明了該模型采用網(wǎng)絡(luò)編碼時具有更多的編碼增益，并且該模型更具有普遍性和適用性。網(wǎng)絡(luò)編碼帶來增益的同時也使得節(jié)點的能量開銷增加，接下來的工作就是找到節(jié)點的能量消耗和采用網(wǎng)絡(luò)編碼產(chǎn)生的增益之間的一個平衡點。

[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.