基于非均勻分簇的HWSN密鑰預分配方案的研究

黃慧娟，許 勇，張 海

(安徽師范大學 數學與計算機科學學院，安徽 蕪湖 241003)

基于非均勻分簇的HWSN密鑰預分配方案的研究

黃慧娟，許 勇，張 海

(安徽師范大學 數學與計算機科學學院，安徽 蕪湖 241003)

密鑰管理問題一直是無線傳感器網絡中的熱點研究問題之一。針對傳統的密鑰預分配方案具有能量不均衡以及網絡生存周期短的問題，文中設計了一種新的基于分簇結構的異構傳感器網絡的密鑰預分配方案(New Clustering In Key Pre-distribution，NCIKP)。詳細給出了簇首選擇過程、非均勻分簇過程以及密鑰預分配過程,在選擇簇首時將同時考慮節點的能量消耗率、節點到基站的距離以及節點的鄰接程度。通過仿真實驗與分析，相較其他的密鑰預分配方案，此方案較好地滿足了異構傳感器網絡的安全和能耗需求。

異構傳感器網絡;非均勻分簇;密鑰預分配;能量均衡

0 引 言

隨著無線傳感器網絡(Wireless Sensor Networks,WSN)[1]的應用發展，WSN的安全通信日益受到關注。傳感器節點通常被隨機置于無人監聽環境之中，易遭受竊聽威脅，也容易被捕獲和破壞，這使得一些常用加密體系中的密鑰管理方法(如公鑰加密體系)不再適用于傳感器網絡。目前，在WSN安全通信中，較為普遍使用的是密鑰預分配方案[2-9]。根據WSN構造形態，可將其分為異構傳感器網絡(Heterogeneous Wireless Sensor Networks，HWSN)和同構傳感器網絡。同構傳感器網絡的密鑰預分配方案的研究已有很多成果[3-6]，相對而言，針對異構傳感器網絡的密鑰預分配方案[8-9]還比較少。

文中主要關注異構傳感器網絡中的密鑰預分配問題。因異構傳感器網絡中節點具有能量差異性，在進行密鑰預分配過程中，若不進行節點能量的均衡與優化，則可能導致部分節點過早耗盡能量而失效。因此文中設計了一種新的基于分簇結構的異構傳感器網絡密鑰預分配方案(New Clustering In Key Pre-distribution，NCIKP)，采用二級網絡結構,綜合考慮節點的能量消耗率、節點到基站的距離以及節點的鄰接程度選擇簇首,用以均衡節點的能量消耗；同時，簇首節點通過競爭形成不同半徑的簇,以防止“熱區”的出現；在此基礎上分別對簇首節點以及簇內節點進行密鑰預分配。

仿真實驗表明，該方案具有較好的安全性能，有效提高了網絡能量利用率,延長了網絡生存周期。

1 相關工作

密鑰預分配一直是無線傳感器網絡安全研究領域的一個研究熱點。對于同構無線傳感網絡,2003年，Eschenauer和Gligor[3]提出了最經典的E-G方案,其基本思想是：每個節點從一個大的密鑰池中隨機分配一些密鑰來構成自己的密鑰環，需要通信節點之間通過發現彼此密鑰環中的公共部分來確定共享密鑰，然后選擇一個作為其會話密鑰。該方案由于不需要任何先驗信息，所以安全性一般；隨后Chan等[4]在E-G方案上進行改進，提出了q-composite方案，將2個節點之間共享密鑰數提高到q個，增強了安全性；Du等[5]提出了一種根據節點部署信息的密鑰預分配方案,有效提高了網絡的連通性；2013年，王小剛等[6]提出了一種基于二次型的無線傳感器網絡密鑰管理方案，該方案利用二次型正交對角化特性建立會話密鑰，提高了安全性和可擴展性。

