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.
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_344895 |
| Date | January 2010 |
| Contributors | Shao, Ziyu., 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 (xi, 140 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.0018 seconds