logo EDITE Quentin BRAMAS
Identité
Quentin BRAMAS
État académique
Thèse soutenue le 2016-10-04
Sujet: Self-organizing, Mobility Aware, Reliable and Timely Body-Area-Networks
Direction de thèse:
Laboratoire:
Voisinage
Ellipse bleue: doctorant, ellipse jaune: docteur, rectangle vert: permanent, rectangle jaune: HDR. Trait vert: encadrant de thèse, trait bleu: directeur de thèse, pointillé: jury d'évaluation à mi-parcours ou jury de thèse.
Productions scientifiques
oai:hal.archives-ouvertes.fr:hal-00866048
The Random Bit Complexity of Mobile Robots Scattering
HASH(0x7f04008c55a8)
http://hal.upmc.fr/hal-00866048 [Research Report] Université Pierre et Marie Curie. 2015Reports 2015-02-19
oai:hal.archives-ouvertes.fr:hal-00985322
Le pouvoir séparateur d'une pièce de monnaie
Nous considérons le problème qui consiste à éparpiller n robots mobiles dans un plan Euclidien, à partir d'une situation initiale quelconque où en particulier, deux robots peuvent occuper la même position. Comme ce problème n'admet pas de solution déterministe (deux robots identiques initialement à la même place ont un comportement identique et donc ne se séparent jamais), les solutions sont nécessairement probabilistes. Nous étudions le nombre de lancers de pièce de monnaie (\emph{alias} le nombre de bits aléatoires) nécessaire à une séparation totale des robots. Nous montrons tout d'abord que n log n lancers sont nécessaires pour éparpiller n robots. Puis, nous donnons une condition nécessaire et suffisante pour qu'un algorithme soit optimal en nombre de lancers. Comme il s'avère que les algorithmes existants vérifient cette condition, ils sont optimaux en nombre de lancers pour le problème de l'éparpillement. Ensuite nous étudions la complexité en temps des algorithmes d'éparpillement, lorsque la détection forte de la multiplicité (i.e., la capacité à compter le nombre de robots sur une position précise) n'est pas disponible. La séparation en temps constant étant impossible, nous présentons une famille d'algorithmes qui éparpille n robots en O(f(n)) pour toute fonction f non bornée supérieurement et, parmi cette famille, nous proposons un algorithme qui est à la fois optimal en temps et en nombre de lancers. Le détail des résultats peut être trouvé dans le rapport technique associé.
ALGOTEL 2014 -- 16èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications ALGOTEL 2014 -- 16èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunicationsconference proceeding 2014
oai:hal.archives-ouvertes.fr:hal-01144309
De la Survie Énergétique des Réseaux de Capteurs
International audience
Les applications récentes des réseaux de capteurs sans fil requièrent des appareils de petite taille, autonomes en énergie, et possédant une longue durée de vie. Il est donc crucial de simuler efficacement et fidèlement la durée de vie des capteurs au sein de ces réseaux. Les simulateurs de réseaux existants implémentent souvent des modèles simplifiés de consommation et de batterie. Par ailleurs, les modèles très réalistes de batterie, implémentés dans des simulateurs dédiés, sont trop complexes pour être utilisés pour la simulation de réseaux de capteurs de grande taille, et dont la durée à simuler peut atteindre des mois, voire des années. Dans ce papier nous présentons WiSeBat, un modèle de batterie et de consommation d'énergie optimisé pour les réseaux de capteurs, et son implémentation dans le simulateur WSNET. Nos résultats montrent que pour un surcoût de simulation minime, ce modèle permet d'obtenir une précision de 86 − 96% (contre une erreur supérieure à 2600% avec le modèle par défaut de WSNET) par rapport à un capteur réel. Dans un deuxième temps, nous utilisons WiSeBat pour comparer l'efficacité énergétique de X-MAC, ContikiMAC et 802.15.4.
ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications https://hal.archives-ouvertes.fr/hal-01144309 ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2015, Beaune, FranceConference papers 2015-06-02
oai:hal.archives-ouvertes.fr:hal-01144458
Agréger Rapidement des Données est Difficile
International audience
La première utilisation des réseaux de capteurs sans fil est l'agrégation des données collectées par chaque capteur, de manière économe en énergie. Dans ce papier, nous présentons le problème de l'agrégation des données de manière formelle dans les réseaux de capteurs dynamiques (dont la topologie évolue avec le temps). Dans les réseaux statiques de degré au plus quatre, il a déjà été prouvé que résoudre ce problème en minimisant le délai est NP-Complet. Il en est donc de même dans les réseaux dynamiques. Notre première contribution est de caractériser exactement ce qui fait de l'agrégation de données un problème NP-Complet. En effet, dans les réseaux statiques, où le problème est trivial pour les réseaux de degré au plus deux, nous montrons que le problème reste NP-Complet dans les réseaux de degré au plus trois. De même, le problème est trivial dans les réseaux dynamiques de degré au plus un et nous montrons qu'il est NP-Complet dans les réseaux dynamiques de degré au plus deux. Nous montrons donc que l'ajout de la dynamique rend le problème de l'agrégation de données intrinsèquement plus difficile. Notre deuxième contribution est de présenter des bornes inférieures et supérieures pour la durée d'agrégation des données dans un réseau dynamique. Là encore, l'ajout de la dynamique augmente la durée d'agrégation des données dans le pire des cas.
ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications http://hal.upmc.fr/hal-01144458 ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2015, Beaune, FranceConference papers 2015-06-02
oai:hal.archives-ouvertes.fr:hal-01135398
The Random Bit Complexity of Mobile Robots Scattering
International audience
We consider the problem of scattering $n$ robots in a two dimensional continuous space. As this problem is impossible to solve in a deterministic manner, all solutions must be probabilistic. We investigate the amount of randomness (that is, the number of random bits used by the robots) that is required to achieve scattering. We first prove that $n \log n$ random bits are necessary to scatter $n$ robots in any setting. Also, we give a sufficient condition for a scattering algorithm to be random bit optimal. As it turns out that previous solutions for scattering satisfy our condition, they are hence proved random bit optimal for the scattering problem. Then, we investigate the time complexity of scattering when strong multiplicity detection is not available. We prove that such algorithms cannot converge in constant time in the general case and in $o(\log \log n)$ rounds for random bits optimal scattering algorithms. However, we present a family of scattering algorithms that converge as fast as needed without using multiplicity detection. Also, we put forward a specific protocol of this family that is random bit optimal ($n \log n$ random bits are used) and time optimal ($\log \log n$ rounds are used). This improves the time complexity of previous results in the same setting by a $\log n$ factor. Aside from characterizing the random bit complexity of mobile robot scattering, our study also closes its time complexity gap with and without strong multiplicity detection (that is, $O(1)$ time complexity is only achievable when strong multiplicity detection is available, and it is possible to approach it as needed otherwise).
Ad-hoc, Mobile, and Wireless Networks - 14th International Conference, ADHOC-NOW 2015 http://hal.upmc.fr/hal-01135398 Ad-hoc, Mobile, and Wireless Networks - 14th International Conference, ADHOC-NOW 2015, Jun 2015, Athènes, Greece. 2015Conference papers 2015-06-28
oai:hal.archives-ouvertes.fr:hal-01153111
Packet Efficient Implementation of the Omega Failure Detector
HASH(0x7f03ffb36f78)
http://hal.upmc.fr/hal-01153111 [Research Report] UPMC Université Paris VI; Kent State University. 2015Reports 2015
oai:hal.archives-ouvertes.fr:hal-01184532
Probabilistic Asynchronous Arbitrary Pattern Formation
HASH(0x7f04008e59d8)
https://hal.archives-ouvertes.fr/hal-01184532 [Research Report] Université Pierre et Marie Curie. 2015ARRAY(0x7f03f9008c80) 2015-08-15
oai:hal.archives-ouvertes.fr:hal-01264285
Distributed Online Data Aggregation in Dynamic Graphs
HASH(0x7f03f9009fc8)
https://hal.archives-ouvertes.fr/hal-01264285 [Research Report] Sorbonne Universités, UPMC Univ Paris 06, CNRS, LIP6 UMR 7606, 4 place Jussieu 75005 Paris.; Osaka University, Japan. 2016ARRAY(0x7f04003fd218) 2016-01-29
Soutenance
Thèse: Reseaux de capteurs sans fil efficaces en energie
Soutenance: 2016-10-04
Rapporteurs: Nathalie MITTON    Nicola SANTORO