王 桐，季本洋

(哈爾濱工程大學信息與通信工程學院，哈爾濱150001)

無線傳感器網絡(WSN)［1］由分布在一個廣泛區(qū)域內的許多節(jié)點組成，傳感器節(jié)點監(jiān)測部署區(qū)域的信息，實現數據采集和任務監(jiān)測.當無線傳感器網絡部署在無人觸及甚至敵方控制的環(huán)境時，節(jié)點將面臨各種各樣的攻擊.因此，如何保證無線傳感器網絡安全是無線傳感器網絡研究領域里的重要內容，其中最基本的一項研究內容是密鑰管理［2］，主要目的是為傳感器節(jié)點建立共享密鑰，從而為網絡提供安全的通信鏈路.大量研究表明，對稱密鑰管理方法以其簡單高效的特點更加符合未來WSN網絡的安全應用.WSN網絡對稱密鑰管理的核心是密鑰預分配(key pre-distribution)，其基本實現過程為在網絡部署前預先給每一個節(jié)點分配一定數量的密鑰信息，部署后任何兩個需要安全通信的節(jié)點使用各自的密鑰信息創(chuàng)建出一個共享的成對密鑰(pair-wise key)來保護未來產生的通信量. WSN網絡密鑰預分配方法［3］中密鑰的分配在節(jié)點部署之前就已完成，解決了無線傳感器網絡建立后分配密鑰所帶來的能量消耗問題，成為目前的研究熱點.

按密鑰的選取方式，目前的無線傳感器網絡密鑰預分配方法可以分成概率性方法和確定性方法兩種.概率性方法:Eschenauer和Gligor［4］提出了實際有效的傳感器網絡概率性密鑰預分配方法.該方法為研究傳感器網絡應用安全保護機制提供了方向性的建議.之后，Haowen等人提出的q-composite［5］方法，使得通信雙方能夠共有q個密鑰，從而增強了網絡的健壯性.Liu［6］等人也提出了基于有限域上對稱二元多項式的隨機密鑰預分配方法，通過預分配的對稱多項式來計算出共享密鑰，但是卻帶來了較大的計算開銷.確定性方法:確定性方法是指在預分配時不是隨機選取密鑰，而是按照特定模型去構造節(jié)點密鑰鏈.第一個確定性密鑰預分配模型是由Camtepe［7］等人提出的對稱平衡不完全區(qū)組設計方法BIBD，為了提高密鑰連通概率，該方法利用區(qū)組設計和有限影射平面構造密鑰預分配模型，可以構造出節(jié)點數為n2+n+1，密鑰鏈長度為n+1，每對節(jié)點正好共享1個密鑰的模型.Lee和Stinson在Camtepe等人的研究基礎上提出了TD模型［8］，Du等人提出了基于多密鑰空間的增強的Bloom模型［9］等等，但是這些方法存在算法復雜、計算開銷大的問題.為了解決上述問題，本文對TD方法進行改進，結合Blom對稱多項式算法提出一種無線傳感器網絡分組密鑰預分配方法CCITD (Improved TD scheme based on Crossless Class)，該方法的主要貢獻為:1)提高相鄰節(jié)點之間共享密鑰的概率，從而提高了節(jié)點之間的連通率;2)可以根據節(jié)點存儲能力改變節(jié)點存儲的密鑰個數進而使整個網絡靈活易變以適應實際需求.

1 相關算法

1.1 Blom矩陣

Blom矩陣［10］利用素域GF(q)上形成的密鑰對生成矩陣A×G來定義節(jié)點間的密鑰對，其中q是能夠支持網絡節(jié)點數的最小的素數，G是一個(λ+1)×N的公共矩陣，N可認為是網絡節(jié)點數目，λ為網絡安全閾值，即只要網絡中被俘的節(jié)點數不大于λ，就不會對現有節(jié)點構成威脅.G通常由范德蒙矩陣生成，因此每個節(jié)點只需存儲每列的第二個元素就可以衍生出整個列，可以減少節(jié)點的存儲空間.令A=(D×G)T，D為一個保密的隨機對稱矩陣，D=(λ+1)(λ+1)，則A×G對應一個N×N的對稱矩陣.若記Kmm為A×G中的第m行和第n列的值，則有:Kij=Kji.每個節(jié)點根據自己的編號i存儲矩陣A的第i行和矩陣G的第i列.當節(jié)點i和j要生成共享密鑰時，彼此交換自己所存儲的的列，然后根據矩陣乘法計算各自的Kij和Kji，由于Kij=Kji，這樣節(jié)點i和j建立起了對密鑰.

1.2 TD方法

