康照玲，徐芹寶，王昌達(dá)

(江蘇大學(xué) 計算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江212013)(*通信作者電子郵箱changda@ujs.edu.cn)

0 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network， WSN)使用范圍非常廣泛，如環(huán)境監(jiān)測、智能電網(wǎng)等[1]。在WSN中，節(jié)點(diǎn)間相互協(xié)作，實時監(jiān)測、感知、采集物理世界的信息，并將這些信息處理為計算機(jī)所能識別的數(shù)據(jù)，通過一跳或多跳的方式傳輸?shù)交?Base Station， BS)[2]。由于傳感器節(jié)點(diǎn)容易受外界環(huán)境的影響，數(shù)據(jù)在傳輸?shù)倪^程中可能被損壞，這就需要對數(shù)據(jù)進(jìn)行可信性分析。溯源(Provenance)是評估數(shù)據(jù)可信性的重要依據(jù)，因為它記錄了傳輸途徑的節(jié)點(diǎn)以及對數(shù)據(jù)的加工處理過程[3-4]。在大規(guī)模傳感器網(wǎng)絡(luò)中，因為數(shù)據(jù)的平均傳輸鏈路較長，所以導(dǎo)致Provenance逐漸增大，進(jìn)而導(dǎo)致數(shù)據(jù)包的過載問題，因此，研究人員提出了分段傳輸Provenance的方法。概率溯源流(Probabilistic Provenance Flow， PPF)[5]是將較大的Provenance分割為一定數(shù)量的片段，每次以給定的概率傳輸溯源分段；偽隨機(jī)噪聲(Pseudo Noise， PN)碼方法[6]則是通過偽噪聲碼將大的Provenance編碼為一系列較小的二進(jìn)制碼塊，通過數(shù)據(jù)包延遲信道傳送。以上兩種方法在全部Provenance分段到達(dá)BS之前無法解碼，所以傳輸?shù)聂敯粜匀?、溯源?shù)據(jù)的利用率低。

針對傳統(tǒng)分段傳輸方法中數(shù)據(jù)利用率低、耗能較高的問題，本文提出一種基于多粒度拓?fù)鋱D的WSN逐級精化溯源(Multi-granularity Topology-based Stepwise Refinement Provenance， MTSRP)方法。多粒度拓?fù)鋱D是指在WSN初始拓?fù)鋱D的基礎(chǔ)上，按一定的規(guī)則將節(jié)點(diǎn)進(jìn)行合并，將同類節(jié)點(diǎn)用一個抽象節(jié)點(diǎn)表示，從而產(chǎn)生一個由抽象節(jié)點(diǎn)所組成的粒度較粗的拓?fù)鋱D；在此基礎(chǔ)上對抽象節(jié)點(diǎn)繼續(xù)合并，可以得到更粗粒度的拓?fù)鋱D。逐級精化傳輸則是指按粒度從粗到細(xì)逐級傳輸Provenance。在BS端，可首先在較粗粒度上獲取Provenance信息，然后根據(jù)后續(xù)到達(dá)的較細(xì)粒度數(shù)據(jù)逐級解碼，直至獲得準(zhǔn)確的Provenance。因為可以根據(jù)粗粒度的信息Provenance初步斷定其可信性，所以BS可以由此判斷是否對接收的Provenance繼續(xù)精化解碼，從而提高了數(shù)據(jù)可信度評估的效率?；赥inyOS- 2.1.2軟件仿真以及ZigBee硬件節(jié)點(diǎn)的實驗均表明，本文所提出的方法與PPF[5]、PN[6]方法相比平均壓縮比更高、節(jié)能效果和魯棒性也更好。

1 相關(guān)工作

由于WSN是一個能量受限的網(wǎng)絡(luò)，所以為了解決問題時減少路由開銷，研究人員提出了大量的Provenance壓縮算法。文獻(xiàn)[7]提出了輕量級壓縮Provenance算法，解決了Provenance隨數(shù)據(jù)包傳輸路徑的增長而迅速膨脹的問題。Hussain等[1]提出了采用算數(shù)編碼壓縮Provenance(Arithmetic Coding based Provenance compression， ACP)的方法，解決了Provenance的大小隨路徑的變化而變化的問題。但是在大規(guī)模WSN中，數(shù)據(jù)傳輸?shù)逆溌烽L，采用輕量級或壓縮的方法還是會出現(xiàn)嚴(yán)重的過載問題，分段傳輸Provenance的方法隨之而出。此方法的主要思想是將Provenance分割成若干小塊，每個小塊攜帶一部分Provenance數(shù)據(jù)，由此解決了數(shù)據(jù)過載問題。

