譚 勁，張曼曼

(中國(guó)計(jì)量學(xué)院信息工程學(xué)院，杭州310018)

無(wú)線傳感器網(wǎng)絡(luò)(WSN)是由大量通信能力、處理能力和能量供應(yīng)都十分受限的微型傳感器節(jié)點(diǎn)，以自組織和多跳的方式構(gòu)成的無(wú)線通信網(wǎng)絡(luò)，通過(guò)協(xié)作感知、采集和處理監(jiān)測(cè)區(qū)域的數(shù)據(jù)，以實(shí)現(xiàn)環(huán)境監(jiān)測(cè)的目的。一旦部署成功，WSN通常要長(zhǎng)期工作在無(wú)人協(xié)助的環(huán)境中，在此期間為了適應(yīng)環(huán)境和網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化，需要相應(yīng)的改變用戶的部分需求，并隨之調(diào)整軟件的功能，這都需要對(duì)傳感節(jié)點(diǎn)上的應(yīng)用程序進(jìn)行再編程。同時(shí)，由于網(wǎng)絡(luò)部署的隨機(jī)性、規(guī)模性和工作環(huán)境的特定性，使得傳統(tǒng)的手工再編程已經(jīng)不切實(shí)際，甚至是不可行的。這就需要網(wǎng)絡(luò)再編程，即通過(guò)無(wú)線通信的方式遠(yuǎn)程對(duì)節(jié)點(diǎn)進(jìn)行軟件更新。

網(wǎng)絡(luò)再編程主要包含兩部分內(nèi)容:第一部分是傳感節(jié)點(diǎn)上已裝入更新代碼的安裝機(jī)制，屬于操作系統(tǒng)與硬件結(jié)構(gòu)研究的范疇;第二部分是分布更新軟件到傳感節(jié)點(diǎn)的傳播機(jī)制，屬于網(wǎng)絡(luò)協(xié)議的范疇，是目前研究的重點(diǎn)和熱點(diǎn)[1]。已有的網(wǎng)絡(luò)再編程協(xié)議，根據(jù)傳感節(jié)點(diǎn)資源受限的特點(diǎn)，通過(guò)無(wú)線信道，采用單跳或多跳的空中加載技術(shù)，將軟件影像傳輸?shù)秸麄€(gè)網(wǎng)絡(luò)。然而，這些協(xié)議大多假定網(wǎng)絡(luò)是同構(gòu)的，即將同一軟件影像傳輸?shù)骄W(wǎng)絡(luò)中的所有節(jié)點(diǎn)，不具有范圍選擇功能。實(shí)際上，為了增強(qiáng)網(wǎng)絡(luò)的可靠性和延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期，傳感節(jié)點(diǎn)在傳感對(duì)象、通信能力、硬件資源(CPU處理能力、帶寬、能量)等方面都是異構(gòu)的[2－3]。不同的節(jié)點(diǎn)或者節(jié)點(diǎn)集會(huì)運(yùn)行不同功能的應(yīng)用程序，以完成不同的傳感任務(wù)。由于傳感節(jié)點(diǎn)的異構(gòu)性、傳感任務(wù)的多樣性和軟件對(duì)地點(diǎn)的可能的依賴性，使得將軟件影像傳輸?shù)秸麄€(gè)網(wǎng)絡(luò)是不合適的[4]，這就需要在軟件傳輸過(guò)程中對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)的選擇，即對(duì)運(yùn)行某種特定應(yīng)用程序的所有節(jié)點(diǎn)進(jìn)行再編程。

本文提出了一種能量有效的基于虛擬骨干網(wǎng)的WSN范圍選擇再編程協(xié)議。該協(xié)議首先根據(jù)要更新的應(yīng)用程序、節(jié)點(diǎn)的剩余能量、有效度數(shù)和節(jié)點(diǎn)間的鏈路質(zhì)量，選出合適的核心節(jié)點(diǎn)，創(chuàng)建虛擬骨干網(wǎng)，然后分兩個(gè)階段實(shí)現(xiàn)數(shù)據(jù)傳輸。在第一階段軟件影像由Sink節(jié)點(diǎn)通過(guò)流水線的方式，先可靠傳輸給核心節(jié)點(diǎn);在第二階段由核心節(jié)點(diǎn)并行傳輸?shù)叫枰钠胀ü?jié)點(diǎn)。有效地減少了參與再編程的節(jié)點(diǎn)數(shù)，節(jié)省了能量，實(shí)現(xiàn)了范圍選擇。另外，采用協(xié)調(diào)調(diào)度并引進(jìn)睡眠機(jī)制，使得不參與數(shù)據(jù)傳輸?shù)墓?jié)點(diǎn)關(guān)閉無(wú)線通信裝置，進(jìn)一步減少能量消耗。性能分析和仿真實(shí)驗(yàn)表明:與已有的協(xié)議ThreeStages和Aqueduct相比，本協(xié)議節(jié)省了大約5．6% ～24．8%的平均延時(shí)和5．1% ～27．7%的能量消耗。

1 相關(guān)工作

