基于層次混合的高效概率包標記WSNs節點定位算法

周先存 黎明曦 陳振偉 徐英來 熊 焰 李瑞霞

①(皖西學院信息工程學院 六安 237012)

②(中國科學技術大學計算機科學與技術學院 合肥 230026)

③(解放軍陸軍軍官學院六系 合肥 230031)

1 引言

無線傳感器網絡(Wireless Sensor Networks,WSN)是由集感知、計算、通信能力于一身的傳感器節點組成，具有快速部署、實時監測、自組織等特點，能在多種場合滿足環境、商業、軍事等信息獲取的實時性、準確性和全面性的需求[1,2]。由于WSN缺乏明顯的邊界和防火墻之類的安全設施，所有節點均直接暴露在攻擊者面前，很容易遭到敵方入侵和滲透，攻擊者一旦俘獲節點，從內部對網絡發動攻擊，典型的如拒絕服務攻擊等會極大地消耗網絡的能量與帶寬，造成極為嚴重的后果[3]。因此，設計一種在節點能量、計算、存儲等資源有限的條件約束下，迅速溯源定位出惡意節點的算法，從而防止惡意節點對網絡造成更大傷害是非常必要的，對推動WSN的發展應用也具有十分重要的意義。

傳統IP網絡中主要有3種著名的基礎性溯源追蹤技術[4]：日志記錄技術(Logging or Hashbased)[5-8]，基于因特網控制報文協議的技術(ICMP-based)[9]和概率包標記技術(Probabilistic Packet Marking, PPM)[10-17]。日志記錄技術需要路由器有較強的計算和存儲能力，以記錄所轉發數據包的摘要信息，通過查詢記錄信息重構出轉發路徑[18]。這在由普通節點行使路由功能的 WSN中是無法應用的。基于因特網控制報文協議的技術是基于TCP/IP協議棧的，同樣不適用于WSN[4]。概率包標記技術(Probabilistic Packet Marking)是指路由器以一定的概率將身份信息寫入數據包后再對其轉發，接收終端通過收集和分析這些標記，復原出包傳輸路徑。概率包標記技術又分為確定性包標記(DPM)與確定性流標記(DFM)，即使攻擊者從NAT或代理服務器后面的網絡發起攻擊， DFM方法也能追蹤到攻擊者的源IP地址，并且處理與內存開銷小[16]。文獻[17]提出了一種自適應概率包標記方案，其主要思想是：當分組進入首跳路由器時，其TTL值被設置為一個統一的值，當分組在網絡中轉發時，每經過一個中間路由器就將分組TTL值減1，因此，每個中間路由器可以推斷出分組所經過的路由器級的跳數，然后相應地用與路由器級跳數成反比的概率標記分組。該標記方法能快速重構攻擊路徑。文獻[19]將日志記錄技術與概率包標記技術結合起來進行惡意節點定位。總體來看，概率包標記技術由于占用網絡資源少，不影響正常的網絡通信，無需人工參與，對不同協議的通用性強。由于傳感器節點的計算性能和存儲性都十分有限，不滿足傳統網絡安全機制的計算復雜度需求，所以對惡意節點的溯源追蹤多采用概率包標記方法。

文獻[20]提出無線傳感網惡意節點溯源定位的基本概率包標記(BPPM)算法，其基本思想是：節點收到數據包后，按照全網統一概率p決定是否對數據包進行標記。每個被標記過的數據包都保存有部分路徑信息，當匯聚節點收集到足夠數量的包時，就可以追蹤到源節點。該方法標記過程簡單，不會對節點造成過多額外的計算、通訊開銷，但算法收斂性差。假設數據包從節點v到匯聚節點S需要經過d跳，那么匯聚節點收到節點v的標記的概率為A=p( 1 -p)d-1,d值越大，A值越小，因此距離S越遠的節點，其標記被收集到的概率就越低，算法的收斂性越差。文獻[20]中針對此種情況又提出了等概率包標記法(EPPM)，令pj表示到達S需要j跳的節點標記數據包的概率，對于每一個j,pj互不相同，但每個節點標記被匯聚節點收集到的概率都基本相等。該方法對所有節點更加平等，當惡意節點較遠時，也可以更加迅速地將其定位。但該算法要求每個節點存儲并不斷更新自己的路由表，計算各自的標記概率，極大地加重了節點的計算、存儲負擔，對資源嚴格受限的WSN是不適應的。

2 層次式混合概率包標記算法

2.1 算法的基本思想

當傳感器網絡部署后，首先按照一定的算法對網絡進行分簇，通過設定簇的規模，將一定數量的節點劃歸為一個簇，將每個簇看成一個大的“簇節點”，即整個網絡由一些大的“簇節點”構成，每個“簇節點”內部又包含一定數量的傳感器節點，在“簇節點”之間采用等概率包標記法，在“簇節點”內部采用基本概率包標記法，因此稱該方法為層次式混合概率包標記算法(Layered Mixed Probabilistic Packet Marking, LMPPM)，既吸取兩種算法的優點，又相對彌補兩種算法的不足，整個網絡被看成由一些大的簇節點 (V1,V2,…) 構成，每個簇節點內部又包含若干個節點 {V1(v1,v2…),V2(v5,v6… ) ,… } ，數據在節點間轉發時，以簇為單位計算標記概率，簇內節點對其所轉發數據包的標記概率滿足

在 WSN中，分簇結構與平面結構相比，能夠簡化網絡拓撲，優化節點的路由選擇，減少節點間的干擾沖突，既能提高整個網絡的通信效率，又能減少網絡能量的消耗，從而延長整個網絡的生存時間。由于“簇節點”的相對穩定性，又可以保持標記概率的相對穩定性，既減少了節點存儲維護路由表和計算標記概率所產生的能量消耗，又較好的提高了溯源定位算法的性能。

2.2 算法描述

步驟 1 網絡初始化。傳感器節點布撒后自組織成網，根據預設的分簇算法，對節點進行分簇，選舉簇頭。匯聚節點定期向網絡中廣播hello消息，各簇頭根據收到的 hello消息確定自身距匯聚節點的跳數；

步驟 2 確定標記概率。各簇頭節點Vi按PVi= 1 /(c-Di)確定標記概率，其中c是常數，Di表示簇頭節點Vi到匯聚節點的跳數。則匯聚節點收到簇頭節點標記的概率為

即各簇頭節點標記被匯聚節點收到的概率是相等的。簇頭計算出標記概率后在簇內發布，簇內節點立即存儲并使用該標記概率；

步驟3 標記方法。為防止惡意節點相互協作，在數據傳輸過程中修改數據，干擾追蹤結果，引入散列消息驗證碼HMAC，即每個節點占用兩個標記域，一個標記域用來存儲加密后的節點標識，另一個用來存儲相應的HMAC。節點以相應概率決定標記數據包，當標記域至少有兩個為0時，則將自身標識添加到相應位置，當標記域均為非0時，則將標記域全部清空，并依次添加自身標識。

3 算法性能分析

基于文獻[20]中對BPPM算法和EPPM算法的實驗設置，本文著眼于具有大量節點的傳感器網絡實際應用系統(例如寧波citysee系統具有2000個以上的實際部署節點)進行分析。相對于小規模傳感器網絡，當傳感器網絡中包含大量節點時，其對于算法的功耗控制和收斂性有更高的要求，網絡節點數與通信平均傳輸次數之間的關系如圖1所示。

由于無線傳感器網絡在實際應用中多為大規模系統，為更好地對算法性能進行定量分析，文中假設惡意節點到匯聚節點需經過 32次數據轉發(網絡節點規模約為322=1024個)，網絡初始化完成后，這32個中間節點被平均分布在8個簇內。考慮到無線傳感器網絡通常包含數量眾多的節點，該假設作為符合算法模型的一個典型代表，其分析結果并不失一般性。下面從收斂時間、路由器負擔、存儲空間等方面，對BPPM算法，EPPM算法和本文提出的LMPPM算法進行分析比較。

假設iA表示數據包在節點vi處被標記且不被后續的節點所覆蓋并最終到達匯聚節點的概率。在算法BPPM中，根據文獻[20]中給出的概率計算公式np= 2 ，其中n為節點數，可得全網統一概率P=0.0625，則有

在算法 EPPM 中，按公式Pvi= 1 /(c-di),c＞di計算節點標記概率，此處c值取34，則有

根據2.2節中的描述，在LMPPM算法中，顯然有AL32=PV8，

根據2.2節中步驟2,c等于34時，計算出各節點標記概率如表1所示。

表1 節點標記概率表

分別計算LMPPM, BPPM和EPPM 3個算法中ALi,ABi和AEi的值，結果如圖2所示。

節點的標記到達匯聚節點的概率越大，說明匯聚節點重構出到達該節點的路徑所需的數據包越少。從圖2中可以看出，在13號節點之前，LMPPM算法明顯好于BPPM算法，并逐漸趨近于EPPM。以下將進行具體分析：

(1)收斂性 在BPPM中，根據票券收集問題，受害者重構攻擊路徑所需的數據包數量的期望為E(N) ＜ ( lnd+O(1 ))/(p( 1 -p)d-1)，忽略常數項O(1)，分別將3個算法中的各節點標記概率代入上式，計算結果如圖3所示。

