余旺科，王淑華

(紹興文理學院數(shù)理信息學院，浙江紹興312000)

無線傳感器網(wǎng)絡WSN(Wireless Sensor Networks)一直被認為具有廣泛的應用前景，能夠部署在當前典型網(wǎng)絡所不能及的環(huán)境，為當前的眾多領域，如污染監(jiān)測、環(huán)境和交通流量監(jiān)控等提供良好的解決方案。針對無線傳感器網(wǎng)絡能量、計算能力、存儲空間及帶寬等局限性問題，為了延長網(wǎng)絡的生存時間，充分利用和優(yōu)化網(wǎng)絡資源顯得尤為重要[1－4]。有效的密鑰管理能為其他安全機制或服務提供最基本的技術支持[5－9]。由于無線傳感器網(wǎng)絡在各方面的局限性，傳統(tǒng)網(wǎng)絡的密鑰管理方案不適合在無線傳感器網(wǎng)絡中的應用。

現(xiàn)有的基于分組的密鑰管理方案還有些不足，如Kong等人提出的一種基于六邊形部署的雙變量多項式密鑰管理方案[10]，在該方案中當q=3時，網(wǎng)絡被俘獲的鏈路比為0．362，而且其網(wǎng)絡覆蓋率只有0．598。在2012年嚴雪莉等人提出的基于六邊形部署的密鑰管理方案中[11]，當m=100和m=200時，其網(wǎng)絡局部連通率最高分別為0．676和0．937，而全局連通率可能會更低一些。在代航陽等人提出的基于六邊形部署方案中[12]，網(wǎng)絡連通率為0．86。其他有些方案建立共享密鑰的不一致性也很嚴重，雖然一個組之間的共享密鑰建立概率很高，但整個無線傳感器網(wǎng)絡的共享密鑰建立概率不是很理想，所以降低了整個無線傳感器網(wǎng)絡的連通性[13]。本文在隨機密鑰預分配方案基礎上，提出一種新的利用正六邊形部署信息的密鑰預分配方案:HBKPS(Hexagon－Based Key Pre－distribution Scheme)。這種新的基于區(qū)域劃分的無線傳感器網(wǎng)絡隨機密鑰預分配方案，通過將無線傳感器網(wǎng)絡分為若干個子區(qū)域，每個子區(qū)域相當于一個分組，然后對各個分組分別部署密鑰。采用正六邊形分別對網(wǎng)絡進行分區(qū)，不但在覆蓋全網(wǎng)的同時分區(qū)之間沒有重疊區(qū)域，而且每個分區(qū)相鄰的分區(qū)數(shù)僅為6個。

1 HBKPS區(qū)域劃分

無線傳感器網(wǎng)絡節(jié)點可以隨機拋撒到目標區(qū)域。這種隨機拋撒傳感器節(jié)點的方式在實際中合理可行，例如可通過直升機到達部署區(qū)域進行拋撒，被拋撒的節(jié)點隨機分布在整個無線傳感器網(wǎng)絡區(qū)域中。本文提出的HBKPS方案將整個無線傳感器網(wǎng)絡區(qū)域分為若干個正六邊形子區(qū)域，每個子區(qū)域相當于一個組，然后對各個組分別部署密鑰。整個無線傳感器網(wǎng)絡被劃分為若干個正六邊形區(qū)域后的模型如圖1所示。

圖1 HBKPS方案的網(wǎng)絡模型

選擇正六邊形部署無線傳感器網(wǎng)絡有一大特點:正六邊形只有6個相鄰組，而正方形和三角形相鄰的組個數(shù)分別為8個和12個[14]。在每個組中的傳感器節(jié)點都是隨機分布的，每個組的傳感器節(jié)點部署模型如圖2所示。其中圓形部分表示每個節(jié)點直接通信的覆蓋范圍。

圖2 每個子區(qū)域的部署模型

HBKPS方案采用基本的密鑰預分配模型:一個大的密鑰池在部署之前被創(chuàng)建，密鑰池里包含了所有密鑰及密鑰所對應的ID，傳感器節(jié)點中的所有密鑰都是從這個大的密鑰池中隨機選取，以使該方案更具有通用性。在密鑰預分配前，先把整個無線傳感器網(wǎng)絡劃分為若干個正六邊形區(qū)域的分組，并把這些分組劃分為3個分區(qū)域，如圖1所示。

