在這篇論文中,我們主要針對Ad-hoc無線網路之壅塞控制問題做最佳化的研究與探討。首先,我們根據功率控制和點對點流量分配的問題，將Ad-hoc多重跳躍的跨層資源管理用數學模型表示。接下來，觀察我們所建立的數學模型:在限制式方面，通道容量為一個非凸的限制式；而在目標函數方面，它是一個最大最小分數型規劃問題，這兩個問題是解決此數學模型的困難所在。然而，資源分配的公平性是影響最大最小分數型規劃問題的重點所在。

在這裡，我們應用局部線性逼近法(LLAM)來處裡通道容量的問題，並且運用熵正則化演算法(MDER)來處裡最大最小分數型規劃問題。此外，我們還結合一些重要的限制式來控制壅塞水平的變化及資源分配的公平性，使得整個系統變得更加穩定。

最後，我們將呈現實驗數據來表示網路的壅塞狀況可以被有效的改善。

In this thesis, we focus on the optimal congestion control of the wireless ad-hoc network. First, we formulate the multi-hop cross layer resource management problem by finding the jointly optimal power allocation and end-to-end communication rates of an ad-hoc network. Secondly, by the analysis of the congestion control model, non-convex capacity formulas and the minimax fractional objective are the two major technical difficulties for solving the model. However, the fairness of resource allocation is the key idea for solving the minimax fractional problem.

Our idea is to design a locally linear approach method (LLAM) to approximate the non-convex capacity and apply the modified Dinkelbach entropic regularization (MDER) method to cope with the minimax fractional programming. In addition, by adding some additional constraints, we can control the fairness of resource allocations to achieve steadiness in the entire system.

Finally, our numerical results indicate that the congestion can be relieved efficiently.

[1] A. Auslender. Penalty and barrier mehods: A uni ed framwork. SIAM Journal on optimization,
10:211-230, 1999.
[2] A. Ben-Tal and M. Teboulle. A smoothing technique for nondifferentiable optimization problems.
Lecture Notes in Mathematics, Springer-Verlag, Berlin, Germany, 1405:1-11, 1989.
[3] L. Bui, A. Ery?lmaz, and R. Srikant. Joint asynchronous congestion control and distributed schedul-
ing for multi-hop wireless networks. Department of Electrical and Computer Engineering.
[4] P. L. Chang. A minimax approach to nonlinear programming. Doctoral Dissertation, Department
of Mathematics, University of Washington, 1980.
[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.
[6] M. Chiang. To layer or not to layer: Balancing transport and physical layers in wireless multihop
networks. IEEE Infocom, 4, 2004.
[7] 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.
[8] J. P. Crouzeix, J. A. Ferland, and S. Schaible. Duality in generalized linear fractional programming.
Mathematical programming, 27(3):342-354, 1983.
[9] J. P. Crouzeix, J. A. Ferland, and S. Schaible. An algorithm for generalized fractional programs.
Journal of Optimization Theory and Applications, 50:183-187, 1986.
[10] W. Dinkelbach. On nonlinear fractional programming. Management Science, 13:492-498, 1967.
[11] R. M. et al. Cross-layer design for lifetime maximization in interference-limited wireless sensor
networks. EEE Infocom, 2005.
[12] A. Host-Madsen. On the capacity of wireless relaying. Electrical Engineering.
[13] 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.
[14] 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.
[15] S. S. Ju. Optimal resources allocation for a cognitive network. Master's thesis, NCKU, 2009.
[16] 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.
[17] X. S. Li and S. C. Fang. On the entropic regularization method for solving min-max problems with
applications. Zeischrift fur Operation Research, 46:119-160, 1997.
[18] J. Y. Lin and R. L. Sheu. Modi ed dinkelbach-type algorithm for generalized fractional programs
with in nitely many ratios. Journal of Optimization Theory and Application, 126(2):323-343, 2005.
[19] 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.
[20] M. J. D. Powell. An e cient method for nding the minimum of a function of several variables
without calculating derivatives. The Computer Journal, 7:155-162, 1964.
[21] M. L. Sichitiu. ross-layer scheduling for power efficiency in wireless sensor networks. IEEE Infocom,
2004.
[22] G. W. Steward. A modi cation of davidon's minimization method to accept difference approxima-
tions of derivatives. Journal of the Association for Computing Machinery, 14:72-83, 1967.
[23] I. Zang. A smooth-out technique for min-max problem. Management Programming, 19:61-77, 1980.