鄭永剛，孫文勝

(杭州電子科技大學(xué) 通信工程學(xué)院，浙江 杭州 310018)

0 引 言

在機會網(wǎng)絡(luò)當中，節(jié)點攜帶的能量是有限的，如果一個設(shè)備節(jié)點的能量過快耗盡，就會喪失接收和轉(zhuǎn)發(fā)消息的能力，從而影響整個機會網(wǎng)絡(luò)的性能。如何節(jié)約機會網(wǎng)絡(luò)中移動節(jié)點的能量變得至關(guān)重要。為了解決這個問題，許多研究者采用周期性的休眠和喚醒移動節(jié)點的方式。但當兩個節(jié)點處在休眠狀態(tài)下時，它們可能無法檢測到對方，導(dǎo)致消息在機會網(wǎng)絡(luò)中傳遞的時延增加，因此需要合理的轉(zhuǎn)發(fā)策略來降低消息時延[1]。

在真實的環(huán)境中，大多數(shù)的消息具有時效性，例如天氣、交通信號等消息。過期的消息是毫無價值的。因此，在這種情況下，需要預(yù)先給定一個預(yù)期的消息可容忍時延時間，并且設(shè)定一個合理的周期性休眠時間，確保消息傳遞過程中的時延在可容忍的范圍之內(nèi)。

機會網(wǎng)絡(luò)中，設(shè)計合理的休眠周期可以快速降低節(jié)點的功耗。雖然休眠對消息的時延會造成較大的影響，但如果喚醒期間采用Epdemic路由算法進行大量的消息轉(zhuǎn)發(fā)，同樣會使得節(jié)點的能量過早耗盡[2]。如果喚醒期間采用Direct Delivery算法，該算法在消息傳輸過程當中，只有遇到目的節(jié)點才會進行轉(zhuǎn)發(fā)，則消息的時延顯然是無法接受的。

因此需要找到一種同時擁有合理的休眠占空因子和消息轉(zhuǎn)發(fā)策略的算法。本文首先利用推導(dǎo)得到一個占空因子，在這基礎(chǔ)上為每個節(jié)點設(shè)置一個有效度，代表當前節(jié)點與目的節(jié)點相遇的機會大小，通過該有效度判斷是否對消息進行轉(zhuǎn)發(fā)。該算法的休眠機制可以明顯延長節(jié)點生命周期，而其轉(zhuǎn)發(fā)策略可以顯著降低消息的時延，提高消息傳遞成功的概率。

1 相關(guān)工作

機會網(wǎng)絡(luò)往往由一些便攜設(shè)備組成，如手機、藍牙設(shè)備等，這些移動設(shè)備的工作狀況可以影響整個網(wǎng)絡(luò)的性能。顯然，能量充足的節(jié)點及其轉(zhuǎn)發(fā)策略，在消息傳遞過程中起決定性作用。因此，如何節(jié)約機會網(wǎng)絡(luò)中節(jié)點的能量和設(shè)計合理的轉(zhuǎn)發(fā)策略，變成了一個亟待解決的問題[3]。

利用固定占空比休眠策略，文獻[4]提出了一種探索式路由算法，該算法通過優(yōu)化節(jié)點間接觸檢測方式來節(jié)約能量。通過理論分析和計算，證明了在某些特定的假設(shè)情況下，以固定占空比的形式進行休眠可以達到最佳的節(jié)能效果。雖然移動節(jié)點以固定占空比進行休眠能夠達到節(jié)能的效果，但是它增加了節(jié)點檢測到對方的時間和消息時延,最終影響消息傳遞成功的概率。

在文獻[5]中，作者提出了一種基于Spray and Focus改進的算法MSAF，該算法通過為每個節(jié)點維護一個代表與目的節(jié)點相遇機會大小的有效度，比較節(jié)點自身有效度和其鄰居節(jié)點有效度的大小，向有效值度大的節(jié)點轉(zhuǎn)發(fā)消息。通過不斷的比較相遇節(jié)點的有效度，消息會迅速向目的節(jié)點靠近。該算法雖然可以降低消息的時延但其節(jié)能效果不佳。