文獻(xiàn)[5－6]對(duì)現(xiàn)有的網(wǎng)絡(luò)再編程協(xié)議給出了很好的總結(jié)。這些協(xié)議大多假定網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都需要同一版本的軟件影像。Trickle[7]通過(guò)周期性的廣播軟件影像的元數(shù)據(jù)(Meta-Data)來(lái)檢測(cè)鄰域內(nèi)的節(jié)點(diǎn)是否需要進(jìn)行軟件更新。動(dòng)態(tài)的調(diào)整廣播率對(duì)控制消息起到了抑制作用，減少了由廣播風(fēng)暴引起的數(shù)據(jù)冗余。Deluge[8]對(duì)Trickle進(jìn)行了擴(kuò)展，將較大的軟件影像分割成固定大小的數(shù)據(jù)頁(yè)，引進(jìn)流水線操作，實(shí)現(xiàn)了空間的多路復(fù)用。循環(huán)冗余碼校驗(yàn)CRC的引入，保證了軟件更新的可靠性。MNP[9－10]引進(jìn)發(fā)送者選擇機(jī)制，選擇鄰域內(nèi)接收到請(qǐng)求最多的節(jié)點(diǎn)為本次的發(fā)送者。支持流水線操作，實(shí)現(xiàn)了數(shù)據(jù)的快速傳播。同時(shí)，MNP引進(jìn)了睡眠機(jī)制，通過(guò)減少節(jié)點(diǎn)無(wú)線通信活躍的時(shí)間來(lái)節(jié)省能量的消耗。Sprinkler[11]和 CORD[12]采用層次結(jié)構(gòu)的方式分發(fā)軟件影像，即將網(wǎng)絡(luò)再編程分成兩個(gè)不同的階段。第一階段:由Sink節(jié)點(diǎn)將軟件影像可靠的傳播到網(wǎng)絡(luò)中的核心節(jié)點(diǎn)(Core Node);第二階段:核心節(jié)點(diǎn)并行的將軟件影像傳播給自己鄰域內(nèi)的非核心(Non-Core Node)節(jié)點(diǎn)。這種類型的協(xié)議可以有效的減少能量的消耗，而關(guān)鍵是在網(wǎng)絡(luò)中創(chuàng)建有效的虛擬骨干網(wǎng)，也就是連通支配集(CDS)。

近期的文獻(xiàn)開(kāi)始著重研究異構(gòu)WSN的具有范圍選擇的再編程協(xié)議。Melete[13]根據(jù)傳感節(jié)點(diǎn)任務(wù)的不同，分成不同的分組。分組內(nèi)部使用Trickle算法傳輸數(shù)據(jù)，分組間通過(guò)構(gòu)造“轉(zhuǎn)發(fā)區(qū)域”進(jìn)行數(shù)據(jù)傳輸，并采用TTL(Time To Live)的方式限制傳輸?shù)姆秶?。Aqueduct[14]對(duì) Deluge 進(jìn)行了擴(kuò)展，使其具有范圍選擇功能。通過(guò)創(chuàng)建成員節(jié)點(diǎn)間的最短路徑，建立起成員節(jié)點(diǎn)間的中間橋梁，從而進(jìn)行軟件的分發(fā)。文獻(xiàn)[15]引進(jìn)了一個(gè)準(zhǔn)備階段，在這個(gè)階段中每個(gè)節(jié)點(diǎn)獲得自己的角色分配。角色分為3種，分別是需要更新的節(jié)點(diǎn)，轉(zhuǎn)發(fā)節(jié)點(diǎn)和完全不參與的節(jié)點(diǎn)。再編程的范圍選擇，通過(guò)每個(gè)需要更新的節(jié)點(diǎn)，以樹(shù)形方式向Sink節(jié)點(diǎn)發(fā)送消息實(shí)現(xiàn)。作者的前期工作，ThreeStages協(xié)議[16]變傳統(tǒng)的 ADV-REQDATA三次握手協(xié)議為路由形成、代碼傳送、請(qǐng)求丟失包三個(gè)階段協(xié)議;中間轉(zhuǎn)發(fā)節(jié)點(diǎn)通過(guò)獲取一跳范圍內(nèi)希望接收更新代碼數(shù)據(jù)的節(jié)點(diǎn)序列，采取單播或組播方式有針對(duì)性傳送更新代碼，而不是泛洪式的廣播，減少了REQ確認(rèn)信息包。但該協(xié)議并未考慮節(jié)點(diǎn)的剩余能量問(wèn)題，路由上的節(jié)點(diǎn)可能由于能量不足，而無(wú)法實(shí)現(xiàn)軟件影像的可靠傳輸。另外，可以通過(guò)引進(jìn)適當(dāng)?shù)乃邫C(jī)制，進(jìn)一步節(jié)省能耗。Pasztor[17]等人將無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用到野生動(dòng)物的監(jiān)測(cè)上，根據(jù)動(dòng)物或人類都是社會(huì)群體，具有明顯的社會(huì)模式和群體交互，提出了針對(duì)動(dòng)態(tài)網(wǎng)絡(luò)的具有范圍選擇的再編程協(xié)議。

然而，目前在具有范圍選擇的網(wǎng)絡(luò)再編程協(xié)議的研究方面，還存在一些問(wèn)題:協(xié)議一般是基于3次握手機(jī)制的，眾多的REQ會(huì)帶來(lái)確認(rèn)爆炸問(wèn)題;不能做出正確、有效的范圍選擇;很少考慮節(jié)點(diǎn)的剩余能量問(wèn)題，導(dǎo)致可能由于節(jié)點(diǎn)的能量不足，而不能實(shí)現(xiàn)軟件影像的可靠傳輸。

2 系統(tǒng)模型

本文的系統(tǒng)模型如下:

(1)整個(gè)網(wǎng)絡(luò)有一個(gè)基站Sink，節(jié)點(diǎn)隨機(jī)分布在一個(gè)二維區(qū)域中，每個(gè)節(jié)點(diǎn)擁有唯一的ID，并都能以單跳或多跳的方式，將自己感知的數(shù)據(jù)傳輸?shù)絊ink。如圖1所示，圖中有矩形、圓形、菱形三類節(jié)點(diǎn)，對(duì)菱形節(jié)點(diǎn)進(jìn)行軟件更新，即菱形節(jié)點(diǎn)為本次的成員節(jié)點(diǎn)。

(2)用一個(gè)連通圖G=(V，E)，來(lái)表示W(wǎng)SN。其中，V是節(jié)點(diǎn)的集合即WSN中的所有傳感節(jié)點(diǎn)的集合，E是節(jié)點(diǎn)間邊的集合。用R(si)表示節(jié)點(diǎn)si的通信半徑，d(si，sj)表示節(jié)點(diǎn)si和sj之間的歐式距離，每條邊 e=(si，sj)∈E(其中，si，sj∈V)都有 d(si，sj)＜R(si)[18]。