關于異構無線傳感器網絡，早在2002年，Duarte等[7]就指出了對比傳統的同構無線傳感器網絡，異構傳感器網絡具有更長的生命周期和可測性。據此，馬春光[8]等于2009年提出了一種基于區域的異構無線傳感器網絡密鑰預分配方案。該方案將網絡監測范圍劃分為多個區域，同時將密鑰池也劃分為多個子密鑰池，在一定程度上提高了相鄰節點共享密鑰的概率，但是密鑰池的劃分較為復雜;2010年，馬春光等[9]又提出了一種基于按對平衡設計的異構無線傳感器網絡密鑰預分配方案。該方案針對網絡中節點的異構性，利用按對平衡設計構造了不同的節點密鑰環，增加了網絡的連通性，有效降低了網絡的通信負載。但上述方案僅實現了安全的密鑰預分配，沒有考慮不同節點的能量差異性，在實際運行中，部分節點可能因能量過早耗盡而引起失效。

針對這個問題，研究者們給出一種分簇算法，通過合理構造分簇結構，將在實現安全通信的同時，也能達到均衡網絡能量消耗及延長網絡壽命的目的。經典的分簇算法有LEACH[10]、HEED[11]等，但這些算法在選擇簇首節點時隨機性比較大，而且在能量節省方面也考慮不夠；2007年，陳貴海[12]等提出一種非均勻分簇路由機制(EEUC)。該算法考慮到了節點剩余能量這一因素，實現了節點間的能量消耗平衡，但仍沒有解決簇首節點選擇時隨機性較大的問題。2006年，卿利等[13]提出了一種異構傳感器網絡的分布式能量有效成簇算法(DEEC)。該算法將節點剩余能量作為選擇簇首節點的主要因素，并且給出了計算最優簇頭公式以及優化簇頭比例公式,可是該算法沒有考慮到節點在網絡中所處的位置，僅以節點剩余能量為依據，存在靠近基站的節點由于承擔過多的任務而過早能量耗盡的問題。2014年，劉唐等[14]提出了一種異構傳感器網絡的分簇算法(DUBP)。該算法首先利用能耗因子進行動態分區，再利用Floyd算法計算節點的路徑因子，隨后進行分簇。算法在一定程度上延長了網絡壽命，但僅考慮普通節點間的能量消耗，卻未考慮到簇首間的能量均衡。

總體上說，現有的分簇算法存在的問題主要有兩點:一是在簇首選擇時考慮的因素不夠全面，具有較大的隨機性，存在部分節點過早能量耗盡的問題；二是鮮有考慮到簇首節點間的能量均衡，使得靠近基站的簇首不僅要承擔本簇的數據融合任務，且要為其他簇進行數據轉發，即存在“熱區”問題。

2 NCIKP方案設計

通過對傳統的密鑰預分配方案的研究，針對其在進行安全通信時未能很好地實現節點能量均衡的問題，給出了一種解決方案，即設計了一種針對異構傳感器網絡的基于分簇結構的密鑰預分配方案。

2.1 基本假設

該方案假設共有N個傳感器節點，隨機分布在一個W*W的正方形區域內，所有的節點是靜止或者是微移動的，從而避免網絡拓撲結構頻繁改變。

表1為方案中的符號及其意義。

2.2 分 簇

2.2.1 分簇準備

定義1(節點到基站的距離)：

(1)

定義2(節點的鄰接程度)：與節點i之間的跳數不超過2跳的節點都是i的相鄰節點。

(2)

定義3(節點的能量消耗率)：

(3)

定義4(節點權值)：

w(i)=di,BS*a+N(i)*b+v(i)*(1-a-b)

(4)

2.2.2 簇首選擇

(1)閾值T(n)的推導。

表1 方案中的符號及其意義

文獻[13]提出計算優化簇頭的公式：

優化簇頭比例為：

假設形成的簇共有L個節點，除去簇首節點，簇內還有L-1個節點，則簇內節點到基站的平均距離可表示為：

結合式(3)可推出簇內節點的平均損耗率為：

結合式(2)可推出簇內節點的平均相鄰節點數目為：

