Ad Hoc Positioning Systems (APS)

Dr. Dragos Niculescu, Researcher
NEC Laboratories, Princeton, NJ


Position and orientation of individual nodes in ad hoc sensor networks are useful for both service and application implementation. Services that can be enabled by availability of position include routing and querying. At application level, position is required in order to label the reported data in a sensor network, whereas position and orientation enable tracking. Nodes may have local capabilities such as the possibility of measuring ranges to neighbors, angle of arrival (AOA), or global capabilities, such as GPS and digital compasses. We present a family of positioning algorithms that use the basic idea of distance vector routing to find positions in an ad hoc network using only a fraction of landmarks (GPS enabled nodes). All the nodes in the network are assumed to have the possibility of measuring: ranges, angle of arrival (AOA), orientation, or a combination of them. We analyze the error characteristics of three classes of APS algorithms, under various conditions of network density, measurement error, and landmark ratio. Range free, range based, and multimodal algorithms are shown to have similar error behavior, with covariance error inversely proportional to the landmark ratio and TTL used; dependence on network density is also characterized.