具有范圍選擇的傳感網絡再編程協議算法研究

譚 勁，張曼曼，禇 娜

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

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

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

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

1 相關工作

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

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

2 系統模型

為了描述方便，本研究的系統模型如下:

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

(2)再編程是網絡管理員對部署好的傳感網絡發起的強制性操作，Sink知道每類節點的個數Ni，i∈(1，T);

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

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

(5)每個節點配備足夠的NAND閃存，接收到的每一個代碼段Pk按順序存放于NAND閃存中;節點執行重啟動后，新的應用程序從NAND閃存轉入內存中;

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

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

圖1 再編程網絡結構(對菱形節點進行代碼更新)

3 協議描述

本文提出的協議分為3部分:

①路由形成 在代碼傳送前，先形成到所有選擇節點的路由，排除不參與代碼更新的節點，類似與傳感網絡數據收集中的AODV、DSR［17］等路由發現階段，但這些協議是End-to-End，而再編程是Oneto-Many協議;

②代碼傳送 形成路由后，代碼傳送變成了一條范圍內的單播或組播，而不是傳統協議中的廣播;

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

3．1 節點類型

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

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

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

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

3．2 協議消息

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

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

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

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

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

中間節點如果在規定的時間內(見§3．3協議算法)接收不到Rresponse，就不參與代碼轉發了，如圖1中的節點v，h節點，但同類中間節點v要參與代碼接收。

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

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

3．3 協議算法

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

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

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

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

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

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

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

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

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

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

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

圖3 中間節點算法流程圖

4 性能分析

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

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

由于Pk遠大于 Rcreation和 Rresponse，δ為等待多個REQ的時間，因而λ遠大于τ，δ大于τ。因此，我們的方案優于傳統的三次握手該協議;代碼段C越大，我們的方案越優。

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

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

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

表2 模擬參數

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

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

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

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

5 結論

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

［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的傳感網絡再編程可靠與能量有效傳輸協議［J］．傳感技術學報，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］ 潘巨龍，李善平，吳震東，等．一種基于無線傳感器網絡安全的社區衛生保健監護系統設計［J］．傳感技術學報，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，February 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．