Les travaux de cette thèse ont pour cadre l'édition de documents électroniques multimédia en considérant en tout premier lieu leur dimension temporelle (enchaînement des objets dans le temps). L'objectif concerne à la fois l'intégration de cette nouvelle dimension dans la structure globale d'un document (logique, spatiale et hypertexte) et l'intégration d'objets de base qui ont eux-mêmes une dimension temporelle (vidéo, audio, interactions de l'utilisateur ..). Les documents visés sont donc multimédia, temporisés et interactifs. Notre étude a porté tout d'abord sur la définition d'un langage temporel multimédia. Celui-ci permet de spécifier, de façon déclarative, le scénario temporel d'un document en s'appuyant sur des résultats obtenus dans le domaine de la satisfaction de contraintes temporelles et de la planification. Nous avons ensuite conçu des mécanismes d'analyse qui permettent la vérification de la cohérence d'une spécification tout en prenant en compte trois aspects essentiels aux systèmes multimédia : l'incrémentalité, l'efficacité, et la gestion de l'indéterminisme. Nous proposons des mécanismes de synthèse qui permettent alors le calcul d'une solution qui sera exploitée par le système de présentation. Celui-ci permet, à partir d'un automate d'états finis extrait du graphe temporel de contraintes, d'exécuter la présentation multimédia et de contrôler dynamiquement son déroulement. Enfin, nous présentons l'ensemble des résultats à travers leur application concrète au sein d'un outil d'édition et de présentation appelé Madeus.

La synchronisation temporelle des systèmes MIMO a été abondamment étudiée dans les quinze dernières années, mais la plupart des techniques existantes supposent que le bruit est blanc temporellement et spatialement, ce qui ne permet pas de modéliser la présence d'interférence. Nous considérons donc le cas de bruits blancs temporellement mais pas spatialement, dont la matrice de covariance spatiale est inconnue. En formulant le problème de l'estimation de l'instant de synchronisation comme un test d'hypothèses, nous aboutissons au test du rapport de vraisemblance généralisé (GLRT) qui donne lieu à la comparaison avec un seuil d'une statistique de test eta_GLRT. Cependant, pour des raisons de complexité, l'utilisation de cette statistique n'est pas toujours considérée comme réaliste. La première partie de ce travail a donc été consacrée à mettre en évidence des tests alternatifs moins complexes à mettre en œuvre, tout en ayant des performances similaires. Une analyse comparative exhaustive, prenant en considération le bruit et l'interférence, le type de canal, le nombre d'antennes en émission et en réception, et l'orthogonalité de la séquence de synchronisation est réalisée. Enfin, nous étudions le problème de l'optimisation du nombre d'antennes en émission K pour la synchronisation temporelle, montrant que pour un RSB élevé, les performances augmentent avec K dès que le produit de K avec le nombre d'antennes de réception M n'est pas supérieur à 8.Le deuxième aspect de ce travail est une analyse statistique de eta_GLRT dans le cas où la taille de la séquence d'apprentissage N est du même ordre de grandeur que M, ce qui conduit naturellement à étudier le comportement de eta_GLRT dans le régime asymptotique des grands systèmes M tend vers l'infini, N tend l'infini de telle sorte que M/N tende vers une constante non nulle. Nous considérons le cadre applicatif d'un système muni d'une unique antenne d'émission et d'un canal à trajets multiples, qui est formellement identique à celui d'un système MIMO dont le nombre d'antennes d'émissions correspondrait au nombre de trajets. Lorsque le nombre de trajets L est beaucoup plus faible que N et M, nous établissons que eta_GLRT a un comportement gaussien avec l'espérance asymptotique L log (1 / (1-M/N)) et la variance (L/N)*(M/N)/(1-M/N). Ceci est en contraste avec le régime asymptotique standard quand N tend vers l'infini et M et L fixe où eta_GLRT a un comportement chi2. Sous l'hypothèse H_1, eta_GLRT a aussi un comportement gaussien. Nous considérons également le cas où le nombre de trajets L tend vers l'infini à la même vitesse que M et N. Nous utilisons des résultats connus concernant le comportement des statistiques linéaires des valeurs propres des grandes F matrices, et déduisons que dans le régime où L,M,N tendent vers l'infini à la même vitesse, eta_GLRT a encore un comportement gaussien sous H_0, mais avec une espérance et variance différentes. L'analyse de eta_GLRT sous H_1 lorsque L,M,L convergent vers l'infini nécessite l'établissement d'un théorème central limite pour les statistiques linéaires des valeurs propres de matrices F de moyennes non-nulles, une tâche difficile. Motivé par les résultats obtenus dans le cas où L reste fini, nous proposons d'approximer la distribution asymptotique par une distribution gaussienne dont l'espérance et la variance sont la somme de l'espérance et la variance asymptotique sous H_0quand L tend vers l'infini avec l'espérance et la variance asymptotique sous H_1 dans le régime classique N tend vers l'infini et M fixé. Des simulations numériques permettent de comparer les courbes ROC des différents approximant avec des courbes ROC empiriques. Les résultats montrent que nos approximant de grandes dimensions fournissent de meilleurs résultats quand M/N augmente, tout en permettant de capturer la performance réelle pour les petites valeurs de M/N / Time synchronization of MIMO systems have been strongly studied in the last fifteen years, but most of the existing techniques assume a spatially and temporally white noise, which does not allow modeling the presence of interference. We consider thus a temporally white but spatially colored noise, with an unknown covariance matrix. Formulating the estimation problem as a hypothesis testing problem, we obtain a Generalized likelihood ratio test (GLRT), which gives us a synchronization statistics eta_GLRT. However, for complexity reasons, it is not always considered realistic for practical situations. A part of this work has thus been devoted to showing that there exist non-GLRT statistics that are less complex to implement than theet a_GLRT, while having similar performance. Furthermore, we perform a comparative parameter analysis, taking into consideration the noise type, channel type, the number of transmit and receive antennas, and the orthogonality of the synchronization sequence. Lastly, the problem of optimization of the number of transmit antennas K for time synchronization has been investigated. showing, for high SNR, increasing performance with K as long as the product KM is not larger than 8, where M is the number of receive antennas. The second aspect of MIMO synchronization studied in thesis is asymptotic analysis of the same GLRT, but for large M. In this context, the synchronization sequence length N is the same order of magnitude as M, and this leads us naturally to the study of the the behavior of eta_GLRT in the asymptotic regime where M,N go towards infinity such that M/N go towards a non-zero constant. We consider the case of a single transmit antenna in a multi-path channel, which formally is equivalent to the MIMO system where the transmit antennas correspond to the number of paths. We address the case When the number of paths L does not scale with M and N, we establish that eta_GLRT has a Gaussian behavior with asymptotic mean L log (1/ (1 - M/N))and variance (L/N)*(M/N)/(1-M/N).This is in contrast with the standard asymptotic regime N goes to infinity and M fixed where eta_GLRT has a chi^2 behaviour. Under hypothesis H_1, eta_GLRT still has a Gaussian behaviour. The corresponding asymptotic mean and variance are obtained as the sum of the asymptotic mean and variance in the standard regime N goes to infinity and M fixed, and L log(1/(1-/M/N))L log (1 / (1-M/N)) and (L/N)*(M/N)/(1-M/N)respectively, i.e. the asymptotic mean and variance under H_0.We also consider the case where the number of paths L converges towards infinity at the same rate as M and N. Using known results of concerning the behaviour of linear statistics of the eigenvalues of large F-matrices, we deduce that in the regime where L,M,N converge to infinity at the same rate, eta_GLRT still has a Gaussian behaviour under H_0, but with a different mean and variance. The analysis of eta_GLRT under H_1 whenL,M,N converge to infinity needs to establish a central limit theorem for linear statistics of the eigenvalues of large non zero-mean F-matrices, a difficult ask. Motivated by the results obtained in the case where L remains finite, we propose to approximate the asymptotic distribution of eta_GLRT by a Gaussian distribution whose mean and variance are the sum of the asymptotic mean and variance under H_0when L goes to infinity with the asymptotic mean and variance under H_1 in the standard regime N goes to infinity and M fixed. Numerical simulations allow to compare the ROC curves obtained with the different approximations with the empirical ROC curves. The results show that the large-system approximations provide better results when M/N increases, while also allowing to capture the actual performance for small values of M/N

Les récentes avancées technologiques en particulier dans le domaine de la miniaturisation de dispositifs robotiques laissent présager l'émergence de grands ensembles distribués de petits robots qui coopéreront en vue d'accomplir des tâches complexes (e.g., robotique modulaire, robots en essaims, microsystèmes électromécaniques distribués). Ces grands ensembles seront composés d'entités indépendantes, intelligentes et communicantes qui agiront comme un ensemble à part entière. Pour cela, elles s'auto-organiseront et collaboreront en vue d'accomplir des tâches complexes. Ces systèmes présenteront les avantages d'être plus polyvalents et plus robustes que les systèmes robotiques conventionnels tout en affichant un prix réduit. Ces ensembles formeront des systèmes distribués complexes dans lequel chaque entité sera un système embarqué à part entière avec ses propres capacités et ressources toute fois limitées. Coordonner de tels systèmes posent des défis majeurs et ouvrent de nouvelles opportunités dans l'algorithmique distribuée. Je défends la thèse qu'il faut d'ores et déjà identifier et implémenter des algorithmes distribués servant de primitives de base à la coordination de ces ensembles. Dans ce travail, nous nous focalisons sur une classe particulière de robots, à savoir les robots modulaires distribués formant de grands ensembles de modules fortement contraints en ressources (mémoire, calculs, etc.), placés dans une grille régulière et capables de communiquer entre voisins connexes uniquement. J'ai identifié et implémente trois primitives servant à la coordination de ces systèmes, à savoir l'élection d'un nœud central au réseau, la synchronisation temporelle ainsi que l'auto-reconfiguration. Dans ce manuscrit, je propose un ensemble d'algorithmes distribués réalisant ces primitives. J'ai évalué mes algorithmes en utilisant des expériences sur des modules matériels et en simulation sur des systèmes, composés de quelques dizaines à plus d'une dizaine de milliers de modules. Ces expériences montrent que nos algorithmes passent à l'échelle et sont adaptés aux grands ensembles distribués de systèmes embarqués avec des ressources fortement limités à la fois en mémoire et en calcul. / Technological advances especially in the miniaturization of robotic devices foreshadow the emergence of large-scale ensembles of small-size resource-constrained robots that distributively cooperate to achieve complex tasks (e.g., modular self-reconfigurable robots, swarm robotic systems, distributed microelectromechanical systems, etc.). These ensembles are formed from independent, intelligent and communicating units which act as a whole ensemble. These units cooperatively self-organize themselves to achieve common goals. These systems are tought to be more versatile and more robust than conventional robotic systems while having at the same time a lower cost.These ensembles form complex asynchronous distributed systems in which every unit is an embedded system with its own but limited capabilities. Coordination of such large-scale distributed embedded systems poses significant algorithmic issues and open for new opportunities in distributed algorithms. In my thesis, I defend the idea that distributed algorithmic primitives suitable for the coordination of these ensembles should be both identified and designed.In this work, we focus on a specific class of modular robotics systems, namely large-scale distributed modular robotic ensembles composed of resource-constrained modules that are organized in a lattice structure and which can only communicate with neighboring modules. We identified and implemented three building blocks, namely centrality-based leader election, time synchronization and self-reconfiguration.We propose a collection of distributed algorithms to realize these primitives. We evaluate them using both hardware experiments and simulations on systems ranging from a dozen of modules to more than a dozen of thousands of modules. We show that our algorithms scale well and are suitable for large-scale embedded distributed systems with scarce memory and computing resources.

La conception de systèmes embarqués devient de plus en plus complexe. Ces systèmes sont hétérogènes dans le sens où ils nécessitent l’intégration de composants décrits au moyen de plusieurs disciplines scientifiques, par exemple, l’électricité, l’optique, la thermique, la mécanique, la chimie ou la biologie. De plus, ces disciplines peuvent être représentées dans des domaines temporels différents, par exemple, le domaine des événements discrets, celui du temps discret, ou celui du temps continu. Face à cette situation, les concepteurs ont besoin d’outils de modélisation et de simulation efficaces pour décrire le comportement d’un système hétérogène dans un environnement de simulation unique. Nous examinons la possibilité de modéliser, de simuler et de synchroniser les systèmes multi-disciplines dans le même environnement, en utilisant comme référence la norme de simulation « SystemC Analog/Mixed-Signal (AMS) ». Nous analysons la méthode introduite par SystemC AMS pour synchroniser le domaine des événements discrets avec celui du temps discret, et nous identifions ses inconvénients. Nous proposons une formalisation du problème de synchronisation qui permet de détecter les problèmes existants dans un modèle avant la simulation. Nous proposons un prototype de simulateur appelé « SystemC Multi-Disciplinary Virtual Prototyping (MDVP) », qui est implémenté comme une extension de SystemC. Il permet la modélisation, l’élaboration, et la simulation hiérarchique de systèmes multi-disciplines au moyen de plusieurs modèles de calcul. Pour concevoir le simulateur MDVP, nous introduisons un nouveau principe de synchronisation entre plusieurs modèles de calcul. En outre, nous introduisons une méthodologie pour ajouter, dans le prototype de simulateur, des modèles de calcul représentés par plusieurs domaines temporels. Nous appliquons cette méthodologie pour ajouter un modèle de calcul « Timed Data Flow (TDF) » dans SystemC MDVP. Ce modèle de calcul repose sur la sémantique du temps discret introduite par SystemC AMS, et sur la formalisation du principe de synchronisation entre le domaine des événements discrets et celui du temps discret. Nous mettons en œuvre le modèle de calcul TDF, dans le cas d’un capteur de vibrations et son circuit numérique. Ce modèle comporte une boucle d’asservissement et plusieurs interactions entre le domaine des événements discrets et celui du temps discret. / The design of embedded systems is currently an increasingly complex problem. These systems tend to become heterogeneous in the sense that they require the integration of components described by means of different physical/engineering disciplines, for example, electrical, optical, thermal, mechanical, chemical, or biological. Besides, these disciplines can be described under different time domains, for example, Discrete Event (DE), Discrete Time (DT), or Continuous Time (CT). To address this problem, designers require modeling and simulation tools to describe the system’s components under different time domains and synchronize them in the same simulation environment. We explore the possibilities of modeling, simulating and synchronizing multi-disciplinary systems in the same environment, using as reference the SystemC Analog/Mixed-Signal (AMS) simulation standard. We analyze the method introduced in SystemC AMS for synchronizing the DE and DT domains, and we identify its drawbacks. Besides, we introduce a new formalization of the synchronization problem, which is used to detect issues in a model before simulation. We propose a simulator prototype called SystemC Multi-Disciplinary Virtual Prototyping (MDVP), which is implemented as an extension of SystemC. It allows the modeling, and the generic hierarchical elaboration and simulation of multi-disciplinary systems, by means of different Models of Computation (MoCs). To build the MDVP simulator, we introduce a synchronization principle to handle interactions between MoCs. In addition, we introduce a methodology to add, in the simulator prototype, MoCs described under different time domains. We apply this methodology to add a Timed Data Flow MoC in SystemC MDVP. This MoC implements the DT semantics introduced by the SystemC AMS standard, and is based on the synchronization principle between the DE and DT domains. Using the TDF MoC, we implement and simulate a case study of a vibration sensor model and its digital front end circuit. This case study includes a feedback loop and several interactions between the DE and DT domains.

La synchronisation temporelle est la première opération effectuée par le démodulateur. Elle permet d'assurer que les échantillons transmis aux processus de démodulation puissent réaliser un taux d'erreurs binaires le plus faible.Dans cette thèse, nous proposons l'étude d'algorithmes innovants de synchronisation temporelle à haute performance.D'abord, nous avons proposé des algorithmes exploitant l'information souple du décodeur en plus du signal reçu afin d'améliorer l'estimation aveugle d'un retard temporel supposé constant sur la durée d'observation.Ensuite, nous avons proposé un algorithme original basé sur la synchronisation par lissage à faible complexité.Cette étape a consisté à proposer une technique opérant dans un contexte hors ligne, permettant l'estimation d'un retard aléatoire variable dans le temps via les boucles d'aller-retour sur plusieurs itération. Les performances d'un tel estimateur dépassent celles des algorithmes traditionnels.Afin d'évaluer la pertinence de tous les estimateurs proposés, pour des retards déterministe et aléatoire, nous avons évalué et comparé leurs performances à des bornes de Cramèr-Rao que nous avons développées pour ce cadre. Enfin, nous avons évalué les algorithmes proposés sur des signaux WBAN. / Time synchronization is the first function performed by the demodulator. It ensures that the samples transmitted to the demodulation processes allow to achieve the lowest bit error rate.In this thesis we propose the study of innovative algorithms for high performance time synchronization.First, we propose algorithms exploiting the soft information from the decoder in addition to the received signal to improve the blind estimation of the time delay. Next, we develop an original algorithm based on low complexity smoothing synchronization techniques. This step consisted in proposing a technique operating in an off-line context, making it possible to estimate a random delay that varies over time on several iterations via Forward- Backward loops. The performance of such estimators exceeds that of traditional algorithms. In order to evaluate the relevance of all the proposed estimators, for deterministic and random delays, we evaluated and compared their performance to Cramer-Rao bounds that we developed within these frameworks. We, finally, evaluated the proposed algorithms on WBAN signals.