臺灣博碩士論文加值系統

本論文探討以軟體無線電(SDR)為基礎的多點無線網路聯合通訊該如何考慮功率控制、排程、路由和流量。隨後，基於分支界定法(branch-and-bound)和凸包放寬(convex-hull relaxation)，建立一個有效解決方法來解決這個動態網路的功率優化。我會演示功率控制的可行性、頻帶效率和頻帶占用空間(bandwidth-footprint product)的有效解決方法過程，並提供有效率的功率控制見解。
在這篇論文中，首先第三章包含以下三個步驟: (1) 我推導出了每一個節點功率控制、排程和路由流量的統一數學模型。(2) 制定了動態網路跨層優化的問題。(3) 介紹一個動態網路跨層優化的解決方案程序。接著我會展示模擬程序的設定、條件和模擬圖來驗證我建議的解決程序是有效的。最後結束本論文。

主要貢獻有以下三點：
#我推導出統一的數學模型：
透過延伸現有的干擾協議模型，基於可行的功率控制排程，我建立一個正式的數學模型。
#定量的功率控制有顯著影響：
通過樣本隨意網路應用程序的解決方案，我已經證明功率控制的數量對功率控制的排程可行性、頻帶效率和頻帶占用空間有顯著的影響。這證實了未來的無線網路模型研究迫切納入的需要。
#可廣泛地運用在類似的問題。

This thesis investigates how to support user communication sessions by jointly considering power control, scheduling, and flow routing for an SDR-based multi-hop wireless network. Subsequently, I develop an efficient solution procedure based on branch-and-bound technique and convex hull relaxation to solve this cross-layer optimization problem. I demonstrate the efficacy of the solution procedure and offer insights on the impact of power control on scheduling feasibility, bandwidth efficiency, and bandwidth-footprint product (BFP).
In this thesis, at first, mathematical models, problem formulation and solution procedures. It contains the following three steps: (1) develop a unified mathematical model for per-node based power control, scheduling, and flow routing. (2) formulate the cross-layer optimization problem. (3) describes a solution procedure to this cross-layer optimization problem. Then, I will show the simulation settings and results to demonstrate the effectiveness of my proposed scheme. At last, concludes this thesis.



The main contributions of my research are as follows：
#I develop a formal mathematical model：
By extending the existing protocol interference model, I will develop a formal mathematical model for scheduling feasibility under the influence of power control.
#Quantitatively that power control has significant impact：
By applying the solution procedure on sample random networks, I have demonstrated quantitatively that power control has significant impact on scheduling feasibility, bandwidth efficiency, and bandwidth-footprint product (BFP). This confirms the critical need of incorporating power control under the protocol interference model for future wireless network research.
#This method can be applied for a broad class of problems.

中文摘要…………...…….………………….………................................I
Abstract………………………………………….…….…………...…...III
Acknowledgement………………………………………………………V
Contents…………………………………………………………..VI
List of Figures………………………………………………….……...VIII
List of Tables……………………………………………………………IX
Chapter.1 Introduction……………………………………………...….1
1.1 Research Motivation………………………………………………….1
1.2 The Proposed and Main Results…………………………………...…4
1.3 Thesis Organization……………………………….………………….6
Chapter.2 Background and Related Works……………………….......7
2.1 The Basic Principles of Cognitive Radio…………………….……....9
2.1.1 Concept and Characteristics of Cognitive Radio…………..….9
2.1.2 The relationship between CRN and SDR.…………………....11
2.2 The Key Physical Layer Cognitive Radio Technology………..…....12
2.2.1 Broadband RF Front-End Technology……………………….12
2.2.2 Spectrum Sensing Technology.……………………………....13
2.2.3 Data Transmission Technology……………………………....15
2.3 Current Situation and Trend………………………………………...17
Chapter.3 Mathematical Models, Problem Formulation and Solution Procedures………………………………………………..19
3.1 Mathematical Models…………………………………………….…19
3.1.1Necessary and Sufficient Condition for Successful Transmission
…………………………………………………………….…21
3.1.2 Per-Node Based Power Control and Scheduling…………….25
3.1.3 Flow Routing and Link Capacity Constraints……………….31
3.2 Problem Formulation………………………………….…………….33
3.2.1 Objective Function…………………………………………...33
3.2.2 Discretization of Transmission Powers………………………35
3.2.3 Problem Formulation…………………………………………35
3.3 Solution Procedures…………………………………………………38
3.3.1 Overview……………………………………………………..38
3.3.2 Linear Relaxation…………………………………………….43
3.3.3 Local Search…………………………………….……………46
3.3.4 Selection of Partition Variable………………………………..48
3.4 Numerical Results…………………………………………………..51
3.4.1 Simulation Setting…………………………………………....51
3.4.2 Results………………………………………………………..53
Chapter.4 Conclusion………………………………………………….55
Chapter.5 References………………………………………………….56

