WSN的對密鑰管理研究

張德樹

（滁州職業(yè)技術學院信息工程系，安徽滁州 239000）

WSN的對密鑰管理研究

張德樹

（滁州職業(yè)技術學院信息工程系，安徽滁州 239000）

無線傳感器節(jié)點由于計算能力小、電源能量有限、通信能力弱和存儲空間非常有限等這些弱點的存在，在對無線傳感器網(wǎng)絡的安全方案設計時，必須考慮到節(jié)點的這個特點。文章先對現(xiàn)有的幾種密鑰預分發(fā)方案的分析可知，現(xiàn)有的各種對密鑰預分發(fā)方案不太適應大規(guī)模WSN發(fā)展的要求，為此，我們提出了一種新的適合發(fā)展大規(guī)模WSN的對密鑰預分發(fā)方案。

傳感器網(wǎng)絡；對密鑰；密鑰管理；節(jié)點

1 WSN的密鑰管理的必要性

1.1 WSN結構

無線傳感器網(wǎng)絡（Wireless Sensor Network，WSN）是由一個個無線傳感器節(jié)點組成，如圖1所示，這些節(jié)點具有對外部的某種物理信息進行采集、處理和傳輸?shù)哪芰?，這些物理信息可能是溫度、光照強度、生物信息、壓力等。當這些節(jié)點被分布在傳感區(qū)域后，能以一定的方式自組織成一個網(wǎng)絡。這個傳感區(qū)域中各節(jié)點將采集或監(jiān)測到的數(shù)據(jù)通過一次或多次轉發(fā)的方式最后匯聚到傳感區(qū)域中特殊節(jié)點的槽節(jié)點（sink節(jié)點）或者基站（Base Station）［1］。槽節(jié)點（sink節(jié)點）或者基站（Base Station）是一個固定的或者移動的節(jié)點，它能夠將WSN連接到現(xiàn)有的如Internet網(wǎng)絡或衛(wèi)星網(wǎng)絡中，以供用戶讀取相關信息。

圖1 WSN結構示意圖

1.2 WSN密鑰管理的必要性

無線傳感器網(wǎng)絡被認為是21世紀最重要的技術之一。無線傳感器網(wǎng)絡技術在二十世紀初期就受到人們的關注，而且國際上很多機構和部門進行了相關的研究，現(xiàn)在，人們已經(jīng)開始了無線傳感器網(wǎng)絡的基本技術的開發(fā)和利用，已經(jīng)在人們生活的各個領域如環(huán)境監(jiān)測、城市交通的控制與管理和軍事信息的獲取等方面發(fā)揮作用，因為無線傳感器網(wǎng)絡在很多特殊場合和領域能夠發(fā)揮其它技術無法替代的作用，所以它的研究會更加深入，應用更廣。但是由于無線傳感器具有配置靈活、組網(wǎng)方便、應用領域廣泛的特點，同時WSN也因為自身節(jié)點的能量受限、通信能力弱、節(jié)點的存儲空間小、計算能力弱和網(wǎng)絡節(jié)點數(shù)量龐大等因素的存在，使得它更易受到外界的攻擊和破壞，如果安全機制解決不好，有可能導致整個網(wǎng)絡的安全受到威脅［2］。

無線傳感器網(wǎng)絡中的某個節(jié)點要與其它的節(jié)點實現(xiàn)可靠通信的前提是這個節(jié)點必須確認與自己通信的節(jié)點是合法的。密碼機制作為一種基礎的安全機制，可以通過用秘密密鑰加密消息的方式為我們提供點到點的安全通信服務。目前有三種對密鑰協(xié)商方案：一種是基于可信第三方的密鑰分發(fā)方案［3］，一種是基于非對稱密碼機制的密鑰協(xié)商方案［4］，另一種是基于對稱密碼機制的密鑰預分發(fā)方案［5］。由于傳感器網(wǎng)絡中沒有可信的基礎設施，基于可信第三方的密鑰分發(fā)方案不能直接應用到傳感器網(wǎng)絡中。又由于無線傳感器結點自身的限制，比如結點的計算能、電源能量、通信能力和存儲空間非常有限，使得非對稱密碼機制中的很多算法，都無法在無線傳感器網(wǎng)絡上實現(xiàn)。因此，基于對稱密碼機制的密鑰預分發(fā)方案成了傳感器網(wǎng)絡中應用的主要方案。

