這篇論文示主要討論在信息不完全情況下的無線網絡資源分配的兩個問題。傳輸節點不固定和信道狀態的不確定性將影響資源分配的選擇。因為不完整的信息，或在這些情況下可能無法確切獲得準確的信息，將對資源優化配置產生一定的影響。對於不完整信息對無線網路的影響，其中用戶的移動性和信道增益的不確定性，將是本論文中討論的兩個主要問題。 / 本論文的第一部分是關於移動傳輸節點的資源分配問題。我們主要分析上行系統的移動用戶，其中每個用戶會盡量優化他或她自己的功效函數，以達到最佳的性能。此外，我們提出對移動用戶的功率分配優化的方案當所有信道信息可用的時候。此外，我們提出了幫助每個用戶預測信道信息總幹擾來優化功效函數，當信息不完備的時候。這形成了一個不完全信息博弈。我們提出了預測的規則，幫助動態預測總幹擾。我們採用了卡爾曼濾波器來處理測量噪聲 我們也說明了利用預測來優化的功效函數和由完整的信息得出的之間的差異。此外，從動態規劃，我們在預測的基礎上給出一個動態的功率分配方案。 / 第二部分討論了在資源分配時，當有關信道增益是不完整時的不確定規劑。我們主要考慮認知無線電模型。在第二部分中，我們考慮，當二級用戶的干擾不會超過一定限制時，他們能夠使用共享的頻率的情況。我們首先利用約束幹擾的限制進行建模，使得二級用戶的干擾，即使在最壞的情況下，也不會超過限制，這將有助於他或她以避免不可行的解決方案。然後，我們擴展我們的概率約束條件來代表不確定性的干擾限制。由於概率約束一般都是難以解決的，而基於無線信道的衰落效應，有關變量的完整的信息是很難獲得。我們重新將概率約束條件轉化為隨機期望約束條件。利用樣本平均近似法，我們提出了隨機學習算法，以幫助次級用戶從主要用戶那裡獲得反饋信息，最大限度地提高自己的功效函數。此外，我們分析了在認知無線電網絡定價條件的頻譜共享方案。我們展示的聯合優化配置方案，幫助次級用戶從主要用戶購買頻譜和優化功率。當有信道增益的不確定性時，二級用戶希望最大限度地提高功效函數的期望值並且採用相對穩定的採購策略追求最佳平均收益。它是一個有鞍點的隨機優化問題。我們展示一個分佈式的隨機算法，以幫助二級用戶更新資源分配策略。在一些實際的情況下，為了減少計算複雜性和希望實施越來較為容易，我們利用迭代平均來為二級用戶進行資源配置。 / Two main issues of resource allocation in wireless networks with incomplete information are addressed in this thesis. Transmission node is not fixed in the wireless system and uncertainties of the channel states would also affect the choices of resource allocation, since full information cannot be provided or may not be exact under these scenarios. For incomplete information in wireless networks, mobility of the users and uncertainties of channel gains are two main issues that would be considered in this thesis. / The first part of this thesis is concerning the resource allocation problems with mobile trans- mission nodes. We consider mobile users in an up-link system. We analyze the mobile system where each user would try to maximize his or her own utility to achieve the best performance. Besides, we propose a power allocation scheme for the mobile users when all channel information is available. We show that our model can form a game. Moreover, we illustrate that each user would expect to predict the aggregate interference to maximize the utility when channel information is incomplete. It can be shown that this forms a game with incomplete information. We demonstrate the prediction rules which help predict the aggregate interference dynamically. We apply the Kalman filter to tackle measurement noises. We also illustrate the bound on the difference between the utility with prediction and that with complete information. Moreover, applying dynamic programming, we give a dynamic power allocation scheme based on the predictions. / The second part discusses the issue of uncertain programming in resource allocation when information about channel gains is incomplete. We mainly consider the model of cognitive radio networks. We introduce a resource allocation scheme for secondary users with spectrum sharing in a cognitive radio network. Secondary users can exploit the spectrum owned by primary links when their interference level does not exceed certain requirements. We first model the interfer- ence constraints as robust constraints such that secondary users would satisfy the interference constraints even under the worst cases, which would help him or her to avoid the unfeasible solutions. We then extend our consideration of the interference constraints as chance constraints to represent uncertainties. Since chance constraints are generally difficult to solve and full in- formation about the uncertain variables is not available due to the fading effects of wireless channels, we reformulate the constraints into stochastic expectation constraints. With sample average approximation method, we propose stochastic distributed learning algorithms to help secondary users satisfy the constraints with the feedback information from primary links when maximizing the utilities. Moreover, we introduce a resource allocation scheme for secondary users to share spectrum and optimize usage of power with pricing. Secondary users need to buy spectrum from primary users. In the process, secondary users also enhance the utilization of the unused bandwidth by primary users. We first demonstrate the resource allocation scheme when full information about channel gains is available. When there are uncertainties of channel gains, secondary users would like to maximize the expected value of the utilities to pursue the best benefits on average with relatively stable buying strategies. It can be shown that it is a stochastic optimization problem with saddle points. We demonstrate a Distributed Stochastic Algorithm to help secondary users update their resource allocation strategies. For some practical scenarios, to reduce computation complexity and make implementation easy, we illustrate an Iterate Average from Distributed Stochastic Algorithm for secondary users. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Zhou, Kenan. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 123-134). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivations --- p.1 / Chapter 1.2 --- Contributions and Outline of the Thesis --- p.2 / Chapter 2 --- Background Study --- p.5 / Chapter 2.1 --- Slow and Flat Fading Wireless Channel --- p.5 / Chapter 2.2 --- Cognitive Radio Networks --- p.7 / Chapter 2.3 --- Multiple-Access Channel --- p.8 / Chapter 2.4 --- Mobility Model --- p.10 / Chapter 2.5 --- Convex Optimization --- p.12 / Chapter 2.6 --- Uncertain Programming --- p.13 / Chapter 2.7 --- Game Theory --- p.14 / Chapter Part I --- Resource Allocation in Wireless Networks with Mobility --- p.16 / Chapter 3 --- Resource Allocation with Mobile Users in an Up-link System --- p.19 / Chapter 3.1 --- System Model --- p.20 / Chapter 3.2 --- Power Allocation for Mobile Users with Complete Information --- p.22 / Chapter 3.3 --- Power Allocation with Incomplete Information --- p.26 / Chapter 3.3.1 --- Bound on the difference between the utility with prediction and that with complete information --- p.27 / Chapter 3.3.2 --- Prediction Scheme for Incomplete Channel Information --- p.30 / Chapter 3.3.3 --- Power Allocation with Dynamic Programming --- p.32 / Chapter 3.4 --- Numerical results and discussion --- p.35 / Chapter 3.4.1 --- Simulation Model --- p.35 / Chapter 3.4.2 --- Numerical Results --- p.36 / Chapter 3.5 --- Chapter Summary --- p.42 / Chapter 3.6 --- Appendices --- p.44 / Chapter 3.6.1 --- Proof of Theorem 3.1 --- p.44 / Chapter 3.6.2 --- Proof of Theorem 3.2 --- p.47 / Chapter Part II --- Resource Allocation inWireless Networks with Uncertain Programming --- p.48 / Chapter 4 --- Resource Allocation with Robust Optimization --- p.52 / Chapter 4.1 --- System Model --- p.52 / Chapter 4.2 --- Resource Allocation with Robust Optimization Approach --- p.54 / Chapter 4.3 --- Trade-Off Between Robustness and Performance --- p.59 / Chapter 4.4 --- Numerical results and discussion --- p.62 / Chapter 4.4.1 --- Choice of the Penalty Function --- p.62 / Chapter 4.4.2 --- Simulation Model --- p.63 / Chapter 4.4.3 --- Simulation Results --- p.64 / Chapter 4.5 --- Chapter Summary --- p.65 / Chapter 5 --- Resource Allocation with Chance Constraints --- p.67 / Chapter 5.1 --- System Model --- p.68 / Chapter 5.2 --- Power Allocation with Complete Information about Probabilistic Constraints --- p.69 / Chapter 5.3 --- A Stochastic Approximation Approach Based on the Outage Event --- p.72 / Chapter 5.3.1 --- Feasibility of the Stochastic Approximation Method --- p.74 / Chapter 5.3.2 --- Stochastic Distributed Learning Algorithm I (SDLA-I) --- p.76 / Chapter 5.3.3 --- Stochastic Distributed Learning Algorithm II (SDLA-II) --- p.80 / Chapter 5.4 --- Numerical Results and Discussion --- p.82 / Chapter 5.4.1 --- Examples of uk(.) for Simulation --- p.82 / Chapter 5.4.2 --- Simulation Model --- p.83 / Chapter 5.4.3 --- Simulation Results and Discussions --- p.84 / Chapter 5.5 --- Chapter Summary --- p.86 / Chapter 5.6 --- Appendices --- p.88 / Chapter 5.6.1 --- Proof of Lemma 5.3 --- p.88 / Chapter 6 --- Priced Resource Allocation with Stochastic Optimization --- p.90 / Chapter 6.1 --- System Model --- p.91 / Chapter 6.2 --- Price-Based Optimization with Complete Information --- p.94 / Chapter 6.3 --- Price-Based Stochastic Optimization with Uncertainties --- p.96 / Chapter 6.4 --- Distributed Stochastic Algorithms for the Price-Based Stochastic Optimization --- p.100 / Chapter 6.4.1 --- Iterate Averages of DSA --- p.104 / Chapter 6.5 --- Numerical Results and Discussion --- p.106 / Chapter 6.5.1 --- Simulation Model --- p.106 / Chapter 6.5.2 --- Numerical Results --- p.107 / Chapter 6.6 --- Chapter Summary --- p.112 / Chapter 6.7 --- Appendices --- p.113 / Chapter 6.7.1 --- Proof of Lemma 6.1 --- p.113 / Chapter 6.7.2 --- Proof of Proposition 6.1 --- p.114 / Chapter 6.7.3 --- Proof of Lemma 6.3 --- p.114 / Chapter 6.7.4 --- Proof of Lemma 6.4 --- p.115 / Chapter 6.7.5 --- Proof of Proposition 6.2 --- p.116 / Chapter 7 --- Conclusion and Future Work --- p.117 / Chapter 7.1 --- Conclusion --- p.117 / Chapter 7.2 --- Future Work --- p.119 / Chapter 7.2.1 --- Joint Power and Channel Access Scheduling for Mobile Users --- p.119 / Chapter 7.2.2 --- Power Control for Heterogeneous Mobile Users --- p.120 / Chapter 7.2.3 --- More on Uncertain Programming in Cognitive Radios --- p.120 / Chapter 7.2.4 --- Transmissions in Complex Networks with Uncertainties --- p.121 / Chapter 7.2.5 --- Secure Transmissions in Wireless Networks with Uncertainties --- p.122 / Bibliography --- p.123

