Decentralized algorithms for sensor registration

In this paper we investigate a problem arising in decentralized registration of sensors. The application we consider involves a heterogeneous collection of sensors - some sensors have on-board global positioning system (GPS) capabilities while others do not. All sensors have wireless communications capability but the wireless communication has limited effective range. Sensors can communicate only with other sensors that are within a fixed distance of each other. Sensors with GPS capability are self-registering. Sensors without GPS capability are less expensive and smaller but they must compute estimates of their location using estimates of the distances between themselves and other sensors within their radio range. GPS-less sensors may be several radio hops away from GPS-capable sensors so registration must be inferred transitively. Our approach to solving this registration problem involves minimizing a global potential or penalty function by using only local information, determined by the radio range, available to each sensor. The algorithm we derive is a special case of a more general methodology we have developed called "emergence engineering".