一種結合網絡編碼的分發協議在無線傳感器網絡中的應用研究

黃名鈿，黎 英，高 偉，張金飛

（昆明理工大學 信息工程與自動化學院，云南 昆明 650500）

0 引言

無線傳感器網絡（WSN）一般由大量部署在信號監測區的集傳感、計算和無線通信功能于一身的微型傳感器節點組成，這些節點通過無線通信的方式形成一個多跳的自組織網絡。無線傳感器網絡中，將節點相關參數更新的過程稱為小數據分發[1]。不同于傳感數據，配置參數對一個網絡的重要性不言而喻，如果不能保證網絡中所有節點的配置參數一致的話，很可能導致整個網絡癱瘓。對部署在無人看管區域的無線傳感器網絡而言，如何高效和可靠地實現對傳感器網絡中的應用程序進行參數配置是一個具有很強應用需求的問題。一種最簡單的想法是將所有部署好的節點收集回來重新進行參數或程序的修改，但這種方式需要耗費大量的人力和時間，在實際應用中可操作性不強，因此研究能夠遠程將所需要配置的參數可靠地分發到傳感器節點的方法具有非常重要的意義。

小數據分發因其所發送的數據量小（通常可能就幾十個字節），而且數據格式往往相差很大，靈活性強，可靠性要求高，因而在實際傳感器網絡的操作中會使用單獨的小數據分發協議來解決這類需求。針對無線傳感器網絡小數據分發，國內外學者提出了許多協議。

Drip[2]協議把每個數據項都當做分發的單獨實體并為每個數據項建立一個獨立的Trickle定時器，提供了很好的粒子性控制，控制何時以及如何快速地把數據項分發出去。對于每個數據項的每一個新的版本都單獨生成一個概要元組進行通知。Drip協議中的傳輸代價是和其數據項成線性相關的。即當有N個數據項時，需要有N個相應的概要元組數據包進行通知。

DIP[3]協議采取將所有數據項借助哈希樹的數據結構壓縮到一個概要數據包中，這樣只需比較根節點數據就可以判斷是否有數據項需要更新。采用這種方案，可在O（1）時間內作出是否有新的數據項需要更新的判斷。然而，由于這種機制將所有的通知都壓縮到一個數據包中，無法給出具體哪個數據包需要更新，并且涉及到復雜的算法，需要耗費更多的內存。

DHV[4]協議提出了僅僅檢測版本號上的差異，以達到傳輸盡可能少的數據的目的。

BDP[7]協議采用了布隆過濾這一數據結構作為壓縮存儲數據項元數據信息的工具，能快速識別出具有相同鍵值的數據項間的版本差異，并且在保證全網范圍內數據項的一致性上具有非常高的可靠性。然而由于布隆過濾天生的缺點可能導致出現假陽性判定錯誤概率，BDP的設計沒有考慮無線傳感器網絡的特點，其長度遠遠大于無線傳感器網絡中消息的大小，此外BDP協議應用不當可能引起死鎖。

DIP和DHV將所有數據項當做一個群體進行分發，而Drip則是把每個數據項當做單一項進行分發，靈活性強，很適合參數重配置這樣的應用場合[5-6]。使用了DIP和DHV協議的網絡中的所有節點在分發消息之前必須統一固定的數據集，在數據量小時容易造成高延時。盡管DIP和DHV在大規模數據項更新方面優勢明顯，但是在小數據項更新方面性能不如Drip，并且 DIP、DHV和 BDP都使用了復雜的算法，計算復雜度使得這些協議需要消耗傳感器節點更多的內存。

網絡編碼[8]（NC）是編碼技術中的一種，于2000年提出，是一種通過將接收到的數據包進行編碼使得在增加傳輸信息量的同時減少網絡中數據包的技術。它推翻了網絡中獨立比特不能再被壓縮的經典結論，理論上能使源與組播成員間達到最大流最小割的組播速率，在解決網絡擁塞，提高傳輸可靠性方面效果顯著。

針對像配置參數這樣的小數據分發，因其數據量小、數據量數目有限、數據格式差異大、要求高可靠性的特點和傳感器節點本身資源有限的實際情況，并不適合使用采用復雜算法的小數據分發協議。因此我們結合Drip協議和網絡編碼技術的優點，采取一種以空間換時間的思路，在Drip協議的基礎上使用網絡編碼，對其進行改進，提出一種改進的基于網絡編碼的無線傳感器網絡小數據分發協議，用以改善小數據分發在延遲和可靠性方面的性能[12]。以下為方便闡述，簡稱該改進協議為NCDP 。

