基于生成樹的WSN溯源數(shù)據(jù)壓縮方法

毛健+王昌達

摘 要：在無線傳感器網(wǎng)絡(luò)（WSN）中溯源數(shù)據(jù)（Provenance）記錄了一個數(shù)據(jù)從產(chǎn)生至被傳輸?shù)交荆˙S）途經(jīng)的所有節(jié)點以及在這些節(jié)點上對數(shù)據(jù)的操作。提出一種基于生成樹的溯源數(shù)據(jù)壓縮方法，其基本思想是在字典中存放WSN拓撲圖的生成樹并對其建立索引，在數(shù)據(jù)包傳輸過程中傳輸?shù)氖巧蓸涞乃饕皇峭暾纳蓸洹７抡鎸嶒灲Y(jié)果表明，在大規(guī)模稀疏WSN中采用該方法，溯源數(shù)據(jù)在文件大小和傳輸能耗等方面都優(yōu)于已知的其它溯源數(shù)據(jù)編碼技術(shù)，而且該方法對線性溯源數(shù)據(jù)和聚合溯源數(shù)據(jù)采用完全相同的處理方式，算法實現(xiàn)簡單、一致性好。

關(guān)鍵詞：生成樹；溯源數(shù)據(jù)；數(shù)據(jù)壓縮

DOIDOI：10.11907/rjdk.171217

中圖分類號：TP301

文獻標(biāo)識碼：A 文章編號：1672-7800（2017）007-0014-04

0 引言

WSN由具有一定通信能力與數(shù)據(jù)處理能力的傳感器節(jié)點組成，是一種能夠根據(jù)環(huán)境自主完成指定任務(wù)的智能自治網(wǎng)絡(luò)系統(tǒng)[1，2]。一般地，WSN節(jié)點的能量主要消耗在數(shù)據(jù)傳輸過程中，因此為了減少遠距離傳輸造成的能量消耗和信號衰減，WSN通常采用多跳的方式與BS通信[3]，即通過相鄰節(jié)點的轉(zhuǎn)發(fā)將數(shù)據(jù)傳輸至BS。傳感器節(jié)點的多樣性也導(dǎo)致對采集數(shù)據(jù)的可信性評估極為困難[4]。在一些關(guān)鍵應(yīng)用中，如工業(yè)控制等領(lǐng)域，因為采用可信度低的數(shù)據(jù)決策而造成重大損失的已有先例[5]。一般地，在WSN中使用溯源數(shù)據(jù)[6]記錄數(shù)據(jù)從源節(jié)點至BS途經(jīng)的所有節(jié)點以及在這些節(jié)點上對數(shù)據(jù)的操作。溯源數(shù)據(jù)是在WSN中實施數(shù)據(jù)可信性評估的重要依據(jù)之一。

最簡單的溯源數(shù)據(jù)模型是在數(shù)據(jù)包中逐次記錄數(shù)據(jù)傳輸途經(jīng)節(jié)點的ID，但這種溯源數(shù)據(jù)會隨著數(shù)據(jù)傳輸路徑的延長迅速膨脹，并最終導(dǎo)致數(shù)據(jù)量過載問題。因此相繼提出了一些輕量級的溯源數(shù)據(jù)方法[7，8]。因為受信息熵極限的制約，輕量級的方法并未從根本上解決溯源數(shù)據(jù)隨數(shù)據(jù)傳輸路徑增長而快速膨脹的問題。

鑒于此，本文提出一種基于生成樹編碼的溯源數(shù)據(jù)壓縮方法（Tree Based Provenance Encoding Scheme，TPE），TPE的應(yīng)用對象是大規(guī)模稀疏WSN。TPE的基本思想是在基于字典壓縮方法的基礎(chǔ)上，將編碼對象由字符串轉(zhuǎn)變?yōu)閃SN拓撲圖的生成樹并建立生成樹的字典，在溯源數(shù)據(jù)傳輸過程中傳輸?shù)氖巧蓸湓谧值渲械乃饕皇峭暾纳蓸??；赥inyOS的仿真實驗表明，在大規(guī)模稀疏WSN中，相較于其它已知的溯源數(shù)據(jù)編碼技術(shù)，相同條件下采用本文TPE獲得的溯源數(shù)據(jù)編碼平均長度最短，因此在WSN中對能量和傳輸帶寬的節(jié)約效果顯著。本文主要貢獻在于：