Alam等[5]提出的概率溯源流(PPF)法，將一個大的Provenance分割成若干小段，通過一定的概率計算決定當(dāng)前應(yīng)當(dāng)傳輸?shù)姆侄?。Sultana等[6]提出了一種偽隨機(jī)噪聲(PN)碼算法，即通過偽噪聲碼將較大的溯源編碼為一系列較小的二進(jìn)制碼塊，通過數(shù)據(jù)包間延遲信道傳輸。這些方法解決了由于傳輸鏈路的增加而導(dǎo)致數(shù)據(jù)過載的問題，但是在全部分段準(zhǔn)確到達(dá)之前無法解碼。

Wang等[8]提出的基于動態(tài)貝葉斯網(wǎng)絡(luò)的傳感器網(wǎng)絡(luò)溯源壓縮方法，即一種使用動態(tài)貝葉斯網(wǎng)絡(luò)對WSN進(jìn)行建模的方案，節(jié)點(diǎn)或BS能周期性地更新網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，然后通過修改的算術(shù)編碼壓縮方法對Provenance進(jìn)行編碼。此方法解決了WSN拓?fù)鋾討B(tài)變化的問題。

文獻(xiàn)[9]提出的商空間法，即根據(jù)一定的等價關(guān)系，將論域進(jìn)行商空間劃分獲得新的元素，而這些新元素會構(gòu)成一個新的空間，即一個較粗粒度的世界。

Wang等[10]提出的使用路徑字典的方法傳輸Provenance，即在傳輸過程中，首先根據(jù)傳輸?shù)腜rovenance路徑信息建立字典，在后續(xù)傳輸過程中只需傳輸路徑的索引即可，此方法解決了路徑熵值的限制，具有很高的壓縮比。所以本文利用了此方法，在每一層拓?fù)鋱D上均建立相應(yīng)的字典，因此傳輸效率很高。

本文所提出的基于多粒度拓?fù)鋱D的WSN逐級精化溯源方法，以信息熵為等價條件，通過計算節(jié)點(diǎn)間的互信息(Mutual Information, MI)，將較大的WSN拓?fù)鋱D劃分為由少量抽象節(jié)點(diǎn)組成的較粗粒度的拓?fù)鋱D，由此可將Provenance按層次分段傳輸，且無需全部分段完全到達(dá)，評估者依然能大致了解到該P(yáng)rovenance傳輸中的衍生過程，而且在傳輸過程中，在每一層拓?fù)鋱D上均建立相應(yīng)的路徑字典信息，提高傳輸效率。

2 系統(tǒng)模型及相關(guān)工作

本章主要介紹基于非均勻粒度拓?fù)鋱D的WSN逐級精化溯源方法所涉及的系統(tǒng)模型。

2.1 WSN拓?fù)鋱D多粒度模型

多粒度模型主要是利用商空間劃分理論[9]通過計算節(jié)點(diǎn)之間的互信息實現(xiàn)的，即在訓(xùn)練階段收集每個節(jié)點(diǎn)在Provenance中出現(xiàn)的頻率以及節(jié)點(diǎn)之間的拓?fù)潢P(guān)系，然后計算節(jié)點(diǎn)間的互信息并利用抽象節(jié)點(diǎn)內(nèi)部的信息熵作為臨界條件逐級將WSN的拓?fù)鋱D進(jìn)行劃分成不同的粒度，且在每個粒度下的抽象節(jié)點(diǎn)內(nèi)部的信息熵是相同的。如圖1所示，在傳輸時，Provenance首先記錄一級粒度下的節(jié)點(diǎn)信息n13、n23、n33，然后再記錄二級粒度下的節(jié)點(diǎn)信息n12、n22，依此類推。在BS端則根據(jù)粒度從粗到細(xì)逐級精化解碼。

