基于組合設(shè)計(jì)框架的無(wú)線傳感器網(wǎng)絡(luò)密鑰預(yù)分配方案

吳苗苗，張勇，曹瑞峰

（鹽城師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，江蘇鹽城224002）

基于組合設(shè)計(jì)框架的無(wú)線傳感器網(wǎng)絡(luò)密鑰預(yù)分配方案

吳苗苗，張勇*，曹瑞峰

（鹽城師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，江蘇鹽城224002）

本文研究了基于超單純平衡不完全區(qū)組設(shè)計(jì)的無(wú)線傳感器網(wǎng)絡(luò)的密鑰預(yù)分配方案。主要采用了基于部分平衡t設(shè)計(jì)的組合研究框架，運(yùn)用matlab仿真方法對(duì)該方案的基本度量進(jìn)行計(jì)算和分析，發(fā)現(xiàn)該方案與基于指數(shù)為1的平衡不完全區(qū)組設(shè)計(jì)的方案相比，保持了連通性，適當(dāng)犧牲了彈性，但獲得了更大的實(shí)用性。

無(wú)線傳感器網(wǎng)絡(luò)；密鑰預(yù)分配方案；部分平衡t設(shè)計(jì)；BIBD

無(wú)線傳感器網(wǎng)絡(luò)是由若干個(gè)具有有限存儲(chǔ)能力、有限能量和有限計(jì)算能力的小的傳感器節(jié)點(diǎn)組成的自適應(yīng)網(wǎng)絡(luò)。節(jié)點(diǎn)間能夠彼此通信來(lái)積累信息，并以安全的方式將其傳遞給基站。由于這種通信通常發(fā)生在敵對(duì)區(qū)里，因此需要對(duì)信息進(jìn)行加密或認(rèn)證。公鑰密碼方案由于其計(jì)算量大以及昂貴的計(jì)算成本，因此不適宜作為加密方案。通常采用密鑰預(yù)分配方案(KPS)，即在節(jié)點(diǎn)分發(fā)前將安全密鑰預(yù)先安裝在每個(gè)傳感器節(jié)點(diǎn)上。影響KPS的主要因素(基本度量)有網(wǎng)絡(luò)規(guī)模、存儲(chǔ)要求、網(wǎng)絡(luò)連通性和網(wǎng)絡(luò)彈性。設(shè)計(jì)一個(gè)好的KPS方案的根本問(wèn)題是如何平衡上述指標(biāo)。

現(xiàn)有基于組合設(shè)計(jì)的KPS方案[1-3]中，Paters on和Stinson引入了部分平衡t設(shè)計(jì)的概念，建立了無(wú)線傳感器網(wǎng)絡(luò)的密鑰預(yù)分配方案的組合研究框架[1]。指數(shù)為1的平衡不完全區(qū)組設(shè)計(jì)(BIBD)[4]作為部分平衡2設(shè)計(jì)有較好的彈性和連通性，但指數(shù)的限制使其在實(shí)際使用中有一定局限性。超單純BIBD是一類指數(shù)大于1且無(wú)重復(fù)區(qū)組的設(shè)計(jì)，因?yàn)樗c相同參數(shù)的一般平衡不完全區(qū)組設(shè)計(jì)相比，能使被區(qū)組覆蓋的三元組的個(gè)數(shù)盡可能大，所以本身有重要的理論價(jià)值，同時(shí)它在編碼和密碼中有重要應(yīng)用。本文提出用超單純BIBD構(gòu)造KPS方案，并分析其性能。

1 基于區(qū)組設(shè)計(jì)的KPS方案

一個(gè)組合設(shè)計(jì)(或稱為區(qū)組設(shè)計(jì))是一個(gè)二元組（X，H），其中X為有限點(diǎn)集，H是X的子集族，稱為區(qū)組集，稱為A∈H區(qū)組，其所含元素個(gè)數(shù)稱為區(qū)組長(zhǎng)度。若所有區(qū)組的長(zhǎng)度是定值k，則稱（X，H）是k階一致的。對(duì)于x∈X，包含x的區(qū)組數(shù)稱為x的次數(shù)。若所有點(diǎn)的次數(shù)是定值r，則稱（X，H）是r次正則的。

如果一個(gè)傳感器網(wǎng)絡(luò)由b個(gè)傳感器節(jié)點(diǎn)U1，…，Ub和v個(gè)密鑰key1，…，keyv組成，那么可采用區(qū)組設(shè)計(jì)（X，H），X={xi∶1≤i≤v}，H={Aj∶1≤j≤b}。節(jié)點(diǎn)Uj（1≤j≤b）接收密鑰子集{keyi∶xi∈Aj}中的密鑰，xi充當(dāng)keyi的身份標(biāo)識(shí)，這樣就建立了一個(gè)基于區(qū)組設(shè)計(jì)的KPS方案。并非所有的區(qū)組設(shè)計(jì)都可用作KPS方案，能用作KPS方案的區(qū)組設(shè)計(jì)被稱為部分平衡t設(shè)計(jì)。

