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

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

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

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

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

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

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

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