Efficient Sensor Localization for Indoor Environments Using Classification of Link Quality Patterns

Abstract

In ubiquitous sensor networks (USN), sensor node localization is normally performed with global positioning system (GPS) or radio signal strength (RSS) between a target node and reference nodes. Because GPS is not available in indoor environments, RSS-based approach is commonly used for indoor localization. However, RSS-based approach is hard to be applied to real indoor environments (e.g., home) because of signal interferences with various indoor obstacles such as walls, doors, furniture, and electric appliances. In this paper, we propose an efficient indoor localization method for Zigbee sensor nodes by classifying link quality indicator (LQI) patterns between a target node and multiple reference nodes rather than using calculation with RSS values. And we also present the results of indoor localization experiments in our ubiquitous home network test bed using the proposed localization method.

1. Introduction

In recent years, ubiquitous sensor network (USN) is globally accepted as an essential infrastructure for ubiquitous computing systems. And localization in USN becomes a very important functionality because the location-based service (LBS) is one of the most typical applications of ubiquitous computing [1–3].

Basically, localization in USN is performed by measuring strength, arrival time, or arrival angle of transferred radio signals between a target node and multiple reference nodes based on the theory that the measured values of signal strength (link quality), arrival time, or angle change with distance between the target node and the reference nodes. Those measured values are used to calculate location of the target node with the triangulation or centroid techniques. However, such methods are hard to be applied to indoor environments (e.g., ubiquitous home environment [4]) because of radio signal reflection, loss, and distortion caused by various obstacles, such as walls, doors, furniture, and electric appliances. Consequently, those interferences result in localization errors.

In this paper, we propose an efficient indoor localization method for Zigbee sensor networks using classification of link quality patterns between each reference node and a target node in a specific location rather than using calculation with signal strength, arrival time, or angle. To classify link quality patterns for each location, we used an artificial neural network (ANN) classifier trained for a target environment. Furthermore, we performed actual experiments in our ubiquitous home test bed to evaluate the proposed method.

The rest of the paper is organized as follows. Section 2 analyzes typical USN localization techniques as related works and discusses the problem to be faced when they are used in actual indoor localization applications. Section 3 describes the design of the proposed localization method in detail. Section 4 explains experimental environment and discusses experimental results of the proposed localization method. Finally, Section 5 summarizes the paper and describes the future research direction as conclusion.

2. Related Works

As mentioned above, typical localization techniques such as triangulation and centroid use received signal strength indicator (RSSI), time of arrival (ToA), time difference of arrival (TDoA), or angle of arrival (AoA) of radio signal transmission to estimate distances between a target node and multiple reference nodes. Recently, some researches [5–7] discuss indoor localization of sensor nodes in USN using LQI to measure distance between a target node and reference nodes.

RSSI measures the attenuation in radio signal strength between sender and receiver. The power of the radio signal falls off exponentially with distance, and the receiver can measure this attenuation in order to estimate the distance to the sender [8, 9]. ToA is based on the speed of radio wave propagation and the measured time it takes for a radio signal to move between two objects. Combining this information allows the ToA system to estimate the distance between sender and receiver [10]. TDoA techniques measure the difference of arrival times. It requires beacon nodes to transmit both ultrasound and RF signals simultaneously. A sensor will measure the difference of the arrival times between the two signals and determine the range to the beacon node. Unlike the previous techniques, which measure distance [11], AoA techniques measure the angle at which a signal arrives. Angles can be combined with distance estimates or other angle measurements to derive positions. AoA is an attractive method due to the simplicity of the subsequent calculations [12].

Thus, triangulation and centroid techniques based on RSSI, ToA, TDoA, or AoA methods are hard to be applied to indoor environments because of radio signal interferences caused by various indoor obstacles that result in estimation of wrong distances between a target node and reference nodes. Furthermore, reduction of battery power of the target or reference nodes may also affect estimation of the distances.

3. Proposed Localization Method