1 網絡編碼分發方式分析

Drip使用了線性掃描來輔助發現具有不同版本號的數據項。僅當某個節點發現鄰居節點上有舊的數據項時，才由前者對后者上的舊數據項進行更新，從而避免了重復傳輸。然而為了保證全網范圍內數據項版本的一致性，對于每一數據項，每個節點都必須周期性地向周圍鄰居廣播相關的版本信息。一旦節點發現周圍存在不同版本的數據，就需要發送更多的消息與鄰居協同，從而識別出哪個節點上的數據具有更新的版本號。在數據項數量較多時，如果處理不當，上述過程將造成大量的通信開銷，既浪費了節點上寶貴的能量，也占用了有限的帶寬資源。因此，如何保持該協議性能的前提下，同時降低協議開銷，是本課題的一項挑戰。接下來，將通過對網絡編碼模式進行分析，證明網絡編碼這一技術的可行性。

1.1 網絡拓撲結構

假定節點的廣播半徑為 R，D為相鄰兩節點之間的距離[9],[13]。當D>R時，源節點發出的數據包將不會到達目標節點；當 D≤R<2D時，源節點發出的數據包將逐跳傳輸到各個節點，整個網絡形成一個多跳的結構；當3D>R≧2D時，源節點發送一次數據包，1跳范圍內和 2跳范圍內的節點都會收到此數據包，第1跳中的節點在轉發此數據包時2跳中的節點將收到大量重復數據包，這將嚴重降低網絡的性能。同理，當R≧3D時，網絡將產生更多的重復數據包，如此類推。本課題討論的無線傳感器網絡如圖1所示。

圖1 網絡拓撲結構Fig.1 Network topology

1.2 網絡編碼分發方式的增益分析

為方便起見，這里只討論一跳范圍內的數據分發[10]。假設一個源節點S向兩個普通節點R1和R2分發N個數據項，源節點S到R1和R2的丟包率分別為 P1和 P2，且 P1

方式A（非網絡編碼分發方式）：當一個節點在當前時隙丟失一個數據包并且先前時隙從未完整接收到該數據包時，立即發送一個 NAK消息給源節點，源節點根據丟包再進行重傳恢復。

方式B（網絡編碼方式）：該方式與方式A相似，如果普通節點不能正確接收到數據包將會立即發送NAK消息給源節點。不同之處在于源節點需要等到所有數據包都發送出去之后才開始進行重傳恢復。同時，源節點維護有一張表，表中包含R1和R2相應丟的數據包的Id，如圖2所示。重傳過程中，先將兩者都缺失的數據包進行異或操作然后分發出去，R1和R2接收到編碼包之后根據先前已接收到的數據包進行恢復。特別的是，對于兩者同時缺失的數據包在重傳的時候不再進行異或操作。對于圖2的例子，源節點在重傳階段發送的編碼包為a1a3⊕，a4a5⊕，a6，a8。R1通過a3⊕（a1a3⊕）恢復丟失的數據包a1，R2通過a1⊕（a1a3⊕）恢復丟失的數據包 a3。由于 R1和R2同時丟失 a6，因此不對a6進行異或編碼。最后，由于只有R1丟失a8，所以也不用進行異或編碼。

圖2 網絡編碼方式Fig.2 Network Coding

根據以上假設，分發N個數據項，接收節點只有兩個的情況下，方式A所需發送的信息量為：

方式B需要發送的信息量為：

當接收節點數量為M時，

使用網絡編碼的分發方式相比非網絡編碼方式，同樣情況下分發更少的數據，更有效率，可靠性和實時性更好。

2 NCDP的實現

2.1 NCDP思想

NCDP使用了Trickle算法用來控制消息分發的速率，并隨機發送編碼包和原始數據包。因為不利用拓撲信息來決定哪些消息需要編碼，因此可以減少路由控制方面的資源開銷，降低延遲，使用網絡編碼提高了可靠性。相對于其它使用了復雜編碼操作的分發協議，考慮到異或操作往往作為一種硬件功能集成在CPU中這一現成優勢，于是NCDP將用簡單的異或操作用于編解碼[9,15]。

2.2 NCDP設計

NCDP是在已有分發協議Drip的基礎上增加網絡編碼的功能，對Drip協議中原有的相關數據幀和數據發送與接收的功能進行重新設計。

（1）相關數據幀定義

數據幀格式定義如圖3所示：

圖3 數據幀定義Fig.3 Data frame definition

分發消息幀格式定義如圖4所示：

圖4 分發消息幀定義Fig.4 Dissemination message frame definition

其中，Idi和 Idj分別為編碼包所包含的源數據項Id，Data為想要分發的原始數據項，NoteId為節點Id。

NCDP協議數據幀格式由包含編碼包信息的頭部和包含被編碼的消息主體Data組成。由于解碼過程需要知道編碼包由哪些原始數據包組成，因此編碼包頭部包含了若干個原始數據包的編號，代表該編碼包由幾個原始數據包編碼而成，每個編號占據一個字節大小，如果數據項超過256個，可以相應地對編號占據的字節數進行擴展。當數據包需要發送時，節點會將數據包幀添加到分發消息幀中，并在分發消息幀中添加上本節點的 NoteId。當數據幀中Idj為0，代表這是一個原始數據，如圖5所示。

圖5 原始數據Fig.5 Raw data

（2）接收與發送功能設計

NCDP數據接收與分發過程流程圖如圖6所示。

當接收到消息時，如果該消息包為原始數據包，那么就將消息存入原始數據存儲區，并和已接收到的編碼包輪流進行解碼操作，嘗試解碼出其它原始數據。如果解碼成功則將解碼出來的原始數據先存儲進原始數據區，然后刪除和其成功進行解碼操作的編碼包，重復此過程直到無法再解碼出新的原始數據。

當接收到的消息是編碼包時，先利用已接收到的原始數據對其進行解碼，如果解碼出另一個原始數據則存儲解碼出來的原始數據并將該編碼包刪除。如果該編碼包無法解碼出原始數據，則將其先存儲到編碼包區，等待下一次解碼。

如果當原始數據區的數據對應的Trickle定時器觸發時將該數據與其它已接收到的原始數據進行隨機編碼然后發送該編碼包給其它鄰居節點。當節點接收到的數據為原始數據并且該數據已存儲在原始數據區時，說明有其它節點正在發送該原始數據給鄰居節點，沒必要再發送給對方，因此將該原始數據對應的Trickle定時器定時間隔翻倍，避免重復發送冗余信息，減輕網絡擁塞。

圖6 NCDP數據接收與分發過程流程圖Fig.6 Process flow chart of data receiving and distribution of NCDP

（3）隨機編碼算法

為了降低延遲，NCDP使用隨機編碼算法對數據包進行隨機編碼，而不是等待所有原始數據都分發出去之后才進行重傳恢復。隨機編碼流程如圖 7所示。其中rand_num為生成的16位隨機數，COMB為隨機編碼概率，MAX_STORE為原始數據存儲區最大存儲量。next_content表示當前原始數據存儲區存放的數據項數量，初始值為 0，每添加一個原始數據項自加1。

圖7 隨機編碼算法流程圖Fig.7 Flow chart of random coding algorithm

隨機編碼步驟如下：

步驟 1.判斷是否是原始數據，是的話進入步驟2，不是的話進入步驟7；

步驟 2.判斷是否小于編碼率，是的話進行步驟3，不是的話進入步驟6；

步驟 3.判斷兩個編碼對象是不是同一個原始數據項，不是的話進入步驟6，是的話進入步驟6；

步驟 4.判斷是否有其它原始數據可以與自身進行編碼，是的話進入步驟5，不是的話進入步驟6；

步驟5.異或編碼并進入步驟6；

步驟6.發送并進入步驟7；

步驟7.結束。

3 仿真實驗

接下來我們將通過一系列實驗來評估NCDP的各項性能。本論文使用的仿真工具是 TOSSIM，TOSSIM 是 TinyOS自帶的仿真器，專門用來仿真TinyOS的應用，可以支持大規模的網絡仿真，而且其仿真代碼和實際的傳感器節點運行的代碼一樣，具有高可信度。TinyOS則是一款專門為無線傳感器網絡而開發的開源嵌入式操作系統，廣泛應用于物聯網領域。

3.1 評估指標

實驗過程中隨機產生節點的網絡拓撲，節點間兩兩連接，為確保仿真的可信度，每個節點都加載了噪聲道模型，每個實驗仿真10次，并選取數據的均值作為實驗結果。我們使用以下指標來評估NCDP的性能。

效率：通過網絡總的消息分發量來衡量效率。

