基于低占空因子休眠和有效度轉(zhuǎn)發(fā)的節(jié)能算法

鄭永剛，孫文勝

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

0 引 言

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 FLADC算法

2.1 主要符號(hào)的含義

FLADC算法中用到的主要符號(hào)，其詳細(xì)描述見表1。

2.2 求解最佳的占空因子

節(jié)點(diǎn)通信的時(shí)間間隔表示在機(jī)會(huì)網(wǎng)絡(luò)當(dāng)中兩個(gè)移動(dòng)節(jié)點(diǎn)成功連接并通信到下一次接觸并成功傳遞消息的時(shí)間間隔。

表1 符號(hào)描述

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

(1)

(2)

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

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

(3)

證明：

由式(2)可以得出

(4)

由式(1)可以得出

(5)

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

(6)

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

(7)

由P{DΔ

(8)

即可得式(9)

(9)

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

H≈logN/log(psN)

(10)

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

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

證畢。

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

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

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

(11)

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

(12)

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

(13)

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

(14)

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

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

(15)

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

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

QVi=FVi×Fcon

(16)

3 FLADC算法的提出與實(shí)施

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

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

圖1 FLADC算法的具體流程

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

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

在實(shí)驗(yàn)過程中，將FLADC與EEAODC，MSAF以及Epdemic算法進(jìn)行對比。

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

表2 實(shí)驗(yàn)所需參數(shù)

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

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

4.2 剩余能量的分析與比較

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

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

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

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

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

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

4.4 消息時(shí)延的分析與比較

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

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

5 結(jié)束語

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

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