Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Minimum-Time Link Scheduling for Emptying Wireless Systems: Solution Characterization and Algorithmic Framework
Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology.
2014 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, 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. Vol. 60, no 2, 1083-1100 p.
Keyword [en]
Algorithm; optimality; scheduling; wireless networks
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-104836DOI: 10.1109/TIT.2013.2292065ISI: 000330286100022OAI: oai:DiVA.org:liu-104836DiVA: diva2:699612
Available from: 2014-02-28 Created: 2014-02-28 Last updated: 2017-12-05
In thesis
1. Revisiting Optimal Link Activation and Minimum-Time Scheduling in Wireless Networks
Open this publication in new window or tab >>Revisiting Optimal Link Activation and Minimum-Time Scheduling in Wireless Networks
2014 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

With the popularity of wireless communications in the last two decades, data traffic is exponentially increasing and requests high speed transmission. However, the resources, in particular, spectrum and energy, are limited. Therefore, network optimization with the objective of utilizing radio resource as efficiently as possible is crucial to the sustainable development of wireless communications.

Link activation and scheduling are two classic problems of access coordination and resource allocation for multiple links that share a common channel. The problems originate from the broadcast nature of wireless media and are of significance in more complicated cross-layer optimization problems. Although there is a rich amount of literature, the problems remain challenging and are extended by novel setups incorporating new interference management technologies.

In this thesis, we revisit these two fundamental problems with the main methods of mathematical modelling and applied optimization. The first two papers address the scheduling problem that amounts to emptying a given amount of data in minimum time. We derive theoretical insights including problem complexity, optimality conditions, as well as problem approximation and algorithmic framework, in general and for a class of networks with a particular structure. In the third paper, we incorporate cooperative transmission and interference cancellation with maximum link activation. Theoretical results and algorithm development are provided. Simulation study shows the new setup brings significant performance gain in comparison with the conventional approach.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2014. 24 p.
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1695
National Category
Communication Systems Telecommunications
Identifiers
urn:nbn:se:liu:diva-112449 (URN)978-91-7519-172-0 (ISBN)
Supervisors
Available from: 2014-11-27 Created: 2014-11-27 Last updated: 2014-11-27Bibliographically approved
2. A Comprehensive Analysis of Optimal Link Scheduling for Emptying a Wireless Network
Open this publication in new window or tab >>A Comprehensive Analysis of Optimal Link Scheduling for Emptying a Wireless Network
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:nbn:se:liu:diva-131359 (URN)10.3384/diss.diva-131359 (DOI)9789176856949 (ISBN)
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

Open Access in DiVA

fulltext(382 kB)193 downloads
File information
File name FULLTEXT01.pdfFile size 382 kBChecksum SHA-512
2c52a6854f95a19ff4b00b8e8feea560f8f1ad3bac06d1e8ae1d9a3e3736b5800fe056865b2cd984d1a8fef374f4a8027b8ca4383c9dcacd0c7d430c16ba0dcb
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Ephremides, AnthonyHe, QingYuan, Di
By organisation
Department of Science and TechnologyThe Institute of TechnologyCommunications and Transport Systems
In the same journal
IEEE Transactions on Information Theory
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 193 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 280 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf