Nicolas Schabanel's PhD Thesis

[ English: abstract keywords download | Français : résumé mots-clés téléchargement | Homepage ]

  
 

En français

« Algorithmes d'approximation pour les télécommunications sans fil:
Ordonnancement pour la dissémination de données et
Allocation statique de fréquences »

Directeurs de thèse: Claire Kenyon and Stéphane Ubéda (directeur local)

Soutenue le 21 janvier 2000 à l'École Normale Supérieure de Lyon, après avis de Michel Habib, Philippe Jacquet et Sanjeev Khanna, devant la commission d'examen formée de Michel Habib, Philippe Jacquet, Claire Kenyon, Sanjeev Khanna, Yves Robert et Stéphane Ubéda.

 
 

Résumé

Cette thèse étudie deux problèmes issus des télécommunications: la dissémination de données et l'allocation de fréquences.

La dissémination de données est une réponse apportée à la surcharge des réseaux et serveurs d'information. Le fait est que la plupart des clients demande la plupart du temps les mêmes informations. Aussi, afin d'éviter de saturer à la fois le serveur et le réseau avec la diffusion des pages les plus populaires, l'approche de la dissémination propose de réserver un certain nombre de canaux d'émission à la diffusion systématique des informations les plus populaires. Ces canaux (typiquement Hertzien, TV par câble,...) sont accessibles en simultané par tous les clients. Le problème est alors d'ordonnancer la diffusion des différentes pages d'information. Un client, intéressé par l'une de ces pages, n'émet pas de requête mais se connecte sur ces canaux réservés et attend que l'information qui l'intéresse soit diffusée. Il s'agit donc de trouver un ordonnancement qui minimise l'attente moyenne des clients.

Ce problème est un problème de minimisation quadratique, qui modélise également d'autres problèmes d'ordonnancement tels la planification de maintenances de machines ou le réapprovisionnement de stocks. Cette thèse démontre que trouver un ordonnancement optimal est NP-dur en général, et propose des algorithmes d'approximation avec garanties de performance prouvées: un schéma d'approximation pour le cas des messages de longueur uniforme, et deux approximations à un facteur constant pour le cas où les messages ont des longueurs différentes, avec et sans préemption.
L'allocation de fréquences consiste à allouer des fréquences aux transmetteurs d'un réseau cellulaire de sorte à ce que deux transmetteurs n'entrent jamais en interférence. Dans cette thèse, nous proposons un algorithme d'approximation avec garantie de performance pour le cas NP-dur où les transmetteurs sont disposés suivant la grille triangulaire.

  
 

Mots-clés

Algorithmique, Optimisation combinatoire, Approximation, Algorithmes randomisés et dérandomisation, Télécommunications sans fil, Dissémination de données, Multicoloriage.

  
 

Options de téléchargement

  • En totalité ps gzipé/pdf*
  • Par chapitre:
    • Couvertures ps/pdf*
    • Table des matières ps/pdf*
    • Introduction ps/pdf*
    • Première Partie: Ordonnancement pour la dissémination de données
      • Chapitre 1.Ordonnancements pour la dissémination de données ps/pdf*
      • Chapitre 2. Dissémination de messages de longueurs non-uniformes ps/pdf*
      • Chapitre 3. Dissémination préemptive de messages de longueurs non-uniformes ps/pdf*
      • Chapitre 4. Un schéma d'approximation pour le cas des messages de longueurs uniformes ps/pdf*
      • Chapitre 5. Résolution des problèmes de minisation définissant nos minorants ps/pdf*
      • Conclusion, bibliographie et index de la première partie ps/pdf*
    • Deuxième Partie: Allocation statique de fréquences
      • Chapitre 6. Allocation statique de fréquences sur la grille triangulaire ps/pdf*

* Certaines figures n'ont pas supporté la conversion en pdf...

[ Back to homepage ]

  
 

In English

« Approximation algorithms for wireless networks:
Scheduling data dissemination and
Static frequency assignment »

PhD Advisors: Claire Kenyon and Stéphane Ubéda (local advisor)

Defended on January 21, 2000 at the École Normale Supérieure de Lyon, after reviewing by Michel Habib, Philippe Jacquet and Sanjeev Khanna, in front of the jury composed by Michel Habib, Philippe Jacquet, Claire Kenyon, Sanjeev Khanna, Yves Robert et Stéphane Ubéda.

  
 

Abstract

This thesis addresses two problems issued from telecommunication: data dissemination and frequency planning.

Data dissemination is an answer to reduce the load of information servers and networks. A fact is that most of the clients require most of the time the same information pages. In order to reduce the server and network loads due to the broadcast of the most popular pages, data dissemination reserves some special channels to broadcast systematically the most popular pages, obliviously from the effective requests. Those channels (typically wireless, cable TV,...) can be monitored simultaneously by all the clients. The problem is now to schedule the broadcasts of the different messages over these special channels. A client interested in one of these pages does not send a request but connects and monitors the special channels until the information he is interested in is broadcast. The problem consists in finding a schedule that minimizes the expected waiting time of the clients.

This problem is a quadratic minimization problem that also models other scheduling problems such as machine maintenance scheduling or stocks supplying. In this thesis, this problem is shown to be NP-hard in general and we give approximation algorithms with proven performance guarantees: a polynomial approximation scheme for the case where all the messages have the same length, and two constant factor approximations for the case where the messages have different lengths, with and without preemption.

Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interferes. In this thesis, we propose an approximation algorithm with proven performance guaranty for the NP-hard case where the transmitter are placed on the triangular lattice.

  
 

Keywords

Algorithmic, Combinatorial optimization, Approximation, Randomized algorithms and derandomization, Wireless telecommunication, Data dissemination and push-based systems, Multicoloring.

  
 

Dowload options

Thesis are written in French in France...

  • The complete document gziped ps/pdf*
  • by chapter:
    • Cover pages ps/pdf*
    • Table of contents ps/pdf*
    • Introduction ps/pdf*
    • First part: Scheduling data dissemination
      • Chapter 1. Scheduling data dissemination ps/pdf*
      • Chapter 2. Data dissemination with non-uniform transmission times ps/pdf*
      • Chapter 3. Preemptive data dissemination ps/pdf*
      • Chapter 4. A polynomial-time approximation scheme for data dissemination with uniform transmission time ps/pdf*
      • Chapter 5. Solving the non-linear problems that yield our lower bounds ps/pdf*
      • Conclusion, bibliography and index of the first part ps/pdf*
    • Second part: Static frequency planning
      • Chapter 6. Static frequency planning on the triangular lattice ps/pdf*

* Some figures did not convert properly to pdf...

[ Back to homepage ]

  
  Dernière mise à jour le 23 mars, 2006 10:45