安全有效的無線傳感器網絡溯源數據方法*

章志明，鄧建剛

江西師范大學 軟件學院，南昌 330022

1 引言

無線傳感器網絡已經廣泛應用于軍事、醫療、工業和環境監測等各個領域[1]。但是在一些敏感領域需要采取一些措施來保證基站收集到的傳感數據的可信性[2]。由于溯源數據記錄了一個數據包在網絡傳輸中整個路徑上所有轉發或融合節點的相關信息，基站可以通過收集包含溯源信息的數據包就能夠恢復出整個數據包的傳輸路徑，因此溯源數據被認為是一種有效的方法來評估數據的真實可靠性[3]。由于傳感器節點計算、通信和存儲空間有限，因此必須設計有效的溯源數據方案。

近年來國內外學者提出了一些有效的溯源數據方案[3-8]。為了記錄路徑上每個轉發節點的溯源信息，最基本方法是把每個節點的溯源信息直接附加到數據包上[4]，但這種方法隨著路徑長度的增加，溯源數據的大小將呈線性增加。為了減小溯源數據的大小，文獻[5]設計了一組基于概率包標記的溯源數據方案，在這些方案中，傳輸路徑上的每個節點以一定的概率，把自己的信息附加到數據包上，但基于概率包標記方案，基站需要收集到足夠多的包含溯源信息的數據包才能恢復出整個數據包的傳輸路徑。為了減少收集數據包的數量，同時減小溯源數據的大小，文獻[3,6-9]提出了基于壓縮技術的無線傳感器網絡溯源數據方案，文獻[3,6]提出基于布隆過濾器的溯源數據方案，但布隆過濾器存在假陽性的問題。為了解決布隆過濾器存在假陽性的問題，文獻[7]提出了一種基于算術編碼的無損壓縮溯源數據方案，文獻[8]提出一種基于數字字典的溯源數據方案，但該方案需要每個中間轉發節點存儲一個字典表，額外增加了網絡負擔。文獻[3-6]的溯源數據大小都會隨著路徑長度的增加而增大，并且大多數方案只考慮了溯源數據的修改或偽造攻擊，都沒有考慮多個惡意節點合謀對溯源數據發起插入、刪除和不標注等攻擊，并且不能定位到發起攻擊的惡意節點位置。

本文基于正交碼和消息鑒別碼鏈，提出一種安全有效的溯源數據傳輸方案（orthogonal code-based provenance scheme，OP）。在OP方案中，傳輸路徑上的節點收到數據包時不是把自己的溯源數據直接加入到數據包中，而是把自己的溯源數據與數據包中原有的溯源數據做正交碼加運算形成一個固定長度的常量，同時計算相關溯源數據的消息鑒別碼，并形成一個新的固定長度的消息鑒別碼鏈，最后更新數據包中的溯源數據域。基站（base station,BS）收到一個包含溯源數據的數據包后，取出相關的溯源數據，恢復出可能的數據包傳輸路徑，并使用消息鑒別碼鏈對可能傳輸路徑進行驗證，驗證通過則為正確的傳輸路徑，否則通過執行惡意節點定位算法來定位到發起攻擊的惡意節點位置。

本文的主要貢獻有：（1）基于正交碼和消息鑒別碼鏈，提出一種安全有效的溯源數據傳輸方案（OP方案）。OP方案只需要一個數據包就能恢復出數據包的傳輸路徑，并且溯源數據的大小與路徑的長度無關。（2）OP方案不僅能抵抗單個惡意節點修改或偽造溯源數據攻擊，還能抵抗多個惡意節點合謀發起的刪除、插入溯源數據等攻擊，并能定位到發起攻擊的惡意節點位置。（3）性能分析及實驗仿真表明，與現有的方案相比，隨著路徑長度的增加，方案在存儲空間、能量消耗等方面具有明顯優勢。

2 相關工作

目前國內外學者已經提出了一些有效的溯源數據方案，這些方案大體可分為基本溯源數據方案、基于概率包標記和壓縮技術等溯源數據方案。

Hasan等人[4]提出了一種基本的溯源數據方案，在該方案中，每個節點把自己的溯源數據直接附加到數據包上，并對自己的溯源數據進行數字簽名，當BS收到含有溯源數據數的數據包后，依次取出每個節點的溯源數據，最終恢復出傳輸路徑。這種溯源數據方法隨著路徑長度的增加，溯源數據的大小將呈線性增加。