圖1 WSN拓?fù)鋱D多粒度分層圖

2.2 數(shù)據(jù)模型

根據(jù)傳感器節(jié)點(diǎn)在WSN中扮演不同角色，可以把傳感器節(jié)點(diǎn)分為三類：1)數(shù)據(jù)源節(jié)點(diǎn)。感知、采集客觀世界信息。2)轉(zhuǎn)發(fā)節(jié)點(diǎn)。將數(shù)據(jù)沿BS方向轉(zhuǎn)發(fā)到下一節(jié)點(diǎn)。3)匯聚節(jié)點(diǎn)。將來自不同節(jié)點(diǎn)的數(shù)據(jù)匯聚為一個較大的數(shù)據(jù)包并傳往BS。

每個數(shù)據(jù)包均具有數(shù)據(jù)值和Provenance數(shù)據(jù)。Provenance數(shù)據(jù)包括數(shù)據(jù)源節(jié)點(diǎn)id、當(dāng)前節(jié)點(diǎn)id、路徑序列號、匯聚集合等。其中，路徑序列號的設(shè)置是為了使BS能夠識別出隸屬于不同粒度上的相同路徑的Provenance分段。

2.3 Provenance模型

在WSN中，Provenance分為兩種結(jié)構(gòu)模型：1)簡單Provenance模型，如圖2(a)，葉子節(jié)點(diǎn)n1產(chǎn)生數(shù)據(jù)包，經(jīng)過中間節(jié)點(diǎn)的轉(zhuǎn)發(fā)直至BS，這種Provenance可以用〈n1,n2,n3,n4,n5,BS〉表示；2)匯聚Provenance模型，如圖2(b)，n1,n2,n3,n4是數(shù)據(jù)源節(jié)點(diǎn)，n5是匯聚節(jié)點(diǎn)，n5匯聚從n1,n2,n3,n4接收的數(shù)據(jù)，然后再傳至BS。這種匯聚Provenance可以用〈{n1,n2,n3,n4},n5,n6,n7,BS〉表示。

圖2 兩種Provenance模型

3 基于非均勻粒度Provenance編碼與解碼

本章主要從WSN粒度圖的劃分、在多級粒度圖上壓縮與解壓縮Provenance三個方面進(jìn)行討論。

3.1 非均勻粒度拓?fù)鋱D的劃分

3.1.1 節(jié)點(diǎn)出現(xiàn)概率和節(jié)點(diǎn)間聯(lián)合概率的計算

為了獲取網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)參與數(shù)據(jù)包轉(zhuǎn)發(fā)、聚合等操作的概率，需要一個訓(xùn)練階段。在訓(xùn)練階段發(fā)生前，BS端處沒有節(jié)點(diǎn)的出現(xiàn)概率和節(jié)點(diǎn)間聯(lián)合概率等信息，所以假定一開始所有節(jié)點(diǎn)的出現(xiàn)概率和節(jié)點(diǎn)間聯(lián)合概率均采用平均分布；然后，在訓(xùn)練過程中BS周期性地更新節(jié)點(diǎn)以及節(jié)點(diǎn)間概率數(shù)據(jù)。下面簡要闡述在訓(xùn)練過程中概率的計算公式：

BS計算節(jié)點(diǎn)ni在數(shù)據(jù)包歷史傳輸路徑中出現(xiàn)的次數(shù)，記為ofi。根據(jù)ofi的值，BS可以計算出傳輸過程中節(jié)點(diǎn)總的發(fā)生頻率of，那么對于節(jié)點(diǎn)ni來說，它的出現(xiàn)概率為opi，其計算方式[1,11]如下：

(1)

opi=ofi/of

(2)

在訓(xùn)練階段結(jié)束前后，BS能檢測出數(shù)據(jù)包路徑中節(jié)點(diǎn)出現(xiàn)的先后次序，并計算出節(jié)點(diǎn)ni出現(xiàn)在節(jié)點(diǎn)nj后的總數(shù)，記為ofij，那么nj到ni的聯(lián)合概率[1,11]為:

opij=ofij/ofj

(3)

3.1.2 互信息和信息熵計算

