Clustering and polygon merging algorithms for fingerprinting positioning in LTE

This paper presents new algorithms for generation of generalized radio maps for fingerprinting positioning in the long term evolution (LTE) cellular system. The algorithms use collected high precision positions of opportunity tagged with measured radio properties like cell ID (CID), received signal strengths (RSS), timing advance (TA) and angle of arrival (AoA) information. The high precision positions are obtained from assisted GPS (A-GPS) or observed time difference of arrival (OTDOA) positioning. All A-GPS and OTDOA measurements with the same tag (fingerprint) are then saved in separate clusters of high precision positions. In this way fingerprinted clusters covering the cellular network are created automatically. Finally, a polygon is computed to describe the boundary of each cluster, resulting in an adaptive self-learning positioning system. The paper refines the clustering step, by the introduction of cluster smoothing, outlier removal and cluster splitting, thereby reducing both the sizes and the irregularity of the clusters of positions. This improves the accuracy of the computed fingerprinted polygons of the generalized radio map. Algorithms for merging of the resulting multiple polygons (per fingerprint) are then presented, rendering one single polygon corresponding to the radio fingerprint. When used for positioning in LTE, the radio fingerprint is measured and the corresponding single polygon is looked up and reported to the end user.