Ad-hoc Positioning System 

Introduction | Implementation  | TinyOS | Demo | Papers | FAQ | Misc | Home

Introduction

Many ad hoc network protocols and applications assume the knowledge of geographic location of nodes. The absolute location of each networked node is an assumed fact by most sensor networks which can then present the sensed information on a geographical map. Finding location without the aid of GPS in each node of an ad hoc network is important in cases where GPS is either not accessible, or not practical to use due to power, form factor or line of sight conditions. Location would also enable routing in sufficiently isotropic large networks, without the use of large routing tables. We are proposing APS -- a distributed, hop by hop positioning algorithm, that works as an extension of both distance vector routing and GPS positioning in order to provide approximate location for all nodes in a network where only a limited fraction of nodes have self location capability.

[Top]

Implementation

APS has limitless possibilities in implementation. Of particular interest to this group were the implications in existing sensor networks. Armed with a dozen or so MICA motes,  and a rudimentary understanding of the TinyOS operating system, we set out to implement APS. With a substantial part of the code base finished, porting code from an earlier implementation (on the more primitive Rene motes) took up a considerable chunk of time. After a successful port, the arduous task of debugging began. A log of our progress took the form of a series of updates:

June 21, 2002 | June 20, 2002 | June 11, 2002 | June 7, 2002 | June 5, 2002  
June 3, 2002 | May 31, 2002 | May 29, 2002 | May 23, 2002

It was found early on that APS would be difficult to implement as long as distance between motes could not be determined reliably. For the purposes of our demonstration, we implemented the DV_HOP method of positioning. In a largely isotropic network, such a method was reasonable, as distance between nodes was assumed to be equal. However, in non isotropic networks, another method of determining distance needed to be found. Our first attempt was correlate distance with signal strength. However, our experimental data, while seeing a general trend of increasing signal strength with decreasing distance (and vice versa), the data was undeterministic. Repeating the experiment in various environments did not yield any more promising results.  We eventually attempted to find other viable solutions (including using sound/sonar). Work in this arena is continuous, and we are determined to find a way to correlate distance with measurable factors.

[Top]

TinyOS 

Sometimes referred to as the bane of our existence, TInyOS is the central figure in all things MICA (and rene, and basically everything mote related). It allows us to program the motes with whatever exciting and interesting application we can think of, albeit a bit clumsily. To be fair, TinyOS is still in its infancy and is continuously being developed and improved. More information about TinyOS and the development environment can be found on UC Berkeley's website. 

APS contains a few core TinyOS components. As with any TinyOS it contains a wiring -aps.desc. It also uses 2 other components: APS, which contains the main APS algorithm and does the heavy processing, and SEND_COORD, which as its name implies, sends a mote's coordinates and other useful information.

[Top]

Demo

With the help of a TCL/TK GUI script, we were able to produce a working version of APS (using DV_HOP). While initial experiments did not have a great deal of accuracy, it was a first step and provided a "ball park" location. We set up a 2 x 5 grid of "landmarks", or nodes that knew their locations with certainty. Motes with unknown locations were then placed some where in the grid, and reported their calculated positions.

 APS Demonstration Poster [ppt] [pdf]
TCL/TK GUI Screen Shot [gif]

[Top]

Papers

• Dragos Niculescu and Badri Nath, "Ad Hoc Positioning System (APS) using AoA", INFOCOM 2003, San Francisco, CA. (.pdf) (TR) (slides).
  


• Dragos Niculescu and Badri Nath, "Ad Hoc Positioning System (APS)",GLOBECOM 2001, San Antonio, Nov 2001. (.pdf) (TR) (slides).


• Dragos Niculescu and Badri Nath, " Localized Positioning in Ad Hoc Networks", in Elsevier journal of AdHoc Networks and in SNPA 2003, May 2003 Anchorage, AK, USA. (.pdf)
  


• Dragos Niculescu and Badri Nath, " DV Based Positioning in Ad hoc Networks", to appear in Kluwer journal of Telecommunication Systems, 2003. (.pdf).

FAQ

[Top]