2 部分平衡t設(shè)計(jì)及其度量

定義1[1]令v，k，t是正整數(shù)，λ0，λ1，…，λt-1也是正整數(shù)。設(shè)（X，H）是v元集X上的一個(gè)含有λ0個(gè)區(qū)組的k階一致的區(qū)組設(shè)計(jì)，稱（X，H）為t-（v,k,λ0，…，λt-1）部分平衡t設(shè)計(jì)(PB t D)，如果滿足：

(1)對(duì)于1≤i≤t-1，每個(gè)i子集出現(xiàn)在0個(gè)區(qū)組或者λi個(gè)區(qū)組中；

(2)對(duì)于t≤i≤k，每個(gè)i子集出現(xiàn)在0個(gè)或1個(gè)區(qū)組中。

網(wǎng)絡(luò)連通性和彈性通常分別記為Pr1和fail(1)。

引理1[1]對(duì)給定的無(wú)線傳感器網(wǎng)絡(luò)，若采用相交門(mén)限為η的t-（v，k，λ0，…，λt-1）-PB t D作為KPS方案，則有

在基于PB t D的KPS方案的框架下可以方便地引入基于超單純BIBD的KPS方案。

3 基于超單純BIBD的KPS方案

設(shè)有v元集X上的一個(gè)含有b個(gè)區(qū)組的r次正則的k階一致的區(qū)組設(shè)計(jì)（X，H），若X中每一對(duì)不同的元素恰好在H的λ個(gè)區(qū)組中相遇，則稱（X，H）是一個(gè)（v，k，λ）平衡不完全區(qū)組設(shè)計(jì)，簡(jiǎn)記為（v，k，λ）-BIBD。容易看出，（v，k，1）-BIBD是部分平衡2設(shè)計(jì)(PB2D)，因此（v，k，1）-BIBD可以用作KPS方案。但是，當(dāng)λ＞1時(shí)，一個(gè)（v，k，λ）-BIBD未必是一個(gè)PB t D。例如，將一個(gè)（v，k，1）-BIBD的所有區(qū)組重復(fù)1次，得到一個(gè)（v，k，2）-BIBD，這就不是一個(gè)PB t D。因此，已有的相關(guān)方案都限定λ=1[1-3]。但是，并不是對(duì)任意節(jié)點(diǎn)的傳感器網(wǎng)絡(luò)都存在一個(gè)區(qū)組數(shù)等于網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的（v，k，1）-BIBD，所以需要研究指數(shù)大于1的BIBD作為KPS方案。

如果區(qū)組集中沒(méi)有重復(fù)區(qū)組，一個(gè)（v，k，λ）-BIBD稱為單純的；如果區(qū)組集中任意兩個(gè)區(qū)組至多相交于兩個(gè)公共點(diǎn)，則稱為超單純的。超單純（v，k，λ）-BIBD記為（v，k，λ）-SSBIBD。當(dāng)k=3時(shí)，單純?cè)O(shè)計(jì)也是超單純；λ=1的設(shè)計(jì)一定是超單純?cè)O(shè)計(jì)。本文僅涉及k=4的超單純?cè)O(shè)計(jì)。對(duì)于（v，4，λ）-SSBIBD，其參數(shù)滿足vr=4b以及3r=λ（v-1），因此由引理1得如下定理。

定理1對(duì)于基于（v，4，λ）-SSBIBD的KPS方案，Pr1和fail(1)為

對(duì)于一個(gè)（v，k，λ）-BIBD，（X，H），取X為Zv，即模v的剩余類環(huán)，則σ∶i→i+1（mod v）是Zv上的一個(gè)置換。如果v整除b，且在H中存在b/v個(gè)區(qū)組，在σ的作用下可得到所有區(qū)組，稱（X，H）是循環(huán)的，記為（v，k，λ）-CBIBD，b/v個(gè)區(qū)組稱為基區(qū)組。超單純（v，k，λ）-CBIBD簡(jiǎn)記為（v，k，λ）-SSCBIBD。

分別以相遇數(shù)為1，2和4的SSCBIBD為例說(shuō)明SSBIBD的度量，后面將以這些例子為基礎(chǔ)分析一般的SSBIBD的性能。

例1(13,4,1)-SSCBIBD如表1。

表1 (13,4,1)-SSBIBD

這里v=13，k=4。將基區(qū)組模加1展開(kāi)后得所有13個(gè)區(qū)組，所以b=λ0=13。計(jì)算得r=λ1=4，λ=λ2=1。根據(jù)定義，這是一個(gè)2-（13，4，13，4）-PB2D。由定理1得

例2(13,4,2)-SSCBIBD如表2。

表2 (13,4,2)-SSBIBD

這里v=13，k=4。將基區(qū)組模加1展開(kāi)后得所有26個(gè)區(qū)組，所以b=λ0=26。計(jì)算得，

根據(jù)定義，這是一個(gè)3-（13，4，26，8，2）部分平衡3設(shè)計(jì)(PB3D)。由定理1得

例3(10,4,4)-SSCBIBD如表3。

表3 (10,4,4)-SSBIBD

這里v=10，k=4。將基區(qū)組模加1展開(kāi)后得所有30個(gè)區(qū)組，所以b=λ0=30。計(jì)算得，

根據(jù)定義，這是一個(gè)3-（10，4，30，12，4）-PB3D設(shè)計(jì)。由定理1得

4 方案的性能分析

首先，關(guān)于連通性，對(duì)于（v，4，λ）-BIBD而言，由定理1知Pr1恒為1，所以基于超單純BIBD的KPS方案保持了連通性。

其次，關(guān)于彈性，運(yùn)用Matlab軟件畫(huà)圖，以區(qū)組數(shù)b為自變量，fail（1）為因變量，（v，4，1）-BIBD與（v，4，2）-SSBIBD的fail（1）的對(duì)比見(jiàn)圖1。

圖1 fail(1)對(duì)比圖，指數(shù)為1和2

圖1 表明，隨著區(qū)組數(shù)的增加，（v，4，2）-SSBIBD比（v，4，1）-BIBD的彈性稍低，但非常接近。

（v，4，2）-SSBIBD與（v，4，4）-SSBIBD的fail(1)的對(duì)比如圖2。從圖中看出，隨著區(qū)組數(shù)的增加，（v，4，2）-SSBIBD比（v，4，4）-SSBIBD的彈性稍好，但非常接近。

圖2 fail(1)對(duì)比圖，指數(shù)為2和4

以節(jié)點(diǎn)數(shù)v為自變量，fail（1）為因變量，（v，4，2）-SSBIBD與（v，4，4）-SSBIBD的fail（1）比較見(jiàn)圖3。

圖3 （v,4,2）-SSBIBD與（v,4,4）-SSBIBD的fail（1）對(duì)比圖

從圖3看出，隨著節(jié)點(diǎn)個(gè)數(shù)的增加，（v，4，2）-SSBIBD比（v，4，4）-SSBIBD的彈性稍好，但非常接近。

在彈性性能方面，從上述幾個(gè)例子的計(jì)算結(jié)果以及圖像來(lái)看，隨著λ的增大，fail（1）的值逐漸增加，彈性有所降低但非常接近，與其他設(shè)計(jì)的結(jié)果差距較小。

最后，要指出基于SSBIBD的KPS方案具有更大的實(shí)用性。例如，（v，4，1）-BIBD存在的條件是v≡1,4（mod12），而（v，4，2）-SSBIBD和（v，4，4）-SSBIBD存在的條件是v≡1（mod 3），而（v，4，6）-SSBIBD存在的條件是v是不小于14的整數(shù)，所以超單純?cè)O(shè)計(jì)使得無(wú)線傳感器網(wǎng)絡(luò)的密鑰數(shù)目v選擇更為自由。同樣，超單純?cè)O(shè)計(jì)也使得傳感器的節(jié)點(diǎn)數(shù)目b的選擇更為自由。因此，基于超單純平衡不完全區(qū)組設(shè)計(jì)的KPS方案更為實(shí)用。

5 SSBIBD的存在性

以（v，4，λ）-SSBIBD為例，說(shuō)明存在為數(shù)眾多的SSBIBD，從而說(shuō)明基于SSBIBD的KPS方案更具有實(shí)用性。對(duì)于任意k，λ必要條件也是漸進(jìn)充分的[5]。對(duì)于（v，4，λ）-SSBIBD，當(dāng)λ=2，3,4,5,6,8,9時(shí)，一個(gè)（v，4，λ）-SSBIBD存在的必要條件也是充分的[2,6-15]。

命題1[2,5-15]對(duì)于λ=2,3,4,5,6,8,9,當(dāng)且僅當(dāng)v和λ滿足表4中所列的條件時(shí)存在一個(gè)（v，4，λ）-SSBIBD。

表4 （v，4，λ）-SSBIBD存在的條件

命題2[15]對(duì)λ=2,3,4于,當(dāng)且僅當(dāng)v和λ滿足表5所列條件時(shí)存在一個(gè)超單純（v，4，λ）-SSCBIBD。

表5 （v，4，λ）-SSCBIBD存在的條件