在BS端計算各個節(jié)點(diǎn)之間的互信息(MI)，互信息越大的兩個節(jié)點(diǎn)關(guān)聯(lián)度越大，互信息的計算方式為：

(4)

通過計算節(jié)點(diǎn)內(nèi)部信息熵[12]來確定粒度的劃分條件，查找出互信息最大的兩個點(diǎn)之后，計算出其內(nèi)部的信息熵，計算公式如下：

(5)

其中ki表示第i個聚類。

3.1.3 多粒度拓?fù)鋱D劃分算法

本方法采用樹的雙親節(jié)點(diǎn)存儲法[13]存儲劃分好的粒度拓?fù)鋱D，存儲的節(jié)點(diǎn)主要包含節(jié)點(diǎn)id、節(jié)點(diǎn)所在層次flag、節(jié)點(diǎn)合并的抽象節(jié)點(diǎn)所在位置parent以及節(jié)點(diǎn)的概率p。多粒度拓?fù)鋱D劃分過程為：1)計算出各節(jié)點(diǎn)之間的互信息MI；2)從MI中找出互信息最大的兩個點(diǎn)ni、nj判斷它們隸屬哪層粒度，若ni.flag==nj.flagnj.flag，則將nj.parent置為ni所在位置。

算法1 WSN非均勻粒度拓?fù)鋱D的劃分算法。

輸入：層次標(biāo)記flag，當(dāng)前粒度閾值value,節(jié)點(diǎn)間互信息MI；

輸出：多粒度拓?fù)鋱Dptree={id,flag,parent,p}。

1)

for eachk

2)

ifMI[k].infois max then

3)

ni=MI[k].id1

4)

nj=MI[k].id2

5)

end if

6)

ifni.flag==nj.flagandni.flag

7)

compute theHofniandnj

8)

ifH

9)

add a new id number into theptree

10)

elsek++

11)

end if

12)

end if

13)

ifni.flag==nj.flagandni.flag==flagthen

14)

compute theHofniandnj

15)

ifH

16)

change value of the child ofnjintoni

17)

deletenjfromptree

18)

elsek++

19)

end if

20)

end if

21)

ifni.flag>nj.flagthen

22)

compute theHofniandnj

23)

ifH

24)

nj.parent=ni

25)

elsek++

26)

end if

27)

end if

28)

ifni.flag

29)

compute theHofniandnj

30)

ifH

31)

ni.parent=nj

32)

elsek++

33)

end if

34)

end if

35)

end for

算法1各符號含義為：1)flag是當(dāng)前要劃分的拓?fù)鋱D的層級數(shù)；2)value為當(dāng)前粒度的閾值；3)MI表示節(jié)點(diǎn)間的互信息，存儲形式為{節(jié)點(diǎn)ni，節(jié)點(diǎn)nj，兩者互信息}；4)ptree存儲劃分完成的多粒度拓?fù)鋱D；5)ni，nj表示互信息最大的兩個節(jié)點(diǎn)；6)num_node表示節(jié)點(diǎn)數(shù)；7)H表示節(jié)點(diǎn)ni，nj內(nèi)部的信息熵值，當(dāng)H大于當(dāng)前粒度所設(shè)置的最大值時，停止合并ni，nj。圖3為多粒度拓?fù)鋱D劃分流程。

圖3 多粒度拓?fù)鋱D劃分流程

多粒度拓?fù)鋱D劃分完成后，BS將劃分完成的拓?fù)鋱D廣播到各個節(jié)點(diǎn)，各個節(jié)點(diǎn)隨即知道它自己的抽象節(jié)點(diǎn)編號。

3.2 Provenance的非均勻多粒度編碼

Provenance的非均勻多粒度編碼是在基于非均勻多粒度劃分的拓?fù)鋱D上采用字典編碼[10]的方法，即在節(jié)點(diǎn)處保存有當(dāng)前層次的數(shù)據(jù)路徑及其字典(Packet Path Dictionary， PPD)。傳輸過程中需要傳輸?shù)男畔〝?shù)據(jù)源節(jié)點(diǎn)、當(dāng)前數(shù)據(jù)節(jié)點(diǎn)、當(dāng)前傳輸層次、匯聚節(jié)點(diǎn)集合、字典索引，記為prIndex={seq,sourceid,nodeid,flag,agr,dicindex}設(shè)置每個節(jié)點(diǎn)內(nèi)部保存的字典為序列號、傳輸路徑、匯聚集合、字典索引，記為PPD={seq,path,agr,dicindex}。已知當(dāng)前傳輸層次為flag，編碼過程如下：

