陳尚弟 張俊梅

(中國民航大學(xué) 天津 300300)

1 引言

無線傳感器網(wǎng)絡(luò)是由若干低成本且資源有限的傳感器節(jié)點(diǎn)組成的一種分布式傳感器網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)技術(shù)是在計(jì)算機(jī)技術(shù)中的突破和創(chuàng)新，作為一種新型的信息收集和處理技術(shù)，具有耗能低、成本低、功能齊全等優(yōu)點(diǎn)，有著非常廣闊的發(fā)展前景[1]。隨著它的廣泛應(yīng)用，網(wǎng)絡(luò)安全問題也受到人們的重視。節(jié)點(diǎn)在部署到目標(biāo)區(qū)域后容易受到敵方攻擊，如信息在傳輸時(shí)被竊聽、篡改、泄密等。在現(xiàn)代密碼學(xué)中，信息的保密性主要取決于密鑰的保密性，因此如何管理密鑰成為一個(gè)極具挑戰(zhàn)的問題。密鑰預(yù)分配是指節(jié)點(diǎn)在部署到目標(biāo)區(qū)域前就將密鑰分配給各個(gè)傳感器節(jié)點(diǎn)。所有的密鑰預(yù)分配方案分為密鑰預(yù)分配階段、共享密鑰發(fā)現(xiàn)階段和路徑密鑰建立階段。

通常從以下4個(gè)方面來分析一個(gè)密鑰預(yù)分配方案是否可行：

(1)網(wǎng)絡(luò)規(guī)模：方案所能支持的最大傳感器節(jié)點(diǎn)數(shù)目。

(2)密鑰環(huán)大小：每個(gè)節(jié)點(diǎn)所能存儲(chǔ)的密鑰量。

(3)連通概率：網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間有共享密鑰的概率，通常用p表示。

(4)損失概率：當(dāng)s個(gè)節(jié)點(diǎn)被捕獲時(shí)，一條隨機(jī)鏈接被破壞的概率，通常用f ail(s)來表示。

若某個(gè)節(jié)點(diǎn)被敵方捕獲，則該節(jié)點(diǎn)內(nèi)存儲(chǔ)的所有密鑰均被泄露。假設(shè)節(jié)點(diǎn)Nk被捕，并且節(jié)點(diǎn)Na和節(jié)點(diǎn)Nb的 共享密鑰存儲(chǔ)在Nk中 ，此時(shí)Na和Nb之間的鏈接就斷開了，Na和Nb之間的鏈接稱為損失的鏈接。網(wǎng)絡(luò)的損失概率反映了網(wǎng)絡(luò)中節(jié)點(diǎn)的抗捕獲能力，損失概率越大，節(jié)點(diǎn)抗捕獲能力越弱。fail(1)為 當(dāng)一個(gè)隨機(jī)節(jié)點(diǎn)被捕獲時(shí)，節(jié)點(diǎn)Na和Nb之間的鏈接被斷開的概率。由此可估算fail(s)=1?(1?fail(1))s。f ail(s)也可通過式(1)表達(dá)式直接求得

自Camtepe等人[2]首次提出利用組合設(shè)計(jì)構(gòu)造密鑰預(yù)分配方案之后，許多基于組合設(shè)計(jì)的密鑰預(yù)分配方案被提出。2010年P(guān)ei等人[3]基于有限域上有理正規(guī)曲線構(gòu)造了一個(gè)密鑰預(yù)分配方案，分析了基于該設(shè)計(jì)下的密鑰預(yù)分配方案的連通概率和損失概率。2015年Bag[4]將網(wǎng)絡(luò)分區(qū)，每個(gè)小區(qū)內(nèi)有普通節(jié)點(diǎn)和簇頭兩種傳感器節(jié)點(diǎn)，簇頭的數(shù)量取決于小區(qū)的大小。2017年Chen等人[5]基于可分解設(shè)計(jì)和有限域上辛幾何構(gòu)造了一系列密鑰預(yù)分配方案。2018年Kumar等人[6]將網(wǎng)絡(luò)分區(qū)，限制每個(gè)小區(qū)內(nèi)的簇頭數(shù)量為3，且將每個(gè)小區(qū)的通信范圍限制在給定小區(qū)的 Lee球體區(qū)域內(nèi)。這種做法既提高了節(jié)點(diǎn)的抗捕獲能力又降低了對(duì)節(jié)點(diǎn)的存儲(chǔ)要求。2019年Akhbarifar等人[7]描述了一種可擴(kuò)展的無線傳感器網(wǎng)絡(luò)安全模型，并提出了一種基于組合設(shè)計(jì)的混合密鑰預(yù)分配方案。提出了無線傳感器網(wǎng)絡(luò)的安全性仿真方法，并與以往的類似方案進(jìn)行了比較。同年袁琪等人[8]基于w?平衡不完全區(qū)組設(shè)計(jì)構(gòu)造了一個(gè)密鑰預(yù)分配方案。2020年P(guān)ang等人[9]分析了基于正交陣列漢明距離的密鑰預(yù)分配方案中用于評(píng)估連通性和彈性的度量的計(jì)算可以簡化。隨后在文獻(xiàn)[10]中給出精確的基于正交陣列的密鑰預(yù)分配方案的彈性的計(jì)算公式。研究了基于正交陣列的廣播增強(qiáng)密鑰預(yù)分發(fā)方案的連通性和彈性。同年Choudhary等人[11]提出了一種基于多項(xiàng)式的密鑰預(yù)分配方案，討論和分析了不同的密鑰分發(fā)協(xié)議，并提出了基于稀疏矩陣的高度安全的多項(xiàng)式池密鑰分發(fā)技術(shù)，以降低存儲(chǔ)和計(jì)算復(fù)雜度。2021年Belim等人[12]提出了一個(gè)廣義的密鑰預(yù)分配方案，密鑰材料是基于向量空間元素和向量空間上的對(duì)稱算子形成的。