綜合上述分析，這里給出更適合異構傳感器網絡的節點成為簇首節點的概率公式：

(5)

在LEACH給出的閾值T(n)計算公式的基礎上進行改進，得到新的閾值計算公式：

T(i)=

(6)

其中，G為最近1/P輪中還未當選簇首的節點的集合；r為節點連續未當選簇首節點的輪數，一旦當選，將r重置為0。

(2)簇首節點產生流程。

①通過節點與節點間、節點與基站間發送消息，每個節點分別算出自己到基站的距離、自己的鄰接節點數、能量損耗速率即di,BS,N(i)以及V(i)。

③節點根據式(6)計算成為簇首節點的概率門限閾值T(i)。

⑤其余節點在本輪競爭結束前都保持睡眠狀態，在本輪競選結束后，下一輪競選按照上述四個步驟重復進行。

2.2.3 分簇形成

(1)簇半徑計算公式。

文中采用文獻[12]中節點的競爭半徑公式：

(7)

其中，dmax為網絡中節點距離基站BS的最遠距離；dmin為網絡中節點距離基站BS的最近距離；C為0-1之間的一個常數；Rmax為網絡中允許的最大競爭半徑。

(2)每輪非均勻成簇流程。

①節點計算自己成為簇首的概率p(i)以及閾值T(i)。

③臨時簇首節點廣播自己的標識號ID，競爭半徑Ri以及權值w(i)。

④若節點j收到i發送來的消息，便開始接下來的判斷。

⑤若滿足d(i,j)

⑥i檢查是否本簇中所有節點的權值都小于自己的權值，若是，則廣播一條消息BEHEAD_MSG(ID)給所有相鄰的臨時簇首節點，通知自己成為本輪簇首。

⑦若i收到本簇中節點j成為簇首的廣播消息，則i必須放棄本輪簇首的機會，然后廣播一條退出消息QUIT_MSG(ID)。

⑧若i收到一條來自簇中j的退出請求消息QUIT_MSG，則立刻將j從簇中刪除。

⑨在每輪簇首節點競爭結束后，其余普通節點就從睡眠狀態恢復過來，所有的簇首節點廣播一條CH__MSG到全網，普通節點判斷收到的來自不同簇首節點的消息，選擇加入一個信號最強的簇中，然后給該簇首節點發送消息JOIN_CH_MSG,通知其自己成為它的簇成員。此時該輪的成簇過程完成。

2.3 密鑰預分配

此階段包括四個部分：基站為簇首分配密鑰、簇首為簇內節點分配密鑰、同一簇內節點的通信、不同簇內節點的通信。

2.3.1 基站為簇首分配密鑰

基站產生一個密鑰池S，為每一個密鑰分配一個唯一的編號KID；在上面階段通過競爭當選簇首的節點向BS發送Cki,BS(ID,di,BS)，告知基站自己成為了簇首；基站根據di,BS來給簇分配一個唯一的編號CID(di,BS越小，CID越小)；簇首節點廣播消息(CID,ID)來發現自己的鄰接簇，發送給基站自己鄰接簇的CID，讓基站知道整個網絡的簇首之間的相鄰關系；基站根據簇首的鄰接簇數目以及鄰接簇已分配密鑰的情況為每個簇分配一定的密鑰，構成自己的密鑰池。

2.3.2 簇首為簇內節點分配密鑰

簇首生成本簇內的會話密鑰CHK，簇首節點從上面分配得到的密鑰池中隨機選擇r個密鑰分配給簇內節點，構成節點的密鑰環，分配的密鑰數不宜過多也不宜過少，過少會出現“孤立點”，從而導致通信困難；過多可能會造成單個節點被捕，整個網絡癱瘓的危險。

2.3.3 同一簇內節點的通信

2.3.4 不同簇內節點的通信

