Change search
ReferencesLink to record
Permanent link

Direct link
A Comprehensive Analysis of Optimal Link Scheduling for Emptying a Wireless Network
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
2016 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Wireless communications have become an important part of modern life. The ubiquitous wireless networks and connectivities generate exponentially increasing data traffic. In view of this, wireless network optimization, which aims at utilizing the limited resource, especially spectrum and energy, as efficiently as possible from a network perspective, is essential for performance improvement and sustainable development of wireless communications.

In the dissertation, we focus on a fundamental problem of wireless network optimization, link scheduling, as well as its subproblem, link activation. The problem type arises because of the nature of wireless media and hence it is of relevance to a wide range of networks with multiple access. We freshen these classic problems up by novel extensions incorporating new technologies of interference management or with new performance metrics. We also revisit the problems in their classic setup to gain new theoretical results and insights for problem-solving. Throughout the study, we consider the problems with a general setup, such that the insights presented in this dissertation are not constrained to a specific technology or network type. Since link activation and scheduling are key elements of access coordination in wireless communications, the study opens up new approaches that significantly improve network performance, and eventually benefit practical applications.

The dissertation consists of five research papers. The first paper addresses maximum link activation with cooperative transmission and interference cancellation. Papers II and III investigate the minimum-time link scheduling problem in general and a particular class of networks, respectively. In Paper IV, we consider the scheduling problem of emptying a network in its broad form and provide a general optimality condition. In Paper V, we study the scheduling problem with respect to age of information.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2016. , 40 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1786
National Category
Information Systems Computer Engineering Mathematics Computer Systems
Identifiers
URN: urn:nbn:se:liu:diva-131359DOI: 10.3384/diss.diva-131359ISBN: 9789176856949 (Print)OAI: oai:DiVA.org:liu-131359DiVA: diva2:970925
Public defence
2016-10-18, TP2, Täppan, Campus Norrköping, Norrköping, 10:15 (English)
Opponent
Supervisors
Funder
EU, FP7, Seventh Framework ProgrammeSwedish Research CouncileLLIIT - The Linköping‐Lund Initiative on IT and Mobile Communications
Available from: 2016-09-15 Created: 2016-09-15 Last updated: 2016-09-16Bibliographically approved
List of papers
1. Maximum Link Activation with Cooperative Transmission and Interference Cancellation in Wireless Networks
Open this publication in new window or tab >>Maximum Link Activation with Cooperative Transmission and Interference Cancellation in Wireless Networks
2016 (English)In: IEEE Transactions on Mobile Computing, ISSN 1536-1233, E-ISSN 1558-0660, 1-1 p.Article in journal (Other academic) Published
Abstract [en]

We address the maximum link activation problem in wireless networks with new features, namely when the transmitters can perform cooperative transmission, and the receivers are able to perform successive interference cancellation. In this new problem setting, which transmitters should transmit and to whom, as well as the optimal cancellation patterns at the receivers, are strongly intertwined. We present contributions along three lines. First, we provide a thorough tractability analysis, proving the NP-hardness as well as identifying tractable cases. Second, for benchmarking purposes, we deploy integer linear programming for achieving global optimum using off-theshelf optimization methods. Third, to overcome the scalability issue of integer programming, we design a sub-optimal but efficient optimization algorithm for the problem in its general form, by embedding maximum-weighted bipartite matching into local search. Numerical results are presented for performance evaluation, to validate the benefit of cooperative transmission and interference cancellation for maximum link activation and to demonstrate the effectiveness of the proposed algorithm.

Place, publisher, year, edition, pages
IEEE, 2016
National Category
Communication Systems Telecommunications
Identifiers
urn:nbn:se:liu:diva-112447 (URN)10.1109/TMC.2016.2546906 (DOI)
Conference
2014 IEEE 25th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), September 2-5, Washington DC, DC, USA
Available from: 2014-11-27 Created: 2014-11-27 Last updated: 2016-09-19Bibliographically approved
2. Minimum-Time Link Scheduling for Emptying Wireless Systems: Solution Characterization and Algorithmic Framework
Open this publication in new window or tab >>Minimum-Time Link Scheduling for Emptying Wireless Systems: Solution Characterization and Algorithmic Framework
2014 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, Vol. 60, no 2, 1083-1100 p.Article in journal (Refereed) Published
Abstract [en]

