具有范圍選擇的傳感網(wǎng)絡(luò)再編程協(xié)議算法研究

譚 勁，張曼曼，禇 娜

(中國計量學(xué)院，杭州310018)

無線傳感網(wǎng)絡(luò)再編程(Reprogramming)通常由兩部分組成:傳感節(jié)點上已裝入更新代碼的安裝機(jī)制和分布更新軟件到傳感節(jié)點的傳播機(jī)制。安裝機(jī)制負(fù)責(zé)將到達(dá)的軟件代碼重啟動，這涉及到重寫閃存和微控制器復(fù)位等技術(shù)問題，屬于操作系統(tǒng)與硬件結(jié)構(gòu)研究的范疇;傳播機(jī)制負(fù)責(zé)及時、安全、可靠地更新代碼傳播到網(wǎng)絡(luò)中的各個節(jié)點，屬網(wǎng)絡(luò)協(xié)議研究的范疇。目前安裝機(jī)制方面的技術(shù)相對成熟，第二代傳感節(jié)點已經(jīng)具備再編程的能力(遠(yuǎn)程節(jié)點程序更新)，新的第三代節(jié)點還支持硬件重配置(Reconfiguration)［1］，因而傳感網(wǎng)絡(luò)再編程傳播協(xié)議成為當(dāng)前研究的重點［2－5］。這些研究將整個軟件影像分成許多段或包，然后采用泛洪方式將段或包分發(fā)到網(wǎng)絡(luò)中的不同節(jié)點，其研究重點集中在用較低的資源消耗和較少的端到端延遲可靠地將更新的軟件影像分發(fā)到網(wǎng)絡(luò)中的每個節(jié)點。為了支持流水線操作以便加速多跳網(wǎng)絡(luò)中的再編程效率，引入了管道(Pipelining)的概念［3］;通過 ADV(廣告)－REQ(請求)－DATA(數(shù)據(jù))三次握手協(xié)商傳輸，避免了代碼冗余傳輸而提高了再編程的可靠性［4－5］;層次結(jié)構(gòu)Sprinkler［2］由于采取層次結(jié)構(gòu)減少了控制包的數(shù)量，從而加快了代碼分發(fā)的速度。

然而，已有的傳感網(wǎng)絡(luò)再編程協(xié)議大多假定網(wǎng)絡(luò)中所有節(jié)點的功能是相同的(Homogeneous)，運行同一版本的應(yīng)用程序，因而將同一軟件影像分發(fā)到整個網(wǎng)絡(luò)，沒有考慮再編程節(jié)點的范圍選擇問題［6］。在實際中，許多傳感網(wǎng)絡(luò)往往分成了許多組，不同的節(jié)點或組完成不同的任務(wù)，為了增強(qiáng)網(wǎng)絡(luò)的可靠性和延長整個網(wǎng)絡(luò)的生命周期，傳感節(jié)點感知的對象、通信能力、CPU處理能力等都是異類的(Heterogeneous)［7－8］。因此，一個傳感網(wǎng)絡(luò)中可能有多個不同功能的應(yīng)用程序，這就需要傳輸協(xié)議動態(tài)地選擇一定范圍的節(jié)點進(jìn)行再編程某種類型應(yīng)用程序的所有節(jié)點。

本文提出了一種新的具有范圍選擇的再編程協(xié)議，該協(xié)議變傳統(tǒng)的ADV－REQ－DATA三次握手協(xié)議為路由形成、代碼傳送、請求丟失包三個階段協(xié)議，有效地降低了參與代碼轉(zhuǎn)發(fā)的中間節(jié)點數(shù);中間節(jié)點通過獲取一跳范圍內(nèi)希望接收更新代碼數(shù)據(jù)的節(jié)點序列，采取單播或組播方式有針對性傳送更新代碼，而不是泛洪式的廣播，減少了REQ確認(rèn)信息包，并能統(tǒng)計出參與代碼更新的同類節(jié)點數(shù)和代碼轉(zhuǎn)發(fā)的異類中間節(jié)點數(shù)。性能分析與模擬實驗表明:該協(xié)議在平均延時、能量消耗等方面優(yōu)于傳統(tǒng)的Aqueduct。