更多結(jié)果請(qǐng)參考文獻(xiàn)[4]及相關(guān)文獻(xiàn)。

6 總結(jié)

總之，使用超單純BIBD的無(wú)線傳感器網(wǎng)絡(luò)的KPS方案與基于λ=1的BIBD的KPS方案相比，保持了原有的連通性，適當(dāng)?shù)臓奚藦椥裕瑫r(shí)換來(lái)了更大的實(shí)用性。文章還舉例說(shuō)明了存在大量的SSBIBD，這在使用上是很方便的，該方案豐富了基于區(qū)組設(shè)計(jì)的KPS方案理論。

[1]PATERSON M B,STINSON D R.A unified approach to combinatorial key predistribution schemes for sensor networks[J]. Designs,Codesand Cryptography,2014（3）：433-457.

[2]LEE J,STINSON D R.On the construction of practical key predistribution schemes for distributed sensor networks using combinatorial designs[J].ACM Transactions on Information and System Security,2008,11(2):1-35.

[3]DENG W,DU J,HAN Y,et al.A pairwise key predistribution scheme forwireless sensor networks[J]．ACM Transactions on Information and System Security,2005，8:228-258.

[4]COLBOURNC J,DINITZ JH.Handbook of combinatorial designs [M].2nd Edition.Boca Raton:Chapman and Hall/CRC,2007.

[5]GRONAU H D O F,MULLIN R C.On super-simple 2-(v,4,λ) designs[J].JournalofCombinatorialMathematicsand Combinatorial Computing,1992，11:113-121.

[6]KHODKAR A.Various super-simple designswith block size four [J].The Australasian Journalof Combinatorics,1994，9:201-210.

[7]BLUSKOV I,HEINRICH K.Super-simple designswith v<=32[J]. JournalofStatisticsand Planning Inference,2001，95:121-131.

[8]CHEN K.On the existence of super-simple(v,4,3)-BIBDs[J]. Journal of Combinatorial Mathematics and Combinatorial Computing，1995，17:149-159.

[9]CHEN K.On the existence of super-simple(v,4,4)-BIBDs[J]. Journalof Statisticsand Planning Inference，1996，51:339-350.

[10]CHEN K,CAO Z,WEIR.Super-simple balanced incomplete block designswith block size4 and index 6[J].Journalof Statistics and Planning Inference，2005，133：537-554.

[11]CHEN K,WEIR.Super-simple cyclic designswith small values [J].Journal of Statistics and Planning Inference，2007，137：2034-2044.

[12]CAO H,CHEN K,Wei R.Super-simp le balanced incomp lete block designs with block size 4 and index 5[J].Discrete Mathematics，2009，309：2808-2814.

[13]ZHANG Y,CHEN K,SUN Y G.Super-simp le balanced incompleteblock designswith block size4 and index9[J].Journal of Statisticsand Planning Inference，2009，3139：3612-3624.

[14]CHEN K,SUN Y G，ZHANG Y.Super-simple balanced incomplete block designs with block size 4 and index 8[J]. UtilitasMathematics，2013，91：213-229.

[15]周海萍,曹海濤.超單嚴(yán)格循環(huán)設(shè)計(jì)的一些結(jié)果[J].數(shù)學(xué)年刊A輯（中文版），2010（4）：427-442.

Key Predistribution forWirelessWensor NetworksBased on a Classof Combinatorial Design

WU Miao-miao，ZHANG Yong，CAO Rui-feng
(School of Mathematics and Statistics，Yancheng Teachers University，Yancheng，Jiangsu 224002，China)

The paper studies the key predistribution schemes of the wireless sensor networks based on super simple balanced incomplete block design.The combinatorial frame is adoped，which is established based on partially balanced tdesign.MATLAB simulation analysis and computation of the basic metric of this scheme,prove that the schememaintains the original connectivity,slightly sacrifice the flexibility but in exchange for greater practicality compared with KPS based on balanced incomplete block design which index is equal to 1.

wireless sensor networks；key predistribution scheme；partially balanced t-design；BIBD

O157.2

A

1007-4260(2016)04-0053-04

時(shí)間：2017-1-3 17:19

http://www.cnki.net/kcms/detail/34.1150.N.20170103.1719.015.html

2016-04-28

江蘇省高等學(xué)校大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項(xiàng)目（201410324039Y，201410324058X）。

吳苗苗，女，江蘇連云港人，鹽城師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院碩士研究生，研究方向?yàn)閭鞲衅骶W(wǎng)絡(luò)。

E-mail:1125098835@qq.com

張勇，男，江蘇鹽城人，博士，鹽城師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院副教授，研究方向?yàn)榻M合設(shè)計(jì)。E-mail:zyyctu@gmail.com

10.13757/j.cnki.cn34-1150/n.2016.04.015