基于動(dòng)態(tài)路由的SPIN路由協(xié)議改進(jìn)

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

（大理學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003）

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的廉價(jià)微型傳感器節(jié)點(diǎn)，通過(guò)無(wú)線(xiàn)通信方式形成的一個(gè)多跳自組織網(wǎng)絡(luò)，現(xiàn)已經(jīng)廣泛應(yīng)用于軍事、生態(tài)環(huán)境、醫(yī)療衛(wèi)生、空間探索、搶險(xiǎn)救災(zāi)等領(lǐng)域〔1〕。在WSN中，路由安全對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的應(yīng)用有著至關(guān)重要的作用。由于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)硬件設(shè)備的特殊性，其更易受到攻擊〔2〕。如何增加無(wú)線(xiàn)傳感器網(wǎng)絡(luò)被攻擊時(shí)的抗攻擊性，以及如何使得網(wǎng)絡(luò)具備更高的吞吐量、降低丟包率，延長(zhǎng)網(wǎng)絡(luò)生命周期是當(dāng)前研究的重點(diǎn)〔3〕。

基于信息協(xié)商的傳感器協(xié)議SPIN（Sensor Protocol for Information via Negotiation）協(xié)議采用高級(jí)的描述符即元數(shù)據(jù)（meta-data）來(lái)描述數(shù)據(jù)，節(jié)點(diǎn)收到數(shù)據(jù)后，廣播數(shù)據(jù)的描述信息，感興趣的節(jié)點(diǎn)在收到數(shù)據(jù)的描述信息后，返回請(qǐng)求信息，只有在收到相應(yīng)的請(qǐng)求后，節(jié)點(diǎn)才向目的地發(fā)送數(shù)據(jù)〔4〕。國(guó)內(nèi)外很多學(xué)者對(duì)其進(jìn)行研究，取得了較為顯著的成果〔5〕。但是SPIN安全路由協(xié)議數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)于復(fù)雜、重復(fù)轉(zhuǎn)發(fā)相同數(shù)據(jù)包的問(wèn)題影響了SPIN 協(xié)議轉(zhuǎn)發(fā)時(shí)的網(wǎng)絡(luò)吞吐量，增加了丟包率，縮短了網(wǎng)絡(luò)的生命周期〔6〕。

本文在研究了SPIN 協(xié)議的基礎(chǔ)上，提出了一種動(dòng)態(tài)路由信息協(xié)商傳感器協(xié)議D-SPIN（Directional-routing Sensor Protocol for Information via Negotiation）協(xié)議，其在SPIN 協(xié)議基礎(chǔ)上加入了動(dòng)態(tài)路由表建立算法和驗(yàn)證下一跳id選擇性轉(zhuǎn)發(fā)策略，并利用NS2 仿真軟件對(duì)算法進(jìn)行仿真。仿真結(jié)果表明，D-SPIN 算法在網(wǎng)絡(luò)吞吐量、丟包率和網(wǎng)絡(luò)時(shí)延等性能參數(shù)上有較大的提高。

1 SPIN協(xié)議算法思想及過(guò)程

SPIN 是一種以數(shù)據(jù)為中心的自適應(yīng)通信路由協(xié)議，其數(shù)據(jù)轉(zhuǎn)發(fā)比較復(fù)雜，重復(fù)轉(zhuǎn)發(fā)相同數(shù)據(jù)包，這給系統(tǒng)性能帶來(lái)了較為嚴(yán)重的影響。它通過(guò)使用節(jié)點(diǎn)間的協(xié)商制度和資源自適應(yīng)機(jī)制，解決了傳統(tǒng)協(xié)議所存在的內(nèi)爆，重疊以及盲目使用資源問(wèn)題。 SPIN 協(xié)議有3 種數(shù)據(jù)包類(lèi)型，即ADV、REQ和DATA。ADV 用于元數(shù)據(jù)的廣播，REQ 用于請(qǐng)求發(fā)送數(shù)據(jù)，DATA 為傳感器采集的數(shù)據(jù)包〔7〕。SPIN協(xié)議通過(guò)兩個(gè)關(guān)鍵的革新，即信息協(xié)商（negotiation）和資源自適應(yīng)（resource-adaptation）克服了flooding協(xié)議的內(nèi)爆和重疊問(wèn)題〔8〕。

