随着无线传感网技术的不断成熟，其应用越来越广泛^[1]. 不同的应用环境对网络的安全需求不同^[2]，网络安全的核心问题是密钥管理^[3]，而密钥管理中最基础、最广泛的研究内容是密钥预分配（key pre-distribution，KPD）问题^[4-11]. 密钥预分配为传感网提供了安全的初始化环境，为无线传感网其他安全服务如身份认证^[12-13]提供了基本保障.

Camtepe等^[14]将组合设计中的对称平衡不完全区组设计（symmetric balanced incomplete block design，sBIBD）映射到密钥预分配中，实现了第一个确定性密钥预分配方案，从此以后，组合设计作为确定性密钥管理中的重要研究方向，引起了广大学者的关注^[15-20]. Bechkit等^[10]利用unital设计理论，将unital映射到密钥预分配方案中，使得网络可扩展性和密钥共享概率不低于 $1 - {{\rm {e}}^{ - 1}} \approx 0.632$ . Lee等^[15]完成了线性和二次型2种类型的横截区组设计（transversal design，TD），实现了基于横截设计的KPD方案；该方案提高了共享密钥发现和路径密钥建立的效率，实现更加简单. Modiri等^[17]第一次使用剩余设计理论，实现了无线传感网的密钥预分配，利用该方案极大地提高了网络的扩展性和密钥连通性. 马春光等^[18]提出的中心可分解型按对平衡设计中，将普通区组作为簇节点的密钥环，特殊区组作为簇头节点的密钥环，构造了层簇结构的传感网KPD方案.

密钥连通性是衡量无线传感网KPD方案的一个重要性能指标. 从区组设计的可行性和KPD方案的高密钥连通性出发，结合簇头节点和簇节点的异构性，构造适用于异构传感网的区组设计KPD方案. 本文首先定义区组设计w-BIBD，构造简单、可行的w-BIBD，将其映射到无线传感网的KPD方案中，该方案具有强密钥连通性且部署简单可行. 为了进一步提高抗毁性，对w-BIBD进行扩展，提出EX-w-BIBD的KPD方案；该方案能够支持更大的网络规模，在保证一定密钥连通性的同时，提高了网络的抗毁性.

1 区组设计相关知识 1.1 区组设计

定义1^[21] 　设基集 ${{V}} = \{ {p_1},{p_2}, \cdots ,{p_v}\} $ ，B是V的子集族，即 ${{B}} = \{ {B_1},{B_2}, \cdots ,{B_b}\} $ ，其中B₁，B₂， $ \cdots $ ，B_b是V的b个子集. 称V中的元素为点（point），B中的元素为区组（block），B为V上的一个区组设计. 若B是V满足特定条件的全排列，则称B为V的一个完全区组设计，否则为不完全区组设计.

定义2^[17] 　设 ${{B}} = \{ {B_1},{B_2}, \cdots ,{B_b}\} $ 是基集 ${{V}} = \{ {p_1}, $ ${p_2}, \cdots ,{p_v}\} $ 的一个区组设计，当B满足如下条件：1）均匀性（uniformity）：B中所有区组的长度（区组中点的个数）均为k；2）正则性（regularity）：V中任意一元素均出现在B的r个区组中；3）平衡性（balance）：V中任意一对元素同时出现在B的λ个区组中；则称B为V的一个平衡不完全区组设计（balanced incomplete block design，BIBD），被表示为B（v，b，r，k，λ）. v、b、r、k、λ作为区组设计的参数，满足如下关系：bk = vr，λ（v−1）=r（k−1），特别地，当b = v时，k = r，称该区组设计为对称平衡不完全区组设计（symmetric BIBD，sBIBD），记作sB（v，k，λ）.

当素数幂q ≥ 2时，存在一个区组设计sBIBD（q² + q + 1，q + 1，q），Comtepe等^[14]利用该区组设计，完成了确定性KPD方案. 文献[11]中，sBIBD（q² + q + 1，q + 1，q）映射到KPD方案中，有如下对应关系：基集V中的元素对应密钥池里的密钥（ID），则密钥池中密钥个数为q² + q + 1；B中的区组对应密钥环，则密钥环个数为q² + q + 1；区组长度代表密钥环中密钥的个数，则每个节点预分配的密钥个数为q + 1；在该区组设计中，任意一对区组均共享1个元素，映射到KPD方案中，即任意一对节点间有1个共享密钥. 由此保证了该KPD方案的连通性为1.

当q较大时，该区组设计的构造是一个困难问题，限制了它所映射的KPD的传感网规模，即当q较大时，基于该区组设计的KPD方案仅仅在理论上可行.

1.2 w-平衡不完全区组设计

将不同类型的区组设计对应到KPD方案中，会产生不同的网络性能. 提出区组设计的概念.

定义3　设基集 ${{V}} = \{ {p_1},{p_2}, \cdots ,{p_v}\} $ 的一个区组设计 ${{B}} = \{ {B_1},{B_2}, \cdots ,{B_b}\} $ ，具有均匀性和正则性，即B中所有区组的长度均为k，V中每一个点均出现在B的r个区组中. 当V中任意一对元素，同时出现在B的区组中的个数有w种情况时，称该区组设计为w-平衡不完全区组设计（w-balanced incomplete block design，w-BIBD）. 该区组设计表示成w-B（v，b，r，k，λ₁： $ \cdots $ ：λ_w），代表V中任意两点同时出现在λ₁~λ_w个区组中，特别地，当b = v时，称该区组设计为对称w-平衡不完全区组设计（w-sBIBD），表示为w-sB（v，b，r，k，λ₁： $ \cdots $ ：λ_w）.

定理1.1　若w-BIBD存在，则有如下关系： $bk = vr$ .

