基于多粒度拓?fù)鋱D的無(wú)線傳感器網(wǎng)絡(luò)逐級(jí)精化溯源方法

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

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

0 引言

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

圖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)。將來(lái)自不同節(jié)點(diǎn)的數(shù)據(jù)匯聚為一個(gè)較大的數(shù)據(jù)包并傳往BS。

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

2.3 Provenance模型

在WSN中，Provenance分為兩種結(jié)構(gòu)模型：1)簡(jiǎn)單Provenance模型，如圖2(a)，葉子節(jié)點(diǎn)n1產(chǎn)生數(shù)據(jù)包，經(jīng)過(guò)中間節(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粒度圖的劃分、在多級(jí)粒度圖上壓縮與解壓縮Provenance三個(gè)方面進(jìn)行討論。

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

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

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

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

(1)

opi=ofi/of

(2)

在訓(xùn)練階段結(jié)束前后，BS能檢測(cè)出數(shù)據(jù)包路徑中節(jié)點(diǎn)出現(xiàn)的先后次序，并計(jì)算出節(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 互信息和信息熵計(jì)算

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

(4)

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

(5)

其中ki表示第i個(gè)聚類。

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

本方法采用樹(shù)的雙親節(jié)點(diǎn)存儲(chǔ)法[13]存儲(chǔ)劃分好的粒度拓?fù)鋱D，存儲(chǔ)的節(jié)點(diǎn)主要包含節(jié)點(diǎn)id、節(jié)點(diǎn)所在層次flag、節(jié)點(diǎn)合并的抽象節(jié)點(diǎn)所在位置parent以及節(jié)點(diǎn)的概率p。多粒度拓?fù)鋱D劃分過(guò)程為：1)計(jì)算出各節(jié)點(diǎn)之間的互信息MI；2)從MI中找出互信息最大的兩個(gè)點(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各符號(hào)含義為：1)flag是當(dāng)前要?jiǎng)澐值耐負(fù)鋱D的層級(jí)數(shù)；2)value為當(dāng)前粒度的閾值；3)MI表示節(jié)點(diǎn)間的互信息，存儲(chǔ)形式為{節(jié)點(diǎn)ni，節(jié)點(diǎn)nj，兩者互信息}；4)ptree存儲(chǔ)劃分完成的多粒度拓?fù)鋱D；5)ni，nj表示互信息最大的兩個(gè)節(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è)置的最大值時(shí)，停止合并ni，nj。圖3為多粒度拓?fù)鋱D劃分流程。

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

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

3.2 Provenance的非均勻多粒度編碼

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

圖4 Provenance編碼

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

輸入：接收節(jié)點(diǎn)編號(hào)ni，序列號(hào)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

為了便于理解此算法，下面給出一個(gè)應(yīng)用實(shí)例。圖4(a)為一個(gè)簡(jiǎn)易WSN拓?fù)鋱D，圖中圓圈內(nèi)部表示節(jié)點(diǎn)的id值，因?yàn)橥負(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ā)而來(lái)的數(shù)據(jù)，再傳輸至BS。Provenance傳輸方式如下：

1)在第3層上傳輸Provenance時(shí)，n1,n4在第3層的抽象節(jié)點(diǎn)編號(hào)為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層上傳輸時(shí)，n1,n4在第2層的抽象節(jié)點(diǎn)編號(hào)分別為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í)，數(shù)據(jù)包更新方式與第2層類似，數(shù)據(jù)包更新結(jié)果如圖4(d)所示。

3.3 Provenance的非均勻多粒度解碼

當(dāng)BS接收到數(shù)據(jù)包p時(shí)將解碼出的數(shù)據(jù)包中節(jié)點(diǎn)的拓?fù)鋱D以T〈Vp,Ep〉形式保存，而B(niǎo)S會(huì)根據(jù)其對(duì)應(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中各符號(hào)含義：1)flag表示當(dāng)前要解碼的層次；2)vi表示存儲(chǔ)有{seq，ni，flag}的集合；3)dicindex表示接收數(shù)據(jù)包中溯源索引；4)Tflag(Vflag,Eflag)表示接收到的數(shù)據(jù)包中第flag層的拓?fù)鋱D。

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

1)BS首先接收到數(shù)據(jù)包{hash,1,3,3,?,〈9,?〉}，解碼出flag=3，則傳輸層次為最高層，且數(shù)據(jù)源節(jié)點(diǎn)為n1，當(dāng)前節(jié)點(diǎn)為n3，沒(méi)有匯聚節(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é)主要對(duì)本文提出的MTSRP算法進(jìn)行時(shí)間復(fù)雜度和空間復(fù)雜度分析，算法1中：1)s表示每個(gè)層次所需抽象的節(jié)點(diǎn)個(gè)數(shù)，2)k表示存儲(chǔ)互信息值的個(gè)數(shù)，3)flag表示需要抽象的層次數(shù)，那么算法1的時(shí)間復(fù)雜度為O(s·flag)，空間復(fù)雜度為O(3·k)。算法2中：p表示PPD中所需保存的字典序列個(gè)數(shù)，算法2只需更新節(jié)點(diǎn)內(nèi)部的PPD以及Provenance中的dicindex、seq、agr部分，所以算法2的時(shí)間復(fù)雜度為O(1)，空間復(fù)雜度為O(4·p)。算法3中：n表示PPD中記錄數(shù)，利用建立好的字典進(jìn)行解碼，只需查詢PPD中的記錄，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。

4.2 仿真與實(shí)驗(yàn)

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

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

4.2.1 性能指標(biāo)

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

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

(6)

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

4.2.2 仿真結(jié)果

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

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

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

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

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

4.2.3 硬件組網(wǎng)實(shí)驗(yàn)

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

圖10 硬件實(shí)驗(yàn)中匯聚Provenance中Provenance平均比特?cái)?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ú)線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計(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ì)算機(jī)學(xué)報(bào),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中基于多級(jí)算術(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.