近年來國內(nèi)外對(duì)密鑰預(yù)分配方案的研究很多，但基于各參數(shù)未達(dá)到最優(yōu)，本文將在這一方面做研究。本文利用有限域上辛空間中子空間之間的正交關(guān)系構(gòu)造了一個(gè)組合設(shè)計(jì)，并基于該設(shè)計(jì)構(gòu)造一個(gè)密鑰預(yù)分配方案。與其他方案相比本方案中節(jié)點(diǎn)的抗捕獲能力非常好，并且隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，方案的連通概率逐漸趨于1。本文創(chuàng)新點(diǎn)為基于有限域上的辛空間構(gòu)造了一個(gè)組合設(shè)計(jì)，并基于該設(shè)計(jì)構(gòu)造了一個(gè)密鑰預(yù)分配方案。基于辛空間構(gòu)造的密鑰預(yù)分配方案較少，方法上具有一定的創(chuàng)新性。

2 預(yù)備知識(shí)

本節(jié)介紹組合設(shè)計(jì)(區(qū)組設(shè)計(jì))和有限域上辛空間相關(guān)知識(shí)，其中辛空間的相關(guān)概念定理均參見文獻(xiàn)[13]。

2.1 組合設(shè)計(jì)

定義1[14]令X和B是兩個(gè)不相交的有限集合，I為X與B之 間 的2 元 關(guān) 系，即X?X×B。D=(X,B,I)為 一個(gè)關(guān)聯(lián)結(jié)構(gòu)，X中的元素稱為點(diǎn)，B中的元素稱為區(qū)組，I稱為關(guān)聯(lián)結(jié)構(gòu)。設(shè)x∈X,B∈B，若(xi,Bj)∈I， 則稱點(diǎn)xi與 區(qū)組Bj關(guān) 聯(lián)，并記作xiIBj。

當(dāng)D=(X,B,I)為有限關(guān)聯(lián)結(jié)構(gòu)時(shí)，通常記|X|=v, |B|=b。為方便X(B)表示與一給定的區(qū)組相關(guān)聯(lián)的點(diǎn)的集合，B(x)表示與一給定的點(diǎn)相關(guān)聯(lián)的區(qū)組的集合，并記|X(B)|=k, |B(x)|=r。另用δ表示與兩個(gè)不同的區(qū)組同時(shí)關(guān)聯(lián)的點(diǎn)數(shù)。

定義2 令v,k,λ,t均為正整數(shù)，且v≥k ≥2,λ ≥1,t≤k。D=(X,B,I)是一個(gè)關(guān)聯(lián)結(jié)構(gòu)，2元組(X,B)是 一個(gè)部分平衡t?(v,k;λ,0)區(qū)組設(shè)計(jì)，如果滿足下列條件：

(1) |X| = v 。

(2)對(duì)任意的B∈B, |B|=k。

(3)X的任意t元子集要么在B的0個(gè)區(qū)組中同時(shí)出現(xiàn)，要么在B的λ個(gè)區(qū)組中同時(shí)出現(xiàn)。

2.2 辛空間

對(duì)于Fq上 的2υ×2υ矩陣T，如果TKTT=K，則稱T是關(guān)于K的 一個(gè)辛矩陣。顯然2υ×2υ階的辛矩陣關(guān)于矩陣的乘法構(gòu)成了一個(gè)群，稱為Fq上 的關(guān)于K的 2υ階 辛群，記作S P2υ(Fq,K)， 簡記為S P2υ(Fq)。

定理4Fq上 2υ維辛空間中，一給定的(m,s)型子空間中的 (m1,s1) 型子空間的數(shù)目N(m1,s1;m,s;2υ)是

3 基于辛空間的密鑰預(yù)分配方案的構(gòu)造

本節(jié)利用辛空間V中的( 1,0)型 子空間和( 2,1)型子空間構(gòu)造一個(gè)組合設(shè)計(jì)，并基于該設(shè)計(jì)構(gòu)造了一個(gè)密鑰預(yù)分配方案。將整個(gè)目標(biāo)區(qū)域劃分為若干個(gè)大小相同的小區(qū)域，每個(gè)小區(qū)有普通節(jié)點(diǎn)和簇頭兩種類型的傳感器節(jié)點(diǎn)，簇頭的計(jì)算、存儲(chǔ)以及通信能力都優(yōu)于普通節(jié)點(diǎn)。同一小區(qū)內(nèi)的節(jié)點(diǎn)或者通過它們之間的共享密鑰直接通信，或者通過小區(qū)內(nèi)的簇頭間接通信，不同小區(qū)內(nèi)的節(jié)點(diǎn)只能通過簇頭建立通信。

3.1 部分平衡 2?設(shè)計(jì)的構(gòu)造

此時(shí)X稱為點(diǎn)集，B稱為區(qū)組集。

對(duì)x∈X,B∈B， 定義x與B關(guān) 聯(lián)當(dāng)且僅當(dāng)x⊥B。即x與B關(guān) 聯(lián)當(dāng)且僅當(dāng)( 2,1)型 子空間x與( 1,0)型子空間B是正交的。

定理5X中任意兩個(gè)不同的點(diǎn)或者與B中0 個(gè)區(qū)組關(guān)聯(lián)，或者與 1個(gè)區(qū)組關(guān)聯(lián)，即λ= 0 或 1。則(X,B) 是一個(gè)部分平衡2?(q4+q2,q2;1,0)區(qū)組設(shè)計(jì)。

證明 令x1和x2是X中任意兩個(gè)不同的點(diǎn)，則x1和x2為V中 兩 個(gè)不同 的( 2,1) 型 子 空間，并 且dim(x1+x2)=3 或4。

若dim(x1+x2)=3 ，根據(jù)2υ維辛空間中存在(m,s)型 子空間的條件，x1+x2是 一個(gè)( 3,1)型子空間。 則 (x1+x2)⊥是 一 個(gè)( 1,0)型 子 空 間， 故λ=N(1,0;1,0;4) = 1。

若dim(x1+x2)=4 ，則x1+x2是 一 個(gè)( 4,2)型子空間，(x1+x2)⊥= { 0} ，故λ= 0。

綜上(X,B)是 一個(gè)部分平衡2?(q4+q2,q2;1,0)區(qū)組設(shè)計(jì)。 證畢

定理6B中任意兩個(gè)不同的區(qū)組B1和B2至多與一個(gè)點(diǎn)同時(shí)關(guān)聯(lián)。

證明令B1和B2是B中任意兩個(gè)不同的區(qū)組，則B1和B2為V中兩個(gè)不同的( 1,0)型子空間，且dim(B1+B2)=2 ， 同理B1+B2或 者是一個(gè)( 2,0)型子空間或者是一個(gè)( 2,1)型子空間。

如果B1+B2是 一個(gè)( 2,0)型 子空間，則(B1+B2)⊥是一個(gè)( 2,0)型 子空間，因此δ=N(2,1;2,0;4)=0。

如果B1+B2是一個(gè)( 2,1)型子空間，同樣地(B1+B2)⊥是一個(gè)( 2,1) 型子空間，因此δ=N(2,1;2,1;4)=1。 證畢

由此，本文基于辛空間構(gòu)造了一個(gè)組合設(shè)計(jì)，并計(jì)算了該設(shè)計(jì)的全部參數(shù)。

3.2 基于部分平衡 2?設(shè)計(jì)的密鑰預(yù)分配方案的構(gòu)造

