Motivated by the fact that the contention graph associated with ICN is a Markov random field (MRF) with respect to the probability distribution of its system states, and that the belief propagation algorithm (BP) is an efficient way to solve "inference" problems in graphical models such as MRF, we study how to apply BP algorithms to the analysis and control of CSMA wireless networks. We investigate three applications: (1) computation of link throughputs given link access intensities; (2) computation of link access intensities required to meet target link throughputs; and (3) optimization of network utility via the control of link access intensities. We show that BP solves the three problems with exact results in tree networks and has manageable computation errors in a network with loopy contention graph. In particular, we show how a generalized version of BP, GBP, can be designed to solve the three problems above with higher accuracy. Importantly, we show how the BP and GBP algorithms can be implemented in a distributed manner, making them useful in practical CSMA network operation. / The above studies focus on computation and control of "equilibrium" link throughputs. Besides throughputs, an important performance measure in CSMA networks is the propensity for starvation. In this thesis, we show that links in CSMA wireless networks are particularly susceptible to "temporal" starvation. Specifically, certain links may have good equilibrium throughputs, yet they can still receive no throughput for extended periods from time to time. We develop a "trap theory" to analyze temporal throughput fluctuations. The trap theory serves two functions. First, it allows us to derive new mathematical results that shed light on the transient behavior of CSMA networks. Second, we can develop automated analytical tools for computing the "degrees of starvation" for CSMA networks to aid network design. We believe that the ability to identify and characterize temporal starvation as established in this thesis will serve as an important first step toward the design of effective remedies for it. / This thesis investigates the performance and control of CSMA wireless networks. To this end, an analytical model of CSMA wireless networks that captures the essence of their operation is important. We propose an Ideal CSMA Network (ICN) model to characterize the dynamic of the interactions and dependency of links in CSMA wireless networks. This model allows us to address various issues related to performance and control of CSMA networks. / We show that the throughput distributions of links in ICN can be computed from a continuous-time Markov chain and are insensitive to the distributions of the transmission time (packet duration) and the backoff countdown time in the CSMA MAC protocol given the ratio of their means rho, referred to as the access intensity. An outcome of the ICN model is a Back-of-the-Envelope (BoE) approximate computation method that allows us to bypass complicated stochastic analysis to compute link throughputs in many network configurations quickly. The BoE computation method emerges from ICN in the limit rho → infinity. Our results indicate that BoE is a good approximation technique for modest-size networks such as those typically seen in 802.11 deployments. Beyond serving as the foundation for BoE, the theoretical framework of ICN is also a foundation for understanding and optimization of large CSMA networks. / Kai, Caihong. / Adviser: Soung Chang Liew. / Source: Dissertation Abstracts International, Volume: 73-03, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 180-183). / 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.
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_344893 |
| Date | January 2010 |
| Contributors | Kai, Caihong., Chinese University of Hong Kong Graduate School. Division of Information Engineering. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, theses |
| Format | electronic resource, microform, microfiche, 1 online resource (xvi, 183 leaves : ill.) |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.002 seconds