This section explains the proposed localization method in detail. In the proposed method, we applied symbolic localization [13] that provides location information referring to predefined abstract notions of place, for example, “Kitchen,” “Living room,” and “Bedroom,” because symbolic locations are more useful than specific physical coordination for most of the location-based services. In some cases where the underlying localization system provides only physical locations, the location-based service applications need to transform the given physical locations into some predefined symbolic locations to aware location context.

3.1. Measurement of Link Qualities

A traditional radio transceiver provides RSSI as a metric to determine link quality. The latest transceivers such as Chipcon's CC2420 Zigbee transceiver provides an additional metric called link quality indicator (LQI), which is a more comprehensive value reported by the radio that takes in multiple factors. LQI values are assumed to be more reliable to estimate link quality and have better correlation with distance between two sensor nodes than RSSI values [14, 15]. So, we choose LQI to measure link quality patterns for a target node.

Figure 1 shows how LQI values between the target node T and the reference nodes $R_1~R_5$ are measured and gathered. As shown in the figure, T broadcasts a beacon packet P periodically and the reference nodes in the vicinity receive P. After receiving P, each reference node gets the LQI value for reception of P and sends the LQI value to the base station that performs the localization procedure for T with these values.

Figure 1

LQI value measurement and gathering.

3.2. Classification of LQI Patterns

To classify LQI value patterns, we adopted ANN classifier [16, 17]. Actually, LQI values between the target node and a reference node are not always the same even when measured in the same position and environment. In addition, there could be loss of beacon packets for measuring LQI values due to unreliable Zigbee radio or transport protocol. The major benefit of using ANN is that it can provide feasible classification results with such unstable data based on its error tolerance feature.

The ANN that we use is the multilayer perceptron (MLP) [16] consisting of three layers: input, hidden, and output layers. As shown in Figure 2, we associate the input nodes with reference nodes $R_1~R_m$ and the output nodes with predefined symbolic locations such as “Kitchen” and “Bedroom.” An MLP model for localization is produced by learning patterns of LQI values between a target node and reference nodes in a supervised manner using the error back-propagation (EBP) algorithm [16]. Thus the resulting model represents the current location of the target node as associated with LQI values $x_1~x_m$ .

Figure 2

Structure of MLP classifier for localization.

In more detail, assume that $\overrightarrow{X}\equiv X_{\mathrm{1}}\times \cdots \times X_m$ is the domain of LQI value tuples, where $X_j$ is the domain of an LQI value $x_j$ from a reference node $R_j$ . A classifier learning dataset $D=\{d_1,\dots ,d_N\}$ and each learning data $d_i=〈\overrightarrow{x},c〉\in \overrightarrow{X}\times C$ , where C is the domain of a symbolic location c and $\overrightarrow{x}\equiv 〈x_{\mathrm{1}},\dots ,x_m〉$ is a tuple of LQI values measured at location c. Note that each LQI value ranging from 0 to 255 needs to be normalized to a scale of 0 to 1 for learning.

4. Experiments

4.1. Experimental Environment

Figure 3 illustrates our ubiquitous home test bed and the actual Zigbee sensor nodes used in the experiments. As shown in the figure, the test bed has 7 locations such as “Entrance,” “Living room,” “Bedroom,” “Bathroom,” “Kitchen,” “Guest room,” and “Back door.” And there are seven Zigbee sensor nodes including one mobile target node and six reference nodes indicated with red rounded rectangles. Each sensor node is developed with a CC2420 Zigbee radio transceiver [18] and basically acts as a wireless sensor node getting environmental data such as temperature, humidity, and brightness of the test bed. We used a Windows-based laptop PC as the base station and implemented the experimental localization classifier on the base station using WEKA [19], an open data mining library implemented in Java [20].

Figure 3

Our ubiquitous home test bed: (a) floor plan, (b) snapshot, and (c) Zigbee sensor node with CC2420.

4.2. Experimental Data

