王國(guó)玲，楊文忠，張振宇，夏揚(yáng)波，殷亞博，楊慧婷

(1.新疆大學(xué) 軟件學(xué)院，烏魯木齊 830046； 2.新疆大學(xué) 信息科學(xué)與工程學(xué)院，烏魯木齊 830046)

0 引言

移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)是一種以數(shù)據(jù)為中心的延遲容忍無(wú)線網(wǎng)絡(luò)[1]，節(jié)點(diǎn)由電池提供能量，并且當(dāng)節(jié)點(diǎn)的能量耗盡時(shí)給節(jié)點(diǎn)充電或更換電池極其困難，其次節(jié)點(diǎn)的通信距離有限并且由于節(jié)點(diǎn)的移動(dòng)，節(jié)點(diǎn)間的鏈路連接動(dòng)態(tài)變化[2-3]。在移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)中，設(shè)計(jì)有效的數(shù)據(jù)傳輸策略成為一個(gè)研究熱點(diǎn)，并且隨著人們對(duì)移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)的深入研究，使其廣泛應(yīng)用于野生動(dòng)物監(jiān)測(cè)[4]、移動(dòng)智能照明控制[5]等。

為了解決移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳輸問(wèn)題，學(xué)者們從不同的角度提出了相應(yīng)的算法。當(dāng)考慮節(jié)點(diǎn)屬性時(shí)，文獻(xiàn)[6]提出一種具有能量感知且負(fù)載均衡的路由算法，根據(jù)節(jié)點(diǎn)的剩余能量特征選出下一跳節(jié)點(diǎn)并進(jìn)行數(shù)據(jù)消息的傳輸。文獻(xiàn)[7]提出一種路由算法，考慮節(jié)點(diǎn)的位置坐標(biāo)和剩余能量，最終實(shí)現(xiàn)數(shù)據(jù)消息的傳輸。文獻(xiàn)[8]提出一種路由協(xié)議EAEpidemic (Energy Aware Epidemic)，兩個(gè)節(jié)點(diǎn)相遇時(shí)彼此交換一個(gè)消息，包含節(jié)點(diǎn)緩存里的數(shù)據(jù)消息、能量水平和剩余緩存空間大小，選擇剩余能量和剩余緩存大小大于自己的鄰居節(jié)點(diǎn)，并向該鄰居節(jié)點(diǎn)復(fù)制對(duì)方?jīng)]有的數(shù)據(jù)消息。文獻(xiàn)[9]提出一種基于能耗自選演進(jìn)機(jī)制的延遲容忍網(wǎng)絡(luò)路由算法，依據(jù)節(jié)點(diǎn)的剩余能量狀態(tài)，利用策略博弈模型確定節(jié)點(diǎn)是否轉(zhuǎn)發(fā)數(shù)據(jù)消息。文獻(xiàn)[10]提出一種路由算法LDM(a new routing algorithm based Location and Direction of Motion)，基于隨機(jī)運(yùn)動(dòng)模型，考慮節(jié)點(diǎn)的運(yùn)動(dòng)方向與當(dāng)前位置分三種情況計(jì)算節(jié)點(diǎn)的傳輸概率。可以看出上述文獻(xiàn)提出的路由算法僅考慮節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)的剩余緩存和節(jié)點(diǎn)的運(yùn)動(dòng)方向，在現(xiàn)實(shí)生活中很多數(shù)據(jù)消息都有延遲要求，并且很多數(shù)據(jù)消息都是大小不一的，為此僅考慮節(jié)點(diǎn)屬性設(shè)計(jì)路由算法，缺乏一定的實(shí)用性。

當(dāng)考慮數(shù)據(jù)消息屬性時(shí)，文獻(xiàn)[11]提出一個(gè)自適應(yīng)的多步路由協(xié)議，選擇距離sink節(jié)點(diǎn)最近的相遇節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，并且每一步路由都根據(jù)數(shù)據(jù)消息的延遲容忍度計(jì)算數(shù)據(jù)消息的副本數(shù)，以便用最少的副本數(shù)達(dá)到期望的傳輸概率。文獻(xiàn)[12]提出一種路由協(xié)議FLDEAR(Fuzzy-Logic based Distance and Energy Aware Routing protocol)，根據(jù)數(shù)據(jù)消息的大小、節(jié)點(diǎn)與sink節(jié)點(diǎn)的距離以及節(jié)點(diǎn)與sink的歷史訪問(wèn)頻率計(jì)算節(jié)點(diǎn)的傳輸概率，從而選擇傳輸概率最大的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)消息。為了提高數(shù)據(jù)消息的投遞率，文獻(xiàn)[13-14]根據(jù)數(shù)據(jù)消息的延遲容忍度對(duì)節(jié)點(diǎn)隊(duì)列里的數(shù)據(jù)消息排序，使得延遲容忍度低的數(shù)據(jù)消息可以優(yōu)先轉(zhuǎn)發(fā)；可以看出沒(méi)有考慮節(jié)點(diǎn)的剩余能量屬性，這樣會(huì)導(dǎo)致網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗不均勻，部分節(jié)點(diǎn)過(guò)早死亡，從而縮短網(wǎng)絡(luò)的生命周期。

