一種結(jié)合網(wǎng)絡(luò)編碼的分發(fā)協(xié)議在無線傳感器網(wǎng)絡(luò)中的應(yīng)用研究

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

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

0 引言

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

小數(shù)據(jù)分發(fā)因其所發(fā)送的數(shù)據(jù)量?。ㄍǔ？赡芫蛶资畟€(gè)字節(jié)），而且數(shù)據(jù)格式往往相差很大，靈活性強(qiáng)，可靠性要求高，因而在實(shí)際傳感器網(wǎng)絡(luò)的操作中會使用單獨(dú)的小數(shù)據(jù)分發(fā)協(xié)議來解決這類需求。針對無線傳感器網(wǎng)絡(luò)小數(shù)據(jù)分發(fā)，國內(nèi)外學(xué)者提出了許多協(xié)議。

Drip[2]協(xié)議把每個(gè)數(shù)據(jù)項(xiàng)都當(dāng)做分發(fā)的單獨(dú)實(shí)體并為每個(gè)數(shù)據(jù)項(xiàng)建立一個(gè)獨(dú)立的Trickle定時(shí)器，提供了很好的粒子性控制，控制何時(shí)以及如何快速地把數(shù)據(jù)項(xiàng)分發(fā)出去。對于每個(gè)數(shù)據(jù)項(xiàng)的每一個(gè)新的版本都單獨(dú)生成一個(gè)概要元組進(jìn)行通知。Drip協(xié)議中的傳輸代價(jià)是和其數(shù)據(jù)項(xiàng)成線性相關(guān)的。即當(dāng)有N個(gè)數(shù)據(jù)項(xiàng)時(shí)，需要有N個(gè)相應(yīng)的概要元組數(shù)據(jù)包進(jìn)行通知。

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

DHV[4]協(xié)議提出了僅僅檢測版本號上的差異，以達(dá)到傳輸盡可能少的數(shù)據(jù)的目的。

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

DIP和DHV將所有數(shù)據(jù)項(xiàng)當(dāng)做一個(gè)群體進(jìn)行分發(fā)，而Drip則是把每個(gè)數(shù)據(jù)項(xiàng)當(dāng)做單一項(xiàng)進(jìn)行分發(fā)，靈活性強(qiáng)，很適合參數(shù)重配置這樣的應(yīng)用場合[5-6]。使用了DIP和DHV協(xié)議的網(wǎng)絡(luò)中的所有節(jié)點(diǎn)在分發(fā)消息之前必須統(tǒng)一固定的數(shù)據(jù)集，在數(shù)據(jù)量小時(shí)容易造成高延時(shí)。盡管DIP和DHV在大規(guī)模數(shù)據(jù)項(xiàng)更新方面優(yōu)勢明顯，但是在小數(shù)據(jù)項(xiàng)更新方面性能不如Drip，并且 DIP、DHV和 BDP都使用了復(fù)雜的算法，計(jì)算復(fù)雜度使得這些協(xié)議需要消耗傳感器節(jié)點(diǎn)更多的內(nèi)存。

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

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

1 網(wǎng)絡(luò)編碼分發(fā)方式分析

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

1.1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

假定節(jié)點(diǎn)的廣播半徑為 R，D為相鄰兩節(jié)點(diǎn)之間的距離[9],[13]。當(dāng)D>R時(shí)，源節(jié)點(diǎn)發(fā)出的數(shù)據(jù)包將不會到達(dá)目標(biāo)節(jié)點(diǎn)；當(dāng) D≤R<2D時(shí)，源節(jié)點(diǎn)發(fā)出的數(shù)據(jù)包將逐跳傳輸?shù)礁鱾€(gè)節(jié)點(diǎn)，整個(gè)網(wǎng)絡(luò)形成一個(gè)多跳的結(jié)構(gòu)；當(dāng)3D>R≧2D時(shí)，源節(jié)點(diǎn)發(fā)送一次數(shù)據(jù)包，1跳范圍內(nèi)和 2跳范圍內(nèi)的節(jié)點(diǎn)都會收到此數(shù)據(jù)包，第1跳中的節(jié)點(diǎn)在轉(zhuǎn)發(fā)此數(shù)據(jù)包時(shí)2跳中的節(jié)點(diǎn)將收到大量重復(fù)數(shù)據(jù)包，這將嚴(yán)重降低網(wǎng)絡(luò)的性能。同理，當(dāng)R≧3D時(shí)，網(wǎng)絡(luò)將產(chǎn)生更多的重復(fù)數(shù)據(jù)包，如此類推。本課題討論的無線傳感器網(wǎng)絡(luò)如圖1所示。

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.1 Network topology