1 相關(guān)工作

范圍選擇允許管理員或網(wǎng)絡(luò)動態(tài)選擇指定的節(jié)點集進(jìn)行再編程，這不僅減少了參與再編程的節(jié)點數(shù)，還能降低整個網(wǎng)絡(luò)能量消耗，但目前具有范圍選擇的研究相對較少，已有的研究主要分為靜態(tài)網(wǎng)絡(luò)［9－13］和移動網(wǎng)絡(luò)［14－16］兩部分。在靜態(tài)網(wǎng)絡(luò)方面，文獻(xiàn)［9－10］是較早進(jìn)行這方面的初步研究。Aqueduct［9］是一種異質(zhì)網(wǎng)絡(luò)代碼分發(fā)協(xié)議，網(wǎng)絡(luò)中的節(jié)點分為轉(zhuǎn)發(fā)節(jié)點(不需進(jìn)行代碼更新，只起連接傳輸路徑的作用)和成員節(jié)點(需要進(jìn)行代碼更新)兩類，減少了參與代碼更新的節(jié)點數(shù)，成員節(jié)點緩存所有代碼，轉(zhuǎn)發(fā)節(jié)點緩存部分經(jīng)過轉(zhuǎn)發(fā)的代碼;Aqueduct與我們提出的協(xié)議網(wǎng)絡(luò)環(huán)境相似，但它是在傳統(tǒng)的ADV－REQ－DATA三次握手協(xié)議的基礎(chǔ)上增加了范圍選擇功能，是一種數(shù)據(jù)包級的范圍選擇協(xié)議。TinyCubus［10］為異質(zhì)網(wǎng)絡(luò)提出了一種跨層的框架，由數(shù)據(jù)管理框架、跨層框架和配置引擎三部分組成;前兩部分支持異質(zhì)傳感網(wǎng)絡(luò)中數(shù)據(jù)獲取，配置引擎采用一種靈活的描述語言并使用規(guī)則進(jìn)行范圍選擇，如“通過檢測振動的節(jié)點再編程檢測溫度的節(jié)點”，但該方案不能保證到達(dá)所有目標(biāo)節(jié)點并進(jìn)行再編程［6］。Melete［11］通過將節(jié)點分組(如監(jiān)視一個房間溫度的所有節(jié)點)構(gòu)造一個“轉(zhuǎn)發(fā)區(qū)域”來控制再編程節(jié)點的范圍，并假設(shè)連接節(jié)點的網(wǎng)關(guān)存儲所有應(yīng)用程序代碼;然而，如果節(jié)點的物理位置不在一個組內(nèi)，再編程的范圍將增長到整個網(wǎng)絡(luò)［12］。Starburst SSD［12］引入了 Hub 節(jié)點(類似于文獻(xiàn)［11］中的網(wǎng)關(guān))，根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和動態(tài)性，一個節(jié)點子集動態(tài)地選擇連接到不同的Hub;并在數(shù)據(jù)包中加入字段來限制再編程范圍，例如，字段表達(dá)式＜VariabledId，Operator，Operand1，Operand2 ＞ 中 的VariabledId是發(fā)布變量，Operator是比較操作符，后面兩個參數(shù)為操作數(shù)，如再編程“感知溫度超過70℃的節(jié)點”;由于更新代碼分成了許多包，節(jié)點接收每個包都要進(jìn)行運算來檢測自己是否接收該數(shù)據(jù)，會消耗節(jié)點的能量;此外，這種依靠規(guī)則來選擇范圍有可能帶來更新代碼不兼容問題，也就是說不同硬件或操作系統(tǒng)平臺的節(jié)點可能都滿足指定的規(guī)則而更新為相同的軟件。文獻(xiàn)［13］提出了一種基于模塊化的再編程方案，將軟件代碼分為全局模塊(運行于所有節(jié)點)與局部模塊(運行部分節(jié)點)，再編程任務(wù)分為插入(Insert)、更新(Update)、刪除(Delete)三種操作;更新/刪除通過比較節(jié)點已裝入的模塊來確定節(jié)點的范圍，而插入新模塊通過在Sink節(jié)點中加入元數(shù)據(jù)(MetaData)來限制插入節(jié)點的范圍，但該方案對節(jié)點的軟件設(shè)計與存儲器分配機(jī)制提出了新要求。

ReMo［14］較早地進(jìn)行了無線移動傳感網(wǎng)絡(luò)環(huán)境下的再編程研究，其思路是在節(jié)點移動過程中，根據(jù)節(jié)點密度而動態(tài)地調(diào)整Advertisement的廣播速率，選擇鏈接優(yōu)良的節(jié)點進(jìn)行代碼交換，減少參與代碼傳播的節(jié)點數(shù)從而節(jié)省能量;但探測節(jié)點周圍其它節(jié)點密度需要耗費比較多的能量，并且不一定準(zhǔn)確，該研究不具備節(jié)點范圍選擇。Pasztor等人提出野生動物監(jiān)測傳感網(wǎng)絡(luò)具有范圍選擇的再編程研究［15－16］，該方案基于野生動物(如大象)群體的個體交互，利用它們的存在和關(guān)系(社會行為)進(jìn)行具有節(jié)點范圍選擇的代碼更新;但該方案需要一種新的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，Sink或節(jié)點一方是可移動的，或者它們都是可移動的，這涉及到移動路線、方式、速率等問題。

2 系統(tǒng)模型

為了描述方便，本研究的系統(tǒng)模型如下:

(1)整個網(wǎng)絡(luò)有一個Sink(基站)，M個節(jié)點隨機(jī)分布在一個二維區(qū)域A;其中M個節(jié)點分為T類，每類節(jié)點有 Nii∈(1，T)，M=N1+…+Ni+…+NT;每個節(jié)點擁有唯一的ID(Sink的ID為0)，且都能通過同類或非同類節(jié)點將自己感知的數(shù)據(jù)通過單跳或多跳的方式傳送到Sink，如圖1所示，圖中有正方形、圓形、菱形三類節(jié)點，對菱形節(jié)點進(jìn)行代碼更新;

(2)再編程是網(wǎng)絡(luò)管理員對部署好的傳感網(wǎng)絡(luò)發(fā)起的強(qiáng)制性操作，Sink知道每類節(jié)點的個數(shù)Ni，i∈(1，T);

(3)同類節(jié)點運行相同版本的應(yīng)用程序Vi，i∈(1，T);

(4)更新的代碼分為在Sink端分為P1P2…PC段，每段 Pk，k∈(1，C)的長度為 L(最后一段 PC可以小于L);

(5)每個節(jié)點配備足夠的NAND閃存，接收到的每一個代碼段Pk按順序存放于NAND閃存中;節(jié)點執(zhí)行重啟動后，新的應(yīng)用程序從NAND閃存轉(zhuǎn)入內(nèi)存中;

(6)和其它研究相同，節(jié)點是靜止的，且無線通信為雙向的;由于再編程過程相對于傳感網(wǎng)絡(luò)工作過程來說是很短暫的，假定這期間節(jié)點不會故障且沒有新的節(jié)點加入;

(7)沒有類似于文獻(xiàn)［11－12］中的Hub節(jié)點，不需要節(jié)點的任何位置信息。

圖1 再編程網(wǎng)絡(luò)結(jié)構(gòu)(對菱形節(jié)點進(jìn)行代碼更新)

3 協(xié)議描述

本文提出的協(xié)議分為3部分:

①路由形成 在代碼傳送前，先形成到所有選擇節(jié)點的路由，排除不參與代碼更新的節(jié)點，類似與傳感網(wǎng)絡(luò)數(shù)據(jù)收集中的AODV、DSR［17］等路由發(fā)現(xiàn)階段，但這些協(xié)議是End-to-End，而再編程是Oneto-Many協(xié)議;

②代碼傳送 形成路由后，代碼傳送變成了一條范圍內(nèi)的單播或組播，而不是傳統(tǒng)協(xié)議中的廣播;

③請求丟失包 參與代碼更新的節(jié)點請求丟失的數(shù)據(jù)包(單播方式)。

3．1 節(jié)點類型

傳感網(wǎng)絡(luò)再編程是對已經(jīng)部屬好并且可能運行一段時間后的節(jié)點進(jìn)行代碼更新，在我們的協(xié)議中，使用了3種類型節(jié)點:同類邊界節(jié)點、同類中間節(jié)點、異類中間節(jié)點。每個節(jié)點收到消息(見§3．2協(xié)議消息)時，能確定自己屬于哪類節(jié)點。

同類邊界節(jié)點:指網(wǎng)絡(luò)中那些自己感知數(shù)據(jù)，不轉(zhuǎn)發(fā)其它同類節(jié)點感知數(shù)據(jù)，又需要進(jìn)行代碼更新的節(jié)點，如圖1中的i，r，t等節(jié)點;同類邊界節(jié)點只接收消息和相關(guān)數(shù)據(jù)，不再進(jìn)行轉(zhuǎn)發(fā)消息和數(shù)據(jù)。與之對應(yīng)的異類邊界節(jié)點(a，l，o)在確定自己是異類后(不同Vi)，不接收相關(guān)數(shù)據(jù)，也不轉(zhuǎn)發(fā)消息。同類邊界節(jié)點可能變成異類中間節(jié)點，如圖1中的y，v在對圓形節(jié)點更新代碼時就變成異類中間節(jié)點。

同類中間節(jié)點:指那些自己感知數(shù)據(jù)且轉(zhuǎn)發(fā)其它節(jié)點感知數(shù)據(jù)的同類節(jié)點(相同Vi)，這類節(jié)點接收更新代碼后，自己變成源節(jié)點，并向周圍節(jié)點轉(zhuǎn)發(fā)，如圖 1 中的 b，d，f，m 等節(jié)點。

異類中間節(jié)點:指那些自己感知數(shù)據(jù)且轉(zhuǎn)發(fā)其它節(jié)點感知數(shù)據(jù)的異類節(jié)點(不同Vi)，這類節(jié)點只起中間橋接作用轉(zhuǎn)發(fā)數(shù)據(jù)，不保存數(shù)據(jù)，如圖1中的e，g，j，p 等節(jié)點。

3．2 協(xié)議消息

本協(xié)議中使用了6種消息，消息格式見圖2。

Rcreation:形成路由，消息中的“同類數(shù)據(jù)源節(jié)點ID”與“異類中間轉(zhuǎn)發(fā)節(jié)點ID”只有一個是有效的，最開始由Sink發(fā)出(“同類數(shù)據(jù)源節(jié)點ID”為0)，“最大跳數(shù)Max”為Sink接收感知數(shù)據(jù)時獲得到最遠(yuǎn)節(jié)點的距離;中間節(jié)點(同類和異類)收到Rcreation后(可能有多個)，選擇 Hop最小的Rcreation(如果Hop相同，選擇先到的)，將Max減1后保存該消息，形成該消息備份，并做如下處理:(1)同類中間節(jié)點將原“同類數(shù)據(jù)源節(jié)點ID”改為自己的ID，“異類中間轉(zhuǎn)發(fā)節(jié)點ID”置為空，并將跳數(shù)(Hop)置為0，繼續(xù)廣播新的Rcreation;(2)異類中間節(jié)點將原“同類數(shù)據(jù)源節(jié)點ID”置為空，“異類中間轉(zhuǎn)發(fā)節(jié)點ID”改為自己的ID，并將跳數(shù)(Hop)加1，繼續(xù)廣播新的Rcreation;如果再收到Rcreation消息，比較消息中的“更新軟件版本Vi”，相同版本不作處理。

Rresponse:路由響應(yīng)，最開始由同類邊界節(jié)點發(fā)出Rresponse，說明該節(jié)點參與再編程，如圖1中的 k，x，r，t，q，y 等;“發(fā)出節(jié) ID”為邊界節(jié)點自身ID，“同類節(jié)點計數(shù)HemoCount”設(shè)置為1。在一個時間段內(nèi)，同類邊界節(jié)點可能收到多個Rcreation消息，選擇Hop最小的Rcreation(如果Hop相同，選擇先到的)保存，Rcreation消息中的“同類數(shù)據(jù)源節(jié)點ID”或“異類中間轉(zhuǎn)發(fā)節(jié)點ID”作為Rresponse消息中的“數(shù)據(jù)源節(jié)點ID”，單播給數(shù)據(jù)源節(jié)點。如圖1中的節(jié)點y，會收到來自節(jié)點 g(Hop=2)和節(jié)點f(Hop=0)的兩條Rcreation，就選擇f作為數(shù)據(jù)源節(jié)點;而對于節(jié)點 i，節(jié)點w，d發(fā)出的Rcreation消息Hop都為0，就按時間先后順序了。

對于中間節(jié)點(同類或異類)，將收到的多個Rresponse中的“同類節(jié)點計數(shù)HomoCount”或“異類節(jié)點計數(shù)HeteroCount”進(jìn)行累加，并在存儲器中形成“接收節(jié)點ID序列”(序列的長度等于收到的Rresponse消息數(shù))用于后續(xù)代碼傳送。表1列出了中間節(jié)點 s，p，n，m，j，f，b 形成的 Rresponse 中相關(guān)字段的值。

表1 中間節(jié)點 s、p、n、m、j、f、b 形成的 Rresponse 消息

中間節(jié)點如果在規(guī)定的時間內(nèi)(見§3．3協(xié)議算法)接收不到Rresponse，就不參與代碼轉(zhuǎn)發(fā)了，如圖1中的節(jié)點v，h節(jié)點，但同類中間節(jié)點v要參與代碼接收。

Dadv與Dsend:數(shù)據(jù)廣告與數(shù)據(jù)發(fā)送，形成路由后，最開始由Sink發(fā)出，中間節(jié)點收到Dadv后，將在路由形成時生成的“接收節(jié)點ID序列”復(fù)制到Dadv“接收節(jié)點ID序列”字段中，采取單播或組播(而不是廣播)的方式傳送代碼數(shù)據(jù)。

Drequest與Dresend:由同類邊界或中間節(jié)點發(fā)出Drequest，同類中間或Sink節(jié)點發(fā)出Dresend。接收數(shù)據(jù)時，如果由于某種原因(校驗位出錯)需要重傳輸某個數(shù)據(jù)包，就由請求節(jié)點向該節(jié)點生成的Rresponse消息中“數(shù)據(jù)源節(jié)點”單播發(fā)出Drequest(“目標(biāo)節(jié)點序列”字段為請求節(jié)點的ID);如果該數(shù)據(jù)源節(jié)點(同類)有請求的代碼包Pk，就在單跳范圍內(nèi)將Pk單播Dresend給請求節(jié)點;否則就在Drequest消息的“目標(biāo)節(jié)點序列”中添加該節(jié)點ID，并向它的數(shù)據(jù)源節(jié)點轉(zhuǎn)發(fā)Drequest;經(jīng)歷幾跳后，如果某個數(shù)據(jù)源節(jié)點有代碼包Pk，就向請求節(jié)點單播發(fā)送Dresend(該消息中的“目標(biāo)節(jié)點序列”為逆向的Drequest消息中“目標(biāo)節(jié)點序列”)。

3．3 協(xié)議算法

本協(xié)議的基本思想就是先形成完整的代碼傳送路由，排除參與代碼轉(zhuǎn)發(fā)的異類中間節(jié)點、同類中間節(jié)點，變傳統(tǒng)再編程的廣播為單播或組播，從而節(jié)省整個網(wǎng)絡(luò)的能量消耗和提高再編程的效率，作為再編程的總指揮Sink節(jié)點，在形成路由時，還獲得了“同類節(jié)點計數(shù) HomoCount”、“異類節(jié)點計數(shù) HeteroCount”等信息。