1.1 元數(shù)據(jù)與消息類(lèi)型SPIN 協(xié)議使用元數(shù)據(jù)（meta-data）簡(jiǎn)潔而完美地描述傳感器所收集的數(shù)據(jù)。SPIN協(xié)議沒(méi)有特殊地規(guī)定元數(shù)據(jù)格式，這種格式是基于實(shí)際應(yīng)用的〔9〕。例如，覆蓋的地理區(qū)域不相交的傳感器可以簡(jiǎn)單地把自己獨(dú)有的標(biāo)識(shí)作為元數(shù)據(jù)。由于每個(gè)實(shí)際應(yīng)用中的元數(shù)據(jù)格式可能都不一樣，所以SPIN根據(jù)每個(gè)應(yīng)用來(lái)解釋和綜合元數(shù)據(jù)。

SPIN協(xié)議包含3個(gè)消息類(lèi)型，分別是：

①ADV（advertisement）消息（廣播消息）：用于新數(shù)據(jù)的廣播。當(dāng)一個(gè)采用SPIN 協(xié)議的節(jié)點(diǎn)有新數(shù)據(jù)時(shí)，通過(guò)發(fā)送一個(gè)包含元數(shù)據(jù)的ADV廣播消息通知其鄰居節(jié)點(diǎn)。

②REQ（request）消息（請(qǐng)求消息）：用于請(qǐng)求數(shù)據(jù)。當(dāng)一個(gè)節(jié)點(diǎn)收到其鄰居節(jié)點(diǎn)的數(shù)據(jù)包廣播，亦即ADV廣播消息，若達(dá)到規(guī)定條件并且需要接收該數(shù)據(jù)包時(shí)可以發(fā)送一個(gè)REQ 消息向發(fā)送節(jié)點(diǎn)請(qǐng)求該數(shù)據(jù)包。

③DATA：實(shí)際數(shù)據(jù)包。DATA是含有攜帶著一個(gè)元數(shù)據(jù)報(bào)頭（meta-data header）的傳感器采集的實(shí)際數(shù)據(jù)包。

將這些有新數(shù)據(jù)需要轉(zhuǎn)發(fā)而發(fā)送ADV 消息的節(jié)點(diǎn)統(tǒng)稱(chēng)為“發(fā)送節(jié)點(diǎn)”，其中網(wǎng)絡(luò)中第一個(gè)封裝并廣播ADV 數(shù)據(jù)包的節(jié)點(diǎn)稱(chēng)為“源節(jié)點(diǎn)”。將所有發(fā)送REQ 請(qǐng)求的節(jié)點(diǎn)以及所有接收數(shù)據(jù)數(shù)據(jù)包的節(jié)點(diǎn)統(tǒng)稱(chēng)為“接收節(jié)點(diǎn)”，即接收節(jié)點(diǎn)接收的數(shù)據(jù)可能是ADV、REQ或DATA中的任何一類(lèi)或幾類(lèi)〔10〕。

1.2 SPIN協(xié)議工作過(guò)程SPIN協(xié)議工作過(guò)程大致分為3個(gè)步驟（又稱(chēng)為“三次握手”）：

步驟1：當(dāng)一個(gè)傳感器節(jié)點(diǎn)（源節(jié)點(diǎn)）有新數(shù)據(jù)需要傳輸時(shí)，使用ADV數(shù)據(jù)包對(duì)其所有的鄰居進(jìn)行廣播，等待接收REQ響應(yīng)消息。

步驟2：當(dāng)鄰居節(jié)點(diǎn)收到這個(gè)廣播消息時(shí)，首先檢查其自身的能量值是否低于設(shè)定閾值，若能量充足則檢查是否已經(jīng)接收過(guò)或請(qǐng)求過(guò)該廣播的數(shù)據(jù)；若請(qǐng)求接收該數(shù)據(jù)，且其擁有足夠的能量，就發(fā)送REQ消息請(qǐng)求接收新的數(shù)據(jù)；若已經(jīng)接收過(guò)或請(qǐng)求過(guò)該數(shù)據(jù)或能量低于設(shè)定閾值，則不響應(yīng)。

步驟3：若源節(jié)點(diǎn)沒(méi)有收到REQ消息，則進(jìn)入結(jié)束狀態(tài)，等待下一次數(shù)據(jù)傳輸；若源節(jié)點(diǎn)收到REQ消息，則發(fā)送數(shù)據(jù)DATA 給請(qǐng)求節(jié)點(diǎn)。接收節(jié)點(diǎn)若不是匯聚節(jié)點(diǎn)，在接收數(shù)據(jù)后就變?yōu)樵垂?jié)點(diǎn)，返回到第一步，繼續(xù)執(zhí)行。