1.2 網(wǎng)絡(luò)編碼分發(fā)方式的增益分析

為方便起見，這里只討論一跳范圍內(nèi)的數(shù)據(jù)分發(fā)[10]。假設(shè)一個(gè)源節(jié)點(diǎn)S向兩個(gè)普通節(jié)點(diǎn)R1和R2分發(fā)N個(gè)數(shù)據(jù)項(xiàng)，源節(jié)點(diǎn)S到R1和R2的丟包率分別為 P1和 P2，且 P1

方式A（非網(wǎng)絡(luò)編碼分發(fā)方式）：當(dāng)一個(gè)節(jié)點(diǎn)在當(dāng)前時(shí)隙丟失一個(gè)數(shù)據(jù)包并且先前時(shí)隙從未完整接收到該數(shù)據(jù)包時(shí)，立即發(fā)送一個(gè) NAK消息給源節(jié)點(diǎn)，源節(jié)點(diǎn)根據(jù)丟包再進(jìn)行重傳恢復(fù)。

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

圖2 網(wǎng)絡(luò)編碼方式Fig.2 Network Coding

根據(jù)以上假設(shè)，分發(fā)N個(gè)數(shù)據(jù)項(xiàng)，接收節(jié)點(diǎn)只有兩個(gè)的情況下，方式A所需發(fā)送的信息量為：

方式B需要發(fā)送的信息量為：

當(dāng)接收節(jié)點(diǎn)數(shù)量為M時(shí)，

使用網(wǎng)絡(luò)編碼的分發(fā)方式相比非網(wǎng)絡(luò)編碼方式，同樣情況下分發(fā)更少的數(shù)據(jù)，更有效率，可靠性和實(shí)時(shí)性更好。

2 NCDP的實(shí)現(xiàn)

2.1 NCDP思想

NCDP使用了Trickle算法用來控制消息分發(fā)的速率，并隨機(jī)發(fā)送編碼包和原始數(shù)據(jù)包。因?yàn)椴焕猛負(fù)湫畔頉Q定哪些消息需要編碼，因此可以減少路由控制方面的資源開銷，降低延遲，使用網(wǎng)絡(luò)編碼提高了可靠性。相對于其它使用了復(fù)雜編碼操作的分發(fā)協(xié)議，考慮到異或操作往往作為一種硬件功能集成在CPU中這一現(xiàn)成優(yōu)勢，于是NCDP將用簡單的異或操作用于編解碼[9,15]。

2.2 NCDP設(shè)計(jì)

NCDP是在已有分發(fā)協(xié)議Drip的基礎(chǔ)上增加網(wǎng)絡(luò)編碼的功能，對Drip協(xié)議中原有的相關(guān)數(shù)據(jù)幀和數(shù)據(jù)發(fā)送與接收的功能進(jìn)行重新設(shè)計(jì)。

（1）相關(guān)數(shù)據(jù)幀定義

數(shù)據(jù)幀格式定義如圖3所示：

圖3 數(shù)據(jù)幀定義Fig.3 Data frame definition

分發(fā)消息幀格式定義如圖4所示：

圖4 分發(fā)消息幀定義Fig.4 Dissemination message frame definition

其中，Idi和 Idj分別為編碼包所包含的源數(shù)據(jù)項(xiàng)Id，Data為想要分發(fā)的原始數(shù)據(jù)項(xiàng)，NoteId為節(jié)點(diǎn)Id。

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

圖5 原始數(shù)據(jù)Fig.5 Raw data

（2）接收與發(fā)送功能設(shè)計(jì)

NCDP數(shù)據(jù)接收與分發(fā)過程流程圖如圖6所示。

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

當(dāng)接收到的消息是編碼包時(shí)，先利用已接收到的原始數(shù)據(jù)對其進(jìn)行解碼，如果解碼出另一個(gè)原始數(shù)據(jù)則存儲解碼出來的原始數(shù)據(jù)并將該編碼包刪除。如果該編碼包無法解碼出原始數(shù)據(jù)，則將其先存儲到編碼包區(qū)，等待下一次解碼。