通常的做法是對這對通信節(jié)點所傳輸?shù)南⑦M行加密，而這對合法節(jié)點當共同擁有了對這個加密后的信息進行解密的密鑰時，這對通信節(jié)點之間才能正常進行會話與通信，這對通信節(jié)點共同擁有的密鑰即為對密鑰。

2 密鑰預分發(fā)及其性能指標

2.1 密鑰預分發(fā)方法

密鑰預分發(fā)即基于對稱密碼機制的密鑰預分發(fā)方案［6］，要實現(xiàn)兩個傳感器節(jié)點之間進行可靠的信息傳輸，我們將對它們所傳輸?shù)男畔⑦M行加密處理，收發(fā)雙方必須都擁有加密信息的秘密密鑰才能實現(xiàn)正常的信息交流。而因為WSN的節(jié)點通常分布于無人值守的環(huán)境中，這個共同擁有的對密鑰必須是在傳感器節(jié)點分布之前就已經(jīng)預存于傳感器節(jié)點之中，這就稱之為密鑰預分發(fā)。當節(jié)點被放置于傳感區(qū)域后，各節(jié)點就通過無線通信的方式尋找與自己擁有相同的密鑰，從而實現(xiàn)通信。

2.2 密鑰預分發(fā)方案的性能指標

在無線傳感器網(wǎng)絡中進行密鑰預分發(fā)是建立對密鑰和節(jié)點之間正常通信的一個很重要的安全性措施，但是不是所有的方案都能適合WSN，特別是現(xiàn)在無線傳感器網(wǎng)絡規(guī)模擴大化，應用環(huán)境復雜化，衡量一個密鑰預分發(fā)方案優(yōu)劣主要考慮以下幾點：

密鑰連通性：從安全通信的角度看，密鑰連通性就是傳感器網(wǎng)絡中成功建立對密鑰的概率。如果一個方案使用時，能使整個網(wǎng)絡的對密鑰建立的成功性越高，說明對密鑰的連通性就越好

抗毀壞性：因為WSN經(jīng)常處于一些危險的環(huán)境中，一個對密鑰預分發(fā)方案良好的抗毀壞性應該是當無線傳感器網(wǎng)絡中某一個節(jié)點或幾個節(jié)點被完全控制后，不會泄露它們與其它節(jié)點之間的對密鑰信息，也就不會造成更多的節(jié)點被毀壞。

存儲開銷：對于一個良好的密鑰預分發(fā)方案應該是在建立對密鑰時所需的存儲空間很小。因為傳感器網(wǎng)絡特點是在傳感區(qū)域內(nèi)安置了成千上萬或更多的傳感器節(jié)點，它們在通信的范圍內(nèi)要與周圍的節(jié)點建立對密鑰，因為傳感器節(jié)點的存儲空間有限，這就要求每對對密鑰所占的存儲越小越好。

擴展性：擴展性是指傳感器網(wǎng)絡能否支持網(wǎng)絡中節(jié)點數(shù)量的變化。因為現(xiàn)在傳感器網(wǎng)絡的規(guī)模越來越大，數(shù)量越來越多，由傳感器網(wǎng)絡存儲開銷內(nèi)容可知，對密鑰預分發(fā)方案的擴展性與節(jié)點所需要的存儲開銷有一定的關系。如果網(wǎng)絡中的每個節(jié)點所需要的存儲開銷越小，網(wǎng)絡支持大規(guī)模的能力通常會越好。

靈活性：靈活性應該是如果一個密鑰分發(fā)方案能夠在支持網(wǎng)絡的動態(tài)變化的同時還能保持網(wǎng)絡的安全性和密鑰連通性能不會受到影響。即在進行密鑰預置方案設計中加入能使被毀壞節(jié)點的密鑰信息及時撤除，防止去破壞其它的網(wǎng)絡節(jié)點。

3 對密鑰預分發(fā)方案的研究現(xiàn)狀

3.1 基礎的完全對密鑰方案

在這個方案中，如果一個無線傳感器網(wǎng)絡想實現(xiàn)百分之百的密鑰連通性，這就要求這個網(wǎng)絡中m個節(jié)點中的任意兩節(jié)點之間建立對密鑰，即實現(xiàn)對密鑰的全連通性。每個節(jié)點都要與其它m－1個節(jié)點之間建立對密鑰，這是一個最基本的對密鑰預分發(fā)方案的思想。這個思想的特點是每個節(jié)點的存儲花費是m－1個對密鑰信息量，因為任意兩個節(jié)點之間的對密鑰是不同的，即某個節(jié)點被惡意節(jié)點毀壞而造成對密鑰信息泄露，也不會造成其它節(jié)點的毀壞，所以具有優(yōu)良的抗毀壞性，

