The ubiquity of mobile devices and particularly smartphones has caused the emergence of a new trend of distributed applications known as Proximity-Based Mobile (PBM) applications. These applications enable a user to interact with others in a defined range and for a certain time duration for différent purposes such as social networking, dating, gaming and driving. The goal of this thesis is to introduce a set of programming abstractions and algorithms that can be used for building PBM applications in a category of mobile networks, called mobile ad hoc networks (MANETs). In fact, the characteristics of MANETs make them a promising technology to enable PBM applications. However, the existing abstractions and algorithms in the literature of MANETs are not fully adequate for building PBM applications. Thus, in this thesis we define proximity-based durable broadcast and proximity-based neighbor détection as the main requirements of PBM applications. Then, in each part of the thesis, we introduce abstractions and algorithms which address one of these requirements.
In the first part of the thesis, we present abstractions and algorithms for proximity- based durable broadcast. Thus, we introduce spotcast, a new communication abstraction that enables a node to disseminate a message for a given time duration to ail nodes located within a given range. We present three variants of spotcast, which differ in their timing guarantees for message delivery. We also introduce scoped broadcast, a communication abstraction that enables a node to disseminate a message to ail nodes located within a given range. We introduce two variants of scoped broadcast: a reliable synchronous variant as well as an asynchronous variant. We discuss the implementability of each scoped broadcast variant in the single-hop and multi-hop cases. We then introduce a generic algorithm, which can implement the three spotcast variants using différent scoped broadcast variants and différent types of message buffers.
In the second part of the thesis, we present abstractions and algorithms for proximity- based neighbor détection. We begin by adapting the hello protocols (which are one of the most famous neighbor détection algorithms in MANETs) for effective and efficient neighbor détection in three typical urban environments where PBM applications are mostly used. Effectiveness refers to the degree to which the détection is successful and efficiency refers to the degree to which the détection is energy saving. Based on a realistic simulation- based study, we show that in ail three environments, there is a conflict between effectiveness and efficiency. Then for each environment, we propose a communication strategy which makes a good tradeoff between effectiveness and efRciency in that environment. One of the limitations of the hello protocols is that they only detect current neighbors. However, for some of the existing PBM applications, neighbor discovery is not restricted to current neighbors. Thus, we continue the second part of the thesis by introducing a new neighbor détection abstraction called the time-limited neighbor detector. This abstraction enables a node to detect its neighbors in the past, present and up to some bounded time interval in the future. We introduce two algorithms that implement the time-limited neighbor detector abstraction based on the notion of virtual mobile nodes already presented in the literature. The fîrst algorithm is simple but limited and uses a single virtual mobile node. The second algorithm is more général and advanced and uses multiple virtual mobile nodes.
--
L'omniprésence des appareils mobiles et en particulier des smartphones, a causé l'émergence d'un nouveau type des applications réparties qu'on appelle les applications mobiles sensibles à la proximité ou applications PBM (Proximity-Based Mobile). Ces applications permettent à un utilisateur d'interagir avec tous les autres utilisateurs situés dans un rayon donné autour de lui pendant une durée déterminée. Ces interactions peuvent avoir des fins différentes, telles que le réseautage social, le jeu en ligne ou le support à la conduite automobile. L'objectif de cette thèse est de proposer des abstractions et des algorithmes qui peuvent être utilisés pour construire les applications PBM dans un type de réseau mobile qu'on appelle réseaux mobiles ad hoc ou MANETs (Mobile Ad-hoc Networks). En effet, les caractéristiques des MANETs en font une technologie prometteuse pour les applications PBM. Toutefois, les abstractions et les algorithmes existants dans la littérature des MANETs ne sont pas tout à fait adéquats pour construire les applications PBM. Dans cette thèse, nous définissons le broadcast durable sensible à la proximité et la détection de voisins sensible à la proximité comme les exigences principales des applications PBM. Ensuite, dans chaque partie de la thèse, nous proposons des abstractions et des algorithmes qui sont conçus pour satisfaire ces exigences.
Dans la première partie de la thèse, nous présentons des abstractions et des algorithmes pour le broadcast durable sensible à la proximité. Pour ce faire, nous introduisons spotcast, une nouvelle abstraction qui permet à un noeud de diffuser un message pendant une durée déterminée à tous les noeuds situés dans un rayon donné autour de lui. Nous présentons trois variantes de spotcast, qui diffèrent par leurs garanties temporels pour la livraison des messages. Nous présentons aussi scoped broadcast, une abstraction qui permet à un noeud de diffuser un message à tous les noeuds situés dans un rayon donné autour de lui. Nous introduisons deux variantes de scoped broadcast: une variante synchrone fiable ainsi qu'une variante asynchrone. Nous discutons de l'implémentation single-hop et multi-hop de chaque variante de scoped broadcast. Ensuite, nous présentons un algorithme générique, qui implémente les trois variantes de spotcast en utilisant les différentes variantes de scoped broadcast et différents types de tampon des messages.
Dans la deuxième partie de la thèse, nous présentons les abstractions et les algorithmes pour la détection de voisins sensible à la proximité. Nous commençons par adapter les pro¬tocoles hello (qui font partie des algorithmes de détection de voisins les plus utilisés dans les MANETs) pour la détection efficace et efficiente de voisins dans trois environnements urbains typiques où les applications PBM sont utilisées. Par efficacité, nous entendons le degré auquel la détection est réussie et par efficience, nous entendons le degré auquel la détection est efficace du point de vue de sa consommation d'énergie. En se basant sur des simulations réalistes, nous montrons que dans les trois environnements, il y a un conflit entre l'efficacité et l'efficience. Ensuite, pour chaque environnement, nous présentons une stratégie de communication qui fait un compromis entre l'efficacité et l'efficience dans cet environnement-là. L'une des limitations des protocoles hello est qu'ils ne détectent que les voisins actuels. Cependant, pour certaines applications PBM, la détection de voisins n'est pas limitée aux voisins actuels. Nous poursuivons donc la seconde partie de la thèse en introduisant une nouvelle abstraction de détection de voisins, appelée le time-limited neighbor detector. Cette abstraction permet à un noeud de détecter ses voisins dans le passé, le présent et jusqu'à un certain intervalle de temps borné dans le futur. Nous présentons deux algorithmes qui implémentent le time-limited neighbor detector, en util¬isant les noeuds virtuels mobiles (la notion du noeud virtuel mobile existe déjà dans la littérature). Le premier algorithme est simple et limité et utilise un seul noeud virtuel mobile. Le second algorithme est plus général et utilise plusieurs noeuds virtuels mobiles.