移动用户(设备)在2010年达到了50亿的庞大数量.鉴于移动设备的数量和他们都使用电池供电的事实,设计高效的算法来减少设备的能量消耗和合理地使用能量来最大化整个移动网络系统的数据吞吐量受到了广泛的关注.近似算法设计和分析是算法理论方向十分重要的领域和评价算法性能的重要手段.本文从理论分析的角度研究了基于调度和分配策略的算法以最优化能量的使用.本文关注的是计算最优解的算法,以及以近似比作为性能评价的近似算法,分别给出了针对单一设备的最优／近似的能量调度算法和针对移动系统的具有最优在线近似比的能量分配算法.单个设备上的能量优化：针对单一设备,动态电压调节技术提供了调节处理器的速度以控制能量消耗的能力.本文首先研究了理想模型和相对更实际的加速模型和处理器模型.其中理想模型允许处理器瞬间变速而加速模型限制处理器的加速率最大为K,存储器模型则是将存储器操作时间也加以考虑.目标是找到能够在期限时间内完成所有任务的最小化能量消耗的最优调度.本文针对单一设备的研究包括以下结果,(1)改进了理想模型下的最优解计算时间：理想模型的理论研究最早可以追溯到1995年Yao等人的富有启发性的工作,目前为止最好的是0(n2logn)时间算法来计算最优解.我们关注一类称为一致性的任务集合,它们满足更早到达的任务不会更迟结束.基于对最优解结构的更加深入的理解和观察,本文改进了计算最优解所需的时间复杂性,给出了O(n2)时间的新算法.(2)首次从理论分析角度给出了计算加速模型最优解的算法：区别于理想模型,比较实际的考虑时间延迟的模型有加速模型和存储器模型,在此之前只有一些启发式算法的研究,而没有关于它们的比较理论的研究.对于加速模型,我们从所有任务都有共同到达时间的特例开始研究,设计针对它的算法并将其作为一个子程序,来确立加速模型下的最优解.本文首次给出了计算其最优解的算法,算法时间上只需用O(n2)时间.(3)解决了处理器模型的复杂性和额外资源条件下的近似算法：本文证明了处理器模型的最优解计算问题是NP难解性.鉴于难解性的结果,之后从近似算法的角度,本文给出了s-倍额外速度条件下的具有常数近似比的算法.这个结果说明了用多项式时间的算法能够常数近似于需要指数计算时间的最优算法.系统层面上的能量分配：以上的内容都是从设备上的能量优化的角度进行研究,之后本文关注系统层面(移动网络)的能量分配问题.受限于设备有限的能量和一些其它物理限制,总体的目标是最大化整个系统的数据吞吐量.模型综合考虑了系统中变化的信道状态,有限的能量和用户之间的干扰这些物理限制.同时,考虑系统的开放性和用户之间的竞争行为,用户可能通过欺骗私有数据信息的方式来最大化自己的收益,以至对系统的性能产生不利影响.方法是使用博弈论中的机制设计理论来抑制用户使其没有对系统进行欺骗的动力(truthful mechanism design),使用在线的竞争比分析(competitive analysis)来证实系统的总体性能不会受到太大影响.关于系统层面的能量优化研究包括以下结果,(1)设计出了能抑制用户欺骗行为的机制：本文设计出了一个随机的机制,证明了它可以保证用户没有进行欺骗的动力,即满足truthful的要求.(2)改进了目前关于任意算法所能达到的性能下界：关于任意算法所能达到的最好性能,目前只有关于确定性算法的性能下界,本文改进了目前为止为好的关于下界的结果,证明所有随机算法最好只能达到Ω(logH/h)－近似,这里使用到的是Yao的极大极小原理.(3)证明本文所设计的机制是最优近似的：即机制在系统的总数据吞吐量评价上是O(logH/h)-近似的.这个结果也从性能评价上证明该机制不仅能应对用户的自私的竞争行为,同时在系统的总体收益上能达到最佳性能(aysymptotic optimal competitive).鉴于近似比分析是以最坏情况的算法性能作为评价手段,这个结果说明不存在其它算法能够在最坏情况的表现上大幅改进本文所设计的算法和机制.