但是此方案帶來的問題是每個節(jié)點的存儲開銷會隨著網(wǎng)絡大?。ü?jié)點數(shù)量的多少）的增加而線性的增加，因為傳感器節(jié)點的存儲能力通常是有限的，WSN的大小就會受到節(jié)點存儲能力的限制，這種方案只適用于小型無線傳感器網(wǎng)絡，所以這種方案的主要缺點是擴展性差。

3.2 基于概率的對密鑰預分發(fā)方案［7］

在一個WSN中，在通常的應用情況之下，在一個傳感網(wǎng)絡區(qū)域內(nèi)可能布置成千上萬個傳感器節(jié)點，這些節(jié)點的無持續(xù)能量供應，自身的能量供應有限，通信的范圍通常只有幾十米，它們通過無線通信的方式形成一個自組織的網(wǎng)絡系統(tǒng)。在進行對密鑰預分發(fā)方案設計時，要求網(wǎng)絡中所有節(jié)點相互都有對密鑰是不必要的。因為多個節(jié)點之間也可以通過多跳的方式實現(xiàn)信息的傳輸。

為此基于概率的對密鑰預分發(fā)方案提出了讓這些節(jié)點只與自己周圍的一部分鄰居節(jié)點建立對密鑰，然后運用密鑰路徑的方式來保證整個網(wǎng)絡具有一定的密鑰連通概率。這樣就提高了網(wǎng)絡連通效率，極大地減少了不必要的對密鑰建立，提高了網(wǎng)絡的效率，同時也降低了節(jié)點的開銷，提高了方案的擴展性。

基于概率的對密鑰預分發(fā)方案缺點是可能一個密鑰數(shù)據(jù)被幾個節(jié)點選擇，若這個密鑰數(shù)據(jù)被惡意節(jié)點得到后，就可能造成網(wǎng)絡中更多的節(jié)點信息泄漏甚至節(jié)點毀壞

3.3 隨機的對密鑰預分發(fā)方案［8］

這種方案有以下幾方面的考慮：為了防止一個密鑰被幾個節(jié)點獲得，方案設計時要求兩個節(jié)點不是擁有一個相同密鑰就可以建立對密鑰，另外就是基站在節(jié)點建立對密鑰后定期發(fā)送對密鑰更新消息，使對密鑰進行更新，防止一個密鑰被幾對節(jié)點使用。還有就是為了既保證在同一個傳感器網(wǎng)絡中對密鑰的唯一性，提高了對密鑰的抗毀壞性，又出于整個網(wǎng)絡的密鑰連通性的考慮，可以使每個節(jié)點在對密鑰建立的時候，當一個密鑰已經(jīng)被某兩個節(jié)點建立為對密鑰了，那么其它節(jié)點就不允許使用這個密鑰了。隨機的對密鑰預分發(fā)方案的缺點是存儲和計算開銷太大。

3.4 基于位置信息概率的對密鑰預分發(fā)方案

本方案的主要思想：考慮到在基本的隨機的概率性方案中，因為基站在節(jié)點分布之前不知道節(jié)點的位置，而是隨機地將各密鑰信息預到各節(jié)點中，當節(jié)點被分布在傳感區(qū)域中后，各節(jié)點的位置是隨機的，這樣就可能出現(xiàn)可能相距較遠的兩個節(jié)點擁有一對對密鑰，而相鄰兩個節(jié)點反而沒有對密鑰。因為傳感器節(jié)點的供電能量和通信能力有限，擁有對密鑰的兩個節(jié)點也不能進行通信，出于提高對密鑰連通性考慮，我們可以將對密鑰預存入位置相鄰的節(jié)點中。Du［9］等人提出的帶結點部署信息的對密鑰預分發(fā)方案。

3.5 分布式基于LU矩陣的密鑰預分發(fā)方案［10］

分布式結構基于LU矩陣的密鑰預分發(fā)方法：在這種傳感器網(wǎng)絡中，如果一個n×n的對稱矩陣K由一個n×n的下三角矩陣L與一個n×n的上三角矩陣U相乘而得，即K＝LU，我們認為L和U的合成陣稱等于對稱矩陣K。對稱密鑰矩陣K可以由兩個三角矩陣L和U計算出來，如式1所示。