Hui, Tan Hing. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 151-162). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.vi / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Literature Review --- p.7 / Chapter 2.1 --- Background --- p.7 / Chapter 2.1.1 --- "Tools for Analyzing Vehicles' Speeds, Traffic Flows and Densities" --- p.7 / Chapter 2.1.2 --- Tools for Analyzing Bytes Received by the Vehicles from an AP --- p.9 / Chapter 2.1.3 --- Effort-Fairness vs Outcome-Fairness --- p.10 / Chapter 2.1.4 --- Quantifying Fairness on the Bytes Received by the Vehicles from an AP --- p.10 / Chapter 2.2 --- Delay-Tolerant Networks(DTNs) --- p.12 / Chapter 2.3 --- Drive-thru Internet Systems --- p.14 / Chapter 2.4 --- Resource Allocation/Scheduling in Drive-thru Internet and Related Systems --- p.20 / Chapter 2.4.1 --- Resource Allocation/Scheduling Algorithms for Multiple Vehicles --- p.20 / Chapter 2.4.2 --- Rate Adaptation Algorithms for Fast-varying Channels due to Vehicular Movement/Mobility --- p.29 / Chapter 3 --- Performance Evaluation of Round-robin Scheduler with IEEE 802.11 MAC --- p.33 / Chapter 3.1 --- System Model --- p.34 / Chapter 3.2 --- Description of the Real-life Vehicular Traffic Trace --- p.36 / Chapter 3.2.1 --- Analysis on Hourly Single-lane Traffic Flow of 1-80 Highway --- p.40 / Chapter 3.2.2 --- Analysis on Hourly Directional Traffic Flow of 1-80 Highway --- p.43 / Chapter 3.2.3 --- Analysis on Hourly Single-lane Vehicles' Speeds of 1-80 Highway --- p.45 / Chapter 3.2.4 --- Analysis on Daily Vehicles' Speeds of 1-80 Highway --- p.48 / Chapter 3.2.5 --- "Relationship among Average Traffic Densities, Flows and Vehicles' Speeds in Singlelane Scenarios" --- p.51 / Chapter 3.2.6 --- "Relationship among Average Traffic Densities, Flows and Vehicles' Speeds in Multilane Scenarios" --- p.52 / Chapter 3.3 --- Trace-driven Simulations of Drive-thru Internet Scenarios using Round-robin Scheduler with IEEE 802.11 MAC --- p.54 / Chapter 3.3.1 --- Simulation Setup --- p.54 / Chapter 3.3.2 --- Scenarios of using Fixed Data Rate --- p.57 / Chapter 3.3.3 --- Scenario of using Auto-rate Algorithm --- p.67 / Chapter 4 --- The Design and Implementation of VECADS --- p.73 / Chapter 4.1 --- Towards the Design of an Intelligent Scheduling for Drive-thru Internet --- p.74 / Chapter 4.1.1 --- System Throughput Maximization vs Fairness --- p.74 / Chapter 4.1.2 --- Antenna --- p.75 / Chapter 4.1.3 --- Speed --- p.76 / Chapter 4.1.4 --- Noisy Measurement of Predicting Channel Condition based on RSSI(or Similar Metrics) only --- p.77 / Chapter 4.1.5 --- Region for Serving “Weak´ح Vehicles --- p.78 / Chapter 4.2 --- System Model --- p.79 / Chapter 4.3 --- The Design of VECADS --- p.83 / Chapter 4.3.1 --- Using Vehicular Context to Help Scheduling --- p.83 / Chapter 4.3.2 --- Penalizing Slow Vehicles in the Coverage . --- p.88 / Chapter 4.3.3 --- "Round-Robin Scheduling for ""Weak"" Vehicles in the “Sweet Zone´ح" --- p.90 / Chapter 4.3.4 --- Rate Adaptation Algorithm in VEC ADS --- p.94 / Chapter 4.4 --- The Implementation of VECADS --- p.97 / Chapter 4.4.1 --- Overall System Architecture of VECADS --- p.97 / Chapter 4.4.2 --- Overall Scheduling Flow of VECADS --- p.100 / Chapter 4.4.3 --- Algorithms in VECADS --- p.102 / Chapter 5 --- Performance Evaluation of VECADS --- p.110 / Chapter 5.1 --- Simulation Setup --- p.110 / Chapter 5.2 --- Simulation Results and Discussion --- p.114 / Chapter 5.2.1 --- Evaluation of the Performance Impact of Different System Parameters --- p.114 / Chapter 5.2.2 --- Evaluation of Different Design Options --- p.119 / Chapter 6 --- Conclusions and Discussion --- p.142 / Chapter A --- Average Bytes Received by a Moving Vehicle from a Roadside AP --- p.146 / Chapter B --- Distribution of the Cumulative Bytes Received by Vehicles from a Roadside AP --- p.148 / Bibliography --- p.151

