基于網絡編碼的無線傳感網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.