我們可以分別從矩陣L和U中分配一行和一列信息給傳感器網(wǎng)絡中的某個節(jié)點如i節(jié)點，也可以向i節(jié)點分配L中同一行號和U中同一列號的密鑰信息，例如：L中的第i行Lhi和U中的第i列Uvi將會被分配給節(jié)點i。在基于LU矩陣的密鑰預分發(fā)方案中，如果兩個節(jié)點i和節(jié)點j需要建立對密鑰，它們需要交換相互的列信息，維持各自節(jié)點的行信息不變，然后進行計算如下：

節(jié)點i：Lri＊U cj＝kij

節(jié)點j：Lrj＊U ci＝kji

交換列信息后，又由于對稱密鑰矩陣K的kji＝kij，所以矩陣變成如式2：

在此方案中，kij或k ji（因為kij＝kji）就將被用作節(jié)點i和節(jié)點j之間通信的對密鑰。按照這個理論和方法，這個方案是應該能保證網(wǎng)絡中任意兩個節(jié)點之間都能建立對密鑰，因為任意兩個節(jié)點的行和列序列信息不可能正好相同，所以網(wǎng)絡中的所有的對密鑰也是唯一的。

這種分布式LU矩陣結構的密鑰預分發(fā)方案的缺點是網(wǎng)絡的擴展性是不好，因為如果傳感器網(wǎng)絡越大，則每個節(jié)點所存儲的行和列信息就越多，同時在進行信息計算時帶來的計算量也更龐大，對密鑰的數(shù)量也會很多，所以基于LU矩陣的密鑰預分發(fā)方案的的每一個節(jié)點的存儲開銷與網(wǎng)絡中節(jié)點的數(shù)目是一個線性增長的關系，這樣，這種方案不適合發(fā)展大規(guī)模WSN。

結論：通過對無線傳感器網(wǎng)絡應用層已經(jīng)提出和使用的幾種對密鑰預分發(fā)方案分析可知，這幾種方案總是在能量的消耗、存儲資源的開銷、網(wǎng)絡的擴展性、靈活性、對密鑰連通性和抗毀壞性這些性能要求的一個或幾個方面存在缺陷，特別是在支持更大規(guī)模的網(wǎng)絡擴展方面，這幾種方案都是不能滿足WSN發(fā)展要求的，為了解決這些問題，現(xiàn)提出一種層次型的基于LU矩陣的對密鑰預分發(fā)方案，我們就來分析一下它的實現(xiàn)方法和性能吧。

4 基于LU矩陣層次型的對密鑰預分發(fā)方案［11］

4.1 網(wǎng)絡模型

網(wǎng)絡層次模型如圖2所示，在這種具有三層結構模型［12］的傳感器網(wǎng)絡結構中一般預定義了層次結構，整個網(wǎng)絡包括通信、計算等能力不同的三種類型的節(jié)點：基站、簇頭和普通的節(jié)點。其中基站的能力和能量在這三類節(jié)點中是最大的，它負責整個傳感器網(wǎng)絡的預分發(fā)密鑰的計算和整個網(wǎng)絡信號的收集以及與外網(wǎng)之間的信息傳輸；而簇頭主要負責整個這個簇內(nèi)的預分發(fā)密鑰的計算和本簇信號的收集以及與其它簇頭和基站之間的信息傳輸，它的能力居中；普通節(jié)點的能力在這三類節(jié)點中最小，通常被按簇部署在簇頭的周圍，主要任務是在本簇內(nèi)進行對密鑰的建立、通信等。

圖2 層次型無線傳感器網(wǎng)絡層次模型

假設在一個節(jié)點位置固定的無線傳感器網(wǎng)絡中，設有n個節(jié)點，而有m個簇頭，在傳感器節(jié)點分布之前，在所有簇頭和基站中預存了能夠實現(xiàn)通信的密鑰信息，而將某個簇頭和部分的普通節(jié)點內(nèi)也預存了能夠實現(xiàn)通信的密鑰信息。當層次型方案而進行布置網(wǎng)絡時，一個簇頭節(jié)點和與它預存了能進行通信的密鑰信息的部分節(jié)點構成一個簇，而且它們在位置上也是距離很近的，每個簇中約有n／m個節(jié)點。在網(wǎng)絡正常工作時，基站一般和簇頭進行通信，同時還與外部如因特網(wǎng)或衛(wèi)星進行通信，并將無線傳感器網(wǎng)絡所感知和處理的信息傳遞出去。簇頭的信息處理能力和通信能力比一般的節(jié)點強，它不僅與基站進行通信，同時還擔負著與本簇內(nèi)所有節(jié)點進行通信，將本簇的信息傳遞給基站。在層次型方案中用到的主要術語如下：