可靠性：通過已接收到所有數據的節點百分比來評估可靠性。

分發速度：通過所有節點接收到所有消息的延遲時間來評估分發速度。

3.2 性能評估

第一組實驗，通過對比 NCDP、Drip、DIP和DHV在不同節點數量下分發20個數據項時，網絡中總的消息發送量來評估其分發效率。根據Roofnet[8]項目，一般真實環境中一對收發節點有50%的丟包率，因此為提高可信度設置網絡的丟包率為50%，實驗結果如圖8所示。

由圖8可以看出，我們可以發現在不同節點數量的網絡中NCDP發送量總要比Drip和DHV低，但比DIP高。雖然DIP分發速度更快，但是因為涉及復雜的哈希樹使得DIP相比NCDP更消耗內存。

圖8 分發效率評估Fig.8 Dissemination efficiency assessment

圖9 分發延遲評估Fig.9 Dissemination delay assessment

第二組實驗，對比NCDP、Drip、DIP和DHV的分發延遲，如圖9所示。圖9展示了隨機布置100個節點，分發20個數據項，節點完成率所對應的時間。由圖9可以看出，Drip、DIP和DHV剛開始時丟包率比較嚴重，因為分發起始階段只有少數的節點傳輸數據，許多數據包丟失了。相比之下，得益于網絡編碼，NCDP在起始階段，即使只有少數的節點在傳輸消息，數據仍然傳播到網絡中的絕大部分。由圖9我們還可以看出最后一兩個節點往往導致整個網絡大范圍延遲，NCDP的網絡延遲比Drip、DIP和DHV更低。這是因為當一些節點沒能收到最后的消息時，使用了Drip、DIP和DHV的節點只能等待其它節點給它發送消息，這樣造成極大的延遲。相比之下，使用了NCDP的節點能通過解碼已接收到的編碼包來提高接收到最后一個數據項的可能性，降低延遲。由圖 8和圖 9，我們可以得出這樣一個結論：NCDP總體比Drip、DIP和DHV更快分發、更可靠和更有效率。

3.3 緩存占用分析

第三組實驗，我們將評估在分發過程中 NCDP每個節點所占用的緩存大小，如圖10所示[15]。通過在網絡中隨機布置100個節點，發送100個數據項。圖 10的 X軸表示節點所占用的最大緩存大小，Y軸表示落在相應緩存大小的節點數量。由圖10可以看出大部分節點只使用了不超過 36個字節大小的緩存，最大的緩存大小為84個字節。圖10中的折線圖顯示網絡中 80%的節點使用了最大為 36個字節大小的緩存。

第四組實驗，我們評估分發數據量對內存占用的影響，如圖 11所示。實驗中，我們通過分發 10到100個數據項，每組實驗按10個數據項遞增，隨機布置100個節點到網絡中。由圖11可以看出盡管最大的內存占用隨著分發數據項數量增多而激增，但是緩沖區的均值卻比較平穩。甚至如果我們增加網絡的分發數據量時，實際緩存的開銷并不像編碼包數量那么多，因為編碼包一旦解碼成功就被刪除了，不會一直占用著空間。

圖10 緩存占用評估Fig.10 Cache occupancy assessment

3.4 編碼率與抑制率分析

由于NCDP使用了Trickle算法和網絡編碼，因此如何設置編碼率和抑制率使得NCDP能發揮出最大的性能，將是接下來兩組實驗中所要研究的。

第四組實驗，我們在一個隨機布置有100個節點的網絡中分發10個數據項，NCDP在不同編碼率下所需分發的消息數和網絡的分發用時，如圖12和圖13所示。由圖12和圖13可觀察出，將編碼率設置為30%-60%比較合適。

第五組實驗，我們在一個隨機布置有100個節點的網絡中分發10個數據項，NCDP在不同抑制率下所需分發的消息數和網絡的分發用時，如圖14和圖15所示。由圖14和圖15可以看出將抑制率設置為50%比較合適。

圖11 最大緩存與均值緩存Fig.11 Maximum caching and mean caching

圖12 編碼率與分發效率Fig.12 Coding rate and dissemination efficiency

4 結論

圖13 編碼率與分發延遲Fig.13 Coding rate and distribution delay

圖14 抑制率與分發效率Fig.14 Inhibition rate and dissemination efficiency

圖15 抑制率與分發延遲Fig.15 Inhibition rate and dissemination delay