For learning and testing of the localization classifier, it is required to measure LQI values between the target node T and the reference nodes for each location of the test bed. We gathered LQI values for each location moving from the center of the location to the border of the location along with a spiral trajectory. At first, we gathered 100 tuples of LQI values for each location (i.e., total 700 tuples for 7 locations) and used the tuples to train the localization classifier. Figure 4 illustrates comparison of LQI value patterns among the three adjacent locations of the test bed: “Entrance,” “Living room,” and “Kitchen.” The diagrams are generated from the LQI value tuples used for learning. For reference, the x-axis displays each reference node and the y-axis displays normalized LQI values. As shown in the diagrams, the range of individual LQI values widely overlaps among the locations, but the tuples of LQI values at each location form distinguishable patterns.

Figure 4

Patterns of LQI values measured at (a) Entrance, (b) Living room, and (c) Kitchen.

4.3. Experimental Results and Discussion

After training the localization classifier, we gathered another 60 tuples of LQI values for each location (total 420 tuples for 7 locations) at randomly selected positions within the location to test the classifier. Table 1 shows the confusion matrix for the test results. As shown in the matrix, the overall localization accuracy is about 74.8%. Actually, in the real application environments where the trails of the target node are mostly concentrated around the center of each location, the overall accuracy would go up due to the reduction of misclassifications at the border areas (lightly shaded cells in the matrix).

Table 1

Result of the experiments. : Correct classifications, : Misclassifications at border areas, : Incorrect classifications.

Table 2 compares the localization results between different test datasets to show the effect of misclassifications at the border areas. The first row of the table summarizes the matrix in Table 1 where all the 420 LQI value tuples gathered at each location are used as the test data. And the second row of the table summarizes the localization results of using 280 tuples excluding 140 tuples gathered around the border of each location. As shown in the table, when we exclude LQI value tuples around the border areas, the localization accuracy goes up from 74.8% to 91.8%. Based on these results, we can insist that the overall localization performance would be feasible in the actual application environments.

Table 2

Effect of the misclassification at the border areas.

Test data		Results
	Correct	Misclassified	Incorrect	Accuracy
420 tuples	314	81	25	74.8%
including border data
280 tuples	257	16	7	91.8%
excluding border data

Table 3 shows additional localization result with the triangulation method using the dataset used to test the localization classifier in the previous experiments. To calculate location of the target node, we chose the 3 highest LQI values from each tuple of the test dataset and then identified locations of the 3 reference nodes that measured those highest LQI values. As shown in the additional localization result, interference with the walls of the test bed affected localization accuracy of the triangulation method, which is based on the theory that the measured values of link quality fall off with distance between the target node and the reference nodes. That is, with such a localization method, it is hard to provide proper localization accuracy in some indoor environments with obstacles such as walls of the test bed.

Table 3

Localization result with the triangulation method.

LQI data		Results
	Correct	Incorrect	Accuracy
420 tuples from the test data set (using the 3 highest values)	203	217	48.3%

In addition, it is possible to improve the localization performance more by using topological knowledge about the application environments. For instance, we can remove the incorrect classification results (darkly shaded cells in Table 1) using an adjacency matrix among the locations.

5. Conclusion

Localization is one of the most important functionalities of ubiquitous sensor networks because the location-based service is one of the most typical applications of ubiquitous computing.

In this paper, we proposed an efficient indoor localization method for Zigbee sensor networks using classification of link quality patterns between each reference node and a target node in a specific location rather than using calculation with received radio signal strength or arrival time. To classify link quality patterns for each location, we implemented an ANN localization classifier with WEKA and Java based on the proposed localization method. Furthermore, we performed localization experiments in our ubiquitous home network test bed using the actual Zigbee sensor nodes deployed in the test bed and the ANN localization classifier.

Finally, our future research direction will focus on indoor human location tracking and behavior recognition based on the proposed localization method and a temporal pattern recognition technique such as hidden Markov model (HMM) [21].