為了彌補(bǔ)上述的不足，本文提出一種基于虛擬貨幣的路由策略，在選擇下一跳的時(shí)候既考慮節(jié)點(diǎn)的屬性又考慮數(shù)據(jù)消息的屬性，使得提出的路由策略更加合乎現(xiàn)實(shí)要求，而且能均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗，延長(zhǎng)網(wǎng)絡(luò)的生命周期。需要發(fā)送數(shù)據(jù)消息的一方為買(mǎi)方，接收方為賣方，當(dāng)買(mǎi)方和賣方相遇時(shí)，根據(jù)節(jié)點(diǎn)的剩余能量和剩余緩存大小以及數(shù)據(jù)消息的延遲容忍度和數(shù)據(jù)消息的大小計(jì)算出價(jià)和要價(jià)，當(dāng)出價(jià)大于或等于要價(jià)時(shí)議價(jià)成功，買(mǎi)方向賣方發(fā)送數(shù)據(jù)消息并更新各自的財(cái)富值。

1 網(wǎng)絡(luò)模型和問(wèn)題描述

1.1 網(wǎng)絡(luò)模型

本文研究的是同構(gòu)傳感器網(wǎng)絡(luò)，整個(gè)網(wǎng)絡(luò)的構(gòu)成包括一個(gè)位置固定在正方形監(jiān)測(cè)區(qū)域中心的sink節(jié)點(diǎn)和分布在該區(qū)域內(nèi)做隨機(jī)運(yùn)動(dòng)的普通傳感器節(jié)點(diǎn)，如圖1所示。普通傳感器節(jié)點(diǎn)擁有相同的存儲(chǔ)空間、相同的通信半徑R、相同的初始能量、相同的初始財(cái)富值M。

圖1 節(jié)點(diǎn)的分布

這里的財(cái)富值是借鑒經(jīng)濟(jì)學(xué)里的概念，財(cái)富值的大小表示節(jié)點(diǎn)的可用資源情況。節(jié)點(diǎn)的可用資源指節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)的剩余緩存空間。

定義1 移動(dòng)模型。采用隨機(jī)移動(dòng)模型Random Waypoint，運(yùn)動(dòng)的節(jié)點(diǎn)通過(guò)GPS或其他定位方法知道此次運(yùn)動(dòng)起點(diǎn)的位置，并且隨機(jī)確定此次運(yùn)動(dòng)的目的地，朝著目的地以某個(gè)位于[vmin,vmax]的速度做勻速直線運(yùn)動(dòng)，到達(dá)目的地后隨機(jī)停留一段時(shí)間，然后以此次的目的地作為下一次的運(yùn)動(dòng)的起點(diǎn)。如圖2所示。

圖2 節(jié)點(diǎn)的運(yùn)動(dòng)模型

定義2 議價(jià)模型。兩個(gè)節(jié)點(diǎn)相遇時(shí)，需要轉(zhuǎn)發(fā)或發(fā)送數(shù)據(jù)消息的一方視為買(mǎi)方，接收數(shù)據(jù)消息的一方視為賣方。買(mǎi)方和賣方都是根據(jù)數(shù)據(jù)的延遲容忍度、數(shù)據(jù)大小、自己的剩余能量和緩存空間利用率進(jìn)行定價(jià)，當(dāng)出價(jià)大于或等于要價(jià)時(shí)交易成功，即可進(jìn)行消息的復(fù)制并轉(zhuǎn)發(fā)；否則交易失敗，節(jié)點(diǎn)繼續(xù)運(yùn)動(dòng)，等待跟其他節(jié)點(diǎn)的相遇。

定義3 數(shù)據(jù)消息的延遲容忍度。每個(gè)傳感器都裝有一個(gè)計(jì)時(shí)器，當(dāng)采集到某個(gè)數(shù)據(jù)并形成數(shù)據(jù)消息時(shí)開(kāi)始倒計(jì)時(shí)，如果在數(shù)據(jù)消息被成功傳輸?shù)絪ink節(jié)點(diǎn)之前延遲容忍度Tj減為0，則該數(shù)據(jù)消息失效。為簡(jiǎn)明起見(jiàn)，數(shù)據(jù)消息從買(mǎi)方被復(fù)制到賣方所花的時(shí)間忽略不計(jì)。

