能量最優(yōu)化問題的算法研究.pdf

1、移動用戶(設(shè)備)在2010年達(dá)到了50億的龐大數(shù)量。鑒于移動設(shè)備的數(shù)量和他們都使用電池供電的事實，設(shè)計高效的算法來減少設(shè)備的能量消耗和合理地使用能量來最大化整個移動網(wǎng)絡(luò)系統(tǒng)的數(shù)據(jù)吞吐量受到了廣泛的關(guān)注。近似算法設(shè)計和分析是算法理論方向十分重要的領(lǐng)域和評價算法性能的重要手段。
　　 本文從理論分析的角度研究了基于調(diào)度和分配策略的算法以最優(yōu)化能量的使用。本文關(guān)注的是計算最優(yōu)解的算法，以及以近似比作為性能評價的近似算法，分別給出了針對

2、單一設(shè)備的最優(yōu)/近似的能量調(diào)度算法和針對移動系統(tǒng)的具有最優(yōu)在線近似比的能量分配算法。
　　 單個設(shè)備上的能量優(yōu)化：針對單一設(shè)備，動態(tài)電壓調(diào)節(jié)技術(shù)提供了調(diào)節(jié)處理器的速度以控制能量消耗的能力。本文首先研究了理想模型和相對更實際的加速模型和處理器模型。其中理想模型允許處理器瞬間變速而加速模型限制處理器的加速率最大為K，存儲器模型則是將存儲器操作時間也加以考慮。目標(biāo)是找到能夠在期限時間內(nèi)完成所有任務(wù)的最小化能量消耗的最優(yōu)調(diào)度。本文針對單

3、一設(shè)備的研究包括以下結(jié)果，
　　 (1)改進(jìn)了理想模型下的最優(yōu)解計算時間：理想模型的理論研究最早可以追溯到1995年Yao等人的富有啟發(fā)性的工作，目前為止最好的是O(n2logn)時間算法來計算最優(yōu)解。我們關(guān)注一類稱為一致性的任務(wù)集合，它們滿足更早到達(dá)的任務(wù)不會更遲結(jié)束。基于對最優(yōu)解結(jié)構(gòu)的更加深入的理解和觀察，本文改進(jìn)了計算最優(yōu)解所需的時間復(fù)雜性，給出了O(n2)時間的新算法。
　　 (2)首次從理論分析角度給出了計算加

4、速模型最優(yōu)解的算法：區(qū)別于理想模型，比較實際的考慮時間延遲的模型有加速模型和存儲器模型，在此之前只有一些啟發(fā)式算法的研究，而沒有關(guān)于它們的比較理論的研究。對于加速模型，我們從所有任務(wù)都有共同到達(dá)時間的特例開始研究，設(shè)計針對它的算法并將其作為一個子程序，來確立加速模型下的最優(yōu)解。本文首次給出了計算其最優(yōu)解的算法，算法時間上只需用O(n2)時間。
　　 (3)解決了處理器模型的復(fù)雜性和額外資源條件下的近似算法：本文證明了處理器模型的

5、最優(yōu)解計算問題是NP難解性。鑒于難解性的結(jié)果，之后從近似算法的角度，本文給出了s—倍額外速度條件下的具有常數(shù)近似比的算法。這個結(jié)果說明了用多項式時間的算法能夠常數(shù)近似于需要指數(shù)計算時間的最優(yōu)算法。
　　 系統(tǒng)層面上的能量分配：以上的內(nèi)容都是從設(shè)備上的能量優(yōu)化的角度進(jìn)行研究，之后本文關(guān)注系統(tǒng)層面(移動網(wǎng)絡(luò))的能量分配問題。受限于設(shè)備有限的能量和一些其它物理限制，總體的目標(biāo)是最大化整個系統(tǒng)的數(shù)據(jù)吞吐量。模型綜合考慮了系統(tǒng)中變化的信道

6、狀態(tài)，有限的能量和用戶之間的干擾這些物理限制。同時，考慮系統(tǒng)的開放性和用戶之間的競爭行為，用戶可能通過欺騙私有數(shù)據(jù)信息的方式來最大化自己的收益，以至對系統(tǒng)的性能產(chǎn)生不利影響。方法是使用博弈論中的機(jī)制設(shè)計理論來抑制用戶使其沒有對系統(tǒng)進(jìn)行欺騙的動力(truthfulmechanism design)，使用在線的競爭比分析(competitive analysis)來證實系統(tǒng)的總體性能不會受到太大影響．關(guān)于系統(tǒng)層面的能量優(yōu)化研究包括以下結(jié)果，

7、
　　 (1)設(shè)計出了能抑制用戶欺騙行為的機(jī)制：本文設(shè)計出了一個隨機(jī)的機(jī)制，證明了它可以保證用戶沒有進(jìn)行欺騙的動力，即滿足truthful的要求。
　　 (2)改進(jìn)了目前關(guān)于任意算法所能達(dá)到的性能下界：關(guān)于任意算法所能達(dá)到的最好性能，目前只有關(guān)于確定性算法的性能下界，本文改進(jìn)了目前為止為好的關(guān)于下界的結(jié)果，證明所有隨機(jī)算法最好只能達(dá)到Ω(logH/h)—近似，這里使用到的是Yao的極大極小原理。
　　 (3)證明