CH j：某一簇頭節(jié)點j；

Cj：第j個簇，j的數(shù)量多于1而少于m個；

Sj－i：簇Cj中節(jié)點i，i的數(shù)量多于1而少于n／m個SMCH：WSN中全部的簇頭節(jié)點和基站所共享的對稱密鑰矩陣；

SMCj：WSN中簇Cj中簇頭節(jié)點與全部的普通節(jié)點所共享的對稱密鑰矩陣；

KCH－ij：簇頭節(jié)點所共享的對稱密鑰矩陣SMCH中第i行、第j列的密鑰；

KCj－ij：簇Cj中的節(jié)點所共享的對稱密鑰矩陣SMCj中第i行、第j列的密鑰；

LCH－h(huán)i：簇頭節(jié)點所共享的對稱密鑰矩陣SMCH的下三角陣CH－L的第i行；

UCH－vi：簇頭節(jié)點所共享的對稱密鑰矩陣SMCH的上三角陣CH－U的第i列；

LCj－h(huán)i：簇Cj中的節(jié)點所共享的對稱密鑰矩陣SMCj的下三角陣C j－L的第i行；

UCj－vi：簇Cj中的節(jié)點所共享的對稱密鑰矩陣SMCj的上三角陣C j－U的第i列

4.2 基于LU矩陣的層次型的密鑰分發(fā)方案的實施過程

本方案中的三種類型的節(jié)點組成了兩種矩陣：一是基站和所有簇頭所共有的對稱密鑰矩陣SMCH；另一個是某個簇中的簇頭和本簇所有節(jié)點所共享的對稱密鑰矩陣SMCj。本方案的實施分為三個階段：

4.2.1 第一階段：對稱密鑰矩陣產(chǎn)生階段，其實施步驟如下：

第一步：基站產(chǎn)生一個數(shù)量很大的密鑰池（如：大于220），這些密鑰都是用來產(chǎn)生簇頭對稱密鑰矩陣SMCH和簇對稱密鑰矩陣SMCj的。

第二步：基站為各簇計算出簇頭和本簇所有節(jié)點所共享的對稱密鑰矩陣SMCj，同時也計算出基站和所有簇頭所共有的對稱密鑰矩陣SMCH。通常要求每一個對稱密鑰陣中的密鑰必須是互不相同的，主要是保證每一對節(jié)點之間的對密鑰的唯一性。

下面我們以產(chǎn)生一個3＊3的對稱密鑰矩陣M的例子來介紹基于LU矩陣的層次型對密鑰分發(fā)方案的密鑰矩陣產(chǎn)生過程。

首先是上三角矩陣U產(chǎn)生和對稱矩陣的分解過程：上三角矩陣U中的信息是由密鑰庫中任意獲取的，例如我們?yōu)榱诵纬蛇@個3＊3上三角矩陣U而在密鑰庫中任意選擇（1，－2，3，4），根據(jù)對稱矩陣的分解原理，可以計算產(chǎn)生下三角陣L，分解過程見式3：

由式3分別計算如下：

然后根據(jù)對稱矩陣的性質kij＝kji，由上面的式（4）、（5）、（6）得到如下方程組：

由上面所計算的等式我們看到，三個等式中共有五個未知數(shù)l11，l21，l22，l31，l32，l33是一個自由變量。從數(shù)學角度我們知道，三個方程六個未知變量答案可以有很多種。在求解時，我們可以先給其中的三個未知量（如：l11，l22，l33）賦值，這樣剩下的兩個未知量就可以確定。假設我們給三個未知量的賦值為l11＝1，l22＝2，l33＝3，帶入上面三個等式后得：

由以上賦值及所計算出的各量得矩陣關系如式10：

進一步計算得到下面的矩陣：

按照這樣的方法，就可以計算出簇Cj中的節(jié)點所共享的對稱密鑰矩陣SM Cj（j＝1，…m）和簇頭節(jié)點所共享的對稱密鑰矩陣SMCH。

4.2.2 第二階段：密鑰預分發(fā)階段：

經(jīng)過上一個對稱密鑰矩陣產(chǎn)生階段后，每一個節(jié)點都已經(jīng)預存了預分發(fā)的密鑰信息，這些節(jié)點是包含了層次型方案中所有節(jié)點：

