基于指紋模式匹配的無(wú)線傳感器網(wǎng)絡(luò)密鑰預(yù)分配方案

吳旭婧,許 勇,張亞楠

(安徽師范大學(xué)數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院,安徽蕪湖241003)

基于指紋模式匹配的無(wú)線傳感器網(wǎng)絡(luò)密鑰預(yù)分配方案

吳旭婧,許 勇,張亞楠

(安徽師范大學(xué)數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院,安徽蕪湖241003)

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

無(wú)線傳感器網(wǎng)絡(luò);部署信息;區(qū)域劃分;指紋識(shí)別;模式匹配;密鑰預(yù)分配

1 概述

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

目前普遍認(rèn)為可行的方法是密鑰預(yù)分配方案,即把密鑰預(yù)置裝入傳感器節(jié)點(diǎn)。文獻(xiàn)［4］提出了一種基于經(jīng)典隨機(jī)圖理論的隨機(jī)密鑰預(yù)分配方案(簡(jiǎn)

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

2 模式匹配與指紋提取

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

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

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

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

3 WSN密鑰預(yù)分配方案

本文方案基于以下假設(shè):(1)所有節(jié)點(diǎn)只能與處于其通信范圍內(nèi)的其他節(jié)點(diǎn)進(jìn)行通信;(2)短時(shí)間內(nèi)基站處于安全位置。

3.1 網(wǎng)絡(luò)初始化

其中,nA為節(jié)點(diǎn)生成的隨機(jī)數(shù),基站收到節(jié)點(diǎn)的位置信息LocA后,根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的分布情況,將大的地理區(qū)域劃分為M×N較小的區(qū)域domain(i,j),同時(shí)將密鑰種子池劃分為與地理區(qū)域相對(duì)應(yīng)且不重疊的M×N個(gè)子密鑰種子池subset(i,j),各地理區(qū)域與子密鑰種子池對(duì)應(yīng)一個(gè)區(qū)域標(biāo)識(shí)GID。基站將該節(jié)點(diǎn)所屬區(qū)域標(biāo)識(shí)GIDA返回給各節(jié)點(diǎn):

圖1 區(qū)域劃分及密鑰選取

3.2 通信密鑰的發(fā)現(xiàn)

網(wǎng)絡(luò)初始化結(jié)束后,為與相鄰節(jié)點(diǎn)建立通信密鑰,節(jié)點(diǎn)廣播自己的區(qū)域標(biāo)識(shí)GIDA。

A通信半徑內(nèi)節(jié)點(diǎn)B收到A廣播的數(shù)據(jù)包,根據(jù)是否與A同一區(qū)域,分2種情況:

(1)B與A屬于同一區(qū)域。B節(jié)點(diǎn)收到數(shù)據(jù)包后,比較GIDA與GIDB是否相等,若相等,則屬于同一區(qū)域。B節(jié)點(diǎn)查找該節(jié)點(diǎn)存儲(chǔ)的區(qū)域標(biāo)識(shí)GIDB對(duì)應(yīng)的密鑰種子池subset(i,j),使用池內(nèi)種子seedi隨機(jī)生成長(zhǎng)度為m的的連續(xù)片段作為模式Y(jié)(B),將該片段對(duì)應(yīng)的SeedIDi片段Y′(B)發(fā)送給A,Y′(B)長(zhǎng)度相對(duì)較小。

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

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

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

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

3.3 密鑰路徑的建立

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

4 性能分析

4.1 連通性分析

圖2 網(wǎng)絡(luò)連通率與鄰居節(jié)點(diǎn)數(shù)的關(guān)系

4.2 存儲(chǔ)開銷分析

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

圖3 網(wǎng)絡(luò)連通率與節(jié)點(diǎn)存儲(chǔ)密鑰數(shù)量的關(guān)系

4.3 計(jì)算開銷分析

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

4.4 通信開銷分析

節(jié)點(diǎn)的通信開銷是節(jié)點(diǎn)生成通信密鑰時(shí)發(fā)送和接收消息所消耗的能量。本文方案中區(qū)域內(nèi)任意節(jié)點(diǎn)只與通信范圍內(nèi)節(jié)點(diǎn)通信產(chǎn)生開銷。在網(wǎng)絡(luò)初始化時(shí),節(jié)點(diǎn)將位置信息Loc發(fā)送給基站并接收基站分配的區(qū)域標(biāo)識(shí)GID產(chǎn)生通信開銷。通信密鑰發(fā)現(xiàn)階段時(shí),設(shè)區(qū)域密度為D,節(jié)點(diǎn)的通信半徑為R,每個(gè)節(jié)點(diǎn)向通信范圍內(nèi)的πDR2-1個(gè)節(jié)點(diǎn)廣播挑戰(zhàn)信息,收到廣播的節(jié)點(diǎn)對(duì)其進(jìn)行判斷并決定是否生成模式與其文本匹配。通信過程中節(jié)點(diǎn)標(biāo)識(shí)NID、區(qū)域標(biāo)識(shí)GID和種子長(zhǎng)度seedi較短,因此產(chǎn)生的通信開銷較小。

4.5 安全性分析

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

5 結(jié)束語(yǔ)

本文在區(qū)域劃分的基礎(chǔ)上,提出一種通過提取指紋進(jìn)行模式匹配的密鑰預(yù)分配方案,并將其與E-G和Q-composite方案進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明,該方案提高了鄰居節(jié)點(diǎn)發(fā)現(xiàn)共享密鑰的概率及網(wǎng)絡(luò)連通性能。此外,網(wǎng)絡(luò)存儲(chǔ)方面的性能也得到改善,節(jié)點(diǎn)存儲(chǔ)的密鑰環(huán)長(zhǎng)度大大減小。方案中模式長(zhǎng)度m和匹配文本長(zhǎng)度n的選擇以及區(qū)域劃分的數(shù)量是需重點(diǎn)考慮的因素。此外,如何減少通信代價(jià)及提高網(wǎng)絡(luò)的擴(kuò)展性是下一步研究的主要內(nèi)容。

［1]蘇 忠,林 闖,封富君.無(wú)線傳感器網(wǎng)絡(luò)密鑰管理的方案和協(xié)議［J］.軟件學(xué)報(bào),2007,18(5):1218-1231.

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

［3]馬祖長(zhǎng),孫怡寧,梅 濤.無(wú)線傳感器網(wǎng)絡(luò)綜述［J］.通信學(xué)報(bào),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]劉志宏,馬建峰,黃啟萍.基于區(qū)域的無(wú)線傳感器網(wǎng)絡(luò)密鑰管理［J］.計(jì)算機(jī)學(xué)報(bào),2006,29(9):1608-1616.

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

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

［9]廖 闊,楊萬(wàn)麟.點(diǎn)模式指紋匹配算法研究與實(shí)現(xiàn)［J］.電子科技大學(xué)學(xué)報(bào),2004,33(2):154-157.

［10]孔貝貝,唐小虎.基于地理位置的蜂窩狀密鑰管理方案［J］.計(jì)算機(jī)應(yīng)用研究,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.算法設(shè)計(jì)技巧與分析［M］.吳偉昶,譯.北京:電子工業(yè)出版社,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

吳旭婧,許 勇,張亞楠.基于指紋模式匹配的無(wú)線傳感器網(wǎng)絡(luò)密鑰預(yù)分配方案［J］.計(jì)算機(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年千人培養(yǎng)計(jì)劃基金資助項(xiàng)目(151408)。

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

2014-03-24

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