定理1.2　若w-BIBD存在，则任意2个区组的公共元素个数为 λ₁， $ \cdots $ ，λ_w个. 当w = 1时，对称w-平衡不完全区组设计退化成对称平衡不完全区组设计，此时，任意两区组共享λ₁个元素.

例 1　设集合V={1, 2, $ \cdots $ , 15}，B = {B₁，B₂， $ \cdots $ ，B₁₅}，其中B₁，B₂， $ \cdots $ ，B₁₅是V的15个区组，B₁ = {2，3，4，5，6，11}；B₂ = {1，3，4，5，7，12}；B₃ = {1，2，4，5，8，13}；B₄ = {1，2，3，5，9，14}；B₅ = {1，2，3，4，10，15}；B₆ = {1，7，8，9，10，11}；B₇ = {2，6，8，9，10，12}；B₈ = {3，6，7，9，10，13}；B₉ = {4，6，7，8，10，14}；B₁₀ = {6，7，8，9，5，15}；B₁₁ = {1，6，12，13，14，15}；B₁₂ = {2，7，11，13，14，15}；B₁₃ = {3，8，11，12，14，15}；B₁₄ = {4，9，11，12，13，15}；B₁₅ = {5，10，11，12，13，14}.

该区组设计B中所有区组的长度均为6，V中每一个点均出现在B的6个区组中，因此B具有均匀性和正则性，v = b = 15，r = k = 6，λ₁ = 1，λ₂ = 2，λ₃ = 3，w = 3. 该区组设计为3-sBIBD，可以表示为3-sB（15，6，1: 2: 3）.

2 基于w-BIBD的KPD方案

基于组合设计的KPD方案是将组合设计中的区组作为密钥环分配给所有的传感器节点，区组中的元素不是密钥，而是密钥的ID，即区组之间一旦具有共享元素，就由该共享元素对应的密钥来生成会话密钥. 由1.2节的w-BIBD定义，分别在二维空间和三维空间上构造w-BIBD区组. 将这2种区组映射到KPD方案的传感器节点密钥环构造中，这2种区组的性质反映了KPD方案的性能.

2.1 一个w-平衡区组设计（w-BIBD）的构造

由于组合设计清晰的结构特征，将组合设计映射到KPD方案中，可以方便地刻画出传感网中KPD方案的性能. 构造w-平衡区组设计w-sB（v，k，λ₁： $ \cdots $ ：λ_w），构造过程如下.

集合V中的点用二维向量[a，b]表示，其中 $a{\rm{, }}b \in {\rm{\{ 1,}} \cdots ,q{\rm{\} }}$ ，基集V的结构为

V：{(1，1)，(1，2)， $ \cdots $ ，(1，q)，

(2，1)，(2，2)， $ \cdots $ ，(2，q)，

$ \cdots $

(q，1)，(q，2)， $ \cdots $ ，(q，q)}

区组的下标用一个二维向量表示，区组的构造形式为B_{a, b} = {（a，y），（x，b）| 1≤ x ≤ q，x ≠ a；1 ≤ y ≤ q，y ≠ b}，则w-BIBD可以表示为B = {B_{a, b}：（a，b）∈Z_q × Z_q}. 为了更好地理解区组中的元素组成，区组与区组元素的对应关系如图1所示. 当区组的下标为（a，b）时，区组中的元素是由V中行下标为a的除（a，b）之外的所有元素和V中列下标为b的除（a，b）之外的所有元素组成.

该区组设计满足如下定理.

定理2.1　在该w-BIBD中，集合V中的元素个数为q × q，区组设计B中的区组个数为q × q，区组长度为2q − 2.

证：由该区组设计的构造过程可知，V是q × q的二维向量的集合，因此V中元素个数为q × q；B中的各个区组 ${B_{a,b}}$ 是由a行不包括（a，b）的所有元素和b列不包括（a，b）所有元素组成，因此区组长度为q – 1 + q – 1 = 2q − 2； $( a , b) \in {{{Z}}_q} \times {{{Z}}_q}$ ，则B中区组个数为q × q. 证毕.

定理2.2　在该w-BIBD中，V中每个元素出现在2q − 2个区组中.

证：由区组的构造形式可知，V中的元素（a，b）应出现在区组 ${B_{a,\overline b }}$ （其中 $\overline b $ 表示列向量为非b元素）和区组 ${B_{\overline a ,b}}$ （其中 $\overline a $ 表示列向量为非a元素）中，因此包含（a，b）的区组个数为2q − 2. 证毕.

定理2.3　在该w-BIBD中，V中的任意不同两点（a₁，b₁）和（a₂，b₂）同时出现在区组中的个数 $\lambda $ 有2种情况：当a₁ = a₂且 b₁ ≠ b₂或 b₁ = b₂且a₁ ≠ a₂时，λ为q − 2；当 a₁ ≠ a₂且 b₁ ≠ b₂时，λ为2.

证：当任意两点行向量值a相同，即两点同行，则这两点同时出现在该行除了这两点外的其他元素表示的区组中，即λ = q − 2个区组中；同理，当任意两点列向量 b相同，即两点同列时，λ = q − 2；当两点行列值不同时，则这两点同时出现在 ${B_{{a_1},{b_2}}}$ 和 ${B_{{a_2},{b_1}}}$ 中，即λ = 2. 证毕.

通过区组设计的3个定理可知，该区组设计w-BIBD是对称的，可以表示为2 - sB（q × q，2q − 2，2：q – 2）.

2.2 w-平衡区组设计到KPD的映射