圖4 Provenance編碼

算法2 多粒度拓?fù)鋱D上編碼Provenance。

輸入：接收節(jié)點(diǎn)編號ni，序列號seqi，層次,flag。

輸出：傳輸數(shù)據(jù)路徑及節(jié)點(diǎn)信息prIndex=(vi,dicindex)。

1)

ifniis a data source node then

2)

3)

4)

seqi=hash(ni)

5)

agr=?

6)

prIndex.v=vi

7)

8)

end if

9)

ifniis a forwarder node then

10)

11)

12)

seqi=hash(seqj+ni)

13)

agr=?

14)

prIndex.v=vi

15)

16)

end if

17)

ifniis an aggregator node then

18)

19)

20)

seqi=hash(seq1+seq2+…+ni)

21)

agr={seq1,seq2,…}

22)

prIndex.v=vi

23)

24)

end if

為了便于理解此算法，下面給出一個應(yīng)用實例。圖4(a)為一個簡易WSN拓?fù)鋱D，圖中圓圈內(nèi)部表示節(jié)點(diǎn)的id值，因為拓?fù)鋱D分為3層，所以節(jié)點(diǎn)(n1,n2,n3,n4)在第2層和第3層所屬抽象節(jié)點(diǎn)id分別為(6，6，7，8)和(9，9，9，9)。如圖4(a)，在數(shù)據(jù)源節(jié)點(diǎn)n1,n4采集到數(shù)據(jù)后，由n2轉(zhuǎn)發(fā)到n3，在n3處匯聚由n2、n4轉(zhuǎn)發(fā)而來的數(shù)據(jù)，再傳輸至BS。Provenance傳輸方式如下：

1)在第3層上傳輸Provenance時，n1,n4在第3層的抽象節(jié)點(diǎn)編號為9，更新數(shù)據(jù)包信息如圖4(b)中的①、圖4(b)中的③；n2在第三層所屬抽象節(jié)點(diǎn)為9，更新數(shù)據(jù)包信息如圖4(b)中的②；n3在第三層所屬抽象節(jié)點(diǎn)為9，更新數(shù)據(jù)包信息如圖4(b)中的④。

2)在第2層上傳輸時，n1,n4在第2層的抽象節(jié)點(diǎn)編號分別為6、8，更新數(shù)據(jù)包信息如圖4(c)中的①、圖4(c)中的③；n2在第二層所屬抽象節(jié)點(diǎn)為6，更新數(shù)據(jù)包信息如圖3(c)中的②；n3在第二層所屬抽象節(jié)點(diǎn)為7，更新數(shù)據(jù)包信息如圖4(c)中的④。

3)在第1層上傳輸時，數(shù)據(jù)包更新方式與第2層類似，數(shù)據(jù)包更新結(jié)果如圖4(d)所示。

3.3 Provenance的非均勻多粒度解碼

當(dāng)BS接收到數(shù)據(jù)包p時將解碼出的數(shù)據(jù)包中節(jié)點(diǎn)的拓?fù)鋱D以T〈Vp,Ep〉形式保存，而BS會根據(jù)其對應(yīng)的PPD中dicindex信息構(gòu)建溯源拓?fù)湫畔ⅰ?/p>

算法3 在第flag層上解碼Provenance。

輸入：傳輸層次flag,數(shù)據(jù)路徑及信息(vi,dicindex)。

輸出：拓?fù)鋱DTflag(Vflag,Eflag)。

1)

if the AM-FM verification fails then

2)

3)

ifv.flag==flagthen

4)

ifv.arg==? then

5)

Tflag(Vflag,Eflag)=search path in PPD

6)

else

7)

pathset=number of ′;′ indicindex

8)

fori=1 topathsetdo

9)

pathi=searchbranchiofdicindexin PPD

10)

end for

11)

Tflag(Vflag,Eflag)=path1;…;pathpathset

12)

end if

13)

end if

14)

end if

15)

ifTflag(Vflag,Eflag) is not useful then

16)

drop the nextpacketviwhenvi.seq=v.seq

17)

end if

算法3中各符號含義：1)flag表示當(dāng)前要解碼的層次；2)vi表示存儲有{seq，ni，flag}的集合；3)dicindex表示接收數(shù)據(jù)包中溯源索引；4)Tflag(Vflag,Eflag)表示接收到的數(shù)據(jù)包中第flag層的拓?fù)鋱D。

為了便于理解此算法，以圖4(a)為例簡要描述此算法。

1)BS首先接收到數(shù)據(jù)包{hash,1,3,3,?,〈9,?〉}，解碼出flag=3，則傳輸層次為最高層，且數(shù)據(jù)源節(jié)點(diǎn)為n1，當(dāng)前節(jié)點(diǎn)為n3，沒有匯聚節(jié)點(diǎn)，則解碼出第3層上的Provenance為圖5(a)。

2)接收數(shù)據(jù)包{hash,1,3,2,{6,8},〈6,7;8,7〉}，解碼出此傳輸層次為第2層，且數(shù)據(jù)源節(jié)點(diǎn)為n1，當(dāng)前節(jié)點(diǎn)為n3，匯聚節(jié)點(diǎn)為n7，匯聚從n6、n8節(jié)點(diǎn)接收到的數(shù)據(jù)包，解碼出第二層上的溯源為圖5(b)。

3)接收數(shù)據(jù)包{hash,1,3,1,{2,4},〈1,3;4,3〉}，與上述兩層解碼方式相同，解碼結(jié)果如圖5(c)。

圖5 Provenance解碼

4 性能分析與仿真

4.1 性能分析

本節(jié)主要對本文提出的MTSRP算法進(jìn)行時間復(fù)雜度和空間復(fù)雜度分析，算法1中：1)s表示每個層次所需抽象的節(jié)點(diǎn)個數(shù)，2)k表示存儲互信息值的個數(shù)，3)flag表示需要抽象的層次數(shù)，那么算法1的時間復(fù)雜度為O(s·flag)，空間復(fù)雜度為O(3·k)。算法2中：p表示PPD中所需保存的字典序列個數(shù)，算法2只需更新節(jié)點(diǎn)內(nèi)部的PPD以及Provenance中的dicindex、seq、agr部分，所以算法2的時間復(fù)雜度為O(1)，空間復(fù)雜度為O(4·p)。算法3中：n表示PPD中記錄數(shù)，利用建立好的字典進(jìn)行解碼，只需查詢PPD中的記錄，時間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。

4.2 仿真與實驗

本文實驗在TinyOS- 2.1.2操作系統(tǒng)下進(jìn)行仿真，采用nesC編程語言編寫應(yīng)用程序，并通過PowerTOSSIMz能量仿真插件進(jìn)行能量評估。

為了驗證本文算法的有效性，將MTSRP方法與基于多級分簇概率溯源流(Hierarchical Clustering Probabilistic Provenance Flow， HCPPF)[14]方法、文獻(xiàn)[8]提出的基于動態(tài)貝葉斯網(wǎng)絡(luò)的Provenance(Dynamic Bayesian Network based Provenance， DBNP)方法進(jìn)行對比。

4.2.1 性能指標(biāo)

1)Average Provenance size：代表數(shù)據(jù)包的平均比特數(shù)。

2)Total Energy Consumption(TEC)：代表節(jié)點(diǎn)總能耗。當(dāng)網(wǎng)絡(luò)中有n1,n2,…,nm個節(jié)點(diǎn)，那么總的能量消耗為：

(6)

其中：ECni表示節(jié)點(diǎn)ni的能量消耗；m表示網(wǎng)絡(luò)中節(jié)點(diǎn)的總數(shù)。

4.2.2 仿真結(jié)果

