臺灣博碩士論文加值系統

在這個能源瀕臨短缺的時代，節約能源是人類科技發展首要的考量。本論文主要在探討Ad-hoc網路能量效益最佳化，根據跨層最佳化的概念考慮使用者間的流量分配、時間排程與傳輸功率控制等問題來規劃能量效益問題。接著透過RLT、熵正則化演算法(IER)與Dinkelbach演算法將Nonlinear programming的能量效益問題放鬆後再分別使用Branch-and-bound與Electromagnetism-like method來得到最佳的網路資源分配，此外本論文中還透過加入一些限制式來限制能量效益的變化與平衡的資源分配來使我們的網路系統更加穩定。

Energy conservation is the primary consideration for human technological development. In this paper, we investigate the Ad-hoc network energy efficiency based on the concept of cross-layer optimization. We consider the distribution of traffic、time scheduling and transmitting power control between users to planning energy efficiency. Then we design the solution procedure by the Branch-and-bound and Electromagnetism-like method. We also use Reformulation-Linearization Technique、IER and Dinkelbach-type algorithm to solve the NP-complete problem.

第一章　簡介 1
第二章　網路架構與限制條件 3
2.1 Ad-hoc網路系統 3
2.2 限制條件 4
2.2.1 排程 6
2.2.2 功率控制 7
2.2.3 路由 8
2.3 能量效益問題 9
2.4 簡化能量效益問題 11
2.4.1 使用自干擾取代0-1整數變數 11
2.4.2 移除對數項 13
2.4.3 能量效益問題形式 14
第三章 分枝定限法求解程序 16
3.1 分枝定限法框架 16
3.2 線性放鬆 21
3.2.1 重新線性化技術(Reformulation Linear Technique) 21
3.2.2 線性分數規劃(Linear Fractional Programming) 23
3.2.3 找尋初始點 27
3.3 Feasibility Pump演算法 27
3.4 切割問題 29
第四章 EM-method求解程序 32
4.1 EM-method隨機演算法 33
4.1.1 EM-method隨機演算法基本原理與求解程序 33
4.1.2 使用EM-method隨機演算法解Sum-of-ratio問題演算法 34
4.2 懲罰函數(Penalty function) 37
第五章 模擬結果 39
5.1 分枝定限法求解程序模擬結果 39
5.2 EM-method求解程序模擬結果 43
第六章 結論 48
參考文獻 48
附錄 51

[1] R. M. et al. Cross-layer design for lifetime maximization in interference-limited wireless sensor networks. EEE Infocom, 2005.
[2] M. L. Sichitiu. Cross-layer scheduling for power efficiency in wireless sensor networks. IEEE Infocom, 2004.
[3] M. Chiang. To layer or not to layer: Balancing transport and physical layers in wireless multihop networks. IEEE Infocom,4, 2004.
[4] L. Bui, A. Erylmaz, and R. Srikant. Joint asynchronous congestion control and distributed scheduling for multi-hop wireless networks. Department of Electrical and Computer Engineering.
[5] L. Chen, S. H. Low, M. Chiang, and J. C. Doyle. Optimal cross-layer congestion control, routing and scheduling design in ad hoc wireless network.In:25th IEEE International Conference on Computer Communications. IEEE INFOCOM Series . IEEE , Piscataway, NJ, pp. 676-688.
[6] B. Johansson, P. Soldati, and M. Johansson. Mathematical decomposition techniques for distributed cross-layer optimization of data networks. IEEE Journal on Selected Areas in Communications, 24(8):1535-1547, 2006.
[7] M. Johansson and L. Xiao. Cross-layer optimization of wireless networks using nonlinear column generation. IEEE Transactions on Wireless Communications, 5(2):435-445, 2006.
[8] S.J. Kim, X. Wang, and M. Madihian. Cross-layer design of wireless multihop backhaul networks with multiantenna beamforming.IEEE Trans. Mob. Comput, 6(11):1259-1269, 2007.
[9] J. Papandriopoulos, S. Dey, and J. Evans. Optimal and distributed protocols for cross-layer design of physical and transport layers in manets. IEEE Trans. on Networking, 16(6):1392-1405, 2008.
[10] Yi Shi,Y. Thomas Hou, Hanif D. Sherali. Cross-Layer Optimization for Data Rate Utility Problem in UWB-Based Ad Hoc Networks. IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 7, NO.6, JUNE 2008.
[11] Yi Shi,Y. Thomas Hou, Sastry Kompella, Hanif D.Sherali. Maximizing Capacity in Multi-Hop Cognitive Radio Networks under the SINR Model.IEEE Transactions on Mobile Computing. VOL. 10, NO. X, XXXXXXX 2011
[12] B. Radunovic and J.-Y. Le Boudec,“Optimal Power Control,Scheduling, and Routing in UWB Networks, IEEE J. Selected Areas in Comm., vol.22, no. 7, pp. 1252-1270, Sept. 2004.
[13] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, pp. 245-248. W.H. Freeman, 1979.
[14] Yi Shi,Y. Thomas Hou, Sastry Kompella, Hanif D.Sherali. Maximizing Capacity in Multi-Hop Cognitive Radio Networks under the SINR Model.IEEE Transactions on Mobile Computing. VOL. 10, NO. X, XXXXXXX 2011
[15] M. Chiang, C. W. Tan, D. P. Palomar, D. O'Neill, and D. Julian. Power control by geometric programming. IEEE Transactions on Wireless Communications, 6(7):2640-2651, 2007.
[16] Matteo Fischetti, Fred Glover and Andrea Lodi,“The feasibility pump, Math. Program., Ser. A 104, 91–104 ,2005.
[17] H.D. Sherali and W.P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems,chapter 8.Kluwer Academic Publishers, 1999.
[18] Ilker Birbil, S. C. Fang and R.L. Sheu, On the convergence of a population-based global optimization algorithm, Journal of Global Optimization, Vol.30, No.3, 301–318, 2004.
[19] R.L. Sheu,W.I. Wu and Ilker Birbil, Solving the Sum-of-Ratios Problem by Stochastic Search Algorithm, Journal of Global Optimization, Vol. 42, No.1, 91-109, 2008.
[20] Gary G. Yen., An Adaptive Penalty Function for Handling. Constraint in Multi-objective Evolutionary Optimization, E. Mezura-Montes (Ed.): Constraint-Handling in Evolution. Optimi., SCI 198, pp. 121–143, 2009.
[21] Özgür Yeniay and Beytepe, Ankara, Penalty function methods for constrained optimization with genetic algorithms, Mathematical and Computational Applications, Vol. 10, No. 1, pp. 45-56, 2005.