分區(qū)域劃分具體步驟如下:首先，在無線傳感器網(wǎng)絡中選擇一個最靠近無線傳感器網(wǎng)絡中心位置的分組作為密鑰分配的起始分組，如圖1中所示的分組(2，1)。接著選擇中心分組(2，1)的6個相鄰分組中的3個，這3個分組必須滿足其互不相鄰，如圖1 中所示的分組(1，1)、分組(3，1)和分組(2，2)。然后，分別沿著分組(2，1)的中心到分組(1，1)、分組(3，1)和分組(2，2)的中心方向繼續(xù)選擇相應的組，如圖1中背景為非白色的分組。最終，所有這些背景為非白色的分組就把整個無線傳感器網(wǎng)絡劃分為3個相同結構的分區(qū)域。

2 HBKPS方案

在密鑰分配前，先在每個分組的中心位置分別放置一個臨時傳感器節(jié)點，稱之為源傳感器節(jié)點。HBKPS方案中的符號含義如表1所示。

在HBKPS方案中，假設對任意的整數(shù)m、n、h和D均能保證下列式子成立:

源節(jié)點的密鑰分配步驟如下:

(1)首先，從密鑰池中隨機選取n個密鑰分配給位于中心分組(2，1)的源節(jié)點，并將其作為初始化源節(jié)點。接著，位于分組(1，1)、分組(3，1)和分組(2，2)的源節(jié)點分別從分組(2，1)的源節(jié)點的密鑰中隨機選取h個密鑰，其余的n－h(huán)個密鑰從密鑰池中隨機選取。

(2)分組(2，1)的中心到分組(1，1)、分組(3，1)和分組(2，2)的中心方向上的源節(jié)點分配方案如下:未分配分組的源節(jié)點從其相鄰的已分配分組的源節(jié)點的密鑰中隨機選取h個密鑰，其余的n－h(huán)個密鑰從密鑰池中隨機選取。

(3)3個分區(qū)域的密鑰分配方案如下(以右下方那個分區(qū)域為例，其它兩個分區(qū)域類似分配即可):如圖1所示，分組(3，2)的相鄰分組中已經(jīng)有3個分組(分組(2，1)、分組(3，1)和分組(2，2))的源節(jié)點已被分配了密鑰。其中分組(3，1)的源節(jié)點和分組(2，2)的源節(jié)點的密鑰都是從分組(2，1)的源節(jié)點的密鑰中分配而來，所以，稱分組(2，1)的源節(jié)點為密鑰的主要來源節(jié)點，其它兩個分組的源節(jié)點為密鑰的次要來源節(jié)點。

(4)如圖3所示，中間的實線邊框長方形分組表示分組(2，1)的源節(jié)點(密鑰主要來源節(jié)點)的密鑰分布，其他兩個長方形分別表示分組(3，1)和分組(2，2)的源節(jié)點的密鑰分布。分組(3，2)的源節(jié)點的密鑰由圖3中所示的C區(qū)的所有2h－n個密鑰和A、B、D、E區(qū)中的各一半密鑰構成，即:

圖3 已分配的3個源節(jié)點的密鑰分布圖

(5)接著，分配該分區(qū)域中的其他分組。如:分組(3，3)由分組(2，2)、分組(2，3)和分組(3，2)共同配置;分組(4，1)由分組(3，1)、分組(3，2)和分組(4，0)共同配置等，直到所有分組分配完成。

在所有分組的源節(jié)點都分配完成后再分配每個分組中的非源節(jié)點。每個分組中的非源節(jié)點的密鑰分配如下:從該分組中的源節(jié)點的密鑰中隨機選取m個密鑰。當所有節(jié)點的密鑰分配完成后，取出無線傳感器網(wǎng)絡中所有的源節(jié)點。因為這些占少數(shù)比例的源節(jié)點集中了絕大部分的分配密鑰，即使被俘獲較少的源節(jié)點也能對整個無線傳感器網(wǎng)絡造成較大的危害。

當有兩個節(jié)點想要進行通信時，首先交換各自擁有的密鑰ID來發(fā)現(xiàn)其互相之間共享的密鑰。任何兩個擁有共享密鑰的節(jié)點都可以隨機選擇其中一個共享的密鑰來進行安全通信。

3 密鑰共享分析

如圖1中所示的分組(3，4)與分組(3，3)、分組(3，2)和分組(2，1)的部署距離 D 分別為 1、2、3，即分組(3，4)中的所有傳感器節(jié)點與分組(2，1)中的所有傳感器節(jié)點的部署距離均為3。下面首先分析任意兩個分組的源節(jié)點之間不同的密鑰總數(shù)情況:

(1)以分組(3，1)和分組(2，1)為例:

在分組(3，1)中的h個密鑰是從分組(2，1)中選取的，剩下的n－h(huán)個密鑰才是從S中選取的，所以分組(3，1)和分組(2，1)中不同的密鑰總數(shù)最多為:

(2)以分組(3，2)和分組(2，1)為例:

如圖3中所示，分組(3，2)和分組(2，1)的共享密鑰是由圖3中C區(qū)的所有2h－n個密鑰和B、D區(qū)中的各一半密鑰構成。所以分組(3，2)和分組(2，1)中共享的密鑰總數(shù)為:

即分組(3，2)和分組(2，1)中不同的密鑰總數(shù)最多為:

(3)以分組(3，2)和分組(2，2)為例:

如圖3中所示，分組(3，2)和分組(2，2)的共享密鑰是由圖3中C區(qū)的所有2h－n個密鑰和D、E區(qū)中的各一半密鑰構成。所以分組(3，2)和分組(2，2)中共享的密鑰總數(shù)為:

即分組(3，2)和分組(2，2)中不同的密鑰總數(shù)最多為:

其他分組之間不同的密鑰總數(shù)類似以上分析。

由于每個分組中的非源節(jié)點從該分組中的源節(jié)點的密鑰中隨機選取m個密鑰，所以分組(3，2)和分組(2，2)中的非源節(jié)點之間共享的密鑰至少為:

其他分組的非源節(jié)點之間共享密鑰類似以上分析，可得HBKPS方案中任意兩個傳感器節(jié)點共享密鑰數(shù)至少為:

其中，當這兩個傳感器節(jié)點位于同一分組時D=0。

由式(4)可以得出:

所以，無線傳感器網(wǎng)絡中任意兩個傳感器節(jié)點都至少共享一個密鑰，無論傳感器節(jié)點移動到哪個區(qū)域，該節(jié)點都能和新的鄰居節(jié)點直接進行安全通信。當有兩個傳感器節(jié)點想要進行通信時，首先交換各自擁有的密鑰ID來發(fā)現(xiàn)其互相之間共享的密鑰。任何兩個擁有共享密鑰的傳感器節(jié)點都可以隨機選擇其中一個共享的密鑰對來進行安全通信。在HBKPS方案中，當傳感器節(jié)點部署的網(wǎng)絡面積很大時，并不需要保證整個網(wǎng)絡中任何節(jié)點都至少共享一個密鑰，因為當傳感器節(jié)點的通信范圍遠小于網(wǎng)絡部署面積的最大寬度時，如果還要保證距離最遠兩端的傳感器節(jié)點至少共享一個密鑰就不切合實際。所以在本文方案中，只需要保證某個節(jié)點與其通信范圍附近的節(jié)點之間至少共享一個密鑰，這樣，在連通概率方面就和保證整個網(wǎng)絡的任何兩個節(jié)點都至少共享一個密鑰相當，因為網(wǎng)絡連通概率可以表述為在相互通信范圍內(nèi)的鄰居節(jié)點之間的連通概率。我們將在下節(jié)的性能分析中具體討論部署距離和HBKPS方案中其它參數(shù)之間的關系。

4 HBKPS性能分析

本節(jié)從節(jié)點存儲需求和安全性對HBKPS方案進行評估。存儲需求:因為傳感器節(jié)點存儲空間有限，所以在保證網(wǎng)絡到達一定連通概率時，節(jié)點應存儲較少的密鑰。安全性:在攻擊者俘獲節(jié)點時，能最大限度的保證其他未被俘獲節(jié)點之間的通信安全。

4．1 存儲需求

在HBKPS中，本節(jié)將分析保證整個網(wǎng)絡連通概率為1的較理想情況下的節(jié)點最少密鑰數(shù)量，這也能相應的反映其它情況下的存儲需求性能。使用如下配置:

①主密鑰池S大小為，|S|=100 000。

②無線傳感器網(wǎng)絡的節(jié)點總數(shù)為10 000。

③部署網(wǎng)絡的總面積為1 000 m×1 000 m。

那么整個網(wǎng)絡被劃分的正六邊形區(qū)域總數(shù)為:

如果把整個網(wǎng)絡邊長單位由米轉換為正六邊形區(qū)域的個數(shù)，并且根據(jù)對角線上兩端的正六邊形區(qū)域的部署距離最大，得出HBKPS方案中的最大部署距離Dmax為:

由式(1)～式(3)、式(9)和式(10)可得出HBKPS方案中的m與L的關系如圖4所示。

圖4 當D=Dmax時m與L的關系圖

由圖4中所示可以看出，當無線傳感器網(wǎng)絡中L=50 m時，在HBKPS方案中每個節(jié)點存儲的密鑰數(shù)量只有20～35，就可以保證無線傳感器網(wǎng)絡中的全局連通概率為1，也就是無線傳感器網(wǎng)絡中任何兩個傳感器節(jié)點都至少擁有一個共同的密鑰。所以，HBKPS方案具有較好的存儲需求性能。

4．2 安全性

假設攻擊者俘獲無線傳感器網(wǎng)絡中的節(jié)點時，都能獲取這些節(jié)點中的所有密鑰信息。在HBKPS方案中用被俘獲的網(wǎng)絡通信鏈路比例來衡量無線傳感器網(wǎng)絡的安全性。當無線傳感器網(wǎng)絡中有x個節(jié)點被俘獲時，其被俘獲的網(wǎng)絡通信鏈路的比例由式(11)定義[15]:

在式(11)中，|S|是整個密鑰池的大小，即10 000。而在HBKPS方案中，為了更好的反應被俘獲網(wǎng)絡通信鏈路的比例，把|S|定義為已經(jīng)分配了的密鑰總數(shù)，而不包括沒有被分配的密鑰數(shù)量，這樣能更真實的反應其安全性。定義如下:

由圖1部署的網(wǎng)絡模型可以看出，在HBKPS方案中，相互通信范圍內(nèi)節(jié)點之間的最大部署距離D為:

由式(13)可得出，在HBKPS方案取不同r(m)和L(m)值時的部署距離D如表2所示。

從表2可以看出，在HBKPS方案中，部署距離D小于3就可以基本滿足網(wǎng)絡的連通概率需求。假設L=20，r=20，由表2可以得出在 HBKPS方案中節(jié)點不移動的情況下D=1。

表2 取不同r和L時得出的D

當n=100時，由式(1)～式(3)和式(9)可以得出在HBKPS方案中滿足網(wǎng)絡的連通概率需求時的最小h如表3所示。

表3 取不同m時得出的最小h

在HBKPS方案中，假設L=20，r=20，由表3也可以得出在節(jié)點不移動的情況下D=1，在移動距離小于2L的情況下D=3。

由HBKPS密鑰預分配過程可以得出，在HBKPS方案中已經(jīng)被分配的密鑰總數(shù)為圖1中非白色背景顏色的區(qū)域，因為其他區(qū)域的密鑰都是從這些區(qū)域中進行分配的。

除了區(qū)域(2，1)中的全部n個密鑰是從主密鑰池中選取的，其他非白色背景顏色區(qū)域的n個密鑰中只有n－h(huán)個密鑰是從主密鑰池中選取，剩下的h個密鑰都是從已分配的區(qū)域中選取的。由圖1可以得出非白色背景顏色的區(qū)域總數(shù)約為:

所以當m=100，L=20時，在HBKPS方案中已經(jīng)被分配的密鑰總數(shù)|S|為:

在HBKPS方案中，由于每個分組中的非源節(jié)點從該分組中的源節(jié)點的密鑰中隨機選取m個密鑰，所以當被俘獲節(jié)點部署距離為D時，式(12)中被俘獲節(jié)點的平均密鑰數(shù)約為:

最后，由式(12)可得，在HBKPS方案中，當有x個節(jié)點被俘獲時，其被俘獲的網(wǎng)絡通信鏈路的比例為:

由式(14)和式(15)，n=100，L=20，D=1 得:

在HBKPS方案的安全性能仿真將采用表3中的參數(shù)，由式(16)得出被俘獲的網(wǎng)絡通信鏈路的比例如圖5所示。

圖5 HBKPS方案的安全性

從圖5中所示可以看出，在HBKPS方案中，當x=20，m=0．9n 和 x=20，m=0．7n 時，網(wǎng)絡中被俘獲網(wǎng)絡通信鏈路的比例僅為0．056 4和0．021 1。所以在HBKPS方案中，網(wǎng)絡被俘獲網(wǎng)絡通信鏈路的比例較理想。如果網(wǎng)絡中傳感器之間的共同密鑰越多，則該網(wǎng)絡的連通概率就越高，所以該網(wǎng)絡的安全性也將更低，因為被俘獲的密鑰中有更多的密鑰還在未被俘獲傳感器之間應用。因此，通過以上HBKPS方案的性能分析可知，HBKPS方案較適合應用在安全要求不是太高，而對連通概率要求很高的網(wǎng)絡環(huán)境中。