協(xié)議的關(guān)鍵是路由形成時間段的確定，由于Sink知道最遠(yuǎn)邊界節(jié)點到Sink的距離H(跳數(shù))，并將此值作為開始的 Rcreation消息重“最大跳數(shù)Max”字段的初值，Rcreation每經(jīng)過一個中間節(jié)點，其Max減1;假定在1跳范圍傳輸Rcreation消息的時間為τ，則形成路由總的時間(Sink發(fā)出Rcreation消息后，收到Rresponse消息的時間間隔)的最大值為2·H·τ?？偠螖?shù)C與某段代碼段Pk保證節(jié)點亂序接收到某代碼段后能寫入NAND閃存中的正確位置，接收完C段代碼后確定接收完成;如果節(jié)點有丟失或出錯的數(shù)據(jù)包，通過周期性地廣播Drequest獲取。圖3為同類中間節(jié)點si算法的主要部分流程圖，協(xié)議的主要操作過程如下:

(1)Sink將更新的代碼分為P1P2…PC段，獲得本次傳輸?shù)拇a段最大值C。

(2)Sink確定填寫“更新軟件版本Vi”、“最大跳數(shù)Max”等值后，發(fā)出形成路由Rcreation消息。

(3)中間節(jié)點收到Rcreation，通過比較Vi就知道自己屬于同類中間節(jié)點或是異類中間節(jié)點，并按中間節(jié)點類型處理并轉(zhuǎn)發(fā)(廣播)Rcreation消息(見§3．2 協(xié)議消息)。

(4)同類邊界節(jié)點收到Rcreation消息，向上一級節(jié)點單播Rresponse消息。

(5)中間節(jié)點收到Rresponse，形成向上級(同類源節(jié)點或異類中間節(jié)點)路由和向下級(接收代碼)節(jié)點 ID序列等信息，并向上一級節(jié)點單播Rresponse消息(見 §3．2 協(xié)議消息)。在 2·Max·τ時間范圍內(nèi)(注意Max在不同級的中間節(jié)點值是不同的)沒有收到Rresponse消息的節(jié)點就不再參與代碼轉(zhuǎn)發(fā)了。

(6)Sink收到Rresponse消息(大于等于1條)后，具有范圍選擇的代碼傳送路由形成完畢，通過累加，獲取了全網(wǎng)參與代碼更新的“同類節(jié)點計數(shù)HomoCount”和“異類節(jié)點計數(shù)HeteroCount”信息。

(7)Sink循環(huán)發(fā)送(單播或組播)Dadv與Dsend，異類中間節(jié)點只轉(zhuǎn)發(fā)Dadv與Dsend，同類中間節(jié)點接收并轉(zhuǎn)發(fā)Dadv與Dsend(也有只接收不轉(zhuǎn)發(fā)的同類中間節(jié)點，如圖1中的v節(jié)點)。

(8)同類中間節(jié)點或同類邊界節(jié)點可以通過發(fā)出Drequest請求丟失的代碼包。

(9)接收完C段代碼后，節(jié)點執(zhí)行重起動運行新的代碼。

圖3 中間節(jié)點算法流程圖

4 性能分析

4．1 減少REQ消息數(shù)與代碼傳輸總時間

本協(xié)議先在2·H·τ時間內(nèi)形成路由和接收代碼節(jié)點序列，排除不參與更新代碼轉(zhuǎn)發(fā)的中間同類和異類節(jié)點，中間節(jié)點在一跳范圍內(nèi)采取單播或組播的方式傳送更新代碼給接收代碼節(jié)點序列，減少了大量REQ確認(rèn)信息包。在傳統(tǒng)的ADV－REQDATA三次握手該協(xié)議中，對每一個數(shù)據(jù)包，數(shù)據(jù)源節(jié)點(Sink或中間節(jié)點)先發(fā)出ADV消息后，需要等待一個時間片δ接收需要DATA節(jié)點發(fā)出的REQ消息后，才發(fā)送DATA，但眾多的REQ會帶來類似于確認(rèn)爆炸(ACK Implosion)問題［18］。而我們提出的協(xié)議在形成路由時發(fā)送一次(Rresponse，相當(dāng)于REQ)，由于Dadv消息中帶有接收代碼節(jié)點序列，收到Dadv的節(jié)點知道應(yīng)該接收后續(xù)的Dsend，數(shù)據(jù)源節(jié)點不需要等待REQ消息，用TotalRt、TotalTt和TotalRo、TotalTo分別表示傳統(tǒng)協(xié)議和我們提出協(xié)議總的REQ數(shù)、傳送完代碼總的時間，則(λ為在一跳范圍內(nèi)傳送代碼段Pk的時間):