LIST of FIGURES

(Fig 1.1) Information Flow Formats of SDR…………………….……...3
(Fig 3.1) No Power Control……………………………………………..23
(Fig 3.2) Per-Node Based Power Control……..………………………...24
(Fig 3.3) Convex Hull for Discrete Term.…..…….……………….……45
(Fig 3.4) 20-node Ad Hoc Network…….………………………………52
(Fig 3.5) Flow Routing For the Five Session in The 20-node Network..54
(Fig 3.6) Objective Value as a Function of Q…………………………..54

LIST of TABLES

(Table 3.1) All Symbols in this Thesis.………………………………..19
(Table 3.2) Pseudo Code for Branch-and-Bound…..………………….42
(Table 3.3) An Algorithm to Obtain x and q………………..………….47
(Table 3.4) Source Node, Destination, and Rate Requirement of the 5 Sessions…………………………………………………..52

[1] M. Kodialam and T. Nandagopal, “Characterizing the capacity region in multi-radio multi-channel wireless mesh networks," in Proc. ACM Mobicom, pp. 73–87, Cologne, Germany, Aug. 2005.
[2] P. Kyasanur and N. H. Vaidya, “Capacity of multi-channel wireless
networks: impact of number of channels and interfaces," in Proc. ACM Mobicom, pp. 43–57, Cologne, Germany, Aug. 2005.
[3] X. Liu and W. Wang, “On the characteristics of spectrum-agile
Communication networks," in Proc. IEEE DySpan, pp. 214–223, Baltimore, MD, Nov. 2005.
[4] J. Liu, T. Y. Park, Y. T. Hou, Y. Shi, and H. D. Sherali, “Crosslayer
optimization of MIMO-based mesh networks under orthogonal
channels," in Proc. IEEE Wireless Commun. Networking Conf. (WCNC), pp. 49–54, Hong Kong, China, Mar. 2007.
[5] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization. New York: John Wiley & Sons, 1999.
[6] B. Radunovic and J.-Y. Le Boudec, “Rate performance objectives of
multi-hop wireless networks," in Proc. IEEE Infocom, pp. 1916–1927, Hong Kong, China, Mar. 2004.
[7] A. Raniwala and T. Chiueh, “Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network," in Proc. IEEE Infocom, pp. 2223–2234, Miami, FL, Mar. 2005.
[8] A. Wyglinski, M. Nekovee, and Y. T. Hou, eds., Cognitive Radio
Communications and Networks: Principles and Practice. Elsevier.
[9] SDR Forum. [Online]. Available: http://www.sdrforum.org.
[10] H. D. Sherali and W. P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Chapter 8. Kluwer Academic Publishers, 1999.
[11] M. Alicherry, R. Bhatia, and L. Li, “Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks," in Proc. ACM Mobicom, pp. 58–72, Cologne, Germany, Aug. 2005.
[12] A. Behzad and I. Rubin, “Impact of power control on the performance of ad hoc wireless networks," in Proc. IEEE Infocom, pp. 102–113, Miami, FL, Mar. 2005.
[13] R. Bhatia and M. Kodialam, “On power efficient communication over multi-hop wireless networks: joint routing, scheduling and power control," in Proc. IEEE Infocom, pp. 1457–1466, Hong Kong, China, Mar. 2004.
[14] C. C. Chen and D. S. Lee, “A joint design of distributed QoS scheduling and power control for wireless networks," in Proc. IEEE Infocom, 12 pages, Barcelona, Catalunya, Spain, Apr. 2006.
[15] R. L. Cruz and A. V. Santhanam, “Optimal routing, link scheduling and power control in multi-hop wireless networks," in Proc. IEEE Infocom, pp. 702–711, San Francisco, CA, Mar. 2003.
[16] R. Draves, J. Padhye, and B. Zill, “Routing in multi-radio, multihop
wireless mesh networks," in Proc. ACM Mobicom, pp. 114–128,
Philadelphia, PA, Sept. 2004.


[17] T. Elbatt and A. Ephremides, “Joint scheduling and power control for wireless ad-hoc networks," in Proc. IEEE Infocom, pp. 976–984, New York, NY, June 2002.
[18] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman and Company, pp. 245–248, 1979.
[19] P. Gupta and P. R. Kumar, “The capacity of wireless networks," IEEE Trans. Inform. Theory, vol. 46, no. 2, pp. 388–404, Mar. 2000.
[20] Joint Tactical Radio System. [Online]. Available: http://jtrs.army.mil/.