無線傳感器網絡中一種改進的對密鑰更新方案

(電子科技大學 寬帶光纖傳輸與通信網技術教育部重點實驗室， 成都 610054)

摘 要：無線傳感器網絡在使用過程中，部分節點會由于環境因素或能量耗盡而失效，為了彌補這些失效節點，網絡中的節點數可以動態地增加或減少，為了保證網絡的安全性，提出了一種改進的對密鑰更新方案。該方案是在傳感器網絡中一種可靠的對密鑰更新方案基礎上提出的，借助Blom矩陣，能夠隨著網絡的動態變化而動態管理密鑰，從而防止了密鑰的泄露。同時與可靠的對密鑰更新方案相比，在保證網絡安全和連通性的條件下，減小了存儲空間和計算開銷。

關鍵詞：無線傳感器網絡；密鑰更新；存儲空間；計算開銷

中圖分類號：TP3097 文獻標志碼：A

文章編號：10013695(2009)01034403

Improved pairwise keyupdating scheme for wireless sensor network

CHEN Ni，YAO Jianbo，WEN Guangjun

(Key Laboratory of Broadband Optical Fiber Transmission Communication Networks of Ministry of Education， University of Electronic Science Technology of China， Chengdu 610054， China)

Abstract:When wireless sensor networks were working， some nodes failed because of environment or energy factors. In order to recuperate the networks，evicted the sensor nodes out of the networks and added some new nodes to the networks.Based on the reliable pairwise keyupdating scheme，this paper proposed the scheme to protect the networks security. The scheme can extend and shrink the keys by Blom matrix with the network topology changes to prevent the adversary from utilizing the captured keys. Comparison the reliable pairwise keyupdating scheme， the scheme can outperforms in terms of memory and computation overhead.

Key words:wireless sensor network; keyupdating; memory overhead; computation overhead

0 引言

近年來，無線傳感器網絡得到了迅速發展。由大量能夠對外界環境變化作出反應的傳感器節點組成的傳感器網絡[1]有著廣泛的應用[2]，如森林防火、火山、地震監測、環境信息采集、軍事領域跟蹤偵察等。在無線傳感器網絡中，網絡節點往往是相對穩定或靜止的，節點的密集程度較高，且大部分節點只有較低的配置。通常由電池供電，電量比較低，有限的數據處理能力，小范圍的無線電通信能力。無線傳感器節點一般被長時間部署在特定的地理環境中，一方面，易受到地勢地貌和氣候條件等外部環境因素變化的影響，造成通信中斷，網絡的拓撲結構動態變化；另一方面，由于節點本身的電量有限，節點數目眾多且老節點失效和新節點加入等，網絡拓撲結構也會頻繁變化。由于傳感器網絡的自身一些特性，當傳感器網絡被安放在敵對環境中，易受到監聽和各種惡意攻擊，通信安全問題顯得極為重要。為了保證通信安全，網絡密鑰動態管理是其中的一個重要問題。

傳感器網絡中一種可靠的對密鑰更新的方案[3]，就是一個密鑰動態管理的方案。它提出了一種基于分簇結構的密鑰預分發方法，使得任意兩個相鄰節點間均能建立一個對密鑰，并且借助于一種改進的Blom矩陣構造方法，能夠動態地伸縮各個節點的密鑰信息來適應網絡的動態變化，但是這種更新方法帶來了很大的計算開銷和通信開銷。

本文就是在傳感器網絡中一種可靠的對密鑰更新方案的基礎上，提出了一種改進的更新方案。

1 改進的更新方案

該方案也是借助于Blom矩陣來更新密鑰信息。

11 Blom矩陣對密鑰分配方案

Blom方案[4]以及Du方案[5]均采用了Blom矩陣。 矩陣構造的具體實施過程是：在有限域上，基站構建矩陣G，其大小為（λ+1）×N。其中：N表示網絡節點數；G作為公共信息。G的矩陣常用的生成方法為[6]

G=111…1

gg2g3…gN

g2(g2)2(g3)2…(gN)2



gλ(g2)λ(g3)λ…(gN)λ

