無線傳感器網絡中一種密鑰預分發算法設計

邵明杰

【摘要】 在無線傳感器網絡（WSNs）中，密鑰預分發算法十分重要。現有的密鑰預分發算法通常是在連通性、抵抗節點捕獲的安全彈性和存儲、通信和計算過載之間進行交換，很難使各項指標都很理想。本文在對WSNs典型密鑰預分發算法的特點進行分析的基礎上，利用部署知識和密鑰空間的極限安全特性于組合模型中的方法，提出了一種新的適合于WSNs密鑰預分發算法。分析該算法在占用較小的內存、局部高概率連通的情況下，能使網絡得到完美的安全彈性。

【關鍵詞】 無線傳感器網絡 密鑰預分發 組合設計 部署知識

一、引言

典型的無線傳感器網絡由成千上萬個非常小的傳感器節點組成，這些節點由電池供能、裝載完整的傳感器系統、有一定的數據處理能力和很小的內存空間、并且能進行短距離無線通信。將這樣一些節點隨機部署在一個特定目標區域，它們就形成了一個無人照顧的無線網絡。

二、無線傳感器網絡密鑰預分發算法的主要評價指標

（1）局部連通性：指部署后位置相互鄰近節點間的連通性能。（2）抵抗節點捕獲的安全彈性：即當網絡中一部分節點被對手破壞后，剩余安全節點間能建立安全鏈路的概率。當任意多個節點被破壞后，網絡中安全節點間任意通信鏈路仍然安全，則稱安全彈性是完美的。（3）計算和通信過載：即節點間為了建立密鑰鏈路所需的計算和通信所用能量。（4）內存過載：即密鑰預分發算法所占用的節點內存。（5）全局連通性：即根據算法形成的密鑰共享圖中，孤立節點占整個網絡的比率。（6）可驗證性：通常傳感器節點無人照顧且缺乏保護，節點完全不可信任，這要求節點間通信應該具有驗證性能。

三、部署知識模型

假設傳感器節點被部署后將是靜止或在很有限的區域內運動。同時設節點被部署在一個 2維區域內，這里稱為目標區域。僅在相互信號半徑內，傳感器節點間能通信。定義傳感器節點的信號半徑為dr且為分析方便令dr=■。定義節點在目標區域內期望的位置為期望位置且用坐標（Lx，Ly）表示，節點在目標區域內最終的實際位置為居住位置且用（x，y）表示，部署傳感器節點的位置為部署位置。部署模型描述如下：

（1）設一個目標區域被分為m個尺寸相等的六邊形（也可以選用三角形等其它形狀的圖形來覆蓋這個區域）。相對于三角形和正方形六邊形能更有效的覆蓋目標區域，同時，相對于12邊形等分析起來更簡便。（2）N個傳感器節點被分到ω個群中，每個群有n=■個節點且被部署到同一個細胞（cell）中，即群i是被部署到第i個cell中，其中i∈[1，m]、θ為與某個cell相鄰的cell數量。（3）一個cell中心是一個部署點。由于是隨機部署，每個節點的居住位置與期望位置通常會有一定誤差，并且當這個誤差在一定范圍內時，利用部署知識能非常有效地改善密鑰預分發性能。設這個部署誤差最大值為e，某節點u的期望位置為（Lx，Ly）。節點u概率密度函數能表示為：

■ （1）

在這里‖·‖表示期望位置與居住位置間的距離。

四、算法實現及性能分析

基于上一部分的部署模型，提出一種新的密鑰預分發算法，它有效地獲得了組合方法在密鑰預分發設計中能提高連通性的優勢、利用部署知識能有效提高密鑰預分發性能的優勢及Blom設計具有的極限安全特性這一非常好的性質。因此，稱這一方法為利用部署知識的多密鑰空間組合設計。在這個設計中，服務器根據每個cell的位置信息為cell內的節點分發密鑰且這些密鑰來自于服務器產生的密鑰空間池中。根據上面的部署模型，給每個cell分一個對應的主密鑰空間及其ID。例如，對于第i個cell內的節點，我們用其對應的主密鑰空間為它及與這個cell相鄰的（θ-1）個cell內的節點分發密鑰。為使密鑰預分發設計具有完美的安全彈性，我們要求主cell及與之相鄰（θ-1）個cell內總節點數小于等于（t+1）。基于這種部署模型，利用組合理論對其進行分析，有下列結論。

通過融合多密鑰空間設計與部署知識于確定性密鑰預分發設計中，可以建立一個v=ω、b=■、r=t+1且k=θ的（v，b，r，k）-BIBD構造。

在這個部署模型中，共有N=b傳感器節點即每個節點作為一個區組。為了相鄰節點間能夠安全通信，需要建立成對密鑰。在部署前，每個節點存儲它所在cell對應的主密鑰空間及相鄰cell對應的主密鑰空間中的密鑰到它ROM中。根據第2節部署模型，節點需要存儲θ個密鑰空間中的密鑰。因此，有k=θ；由于若兩個區組中有來自同一個密鑰空間的密鑰，則它們就可以利用這個公共的密鑰空間建立直接密鑰。在部署模型中，一個密鑰空間被用于（t+1）個節點，因此，從區組圖的角度考慮，可以認為每個密鑰空間被使用了（t+1）次，即有r=t+1；同時，由于每個cell中有n=■個節點，且整個網絡中共有ω個cell。因此，區組總數為b=■且v=ω。

