一種基于Shamir的安全WSN分簇路由協議設計*

戴國勇，呂何新，丁健龍，趙 方，毛科技，彭 豐

(1.浙江樹人大學信息科技學院，浙江 杭州 310015；2.浙江工業大學計算機科學與技術學院，浙江 杭州 310023；3.衢州華數廣電網絡有限公司，浙江 衢州 324000)

無線傳感器網絡(Wireless Sensor Networks，WSNs)是物聯網的一項重要技術，由大量具有計算能力、通信能力和數據處理能力的傳感器節點，通過無線自組織的形式構成的網絡[1-2]。路由技術是無線傳感器網絡除節點定位、網絡覆蓋、能量管理和隱私保護等問題外的一個重要研究方向[3]。一種良好的路由技術能夠提供可靠的數據轉發、較好的能耗均衡以及安全的數據路由[4]。由于傳感器網絡部署的環境復雜，傳感器節點更換電池困難，當節點負載不均衡時，負載大的節點消耗的能量多，死亡較快，從而導致網絡過早失效。在無線傳感器網絡中，惡意節點可偽裝成網絡內的成員節點破壞網絡或者竊取網絡數據，給WSN帶來安全威脅，因此路由協議設計時需考慮數據安全性。

無線傳感器網絡路由協議主要分為兩種，一種是鏈式路由協議，另一種是層次路由協議[5]。其中鏈式路由協議在數據流量較大時容易導致鏈路擁塞，因此適合應用于小規模的網絡中。而層次路由協議是一種劃分區域的路由協議，適用于大規模的網絡。分簇路由協議作為層次路由協議的一種，具有較好的能耗均衡性，被廣泛地應用于無線傳感器網絡路由中。LEACH(low energy adaptive clustering hierarchy，LEACH)路由協議[6]首次提出了分簇思想，該協議分為簇建立階段和穩定階段，在簇建立階段通過循環方式隨機選擇簇頭節點，將網絡能耗平均分配至每個節點，從而在一定程度上提高網絡能耗均衡性，延長網絡整體生存時間。通過隨機方式選擇簇頭可能導致能量較低的節點作為簇頭，造成能耗不均勻。文獻[7]將LEACH改進為一種節能多跳路由協議，對LEACH簇的創建、數據傳輸以及簇的更新等階段進行了修改，然而該方法構造的多跳路徑是未優化的，從而容易導致路由中斷。

在網絡可靠性方面，文獻[8]提出了一種負載均衡和數據收集算法，該算法節約了能耗，提高了數據聚合和轉發方面的性能。然而通過多跳的方式進行數據傳輸，提高了通信成本。文獻[9]提出了基于鏈的路由協議(Chain-chain based routing protocol，CCBRP)，CCBRP集成了傳感器信息系統(PEGASIS)的過濾和能量高效收集功能，將整個節點安排到不同的鏈中。CCBRP提供了一個混合方案，并在兩個不同的階段執行所構建的鏈。該協議的主要問題是隨著網絡規模的增大而帶來的高能耗和高延遲。因此，由于可擴展性的限制，CCBRP不適合于大規模網絡。文獻[10]提出了LEACH-MAC協議，改進了LEACH協議隨機產生簇頭節點導致能耗不均的問題，該方法通過控制簇頭數量為一定數值，提高網絡生存時間。文獻[11]提出了LEACH-ER協議，通過能量和數據可靠性因子選擇簇頭，該協議通過降低簇頭和成員節點之間的簇內部數據包的接收速率，從而提高網絡壽命和能源效率。然而該協議并未對路由進行優化，容易導致數據重傳和路由中斷，可靠性有所欠缺。

在路由數據安全性方面，文獻[12]提出的大規模無線傳感器網絡的可靠且節能的數據收集方法，在熱點區域，選擇較少的節點來捕獲信息，而在非熱點區域則選擇較多的監控節點。然而，所提出的解決方案忽視了數據安全，在惡劣復雜的環境中，將會給網絡帶來安全性問題。文獻[13]提出了三因素認證方法，為無線傳感器網絡提供了數據安全保障，提出的方法在節點之間提供了適當的相互認證，但是在認證過程中消耗了不必要的能量，降低了網絡的生存期。文獻[14-15]使用Shamir加密共享方案設計無線傳感器網絡數據加密方法，為網絡數據提供了安全的傳輸環境，具有一定的代表性。

針對目前無線傳感器網絡路由協議存在安全性不高、網絡可靠性差等問題，提出了一種安全可靠的WSN路由協議(Shamir-based Secure Reliable Routing，SSCRP)，在簇頭的選舉中對節點剩余能量、信號強度以及節點到基站的最短路徑長度等進行綜合考慮，考慮到惡意節點的加入，網絡使用Shamir密鑰共享算法對數據進行加密，當網絡工作一段時間后進行簇首的輪換。該協議能夠在保證數據安全性的情況下，提高網絡能耗的均衡性以及網絡的可靠性。

