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

Direct link
BETA
Publications (8 of 8) Show all publications
He, Q., Yuan, D. & Ephremides, A. (2018). Optimal Link Scheduling for Age Minimization in Wireless Systems. IEEE Transactions on Information Theory, 64(7), 5381-5394
Open this publication in new window or tab >>Optimal Link Scheduling for Age Minimization in Wireless Systems
2018 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 64, no 7, p. 5381-5394Article in journal (Refereed) Published
Abstract [en]

Information age is a recently introduced metric to represent the freshness of information in communication systems. We investigate age minimization in a wireless network and propose a novel approach of optimizing the scheduling strategy to deliver all messages as fresh as possible. Specifically, we consider a set of links that share a common channel. The transmitter at each link contains a given number of packets with time stamps from an information source that generated them. We address the link transmission scheduling problem with the objective of minimizing the overall age. This minimum age scheduling problem (MASP) is different from minimizing the time or the delay for delivering the packets in question. We model the MASP mathematically and prove it is NP-hard in general. We also identify tractable cases as well as optimality conditions. An integer linear programming formulation is provided for performance benchmarking. Moreover, a steepest age descent algorithm with better scalability is developed. Numerical study shows that, by employing the optimal schedule, the overall age is significantly reduced in comparison to other scheduling strategies.

Place, publisher, year, edition, pages
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 2018
Keywords
Information age; link scheduling; optimization; wireless networks
National Category
Communication Systems
Identifiers
urn:nbn:se:liu:diva-149703 (URN)10.1109/TIT.2017.2746751 (DOI)000435979500038 ()
Note

Funding Agencies|EC Marie Curie Actions Projects MESH-WISE [324515]; Career LTE [329313]; National Science Foundation [CCF-0728966, CCF-1420651]; ONR [N000141410107]

Available from: 2018-07-24 Created: 2018-07-24 Last updated: 2018-08-14
He, Q., Yuan, D. & Ephremides, A. (2017). Maximum Link Activation with Cooperative Transmission and Interference Cancellation in Wireless Networks. Paper presented at 2014 IEEE 25th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), September 2-5, Washington DC, DC, USA. IEEE Transactions on Mobile Computing, 16(2), 408-421
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, p. 408-421Article in journal (Refereed) 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)000393808500009 ()
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: 2018-08-14Bibliographically approved
He, Q., Angelakis, V., Ephremides, A. & Yuan, D. (2016). Polynomial Complexity Minimum-Time Scheduling in a Class of Wireless Networks. IEEE Transactions on Control of Network Systems, 3(3), 322-331
Open this publication in new window or tab >>Polynomial Complexity Minimum-Time Scheduling in a Class of Wireless Networks
2016 (English)In: IEEE Transactions on Control of Network Systems, ISSN 2325-5870, Vol. 3, no 3, p. 322-331Article 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), 2016
Keywords
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)000384701100010 ()
Note

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

Available from: 2014-11-27 Created: 2014-11-27 Last updated: 2019-07-15Bibliographically approved
Karipidis, E., Yuan, D., He, Q. & Larsson, E. G. (2015). Max-Min Power Control in Wireless Networks With Successive Interference Cancelation. IEEE Transactions on Wireless Communications, 14(11), 6269-6282
Open this publication in new window or tab >>Max-Min Power Control in Wireless Networks With Successive Interference Cancelation
2015 (English)In: IEEE Transactions on Wireless Communications, ISSN 1536-1276, E-ISSN 1558-2248, Vol. 14, no 11, p. 6269-6282Article in journal (Refereed) Published
Abstract [en]

We consider a wireless network comprising a number of cochannel (hence mutually interfering) links. We study the power control problem of maximizing the rate that all links can simultaneously support under a novel setup, where receivers have interference cancelation (IC) capabilities. The problem of allocating the transmitting power is intertwined with determining the links on which receivers can perform IC and the order of cancelations. We provide and prove the theoretical results of the problem complexity and structural properties. For the problem solution, we propose a mixed-integer linear programming framework that enables jointly determining the optimal power and the IC patterns using off-the-shelf algorithms. This allows for the accurate assessment of the potential of IC for power control. Extensive numerical results are presented for performance evaluation, demonstrating the benefit of deploying IC in power control.

Place, publisher, year, edition, pages
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 2015
Keywords
Optimization; power control; successive interference cancellation; wireless networks
National Category
Telecommunications Communication Systems Signal Processing
Identifiers
urn:nbn:se:liu:diva-123332 (URN)10.1109/TWC.2015.2451653 (DOI)000365046100029 ()
Note

Funding Agencies|Swedish Research Council (VR); Swedish Foundation of Strategic Research (SSF); Excellence Center at Linkoping-Lund in Information Technology (ELLIIT); European FP7 Marie Curie Project [324515, 329313]