由定理2、3可知，当q > 3时，w-BIBD中任意2个区组之间至少有2个共享元素；因此，在区组设计到KPD的映射中，为了节省节点存储空间耗费，同时提高网络的扩展性，将一个密钥平均分成两部分，则实际的密钥池中的密钥和密钥环中的密钥都是半密玥. 具体过程如下. 利用某种密钥生成算法产生q × q个密钥，将q × q个密钥分成2q × 2q个半密钥放到密钥池（key pool）中，则2q × 2q个元素(1，1)， $ \cdots $ ，(1，2q）， $ \cdots $ ，（a，b）， $ \cdots $ ，(2q，1)， $ \cdots $ ，(2q，2q)作为半密钥标识（key ID）分配给密钥池中的各个半密钥，元素（a，b）（1 ≤ a ≤ 2q，1 ≤ b ≤ 2q）和对应的半密钥key_{（a, b）}作为一个整体表示成p_{a, b}，V是p_{a, b}（1 ≤ a ≤ 2q，1 ≤ b ≤ 2q）的集合. 按照2.1节的区组设计构造方法，生成2q × 2q个区组B_{a, b}，（a，b）∈Z_2q × Z_2q，B_{a, b} = {p_{x, b}，p_{a, y} | 1 ≤ a ≤ 2q，x ≠ a，1 ≤ b ≤ 2q，y ≠ b}，区组B_{a, b}长度为2（2q－1）.

密钥预分配阶段如下：将区组B_{a, b}中的 2（2q－1）个元素p_{a, b}（半密钥）作为密钥环分配给某个传感器节点，w-BIBD与KPD的基本映射关系如表1所示. 表中各参数的定义与1节中的定义一致.

共享密钥发现阶段如下：当某个传感器节点需要传输数据时，该节点广播密钥环中的密钥ID，在该节点通信范围内的节点一旦有相同的密钥ID，则与该密钥ID所对应的半密钥是这2个节点的共享半密钥. 由定理2. 3可知，两节点间共享密钥的个数有2种可能性：2和2q－2，即任意两节点间至少有2个半密钥.

会话密钥建立阶段如下：当两节点间发现多个共享半密钥时，任意2个半密钥根据顺序不同可以合成2个密钥，则共享的2q－2个半密钥可以合成 ${\rm{2C}}_{2q{\rm{ - 2}}}^2$ 个共享密钥. 为了提高节点间通信的安全性，采用文献[15]所提的方案，选取两节点N_i和N_j间的s个共享密钥{ k₁，k₂， $ \cdots $ ，k_s }，2 ≤ s ≤ ${\rm{2C}}_{2q{\rm{ - 2}}}^2$ ；通过Hash函数计算得出两节点间会话密钥K_i,j，即 ${K_{i,j}} = h({k_1}\left\| \cdots \right\|\left\| {{k_s}} \right\|i\left\| j \right\|)$ . 由于两节点间共享的半密钥可以组合成多个密钥，为了提高共享密钥强度，当相同两节点进行多次通信时，可以选取不同的共享密钥进行Hash运算.

基于w-BIBD的密钥预分配方案具有以下优点：w-BIBD构造简单，映射到KPD中实现容易；具有强连通性，2个节点间有2个或者多个共享密钥，保证了网络中任意节点间的密钥直接连通.

2.3 方案性能分析

基于组合设计的KPD方案的性能分析主要是从密钥存储、密钥性通性、网络可扩展性和面对节点妥协的抗毁性这5个方面讨论^{[15, 17, 22-23]}.

1）存储耗费（storage overhead）.

将w-BIBD映射到KPD方案中，密钥池中半密钥的个数为2q×2q，每一个节点预分配一个密钥环，密钥环中的半密钥个数即区组中元素的个数，为2（2q－1）. 节点存储密钥所需的空间为l ×（2q－1），其中l表示密钥的大小.

2）网络可扩展性（network scalability）.

可扩展性是指无线传感网中KPD所支持的最大网络规模. 在基于组合设计的KPD方案中，组合设计中的区组对应节点的密钥环，因此区组个数代表了传感网的节点数量，即传感网网络规模.

在w-BIBD中，区组个数为2q×2q，区组大小为2(2q－1)，映射到KPD方案中，在密钥环中密钥个数为M = 2q－1的情况下，方案所支持的最大网络规模T₁=（M + 1）².

3）密钥连通性.

密钥连通性是衡量无线传感网KPD方案性能的重要指标之一. 良好的连通性既能节省无线传感网的通信开销，又能保证传感网的安全性^[3].

在w-sBIBD中，将基集V中的元素表示成2q×2q二维向量形式，则任意两点出现在2或者2q－2个相同的区组中. 将该定理映射到KPD模型中，则表示节点之间的共享密钥个数有2种可能性：当两节点密钥ID的行向量相同或列向量相同时，两节点共享2q－2个半密钥；当两节点密钥ID的行、列向量均不相同时，两节点间共享2个半密钥. 无论哪种情况，两节点之间至少有2个共享半密钥. w-sBIBD映射下的KPD方案中，节点间的密钥连通率T₂ = 1.

4）网络抗毁性

抗毁性是衡量传感网性能的重要指标，指当传感网面对节点捕获攻击（node capture）时，妥协节点对剩余节点安全性的影响，即当x个随机节点被捕获后，2个确定的节点（未妥协）间通信被破解的概率^{[12, 15]}，用 res（x）来表示，res（x）越小，抗毁性越强.

在w-sBIBD的KPD方案中，两节点之间的共享半密钥个数是2或2q－2个. 下面对方案的抗毁性进行分析.

a）两节点间的共享半密钥个数为2.

设节点N1和N2的区组下标分别为（a₁, b₁）和（a₂, b₂），分配给N1和N2的密钥环对应的区组为 ${B_{a_1,{\rm{ }}b_1}}$ 和 ${B_{a_2,{\rm{ }}b_2}}$ ，两节点之间有2个共享半密钥，半密钥ID表示为（a₁, b₂）和（a₂, b₁）. 为了简单起见，用半密钥ID表示半密钥. 当x个随机节点被捕获后，N1和N2之间的通信被破解的概率即抗毁性，用r₁（x）来表示. 设 ${{{G}}_{(a_1,{\rm{ }}b_2)}}$ 和 ${{{G}}_{(a_2,{\rm{ }}b_1)}}$ 分别是包含（a₁, b₂）和（a₂, b₁）的区组的集合. 由定理2.2可知，

$|{{{G}}_{(a_1,{\rm{ }}b_2)}}|{\rm{ = }}|{{{G}}_{(a_2,{\rm{ }}b_1)}}|{\rm{ = }}2(2q - 1),$

$ |{{{G}}_{(a_1,{\rm{ }}b_2)}} \cap {{{G}}_{(a_2,{\rm{ }}b_1)}}| = 2, $

则 $|{{{G}}_{(a_1,b_2)}} \cup {{{G}}_{(a_2,b_1)}}| = 4{\rm{ }}(2q - 1) - 2 = 8q - 6$ . 要想保证N1和N2这2个节点之间的通信安全，（a₁，b₂）或（a₂，b₁）不应该出现在x个妥协节点的密钥环（区组）中.

与（a₁，b₂）无关的x个节点选取方法有 $\left( \begin{array}{c}4{q^2} - 4q + 2\\x\end{array} \right)$ .

同样地，与（a₂，b₁）无关的x个节点选取方法为 $\left( \begin{array}{c} 4{q^2} - 4q + 2 \\ x \\ \end{array} \right)$ .

在与 ${{{G}}_{(a_1,b_1)}} \cup {{{G}}_{(a_2,b_2)}}$ 无关的区组中选择出x个区组的方法有 $\left( \begin{array}{c} 4{q^2} - 8q + 6 \\ x \\ \end{array} \right)$ .

若x个节点妥协，则2个给定节点间的通信被破解的概率为

$\begin{split} r_1(x) = & 1 - \frac{{2\left( \begin{array}{c} 4{q^2} - 4q + 2\\ x \end{array} \right) - \left( \begin{array}{c} 4{q^2} - 8q + 6\\ x \end{array} \right)}}{{\left( \begin{array}{c} 4{q^2} - 2\\ x \end{array} \right)}} = \\ & 1 - 2{\left( {1 - \frac{{4{{q}} - 4}}{{4{q^2} - 2}}} \right)^x} + {\left( {1 - \frac{{8{{q}} - 8}}{{4{q^2} - 2}}} \right)^x}. \end{split}$

b）两节点间的共享半密钥个数为2q – 2.

当映射到节点N1和N2的密钥环上的区组表示同行（或同列）时，两节点共享2q − 2个半密钥. 当妥协节点个数为 x时，在3种情况下N1和N2会被破解：（1）在妥协的x个节点中，至少有2个节点的密钥环对应的区组行（或列）下标与N1和N2的区组行（或列）下标相同；（2）在妥协的节点中，有一个节点的区组与N1和N2的区组同行（或列），另一个节点的区组列（或行）下标与该节点的区组列（或行）下标相同；（3）在妥协的x节点中，当所有节点的区组下标都与N1和N2的区组下标不同时， $x \geqslant 2q - 2$ 且至少有2q − 2个妥协节点的区组列下标与N1和N2区组列下标不同.

情况I和II下的抗毁性为

$r{\rm{_{2\_1}(}}x{\rm{) = }}1 - \frac{{\left( \begin{array}{c} 4{q^2} - 2q \\ x \\ \end{array} \right) + \left( \begin{array}{c} 2q - 2 \\ 1 \\ \end{array} \right)\left( \begin{array}{c} 4{q^2} - 2q \\ x - 1 \\ \end{array} \right)}}{{\left( \begin{array}{c} 4{q^2} - 2 \\ x \\ \end{array} \right)}}.$

在情况III下，x个妥协节点中应保证除N1和N2的区组之外，其余区组列至少有一个妥协节点，则此时妥协节点的选取方式为

$\begin{split} s{\rm{_{2\_2}(}}x{\rm{) = }}&\left( \begin{array}{c} 2q(2q - 1)\\ x \end{array} \right) - \\ & \left( \begin{array}{c} 2q - 2\\ 1 \end{array} \right)\left( \begin{array}{c} (2q - 1)(2q - 1)\\ x \end{array} \right){\rm{ + }}\\ & \left( \begin{array}{c} 2q - 2\\ 2 \end{array} \right)\left( \begin{array}{c} (2q - 1)(2q - 2)\\ x \end{array} \right){\rm{ + }} \cdots {\rm{ + }}\\ & {{\rm{( - 1)}}^\theta }\left( \begin{array}{c} 2q - 2\\ \theta \end{array} \right)\left( \begin{array}{c} (2q - 1)(2q - \theta )\\ x \end{array} \right) + \cdots . \end{split}$

其中， ${\rm{(2}}q - 1{\rm{)(2}}q - 2{\rm{)}} \geqslant x \geqslant 2q - 2$ . 此时的抗毁性为

$r{\rm{_{2\_2}(}}x{\rm{) = }}\frac{{s{\rm{_{2\_2}}}(x)}}{{\left( \begin{array}{c} 2q(2q - 1) \\ x \\ \end{array} \right)}}. $

当两节点共享密钥个数为2q − 2时，抗毁性为

$r_2(x){\rm{ = }}r_{2\_1}(x) + r_{2\_2}(x). $

由w-sBIBD结构可知，两节点共享2q − 2个半密钥的概率为

$p_2 = \frac{{4q - 2}}{{4{q^2} - 1}} = \frac{2}{{2q + 1}}. $

节点共享2个密钥的概率为

$p_1 = 1 - p_2 = \frac{{2q - 1}}{{2q + 1}}. $

因此，基于w-sBIBD的KPD方案的抗毁性为

$ \begin{aligned} & {\rm res}\;(x) = p_1 r_1(x) + p_2 r_2(x){\rm{ = }}\\ & \frac{{2q{\rm{ - 1}}}}{{2q{\rm{ + 1}}}}\left[ {1 - 2{{\left( {1 - \frac{{4q - 4}}{{4{q^2} - 2}}} \right)}^x} + {{\left( {1 - \frac{{8q - 8}}{{4{q^2} - 2}}} \right)}^x}} \right]{\rm{ + }}\\ & \frac{2}{{2q + 1}}\left[ {1 - \frac{{\left( \begin{array}{c} 4{q^2} - 2q + 2\\ x\end{array} \right) + \left( \begin{array}{c} 2q - 2\\ 1 \end{array} \right)\left( \begin{array}{c} 4{q^2} - 4q{\rm{ + }}3\\ x - 1 \end{array} \right)}}{{\left( \begin{array}{c} 4{q^2} - 2\\ x \end{array} \right)}}} \right.{\rm{ + }}\\ & \left. {\frac{{{S_{{\rm{2}}\_{\rm{2}}}}}}{{\left( \begin{array}{c} 2q(2q - 1)\\ x \end{array} \right)}}} \right]. \end{aligned} $

方案的密钥强连通性必然会降低网络抗毁性. 为了提高网络抗毁性，同时保证密钥的连通性，对2.1节的w-BIBD进行扩展，构造EX-w-BIBD，并映射到无线传感网的KPD中.

3 扩展的w-BIBD的KPD方案 3.1 EX-w-BIBD到KPD方案的映射

与基于BIBD的KPD方案相比，w-BIBD方案所支持的网络规模较小，可扩展性不足. 将2. 1节中二维向量的区组构造扩展到三维向量，w-BIBD由二维平面扩展到三维空间，构造三维空间的w-BIBD，称为EX-w-BIBD. 扩展过程如下.

集合V中的点用三维向量[a，b，c] 表示，其中a，b，c∈{1，···，q}，基集V中的元素可以表示为

$V = \left\{ {(1,1,1), \cdots ,(i,j,l), \cdots ,(q,q,q)} \right\}. $

构造该基集V下的区组设计，其中区组个数为q × q × q，区组大小为3（q− 1）.

$ \begin{aligned} {B_{a,b,c}} = & \{ (x,b,c),(a,y,c),(a,b,z)|1 \leqslant x \leqslant q,{\rm{ }}x \ne a;\\& 1 \leqslant y \leqslant q,{\rm{ }}y \ne b;1 \leqslant z \leqslant q,{\rm{ }}z \ne c\} , \end{aligned} $

则 ${{B}} = \{ {B_a}_{,b,c}{:}(a,b,c) \in {{{Z}}_q} \times {{{Z}}_q} \times {{{Z}}_q}\} $ . 为了清楚地理解三维空间上的区组构造，图2中区组与区组元素之间的关系表示如下. 每个小正方体代表V中的元素，图2中3个条形相交的正方体用三维向量[a，b，c]表示，则区组 ${B_{a,b,c}}$ 中的区组元素是这3个条形空间（除相交部分的正方体）所代表的元素.

与2.2节中的区组设计KPD方案相同，将每一个密钥分成2个半密钥，实际KPD方案中的密钥池和密钥环中存储的都是半密钥. 扩展的w-BIBD区组设计（EX-w-BIBD）的KPD是指用基集V中的点作为半密钥ID，分配给密钥池中的2q × 2q × 2q个半密钥，每一个区组 ${B_{a,b,c}}$ 作为密钥环分给无线传感器中的各个节点，则各区组之间的共享元素代表了传感网节点之间的共享半密钥的ID. 最后由共享半密钥合并确定节点之间的会话密钥，其过程与二维向量的区组表示相同.

3.2 方案性能分析

1）存储耗费.

将EX-w-BIBD映射到KPD方案中，密钥池密钥的个数为2q × 2q × 2q，每一个节点预分配一个密钥环，密钥环的个数即区组中元素的个数，为6q－3. 节点存储密钥所需的空间为 $l (6q - 3)/2.$

2）网络可扩展性.

在EX-w-BIBD中，区组个数为2q × 2q × 2q，区组大小为6q－3，则在该区组设计的KPD方案中，密钥环中的密钥个数为 $M = 3(2q - 1)/2$ ，网络的可扩展性T₁ = ${\left[ {\left( {2M + 3} \right)/3} \right]^3}$ .

3）密钥连通性.

在EX-w-sBIBD方案中，由于基集V中的元素（半密钥ID）是由三维向量表示，设分配给2个节点的区组分别为 ${B_{a_1,b_1,c_1}}$ 和 ${B_{a_2,b_2,c_2}}$ ，则有以下3种情况.

a）当a₁ ≠ a₂且b₁ ≠ b₂，c₁ ≠ c₂时，2个区组无共同元素.

b）在 a₁ 和a₂、b₁ 和b₂、c₁ 和c₂中，任意一对相等，其余两对不等时，2个区组有2个共同元素.

c）在a₁ 和a₂、b₁ 和b₂、c₁ 和c₂中，任意两对相等，剩余一对不等时，2个区组有2q－2个共同元素.

由此，在EX-w-sBIBD方案中，与某一节点有共享密钥的节点个数为6q（2q – 1）个，传感网中节点个数为（2q）³ − 1. WSNs的直接连通性为

$T_2 = \frac{{6q(2q - 1)}}{{{{(2q)}^3} - 1}} = \frac{{6q}}{{4{q^2} + 2q + 1}}. $

4）网络抗毁性.

EX-w-BIBD下的KPD方案中，两节点之间的共享密钥有0、2或2q－2个. 下面对方案的抗毁性进行分析，分析过程与w-BIBD相似.

a）两节点间有2个共享密钥.

当两节点对应的区组下标在同一平面上的不同行列时，有2个共享密钥. 设半密钥ID为（a₁, b₁, c₁）和（a₂, b₂, c₂）， ${{{G}}_{(a_1,b_1,c_1)}}$ 和 ${{{G}}_{(a_2,b_2,c_2)}}$ 分别为包含（a₁, b₁, c₁）和（a₂, b₂, c₂）的区组的集合，此时

$ |{{{G}}_{(a_1,b_1,c_1)}}| = |{{{G}}_{(a_2,b_2,c_2)}}| = 6q - 3, $

$ |{{{G}}_{(a_1,b_1,c_1)}} \cap {{{G}}_{(a_2,b_2,c_2)}}| = 2, $

则

$|{{{G}}_{(a_1,b_1,c_1)}} \cup {{{G}}_{(a_2,b_2,c_2)}}| = 2(6q - 3) - 2 = 12q - 8. $

若要保证N1和N2这2个节点之间的通信安全，则（a₁, b₁, c₁）或（a₂, b₂, c₂）不应该出现在x个妥协节点的密钥环（区组）中.

与（a₁, b₁, c₁）和（a₂, b₂, c₂）无关的x个节点（区组）选取方法有 $\left( \begin{array}{c} 8{q^3} - 6q + 3 \\ x \\ \end{array} \right)$ ， ${{{G}}_{(a_1,b_1,c_1)}} \cup $ $ {{{G}}_{(a_2,b_2,c_2)}}$ 无关的区组中选择出x个区组的方法有 $\left( \begin{array}{c} 8{q^3} - 12q + 8 \\ x \\ \end{array} \right)$ ;

因此，如果 x个节点妥协，那么2个给定节点间的通信被破解的概率为

$\begin{aligned} r_{_1}'(x) = & 1 - \frac{{2\left( \begin{array}{c} 8{q^3} - 6q + 3\\ x\end{array} \right) - \left( \begin{array}{c} 8{q^3} - 12q + 8\\ x\end{array} \right)}}{{\left( \begin{array}{c} 8{q^3} - 2\\ x\end{array} \right)}} = \\ & 1 - 2{\left( {1 - \frac{{6q - 5}}{{8{q^3} - 2}}} \right)^x} + {\left( {1 - \frac{{12q - 10}}{{8{q^3} - 2}}} \right)^x}. \end{aligned}$

b）两节点间的共享密钥为2q – 2.

当区组下标表示位于同一平面的同行（或同列）时，两节点共享2q − 2个密钥，当妥协节点的区组与这两节点的区组有相同的行（列）下标时，节点抗毁性分析应与二维区组设计相同，此时的抗毁性为

$r_{_{{\rm{2\_1}}}}'{\rm{(}}x{\rm{) = }}1 - \frac{{\left( \begin{array}{c} 8{q^2} - 4q \\ x \\ \end{array} \right) + \left( \begin{array}{c} 2q - 2 \\ 1 \\ \end{array} \right)\left( \begin{array}{c} 8{q^2} - 4q \\ x - 1 \\ \end{array} \right)}}{{\left( \begin{array}{c} 8{q^3} - 2 \\ x \\ \end{array} \right)}}. $

妥协节点的选取方式有

$\begin{aligned} s_{_{{\rm{2\_2}}}}'{\rm{(}}x{\rm{) = }} & \left( \begin{array}{c} 4q(2q - 1)\\ x\end{array} \right) - \\ & \left( \begin{array}{c} 2q - 2\\ 1\end{array} \right)\left( \begin{array}{c} 2(2q - 1)(2q - 1)\\ x\end{array} \right){\rm{ + }}\\ & \left( \begin{array}{c} 2q - 2\\ 2\end{array} \right)\left( \begin{array}{c} 2(2q - 1)(2q - 2)\\ x\end{array} \right){\rm{ + }} \cdots {\rm{ + }}\\ & {{\rm{( - 1)}}^\theta }\left( \begin{array}{c} 2q - 2\\ \theta \end{array} \right)\left( \begin{array}{c} 2(2q - 1)(2q - \theta )\\ x\end{array} \right){\rm{ + }} \cdots . \end{aligned}$

式中： ${\rm{ (2}}q - 1{\rm{)(2}}q - 2{\rm{)}} \geqslant x \geqslant 2q - 2$ .

当两节点共享半密钥个数为2q − 2时，抗毁性为

$r_{_{{\rm{2\_2}}}}'{\rm{(}}x{\rm{) = }}\frac{{s_{_{{\rm{2}}\_{\rm{2}}}}'(x)}}{{\left( \begin{array}{c} 4q(2q - 1) \\ x \\ \end{array} \right)}}. $

两节点共享2 q − 2个半密钥的概率为

$p_{_2}' = \frac{{6q - 3}}{{8{q^3} - 1}} = \frac{3}{{4{q^2} + 2q + 1}}. $

两节点共享2个半密钥的概率为

$p_{_1}' = \frac{{6q - 3}}{{4{q^2} + 2q + 1}}. $

EX-w-sBIBD的KPD方案的抗毁性为

$\begin{array}{*{20}{l}} {{\rm{re}}{{\rm{s}}^\prime }(x) = {p_{\rm{1}}}^\prime {{{r}}_{\rm{1}}}^\prime ({{x}}){\rm{ + }}{{{p}}_2}^\prime{r_2}^\prime({{x}}){\rm{ = }}}\\ {\displaystyle\frac{{{{6q - 3}}}}{{{\rm{4}}{{{q}}^{\rm{2}}}{{ + 2q + 1}}}}\left[ {{\rm{1 - 2}}{{\left( {{\rm{1 - }}\frac{{{{6q - 5}}}}{{{\rm{8}}{{{q}}^{\rm{3}}}{\rm{ - 2}}}}} \right)}^{{x}}}{\rm{ + }}{{\left( {{\rm{1 - }}\frac{{{{12q - 10}}}}{{{\rm{8}}{{{q}}^{\rm{3}}}{\rm{ - 2}}}}} \right)}^{{x}}}} \right]{\rm{ + }}}\\ \begin{array}{l} \\[-5pt] \displaystyle\frac{{\rm{3}}}{{{\rm{4}}{{{q}}^{\rm{2}}}{{ + 2q + 1}}}}\left[ {{\rm{1 - }}\frac{{\left( {\begin{array}{*{20}{c}} {{\rm{8}}{{{q}}^{\rm{2}}}{{ - 4q}}}\\ {{x}} \end{array}} \right){\rm{ + }}\left( {\begin{array}{*{20}{c}} {{{2q - 2}}}\\ {\rm{1}} \end{array}} \right)\left( {\begin{array}{*{20}{c}} {{\rm{8}}{{{q}}^{\rm{2}}}{{ - 4q}}}\\ {{{x - 1}}} \end{array}} \right)}}{{\left( {\begin{array}{*{20}{c}} {{\rm{8}}{{{q}}^{\rm{3}}}{\rm{ - 2}}}\\ {{x}} \end{array}} \right)}}} \right.{\rm{ + }} \end{array} \end{array} $

$\left. {\frac{{S{^{\prime} _{2\_2}}}}{{\left( {\begin{array}{*{20}{c}} {{{4q}}({{2q - 1}})}\\ {{x}} \end{array}} \right)}}} \right]. $

