適合無線傳感器網絡的自適應動態電壓調節算法

(湖南大學 計算機與通信學院， 長沙 410082)



摘 要：

對于能量有限的傳感器網絡，在計算復雜度較高的應用中，節省CPU的能耗具有重要意義。針對以事件為驅動的無線傳感器網絡的任務模式，提出一種基于零散任務模型的自適應DVS算法——ADVS。ADVS算法根據CPU的任務量實時調整工作頻率和電壓，能在很大程度上降低CPU能耗的同時，保證任務的實時性要求。理論分析和實驗結果表明，ADVS算法的實際節能效果接近理論分析值的80%左右，可在很大程度上延長節點的生命周期。

關鍵詞：無線傳感器網絡; 動態電壓調節算法； 自適應； 能量有效性

中圖分類號：TP212.5 文獻標志碼：A

文章編號：10013695(2008)12380004



Adaptive dynamic voltage scaling algorithm for wireless sensor networks



ZHANG Chenggang， XU Cheng

(College of Computer Communication， Hunan University， Changsha 410082， China)



Abstract:It is significant to lower energy consumption from CPU for applications with high computing cost in energyconstrained wireless sensor networks. This paper proposed a scattered task model based adaptive DVS (dynamic voltage scaling) algorithm， ADVS， in the presence of the task characteristic in eventdriven wireless sensor networks. ADVS algorithm could scale the working frequency and voltage dynamically according to the workload. As a result， it could decrease the CPU energy consumption meanwhile meeting the realtime requirements of tasks. Theoretical and experimental results show that the ADVS algorithm can achieve 80% or so theoretical energy savings so that prolong the lifetime of sensor nodes.

Key words：wireless sensor networks; dynamic voltage scaling algorithm; adaptive; energy efficiency



0 引言

無線傳感器網絡的廣泛應用前景，如戰場監視、環境和交通監測、災難救助等，吸引了眾多研究者進行研究^[1~4]。由于節點的能量有限，節約能耗通常成為無線傳感器網絡設計的首要目標。針對計算復雜度較高的應用(如戰場監視中的圖像采集與傳輸)，研究如何節約CPU的能耗，對于降低系統整體能耗，延長網絡生存周期，具有重要意義。

盡管針對無線傳感器網絡的能量有效性方面的研究比較多，如MAC協議和各種喚醒/睡眠調度算法等^[5~9]。但主要是集中研究如何調度射頻模塊，使節點處于休眠狀態，從而到達節能的目的。而目前針對節點CPU的節能機制的研究國內外尚不多見^[10~13]。動態電壓調節技術(dynamic voltage scaling， DVS)可以通過實時調整CPU正常工作時的電壓和頻率，從而在滿足實時性要求的前提下，降低系統無用能耗，盡可能提高能量有效性^[14，15]。

而文獻[10~13]的方法主要是采用傳統DVS方法，對CPU的任務量進行預測，然后進行相應的頻率和電壓調整。與之不同，本文針對具有較高計算復雜度的應用，提出一種適合無線傳感器網絡的自適應的DVS算法——ADVS(adaptiveDVS)，以降低CPU的能耗。該算法首先將無線傳感器網絡中節點以事件為驅動的工作模式歸結為實時系統中的零散任務模型^[16]，然后結合EDF調度算法^[17]，根據CPU的工作負載，由頻率調節因子α對CPU進行實時電壓和頻率調節。理論分析證明ADVS算法能在降低能耗的同時保證任務的實時性要求。最后，基于IMOTE2(www.xbow.com.cn/wsn/pdf/IMote2.pdf)節點的XSCALE處理器的性能參數對ADVS算法進行模擬實驗。實驗結果表明，模擬結果獲得的節能效果基本接近理論分析值的80%左右。

1 問題描述