如果當(dāng)原始數(shù)據(jù)區(qū)的數(shù)據(jù)對應(yīng)的Trickle定時(shí)器觸發(fā)時(shí)將該數(shù)據(jù)與其它已接收到的原始數(shù)據(jù)進(jìn)行隨機(jī)編碼然后發(fā)送該編碼包給其它鄰居節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)接收到的數(shù)據(jù)為原始數(shù)據(jù)并且該數(shù)據(jù)已存儲在原始數(shù)據(jù)區(qū)時(shí)，說明有其它節(jié)點(diǎn)正在發(fā)送該原始數(shù)據(jù)給鄰居節(jié)點(diǎn)，沒必要再發(fā)送給對方，因此將該原始數(shù)據(jù)對應(yīng)的Trickle定時(shí)器定時(shí)間隔翻倍，避免重復(fù)發(fā)送冗余信息，減輕網(wǎng)絡(luò)擁塞。

圖6 NCDP數(shù)據(jù)接收與分發(fā)過程流程圖Fig.6 Process flow chart of data receiving and distribution of NCDP

（3）隨機(jī)編碼算法

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

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

隨機(jī)編碼步驟如下：

步驟 1.判斷是否是原始數(shù)據(jù)，是的話進(jìn)入步驟2，不是的話進(jìn)入步驟7；

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

步驟 3.判斷兩個(gè)編碼對象是不是同一個(gè)原始數(shù)據(jù)項(xiàng)，不是的話進(jìn)入步驟6，是的話進(jìn)入步驟6；

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

步驟5.異或編碼并進(jìn)入步驟6；

步驟6.發(fā)送并進(jìn)入步驟7；

步驟7.結(jié)束。

3 仿真實(shí)驗(yàn)

接下來我們將通過一系列實(shí)驗(yàn)來評估NCDP的各項(xiàng)性能。本論文使用的仿真工具是 TOSSIM，TOSSIM 是 TinyOS自帶的仿真器，專門用來仿真TinyOS的應(yīng)用，可以支持大規(guī)模的網(wǎng)絡(luò)仿真，而且其仿真代碼和實(shí)際的傳感器節(jié)點(diǎn)運(yùn)行的代碼一樣，具有高可信度。TinyOS則是一款專門為無線傳感器網(wǎng)絡(luò)而開發(fā)的開源嵌入式操作系統(tǒng)，廣泛應(yīng)用于物聯(lián)網(wǎng)領(lǐng)域。

3.1 評估指標(biāo)

實(shí)驗(yàn)過程中隨機(jī)產(chǎn)生節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)洌?jié)點(diǎn)間兩兩連接，為確保仿真的可信度，每個(gè)節(jié)點(diǎn)都加載了噪聲道模型，每個(gè)實(shí)驗(yàn)仿真10次，并選取數(shù)據(jù)的均值作為實(shí)驗(yàn)結(jié)果。我們使用以下指標(biāo)來評估NCDP的性能。

效率：通過網(wǎng)絡(luò)總的消息分發(fā)量來衡量效率。

可靠性：通過已接收到所有數(shù)據(jù)的節(jié)點(diǎn)百分比來評估可靠性。

分發(fā)速度：通過所有節(jié)點(diǎn)接收到所有消息的延遲時(shí)間來評估分發(fā)速度。

3.2 性能評估

第一組實(shí)驗(yàn)，通過對比 NCDP、Drip、DIP和DHV在不同節(jié)點(diǎn)數(shù)量下分發(fā)20個(gè)數(shù)據(jù)項(xiàng)時(shí)，網(wǎng)絡(luò)中總的消息發(fā)送量來評估其分發(fā)效率。根據(jù)Roofnet[8]項(xiàng)目，一般真實(shí)環(huán)境中一對收發(fā)節(jié)點(diǎn)有50%的丟包率，因此為提高可信度設(shè)置網(wǎng)絡(luò)的丟包率為50%，實(shí)驗(yàn)結(jié)果如圖8所示。

由圖8可以看出，我們可以發(fā)現(xiàn)在不同節(jié)點(diǎn)數(shù)量的網(wǎng)絡(luò)中NCDP發(fā)送量總要比Drip和DHV低，但比DIP高。雖然DIP分發(fā)速度更快，但是因?yàn)樯婕皬?fù)雜的哈希樹使得DIP相比NCDP更消耗內(nèi)存。

