ࡱ > h j g l m I M A F R bjbj22 jXgjXgP > > 4 h v z! \ @ ! j @( @( @( @( h) B* T * , ? ? ? ? ? ? ? $ zC 0F ? * h) h) * * ? @( @( ( \@ 1 1 1 * ` @( @( ? 1 * ? 1 1 = = @( |Aϩ ", = }? r@ 0 @ = F , F , = F = * * 1 * * * * * ? ? - $ * * * @ * * * * F * * * * * * * * * > b : A n I m p r o v e d I n d o o r P o s i t i o n i n g M e t h o d B a s e d o n R e c e i v e d S i g n a l S t r e n g t h s S Z h a n g 1 , * , S L i 1 , 2 a n d W W a n g 1 ( T(WMR, )QY(WTS Nh?b/OpeW[h:y\OvUSMO) 1 S t a t e K e y L a b o r a t o r y o f N e t w o r k i n g a n d S w i t c h i n g T e c h n o l o g y , B e i j i n g U n i v e r s i t y o f P o s t s a n d T e l e c o m m u n i c a t i o n s , B e i j i n g , 1 0 0 8 7 6 , C h i n a 2 T h e S c h o o l o f C o m p u t e r S c i e n c e , C h a n g s h a U n i v e r s i t y o f S c i e n c e a n d T e c h n o l o g y , C h a n g s h a 4 1 0 0 7 6 , C h i n a * c o r r e s p o n d i n g a u t h o r ( * h:y,geO\O) E - m a i l : H Y P E R L I N K " m a i l t o : 1 1 1 1 1 1 1 @ 1 6 3 . c o m " 1 1 1 1 1 1 1 @ 1 6 3 . c o m , H Y P E R L I N K " m a i l t o : 2 2 2 2 2 2 2 2 @ q q . c om" 22222222@qq.com, HYPERLINK "mailto:33333333@sina.com" 33333333@sina.com Abstract. With the economy developing rapidly, Location Based Service (LBS) has attracted more and more peoples attention. Indoor positioning methods based on WLAN and RSS with advantage of low cost are most widely used. In this paper, we propose an improved indoor positioning method based on received signal strength to obtain better accuracy. We apply selected weighed K nearest neighbor (WSKNN) to get a better initial point of the gradient-descent-based location search (GLS) which is combined with exhaustive location search (ELS) to achieve a better result. Experimental results conducted in the real environments show that our proposed algorithm can obtain improvement of the mean error distance of 7.17% and 22.54%, compared with the GLS-CF method and traditional KNN method, respectively. Xd SOs,gexvzvv0Ǒ(uUOyel0_0RvwQSO~gT~W[pe(W1 0 0 - 2 0 0 *NUS͋ K e y w o r d s . F i n g e r p r i n t i n g ; I n d o o r L o c a l i z a t i o n ; L o c a t i o n S e a r c h I n t r o d u c t i o n A s t h e e c o n o m y i s d e v e l o p i n g r a p i d l y , t h e d e v e l o p e d t r a n s p o r t a t i o n a n d s p e e d y u r b a n i z a t i o n p o s e a g r e a t d e g r e e o f c o n v e n i e n c e t o p e o p le's lives. Thus, peoples demand for location-based information is more and more urgent and Location Based Service (LBS) comes into being. LBS is a kind of application whose functions are based on the locations of clients, such as kid's safety care system and location-aware information retrieval system [1]. Even though Global Position System (GPS) has been widely used for positioning purpose, it is virtually impossible to locate an object in an indoor environment. In the indoor environment, Signal propagation has the characteristics of multipath, non-line-of-sight, complex and changeable, therefore, GPS cannot be applied in the indoor environment [2]. Many techniques, such as Infrared Ray (IR), Ultrasonic, RFID and Bluetooth, have been utilized for indoor positioning. ORLs Active Badge System makes use of IR. But as it requires line-of-sight pass between clients Badge and sensors, the application scope of the system is limited [1]. The most widespread low-cost indoor localization solutions nowadays are those based on Wireless Local Area Networks (WLAN) signals taking advantage of heir Received Signal Strengths(RSS) [3]. In 2015, Bang et al. [4] proposed applying the curve fitting (CF) technique to establish the RSSdistance relation in indoor environments. In order to express clearly, we call their algorithm Bang method. Bang et al. used a series of linearly independent primary functions to construct a general RSSdistance model instead of using the log-distance PM, with the advantage of extracting the data change trend from only a few of RSS profiles. Then, they used two location search algorithms to find a mobile devices location after the subarea determination, namely exhaustive location search (ELS) and gradient-descent-based location search (GLS). However, ELS has a high computation complexity and GLS has a fast convergence rate. It is not a perfect choice to use them respectively. Moreover, Bang et al. employed the Nearest Neighbor (NN) as the initial point on which the GLS has a great dependence. In order to improve the efficiency of NN, K Weighed Nearest Neighbor (KWNN) can be employed. KWNN calculates the user location using the K nearest neighbors considering Euclidian distance and the weight. Selecting the nearest neighbors in KNN method is an experimental process dependent on the environment conditions such as the number and placement of APs and RPs. If some selective works could be done to those neighbors, this locating could be more accurate [5]. For the reasons above, we propose an improved method which applies selected weighed KNN as well as combined GLS and ELS with curve fitting (WSKNN) to obtain better accuracy. Indoor positioning based on gls and els 2.1. Positioning principle based on location fingerprints The positioning process based on location fingerprints is shown in Figure 1, where AP1, AP2, , APn represent the positions of n wireless routers, respectively. Additionally, (x, y) | (RSS1, RSS2, , RSSn) indicates the n wireless router signal strength received by the mobile user at the position of the point (x, y). EMBED Visio.Drawing.11 Figure 1. Positioning principle based on location fingerprints. The location fingerprinting method has two different phases: a training phase (off-line phase, calibration phase) to create a radio map utilizing coordinates of Reference Points (RPs) and a positioning phase (online phase) to calculate the user location. In training phase, channel modeling techniques can be used to create the radio map to prevent time consuming process of the actual measurements [6]. In positioning phase of fingerprinting, the RSS values of a mobile user with unknown location from several APs are measured. With the aid of comparing these values with the data in radio map, many different supervised methods can be applied to compute the user location and a basic one is KNN. 2.2. Positioning phase based on K Nearest Neighbor (KNN) In this method, the Euclidian distance between the observed signal strength of mobile user and all signal strengths in radio map collected during training phase is calculated to determine the best signal strengths that matches the one observed [7]. QUOTE We have the signal strength vector of ith RP as EMBED Equation.DSMT4 in the radio map collected in training phase, where i=1,2,,M and j=1,2,,N in which M is the number of RPs, and N is the number of APs. Then EMBED Equation.DSMT4 QUOTE is the signal strength of jth AP received in ith RP. Assume EMBED Equation.DSMT4 QUOTE is the signal strength vector of observed mobile user by jth AP. To find mobile user location, we can calculate the Euclidian distance between EMBED Equation.DSMT4 QUOTE and all entries in the set defined by the radio map as follow: [6] EMBED Equation.DSMT4 (1) After sorting the calculated QUOTE , a set of K data samples (RPs) with smaller Euclidian distance named nearest neighbors are picked up. K is an integer number between 1 and M in KNN algorithm. To estimate mobile user location, the smaller E declares the nearest corresponding physical coordinate [6]. So, all the K nearest neighbors should be weighted. If EMBED Equation.DSMT4 QUOTE shows the weigh of the ith selected RP (nearest neighbor) then EMBED Equation.DSMT4 QUOTE can be calculated by averaging the K neighbors equals EMBED Equation.DSMT4 QUOTE or can be determined by inversely proportional to the square of Euclidean distance [8] according to following: EMBED Equation.DSMT4 (2) Finally, mobile user location is calculated by: EMBED Equation.DSMT4 (3) 2.3. Review of the Bang method In the Bang method, they divided the whole indoor environment into several subareas and construct a fitted RSSdistance curve for each AP and each subarea. Then, they proposed a two-step localization method. In the first step, they proposed subarea fingerprinting to first localize a mobile device to a subarea. In each subarea, they created a subarea fingerprint and constructed fitting functions based on the fingerprints of only those RPs within the subarea. In the online positioning phase, suppose that the mobiles fingerprint was defined as EMBED Equation.DSMT4 . Comparing EMBED Equation.DSMT4 QUOTE with those subarea fingerprints EMBED Equation.DSMT4 QUOTE , the subarea with the minimum fingerprint difference would be selected. And then they searched a space point within the subarea as the mobile devices location. In the second step, they defined an objective function as the sum of distance estimation errors from all available APs for each subarea. Suppose that the kth subarea was selected in the first step. In the second step, they searched a space point EMBED Equation.DSMT4 QUOTE within the selected subarea, such that the sum of distance estimation error for each AP could be minimized. That is EMBED Equation.DSMT4 (4) where EMBED Equation.DSMT4 QUOTE is the RSSdistance fitting function of the jth AP in the kth subarea, and EMBED Equation.DSMT4 QUOTE is the estimated distance between the mobile device and the jth AP. Afterward, they proposed two location search algorithms to find the mobile devices location after the subarea determination, namely exhaustive location search (ELS) and gradient-descent-based location search (GLS). The ELS algorithm is to divide the subarea into many grid points (more than the number of RPs within the subarea) and to search among them a grid point with the least objective value. The GLS algorithm is to iteratively search the global minimizer for the objective function, which utilizes the slope characteristics of the objective function and applies an adjustable step size in the iterative search process. However, ELS has a high computation complexity and GLS has a fast convergence rate. It is not a perfect choice to use them respectively. Moreover, Bang method employed the Nearest Neighbor (NN) as the initial point on which the GLS has a great dependence. For the reasons above, we propose to apply selected weighed KNN as well as combined GLS and ELS to obtain better accuracy. 2.4. Our Improvement Since the GLS method can barely jump out of local minima to reach the global minimum, selection of the initial point has a great influence on the search results, or even directly determines the accuracy of search results. As a result, we use K nearest neighbor algorithm (KNN) rather than nearest neighbor algorithm (NN) in the selection of the initial point to avoid large errors. Furthermore, when KNN is employed, ideally, the K data points should gather in one physical space. But in practice, due to a variety of factors in the real environment, some outliers may be selected. Therefore, we need to filter out the outliers in order to achieve better accuracy. In addition, as the gradient descent method convergence too fast, the o p t i m u m v a l u e m a y b e m i s s e d i n t h e s e a r c h p r o c e s s . C o n s e q u e n t l y , w e c o m b i n e t h e a d v a n t a g e s o f G L S a n d E L S s o t h a t t h e i m p r o v e d a l g o r i t h m c a n a c h i e v e h i g h e r a c c u r a c y . G r a d i e n t D e s c e n t S e a r c h i s t o i t e r a t i v e l y s e a r c h a l o c a t i o n l a" ( x , y ) t o r e d u c e E M B E D E quation.DSMT4 QUOTE in each iteration. Let EMBED Equation.DSMT4 QUOTE denote the location in the tth iteration. The search iteration is defined by EMBED Equation.DSMT4 (5) where EMBED Equation.DSMT4 QUOTE is the search step size and EMBED Equation.DSMT4 QUOTE is the search direction, respectively. In this paper, we allow an adjustable search step size. First, we should determine EMBED Equation.DSMT4 QUOTE . EMBED Equation.DSMT4 QUOTE is the initial location of the iterative search process. Generally, it can be randomly selected. However, according to the experimental result, it is extremely easy for GLS to fall into local minima, thus selecting the initial point has a great influence on positioning accuracy. More seriously, if the initial point selected incorrectly, it may cause significant errors. As a consequence, we deploy selected weighed KNN to obtain an optimal result. First we select QUOTE k points with minimum difference of RSS vector received by the mobile device from the offline database. Assume that the coordinates of the k points are denoted as EMBED Equation.DSMT4 , EMBED Equation.DSMT4 QUOTE . If the RSS vector difference between the k points and the mobile device are EMBED Equation.DSMT4 , respectively, take their weigh EMBED Equation.DSMT4 QUOTE . Thus the rough result can be calculated by a weighted KNN algorithm as follows: EMBED Equation.DSMT4 (6) Then, we take this point as the center for that k-nearest neighbor filter. First, we take an appropriate length value m. Next, we take the point EMBED Equation.DSMT4 QUOTE as the center, and m as the length of side, forming a cube. If the k points meet the following criteria, we would keep them, otherwise we would discard them. And the criteria can be defined as EMBED Equation.DSMT4 QUOTE QUOTE (7) Suppose that there are h points qualifying, the initial point is computed by: EMBED Equation.DSMT4 (8) That is, EMBED Equation.DSMT4 QUOTE is taken as EMBED Equation.DSMT4 QUOTE . Next, we should determine EMBED Equation.DSMT4 QUOTE and EMBED Equation.DSMT4 QUOTE . For this part, we apply the gradient descent search and the Golden Section method to obtain the value of EMBED Equation.DSMT4 QUOTE and EMBED Equation.DSMT4 QUOTE as described in Bang method [4]. After that, we can get a course location point of EMBED Equation.DSMT4 . For the reason that the gradient descent search has a rapid convergence speed as well as some points may be outside the fitting curve, we may miss the optimal point. As a consequence, we apply ELS here to obtain a better result. We search the points around EMBED Equation.DSMT4 QUOTE by a small step size of 0.1m so that J achieves the minimum value. Suppose that the point around EMBED Equation.DSMT4 QUOTE is EMBED Equation.DSMT4 QUOTE , we compare the value EMBED Equation.DSMT4 QUOTE and EMBED Equation.DSMT4 QUOTE . If EMBED Equation.DSMT4 QUOTE , we take EMBED Equation.DSMT4 QUOTE as the start of next point. Else, EMBED Equation.DSMT4 QUOTE would be taken.Eventually, we take the result of ELS as the estimated position. Test bed and measurements The experimental test bed was located on the fifth floor of New Scientific Research Building at Beijing University of Posts and Telecommunications, Beijing, China. The layout of the test bed is indicated in Fig. 2 and there are five access points (APs) available at this location as shown in the figure. EMBED Visio.Drawing.11 Figure 2. Layout of the test bed. We used an Asustek laptop that is equipped with Intel Core i5-3210M CPU 2.5GHz and 4-GB memory as the server while a smart phone of Samsung SM_G3568V with Android 4.4.2 as the mobile node, collecting RSS. The general information of the equipment is shown in table 1. The mobile node was able to report the MAC addresses and the received power in dBm from sensed APs. In this test field, we collected 100 RSS measurements for each AP at every location. There are 312 locations separated by 0.6 m for building the radio map. Then, we collected 60 testing RSS measurements from distinct locations to evaluate the positioning performance. We evaluated the proposed algorithms through comparison with 2 positioning methods of KNN and CF. Table 1. The Informartion Of Equipment. BrandTypeSystemServerAsustekK45vWindows 7ClientSamsungSM_G3568VAndroid 4.4.2 Before testing our system, we built a radio map. In order to build the radio map, we defined 312 points or cells with a spacing of 0.6 meter in the corridor. In each cell we took about 100 RSS samples from each access point. This leads to about 156000 measurements for the offline phase. For the environment, it is also possible that some access points may not be detected at some reference points because of the characteristics of signal propagation. As the proposed algorithms need a value for each access point, an RSS default value was assigned to every missing AP. For those cases, RSS value was set to -99 dBm in the environment. We take the results of three methods of KNN, GLS based on CF (GLS-CF) and WSKNN for comparison. Figure 3 shows the cumulative probability of positioning errors of the three methods. Figure 3. Experiment results. In Fig. 3, we can see WSKNN has a better accuracy than basic KNN and a higher stability than GLS-CF. When the error distance is less than 3.4m, WSKNN is no worse than GLS-CF. Yet, when the error distance is greater than 3.4m, WSKNN is improved significantly. Moreover, the maximum error distance of WSKNN is 7.4m, which obtains an increase of 16.67%, while that of GLS-CF is 8.88m. We can explain the experimental results as follows. When the signal characteristic of RSS vectors of offline database as well as that of mobile device has a significant feature, GLS-CF with the nearest neighbor can achieve higher accuracy in the case that the nearest point selected is exactly the nearest neighbor of the mobile device in the physical environment. However, due to various factors in the real environment, the nearest point selected is not necessarily the nearest neighbor of the mobile device on the physical distance, which may result in large errors in GLS-CF with the nearest neighbor. Therefore, WSKNN can achieve higher stability in practice. Furthermore, we take the mean error distance and standard deviation for comparison between WSKNN and GLS-CF. The result is displayed as follows in Table1. The table shows that the mean error distance reduces from 2.37m to 2.20m with a decline of 7.17% and the standard deviation decreases from 2.07m to 1.81m while applying WSKNN instead of GLS-CF. T h a t i s , u t i l i z i n g s e l e c t e d w e i g h t e d K N N c a n p o s s i b l y r e d u c e t h e m e a n e r r o r d i s t a n c e a n d t h e s t a n d a r d d e v i a t i o n , c o n s e q u e n t l y g e t t i n g a h i g h e r s t a b i l i t y . B y c o n t r a s t , t h e b a s i c K N N i s a l s o d i s p l a y e d i n T a b l e `!, i n w h i c h w e c a n s e e t h a t W S K N N i s a l s o h a s a better performance of KNN. Table 2. Performance Of Each Algorithm. KNN GLS-CFWSKNNMean Error Distance(m)2.842.372.20Standard Deviation (m)1.552.071.81 The given experiments conclude that the proposed WSKNN provides a robust improvement in positioning in the real environment. WSKNN can achieve a better accuracy as well as a higher stability than the traditional KNN and GLS-CF. Conclusions This paper proposed an improved indoor positioning algorithm based on selected weighed KNN and curve fitting. Compared with the conventional indoor fingerprint-based positioning algorithms, a better accuracy and a higher stability are achieved. By applying the selected weighed KNN method, a more accurate initial point is chosen to improve the accuracy. By combining the advantages of GLS and ELS, a more precise result is obtained. Field experiment results show that more than 7.17% and 22.54% improvement İĜ܇pY