Lee和Stinson利用一種特殊的可分組設計(Transversal Design)，構造了一類新的基于組合設計的密鑰預分配方法.設(X，B)為一個區(qū)組設計，其中:X有v個點，B是X的一個有限子集，稱為區(qū)組，每個區(qū)組都有k個點，且每一個點x都在r個區(qū)組中出現，稱這樣的區(qū)組設計是(v，b，r，k)結構，易得bk=vr.如果一個區(qū)組設計(X，B)滿足對于任意一個元素x∈X，在B的r個區(qū)組中出現，且B中任意兩個不同的區(qū)組Bi，Bj，，至多相交于有一個點，稱這樣的區(qū)組設計(X，B)為一個(v，b，r，k)結構.由這樣的(X.B))構造的密鑰預分配方法的特點是:對于節(jié)點N來說，與其有公共密鑰的節(jié)點個數達到理論上的最大值.TD(k，n)設計是滿足以下條件的三元組(X，B，H):1)X是一個有kn個點的集合，B是集合X的子集構成的集合，其元素Bi(0≤i≤b)稱為區(qū)組，每個區(qū)組Bi都含有k個元素，2)H是X的一個劃分，分成k組，每組n個點，3)每一個組H和每一個區(qū)組Bi(0≤i≤b)只有一個點相同;4)從不同組任意選出兩個點x，y，恰好只在一個區(qū)組中同時出現.

2 基于不相交類的密鑰預分配方法

對TD方法進行改進，提出基于不相交類的密鑰預分配方法CCITD(Improved TD Scheme based on Crossless Class).

首先，根據TD方法，提出一個基于不相交類的TD(k，n)模型.模型包含個點，把kn個點分成個集合，每個集合包含n個點，集合被稱為組(這里的組指的是模型中的組，而不是傳感器節(jié)點組)，取kn點中的k個點組成區(qū)組，區(qū)組的集合設為B區(qū)組可以被分成B1，B2，…，Bn個集合.

定義1 不相交類:對于每一個集合B，每一個點只在其中的一個區(qū)組出現一次.這些區(qū)組的集合B被稱為不相交類.

從以上的定義可知，有n2個區(qū)組，每個區(qū)組包含k個點，每個區(qū)組只和每個組的一個點相交.有n個不相交類，每個不相交類包含n個區(qū)組，在同一個不相交類中的兩個區(qū)組不包含相同的點.

舉例說明，以下是一個基于不相交類的TD(3，5)模型，這個設計包含15個點，將點分成3個組G，每個組包含5個點.共有5個不相交類，每個不相交類包含5個區(qū)組，每個區(qū)組包含3個不同的點，設點的集合為{00，01，02，03，04，10，11，12，13，14，20，21，22，23，24)}.

可以發(fā)現，每個點只在一個組Gi中出現，每個區(qū)組Li從每個組G中取一個點組合而成，每個點只在一個不相交類Bi中出現一次.在CCITD方法中，把點和密鑰相對應，區(qū)組和節(jié)點相對應，要利用設計的不相交類分配組內的節(jié)點.在闡述CCITD方法之前，先來考慮組內和組間密鑰的分配過程.

考慮一個n組節(jié)點的傳感器網絡，每組中有n個傳感器節(jié)點，對于初始值n，可以把設計出來的區(qū)組和傳感器節(jié)點相關聯，包含區(qū)組的不相交類和傳感器節(jié)點組相關聯.

對于CCITD(k，n)(1＜k＜n)，以增加存儲量為代價，增加一個變量k以提高不同傳感器節(jié)點組之間的連通率.考慮傳感器節(jié)點數量為n2的情況.當λ是的n的除數的時候，通過把TD(k，n)的n個不相交類分成λ個不相交的集S1，S2，…Sλ，每個集合包n/λ含個不相交類，并且讓不相交類中的區(qū)組和節(jié)點組中的傳感器節(jié)點相對應，當傳感器節(jié)點組群數量比較小的時候，這種方法可以保持高連通率.

CCITD方法中的點和Blom矩陣的t次對稱多項式相關聯.因此，不同節(jié)點組間節(jié)點對能夠建立密鑰連接，每個節(jié)點需要存儲k(t+1)個密鑰.在CCITD方法中，通過在每個不相交類中引入獨立的基于多項式方法來減少節(jié)點間密鑰計算的難度，提高節(jié)點連通率，對于不同節(jié)點組的節(jié)點，也會通過不相交類來實現連接.

定義2 CCITD方法:給出一個初始變量n，一個非負整數k(1≤k≤n)，一個組數λ和一個t，0≤n2/λ-1-1，使用TD(k，n)來建立一個密鑰預分配方法，n2個節(jié)點分布在λ個組中(G1，G2，…，Gλ)，每個組中含有n2/λ個節(jié)點.