為了減小溯源數據的大小，Alam等人[5]設計了三種基于概率包標記的溯源數據方案，這三種溯源數據方案基本思想都是一樣：數據包傳輸路徑上的每個節點以一定的概率，把自己的溯源數據附加到數據包上，BS只要收集到足夠多的包含溯源信息的數據包就能恢復出整個數據包的傳輸路徑，三種方案不同在于分別利用位置序列、初等乘法和Rabin指紋技術對溯源數據進行編碼。為了減少能量的消耗，Alam等人[10]還提出了一種概率包標記的溯源數據方案，但是該方案沒有采用任何安全機制來保證數據的安全性。

為了減少收集數據包的數量，同時減小溯源數據的大小，文獻[3,6-7]提出了基于壓縮技術的無線傳感器網絡溯源數據方案。Sultana等人[3,6]提出基于布隆過濾器的溯源數據方案（bloom filter-based provenance scheme，BFP），在BFP方案中，每個數據包被初始化一個布隆過濾器，用于存儲路徑上每個節點的溯源數據，當收到包含布隆過濾器的數據包后，BS從數據包的布隆過濾器中取出并驗證溯源數據，最后恢復出傳輸路徑。但基于布隆過濾器的方案存在假陽性問題,為了解決布隆過濾器的假陽性問題，Hussain等人[7]提出了一種基于算術編碼的無損壓縮溯源數據方案，該方案利用算術編碼技術把路徑上每個節點的溯源數據壓縮成一個0到1之間的小數，然后把壓縮后的溯源數據附加到數據包上依次傳送給BS。該方案中，溯源數據的大小不直接依賴于傳輸路徑的長度，而是取決于節點出現在數據包傳輸路徑上的概率，概率越大，則溯源數據越小。為了獲取每個節點出現在數據包傳輸路徑上的概率，首先需要一個時間周期觀察、計算每個節點出現在數據包傳輸路徑上的次數。

為了解決基于有損壓縮的溯源數據方案存在溯源數據的大小隨著傳輸路徑長度增加而增大的問題，Wang等人[8]提出了一種基于字典的溯源數據方案。在該方案中，每條路徑用一條獨一無二的字典索引表示，一個數據包的溯源數據就用此數據包傳輸路徑的字典索引來表示，因為一條固定大小的路徑字典索引可以代表一條任意長度的傳輸路徑，所以數據包的溯源數據是一個與路徑長度無關的常量值。但是在該方案中，每一個節點需要存儲、維護一張經過該節點的路徑索引字典表。Wang等人[9]還提出了一種基于動態貝葉斯網絡的溯源數據壓縮方案來解決基于有損壓縮的溯源數據方案存在的問題。

3 系統模型

3.1 正交碼

正交碼（orthogonal code）被廣泛應用于無線通訊、信息隱藏等領域[11-12]。對于正交碼的詳細定義請參考文獻[13]，正交碼的產生請參考文獻[14]，在此不進行詳細描述。正交碼具有以下三種特性：

（1）任意兩個相異的正交碼做內積運算，其運算結果為0。例如，如果A、B為兩個相異的正交碼，則：

（2）任意一個正交碼與其本身做內積運算，其運算結果為1。例如，如果A為一正交碼，則：

（3）正交碼具有可累加性，K個正交碼相加后，仍保持有（1）、（2）項的特性。例如，如果有A、B、C、D四個相異正交碼，S為A、B、C三個正交碼相加后的值，則：

從式（1）中可以判斷，A包含在S中，從式（2）中可以判斷，D不包含在S中。

3.2 網絡模型

整個傳感器網絡由n個普通節點、m個惡意節點和一個BS組成。每個節點i在部署之前都被分配一個與BS共享的對稱密鑰Ki,BS，分配一個獨一無二的正交碼作為身份標記IDi，這個身份標記就是節點附加到數據包上的溯源數據。假設在網絡被部署到目標區域后，每個節點不再移動，所有節點形成一棵以BS為根的樹形結構，在網絡運行過程中，可能一些節點由于能量耗盡而死亡，從而引起網絡路徑發生變化，因此，每隔一段時間，BS將及時更新整個網絡的拓撲結構。當節點感知到數據后，將通過多跳的方式把數據發送給BS，在數據包被發送給BS的過程中，每個中間轉發節點或數據融合節點將把自己的溯源數據附加到數據包上傳給下一個節點，當BS收到一個包含溯源數據的數據包，將根據溯源數據恢復出數據包的溯源路徑也即傳輸路徑。數據包的傳輸路徑分成兩種，一種是簡單路徑，如圖1（a）所示，節點n1把感知的數據分別通過節點n2、n3傳送給BS，其簡單傳輸路徑用(n1,n2,n3)表示；另一種是樹狀路徑，如圖1（b）所示，節點n4、n5分別把感知的數據發送給n6,n6對收到的數據及自己感知的數據進行融合再分別通過節點n7傳送給BS，其樹狀路徑用((n4,n5),n6,n7)表示。國內外學者對于傳感數據的產生、融合已經提出了許多方案[15-16]，本文在此不進行詳細描述，本文主要關注如何安全、有效地生成、傳送和恢復溯源數據。本文假設基站的計算、存儲和通信能力都不受限制，并且假設敵人只能俘獲普通傳感節點，而不能俘獲基站。為了方便閱讀和說明，表1對本文所用到的符號進行了描述。