We consider a set of transmitter-receiver pairs, or links, that share a wireless medium and address the problem of emptying backlogged queues with given initial size at the transmitters in minimum time. The problem amounts to determining activation subsets of links, and their time durations, to form a minimum-time schedule. Scheduling in wireless networks has been studied under various formulations before. In this paper, we present fundamental insights and solution characterizations that include: 1) showing that the complexity of the problem remains high for any continuous and increasing rate function; 2) formulating and proving sufficient and necessary optimality conditions of two baseline scheduling strategies that correspond to emptying the queues using one-at-a-time or all-at-once strategies; and 3) presenting and proving the tractability of the special case in which the transmission rates are functions only of the cardinality of the link activation sets. These results are independent of physical-layer system specifications and are valid for any form of rate function. We then develop an algorithmic framework for the solution to this problem. The framework encompasses exact as well as sub-optimal, but fast, scheduling algorithms, all under a unified principle design. Through computational experiments, we finally investigate the performance of several specific algorithms from this framework.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2014
Keyword
Algorithm; optimality; scheduling; wireless networks
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-104836 (URN)10.1109/TIT.2013.2292065 (DOI)000330286100022 ()
Available from: 2014-02-28 Created: 2014-02-28 Last updated: 2016-09-15
3. Polynomial Complexity Minimum-Time Scheduling in a Class of Wireless Networks
Open this publication in new window or tab >>Polynomial Complexity Minimum-Time Scheduling in a Class of Wireless Networks
2015 (English)In: IEEE Transactions on Control of Network Systems, ISSN 2325-5870 (Print), 2325-5870 (online), Vol. 3, no 3, 322-331 p.Article in journal (Other academic) Epub ahead of print
Abstract [en]

We consider a wireless network with a set of transmitter-receiver pairs, or links, that share a common channel, and address the problem of emptying finite traffic volume from the transmitters in minimum time. This, so called, minimum-time scheduling problem has been proved to be NP-hard in general. In this paper, we study a class of minimum-time scheduling problems in which the link rates have a particular structure. We show that global optimality can be reached in polynomial time and derive optimality conditions. Then we consider a more general case in which we apply the same approach and obtain an approximation as well as lower and upper bounds to the optimal solution. Simulation results confirm and validate our approach.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2015
Keyword
algorithm, interference, optimality, scheduling, wireless networks
National Category
Communication Systems Telecommunications
Identifiers
urn:nbn:se:liu:diva-112446 (URN)10.1109/TCNS.2015.2512678 (DOI)
Note

At the time for thesis presentation publication was in status: Manuscript

Available from: 2014-11-27 Created: 2014-11-27 Last updated: 2016-09-16Bibliographically approved
4. A general optimality condition of link scheduling for emptying a wireless network
Open this publication in new window or tab >>A general optimality condition of link scheduling for emptying a wireless network
2016 (English)Conference paper (Refereed)
Abstract [en]

We consider link scheduling in wireless networks for emptying the queues of the source nodes, and provide a unified mathematical formulation that accommodates all meaningful settings of link transmission rates and network configurations. We prove that, any scheduling problem is equivalent to solving a convex problem defined over the convex hull of the rate region. Based on the fundamental insight, a general optimality condition is derived, that yields a unified treatment of optimal scheduling. Furthermore, we demonstrate the implications and usefulness of the result. Specifically, by applying the theoretical insight to optimality characterization and complexity analysis of scheduling problems, we can both unify and extend previously obtained results.

Place, publisher, year, edition, pages
IEEE, 2016
Series
, IEEE International Symposium on Information Theory. Proceedings, ISSN 2157-8095 (Print), 2157-8117 (online) ; 2016
Keyword
convex programming;radio links;radio networks;telecommunication scheduling;convex hull;convex problem;general optimality condition;link scheduling;link transmission rates;network configurations;optimal scheduling;source nodes;wireless network;Complexity theory;Information theory;Interference;Optimal scheduling;Processor scheduling;Scheduling;Wireless networks;complexity;optimality;scheduling;wireless networks
National Category
Computer Engineering Information Systems Software Engineering
Identifiers
urn:nbn:se:liu:diva-131357 (URN)10.1109/ISIT.2016.7541538 (DOI)
Conference
IEEE International Symposium on Information Theory (ISIT), 2016, Universitat Pompeu Fabra, Barcelona, Spain, July l0-l5, 2016
Available from: 2016-09-15 Created: 2016-09-15 Last updated: 2016-09-15Bibliographically approved

Open Access in DiVA

Comprehensive Analysis of Optimal Link Scheduling for Emptying a Wireless Network(360 kB)17 downloads
File information
File name FULLTEXT01.pdfFile size 360 kBChecksum SHA-512
1f75014fd8a7a09128d8c0a083db855d3491c793cc7739e810fa9aec30a66e2946569b979c47e0705797f4deb729d016918ab4eb69452cd2d030587b95e60fc7
Type fulltextMimetype application/pdf
omslag(98 kB)7 downloads
File information
File name COVER01.pdfFile size 98 kBChecksum SHA-512
a30ea004a1d00f94df4a56e01daee28660dfbb6ef1c8dace75ed881e3ebf75aef4c1a4f0e08f16f7e81e816e676df4e6f1346513c1c7b7d9bb84b33012484353
Type coverMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
He, Qing
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
Information SystemsComputer EngineeringMathematicsComputer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 17 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 143 hits
ReferencesLink to record
Permanent link

Direct link