The rise of applications that require reliable, robust location information has increased rapidly in recent times, and location and context-aware technology transcends numerous fields and areas, from autonomous robotics [1], inventory management [2], interactive multimedia [3], through to the monitoring of the health of vulnerable adults [4,5].
While GNSS technologies such as GPS are considering the 'gold standard' of modern positioning systems, their reliance on line-of-sight communication with satellites limits their practicality in indoor environments. RF-based indoor positioning systems, then, often turn to terrestrial technologies to provide reference points with which to locate devices, such as Bluetooth, Wi-Fi and Ultra Wide-Band (UWB). The use of Wi-Fi, for example, is nowadays ubiquitous for network and Internet communications, and while, for example, utilising channel state information (CSI) of wideband technologies like UWB can result in very high precision position estimation (in ideal conditions), Wi-Fi base stations remain a popular reference source due to the ability to leverage existing infrastructure. Information such as CSI, carrier phase or received power with respect to an array of static reference devices can be used to construct a unique fingerprint which can be mapped to a specific location or region. A database can be constructed of such fingerprints collected across a wide area, and used to construct an estimated channel model of that area.
Up until the last few years, the development of fingerprinting models for indoor positioning has largely treated fingerprints as simple vectors, utilising techniques such as artificial neural networks [6,7], decision trees [8] and k-Nearest Neighbour [9]. While this format is common in machine learning, positioning is an inherently geometric problem; any such model will ultimately infer the spatial relationship that maps fingerprints to coordinates, but 'flattening out' each fingerprint creates difficulty in incorporating information already known about the geometric structure of the environment or the relationship between individually collected fingerprints.
More recently, a field has emerged which extends conventional deep learning architectures to accommodate spatial and structural relationships, by operating directly on data structured as graphs [10,11]. Several models have been proposed since on graph-based positioning, but in general each proposition focuses on a single structuring of the fingerprint database [12]. In this paper, we present a current work-in-progress study which fuses two graph representations of a RF-based fingerprint database to increase the expressiveness of the training data.
The remainder of this paper is organized as follows: In Section 2, we briefly present Graph Neural Networks and the specific architectures used in this study. Section 3 describes the generation of a simulated indoor positioning dataset and the multi-graph model we evaluate. The current results of our work are given in Section 4, and in Section 5 we summarize our work so far and discuss the next stages of our study.
Graph Neural Networks [13] differ fundamentally from conventional neural networks in that the latter can only operate on data ordered in vector or matrix form. GNNs, by comparison, can operate directly on graph-structured data, allowing them to better leverage the relationship between data. We define a graph as a pair ๐บ = (๐, ๐ธ) comprising a set of nodes -or vertices -๐ and a set of edges ๐ธ โ ๐ ร ๐ defining relations between nodes. A node typically consists of a feature vector of fixed and consistent size (heterogeneous graphs that contain nodes of varying feature size do exist but are not considered for the purpose of this paper). GNNs are able to operate on graphs of arbitrary size, and are typically invariant to the ordering of nodes.
In a conventional feedforward neural network, each layer ๐ applies a transformation
where ๐ is a trainable weight matrix and ๐ is a trainable additive bias. ๐ is a non-linear activation function such as ReLU. We let โ (0) be the original input feature vector. This forms the basis for the transformation of node features in a Graph Convolutional Network (GCN). However, instead of a node applying a transformation of its own representation from the previous layer, a GCN aggregates the features of the node's neighbours, a process known as message passing:
Here, ๐ฉ ๐ is the neighbourhood of the ๐th node, and โ
๐ฃ the node embedding of neighbour ๐ฃ at the ๐th layer. 1 deg(๐) is a normalization constant which applies a weighting by the size of the node's neighbourhood. One can observe an analogy between the aggregation of neighbouring nodes in a GCN and the convolution of a filter with, say, an image within a layer of a Convolutional Neural Network.
By applying Equation 2 over a number of layers, a given node's representation incorporates information from deeper into the network. A three-layer GCN, then, will incorporate the features from nodes three 'hops' from that node. Reaching a balance in the number of layers to use is an important consideration; in a feedforward neural network, too many layers can result in vanishing gradients or overfitting. In a GCN, there is an additional risk of every node embedding essentially converging to the same value, as more nodes are being shared in the aggregations of each node.
Kipf et al. [14] further extended the update function to account for the observation that nodes with a larger neighbourhood will naturally disseminate information wider than one with fewer neighbours.
They update the normalization constant of Equation 2 to redress this by increasing the weighting of nodes with smaller neighbourhoods:
In some implementations, edges can be optionally assigned a numerical weight, to increase the influence of certain nodes over others. For example, in a geometric scenario, one could weight edges by similarity or distance between nodes. After a set number of message passing layers, the resulting node embeddings can be returned as-is, further transformed, for example via a feedforward neural network, or aggregated with other nodes to give a single graph-level representation.
Graph Attention Networks [15] (GATs) are an adaptation of GCN which differ in the way in which they aggregate each node's neighbourhood. From Equation 3 one can note that the update functions is an isotropic aggregation in which each node equally contributes towards the new representation of a node, while other implementations that allow for edge weighting require these weights to be known and specified in advance. GATs assign a different weighting to each edge via learnable 'attention coefficients':
where โ is the concatenation operator. ๐
๐๐ applies a softmax to the so-called 'attention score' ๐
๐๐ , the purpose of which is to calculate the relative importance of a particular neighbour.
We propose a graph-based model that models both the relationship between individual fingerprints in a pre-collected database, and the underlying geometric structure of the environment. To achieve this, we consider a fingerprint database comprising the received power, phase and delay spread between a given location and a set of static reference points (RPs) within an indoor environment. This database is then transformed into two graph representations; one based primarily on the sampled locations, and the other on the reference points.
In the former case, which we will denote as the fingerprint graph, we define a graph ๐บ fp (๐ fp , ๐ธ fp ) with each node ๐ฃ ๐ โ ๐ fp being a point in the fingerprint database sampled at a given location with initial node feature โ (0) ๐ฃ set to the concatenated fingerprint (comprising the received power, phase and delay spread) from each RP at ๐ฃ. In our study we use an environment with eight RPs, and therefore have an initial feature vector of length 24. For each node ๐ฃ โ ๐ fp , for some value ๐ โ N, ๐ โฅ 1 an incoming edge is created between the ๐ most similar fingerprints (by euclidean distance) and ๐ฃ. In our experiments we find that ๐ = 3 yields optimum performance. This graph is static throughout training, For the RP graph, ๐บ RP , we instead define a fully connected graph (every node has a bidirectional edge to all other nodes, without, in this case, self-loops) in which the nodes are defined as the individual RPs. The node features for this graph are unique to each individual location sampled in the fingerprint database; for each location we get the initial node state of the 3-feature fingerprint for each RP.
We divide our fingerprint database into a train and test set, and construct a single fingerprint graph for the training set. When considering a given location, we identify that node in the fingerprint graph, and distribute its feature vector across the nodes in our RP graph. We pass the fingerpring graph through a GAT network, and the RP graph through a number of GCN layers. ReLU is used as the non-linearity for both models. The final node embedding of the targeted node is then extracted from the GAT network, and concatenated with a Global Mean Pool1 readout of the final RP graph. The resulting vector is then passed through a feedforward neural network, finally outputting a length-2 vector which we take as the coordinate prediction. A schematic of our model is shown in Figure 1.
To initially evaluate the potential of our positioning model, we constructed an approximately 368 m 2 simulated environment indicative of a medium-sized office floor, comprising a number of rooms varying from 4.1 m 2 to 50 m 2 connected by corridors. The environment was constructed using the Blender ยฎ 3D modelling software [16], and imported into the Remcom Wireless InSite ยฎ EM propagation software [17]. The environment was divided into a grid of 3.68 million 1 cm 2 squares, into which a receiver antenna was positioned. Eight transmitters were placed throughout the environment, along the main corridor and in each of the large atriums. Figure 2a shows the positions of the transmitters, indicated in green.
The receivers and transmitters were configured according to the parameters given in Table 1 and the EM environment configured as in Table 2, and pairwise propagation simulations performed between every Tx and Rx, from which received power, phase and delay spread were obtained. An example of a received power plot is shown in Figure 2c.
While such a high resolution dataset would be impractical to gather in reality, we are able to sample from the dataset to emulate measurement campaigns of varying degrees of coverage and uniformity [16,8] [32,16] without the need to perform multiple time-consuming simulations. In this instance, to replicate the performing of a realistic fingerprint measurement campaign as closely as possible, as well as to allow for the future extension of this environment towards training with sequential path data (for which the availability of robust public datasets is limited), random walking paths through the environment were generated using MATLAB's Navigation Toolbox. Positions were sampled every 10 cm, and the power, phase and delay spread estimated by means of linear interpolation. A total of 137 paths, shown in Figure 2b, were generated for the purpose of this study, comprising 30 496 individual locations. Gaussian noise was then applied to the data to add additional uncertainty to the simulated data.
All data in the fingerprint database, including the ground truth labels, was standardized prior to use using so-called robust standardization, a variant of Z-score standardization more robust against outliers which uses the median and inter-quartile range of each feature in place of mean and standard deviation, respectively.
The graph models were implemented using PyTorch Geometric [18], an extension to PyTorch for graphbased learning, and trained using the Adam optimizer, and MSE loss functions. Batch size was set to 32, and the learning rate 1 ร 10 โ4 . The hyperparameters tuned for our model are given in Table 3.
We compared the accuracy of our model against several reference models; kNN, for values of k from 1 to 30 and using cosine, euclidean and Manhattan distance metrics; Random Forest [19] with 8, 16, 32, 64, 128, 256, 512 and 1024 trees; and a multilayer perceptron (MLP), with tuned hyperparameters for the number of layers and hidden channel size. In addition, the multi-graph method was compared with the performance of each respective graph model alone.
The performance of the optimum models and benchmarks are summarized in Figure 3. We can see from the results that our model appears to improve upon these benchmark models by a significant degree, with a 29% reduction in average error than using just an MLP, the best performing non-graph model. It is also interesting to observe that the combination of both the fingerprint and RP graphs results in a greater accuracy than either graph model used individually. This suggests that both graph representations capture and utilise information not present in the other, and further supports the argument that graph-based models are a promising and effective way of incorporating relevant structural information that would otherwise have been lost in a simple vector-based fingerprinting model.
We observe that our model results in significantly fewer outliers, which contributes strongly to the improvement in mean accuracy, though median error is currently higher than our benchmark models (Figure 4. The maximum error encountered using Random Forest, for example, was over 30 metres, compared to 5.43 m using our own model. The coverage of our dataset is not uniformly distributed throughout the environment; the corners of rooms in particular are sparsely sampled in comparison to high-traffic areas such as the main corridors. Distributed and crown sourced walking surveys is a common means of data collection for positioning systems [20], though more so in models that locate a user to within a discrete region as opposed to specific coordinates, and achieving uniformly distributed training data can be time consuming. Accordingly, the kNN model struggled to correctly position locations at the boundaries of the sampled area. By comparison, our model was able to position outlying test locations to within 2 m, even in these sparse regions.
With respect to data collection, we note that the 10cm resolution at which locations were sampled for the purpose of training the models may present challenges when transferring this method to the real world. While this resolution may be possible at an acceptable sampling frequency using bespoke hardware, smartphones are typically constrained in their maximum sample rate. In recent versions of the Android operating system, for example, the time to complete a scan of broadcasting WiFi devices and their signal strengths is around 3-5 s depending on handset model [21]. A data collection campaign of the scale described in our paper could take many hours to complete, even accounting for a division of labour using multiple devices. A possible solution to this is currently ongoing, which is investigating the feasibility of transfer learning, which has previously been applied to RF data [22,23], to augment a smaller amount of manually sampled locations with a higher resolution synthetic dataset, to allow for a shorter data collection campaign while maintaining acceptable localisation performance.
We have presented a new RF-based positioning model which combines two different graph representations of a simulated indoor environment. Current results have indicated a 32 cm improvement over all benchmarks, and stronger performance compared to the use of only one or the other graph representation. Considering future work, with respect to the fingerprint graph, at present we only consider each location independently, and incorporating new ones into the graph does not affect the rest of the graph (new incoming edges can added to allow information to propagate to unseen nodes, but this does not allow information flow in the other direction). One might consider the case where multiple users are present in the same environment. In this case, it may be advantageous to consider the relationship between users, turning this problem into one of collaborative positioning. Future work is, at the time of writing, underway to investigate the potential for this model to be extended into a collaborative one, to explore the use of temporal data (the dataset having been constructed as a set of walking paths) to further improve model performance, and to further evaluate performance against industry standard datasets such as UJIIndoorLoc [24]. Noting the improvement in accuracy in outlying regions of our environment, we also wish to explore the extent to which our model is able to mitigate against inconsistent and non-uniform measurement campaigns.
Liam M. Self was supported by the UK Engineering and Physical Sciences Research Council (EPSRC) grant EP/S023046/1 for the EPSRC Centre for Doctoral Training in Sensor Technologies for a Healthy and Sustainable Future.