基站：基站在整個網(wǎng)絡中的能力最強，它主要是與本傳感器網(wǎng)絡中的所有簇頭節(jié)點以及外網(wǎng)進行通信，當它與本傳感器網(wǎng)絡中的所有簇頭節(jié)點進行信息交流時，必須與它們建立對密鑰，所以它存儲的密鑰信息是簇頭節(jié)點所共享的對稱密鑰矩陣SMCH的下三角陣CH－L的第i行和SMCH的上三角陣CH－U的第i列信息（LCH－h(huán)i，UCH－vi），

簇頭：每一個簇頭不僅要與鄰居簇頭和基站共享對稱矩陣SMCH，還要與簇成員共享對稱密鑰矩陣SMCi。這就意味著，它需要存儲（（LCH－h(huán)i，U CH－vi），（LCH－h(huán)（n／m＋1），U CH－v（n／m＋1）））這些信息，其中（LCH－h(huán)i，U CH－vi）是簇頭將來用于與其它各簇頭節(jié)點和基站建立對密鑰，（LCH－h(huán)（n／m＋1），UCH－v（n／m＋1））是簇頭節(jié)點將來用于與本簇內(nèi)各節(jié)點之間建立對密鑰。

普通節(jié)點：普通節(jié)點在本傳感器網(wǎng)絡中的能力最弱，它主要負責進行信息的采集處理后再與簇頭和本簇的其它節(jié)點進行通信，所以它存儲的密鑰信息是（LCj－h(huán)i，U Cjvi）。因為在一個具有n個節(jié)點的WSN中，普通節(jié)點的數(shù)量是最大的，如果采用分布式對密鑰預分配方案中每個節(jié)點需要存儲與其它n－1個節(jié)點建立對密鑰的密鑰信息，而在層次式的方案中，普通節(jié)點只需要存儲約n／m個密鑰信息，使用的存儲空間更小了。

4.2.3 第三階段：對密鑰建立階段：

當各節(jié)點部署到特定的區(qū)域后，網(wǎng)絡中每一個簇中的所有成員節(jié)點需要建立對密鑰，基站和所有簇頭都需也要建立對密鑰，一個簇中的簇頭和簇內(nèi)所有普通節(jié)點也要建立對密鑰，下面介紹簇Cj中的節(jié)點a（Sj－a）和節(jié)點b（Sj－a）之間對密鑰的建立過程：

第一步：簇Cj中a節(jié)點將其列信息｛U Cj－ca｝發(fā)送給同一簇中的b節(jié)點；

第二步：當節(jié)點b接收到從節(jié)點a發(fā)送過來的列信息后，節(jié)點b立即計算出K Cj－ba，并回復｛U Cj－cb，F(xiàn)（KCj－ba）｝，這里的U Cj－cb是簇C j中的節(jié)點所共享的對稱密鑰矩陣SMCj的上三角陣C j－U的第b列的序列信息；而F（K Cj－ba）是節(jié)點b計算出的密鑰K Cj－ba的數(shù)值

第三步：節(jié)點a接收到節(jié)點b發(fā)來｛U Cj－cb，F(xiàn)（K Cj－ba）｝以后，它會根據(jù)收到的列信息U Cj－cb計算出另一個密鑰K Cj－ab，而得到密鑰K Cj－ab值F（K Cj－ab），然后再驗證這個密鑰數(shù)值是不是和收到的密鑰KCj－ba的數(shù)值F（KCj－ba）相等。

第四步：如果節(jié)點a驗證了F（K Cj－ab）＝F（K Cj－ba），那么就意味著K Cj－ab＝K Cj－ba。于是節(jié)點a會用K Cj－ab作為它和節(jié)點b的對密鑰，并將｛ok，K Cj－ab｝信息反饋回節(jié)點b，如果節(jié)點a驗證了F（KCj－ab）≠F（KCj－ba），那么就意味著KCj－ab≠KCj－ba。此時節(jié)點a反饋回節(jié)點b的信息就是｛err，Sj－a｝，表明這兩個節(jié)點不能建立對密鑰。

基站和各簇頭之間建立對密鑰的過程和一個簇中簇頭和普通節(jié)點建立對密鑰的過程相同，只是它們所使用的對密鑰矩陣與一個簇內(nèi)所有節(jié)點使用的對密鑰矩陣不是一個層次而已。

