一種基于多播分發樹的無線傳感器網絡代碼分發協議*

任萬春， 馬廷淮， 劉 琦

(南京信息工程大學 計算機與軟件學院，江蘇 南京 210044)

0 引 言

無線傳感器網絡(WSNs)在實地部署之后,隨著用戶需求的變化和技術的進步,不可避免地需要修改傳感器節點的軟件功能或者修復節點軟件中存在的問題。傳感器節點可能部署在環境非常惡劣的人類不可抵達區域(如火山、深海)，人工回收傳感器節點也有可能破壞監測過程(如鳥類生活習性監測)，因此，人工燒錄節點的方式不能滿足實際應用的需要。使用代碼分發協議通過無線方式進行代碼更新是上述問題的有效解決途徑[1]。代碼分發協議已經成為現階段無線傳感器網絡研究的熱點問題。

Deluge協議[2]是TinyOS系統的標準代碼分發協議，采用ADV-REQ-DATA三次握手機制和NACK(negatrue acknowledge)機制來保證可靠性。該協議提出了分頁機制，使得網絡能夠使用流水線進行空間多路分發，大大提高了分發速度。

Typhoon協議[3]使用Snoop機制進行數據偵聽，在進行快速重傳的同時，降低了數據碰撞概率，使用信道轉換技術解決了隱蔽站問題，提高了空間多路傳輸的效率。

ECD協議[4]提出了一種基于鏈路質量的發送節點選擇算法，該算法選擇鏈路質量最優的節點作為發送節點，提高了發送節點選擇的精確度。此外,該協議能夠動態地對數據包大小進行配置，極大提高了代碼分發的效率。

SYNAPASE++協議[5]使用無比率噴泉碼對數據包進行錯誤恢復，通過降低數據包重傳次數提高代碼分發效率,同時采用了基于NACK的ARQ錯誤恢復機制進一步提高了代碼分發效率。

綜上所述，傳統的代碼分發協議基于傳染病[6]機制通過廣播方式進行數據傳輸，網絡中所有節點都要參與代碼分發并接收到完整的新代碼文件。在實際應用中，不同傳感器節點的硬件結構可能不同，不同傳感器節點也可能需要負責不同的感知或通信任務，這樣就造成不同傳感器節點執行的代碼鏡像文件的差異，對不同類型的節點需要分發不同的代碼鏡像文件。使用傳染病算法對特定目標節點進行代碼分發有以下不足：1)冗余代碼鏡像的傳輸浪費大量的網絡資源；2)所有節點參與代碼分發，對網絡監測應用造成影響。

因此，本文提出了一種基于多播分發樹的代碼分發(multicast dissemination tree-based code dissemination，MTCD)協議。MTCD協議通過建立分發樹將代碼文件發送到網絡中指定的目標節點上，使得在面向特定目標節點進行代碼分發時，降低參與代碼分發節點的數目，避免冗余代碼數據的傳輸。

1 MTCD協議的模型

1.1 MTCD協議的原理

MTCD協議能夠將代碼鏡像文件分發到網絡中指定的目標節點中，其核心在于建立以基站節點為樹根節點的多播分發樹。如圖1所示，MTCD協議通過廣播發送代碼版本消息，使網絡中所有節點建立到基站節點的路由路徑，形成以基站節點為根節點的多播分發樹。指定目標節點向其上游節點發送代碼請求消息，代碼請求消息通過分發樹多跳傳輸到基站節點。基站節點在接收到目標節點的代碼數據請求后，沿著代碼請求的路徑將代碼數據發送到目標節點。

圖1 MTCD協議的代碼分發過程

1.2 代碼版本廣播