(3)研究的WSN是靜態(tài)的，且無(wú)線通信是雙向的，并且是在網(wǎng)絡(luò)運(yùn)行一定時(shí)間的基礎(chǔ)上對(duì)網(wǎng)絡(luò)進(jìn)行再編程。根據(jù)之前數(shù)據(jù)交換時(shí)數(shù)據(jù)包的丟失率，統(tǒng)計(jì)得到節(jié)點(diǎn)間的鏈路質(zhì)量 Quv，且 Quv=min(Qu－＞v，Qv－＞u)[12]。每個(gè)節(jié)點(diǎn)中都保存有自己的鄰居列表，鄰居列表包括該節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)和鄰居節(jié)點(diǎn)與該節(jié)點(diǎn)間的鏈路質(zhì)量。

(4)再編程開(kāi)始時(shí)，Sink節(jié)點(diǎn)會(huì)將軟件影像分割成數(shù)據(jù)頁(yè)，每頁(yè)包含K個(gè)數(shù)據(jù)包(最后一頁(yè)包含的數(shù)據(jù)包的數(shù)量可以小于K)。同時(shí)，記錄下起始時(shí)間，并將時(shí)間分成長(zhǎng)度為L(zhǎng)的時(shí)間片。時(shí)間片相對(duì)較長(zhǎng)，長(zhǎng)到可以完整可靠的傳輸完一個(gè)數(shù)據(jù)頁(yè)的K個(gè)數(shù)據(jù)包。

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

本文使用到的新的定義:

定義1 核心節(jié)點(diǎn):是將WSN看作是一個(gè)連通圖而構(gòu)造的虛擬骨干網(wǎng)上的節(jié)點(diǎn)，Sink節(jié)點(diǎn)默認(rèn)為虛擬骨干網(wǎng)上的核心節(jié)點(diǎn)。

定義2 非核心節(jié)點(diǎn):在創(chuàng)建虛擬骨干網(wǎng)時(shí)，上層核心節(jié)點(diǎn)在自己的鄰居節(jié)點(diǎn)中選擇符合條件的節(jié)點(diǎn)為下層核心節(jié)點(diǎn)，并發(fā)送通知消息給所有鄰居節(jié)點(diǎn)，收到通知消息而未被選為核心節(jié)點(diǎn)的鄰居節(jié)點(diǎn)為下層非核心節(jié)點(diǎn)。

定義3 剩余節(jié)點(diǎn):虛擬骨干網(wǎng)創(chuàng)建完成之后，網(wǎng)絡(luò)中除核心節(jié)點(diǎn)與非核心節(jié)點(diǎn)之外，可能還有剩余的節(jié)點(diǎn)，這些節(jié)點(diǎn)為剩余節(jié)點(diǎn)。

定義4 普通節(jié)點(diǎn):網(wǎng)絡(luò)中除虛擬骨干網(wǎng)上的核心節(jié)點(diǎn)之外的節(jié)點(diǎn)，包括非核心節(jié)點(diǎn)和剩余節(jié)點(diǎn)。

定義5 父節(jié)點(diǎn):一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，是能夠與該節(jié)點(diǎn)直接通信的上游核心節(jié)點(diǎn)。如圖1中Sink節(jié)點(diǎn)是節(jié)點(diǎn)2、節(jié)點(diǎn)4和節(jié)點(diǎn)12的父節(jié)點(diǎn)。

定義6 有效度數(shù)d(si):一個(gè)節(jié)點(diǎn)的有效度數(shù)，是從自己的所有鄰居節(jié)點(diǎn)中減去自己的鄰居節(jié)點(diǎn)與父節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的交集后，該節(jié)點(diǎn)所剩的鄰居節(jié)點(diǎn)數(shù)，如圖1中節(jié)點(diǎn)4的有效度數(shù)是2。

定義7 權(quán)重w(si):一個(gè)節(jié)點(diǎn)的權(quán)重，是將該節(jié)點(diǎn)的剩余能量和有效度數(shù)綜合考慮的結(jié)果。w(si)=Er(si)＞Es＆＆d(si)＞Ds，其中 Es表示核心節(jié)點(diǎn)剩余能量的閾值，Er(si)為節(jié)點(diǎn)si的剩余能量，Ds為核心節(jié)點(diǎn)有效度數(shù)的閾值，＆＆表示邏輯且。如果節(jié)點(diǎn)的剩余能量和有效度數(shù)都分別超過(guò)對(duì)應(yīng)的閾值，則w(si)為1，否則為0。

3 協(xié)議描述

本文協(xié)議設(shè)計(jì)分為兩個(gè)部分:

(1)根據(jù)要更新的應(yīng)用程序、節(jié)點(diǎn)的剩余能量、有效度數(shù)和節(jié)點(diǎn)間的鏈路質(zhì)量，選出合適的核心節(jié)點(diǎn)，創(chuàng)建虛擬骨干網(wǎng)。

(2)傳輸軟件更新:分兩個(gè)階段實(shí)現(xiàn)軟件更新的傳輸，在第一階段軟件影像由Sink節(jié)點(diǎn)通過(guò)流水線的方式，先傳輸給核心節(jié)點(diǎn);在第二階段由核心節(jié)點(diǎn)并行傳輸?shù)叫枰浖碌钠胀ü?jié)點(diǎn)。

3．1 協(xié)議消息

本協(xié)議中使用了以下7種消息，消息格式見(jiàn)圖2。

圖2 協(xié)議中使用的消息

CLAIM:核心節(jié)點(diǎn)的聲明消息，消息中的“應(yīng)用程序的版本號(hào)Vi”包含兩層意思，需要更新的是什么類型的軟件和該軟件更新到什么程度。“時(shí)間偏移O”是第一個(gè)時(shí)間片開(kāi)始的時(shí)間到現(xiàn)在的時(shí)間偏移?！肮?jié)點(diǎn)在網(wǎng)絡(luò)中的層數(shù)”是節(jié)點(diǎn)距離Sink節(jié)點(diǎn)的具體跳數(shù)。