4.3 基于LU矩陣層次型的對密鑰預分發(fā)方案安全性及性

4.3.1 安全可靠性分析

在分布式LU矩陣的對密鑰分發(fā)方案中，所有的節(jié)點在同一個層次，而一個無線傳感器網(wǎng)絡中的節(jié)點數(shù)量通常是巨大的，節(jié)點需要盡可能地與周圍節(jié)點建立對密鑰，所有節(jié)點建立的對密鑰不可能是唯一的，所以為了提高密鑰連通性，同一個對密鑰信息會預存于整個網(wǎng)絡的多個節(jié)點中，這樣，在對密鑰建立時，一個節(jié)點可能與周圍好幾個節(jié)點利用同一個對密鑰信息建立對密鑰而實現(xiàn)連通。這就造成了對密鑰不是唯一的，這就增加密鑰信息被非法節(jié)點截獲的可能性，如果多個對密鑰信息被截獲，會造成毀壞節(jié)點的數(shù)量增加，使這種方案的安全性降低了。

而在層次式的方案中，因為每個普通節(jié)點只需和本簇的節(jié)點建立對密鑰進行信息交流，而在一個簇中的節(jié)點的數(shù)量是有限的，所以節(jié)點存儲用于建對密鑰的密鑰信息量是很小的，所以可以使每個傳感器節(jié)點與其它節(jié)點建立的對密鑰是唯一的，提高了安全性。同時在安全建立的過程中，兩個節(jié)點還可以通過所計算的密鑰值進行再次確認相互之間的合法性，更加提高了網(wǎng)絡的安全性。

4.3.2 存儲開銷分析

在層次型LU矩陣的密鑰預分發(fā)方案中，由于采用了層次設計思想，將整個傳感器網(wǎng)絡的所有節(jié)點劃分為多個單元即簇，如果單元的數(shù)量越多，則每個單元內(nèi)的節(jié)點的數(shù)量就會減少，這樣，每個節(jié)點需要存儲的信息量就減少，如在一個節(jié)點總數(shù)為n而簇數(shù)為m的網(wǎng)絡中，每個簇內(nèi)節(jié)點數(shù)只有約n／m個，節(jié)點在存儲對密鑰的密鑰信息時，只需存儲三角矩陣的一行和一列信息，即存儲開銷為2n／m，而且在對密鑰建立過程中，采用的是特殊的三角矩陣，三角矩陣中每行、每列都有一部分序列信息為0，所以真正在存儲時的開銷比2n／m還小，因為這些0的信息通常是相連的，我們在存儲時對采用非0信息按原信息存儲，而0信息存儲時是存儲連0的個數(shù)信息，按這種方法，又可以降低存儲消耗，經(jīng)過多次數(shù)學運算和統(tǒng)計，每個節(jié)點存儲一行或一列密鑰信息所需存儲開銷為n／2m＋1，每個節(jié)點存儲的實際開銷約為n／m＋2。前面所說的確定的對密鑰預發(fā)方案中，如果要為具有n個節(jié)點的WSN建立對密鑰，每個節(jié)點直接與網(wǎng)絡中其他n－1個節(jié)點的建立對密鑰，這就要求在每一個節(jié)點中都存儲n－1個密鑰。經(jīng)過對比，基于LU矩陣的層次型構造的對密鑰預分發(fā)方案的存儲開銷比確定的對密鑰預發(fā)方案的存儲開銷小多了。

4.3.3 通信開銷分析

在層次型LU矩陣的密鑰預分發(fā)方案中，對密鑰建立過程中每一對節(jié)點之間只需要交換一個密鑰的密鑰計算值（密鑰計算值）和一列的信息。如在一個節(jié)點總數(shù)為n而簇數(shù)為m的網(wǎng)絡中，每個簇內(nèi)節(jié)點數(shù)只有約n／m個，每個節(jié)點存儲一行或一列密鑰信息所需存儲開銷為n／2m＋1，因此在這個方案中密鑰建立過程的通信傳輸開銷為（n／2m＋1＋1）。

4.3.4 計算開銷分析

