基于正六邊形部署的WSN密鑰預分配方案*

余旺科，王淑華

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

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

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

1 HBKPS區域劃分

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

圖1 HBKPS方案的網絡模型

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

圖2 每個子區域的部署模型

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

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

2 HBKPS方案

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

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

源節點的密鑰分配步驟如下:

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

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

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

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

圖3 已分配的3個源節點的密鑰分布圖

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

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

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

3 密鑰共享分析

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

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

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

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

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

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

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

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

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

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

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

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

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

由式(4)可以得出:

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

4 HBKPS性能分析

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

4．1 存儲需求

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

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

②無線傳感器網絡的節點總數為10 000。

③部署網絡的總面積為1 000 m×1 000 m。

那么整個網絡被劃分的正六邊形區域總數為:

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

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

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

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

4．2 安全性

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

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

由圖1部署的網絡模型可以看出，在HBKPS方案中，相互通信范圍內節點之間的最大部署距離D為:

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 HBKPS方案的安全性

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

5 結論

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

[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]祁榮賓，李思瑾，馬天義，等．基于迭代的無線傳感器網絡三維定位算法[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]潘巨龍，高建橋，徐展翼，等．一種基于確定性理論的無線傳感器網絡信任機制 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]嚴雪莉，葉曉慧．一種基于六邊形部署模型的面向傳感器網絡的隨機密鑰預分配方案[J]．計算機應用研究，2012，29(4):1457－1461．

[12]代航陽，徐紅兵．基于六邊形網格部署模型的傳感器網絡密鑰管理[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．