Les réseaux de capteurs sans fils (RCSFs) suscitent un intérêt croissant depuis une vingtaine d'années. La première partie de cette thèse est consacré à l'étude de l'efficacité de compression de données corrélées provenant d'un RCSF et acheminées vers un point de collecte à l'aide du codage réseau linéaire aléatoire. Les conditions nécessaires et suffisantes sont obtenues pour récupérer parfaitement les données que les capteurs mesurent. Puis on considère les nœuds dans un RCSF collaborant afin d'exécuter une tâche donnée (acquisition, détection...), pour laquelle chaque nœud a potentiellement un niveau d'expertise différent. La seconde partie de cette thèse est dédiée à la conception et à l'analyse d'algorithmes d'auto-évaluation distribués (AED), qui permettent à chaque nœud d'auto-évaluer son niveau d’expert. Trois types de problèmes sont considérés: i) la détection distribuée des nœuds défaillants (DDD), qui permet d'identifier les nœuds équipés de capteurs défectueux dans un RCSF; ii) la DDD dans un réseau tolérant aux déconnections (RTD) dont la topologie est dynamique et le degré de connectivité très faible; iii) la AED avec interactions pair à pair. Les résultats théoriques sont utiles pour configurer les paramètres des algorithmes. / Wireless sensor networks (WSNs) have attracted much interests in the last decade. The first part of this thesis considers sparse random linear network coding is for data gathering and compression in WSNs. An information-theoretic approach is applied to demonstrate the necessary and sufficient conditions to realize the asymptotically perfect reconstruction under MAP estimation. The second part of the thesis concerns the distributed self-rating (DSR) problem, for WSNs with nodes that have different ability of performing some task (sensing, detection...). The main assumption is that each node does not know and needs to estimate its ability. Depending on the number of ability levels and the communication conditions, three sub-problems have been addressed: i) distributed faulty node detection (DFD) to identify the nodes equipped with defective sensors in dense WSNs; ii) DFD in delay tolerant networks (DTNs) with sparse and intermittent connectivity; iii) DSR using pairwise comparison. Distributed algorithms have been proposed and analyzed. Theoretical results assess the effectiveness of the proposed solution and give guidelines in the design of the algorithm.

A Disruption Tolerant Network (DTN) is a sparse network where connectivity is regulated by the proximity of mobile nodes. Connections are sporadic and the delivery rate is closely related to node movement. As network resources often are limited in such settings, it is useful to monitor the network in order to make more efficient communication decisions. This study investigates existing routing protocols and monitoring tools for DTN that best cope with the requirements of a tactical military network. A model is proposed to estimate source to destination delay in DTN. This model is evaluated in a Java-based software simulator called The ONE. In order to match the tactical military environment, two scenarios are constructed. The squad scenario simulates the formation movement pattern of several squads and the hierarchical communication scheme that is maintained in a military context. The other scenario simulates a convoy line movement of a military group during transportation. The results of this study show that the proposed mechanism can improve delivery rate and reduce network overhead in settings with strict buffer limitations. The estimation worked best in scenarios that contained some patterns of movement or communication. These patterns are resembled in the model's collected data and the model can provide the user with rough estimates of end-to-end delays in the network. Primary use of this model has been to reduce number of old messages in the network, but other applications like anomaly detection are also discussed in this work. / Ett avbrottstolerant nätverk (DTN) är ett glest nät där konnektiviteten avgörs av närheten bland de rörliga noderna i nätverket. Avbrotten i ett sådant nät förekommer ofta och sporadiskt. Eftersom nätverksresurserna oftast är begränsade i sådana sammanhang, så är det lämpligt att övervaka nätverket för att göra det möjligt att fatta mer effektiva kommunikationsbeslut. Det här arbetet undersöker olika routingalgoritmer och övervakningsvektyg för DTN med hänsyn till de krav som ställs av ett taktiskt nät. En modell för att uppskatta fördröjningen från källa till destination är framtagen i arbetet. Modellen är utvärderad med hjälp av en Javabaserad mjukvarusimulator som heter The ONE. För att bäst representera den miljö som uppstår i militära sammanhang är två scenarion framtagna. Det första är ett truppscenario där nodernar rör sig i fromationer och nättrafiken följer den hierarkiska modellen som används i militär kommunikation. Det andra scenariot är ett konvojscenario där enheter marcherar på led. Resultaten från denna studie visar att den föreslagna modellen kan öka andelen levererade meddelanden och minska nätverksbelastningen i en miljö där bufferstorleken hos noderna är begränsad. Uppskattningen visade sig fungera bäst i scenarion som innehöll någon form av mönster bland nodernas rörelse eller deras kommunikation. Dessa mönster återspeglas i modellens insamlade data och modellen kan förse användaren med en grov estimering av slutfördröjningen till alla destinationer i nätet. Modellen har i huvudsak använts till att minska antalet gamla meddelanden i nätet, men arbetet berör även andra användningsområden som anomalidetektion.