Fig.1 Transmission path graphs of data packet圖1 數據包的傳輸路徑圖

Table 1 Notation definition of proposed scheme表1 符號定義表

3.3 攻擊模型與安全目標

假設在網絡中，除了BS不會被俘獲，其余的普通節點都有可能被俘獲，節點一旦被俘獲，攻擊者可以很容易地獲取其中的安全信息，如身份、密鑰等，并以俘獲節點為惡意節點發起一系列攻擊，這些攻擊不但會使BS做出錯誤的決策，而且會消耗大量網絡的寶貴資源，惡意節點能發起以下攻擊：

（1）惡意節點可以否認自己的溯源數據。

（2）惡意節點能修改數據包上的溯源數據。

（3）一個或多個惡意節點能單獨或合謀刪除數據包上的溯源數據。例如，在圖2（a）中，惡意節點n4試圖刪除節點n3的溯源數據，使路徑變成{n1,n2,n4,n5,n6}。路徑上多個惡意節點也可能合謀刪除數據包上的溯源數據，例如，在圖2（b）中，惡意節點n2和n4試圖合謀刪除節點n3的溯源數據，使路徑變成{n1,n2,n4,n5,n6}。

Fig.2 Malicious nodes attack graphs(black nodes represent malicious nodes and white nodes represent normal nodes)圖2 惡意節點攻擊示意圖（黑色節點表示惡意節點，白色節點表示正常節點）

（4）一個或多個惡意節點能故意不標注自己的溯源數據，從而達到欺騙BS的目的。例如，在圖2（c）中，惡意節點n3和n4故意不把自己的溯源數據增加到數據包上，此時，路徑變成{n1,n2,n5,n6}。

（5）多個惡意節點能合謀往數據包上插入一條或多條溯源數據。例如，在圖2（d）中，惡意節點n3和n4合謀往數據包上插入了一條惡意節點n4的溯源數據，此時路徑變成{n1,n2,n3,n4,n5,n6}。

本文提出方案的安全目標是能抵抗惡意節點發起的以上攻擊。

4 安全有效的溯源數據方案

本文提出的溯源數據方案（OP方案）具體分為產生溯源數據、恢復溯源數據和驗證溯源數據三個步驟。

4.1 產生溯源數據

溯源數據產生是指數據包傳輸路徑上每個節點生成自己的溯源數據并把溯源數據附加到數據包上的過程。整個數據包傳輸路徑上包含三種節點：產生數據包的源節點、僅轉發數據包的轉發節點和融合數據的融合節點。接下來將分別詳細描述這三種節點產生溯源數據的過程。

（1）源節點產生溯源數據

當源節點S想要發送傳感數據給BS，在生成完數據包后，它將在數據包上創建四個字段用于存儲數據包的溯源數據，字段格式如表2所示。其中，Seq-Number字段存放當前數據包的標識，Count字段存放源節點距離BS的跳數，Provenance字段存放節點的溯源數據，MAC字段存放溯源數據的消息鑒別碼。創建完存儲溯源數據的字段后，節點S產生一個數據包序列號SN存入Seq-Number字段，使Count字段的值為1，把PVS=IDS作為溯源數據存入Provenance字段，計算MACS=CKS,BS(PVS)作為溯源數據的消息鑒別碼并存入MAC字段，最后把包含溯源數據的數據包發送給下一個節點。圖1（a）中的數據源節點n1產生的溯源數據如表2所示。

Table 2 Provenance of source noden1表2 源節點n1的溯源數據

（2）轉發節點產生溯源數據

