無線傳感器網(wǎng)絡(luò)中一種密鑰預(yù)分發(fā)算法設(shè)計

邵明杰

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

【關(guān)鍵詞】 無線傳感器網(wǎng)絡(luò) 密鑰預(yù)分發(fā) 組合設(shè)計 部署知識

一、引言

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

二、無線傳感器網(wǎng)絡(luò)密鑰預(yù)分發(fā)算法的主要評價指標

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

三、部署知識模型

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

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

■ （1）

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

四、算法實現(xiàn)及性能分析

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

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

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

4.1 抵抗節(jié)點捕獲的安全彈性

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

4.2 計算連通性

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

4.2.1 局部連通性

首先，假設(shè)節(jié)點Na的居住位置和期望位置分別用■a和表示■a?？紤]被分別部署在目標區(qū)域的兩個節(jié)點Na和Nb，設(shè)它們的期望位置已知，則它們居住位置相鄰的概率為：

■ （2）

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

■ （3）

■ （4）

■ （5）

■ （6）

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

4.2.2 全局直接連通性

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

pglobal=■ （7）

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

五、結(jié)語

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

參 考 文 獻

[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] 孫永進，孫雨耕，陳寶江，房朝暉. 無線傳感器網(wǎng)絡(luò)1點和2點連通可靠性研究[J]. 傳感技術(shù)學(xué)報. 2004，（3）：3792385.