Deux situations de comportement égoïste des agents dans les réseaux de communication sont considérées dans le cadre de la théorie des jeux.La première situation concerne les réseaux de communication utilisant un routage décentralisé basé sur des agents autonomes. Nous étudions les propriétés de convergence des dynamiques de meilleures réponses dans un jeu de routage sur des liens parallèles. Le jeu implique un nombre fini d'agents, chacun décidant comment son trafic est routé sur les liens de manière à minimiser son propre coût. Nous proposons l'utilisation du rayon spectral généralisé des matrices Jacobiennes de l'opérateur de meilleure réponse pour démontrer la convergence.La seconde situation apparaît dans les réseaux tolérants aux délais dont l'objectif est de permettre la communication dans des environnements où la connectivité n'est qu'intermittente et où les délais de communication peuvent être très longs. Nous proposons tout d'abord un mécanisme d'incitation basé sur une récompense pour convaincre les noeuds mobiles de relayer les messages, et analysons l'influence de l'information donnée par la source (nombre de copies du message, âge de ces copies) aux relais sur le prix à payer pour transmettre le message. Nous considérons ensuite un modèle dans lequel la source propose une récompense fixe. Les noeuds mobiles peuvent alors décider d'accepter ou non le message, et s'ils l'acceptent, peuvent ensuite à tout moment décider de l'abandonner. Nous modélisons l'interaction entre les noeuds mobiles sous la forme d'un jeu stochastique partiellement observable et analysons les politiques optimales pour les relais. / This thesis focuses on the issues related to the selfish behavior of the agents in the communication networks. We are particularly interested in two situations in which these issues arise and we address game-theoretical framework to study them.The first situation relates to communication networks using a distributed routing based on autonomous agents. Compared to a centralized routing, this type of routing offers significant advantages in terms of scalability, ease of deployment or robustness to failures and environmental disturbances. We investigate the convergence properties of the sequential best-response dynamics in a routing game over parallel links. The game involves a finite number of routing agents each of which decides how much flow to route on each of the links with the objective of minimizing its own costs. For some particular cases (e.g., two players), the convergence of the best-response dynamics can be proved by showing that this game has a potential function. For other cases, a potential function has remained elusive. We propose the use of non-linear spectral radius of the Jacobian of the best-response dynamics as an alternative approach to proving its convergence.The second situation occurs in Delay Tolerant Networks (DTNs) that have been the subject of intensive research over the past decade. DTN has an idea to support communication in environments where connectivity is intermittent and where communication delays can be very long. We focus on game-theoretic models for DTNs. First, we propose an incentive mechanism to persuade selfish mobile nodes to participate in relaying messages, and investigate the influence of the information given by the source (number of existing copies of the message, age of these copies) to the relays on the rewards proposed. For static information polices, that is the same type of information given to all the relays, it is shown that the expected reward paid by the source is independent of the policy. However, the source can reduce the reward by dynamically adapting the type of information based on the meeting times with the relays. For the particular cases, we give some structural results of the optimal adaptive policy. Next, we consider the model where the source proposes a fixed reward. The mobile relays can decide to accept or not the packet and then to drop the packet in the future. This game can be modelled as a partially-observable stochastic game. For two relays, we have shown that the optimal policies for the relays relates to the threshold type.

在耐延遲網路(Delay Tolerant Network)中，因為節點具有移動性，因此找不到穩定且持續的點對點資料傳送路徑。常見的路由協定可分為機會路由、基於預測的路由以及調度路由，然而這些路由協定使用在市區環境中，有著些許不足與不適用，因此本論文提出一個適用在市區資料傳送的演算法。 本論文提出之混合階層式路由演算法，是在市區環境中建立一個以公車為基礎的資料傳送架構，包含行人與公車兩種節點。我們建立節點與節點相遇時資料交換傳送規則，例如行人與行人相遇、行人與公車相遇或是公車與公車相遇時各自有不同的資料傳送判斷與限制。 實驗結果也證明所提出之混合階層式演算法，除了可以有效地減少傳送延遲時間並提高訊息傳送成功率，並且在給定節點一定的移動速度與緩衝區大小下，我們的演算法有著最突出的效能。 / In Delay Tolerant Networks (DTNs), there is no guarantee that a stable connected path between source and destination nodes always exists because of high node mobility. The current DTN routing protocols can be summarized into three categories: opportunistic, prediction-based and scheduling protocols. However, these routing protocols have some deficiencies and are not specifically focused on the urban areas which have primarily two hierarchical nodes, namely pedestrian and bus nodes. We proposed a Hybrid Hierarchy Routing Protocol, a bus-based architecture for urban areas. We established the rules of data transmission when one node contacts other nodes. More specifically, Ped-to-Ped, Ped-to-Bus and Bus-to-Bus contacts, have different judgments and restrictions for data forwarding. The simulation results demonstrate that the Hybrid Hierarchy Routing Protocol can effectively reduce the delivery delay and improve the successful delivery rate. And in given certain speed and buffer sizes, our algorithm has the most prominent performance.