（1）針對大規(guī)模稀疏WSN，提出了一種基于其拓撲圖生成樹的溯源數(shù)據(jù)無損壓縮方法TPE，在已知的同類方法中，具有最高的平均壓縮比。

（2）TPE對線性溯源數(shù)據(jù)和聚合溯源數(shù)據(jù)，采用相同的編碼方法，算法的通用性、一致性好。

（3）通過基于TinyOS的仿真實驗，實證了TPE的各項主要性能指標(biāo)。

1 溯源數(shù)據(jù)模型

在WSN中，節(jié)點按照功能可劃分為源節(jié)點、轉(zhuǎn)發(fā)節(jié)點和匯聚節(jié)點。其中：源節(jié)點采集數(shù)據(jù)并將其封裝在數(shù)據(jù)包中；轉(zhuǎn)發(fā)節(jié)點沿著趨向于BS的方向?qū)碜栽垂?jié)點的數(shù)據(jù)包轉(zhuǎn)發(fā)至相鄰節(jié)點；匯聚節(jié)點將來自不同路徑上的多個數(shù)據(jù)包整合成一個較大的數(shù)據(jù)包并發(fā)往BS。傳輸由若干個較小數(shù)據(jù)包整合而成的較大數(shù)據(jù)包比獨立傳輸這些較小的數(shù)據(jù)包更節(jié)省能量，因此WSN的傳輸協(xié)議大多支持匯聚操作。

溯源數(shù)據(jù)有兩種基本類型：①線性溯源數(shù)據(jù)，如圖1（a）所示，其中數(shù)據(jù)源節(jié)點n4產(chǎn)生數(shù)據(jù)包并通過轉(zhuǎn)發(fā)節(jié)點傳送至BS（節(jié)點n1），可用表示；②聚合溯源數(shù)據(jù)，如圖1（b）所示，其中匯聚節(jié)點n3將從n4和n5接收的數(shù)據(jù)整合成一個較大的數(shù)據(jù)包后通過轉(zhuǎn)發(fā)節(jié)點傳送至BS，可表示為：<（（（n6，n7），n4），（n8，n5）），n3，n2，n1>。其中，遞歸式表示樹，a表示根節(jié)點；b表示其左孩子節(jié)點；c表示除左孩子外的其他孩子節(jié)點，c可以為空，也可以是1個或多個節(jié)點。

因為從樹的葉子節(jié)點到其根節(jié)點的路徑是唯一的，所以給定一棵生成樹以及其上的某個葉子節(jié)點，即可確定一個從該葉子節(jié)點到BS的線性溯源數(shù)據(jù)；而給定一棵樹以及其上的多個葉子節(jié)點，即可確定一個從這些葉子節(jié)點到BS的聚合溯源數(shù)據(jù)。例如在圖1（b）的生成樹中，若數(shù)據(jù)源為n7，則線性溯源數(shù)據(jù)為；若數(shù)據(jù)源為n7與n8，則聚合溯源數(shù)據(jù)為：<（（n7，n4），（n8，n5）），n3，n2，n1>。

2 溯源數(shù)據(jù)編碼與解碼算法

因為WSN中每個節(jié)點都存有完整的生成樹字典，所以溯源數(shù)據(jù)只需記錄：①某棵生成樹的索引（treeID）；②數(shù)據(jù)傳輸所在當(dāng)前節(jié)點的ID （currentID）；③一個或多個數(shù)據(jù)源節(jié)點的ID （sourcetID）。TPE方法中溯源數(shù)據(jù)的表示形式為：

因為TPE的解碼只涉及對樹的查找操作，而編碼在每個數(shù)據(jù)包途經(jīng)的每個節(jié)點上均需要先解碼、再編碼，所以先討論TPE的解碼算法。

