移動傳感網中基于虛擬貨幣的路由策略

王國玲，楊文忠，張振宇，夏揚波，殷亞博，楊慧婷

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

0 引言

移動無線傳感器網絡是一種以數據為中心的延遲容忍無線網絡[1]，節點由電池提供能量，并且當節點的能量耗盡時給節點充電或更換電池極其困難，其次節點的通信距離有限并且由于節點的移動，節點間的鏈路連接動態變化[2-3]。在移動無線傳感器網絡中，設計有效的數據傳輸策略成為一個研究熱點，并且隨著人們對移動無線傳感器網絡的深入研究，使其廣泛應用于野生動物監測[4]、移動智能照明控制[5]等。

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

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

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

1 網絡模型和問題描述

1.1 網絡模型

本文研究的是同構傳感器網絡，整個網絡的構成包括一個位置固定在正方形監測區域中心的sink節點和分布在該區域內做隨機運動的普通傳感器節點，如圖1所示。普通傳感器節點擁有相同的存儲空間、相同的通信半徑R、相同的初始能量、相同的初始財富值M。

圖1 節點的分布

這里的財富值是借鑒經濟學里的概念，財富值的大小表示節點的可用資源情況。節點的可用資源指節點的剩余能量和節點的剩余緩存空間。

定義1 移動模型。采用隨機移動模型Random Waypoint，運動的節點通過GPS或其他定位方法知道此次運動起點的位置，并且隨機確定此次運動的目的地，朝著目的地以某個位于[vmin,vmax]的速度做勻速直線運動，到達目的地后隨機停留一段時間，然后以此次的目的地作為下一次的運動的起點。如圖2所示。

圖2 節點的運動模型

定義2 議價模型。兩個節點相遇時，需要轉發或發送數據消息的一方視為買方，接收數據消息的一方視為賣方。買方和賣方都是根據數據的延遲容忍度、數據大小、自己的剩余能量和緩存空間利用率進行定價，當出價大于或等于要價時交易成功，即可進行消息的復制并轉發；否則交易失敗，節點繼續運動，等待跟其他節點的相遇。

定義3 數據消息的延遲容忍度。每個傳感器都裝有一個計時器，當采集到某個數據并形成數據消息時開始倒計時，如果在數據消息被成功傳輸到sink節點之前延遲容忍度Tj減為0，則該數據消息失效。為簡明起見，數據消息從買方被復制到賣方所花的時間忽略不計。

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

1.2 問題描述

針對移動無線傳感器網絡中節點做隨機運動的路由問題，前人作了相應的研究，提出了相關的路由算法。可以看出大多都是基于相遇節點的傳輸概率進行數據消息的復制轉發；而且節點在計算傳輸概率時考慮的因素不全，沒有綜合考慮節點的屬性和數據消息的屬性；此外節點在進行隨機運動時，其運動速度和運動方向都是隨機的，過分依靠節點的傳輸概率進行數據消息的復制轉發意義不是很大，反而會浪費節點寶貴的能量資源和計算資源，甚至會錯過最佳的數據消息轉發機會。因此有效的數據消息路由算法應該具備以下幾個特點：1)下一跳節點的選擇應該綜合考慮節點的剩余能量、緩存空間大小等節點屬性以及數據消息大小、延遲容忍度等數據消息的屬性；2)刪除無效數據消息，避免無效消息帶來的資源浪費，甚至影響有效數據消息的轉發和傳輸；3)均衡整個網絡中節點的能量消耗，避免部分節點能量消耗過大，從而延長網絡的生命周期。

1.3 能量模型

采用簡單無線通信能耗模型[15]。由于通信模塊的能量消耗最大[16]，簡單起見，只考慮節點在發送數據消息和接收數據時的能量消耗，忽略其他方面帶來的能量消耗。節點在發送數據消息時的能量消耗與距離d和數據長度L有關，當d小于距離閾值d0時采用自由空間模型，當d大于距離閾值d0時采用多徑衰減模型。

圖3 能耗模型

如果節點發送Lb的數據，傳輸距離為d時，所消耗的能量滿足以下公式：

(1)

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

如果節點接收Lb的數據包，那么能量消耗如下：

ERX(l)=lEelec

(2)

本文假設節點的通信半徑R小于d0，兩個節點相遇時，節點發送長度為Lb的數據消息時能量消耗為：

ERX(l)=lEelec+lεfsd2

(3)

節點發送和接收長度為Lb的數據消息時總能量消耗為：

E(l)=2lEelec+lεfsd2

(4)

2 數據傳輸機制——DTVC

為了解決節點基于隨機運動模型的路由問題，本文提出了一種基于虛擬貨幣的低能耗數據傳輸機制——DTVC(Data Transmission based on Virtual Currency)。數據消息字段如圖4所示，Nop表示協議信息，Seq表示數據消息的ID，SID表示源節點ID，JID表示目的節點的ID，L表示數據消息的長度，RSD表示數據消息的延遲容忍度。基本思想描述如下：攜帶數據消息的節點在隨機運動的過程中若與其他節點相遇，先向對方發送一個包含需要轉發或傳輸的數據消息的ID、數據消息的目的節點的ID、數據消息的大小、發送節點的剩余能量以及數據消息的延遲容忍度的hello包；收到hello包后先查看數據消息的ID和目的節點的ID，若接收節點緩存里沒有該數據消息，則回復一個包含接收節點的ID、接收節點的剩余能量和該數據消息的ID的ACK確認信息；發送節點查看ACK確認信息后，若接收節點是數據消息的目的節點，則直接發送數據消息，否則根據定價規則進行出價，接收節點根據定價規則進行要價，如果成交則把數據消息發送給接收節點并更新財富值，否則繼續運動等待與其他節點相遇。

圖4 數據消息的構成

Fig. 4 Composition of data messages

2.1 買方和賣方的定價規則

兩個節點相遇后，根據規定的定價機制進行定價，如果買方的出價大于或等于賣方的要價即c≥b，則交易成功。設買方的出價為c，賣方的要價為b，對應如下：

(5)

其中:α、β和γ為節點的剩余緩存空間、數據的延遲容忍度和節點剩余能量對應的權重，且α+β+γ=1，L是數據消息的長度，Tm指當前數據消息m的延遲容忍度，Tinit指數據消息產生時的延遲容忍度，Sj指節點j的空間利用率，Ej_res指節點j的剩余能量，Einit指節點j的初始能量。

(6)

其中:Tinit、Tm和Einit的含義跟上式相同，Sk指節點k的空間利用率，Ek_res指節點k的剩余能量，ω、η和θ是對應的權重，且ω+η+θ=1。買方和賣方按規定的定價機制進行定價，從而決定此次交易是否成功。

2.2 權重的設置

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

由式(6)可知ω、η、θ為節點緩存空間、數據消息延遲容忍度和節點剩余能量對應的權值。矩陣B里的每個值的含義與A類似，對賣方來說，當節點的剩余能量很小以及緩存空間小時就不愿意接收消息，所以緩存空間較延遲容忍度重要性大一些，較剩余能量重要性也小一些，延遲容忍度較剩余能量重要性小一些。B里的第一行取值為1、5和1/7，第二行取值為7、1、1/3，判斷矩陣B的全部取值如下：

2.3 數據消息的轉發

采用動態多副本進行數據消息的轉發，具體的轉發過程描述如下：

步驟1 準備階段。節點j攜帶數據消息s和節點k相遇，首先節點j向節點k發送一個hello包，之后收到來自節點k的確認信息ACK，若節點k的緩存里沒有數據消息s并且是數據s的目的節點，節點j直接發送數據消息s，轉步驟5；否則節點j根據式(5)計算出價c，轉步驟2。

步驟2 服務請求。節點j向節點k發出包含數據消息s的ID、長度l和出價c的服務請求。

步驟3 服務應答。節點k對該請求消息進行查看，如果緩存里的數據消息的ID跟數據消息s的ID都不同，則節點k根據(6)計算要價b，并把b和c進行比較，如果c≥b，給出一個包含數據消息ID以及成交價格0.5(b+c)的確認信息，表示愿意接收該數據消息，轉步驟4；否則此次交易失敗，節點j攜帶數據消息s繼續運動。

步驟4 數據發送。節點j收到確認信息后，如果節點j對數據s是源節點，需要對數據s進行一次復制；否則不復制直接發送數據消息s給節點k。

步驟5 財富值更新。節點j的財富值減0.5(b+c)，節點k的財富值增加0.5(b+c)。

假設當前有k′個節點進入節點j的通信范圍，即有k′個節點與節點j相遇，令Σ={Ψk|1≤k′}表示k′個相遇節點的集合。數據消息傳輸算法如下：

輸入：相遇節點;

輸出：滿足條件的相遇節點并判斷是否需要復制。

Φ=?

fork=1 tok′

//識別相遇節點

do ifkis sink node

forward message(d,k);

//節點j直接把s發送給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);

//節點j復制并轉發給滿足條件的節點Φn

else forn=1 to |Φ|

forward message(s,Φn);

//節點直接轉發給滿足條件的節點Φn

end for

end for

end if

2.4 算法的性能分析

時間復雜度分析 對于含n個節點的傳感器網絡，識別鄰居節點所花的時間為O(n)，之后節點進行數據消息的復制和傳輸所花的時間為O(1)，刪除無效數據消息所花的時間也為O(1)，所以最終算法的時間復雜度為O(n)。