這個(gè)過(guò)程重復(fù)下去，直到數(shù)據(jù)被傳輸?shù)絽R聚節(jié)點(diǎn)。

2 D-SPIN協(xié)議算法

針對(duì)SPIN 存在的問(wèn)題，文章在分析了SPIN 協(xié)議的基礎(chǔ)上，加入了動(dòng)態(tài)路由表建立算法和驗(yàn)證下一跳id選擇性轉(zhuǎn)發(fā)策略，提出了一種基于動(dòng)態(tài)路由的信息協(xié)商傳感器協(xié)議D-SPIN協(xié)議。

2.1 D-SPIN協(xié)議改進(jìn)方法

2.1.1 初始化路由建立算法 D-SPIN協(xié)議在SPIN協(xié)議基礎(chǔ)上增加了動(dòng)態(tài)路由算法，在網(wǎng)絡(luò)初始化階段（以下簡(jiǎn)稱(chēng)“初始化階段”）建立可用路由記錄表，這樣在節(jié)點(diǎn)有數(shù)據(jù)轉(zhuǎn)發(fā)的時(shí)候直接查找路由表中的下一跳節(jié)點(diǎn)id，將節(jié)點(diǎn)id 封裝到ADV 包中，接收節(jié)點(diǎn)收到ADV 包后首先匹配id，只有當(dāng)ADV 包中的id 信息（用變量nexthop_表示）與自身id 相同時(shí)，才判斷是否已經(jīng)有該數(shù)據(jù)，然后執(zhí)行后續(xù)的工作。從而保證了一個(gè)數(shù)據(jù)包只被無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中一條鏈路傳輸。

D-SPIN協(xié)議在建立路由表階段，將可用的鄰居節(jié)點(diǎn)（處于正常工作狀態(tài)并且可以到達(dá)的鄰居節(jié)點(diǎn)）id 都記入路由表中，在有數(shù)據(jù)需要發(fā)送或轉(zhuǎn)發(fā)時(shí)，使用隨機(jī)選擇算法從路由表中隨機(jī)選擇節(jié)點(diǎn)直接進(jìn)行轉(zhuǎn)發(fā)。

此路由建立算法用在網(wǎng)絡(luò)初始化階段，通過(guò)此算法在每個(gè)節(jié)點(diǎn)上建立可用路由表。當(dāng)節(jié)點(diǎn)監(jiān)測(cè)到檢測(cè)對(duì)象變化情況或者網(wǎng)絡(luò)中有數(shù)據(jù)需要節(jié)點(diǎn)轉(zhuǎn)發(fā)時(shí)，節(jié)點(diǎn)即可隨機(jī)讀取可用路由表中的一條記錄作為下一跳地址進(jìn)行轉(zhuǎn)發(fā)。

與SPIN協(xié)議的原始過(guò)程相對(duì)比，路由建立算法在節(jié)點(diǎn)“有數(shù)據(jù)需要發(fā)送”這一狀態(tài)和“發(fā)送ADV消息”這一動(dòng)作之間。見(jiàn)圖1。

圖1 D-SPIN協(xié)議路由建立算法

2.1.2 D-SPIN 協(xié)議網(wǎng)絡(luò)正常工作階段算法改進(jìn)D-SPIN 協(xié)議在網(wǎng)絡(luò)初始化完成以后即進(jìn)入網(wǎng)絡(luò)正常工作階段，以下簡(jiǎn)稱(chēng)“正常工作階段”。在正常工作階段，協(xié)議的算法比起初始化階段大為簡(jiǎn)化，相比SPIN 協(xié)議原始工作流程圖僅僅多了維護(hù)可用路由表的工作。只要節(jié)點(diǎn)路由表中還有可用路由（可用路由記錄指：該路由表nexthop_變量所代表的節(jié)點(diǎn)可達(dá)，并且處于正常工作狀態(tài)或可以被喚醒進(jìn)入正常工作狀態(tài)），就不會(huì)再次啟用路由建立算法。只有當(dāng)節(jié)點(diǎn)路由表中已經(jīng)沒(méi)有可用路由才會(huì)使用路由建立算法重建可用路由表。

維護(hù)可用路由表的工作分為兩部分，分別由發(fā)送節(jié)點(diǎn)（源節(jié)點(diǎn)或者轉(zhuǎn)發(fā)節(jié)點(diǎn)）和接收節(jié)點(diǎn)完成。分工如下。

①發(fā)送節(jié)點(diǎn)：在原始流程中“生成ADV包”動(dòng)作之后，“發(fā)送ADV消息”之前這個(gè)區(qū)間內(nèi)加入了對(duì)下一跳路由記錄（本文中等價(jià)于“下一跳id 記錄”，即變量“nexthop_”所示）的判斷，并且隨機(jī)讀取一個(gè)下一跳id記錄到ADV包中專(zhuān)門(mén)預(yù)留的地址字段，文章中用變量“id_”表示。如果無(wú)可用的下一跳id 則節(jié)點(diǎn)自動(dòng)啟用路由建立算法獲取并更新可用路由表。如果成功讀取了可用的下一跳id 并已經(jīng)正確添加到ADV包的“id_”字段，則發(fā)送該ADV包，接下來(lái)的工作與SPIN原始協(xié)議流程圖相同。見(jiàn)圖2。

圖2 發(fā)送節(jié)點(diǎn)算法改進(jìn)

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

圖3 接收節(jié)點(diǎn)算法改進(jìn)

2.2 D-SPIN適用環(huán)境D-SPIN協(xié)議，保留了SPIN協(xié)議的諸多特點(diǎn)：平面路由協(xié)議，以數(shù)據(jù)為中心，能量管理機(jī)制，資源自適應(yīng)，使用元數(shù)據(jù)表示數(shù)據(jù)等。因此SPIN 協(xié)議適用的環(huán)境D-SPIN 協(xié)議都適用。具體而言，主要用于可以形成平面或者直線(xiàn)的監(jiān)控網(wǎng)絡(luò)均可以采用D-SPIN協(xié)議，比如橋梁監(jiān)控，公路路況監(jiān)控，交通監(jiān)控，鐵路監(jiān)控，甚至通過(guò)在潛艇上部署以用來(lái)檢測(cè)水流速等。

在移動(dòng)環(huán)境中D-SPIN協(xié)議仍然適用。D-SPIN協(xié)議對(duì)節(jié)點(diǎn)使用了唯一標(biāo)識(shí)，并且必須保證下一跳信息即“nexthop_”變量與使用的唯一標(biāo)識(shí)一致，這樣的設(shè)計(jì)保證了對(duì)移動(dòng)節(jié)點(diǎn)的有效標(biāo)識(shí)。但為了準(zhǔn)確地對(duì)移動(dòng)節(jié)點(diǎn)引起的路由變化進(jìn)行準(zhǔn)確的識(shí)別并更新，不論是否還有可用路由記錄，必須根據(jù)移動(dòng)節(jié)點(diǎn)的移動(dòng)速度制定具體的路由更新計(jì)劃。如果移動(dòng)節(jié)點(diǎn)的移動(dòng)速度快，即需要縮短更新周期，如果移動(dòng)節(jié)點(diǎn)的移動(dòng)速度較慢，就可以將路由表更新周期相應(yīng)延長(zhǎng)。

3 性能分析

為了對(duì)新協(xié)議D-SPIN 的性能進(jìn)行評(píng)價(jià)，本文利用NS2 仿真平臺(tái)對(duì)SPIN，D-SPIN 兩個(gè)協(xié)議進(jìn)行仿真。仿真環(huán)境在100M*100M 的區(qū)域內(nèi)隨機(jī)部署100個(gè)節(jié)點(diǎn)，仿真參數(shù)包括系統(tǒng)吞吐量、丟包率和節(jié)點(diǎn)的傳輸時(shí)延。通過(guò)編寫(xiě)tcl腳本對(duì)協(xié)議測(cè)試，編寫(xiě)awk 腳本對(duì)仿真結(jié)果提取數(shù)據(jù)計(jì)算協(xié)議的參數(shù)指標(biāo)，使用gnuplot畫(huà)圖工具繪制效果圖。

網(wǎng)絡(luò)吞吐量對(duì)比圖，見(jiàn)圖4。從實(shí)驗(yàn)結(jié)果來(lái)看，D-SPIN 協(xié)議的吞吐量在網(wǎng)絡(luò)工作一段時(shí)間后比起SPIN協(xié)議有所提高，在網(wǎng)絡(luò)初始化階段略低于SPIN 協(xié)議，但是在系統(tǒng)穩(wěn)定之后，D-SPIN 協(xié)議比SPIN協(xié)議在吞吐量方面提高約5.6%。

圖4 系統(tǒng)吞吐量對(duì)比圖

