基于動態路由的SPIN路由協議改進

馮立波，李 全，張 梅，羅桂蘭

（大理學院數學與計算機學院，云南大理 671003）

無線傳感器網絡（Wireless Sensor Networks，WSN）是由部署在監測區域內大量的廉價微型傳感器節點，通過無線通信方式形成的一個多跳自組織網絡，現已經廣泛應用于軍事、生態環境、醫療衛生、空間探索、搶險救災等領域〔1〕。在WSN中，路由安全對無線傳感器網絡的應用有著至關重要的作用。由于無線傳感器網絡硬件設備的特殊性，其更易受到攻擊〔2〕。如何增加無線傳感器網絡被攻擊時的抗攻擊性，以及如何使得網絡具備更高的吞吐量、降低丟包率，延長網絡生命周期是當前研究的重點〔3〕。

基于信息協商的傳感器協議SPIN（Sensor Protocol for Information via Negotiation）協議采用高級的描述符即元數據（meta-data）來描述數據，節點收到數據后，廣播數據的描述信息，感興趣的節點在收到數據的描述信息后，返回請求信息，只有在收到相應的請求后，節點才向目的地發送數據〔4〕。國內外很多學者對其進行研究，取得了較為顯著的成果〔5〕。但是SPIN安全路由協議數據轉發過于復雜、重復轉發相同數據包的問題影響了SPIN 協議轉發時的網絡吞吐量，增加了丟包率，縮短了網絡的生命周期〔6〕。

本文在研究了SPIN 協議的基礎上，提出了一種動態路由信息協商傳感器協議D-SPIN（Directional-routing Sensor Protocol for Information via Negotiation）協議，其在SPIN 協議基礎上加入了動態路由表建立算法和驗證下一跳id選擇性轉發策略，并利用NS2 仿真軟件對算法進行仿真。仿真結果表明，D-SPIN 算法在網絡吞吐量、丟包率和網絡時延等性能參數上有較大的提高。

1 SPIN協議算法思想及過程

SPIN 是一種以數據為中心的自適應通信路由協議，其數據轉發比較復雜，重復轉發相同數據包，這給系統性能帶來了較為嚴重的影響。它通過使用節點間的協商制度和資源自適應機制，解決了傳統協議所存在的內爆，重疊以及盲目使用資源問題。 SPIN 協議有3 種數據包類型，即ADV、REQ和DATA。ADV 用于元數據的廣播，REQ 用于請求發送數據，DATA 為傳感器采集的數據包〔7〕。SPIN協議通過兩個關鍵的革新，即信息協商（negotiation）和資源自適應（resource-adaptation）克服了flooding協議的內爆和重疊問題〔8〕。

1.1 元數據與消息類型SPIN 協議使用元數據（meta-data）簡潔而完美地描述傳感器所收集的數據。SPIN協議沒有特殊地規定元數據格式，這種格式是基于實際應用的〔9〕。例如，覆蓋的地理區域不相交的傳感器可以簡單地把自己獨有的標識作為元數據。由于每個實際應用中的元數據格式可能都不一樣，所以SPIN根據每個應用來解釋和綜合元數據。

SPIN協議包含3個消息類型，分別是：

①ADV（advertisement）消息（廣播消息）：用于新數據的廣播。當一個采用SPIN 協議的節點有新數據時，通過發送一個包含元數據的ADV廣播消息通知其鄰居節點。

②REQ（request）消息（請求消息）：用于請求數據。當一個節點收到其鄰居節點的數據包廣播，亦即ADV廣播消息，若達到規定條件并且需要接收該數據包時可以發送一個REQ 消息向發送節點請求該數據包。

③DATA：實際數據包。DATA是含有攜帶著一個元數據報頭（meta-data header）的傳感器采集的實際數據包。

將這些有新數據需要轉發而發送ADV 消息的節點統稱為“發送節點”，其中網絡中第一個封裝并廣播ADV 數據包的節點稱為“源節點”。將所有發送REQ 請求的節點以及所有接收數據數據包的節點統稱為“接收節點”，即接收節點接收的數據可能是ADV、REQ或DATA中的任何一類或幾類〔10〕。

1.2 SPIN協議工作過程SPIN協議工作過程大致分為3個步驟（又稱為“三次握手”）：

步驟1：當一個傳感器節點（源節點）有新數據需要傳輸時，使用ADV數據包對其所有的鄰居進行廣播，等待接收REQ響應消息。

步驟2：當鄰居節點收到這個廣播消息時，首先檢查其自身的能量值是否低于設定閾值，若能量充足則檢查是否已經接收過或請求過該廣播的數據；若請求接收該數據，且其擁有足夠的能量，就發送REQ消息請求接收新的數據；若已經接收過或請求過該數據或能量低于設定閾值，則不響應。