After that, the cooperative transmission scheme is extended for the scenario of more than two source-destination pairs. One objective is to investigate the relationship between the diversity order and the number of source-destination pairs. This is done by considering the sum power minimization problem. A pricing game is derived to provide a distributed implementation. At Nash Equilibrium of the game, the total transmission power is minimized. Simulation results show the rapid convergence of the game and its adaptation to channel fluctuations. It also shows that the cooperative transmission scheme achieves full diversity order. / Apart from replacing a superposition code based cooperative transmission scheme by a TDM based scheme, the implementation can be simplified by introducing a partner selection scheme to the nodes. In that network, the cooperative transmission code still uses superposition code as the building block. Instead of relaying the messages from all other nodes, in this new scheme, the source nodes only relay the messages for their assigned partners. A natural question is: How can we assign the partners to the source nodes such that the total transmission power is minimized. The problem is solved in two phases. Firstly, we solve the sum power minimization problem for each pair of nodes. In some cases, this problem has closed-form solutions while for the other cases, a simple iterative algorithm can solve this problem. / Firstly, cooperative orthogonal-division channel is defined and two cooperative transmission schemes based on dirty-paper coding and superposition code are proposed and compared through simulations. Simulation Results show the significant improvement over the pure direct transmission schemes. Although one cooperative transmission scheme achieves a slightly larger rate region, the other scheme has a much simpler implementation so the remaining parts of the thesis focus on this scheme. The outage performance of this scheme is also compared with a simplified Han-Kobayashi scheme through simulations. Simulation results illustrate the significant improvement in the diversity gain of this scheme over the Han-Kobayashi scheme. / However, it is noted that the complexity of implementing superposition code, which is a building block of the cooperative transmission code, is very high when there are many users in the network. Hence, another time-division multiplex (TDM) based cooperative transmission scheme is proposed. Similar to the superposition code based scheme, there is a pricing game which can provide a distributed sum power minimization. Simulation results also show that the game has high convergence rate and it can adapt to changes of channel conditions efficiently. In addition, this cooperative transmission scheme also achieves full diversity order. / In this thesis, different codes and resource allocation algorithms for cooperative transmissions are proposed. Briefly speaking, in cooperative transmission, a number of wireless nodes form a coalition in which they exchange and cooperatively transmit messages. As a result, the order of diversity can be increased without installing additional antennas. / Next, a weighted sum rate maximization algorithm is proposed. There are two purposes of this algorithm. Firstly, this algorithm is adopted to find the Pareto-optimal points of the boundary of the achievable rate region through simulations. Secondly, this algorithm can be extended to solve the max-min fairness problem and the joint utility maximization algorithm by the proposed framework. / This thesis is ended with some future research directions. / With this information, we can assign the partners by Gabow's algorithm, which solves the maximum weighted matching problem that is mapped from the original partner selection problem. Nonetheless, it is noted that when the number of users is very large, it involves a large amount of the communication and computational cost to solve the sum power minimization problem for each pair of nodes as well as the partner selection problem. Therefore, the Grouping Algorithm is proposed to reduce the aforementioned implementation cost. Simulation results show that the optimal algorithm and the Grouping Algorithm can achieve full diversity order. Moreover, although the Grouping Algorithm is sub-optimal in general, it costs only 1dB of the sum power more than the optimal algorithm. / Ng, Cho Yiu. / Adviser: Tal M. Lok. / Source: Dissertation Abstracts International, Volume: 73-03, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 152-162). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Lin, Xingqin. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 103-109). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Background --- p.3 / Chapter 1.2.1 --- Wireless Communication Schemes --- p.3 / Chapter 1.2.2 --- Mathematical Preliminaries --- p.8 / Chapter 1.3 --- Outline of the Thesis --- p.12 / Chapter 2 --- Learning for Parallel Gaussian Interference Channels --- p.14 / Chapter 2.1 --- System Model and Problem Formulation --- p.16 / Chapter 2.2 --- Stochastic Algorithm for Learning --- p.18 / Chapter 2.2.1 --- Algorithm Design --- p.18 / Chapter 2.2.2 --- Convergence Analysis --- p.21 / Chapter 2.3 --- Continuous Time Approximation --- p.26 / Chapter 2.4 --- Learning with Averaging --- p.28 / Chapter 2.5 --- Numerical Results --- p.29 / Chapter 3 --- Power Control for One-to-Many Transmissions --- p.34 / Chapter 3.1 --- System Model --- p.35 / Chapter 3.2 --- A GNEP Approach --- p.38 / Chapter 3.2.1 --- Problem Formulation --- p.38 / Chapter 3.2.2 --- Preliminary Results --- p.39 / Chapter 3.3 --- Algorithm Design --- p.42 / Chapter 3.4 --- Numerical Results --- p.46 / Chapter 4 --- Flow Allocation in Multiple Access Networks --- p.50 / Chapter 4.1 --- System Model and Problem Formulation --- p.52 / Chapter 4.1.1 --- System Model --- p.52 / Chapter 4.1.2 --- Problem Formulation --- p.53 / Chapter 4.2 --- Characterization of NE --- p.57 / Chapter 4.2.1 --- Feasibility Assumption --- p.57 / Chapter 4.2.2 --- Existence and Uniqueness of NE --- p.58 / Chapter 4.3 --- Distributed Algorithms Design --- p.60 / Chapter 4.3.1 --- D-SBRA --- p.60 / Chapter 4.3.2 --- P-SBRA --- p.61 / Chapter 4.3.3 --- Best Response and Layered Structure --- p.65 / Chapter 4.4 --- Performance Evaluation --- p.67 / Chapter 4.4.1 --- Protocol Evaluation --- p.67 / Chapter 4.4.2 --- Convergence and Performance --- p.69 / Chapter 4.4.3 --- Flow Distribution --- p.71 / Chapter 4.4.4 --- A Grid Network Simulation --- p.73 / Chapter 5 --- Relay Assignment in Cooperative Networks --- p.76 / Chapter 5.1 --- System Model and Problem Formulation --- p.77 / Chapter 5.1.1 --- Three-Node Relay Model --- p.77 / Chapter 5.1.2 --- Network Model --- p.78 / Chapter 5.1.3 --- Problem Formulation --- p.78 / Chapter 5.2 --- Centralized Scheme --- p.80 / Chapter 5.2.1 --- Generalized Relay Assignment --- p.80 / Chapter 5.2.2 --- Admission Control --- p.83 / Chapter 5.2.3 --- Iteration Algorithm and Some Remarks --- p.84 / Chapter 5.3 --- A Simple Distributed Algorithm --- p.84 / Chapter 5.4 --- Numerical Results --- p.86 / Chapter 6 --- Conclusions and Future Work --- p.88 / Chapter 6.1 --- Conclusions --- p.88 / Chapter 6.2 --- Future Work --- p.89 / Chapter A --- Proof of Theorem 21 --- p.93 / Chapter B --- Proof of Theorem 22 --- p.96 / Chapter C --- Proof of Proposition 31 --- p.98 / Chapter D --- Proof of Proposition 44 --- p.101 / Bibliography --- p.103