兩個(gè)協(xié)議的對(duì)比曲線(xiàn)，見(jiàn)圖5。D-SPIN 協(xié)議丟包率全程都低于SPIN，并且穩(wěn)定在一個(gè)較低的范圍，同時(shí)可以看出，D-SPIN協(xié)議比SPIN協(xié)議的丟包率減少了11%。

圖5 丟包率對(duì)比曲線(xiàn)

傳輸時(shí)延比對(duì)比圖，見(jiàn)圖6，傳輸時(shí)延在網(wǎng)絡(luò)開(kāi)始時(shí)比較明顯，高于SPIN 協(xié)議，但是網(wǎng)絡(luò)穩(wěn)定后維持在一個(gè)較低的比值范圍，D-SPIN 協(xié)議比SPIN 協(xié)議的傳輸時(shí)延節(jié)省約45%，從而提高了網(wǎng)絡(luò)的生命周期。

圖6 傳輸時(shí)延比對(duì)比圖

由于網(wǎng)絡(luò)初始化階段需要建立路由，而沒(méi)有現(xiàn)成的可用路由進(jìn)行轉(zhuǎn)發(fā)，而且數(shù)據(jù)轉(zhuǎn)發(fā)所消耗的時(shí)間會(huì)比SPIN協(xié)議長(zhǎng)，表現(xiàn)出的特征就是前期時(shí)延比較大。在網(wǎng)絡(luò)穩(wěn)定后，由于節(jié)點(diǎn)已經(jīng)建立了可用路由表，可直接進(jìn)行轉(zhuǎn)發(fā)，而節(jié)點(diǎn)在接收數(shù)據(jù)時(shí)使用了id 匹配后才接收，這樣不僅傳輸效率提升了，網(wǎng)絡(luò)吞吐量即有所上升，丟包率和傳輸時(shí)延有所下降并保持在一個(gè)較低水平。

4 結(jié)論

在分析SPIN 協(xié)議的基礎(chǔ)上提出了一種動(dòng)態(tài)路由信息協(xié)商傳感器協(xié)議D-SPIN 協(xié)議，其在SPIN 協(xié)議基礎(chǔ)上加入了動(dòng)態(tài)路由表建立算法和驗(yàn)證下一跳id選擇性轉(zhuǎn)發(fā)策略，并利用NS2仿真軟件對(duì)算法進(jìn)行仿真。仿真結(jié)果表明，D-SPIN 算法在網(wǎng)絡(luò)吞吐量、丟包率和網(wǎng)絡(luò)時(shí)延等性能參數(shù)上有較大的提高。同時(shí)，D-SPIN 協(xié)議仍然保持了SPIN 協(xié)議的諸多優(yōu)點(diǎn)，而提供了較多的可改進(jìn)和擴(kuò)展空間。但是路由表的建立同樣會(huì)增加節(jié)點(diǎn)負(fù)擔(dān)，增加能耗成本，這將是下一步工作的方向。

〔1〕馮立波，黃婷，羅桂蘭.一種用于森林防火的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位算法〔J〕.傳感器與微系統(tǒng)，2011，30（5）:123-126.

〔2〕張江豐.基于網(wǎng)格拓?fù)涞臒o(wú)線(xiàn)傳感器網(wǎng)絡(luò)低能耗路由策略〔J〕.傳感器與微系統(tǒng)，2013，32（7）:45-49.

〔3〕馮立波，潘麗靜，楊潤(rùn)標(biāo)，等.一種適用于異構(gòu)網(wǎng)絡(luò)的TCP New Vegas 算法〔J〕.大理學(xué)院學(xué)報(bào)，2014，13（6）:10-14.

〔4〕任秀麗，李政.基于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)SPIN 協(xié)議的一種改進(jìn)方案〔J〕.化工自動(dòng)化及儀表，2O06，33（2）:35-38.

〔5〕彭志娟，王汝傳.基于SPINS的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)低能耗安全路由協(xié)議〔J〕.計(jì)算機(jī)應(yīng)用，2010，30（5）:1149-1152.

〔6〕敬超，常亮，古天龍.基于SPIN的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)安全協(xié)議建模與分析〔J〕.2009，36（10）:132-135.

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

〔8〕邢明彥，李臘元，何延杰.基于聲譽(yù)機(jī)制的WSN安全路由協(xié)議的研究〔J〕. 武漢理工大學(xué)學(xué)報(bào)，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安全框架協(xié)議研究〔J〕.計(jì)算機(jī)科學(xué)，2006，33（8）:106-108.