1 網絡能耗模型

1.1 網絡相關假設

假設1 網絡采用星型網絡架構，即網絡內所有節點可以直接與基站通信。

假設2 基站由服務器供電，能量充足有足夠處理能力。

假設3 無線傳感器網絡內節點同構，初始能量相同都為E0。

假設4 網絡內節點的通信半徑為r，在通信半徑內節點通信穩定。

1.2 節點能耗模型

節點通信時，節點發送數據和接收收據時都需要消耗能量，其中節點通信能耗模型如圖1所示。發送數據能耗和接收數據能耗如式(1)和式(2)所示。

圖1 節點通信能耗模型

式(1)、式(2)中:Ee表示數據在發送和接收時每處理1 bit數據時消耗到的能量；Eamp表示功率放大電路的系統；k表示數據包的位數；d表示數據傳輸距離；dt是距離閾值。

2 路由協議設計

SSCRP協議的主要步驟為:①簇頭選擇與成簇:根據節點剩余能量、接收信號強度、節點與基站的最短路徑長度以及節點的負載率等因素，進行簇頭節點的選擇，網絡內節點全部加入相鄰簇頭形成簇。②數據加密傳輸:基站使用Shamir密鑰共享算法給網絡內所有節點發送密鑰，驗證節點是否為非法節點。③簇頭輪換:利用簇頭輪換方法更新簇頭，實現網絡能耗的均衡性，提高網絡數據傳輸的可靠性。

2.1 簇頭選擇與成簇

在初始階段，節點被隨機部署于正方形的網絡區域內，每個節點都保持靜態，且具有唯一的ID。基站向網絡區域內的所有節點通過多跳的方式廣播其位置，節點接收到數據后通過合并鄰居節點的信息更新自身的路由表。接著在網絡區域內以分散的方式發布簇頭選擇機制。由于簇頭節點不僅需要處理簇內成員節點的數據，還需要轉發其他簇頭的數據至下一跳簇頭節點，所以與簇內成員節點相比需要更多的剩余能量、更強的接收信號強度等。

因此本文提出的簇頭選擇機制，通過節點剩余能量(Eres)、接收信號強度指示(Received Signal Strength Indicator，RSSI)、節點到基站的最短路徑長度(Dsp)以及節點的負載率(LF)等因子，計算所有節點的競爭值CV，競爭值CV越大表示節點出任簇頭的機會越大，就越容易成為簇頭。每個節點通過交換控制消息來接收鄰居節點信息。節點剩余能量(Eres)是影響網絡生存時間最重要的因素，節點的剩余能量越多，表示節點的競爭能量越強，就越容易成為簇頭。接收信號強度指示(RSSI)是衡量無線鏈路質量的一個重要標準，假設節點信標包的接收速率為X，某段時間內，有N個鄰居節點向該節點發送信標數據包，節點能夠順利接收數據包且沒有發生丟失和重傳，則該節點信標數據包的平均接收速率為RSSIth，如式(3)所示，則可將RSSIth作為RSSI的閾值。

當節點的RSSI值小于閾值時，表明鏈路質量低，丟包率上升。當RSSI值大于RSSIth時，能夠提供良好的包接收速率，數據傳輸就越穩定，此時該節點就越容易出任簇頭。當節點至基站的最短路徑長度(Dsp)越小時，數據轉發的次數就越少，能耗就越低，因此盡量選擇最短路徑長度短的節點作為簇頭。節點的負載率(LF)也是影響數據傳遞性能的一個重要標準，節點負載率通過節點此時接收的包的字節數(RP)，以及節點的總緩沖大小(TB，以字節為單位)進行衡量，如式(4)所示。

節點的負載率越小表示該節點此時的處理能力就越強，網絡越不容易擁塞，該節點出任簇頭的概率就越大。

最后，對所有影響因子進行加權，計算出節點的競爭值CV，如式(5)所示。對網絡內所有節點的競爭值進行排序，選舉出前K個CV值最大的節點作為簇頭節點，其中K為網絡內的簇頭節點數量。

式中:w1、w2、w3、w4分別表示影響因子對應的加權值，且權值滿足w1+w2+w3+w4＝1。

當選舉出K個簇首節點時，簇首節點向周圍鄰居節點廣播信號幀，當鄰居節點接收到狀態信息后，都加入至相鄰簇頭以形成簇，由于鄰居節點可能接收到多個簇頭發送的狀態信息，此時鄰居節點將與RSSI值最大的簇頭關聯形成簇。當完成簇的建立之后，為所有的簇分配一個唯一的簇ID，形成簇集合(Scluster＝{c1，c2，…，ck})，以指定簇邊界，所有簇頭節點根據時分多址(Time Division Multiple Access，TDMA)發布信道訪問方案時間表。從而完成整個網絡路由建立。其中具體的路由建立過程如表1所示。