為安全起見，規定不同簇內節點通信必須選擇簇首節點作為中間節點。假設2個位于不同簇的節點i,j想要通信，它們分屬的簇頭分別為C1,C2，若2個節點間有k1,k2,…,kL個相同密鑰，則利用hash函數計算，得到hash(k1‖k2‖…‖kL),來作為二者的共享密鑰Ki,j，節點i用Ki,j將要發送的數據進行加密，得到EKi,j(數據)，然后用CHK1進行第二次加密，即把ECHK1{EKi,j(數據)}發送給C1，C1用CHK1解密，得到EKi,j(數據)；C1用其與C2的密鑰KC1,C2加密EKi,j(數據)，隨后發給C2；C2用KC1,C2解密，然后用CHK2加密得到ECHK2{EKi,j(數據)}，發給j,j隨后兩次解密得到原始數據，通信完成。

3 安全性分析及性能分析

3.1 安全性分析

在該方案中，簇首節點需要向基站注冊自己的身份以及鄰接簇情況，因此即使一個簇首被攻擊者冒充，也會立即被基站檢測出來；基站根據簇首鄰接簇情況為其分配密鑰，隨后簇首再從自己的密鑰池中隨機取部分密鑰分配給簇內節點，因此不同節點被分配到相同密鑰的概率較低；在同一個簇內節點通信時，若采用以往算法中通過廣播節點密鑰來建立會話密鑰的方法，則會增加被攻擊的概率，因此該方案中同簇節點建立會話密鑰時采用節點取自己的密鑰來加密一個隨機數和本簇標識號并與其他節點加密結果比較的方法，提高了安全性；此外該方案規定，在不同簇內節點通信時必須經過簇首節點的轉發，進行二次加密，可以保證即使一個簇被攻擊，也不會影響到其他簇的安全，且利用了hash函數的單向性，有效防止攻擊者從單個節點的密鑰來推算出節點間的通信密鑰。

3.2 性能分析

利用Matlab對文中分簇算法與LEACH和EEUC協議進行性能比較分析。采用文獻[10]中提出的無線通信系統能量消耗模型來進行計算。

(1)傳送一個l bit的數據包到距離d的節點需耗費的能量為：

(2)接收一個lbit字節的數據包需要的能量為：

ERx(l)=lEelec

表2為仿真采用的參數表；圖1為仿真場景圖。

表2 仿真參數表

圖1 200個節點隨機布于200 m*200 m的區域

死亡節點個數和網絡剩余能量隨著進行的輪數變化情況比較見圖2和圖3。

4 結束語

文中設計了一種針對異構傳感器網絡的基于分簇結構的密鑰預分配方案(NCIKP)。在該方案中，首先給出了一種新的分簇算法，該算法可以有效地均衡節點間的能量消耗；在密鑰預分配過程中，將分別對簇首節點和簇內節點進行預分配，以降低節點被分配到相同密鑰的概率；同一簇內節點在建立會話密鑰時，只需隨機取一個密鑰加密一個隨機數以及本簇標識號，并與其余節點加密結果相比較即可，避免了廣播密鑰帶來的被攻擊的風險；不同簇節點通信時，規定必須經過簇首節點的轉發，進行二次加密，因此即使一個簇被攻擊，也不會影響到其他簇的安全，此外還加入了Hash函數，利用其單向性來進一步提高網絡的安全性。

圖3 網絡剩余能量隨著進行的輪數變化情況比較

通過仿真實驗表明，該方案具有較強的安全性，此外獲得了更好的能量利用率以及更長的網絡生命周期。

方案暫未考慮到異構傳感器網絡中節點的移動性這一問題，此外如何降低節點的計算和存儲開銷也將是下一步工作研究的重點。

[1] 蘇金樹,郭文忠,余朝龍,等.負載均衡感知的無線傳感器網絡容錯分簇算法[J].計算機學報,2014,37(2):446-456.

[2] 孫力娟,魏 靜,郭 劍,等.面向異構無線傳感器網絡的節點調度算法[J].電子學報,2014,42(10):1907-1912.

