Online Energy-Efficient Packet Scheduling for a Common Deadline With and Without Energy Harvesting

被引：20

作者：

Deshmukh, Aditya ^{[1
]}

Vaze, Rahul ^{[2
]}

机构：

[1] Indian Inst Technol Madras, Dept Elect Engn, Madras 600036, Tamil Nadu, India

[2] Tata Inst Fundamental Res, Sch Technol & Comp Sci, Bombay 400005, Maharashtra, India

来源：

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS | 2016年 / 34卷 / 12期

关键词：

Energy harvesting; online algorithms; scheduling with deadlines; TRANSMISSION POLICIES; COMMUNICATION-SYSTEM; GUARANTEES; NETWORKS; CHANNELS; LINK;

D O I：

10.1109/JSAC.2016.2611899

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

The problem of online packet scheduling to minimize the required conventional grid energy for transmitting a fixed number of packets given a common deadline is considered. The total number of packets arriving within the deadline is known, but the packet arrival times are unknown, and can be arbitrary. The proposed algorithm tries to finish the transmission of each packet assuming that all future packets are going to arrive at equal time intervals within the left-over time. The proposed online algorithm is shown to have competitive ratio that is logarithmic in the number of packet arrivals. The hybrid energy paradigm is also considered, where in addition to grid energy, energy is also available via extraction from renewable sources. The objective here is to minimize the grid energy use. A suitably modified version of the previous algorithm is also shown to have competitive ratio that is logarithmic in the number of packet arrivals.

引用

页码：3661 / 3674

页数：14

共 24 条

[1] Structural properties of optimal transmission policies over a randomly varying channel [J].

Agarwal, Mukul ;

Borkar, Vivek S. ;

Karandikar, Abhay .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2008, 53 (06) :1476-1491

[2] Optimal Packet Scheduling on an Energy Harvesting Broadcast Link [J].

Antepli, Mehmet Akif ;

Uysal-Biyikoglu, Elif ;

Erkal, Hakan .

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2011, 29 (08) :1721-1731

[3] On-line routing of virtual circuits with applications to load balancing and machine scheduling [J].

Aspnes, J ;

Azar, Y ;

Fiat, A ;

Plotkin, S ;

Waarts, O .

JOURNAL OF THE ACM, 1997, 44 (03) :486-504

[4] ONLINE LOAD BALANCING [J].

AZAR, Y ;

BRODER, AZ ;

KARLIN, AR .

THEORETICAL COMPUTER SCIENCE, 1994, 130 (01) :73-84

[5] Optimal Power-Delay Tradeoffs in Fading Channels-Small-Delay Asymptotics [J].

Berry, Randall A. .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2013, 59 (06) :3939-3952

[6] Energy efficient scheduling with individual packet delay constraints: Offline and Online results [J].

Chen, Wanshi ;

Neely, Michael J. ;

Mitra, Urbashi .

INFOCOM 2007, VOLS 1-5, 2007, :1136-+

[7] Delay-Aware BS Discontinuous Transmission Control and User Scheduling for Energy Harvesting Downlink Coordinated MIMO Systems [J].

Cui, Ying ;

Lau, Vincent K. N. ;

Wu, Yueping .

IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2012, 60 (07) :3786-3795

[8]

Göbel O, 2014, LECT NOTES COMPUT SC, V8573, P508

[9]

Gómez-Vilardebò J, 2015, IEEE INT WORK SIGN P, P11, DOI 10.1109/SPAWC.2015.7226990

[10]

Gomez-Vilardebo J, 2014, 2014 IEEE GLOBAL CONFERENCE ON SIGNAL AND INFORMATION PROCESSING (GLOBALSIP), P123, DOI 10.1109/GlobalSIP.2014.7032091

← 1 2 3 →