A Converging Distributed Positioning Algorithm for Internet-of-Things.
As Internet of Things (IoT) is being actively research and shaped a number of issues remain unresolved. One of such issues is a potential to perform positioning and navigation tasks with IoT network nodes by employing Radio Frequency (RF) communication channels. Positioning information can be beneficially employed in numerous tasks, ranging from indoor localization, to security and data integrity verification. Positioning methods have been proposed over the years based on Received Signal Strength Indicator (RSSI), Time of Arrival (ToA), Time Difference of Arrival (TDoA), and Angle of Arrival (AoA) . Initial approaches relied on a priori knowledge of networks geolocational distribution or on an extensive profiling of networks parameters, such as RSSI fingerprint mapping. While such approaches might be valid for small scale scenarios, in the context and scale of IoT application they become unfeasible.
Positioning and ranging methods used in a true Ad-Hoc localization on IoT network have a need to integrate nodes working on various existing wireless communication technologies and protocols such as WiFi, ZigBee, Bluetooth, etc. with varying communication ranges and power levels. The most universal ranging method in such case is based on ToA measurements. ToA ranging with a 1ns accuracy can provide ranging estimation resolution of up to 0.33 m, which in turn, given satisfactory geometry, can produce an adequate positioning solution . Due to the nature of IoT nodes, high energy and computational constrains are placed upon localization tasks.
II. RELATED WORK
There exist a number of algorithms for localization and positioning solutions in Ad-hoc networks and subsequently IoT. These solutions can be distinguished by the level of accuracy and decentralization they are capable of, yet there is no one definitive approach. Such a distributed ad-hoc network positioning solution would provide an enabling impetus for a number of Machine-to-Machine (M2M) applications . Accuracy is both a function of employed measurement techniques  and algorithms used to compute positioning solution. The most prevalent measurement techniques are:
--Time of Arrival (ToA) which requires clock synchronization among network nodes.
--Round Trip Time (RTT) which requires high timing resolution and standardized packet processing time, however current IoT software and hardware setups are unable to fulfill these requirements.
--Angle of Arrival (AoA) requires specific hardware to estimate the direction from where RF signal has arrived.
--Received Signal Strength Indicator (RSSI) is highly unreliable as a measurement due to its strong susceptibility to noise and signal attenuation.
From these types of measurements, range estimation derived from RTT timing information is the most universal, though still hardly applicable to IoT networks due to low timing resolution in existing wireless network modules produced for IoT applications. However, probable technological improvements in networking hardware will allow it to become a viable and dominant ranging method. Less popular approaches to the problem of ranges estimation are also being developed  with the promise to reduce the impact of high timing resolution requirement.
The most basic algorithm used for positioning based on range estimation is trilateration . While being capable of providing positioning solution, it is limited to work with only 4 ranges and cannot make use of additional measurement. A more mathematically advance solution is Linearized Least Squares (LLS) algorithm. LLS comes with increased computational complexity which grows exponentially with the number of available observations. Performance of different algorithms has been extensively studied ,  and a growing consensus is focused on distributed algorithms  as the predictions of the scale of IoT is increasing . Distributed localization algorithms are extensively discussed in ,  with specific focus on positioning errors .
III. POSITIONING FOR IOT
Let our IoT network be comprised of three types of nodes and possess ability to store local and absolute positioning solutions.
--Network Node (NN) is such a node that is static position wise. It has capabilities to send and receive data and perform RTT ranging measurements with other nodes it has direct communication.
--A User Node (UN) is such a node that is mobile, has capabilities to send and receive data and perform RTT measurement with NNs.
--A Local Reference Frame (LRF) is set of minimum 4 interconnected NN. None of three NN may lay on a straight line and the forth NN must be outside of the plain, formed by the first three NN. Such interconnected set of NNs forms a tetrahedron in three dimensions.
--An Absolute Positioning Solution (APS) is a positioning solution independent and external to LRFs in IoT. It can be obtained by the NN directly, provided by Global Satellite Navigation Systems (GNSS), if NN has relevant technological capabilities, or indirectly through ranging UNs and incorporation of UNs APS coordinates into IoT localization algorithm.
--A Virtual Network Node (VNN) is a UN positioning solution conducted in one or more LRF. Such VNN can contain an APS coordinates provided by independent UN feature. VNN is used to relate two or more overlapping LRFs and translate LRF's coordinates to APS.
--Network Convergence (NC) can be a local (lNC) or a full IoT subnetwork event, where the coordinates of NN in LRF are replaced by APS coordinates. Once NC is achieved, IoT positioning solution converts to an APS augmentation/substitution solution and is fully compatible with other APS systems such as GPS, Galileo, Glonass, etc.
In order to perform positioning in three dimensions at least four NNs must be in direct contact with each other. Communication between these nodes provides both possibility to perform direct ranging measurements and the exchange of information. During the initialization stage each node performs RTT observation with all neighbouring NN that are in its range. Such measurements produce two separate results for each individual pair of neighbouring NN. These results are shared in between them and averaged to reduce the measurement noise.
All measurements are aggregated into individual databases containing NN's id and a range estimate. Each NN in its private LRF is designated as [NN.sub.0] and its position is defined as [X.sub.0] = 0, [y.sub.0] = 0 and [Z.sub.0] = 0. Ranging measurements between NNs in LRF are defined as [r.sub.ij], where i and j represents the indexes of the NNs inside a specific LRF, where index i represents the origin node and index j represents connected node. It is noteworthy that NN can and usually does belong to multiple LRFs and its reference indexes are different for each individual LRF.
Further, each individual node shares its own database with immediate NN. After this stage, each individual node collates obtained measurements and performs search through existing database to identify such connecting NNs, that at least a single tetrahedron can be formed. In case multiple tetrahedrons can be formed, algorithm then seeks to merge such tetrahedrons that share two additional NNs.
After the search, all duplicates are removed ensuring that only unique tetrahedrons are contained in the databases. Each tetrahedron originates on the host node such that coordinates assigned to it are [x.sub.0] = 0, [y.sub.0] = 0 and [z.sub.0] = 0. For each tetrahedron a trilateration algorithm is applied. The first neighboring NN receives such coordinates that it is placed on the LRF's X axis: [x.sub.1] = [r.sub.01], [y.sub.1] = 0 and [z.sub.1] = 0. The coordinates of the second and the third neighbouring NN for a LFR associated with the host NN are computed using (1):
[mathematical expression not reproducible]. (1)
When the coordinates of all NNs in the tetrahedron are computed, they are combined in a LRF by computing rotation matrixes between two tetrahedrons and converting coordinates into unified LRF comprising of all unique tetrahedrons that the host NN was able to form with neighboring NNs. The computation of rotation matrixes involves Linearized Least Squares (LLS) algorithm as no analytical model can be applied due to noisy measurements. The size of matrixes involved in the computation of LLS solution is constrained to the size of 3 x 3, thus does not amount to significant computational requirements for each individual node.
Once this stage is complete, the network is populated with overlapping LRFs. The orientation of each individual LRF is random and does not correlate with its neighbours. Further aggregation of LRF is not advisable as errors from ranging measurements propagate into rotation matrixes and positioning error significantly increases with the increase of distance between host NN and nodes being aggregated into LRF. Every connected neighbouring LRF is ensured to share mutual nodes, thus transition of positioning solution between two neighbouring LRFs is possible. The continuous positioning solution between unconverged LRF is obtained through the fact that neighbouring LRF have a significant overlapping. Once UN enters such overlapping zone, its position is computed in both LRF in parallel.
During the transition of UN through a LRF a set of [VNN.sub.i] is created, where i = 0:n. As VNNs are created with each successful set of ranging measurements, positioning solutions from all overlapping LRFs, that has performed their measurements in that point in space, can be directly matched. In case that UV does not possess independent measurement capability, the feature can be successfully applied if linear motion of the UV is assumed. Additionally, with sampling rate sufficiently high in relation to UV's movement speed, a linearization assumption can be adopted, such that trajectory of the UV is interpreted as linear for time equal to the period between the measurements.
In case two LRF's are connected with less than 3 mutual nodes, or have NN in-between them that did not have a possibility to form its own LRF, continual localization could be enabled by creation VN or external independent means such as Inertial Navigation (IN).
A. Node Specific Positioning
When a User Node (UN) enters an area, where it can obtain at least 3 ranging measurements to 3 distinct NN of a LRF, a trilateration algorithm can be performed and a solution for its relative position inside LRF can be obtained. If UN is capable of higher computational performance, LLS algorithm can be employed to achieve higher accuracy, since more measurements can be employed in calculation of a positioning solution.
In case a UN has an independent positioning solution, its results can be transferred to LRF. Each individual measurement is then treated as a VNN with APS coordinates associated with it, as represented in Fig. 2, where [V.sub.0] represents estimated position of UN at measurement time [t.sub.0], [V.sub.1] represents estimated position at measurement time [t.sub.1], etc. If the nature of such independent positioning solution provides only relative UN positional changes (e.g. inertial navigation), it can be used to augment ranging solution inside LRF. If independent UN's positioning solution is able to provide absolute coordinates (e.g. from GNSS), such VNN is incorporated into LRF and is used to achieve NC. In order to translate NNs coordinates from LRF to APS, NN must have connections to three VNNs or NNs with APS solution. Required three VNNs or NNs must not be positioned on a line. Once sufficient amount of measurements is collected, LRF can be migrated to absolute coordinate system as each of its NN is connected to at least three other NN. LRF is then considered to be fully converged. The quality of positioning solution can further be augmented with additional measurements and observations of higher geometrical quality.
B. Convergence of the Network
When LRF obtains positioning solution for its nodes in absolute positioning system, solution can be migrated to neighboring LRF. Such migration can be achieved because neighboring LRFs share a number of NN. If at least 3 NN of LRF obtain coordinates in absolute positioning system, transition from local coordinates to absolute can be obtained with rotation matrix by computing rotation LRF around its origin. Such approach avoids pitfall of drastic error accumulation when LRF are being conjoined with only relative positions derived from ranging estimations.
If neighbouring LRF shares less than required 3 NN, o a neighbouring NN does not have sufficient number of its own neighbours to form LRF, and introduction of VNN is insufficient to meet this requirement, NN's coordinates in absolute positioning system can be approximated. This approximation can be further enhanced with either new VNN being provided by a new UN, or by having a connection to a different adjacent LRF that has converged to absolute positioning system.
Simulation has been performed in MATLAB environment. A set of 100 nodes were randomly distributed in a volume of 30 m by 10 m by 5 m as represented in Fig. 3. A maximum communication distance has been introduced and computed ranges were subjected to 2 % random noise of ranges estimation via RTT for communication range of 5 m.
When simulation is initialized, no positioning information is present in the network. First LRF are created for each individual NN. In actual implementation of algorithm, this step would not be instantaneous as ranging estimates would be collected and distributed in a P2P manner. Given the immobility of the NN individual ranging estimates would form from natural communication and data relay between NNs in an ad-hoc network and precision could be increased by averaging measurements over period of time. Once ranging information is obtained, each node creates an individual database. For the purposes of simulation database has been aggregated in a single structure. While in actuality duration of the formation of each individual LRF can vary, for simulation purpose we compute all LRF at [t.sub.0]. Computed LRF are not aligned in absolute positioning system and are randomly orientated. Its orientation being dependent on the first two nodes it managed to form a tetrahedron.
Once LRFs are computed UNs are released to the simulated environment. UN movement is simulated over time with the sampling rate of 1s as a discreet set of ranging measurements with equal constrains as were applied to NN. Each UN is moving in a linear trajectory at the speed of 1 m/s. VN are created only if 3 ranging measurement are performed with individual LRF. If UN is in an overlapping zone between two or more LRF and has at least 3 ranging measurements with each individual LRF, VN obtains positioning solutions in all LRFs. Once UNs finish their routes, networks status is investigated in relation to NN positioning accuracy and LRF convergence to absolute positioning system.
The evaluation of algorithms performance has been acquired over 100 simulations. Such sample size has been chosen to average out the geometric influence to the positioning solution from the random nature of NN locations. Additionally, UN trajectories also have been randomized.
Figure 4 shows the distribution of number of connections for NNs in the simulated network. Higher connectivity produces consistent UN positioning solution due to overlapping LRF and enables faster network convergence. Nodes with connection number lower than 3 are unable to form LRF. Figure 5 shows average positioning error for randomly generated UNs moving on a linear trajectory through the network. UNs cleared the networks coverage area in under 14 steps. During each step VNN were created if LRF was present. Positioning error in initial simulation steps is significantly higher due to unfavourable geometry as UN enters the simulated network and has NN located only in front of it. As the UN moves further through simulated space, it enters the network and becomes surrounded by NN. Having NN located around UN produces higher accuracy positioning solution.
After simulation was performed 26 % of NN have achieved convergence. Although full network convergence has not been achieved, it is noteworthy that only with 3 UN having APS functionality and following a random straight line path, local NC occurred in four zones. Additional iterations improve networks convergence level and positioning accuracy significantly as presented in table I. Full network convergence has not been achieved as NN on the fringes of the network have not been able to form LRFs.
V. DISCUSSION AND FUTURE WORK
Results presented in simulation section are a proof-of concept for an algorithm to study the possibility of LRFs utilization for positioning purpose inside the IoT network. Simulation has validated the concept of translation of coordinates between LRFs in order to achieve continuous positioning solution for UN. For future work a comparative analysis between proposed and centralized positioning algorithms is planned in order to assess the power and bandwidth requirements for proposed algorithm. Network did not achieve 100 % convergence due to the facts, that a) not all randomly place NN could form LRF and thus could not obtain coordinates relative to other NNs and b) trajectories of the UNs were linear and not evenly distributed throughout the network due to the random nature of their origin and direction of movement. An actual IoT positioning system would not be limited to several UN appearances, thus performed simulation presents only limited view of the systems performance, however we have simplified it by omitting influences on accuracy from varying noise levels, signal multipath, packet loss and movement of NN, thus such simulation more accurately represent a snapshot of network convergence, rather than its full functionality. Proposed algorithm would best be deployed in an indoor environment densely populated with IoT NNs. Real life applications range from localization tasks in industrial environments such as warehouses, to indoor/urban canyon settings where GNSS signals are obstructed or outright undetectable.
In real life applications such algorithm would be operational over long periods of time, gathering additional data from VNNs and improving its positioning solution. Investigation of such influences is reserved for future studies.
Future work also includes an integration of independent measurements in UN such as inertial navigation, GNSS, magnetometer in order to investigate possible enhancing effects of these independent measurements and their fusion in a prototype system, that will be deployed in order to evaluate real life performance in noisy environment, to estimate power consumption and necessary throughput in order to achieve seamless positioning for moving UN.
This paper presents a novel converging distributed positioning algorithm for IoT applications. It is capable of performing localization in an independent decentralized fashion. Presented algorithm is designed to be deployed over ad-hoc IoT networks in order to provide a seamless positioning solution for UN. Algorithm is based on distributed, overlapping LRFs, each providing an independent relative positioning solution. Such distributed approach reduces communicational and computational overhead in the system. A relative position of an UN inside LRF can be integrated with prior UN's APS and extend its functionality through sensor fusion techniques. Furthermore, LRF approach reduces the potential privacy issues concerning location tracking, as UN position is computed in a distributed fashion and is not broadcasted throughout the network. The algorithm is designed to incorporate independent measurements of opportunity in order to enhance its positioning solution over time via creation of VNNs. By employing independent measurements, the network is able to achieve local or global convergence with absolute positioning systems such as GNSS.
Proposed algorithm has been simulated in MATLAB environment with the focus on its ability to perform continuous positioning between overlapping LRF and its ability to converge to absolute positioning system with integration of external independent measurements via incorporation of VNNs. Positioning accuracy of the algorithm presented in this paper is directly dependent on the quality of available RTT measurements, geometry of these measurements and availability of independent measurements. Proposed algorithm does not provide enhancements to the accuracy of positioning solution, but rather enables UN to achieve relative or global, if NC is achieved, positioning solution in a fully distributed manner.
The goal of this paper was to evaluate the possibility to use overlapping LRFs for continuous distributed localization solution and investigate possible full or partial convergence of the IoT network to the APS. Performed simulation of a IoT network containing 100 NN reached 74 % convergence rate after 8 simulation iterations with UNs generated on the fringes of the network and moving in a linear trajectory at a random direction through the network. Both goals of providing a distributed positioning solution and obtaining partial NC have been successfully achieved, as illustrated in results section, thus validating the proposed algorithm. Proposed algorithm is capable to provide identical coverage of positioning solution as a centralized localization method, with significantly reduced computational complexity and data transmission via the IoT, and reduced concerns to user's privacy.
 H. Liu, et al., "Survey of wireless indoor positioning techniques and systems", IEEE Trans. on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 37, no. 6, pp. 1067-1080, 2007. Online. [Available]: https://doi.org/10.1109/TSMCC.2007.905750
 Y. Zheng, Y. Liu, "Quality of trilateration: Confidence-based iterative localization", IEEE Trans. Parallel and Distributed Systems, vol. 21, no. 5, pp. 631-640, 2010. Online. [Available]: https://doi.org/ 10.1109/TPDS.2009.90
 P. K. Verma, R. Verma, A. Prakash, A. Agrawal, K. Naik, R. Tripathi, M. Alsabaan, T. Khalifa, T. Abdelkader, A. Abogharaf, "Machine-to-Machine (M2M) communications: A survey", Journal of Network and Computer Applications, pp. 83-105, 2016. Online. [Available]: https://doi.org/10.1016/jjnca.2016.02.016
 A. Savvides, C.-C. Han, M. B. Strivastava, "Dynamic fine-grained localization in ad-hoc networks of sensors", in Proc. 7th annual Int. Conf. Mobile Computing and Networking, 2001. Online. [Available]: https://doi.org/10.1145/381677.381693
 K. Bagdonas, H. Schioler, K. Borre, "Range estimation for indoor positioning via drifting clocks", in Proc. 22nd Int. Technical Meeting of the Satellite Division of the Institute of Navigation, 2009.
 W. Murphy, W. Hereman, "Determination of a position in three dimensions using trilateration and approximate distances", in Department of Mathematical and Computer Sciences, Colorado School of Mines, Golden, Colorado, MCS-95, 1995.
 Y. Shang, H. Shi, A. A. Ahmed, "Performance study of localization methods for ad-hoc sensor networks", in Mobile Ad-hoc and Sensor Systems, 2004.
 D. Macagnano, G. Destino, G. Abreu, "Indoor positioning: A key enabling technology for IoT applications", IEEE World Forum on Internet of Things (WF-IoT 2014), 2014. Online. [Available]: https://doi.org/10.1109/WF-IoT.2014.6803131
 C. S. J. Rabaey, K. Langendoen, "Robust positioning algorithms for distributed ad-hoc wireless sensor networks", in USENIX Technical Annual Conference, 2002.
 J. Gubbi, R. Buyya, S. Marusic, M. Palaniswami, "Internet of Things (IoT): A vision, architectural elements, and future directions", Future Generation Computer Systems, pp. 1645-1660, 2013. Online. [Available]: https://doi.org/10.1016/j.foture.2013.01.010
 H. Wymeersch, J. Lien, M. Win, "Cooperative localization in wireless networks", IEEE Proc., vol. 97, no. 2, pp. 427-450, 2009. Online. [Available]: https://doi .org/10.1109/JPROC.2008.2008853
 M. Guoqiang, B. Fidan, B. Anderson, "Wireless sensor network localization techniques", Computer networks, vol. 51, no. 10, pp. 2529-2553, 2007. Online. [Available]: https://doi.org/10.1016/ j.comnet.2006.11.018
 D. Niculescu, B. Nath, "Error characteristics of Ad Hoc positioning systems (APS)", in Proc. 5th ACM Int. symposium on Mobile ad hoc Networking and Computing, 2004. Online. [Available]: https://doi.org/ 10.1145/989459.989463