COMPETE:同屬于一個(gè)父節(jié)點(diǎn)，并與父節(jié)點(diǎn)具有良好鏈路質(zhì)量，且權(quán)重為1的節(jié)點(diǎn)競(jìng)爭(zhēng)成為核心節(jié)點(diǎn)時(shí)發(fā)送的消息。成員節(jié)點(diǎn)具有競(jìng)爭(zhēng)優(yōu)先權(quán)。

ANNOUNCE:通知消息，父節(jié)點(diǎn)從參與競(jìng)爭(zhēng)的節(jié)點(diǎn)中選擇出核心節(jié)點(diǎn)，通過(guò)ANNOUNCE消息通知自己的鄰居節(jié)點(diǎn)。

ADV:傳輸數(shù)據(jù)的廣告消息，整個(gè)軟件影像分割成了固定大小的數(shù)據(jù)頁(yè)，并對(duì)數(shù)據(jù)頁(yè)進(jìn)行編號(hào)，按照編號(hào)由小到大的順序，以數(shù)據(jù)頁(yè)為單位進(jìn)行傳輸。每個(gè)數(shù)據(jù)頁(yè)內(nèi)部同樣對(duì)包含的數(shù)據(jù)包進(jìn)行了編號(hào)。

REQ:數(shù)據(jù)請(qǐng)求消息，如果由于某種原因(如:數(shù)據(jù)包在傳輸過(guò)程中丟失)，需要重傳某些數(shù)據(jù)包，或者普通節(jié)點(diǎn)需要核心節(jié)點(diǎn)ADV廣告的數(shù)據(jù)，則請(qǐng)求節(jié)點(diǎn)需要發(fā)送REQ消息。

DATA:數(shù)據(jù)發(fā)送消息，分為兩種情況，如果是REQ請(qǐng)求的數(shù)據(jù)，則根據(jù)收到的REQ中的相關(guān)字段，發(fā)送對(duì)應(yīng)的某個(gè)數(shù)據(jù)頁(yè)的某些數(shù)據(jù)包;否則，則根據(jù)之前發(fā)送的ADV的相關(guān)字段，發(fā)送對(duì)應(yīng)的某個(gè)數(shù)據(jù)頁(yè)的所有數(shù)據(jù)包。

TEST:測(cè)試消息，在虛擬骨干網(wǎng)創(chuàng)建完成之后，網(wǎng)絡(luò)中可能存在一些剩余節(jié)點(diǎn)。這些節(jié)點(diǎn)可能不知道自己是否需要更新，則在數(shù)據(jù)傳輸階段，發(fā)送TEST消息給與自己鏈接質(zhì)量最好的鄰居節(jié)點(diǎn)，查看是否需要軟件更新，并做出相應(yīng)處理。

3．2 虛擬骨干網(wǎng)的創(chuàng)建

協(xié)議的關(guān)鍵是虛擬骨干網(wǎng)的創(chuàng)建，在創(chuàng)建虛擬骨干網(wǎng)選擇核心節(jié)點(diǎn)時(shí)，協(xié)議充分考慮了節(jié)點(diǎn)的剩余能量問(wèn)題，以保證核心節(jié)點(diǎn)有充足的能量，來(lái)實(shí)現(xiàn)軟件影像的可靠傳輸。由于一般的傳感節(jié)點(diǎn)不具備直接測(cè)量其剩余能量的功能，本協(xié)議采用一種間接的方法計(jì)算節(jié)點(diǎn)的剩余能量。傳感節(jié)點(diǎn)的耗能模塊分別是傳感模塊、通信模塊和處理模塊，則節(jié)點(diǎn)的剩余能量為初始能量減去這3個(gè)耗能模塊消耗的能量的總和(假定在網(wǎng)絡(luò)開(kāi)始運(yùn)行時(shí)，傳感節(jié)點(diǎn)都具有相同的初始能量)。用E0表示初始能量，Er表示剩余能量，Esen表示傳感模塊消耗的能量，Ecom表示通信模塊消耗的能量，Ecpu表示處理模塊消耗的能量，可得:

然而傳感節(jié)點(diǎn)的通信模塊的功耗，遠(yuǎn)比傳感模塊和通信模塊大得多，且通信模塊在節(jié)點(diǎn)的生命周期內(nèi)一般都是開(kāi)啟的，進(jìn)而得到傳感節(jié)點(diǎn)的通信模塊，遠(yuǎn)比傳感模塊和處理模塊消耗的能量多。因此，傳感節(jié)點(diǎn)的剩余能量約等于初始能量減去通信模塊消耗的能量，可得:

再編程開(kāi)始時(shí)，Sink節(jié)點(diǎn)會(huì)根據(jù)要傳輸?shù)能浖跋竦拇笮?，?jì)算出虛擬骨干網(wǎng)上的核心節(jié)點(diǎn)完成整個(gè)再編程任務(wù)時(shí)，需要消耗的能量，繼而給出核心節(jié)點(diǎn)剩余能量的閾值Es。傳感節(jié)點(diǎn)根據(jù)式(2)計(jì)算出自己的剩余能量Er，只有Er大于Es時(shí)才可以成為核心節(jié)點(diǎn)。

節(jié)點(diǎn)的有效度數(shù)與節(jié)點(diǎn)間的鏈路質(zhì)量，與WSN的部署環(huán)境和網(wǎng)絡(luò)的分布密度有關(guān)，根據(jù)實(shí)際經(jīng)驗(yàn)選取對(duì)應(yīng)的有效度數(shù)的閾值Ds和鏈路質(zhì)量的閾值Qs。

