Faster Algorithms for Minimum-Energy Scheduling of Wireless Data Transmissions

Abstract : This paper considers the problem of minimizing the energy used in transmitting a given sequence of packets with specied completion deadlines from a node in a wireless packet network. The packets have to to be transmitted in rst-in-rst-out order. Packets can be destined to dierent receivers. The channel conditions to each receiver (and so the energy per bit needed) can be dierent and assumed to be known. An offline algorithm for the case where all the packets have a common completion deadline was presented in [3, 4], and was used as the basis for an online scheduling algorithm. In this paper, we present a faster offline algorithm for the more general case of dierent packet completion deadlines. The presented algorithm has a running time of O(M2), where M is the length of the given packet sequence, provided the inverse of the derivative of the energy function is invertible in closed form. Otherwise, the running time depends on the number of receivers as well.
Type de document :
Communication dans un congrès
WiOpt'03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Mar 2003, Sophia Antipolis, France. 9 p., 2003
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00466708
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 25 mars 2010 - 12:06:12
Dernière modification le : jeudi 25 mars 2010 - 14:32:06
Document(s) archivé(s) le : jeudi 16 septembre 2010 - 10:34:22

Fichier

keslassy-faster.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00466708, version 1

Collections

Citation

Isaac Keslassy, Murali Kodialam, T.V. Lakshman. Faster Algorithms for Minimum-Energy Scheduling of Wireless Data Transmissions. WiOpt'03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Mar 2003, Sophia Antipolis, France. 9 p., 2003. 〈inria-00466708〉

Partager

Métriques

Consultations de la notice

147

Téléchargements de fichiers

53