2.1 解碼

當(dāng)BS收到某數(shù)據(jù)源節(jié)點傳來的數(shù)據(jù)包時，先根據(jù)其攜帶的treeID在字典中查找對應(yīng)的生成樹，然后在找到的生成樹上根據(jù)sourcetID的位置即可求出數(shù)據(jù)傳輸?shù)穆窂剑磸膕ourcetID所在的葉子節(jié)點至樹的根節(jié)點（BS）所確定的唯一路徑。

若溯源數(shù)據(jù)中只含有一個sourcetID，則解碼的結(jié)果是一個線性溯源數(shù)據(jù)；若溯源數(shù)據(jù)中含有多個sourcetID，則解碼的結(jié)果是一個聚合溯源數(shù)據(jù)。溯源數(shù)據(jù)的解碼算法如下：

Algorithm 1. Provenance Decoding

Input：pk

Output：A（P）

A（P）=0

I=pk .treeID

FOR t=0；t≤m-1；t++

IF in A（TI），a[pk .currentID，t] ！= 0

pk .currentID.nextID（ ）=a[pk .currentID，t]

END IF

END FOR

WHILE current node is not source node and receives a packet pk THEN

IF pk .currentID.nextID（ ）=current node id THEN

FOR all pk .sourceID

traverse A（TI）

front= pi .sourceID

next= pi .sourceID.nextID（ ）

WHILE pi .currentID ！= next

in A（P），a[front，next]=1

front=next，next=front.nextID（ ）

END WHILE

return A（P 1），A（P 2），…，A（P n）

END FOR

END IF

A（P）=A（P 1）|| A（P 2）||…|| A（P n）

END WHILE

2.2 編碼

（1）源節(jié)點處的編碼方法。當(dāng)源節(jié)點ni產(chǎn)生一個新的數(shù)據(jù)包時，其溯源數(shù)據(jù)的生成樹索引treeID為， sourceID和currentID的值都是ni。

（2）轉(zhuǎn)發(fā)節(jié)點處的編碼方法。當(dāng)ni為轉(zhuǎn)發(fā)節(jié)點時，在轉(zhuǎn)發(fā)時溯源數(shù)據(jù)的sourceID不變，currentID更新為ni，然后根據(jù)以下方法更新treeID：設(shè)轉(zhuǎn)發(fā)節(jié)點ni收到其上一跳節(jié)點傳遞的溯源數(shù)據(jù)Pj={treeID，nk，nj}，根據(jù)Algorithm 2，首先計算出Pj從數(shù)據(jù)源nj到ni的當(dāng)前路徑，并通過字典找出所有包含當(dāng)前路徑的生成樹，具體方法是將表示當(dāng)前數(shù)據(jù)路徑的鄰接矩陣和字典中所有生成樹的矩陣A（T0），A（T1），…，A（Tk-1）依次作異或XOR運算，對于當(dāng)前路徑鄰接矩陣內(nèi)的非零元素位置，若XOR后得到的新矩陣A（TI）（0≤I≤k-1）中的對應(yīng)位置的元素都等于0，那么I即為滿足條件的生成樹索引，即轉(zhuǎn)發(fā)后的線性溯源數(shù)據(jù)為：pj'={I，ni，nj}。

（3）匯聚節(jié)點處的編碼方法。當(dāng)匯聚節(jié)點nr先后接收到來自源節(jié)點ns和nt的溯源數(shù)據(jù)ps和pt后，首先通過匯聚得到新的數(shù)據(jù)包及其上的溯源數(shù)據(jù)pr'；然后在nr上執(zhí)行Algorithm 1分別求出從ns和nt至當(dāng)前節(jié)點nr的路徑，并通過生成樹字典找出同時包含以上2條路徑的生成樹的索引，記為treeID'；最后將currentID更新為nr，將ns和nt作為新的sourceID。即經(jīng)過匯聚節(jié)點的溯源數(shù)據(jù)為：pr'={treeID'，nr，ns，nt}。

Algorithm 2. Provenance Encoding

Input：pi，pj

Output：pk′