當一個中間轉發節點ni收到序列號為SN的數據包，它將更新Count字段的值，使Count=Count+1，計算PVi=PVi-1+IDi作為溯源數據并更新Provenance字段，計算MACi=MACi-1⊕CKi,BS(PVi)作為溯源數據的消息鑒別碼并更新MAC字段，最后把更新后數據包發送給下一個節點。圖1（a）中的節點n2和n3產生的溯源數據分別如表3和表4所示。

Table 3 Provenance of forwarding noden2表3 轉發節點n2的溯源數據

Table 4 Provenance of forwarding noden3表4 轉發節點n3的溯源數據

（3）融合節點產生溯源數據

當一個融合節點nj收到孩子節點nj1和nj2發送的數據，它首先把nj1、nj2和自己的數據融合、生成新的數據包，然后分別從nj1和nj2原來數據包中取出溯源數據，使Count=Count+1，并把Count值存入新融合數據包的Count字段，計算PVj=PVj1+PVj2+IDj作為新的溯源數據并存入新融合數據包的Provenance字段，計算MACj=MACj1⊕MACj2⊕CKj,BS(PVj)作為溯源數據的消息鑒別碼并存入新融合數據包的MAC字段，最后把新融合數據包發送給下一個節點。圖1（b）中的節點n6產生的溯源數據如表5所示。

4.2 恢復溯源數據

當BS收到一個節點nt發送的數據包，它取出數據包Count字段的值，設為Length，取出Provenance字段的值，設為PVt，然后以節點nt為根節點，在網絡中進行深度優先搜索（depth first search，DFS），找到M條長度為Length的路徑集合P[M]。然后在P[M]集合中找出一條或多條路徑，使這一條或多條路徑上的所有節點的身份標記IDi與PVt分別做正交碼的內積運算，結果都等于1，因為根據正交碼的特性，如果都等于1，可知這一條或多條路徑上的所有節點的溯源數據都在PVt中，則這一條或多條路徑就是此數據包的可能傳輸路徑，如果傳輸路徑是多條，則把這多條路徑合并成一條具有樹型結構的融合路徑。如果P[M]集合中沒有一條路徑上的所有節點的身份標記IDi與PVt分別做正交碼的內積運算，結果都等于1，表示此數據包受到攻擊，BS將立即丟棄該數據包。具體查找數據包的可能傳輸路徑算法如算法1所示，根據算法1，圖1（a）是一條簡單的可能傳輸路徑，用(n1,n2,n3)表示，圖1（b）是一條樹狀的可能傳輸路徑，用((n4,n5),n6,n7)表示。

Table 5 Provenance of forwarding noden6表5 轉發節點n6的溯源數據

算法1查找數據包的可能傳輸路徑

輸入：M條長度為Length的路徑集合P[M]；數據包的溯源數據PVt。

輸出：數據包的可能傳輸路徑(transmission path,TP)

4.3 驗證溯源數據

溯源數據具體驗證算法如算法2所示。BS根據算法1得到數據包的可能傳輸路徑（TP），依次從路徑TP中取出節點的身份標記IDi，按照4.1節產生溯源數據的方法，依次計算得到各節點的溯源數據和對應的消息鑒別碼PV=[PV1',PV2',…,PVt']，MAC=[MAC1',MAC2',…,MACt']；然后從收到的數據包中取出Provenance字段的值，設為PVt，取出MAC字段的值，設為MACt；最后比較MACt'是否與MACt相等，如果相等，則表示路徑TP上所有節點的溯源數據是真實的，否則表示路徑TP上節點的溯源數據被篡改。如果節點的溯源數據被篡改，BS將從路徑TP的最后一個節點nt開始向前依次驗證每個節點的溯源數據，從而定位到發起攻擊的惡意節點位置，具體惡意節點定位算法如算法3所示。

算法2溯源數據驗證算法

輸入：數據包的可能傳輸路徑TP；數據包MAC字段的值MACt。

輸出：驗證通過返回True，否則返回False。