由于Pk遠(yuǎn)大于 Rcreation和 Rresponse，δ為等待多個REQ的時間，因而λ遠(yuǎn)大于τ，δ大于τ。因此，我們的方案優(yōu)于傳統(tǒng)的三次握手該協(xié)議;代碼段C越大，我們的方案越優(yōu)。

4．2 平均延時與能量消耗

我們提出協(xié)議為三階段協(xié)議ThreeStages，其網(wǎng)絡(luò)模型與Aqueduct相似，網(wǎng)絡(luò)中沒有Hub、網(wǎng)關(guān)等專用節(jié)點，全是可再編程的不同類型節(jié)點。因此，我們比較ThreeStages與Aqueduct的性能。在不同代碼大小傳輸下，我們在OMNet++4．0網(wǎng)絡(luò)仿真環(huán)境下比較兩種協(xié)議的性能。我們假定傳感節(jié)點隨機(jī)分布在7×7的網(wǎng)格內(nèi)，節(jié)點總數(shù)為49，再編程范圍為菱形節(jié)點，總數(shù)為20個，圓形節(jié)點為29個，如圖4所示。模擬參數(shù)見表2，模擬結(jié)果見圖5、圖6。

圖4 模擬實驗節(jié)點分布圖(菱形為再編程節(jié)點)

表2 模擬參數(shù)

圖5 不同更新代碼大小下的平均延時

從圖5中可以看出，在傳輸完不同大小代碼影像(30 k～80 k)的平均延時方面，ThreeStages明顯優(yōu)于Aqueduct，原因是ThreeStages是先形成路由，再傳送代碼;而Aqueduct是在ADV－REQ－DATA的基礎(chǔ)上增加了轉(zhuǎn)發(fā)功能，也就是說中間節(jié)點在轉(zhuǎn)發(fā)每一個代碼數(shù)據(jù)段Pi時，都需要等待一個時間片δ;而ThreeStages只在路由形成階段需要等待，延時的主要部分是Pi的傳輸時間。

圖6 不同更新代碼大小下的消息總數(shù)

我們沒有直接測試每個節(jié)點的能量消耗，而是統(tǒng)計出所有節(jié)點轉(zhuǎn)發(fā)的消息數(shù)。因為發(fā)送/接收消息遠(yuǎn)比計算指令更耗費能量。在圖6中，由于ThreeStages在路由形成的2·H·τ時間內(nèi)，采用泛洪的廣播方式轉(zhuǎn)發(fā)了比較多的消息;而在代碼傳送階段采取組播或單播的形式傳送，有效地減少了中間節(jié)點數(shù)，從而減少了消息數(shù)。例如，在代碼傳送階段，Sink只需要單播給左上角的菱形節(jié)點，緊靠該節(jié)點的兩個圓形節(jié)點不參與代碼轉(zhuǎn)發(fā)了。但是，在重傳輸率比較大時(50%)，由于ThreeStages沒有采取異類中間節(jié)點緩存，消息數(shù)增加明顯，這是該協(xié)議需要改進(jìn)的地方。

5 結(jié)論

已有的傳感網(wǎng)絡(luò)再編程協(xié)議大多假定網(wǎng)絡(luò)中所有節(jié)點，運行同一版本的應(yīng)用程序，沒有節(jié)點范圍選擇，基于泛洪的代碼傳送方式盡管能在很短的時間內(nèi)將更新代碼傳遍整個網(wǎng)絡(luò)，但也帶來了很多不必要的消息開銷。本文提出了一種新的具有范圍選擇的再編程協(xié)議，該協(xié)議變傳統(tǒng)的ADV－REQ－DATA三次握手該協(xié)議為路由形成、代碼傳送、請求丟失包三個階段協(xié)議，有效地降低了參與代碼轉(zhuǎn)發(fā)的中間節(jié)點數(shù)，提高了代碼傳送的有效性。接下來準(zhǔn)備將緩存相關(guān)理論引入代碼傳送中，研究有效的緩存策略算法，進(jìn)一步完善本協(xié)議。