4 性能对比及分析

将w-BIBD和EX-w-BIBD的KPD方案与UD方案^[12]和RD方案^[17]的性能进行对比分析，4种方案的对应参数如表2所示. 表中参数对应区组设计中的参数，v为基集V中的元素个数，该方案是指密钥池中的半密钥个数；b为区组个数，即密钥环个数；r为半密钥出现在密钥环的个数；k为密钥环大小； $\lambda $ 为一对密钥出现在密钥环的个数.

4.1 存储耗费对比

对比相同网络规模下这4种方案的存储耗费，在b相同的情况下，密钥环存储耗费（为了简化起见，用k表示）的对应关系如图3所示.

从图3可以看出，在节点个数由1 000到10 000递增的过程中，w-BIBD方案的存储耗费上升很快，其他3个方案的存储耗费上升缓慢，这说明当网络规模巨大时，w-BIBD方案需要大量的空间来存储密钥，因此该方案不适合规模巨大的无线传感网. EX-w-BIBD方案相比w-BIBD方案，存储耗费得到了极大的节省. 当网络中节点个数为5 000时，w-BIBD、EX-w-BIBD、UD和RD方案节点密钥环大小分别为70、24、10和8，其中w-BIBD方案和EX-w-BIBD方案中，2个半密钥和1个密钥所占的存储空间是一样的，因此这2个方案用2个半密钥个数代替密钥个数来表示存储耗费. 当网络中节点个数为10 000时，这3个方案中密钥环大小分别至少为99、31、12和10个. 假设该方案采用128位的AES密钥，传感网为10 000个传感器节点，则在EX-w-BIBD方案中，节点密钥环所占用的存储空间为31×128 bit ≈ 0.5 kB. 与UD和RD方案相比，EX-w-BIBD方案所占密钥存储空间略大. 从实际的无线传感网网络规模及传感器节点性能来看，在基于EX-w-BIBD的KPD方案中，节点中密钥占用的存储空间可以满足现有的网络规模.