從圖3中可以明顯看出，距離匯聚節點越遠，LMPPM 算法的收斂性比 BPPM 算法提升得越明顯，但對距離較近的節點，其期望值略大于BPPM算法，而EPPM算法收斂性則最好。

(2)最弱鏈問題 獲得最弱鏈標記所需接收數據包數量的數學期望計算公式是E(N)PPM=，根據上述分析，3種算法為獲得最弱鏈標記所需接收數據包數量的數學期望分別是

圖1 不同規模無線傳感器網絡的運行特征

圖2 節點標記到達匯聚節點概率圖

圖3 重構攻擊路徑所需數據包數量期望圖

(3)計算與存儲負擔 BPPM 算法中節點只需儲存一個固定概率值，無需更新維護路由以計算自身標記概率，故其計算與存儲負擔最小，EPPM算法需要節點儲存自身路由信息并據此計算各自不同的標記概率，計算與存儲負擔最大。LMPPM 算法則介于兩者之間，相對于BPPM增加了網絡初始化階段的分簇過程，但相對于分簇結構對 WSN整體性能的作用而言，該過程所帶來的能量消耗是完全值得的。網絡初始化完成后，僅需簇頭節點計算標記概率，簇內其它節點只需存儲簇頭發布的標記概率，節點整體的計算負擔相較 EPPM 有明顯的降低，就本文所舉例子來看，降幅約在3/4左右。而且簇結構的相對穩定性，也避免了因節點休眠引起的頻繁更新路由信息所帶來的計算與存儲負擔。

4 簇規模對算法的影響

為進一步研究算法的適用范圍，從節點標記到達匯聚節點的概率、收斂性，最弱鏈3個方面對不同簇規模下算法的性能進行分析。m代表分簇數目，m= 1時相當于整個網絡為一個簇，等同于 BPPM算法，m=32時相當于每個節點即為一個簇，等同于EPPM算法，剛才討論了m=8時LMPPM算法的性能，下面進一步對m值分別等于2,4,16時的LMPPM算法性能進行分析。

4.1 到達匯聚節點的標記概率比較

節點的標記概率以及節點標記到達匯聚節點的概率計算方法與第3節相同，在不同簇規模下分別計算LMPPM, BPPM和EPPM 3個算法中ALi,ABi和AEi的值，得到如圖4所示的計算結果。

分別對應于上一節分析的 BPPM,EPPM,LMPPM算法，可以明顯看出：(1)不論簇規模大小，使用該算法都提高遠距離節點的標記到達匯聚節點的概率；(2)隨著分簇的細化，算法逐步逼近EPPM；(3)分簇規模對算法的影響并不顯著，從 16個節點為一簇到2個節點為一簇，首個轉發節點標記的到達概率并沒得到顯著提高。

4.2 收斂性比較

重構攻擊路徑所需的數據包數量按式(5)計算

將不同分簇情況下的標記概率代入式(5)，忽略常數項O(1)，計算結果如圖5所示。

分析圖5可以看出，即使網絡只被分為兩個簇，LMPPM算法在遠距離節點上的收斂性都明顯好于BPPM，隨著分簇的細化，算法收斂性隨之提升，但不同分簇規模下，算法的收斂性差距并不明顯。

4.3 最弱鏈

圖4 不同簇規模下節點標記到達匯聚節點概率圖

圖5 不同粗規模下重構攻擊路徑所需數據包數量期望圖

即不論簇規模大小，LMPPM算法較之BPPM算法在最弱鏈問題上都有較大的改進，隨著分簇細化，性能穩步提升，但升幅躍升不明顯，比之EPPM算法還有較大差距。

綜合上述分析可知，本文提出的LMPPM算法對分簇規模并沒有特定要求。在不同簇規模下，算法性能均比 BPPM 算法有大幅度提升，比 EPPM算法更貼合網絡實際，進一步提高了算法的適用范圍。

5 結束語

本文提出的層次式混合概率包標記算法LMPPM結合了BPPM算法和EPPM算法的優點，與BPPM相比，在算法收斂性方面有了很大改善，與EPPM相比，較好地解決了節點計算與存儲負擔較重的問題。而這兩種算法本質上是LMPPM的兩個極端情況：當簇的規模設為最大值時，將整個網絡看做一個簇，簇內節點都取同一標記概率，即等同于BPPM算法；當簇的規模設為最小值1時，將每個節點都是看做一個簇，簇間選擇不同標記概率，即相當于EPPM算法。故本文所提出LMPPM算法體現的是在 WSN特征條件約束下，尋求整體最優的思想。通過對不同簇規模下算法性能的分析，驗證了該算法的通用性，說明該算法具有更廣泛的適用范圍。