［1］ Kateeb A E．Hardware Reconfiguration Capability for Third-Generation Sensor Nodes［J］．Computer，2009，42(5):95－97．

［2］ Vinayak N，Anish A，Prasun S，et al．Sprinkler:A Reliable and Energy Efficient Data Dissemination Service for Extreme Scale Wireless Networks of Embedded Devices［J］．IEEE Transactions on Mobile Computing，2007，6(7):1－13．

［3］ Krasniewski M D，Panta R K，Bagchi S，et al．Energy-Efficient On-Demand Reprogramming of Large-Scale Sensor Networks［J］．ACM Transactions on Sensor Networks，2008，4(1):Article 2．

［4］ Kulkarni S，Wang L．Energy-Efficient Multihop Reprogramming for Sensor Networks［J］．ACM Transactions on Sensor Networks，2009，5(2):16．

［5］ 譚勁，康順利，金寧．一種基于OLSR的傳感網(wǎng)絡(luò)再編程可靠與能量有效傳輸協(xié)議［J］．傳感技術(shù)學(xué)報，2010，23(8):1146－1152．

［6］ Wang Q，Zhu Y Y，Cheng L．Reprogramming Wireless Sensor Networks:Challenges and Approaches［J］．IEEE Networks，2006，20(3):48－55．

［7］ Shilpa M，Jyoteesh M．Energy Efficient Control Strategies in Heterogeneous Wireless Sensor Networks:A Survey［J］．International Journal of Computer Applications，2011，14(6):31－37．

［8］ 潘巨龍，李善平，吳震東，等．一種基于無線傳感器網(wǎng)絡(luò)安全的社區(qū)衛(wèi)生保健監(jiān)護(hù)系統(tǒng)設(shè)計［J］．傳感技術(shù)學(xué)報，2009，22(6):838－843．

［9］ Phillips L A．Aqueduct:Robust and Efficient Code Propagation in Heterogeneous Wireless Sensor Networks［D］．Master’s thesis，University of Colorado，2005．

［10］ Pedro J M，Daniel M，Andreas L，et al．TinyCubus:An Adaptive Cross-Layer Framework for Sensor Networks［J］．Information Technology，2005，47(2):87－97．

［11］ Yu Y，Rittle L J．Supporting Concurrent Applications in Wireless Sensor Networks［C］//Proc．of the 4th International Conference on Embedded Networked Sensor Systems，Boulder，Colorado，USA，November 2006．

［12］ Tahir A，Qasim M，Philip L．Starburst SSD:An Efficient Protocol for Selective Dissemination［C］//Proc．of the IEEE International Conference on Communications，Dresden，Germany，June 2009．

［13］ Lee S H，Choi L，Nah Y．Policy-Based Reprogramming for Wireless Sensor Networks［C］//Proc．ofthe13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops，Carmona，Sevilla，Spain，May 2010．

［14］ De P，Liu Y，Das S K．ReMo:An Energy Efficient Reprogramming Protocol for Mobile Sensor Networks［C］//Proc．of Sixth Annual IEEE International Conference on Pervasive Computing and Communications，Hong Kong，March 2008．

［15］ Pasztor B，Mottola L，Mascolo C，et al．Selective Code Dissemination in Mobile Wireless Sensor Networks［C］//Proc．of the ACM/IFIP/USENIX Middleware Conference Companion， Leuven，Belgium，December 2008．

［16］ Pasztor B，Mottola L，Mascolo C，et al．Selective Reprogramming of Mobile Sensor Networks through Social Community Detection［C］//Proc．of the European Conference on Wireless Sensor Networks，Coimbra，Portugal，F(xiàn)ebruary 2010．

［17］ Jeya Kumar M K，Rajesh R S．A Survey of MANET Routing Protocols in Mobility Models［J］．InternationalJournalofSoft Computing，2009，4(3):136－141．

［18］ Yamamoto K，Sawa Y，Yamamoto M，et al．Performance Evaluation of ACK-Based and NAK-Based Flow Control Schemes for Reliable Multicast［C］//Proc．of IEEE TENCON 2000，Kuala Lumpur，Malaysia，September 2000．