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

邵明杰

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

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

一、引言

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

二、無(wú)線(xiàn)傳感器網(wǎng)絡(luò)密鑰預(yù)分發(fā)算法的主要評(píng)價(jià)指標(biāo)

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

三、部署知識(shí)模型

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

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

（1）

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

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

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

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

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

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

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

4.2 計(jì)算連通性

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

4.2.1 局部連通性

首先，假設(shè)節(jié)點(diǎn)Na的居住位置和期望位置分別用a和表示a。考慮被分別部署在目標(biāo)區(qū)域的兩個(gè)節(jié)點(diǎn)Na和Nb，設(shè)它們的期望位置已知，則它們居住位置相鄰的概率為：

（2）

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

（3）

（4）

（5）

（6）

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

4.2.2 全局直接連通性

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

pglobal= （7）

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

五、結(jié)語(yǔ)

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

參 考 文 獻(xiàn)

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