[1] Chen X Q, Makki K, Yen K,et al.. Sensor network security: a survey[J].IEEE Communications Surveys&Tutorials, 2009,11(2): 52-73.

[2] 劉萍, 李鵬飛, 諶屹, 等. 復雜電磁環境下的無線傳感器網絡戰場電磁偵察與干擾應用研究[C]. 第 3屆全國電磁環境效應與防護技術學術研討會, 武漢, 2012: 28-31.Liu Ping, Li Peng-fei, Zhen Yi,et al.. Applied research on wireless sensor network battlefield reconnaissance and electromagnetic interference in complex electromagnetic environment[C]. The 3rd National Conference on Electromagnetic Environment Effects and Protection, Wuhan,2012: 28-31.

[3] Xu J, Zhou X H, and Yang F. Traceback in wireless sensor networks with packet marking and logging[J].Frontiers of Computer Science in China, 2011, 5(3): 308-315.

[4] 楊坤, 楊庚. 關于無線傳感器網絡中溯源方法的分析[J]. 計算機技術與發展, 2011, 21(7): 58-62.Yang Kun and Yang Geng. An analysis on traceback methods in wireless sensor networks[J].Computer Technology and Development, 2011, 21(7): 58-62.

[5] Snoeren A C, Partridge C, Sanchez L A,et al.. Hash-based IP traceback[C]. ACM SIGCOMM, New York, 2001: 3-14.

[6] Snoeren A C, Partridge C, Sanchez L A,et al.. Singlepacket IP traceback[J].IEEE/ACM Transactions on Networking, 2002, 10(6): 721-734.

[7] Sung M, Xu J, Li J,et al.. Large-scale IP traceback in highspeed Internet: practical techniques and theoretical foundation[J].IEEE/ACM Transactions on Networking, 2008,16(6): 1253-1266.

[8] Matsuda S, Baba T, Hayakawa A,et al.. Design and implementation of unauthorized access tracing system[C].SAINT,02 Proceedings of the 2002 Symposium on Applications and the Internet, Washington, 2002: 74-81.

[9] Bellovin S M. ICMP Traceback Messages[EB/OL]. http://tools.ietf.org/html/draft-ietf-itrace-04, 2000.

[10] Tseng Y, Chen H, and Hsieh W. Probabilistic packet marking with non-preemptive compensation[J].IEEE Communications Letters, 2004, 8(6): 359-361.

[11] Peng S H, Chang K D, Chen J L,et al.. A probabilistic packet marking scheme with LT code for IP traceback[J].InternationalJournalofFutureComputerand Communication, 2012, 1(1): 51-56.

[12] Belenky A and Ansari N. IP traceback with deterministic packet marking[J].IEEE Communications Letters, 2003, 7(4):162-164.

[13] Belenky A and Ansari N. On deterministic packet marking[J].Computer Networks:The International Journal of Computer and Telecommunications Networking, 2007, 51(10): 2677-2700.

[14] Foroushani V A and Heywood A N Z. Deterministic and authenticated flow marking for IP traceback[C]. The 27th IEEE International Conference on Advanced Information Networking and Applications (AINA2013), Barcelona, 2013:397-404.

[15] Tian H C and Bi J. An incrementally deployable flow-based scheme for IP traceback[J].IEEE Communications Letters,2012, 16(7): 1140-1143.

[16] Foroushani V A and Heywood A N Z. On evaluating IP traceback schemes: a practical perspective[C]. IEEE Security and Privacy Workshops, San Francisco, 2013: 127-134.

[17] Tian H C, Bi J, and Jiang X K. An adaptive probabilistic marking scheme for fast and secure traceback[J].Networking Science, 2013, 2(1/2): 42-51.

[18] Belenky A, Ansari N, and Jersey N. On IP traceback[J].IEEE Communications Magazine, 2003, 41(7): 142-153.

[19] Yang M H and Yang M C. RIHT: a novel hybrid IP traceback scheme[J].IEEE Transactions on Information Forensics andSecurity, 2012, 7(2): 789-797.

[20] 楊峰, 周學海, 張起元, 等. 無線傳感器網絡惡意節點溯源追蹤方法研究[J]. 電子學報, 2009, 37(1): 202-206.Yang Feng, Zhou Xue-hai, Zhang Qi-yuan,et al.. A practical traceback mechanism in wireless sensor networks[J].Acta Electronica Sinica, 2009, 37(1): 202-206.