進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-0812200915261519
論文名稱(中文) 無線感知網路資源管理最佳化
論文名稱(英文) Optimal Resources Allocation for a Cognitive Network
校院名稱 成功大學
系所名稱(中) 數學系應用數學碩博士班
系所名稱(英) Department of Mathematics
學年度 97
學期 2
出版年 98
研究生(中文) 朱書賢
研究生(英文) Shu-hsien Chu
學號 l1696403
學位類別 碩士
語文別 英文
論文頁數 64頁
口試委員 口試委員-蘇賜麟
指導教授-郭文光
指導教授-許瑞麟
口試委員-林仁彥
中文關鍵字 無線網路  最佳化  感知無線電  資源管理  跨層 
英文關鍵字 Wireless Network  Resource Management  Cognitive Radio  Cross-Layer  Optimization 
學科別分類
中文摘要 在這篇文章中,我們將感知無線電多重跳躍網路的跨層資源管理最佳化問題,透過對無線網路特性的分析,寫成一個有 0-1 整數條件及非凸限制式的網路最大流量問題。然而,這個結構可以被推廣到考慮不同目的的網路,譬如:功率最小問題、壅塞控制和影像品質控制。
這個問題總共橫跨了OSI七層中的實體層、資料連結層和網路層等三層,包含連線排程、頻道分配、流量分配、路由和功率控制等,均被寫入一個NP-hard混合整數非線性規劃問題。
技術上,我們主要面對兩種限制式。在非凸限制式上,我們發展了一個局部線性逼近 (LLA) 演算法。在演算法中,先對原非凸函數的變數,進行定義域的切割,然後,在各個切割上,找到一個單變數的凸上(下)界近似函數,再利用線性化的技巧,求得該凸函數的線性上(下)界,以此取代非凸函數。
在0-1整數條件中,我們先利用分支限界法來求最佳解;在這問題中,分支限界法的二元樹中存在許多歪斜結構的子樹。這些歪斜結構可以加快求解速度,但是求解所需的時間仍是呈指數成長。因此,我們發展了一套直覺式的演算法 Greedy Search (GS)。這個演算法中,對於放寬的整數變數,經過特定的規則排序後,我們逐一假設它為0和1求解,然後比較這兩種假設的上界解,取其大者,直至所有變數都被確定為止。而且,這套演算法只需要線性的時間就可以得到近似解。
最後的實驗數據說明了利用我們的演算法所求得的近似解很接近最佳解。而且利用我們的演算可以解決分支限界法所不能處理的大拓墣網路問題。
英文摘要 In this paper, through characteristic analysis of wireless network, we formulate the cognitive radio multi-hop network cross-layer resource management optimization problem into a network maximum throughput problem with 0-1 integer constraint and non-convex constraint. And this structure can be extended to networks considering different objects, e.g., minimum power consumption, minimum worst congestion level, and maximum worst PSNR quality.
This problem totally cross three layers, physical layer, data-link layer, and network layer. The link scheduling, channel assignment, flow allocation, routing, and power management issues are involved in a NP-hard mixed-integer-non-linear program (MINLP).
Technically, we face two major constraints. For the non-convex constraint, we develop a local linear approach (LLA) algorithm. In this algorithm, we partition the domain of variables in the non-convex function. Then, we find a single variable upper (or lower) approximation function on each partition. By linearizing the approximated function, we find the upper (or lower) linear function and replace the non-convex function with it.
For the 0-1 integer constraint, we use branch and bound to find the optimal solution at first. In this network model, there exists many skew subtrees in the binary tree of branch and bound. The skew structure results the speeded up solution. But the time it need for finding solution still grow up exponentially. Thus, we propose a heuristic scheme, Greedy Search (GS). In this scheme, we assume that someone of sorted relax integer variable is 0 or 1 respectively and find the corresponding solutions. Then we compare the solutions and choose the larger one. The process will continue till all relax variables are determined. Moreover, this is a linear time algorithm.
The numerical result shows that the approximated solution obtained form our scheme is close to the optimal. And it can solve large networks that SBNB can not.
論文目次 Contents
1 Introduction 7
2 System Model and Problem Formulation 12
2.1 AD-HOC Network System . . . . . . . . . . . . . . . . . . . . 12
2.2 Cognitive Radio . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Power Constraint . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 CR Interference Constraint . . . . . . . . . . . . . . . . 15
2.3.3 Half-Duplex Constraint . . . . . . . . . . . . . . . . . . 16
2.3.4 Capacity Constraint . . . . . . . . . . . . . . . . . . . 17
2.3.5 Flow Conservation . . . . . . . . . . . . . . . . . . . . 17
2.4 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.1 Max Throughput, Min Power . . . . . . . . . . . . . . 19
2.4.2 Min the Worst Congestion Situation . . . . . . . . . . 19
2.4.3 Max the Worst Video Quality . . . . . . . . . . . . . . 19
2.5 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Scheme to Solve 22
3.1 Locally Linear Approach . . . . . . . . . . . . . . . . . . . . . 22
3.1.1 Single Variable Bounds (SVB) . . . . . . . . . . . . . . 23
3.1.2 Linearly Local Subproblem . . . . . . . . . . . . . . . . 25
3.1.3 Terminate Conditions . . . . . . . . . . . . . . . . . . . 26
3.1.4 Domain Partition . . . . . . . . . . . . . . . . . . . . . 27
3.1.5 Flow Chart of LLA . . . . . . . . . . . . . . . . . . . . 28
3.2 Skew Branch and Bound (SBNB) . . . . . . . . . . . . . . . . 30
3.2.1 Introduction of BNB Method . . . . . . . . . . . . . . 30
3.2.2 Skew BNB Method . . . . . . . . . . . . . . . . . . . . 32
3.2.3 Dynamically LB Update Procedure . . . . . . . . . . . 33
3.2.4 Flow Chart of SBNB Method . . . . . . . . . . . . . . 34
3.3 Greedy Search (GS) Method . . . . . . . . . . . . . . . . . . . 35
3.3.1 Flow Chart of GS Method . . . . . . . . . . . . . . . . 35
3.4 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1
3.4.1 Model Pruning . . . . . . . . . . . . . . . . . . . . . . 36
3.4.2 Binary Variable Pruning . . . . . . . . . . . . . . . . . 36
3.5 Tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Numerical Result 41
4.0.1 Compare the Solution with CR Constraint . . . . . . . 45
5 Conclusion 49
5.1 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Bibliography 52
A Row Data 57
B Coordinate of Nodes in Each Topology 59
參考文獻 [1] Report of the spectrum efficiency working group. Technical report, FCC, November 2002.
[2] 2nd International Conference on Broadband Networks (BROADNETS 2005), 3-7 October 2005, Boston, Massachusetts, USA. IEEE, 2005.
[3] Proceedings of the Fourth Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, SECON 2007, Merged with IEEE International Workshop on Wireless Ad-hoc and Sensor Networks (IWWAN), June 18-21, 2007, San Diego, California, USA. IEEE, 2007.
[4] Proceedings of the Global Communications Conference, 2007. GLOBECOM '07, Washington, DC, USA, 26-30 November 2007. IEEE, 2007.
[5] INFOCOM 2008. 27th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 13-18 April 2008, Phoenix, AZ, USA. IEEE, 2008.
[6] Proceedings of the 68th IEEE Vehicular Technology Conference, VTC Fall 2008, 21-24 September 2008, Calgary, Alberta, Canada. IEEE, 2008.
[7] I. F. Akyildiz, W.-Y. Lee, M. C. Vuran, and S. Mohanty. Next generation/dynamic spectrum access/cognitive radio wireless networks: a survey. Comput. Networks, 50(13):2127-2159, September 2006.
[8] M. Alicherry, R. Bhatia, and E. L. Li. Joint channel assignment and routing for throughput optimization in multiradio wireless mesh networks. IEEE Journal on Selected Areas in Communications, 24(11):1960-1971, 2006.
[9] M. Bazaraa. Nonlinear Programming. J. Wiley and Sons, New York, 2006.
[10] Y. S. Chan and J. W. Modestino. A joint source-coding power-control approach combined with adaptive channel coding for video transmission over CDMA networks. IEEE Transactions on Communications, 54(10):1705-1709, 2006.
[11] H. Chen, S. Schaible, and R. Sheu. Generic algorithm for generalized fractional programming. Journal of Optimization Theory and Applications.
[12] L. Chen, Q. Zhang, M. Li, and W. Jia. Joint topology control and routing in ieee 802.11-based multiradio multichannel mesh networks. IEEE Transactions on Vehicular Technology, 56(5):3123-3136, September 2007.
[13] 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.
[14] J.-P. Crouzeix and J. A. Ferland. Algorithms for generalized fractional programming. Math. Program, 52:191-207, 1991.
[15] A. de Baynast, P. Mahonen, and M. Petrova. ARQ-based cross-layer optimization for wireless multicarrier transmission on cognitive radio networks. Computer Networks, 52(4):778-794, 2008.
[16] S. Ergen and P. Varaiya. On multi-hop routing for energy efficiency. IEEE Communications Letters, 9(10):880-881, October 2005.
[17] M. A. Haleem and R. Chandramouli. Adaptive downlink scheduling and rate selection: a cross-layer design. IEEE Journal on Selected Areas in Communications, 23(6):1287-1297, 2005.
[18] A. T. Hoang and Y.-C. Liang. Downlink channel assignment and power control for cognitive radio networks. IEEE Transactions on Wireless Communications, 7(8):3106-3117, 2008.
[19] Y. T. Hou, Y. Shi, and H. D. Sherali. Spectrum sharing for multi-hop networking with cognitive radios. IEEE Journal on Selected Areas in Communications, 26(1):146-155, 2008.
[20] H. Jiang and W. Zhuang. Resource allocation with service differentiation for wireless video transmission. IEEE Transactions on Wireless Communications, 5(6):1456-1468, 2006.
[21] B. Johansson, P. Soldati, and M. Johansson. Mathematical decomposition techniques for distributed cross-layer optimization of data networks. Selected Areas in Communications, IEEE Journal on, 24(8):1535-1547, 2006.
[22] 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.
[23] L. P. Kondi, D. Srinivasan, D. A. Pados, and S. N. Batalama. Layered video transmission over wireless multirate DS-CDMA links. IEEE Trans. Circuits and Systems for Video Technology, 15(12):1629-1637, Dec. 2005.
[24] H. Kwon, T.-H. Kim, S. Choi, and B. G. Lee. A cross-layer strategy for energye efficient reliable delivery in wireless sensor networks. IEEE Transactions on Wireless Communications, 5(12):3689-3699, 2006.
[25] J. Li, D. Chen, W. Li, and J. Ma. Multiuser power and channel allocation algorithm in cognitive radio. In Proc. 2007 International Conference on Parallel Processing (36th ICPP'07), page 72, Xi-An, China, Sept. 2007. IEEE Computer Society.
[26] X.-Y. Li, A. Nusairat, Y.Wu, Y. Qi, J. Zhao, X. Chu, and Y. Liu. Joint throughput optimization for wireless mesh networks. IEEE Transactions on Mobile Computing, 99(2), 2008.
[27] X. Lin, N. B. Shroff, and R. Srikant. A tutorial on cross-layer optimization in wireless networks. Selected Areas in Communications, IEEE Journal on, 24(8):1452-1463, 2006.
[28] R. Madan, S. Cui, S. Lall, and N. A. Goldsmith. Cross-layer design for lifetime maximization in interference-limited wireless sensor networks. IEEE Transactions on Wireless Communications, 5(11):3142-3152, 2006.
[29] G. Nemhauser. Integer and Combinatorial Optimization. Wiley, New York, 1988.
[30] C. Peng, H. Zheng, and B. Y. Zhao. Utilization and fairness in spectrum assignment for opportunistic spectrum access. MONET, 11(4):555-576, 2006.
[31] Q. Qu, L. B. Milstein, and D. R. Vaman. Cognitive radio based multi-user resource allocation in mobile ad hoc networks using multi-carrier CDMA modulation. IEEE Journal on Selected Areas in Communications, 26(1):70-82, 2008.
[32] A. H. M. Rad and V. W. S. Wong. Cross-layer fair bandwidth sharing for multichannel wireless mesh networks. IEEE Transactions on Wireless Communications, 7(9):3436-3445, 2008.
[33] B. Radunovic and J.-Y. L. Boudec. Rate performance objectives of multihop wireless networks. IEEE Trans. Mob. Comput, 3(4):334-349, 2004.
[34] A. Rajeswaran, G. Kim, and R. Negi. Joint power adaptation, scheduling, and routing for ultra wide band networks. IEEE Transactions on Wireless Communications, 6(5):1964-1972, 2007.
[35] Y. Shi and Y. T. Hou. A distributed optimization algorithm for multi-hop cognitive radio networks. In INFOCOM [5], pages 1292-1300.
[36] Y. Shi, Y. T. Hou, and H. D. Sherali. Cross-layer optimization for data rate utility problem in UWB-based ad hoc networks. IEEE Trans. Mob. Comput, 7(6):764-777, 2008.
[37] G. M. Su, Z. Han, M. Wu, and K. J. R. Liu. A scalable multiuser framework for video over OFDM networks: Fairness and efficiency. IEEE Trans. Circuits and Systems for Video Technology, 16(10):1217-1231, Oct. 2006.
[38] J. Tang, G. Xue, and W. Zhang. Cross-layer optimization for end-to-end rate allocation in multi-radio wireless mesh networks. Wirel. Netw., 15(1):53-64, 2009.
[39] R. Urgaonkar and M. J. Neely. Opportunistic scheduling for reliability in cognitive radio networks. Technical report, USC Technical Report CSI-07-07-03, University of Southern California, Los Angeles, CA 90089, July 2007.
[40] W.Wang, X. Liu, and D. Krishnaswamy. Robust routing and scheduling in wireless mesh networks. In SECON [3], pages 471-480.
[41] Y. Xing, C. N. Mathur, M. A. Haleem, R. Chandramouli, and K. P. Subbalakshmi. Dynamic spectrum access with qos and interference temperature constraints. Mobile Computing, IEEE Transactions on, 6(4):423-433, 2007.
[42] F. Ye, Q. Chen, and Z. Niu. End-to-end throughput-aware channel assignment in multi-radio wireless mesh networks. In GLOBECOM [4], pages 1375-1379.
[43] Y. Zhang and K. Letaief. Cross-layer adaptive resource management for wireless packet networks with ofdm signaling. IEEE Transactions on Wireless Communications, 5(11):3244-3254, 2006.
[44] Y. Zhang and C. Leung. A distributed algorithm for resource allocation in OFDM cognitive radio systems. In VTC Fall [6], pages 1-5.
[45] X. Zhou, L. Lin, J. Wang, and X. Zhang. Cross-layer routing design in cognitive radio networks by colored multigraph model. Wireless Personal Communications, 49(1):123-131, april 2009.
[46] J. Zhuang, H.Wu, Q. Zhang, and B. Li. Joint routing and scheduling in multi-radio multi-channel multi-hop wireless networks. In BROADNETS [2], pages 678-687.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2017-07-31起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2019-07-31起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw