무선 네트워크에서 크로스 레이어 설계를 위한 선형 계획 기반의 최적화 연구
Study on Optimization Based on Linear Programming for Cross-layer Design in Wireless Networks
- 주제(키워드) Optimization , Linear programming , Wireless networks
- 발행기관 아주대학교
- 지도교수 이채우
- 발행년도 2012
- 학위수여년월 2012. 8
- 학위명 박사
- 학과 및 전공 일반대학원 전자공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000012897
- 본문언어 한국어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
In today's practical wireless networks, one of the most important issues is how to jointly optimize various functions at different layers (e.g., routing, scheduling and power control) for high performance. To illustrate this point, researchers usually present what they call a cross-layer design. Cross-layer design can help to exploit the interactions between layers and promotes adaptability at various layers based on information exchanged. However, it is often hard to characterize the interactions between protocols at different layers, and the joint optimization across layers may lead to complex schemes. Furthermore, in wireless networks, available resources (for scheduling or routing) are generally restricted, and profits between nodes are often structurally twisted and complicated. Thus, it is considerably difficult to take various functions at different layers and profits between the nodes into consideration jointly and to optimize the network. In this context, mathematical programming such as linear programming (LP, or linear optimization) can be a nice approach to the cross-layer optimization problem. LP is a mathematical method for determining a way to achieve the best outcome such as maximum profit or minimum cost in a given mathematical model for some list of requirements represented as linear relationships. It is applied to various fields of study, and it is also useful in optimizing the network due to proven usefulness in planning (e.g., routing, scheduling, assignment, and design), fast derivation of the solution, intuitive formulation, and handling of many variables. Our study for cross-layer optimization design in wireless networks has a straightforward linear programming formulation and, it will be the main theme of this thesis. The main idea of our study is to represent the acceptance or rejection of resource assignment (i.e., time and/or channel allocation) for each node as a binary integer variable which can only take on the value of 0 or 1 (rather than arbitrary integers). Then, we consider the characteristics of wireless networks (such as RFID system and ad hoc network) and formulate the linear program that sequentially achieves several objectives (such as minimum frame size, maximum utilization, energy efficiency, etc.) while taking the controls (such as scheduling, routing and power control, etc.) in different layers into consideration jointly. Numerical results demonstrate the effectiveness of the proposed optimization designs.
more목차
1 Introduction
1.1 Background and Motivation
1.2 Thesis Outline
1.3 Thesis Contributions
2 Understanding of Linear Programming for Network Optimization
2.1 Introduction to Linear Programming
2.2 Basic mechanism for solving linear programs
2.3 Existing LP-based Network Optimization
2.3.1 Basic constraint for the network flow optimization Flow conservation
2.3.2 Minimum cost flow problem
2.3.3 Maximal flow problem
2.3.4 Network optimization problem in wireless networks
3 Independent Set Problem in Wireless Networks
3.1 Independent Set Problem
3.2 Existing works for nding independent sets
3.3 Network Model
3.4 An ILP-based Optimization For Finding the Optimal Independent Sets
3.4.1 Two-stage Optimization
3.4.2 Single-stage Optimization
3.5 Numerical Results
3.6 Summary
4 Multi-Reader Arbitration in RFID Systems
4.1 Reader Interference Problem in RFID Systems
4.2 Countermeasures To Reader Interference Problem
4.2.1 SDMA based collision resolution
4.2.2 FDMA based collision resolution
4.2.3 TDMA based collision resolution
4.2.4 CSMA based collision resolution
4.2.5 Power control based collision resolution
4.2.6 Centralized Resource allocation based collision resolution
4.3 Network Model
4.3.1 General description
4.3.2 Reader interference model
4.4 A Cross-layer Optimization for Resource Scheduling and Power Allocation
4.4.1 Three-stage optimization
4.4.2 Single-stage optimization
4.5 Numerical Results
4.6 Comparative View of the Anti-Collision Approaches
4.7 Summary
5 Multicast Communications for Multi-hop Wireless Networks
5.1 Multicast communication problem in Multi-hop Wireless Networks
5.2 Related works on multicast in multi-hop wireless networks
5.3 Consideration for multicast tree construction
5.3.1 Transmission and interference
5.3.2 Multicast tree construction
5.4 Network Model and Formulation
5.4.1 Node Scheduling and Interference Modeling
5.4.2 Multicast Tree construction
5.4.3 Loop Prevention
5.4.4 Problem Formulation
5.5 Numerical Results
5.6 Summary
6 Conclusion