用戶將編譯好的代碼鏡像文件通過串口發送到基站節點，當基站節點接收到完整的代碼鏡像文件后，開始廣播發送代碼版本消息，代碼版本消息描述了代碼鏡像的摘要信息，其中標識號(UID)是每個代碼文件的唯一標識；類型號(Type)用來區分傳感器網絡中不同類型的傳感器節點；版本號碼(CodeVersion)代表代碼鏡像文件的版本號碼；代碼大小(CodeSize)和頁數(PageNum)用來描述代碼文件的大小和代碼文件包含的頁數；TTL用來描述代碼版本消息的生存周期；序列號(SequenceNum)用來區分不同廣播周期發送的代碼版本消息。MTCD協議使用泛洪方式發送代碼版本消息，在泛洪的過程中，網絡中的每個節點都選擇一個鄰居節點作為其父節點，這樣就建立了以基站節點為根節點的分發樹。

1.3 代碼數據請求

由于代碼文件占用存儲空間很大(10～50 kB)，遠遠超過節點的內存容量，因此，代碼鏡像文件被劃分為固定大小的頁，頁被劃分為固定大小的數據包，如圖2所示。每頁的數據量占用內存較小，能夠滿足節點的內存容量要求，基站節點到目標節點的數據傳輸以頁為單位進行。目標節點通過發送代碼請求消息來請求頁面數據，代碼請求消息沿著分發樹進行頁面數據請求，基站節點作為分發樹的根節點逐頁發送數據。代碼請求消息中包含節點自身ID、目標節點ID、請求頁號、請求數據包號。目標節點只有在完整接收到一個頁的數據后，才進行下一個頁的請求。

圖2 代碼鏡像文件劃分

1.4 代碼數據發送

節點接收到下游節點發送的代碼請求消息后，向其父節點進行代碼數據請求。代碼請求從目標節點經過中間節點轉發到基站節點，基站節點接收到代碼請求消息后，將代碼數據封裝在代碼數據消息中發送。代碼數據消息包括下游請求節點ID、目標節點ID和代碼數據。代碼數據沿著分發樹從基站節點先發送到離基站較近的中間節點，然后通過多跳傳輸到目標節點。

2 多播分發樹的建立與維護

MTCD協議的核心在于通過基站節點到目標節點之間的路由路徑來進行代碼數據的分發。路由路徑的建立基于網絡中節點的鄰居節點表和請求節點表。鄰居節點表用來記錄鄰居節點的狀態信息，每條記錄包含鄰居節點ID、鄰居節點到基站的跳數、鄰居節點到本節點的鏈路質量、以及鄰居節點是否為本節點的父節點。請求節點表用來記錄向本節點請求數據的下游節點的信息，每條記錄包括其請求節點ID、代碼文件標識號(UID)、請求頁的號碼、請求數據包的號碼和目標節點ID。

2.1 普通節點的算法流程

MTCD協議通過代碼版本消息建立和維護分發樹。基站節點周期性地廣播發送代碼版本消息，節點通過代碼版本消息對其鄰居節點表進行更新，這樣,如果新的節點加入到網絡或者節點失效，依然能夠建立新的分發樹進行數據分發。當網絡中的節點接收到代碼版本消息時，可以通過代碼版本消息中的TTL來計算鄰居節點到基站節點的跳數；鏈路質量可以使用無線信號的接收信號強度指示(RSSI)或者鏈路質量指示(LQI)來表示。節點選擇鄰居節點中到基站距離(跳數)最小并且鏈路質量最優的節點為父節點。

如圖3所示，節點在接收到代碼版本消息后，對節點的鄰居節點表進行更新，同時更新其父節點。網絡中的所有節點在起初都是普通節點，普通節點在接收到代碼版本消息后，如果代碼版本消息中的Type號與自身的相同，并且代碼版本消息中的代碼版本號也要比自身的新，那么,此節點成為目標節點。代碼版本消息中的序列號(SequenceNum)越大，說明是越新的代碼版本消息。如果接收到的是新的代碼版本消息,則節點重新將此代碼版本消息廣播發送。當節點接收到代碼請求消息后，對其自身的請求節點表進行更新。如果節點已經有請求頁的數據，那么,節點直接將請求頁的數據發送給下游的請求節點；如果節點正在向父節點請求這個頁的數據，那么,等接收完請求頁的數據后進行轉發；否則，節點將代碼請求消息轉發給其父節點。當普通節點接收到代碼數據消息時，通過查詢自身的請求節點表，將代碼數據轉發給下游的請求節點。