將上述組合設(shè)計(jì)中的點(diǎn)集與密鑰池中的密鑰建立一一對(duì)應(yīng)的關(guān)系，區(qū)組與方案中的節(jié)點(diǎn)建立一一對(duì)應(yīng)的關(guān)系。與每個(gè)區(qū)組相關(guān)聯(lián)的點(diǎn)數(shù)即為每個(gè)節(jié)點(diǎn)所能存儲(chǔ)的最大密鑰量，即密鑰環(huán)的大小。密鑰環(huán)即為與一給定的 ( 1,0) 型 子空間正交的( 2,1)型子空間的個(gè)數(shù)。特別地，基于該設(shè)計(jì)的密鑰預(yù)分配方案中任意兩個(gè)不同的節(jié)點(diǎn)至多有一個(gè)共享密鑰。部分平衡 2?(q4+q2,q2;1,0)設(shè)計(jì)到密鑰預(yù)分配方案的對(duì)應(yīng)關(guān)系如表1所示。

3.3 方案設(shè)計(jì)

將整個(gè)部署區(qū)域劃分為若干個(gè)大小相同的小區(qū)域，Ci表 示網(wǎng)絡(luò)中第i個(gè)小區(qū)，每個(gè)小區(qū)包含普通節(jié)點(diǎn)和簇頭兩種類型的傳感器節(jié)點(diǎn)。每個(gè)小區(qū)內(nèi)的普通節(jié)點(diǎn)均采用基于部分平衡2-設(shè)計(jì)的密鑰預(yù)分配方案，不同小區(qū)內(nèi)節(jié)點(diǎn)所用密鑰池各不相同，因此不同小區(qū)內(nèi)的節(jié)點(diǎn)無法直接通信。簇頭之間采用完全密鑰預(yù)分配方式分發(fā)密鑰，即任意兩個(gè)簇頭之間都有共享密鑰。本方案中簇頭不僅要為同一小區(qū)內(nèi)兩個(gè)沒有共享密鑰的普通節(jié)點(diǎn)建立間接通信，還要為不同小區(qū)內(nèi)需要通信的兩個(gè)節(jié)點(diǎn)建立間接通信。接下來介紹同一小區(qū)內(nèi)普通節(jié)點(diǎn)與簇頭如何通信，不同小區(qū)內(nèi)的簇頭如何通信。

3.3.1 小區(qū)內(nèi)普通節(jié)點(diǎn)與簇頭節(jié)點(diǎn)的通信方式

由于任意兩個(gè)普通節(jié)點(diǎn)至多共享 1個(gè)密鑰，方案的連通概率小于1。為使每個(gè)小區(qū)內(nèi)沒有共享密鑰的兩個(gè)節(jié)點(diǎn)也能通信，考慮利用簇頭作為中間節(jié)點(diǎn)為沒有共享密鑰的兩個(gè)節(jié)點(diǎn)建立間接通信。如何建立簇頭與普通節(jié)點(diǎn)之間的通信是一個(gè)至關(guān)重要的問題。

基本密鑰協(xié)議的主要思想是節(jié)點(diǎn)部署到目標(biāo)區(qū)域之后，需要通信的兩個(gè)節(jié)點(diǎn)通過密鑰協(xié)商的方式建立它們之間的共享密鑰。如節(jié)點(diǎn)Na與其通信范圍內(nèi)的節(jié)點(diǎn)Nb需 要通信時(shí)，Na從密鑰列表中隨機(jī)選擇一個(gè)密鑰ki廣 播，節(jié)點(diǎn)Nb接 收到ki后隨機(jī)產(chǎn)生一個(gè)密鑰kij，隨后將密鑰kij和其身份標(biāo)識(shí)符j用ki加密之后再發(fā)送給Na。節(jié)點(diǎn)Na將傳回的信息用ki解 密之后就可得到它們之間的共享密鑰kij以及身份標(biāo)識(shí)信息。這樣節(jié)點(diǎn)Na和Nb就協(xié)商了一個(gè)密鑰。

本文方案中每個(gè)小區(qū)內(nèi)的普通節(jié)點(diǎn)和簇頭之間的通信采用基本密鑰協(xié)議。具體方法如下：在節(jié)點(diǎn)部署前預(yù)先為每個(gè)簇頭存儲(chǔ)Fq(8)V中的一個(gè)1 維子空間，當(dāng)同一小區(qū)內(nèi)的普通節(jié)點(diǎn)和簇頭需要通信時(shí)，這個(gè)普通節(jié)點(diǎn)從密鑰列表中隨機(jī)產(chǎn)生一個(gè)密鑰ki并廣播給簇頭。由3.2節(jié)知，每個(gè)密鑰與V中一個(gè)1 維子空間對(duì)應(yīng)，于是簇頭利用ki和 預(yù)先存儲(chǔ)的1 維子空間生成一個(gè)2維子空間，生成的這個(gè)子空間就作為普通節(jié)點(diǎn)和簇頭的共享密鑰，記為kij。密鑰kij使用ki加密之后再發(fā)送給這個(gè)普通節(jié)點(diǎn)，這樣普通節(jié)點(diǎn)與簇頭就可相互通信。

