Randomized location service in Mobile Ad Hoc Networks

Abstract

Mobile Ad-Hoc Networks (MANETS) are networks of mobile hosts that do not have a fixed infrastructure. Communication between these hosts is made difficult by the continuously changing topology. A node in the network can communicate directly only with its neighbors, that is, with nodes that are within its transmission range. If a direct communication link cannot be established, then multi-hop routing may be used for communication. The main challenge in the operation of MANETS is coping with their continuously changing connectivity. Recent research in this field includes ways of solving existing problems in MANETS by the use of location information of the nodes. For example, some routing algorithms use information about the geographic location of the nodes to optimize the routing process. However, since the location of the hosts change frequently, maintaining location information is also a challenge in these networks. This thesis considers a location service, where all nodes maintain location information about all other nodes in the network keeping this information as up-to-date as practical. This information can be used by an upper level application to provide various services. To this end we look at three algorithms and simulate them in NS-2 to see their performance. Our aim is to achieve simpler and more efficient algorithms, through the application of probabilistic quorums at the expense of intermittently outdated information. Such a location service generates a few outdated values but can be used by applications that can tolerate outdated location information. We compare the performance of our algorithms by measuring the percentage of outdated values received and the average operation time.