The super collision between the Internet phenomenon and the wireless communication revolution gives birth to a wealth of novel research problems, design challenges and standardization activities. Within this domain, spontaneous wireless IP networking are probably the most extreme example of new ''particles'' born from the collision. Indeed, these particles defy the laws of the Internet in many ways. The absorption of such peculiar particles in the global IP network has already started thanks to pioneering algorithmic and protocol work -- for instance OLSR -- and through the deployment of wireless mesh networks around the world, such as urban community wireless networks. With the recent revolutions in North Africa, and movements such as Occupy Wall Street, the prospect of spontaneous wireless IP networking has become even more attractive on social and political grounds. Dedicated conferences have recently been organized, and as a result, ambitious, multi-million dollar initiatives have been launched (e.g. the US Government-funded project Commotion Wireless, or the EU-funded initiative CONFINE). However, spontaneous IP wireless networks are not yet widely deployed because pioneer work such as OLSR is vastly insufficient to fully bridge the gap between the Internet and these new networks. This thesis presents work that analyzes this gap and proposes some solutions as to how to bridge it. The focus is put on three domains: a first part presents work in the domain of wireless mesh and ad hoc networks. A second part presents work on sensor networks and in the Internet of Things. And the last part presents work in the domain of delay tolerant networking and vehicular networks.

在耐延遲網路環境下，訊息資料的傳送依賴於節點間因移動性而產生的間斷性連結，並使用「儲存並攜帶再轉送」的方式傳遞至其目的地，因此網路中各個節點的儲存空間以及與其他節點的「接觸關連性」將扮演訊息傳遞品質的重要因素。 本論文提出一以Flooding-based與Forwarding-based兩類路由協定為基礎設計結構、並加以擴充考量訊息優先權於轉發機制之三階段式路由演算法。其主要概念在於利用網路中節點的移動特性來週期性地預測節點與節點間未來的相遇人氣做為訊息散播時的分配權重、及以累計相遇時間之比率為接觸關聯性做為訊息是否進一步轉送之依據、最後並在訊息傳送順序上加入優先權排序的策略。根據與其他路由演算法的模擬實驗，顯示我們所提的演算法能有較高的訊息傳遞成功率、相對低的資源耗費、以及差異化訊息傳送服務的效能。 / Delay Tolerant Networks (DTNs) use the “Store-Carry-and-Forward” approach to deliver the messages to the destinations. It relies on the intermittent link that occurs when two nodes contact each other due to mobility. Therefore, the buffer and “contact association” of nodes are two important factors that affect the delivery performance. In this thesis, we propose a three-phase algorithm (SFMS: Spray and Forwarding scheme with Message Scheduling) that integrates the concepts of flooding-based and forwarding-based protocols, and considers message priority. The main idea of SFMS is to periodically predict the contact popularity and contact association among nodes, such that we can determine the fast message spraying and efficient forwarding strategy. Furthermore, we come up with a message scheduling mechanism to enhance the resource allocation. Simulation results show that our scheme has a better performance for delivering messages. Besides, it also achieves a differential delivery performance for different priorities of messages while maintaining a better resource allocation.