圖3 普通節點流程圖

2.2 目標節點的算法流程

如圖4所示，當目標節點接收到代碼數據消息時，如果代碼數據消息的目標節點不是本節點，那么節點根據其請求節點表將收到的代碼數據消息轉發給請求節點。如果代碼數據消息的目標節點是本節點，則將代碼數據存儲入外存中；如果已接收到完整的代碼頁數據，則發送代碼請求消息進行下一個頁的傳輸。當目標節點接收到完整的代碼鏡像后，目標節點停止周期性發送代碼請求消息，節點從目標節點變化為普通節點。

圖4 目標節點流程圖

請求節點表的每條記錄都有一個有效時間，如果記錄在有效時間內未進行更新，那么就將此條記錄從請求節點表刪除。每個目標節點都會周期性地發送代碼請求消息對路徑上節點的請求節點表進行更新。當目標節點接收到完整鏡像時，停止發送代碼請求消息。其上游節點的請求節點表中的記錄在超過有效時間后被刪除。

3 MTCD協議的可靠性機制

由于代碼鏡像文件的特殊性，代碼分發協議必須保證目標節點接收到100%可靠地代碼鏡像文件。保證傳輸可靠性的機制主要有兩種，糾錯編碼機制和重傳機制。糾錯編碼機制在每個數據包附加大量的冗余數據來進行數據恢復，額外消耗能量較多。傳感器網絡多采用重傳機制，即使用數據包重傳來保證可靠性，分為NACK(negative acknow-ledge)機制與ACK(acknowledge)機制。

ACK機制由發送節點負責丟包監測，即接收節點每接收到數據包，就發送ACK包給發送節點進行確認，發送節點在接收到ACK包后確認數據包成功發送，否則，需要重傳此數據包。傳統的分發協議多采用NACK機制，即接收節點進行丟包監測，接收節點周期性地根據數據接收狀態來發送重傳請求消息進行數據請求。傳統的分發協議由于使用傳染病算法，數據發送采用的是廣播方式。如果使用ACK機制，由于廣播域內的節點都會發送ACK包進行數據確認，會造成網絡擁塞。

MTCD協議代碼數據的發送是基于單播，避免了ACK機制可能引起的網絡擁塞問題。如果使用NACK機制，由于NACK機制必須由接收節點周期性地發送重傳請求消息進行數據發送，相比ACK機制，其數據重傳速度較慢，在重傳請求消息的發送周期上浪費大量時間。因此，MTCD協議使用ACK機制進行數據重傳來保證協議的可靠性。

4 實驗結果與分析

本文使用TinyOS系統的專用仿真平臺TOSSIM[7]進行仿真實驗，并與Deluge協議進行對比。實驗的網絡拓撲使用柵格(grid)結構，節點傳輸半徑為5 m，節點間的間距為3 m，實驗用代碼文件大小為33 kB。如圖5所示為一個5 grid×5 grid網絡拓撲，基站節點位于網絡左上角,為測試目標節點位置對MTCD協議的影響，使用MTCD-T代表目標節點為離基站距離固定為2跳的黑色節點；MTCD-R代表目標節點為網絡右下角的2個灰色節點。通過改變每條邊上節點的個數，來測試網絡3×3～10×10不同節點規模下的性能。文獻[8]給出了傳感器每項操作耗費能量的經驗模型，通過統計各項操作次數結合經驗模型計算其各項操作的耗費能量。

圖5 5 grid×5grid網絡拓撲

