基于生成樹的WSN溯源數據壓縮方法

毛健+王昌達

摘 要：在無線傳感器網絡（WSN）中溯源數據（Provenance）記錄了一個數據從產生至被傳輸到基站（BS）途經的所有節點以及在這些節點上對數據的操作。提出一種基于生成樹的溯源數據壓縮方法，其基本思想是在字典中存放WSN拓撲圖的生成樹并對其建立索引，在數據包傳輸過程中傳輸的是生成樹的索引而不是完整的生成樹。仿真實驗結果表明，在大規模稀疏WSN中采用該方法，溯源數據在文件大小和傳輸能耗等方面都優于已知的其它溯源數據編碼技術，而且該方法對線性溯源數據和聚合溯源數據采用完全相同的處理方式，算法實現簡單、一致性好。

關鍵詞：生成樹；溯源數據；數據壓縮

DOIDOI：10.11907/rjdk.171217

中圖分類號：TP301

文獻標識碼：A 文章編號：1672-7800（2017）007-0014-04

0 引言

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

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

鑒于此，本文提出一種基于生成樹編碼的溯源數據壓縮方法（Tree Based Provenance Encoding Scheme，TPE），TPE的應用對象是大規模稀疏WSN。TPE的基本思想是在基于字典壓縮方法的基礎上，將編碼對象由字符串轉變為WSN拓撲圖的生成樹并建立生成樹的字典，在溯源數據傳輸過程中傳輸的是生成樹在字典中的索引而不是完整的生成樹?；赥inyOS的仿真實驗表明，在大規模稀疏WSN中，相較于其它已知的溯源數據編碼技術，相同條件下采用本文TPE獲得的溯源數據編碼平均長度最短，因此在WSN中對能量和傳輸帶寬的節約效果顯著。本文主要貢獻在于：

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

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

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

1 溯源數據模型

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

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

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

2 溯源數據編碼與解碼算法

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

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

2.1 解碼

當BS收到某數據源節點傳來的數據包時，先根據其攜帶的treeID在字典中查找對應的生成樹，然后在找到的生成樹上根據sourcetID的位置即可求出數據傳輸的路徑，即從sourcetID所在的葉子節點至樹的根節點（BS）所確定的唯一路徑。

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

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）源節點處的編碼方法。當源節點ni產生一個新的數據包時，其溯源數據的生成樹索引treeID為， sourceID和currentID的值都是ni。

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

（3）匯聚節點處的編碼方法。當匯聚節點nr先后接收到來自源節點ns和nt的溯源數據ps和pt后，首先通過匯聚得到新的數據包及其上的溯源數據pr'；然后在nr上執行Algorithm 1分別求出從ns和nt至當前節點nr的路徑，并通過生成樹字典找出同時包含以上2條路徑的生成樹的索引，記為treeID'；最后將currentID更新為nr，將ns和nt作為新的sourceID。即經過匯聚節點的溯源數據為：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環境下使用TinyOS 2.1.2進行，共采用編號0～99的100個節點，WSN的跳數在2～10之間，其中編號為0的節點是BS，其它節點被隨機地選為數據源節點或轉發節點。數據采集的周期為2秒。

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

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

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

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

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

3.1 性能指標

本文使用如下性能指標分析TPE壓縮方法：

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

可通過如下公式計算平均溯源數據的長度：

其中，PSi表示節點ni上產生的單個溯源數據的長度sprovenance，m表示數據包傳輸途經的節點數量。

3.2 仿真結果

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

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

其中，ECi表示節點ni消耗的能量，n表示WSN中節點的數量。

圖3給出了WSN中在所有數據源節點都產生100個數據包的前提下，MP、BFP、TPE這3種不同方法的能量消耗，即數據包經過不同傳輸跳數時節點所消耗的總能量（TEC）。在相同環境下，MP與BFP的能耗明顯大于TPE，而且隨著網絡規模的擴大、節點數量的增加，TPE在節約能耗方面的優勢更加明顯。

4 結語

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

參考文獻：

[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，FAHMY 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.