3.3.2 不同小區(qū)內(nèi)簇頭間的通信方式

每個(gè)小區(qū)內(nèi)放置3個(gè)簇頭，且3個(gè)簇頭所用密鑰池各不相同。依據(jù)所用密鑰池的不同，簇頭可分為3類，同類簇頭可相互通信，不同類型的簇頭無法通信。每個(gè)小區(qū)內(nèi)的簇頭用 C Hij表示，其中i表示網(wǎng)絡(luò)中第i個(gè) 小區(qū)，j表示簇頭的類型。例如C H11,CH12和C H13分別表示網(wǎng)絡(luò)中第1個(gè)小區(qū)內(nèi)的3種類型的簇頭。假設(shè)目標(biāo)區(qū)域被劃分為N個(gè)小區(qū)，則1≤i ≤N, 1≤j ≤3，不同小區(qū)內(nèi)同一類型的簇頭

2 ?(q4+q2,q2;1,0)部分平衡 區(qū)組設(shè)計(jì) 密鑰預(yù)分配方案v =|X|=N(2,1;4)=q4+q2 密鑰池大小b=|B|=N(1,0;4)=q3+q2+q+1 方案所能支持的最大傳感器節(jié)點(diǎn)數(shù)目k =|X(B)|=N(2,1;3,1;4)=q2 密鑰環(huán)大小r =|B(x)|=N(1,0;2,1;4)=q+1 包含一給定密鑰的節(jié)點(diǎn)數(shù)目δ =0或1 任意兩個(gè)節(jié)點(diǎn)共享的密鑰量

表 1 部分平衡2?(q4+q2,q2;1,0)設(shè)計(jì)到密鑰預(yù)分配方案的對(duì)應(yīng)關(guān)系采用完全密鑰預(yù)分配方式分發(fā)密鑰，所謂完全密鑰預(yù)分配即為每個(gè)簇頭存儲(chǔ)N?1個(gè) 密鑰，這N?1個(gè)密鑰恰好為這個(gè)簇頭分別與其他N ?1個(gè)小區(qū)內(nèi)同類簇頭的共享密鑰。這樣任意兩個(gè)同類簇頭均有共享密鑰，簇頭之間的連通概率為1。但隨著小區(qū)數(shù)量增加，簇頭存儲(chǔ)的密鑰數(shù)越來越多，對(duì)簇頭的存儲(chǔ)要求會(huì)越來越高。

基于上述考慮將每個(gè)小區(qū)的通信范圍限制在其Lee球體[15]區(qū)域內(nèi)。Lee距離為ρ的Lee球體是由所有與選定小區(qū)距離不超過ρ的小區(qū)組成的。任意兩個(gè)小區(qū)之間的距離為這兩個(gè)小區(qū)的水平距離和垂直距離之和。因此以Ci為 中心的Lee距離為ρ的Lee球體中有2ρ(ρ+1)個(gè) 小區(qū)(除Ci)，故小區(qū)內(nèi)每種類型的簇頭只需存儲(chǔ)2ρ(ρ+1)個(gè)密鑰。此時(shí)每個(gè)簇頭存儲(chǔ)的密鑰量遠(yuǎn)少于未限制小區(qū)通信范圍之前所需存儲(chǔ)的密鑰量。例如當(dāng)目標(biāo)區(qū)域被劃分為 9個(gè)小區(qū)，且Lee距離為1時(shí)，圖1實(shí)線區(qū)域?yàn)镃5的Lee距離為1的Lee球體區(qū)域。

圖1 ρ = 1 時(shí)C 5的Lee球體區(qū)域

4 分析

4.1 小區(qū)內(nèi)的連通概率

雖然這個(gè)方案的連通概率沒有達(dá)到1，但是隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，連通概率逐漸趨于1。

4.2 損失概率的估算

網(wǎng)絡(luò)中的節(jié)點(diǎn)易受敵方攻擊，當(dāng)一個(gè)節(jié)點(diǎn)被敵方捕獲時(shí)，該節(jié)點(diǎn)內(nèi)的所有密鑰均被泄露。損失概率反映了網(wǎng)絡(luò)中節(jié)點(diǎn)的抗捕獲能力，損失概率越低，節(jié)點(diǎn)的抗捕獲能力越強(qiáng)。網(wǎng)絡(luò)的損失概率分為局部損失概率和全局損失概率。局部損失概率指一個(gè)小區(qū)內(nèi)S個(gè)普通節(jié)點(diǎn)被捕后，任意兩個(gè)未被捕獲的普通節(jié)點(diǎn)之間鏈接斷開的概率。全局損失概率指S′個(gè)簇頭被捕后，任意兩個(gè)小區(qū)之間的鏈接被斷開的概率。