4.2 网络扩展性对比

网络扩展性与存储耗费的关系是互逆的，即网络扩展性强，则存储耗费高. 扩展性受k的影响. 在传感器节点的密钥环大小相同的情况下，网络扩展性的对比结果如图4所示. 可知，这4种方案在相同的密钥环大小下，EX-w-BIBD的扩展性明显优于w-BIBD，但低于UD方案和RD方案. 由表2可知，在组合设计的参数映射KPD方案中，相同密钥环大小的情况下，UD方案和RD方案的网络扩展性为 $O({q^4})$ ，w-BIBD和EX-w-BIBD的网络扩展性分别为 $O({q^2})$ 和 $O({q^3})$ . 如当k = 30时，UD、RD、EX-w-BIBD和w-BIBD所支持的网络规模大小分别为：683 733、865 830、9 261和1 024. 当k = 50时，5 649 553、65 050 506、40 471和2 704. 尽管EX-w-BIBD所支持的网络规模比UD和RD小得多，但从实际的网络部署来看，该方案完全可行.

4.3 密钥连通性对比

在UD方案中，两节点共享密钥的概率为 ${{{{\left(q + 1\right)}^2}}}/({{{q^3} + q + 1}})$ .

在RD方案中，密钥的连通率可以表示为

$\frac{{{q^2}}}{{{q^2} + q}}{\rm QSC} + \frac{{(q - 1)({q^2} + 1) + {q^2}\left( {{q^2} - q{\rm{ + }}1} \right)}}{{{{({q^2} + q)}^2}}}{\rm QDC}.$