published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

An algorithmic approach is developed for solving the minimax continuous resource allocation problem with multimodal cost functions. Unlike previous research in the same area which developed solutions for the same problem by imposing restrictions on the cost functions, such as the assumptions of monotoniciy or convexity, this approach is applicable to problems with multimodal functions with a finite number of local extrema. Another significant advantage demonstrated by this approach is that it provides all the optimal solutions to the problem; in contrast to previous algorithms which provided a single optimal solution. When a further level of optimization using a second objective function is desired, one needs the entire set of optimal solutions as provided by the procedures of this thesis. / Master of Science

Designing distributed algorithms for optimizing system-wide performances of large scale communication networks is a challenging task. The key part of this design involves a lot of combinatorial network optimization problems, which are computationally intractable in general and hard to approximate even in a centralized manner. Inspired by the seminal work of Jiang-Walrand, Markov approximation framework was proposed for synthesizing distributed algorithms for general combinatorial network optimization problems. To provide performance guarantees, convergence properties of these distributed algorithms are of significance. / First, we consider instances of the designed Markov chain over resource allocation algorithms. We focus on the convergence issues. We find several examples such that the related convergence results can be applied directly. These examples include optimal path (or tree) selection for wireline networks, optimal neighboring selection for peer-to-peer networks, and optimal channel (or power) assignment for wireless local area networks. / In this thesis, we first review Markov approximation framework and further develop this framework by studying convergence properties of distributed algorithms. These system-wide algorithms consist of the designed Markov chain and resource allocation algorithms. We concentrate on two general scenarios: the designed Markov chain over resource allocation algorithms and resource allocation algorithms over the designed Markov chain. With imprecise measurements of network parameters and without the time-scale separation assumption, we prove convergence to near-optimal solutions for both scenarios under mild conditions. Then we apply Markov approximation framework and associated convergence results to various combinatorial network optimization problems. / Second, we consider instances of resource allocation algorithms over the designed Markov chain. We focus on the system-wide performances. Two instances are investigated: cross-layer optimization for wireless networks with deterministic channel model and wireless networks with network coding. For both instances, guided by Markov approximation framework, we design distributed schemes to achieve maximum utilities. These schemes include primal-dual flow control algorithms, Markov chain based scheduling algorithms, and routing (or network coding) algorithms. Under time-dependent step sizes and update intervals, we show that these distributed schemes converge to the optimal solutions with probability one. Further, under constant step sizes and constant update intervals, we prove that these distributed schemes also converge to a bounded neighborhood of optimal solutions with probability one. These analytical results are validated by numerical results as well. / Shao, Ziyu. / Adviser: Shou Yen Robert Li. / Source: Dissertation Abstracts International, Volume: 73-03, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 134-140). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Resource allocation in wireless systems is addressed via a flow calculus approach in this thesis. Because of the exponential relationship between transmission rates and powers, the marginal increase in power at higher rate regions is larger. To support the high rate transmissions in the next generation wireless systems and applications, we are motivated to consider simultaneous transmissions of multiple distinct flows. / The first part of this thesis is concerning the resource allocation problems in single-source networks. We illustrate what can really be achieved by using multiple relays in parallel relay networks. Simulation results indicate a large improvement from using a single flow to using two distinct flows. By using two distinct flows, the performance is close to optimal. Then, we discuss the trade-off between power and coding complexity by proposing a combination of time-division and cooperative broadcasting. Since the problem involved is NP-hard, we propose a sub-optimal algorithm with a lower computational complexity. The algorithm has a satisfactory performance in terms of total transmission power compared with other schemes and a lower bound. / The second part discusses the issues in multiple-source networks. We show the superior performance of spreading the information over multiple distinct flows in uplink systems. We also discuss a sub-optimal scheme with a satisfactory tradeoff between power and complexity. Furthermore, we use distributed rate allocation. Then, we focus on the relaying situations with information loss during transmissions. We discuss two cases. The first case involves lossy links, while the second case involves the selfish behaviors of the users. In the first case, retransmissions are employed to recover the lost information. We propose a distributed algorithm in which each user allocates its own transmission rates. Also, we suggest a minimax delay data allocation scheme, which reduces the chance of having a long delay for the data due to loss and recovery. In the second case, we use a game-theoretic approach to analyze the problem. We suggest a pricing game with two parts, namely rate allocation and price-setting. The Nash Equilibrium of this pricing game is proved to be the optimal solution to our problem. / Tam, Wai Pan. / Adviser: Tat-Ming Lok. / Source: Dissertation Abstracts International, Volume: 73-03, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 175-190). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Chen, Jieying. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (p. 58-62). / Abstract in English only. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Literature Review --- p.5 / Chapter 1.3 --- Contributions Of This Thesis --- p.7 / Chapter 1.4 --- Structure Of This Thesis --- p.8 / Chapter 2 --- Problem Formulation --- p.9 / Chapter 2.1 --- The JBAPC Problem --- p.9 / Chapter 2.2 --- The Single-Stage Reformulation --- p.12 / Chapter 3 --- The BARN Algorithm --- p.15 / Chapter 3.1 --- Preliminary Mathematics --- p.15 / Chapter 3.1.1 --- Duality Of The Linear Optimization Problem --- p.15 / Chapter 3.1.2 --- Benders Decomposition --- p.18 / Chapter 3.2 --- Solving The JBAPC Problem Using BARN Algorithm --- p.21 / Chapter 3.3 --- Performance And Convergence --- p.24 / Chapter 3.3.1 --- Global Convergence --- p.26 / Chapter 3.3.2 --- BARN With Error Tolerance --- p.26 / Chapter 3.3.3 --- Trade-off Between Performance And Convergence Time --- p.26 / Chapter 4 --- Accelerating BARN --- p.30 / Chapter 4.1 --- The Relaxed Master Problem --- p.30 / Chapter 4.2 --- The Feasibility Pump Method --- p.32 / Chapter 4.3 --- A-BARN Algorithm For Solving The JBAPC Problem --- p.34 / Chapter 5 --- Computational Results --- p.36 / Chapter 5.1 --- Global Optimality And Convergence --- p.36 / Chapter 5.2 --- Average Convergence Time --- p.37 / Chapter 5.3 --- Trade-off Between Performance And Convergence Time --- p.38 / Chapter 5.4 --- Average Algorithm Performance Of BARN and A-BARN --- p.39 / Chapter 6 --- Discussions --- p.47 / Chapter 6.1 --- Resource Allocation In The Uplink Multi-cell Networks --- p.47 / Chapter 6.2 --- JBAPC Problem In The Uplink Multi-cell Networks --- p.48 / Chapter 7 --- Conclusion --- p.50 / Chapter 7.1 --- Conclusion Of This Thesis --- p.50 / Chapter 7.2 --- Future Work --- p.51 / Chapter A --- The Proof --- p.52 / Chapter A.l --- Proof of Lemma 1 --- p.52 / Chapter A.2 --- Proof of Lemma 3 --- p.55 / Bibliography --- p.58

This study is concerned with the problem of resource-constrained project scheduling which includes splittable and nonsplittable jobs, renewable and nonrenewable resources, variation in resource availabi1ity, time-resource tradeoff, time-cost tradeoff, and multiple objectives. The problem is formulated as a zero-one integer programming model. A specialized solution technique is developed for the preemptive goal programming, resource-constrained project. scheduling problem for time, cost, and resource leveling objectives. In addition, single objective algorithms are also provided for the time, cost, and resource leveling objectives. These algorithms are based on the idea of the implicit enumeration process, and use the special structures of the problem to expedite the search process. Computer-generated problems are used to test each of the single objective algorithms. The results show that the algorithms give optimal solutions to tested problems with time and cost objectives using a reasonable computation time; however, heuristic solutions are more feasible for problems with resource leveling objective. The multiple objective algorithm is illustrated through application to a warehouse project problem. / Graduation date: 1993