步驟3：若源節點沒有收到REQ消息，則進入結束狀態，等待下一次數據傳輸；若源節點收到REQ消息，則發送數據DATA 給請求節點。接收節點若不是匯聚節點，在接收數據后就變為源節點，返回到第一步，繼續執行。

這個過程重復下去，直到數據被傳輸到匯聚節點。

2 D-SPIN協議算法

針對SPIN 存在的問題，文章在分析了SPIN 協議的基礎上，加入了動態路由表建立算法和驗證下一跳id選擇性轉發策略，提出了一種基于動態路由的信息協商傳感器協議D-SPIN協議。

2.1 D-SPIN協議改進方法

2.1.1 初始化路由建立算法 D-SPIN協議在SPIN協議基礎上增加了動態路由算法，在網絡初始化階段（以下簡稱“初始化階段”）建立可用路由記錄表，這樣在節點有數據轉發的時候直接查找路由表中的下一跳節點id，將節點id 封裝到ADV 包中，接收節點收到ADV 包后首先匹配id，只有當ADV 包中的id 信息（用變量nexthop_表示）與自身id 相同時，才判斷是否已經有該數據，然后執行后續的工作。從而保證了一個數據包只被無線傳感器網絡中一條鏈路傳輸。

D-SPIN協議在建立路由表階段，將可用的鄰居節點（處于正常工作狀態并且可以到達的鄰居節點）id 都記入路由表中，在有數據需要發送或轉發時，使用隨機選擇算法從路由表中隨機選擇節點直接進行轉發。

此路由建立算法用在網絡初始化階段，通過此算法在每個節點上建立可用路由表。當節點監測到檢測對象變化情況或者網絡中有數據需要節點轉發時，節點即可隨機讀取可用路由表中的一條記錄作為下一跳地址進行轉發。

與SPIN協議的原始過程相對比，路由建立算法在節點“有數據需要發送”這一狀態和“發送ADV消息”這一動作之間。見圖1。

圖1 D-SPIN協議路由建立算法

2.1.2 D-SPIN 協議網絡正常工作階段算法改進D-SPIN 協議在網絡初始化完成以后即進入網絡正常工作階段，以下簡稱“正常工作階段”。在正常工作階段，協議的算法比起初始化階段大為簡化，相比SPIN 協議原始工作流程圖僅僅多了維護可用路由表的工作。只要節點路由表中還有可用路由（可用路由記錄指：該路由表nexthop_變量所代表的節點可達，并且處于正常工作狀態或可以被喚醒進入正常工作狀態），就不會再次啟用路由建立算法。只有當節點路由表中已經沒有可用路由才會使用路由建立算法重建可用路由表。

維護可用路由表的工作分為兩部分，分別由發送節點（源節點或者轉發節點）和接收節點完成。分工如下。

①發送節點：在原始流程中“生成ADV包”動作之后，“發送ADV消息”之前這個區間內加入了對下一跳路由記錄（本文中等價于“下一跳id 記錄”，即變量“nexthop_”所示）的判斷，并且隨機讀取一個下一跳id記錄到ADV包中專門預留的地址字段，文章中用變量“id_”表示。如果無可用的下一跳id 則節點自動啟用路由建立算法獲取并更新可用路由表。如果成功讀取了可用的下一跳id 并已經正確添加到ADV包的“id_”字段，則發送該ADV包，接下來的工作與SPIN原始協議流程圖相同。見圖2。

圖2 發送節點算法改進

②接收節點：在正常工作狀態，接收節點在收到ADV消息后，先讀取ADV包中的“nexthop_”變量（即上一跳節點指定的id字段值），將讀取的nexthop_存放到一個臨時變量hop 中，判斷hop 的值是否等于自身的id，如果不相等，則不作進一步的判斷，直接丟棄ADV 包；如果hop 的值與自身id 相等，則表示該包確實是發給自己的，就對ADV聲明的數據包進行判斷，同時核對自己是否已經有該數據包DATA，如果已經有該DATA，就對該ADV 消息進行簡要記錄，以便在一段時間內用于判斷是否有重復的包送達，在一段規定的時間后，該ADV 自動失效。接下來的過程與原始SPIN協議流程一致。見圖3。

圖3 接收節點算法改進

2.2 D-SPIN適用環境D-SPIN協議，保留了SPIN協議的諸多特點：平面路由協議，以數據為中心，能量管理機制，資源自適應，使用元數據表示數據等。因此SPIN 協議適用的環境D-SPIN 協議都適用。具體而言，主要用于可以形成平面或者直線的監控網絡均可以采用D-SPIN協議，比如橋梁監控，公路路況監控，交通監控，鐵路監控，甚至通過在潛艇上部署以用來檢測水流速等。

在移動環境中D-SPIN協議仍然適用。D-SPIN協議對節點使用了唯一標識，并且必須保證下一跳信息即“nexthop_”變量與使用的唯一標識一致，這樣的設計保證了對移動節點的有效標識。但為了準確地對移動節點引起的路由變化進行準確的識別并更新，不論是否還有可用路由記錄，必須根據移動節點的移動速度制定具體的路由更新計劃。如果移動節點的移動速度快，即需要縮短更新周期，如果移動節點的移動速度較慢，就可以將路由表更新周期相應延長。

3 性能分析

為了對新協議D-SPIN 的性能進行評價，本文利用NS2 仿真平臺對SPIN，D-SPIN 兩個協議進行仿真。仿真環境在100M*100M 的區域內隨機部署100個節點，仿真參數包括系統吞吐量、丟包率和節點的傳輸時延。通過編寫tcl腳本對協議測試，編寫awk 腳本對仿真結果提取數據計算協議的參數指標，使用gnuplot畫圖工具繪制效果圖。

網絡吞吐量對比圖，見圖4。從實驗結果來看，D-SPIN 協議的吞吐量在網絡工作一段時間后比起SPIN協議有所提高，在網絡初始化階段略低于SPIN 協議，但是在系統穩定之后，D-SPIN 協議比SPIN協議在吞吐量方面提高約5.6%。

圖4 系統吞吐量對比圖

兩個協議的對比曲線，見圖5。D-SPIN 協議丟包率全程都低于SPIN，并且穩定在一個較低的范圍，同時可以看出，D-SPIN協議比SPIN協議的丟包率減少了11%。

圖5 丟包率對比曲線

傳輸時延比對比圖，見圖6，傳輸時延在網絡開始時比較明顯，高于SPIN 協議，但是網絡穩定后維持在一個較低的比值范圍，D-SPIN 協議比SPIN 協議的傳輸時延節省約45%，從而提高了網絡的生命周期。

圖6 傳輸時延比對比圖

由于網絡初始化階段需要建立路由，而沒有現成的可用路由進行轉發，而且數據轉發所消耗的時間會比SPIN協議長，表現出的特征就是前期時延比較大。在網絡穩定后，由于節點已經建立了可用路由表，可直接進行轉發，而節點在接收數據時使用了id 匹配后才接收，這樣不僅傳輸效率提升了，網絡吞吐量即有所上升，丟包率和傳輸時延有所下降并保持在一個較低水平。

4 結論

在分析SPIN 協議的基礎上提出了一種動態路由信息協商傳感器協議D-SPIN 協議，其在SPIN 協議基礎上加入了動態路由表建立算法和驗證下一跳id選擇性轉發策略，并利用NS2仿真軟件對算法進行仿真。仿真結果表明，D-SPIN 算法在網絡吞吐量、丟包率和網絡時延等性能參數上有較大的提高。同時，D-SPIN 協議仍然保持了SPIN 協議的諸多優點，而提供了較多的可改進和擴展空間。但是路由表的建立同樣會增加節點負擔，增加能耗成本，這將是下一步工作的方向。

〔1〕馮立波，黃婷，羅桂蘭.一種用于森林防火的無線傳感器網絡定位算法〔J〕.傳感器與微系統，2011，30（5）:123-126.

〔2〕張江豐.基于網格拓撲的無線傳感器網絡低能耗路由策略〔J〕.傳感器與微系統，2013，32（7）:45-49.

〔3〕馮立波，潘麗靜，楊潤標，等.一種適用于異構網絡的TCP New Vegas 算法〔J〕.大理學院學報，2014，13（6）:10-14.

〔4〕任秀麗，李政.基于無線傳感器網絡SPIN 協議的一種改進方案〔J〕.化工自動化及儀表，2O06，33（2）:35-38.

〔5〕彭志娟，王汝傳.基于SPINS的無線傳感器網絡低能耗安全路由協議〔J〕.計算機應用，2010，30（5）:1149-1152.

〔6〕敬超，常亮，古天龍.基于SPIN的無線傳感器網絡安全協議建模與分析〔J〕.2009，36（10）:132-135.

〔7〕朱磊，吳灝，王清賢.基于可信基站的SPINS 協議研究與改進〔J〕.計算機應用研究，2010，27（10）:2331-2335.

〔8〕邢明彥，李臘元，何延杰.基于聲譽機制的WSN安全路由協議的研究〔J〕. 武漢理工大學學報，2009，31（6）:896-899.

〔9〕PERRIG A，SZEWCZYK R，WEN V，et a1．SPINS：Security protocols for sensor networks〔J〕．Wireless Networks，2002，8（5）：521-534.

〔10〕程宏兵，王江濤，楊庚.SPINS安全框架協議研究〔J〕.計算機科學，2006，33（8）:106-108.