式中：

${\rm QSC}{\rm{ = }}\frac{{\left( \begin{array}{c} {q^2} + q \\ 2 \\ \end{array} \right)}}{{\left( \begin{array}{c} ({q^2} + q)({q^2} + q + 1) \\ 2 \\ \end{array} \right)}},$

${\rm QDC}{\rm{ = }}\frac{{{{({q^2} + q)}^2}}}{{\left( \begin{array}{c} ({q^2} + q)({q^2} + q + 1) \\ 2 \\ \end{array} \right)}}. $

在传感器节点密钥环大小相同的情况下，这4种方案的密钥连通率对比结果如图5所示. 可知，w-BIBD具有强连通性，密钥连通率为1. 对w-BIBD方案进行扩展，从二维空间扩展到三维空间，设计了EX-w-BIBD方案. 扩展的同时连通性下降，由图5可知，尽管EX-w-BIBD方案的连通率下降，但明显优于UD方案和RD方案. 当k<17时，RD方案的连通性高于EX-w-sBIBD方案；在k超过17后，RD方案的连通率下降得更快，低于EX-w-sBIBD方案的连通率. 在这4个方案中，UD方案的连通性最弱.

4.4 网络抗毁性对比

通过数据对比可知，UD方案、RD方案、w-BIBD方案和EX-w-BIBD方案这4种方案的抗毁性结果如图6所示. 图中，x为妥协节点个数. 所提方案的抗毁性参考2. 3节和3. 2节，RD方案^[17]的网络抗毁性为