4.1 抵抗節點捕獲的安全彈性

由于當每個密鑰空間最多被t+1個節點使用時，無論整個網絡中有多少個節點被撲獲，都不會影響網絡中其它剩余安全節點間的通信。因此，被提出的設計將具有完美的安全彈性。然而，這又產生了新的問題：網絡密度很大程度上被降低。為了解決這個問題，這里提出了進行部署時，要根據密度要求來確定cell的尺寸。以 節點為例（這里設dr=300m）：當每個cell的面積為400m2時，每個cell內有α個傳感器節點。則有每個密鑰空間被θα個節點使用；當每個cell的面積為40m2時，每個cell內有β個節點。則有每個密鑰空間被θβ個節點使用。由于網絡密度D=■在這里（m+1）為某個節點通信范圍內鄰節點的數量，因此，兩種情況下的網絡密度分別為：D1=■ D2=■。因此，網絡密度與每個cell內節點的數量成正比的關系。這樣，我們就可以根據網絡密度、每個cell內節點的數量和每個密鑰空間被最多t+1個節點使用的關系來確定適合的cell尺寸。從而使整個網絡就具有了完美的安全彈性。

4.2 計算連通性

在無線傳感器網絡中對于連通性，通常由局部連通性和全局連通性兩個方面進行分析。在這個被提出的設計中，局部連通性是指：在目標區域內居住位置相鄰的節點間能夠建立直接密鑰的概率。全局連通性是指：整個網絡中任意節點間能建立直接密鑰的概率。由于，在無線傳感器網絡中，更重要的是局部連通性。因此，對全局連通性進行分析時，為了簡化這一過程，常假設此時節點的信號半徑為無限大。

4.2.1 局部連通性

首先，假設節點Na的居住位置和期望位置分別用■a和表示■a。考慮被分別部署在目標區域的兩個節點Na和Nb，設它們的期望位置已知，則它們居住位置相鄰的概率為：

■ （2）

下面定義兩個事件E和F：（1）E：能與第i個cell中的某節點Na直接通信的節點數μ。（2）F：在與Na居住位置相鄰節點中，能與節點Na建立直接密鑰的節點數μ'。這樣，網絡的局部連通性可以表示為：p■=■。為了計算F和E，需要設第i個cell用Ci表示，并且節點在期望位置的主cell內是隨機部署的，則在cell內任意節點期望位置的概率密度函數為■或0（在這里R為正六邊形的邊長）。用Si表示與主cell是i的節點共享至少一個公共密鑰的一組節點所在的主cell。根據上一部分的部署模型，可知每個Si中有19個cell。這樣，可計算得：

■ （3）

■ （4）

■ （5）

■ （6）

從而，可以得到局部連通性的概率表達式。

4.2.2 全局直接連通性

為了減少傳感器節點通信過載，設計僅考慮網絡中任意節點間直接連通的情況，稱全局直接連通性。在（v，b，r，k）-BIBD構造的密鑰預分發模型中，網絡的全局直接連通概率可以用pglobal=■來表示。則根據定理1，可得在這個設計中網絡的全局連通概率為：

pglobal=■ （7）

在這里，由于部署模型采用的是六邊形的蜂窩結構，因此，為了簡化分析，令θ=7。同時，設t=39，則根據定理1存在的充要條件，可知需滿足ω≥241，將其代入上式有pglobal≈20%。由此可知，所形成的區組圖中任意兩區組連通的概率約為20%。因此若選擇更適合的部署策略，僅需用6-8個cell就可以代替算法中要求的至少241個cell。但這時密鑰空間的極限安全性能又無法保證網絡完美的安全彈性。因此，根據實際工作要求的主要性能，對不同的部署策略需要更深入研究。

五、結語

在這篇文章中，為了有效地改善無線傳感器網絡中密鑰預分發設計的性能，我們利用部署知識、組合理論和密鑰空間極限特性的優勢，提出了一種新的算法。分析表明，當網絡中的傳感器節點能以一個確定的概率被部署到期望位置或部署后能夠發現這個節點的位置時，這個設計在占用很少的內存和通信、計算過載的情況下，為網絡提供了一個完美的抵抗節點捕獲安全彈性，并且同時具有較好的連通性能。

參 考 文 獻

[1] J.Zheng， P.Lorenz， P.Dini. Wireless Sensor Networking[J].IEEE Network， 2006（3）：2-3

[2] Fredric Newberg.wireless sensor networks design and implementation[D].Los Angeles： University of California， Los Angeles， 2002

[3] Fei Hu，Jason Tillet，Jim Ziobro，N.K.Sharma. Secure Wireless Sensor Networks：Problems and Solutions[J].Journal on Systemics， Cybernetics and Informatics.2004，11（9）：419-439.

[4] 孫永進，孫雨耕，陳寶江，房朝暉. 無線傳感器網絡1點和2點連通可靠性研究[J]. 傳感技術學報. 2004，（3）：3792385.