表1 路由建立過程

2.2 簇頭選擇與成簇

為防止惡意節點入侵網絡從而破壞或者竊取網絡數據，提出了基于Shamir密鑰共享算法的數據加密方法。基站生成密鑰S，該密鑰使用Shamir的(t，n)密鑰共享算法將其傳遞給n個簇頭節點，其中簇頭的任意t個子集都能夠重建密鑰S。Shamir密鑰共享算法需要滿足下面兩個條件:

條件1:任意t個或者大于t個子鍵的組合(S0，S1，…，St-1)都能夠重構密鑰S。

條件2:小于t個子集的組合不能重構密鑰S。

在Shamir密鑰共享算法中，利用t-1次多項式對數據進行加密，其中構造的多項式如式(6)所示，假設將S的值賦值給a0，當通過t個子集求解出多項式的系數集合(a0，a1，…，at-1)時即可實現密鑰的重構。

為了實現加密密鑰的重構，需要通過拉格朗日插值公式進行計算，如式(7)所示。

基站將密鑰Si的每個子鍵分配給K個簇頭，簇頭將密鑰發送給簇中的成員節點。當成員節點向簇頭節點轉發網絡數據Di時，將密鑰Si和數據網絡數據Di進行異或操作進行加密，如式(8)所示。

簇頭從成員節點接收到加密數據EDi后，將其傳輸至基站，基站使用解密密鑰S對數據進行解密，最終實現網絡數據的安全傳輸，從而防止惡意節點的侵入給網絡帶來安全性問題。具體的安全數據路由實現步驟如表2所示。

表2 安全數據路由實現過程

2.3 簇頭輪換

由于無線傳感器網絡內，不同區域的簇負載程度不同，負載大的簇頭消耗的資源多，容易因能量耗盡而死亡。為了實現能耗的負載均衡提高網絡整體的生存期，需要動態地輪換簇內的簇頭。當出現以下情況時需要進行簇頭輪換:

情況1當簇頭接收到網絡數據包時，首先判斷是否已經接收到相同的數據包，如果是，則丟棄該數據包，以減少網絡擁塞和能耗。如果接收到的是一個新的數據包，簇頭將會判斷自身的剩余能量是否充足，即是否滿足Eresi≥Ethreshold(其中Ethreshold是簇頭所在的簇的所有節點的平均能耗)，如果不滿足則不進行數據包轉發，此時在簇內計算所有成員節點的競爭值CV，并將CV值最大的節點作為該簇新的簇頭節點。

情況2計算每個簇的擁塞率Cr，如式(9)所示。不斷地檢查擁塞率Cr的值，當檢查到Cr的值不在[0，1]范圍內時，表明該簇的簇頭已經出現了網絡擁塞，此時需要利用2.1中的方法重新進行網絡內簇頭的選擇，實現新一輪簇頭的輪換。其中簇頭輪換的具體實現如表3所示。

表3 簇頭輪換過程

式中:ADR表示數據包之間到的平均延遲率；ARR表示數據包的平均接收效率。

3 仿真實驗分析

在i7處理器、8 G內存的PC機中利用NS2仿真平臺對本文提出的WSN路由協議進行性能分析。將不同數量的節點隨機部署于正方形區域內，其中包含了10個惡意節點，惡意節點通過廣播錯誤的路由數據包，以便被選作數據轉發的下一跳。其中仿真參數如表4所示。

表4 仿真參數表

3.1 權重因子影響

為了衡量本文提出的SSCRP協議在不同加權值情況下對網絡性能的影響，將100個傳感器節點隨機部署于100 m×100 m的區域內，網絡參數按照表4設置，將不同加權值參數分為三組:組1權值配置為w1＝0.1、w2＝0.5、w3＝0.3、w4＝0.1；組2配置為w1＝0.2、w2＝0.1、w3＝0.1、w4＝0.6；組3配置為w1＝0.5、w2＝0.3、w3＝0.1、w4＝0.1；對這三組配置進行能耗、路由中斷次數和數據包傳遞率分析。結果如圖2~圖4所示。

圖2 簇頭節點個數與網絡能耗關系

圖4 簇頭節點個數與數據包投遞率關系

從圖2~圖4可以看出，不同權值情況下，選舉的不同簇頭對網絡的能耗、網絡中斷次數以及數據包投遞率都有相應影響。從圖2中可以看出分配給剩余能量(Eres)權重值最大的組3，網絡能耗最低。因為在簇頭的選舉時，能耗所占權值大，因此對能耗考慮的越充分。從圖3可以看出組1分配給信號強度(RSSI)的權值最大，路由中斷次數最少。因為當節點信號強度較大時，表明此時節點的通信質量高，則此時網絡中斷次數少。從圖4可以看出組2的節點的負載率(LF)占比最大，此時數據包的投遞率最高。原因是當對節點的負載率考慮越充分時，此時節點能夠轉發的數據包能力就越強，則數據包投遞率就越高。