定義4 緩存空間利用率。緩存空間利用率Sj表示節(jié)點(diǎn)j中已占用的空間與初始緩存空間的比值，緩存空間利用率越高，表示剩余緩存空間就越小。sink節(jié)點(diǎn)的緩存空間不受限，普通傳感器節(jié)點(diǎn)的緩存空間都受限，一旦剩余緩存空間為0，則再來(lái)數(shù)據(jù)消息時(shí)將與節(jié)點(diǎn)緩存隊(duì)列里延遲容忍度最大的數(shù)據(jù)消息比較，并決定是否替換。

1.2 問(wèn)題描述

針對(duì)移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)做隨機(jī)運(yùn)動(dòng)的路由問(wèn)題，前人作了相應(yīng)的研究，提出了相關(guān)的路由算法?？梢钥闯龃蠖喽际腔谙嘤龉?jié)點(diǎn)的傳輸概率進(jìn)行數(shù)據(jù)消息的復(fù)制轉(zhuǎn)發(fā)；而且節(jié)點(diǎn)在計(jì)算傳輸概率時(shí)考慮的因素不全，沒(méi)有綜合考慮節(jié)點(diǎn)的屬性和數(shù)據(jù)消息的屬性；此外節(jié)點(diǎn)在進(jìn)行隨機(jī)運(yùn)動(dòng)時(shí)，其運(yùn)動(dòng)速度和運(yùn)動(dòng)方向都是隨機(jī)的，過(guò)分依靠節(jié)點(diǎn)的傳輸概率進(jìn)行數(shù)據(jù)消息的復(fù)制轉(zhuǎn)發(fā)意義不是很大，反而會(huì)浪費(fèi)節(jié)點(diǎn)寶貴的能量資源和計(jì)算資源，甚至?xí)e(cuò)過(guò)最佳的數(shù)據(jù)消息轉(zhuǎn)發(fā)機(jī)會(huì)。因此有效的數(shù)據(jù)消息路由算法應(yīng)該具備以下幾個(gè)特點(diǎn)：1)下一跳節(jié)點(diǎn)的選擇應(yīng)該綜合考慮節(jié)點(diǎn)的剩余能量、緩存空間大小等節(jié)點(diǎn)屬性以及數(shù)據(jù)消息大小、延遲容忍度等數(shù)據(jù)消息的屬性；2)刪除無(wú)效數(shù)據(jù)消息，避免無(wú)效消息帶來(lái)的資源浪費(fèi)，甚至影響有效數(shù)據(jù)消息的轉(zhuǎn)發(fā)和傳輸；3)均衡整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗，避免部分節(jié)點(diǎn)能量消耗過(guò)大，從而延長(zhǎng)網(wǎng)絡(luò)的生命周期。

1.3 能量模型

采用簡(jiǎn)單無(wú)線通信能耗模型[15]。由于通信模塊的能量消耗最大[16]，簡(jiǎn)單起見(jiàn)，只考慮節(jié)點(diǎn)在發(fā)送數(shù)據(jù)消息和接收數(shù)據(jù)時(shí)的能量消耗，忽略其他方面帶來(lái)的能量消耗。節(jié)點(diǎn)在發(fā)送數(shù)據(jù)消息時(shí)的能量消耗與距離d和數(shù)據(jù)長(zhǎng)度L有關(guān)，當(dāng)d小于距離閾值d0時(shí)采用自由空間模型，當(dāng)d大于距離閾值d0時(shí)采用多徑衰減模型。

圖3 能耗模型

如果節(jié)點(diǎn)發(fā)送Lb的數(shù)據(jù)，傳輸距離為d時(shí)，所消耗的能量滿足以下公式：

(1)

其中：Eelec為發(fā)送的能耗，εfs和εmp是功率放大這部分能耗的系數(shù)。

如果節(jié)點(diǎn)接收Lb的數(shù)據(jù)包，那么能量消耗如下：

ERX(l)=lEelec

(2)

本文假設(shè)節(jié)點(diǎn)的通信半徑R小于d0，兩個(gè)節(jié)點(diǎn)相遇時(shí)，節(jié)點(diǎn)發(fā)送長(zhǎng)度為L(zhǎng)b的數(shù)據(jù)消息時(shí)能量消耗為：

ERX(l)=lEelec+lεfsd2

(3)

節(jié)點(diǎn)發(fā)送和接收長(zhǎng)度為L(zhǎng)b的數(shù)據(jù)消息時(shí)總能量消耗為：

E(l)=2lEelec+lεfsd2

(4)

2 數(shù)據(jù)傳輸機(jī)制——DTVC

為了解決節(jié)點(diǎn)基于隨機(jī)運(yùn)動(dòng)模型的路由問(wèn)題，本文提出了一種基于虛擬貨幣的低能耗數(shù)據(jù)傳輸機(jī)制——DTVC(Data Transmission based on Virtual Currency)。數(shù)據(jù)消息字段如圖4所示，Nop表示協(xié)議信息，Seq表示數(shù)據(jù)消息的ID，SID表示源節(jié)點(diǎn)ID，JID表示目的節(jié)點(diǎn)的ID，L表示數(shù)據(jù)消息的長(zhǎng)度，RSD表示數(shù)據(jù)消息的延遲容忍度?；舅枷朊枋鋈缦拢簲y帶數(shù)據(jù)消息的節(jié)點(diǎn)在隨機(jī)運(yùn)動(dòng)的過(guò)程中若與其他節(jié)點(diǎn)相遇，先向?qū)Ψ桨l(fā)送一個(gè)包含需要轉(zhuǎn)發(fā)或傳輸?shù)臄?shù)據(jù)消息的ID、數(shù)據(jù)消息的目的節(jié)點(diǎn)的ID、數(shù)據(jù)消息的大小、發(fā)送節(jié)點(diǎn)的剩余能量以及數(shù)據(jù)消息的延遲容忍度的hello包；收到hello包后先查看數(shù)據(jù)消息的ID和目的節(jié)點(diǎn)的ID，若接收節(jié)點(diǎn)緩存里沒(méi)有該數(shù)據(jù)消息，則回復(fù)一個(gè)包含接收節(jié)點(diǎn)的ID、接收節(jié)點(diǎn)的剩余能量和該數(shù)據(jù)消息的ID的ACK確認(rèn)信息；發(fā)送節(jié)點(diǎn)查看ACK確認(rèn)信息后，若接收節(jié)點(diǎn)是數(shù)據(jù)消息的目的節(jié)點(diǎn)，則直接發(fā)送數(shù)據(jù)消息，否則根據(jù)定價(jià)規(guī)則進(jìn)行出價(jià)，接收節(jié)點(diǎn)根據(jù)定價(jià)規(guī)則進(jìn)行要價(jià)，如果成交則把數(shù)據(jù)消息發(fā)送給接收節(jié)點(diǎn)并更新財(cái)富值，否則繼續(xù)運(yùn)動(dòng)等待與其他節(jié)點(diǎn)相遇。

圖4 數(shù)據(jù)消息的構(gòu)成

Fig. 4 Composition of data messages

2.1 買(mǎi)方和賣方的定價(jià)規(guī)則

兩個(gè)節(jié)點(diǎn)相遇后，根據(jù)規(guī)定的定價(jià)機(jī)制進(jìn)行定價(jià)，如果買(mǎi)方的出價(jià)大于或等于賣方的要價(jià)即c≥b，則交易成功。設(shè)買(mǎi)方的出價(jià)為c，賣方的要價(jià)為b，對(duì)應(yīng)如下：

(5)

其中:α、β和γ為節(jié)點(diǎn)的剩余緩存空間、數(shù)據(jù)的延遲容忍度和節(jié)點(diǎn)剩余能量對(duì)應(yīng)的權(quán)重，且α+β+γ=1，L是數(shù)據(jù)消息的長(zhǎng)度，Tm指當(dāng)前數(shù)據(jù)消息m的延遲容忍度，Tinit指數(shù)據(jù)消息產(chǎn)生時(shí)的延遲容忍度，Sj指節(jié)點(diǎn)j的空間利用率，Ej_res指節(jié)點(diǎn)j的剩余能量，Einit指節(jié)點(diǎn)j的初始能量。

(6)

其中:Tinit、Tm和Einit的含義跟上式相同，Sk指節(jié)點(diǎn)k的空間利用率，Ek_res指節(jié)點(diǎn)k的剩余能量，ω、η和θ是對(duì)應(yīng)的權(quán)重，且ω+η+θ=1。買(mǎi)方和賣方按規(guī)定的定價(jià)機(jī)制進(jìn)行定價(jià)，從而決定此次交易是否成功。

2.2 權(quán)重的設(shè)置

由式(5)可知α、β、γ為節(jié)點(diǎn)緩存空間、數(shù)據(jù)消息延遲容忍度和節(jié)點(diǎn)剩余能量對(duì)應(yīng)的權(quán)值。矩陣A里的aij表示要素i較要素j的重要程度，所以矩陣的對(duì)角線上都取值為1，并且aij=1/aji。對(duì)買(mǎi)方來(lái)說(shuō)，希望把延遲容忍度小的數(shù)據(jù)消息傳輸出去，并且剩余緩存空間越小以及剩余能量越小越急切把消息傳輸出去，所以緩存空間較延遲容忍度重要性小一些，較剩余能量重要性也小一些，延遲容忍度較剩余能量重要性小一些。A里的第一行取值為1，1/3和1/5，第二行取值為3,1，1/7，判斷矩陣A的全部取值如下：

由式(6)可知ω、η、θ為節(jié)點(diǎn)緩存空間、數(shù)據(jù)消息延遲容忍度和節(jié)點(diǎn)剩余能量對(duì)應(yīng)的權(quán)值。矩陣B里的每個(gè)值的含義與A類似，對(duì)賣方來(lái)說(shuō)，當(dāng)節(jié)點(diǎn)的剩余能量很小以及緩存空間小時(shí)就不愿意接收消息，所以緩存空間較延遲容忍度重要性大一些，較剩余能量重要性也小一些，延遲容忍度較剩余能量重要性小一些。B里的第一行取值為1、5和1/7，第二行取值為7、1、1/3，判斷矩陣B的全部取值如下：

2.3 數(shù)據(jù)消息的轉(zhuǎn)發(fā)

采用動(dòng)態(tài)多副本進(jìn)行數(shù)據(jù)消息的轉(zhuǎn)發(fā)，具體的轉(zhuǎn)發(fā)過(guò)程描述如下：

步驟1 準(zhǔn)備階段。節(jié)點(diǎn)j攜帶數(shù)據(jù)消息s和節(jié)點(diǎn)k相遇，首先節(jié)點(diǎn)j向節(jié)點(diǎn)k發(fā)送一個(gè)hello包，之后收到來(lái)自節(jié)點(diǎn)k的確認(rèn)信息ACK，若節(jié)點(diǎn)k的緩存里沒(méi)有數(shù)據(jù)消息s并且是數(shù)據(jù)s的目的節(jié)點(diǎn)，節(jié)點(diǎn)j直接發(fā)送數(shù)據(jù)消息s，轉(zhuǎn)步驟5；否則節(jié)點(diǎn)j根據(jù)式(5)計(jì)算出價(jià)c，轉(zhuǎn)步驟2。

步驟2 服務(wù)請(qǐng)求。節(jié)點(diǎn)j向節(jié)點(diǎn)k發(fā)出包含數(shù)據(jù)消息s的ID、長(zhǎng)度l和出價(jià)c的服務(wù)請(qǐng)求。

步驟3 服務(wù)應(yīng)答。節(jié)點(diǎn)k對(duì)該請(qǐng)求消息進(jìn)行查看，如果緩存里的數(shù)據(jù)消息的ID跟數(shù)據(jù)消息s的ID都不同，則節(jié)點(diǎn)k根據(jù)(6)計(jì)算要價(jià)b，并把b和c進(jìn)行比較，如果c≥b，給出一個(gè)包含數(shù)據(jù)消息ID以及成交價(jià)格0.5(b+c)的確認(rèn)信息，表示愿意接收該數(shù)據(jù)消息，轉(zhuǎn)步驟4；否則此次交易失敗，節(jié)點(diǎn)j攜帶數(shù)據(jù)消息s繼續(xù)運(yùn)動(dòng)。

步驟4 數(shù)據(jù)發(fā)送。節(jié)點(diǎn)j收到確認(rèn)信息后，如果節(jié)點(diǎn)j對(duì)數(shù)據(jù)s是源節(jié)點(diǎn)，需要對(duì)數(shù)據(jù)s進(jìn)行一次復(fù)制；否則不復(fù)制直接發(fā)送數(shù)據(jù)消息s給節(jié)點(diǎn)k。

步驟5 財(cái)富值更新。節(jié)點(diǎn)j的財(cái)富值減0.5(b+c)，節(jié)點(diǎn)k的財(cái)富值增加0.5(b+c)。

假設(shè)當(dāng)前有k′個(gè)節(jié)點(diǎn)進(jìn)入節(jié)點(diǎn)j的通信范圍，即有k′個(gè)節(jié)點(diǎn)與節(jié)點(diǎn)j相遇，令Σ={Ψk|1≤k′}表示k′個(gè)相遇節(jié)點(diǎn)的集合。數(shù)據(jù)消息傳輸算法如下：

輸入：相遇節(jié)點(diǎn);

輸出：滿足條件的相遇節(jié)點(diǎn)并判斷是否需要復(fù)制。

Φ=?

fork=1 tok′

//識(shí)別相遇節(jié)點(diǎn)

do ifkis sink node

forward message(d,k);

//節(jié)點(diǎn)j直接把s發(fā)送給k

else nodejandkcalculate the pricecandb

ifc≥bthen

Φ=Φ∪Ψk;

end if

end if

end for

if the data messagesis sensed by nodej

forn=1 to |Φ|

