# A Linear Algorithm That Can Locate Smartphones Without GPS

• Engineers develop self-localization algorithm that uses device-to-device communication.
• It performs all calculations locally and eliminates the need of GPS or cell towers.
• This linear model could be scaled to meet demands of billions of smart devices.

With 5G technologies, there is potential for networking billions of smart devices, the Internet-of-Things (IoT). At present, wireless devices use a centralized system to know their location. By centralized system, we mean “anchors” with known positions, like GPS or cell towers, that directly communicate with all devices.

The burden on anchors extends as the number of devices increases in a particular region. Thus a centralized positioning system can become unwieldy as the tracking devices grow significantly. The solution is to install new towers in highly populated areas, which increases the cost of communication system.

What if all heterogeneous devices were smart enough to perform sensing and calculations locally, so that there would be no need for any central coordinator? Well, developers at the Tufts University have built an algorithm to do the same.

It’s an alternative solution to centralized system that could enable devices running on 5G network to locate themselves without requiring direct access to GPS or cell tower.

In general this solution contains 2 stages-

1. Obtaining measurements, and
2. Transforming them into coordinate information.

### Distributed Localization Method

The self-localization algorithm uses point-to-point communication, and thus devices can effectively communicate in offices, underground facilities, under thick cloud cover, or even underwater.

Devices running on this method have advantages over the ones using GPS system. Not only they can perform better under extreme conditions (where GPS doesn’t work), but also cuts the cost of installation and maintenance cell towers.

However, the mobility of smart devices makes self-localization quite difficult. To simplify the calculations without compromising with accuracy, the positions should be rapidly tracked in real-time.

To do this, engineers replaced the non-linear position measurements — that are extremely resource demanding — with a linear model which can immediately converge on the precise position of the device.

The linearity of this setup is a consequence of a re-parameterization of the devices’ coordinates obtained by exploiting a specific convexity intrinsic to the device deployment. More specifically, a device doesn’t update its position with respect to an arbitrarily selected set of nearly devices, but depends on an optimally chosen subset of neighbors, called Triangulation set.

While searching for position, each device updates its coordinate estimate as a function of the coordinate estimates of its neighbors [in Triangulation set], weight by barycentric coordinates [the re-parameterization].

Reference: IEEEXplore | doi: 10.1109/JPROC.2018.2823638 | Tufts University

According to the developers, convergence to precise location is extremely fast, which makes real-time tracking of a huge amount of devices feasible.

### Applications

The solution could be scaled to meet the demands of up to 50 billion devices connected to 5G by 2020. Location awareness will enhance the capability of deploying new services with better management of the overall 5G network.

In addition to location-aware technologies, it could enable a wide range of applications, including asset tracking, intruder detection, precision agriculture and ocean data acquisition.

It will be extremely useful in emergency services to provide an effective response in disasters. Other related applications include physical security, military sensing, industrial and manufacturing automation.

Moreover, localization is crucial in randomly deployed networks, where network location changes during runtime, and manual positioning of objects isn’t practical.

Written by
###### Varun Kumar

Varun Kumar is a professional science and technology journalist and a big fan of AI, machines, and space exploration. He received a Master's degree in computer science from GGSIPU University. To find out about his latest projects, feel free to directly email him at [email protected]