Dans les systèmes répartis asynchrones, l'horloge logique et le vecteur d'horloges sont deux outils fondamentaux pour gérer la communication et le partage de données entre les entités constitutives de ces systèmes. L'objectif de cette thèse est d'exploiter ces outils avec une perspective d'implantation. Dans une première partie, nous nous concentrons sur la communication de données et contribuons au domaine de la diffusion uniforme à ordre total. Nous proposons le protocole des trains : des jetons (appelés trains) circulent en parallèle entre les processus participants répartis sur un anneau virtuel. Chaque train est équipé d'une horloge logique utilisée pour retrouver les train(s) perdu(s) en cas de défaillance de processus. Nous prouvons que le protocole des trains est un protocole de diffusion uniforme à ordre total. Puis, nous créons une nouvelle métrique : le rendement en termes de débit. Cette métrique nous permet de montrer que le protocole des trains a un rendement supérieur au meilleur, en termes de débit, des protocoles présentés dans la littérature. Par ailleurs, cette métrique fournit une limite théorique du débit maximum atteignable en implantant un protocole de diffusion donné. Il est ainsi possible d'évaluer la qualité d'une implantation de protocole. Les performances en termes de débit du protocole des trains, notamment pour les messages de petites tailles, en font un candidat remarquable pour le partage de données entre coeurs d'un même processeur. De plus, sa sobriété en termes de surcoût réseau en font un candidat privilégié pour la réplication de données entre serveurs dans le cloud. Une partie de ces travaux a été implantée dans un système de contrôle-commande et de supervision déployé sur plusieurs dizaines de sites industriels. Dans une seconde partie, nous nous concentrons sur le partage de données et contribuons au domaine de la RFID. Nous proposons une mémoire répartie partagée basée sur des étiquettes RFID. Cette mémoire permet de s'affranchir d'un réseau informatique global. Pour ce faire, elle s'appuie sur des vecteurs d'horloges et exploite le réseau formé par les utilisateurs mobiles de l'application répartie. Ainsi, ces derniers peuvent lire le contenu d'étiquettes RFID distantes. Notre mémoire répartie partagée à base de RFID apporte une alternative aux trois architectures à base de RFID disponibles dans la littérature. Notre mémoire répartie partagée a été implantée dans un jeu pervasif qui a été expérimenté par un millier de personnes. / In asynchronous distributed systems, logical clock and vector clocks are two core tools to manage data communication and data sharing between entities of these systems. The goal of this PhD thesis is to exploit these tools with a coding viewpoint. In the first part of this thesis, we focus on data communication and contribute to the total order broadcast domain. We propose trains protocol: Tokens (called trains) rotate in parallel between participating processes distributed on a virtual ring. Each train contains a logical clock to recover lost train(s) in case of process(es) failure. We prove that trains protocol is a uniform and totally ordered broadcast protocol. Afterwards, we create a new metric: the throughput efficiency. With this metric, we are able to prove that, from a throughput point of view, trains protocol performs better than protocols presented in literature. Moreover, this metric gives the maximal theoretical throughput which can be reached when coding a given protocol. Thus, it is possible to evaluate the quality of the coding of a protocol. Thanks to its throughput performances, in particular for small messages, trains protocol is a remarkable candidate for data sharing between the cores of a processor. Moreover, thanks to its temperance concerning network usage, it can be worthwhile for data replication between servers in the cloud. Part of this work was implemented inside a control-command and supervision system deployed among several dozens of industrial sites. In the second part of this thesis, we focus on data sharing and contribute to RFID domain. We propose a distributed shared memory based on RFID tags. Thanks to this memory, we can avoid installing a computerized global network. This is possible because this memory uses vector clocks and relies on the network made by the mobile users of the distributed application. Thus, the users are able to read the contents of remote RFID tags. Our RFID-based distributed shared memory is an alternative to the three RFID-based architectures available in the literature. This distributed shared memory was implemented in a pervasive game tested by one thousand users.

No description available.

No description available.

The astronomical increase in the number of wireless devices such as smart phones in 21th century has revolutionized the way people communicate with one another and share information. The new wireless technologies have also enabled researchers to collect real data about how people move and meet one another in different social settings. Understanding human mobility has many applications in different areas such as traffic planning in cities and public health studies of epidemic diseases. In this thesis, we study the fundamental properties of human contact graphs in order to characterize how people meet one another in different social environments. Understanding human contact patterns in return allows us to propose a cost-effective routing algorithm for spreading information in Delay Tolerant Networks. Furthermore, we propose several contact predictors to predict the unobserved parts of contact graphs when only partial observations are available. Our results show that we are able to infer hidden contacts of real contact traces by exploiting the underlying properties of contact graphs. In the last few years, we have also witnessed an explosion in the number of people who use social media to share information with their friends. In the last part of this thesis, we study the running times of several information spreading algorithms in social networks in order to find the fastest strategy. Fast information spreading has an obvious application in advertising a product to a large number of people in a short amount of time. We prove that a fast information spreading algorithm should efficiently identify communication bottlenecks in order to speed up the running time. Finally, we show that sparsifying large social graphs by exploiting the edge-betweenness centrality measure can also speed up the information spreading rate. / Graduate