1)CCITD(k，n)將n個P1，P2，…，Pn不相交類分成λ個集合，每個集合含有n/λ個不相交類，用S1，S2，…，Sλ來表示每個集合.每個集合含有n2/λ個區(qū)組.

2)傳感器節(jié)點對應CCITD方法中的區(qū)組，傳感器節(jié)點對應組Si.

3)一個Blom矩陣的t次對稱多項式對應于CCITD方法中的點，將點分配給相應的區(qū)組.

4)一個Blom矩陣的t次對稱多項式被分配給每一個不相交類Pi，1≤i≤n，之后通過把這個多項式分配給相應節(jié)點(這些節(jié)點所對應的區(qū)組被包含在不相交類Pi中).表1總結了密鑰預分配方法和CCITD方法的對應關系.

表1 無線傳感器網絡和CCITD方法的對應關系

下面對 CCITD方法進行舉例說明，假設CCITD(3，5)，t=1，構建25個節(jié)點，分布于5個部署組中，每個部署組中5個節(jié)點，每個節(jié)點存儲對應的8個密鑰.n/λ=1，所以每個集合Si只包含一個不相交類.假設第1組節(jié)點含有IDs l，m，r，s，t.第2組節(jié)點含有IDs u，v，w，xy把和點(point)相對應的Blom多項式表示為，把和每個不相交Bi類對應的Blom多項式表示為，則前兩個節(jié)點組如下所示

應用CCITD方法建立的密鑰預分配方法具有如下性質:

1)每個節(jié)點相當于存儲(k+1)(t+1)個密鑰.

2)對于每個Blom矩陣的多項式，有n個節(jié)點應用到那個Blom多項式.

3)q=k/n.

證明:

1)每個CCITD(k，n)中的區(qū)組都包含k個點，且都被包含在一個不相交類中.每個節(jié)點存儲k+ 1個Blom多項式，所以每個節(jié)點要求存儲(k+1) (t+1)個密鑰.

2)每個CCITD(k，n)的點被包含在n個區(qū)組中，每個不相交類正好含有n個區(qū)組，因此每個Blom多項式分配給n個節(jié)點.

3)如果不同組的兩個節(jié)點對應的區(qū)組相交，那么他們擁有一個共同的Blom多項式，因為設計的區(qū)組中每個含有k個點，每個點還位于n-1個其他的區(qū)組中，所以不同組間節(jié)點共享密鑰的概率為k(n-1)/(n2-n)=k/n=q.

4)對應于同一個不相交類中的區(qū)組，兩個節(jié)點來自同一個組的概率為(n-1)/(n2/λ-1)，在這種情況下，他們擁有共同的Blom多項式.相反的，節(jié)點對應的區(qū)組分布在不同不相交類中的概率為(n2/λ-n)/(n2/λ-1)，在這種情況下，他們擁有相同Blom多項式的概率為k/n.因此同一組中隨機抽取兩個節(jié)點，他們擁有相同密鑰的概率為.

可以發(fā)現，對于λ＞1，q＜p.

3 分析與評價

3.1 節(jié)點連通度

如果一組中的2個節(jié)點是相鄰節(jié)點，那么通過一跳或者二跳建立連接的概率是

其中:η是組內相鄰節(jié)點數，p是組內節(jié)點建立直接密鑰的概率.

考慮同組內的一對相鄰傳感器節(jié)點不能共享一對密鑰的概率為1-p.對于每一個普通的相鄰節(jié)點，通過2跳路徑無法建立連接的概率為1-p2.因此，節(jié)點間無法通過兩跳來建立共享密鑰的概率為(1-p)(1-p2)η.

如果兩個相鄰節(jié)點分別屬于不同的部署組，那么它們通過1跳或者2跳建立連接的概率為

其中:η為相鄰節(jié)點數，p為組內節(jié)點共享密鑰的概率，q為組間節(jié)點共享密鑰的概率.

兩個來自不同組的相鄰節(jié)點不能共享密鑰的概率為(1-q).在它們的組內這些節(jié)點有η個普通相鄰節(jié)點.對于每一個這樣的相鄰節(jié)點，節(jié)點不能通過這個相鄰節(jié)點建立兩跳連接的概率為(1-pq).因此，在它不能通過一跳或者兩跳建立連接的概率為(1-q)(1-pq)2n.所以，他們能通過1跳或者2跳建立連接的概率為1-(1-q)(1-pq)2η.

3.2 仿真結果和性能對比

