GDE

Abstract

Today, wireless networks are connecting more and more devices around us. The scale of these systems demands for novel techniques to maintain availability for various services such as routing, localization, context detection, etc. Distance estimation is one of their most important building blocks. The majority of current algorithms presume knowledge about node position via systems such as GPS. While for some application scenarios this approach is feasible, for a lot of cases it suffers from frequent unavailability and high costs in terms of energy consumption. The main contribution of the thesis is the introduction of a novel distributed algorithm called GDE for the estimation of distances in large-scale wireless networks. It is based on a gossiping mechanism to estimate distances between nodes solely based on local interaction. We analyze the parameters that should be considered by real applications, and present mathematical models to compensate their influence for distance estimation. Three kinds of applications are shown in the thesis using the GDE algorithm, including cluster center detection, overlay shape construction, and routing. Finally, we introduce some more improvement methods for the GDE algorithm to increase the distance estimation accuracy. The evaluations by means of simulation show that GDE succeeds in estimating the distance between nodes in both static and mobile scenarios with considerably high accuracy for various parameter setups, such as varying node density, node speed, spatial node distribution, etc.