4.2.1 局部損失概率

對(duì)于任意一對(duì)給定的節(jié)點(diǎn)Na和Nb，假設(shè)它們之間有一個(gè)共享密鑰k。由于密鑰k存儲(chǔ)在r個(gè)節(jié)點(diǎn)中，捕獲除Na和Nb外 其余r?2個(gè)節(jié)點(diǎn)中的任意一個(gè)都會(huì)使密鑰k泄露，此時(shí)節(jié)點(diǎn)Na和Nb之間的鏈接被破壞。 fail(1)為隨機(jī)捕獲一個(gè)節(jié)點(diǎn)，使得節(jié)點(diǎn)Na和Nb之間的鏈接被破壞的概率。于是

圖2為不同網(wǎng)絡(luò)規(guī)模下(q取不同值時(shí))，隨著捕獲的節(jié)點(diǎn)數(shù)量逐漸增多，網(wǎng)絡(luò)的損失概率逐漸增大。且捕獲相同數(shù)量的節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)規(guī)模越大，損失概率越小。

圖2 損失概率圖

假設(shè)一共有S個(gè)普通節(jié)點(diǎn)被捕獲，當(dāng)目標(biāo)區(qū)域被劃分為N個(gè)小區(qū)時(shí)，平均每個(gè)小區(qū)內(nèi)有S/N個(gè)普通節(jié)點(diǎn)被捕獲，于是局部損失概率大致估算為

由表2可知，當(dāng)捕獲節(jié)點(diǎn)數(shù)量較多時(shí)，網(wǎng)絡(luò)中的節(jié)點(diǎn)仍然具有良好的抗捕獲能力。這表明將整個(gè)目標(biāo)區(qū)域分為若干小區(qū)的方法極大地提高了網(wǎng)絡(luò)中節(jié)點(diǎn)的抗捕獲能力。

表2 當(dāng)q =4 , q =5 , q =7 , q =8時(shí)的局部損失概率

4.2.2 全局損失概率

同Kumar等人[6]一樣將小區(qū)之間的鏈接稱為主鏈接，簇頭之間的鏈接稱為2次鏈接。若Ci和Cj是兩個(gè)不同的小區(qū)，則Ci和Cj之間存在一條主鏈接。假設(shè)Ci1,Ci2和Ci3是Ci中 的3個(gè)簇頭，Cj1,Cj2,Cj3是Cj中的3個(gè)簇頭。此時(shí)有3條2次鏈接，分別為Ci1和Cj1,Cj2和Cj2,Ci3和Cj3。顯然2次鏈接的數(shù)量是主鏈接的3倍。在估算全局損失概率時(shí)只考慮當(dāng)S′個(gè)簇頭被捕時(shí)主鏈接的斷開情況，全局損失概率數(shù)學(xué)表達(dá)式為

事畢，我側(cè)臥在沙發(fā)上，看見月亮高高地掛在客廳落地窗的上方，地板上那片朦朧的金色月光被玻璃拉門的對(duì)扇隔檔切為兩半。

當(dāng)把每個(gè)小區(qū)的通信范圍限制在其Lee球體區(qū)域內(nèi)時(shí)，靠近部署邊界的小區(qū)的Lee球體區(qū)域內(nèi)所包含的小區(qū)數(shù)量減少，1個(gè)小區(qū)至多關(guān)聯(lián)2ρ(ρ+1)條主鏈接。所以整個(gè)網(wǎng)絡(luò)中至多有Nρ(ρ+1)條主鏈接。事實(shí)上，1條主鏈接斷開當(dāng)且僅當(dāng)這兩個(gè)小區(qū)內(nèi)的3條2次鏈接都要斷開，且捕獲一個(gè)簇頭時(shí)至多有 2ρ(ρ+1)條 2次鏈接斷開。當(dāng)S′個(gè)簇頭被捕時(shí)，可分為下列3種情況：

(1)捕獲的S′個(gè)簇頭中只包含其中1種類型的簇頭，則有2S′ρ(ρ+1)條2次鏈接斷開。

(2)捕獲的S′個(gè)簇頭中僅包含其中2種類型的簇頭，若類型1簇頭有X個(gè)，則有2Xρ(ρ+1)+2ρ(S′?X)(ρ+1)條2次鏈接斷開。