本文給出了針對現有小數據分發協議在無線傳感器網絡參數重配置場合下的不足之處，以空間換時間的思路，通過對Drip協議使用網絡編碼技術并對其中收發數據功能進行改進，提出 NCDP。盡管NCDP需要額外的空間用于存儲消息包的版本號和額外的緩存用來存儲編碼包。不過這些開銷可以通過指定最大編碼數和最大緩存空間來控制。通過多次仿真實驗研究結果表明，NCDP相比Drip和DHV，在同樣情況下只需發送更少的消息。盡管在同樣情況下NCDP發送的消息包多于DIP，但是相比DIP它可靠性更好。總的來說，NCDP相比 Drip、DIP和 DHV在小數據分發實時性和可靠性總體性能方面有一定提高。

[1] 潘浩, 董齊芬, 張貴軍, 等. 無線傳感器網絡操作系統TinyOS[M]. 北京: 清華大學出版社, 2011.4.PAN H, DONG Q F, ZHANG G J et al. Wireless Sensor Network Operating System[M]. Beijing: Tsinghua university press, 2011.4

[2] Tolle G, Culler D. Design of an application cooperative management system for wireless sensor network[C]. Istanbul,Turkey: Sencond European Workshop on Wireless Sensor Networks (EWSN), 2005, 121-132.

[3] Lin K., Levis P. Data discovery and dissemination with dip[C]. Washington DC, USA: Proceedings of the 7th International Conference on Information Processing in Sensor,2008, 433-444.

[4] Dang T., Bulusu N., Feng W. C., et al. DHV: A Code Consistency Maintenance Protocol for Multi-hop Wireless Sensor Networks[C]. Cork, Ireland: Wireless Sensor Networks, 6th European Conference, 2009, 327-342.

[5] 閆彩芹, 方群. 基于能量敏感的無線傳感器網絡信任度計算模型[J]. 軟件, 2012, 33(4): 84-88.YAN C Q, FAN Q. A Model of Reliability Calculation of Wireless Sensor Network Based on Energy[J] Sensitivity.Software, 2012, 33(4): 84-88.

[6] 周唯, 劉冬, 劉會師. 基于無線傳感器網絡拓撲的研究與設計[J]. 軟件, 2013, 34(12): 22-25.ZHOU W, LIU D, LIU H S. Research and Design of Wireless Sensor Network Topology[J]. Software, 2013, 34(12): 22-25.

[7] Chen Tao, Guo Deke. A Bloom filters based dissemination protocol in wireless sensor networks[J]. Ad Hoc Network,2013, 11: 1359-1371.

[8] Ahlswede R., Cai N., Li S. Y., et al. Network information flow[C]. Inf. Theory IEEE Trans, 2000, 46(4): 1204-1216.

[9] 鄭軍、張寶賢 編著. 無線傳感器網絡技術[M]. 北京: 機械工業出版社, 2012.ZHENG J, ZHANG B X. Wireless Sensor Network Technology[M]. Beijing: Mechanical industry press, 2012.

[10] Wang Xiumin, Wang Jianping, Xu Yinlong. Data Dissemination in Wireless Sensor Networks with Network Coding[J].EURASIP Journal on Wireless Communications and Networking, 2010, 2010: 14-30.

[11] Nildo dos Santos Ribeiro Júnior. CodeDrip: Improving data dissemination for wireless sensor networks with network coding[J]. Ad Hoc Network. 2017, 54: 42-52.

[12] Doddavenkatappa M., Chan M. C., Leong B. Splash: fast data dissemination with constructive interference in wireless sensor networks[C], Lombard: The 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13), 2013, 269-282.

[13] Gao Y., Bu J., Dong W., et al. Exploiting concurrency for efficient dissemination in wireless sensor networks[C], New York:IEEE Transactions on Parallel and Distributed Systems,2013, 24(4): 691-700.

[14] 趙欣榮, 肖迎元, 王曉曄, 等. 無線傳感器網絡多路徑聚集的改進[J]. 軟件, 2014, 35(7): 7-12.ZHAO X R, XIAO Y Y, WANG X Y. Improvement of Multi-path Aggregation of Wireless Sensor Networks[J].Software, 2014, 35(7): 7-12.

[15] 呂占偉, 陶崢. 重傳下的無線傳感器網絡的生命周期分析[J]. 軟件, 2015, 36(1): 116-121.LU Z W, TAO Z. Life Cycle Analysis of Wireless Sensor Networks under Retransmission[J]. Software, 2015, 36(1):116-121.