圖3 簇頭節點個數與路由中斷次數關系

3.2 端到端時延分析

為了評估本文提出的WSN路由協議性能，本文以下的實驗部分將其與CCBRP[9]、LEACH-MAC[10]和LEACH-ER協議[11]進行對比。并將簇頭選舉時的權值參數設置為相同，即w1＝w2＝w3＝w4＝0.25。

理論上隨著節點數量的增多，網絡內的流量增大，擁塞情況嚴重，此時端到端的時延就會增大。實驗結果如圖5所示。

圖5 端到端平均延時

從圖5可以看出，隨著節點數量的增多，端到端的延時都在不斷增大，其中本文提出的SSCRP方法平均延時最低，且隨著節點數量的增多網絡流量和網絡負載迅速上升，SSCRP協議具有更低的端到端延遲。原因是SSCRP協議通過自適應的方式形成簇，并根據簇頭的當前性能進行及時輪換，從而減少了路由空洞的出現，降低了數據延遲。

3.3 數據包交付率分析

數據包交付率是評價路由協議性能的重要指標之一，理論上網絡處理能力越強，網絡數據安全性越高，數據包交付率就越高。其中數據包交付率實驗結果如圖6所示。

圖6 數據包交付率

從圖6可以看出隨著節點數量的增多，數據包交付率都在降低，原因是隨著節點數量的增多，網絡流量和網絡負載都在急劇上升，因此導致有些數據包出現擁塞，導致數據包丟失，交付率降低。可以看出本文提出的SSCRP交付率最高，且隨著節點增多，交付率仍維持在較高水平。原因是SSCRP在簇頭選擇時充分考慮了多個因素，優先考慮性能較優的節點出任簇頭，從而生成更加穩定高效的簇。并且SSCRP采用基于Shamir密鑰共享算法的數據加密方法實現了基站和簇頭之間通信時數據包的可靠性，減少了路由的中斷，最終提高數據交付性能。

3.4 節點平均通信成本分析

節點平均通信成本是衡量WSN路由協議性能的一個標準，節點的平均通信成本越低，則該路由協議性能就越優越。其中節點平均通信成本的實驗結果如圖7所示。

圖7 節點平均通信成本

從圖7可以看出隨著網絡節點密度的增大，四種協議的平均通信能耗都在不斷上升，其中本文提出的SSCRP協議的平均通信成本最低，特別在網絡負載增大時，節點的平均通信成本仍維持了較低的水平。是因為SSCRP在簇頭選舉時，對節點的剩余能耗進行充分考慮，當簇的剩余能量不足或者簇的擁塞率大于一定閾值時，進行簇頭輪換。SSCRP采用基于Shamir密鑰共享算法的數據加密方法保證了數據的安全性和可靠性，從而降低了數據包重發次數，降低通信成本。

3.5 網絡生存時間分析

網絡生存時間是衡量路由協議優劣的一個重要標準。在同等條件下，網絡生存時間越長的網絡，表示網絡的能耗均衡性就越好，路由協議就越優秀。其中網絡生存時間實驗結果如圖8所示。

從圖8可以看出，在相同節點密度下SSCRP路由協議的網絡生存時間明顯高于CCBRP、LEACHMAC和LEACH-ER協議。因為當簇頭節點的剩余能量低于簇內成員節點的平均剩余能量時，SSCRP在該簇內重新計算節點競爭值CV，并指定競爭值最大的節點出任簇頭，而不是重新計算整個網絡中節點的競爭值，重新輪換所有簇頭，因此在一定程度上降低了計算時的能耗，提高了整個網絡的生命周期。可以看出LEACH-ER的生命周期最短，雖然LEACH-ER在簇頭選舉時考慮了節點的剩余能耗和RSSI值，但是并沒有考慮到節點與基站的最短路徑長度以及網絡負載率等因素，因此容易導致數據重傳和路由中斷，能耗上升，生命周期縮短。

圖8 網絡生存時間

4 總結

本文基于Shamir密鑰共享算法提出了一種安全可靠的WSN路由協議(SSCRP)，與現有的路由協議相比，在端到端時延、數據包交付率以及網絡生存時間方面都表現出較好的性能。提出了一種優化簇頭的選擇過程，采用分布式策略生成簇，并根據簇頭剩余能耗和簇的擁塞率及時輪換簇頭，使能耗更加均衡。為了防止惡意節點侵入網絡，使用基于Shamir密鑰共享算法的數據加密方法，保護數據從節點到簇頭再到基站這條鏈路的數據安全。下一步的工作，將SSCRP協議應用到實際場景之中，進行性能驗證。