(3)捕獲的這S′個(gè)簇頭中包含3種類型的簇頭，假設(shè)類型1簇頭有X個(gè)，類型2簇頭有Y個(gè)，此時(shí)有2Xρ(ρ+1)+2Y ρ(ρ+1)+2ρ(S′?X ?Y)(ρ+1)條2次鏈接斷開。

只有在第3種情況發(fā)生時(shí)，才有可能將兩個(gè)小區(qū)間的3條2次鏈接都斷開，才有可能斷開1條主鏈接。實(shí)際中無法確定捕獲的簇頭包含幾種類型及每種類型的簇頭被捕獲的數(shù)量，因此無法得到全局損失概率的理論值。但依據(jù)簇頭所采用的密鑰預(yù)分配方案，未被捕獲的簇頭之間的鏈接不會(huì)被斷開，故簇頭之間的損失概率是極小的。

4.3 節(jié)點(diǎn)斷開的估算

當(dāng)捕獲的節(jié)點(diǎn)數(shù)量足夠多時(shí)，存在未被捕獲的節(jié)點(diǎn)所含密鑰泄露的情況。此時(shí)該節(jié)點(diǎn)不能再使用， 這類節(jié)點(diǎn)稱為從網(wǎng)絡(luò)中斷開的節(jié)點(diǎn)。考慮至少捕獲多少普通節(jié)點(diǎn)才能從網(wǎng)絡(luò)中斷開一個(gè)未被捕獲的普通節(jié)點(diǎn)。

因?yàn)槊總€(gè)節(jié)點(diǎn)都存儲(chǔ)q2個(gè)密鑰，并且任意兩個(gè)普通節(jié)點(diǎn)至多共享一個(gè)密鑰，因此至少要捕獲q2個(gè)節(jié)點(diǎn)才可能斷開小區(qū)內(nèi)的一個(gè)普通節(jié)點(diǎn)。若整個(gè)網(wǎng)絡(luò)中一共有K個(gè)普通節(jié)點(diǎn)被捕獲，平均每個(gè)小區(qū)捕獲K/N，因此需要滿足K/N ≥q2， 即K≥Nq2。

例如當(dāng)q= 5時(shí) ，網(wǎng)絡(luò)被劃分為9 00個(gè)小區(qū)，則每個(gè)小區(qū)有1 56 個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有2 5個(gè)密鑰。為了斷開一個(gè)未捕獲的節(jié)點(diǎn)至少需要捕獲22500個(gè)節(jié)點(diǎn)。實(shí)際上，這是一個(gè)非常大的數(shù)，因此很難將一個(gè)節(jié)點(diǎn)從網(wǎng)絡(luò)中斷開。

由于簇頭采用完全密鑰預(yù)分配方式分配密鑰，因此無論捕獲多少簇頭都不會(huì)使得未被捕獲的簇頭從網(wǎng)絡(luò)中斷開。

5 與一些其他方案的比較

本節(jié)將本文方案與一些其它方案就連通概率、局部損失概率進(jìn)行比較。因方案設(shè)計(jì)上的差異，有些方案(除Kumar方案外)并沒有區(qū)分局部損失概率和全局損失概率，因此比較時(shí)將我們方案的局部損失概率和其他方案的損失概率進(jìn)行比較。圖3和圖4分別為連通概率和損失概率對(duì)比圖，表3給出各個(gè)方案的參數(shù)。表4為符號(hào)表。

表3 各個(gè)方案的參數(shù)

表4 符號(hào)表

圖3 連通概率對(duì)比圖

Pei等人[3]基于有限域上有理正規(guī)曲線構(gòu)造了一個(gè)密鑰預(yù)分配方案，記為RNC。將射影空間PG(n,Fq)中 的點(diǎn)看作區(qū)組設(shè)計(jì)中的點(diǎn)集，PG(n,Fq)中所有有理正規(guī)曲線作為區(qū)組集構(gòu)造了一個(gè)強(qiáng)部分平衡設(shè)計(jì)。當(dāng)n= 2時(shí)，基于該設(shè)計(jì)下的密鑰預(yù)分配方案具有良好性能。該方案的連通性隨著密鑰環(huán)的增大而逐漸下降，連通概率劣于本文方案，且隨著節(jié)點(diǎn)捕獲數(shù)量的增加，損失概率逐漸趨于1，遠(yuǎn)高于我們方案的損失概率。