在計算復雜度較高的應用中(如目標監控、災難分析報警)，CPU的開銷往往不可忽略^[18]，且系統具有一定的實時性要求。基于事件驅動的無線傳感器網絡往往在事件發生時有大量任務要處理，而在其他時間段CPU存在較多的空余時間。本文將這種任務模式歸結為零散任務模型^[16]。其中，任務(task)表示一段具體的執行代碼，每個任務的一次具體執行稱為工作(job)。設零散任務集合T={T1，T2，…，Tn}中的單個任務具有三個屬性：p表示同一個任務的兩次連續工作的最小時間間隔；e表示一次工作的最差執行時間，通常p>e；d表示一次工作的最長期限，本文設d=p。因此，任務Ti可用(p， e)來表示。在以上模式中，當CPU工作在高頻率時，由于單個任務通常存在松弛時間(如某任務要求在(0，t1)內完成，但在較高頻率下，任務在t2即可完成(t2

本文研究適合傳感器網絡工作模式的DVS技術，通過適當延長處理時間，在保證實時性要求的前提下，控制CPU工作電壓和頻率來提高能量有效性。

2 ADVS算法

本文提出的ADVS算法屬于任務間的調度算法，基于單個工作進行CPU的電壓和頻率調整。由于頻率和電壓成正比，ADVS算法通過頻率來表示電壓的調整。

定義 1 頻率調節因子α定義為當前調整的頻率與CPU最大頻率的比值，α=fnew/fmax ，則α≤1。

定義 2 空閑狀態下的調節因子αidle，表示無工作狀態下的調節因子的最小值。實際中，由于需要支持節點的喚醒和一些時間操作，節點的CPU頻率不可能為0。為便于分析，本文假設αidle→0。此條件將在實驗中去除。

定義 3 延遲的任務集合TD，定義為任務集T={T1，T2，…，Tn}的一個子集，該子集中的任務的最后一次工作至少在pi前發生，即在任何時間t，TD={Ti|Ti∈T∧(t≥ri+pi)}。其中：ri為任務Ti的最后一次工作的發生時間，或當Ti從未發生時為- ∞。

定義 4 CPU的利用率定義為U=∑ni=1ei/pi。

ADVS的核心思想是：根據工作負載，通過頻率調節因子α對CPU頻率和電壓進行自適應調整。ADVS算法的詳細描述如圖1所示。初始狀態下，設定TD=T，且CPU頻率設為αidle。當某個任務Ti的工作發生時，ADVS提高α為(α+e/pi)，并將Ti從TD刪除；若任務Ti在最小發生間隔pi結束時沒有工作發生，則ADVS將降低α為(α-ei/pi)，并將Ti添加到TD。若當前沒有工作執行，則設α=αidle，即CPU轉入睡眠或空閑狀態。ADVS算法如下：

Algorithm: ADVS()

set α←αidle; TD←T

while (true){

sleep when (no task is executing)

if (a job of Ti occurs and T∈TD) then

α←α+ei/pi; TD←TD-{Ti}

else if (TiTD and curent_time≥ri+pi)

α←α-ei/pi; TD←TD+{Ti}

else

α←αidle; TD←T}



因此，ADVS算法中的調節因子α的值依賴于前一次的值。由于α隨時間變化，設αn表示第n次調整后的α值。下式表示αn與時間t的關系。

αn=αidle， t=0 or no taks is executing

αn-1-ei/pi， t≥ri+pi and Ti TD

αn-1+ei/pi， a job of Ti occurs at t and Ti∈TD

no change， otherwise

(1)



下面舉例說明ADVS算法如何與EDF調度算法相結合。EDF(earliest deadline first)算法的主要原理是讓完成期限最早的任務最先運行。

考慮任務集T1=(4，1)，T2=(5，1)，T1=(10，3)，則未使用ADVS算法前的CPU利用率U=0.75。若僅使用EDF對任務進行調度時的任務運行情況如圖2所示。設α=1，用J(i， j)表示任務Ti的第j個工作。其中：T1在時間點(0， 4， 10)執行；T2在時間點(0， 6， 11)執行；T3在時間點8執行。從圖1可以發現，不少任務均存在一定的松弛時間。其中，在[2， 4)、 [5， 6)、 [7， 8)三個時間段，CPU處于空閑狀態。

當使用ADVS算法時，各個任務的執行時間段將發生改變。表1詳細列出了分別在未使用和使用ADVS情況下的任務的執行情況。表1中ri，j表示工作的發生時間，Di，j表示工作的最晚完成期限。未使用ADVS算法時，CPU處于滿負荷工作狀態，即α=1，但是CPU存在空閑時間。而當使用ADVS算法時，α最大值為0.75，但所有任務仍然均能在完成期限之前完成(這將在下一節進行證明)。表1中用黑體表示的為頻率調節因子α發生改變的時間點。α均在每個時間段開始時變化，即當某個工作的期限到來或新的工作發生時。而在時間點4時，由于既有新的工作J(1，2)發生，又有J(1，1)的期限到達，故α的值不變。同樣，時間點11時，既有J(2，3)發生又有J(2，2)到期。此外，根據EDF算法，由于工作J(3，1)期限比在時間點10發生的J(3，1)的期限要晚，故在時間點10被打斷。

根據表1，得到最后的ADVS算法調整后的任務執行情況，如圖2所示。可以發現此時的CPU利用率為1，任務集在[0， 17.987)內全部完成。

表 1 未使用和使用ADVS算法時的任務執行情況對比

工作ri，jDi，j

EDF

時間段α工作量/%

EDF ADVS

時間段α工作量/%

J(1，1)04[0， 1)1100[0， 2.22)0.45100

J(2，1)05[1， 3)1100[2.22， 4.44)0.45100

J(1，2)48[4， 5)1100[4.44， 5)0.4525.2

[5， 6)0.2525

[6， 7.11)0.4549.8

J(2，2)611[6， 7)1100[7.11， 8)0.4540

[8， 9.2)0.560

J(3，1)818[8， 10)166.67[9.2， 10)0.513.33

[12，13)133.33[12.66，14)0.7533.5

[14，16)0.533.3

[16，17.987)0.319.87

J(1，3)1014[10，11)1100[10，11.33)0.75100

J(2，3)1116[11，12)1100[11.33，12.66)0.75100

3 算法性能分析

3. 1 實時性分析 

雖然ADVS算法調整了任務的執行時間，但其仍然能保證各個任務的實時性要求，在期限前完成任務。本節在證明實時性之前給出相關的定義。

定義 5 調節執行時間esi定義為使用ADVS算法時，調節因子為α時任務Ti實際執行時間。在α為固定常量的任意時間段內，任務Ti的調節執行時間為esi=ei/α。

定義 6 調節利用率Usψ定義為α為固定常量的任意時間段ψ內的CPU實際利用率，Usψ=∑ni=1，TiTDesi/pi。

定義 7 調節因子穩定間隔ψi定義為兩個連續的不同調節因子αi與αi+1之間的時間段。

引理 1 若U=∑ni=1ei/pi≤1，當使用ADVS算法時，若任意任務Ti均以最大頻率發生，即發生間隔為pi，則Usψ≡1。

證明 設ψs={ψ1，ψ2，…，ψm}為上次空閑結束到下一次CPU空閑時間段內的所有調節因子穩定間隔的集合。若沒有空閑時間，則ψs為所有任務的執行時間之和，并設αs={α1，α2，…，αm}為ψs中相應穩定間隔對應的調節因子的集合。則穩定間隔ψj (1≤j≤m)期間，Usψj=∑ni=1，TiTDesi/pi。其中：esi=ei/αsj，根據算法本身的性質，αsj=∑ni=1，TiTDei/pi。代入Usψj可得Usψj=∑ni=1，TiTDesi/pi=∑ni=1，TiTDei/αsjpi=1/αsj∑ni=1，TiTDesi/pi=1，進而在整個ψs階段的CPU調整利用率為

Usψ=∑mj=1ψsj/∑mj=1ψsj#8226;Usψj=1/∑mj=1ψsj∑mj=1ψsj#8226;Usψj(所以USψj=1)≡1





引理1解析圖2中為何沒有CPU空閑的原因，直觀上，U=∑ni=1ei/pi≤1是保證ADVS可行性的充要條件，但在證明之前，下面還需要引入新的定義。

定義 8 未發生的工作集合Wψ包含時間段ψ內的所有在最小發生時間間隔pi內一直沒有發生的所有任務的工作。

引理 2 設T={T1，T2，…，Tn}為滿足pi=di的零散任務集合；設J={J(1，1)，J(1，2)，…，J(1，m1)，…，J(n，1)，J(n，2)，…，J(n，mn)}為在時間段ψ內發生的工作集合；設Δδ={δ(1，0)，δ(1，1)，…，δ(1，m1)，…，δ(n，0)，δ(n，1)，…，δ(n，mn)}為時間段ψ內相應的兩個連續的工作發生時間間隔的集合，δ(i，j)=ri，j+1-ri，j，δ(i，j)≥pi;δ(i，0)對應時間段ψ開始時刻與發生時的時間段，δ(i，mi)對應J(i，mi)發生時刻與時間段ψ結束時的時間段。時間段ψ內未發生工作數量為

|Wφ|=∑ni=1∑mij=0(「δ(i，j)/pi-1)

(2)



證明 考慮開放時間邊界，任務Ti在δ(i，j)內未發生的工作數量為(「δ(i，j)/pi-1)，故所有任務在時間段ψ內的未發生工作數量如式(2)所示。

定義 9 時間段[t1，t2)的CPU有效工作量ρ定義為ρ=α(t2-t1)。其中：α在[t1，t2)內為固定常量。

定義10 任務Ti(pi，ei)的一個頻率調整持續時間，ω定義為時間段[t1，t2)，t1時由于Ti的一個工作使得CPU頻率升高ei/pi，t2時因未發生Ti的工作CPU頻率降低ei/pi。

引理3 根據定義10，設Ti (pi，ei)的工作J(i，j)發生在t0，此時α增加ei/pi。若其連續以最小間隔產生工作直到t1發生J(i，j+k)；t2時無Ti的工作發生，α減少 ei/pi。易知(t1-t0)為pi的整數倍，且(t2-t1)=pi，故頻率調整持續時間ω=Mi×pi，Mi為工作發生次數。根據引理2，時間段ψ內Ti發生的工作數為

Mi=Ti工作發生量大值-未發生工作數=

[ψ/pi]-∑mij=0(「δ(i，j)/pi-1)

(3)



設ψs={ψ1，ψ2，…，ψm}為某時間段ψ內的穩定間隔集合。αs={α1，α2，…，αm}為ψs相應穩定間隔對應的調節因子的集合。Δω={ω(1，0)， ω(1，1)，…，ω(1，k1)，…， ω(n，0)， ω(n，1)，…，ω(n，kn)}為各個任務相應的頻率調整持續時間集合，ω(i，j)表示任務Ti的第j個頻率調整持續時間。根據引理4可以推出ρ表示如式(4)所示。其中：Δαi，j表示J(i，j)引起的α增值。 

 ρ=∑mi=1αiψi=∑ni=1∑kij=1Δαi，jω(i，j)=

∑ni=1ei/pi∑kij=1ω(i，j)=∑niei/pi#8226;Mi#8226;pi=

∑niMiei=∑ni=1(「ψ/pi-∑mij=0(「δ(i，j)/pi-1))ei

(4)



定理1 設T={T1，T2，…，Tn}為滿足pi=di的零散任務集合，當且僅當U=ni=1ei/pi≤1，基于EDF算法，ADVS算法將保證任務的實時性要求。

證明 首先考慮必要性，即當U>1時，根據文獻[17]，EDF將不具有可行性，故ADVS算法無法與EDF結合。然后證明充分性，假設U≤1時，時間段[t0，t1)內基于EDF的ADVS算法對任務進行調整，t0為CPU最后一次空閑時段的結束，存在工作J(i，j)未在其任務期限t1前完成任務。設時間段ψ內的需要完成的工作量為ρ*。因J(i，j)未在期限td前完成，根據式(4)可得

ρ*=∑ni=1((t1-t0)/pi」-∑mij=0（「δ(i，j)/pi-1))ei





設正常完成時的有效工作量為ρ，則

ρ＜ρ*

∑ni=1(「(t1-t0)/pi-∑mij=0(「δ(i，j)/pi-1))ei＜

∑ni=1((t1-t0)/pi」-∑mij=0(「δ(i，j)/pi-1))ei

0＜∑ni=1((t1-t0)/pi」-「(t1-t0)/pi)





由于x∈R，x>0，x」-「x≤0，上式不成立，則不存在未在期限t1前完成的工作J(i，j)。因此ADVS算法可保證所有工作均在期限前完成。

3. 2 節能效果 

根據CMOS芯片的能耗模型^[19]，CPU功率為

PCMOS=C0V2f

(5)

其中：C0為常數；V為電壓。單個操作能耗為E=C1V2，且頻率為

f=(V-Vt)/(C2V)

(6)



其中：C1 和C2為由物理設備決定的常量；Vt為電壓門限值(V>Vt)。若任務Ti有μi個操作要完成，根據f=μi/ui，ui為處理時間，則任務Ti所需的能耗為

θi(ui)=μiE=μiC1V2=μiC1(Vtui/（ui-μiC2）)2

(7)



可見當ui>μiC2時，θi(ui)隨著處理時間ui單調遞減。由于ADVS算法延長了單個任務的執行時間，并相應降低了電壓，故降低了單個任務的能耗。下文進行具體分析。

設在長度為ψ的時間段[t0，t1)內，ADVS算法在t1完成所有任務(則不使用ADVS算法時CPU可在t1前完成所有任務)，設ψs={ψ1，ψ2，…，ψm}為該時間段內的穩定間隔集合。αs={α1，α2，…，αm}為ψs中相應穩定間隔對應的調節因子的集合。設未使用和使用ADVS算法時的CPU能耗分別為Emax、EADVS，則有

Emax=Pmax(t1-t0)， EADVS=∑mi=1Pi×ψi

(8)



其中：Pi表示時間段ψi的功率。與α相對應，設電壓調節因子β=V/Vmax，可由式(6)得出

α=(βVmax-Vt)/(β(Vmax-Vt))

(9)



設βs={β1，β2，…，βm}為相應的電壓調節因子集合。結合式(5)，故ADVS算法的規則化后的能量節省率為

λ=（Emax-EADVS）/Emax=（Pmaxψ-∑mi=1Pi#8226;ψi）/Pmaxψ=

[ψC0fmaxV2max-∑mi=1C0αifmax(βiVmax)2#8226;ψi]/ψC0fmaxV2max=(10)

1-1/ψ∑mi=1αiβ2iψi





4 實驗與評估

本文基于OMNET++^[20]模擬ADVS和EDF算法。模擬程序主要包括CPU時鐘發生模塊、任務調度模塊和能耗統計模塊。實驗參數參照IMOTE2節點的PXA271 XScale處理器。工作頻率為13~416 MHz，最低工作電壓為0.85 V，即αidle=αmin=13/416=0.031。實驗模擬監控應用，所定義的零散任務集合為T={T1(采樣)，T2(目標確認)，T3(事件觸發)，T4(接收消息)，T5(數據融合)，T6(發送消息)}。各任務具體的信息如表2所示。其中t表示所模擬的單位時間。由表2可見Umax=0.380 8<1，故ADVS算法是可行的。實驗過程中，模擬隨機的事件，然后依次觸發相應的任務。每次實驗進行五次，取平均值為最后結果。

圖4(a)(b)分別顯示了模擬500和1 000個事件時的節能效果。X軸表示CPU相對利用率=(CPU實際利用率平均值)/Umax，Y軸表示規則化的節能效果。理論分析值由式(10)求出，ψ為10個任務完成時間。實際結果與理論分析值有一定的差異，實際結果接近理論分析的80%左右。其主要原因是CPU頻率調整本身需要消耗少量的能量，且αidle≠0。圖4(b)中ADVS的節能效果比(a)好，這是由于模擬的任務比較多，ADVS的優勢越明顯的原因。總體上ADVS算法的節能效果約在40%~82%，很大程度上降低了系統能耗。

表2 任務詳細屬性

任務pieiei/pi

T17.25t0.1t0.013 8

T27.25t1t0.138

T37.25t0.26t0.036

T43×7.25t1.5t0.069

T52×7.25t0.8t0.055

T63×7.25t1.5t0.069

5 結束語

本文根據無線傳感器網絡的特性，針對計算復雜度較高的應用，提出一種自適應的DVS算法ADVS。ADVS能在很大程度降低CPU能耗的同時，保證任務的實時性要求。下一步的工作將在實際節點IMOTE2上進行ADVS算法實現。

參考文獻：

［1］AKVILDIZ I F. Wireless sensor networks: a survey[J]. Computer Networks， 2002，38(4): 393422.

［2］任豐原，黃海寧，林闖.無線傳感器網絡[J].軟件學報， 2003，14(7):12821291.

［3］李建中，李金寶，石勝飛.傳感器網絡及其數據管理的概念、問題與進展[J].軟件學報， 2003，14(10):17171727.

［4］崔莉，鞠海玲，苗勇，等.無線傳感器網絡研究進展[J].計算機研究與發展， 2005，42(1):163174.

［5］YE W， HEIDEMANN J， ESTRIN D. Medium access control with coordinated adaptive sleeping for wireless sensor networks[J]. IEEE/ACM Trans on Networking， 2004，12(3): 493506.

［6］DAM T V， LANGENDOEN K. An adaptive energyefficient MAC protocol for wireless sensor networks[C]//Proc of ACM SenSys2003. Los Angeles: [s.n.]，2003:6572.

［7］POLASTRE J， HILL J， CULLER D. Versatile low power media access for wireless sensor networks[C]//Proc of ACM SenSys2004. Baltimore: [s.n.]， 2004:95107.

［8］ZHENG T， RADHAKRISHNAM S， SARANGAN V. PMAC: an adaptive energyefficient MAC protocol for wireless sensor networks[C]//Proc of IPDPS. Denver: [s.n.]，2005.

［9］YE W， SILVA F， HEIDEMANN J. UltraLow duty cycle MAC with scheduled channel polling[C]//Proc of ACM SenSys2006.Boulder: [s.n.]，2006:321334.

［10］SINHA A， CHANDRAKASAN A. Dynamic power management in wireless sensor networks[J]. IEEE Design Test of Computers， 2001，18(2):6274.

［11］MIN R， FURRER T， CHANDRAKASAN A. Dynamic voltage scaling techniques for distributed microsensor networks[C]//Proc of VLSI2000. Orlando: [s.n.]， 2000:4346.

［12］陳歡，陳向東，胡黎黎，等.基于小波的DVS在無線傳感器網絡中的應用[J].計算機應用研究， 2007，24(8):262263.

［13］田豐民，陳向東，張傳武.無線傳感器網絡動態功率管理方法[J].傳感器技術， 2005，24(11): 3335.

［14］HONG D K， QU G， POTKONJAK M， et al. Power optimization of variablevoltage corebased systems[C]//Proc of IEEE ComputerAided Design.[S.l.]: IEEE Press， 1999:17021714.

［15］ZHANG F， CHANSON S T. Processor voltage scheduling for realtime tasks with nonpreemptable sections[C]//Proc of the 23rd IEEE International Realtime Systems Symposium. Austin : [s.n.]， 2002:235245.

［16］MOK A K. Fundamental design problems of distributed systems for the hard realtime environment[D]. Massachusetts: [s.n.]， 1983.

［17］LIU C， LAVLAND J. Scheduling algorithms for multiprogramming in a hard realtime environment[J]. Journal of the ACM， 1973，20(1):4661.

［18］LUO H， LIU Y， DAS S. Routing correlated data with fusion cost in wireless sensor networks[J]. IEEE Trans on Mobile Computing， 2006，5(11):16201632.

［19］ISHILHARA T， YASUURA H. Voltage scheduling problem for dynamically variable voltage processors[C]//Proc of International Symposium on Low Power Electronics and Design. 1998:197202.

［20］VARGA A. The OMNeT++ discrete event simulation system[C]//Proc of European Simulation Multiconference. Prague:[s.n.]， 2001:319324.