圖6是協議在不同節點規模下的分發時間對比。分發時間是與目標節點到基站節點的距離相關的，距離越大，需要耗費在路由轉發上的時間就越多。MTCD-R隨著節點規模變大，分發時間漸漸超過Deluge協議，這是由于隨著路由路徑變長，路由路徑失效的概率增大，每次路由路徑失效，都需花費大量時間進行路由重建。

圖6 分發時間對比

圖7是協議在不同節點規模下的空閑偵聽耗費能量對比。空閑偵聽耗費能量與網絡中參與分發的節點數目以及分發耗費時間相關。Deluge協議是面向全網節點分發的，因此,網絡中所有節點總空閑偵聽時間很大。隨著節點規模的擴大，MTCD-R路由路徑上節點數目變多，分發時間耗費能量逐漸增多；MTCD-T由于參與分發節點數目很少，分發耗費時間最低，因此,空閑偵聽能耗是最小的。

圖7 空閑偵聽耗費能量

圖8是協議在不同節點規模下的數據消息耗費能量對比，數據消息指用來發送代碼數據的消息。數據消息耗費能量與數據消息的傳輸次數相關。Deluge協議將代碼數據發送到網絡中所有節點，MTCD協議只需要將代碼數據沿分發樹的路徑進行轉發。因此,MTCD協議的數據消息能耗隨分發樹的路徑長度增大而增大，數據消息傳輸低于Deluge。

圖8 數據消息耗費能量

圖9是協議在不同節點規模下的控制消息耗費能量對比，控制消息不進行代碼數據的傳輸，而是協議用來進行網絡信息交換，包括代碼版本消息、代碼請求消息以及ACK消息。MTCD協議的性能稍優于Deluge協議，MTCD-R的控制消息開銷與MTCD-T相差不大。這是由于MTCD協議的代碼版本消息周期性使用泛洪方式進行廣播發送，造成了大量的控制消息傳輸開銷。

圖9 控制消息耗費能量

5 結 論

本文提出了一種MTCD協議,與傳統的基于傳染病算法的代碼分發協議Deluge相比，MTCD協議通過建立代碼分發目標節點與基站節點之間的路由路徑，減少了網絡中參與代碼分發節點的個數，并保證了協議的可靠性。TOSSIM仿真實驗結果表明：在對指定目標節點進行分發時，MTCD協議的能量消耗遠遠低于Deluge協議。

參考文獻:

[1] 況曉輝,許 飛,劉 麗.無線傳感器網絡遠程代碼更新技術研究進展[J].計算機科學,2013,40(6):255-261.

[2] Hui J,Culler D.The dynamic behavior of a data dissemination protocol for network programming at scale[C]∥Proc ACM SenSys'04.Baltimore,MD,USA:ACM,2004:81-94.

[3] Liang M,Musaloiu-E M,Terzis A.Typhoon:A reliable data dissemination protocol for wireless Sensor Networks [C] ∥EWSN 2008,Bologna,Italy:Springer,2008:268-285.

[4] Dong Wei,Liu Yunhao,Wang Chao,et al.Link quality aware code dissemination in wireless sensor networks[C]∥The 19th IEEE International Conference on Network Protocols,Vancouver,BC:IEEE,2011:89-98.

[5] Rossi M,Bui N,Zanca G,et al.SYNAPSE++:Code dissemination in wireless sensor networks using fountain codes [J].IEEE Transactions on Mobile Computing,2010,9(12):1749-1765.

[6] Akdere M,Bilgin C,Gerdaneri O,et al.A comparison of epidemic algorithms in wireless sensor networks [J].Computer Communications.2006,29:2450-2457.

[7] Levis P,Lee N,Welsh M,et al.TOSSIM:Accurate and scalable simulation of entire TinyOS Applications[C]∥Proc ACM SenSys’03,Los Angeles,CA,USA:ACM 2003:126-137.

[8] Mainwaring A,Culler D,Polastre J,et al.Wireless sensor networks for habitat monitoring∥Proc the 1st ACM International Workshop on Wireless Sensor Networks and Applications,Atlanta,GA,USA:ACM,2002:88-97.