在層次型LU矩陣的密鑰預分發(fā)方案中，簇內(nèi)節(jié)點的對密鑰建立過程包括一個密鑰值計算和一個向量乘法。在簇頭毀壞的補救過程中，如果一個簇頭節(jié)點毀壞，則需要簇頭與本簇中（n／m－1）個普通節(jié)點進行（n／m－1）次的上三角L和下三角的行列數(shù)為（n／m－1）行列式相乘計算，從而計算出（n／m－1）個密鑰數(shù)值，這樣才能使新簇頭與本簇內(nèi)的普通節(jié)點建立對密鑰關系；而如果是某個簇中的普通節(jié)點毀壞，它只需與簇頭建立對密鑰，所有計算量為一次的上三角L和下三角的行列數(shù)為（n／m－1）行列式相乘計算。

4.3.5 網(wǎng)絡擴展性分析

這一點對于我們發(fā)展大規(guī)模的無線傳感器網(wǎng)絡是很重要的。在層次型LU矩陣的密鑰預分發(fā)方案中，因為在某個層次（如簇）中的節(jié)點的數(shù)量是一定的，所以每個簇中各節(jié)點的存儲信息也是一定的。若網(wǎng)絡要擴展，可以增加簇的數(shù)量，但是每個簇中的節(jié)點數(shù)目是不改變的。所以，即使各節(jié)點內(nèi)存有一定的限制，也不會給網(wǎng)絡的規(guī)模擴展帶來障礙，所以本方案特別適合在大規(guī)模無線傳感器網(wǎng)絡中使用。

5 結論

因為無線傳感器在能量供應、計算能力、通信能力和存儲空間等方面弱點的存在，原有的幾種方案都存在很大的局限性，不能適應發(fā)展大規(guī)模無線傳感器網(wǎng)絡的要求，而層次式的基于LU矩陣的對密鑰預分發(fā)方案更加適合大規(guī)模無線傳感器網(wǎng)絡。

［1］溫 蜜.無線傳感器網(wǎng)絡中關鍵安全技術研究［D］.上海：上海交通大學，2008.

［2］C.Karlof and D.Wagner.Secure routing in wireless sensor networks：Attacks and countermeasures.Elsevier’s Ad Hoc Networks Journal［C］.Special Issue on Sensor Network Applications and Protocols1，2003，（2－3）：293－315.

［3］B.C.Neuman and T.Tso.Kerberos：An authentication service for computer networks［C］.IEEECommunications，1994，32（9）：33－38.

［4］W.Diffie and M.E.Hellman.New directions in cryptography［J］.IEEE Transactions on Information Theory，1976，22（11）：644－654.

［5］Du W，Deng J，Han YS，Varshney PK.A pairwise key predistribution scheme for wireless sensornetworks.In：Proc.of the 10th ACM Conf.on Computer and Communications Security［D］.New York：ACM Press，2003，42：51.

［6］Du W，Deng J，Han YS，Varshney PK.A pairwise key predistribution scheme for wireless sensornetworks.In：Proc.of the 10th ACM Conf.on Computer and Communications Security.New York：ACM Press，2003，42：51.

［7］Laurent Eschenauer and Virgil D.Gligor.A key－management scheme for distributed sensor net－works.In Proceedings of the 9th ACM Conference on Computer and Communication Security，2002，（11）：41－47.

［8］Chan H，Perrig A，Song D.Random key predistribution schemes for sensor networks.In：Proc.of the 2003 IEEE Symp.on Security and Privacy.Washington：IEEE Computer Society，2003，197，213.

［9］W.Du，J.Deng，Y.S.Han，S.Chen，P.Varashney.A Key Management Scheme for Wireless Sen－sor Networks Using Deployment Knowledge.IEEE TRANSACTIONS ON DEPENDABLE ANDSECURE COMPUTING，2006，3（1）：62－77.

［10］Park，C.W.，Choi，S.J.，Youn，H.Y.：A Noble Key Pre－distribution Scheme with LU Matrix forSecure Wireless Sensor Networks.In：CIS，2005，LNCS（LNAI），38（02）：494－499.

［11］Cheng Y，Dharma P.Agrawal.An improved key distribution mechanism for large－scale hierarchicalwireless sensor networks，Ad Hoc Networks，2007，5（1）：35－48.

［12］Blom R.An optimal class of symmetric key generation systems.Advances in Cryptology：Proceed－ings of EUROCRYPT 84（Thomas Beth，Norbert Cot，and Ingemar Ingemarsson，eds.），LectureNotes in Computer Science，Springer－Verlag，1985，209：335－338.

TN92

A

1673－1794（2011）05－0025－05

張德樹（1972－），男，工學碩士，講師，研究方向：電子技術。

滁州職業(yè)技術學院2011年院級科研項目（YJY－2011－18）

2011－01－28