在仿真實驗中，采用編號1～50的節(jié)點(diǎn)，其中節(jié)點(diǎn)50為BS節(jié)點(diǎn)，網(wǎng)絡(luò)中跳數(shù)最大為12跳。在仿真過程中，分析線性Provenance和匯聚Provenance兩種情況，討論兩者傳輸跳數(shù)與Provenance包含的平均比特數(shù)之間以及總能耗的關(guān)系。

圖6給出了HCPPF、DBNP、MTSRP三種方法中Provenance平均比特數(shù)與傳輸跳數(shù)的關(guān)系。從圖中可以明顯看出在線性Provenance中，MTSRP方法采用路徑字典壓縮方法傳輸Provenance，所以隨著傳輸跳數(shù)的增加，Provenance平均比特數(shù)一直處于較低的狀態(tài)，壓縮比相比其他方法而言優(yōu)勢較為明顯。

圖6 仿真實驗中線性Provenance中Provenance平均比特數(shù)與傳輸跳數(shù)的關(guān)系

圖7是HCPPF、DBNP、MTSRP三種方法傳輸跳數(shù)與總的能量消耗之間的關(guān)系。從圖7中可以看出，在傳輸跳數(shù)逐漸增加時，MTSRP相比其他兩種方法耗能最少。

圖8所顯示的是在TinyOS- 2.1.2中仿真時選取10個源節(jié)點(diǎn)和5個匯聚節(jié)點(diǎn)，并使用DBNP、HCPPF、MTSRP方法得到的Provenance平均比特數(shù)與數(shù)據(jù)包傳輸數(shù)目的關(guān)系。圖8中曲線關(guān)系表示，MTSRP方法在數(shù)據(jù)包傳輸數(shù)目增加時，Provenance會根據(jù)建立好的路徑字典中選取對應(yīng)路徑的索引來代替完整路徑，所以匯聚效果更好并趨向于一個更低值。

4.2.3 硬件組網(wǎng)實驗

采用50個ZigBee節(jié)點(diǎn)進(jìn)行硬件實驗，分別給這50個節(jié)點(diǎn)分配地址編號為0x0001～0x0050，其中編號0x0050為BS節(jié)點(diǎn)。將在仿真中已編譯成功的二進(jìn)制文件下載到節(jié)點(diǎn)的芯片上，并將節(jié)點(diǎn)部署在一個15 m×15 m的空地上。

圖7 線性Provenance傳輸跳數(shù)與總能耗的關(guān)系

圖8 仿真實驗中匯聚Provenance中Provenance平均比特數(shù)與傳輸跳數(shù)的關(guān)系

圖9顯示的是在硬件組網(wǎng)實驗中，在線性傳輸Provenance條件下，采用HCPPF、MTSRP、DBNP三種方法時，數(shù)據(jù)包傳輸跳數(shù)與Provenance平均比特數(shù)的關(guān)系。圖中的數(shù)據(jù)曲線與圖6的數(shù)據(jù)曲線相比相差不大，基本吻合。

圖9 硬件實驗中線性Provenance中Provenance平均比特數(shù)與傳輸跳數(shù)的關(guān)系

圖10顯示的是在匯聚Provenance條件下分別采用HCPPF、MTSRP、DBNP方法時，數(shù)據(jù)包傳輸跳數(shù)與Provenance平均比特數(shù)的關(guān)系。圖中的數(shù)據(jù)曲線與圖8的數(shù)據(jù)曲線相比數(shù)據(jù)變化趨勢基本相同。由此證明了本文MTSRP方法的實用性和有效性。

5 結(jié)語

針對傳統(tǒng)分段傳輸數(shù)據(jù)利用率低、耗能較高的問題，本文提出一種基于多粒度拓?fù)鋱D的溯源傳輸方法，即將大的WSN拓?fù)鋱D按一定的規(guī)則抽象成粗粒度的拓?fù)鋱D，在傳輸過程中由粗到細(xì)傳輸Provenance。一方面解決了傳統(tǒng)分段方法中全部分段到達(dá)之前無法解碼的問題；另一方面評估者可以根據(jù)先到達(dá)的粗粒度數(shù)據(jù)衍生過程來判斷當(dāng)前數(shù)據(jù)是否可靠，是否需要采用更細(xì)粒度的數(shù)據(jù)進(jìn)行評估；與此同時，本文方法在Provenance傳輸過程中節(jié)約了大量的能量。仿真實驗以及硬件組網(wǎng)實驗驗證了本文方法的實用性和有效性。在下一步的工作中，將針對本文使用的路徑字典的傳輸方法進(jìn)行進(jìn)一步的改進(jìn)，解決網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化時字典傳輸不穩(wěn)定的問題。