這樣每個節點只需記憶每列的第二個元素就可以衍生出整個列，從而減少對存儲空間的需求。同時基站還構建隨機對稱矩陣D。其中矩陣的大小為(λ+1)×(λ+1)，D是保密的，并計算矩陣A=(D×G)T。其中(D×G)T表示D×G轉置矩陣，然后A×G最終對應一個N×N的密鑰分配矩陣，并且是對稱矩陣。當兩個節點要生成密鑰對時，彼此交換各自所帶的G信息，并按照矩陣的乘法規則各自計算。因此對于每個節點i只需預存A的第i行，以及G的第i列的列種子就可以了。這樣，只要被俘節點的數目沒有達到門限值λ，網絡就是安全的。

12 改進的更新過程

根據Blom矩陣方案，所有的節點在部署前均預存了一些密鑰信息。為了方便描述，令

D=d11d12d13…d1αd21d22d23…d2α

d31d32d33…d3α



dα1dα2dα3…dαα

其中α=λ+1，當i≠j時，dij=dji。D的產生方式可以與 Blom矩陣方案以及Du方案中的一樣，也可以與可靠更新方案中的相同。那么可知：

A=[a1 a2 a3 …aN]T

其中ai表示A的行向量，且

ai=d11+d12gi+…+d1α(gi)λ

d21+d22gi+…+d2α(gi)λ

d31+d32gi+…+d3α(gi)λ



dα1+dα2gi+…+dαα(gi)λT

同時，用列向量ηi來表示G，ηi=[1gi(gi)2…(gi)λ]T則G=[η1η2η3…ηN]。因此可以計算得到

A×G=a1η1a1η2a1η3…a1ηN

a2η1a2η2a2η3…a2ηN

a3η1a3η2a3η3…a3ηN



aNη1aNη2aNη3…aNηN

很容易知道，這是一個對稱矩陣。

121 節點的加入

為了描述方便，假如這個加入的節點就是節點N+1。根據Blom矩陣方案，當節點加入時，首先要預存一些密鑰信息給這個節點。易知基站會產生一個列種子gN+1并存在節點N+1中。那么此時帶有節點N+1的信息的G′為

G′=11…11

gg2…gNgN+1

g2(g2)2…(gN)2(gN+1)2



gλ(g2)λ…(gN)λ(gN+1)λ

根據前面所述計算A′=(D×G′)T=[a1 a2 a3 … aN aN+1]T。這里的ai仍然與前面給出的一樣。那么很容易知道對于新加入的節點N+1，要預存的信息就是aN+1和gN+1。同時根據ai可以看出A′中只有aN+1與節點N+1有關。

那么A′×G′=a1a2a3aNaN+1×[η1 η2 η3…ηN ηN+1]可以得出

A′×G′=a1η1a1η2a1η3…a1ηNa1ηN+1

a2η1a2η2a2η3…a2ηNa2ηN+1

a3η1a3η2a3η3…a3ηNa3ηN+1



aNη1aNη2aNη3…aNηNaNηN+1

aN+1η1aN+1η2aN+1η3…aN+1ηNaN+1ηN+1

易知這個矩陣也是一個對稱矩陣。對比A×G，可以看出

A′×G′=a1ηN+1

a2ηN+1

A×G

aNηN+1

aN+1η1aN+1η2…aN+1ηNaN+1ηN+1

由此可知，只要給節點N+1預存自己的密鑰信息，然后由基站廣播它的加入和它的ID(節點的ID與它的列種子一樣)，那么它就能與其他節點通過交換彼此的G信息，按照矩陣乘法規則就能與其他節點建立共享密鑰。而其他節點無須更新自己所預存的密鑰信息。這樣就大大減少了節點的計算開銷。

122 節點的刪除

節點可能會受到設備可靠性、安全攻擊、能量耗盡等原因不斷喪失工作能力，為了防止因為這樣的節點而泄露相關信息，要求有相應的措施來保證網絡的安全。在該方案中，假設失效的節點能夠用一些方法或措施[7，8]而及時地被探測到，并且每次被探測到就激發一次節點刪除過程。當節點被探測到有危險性時，假設被探測的這個危險節點是節點1。根據Blom矩陣方案，那么對于G=[η1 η2 η3…ηN]就知道η1具有危險性，同時根據矩陣乘法可以知道a1也有危險性。根據

