Saroja Kanchi, Kettering University, USA

The localization of wireless sensor networks is an important problem where the location of wireless sensors is determined using the distance between sensors. Trilateration is a geometric technique used to find location of points in 2D using distances. Using geometry, one can find the location of a point uniquely in 2D given its distance to three other points in 2D. The problem of finding the trilateration order of vertices even if the network of sensors is a uniquely localizabe is NP-Complete. The 2D localization problem is closely related to the problem of graph rigidity. A graph can be uniquely realized in 2D if and only if the underlying network graph is globally rigid. Therefore by examining the structure of the underlying graph for rigidity and localization guided by rigidity is another technique used in localization. We study the performance of trilateration which is based on geometry and local information to see if it is effected by graph rigidity which is a global property. In particular, we compare the performance of the trilateration on connected non-rigid networks and connected rigid networks. We focus on sparse networks graphs of lower radius.