基于低占空因子休眠和有效度轉發的節能算法

鄭永剛，孫文勝

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

0 引 言

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

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

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

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

1 相關工作

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

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

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

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

2 FLADC算法

2.1 主要符號的含義

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

2.2 求解最佳的占空因子

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

表1 符號描述

通過考慮機會網絡當中的所有節點，推導得出一個占空因子。假設Pmin表示消息時延大于dmax的最小概率，則有P{D

(1)

(2)

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

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

(3)

證明：

由式(2)可以得出

(4)

由式(1)可以得出

(5)

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

(6)

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

(7)

由P{DΔ

(8)

即可得式(9)

(9)

由文獻[9]給出的隨機網絡中計算平均路徑長度的方法可得H

H≈logN/log(psN)

(10)

其中，N表示網絡中節點的個數，ps表示在機會網絡中任意兩個節點通信的概率。

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

證畢。

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

2.3 求解節點的有效度

節點Vi的平均消息轉發率Rfwd為

(11)

節點Vi的平均消息刪除率Rdrop為

(12)

節點Vi的緩存占用率Roccupy為

(13)

定義節點屬性FVi函數為[5]

(14)

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

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

(15)

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

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

QVi=FVi×Fcon

(16)

3 FLADC算法的提出與實施

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

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

圖1 FLADC算法的具體流程

4 仿真和結果分析

4.1 實驗設置

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

本文使用的仿真工具ONE[11]是一款專門針對DTN網絡環境開發的仿真平臺，具有面向對象，離散事件驅動、可以模擬真實網絡環境的特點。仿真實驗是使用ONE中的工作日模型來進行的，該移動模型可以很好地模擬人類活動的真實軌跡并且具有可調控、可配置等優點。實驗收集了12小時內360個節點的移動數據。仿真的具體參數設置見表2。

表2 實驗所需參數

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

表3 設備的能耗功率值

4.2 剩余能量的分析與比較

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

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

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

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

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

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

4.4 消息時延的分析與比較

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

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

5 結束語

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

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