Localization in Mobile Networks via Virtual Convex Hulls

In this paper, we develop a distributed algorithm to localize an arbitrary number of agents moving in a bounded region of interest. We assume that the network contains at least one agent with known location (hereinafter referred to as an anchor), and each agent measures a noisy version of its motion and the distances to the nearby agents. We provide a  geometric approach , which allows each agent to (i) continually update the distances to the locations where it has exchanged information with the other nodes in the past; and (ii) measure the distance between a neighbor and any such locations. Based on this approach, we provide a linear update to find the locations of an arbitrary number of mobile agents when they follow some convexity in their deployment and motion. Since the agents are mobile, they may not be able to find nearby nodes (agents and/or anchors) to implement a distributed algorithm. To address this issue, we introduce the notion of a virtual convex hull with the help of the aforementioned geometric approach. In particular, each agent keeps track of a virtual convex hull of other nodes, which may not physically exist, and updates its location with respect to its neighbors in the virtual hull. We show that the corresponding localization algorithm, in the absence of noise, can be abstracted as a linear time-varying system, with nondeterministic system matrices, which asymptotically tracks the true locations of the agents. We provide simulations to verify the analytical results and evaluate the performance of the algorithm in the presence of noise on the motion as well as on the distance measurements.