Cooperative Localisation: Distributed Optimisation with Hypothesis Testing

Lead Research Organisation: University College London
Department Name: Adastral Park Campus

Abstract

Critical locational information has long been used in a variety of military settings. In many of these settings, it would be advantageous if information concerning the spatial locations of particular entities and/or events could be conveyed. Localisation requirement has also become more pervasive and has found many strategic applications to the ground forces. For instance, the troops' safety can be directly linked to the degree of location-awareness of the troops and their enemies in a battlefield. For non-military applications, the first need to track a mobile user appeared as an essential public safety feature from the order issued by the Federal Communications Commission (FCC) in the US in 1996, which mandated all wireless service providers to deliver accurate location of an emergency 911 (E-911) caller to public safety answering points. Since then, various location-based services (LBSs) have emerged in the market, from identifying the whereabouts of a friend or employee to personalised LBS such as discovering the nearest cash machine. It is estimated that LBSs will generate annual revenues of the order of 10 billions worldwide.Providing a useful localisation will require, in some cases, metre-perfect resolution to be achieved over air. Yet, the fundamental physical challenges such as channel fading, low signal-to-noise ratios (SNRs), multiuser interference, and multipath conditions have put obstacles on meeting the objective. Our vision of next-generation (xG) localisation systems will be the provision of dynamic, distributed, robust and high-resolution LBSs. The realisation of these xG LBSs will require advanced signal processing and intelligence at the nodes to resolve the problem of interference and to detect the presence of a direct line-of-sight (LoS) for reliable ranging and localisation. Advanced multi-antenna technologies such as multiple-input multiple-output (MIMO) are expected to be adopted at mobile terminals for providing enhanced locational information as well as mitigating the multipath and multiuser interference.To achieve the needed LBSs, this project proposes to investigate the use of mobile user cooperation for localisation. The novelty of user or node cooperation lies in that nodes can work collaboratively by proper relaying to mitigate the multipath interference that can help identify the LoS for ranging in the presence of delay paths. The cooperation can, more importantly, exchange locational information from one node to another so that location ambiguity due to the lack of LoS signal paths could be removed and higher resolution can also be achieved. Another novelty of this proposal is the use of hypothesis testing based machine learning for the detection of LoS, which will be integrated with the cooperative signal processing for wireless localisation. This exceptionally challenging objective also has the potential to redefine the architecture of wireless networks, provide a novel system solution for organising the access of users to the system resources in this cooperative and self-regulating architecture, and revolutionise key areas of the 21st century ICT.Of particular relevance to the interests of DSTL, the areas that this project covers include:(1) Broadband signal separation - classification of LoS and non-LoS signals;(2) Detection - enhanced reception in multiuser and multipath interference channels using cooperative signal processing;(3) High-resolution localisation - determining the locations of mobile users in wireless environments;(4) Multipath mitigation - suppressing multipath interference using cooperative signal processing.The final outcomes of this project will not only elucidate the benefits of a wireless positioning problem using mobile node cooperation but also offer distributed algorithms for realising high-resolution localisation as well as address some key problems in communications systems.
 
Description We have designed algorithms that have realistically low computational and communication costs. It was also important to accomplish these with as little compromise to the accuracy as possible, even in high noise scenarios. In more detail, the following major issues were tackled:

• 3D probabilistic cooperative localisation. Probabilistic cooperative localisation algorithms have been developed with great success in the 2D case, resulting to a huge number of message passing variants. Unfortunately the aforementioned are computationally expensive algorithms and become even more so in the 3D case due to the added dimension in the solution space. We proposed a novel cooperative localisation algorithm, namely HEVA, that drastically decreases the computational cost in localisation, while at the same time improving localisation accuracy, even in high noise, 3D environments with NLoS affected communications. Monte Carlo simulations were run to showcase the improvements in both accuracy and computational costs relative to published algorithms in the literature.

• Reference-free 2D localisation. A hidden issue in cooperative localisation is the definition of the reference point. All literature either assumes that all nodes have a common reference point with precise knowledge of their relative location of it, or in the best of cases simply acknowledge the issue and the notes localized relative to each other and some arbitrary chosen reference point. We proposed a novel cooperative localisation algorithm, namely Grid-BP, that implements a unique ID grid reference system, overcoming the reference point issue. At the same time the algorithm offers parametric message passing allowing for very fast and efficient computational time.

• Combining local sensor based pedestrian tracking with cooperative localisation. There has been great development in the use of sensor based pedestrian tracking, or pedestrian tracking/GPS hybrid algorithms, but the research on pedestrian tracking/cooperative localisation algorithms has been quite limited. As a result, we have proposed a novel probabilistic hybrid INS/PDR tracking algorithm, named PHIMTA. PHIMTA can be used in a probabilistic temporal model with Grid-BP to offer high accuracy pedestrian tracking in GPS-denied environments.

• Message Scheduling in Distributed Message Passing algorithms. A lot of research has been done in message scheduling of centralized message passing algorithms, as the algorithm can be both optimized in communication overhead, and solution accuracy. Unfortunately there has been almost no research done in the distributed case due to the inherent lack of message scheduler with global knowledge of the network. We proposed a truly distributed message scheduling algorithm, namely SR-BP, which extends the advantages of R-BP in distributed scenarios, such as cooperative localisation or distributed spectrum sensing.
Exploitation Route A technical report has been submitted to DSTL.
Sectors Aerospace, Defence and Marine,Digital/Communication/Information Technologies (including Software),Electronics
 
Description Part of the work as a result of this project has contributed to forming the long-term strategy research strategy as documented in the BT long-term strategy research foundation theme report Q3 2013/2014, where they considered indoor localisation as an enabling technology following the fundings of this project. To be more specific, the idea of cooperative localisation which was addressed in the project, was considered as a potential technology that could build location awareness capability to BT's infrastructure on a national basis without requiring any field measurement campaigns or infrastructure deployments/upgrades. Our key findings show that high location accuracy for an acceptable confidence threshold is possible with cooperative localisation. The importance of this technique is that it could be used to build location awareness in existing infrastructure with no upgrades or field engineers performing measurements. This makes the proposed solution highly scalable. Various commercial opportunities based on location-aware infrastructure were presented in the document. In order to manage the overhead and computational cost of cooperative localisation approach, nodes should avoid flooding the network with messages. Since the algorithm is completely distributed and highly localised, each device only needs to compute the messages received from neighbours, to build the distance estimates. This means that the algorithm can be scaled to an arbitrarily large network size without any computational increase at each device, as long as the number of neighbours' remains to practical levels, that is, those observed in dense urban environments. Due to the heuristics nature of the solution convergence time cannot be guaranteed, however in practice simulation results show that message passing algorithm tend to converge to a fixed point of the solution domain within 10 iterations; practical computational complexity per device takes less of second for the algorithm to run.
First Year Of Impact 2013
Sector Digital/Communication/Information Technologies (including Software)
Impact Types Economic
 
Description BT Labs Short-term Localisation Project
Amount £3,200 (GBP)
Organisation BT Group 
Department BT Research
Sector Private
Country United Kingdom
Start 02/2013 
End 04/2013