Kazimieras Bagdonas, Nerijus Jusas, Algimantas Venckauskas
Department of Computer, Faculty of Informatics, Kaunas University of Technology, Studentu St. 50, LT-51368 Kaunas, Lithuania
Manuscript received 24 April, 2017; accepted 18 October, 2017.
Caption: Fig. 1. Formation of tetrahedrons for NN 1.
Caption: Fig. 2. Observation of the VNN over its trajectory.
Caption: Fig. 3. NNs of a simulated network.
Caption: Fig. 4. Distribution of connectivity between the nodes of simulated network.
Caption: Fig. 5. Average positioning error for all simulated UNs during their crossing of simulated network.
TABLE I. SIMULATION RESULTS. Number of Network convergence Average positioning iterations level, % error, m 1 26 2.8 2 63 2.2 4 70 1.9 8 74 1.9
|Printer friendly Cite/link Email Feedback|
|Title Annotation:||System Engineering, Computer Technology|
|Author:||Bagdonas, Kazimieras; Jusas, Nerijus; Venckauskas, Algimantas|
|Publication:||Elektronika ir Elektrotechnika|
|Date:||Dec 1, 2017|
|Previous Article:||A Real-Time Parallel Image Processing Approach on Regular PCs with Multi-Core CPUs.|
|Next Article:||The Automatic Radio Transmission Systems Recognition.|