圖10 硬件實驗中匯聚Provenance中Provenance平均比特數(shù)與傳輸跳數(shù)的關(guān)系

References)

[1] HUSSAIN S R, WANG C, SULTANA S, et al. Secure data provenance compression using arithmetic coding in wireless sensor networks [C]// Proceeding of the 2015 Performance Computing and Communications Conference. Piscataway, NJ: IEEE, 2015: 1-10.

[2] 李建中,高宏.無線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計算機(jī)研究與發(fā)展,2008,45(1):1-15.(LI J Z, GAO H. Survey on sensor network research [J]. Journal of Computer Research and Development, 2008, 45(1): 1-15.

[3] DOGAN G. A survey of provenance in wireless sensor networks [J]. Ad Hoc & Sensor Wireless Networks, 2016, 30(1/2): 21.

[4] BISDIKIAN C, KAPLAN L M, SRIVASTAVA M B. On the quality and value of information in sensor networks [J]. ACM Transactions on Sensor Networks, 2013, 9(4): 48.

[5] ALAM S M I, FAHMY S.A practical approach for provenance transmission in wireless sensor networks [J]. Ad Hoc Networks, 2014, 16(4): 28-45.

[6] SULTANA S, SHEHAB M, BERTINO E. Secure provenance transmission for streaming data [J]. IEEE Transactions on Knowledge & Data Engineering, 2013, 25(8): 1890-1903.

[7] SHEBARO B, SALMIN S, BERTINO E, et al. Demonstrating a lightweight data provenance for sensor networks [C]// Proceeding of the 2012 ACM Conference on Computer and Communications Security. New York: ACM, 2012: 1022-1024.

[8] WANG C, BERTINO E. Sensor network provenance compression using dynamic Bayesian networks [J]. ACM Transactions on Sensor Networks, 2017, 13(1): Article No. 5.

[9] 張燕平,張鈴,吳濤.不同粒度世界的描述法——商空間法[J].計算機(jī)學(xué)報,2004,27(3):328-333.(ZHANG Y P, ZHANG L, WU T. The representation of different granular worlds: a quotient space [J]. Chinese Journal of Computers, 2004, 27(3): 328-333.)

[10] WANG C, HUSSAIN S R, BERTINO E. Dictionary based secure provenance compression for wireless sensor networks [J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(2): 405-418.

[11] 袁裕琳.WSN中基于多級算術(shù)編碼的溯源數(shù)據(jù)壓縮方法[D].鎮(zhèn)江：江蘇大學(xué),2016.(YUAN Y L. Data provenance compression using cluster based arithmetic coding in wireless sensor networks [D]. Zhenjiang: Jiangsu University, 2016.)

[12] YUAN L, KEVIN C, DESOUZA, et.al. Measuring agility of networked organizational structures via network entropy and mutual information [J]. Applied Mathematics and Computation, 2010, 216(10): 2824-2836.

[13] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,2007:135.(YAN W M, WU W M. Date Structure [M]. Beijing: Tsinghua University Press, 2007: 135.)

[14] 宋澤.基于分層視圖的WSN溯源壓縮算法的研究[D].鎮(zhèn)江：江蘇大學(xué),2017.(SONG Z. Research on provenance compression algorithm based on hierarchical view in WSN [D]. Zhenjiang: Jiangsu University, 2017.)

This work is partially supported by the National Natural Science Foundation of China (61672269), the Transformation Project of Science & Technology Achievements of Jiangsu Province (BA2015161), the Top-Notch Talent Planning Project of Jiangsu University (1213000013).

KANGZhaoling, born in 1993, M. S. candidate. Her research interests include information security, wireless sensor network.

XUQinbao, born in 1987, M. S. candidate. His research interests include information security, wireless sensor network.

WANGChangda, born in 1971, Ph. D., professor. His research interests include information security, network communication, Internet of things.