本文對(duì)文獻(xiàn)[18－19]提出的虛擬骨干網(wǎng)的算法進(jìn)行了改進(jìn)，使得需要更新的成員節(jié)點(diǎn)具有成為核心節(jié)點(diǎn)的優(yōu)先權(quán)，對(duì)異構(gòu)的WSN的再編程做出了范圍選擇的處理。以下是虛擬骨干網(wǎng)創(chuàng)建的過(guò)程:

(1)核心節(jié)點(diǎn)(最初是Sink節(jié)點(diǎn))根據(jù)鄰居列表，將CLAIM消息組播給所有鄰居節(jié)點(diǎn)。

(2)節(jié)點(diǎn)收到CLAIM消息后，如果已知自己在網(wǎng)絡(luò)中的分層，且分層小于或等于CLAIM消息中“節(jié)點(diǎn)在網(wǎng)絡(luò)中的層數(shù)”則丟棄不做處理。否則，復(fù)制CLAIM內(nèi)容，選擇發(fā)送CLAIM消息的源節(jié)點(diǎn)為父節(jié)點(diǎn)，與其保持同步，存儲(chǔ)父節(jié)點(diǎn)的ID，計(jì)算自己在網(wǎng)絡(luò)中的分層為父節(jié)點(diǎn)的網(wǎng)絡(luò)層數(shù)加1(Sink節(jié)點(diǎn)在網(wǎng)絡(luò)中的分層為0)。如果收到上層多個(gè)核心節(jié)點(diǎn)發(fā)送來(lái)的CLAIM消息，則選擇ID最小的源節(jié)點(diǎn)為父節(jié)點(diǎn)，將其他CLAIM消息丟棄不做處理。

圖3 虛擬骨干網(wǎng)創(chuàng)建的主要流程圖

(3)與父節(jié)點(diǎn)具有良好鏈路質(zhì)量(與父節(jié)點(diǎn)之間的鏈路質(zhì)量達(dá)到閾值Qs)，且權(quán)重為1的節(jié)點(diǎn)，在收到CLAIM消息后，單播COMPETE消息給父節(jié)點(diǎn)，父節(jié)點(diǎn)從中選擇核心節(jié)點(diǎn)。在這些節(jié)點(diǎn)中:(a)如果有成員節(jié)點(diǎn)，則選擇所有的成員節(jié)點(diǎn)為核心節(jié)點(diǎn)，且不再選擇同層的非成員節(jié)點(diǎn)為核心節(jié)點(diǎn);(b)如果沒(méi)有成員節(jié)點(diǎn)，則選擇有效度數(shù)最大的節(jié)點(diǎn)為核心節(jié)點(diǎn)(如果有效度數(shù)相同，則選擇ID最小的節(jié)點(diǎn))。父節(jié)點(diǎn)做出決定后，組播ANNOUNCE消息給所有鄰居節(jié)點(diǎn)。

(4)回到步驟(1)，并循環(huán)執(zhí)行步驟(1)～步驟(3)，直到找到網(wǎng)絡(luò)中最后一個(gè)核心節(jié)點(diǎn)為止。

這時(shí)網(wǎng)絡(luò)中可能存在一些剩余節(jié)點(diǎn)，這些節(jié)點(diǎn)可能不知道自己是否需要軟件更新，在數(shù)據(jù)傳輸階段將會(huì)對(duì)其進(jìn)行處理。

3．3 數(shù)據(jù)傳輸

虛擬骨干網(wǎng)創(chuàng)建完成之后，進(jìn)入到數(shù)據(jù)傳輸階段，并分為兩個(gè)階段進(jìn)行數(shù)據(jù)的分發(fā)。由于在第一階段將軟件影像由Sink節(jié)點(diǎn)分發(fā)給核心節(jié)點(diǎn)時(shí)，使用了流水線操作，導(dǎo)致同時(shí)發(fā)送數(shù)據(jù)的兩個(gè)節(jié)點(diǎn)間至少有3跳的距離，才能避免數(shù)據(jù)干擾，如圖4所示。因此采用與 CORD[12]類似的時(shí)間調(diào)度方案。調(diào)度由重復(fù)的長(zhǎng)度為L(zhǎng)的時(shí)間片組成，在數(shù)據(jù)傳輸時(shí)每個(gè)核心節(jié)點(diǎn)輪流進(jìn)入發(fā)送、接收和睡眠狀態(tài)。我們將這些在時(shí)間調(diào)度中連續(xù)的時(shí)間片，分別用SSlot、R-Slot和Q-Slot來(lái)表示。核心節(jié)點(diǎn)的時(shí)間調(diào)度即是重復(fù)S-R-Q。圖5闡明了處于3個(gè)網(wǎng)絡(luò)分層的鄰接的核心節(jié)點(diǎn)u、v、w的時(shí)間調(diào)度情況。

圖4 流水線傳輸

圖5 3個(gè)鄰接核心節(jié)點(diǎn)的協(xié)調(diào)調(diào)度

數(shù)據(jù)傳輸?shù)膬蓚€(gè)階段:

(1)由Sink節(jié)點(diǎn)開(kāi)始，將軟件影像以數(shù)據(jù)頁(yè)為單位傳輸給虛擬骨干網(wǎng)中的核心節(jié)點(diǎn)。傳輸采用流水線操作，伴隨著時(shí)間調(diào)度，以單播或者組播的方式進(jìn)行。主要算法見(jiàn)圖6。

圖6 數(shù)據(jù)傳輸?shù)谝浑A段

(2)核心節(jié)點(diǎn)并行的將軟件影像傳輸給需要更新的普通節(jié)點(diǎn)。傳輸以單播或者組播的方式進(jìn)行。主要算法見(jiàn)圖7。

圖7 數(shù)據(jù)傳輸?shù)诙A段