圖8 分發(fā)效率評估Fig.8 Dissemination efficiency assessment

圖9 分發(fā)延遲評估Fig.9 Dissemination delay assessment

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

3.3 緩存占用分析

第三組實(shí)驗(yàn)，我們將評估在分發(fā)過程中 NCDP每個(gè)節(jié)點(diǎn)所占用的緩存大小，如圖10所示[15]。通過在網(wǎng)絡(luò)中隨機(jī)布置100個(gè)節(jié)點(diǎn)，發(fā)送100個(gè)數(shù)據(jù)項(xiàng)。圖 10的 X軸表示節(jié)點(diǎn)所占用的最大緩存大小，Y軸表示落在相應(yīng)緩存大小的節(jié)點(diǎn)數(shù)量。由圖10可以看出大部分節(jié)點(diǎn)只使用了不超過 36個(gè)字節(jié)大小的緩存，最大的緩存大小為84個(gè)字節(jié)。圖10中的折線圖顯示網(wǎng)絡(luò)中 80%的節(jié)點(diǎn)使用了最大為 36個(gè)字節(jié)大小的緩存。

第四組實(shí)驗(yàn)，我們評估分發(fā)數(shù)據(jù)量對內(nèi)存占用的影響，如圖 11所示。實(shí)驗(yàn)中，我們通過分發(fā) 10到100個(gè)數(shù)據(jù)項(xiàng)，每組實(shí)驗(yàn)按10個(gè)數(shù)據(jù)項(xiàng)遞增，隨機(jī)布置100個(gè)節(jié)點(diǎn)到網(wǎng)絡(luò)中。由圖11可以看出盡管最大的內(nèi)存占用隨著分發(fā)數(shù)據(jù)項(xiàng)數(shù)量增多而激增，但是緩沖區(qū)的均值卻比較平穩(wěn)。甚至如果我們增加網(wǎng)絡(luò)的分發(fā)數(shù)據(jù)量時(shí)，實(shí)際緩存的開銷并不像編碼包數(shù)量那么多，因?yàn)榫幋a包一旦解碼成功就被刪除了，不會一直占用著空間。

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

3.4 編碼率與抑制率分析

由于NCDP使用了Trickle算法和網(wǎng)絡(luò)編碼，因此如何設(shè)置編碼率和抑制率使得NCDP能發(fā)揮出最大的性能，將是接下來兩組實(shí)驗(yàn)中所要研究的。

第四組實(shí)驗(yàn)，我們在一個(gè)隨機(jī)布置有100個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中分發(fā)10個(gè)數(shù)據(jù)項(xiàng)，NCDP在不同編碼率下所需分發(fā)的消息數(shù)和網(wǎng)絡(luò)的分發(fā)用時(shí)，如圖12和圖13所示。由圖12和圖13可觀察出，將編碼率設(shè)置為30%-60%比較合適。

第五組實(shí)驗(yàn)，我們在一個(gè)隨機(jī)布置有100個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中分發(fā)10個(gè)數(shù)據(jù)項(xiàng)，NCDP在不同抑制率下所需分發(fā)的消息數(shù)和網(wǎng)絡(luò)的分發(fā)用時(shí)，如圖14和圖15所示。由圖14和圖15可以看出將抑制率設(shè)置為50%比較合適。

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

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

4 結(jié)論

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

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

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

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

[1] 潘浩, 董齊芬, 張貴軍, 等. 無線傳感器網(wǎng)絡(luò)操作系統(tǒng)TinyOS[M]. 北京: 清華大學(xué)出版社, 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] 閆彩芹, 方群. 基于能量敏感的無線傳感器網(wǎng)絡(luò)信任度計(jì)算模型[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] 周唯, 劉冬, 劉會師. 基于無線傳感器網(wǎng)絡(luò)拓?fù)涞难芯颗c設(shè)計(jì)[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] 鄭軍、張寶賢 編著. 無線傳感器網(wǎng)絡(luò)技術(shù)[M]. 北京: 機(jī)械工業(yè)出版社, 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] 趙欣榮, 肖迎元, 王曉曄, 等. 無線傳感器網(wǎng)絡(luò)多路徑聚集的改進(jìn)[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] 呂占偉, 陶崢. 重傳下的無線傳感器網(wǎng)絡(luò)的生命周期分析[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.