5 結論

本文提出的基于部署信息的無線傳感器網(wǎng)絡隨機密鑰預分配方案:基于正六邊形區(qū)域劃分的隨機密鑰預分配方案HBKPS。其核心思想是利用部署信息來進行區(qū)域劃分，使其更適應于無線傳感器網(wǎng)絡。數(shù)據(jù)分析和仿真結果表明，HBKPS方案中無論無線傳感器網(wǎng)絡部署的傳感器數(shù)量有多大，面積有多廣，只要某些參數(shù)滿足一定的要求，所有節(jié)點之間直接共享一個密鑰的概率均為1，從而降低了在其他方案中因密鑰協(xié)商帶來的通信負載。即使在保證比其他方案更高連通概率的情況下，也只需更小的存儲空間。綜上所述，HBKPS方案具有很高的連通概率，能有效減小節(jié)點的存儲空間，并具有較好的擴展性。不過針對HBKPS方案，還有些問題需要繼續(xù)深入研究，如怎樣優(yōu)化部署信息中參數(shù)才能同時具有更好的網(wǎng)絡連通性和安全性等。

[1]Lynch K M，Schwartz I B，Yang P，et al．Decentralized Environmental Modeling by Mobile Sensor Networks[J]．IEEE Transactions on Robotics，2008，24(3):710－724．

[2]Bertsekas D P，Tsitsiklis J N．Comments of Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules[J]．IEEE Transactions on Automatic Control，2007，52(5):968－969．

[3]祁榮賓，李思瑾，馬天義，等．基于迭代的無線傳感器網(wǎng)絡三維定位算法[J]．傳感技術學報，2012，25(5):645－650．

[4]Lu K，Qian Y，Guizani M，et al．A Framework for a Distributed Key Management Scheme in Heterogeneous Wireless Sensor Networks[J]．IEEE Transactions on Wireless Communications，2008，7(2):639－647．

[5]Song C，Cao J N，Liu M，et al．Maximizing Network Lifetime Based on Transmission Range Adjustment in Wireless Sensor Networks[J]．Computer Communications，2009，32(11):1316－1325．

[6]Ye Z，Abouzeid A A，Ai J．Optimal Stochastic Policies for Distributed Data Aggregation in Wireless Sensor Networks[J]．IEEE/ACM Transactions on Networking，2009，17(5):1494－1507．

[7]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．

[8]Ozdemir S．Functional Reputation Based Reliable Data Aggregation and Transmission for Wireless Sensor Networks[J]．Computer ＆Communications，2008，31(17):3941－3953．

[9]潘巨龍，高建橋，徐展翼，等．一種基于確定性理論的無線傳感器網(wǎng)絡信任機制 nTRUST[J]．傳感技術學報，2012，25(2):240－245．

[10]Kong B B，Chen H Y，Tang X H，et al．Key Pre－Distribution Schemes for Large－Scale Wireless Sensor Networks Using Hexagon Partition[C]//IEEE Wireless Communications and Networking Conference，WCNC，2010:1－5．

[11]嚴雪莉，葉曉慧．一種基于六邊形部署模型的面向傳感器網(wǎng)絡的隨機密鑰預分配方案[J]．計算機應用研究，2012，29(4):1457－1461．

[12]代航陽，徐紅兵．基于六邊形網(wǎng)格部署模型的傳感器網(wǎng)絡密鑰管理[J]．電子測量與儀器學報，2008，22(5):48－52．

[13]Zhang J，Varadharajan V．Wireless Sensor Network Key Management Survey and Taxonomy[J]．Journal of Network and Computer Applications，2010，33(2):63－75．

[14]Yu Z，Guan Y．A Key Management Scheme Using Deployment Knowledge for Wireless Sensor Networks[J]．IEEE Transactions on Parallel and Distributed Systems，2008，19(10):1413－1420．

[15]Du W，Deng J，Han Y S，et al．A Key Management Scheme for Wireless Sensor Networks Using Deployment Knowledge[C]//Pro of the IEEE Infocom．Piscataway:IEEE Press，2004:586－597．