在虛擬骨干網(wǎng)創(chuàng)建完成之后，網(wǎng)絡(luò)中可能存在一些剩余節(jié)點(diǎn)。這些節(jié)點(diǎn)可能不知道自己是否需要更新，則在數(shù)據(jù)傳輸?shù)牡谝浑A段，以單播的方式發(fā)送TEST消息給與自己鏈路質(zhì)量最好的鄰居，這個(gè)鄰居節(jié)點(diǎn)收到消息后根據(jù)保存的CLAIM消息，判斷TEST的發(fā)送節(jié)點(diǎn)是否需要軟件更新。(這個(gè)鄰居可能是核心節(jié)點(diǎn)，也可能是緊鄰核心節(jié)點(diǎn)的非核心節(jié)點(diǎn))如果不需要更新，則不做處理;如果需要更新則在數(shù)據(jù)傳輸?shù)牡诙A段做以下操作:(a)如果這個(gè)鄰居是核心節(jié)點(diǎn)，則該核心節(jié)點(diǎn)在組播了ADV消息，并收到非核心的成員節(jié)點(diǎn)發(fā)送的REQ消息后，將軟件影像一起組播給需要的成員節(jié)點(diǎn)和這個(gè)發(fā)送TEST消息的節(jié)點(diǎn);(b)如果這個(gè)鄰居是非核心節(jié)點(diǎn)，則在這個(gè)鄰居的父節(jié)點(diǎn)組播了ADV消息后，這個(gè)鄰居節(jié)點(diǎn)向其父節(jié)點(diǎn)單播REQ請(qǐng)求軟件更新。獲得完整軟件后，再轉(zhuǎn)發(fā)給需要的鄰居節(jié)點(diǎn)。

4 性能分析

4．1 仿真環(huán)境與模擬設(shè)定

在不同軟件更新大小傳輸下，我們利用OMNet++4．0網(wǎng)絡(luò)仿真環(huán)境，比較Aqueduct和作者前期提出的ThreeStages協(xié)議，與本協(xié)議在平均時(shí)間延遲和能量消耗方面的性能。仿真的網(wǎng)絡(luò)模型和參數(shù)與ThreeStages協(xié)議相同。實(shí)驗(yàn)假定傳感節(jié)點(diǎn)隨機(jī)分布于7*7的網(wǎng)格內(nèi)，節(jié)點(diǎn)的總數(shù)是49，再編程的成員節(jié)點(diǎn)(菱形節(jié)點(diǎn))為20個(gè)，非成員節(jié)點(diǎn)(圓形節(jié)點(diǎn))為29個(gè)。如圖8所示。

模擬參數(shù)見(jiàn)表1，模擬結(jié)果見(jiàn)圖9～圖11。

表1 模擬參數(shù)

圖9 不同軟件更新大小下的平均延時(shí)

圖10 不同軟件更新大小下的消息總數(shù)

圖11 不同軟件更新大小下是否采用休眠機(jī)制的能量消耗

圖8中菱形表示再編程節(jié)點(diǎn)即本次的成員節(jié)點(diǎn)，圓形為非成員節(jié)點(diǎn)。如圖8(1)所示，本實(shí)驗(yàn)根據(jù)上文提出的虛擬骨干網(wǎng)創(chuàng)建算法，選出了20個(gè)核心節(jié)點(diǎn)，構(gòu)成整個(gè)虛擬骨干網(wǎng)(如圖中實(shí)線連接的部分)，將網(wǎng)絡(luò)分成了9層(核心節(jié)點(diǎn)中的數(shù)字表示該核心節(jié)點(diǎn)在網(wǎng)絡(luò)中的層數(shù))。網(wǎng)絡(luò)中剩余的29個(gè)節(jié)點(diǎn)中，包含24個(gè)非核心節(jié)點(diǎn)，與5個(gè)剩余節(jié)點(diǎn)。

圖8(1)是在假定節(jié)點(diǎn)都有充足的剩余能量，來(lái)實(shí)現(xiàn)軟件影像可靠傳輸?shù)睦硐肭闆r下形成的。實(shí)際上，由于再編程是網(wǎng)絡(luò)運(yùn)行一段時(shí)間之后開(kāi)始的，耗能模塊主要是通信模塊對(duì)傳感節(jié)點(diǎn)有限的能量進(jìn)行了消耗。再編程進(jìn)行時(shí)，傳感節(jié)點(diǎn)的剩余能量可能不足以完成對(duì)應(yīng)的再編程任務(wù)。尤其是虛擬骨干網(wǎng)上的核心節(jié)點(diǎn)，由于需要參與數(shù)據(jù)傳輸?shù)膬蓚€(gè)階段，對(duì)剩余能量要求較高。因此，在創(chuàng)建虛擬骨干網(wǎng)選擇核心節(jié)點(diǎn)時(shí)，要充分考慮節(jié)點(diǎn)的剩余能量。圖8的(2)是在(1)的實(shí)驗(yàn)基礎(chǔ)上設(shè)定節(jié)點(diǎn)15的剩余能量不足，因而不能參與競(jìng)爭(zhēng)成為核心節(jié)點(diǎn)，則其父節(jié)點(diǎn)8選擇節(jié)點(diǎn)16為下一層的核心節(jié)點(diǎn)，繼而逐層選擇核心節(jié)點(diǎn)形成新的虛擬骨干網(wǎng)。

4．2 時(shí)間延遲

本協(xié)議總的時(shí)間延遲，包括虛擬骨干網(wǎng)的創(chuàng)建時(shí)間和數(shù)據(jù)傳輸時(shí)間兩部分。而數(shù)據(jù)傳輸部分又包含兩個(gè)階段。用T表示總的傳輸時(shí)間，Tcds表示虛擬骨干網(wǎng)的創(chuàng)建時(shí)間，Ttf表示數(shù)據(jù)傳輸?shù)谝浑A段的時(shí)間，Tts表示數(shù)據(jù)傳輸?shù)诙A段的時(shí)間，可得:

虛擬骨干網(wǎng)創(chuàng)建時(shí)間，是由選取網(wǎng)絡(luò)中每一層的核心節(jié)點(diǎn)的時(shí)間構(gòu)成的。用L表示將網(wǎng)絡(luò)分成的最大層數(shù)，用Ncom表示每一層中向自己的父節(jié)點(diǎn)，發(fā)送COMPETE消息的節(jié)點(diǎn)數(shù)，可得:

數(shù)據(jù)傳輸?shù)牡谝浑A段，是由Sink節(jié)點(diǎn)將軟件影像通過(guò)流水線的方式，先傳輸給核心節(jié)點(diǎn)。結(jié)合流水線傳輸和協(xié)調(diào)調(diào)度，可得:

數(shù)據(jù)傳輸?shù)牡诙A段，是由核心節(jié)點(diǎn)將軟件影像并行傳輸?shù)叫枰钠胀ü?jié)點(diǎn)。由于傳輸時(shí)最多只有兩跳，所以無(wú)法使用流水線操作，可得:

圖9顯示了本協(xié)議與ThreeStages和Aqueduct，在平均延時(shí)方面的對(duì)比?？梢缘玫奖緟f(xié)議在平均延時(shí)方面優(yōu)于ThreeStages和Aqueduct，降低了大約5．6% ～24．8%的平均延時(shí)。原因是Aqueduct的中間節(jié)點(diǎn)在轉(zhuǎn)發(fā)每一個(gè)數(shù)據(jù)頁(yè)后，都要等待一個(gè)時(shí)間片，延長(zhǎng)了再編程的時(shí)間。ThreeStages在數(shù)據(jù)傳輸時(shí)沒(méi)有使用流水線操作。而本協(xié)議在創(chuàng)建完虛擬骨干網(wǎng)之后，在數(shù)據(jù)傳輸?shù)牡谝浑A段，上層核心節(jié)點(diǎn)只需根據(jù)自己存儲(chǔ)的下層核心節(jié)點(diǎn)的ID，以流水線的方式單播或者組播發(fā)送ADV和數(shù)據(jù)。在第二階段，核心節(jié)點(diǎn)并行的將軟件更新傳輸給需要的節(jié)點(diǎn)，而需要軟件更新的節(jié)點(diǎn)距離自己的核心節(jié)點(diǎn)最多只有2跳，可以實(shí)現(xiàn)數(shù)據(jù)的快速傳輸。

4．3 能量消耗

因?yàn)橥ㄐ拍K遠(yuǎn)比處理模塊和傳感模塊消耗的能量多，對(duì)于網(wǎng)絡(luò)的耗能問(wèn)題，我們沒(méi)有直接測(cè)試每個(gè)節(jié)點(diǎn)的能量消耗，而是轉(zhuǎn)化為統(tǒng)計(jì)出所有節(jié)點(diǎn)收發(fā)的消息總數(shù)。本協(xié)議的總消息數(shù)，包含創(chuàng)建虛擬骨干網(wǎng)時(shí)收發(fā)的消息數(shù)和數(shù)據(jù)傳輸時(shí)收發(fā)的消息數(shù)兩部分。其中，創(chuàng)建虛擬骨干網(wǎng)時(shí)的消息為CLAIM、COMPETE和ANNOUNCE消息，都是控制消息，而在數(shù)據(jù)傳輸時(shí)的消息為ADV、REQ、TEST和DATA消息，前3者是控制消息，而DATA消息為數(shù)據(jù)消息。用N表示消息總數(shù)，Ncds表示創(chuàng)建虛擬骨干網(wǎng)的消息數(shù)，Nt表示傳輸數(shù)據(jù)時(shí)的消息數(shù)，可得:

由圖10可以看出與ThreeStages和Aqueduct相比，本協(xié)議在能量消耗方面優(yōu)勢(shì)明顯，降低了大約5．1% ～27．7%的能量消耗。原因是在Aqueduct中所有的節(jié)點(diǎn)都廣播ADV消息，并且每個(gè)節(jié)點(diǎn)都有可能成為數(shù)據(jù)的發(fā)送者。ThreeStages在路由形成時(shí)，采用泛洪的廣播方式轉(zhuǎn)發(fā)了比較多的消息，在代碼傳送階段采用組播或單播的形式傳送。在本協(xié)議中，虛擬骨干網(wǎng)創(chuàng)建時(shí)就采用組播或單播的方式轉(zhuǎn)發(fā)消息，在數(shù)據(jù)傳送階段只有核心節(jié)點(diǎn)才會(huì)發(fā)送ADV和數(shù)據(jù)，并且遵循固定的調(diào)度，有效減少了收發(fā)的消息總數(shù)。

4．4 休眠機(jī)制下節(jié)省的能量

結(jié)合傳感器節(jié)點(diǎn)在發(fā)送消息、接收消息、空閑監(jiān)聽(tīng)和休眠這4種狀態(tài)下的功耗情況，即節(jié)點(diǎn)在發(fā)送消息時(shí)，功耗最多;接收消息和空閑監(jiān)聽(tīng)的功耗相當(dāng)，且比發(fā)送消息功耗略小;休眠狀態(tài)下遠(yuǎn)比前3者的功耗小。根據(jù)數(shù)據(jù)傳輸?shù)谝浑A段的傳輸時(shí)間和協(xié)調(diào)調(diào)度，得到在數(shù)據(jù)傳輸?shù)谝浑A段的能量消耗情況。

圖11對(duì)比了在數(shù)據(jù)傳輸?shù)谝浑A段不引進(jìn)睡眠機(jī)制和引進(jìn)睡眠機(jī)制時(shí)，網(wǎng)絡(luò)消耗的能量，且容易得到后者明顯優(yōu)于前者。原因是引進(jìn)睡眠機(jī)制后，節(jié)點(diǎn)將原來(lái)的空閑監(jiān)聽(tīng)狀態(tài)改為了睡眠狀態(tài)，有效降低了能耗。

5 結(jié)論

