Anchor-Free Multi-Level Self-Localization in Ad-hoc Networks

In this paper, we propose a multi-level localization algorithm that breaks a centralized localization problem into a cluster-level distributed localization problem, where each cluster is a centralized unit. In contrast to fully distributed localization, the cluster-level distributed scheme results in reduction in contention, communication overheads, convergence time and energy consumption because cluster heads are responsible for the intra cluster positioning on behalf of the whole cluster. To generate a global map, the cluster heads communicate with their direct neighbors to carry out inter-cluster ranging and positioning. The proposed method is suitable for large ad-hoc networks where most agents are low-cost, low-power RF transceivers used for ranging only while some agents are integrated with microcomputers such as Raspberry Pis capable of running intra and inter-cluster localization algorithms. The proposed system can work without anchor nodes and thus it can be deployed in the environments such as urban canyon, inside multi-story buildings, airports, and underground shopping malls where access to anchors or Global Navigation Satellite System (GNSS) is limited or prohibitive. We exploit a hybrid of two well-known methods: multidimensional scaling (MDS) and extended Kalman filtering (EKF) to effectively construct local and global position maps, even in the absence of GNSS information, anchors, or a complete ranging matrix.