liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
Revisiting Optimal Link Activation and Minimum-Time Scheduling in Wireless Networks
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology.
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: urn:nbn:se:liu:diva-112449ISBN: 978-91-7519-172-0 (print)OAI: oai:DiVA.org:liu-112449DiVA: diva2:766500
Supervisors
Available from: 2014-11-27 Created: 2014-11-27 Last updated: 2014-11-27Bibliographically approved
List of papers
1. 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, 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
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: 2017-12-05
2. 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, Vol. 3, no 3, 322-331 p.Article in journal (Other academic) Published
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-11-25Bibliographically approved
3. 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
2017 (English)In: IEEE Transactions on Mobile Computing, ISSN 1536-1233, E-ISSN 1558-0660, Vol. 16, no 2, 408-421 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, 2017
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
Note

Funding agencies: Swedish Research Council; EU FP7 Marie Curie [324515, 329313]; National Science Foundation [CCF-0728966, CCF-1420651]; ONR [N000141410107]

Available from: 2014-11-27 Created: 2014-11-27 Last updated: 2017-12-05Bibliographically approved

Open Access in DiVA

omslag(3051 kB)28 downloads
File information
File name COVER01.pdfFile size 3051 kBChecksum SHA-512
b2c1f09be70a716877c18468505aad29c0a3a74dd65b282018d63ccadfa528becf20e93e3c656981d891eae510e90a4f765a30c0182a8f2846c654058334c1b1
Type coverMimetype application/pdf

Authority records BETA

He, Qing

Search in DiVA

By author/editor
He, Qing
By organisation
Communications and Transport SystemsThe Institute of Technology
Communication SystemsTelecommunications

Search outside of DiVA

GoogleGoogle Scholar
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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 155 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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