do copy and forward message(s,Φn);

//節(jié)點(diǎn)j復(fù)制并轉(zhuǎn)發(fā)給滿足條件的節(jié)點(diǎn)Φn

else forn=1 to |Φ|

forward message(s,Φn);

//節(jié)點(diǎn)直接轉(zhuǎn)發(fā)給滿足條件的節(jié)點(diǎn)Φn

end for

end for

end if

2.4 算法的性能分析

時(shí)間復(fù)雜度分析 對(duì)于含n個(gè)節(jié)點(diǎn)的傳感器網(wǎng)絡(luò)，識(shí)別鄰居節(jié)點(diǎn)所花的時(shí)間為O(n)，之后節(jié)點(diǎn)進(jìn)行數(shù)據(jù)消息的復(fù)制和傳輸所花的時(shí)間為O(1)，刪除無(wú)效數(shù)據(jù)消息所花的時(shí)間也為O(1)，所以最終算法的時(shí)間復(fù)雜度為O(n)。

空間復(fù)雜度分析 網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)消息數(shù)為O(1)個(gè)，對(duì)于規(guī)模為n的傳感器網(wǎng)絡(luò)，其空間復(fù)雜度為O(n)。

2.5 無(wú)效數(shù)據(jù)消息的處理

當(dāng)sink節(jié)點(diǎn)收到某個(gè)經(jīng)過(guò)中間節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)消息后，廣播一個(gè)包含該數(shù)據(jù)消息ID的消息，網(wǎng)絡(luò)中的其他節(jié)點(diǎn)查看自己緩存空間里數(shù)據(jù)消息的ID，若有某個(gè)數(shù)據(jù)消息的ID跟sink節(jié)點(diǎn)廣播的數(shù)據(jù)消息ID相同，則直接刪除，根據(jù)文獻(xiàn)[17]可知sink節(jié)點(diǎn)廣播消息對(duì)網(wǎng)絡(luò)中正常數(shù)據(jù)消息傳輸?shù)挠绊懖淮?，為此本文忽略該影響。此外?jié)點(diǎn)會(huì)定期檢查自己緩存隊(duì)列里的數(shù)據(jù)消息，當(dāng)數(shù)據(jù)消息的延遲容忍度減為0時(shí)，作刪除處理。

3 仿真實(shí)驗(yàn)

選取文獻(xiàn)[12]提出的路由算法(FLDEAR)、文獻(xiàn)[9]提出的路由算法(一種基于能耗自選演繹機(jī)制的延遲容忍網(wǎng)絡(luò)路由算法)和FAD算法作為比較對(duì)象，選擇的原因是文獻(xiàn)[12]和文獻(xiàn)[9]提出的路由算法分別是2018年和2017年提出來(lái)的，比較新，F(xiàn)AD算法是比較經(jīng)典的路由算法。四種算法在默認(rèn)的仿真條件下針對(duì)網(wǎng)絡(luò)生命周期、數(shù)據(jù)消息傳送成功率和每個(gè)數(shù)據(jù)消息的平均副本數(shù)這幾個(gè)性能指標(biāo)進(jìn)行比較，并通過(guò)改變節(jié)點(diǎn)數(shù)從而改變節(jié)點(diǎn)密度以及改變節(jié)點(diǎn)的傳輸半徑觀察四種算法中每個(gè)數(shù)據(jù)消息平均副本數(shù)和數(shù)據(jù)消息的投遞率；值得注意的是，每個(gè)數(shù)據(jù)消息的平均副本數(shù)反映了網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗情況，平均副本數(shù)越多，能耗越大。此外當(dāng)節(jié)點(diǎn)的緩存空間已滿，即緩存空間利用率為100%時(shí)，四種路由算法下節(jié)點(diǎn)只接收數(shù)據(jù)延遲容忍度比緩存列表中最大延遲容忍度小的數(shù)據(jù)，并替換緩存列表中延遲容忍度最大的數(shù)據(jù)消息。以下實(shí)驗(yàn)結(jié)果如未特別說(shuō)明，均為50次實(shí)驗(yàn)結(jié)果的平均值。

本文依據(jù)數(shù)據(jù)消息的延遲容忍度對(duì)消息進(jìn)行排隊(duì)，旨在提高網(wǎng)絡(luò)中數(shù)據(jù)消息的投遞率，因?yàn)檠舆t容忍度越低則優(yōu)先級(jí)越高，可以優(yōu)先得到傳輸。實(shí)驗(yàn)部分將通過(guò)數(shù)據(jù)消息的投遞率和副本數(shù)指標(biāo)對(duì)算法進(jìn)行驗(yàn)證。對(duì)于算法的時(shí)間效率，可以通過(guò)算法的時(shí)間復(fù)雜度分析得到。