A×G=a1η1a1η2a1η3…a1ηN

a2η1a2η2a2η3…a2ηN

a3η1a3η2a3η3…a3ηN



aNη1aNη2aNη3…aNηN

知道，只有這個矩陣的第1行和第1列帶有了危險性的信息。因此對于不含危險信息的G″\\[η2η3…ηN]，根據Blom矩陣方案同理可以知道A″=(D×G″)T=[a2 a3 …aN]T，則有A″×G″=a2η2a2η3…a2ηN

a3η2a3η3…a3ηN



aNη2aNη3…aNηN。

同理比較A×G可以得到

A×G=a1η1a1η2a1η3…a1ηN

a2η1

a3η1

A″×G″

aNη1

由此可知，當探測到節點有危險性時，基站就廣播該節點的ID，并通知其他節點不與這個節點通信；而其他節點無須改變自己的密鑰信息，也能保證網絡的安全。

2 性能分析

根據矩陣的構造以及Blom矩陣方案，只要被損的節點數不超過λ個，網絡就是安全的。當λ增大時，其安全性就越高，但是其節點的存儲空間也相應地增大。

為了方便比較該更新過程和可靠的對密鑰更新方案中的更新過程，選取相同的初始網絡，均采用三層分簇結構[9，10]，如圖1所示，并假設網絡中均有m個簇，每個簇中有一個簇頭和n-1個普通節點。由于可靠的更新方案中，初始網絡中簇頭和基站所組成的高級簇中，采用安全門限值λ=m+1；在其他普通簇中，采用λ=n的安全門限值。在相同的初始網絡中的各個簇中運用改進的更新過程時，也選擇在簇頭和基站所組成的高級簇中，采用安全門限值λ=m+1；在其他普通簇中，采用λ=n的安全門限值。這樣很容易知道在這兩個初始狀態相同的網絡中，節點建立共享密鑰的方式是相同的，且它們均由密鑰動態管理，以防止密鑰泄露，因此在抗毀性上來說，均是很可靠的；最主要不同的是存儲空間和計算開銷。

21 存儲空間的比較

根據上述所描述的初始狀態基本相同的網絡，則容易知道，在采用改進的更新過程的網絡中，每個簇頭CHi（每個簇頭在所在的普通簇內的記為該簇的節點n）將預存兩個不同的密鑰空間，一個是用于與其他簇頭和基站通信的(aBi，gi)。其中aBi表示用于所有簇頭和基站組成的高級簇通信的AB的第i行，以及用于簇內通信的(ain，gn)。其中ain表示用于簇頭CHi和節點組成的普通簇通信的Ai的第n行。而第i個簇內的普通節點j預存的密鑰空間就是(aij，gj)。其中aij表示Ai的第j行。

根據文獻[3]，采用可靠的對密鑰更新方案中的更新過程時，網絡中每個簇頭CHi（每個簇頭在普通簇內的記為節點n）將預存兩個不同的密鑰空間，一個是用于與其他簇頭和基站通信的(aBi，gi)以及用于簇內通信的(ain，gn，sij，j=1，…，n)。其中：aBi和ain與前面所提到的相同；sij表示在簇頭CHi所在簇中用于產生Di的行種子。而第i個簇內的普通節點j預存的密鑰空間就是(aij，gj)。其中aij與前面的相同。

對比可知，這兩種情況下普通節點預存的存儲空間是一樣的，而該方案中簇頭無須存儲產生矩陣D的行種子，因此最初預存的存儲空間要比可靠更新方案中的存儲空間小。可靠的更新方案中簇頭要存儲產生相應矩陣D的行種子，是與它的更新過程有關，如在加入節點時，會為加入的節點產生一個相應的行種子，目的是為了保證在節點增加時，其安全性仍然是完全可靠的，即增加了新節點的簇內λ=n+1。因此，在網絡中加入新節點（或刪除節點）時，可靠的更新方案中的節點的存儲空間也隨著增大(或減小)，但是在改進的更新過程中存儲空間則不變。在改進的更新過程中，當節點刪除或者加入時，它的安全門限值仍然是初始網絡時所選擇的最大節點數n；但是在可靠的更新方案中，當節點刪除或者加入時，它的安全門限值就分別是動態網絡中各個簇中最大節點數而不固定為初始的最大節點數。由此可知，當節點刪除時，兩種更新方案都是完全可靠的，但是節點加入時，該更新方案只要各個簇內被俘和損壞節點數小于n個節點，網絡仍是安全的；而可靠的更新方案要簇內所有節點都損壞或被俘才會受到威脅。