從路徑TP恢復出的溯源數據PV=[PV1',PV2',…,PVt']；

從路徑TP恢復出的消息鑒別碼MAC=[MAC1',MAC2',…,MACt']。

算法3惡意節點定位算法

輸入：從路徑TP恢復出的溯源數據PV=[PV1',PV2',…,PVt']；從路徑TP恢復出的消息鑒別碼MAC=[MAC1',MAC2',…,MACt']；數據包MAC字段的值MACt。

輸出：惡意節點ni。

5 安全性分析

3.3節分析了攻擊者一旦俘獲了網絡中的某些節點，將以俘獲節點為惡意節點發起一系列攻擊，這些攻擊不但會使BS做出錯誤的決策，而且會消耗大量網絡的寶貴資源。本章將討論本文提出的OP方案如何抵抗3.3節提出的惡意節點發起的圖2所示的一系列攻擊。

定理1任何一個節點都不能否認自己的溯源數據。

證明每個節點ni往數據包的溯源數據字段上更新自己的溯源數據時，同時用自己與BS共享的對稱密鑰Ki,BS計算對應的消息鑒別碼。假如一個惡意節點ni往溯源數據字段上更新自己的溯源數據PVi=PVi-1+IDi時，用前一個節點ni-1的消息鑒別碼MACi-1來代替自己對PVi計算的消息鑒別碼MACi，以此來否認自己的溯源數據，則根據算法2和算法3就能驗證并定位到節點ni，因此任何一個節點不能否認自己的溯源數據。

定理2任何一個惡意節點不能修改數據包溯源數據字段上的溯源數據而不被檢測。

證明一個惡意節點ni收到它前一個節點ni-1發送的溯源數據，它既可以修改溯源數據PVi-1，也可以修改PVi-1的消息鑒別碼MACi-1。當它僅修改PVi-1時，根據算法1將不能恢復出任何一條可能的傳輸路徑TP，BS將丟棄該數據包；當它僅修改消息鑒別碼MACi-1時，則根據算法2和算法3就能驗證并定位到節點ni，因此任何一個惡意節點不能修改數據包溯源數據字段上的溯源數據而不被檢測。

定理3任何一個或多個惡意節點不能單獨或合謀從數據包溯源數據字段上刪除一條或多條溯源數據而不被檢測。

證明一個或多個惡意節點收到數據包時，刪除數據包溯源數據字段上的一條或多條溯源數據有兩種情況。

第一種情況是惡意節點ni刪除它前面的一個或多個節點的溯源數據。例如，在圖2（a）中，惡意節點n4試圖刪除節點n3的溯源數據，在這種情況下，因為n4收到n3發送給它的溯源數據PV3為節點n4前面所有節點的身份標記值做正交碼加運算得到的一個新的正交碼值，即PV3=PV1+PV2+ID3，所以它沒辦法從PV3中刪除節點n3身份標記值；同樣溯源數據的消息鑒別碼MAC3=MAC1⊕MAC2⊕CK3,BS(PV3)，由于它沒有節點n3與BS共享的對稱密鑰K3,BS，不能計算出PV3的消息鑒別碼CK3,BS(PV3)，因此它也沒辦法從MAC3中刪除節點n3的消息鑒別碼CK3,BS(PV3)。

第二種情況是多個惡意節點合謀刪除它們之間的一個或多個節點的溯源數據。例如，在圖2（b）中，惡意節點n2和n4試圖合謀刪除節點n3的溯源數據，當n2收到溯源數據時它直接把數據包發送給另一個惡意節點n4，通過跳過節點n3從而達到刪除節點n3的溯源數據的目的。在這種情況下，傳輸路徑TP={n1,n2,n4,n5,n6}，路徑長度為5。BS收到數據包后，通過深度優先（DFS）搜索，找到1條長度為5的路徑集合P[1]={n2,n3,n4,n5,n6}，然后根據算法1可知路徑集合P[1]中沒有任何一條有效的傳輸路徑，表示此數據包受到攻擊，BS將立即丟棄該數據包。

綜上所述，任何一個或多個惡意節點不能單獨或合謀從數據包溯源數據字段上刪除一條或多條溯源數據而不被檢測。

定理4任何一個或多個惡意節點不能故意不標注自己的溯源數據而不被檢測。

證明一個或多個惡意節點收到溯源數據時，它可以故意不標注自己的溯源數據。例如，在圖2（c）中，惡意節點n3和n4故意不把自己的溯源數據更新到數據包溯源數據字段上，以此達到欺騙BS的目的。在這種情況下，傳輸路徑TP={n1,n2,n5,n6}，路徑長度為4。BS收到數據包后，通過深度優先（DFS）搜索，找到1條長度為4的路徑集合P[1]={n3,n4,n5,n6}，然后根據算法1可知路徑集合P[1]中沒有任何一條有效的傳輸路徑，表示此數據包受到攻擊，BS將立即丟棄該數據包，因此任何一個或多個惡意節點不能故意不標注自己的溯源數據而不被檢測。 □

定理5多個惡意節點不能合謀往數據包溯源數據字段上插入一條或多條溯源數據而不被檢測。

證明一個惡意節點收到溯源數據時，可以與路徑外的另一個或多個惡意節點合謀往數據包溯源數據字段上插入一條或多條溯源數據。例如，在圖2（d）中，惡意節點n3和n4合謀往數據包溯源數據字段上插入了一條不在本次數據包傳輸路徑上的惡意節點n4的溯源數據。在這種情況下，傳輸路徑TP={n1,n2,n3,n4,n5,n6}，路徑長度為6。BS收到數據包后，通過深度優先搜索，找到長度為6的但不包括節點n4的路徑集合，假設圖（d）中的節點n1前面還有一個節點n0，則通過深度優先搜索出的路徑集合P[1]={n0,n1,n2,n3,n5,n6}，然后根據算法1可知路徑集合P[1]中沒有任何一條有效的傳輸路徑，表示此數據包受到攻擊，BS將立即丟棄該數據包，因此多個惡意節點不能合謀往數據包溯源數據字段上插入一條或多條溯源數據而不被檢測。 □

6 性能分析

本文提出的OP方案將與文獻[4,6]及基于簡單消息鑒別碼的MP（message authentication code-based provenance scheme）方案在存儲空間和能量消耗方面進行比較。文獻[6]提出一種基于布隆過濾器的方案（bloom filter-based provenance scheme，BFP），它使用一個固定大小的布隆過濾器來嵌入傳輸路徑上所有節點的溯源數據。文獻[4]提出了一種安全的溯源數據方案（secure provenance scheme，SSP）。為了方便比較，與文獻[6]一樣，把SSP方案中每個節點i的溯源數據簡化為Pi=＜ni,hash(Di),Ci＞，其中ni表示節點的身份標記，hash(Di)表示對數據進行哈希運算，Ci=Sign(ni,hash(Di)|Ci-1)表示對ni,hash(Di),Ci-1的數字簽名。與文獻[6]一樣，也考慮一種基于簡單消息鑒別碼的方案MP，在MP方案中傳輸路徑上的每個節點ni依次把自己的身份標記IDi和身份標記的消息鑒別碼直接附加到數據包中。

6.1 存儲開銷

假設從源節點到基站的傳輸路徑長度為L，文獻[4]的SSP方案和基于簡單消息鑒別碼的MP方案中的一個節點身份標記長度為2 Byte，本文提出的OP方案的一個節點身份標記長度為4 Byte，一個數據包序列號（Seq-Number）長度為12 bit，數據包中源節點距離BS的跳數（Count）用12 bit存儲。在文獻[6]的BFP方案中，一個數據包的溯源數據需要的存儲開銷為-L×ln(Pfp)/(ln2)2，其中Pfp為布隆過濾器假陽性概率。在文獻[4]中，使用SHA-1作為加密哈希算法，產生固定長度為160 bit的哈希值，使用文獻[17]的數字簽名方法，產生長度為160 bit的數字簽名，則SSP方案中，一個數據包的溯源數據需要的存儲開銷為L×42 Byte。在基于簡單消息鑒別碼的方案MP中，使用文獻[18]的方法產生長度為4 Byte的消息鑒別碼，則MP方案中，一個數據包的溯源數據需要的存儲開銷為L×6 Byte。在本文提出的OP方案中，一個數據包的溯源數據由4個字段組成，如表2所示，即一個數據包的溯源數據可表示為＜SNi,count,PVi,MACi＞。其中，SNi表示長度為12 bit的數據包序列號（Seq-Number）；count表示長度為12 bit的源節點距離BS的跳數；PVi表示傳輸路徑上所有節點的身份標記IDi做正交碼的加運算得到的結果，根據正交碼加運算性質，任意多個正交碼做加運算的結果其長度不變，即一個節點身份標記IDi長度為4 Byte，則PVi的長度仍然為4 Byte；MACi表示長度為128 bit的消息鑒別碼。因此在本文提出的OP方案中，一個數據包的溯源數據需要的存儲開銷為23 Byte。綜上所述，BFP方案、SSP方案和MP方案都與傳輸路徑長度有關，隨著傳輸路徑長度增加，其存儲開銷也隨之增加。而OP方案的PVi是正交碼做加運算的結果，其值是固定長度，MACi是多個消息鑒別碼做異或運算的結果，其值也是固定長度，因此OP方案的溯源數據存儲開銷為一個常量。表6描述了本文提出的OP方案與BFP方案、SSP方案、MP方案的具體存儲開銷，其中L表示從源節點到基站的傳輸路徑長度。

Table 6 Comparison of storage overhead表6 存儲開銷比較表

6.2 能量消耗

節點能量的消耗主要是對數據包的接收和發送，與數據包的大小直接相關。假設數據包的傳輸路徑長度為L，在BFP方案、SSP方案和MP方案中，一個數據包的溯源數據需要的存儲開銷分別為-L×ln(Pfp)/(ln2)2、L×42 Byte和L×6 Byte，其相應的能量消耗也分別與 -L×ln(Pfp)/(ln2)2、L×42 Byte和L×6 Byte成比例增加。而在本文提出的OP方案中，溯源數據存儲開銷為一個常量，顯然，隨著傳輸路徑長度增加，OP方案的能量消耗要比其他方案要少很多。

6.3 計算開銷

本節將分析本文提出的OP方案的計算開銷。由于OP方案假設BS的計算、存儲和通信能力都不受限制，因此不討論BS恢復和驗證溯源數據的計算開銷，只分析數據源節點、融合節點和中間轉發節點的計算開銷。本文不考慮節點收集數據、產生數據包和把數據存入數據包等基本操作，重點分析節點的計算操作。用OP_Add表示執行一次正交碼的加運算，OP_XOR表示執行一次異或運算，OP_MAC表示執行一次計算消息M的消息鑒別碼運算。OP方案的計算開銷主要由源節點產生溯源數據，轉發節點產生溯源數據和融合節點產生溯源數據三部分組成。

（1）源節點產生溯源數據。源節點產生溯源數據的主要計算操作為計算一次自己身份標記的消息鑒別碼，因此源節點的計算開銷為：

（2）轉發節點產生溯源數據。當轉發節點i收到數據包時，它的主要計算操作為：將自己的溯源數據IDi與數據包中的溯源數據PVi-1做正交碼加運算，得到一個固定長度的常量值PVi作為新的溯源數據，然后計算PVi的消息鑒別碼，并與數據包中的原消息鑒別碼MACi-1做異或運算，得到新的溯源數據的消息鑒別碼MACi。因此，轉發節點的計算開銷為：

（3）融合節點產生溯源數據。當一個融合節點j收到m個孩子節點發送的數據包，它的主要計算操作為：將自己的溯源數據IDj與m個孩子節點發送的數據包中的溯源數據做正交碼加運算，得到一個固定長度的常量值PVj作為新的溯源數據，然后計算PVj的消息鑒別碼，并與m個孩子節點發送的數據包中的原消息鑒別碼做異或運算，得到新的溯源數據的消息鑒別碼MACj。因此，融合節點的計算開銷為：

綜上所述，OP方案的計算開銷主要是執行了正交碼的加運算、異或運算和計算消息鑒別碼運算，其中正交碼的加運算本質上是一種類似于異或運算的操作，而異或運算和計算消息鑒別碼運算都是密碼學中最基本的輕量級操作，因此OP方案是一種輕量級的安全有效方案。

7 仿真實驗

仿真實驗環境是在TinyOS-2.1.2的TOSSIM平臺上進行，在Tiny OS上配置Power TOSSIMz插件來仿真節點能量的消耗。100個節點隨機分布在100 m×100 m的正方形區域內，在節點被部署之前，按文獻[16]的方法為每個節點分配一個獨一無二的正交碼作為節點的身份編號，BS作為目的節點放置在區域的中心位置，節點部署之后將不再移動。隨機選取網絡的一些節點作為數據源節點、融合節點和惡意節點，其他節點作為中間轉發節點。數據源節點每隔1 s通過多跳的方式向BS發送一次數據，每個數據包的長度為256 Byte。當惡意節點成為中間轉發節點后，它將以一定的概率篡改轉發的數據包。對于每個設置的參數，取仿真50次得到的平均值。

7.1 性能指標

與文獻[6]一樣，本節從以下幾方面對方案的性能進行仿真評估。

（1）驗證錯誤率

當BS收到源節點發送的數據包，它將執行算法1和算法2恢復和驗證數據包中的溯源數據，由于溯源數據被惡意節點篡改或網絡拓撲結構的改變，使得溯源數據不正確，從而驗證失敗。假設BS總共收到L個數據包，其中有d個數據包的溯源數據不正確，則驗證錯誤率。

（2）平均溯源數據大小

假設BS收到L個數據包，平均溯源數據大小（average provenance size，APS）是指L個數據包的溯源數據長度的平均值，即：

其中，PRi表示數據包Pi的溯源數據長度值。

（3）總能量消耗

假設網絡中共有L個節點，總能量消耗（total energy consumption，TEC）是指L個節點能量消耗總和，即：

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

7.2 仿真結果

當BS收到源節點發送的數據包，它將試圖恢復和驗證數據包中的溯源數據，從而恢復數據的完整傳輸路徑。由于網絡拓撲結構的改變或溯源數據被惡意節點篡改，使得溯源數據不正確，從而驗證失敗。圖3（a）描述了路徑長度分別為2、4、6、8、10、12和14跳，OP方案與BFP方案的驗證錯誤率。從圖3（a）中可以看出，當BFP方案的布隆過濾器大小為20 Byte，路徑長度大于8跳時，驗證錯誤率要明顯高于OP方案，這是由于布隆過濾器存在假陽性的問題，即把不在集合中的元素錯判成集合中的元素，從而在一定程度上影響了BFP方案的驗證錯誤率。圖3（b）描述了路徑中存在惡意節點，并且惡意節點篡改數據的概率q分別為0.1、0.2和0.3的情況下，路徑長度為8跳，數據包個數分別從0到60時，OP方案的驗證錯誤率。從圖3（b）中可以看出，隨著惡意節點篡改數據概率增大，驗證錯誤率也越來越大，但是隨著數據包個數的增加，驗證錯誤率將趨于穩定，例如，當數據包個數超過40個時，驗證錯誤率都接近于0.02。

Fig.3 Verification error rate圖3 驗證錯誤率

圖4描述了OP方案、BFP方案、SSP方案和MP方案包在路徑長度分別為2、4、6、8、10、12和14跳時的平均溯源數據大小。在SSP方案和MP方案中，傳輸路徑上的每個節點收到數據包時都是直接把自己的溯源數據加入到數據包中，因此溯源數據大小與傳輸路徑長度直接相關，隨著傳輸路徑長度增加，其平均溯源數據大小呈線性增加。雖然BFP方案的溯源數據大小也與傳輸路徑長度相關，但沒有SSP方案和MP方案明顯。而在本文提出的OP方案中，傳輸路徑上的每個節點收到數據包時不是直接把自己的溯源數據加入到數據包中，而是把自己的溯源數據與數據包中的溯源數據做正交碼加和異或運算，其結果是一個固定長度值。從圖4中可以看出，當路徑長度大于4跳時，OP方案的平均溯源數據大小要明顯低于MP方案，當路徑長度小于10跳時，OP方案的平均溯源數據要略大于BFP方案，但當路徑長度大于10跳時，OP方案的平均溯源數據要小于BFP方案。

Fig.4 Average provenance size under different path lengths圖4 不同路徑長度下的平均溯源數據大小

圖5描述了路徑長度分別為2、4、6、8、10、12和14跳，OP方案、BFP方案和MP方案總能量消耗。從圖5中可以看出，當路徑長度超過8跳時，MP方案能量消耗急劇增加，遠遠大于OP和BFP方案，這是由于MP方案中每個數據包的溯源數據大小與路徑長度呈線性關系。從圖5中可以看出，當路徑長度超過8跳時，OP方案總能量的消耗要小于BFP方案。

8 總結

Fig.5 Total energy consumption under different path lengths圖5 不同路徑長度下的總能量消耗

本文利用正交碼和消息鑒別碼鏈，提出一種安全有效的溯源數據傳輸方案（OP方案）。OP方案把正交碼作為身份標記ID（溯源數據），當傳輸路徑上的一個節點ni收到數據包時把自己的溯源數據與數據包中的溯源數據做正交碼加運算，產生一個固定長度的溯源數據作為數據包的新溯源數據，并且形成一個新的固定長度的消息鑒別碼鏈。通過溯源數據的正交加運算，OP方案只需要一個數據包就能恢復出數據包的傳輸路徑，并且溯源數據的大小與路徑的長度無關。通過消息鑒別碼鏈，OP方案不僅能抵抗單個惡意節點修改或偽造溯源數據攻擊，還能抵抗多個惡意節點合謀發起的刪除、插入溯源數據等攻擊，并能定位到發起攻擊的惡意節點位置。性能分析及實驗仿真表明與現有的方案相比，隨著路徑長度的增加，方案在存儲空間、能量消耗等方面也具有明顯優勢。