一種基于多播分發(fā)樹的無線傳感器網(wǎng)絡(luò)代碼分發(fā)協(xié)議*

任萬春， 馬廷淮， 劉 琦

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

0 引 言

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

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

Typhoon協(xié)議[3]使用Snoop機制進行數(shù)據(jù)偵聽，在進行快速重傳的同時，降低了數(shù)據(jù)碰撞概率，使用信道轉(zhuǎn)換技術(shù)解決了隱蔽站問題，提高了空間多路傳輸?shù)男省?/p>

ECD協(xié)議[4]提出了一種基于鏈路質(zhì)量的發(fā)送節(jié)點選擇算法，該算法選擇鏈路質(zhì)量最優(yōu)的節(jié)點作為發(fā)送節(jié)點，提高了發(fā)送節(jié)點選擇的精確度。此外,該協(xié)議能夠動態(tài)地對數(shù)據(jù)包大小進行配置，極大提高了代碼分發(fā)的效率。

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

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

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

1 MTCD協(xié)議的模型

1.1 MTCD協(xié)議的原理

MTCD協(xié)議能夠?qū)⒋a鏡像文件分發(fā)到網(wǎng)絡(luò)中指定的目標節(jié)點中，其核心在于建立以基站節(jié)點為樹根節(jié)點的多播分發(fā)樹。如圖1所示，MTCD協(xié)議通過廣播發(fā)送代碼版本消息，使網(wǎng)絡(luò)中所有節(jié)點建立到基站節(jié)點的路由路徑，形成以基站節(jié)點為根節(jié)點的多播分發(fā)樹。指定目標節(jié)點向其上游節(jié)點發(fā)送代碼請求消息，代碼請求消息通過分發(fā)樹多跳傳輸?shù)交竟?jié)點?；竟?jié)點在接收到目標節(jié)點的代碼數(shù)據(jù)請求后，沿著代碼請求的路徑將代碼數(shù)據(jù)發(fā)送到目標節(jié)點。

圖1 MTCD協(xié)議的代碼分發(fā)過程

1.2 代碼版本廣播

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

1.3 代碼數(shù)據(jù)請求

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

圖2 代碼鏡像文件劃分

1.4 代碼數(shù)據(jù)發(fā)送

節(jié)點接收到下游節(jié)點發(fā)送的代碼請求消息后，向其父節(jié)點進行代碼數(shù)據(jù)請求。代碼請求從目標節(jié)點經(jīng)過中間節(jié)點轉(zhuǎn)發(fā)到基站節(jié)點，基站節(jié)點接收到代碼請求消息后，將代碼數(shù)據(jù)封裝在代碼數(shù)據(jù)消息中發(fā)送。代碼數(shù)據(jù)消息包括下游請求節(jié)點ID、目標節(jié)點ID和代碼數(shù)據(jù)。代碼數(shù)據(jù)沿著分發(fā)樹從基站節(jié)點先發(fā)送到離基站較近的中間節(jié)點，然后通過多跳傳輸?shù)侥繕斯?jié)點。

2 多播分發(fā)樹的建立與維護

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

2.1 普通節(jié)點的算法流程

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

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

圖3 普通節(jié)點流程圖

2.2 目標節(jié)點的算法流程

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

圖4 目標節(jié)點流程圖

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

3 MTCD協(xié)議的可靠性機制

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

ACK機制由發(fā)送節(jié)點負責丟包監(jiān)測，即接收節(jié)點每接收到數(shù)據(jù)包，就發(fā)送ACK包給發(fā)送節(jié)點進行確認，發(fā)送節(jié)點在接收到ACK包后確認數(shù)據(jù)包成功發(fā)送，否則，需要重傳此數(shù)據(jù)包。傳統(tǒng)的分發(fā)協(xié)議多采用NACK機制，即接收節(jié)點進行丟包監(jiān)測，接收節(jié)點周期性地根據(jù)數(shù)據(jù)接收狀態(tài)來發(fā)送重傳請求消息進行數(shù)據(jù)請求。傳統(tǒng)的分發(fā)協(xié)議由于使用傳染病算法，數(shù)據(jù)發(fā)送采用的是廣播方式。如果使用ACK機制，由于廣播域內(nèi)的節(jié)點都會發(fā)送ACK包進行數(shù)據(jù)確認，會造成網(wǎng)絡(luò)擁塞。

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

4 實驗結(jié)果與分析

本文使用TinyOS系統(tǒng)的專用仿真平臺TOSSIM[7]進行仿真實驗，并與Deluge協(xié)議進行對比。實驗的網(wǎng)絡(luò)拓撲使用柵格(grid)結(jié)構(gòu)，節(jié)點傳輸半徑為5 m，節(jié)點間的間距為3 m，實驗用代碼文件大小為33 kB。如圖5所示為一個5 grid×5 grid網(wǎng)絡(luò)拓撲，基站節(jié)點位于網(wǎng)絡(luò)左上角,為測試目標節(jié)點位置對MTCD協(xié)議的影響，使用MTCD-T代表目標節(jié)點為離基站距離固定為2跳的黑色節(jié)點；MTCD-R代表目標節(jié)點為網(wǎng)絡(luò)右下角的2個灰色節(jié)點。通過改變每條邊上節(jié)點的個數(shù)，來測試網(wǎng)絡(luò)3×3～10×10不同節(jié)點規(guī)模下的性能。文獻[8]給出了傳感器每項操作耗費能量的經(jīng)驗?zāi)Ｐ?，通過統(tǒng)計各項操作次數(shù)結(jié)合經(jīng)驗?zāi)Ｐ陀嬎闫涓黜棽僮鞯暮馁M能量。

圖5 5 grid×5grid網(wǎng)絡(luò)拓撲

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

圖6 分發(fā)時間對比

圖7是協(xié)議在不同節(jié)點規(guī)模下的空閑偵聽耗費能量對比?？臻e偵聽耗費能量與網(wǎng)絡(luò)中參與分發(fā)的節(jié)點數(shù)目以及分發(fā)耗費時間相關(guān)。Deluge協(xié)議是面向全網(wǎng)節(jié)點分發(fā)的，因此,網(wǎng)絡(luò)中所有節(jié)點總空閑偵聽時間很大。隨著節(jié)點規(guī)模的擴大，MTCD-R路由路徑上節(jié)點數(shù)目變多，分發(fā)時間耗費能量逐漸增多；MTCD-T由于參與分發(fā)節(jié)點數(shù)目很少，分發(fā)耗費時間最低，因此,空閑偵聽能耗是最小的。

圖7 空閑偵聽耗費能量

圖8是協(xié)議在不同節(jié)點規(guī)模下的數(shù)據(jù)消息耗費能量對比，數(shù)據(jù)消息指用來發(fā)送代碼數(shù)據(jù)的消息。數(shù)據(jù)消息耗費能量與數(shù)據(jù)消息的傳輸次數(shù)相關(guān)。Deluge協(xié)議將代碼數(shù)據(jù)發(fā)送到網(wǎng)絡(luò)中所有節(jié)點，MTCD協(xié)議只需要將代碼數(shù)據(jù)沿分發(fā)樹的路徑進行轉(zhuǎn)發(fā)。因此,MTCD協(xié)議的數(shù)據(jù)消息能耗隨分發(fā)樹的路徑長度增大而增大，數(shù)據(jù)消息傳輸?shù)陀贒eluge。

圖8 數(shù)據(jù)消息耗費能量

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

圖9 控制消息耗費能量

5 結(jié) 論

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

參考文獻:

[1] 況曉輝,許 飛,劉 麗.無線傳感器網(wǎng)絡(luò)遠程代碼更新技術(shù)研究進展[J].計算機科學(xué),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.