仿真過程如下，設計一個10 000個節(jié)點的傳感器網絡，給出CCITD(25，100)，假設η=7，結合CCITD方法中的p、q以及公式(1)，(2)得到如圖1的仿真結果，橫坐標表示傳感器節(jié)點分組的數目，縱坐標表示CCITD方法相鄰節(jié)點間的連通率.

圖1 CCITD密鑰預分配方法中相鄰節(jié)點之間共享密鑰概率

由圖1可知，本地連接概率隨著節(jié)點組組數的增加而提高，并且組內和組內節(jié)點連通率都保持在一個較高的水準.

為了與 CCITD方法進行對比，部分實現了Liu［10］的方法，將10 000個節(jié)點分布在λ個組中，參數η=7，結合公式1，2，得到如圖2的仿真結果.圖2的橫坐標表示傳感器節(jié)點分組的數目，縱坐標表示不同組間傳感器相鄰節(jié)點的連通率.可以發(fā)現對于不同組的傳感器節(jié)點，CCITD方法的不同組間節(jié)點連通率遠高于Liu的方法.這是因為傳統分組密鑰預分配方法組間密鑰共享概率很低，嚴重影響整體連接，整個組群可能與網絡斷開連接，此外，即使組群正在連接之中，少數節(jié)點必須承擔組群中的通信負擔，很可能使組群的通信出現瓶頸.

Liu的方法要求組內節(jié)點的連通率為100%，當每個節(jié)點組很大時，獨立的成對密鑰對存儲的需求變的非常高.另一方面，當組群數量變小時，基于多項式算法的抗捕獲性也會變弱.無法調整的連接意味著對于節(jié)點數量比較大的組群，Liu的方法是不合適的.而CCITD方法比較好的解決了這個問題［11-12］.

圖2 CCITD方法和Liu的方法中不同組間相鄰節(jié)點間共享密鑰概率對比

另外CCITD(k，n)方法中每個節(jié)點存儲個密鑰，增大則節(jié)點存儲的密鑰數量增加，節(jié)點間的連通率提高，但是這樣傳感器節(jié)點的存儲量就會變大，能量消耗也會變大，因此，可以根據實際需要來規(guī)定的值，以達到連通率和節(jié)點存儲量的平衡.

4 結語

本文提出一種改進的無線傳感器密鑰預分配方法CCITD，該方法的優(yōu)勢在于:可獲得較好的相鄰傳感器節(jié)點間連通率;可動態(tài)的、根據實際需要去改變節(jié)點數量，節(jié)點組數量以及節(jié)點中所存儲的密鑰數目，從而適應不同應用環(huán)境對傳感器網絡的需求.

［1］ 孫利民，李建中.無線傳感器網絡［M］.北京:清華大學出版社，2005.

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

［3］ 夏戈明，黃遵國，王志英.基于對稱平衡不完全區(qū)組設計的無線傳感器網絡密鑰預分配方法閉［J］.計算機研究與發(fā)展，2008，45(l):154-164.

［4］ ESCHENAUER L，AND GLIGOR V D.A key-management scheme for distributed sensor networks［C］//Proceedings of the ACM Conference on Computer and Communications Security (CCS’02)，ACM，New York，2002，41-47.

［5］ CHAN H，PERRIG A，SONG D.Random key pre-distribution schemes for sensor networks［C］//Process of IEEE Symposium on Research in Security and Privacy，Berkeley:IEEE Computer Society，2003:197-213.

［6］ LIU D，NING P.Establishing pairwise keys in distributed sensor networks［C］//Process of the 10th ACM Conference on Computer and Communications Security，New York:ACM Press，2003: 52-61.

［7］ CAMTEPE S A，YENER B.Key distribution mechanisms for wireless sensor networks:a survey［R］.Tech.rep.TR-05-07，Rensselaer Polytechnic Institute，2005.

［8］ LEE J，STINSON D R.On the construction of practical key predistribution schemes for distributed sensor networks using combinatorial designs［J］.ACM Trans.Inform.Syst.Secur.，2008，11(2):1-35.

［9］ WEN L D，JING D.A pairwise key predistribution scheme for wireless sensor networks［C］ //Proceedings of the 10th ACM conference and communications Security，New York:ACM Press，2003:42-51.

［10］ BLOM R.An optimal class of symmetric key generation systems［C］//Proceedings of EUROCRYPT’84.Lecture Notes in Computer Science，Berlin:Springer-Verlag，1985(209):335 -338.

［11］ LIU D，NING P，DU W.Group-based key pre-distribution in wireless sensor networks［J］.ACM Trans.Sen.Netw.，2005，4(2):1-30.

［12］ 黃 玲，陳東彥，王攀宇.數據包錯序的多包傳輸網絡控制系統研究［J］.哈爾濱商業(yè)大學學報:自然科學版，2011，27 (6):857-861.