Available from: 2015-12-14 Created: 2015-12-11 Last updated: 2018-08-14
Angelakis, V., Ephremides, A., He, Q. & Yuan, D. (2014). Minimum-Time Link Scheduling for Emptying Wireless Systems: Solution Characterization and Algorithmic Framework. IEEE Transactions on Information Theory, 60(2), 1083-1100
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, p. 1083-1100Article 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
Keywords
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: 2018-08-14
He, Q. (2014). Revisiting Optimal Link Activation and Minimum-Time Scheduling in Wireless Networks. (Licentiate dissertation). Linköping: Linköping University Electronic Press
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. p. 24
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: 2018-08-14Bibliographically approved
Angelakis, V., Ephremides, A., He, Q. & Yuan, D. (2012). On Emptying a Wireless Network in Minimum Time. In: 2012 IEEE International Symposium on Information Theory Proceedings (ISIT): . Paper presented at IEEE International Symposium on Information Theory Proceedings (ISIT), Cambridge, MA, USA, 1-6 July 2012 (pp. 2671-2675). Piscataway, NJ, USA: IEEE
Open this publication in new window or tab >>On Emptying a Wireless Network in Minimum Time
2012 (English)In: 2012 IEEE International Symposium on Information Theory Proceedings (ISIT), Piscataway, NJ, USA: IEEE , 2012, p. 2671-2675Conference paper, Published paper (Refereed)
Abstract [en]

We consider N transmitter-receiver pairs that share a wireless channel and we address the problem of obtaining a schedule for activating subsets of these links so as to empty the transmitter queues in minimum time. Our aim is to provide theoretical insights for the optimality characterization of the problem, using both a cross-layer model formulation, which takes into account the effect of interference on achievable transmission rates, as well as a collision-based model, which does not incorporate the physical layer realities into the problem. We present the basic linear programming formulation of the problem and establish that the optimal schedule need not consist of more than N subset activation frames. We then prove that the problem is NP-hard for all reasonable continuous rate functions. Finally, we obtain sufficient and/or necessary conditions for optimality in a number of special cases.

Place, publisher, year, edition, pages
Piscataway, NJ, USA: IEEE, 2012
Series
IEEE International Symposium on Information Theory. Proceedings, ISSN 2157-8095
Keywords
interference; optimality; scheduling; wireless networks
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-96567 (URN)10.1109/ISIT.2012.6284004 (DOI)000312544302154 ()978-1-4673-2580-6 (ISBN)978-1-4673-2578-3 (ISBN)
Conference
IEEE International Symposium on Information Theory Proceedings (ISIT), Cambridge, MA, USA, 1-6 July 2012
Available from: 2013-08-21 Created: 2013-08-20 Last updated: 2018-08-14Bibliographically approved
He, Q., Angelakis, V., Ephremides, A. & Yuan, D. (2012). Revisiting Minimum-Length Scheduling in Wireless Networks: An Algorithmic Framework. In: International Symposium on Information Theory and its Applications (ISITA), 2012: . Paper presented at International Symposium on Information Theory and its Applications (ISITA),Honolulu, HI, USA, 28-31 Oct. 2012 (pp. 506-510). Piscataway, NJ, USA: IEEE
Open this publication in new window or tab >>Revisiting Minimum-Length Scheduling in Wireless Networks: An Algorithmic Framework
2012 (English)In: International Symposium on Information Theory and its Applications (ISITA), 2012, Piscataway, NJ, USA: IEEE , 2012, p. 506-510Conference paper, Published paper (Refereed)
Abstract [en]

We consider the problem of constructing the minimum length schedule required to empty a wireless network with queues of given size. In a recent work we have provided new fundamental insights towards its structure and complexity. Motivated by the problem computational complexity, we demonstrate here how a one-size-fits-all optimal algorithm cannot be expected and introduce a framework that decomposes the problem in two core sub-problems: Selecting which subset of wireless links to activate and for how long. This modular approach enables the construction of algorithms that can yield solutions ranging from simple and intuitive to exact optimal. We provide a comprehensive set of design strategies and results to elucidate how different combinations within the framework modules can be used to approach optimality.

Place, publisher, year, edition, pages
Piscataway, NJ, USA: IEEE, 2012
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-96522 (URN)000320850700106 ()978-1-4673-2521-9 (ISBN)
Conference
International Symposium on Information Theory and its Applications (ISITA),Honolulu, HI, USA, 28-31 Oct. 2012
Available from: 2013-08-21 Created: 2013-08-20 Last updated: 2018-08-14Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-6213-8561

Search in DiVA

Show all publications