??? 摘 要： 低功耗的設(shè)計已經(jīng)成為嵌入式系統(tǒng)設(shè)計中一個非常重要的方面，而動態(tài)電壓調(diào)度算法DVS又被認為是降低功耗的一種有效手段。分析了已有的基于電池剩余電量的DVS調(diào)度算法局限性，通過實驗對非周期性電流負載" title="電流負載">電流負載對應(yīng)的電池單元行為進行建模，設(shè)計了一種新的低能耗" title="低能耗">低能耗調(diào)度算法。實驗證明該算法能很好滿足復(fù)雜的具有非周期性任務(wù)特點的嵌入式實時系統(tǒng)的性能與低功耗要求。
??? 關(guān)鍵詞： 電池非理想特性；自恢復(fù)效應(yīng)" title="自恢復(fù)效應(yīng)">自恢復(fù)效應(yīng)；DVS算法；非周期性；低功耗
?
??? 能量消耗問題是近幾年在嵌入式系統(tǒng)設(shè)計中被廣為關(guān)注的難點與熱點，它嚴重制約著嵌入式系統(tǒng)的應(yīng)用與發(fā)展[1]。降低能耗、延長電池壽命" title="電池壽命">電池壽命在軍用或民用嵌入式系統(tǒng)中(如傳感網(wǎng)絡(luò)節(jié)點、微小衛(wèi)星、PDA等)具有重要的現(xiàn)實意義。動態(tài)電壓調(diào)節(jié)技術(shù)可以根據(jù)當前運行任務(wù)的需求來實時調(diào)節(jié)處理器工作電壓" title="工作電壓">工作電壓，以達到任務(wù)完成時間和系統(tǒng)能耗之間的平衡，因而被廣泛應(yīng)用在嵌入式實時系統(tǒng)中。傳統(tǒng)DVS(Dynamic Voltage Scaling)算法（Wiser and Govil[2]）多是基于最優(yōu)化的電池單元模型，而沒有試圖對電池的理化現(xiàn)象精確建模。實際上不同的電流負載對應(yīng)的電池單元行為不同，對不同情況下電池單元行為進行精確建模能提高電池利用率，延長其壽命，故進一步研究與電池特性相關(guān)的DVS策略非常有意義。
1 基于電池特性DVS算法本質(zhì)
??? DVS策略主要基于一個事實，即：處理器的確定性能量消耗與工作電壓呈平方正比的關(guān)系[3]：
??? 
?
??? C為工作電源電壓，V為每周期的平均開關(guān)電容，f 為時鐘頻率，Vbs為襯底和源極之間的電壓，Ij為節(jié)點漏電，K0、K1、K2均為常數(shù)。故在保證性能前提下，可根據(jù)系統(tǒng)工作狀態(tài)動態(tài)調(diào)整電壓達到降低能耗的目的。基于電池特性的DVS算法不僅根據(jù)系統(tǒng)工作狀態(tài)來動態(tài)調(diào)節(jié)電壓，而且還以電池特性為基礎(chǔ)設(shè)計調(diào)度策略，以對電池合理利用，進一步延長電池壽命。Luo[4]等人研究提出的DVS策略通過降低電池的峰值功率來優(yōu)化能量消耗；Rakhmatov[5]提議利用電池自恢復(fù)效應(yīng)增加電容以節(jié)省能量等，這些都是基于電池特性的研究成果并取得較好的節(jié)能效果。
2 已有的基于電池剩余能量的DVS算法局限性
??? 在Sukwon Choia[6]等人提出的一種基于電池剩余能量的可選擇DVS策略中，對周期性電流負載對應(yīng)的電池單元行為建模，并根據(jù)自恢復(fù)效應(yīng)影響因子的強弱將電池放電過程分為三個不同的階段，在不同階段提供不同的策略起到了降低功耗的作用。但其存在下列缺點：
??? (1)建立的電池單元行為模型有一定局限性，只符合周期性電流負載的特點；而更為普遍的具有非周期性電流負載對應(yīng)的電池單元行為模型與之存在較大差異，故需要對電池單元行為重新建模。
??? (2)在rate capacity區(qū)域計算Poptimal方法：基于過去周期段處理器利用率和當前時刻預(yù)測利用率來設(shè)定最優(yōu)功率，即：
?????
其中i≥1，P0=Pmax。而對非周期性和隨機任務(wù)，簡單的基于處理器以往利用率的計算模型不能提供最優(yōu)的動態(tài)電壓調(diào)節(jié)方法，需要考慮采取符合隨機任務(wù)特點的新策略。
??? (3)在Alarm 區(qū)域電池進入低電壓報警區(qū)，調(diào)節(jié)功率為Poptimal=Pmin可以降低能耗。但是如果結(jié)合動態(tài)電源管理DPM策略，對系統(tǒng)單元采用合理的休眠/喚醒算法，則能更好地減少不必要的消耗。
3 電池的非理想特性
??? 大多數(shù)有關(guān)低能耗設(shè)計的研究，都將電池隱式認為是一個理想的電荷儲存器，即：存儲某個固定的電荷總量，而且直到電荷全部耗盡時電壓才退出標稱值。然而在實際情況中，電池沒有任何一處接近于理想電荷存儲單元。由于電池的化學特性，電池在滿電荷至臨界低電荷放電期間其放電率受到很多因素的影響。其中最主要的兩個因素是：the rate capacity effect和the recovery effect[7]。the rate capacity effect現(xiàn)象反映了電流負載和電池壽命的非線性反比關(guān)系，而且電池壽命變化率比電流負載變化率要快。這主要是由于電池在生命周期中所能釋放的容量總和與放電電流有關(guān)。因為從能量轉(zhuǎn)換角度看，當電流越大時，電池在將內(nèi)存的化學能轉(zhuǎn)變成電能時的效率越低。電池的這種非線性特征可通過Peukert公式[8]來說明；the recovery effect現(xiàn)象反映了當電池空閑時電池電容有自恢復(fù)效應(yīng)。因為電池在沒有放電時，電極——電解質(zhì)周圍的有效物質(zhì)通過擴散的方法會被重新填充，電池容量會有恢復(fù)現(xiàn)象。若能利用該特性，將有利于降低系統(tǒng)能耗，延長電池壽命。
??? 實驗在IPAQ3600 PDA上運行Linux，并修改Linux內(nèi)核控制硬件來讀取電池剩余電量值。系統(tǒng)預(yù)設(shè)5個任務(wù)，并通過隨機策略調(diào)度其運行來模擬非周性任務(wù)的執(zhí)行，在整個監(jiān)測過程中，系統(tǒng)處于隨機的繁忙和空閑交替狀態(tài)中。實驗數(shù)據(jù)顯示（圖1）：系統(tǒng)工作時間與電池剩余電量值局部呈不規(guī)則曲線狀，但整體上曲線變化有一定規(guī)律，可以分為三個區(qū)域：在Recovery effect段（Lfull～LR）電容恢復(fù)現(xiàn)象明顯，電池部分放電被恢復(fù)效應(yīng)補償，電量下降緩慢;在Rate capacity effect段(LR～Lc)恢復(fù)效應(yīng)減弱補償能力下降，電量下降加快，并與放電時間趨于線性關(guān)系；最后在Alarm段(Lc～Llow)放電行為占主導(dǎo)，電量急速下降。
???????????????????????? 
??? 實驗結(jié)果：周期性電流負載和非周期性電流負載對應(yīng)的電池電量監(jiān)測曲線分別為細線條和粗線條部分?？梢钥吹剑悍侵芷谛噪娏髫撦d對應(yīng)的電池特性曲線仍然分為三個區(qū)域，但是其曲線波動特點很不規(guī)律。階段1：前者曲線波動均勻，后者幅度較大；階段2：前者呈線性下降，后者曲線圍繞前者上下波動；階段3：兩者電量均迅速下降，前者下降平穩(wěn)，后者有平緩部分。且由于任務(wù)的隨機性，后者進入某區(qū)域的時間點相對模糊，其區(qū)域分割點與任務(wù)調(diào)度的隨機過程有關(guān)。同樣都是基于電池特性，但是在相同的特性區(qū)域，對應(yīng)的電流負載特點不同，故在相同的特性區(qū)域應(yīng)采用不同的策略以求低能耗最優(yōu)。
4 基于電池非理想特性的DVS算法
4.1 DVS算法思想
??? 根據(jù)曲線特點分析電池動態(tài)特性，從而設(shè)計合適的策略才是關(guān)鍵：該DVS算法根據(jù)電量余值L作出策略切換。當L∈(Lfull～LR)時，以充分利用電池恢復(fù)效應(yīng)為主；L∈(LR～Lc)時，因L值持續(xù)減少，故在保證系統(tǒng)性能前提下盡量減少放電量；L∈(Lc～Llow)時，電池電量進入低報警區(qū)，系統(tǒng)單元采取關(guān)閉/喚醒的PM策略，需要犧牲部分性能以盡量延長電池壽命(Lfull、LR、Lc、Llow均為電池在某時刻的電量余值）。
4.2 確定電池狀態(tài)
??? 要根據(jù)電池剩余電量進行策略切換，首先要判斷電池狀態(tài)區(qū)間分割點。非周期電流負載對應(yīng)的電池行為模型不像周期性電流負載對應(yīng)的電池行為那么有規(guī)律，所以判斷起來相對復(fù)雜。但共同之處在于：在相同的特性區(qū)域，同時間片能耗與補償能量的大小關(guān)系類似。所以可以將處理器工作時間劃分成若干時間段(如圖2)，task期間在單位時間段內(nèi)任務(wù)的平均能耗量ΔH(式(3))和隨后相鄰的Idle期間單位時間段內(nèi)平均能量補償量ΔB（式(4)），設(shè)ΔM=ΔH+ΔB，若有ΔM≤0現(xiàn)象出現(xiàn)，則電池處于recovery effect區(qū)；若在一定時間內(nèi)持續(xù)ΔM>0，則認為恢復(fù)效應(yīng)開始模糊，電池進入rate capacity區(qū)；若ΔM>0并且數(shù)值明顯增大，則認為電池進入alrm區(qū)。Lmax為電池最大放電量，Li為I時間片時電池剩余電量，兩個值都可通過監(jiān)測獲得。B(Qk)為Qk時能耗量為：
??? 
????????????????????? 
??? 可推得Qi時能耗量：?
??? 
?
??? 在連續(xù)任務(wù)時間段內(nèi)，單位時間片的平均能耗量：?
??? 
????相鄰空閑時間段內(nèi)，單位時間片平均補償能量：?
??? 
4.3 DVS算法設(shè)計
??? 若電池狀態(tài)為系統(tǒng)所知，則系統(tǒng)就可以根據(jù)電池當前狀態(tài)選擇合理的DVS策略。在Recovery effect區(qū)域，應(yīng)考慮充分利用電池的自恢復(fù)效應(yīng)，故可以使處理器Ppower=Pmax，用以縮短任務(wù)執(zhí)行時間，使處理器更多地處于空閑狀態(tài)以最大化恢復(fù)效應(yīng)。在Rate capacity區(qū)，應(yīng)在保證系統(tǒng)性能的同時，以降低任務(wù)執(zhí)行時的電池負載為主。這個求解過程可以轉(zhuǎn)化為一個在相關(guān)限制條件下求目標函數(shù)最值的非線性規(guī)劃問題來解決，最優(yōu)化對象是每個任務(wù)所對應(yīng)的工作電壓，分析過程如下。
??? (1)時序可行性檢測（SFC）
??? 假設(shè)在時刻t，任務(wù)隊列中已經(jīng)有N個被調(diào)度器接收但是還沒有執(zhí)行完畢的瞬態(tài)任務(wù)，記為SQ={Ti(Si，Ei，Di)，1≤i≤N}，參數(shù)依次表示任務(wù)Ti的到達時間、在最高電壓下(即Vmax)的執(zhí)行時間和截止時間。SQ中的各個任務(wù)按照Di的上升趨勢進行排序。LE(Ti，Vi，t)表示任務(wù)Ti在時刻t基于工作電壓Vi所對應(yīng)的剩余執(zhí)行時間。另外假設(shè)Ti(1，…，N)在進入SQ之前都經(jīng)過時序可行性檢測。其主要作用是保證SQ中所有任務(wù)的deadline得到滿足。
??? (2)最優(yōu)化數(shù)學模型。目標函數(shù)式(5)表示任務(wù)隊列中所有任務(wù)執(zhí)行完畢時所消耗的能量，其中P（Ti，Vi）表示任務(wù)Ti在Vi下所對應(yīng)的功耗。三個限制條件分別從執(zhí)行時間和工作電壓上作出限制。由于Ti在進入任務(wù)隊列之前都經(jīng)過了時序可行性檢測，因此該計算模型在式(6)、式(7)、式(8)限制條件下必然能夠得到一組工作電壓的最優(yōu)解，記為OV={OVi，i=1，…，N}，其中OVi代表任務(wù)Ti所對應(yīng)工作電壓。
??? 
?
??? 根據(jù)OV1來執(zhí)行任務(wù)隊列中處于起始位置的任務(wù); 一旦出現(xiàn)新的瞬態(tài)任務(wù)Tnew，且該任務(wù)已通過SFC檢驗時，系統(tǒng)將為SQ重新計算最優(yōu)解OV；而當前任務(wù)執(zhí)行完畢時，其將從任務(wù)隊列中移走并在OV中執(zhí)行OVi->OVi+1的平移操作(i=1，…，N-1)。
??? 在Alarm區(qū)，為了盡可能延長電池壽命，可結(jié)合基于動態(tài)超時的DPM策略，即當電池電壓下降了ΔV(ΔV>0)后進入Alarm區(qū)域時，則在原有超時時限值t0的基礎(chǔ)上進一步降低，從而盡量延長電池的使用時間；反之則恢復(fù)原t0值。
??? 算法實現(xiàn)：
??? SelectiveDVS(Currrent task){
????? Open Dvs Mechanism；Time t0=value；
????? STATUS=Get current battery region information；
????? Switch(STATUS){
????? Case? RECOVERY_REGION：Pi=Pmax
????? Case? RATECAPACITY_REGION：
???????? If(newtask)?? Calculate OV[n]；
???????? else{ExecuteCurrentTask；RemoveCurrentTask；
???????? Vdd=OVnext；Pi=KVdd3；}
????? Case? ALARM_REGION：
???????? Close Dvs Mechanism；
??? Start DynamicTime_outPolicy(t0)；
??? //t0 is first value } }
??????Time t1=t；//Dynamic time value
????? Dynamic time_out policy(t){
?????? ?If(0<=t1<=t){
????????? If(SystemTime>=t1)? Close devices；
? ???? ???? If(tasking)? Sleep devices；
??????? If(battery coulometry down)
??????????? t1--；
??????? else? t1++；}}
5 算法性能實驗分析
??? 實驗分別采取本文設(shè)計的DVS算法、簡單DVS（Pi=Pmin）、無DVS三種策略進行對比，分別稱為算法1、算法2、算法3。如圖3可知：由于在Recovery區(qū)算法1和算法3均設(shè)定Pi=Pmax，故電池行為方式比較接近，算法2由于Pi=Pmin沒有最大化恢復(fù)效應(yīng)，故曲線下降快；在Rate capacity區(qū)，算法1和算法2均考慮以降低電流負載為主，故后者曲線上升靠近前者曲線，而算法3功率仍為Pmax故電量下降較快；在Alarm區(qū)，算法1、算法2均采取了省電策略，故與算法3相比電量下降緩慢，且算法1與算法2相比，采取適當休眠策略要比持續(xù)Pmin節(jié)能效果好。表1為三種策略的效能比較。
???????????????????????? 
?????????????????????? 
??? 基于電池特性的動態(tài)電壓調(diào)節(jié)技術(shù)是降低嵌入式實時系統(tǒng)能耗的有效方法，也是當前研究的熱門。少量系統(tǒng)的任務(wù)具有周期性特點，但更多的還是具有非周期性等隨機特點的任務(wù)系統(tǒng)。本文通過實驗對非周期性電流負載對應(yīng)的電池行為進行分析，并在此基礎(chǔ)上設(shè)計了適合于非周期性任務(wù)系統(tǒng)的策略。結(jié)果表明該算法能有效降低能耗,與無DVS策略相比，電池壽命延長17.3%，性能提高1.2%。該算法對降低非周期性電流負載的系統(tǒng)能耗比較合適，而對于混合型特點任務(wù)系統(tǒng)的低能耗策略還需要進一步研究。DVS技術(shù)在過去十幾年的時間內(nèi)取得了很大的研究成果，系統(tǒng)低功耗設(shè)計領(lǐng)域的研究空間仍然非常巨大。系統(tǒng)層的低能耗設(shè)計以及有關(guān)能耗最優(yōu)化設(shè)計和分析技術(shù)在今后幾年中還將是重要的研究主題。
參考文獻
[1] 許海燕，盧偉，楊晨輝，等.低耗能嵌入式系統(tǒng)的設(shè)計[J].計算機應(yīng)用研究，2002，19(6)：123-124.
[2] WEISER M，WELCH B，DEMERS A，et al.Scheduling for reduced CPU energy.Proceedings of USEN/X Symposium on Operating Systems Design，Monterey，California，United?States，1994.
[3] FLAUTER K，REINHARDT S.Automatic Performance Setting for Dynamic Voltage Scaling[J].Mobile.ComPutingandNetworking，2001：26.
[4] LUO J，NIRAJ J K.Battery-aware static scheduling for distributed realtime embedded systems design.Proceedings of?ACM/IEEE Conference on Design Automation, Las Vegas，Nevada，United States，2001：444-449.
[5] MARTIN T L，BATTERIES B.Power and performance：system issues in CPU speed-setting for mobile computing，Ph.D.thesis，Department of Electrical and Computer Engineering，Carnegie Mellon University，1999.
[6] SukwonChoi，HojungCha，RhanHa.A selective DVS technique based on battery residual Microprocessors and? Microsystems 30，2006：33-42.
[7] BENINI L，CASTELLI G，MACII A.Extending lifetime of?portable systems by battery scheduling.Proceedings of the?Conference on Design，Automation and Test，Munich，Germany，2001：197-203.
[8] CaldariM，ContM，CIPPap，et al.Dynamicpower managementinanAMBA-basedbattery-poweredsystem[C].Electronics，CircuitsandSystems，2002.9thIntationalConfefence.2002，2：525-528.