$\begin{array}{l} {\rm{res}}\_{\rm{RD}}(x){\rm{ = }}\\ \\[-5pt] \displaystyle\sum\limits_{j = 1}^{{q^2} + q + 1} \frac{{\left( {\begin{array}{*{20}{c}} {q(q + 1)}\\ 2 \end{array}} \right)}}{{\left( {\begin{array}{*{20}{c}} {({q^2} + q + 1)(q + 1)}\\ 2 \end{array}} \right)}}\left( {1 - \frac{{\left( {\begin{array}{*{20}{c}} {(q + 1)({q^2} + 1)}\\ x \end{array}} \right)}}{{\left( {\begin{array}{*{20}{c}} {({q^2} + q + 1)(q + 1)}\\ x \end{array}} \right)}}} \right) = \\ \\[-5pt] \displaystyle\frac{{{q^2} + q - 1}}{{{q^2} + 2q + 2}}\left[ {1 - {{\left( {1 - \frac{q}{{{q^2} + q + 1}}} \right)}^x}} \right]. \end{array}$

在UD^[12]方案中，网络抗毁性表示为

${\rm res}{\rm{\_UD}}(x) = 1 - \frac{{\left( \begin{array}{c} {q^3}(q - 1) \\ x \\ \end{array} \right)}}{{\left( \begin{array}{c} {q^2}({q^2} - q + 1) \\ x \\ \end{array} \right)}}. $

EX-w-BIBD方案的抗毁性相比w-BIBD方案得到了极大的提高，这是由于w-BIBD的强连通性，导致映射的KPD方案的抗毁性较差；EX-w-BIBD方案平衡了连通性和抗毁性的关系，在保证密钥连通性的同时，极大地提高了网络的抗毁性. 可以看出，k越大，抗毁性越高. 由于组合设计中k和v的对应关系，在KPD方案中，密钥环中密钥个数增加，意味着相应的网络规模增大，网络中节点个数增多，网络的抗毁性提高. 分别对传感器节点的密钥环大小为24和48两种情况下，4种方案的网络抗毁性进行对比. 如图6(a)、(b)所示为当k =24和48时，在妥协节点个数x相同的情况下，4种方案的抗毁性对比. 可以看出，EX-w-BIBD方案的抗毁性明显优于其他3种方案.

4.5 对比分析

通过4.4节方案的性能对比可以看出，w-BIBD方案具有强密钥连通性，但同时导致了存储性、网络扩展性及网络抗毁性较差. 为了平衡各个性能，设计EX-w-BIBD方案. 该方案通过降低密钥连通性，获得了较好的网络扩展性和抗毁性. 如表3所示，对节点密钥环大小k = 12、24、36、48这4种情况下w-BIBD和EX-w-BIBD的扩展性及抗毁性进行数据对比. 表3中，T₁表示k所支持的网络规模. 在具体的异构网部署中，可以依据表3进行权衡，以适应不同的网络需求.

层簇式异构传感网是由sink节点、簇头节点和簇节点组成的3层拓扑结构，网络通信包括簇内通信和簇间通信. 异构传感网中的密钥预分配方案主要考虑如何为簇节点和簇头节点预分配密钥. 在异构传感网中，高性能的簇头节点数量少，因此应尽量保证簇头之间的有效安全通信. 簇头节点具有较大的存储空间且一般都具有抗捕获装置，即当簇头节点妥协时，存储内容不会被敌方获取. 根据这些特性可知，在设计对簇头节点进行密钥预分配时，可以考虑利用w-BIBD方案. 该方案的强连通性可以保证簇头之间彼此具有共享密钥,簇头中具有抗捕获装置，因此可以忽略该方案的弱抗毁性. 由于低性能的簇节点个数多，存储空间小且没有抗捕获装置，对簇节点进行密钥预分配可以利用EX-w-BIBD方案. 该方案较好的扩展性和抗毁性使其适用于大规模的低性能传感器，可以有效地保证簇节点之间的安全通信.

5 结　语

由于现有的区组设计构造相对复杂，导致区组设计的KPD方案应用在较大规模的传感网时，算法复杂度较高. 为了降低算法复杂度，在sBIBD设计的基础上提出w-平衡不完全区组设计的定义，构造w-BIBD，将该区组设计映射到KPD方案中. 基于w-BIBD的KPD实现简单，保证了全网的连通性，但方案扩展性和抗毁性较差. 为了提高方案的抗毁性，对w-BIBD方案进行扩展，将w-BIBD中区组对应的密钥环由二维向量空间扩展到三维向量空间，提出基于EX-w-BIBD的KPD方案. EX-w-BIBD方案在保证网络连通性的同时，提高了方案的扩展性. 与UD方案和RD方案相比，在有效的网络扩展性基础上，获得了密钥连通性和抗毁性之间的平衡.