Biondi E研究中[6]提出的EEAODC算法，在充分考慮到可接受的消息傳遞時延的情況下，提出兩個節(jié)點之間以合理的占空因子進行周期性休眠。Biondi E假設(shè)消息的時延小于預(yù)期時延的最大值dmax時的最小概率為Pmin，即P{DΔopt

2 FLADC算法

2.1 主要符號的含義

FLADC算法中用到的主要符號，其詳細描述見表1。

2.2 求解最佳的占空因子

節(jié)點通信的時間間隔表示在機會網(wǎng)絡(luò)當中兩個移動節(jié)點成功連接并通信到下一次接觸并成功傳遞消息的時間間隔。

表1 符號描述

通過考慮機會網(wǎng)絡(luò)當中的所有節(jié)點，推導(dǎo)得出一個占空因子。假設(shè)Pmin表示消息時延大于dmax的最小概率，則有P{D

(1)

(2)

Bracciale L在其文獻[8]中證明了節(jié)點在周期性休眠模式下的機會網(wǎng)絡(luò)中通信的時間間隔仍然服從指數(shù)分布，其中休眠模式下指數(shù)分布的參數(shù)為λΔ=λΔ(λΔ=E[tΔ]-1)。當考慮網(wǎng)絡(luò)中所有節(jié)點時，則可以得出休眠模式下消息傳遞成功的時延仍然近似的服從指數(shù)分布，其中指數(shù)分布的參數(shù)為λDΔ=λΔ/H，則有λDΔ=λΔ/H=λΔ/H(1≤H≤N-1)。因此，可以得出。

當節(jié)點通信的時間間隔t服從參數(shù)為λ指數(shù)分布時，基于最小概率Pmin的消息的延遲時間小于dmax。則可求出最佳占空因子為

(3)

證明：

由式(2)可以得出

(4)

由式(1)可以得出

(5)

結(jié)合式(4)和式(5)可以得出

(6)

由式(6)可推斷出DΔ的概率分布函數(shù)為

(7)

由P{DΔ

(8)

即可得式(9)

(9)

由文獻[9]給出的隨機網(wǎng)絡(luò)中計算平均路徑長度的方法可得H

H≈logN/log(psN)

(10)

其中，N表示網(wǎng)絡(luò)中節(jié)點的個數(shù)，ps表示在機會網(wǎng)絡(luò)中任意兩個節(jié)點通信的概率。

結(jié)合式(9)和式(10)可得

證畢。

在給定可容忍的消息時延和傳遞成功概率的條件下，可得到節(jié)點周期性休眠的最佳占空因子ΔFLADC。

2.3 求解節(jié)點的有效度

節(jié)點Vi的平均消息轉(zhuǎn)發(fā)率Rfwd為

(11)

節(jié)點Vi的平均消息刪除率Rdrop為

(12)

節(jié)點Vi的緩存占用率Roccupy為

(13)

定義節(jié)點屬性FVi函數(shù)為[5]

(14)

其中，α,β,γ分別為節(jié)點Vi在當前時刻Rfwd,Rdrop和Roccupy的權(quán)重因子，并且α+β+γ=1。

節(jié)點之間的相遇屬性Fcon，定義如下[5]

(15)

其中，Ncon表示節(jié)點Vi截至當前與目標節(jié)點相遇的總次數(shù)。Tcon表示相遇的總持續(xù)時間。Tint表示節(jié)點相遇的時間間隔，Ttatal表示仿真時間。

節(jié)點的有效度QVi用于決策消息的轉(zhuǎn)發(fā)過程，將消息轉(zhuǎn)發(fā)給與目的節(jié)點接觸機會較大的中繼節(jié)點，即向有效度高的節(jié)點轉(zhuǎn)發(fā)消息，這樣有助于提高消息的轉(zhuǎn)發(fā)效率，定義如下

QVi=FVi×Fcon

(16)

3 FLADC算法的提出與實施

根據(jù)2.2中的結(jié)論，在給定消息傳遞時延和傳遞成功概率的條件下，由式(3)可以得出最佳占空因子ΔFALDC。

機會網(wǎng)絡(luò)中節(jié)點交替進行休眠和喚醒的周期T是固定的。對每一個節(jié)點來說，如果當前系統(tǒng)時間等于最后醒來的時間加ton，該節(jié)點自動將自己轉(zhuǎn)入睡眠狀態(tài)，并將最后一次睡眠時間設(shè)置為當前系統(tǒng)時間。如果當前系統(tǒng)時間等于最后休眠的時間加(T-ton)，則節(jié)點將自動轉(zhuǎn)為喚醒狀態(tài)并將最后一次喚醒的時間設(shè)置為當前系統(tǒng)時間。

圖1 FLADC算法的具體流程

4 仿真和結(jié)果分析

4.1 實驗設(shè)置

在實驗過程中，將FLADC與EEAODC，MSAF以及Epdemic算法進行對比。

本文使用的仿真工具ONE[11]是一款專門針對DTN網(wǎng)絡(luò)環(huán)境開發(fā)的仿真平臺，具有面向?qū)ο?，離散事件驅(qū)動、可以模擬真實網(wǎng)絡(luò)環(huán)境的特點。仿真實驗是使用ONE中的工作日模型來進行的，該移動模型可以很好地模擬人類活動的真實軌跡并且具有可調(diào)控、可配置等優(yōu)點。實驗收集了12小時內(nèi)360個節(jié)點的移動數(shù)據(jù)。仿真的具體參數(shù)設(shè)置見表2。

表2 實驗所需參數(shù)

本章根據(jù)文獻[12]中提出的基于工作日模型的數(shù)據(jù)擬合方法，對沒有部署占空比節(jié)能策略產(chǎn)生的節(jié)點接觸間隔時間數(shù)據(jù)進行了分析，得出該數(shù)據(jù)集服從指數(shù)分布且參數(shù)λ=5.19×10-4。設(shè)定預(yù)期最大消息延遲時間為dmax=10800s，最小概率Pmin=0.8。網(wǎng)絡(luò)中任意兩個節(jié)點通信的概率為ps=0.4，根據(jù)式(3)可以計算出ΔFLADC=0.3401，根據(jù)文獻[6]中的結(jié)論可以得出ΔEEAODC=0.3612。設(shè)備的能耗功率值見表3，本文中節(jié)點的初始能量設(shè)定為17 000 J。

表3 設(shè)備的能耗功率值

4.2 剩余能量的分析與比較

在機會網(wǎng)絡(luò)中，移動節(jié)點主要依靠電池供電其能量有限。節(jié)點在掃描周圍設(shè)備，傳輸消息和休眠時都會不可避免地消耗能量。圖2展示了在應(yīng)用FLADC，EEALODC，MSAF和Epidemic算法下的機會網(wǎng)絡(luò)中所有節(jié)點的剩余能量的平均值的變化情況，仿真結(jié)果表明在4種算法當中FLADC功耗最低，節(jié)能效果最佳，而Epidemic最差，MSAF和EEAODC算法次之。網(wǎng)絡(luò)的生命周期指從機會網(wǎng)絡(luò)創(chuàng)建開始到最后一個節(jié)點能量耗盡所經(jīng)歷的時間。網(wǎng)絡(luò)的生命周期與節(jié)點的功耗成反比，因此4種算法的生命周期為TFLADC>TEEAODC>TMSAF>TEpidemic。在仿真中節(jié)點休眠占空因子的大小對節(jié)能效果起決定性作用，轉(zhuǎn)發(fā)策略也會影響節(jié)點的功耗，但為次要因素。而ΔFLADC<ΔEEAODC<ΔMSAF=ΔEpidemic，與仿真結(jié)果相符。

圖2 隨著時間的推移節(jié)點攜帶平均剩余能量

4.3 消息傳遞概率分析與比較

消息傳遞概率等于成功到達目的節(jié)點的消息數(shù)量與網(wǎng)絡(luò)中創(chuàng)建的所有消息的總數(shù)之比。在圖3中，前6個小時內(nèi)Epidemic和MSAF的消息傳遞概率高于FLADC和EEAODC算。因為在Epidemic和MSAF算法中，節(jié)點總是處于喚醒狀態(tài)而且能量充足，不會錯過任何有效的接觸，而Epidemic算法傳遞概率會略高于MSAF，因為Epidemic是泛洪傳播，效率更高，不過功耗也更大。后6個小時，部分節(jié)點因能量耗盡而失去通信能力。這種情況削弱了機會網(wǎng)絡(luò)節(jié)點的連通性。此外，它影響消息的傳遞概率，因此Epidemic和MSAF的消息傳遞概率會快速下降而此時EEAOD和FLADC算法中節(jié)點的能量充足，消息傳遞概率幾乎不變。

圖3 隨著時間的推移消息投遞成功的概率

對于EEAOD算法由于其在喚醒狀態(tài)采用的轉(zhuǎn)發(fā)策略與Epidemic一致，所以開始時其消息傳遞概率略高于FLADC算法，而經(jīng)過8小時左右之后FLADC算法會優(yōu)于EEAODC，因為EEAODC算法沒有對轉(zhuǎn)發(fā)消息進行限制，對節(jié)點能量和緩存空間的消耗高于FLADC算法，一旦節(jié)點的能量或緩存空間耗盡就無法轉(zhuǎn)發(fā)消息，從而影響消息傳遞成功概率。FLADC算法在兼顧消息傳遞概率的同時更加節(jié)能。

4.4 消息時延的分析與比較

消息時延等于消息從創(chuàng)建開始到到達目的節(jié)點所經(jīng)歷的時間。如圖4所示，F(xiàn)LADC和EEAODC平均消息延遲低于MSAF和Epidemic算法。在后期仿真實驗中，MSAF和Epidemic算法有更多的節(jié)點耗盡能量并失去通信能力。EEAODC在喚醒狀態(tài)下的轉(zhuǎn)發(fā)策略相比于FLADC算法沒有進行優(yōu)化，因此功耗更大節(jié)點也會較快死亡，因此FLADC的平均時延優(yōu)于EEAODC算法。FLADC算法在擁有較好的節(jié)能效果的同時，兼顧了消息延遲和傳遞概率之間的平衡。機會網(wǎng)絡(luò)中，F(xiàn)LADC算法可以確保一定的消息延時和傳遞成功概率，節(jié)省更多的能量，延長網(wǎng)絡(luò)的生命周期。

圖4 隨著時間的推移消息傳遞過程中平均時延

5 結(jié)束語

在本文中，假設(shè)機會網(wǎng)絡(luò)中任意兩個節(jié)點之間的通信時間間隔服從指數(shù)分布。在給定預(yù)期最大消息時延和消息傳遞概率的條件下，可以計算出一個全局最佳占空因子ΔFLADC。然后根據(jù)ΔFLADC設(shè)計節(jié)點周期性休眠和喚醒的時間，在喚醒時優(yōu)化了消息的轉(zhuǎn)發(fā)策略，在不影響網(wǎng)絡(luò)性能的情況下降低了功耗。最后，實驗結(jié)果表明FLADC是比Epidemic，MSAF和EEAODC算法更高效的算法，可以節(jié)省更多的能量。

在真實場景中，人類之間的接觸時間間隔也可能服從冪律分布[13]，而網(wǎng)絡(luò)的結(jié)構(gòu)往往會更加不均勻。在未來的工作中，可以考慮這些因素，提出更加高效的節(jié)能算法。