[3]EschenauerL,GligorVD.Akey-managementschemefordistributedsensornetwork[C]//Procof9thACMconfoncomputerandcommunicationsecurity.Washtington,DC,USA:ACM,2002:41-47.

[4]ChanH,PerrigA,SongD.Randomkeypre-distributionschemeforsensornetworks[C]//ProceedingsofIEEE2003symposiumonsecurityandprivacy.Berkeley,CA,USA:IEEE,2003:197-210.

[5]DuW,DengJ,HanY.Akeymanagementschemeforwirelesssensornetworksusingdeploymentknowledge[C]//ProceedingsofIEEEINFOCOM’04.HongKong,China:IEEE,2004:586-597.

[6] 王小剛,石為人,周 偉,等.一種基于二次型的無線傳感器網絡密鑰管理方案[J].電子學報,2013,41(2):214-219.

[7]Duarte-MeloeJ,LiuMY.Analysisofenergyconsumptionandlifetimeofheterogeneouswirelesssensornetworks[C]//ProceedingsofIEEEGLOBEC-OM.Taipei:IEEE,2002:21-25.

[8] 馬春光,尚治國,王慧強.基于區域的異構無線傳感器網絡密鑰管理[J].通信學報,2009,30(5):74-81.

[9] 馬春光,張秉政,孫 原,等.基于按對平衡設計的異構無線傳感器網絡密鑰預分配方案[J].通信學報,2010,31(1):37-43.

[10]HeinzelmanW,ChandrakasanA,BalakrishanH.Anapplication-specificprotocolarchitectureforwirelessmicrosensornetworks[J].IEEETransactionsonWirelessCommunications,2002,1(4):660-670.

[11]YounisO,FahrnyS.Heed:ahybird,energy-efficient,distributedclusteringapproachforad-hocsensornetworks[J].IEEETransonMobileComputing,2004,3(4):660-669.

[12] 李成法,陳貴海,葉 懋,等.一種基于非均勻分簇的無線傳感器網絡路由協議[J].計算機學報,2007,30(1):27-36.

[13]QingLi,ZhuQingxin,WangMingwen.Adistributedenergy-efficientclusteringalgorithmforheterogeneouswirelesssensornetworks[J].JournalofSoftware,2006,17(3):1282-1291.

[14] 劉 唐,孫彥清.基于負載均衡和最短路徑的異構無線傳感器網絡成簇算法[J].計算機科學,2014,41(10):169-172.

[15] 劉 唐，汪小芬，楊 進.基于相對距離的多級能量異構傳感器網絡成簇算法[J].計算機科學,2012,39(8):119-121.

Research on Key Pre-distribution Scheme for Heterogeneous Wireless Sensor Networks Based on Unequal Clustering

HUANG Hui-juan,XU Yong,ZHANG Hai

(College of Mathematics and Computer Science,Anhui Normal University,Wuhu 241003,China)

The key management is always one of hot topics in wireless sensor network.For many traditional key pre-distribution scheme with energy imbalance and network short lifetime problem,a new cluster-based key pre-distribution scheme (New Clustering in Key Pre-distribution,NCIKP) for Heterogeneous Wireless Sensor Networks (HWSN) is proposed.The cluster head selection process,unequal clustering process and key pre-distribution process are given in detail.In the selection of cluster head,also consider node energy consumption rate,node distance to the base station and node adjacency degree.According to the simulation experiment,compared with other key pre-distribution scheme,it’s better to meet the security and consumption demand for HWSN.

heterogeneous wireless sensor networks;unequal clustering;key pre-distribution;energy balance

2015-04-03

2015-07-08

時間：2016-01-04

安徽省自然科學基金資助項目(11040606M137)

黃慧娟(1990-)，女，碩士研究生，研究方向為計算機網絡與信息安全；許 勇，博士，教授，碩士生導師，研究方向為計算機網絡與信息安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20160104.1608.078.html

TP393

A

1673-629X(2016)02-0077-05

10.3969/j.issn.1673-629X.2016.02.018