Kumar等人[6]利用對(duì)稱設(shè)計(jì)構(gòu)造了一個(gè)密鑰預(yù)分配方案，也將部署區(qū)域劃分為若干個(gè)大小相同的小區(qū)。雖然方案的連通概率恒為1，優(yōu)于我們的方案，但由圖4可知捕獲相同數(shù)量的普通節(jié)點(diǎn)時(shí)，該方案的局部損失概率高于我們方案的局部損失概率。且由于該方案簇頭之間采用基于對(duì)稱設(shè)計(jì)的密鑰預(yù)分配方案，因此當(dāng)捕獲足夠多的簇頭時(shí)存在未被捕獲的簇頭從網(wǎng)絡(luò)中斷開的情況，而本文方案無論捕獲多少簇頭均不會(huì)有這種情況。

Bechkit等人[16]基于一種組合設(shè)計(jì)構(gòu)造了一個(gè)密鑰預(yù)分配方案，記作NU-KP。由于該方案連通概率較低。于是為了提高方案的連通概率作者將該方案修改進(jìn)一步提出方案t-UKP。在與t-UKP比較中取t=2。從圖3和圖4可看到，這兩個(gè)方案的連通概率以及節(jié)點(diǎn)的抗捕獲能力均不及本文方案。

圖4 損失概率對(duì)比圖

袁琪等人[8]基于3維空間構(gòu)造w-平衡不完全區(qū)組設(shè)計(jì)，并基于該設(shè)計(jì)構(gòu)造了密鑰預(yù)分配方案，記作Ex-w-BIBD。該方案連通概率較差，且損失概率也遠(yuǎn)高于本文方案的損失概率，方案的各個(gè)性能較差。

Ruj等人[17]提出了成對(duì)和三重密鑰分配，該方案記作TKP。該方案中密鑰鏈大小為k，且4≤k≤q。 方案所能支持的最大傳感器數(shù)目為2q2。雖然該方案的損失概率較低，但仍然高于我們方案的損失概率，且該方案網(wǎng)絡(luò)的連通性較差，遠(yuǎn)低于本文方案的局部連通概率。

圖3為本文方案與其他幾個(gè)方案在密鑰環(huán)大小相近時(shí)，方案的連通概率對(duì)比圖。其中各個(gè)方案的密鑰環(huán)大小在4,9,16,25,49,64,81,121,169,256,289這些值上下輕微波動(dòng)。圖4為網(wǎng)絡(luò)規(guī)模相近時(shí)，本文方案與其他幾個(gè)方案在捕獲相同節(jié)點(diǎn)數(shù)時(shí)，方案的局部損失概率對(duì)比圖。特別地，RNC中q=4，NU-KP中q=5 ，2-UKP中q=7，Kumar方案中q=9 ，Ex-w-BIBD中q=8 ，以及TKP中q=23。從中可看到本文方案在連通概率逐漸趨于 1時(shí)還能保證較低的損失的概率。

6 結(jié)束語

本文基于有限域上辛空間中子空間之間的正交關(guān)系構(gòu)造了一個(gè)新的組合設(shè)計(jì)。將目標(biāo)區(qū)域劃分為若干個(gè)大小相同的小區(qū)，每個(gè)小區(qū)有普通節(jié)點(diǎn)和簇頭兩種傳感器節(jié)點(diǎn)。同一小區(qū)內(nèi)的節(jié)點(diǎn)采用基于有限域上辛空間構(gòu)造的密鑰預(yù)分配方案來分配密鑰，小區(qū)內(nèi)的節(jié)點(diǎn)或者通過共享密鑰直接通信，或者通過簇頭間接通信。簇頭之間采用完全密鑰預(yù)分配方式分配密鑰，不同小區(qū)內(nèi)的節(jié)點(diǎn)必須通過簇頭建立通信。

與其他方案相比本文方案既降低了網(wǎng)絡(luò)的損失概率，又保證了在網(wǎng)絡(luò)規(guī)模逐漸增大時(shí)網(wǎng)絡(luò)的連通概率逐漸趨于1，即并沒有以嚴(yán)重犧牲網(wǎng)絡(luò)的連通概率來提高節(jié)點(diǎn)的抗捕獲能力。此外將網(wǎng)絡(luò)分區(qū)的方法也有效地提高了網(wǎng)絡(luò)中節(jié)點(diǎn)的抗捕獲能力，并降低了對(duì)方案中所能支持的最大傳感器數(shù)目的要求。但本方案仍有不足之處，與其他方案相比相同規(guī)模下本文方案中每個(gè)節(jié)點(diǎn)存儲(chǔ)的密鑰量較多，需要進(jìn)一步研究和改進(jìn)。