空間復雜度分析 網絡中每個節點存儲的數據消息數為O(1)個，對于規模為n的傳感器網絡，其空間復雜度為O(n)。

2.5 無效數據消息的處理

當sink節點收到某個經過中間節點轉發的數據消息后，廣播一個包含該數據消息ID的消息，網絡中的其他節點查看自己緩存空間里數據消息的ID，若有某個數據消息的ID跟sink節點廣播的數據消息ID相同，則直接刪除，根據文獻[17]可知sink節點廣播消息對網絡中正常數據消息傳輸的影響不大，為此本文忽略該影響。此外節點會定期檢查自己緩存隊列里的數據消息，當數據消息的延遲容忍度減為0時，作刪除處理。

3 仿真實驗

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

本文依據數據消息的延遲容忍度對消息進行排隊，旨在提高網絡中數據消息的投遞率，因為延遲容忍度越低則優先級越高，可以優先得到傳輸。實驗部分將通過數據消息的投遞率和副本數指標對算法進行驗證。對于算法的時間效率，可以通過算法的時間復雜度分析得到。

3.1 實驗統計量

1)網絡生命周期。

本文定義網絡的生命周期為從網絡開始運行到有一半傳感器節點能量耗盡時的時間間隔。

2)數據傳送成功率。

指最后被sink節點成功接收的所有數據消息的數目與所有源節點發送的數據消息數目的比值。反映的是在數據消息的有效期內，能夠成功被傳輸到sink節點的數據消息的情況，數據消息投遞成功率越高表示網絡的效率越高。對應的計算式為：Dsec=Dd/Ds，Dd表示被sink節點成功接收的數據消息的數量，Ds表示所有源節點發送的數據消息的數量。

3)數據消息的平均副本數。

指網絡中所有數據消息的數目與不同的數據消息個數的比值。每個數據消息的平均副本數反映數據消息在網絡中的冗余度以及網絡的能量消耗情況，平均副本數越多，冗余度越大，網絡中的能量消耗越多。

3.2 實驗設置

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

表1 仿真實驗參數

3.2.1 節點通信半徑對性能的影響

傳感器節點通信半徑越大，與sink節點和網絡中其他傳感器節點相遇的可能性越大，那么數據消息的投遞率也隨之變大。為了驗證通信半徑對算法性能的影響，改變傳感器節點的通信半徑，并觀察4種路由算法下數據消息的投遞率和副本數的變化。仿真實驗結果如圖5所示。

圖5 節點通信半徑對算法性能的影響

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

從圖5(b)可以看出隨著傳感器節點的通信半徑逐漸增大，4種路由算法對應的數據消息平均副本數曲線都呈現上升的趨勢。其中路由算法DTVC的消息平均副本數低于其他3個算法。這是因為當網絡中的節點可相遇的節點數增多時，滿足條件的鄰居節點數隨著增多。本文提出的路由算法DTVC中，為了控制數據消息的副本數，規定只有源節點可以復制數據消息。而其他3個路由算法中，復制數據消息時不分源節點和中繼節點，所以會使得數據消息的冗余度大于DTVC。

3.2.2 節點密度對性能的影響

本文通過改變網絡中的傳感器節點數目控制節點密度。不失一般性，節點密度越大，網絡中任意2個節點相遇的可能性也就越大，數據消息的投遞率也會隨著增大；但是隨著節點密度的增加，采用多副本傳輸時網絡中數據消息的副本數也會增多，從而增加網絡的負載和能量消耗。圖6(a)顯示了節點密度對4種算法中數據消息投遞率的影響，可以看出隨著節點密度的逐漸增大，4種路由算法對應的數據消息投遞率都在增大，但是增加的幅度越來越小。這是因為隨著節點密度的增大，數據消息可以通過源節點直接傳輸給sink節點和通過中繼節點轉發給sink節點的可能性都在增大，但是隨著節點數的不斷增多，增加的數據消息副本數帶來的投遞率就不那么明顯了。從圖6(b)可以看出節點密度對4種算法平均副本數的影響，可以看出消息的副本數隨著節點密度的增大而增多。原因如前面所述。

4 結語

本文在前人工作的基礎上，通過對移動傳感器網絡中基于多副本傳輸的路由問題作進一步研究，當節點做隨機運動時提出了低能耗數據消息傳輸機制DTVC。按照傳統思想，發送節點在轉發數據消息的時候大多從鄰居節點中選擇傳輸概率比自己大的節點，本文不依賴于相遇節點的傳輸概率，而是根據發送節點和接收節點的屬性以及數據消息的屬性來決定是否進行數據消息的轉發。此外為了減少網絡中不必要的能量消耗，刪除無效數據消息。下一步的工作是考慮網絡異構時如何實現數據的有效傳輸路由問題。

圖6 節點密度對算法性能的影響