針對(duì)異構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)，本文提出了一種能量有效的基于虛擬骨干網(wǎng)的WSN范圍選擇再編程協(xié)議。協(xié)議的關(guān)鍵是建立層次路由，即在軟件更新的數(shù)據(jù)傳輸之前，綜合考慮更新的應(yīng)用程序、剩余能量、有效度數(shù)和節(jié)點(diǎn)間的鏈路質(zhì)量，選出合適的核心節(jié)點(diǎn)，創(chuàng)建虛擬骨干網(wǎng)。減少了參與再編程的節(jié)點(diǎn)數(shù)，降低了能量消耗，實(shí)現(xiàn)了范圍選擇。在虛擬骨干網(wǎng)的創(chuàng)建過(guò)程中，同時(shí)完成節(jié)點(diǎn)與其父節(jié)點(diǎn)之間的同步設(shè)置，以便于數(shù)據(jù)傳輸時(shí)協(xié)調(diào)調(diào)度并引進(jìn)睡眠機(jī)制，從而進(jìn)一步節(jié)省能量的消耗。數(shù)據(jù)傳輸分為兩個(gè)階段，在第一階段軟件影像首先由Sink節(jié)點(diǎn)通過(guò)流水線的方式，可靠的傳輸給核心節(jié)點(diǎn);在第二階段由核心節(jié)點(diǎn)并行傳輸?shù)叫枰钠胀ü?jié)點(diǎn)，有效減少了時(shí)間的延遲。協(xié)議中假定了，再編程時(shí)只負(fù)責(zé)轉(zhuǎn)發(fā)的非成員節(jié)點(diǎn)，不考慮自身的能耗問(wèn)題，“無(wú)私”的完成轉(zhuǎn)發(fā)軟件影像的任務(wù)。再編程結(jié)束后，這些節(jié)點(diǎn)可能由于能量所剩無(wú)幾，而無(wú)法繼續(xù)正常的傳感工作。將來(lái)主要研究，非成員節(jié)點(diǎn)如何根據(jù)要傳輸?shù)能浖跋竦拇笮『凸?jié)點(diǎn)的剩余能量，在保證后續(xù)工作能夠正常進(jìn)行的情況下參與再編程，完成軟件影像的可靠轉(zhuǎn)發(fā)。

[1]譚勁，陳曉竹，劉硯秋．無(wú)線傳感網(wǎng)絡(luò)再編程研究[J]．電子器件，2008，31(3):1049－1053．

[2]Shilpa M，Jyoteesh M．Energy Efficient Control Strategies in Heterogeneous Wireless Sensor Networks:A Survey[J]．International Journal of Computer Application，2011，14(6):31－37．

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

[4]Nils Aschenbruck，Jan Bauer，Jakob Bieling，et al．Selective and Secure Over-the-air Programming for Wireless Sensor Networks[C]//2012 21st International Conference on Computer Communications and Networks，ICCCN 2012．

[5]Wang Qiang，Zhu Yaoyao，Cheng Liang．Reprogramming Wireless Sensor Networks:Challenges and Approaches[C]//IEEE Network，2006，20(3):48－55．

[6]Sun Junzhao．Dissemination Protocols for Reprogramming Wireless Sensor Networks:A Literature Survey[C]//4th International Conference on Sensor Technologies ans Applications，Sensorcomm，2010:151－156．

[7]Levis P，Patel N，Shenker S，et al．Trickle:A Self-regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks[C]//Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation(NSDI)，2004，15－28．

[8]Jonathan W Hui，David Culler．The Dynamic Behavior of a Data Dissemination Protocol for Network Programming at Scale．[C]//Proc．SenSys’04，Baltimore，Maryland，USA，November 2004．

[9]Sanded S．Kulkarni，Limin Wang．MNP:Multihop Network Programming for Sensor Networks[C]//Proc 25th IEEE International Conference on Distributed Computing Systems(ICDCS 2005)，Columbus OH，June 2005，7－16．

[10]Sandeep S．Kulkarni，Limin Wang，Energy-Efficient Multi-hop Reprogramming For Sensor Networks[J]．ACM Transactions on Sensor Networks(TOSN)，2009，5(2): － ．

[11]Nail V，Arora A，Sinha P，et al．Sprinkler:a Reliable and Energy Efficient Data Dissemination Service forWireless Embedded devices[C]//Proc．of the 26th IEEE International Real-Time Systems Symposium(RTSS 2005)，Miami，F(xiàn)L，USA，December 2005．

[12]Leijun Huang，Sanjeev Setia．CORD:Energy-efficient Reliable Bulk Data Dissemination in Sensor Networks[C]//27th IEEE Communications Society Conference on Computer Communications，INFOCOM，2008，1247－1255．

[13]Yu Y，Rittle L J．Supporting Concurrent Application in Wireless Sensor Networks[C]//Conference On Embeded Networked Sensor Systems，．ACM Press，2006，139－152．

[14]Phillips L A．Aqueduct:Robust and Efficient Code Progagation in Heterogeneous Wireless Sensor Networks[D]．Master’s thesis，University of Colorado，2005．

[15]Lee K，Kim J，Thuy D D，et al．Multi-hop Network Re-programming Model for Wireless Sensor Networks[C]//5th IEEE Conference on Sensor，2006，884－887．

[16]譚勁，張曼曼．具有范圍選擇的傳感網(wǎng)絡(luò)再編程協(xié)議算法研究[J]．傳感技術(shù)學(xué)報(bào)，2012，25(2):251－257．

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

[18]趙仕俊，陳琳，李曉東．能量高效的傳感器網(wǎng)絡(luò)虛擬骨干網(wǎng)構(gòu)造算法[J]．計(jì)算機(jī)應(yīng)用，2007，27(8):1839－1845．

[19]Cheng X，Ding M，Du D，et al．Virtual Backbone Construction in Multichip Ad Hoc Wireless Networks[J]．Wireless Communications and Mobile Computing，2006，6:183－190．