IF current node is source node THEN

FOR any Provenance

sourceID=source node id=currentID

treeID =

END FOR

END IF

ELSE IF a simple node nk receives pi THEN

Pi′ .currentID= current node id

Pi′ .treeID is tree′s index which includes current path

current path is decoded using Algorithm 2

END IF

IF an aggregated node nk receives pi and pj THEN

package′s path is decoded using Algorithm 2

pi′s path=A（P 1）， pj′s path=A（P 2）

pk′s path=A（P 1）|| A（P 2）

pk′ .treeID is tree′s index which includes pk′s path

pk′ .currentID=k

pk′.sourceID=i，j

END IF

3 仿真實驗

仿真在Linux環(huán)境下使用TinyOS 2.1.2進行，共采用編號0～99的100個節(jié)點，WSN的跳數(shù)在2～10之間，其中編號為0的節(jié)點是BS，其它節(jié)點被隨機地選為數(shù)據(jù)源節(jié)點或轉(zhuǎn)發(fā)節(jié)點。數(shù)據(jù)采集的周期為2秒。

將TPE的主要性能與以下3種常見的溯源數(shù)據(jù)編碼方法作對比。

（1）Bloom filter based provenance scheme （BFP） [7] ：在該方法中，溯源數(shù)據(jù)表示形式為pd=vd，v1，v2，v3，其中v1、v2和v3分別表示源節(jié)點vd發(fā)出的數(shù)據(jù)在傳輸過程中所經(jīng)過的節(jié)點。溯源數(shù)據(jù)的存儲采用布隆過濾器格式隨數(shù)據(jù)包一同傳輸。若節(jié)點vd的ID用vidi表示，則其計算公式如下：

其中，seq表示數(shù)據(jù)包序列號，E是基于AES的分塊加密函數(shù)。

（2）Generic secure provenance scheme （SPS） [9] ：在該方法中，溯源數(shù)據(jù)表示形式為pi=ni，hash（Di），Ci，其中hash（Di）表示數(shù)據(jù)Di的哈希值，Ci包含了由計算公式Sign（hash（ni，hash（Di）|| Ci-1））求得的一個帶有簽名的完整性校驗和。

（3）MAC based provenance scheme （MP） [10] ：該方法溯源數(shù)據(jù)中記錄的是數(shù)據(jù)包途經(jīng)節(jié)點的ID以及為了確保數(shù)據(jù)完整性而根據(jù)節(jié)點ID計算出的消息驗證碼CBC-MAC。

3.1 性能指標(biāo)

本文使用如下性能指標(biāo)分析TPE壓縮方法：

溯源數(shù)據(jù)的平均大?。ˋverage Provenance Size，APS）：當(dāng)BS接收到一個來自源節(jié)點ni的數(shù)據(jù)包時，通過其攜帶的treeID和sourceID可計算出數(shù)據(jù)的完整溯源路徑。若treeID與sourceID的大小分別用streeID和ssourceID表示，則溯源數(shù)據(jù)的大小為：

可通過如下公式計算平均溯源數(shù)據(jù)的長度：

其中，PSi表示節(jié)點ni上產(chǎn)生的單個溯源數(shù)據(jù)的長度sprovenance，m表示數(shù)據(jù)包傳輸途經(jīng)的節(jié)點數(shù)量。

3.2 仿真結(jié)果

圖2分別顯示了在SPS、MP、BFP和TPE等不同方法下，溯源數(shù)據(jù)的平均大小與數(shù)據(jù)包傳輸跳數(shù)的關(guān)系。在SPS與MP的方法中，數(shù)據(jù)包途經(jīng)的各節(jié)點都是向溯源數(shù)據(jù)中添加自身的ID，因此溯源數(shù)據(jù)的平均大小與傳輸跳數(shù)的增加均呈線性增長，且SPS方法的增速明顯更快。雖然BFP的平均溯源數(shù)據(jù)大小整體上也呈上升趨勢，但是相比前兩者明顯平緩，尤其在數(shù)據(jù)包傳輸跳數(shù)增加較大的情況下增速較為平緩，因此在大規(guī)模WSN中BFP具有良好的適用性。而在TPE方法中，在聚合溯源數(shù)據(jù)中源節(jié)點個數(shù)有限的前提下，無論數(shù)據(jù)包傳輸?shù)奶鴶?shù)如何增加，平均的溯源數(shù)據(jù)大小幾乎保持不變，約占3 Byte。又因為WSN主要的能耗用于無線信號的發(fā)送與接收，所以與SPS、MP和BFP相比，TPE方法在能量節(jié)約方面表現(xiàn)出較好的性能。