3.1 實(shí)驗(yàn)統(tǒng)計(jì)量

1)網(wǎng)絡(luò)生命周期。

本文定義網(wǎng)絡(luò)的生命周期為從網(wǎng)絡(luò)開(kāi)始運(yùn)行到有一半傳感器節(jié)點(diǎn)能量耗盡時(shí)的時(shí)間間隔。

2)數(shù)據(jù)傳送成功率。

指最后被sink節(jié)點(diǎn)成功接收的所有數(shù)據(jù)消息的數(shù)目與所有源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)消息數(shù)目的比值。反映的是在數(shù)據(jù)消息的有效期內(nèi)，能夠成功被傳輸?shù)絪ink節(jié)點(diǎn)的數(shù)據(jù)消息的情況，數(shù)據(jù)消息投遞成功率越高表示網(wǎng)絡(luò)的效率越高。對(duì)應(yīng)的計(jì)算式為：Dsec=Dd/Ds，Dd表示被sink節(jié)點(diǎn)成功接收的數(shù)據(jù)消息的數(shù)量，Ds表示所有源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)消息的數(shù)量。

3)數(shù)據(jù)消息的平均副本數(shù)。

指網(wǎng)絡(luò)中所有數(shù)據(jù)消息的數(shù)目與不同的數(shù)據(jù)消息個(gè)數(shù)的比值。每個(gè)數(shù)據(jù)消息的平均副本數(shù)反映數(shù)據(jù)消息在網(wǎng)絡(luò)中的冗余度以及網(wǎng)絡(luò)的能量消耗情況，平均副本數(shù)越多，冗余度越大，網(wǎng)絡(luò)中的能量消耗越多。

3.2 實(shí)驗(yàn)設(shè)置

使用Matlab作為仿真軟件，主要仿真參數(shù)設(shè)置如表1所示。

表1 仿真實(shí)驗(yàn)參數(shù)

3.2.1 節(jié)點(diǎn)通信半徑對(duì)性能的影響

傳感器節(jié)點(diǎn)通信半徑越大，與sink節(jié)點(diǎn)和網(wǎng)絡(luò)中其他傳感器節(jié)點(diǎn)相遇的可能性越大，那么數(shù)據(jù)消息的投遞率也隨之變大。為了驗(yàn)證通信半徑對(duì)算法性能的影響，改變傳感器節(jié)點(diǎn)的通信半徑，并觀察4種路由算法下數(shù)據(jù)消息的投遞率和副本數(shù)的變化。仿真實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 節(jié)點(diǎn)通信半徑對(duì)算法性能的影響

從圖5(a)可以看出隨著傳感器節(jié)點(diǎn)的通信半徑逐漸增大，4種路由算法對(duì)應(yīng)的消息投遞率曲線都呈現(xiàn)上升的變化，其中本文提出的路由算法DTVC的消息投遞率高于其他3個(gè)算法。這是因?yàn)殡S著節(jié)點(diǎn)通信半徑的增大，網(wǎng)絡(luò)中的節(jié)點(diǎn)可相遇的節(jié)點(diǎn)數(shù)增多，所以4種路由算法對(duì)應(yīng)的消息投遞率增大。本文提出的路由算法DTVC中，節(jié)點(diǎn)在傳輸數(shù)據(jù)消息的時(shí)候既考慮相遇節(jié)點(diǎn)的投遞能力又考慮數(shù)據(jù)消息的延遲容忍度，此外通過(guò)刪除網(wǎng)絡(luò)中的無(wú)效數(shù)據(jù)消息，從而節(jié)省網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗并提高節(jié)點(diǎn)緩存空間的有效利用，所以網(wǎng)絡(luò)中數(shù)據(jù)消息的投遞率最高。FAD算法中，數(shù)據(jù)消息的傳輸類似于傳染算法，之后依據(jù)消息的容錯(cuò)大小決定其轉(zhuǎn)發(fā)優(yōu)先級(jí)，但是傳感器節(jié)點(diǎn)的存儲(chǔ)空間有限，隨著網(wǎng)絡(luò)的運(yùn)行傳感器節(jié)點(diǎn)的緩存隊(duì)列很快就會(huì)被用完，節(jié)點(diǎn)會(huì)刪除容錯(cuò)最大的數(shù)據(jù)消息，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)消息的頻率很高時(shí)，數(shù)據(jù)消息還來(lái)不及傳輸就被節(jié)點(diǎn)刪除。文獻(xiàn)[12]提出的路由算法只考慮傳感器節(jié)點(diǎn)剩余能量和距離2個(gè)因素，沒(méi)有考慮數(shù)據(jù)消息的屬性，延遲容忍度較低的數(shù)據(jù)消息可能會(huì)因?yàn)闆](méi)有及時(shí)被傳輸而失效。文獻(xiàn)[9]提出的路由算法中，傳感器節(jié)點(diǎn)根據(jù)自身的剩余能量決定是否轉(zhuǎn)發(fā)接收到的數(shù)據(jù)消息，導(dǎo)致很多數(shù)據(jù)消息被中間轉(zhuǎn)發(fā)節(jié)點(diǎn)直接丟棄，其次沒(méi)有對(duì)節(jié)點(diǎn)的緩存隊(duì)列進(jìn)行有效地管理。

從圖5(b)可以看出隨著傳感器節(jié)點(diǎn)的通信半徑逐漸增大，4種路由算法對(duì)應(yīng)的數(shù)據(jù)消息平均副本數(shù)曲線都呈現(xiàn)上升的趨勢(shì)。其中路由算法DTVC的消息平均副本數(shù)低于其他3個(gè)算法。這是因?yàn)楫?dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)可相遇的節(jié)點(diǎn)數(shù)增多時(shí)，滿足條件的鄰居節(jié)點(diǎn)數(shù)隨著增多。本文提出的路由算法DTVC中，為了控制數(shù)據(jù)消息的副本數(shù)，規(guī)定只有源節(jié)點(diǎn)可以復(fù)制數(shù)據(jù)消息。而其他3個(gè)路由算法中，復(fù)制數(shù)據(jù)消息時(shí)不分源節(jié)點(diǎn)和中繼節(jié)點(diǎn)，所以會(huì)使得數(shù)據(jù)消息的冗余度大于DTVC。

3.2.2 節(jié)點(diǎn)密度對(duì)性能的影響

本文通過(guò)改變網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)數(shù)目控制節(jié)點(diǎn)密度。不失一般性，節(jié)點(diǎn)密度越大，網(wǎng)絡(luò)中任意2個(gè)節(jié)點(diǎn)相遇的可能性也就越大，數(shù)據(jù)消息的投遞率也會(huì)隨著增大；但是隨著節(jié)點(diǎn)密度的增加，采用多副本傳輸時(shí)網(wǎng)絡(luò)中數(shù)據(jù)消息的副本數(shù)也會(huì)增多，從而增加網(wǎng)絡(luò)的負(fù)載和能量消耗。圖6(a)顯示了節(jié)點(diǎn)密度對(duì)4種算法中數(shù)據(jù)消息投遞率的影響，可以看出隨著節(jié)點(diǎn)密度的逐漸增大，4種路由算法對(duì)應(yīng)的數(shù)據(jù)消息投遞率都在增大，但是增加的幅度越來(lái)越小。這是因?yàn)殡S著節(jié)點(diǎn)密度的增大，數(shù)據(jù)消息可以通過(guò)源節(jié)點(diǎn)直接傳輸給sink節(jié)點(diǎn)和通過(guò)中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)給sink節(jié)點(diǎn)的可能性都在增大，但是隨著節(jié)點(diǎn)數(shù)的不斷增多，增加的數(shù)據(jù)消息副本數(shù)帶來(lái)的投遞率就不那么明顯了。從圖6(b)可以看出節(jié)點(diǎn)密度對(duì)4種算法平均副本數(shù)的影響，可以看出消息的副本數(shù)隨著節(jié)點(diǎn)密度的增大而增多。原因如前面所述。

4 結(jié)語(yǔ)

本文在前人工作的基礎(chǔ)上，通過(guò)對(duì)移動(dòng)傳感器網(wǎng)絡(luò)中基于多副本傳輸?shù)穆酚蓡?wèn)題作進(jìn)一步研究，當(dāng)節(jié)點(diǎn)做隨機(jī)運(yùn)動(dòng)時(shí)提出了低能耗數(shù)據(jù)消息傳輸機(jī)制DTVC。按照傳統(tǒng)思想，發(fā)送節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)消息的時(shí)候大多從鄰居節(jié)點(diǎn)中選擇傳輸概率比自己大的節(jié)點(diǎn)，本文不依賴于相遇節(jié)點(diǎn)的傳輸概率，而是根據(jù)發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)的屬性以及數(shù)據(jù)消息的屬性來(lái)決定是否進(jìn)行數(shù)據(jù)消息的轉(zhuǎn)發(fā)。此外為了減少網(wǎng)絡(luò)中不必要的能量消耗，刪除無(wú)效數(shù)據(jù)消息。下一步的工作是考慮網(wǎng)絡(luò)異構(gòu)時(shí)如何實(shí)現(xiàn)數(shù)據(jù)的有效傳輸路由問(wèn)題。

圖6 節(jié)點(diǎn)密度對(duì)算法性能的影響