基于指紋模式匹配的無線傳感器網絡密鑰預分配方案

吳旭婧,許 勇,張亞楠

(安徽師范大學數學計算機科學學院,安徽蕪湖241003)

基于指紋模式匹配的無線傳感器網絡密鑰預分配方案

吳旭婧,許 勇,張亞楠

(安徽師范大學數學計算機科學學院,安徽蕪湖241003)

隨著無線傳感器網絡(WSN)的廣泛應用,其安全問題尤其突出,WSN的密鑰分配和管理受到越來越多研究者的重視。通過收集節點的部署信息對區域進行劃分,提出一種根據指紋識別進行模式匹配的密鑰預分配方案。該方案將網絡劃分成多個較小區域,同時將密鑰種子池分成多個與其對應的子密鑰種子池。節點通過挑選相應區域內種子生成模式和文本,根據匹配成功時生成的指紋函數值建立通信密鑰。安全性分析結果表明,與傳統的隨機密鑰預分配方案相比,該方案具有較高的網絡連通率及較低的存儲能耗。

無線傳感器網絡;部署信息;區域劃分;指紋識別;模式匹配;密鑰預分配

1 概述

無線傳感器網絡(Wireless Sensor Network, WSN)集微機電系統技術、片上系統技術、無線通信技術等多種技術于一體,是當今研究的熱點問題之一［1］。WSN由大量廉價的微型無線傳感器節點組成,通常被部署在無人維護和極易受到威脅的環境。它們通過分布式部署、自組織方式采集和監控管理區域內的信息。與傳統的網絡相比,WSN節點在計算能力、存儲空間、帶寬大小、通信能量等方面資源受限,節點本身更易被俘獲。因而一些傳統的對節點資源有較高要求的加密方法,如公鑰加密體系、基于密鑰分發中心(KDC)的安全體系等不適用于無線傳感器網絡,設計適合無線傳感器網絡的安全方案顯得十分必要［2-3］。以提供安全、可靠的保密通信為目標的密鑰分配和管理方案成為無線傳感器網絡不可忽略的一個問題。

目前普遍認為可行的方法是密鑰預分配方案,即把密鑰預置裝入傳感器節點。文獻［4］提出了一種基于經典隨機圖理論的隨機密鑰預分配方案(簡

稱E-G方案),該方案在減少對節點資源要求的同時獲得高連通率,且不需節點的任何先驗信息,但安全性一般。文獻［5］對E-G方案進行改進后提出Q-composite方案,部署后2個相鄰節點至少需要共享q個密鑰才能直接建立配對密鑰,網絡的抗毀性增強。文獻［6］利用節點的部署和位置信息,提出了基于區域的隨機密鑰預分配方案DR-KPS,提高了網絡的連通性,但密鑰池的劃分較為復雜。本文方案在改進區域劃分［7］的基礎上,提出一種新的基于指紋識別和模式匹配［8-9］的WSN密鑰管理方案。該方案利用節點的位置信息［10-11］增加相鄰節點的連通性,利用模式匹配有效減少經典方案中節點存儲能耗較大的問題,利用指紋對照有效減少共享密鑰發現階段計算能耗較大的問題。

2 模式匹配與指紋提取

假設有一個文本串X=x1x2…xn和模式Y=y1y2…ym,其中,m≤n,模式匹配即為確定模式Y是否在文本X中出現。解決模式匹配最簡單直接的方法是移動模式經過整個文本,每次將長度為m的模式與部分文本進行比較,這種傳統的方法耗時較長且計算較為復雜,為O(mn)。結合不確定性算法中的指紋提取函數,可以將運行時間簡單的縮短為O(m+n),適用于WSN節點資源受限的特點［12］。基于指紋提取的模式匹配是將模式指紋Ip(Y)劃過文本,與文本塊中指紋Ip(X(j))進行比較。指紋提取函數滿足以下特點:

(1)文本的O(n)個指紋都易于計算。

(2)新塊X(j+1)的指紋可以方便從X(j)中計算得到,且X(j+1)與X(j)滿足遞歸式:

Ip(X(j+1))=(2IpX(j)-Wpxj+xj+m)(modp)其中,Wp=2m。

3 WSN密鑰預分配方案

本文方案基于以下假設:(1)所有節點只能與處于其通信范圍內的其他節點進行通信;(2)短時間內基站處于安全位置。

3.1 網絡初始化

其中,nA為節點生成的隨機數,基站收到節點的位置信息LocA后,根據網絡中節點的分布情況,將大的地理區域劃分為M×N較小的區域domain(i,j),同時將密鑰種子池劃分為與地理區域相對應且不重疊的M×N個子密鑰種子池subset(i,j),各地理區域與子密鑰種子池對應一個區域標識GID。基站將該節點所屬區域標識GIDA返回給各節點:

圖1 區域劃分及密鑰選取

3.2 通信密鑰的發現

網絡初始化結束后,為與相鄰節點建立通信密鑰,節點廣播自己的區域標識GIDA。

A通信半徑內節點B收到A廣播的數據包,根據是否與A同一區域,分2種情況:

(1)B與A屬于同一區域。B節點收到數據包后,比較GIDA與GIDB是否相等,若相等,則屬于同一區域。B節點查找該節點存儲的區域標識GIDB對應的密鑰種子池subset(i,j),使用池內種子seedi隨機生成長度為m的的連續片段作為模式Y(B),將該片段對應的SeedIDi片段Y′(B)發送給A,Y′(B)長度相對較小。

(2)B與A不屬于同一區域但所選子密鑰種子池區域有部分重合。B從重合區域中隨機選取一個區域GIDselect,和屬于同一區域的方法類似,使用該區域種子生成模式片段Y(B),將對應的SeedIDi片段Y′(B)發送給A。

A根據解密收到的數據包選取GIDB或GIDselect對應區域種子seedi,使用seedi隨機生成長度為n(n＞m)的文本片段作為模式匹配的文本X(A),提取相應的指紋函數值比較Y′(B)對應的模式Y(B)與X(A)是否匹配。若匹配成功,則用指紋值和匹配成功的位置生成通信密鑰進行通信,按以下步驟生成通信密鑰:

若生成通信密鑰,則將p和匹配位置l加密傳送給B。

B通過解密A發送回的數據包計算通信密鑰kA,B=H(Ip(Y(B)),l)。所有通信密鑰生成結束后,為防止節點被俘獲泄露通信密鑰信息,節點需刪除存儲的匹配文本X(A)和模式Y(B),通信密鑰的生成基本上實現“一次一密”。

3.3 密鑰路徑的建立

通信密鑰發現結束后,傳感器網絡構成一個共享密鑰圖G(V,E),圖G由找到共享密鑰的鄰居節點和其安全鏈路構成。沒有找到匹配建立通信密鑰的節點通過其他存在共享密鑰的鄰居節點經過若干跳后建立雙方的一條密鑰路徑。為發現與目標節點通信的密鑰路徑,源節點挑選一系列已經與它建立共享密鑰的中間節點,并發送請求給所有中間節點。如果中間的某一節點與目標節點有一個直接的共享密鑰,這條密鑰路徑就已找到。否則,中間節點將繼續轉發請求,此過程類似路由發現過程。該過程為減少通信開銷,可以把廣播范圍限定在3跳之內。

4 性能分析

4.1 連通性分析

圖2 網絡連通率與鄰居節點數的關系

4.2 存儲開銷分析

節點的存儲開銷即為建立通信密鑰所需的存儲空間。本文方案的存儲開銷主要為模式匹配過程中生成的匹配文本的存儲。圖3為網絡的連通性與節點存儲密鑰數量之間的關系。本文方案和其他方案不同,節點存儲的是用來匹配的文本X(A),M=N= 4,種子密鑰池中種子數S=32,子種子密鑰池種子數s=2,模式長度m=3,只有當m＜n時才可進行模式匹配,其他方案中密鑰池大小為10 000。從圖中看出,當節點存儲的文本長度約達到37時,網絡中有較高的連通概率(約為0.99)。而達到同樣概率,EG方案需存儲的密鑰環長度約為213,Q-composite方案約為255。通過比較,本文方案存儲性能有很大程度提高。

圖3 網絡連通率與節點存儲密鑰數量的關系

4.3 計算開銷分析

節點的計算開銷是節點生成通信密鑰時計算所消耗的能量。本文方案的計算開銷主要為輔助密鑰的生成和匹配操作所需開銷。輔助密鑰的計算為網絡初始化時節點生成初始密鑰Kmaster、生成用于加密通信消息的派生密鑰以及找到匹配時通信密鑰的計算。在模式匹配過程中,節點計算Wp,Ip(Y(B))和Ip(X(A)1)耗費的時間為O(m)。根據Ip(X(A)l)計算Ip(X(A)l+1)時,只需常數個加減法運算,逐個匹配時(2≤l≤n-m+1),計算每個Ip(X(A)l)僅需O(1)的時間,總共需要O(n)的時間,因此,本文方案中模式匹配的時間為O(m+n),適合于WSN節點計算能力有限的特點。

4.4 通信開銷分析

節點的通信開銷是節點生成通信密鑰時發送和接收消息所消耗的能量。本文方案中區域內任意節點只與通信范圍內節點通信產生開銷。在網絡初始化時,節點將位置信息Loc發送給基站并接收基站分配的區域標識GID產生通信開銷。通信密鑰發現階段時,設區域密度為D,節點的通信半徑為R,每個節點向通信范圍內的πDR2-1個節點廣播挑戰信息,收到廣播的節點對其進行判斷并決定是否生成模式與其文本匹配。通信過程中節點標識NID、區域標識GID和種子長度seedi較短,因此產生的通信開銷較小。

4.5 安全性分析