本文采用PowerTOSSIMz進行能量仿真。若WSN中有n個節(jié)點n1，n2，n3，….，nn，則總能量消耗（Total energy consumption，TEC）計算公式如下：

其中，ECi表示節(jié)點ni消耗的能量，n表示W(wǎng)SN中節(jié)點的數(shù)量。

圖3給出了WSN中在所有數(shù)據(jù)源節(jié)點都產(chǎn)生100個數(shù)據(jù)包的前提下，MP、BFP、TPE這3種不同方法的能量消耗，即數(shù)據(jù)包經(jīng)過不同傳輸跳數(shù)時節(jié)點所消耗的總能量（TEC）。在相同環(huán)境下，MP與BFP的能耗明顯大于TPE，而且隨著網(wǎng)絡(luò)規(guī)模的擴大、節(jié)點數(shù)量的增加，TPE在節(jié)約能耗方面的優(yōu)勢更加明顯。

4 結(jié)語

本文針對大規(guī)模稀疏WSN，提出了一種基于生成樹的溯源數(shù)據(jù)無損壓縮方法TPE。TPE對線性溯源數(shù)據(jù)和聚合溯源數(shù)據(jù)都可采用相同的編碼方法，且能確保溯源數(shù)據(jù)在途經(jīng)節(jié)點數(shù)量增加的情況下變化較小。軟件仿真和硬件實驗均表明，與其它已知的同類溯源數(shù)據(jù)壓縮方法相比，TPE在節(jié)約能量和降低無線帶寬占用率等方面都具有顯著優(yōu)勢。

參考文獻：

[1]LIU VINCENT，ZHAO Y.Wireless sensor networks for internet of things：a systematic review and classification[J].Information Technology Journal，2013，12（16）：3581-3585.

[2]CHEN X Q，MAKKI K，YEN K.Sensor network security：a survey[J].IEEE Communications Surveys and Tutorials，2009，11（2）：52-73.

[3]SUTAR U S，BODHE S K.Energy efficient topology control algorithm for multi-hop ad-hoc wireless sensor network[C].IEEE International Conference on Computer Science & Information Technology，2010：418-421.

[4]FENG H L，LI G H，LU W W.Trust based secure in-network data processing schema in wireless sensor networks[J].Journal of Networks，2011，6（2）：295-302.

[5]CHRISTIN D，MOGRE P S，HOLLICK M.Survey on wireless sensor network technologies for industrial automation：the security and quality of service perspectives[J].Future Internet，2010，2（2）：96-125.

[6]BUNEMAN P，KHANNA S，TAN W C.Why and where：a characterization of data provenance[C].International Conference on Database Theory，2001：316-330.

[7]SULTANA S，GHINITA G，BERTINO E.A lightweight secure scheme for detecting provenance forgery and packet dropattacks in wireless sensor networks[J].IEEE Transactions on Dependable & Secure Computing，2015，12（3）：256-269.

[8]ALAM S M I，F(xiàn)AHMY S.Energy-efficient provenance transmission in large-scale wireless sensor networks[C].IEEE International Symposium on a World of Wireless，Lucca ，2011，1：1-6.

[9]HASAN R，SION R，WINSLETT M.The case of the fake picasso：preventing history forgery with secure provenance[C].Usenix Conference on File and Storage Technologies，2009：1-14.

[10]SULTANA S，GHINITA G，BERTINO E.A lightweight secure provenance scheme for wireless sensor networks[C].International Conference on Parallel and Distributed Systems，2012：101-108.