22 計算開銷的比較

此處將分別對節點加入和刪除的過程來比較兩種方案的計算開銷。

為方便比較，假設節點n+1加入時，在該方案中，只需基站廣播這個新加節點的G的列種子gn+1并將其存入節點n+1中，而它的簇頭（假設它的簇頭為CHi）為它產生G的第n+1列ηn+1和Ai的第n+1行ai(n+1)。在這個過程中，只需n個冪運算，n個乘法運算。而在可靠的更新方案中，一個節點加入時，簇頭需要進行n+1個散列函數運算、n+1個乘法運算、n+1個冪運算，并且簇內節點還要進行2n+1個乘法運算和n+1個冪運算[3]。

節點被刪除時，在該方案中，只需基站廣播這個節點的列種子有危險，任何節點均不與其通信即可，而無須其他的運算開銷。可靠的更新方案中，根據此方案可知，該節點所在簇頭要進行[(n-1)/2]個散列函數運算，簇內的其他節點需進行[(n-1)/2]個散列函數運算、n-1個乘法運算和冪運算[3]。

由此可見，與可靠的更新方案比較，該方案大大減小了運算開銷。

3 結束語

該方案在保證節點連通率的基礎上，能夠隨著網絡的動態變化而動態地管理密鑰，提高了網絡的抗毀性能；該方案的λ是個變量，在不同的應用中，可以根據具體的應用來選擇值，從而應用更廣泛；該方案的D的產生方式還具有多樣性，不僅僅拘于可靠更新方案中的方法。在基本相同的參數條件下，與可靠的對密鑰更新方案比較，該方案大大降低了計算開銷，同時也降低了節點的存儲空間。

參考文獻：

［1］周賢偉，覃伯平，徐福華. 無線傳感器網絡與安全[M]. 北京：國防工業出版社，2007.

［2］AKYIDIZ I，SU W，SANAKARASVBRAMANIAM Y，et al.Wireless sensor network[J].Survey Computer Networks，2002，38(4):393422.

［3］WEN Mi，CHEN Kefei，ZHENG Yanfei，et al.A reliable pairwise keyupdating scheme for sensor networks[J].Journal of Software，2007，18(5):12321245.

［4］BLOM R.An optimal class of symmetric key generation systems[C]//THOMAS B，NORBERT C，INGEMAR SSON.Proc of EUROCRYPT’84，Lecture Notes in Computer Science.New York:SpringerVerlag，1985:335338.

［5］DU Wenliang，DENG Jing，HAN Y S，et al.A pairwise key predistribution scheme for wireless sensor networks[C]//Proc of the 10th ACM Conference on Computer and Communications Security (CCS).New York:ACM Press，2003:4251.

［6］MacWILLIAMS F J，SLOANE N J A.The theory of errorcorrecting codes[M].New York:Elsevier Science Publishing Company， 1977.

［7］WANG Guiling，ZHANG Wensheng，CAO Guohong，et al.On supporting distributed collaboration in sensor networks[C]//Proc of IEEE Military Communications Conf.Boston:IEEE Press，2003:752757.

［8］SHANECK M，MAHADEVAN K， KHER V，et al.Remote softwarebased attestation for wireless sensors[C]//Proc of the 2nd European Workshop (ESAS 2005)，LNCS 3813.Visegrad:SpringerVerlag，2005:2741.

［9］YOUNIS M，YOUSSEF M，ARISHA K.Energyaware routing in clusterbased sensor networks[C]//Proc of the 10th IEEE/ACM International Symposium on Modeling， Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS2002).Washington DC:IEEE Computer Sociaty，2002:129136.

［10］ARISHA K，YOUSSEF M，YOUNIS M.Energyaware TDMA based MAC for sensor networks[C]//Pro of IEEE Workshop on Integrated Management of Power Aware Communications， Computing and Networking(IMPACCT 2002).New York:Springer，2002:2124.