網絡的安全性表現在部分傳感器節點被俘獲時,攻擊者利用節點存儲的信息竊聽其他節點間的通信。本文方案的安全性主要基于以下3點:(1)使用密鑰種子seedi用于匹配的模式和文本從而生成密鑰,而不直接預置密鑰,模式和文本的生成過程隨機使通信密鑰的生成具有不可預測性,即使節點被俘獲,攻擊者只能竊取該節點與其建立通信密鑰節點的通信密鑰,不能計算出其他節點間的通信密鑰,網絡受影響范圍不大。(2)通信密鑰生成結束后,節點刪除模式和文本,該操作增加了破解密鑰的難度,通信密鑰發現過程中即使俘獲部分信息,也很難推算出通信密鑰。(3)基于區域的設計使某一區域內節點被俘獲,也只會增加局部區域被攻擊的概率,不會對整個網絡安全產生影響。

5 結束語

本文在區域劃分的基礎上,提出一種通過提取指紋進行模式匹配的密鑰預分配方案,并將其與E-G和Q-composite方案進行比較。實驗結果表明,該方案提高了鄰居節點發現共享密鑰的概率及網絡連通性能。此外,網絡存儲方面的性能也得到改善,節點存儲的密鑰環長度大大減小。方案中模式長度m和匹配文本長度n的選擇以及區域劃分的數量是需重點考慮的因素。此外,如何減少通信代價及提高網絡的擴展性是下一步研究的主要內容。

［1]蘇 忠,林 闖,封富君.無線傳感器網絡密鑰管理的方案和協議［J］.軟件學報,2007,18(5):1218-1231.

［2]米 波,曹建秋,段書凱,等.無線傳感器網絡密鑰管理問題綜述［J］.計算機工程與應用,2011,47(13): 77-82.

［3]馬祖長,孫怡寧,梅 濤.無線傳感器網絡綜述［J］.通信學報,2004,25(4):114-124.

［4]Eschenauer L,Gligor V D.A Key-management Scheme for Distributed Sensor Networks［C］//Proceedings of the 9th ACM ConferenceonComputerandCommunications Security.New York,USA:ACM Press,2002:41-47.

［5]Chan H,Perrig A,Song D.Random Key Predistribution Schemes for Sensor Networks［C］//Proceedings of 2003 Symposium on Security and Privacy.Washington D.C., USA:IEEE Press,2003:197-213.

［6]劉志宏,馬建峰,黃啟萍.基于區域的無線傳感器網絡密鑰管理［J］.計算機學報,2006,29(9):1608-1616.

［7]李長庚,劉 波,歐蘭英,等.基于區域劃分的WSN混沌密鑰管理方案［J］.計算機工程,2012,38(8): 95-97.

［8]翁年鳳,刁興春,曹建軍,等.不確定模式匹配研究綜述［J］.計算機科學,2012,38(12):1-5.

［9]廖 闊,楊萬麟.點模式指紋匹配算法研究與實現［J］.電子科技大學學報,2004,33(2):154-157.

［10]孔貝貝,唐小虎.基于地理位置的蜂窩狀密鑰管理方案［J］.計算機應用研究,2010,27(4):1514-1520.

［11]Liu D,Ning P.Location-based Pairwise Key Establishments for Static Sensor Networks［C］//Proceedings of the 1st ACM Workshop on Security of Ad Hoc and Sensor Networks.New York,USA:ACM Press,2003:72-82.

［12]Alsuwaiyel M H.算法設計技巧與分析［M］.吳偉昶,譯.北京:電子工業出版社,2010.

編輯 索書志

Key Pre-distribution Scheme of Wireless Sensor Network Based on Fingerprint Pattern Matching

WU Xujing,XU Yong,ZHANG Yanan
(College of Mathematics and Computer Science,Anhui Normal University,Wuhu 241003,China)

With the widely application of the Wireless Sensor Network(WSN),the security problem is more and more prominent.The distribution and management of WSN receive more and more attention.This paper proposes a key predistribution scheme which matches patterns according to the fingerprint identification by dividing the network after collecting the deployment information.The scheme divides the network into several domains,and the seed pool is divided into multiple sub-seed pools relatively.Nodes select seeds from relative areas to generate patterns and texts,and use fingerprint function values as communication keys when match successfully.The performance and security analysis shows that the scheme can substantially improve a network’s connectivity and reduce storage consumption compared with the traditional random key pre-distribution scheme.

Wireless Sensor Network(WSN);deployment information;regional dividing;fingerprint identification; pattern matching;key pre-distribution

吳旭婧,許 勇,張亞楠.基于指紋模式匹配的無線傳感器網絡密鑰預分配方案［J］.計算機工程, 2015,41(3):106-109.

英文引用格式:Wu Xujing,Xu Yong,Zhang Yanan.Key Pre-distribution Scheme of Wireless Sensor Network Based on Fingerprint Pattern Matching［J］.Computer Engineering,2015,41(3):106-109.

1000-3428(2015)03-0106-04

:A

:TP309

10.3969/j.issn.1000-3428.2015.03.020

安徽省2013年千人培養計劃基金資助項目(151408)。

吳旭婧(1990-),女,碩士研究生,主研方向:網絡與信息安全;許 勇,教授;張亞楠,碩士研究生。

2014-03-24

:2014-05-20E-mail:kidaulthood@163.com