# Pedestrian Motion Learning Based Indoor WLAN Localization via Spatial Clustering

Authors: Xiaolong Yang; Yanmeng Wang; Mu Zhou; Yiyao Liu
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Applications on Location Based Services (LBSs) have driven the increasing demand for indoor localization technology. The conventional location fingerprinting based localization involves heavy time and labor cost for database construction, while the well-known Simultaneous Localization and Mapping (SLAM) technique requires assistant motion sensors as well as complicated data fusion algorithms. To solve the above problems, a new pedestrian motion learning based indoor Wireless Local Area Network (WLAN) localization approach is proposed in this paper to achieve satisfactory LBS without the demand for location calibration or motion sensors. First of all, the concept of pedestrian motion learning is adopted to construct users’ motion paths in the target environment. Second, based on the timestamp relation of the collected Received Signal Strength (RSS) sequences, the RSS segments are constructed to obtain the signal clusters with the newly defined high-dimensional linear distance. Third, the PageRank algorithm is performed to establish the hotspot mapping relations between the physical and signal spaces which are then used to localize the target. Finally, the experimental results show that the proposed approach can effectively estimate the target’s locations and analyze users’ motion preference in indoor environment.


---

## Body

## 1. Introduction

For well over a decade, the rapid development of wireless communication technology has driven the increasing demand for the Location Based Services (LBSs) [1–3]. Because of the complicated indoor building structure and multipath effect, the performance of the outdoor positioning systems such as Global Positioning will dramatically deteriorate in indoor environment. Meanwhile, with the wide deployment of Wireless Local Area Network (WLAN) infrastructure, WLAN has become one of the priorities for indoor positioning [4].Due to the easily accessible WLAN Received Signal Strength (RSS), the location fingerprinting based WLAN indoor localization systems [5, 6] have been widely researched. These systems generally contain two phases, namely, offline and online phases. In offline phase, the RSS data from the hearable Access Points (APs) at each precalibrated Reference Point (RP) are collected to construct fingerprint database. Then, in online phase, the newly collected RSS data are matched against fingerprint database to obtain the target location estimate [7]. However, because of the heavy time and labor cost for fingerprint database construction, this technology cannot be widely spread especially in the large-scale environment.To mitigate the cost of fingerprint database construction, the calibration-free indoor localization approaches have been intensively studied. By integrating the RSS data with motion sensor information, the Simultaneous Localization and Mapping (SLAM) technique [8] is proposed to effectively reduce the overhead of fingerprints calibration. Based on the specially designed sniffers, the authors in [9] conduct the dynamic radio map of target indoor environment to perform localization. In [10], the RSS measurements are fused with the odometric data from the foot-mounted Inertial Measurements Units (IMU) to conduct pedestrian navigation, and the odometry based Bayesian inference theory used for localization is analyzed in [11]. In all, the SLAM based localization techniques need additional motion sensors [12], as well as the sophisticated algorithms for feature extraction and data fusion [13].Different from these approaches, a new pedestrian motion learning based indoor WLAN localization approach is proposed in this paper, which has no demands for fingerprints calibration or assistant motion sensors. In general, there are four contributions of this paper as follows.(1)
Indoor user’s behavior model construction by pedestrian motion learning: with the statistical observation of users’ motion patterns, a heuristic pedestrian motion learning approach is performed to construct users’ walking paths in indoor environment.(2)
RSS data collection without fingerprints calibration: different from the location fingerprinting or SLAM based approaches, the RSS data in our approach are collected based on the motion behavior model corresponding to the users’ daily routines in the target area.(3)
Signal clustering on RSS segments: based on the timestamp relations of the collected RSS sequences, the RSS segments which reflect users’ continuous movement are constructed to obtain the signal clusters with newly defined high-dimensional linear distance.(4)
Comprehensive motion behavior analysis: the activity frequency of each physical subarea and the related transfer frequency between different physical subareas exhibit the users’ movement preference in the target environment.The rest of this paper is organized as follows. Section2 describes the proposed approach in detail. Then, Section 3 illustrates the experimental results. Finally, Section 4 concludes the paper and gives some future directions.


## 2. System Description

The proposed approach contains two main modules, namely, the context-aware sensing module and the motion exploration module as shown in Figure1.Figure 1
Flowchart of the proposed approach.In the process of context-aware sensing, we first construct the floor map of target environment and then adopt the pedestrian motion learning to establish the users’ motion behavior model. After that, according to the transfer relations between different physical subareas which are associated with users’ motion paths, the physical logic graph is constructed. Meanwhile, the RSS segments are constructed by mapping the raw RSS data into two-dimensional plane, and the density based spatial clustering is adopted to merge the RSS segments with respect to the similar motion behavior together. Then, with the transfer relations between different signal clusters, the signal logic graph is constructed. After the construction of logic graphs, PageRank algorithm [15] is performed to establish hotspot mapping relations between the physical and signal spaces.Then, in the process of motion exploration, the new RSS data collected by users is compared with each signal cluster, and the physical subarea mapped to the most similar one is selected as the area that the user most likely belongs to. In addition, based on the area-level localization results, the users’ motion behavior in the target environment is analyzed.


### 2.1. Floor Map Construction

By considering the functional differentiation of different physical subareas in floor map, we divide the target environment intoNarea (= 10) physical subareas as shown in Figure 2. In this figure, subarea #1 is the doorway to the lifts and a staircase, subareas #2, #3, and #4 are the corridors to the office rooms, subarea #5 is the doorway to the washrooms and another staircase, and the other subareas are the office rooms.Figure 2
Division of target environment.The objects in target environment mainly involve the walls, doors, and furniture. Among them, the furniture is the most favored target at which the users much probably arrive. When the user arrives at a piece of furniture like the table, chair, bookcase, and drinking fountain, he/she will normally stay for a while. Thus, we define the physical area around each piece of furniture asInterested Area (IA), and meanwhile the users’ motion paths are much likely to be the paths between different IAs. For example, the path from a chair to a drinking fountain indicates that the user has planned to get some water during the work time.To simulate the users’ motion paths in target environment, we transform the floor map into an image with the pixel width equallingwp (= 0.3 m) in Figure 3, where the notation “[∙]” represents the integer operation. In this case, the motion paths simulation is equivalent to the determination of the pixels reflecting the users’ motion behavior in target environment.Figure 3
Transformed image of floor map.


### 2.2. Pedestrian Motion Learning

By using the pedestrian motion learning, we construct the motion paths in the transformed image of floor map. Then, according to the statistical observation, there are three typical types of users’ motion behavior as follows.(i)
The motion paths from the staircases and lifts to office rooms.(ii)
The motion paths between different IAs.(iii)
The motion paths from office rooms to staircase or staircases and lifts.Meanwhile, based on our previousA∗ algorithm based motion path simulation approach [16], we define the cost function with respect to the walking distance from start to end points as(1)Ft,i=Gt,i+Ht,i,where G(t,i) is the distance from the starting pixel to current one i at moment t, which is the distance estimation of the passed path. In this paper, the Euclidean distance is adopted to estimate this type of distance since it is in accordance with users’ habit of measuring the path he/she has passed. H(t,i) is the distance from the current to ending pixels, which is measured by Manhattan distance by considering that the ending pixel is non-line-of-sight (NLOS) to the user in most cases.At each moment, the defined walking distance cost of each motion path is iteratively updated. Specifically, on each motion path, when the current pixeli is obtained (in the first iteration, the current pixel is randomly selected from the starting IA which is determined by the related motion behavior), the walking distance cost with respect to the eight adjacent pixels of i, Pij, can be represented by(2)Ft,Pij=Gt,i+Di,Pij+Ht,Pij,where D(i,Pij) is the Euclidean distance between the current pixel i and its adjacent one. Then, the accessible adjacent pixel with the smallest walking distance cost is selected as the next pixel i′ (or the current pixel at the next moment t+1). We continue this process until the current pixel falls into the ending IA which is determined by the related motion behavior. Following this heuristic learning way, each motion path of pedestrians in target environment, which is constituted by a series of consecutive pixels, can be obtained. Figure 4 gives an example of walking distance cost updating in the process of one motion path construction.Figure 4
Walking distance cost updating.In addition, in order to incorporate the randomness property into motion paths construction, a small proportion of accessible pixels are randomly converted into inaccessible ones, which will block the users’ motion paths in target environment. The pseudocode of pedestrian motion learning is shown in Algorithm1.Algorithm 1:Pseudocode of pedestrian motion learning.
Input: Starting and ending pixels, A and B Output: Motion path from A to B (1) Set starting pixel as A=(xA,yA); // Starting pixel (2) Set ending pixel as B=(xB,yB); // Ending pixel (3) A certain proportion of accessible pixels are converted into inaccessible ones; (4) Add A into Possible Path Location (PPL) set; (5) Initialize Existing Path Location (EPL) as an empty set; (6)  i←A; // Current pixel (7) while  i is not equal to B  do (8) for (each adjacent pixel around i, Pij) // Pixel traversal (9) if  Pij is an inaccessible pixel then (10) Continue; (11) else ifPij belongs to EPL set then (12) Continue; (13) else ifPij is neither in EPL set nor in PPL set then (14) Add Pij into PPL set; (15) Set i as the father pixel of Pij; (16) Calculate the Euclidean distance from Pij to A, Gij; (17) Calculate the Manhattan distance from Pij to B, Hij; (18) Set Fij=Gij+Hij; (19) else ifPij belongs to PPL set then (20)Calculate the distance from i to Pij, Dij; (21) G′ij←Gi+Dij; (22)IfG′ij<Gij  then (23) Gij←G′ij; (24) Fij←G′ij+Hij; (25)Set i as the father pixel of Pij; (26)end if (27)end if (28)end for (29)Add i into EPL set; (30)Remove i from PPL set; (31)Update i with the pixel with the smallest value Fij in PPL set; (32)end while (33) Nt=B; // Initialize traversal pixel (34)Add B into set Trace as the 1st pixel; (35) k←2; (36)whileNt is not equal to A (37)Add the father pixel of Nt into Trace as k-th pixel; (38) k←k+1; (39) Nt ← Father pixel of Nt; (40)end while (41)Consecutively connect the pixels in Trace as the constructed motion path.Figure5 shows an example of two different generated motion paths starting from the same staircase to a table, from which we can find that the randomness property results in different constructed motion paths even if the starting and ending pixels are the same.Figure 5
Construction of two motion paths with the same starting and ending locations.
(a)
Motion path #1 (b)
Motion path #2Finally, according to the transfer relations of motion paths between different physical subareas, the physical logic graph can be constructed, where a transfer between any two adjacent physical subareas is counted only if there is a pair of consecutive pixels located into these two subareas, respectively.


### 2.3. RSS Segments Construction and Clustering

Based on the pedestrian motion learning, some specific pixels on each motion path are labeled with the consideration of the statistical result corresponding to pedestrians’ motion velocities [17]. At the same time, the RSS data at each labeled pixel is calculated from the COST231 model [18, 19] which has a good compromise among the computation complexity, system flexibility, and practicability. The set of RSS data at the labeled pixels on the ith motion path forms the RSS sequence collected on the ith motion path, RSSi={rssi1,…,rssimi}, where rssij(j=1,…,mi) is the RSS data at the jth labeled pixel on the ith motion path and mi is the number of labeled pixels on the ith motion path, and rssij is the RSS value from the lth (l=1,…,NAP) AP which is calculated by(3)rssijl=rss0-10βlog⁡dld0-n0-Pa,where NAP is the number of APs, dl is the Euclidean distance between the target and lth AP, d0 is the reference distance which is usually set as 1 m, rss0 is the RSS at reference location, β is attenuation exponent, n0 is Gaussian noise, and Pa=Pawall+Pabody is the attenuation caused by walls and pedestrian’s body between the target and lth AP, where Pawall and Pabody (= 9.32 dB) stand for the attenuation factors with respect to the walls and human body, respectively, which are obtained from [20].After the RSS sequences are generated, the RSS segments are constructed with the timestamp relations of RSS sequences. In concrete terms, the RSS segments are constructed assegijrss=[rssij,rssi(j+1)], in which each RSS data is viewed as a vertex and the connection between every two consecutive RSS data is viewed as an edge in the NAP-dimensional space. To measure the similarity between two RSS segments, segijrss=[rssij,rssi(j+1)] and segpqrss=[rsspq,rssp(q+1)], we define a new NAP-dimensional linear distance as(4)dsegij-pq=∑l1,l2∈1,…,NAP;l1≠l2d-⊥l1l2+d-∥l1l2+d-θl1l2,where d-⊥l1l2, d-∥l1l2, and d-θl1l2 are the normalized values of the vertical distance d⊥l1l2, parallel distance d∥l1l2, and angle distances dθl1l2 between segijl1l2=[(rssijl1,rssijl2),(rssi(j+1)l1,rssi(j+1)l2)] and segpql1l2=[(rsspql1,rsspql2),(rssp(q+1)l1,rssp(q+1)l2)], which are the mapping data of segijrss and segpqrss in the 2-dimensional space with respect to the l1-th and l2-th APs. To be clearer, the geometric definition of d⊥l1l2, d∥l1l2, and dθl1l2 is shown in Figure 6. As can be seen from this figure, the smaller NAP-dimensional distance reflects the higher similarity of the RSS segments.Figure 6
Definition of the vertical, parallel, and angular distances.Based on the definition ofNAP-dimensional linear distance, the density based spatial clustering is conducted to merge the RSS linear segments corresponding to the similar motion patterns together. The pseudocode of density based spatial clustering is shown in Algorithm 2.Algorithm 2:Pseudocode of spatial clustering.
Input: RSS segments Output: Signal clusters (1)  m=1; // Initialize the number of RSS clusters (2) for (each RSS segment segijrss) do // Data traversal (3) Calculate the NAP-dimensional linear distance between segijrss and each of the rest RSS segments; (4) Save the RSS segments with the NAP-dimensional linear distance smaller than a given threshold, e, into set Cij; (5) if (the number of elements in Cij is not smaller than a given threshold, Min) then (6) continue; (7) else (8) for (each RSS segment in Cij, segpqrss) do // Data traversal (9) if (the number of RSS segments in Cpq is not smaller than the thresholdMin) then (10) Merge Cpq into Cij; (11) else (12) continue; (13) end if (14) end for (15) Set Cij as the m-th signal cluster; (16)  m←m+1; (17)  end if (18)  end forFinally, similar to physical logic graph, the RSS logic graph is constructed by selecting the RSS clusters and the corresponding transfer relations between them as the vertices and edges, respectively, where a transfer between any two RSS clusters is counted if and only if there is a pair of consecutive RSS segments falling into these two RSS clusters, respectively.


### 2.4. Hotspot Mapping between Physical and Signal Spaces

With the PageRank algorithm [15], a PageRank (PR) value is distributed to each physical subarea and RSS cluster, and then the hotspot mapping is performed between the physical and signal spaces. To achieve this goal, we first count the transfer number between every two adjacent physical subareas, Aη and Al, as TηlA(η,l∈{1,…,Narea};η≠l), where Narea is the number of physical subareas, and calculate the transfer probability, Pη→lA, as(5)Pη→lA=TηlA∑k=1NareaTηkAWhen the appearance probability of the pedestrian inAη at the moment t is PtA(Aη), the appearance probability in Al at the moment t+1, Pt+1A(Al) can be estimated by(6)Pt+1AAl=∑η=1NareaPtAAηPη→lAAs a special case, when a user is located inAη at the moment t, he/she may enter an anonymous physical subarea at the next moment. In this case, we assume that the user is equally likely to appear in every physical subarea at the moment t+1, such that(7)Pt+1AAl=1NareaThen, considering the movement trend of pedestrians in the target environment, the transfer relations between different physical subareas are obtained as follows [21]:(8)Pt+1A=QAPtA,where(9)PtA=PtA1,…,PtANareaT,P0A=1Narea,…,1Narea︸Nareain totalT,QA=θPA+esTNarea+1-θeeTNarea,and θ∈[0,1] is the proportion of users satisfying the transfer relations in (6), e=[1,…,1︸Nareain total]T, PA is a Narea×Narea matrix, in which Pη→lA is the element on the ηth row and the lth column, and s=[s1,…,sNarea]T, in which the ηth element satisfies(10)sη=1,If∑l=1NareaTηlA=00,OtherwiseAfter that, the set of the PR values of physical subareas,PhotA, is obtained as(11)PhotA=limtz→∞⁡PtzA=PA1,…,PANareaTSimilarly, in RSS logic graph, based on the transfer relations between different RSS clusters, we calculate the transfer frequency from the RSS clustersCη to Cl as(12)Pη→lC=TηlC∑k=1NclusterTηkC,where TηlC is the transfer number from Cη to Cl and Ncluster is the number of RSS clusters. Then, the set of the PR values of RSS clusters is obtained as(13)PhotC=limtz→∞⁡PtzC=PC1,…,PCNclusterTFinally, we construct the sets of the ranked PR values of physical subareas and RSS clusters asPRankA and PRankC, respectively, in (13).(14)PRankA=PRankA1,…,PRankANareaTPRankC=PRankC1,…,PRankCNclusterT,where PRankA1≥⋯≥PRankA(Narea) and PRankC1≥⋯≥PRankC(Ncluster). Then, the RSS clusters are mapped into the physical subareas with same order of PR values. By considering that Ncluster is generally larger than Narea, the RSS clusters having no physical subarea to be mapped into are discarded in the process of hotspot mapping.


### 2.5. Localization and Behavior Analysis

In online phase, for each RSS datarssjnew=[rssj1new,…,rssjNAPnew] in the newly collected RSS sequence, we calculate its confidence probability to each RSS cluster as(15)pjη=∏l=1NAPpljη,where pljη(η=1,…,Ncluster) is the confidence probability of the ηth RSS cluster with respect to rssjnew from the lth AP. Then, based on the established hotspot mapping relations between physical and signal spaces, the physical subarea corresponding to the RSS cluster with the highest confidence probability is chosen as the area where rssjnew is most probably to be collected.After that, according to the area-level localization results, we can analyze users’ motion behavior in the target environment by calculating the activity frequency in each physical subarea,FηA, and the transfer probability between adjacent physical subareas, Mη→lA, as follows:(16)FηA=Nηloc⁡∑k=1NareaNkloc⁡,where Nηloc⁡ is the number of the RSS data which are localized in the physical subarea Ak in the newly collected RSS sequence.(17)Mη→lA=TηlA∑k=1NareaTηkA,where TηlA is the number of the pairs of consecutive RSS data which are localized in the physical subareas Aη and Al, respectively, in the newly collected RSS sequence.


## 2.1. Floor Map Construction

By considering the functional differentiation of different physical subareas in floor map, we divide the target environment intoNarea (= 10) physical subareas as shown in Figure 2. In this figure, subarea #1 is the doorway to the lifts and a staircase, subareas #2, #3, and #4 are the corridors to the office rooms, subarea #5 is the doorway to the washrooms and another staircase, and the other subareas are the office rooms.Figure 2
Division of target environment.The objects in target environment mainly involve the walls, doors, and furniture. Among them, the furniture is the most favored target at which the users much probably arrive. When the user arrives at a piece of furniture like the table, chair, bookcase, and drinking fountain, he/she will normally stay for a while. Thus, we define the physical area around each piece of furniture asInterested Area (IA), and meanwhile the users’ motion paths are much likely to be the paths between different IAs. For example, the path from a chair to a drinking fountain indicates that the user has planned to get some water during the work time.To simulate the users’ motion paths in target environment, we transform the floor map into an image with the pixel width equallingwp (= 0.3 m) in Figure 3, where the notation “[∙]” represents the integer operation. In this case, the motion paths simulation is equivalent to the determination of the pixels reflecting the users’ motion behavior in target environment.Figure 3
Transformed image of floor map.


## 2.2. Pedestrian Motion Learning

By using the pedestrian motion learning, we construct the motion paths in the transformed image of floor map. Then, according to the statistical observation, there are three typical types of users’ motion behavior as follows.(i)
The motion paths from the staircases and lifts to office rooms.(ii)
The motion paths between different IAs.(iii)
The motion paths from office rooms to staircase or staircases and lifts.Meanwhile, based on our previousA∗ algorithm based motion path simulation approach [16], we define the cost function with respect to the walking distance from start to end points as(1)Ft,i=Gt,i+Ht,i,where G(t,i) is the distance from the starting pixel to current one i at moment t, which is the distance estimation of the passed path. In this paper, the Euclidean distance is adopted to estimate this type of distance since it is in accordance with users’ habit of measuring the path he/she has passed. H(t,i) is the distance from the current to ending pixels, which is measured by Manhattan distance by considering that the ending pixel is non-line-of-sight (NLOS) to the user in most cases.At each moment, the defined walking distance cost of each motion path is iteratively updated. Specifically, on each motion path, when the current pixeli is obtained (in the first iteration, the current pixel is randomly selected from the starting IA which is determined by the related motion behavior), the walking distance cost with respect to the eight adjacent pixels of i, Pij, can be represented by(2)Ft,Pij=Gt,i+Di,Pij+Ht,Pij,where D(i,Pij) is the Euclidean distance between the current pixel i and its adjacent one. Then, the accessible adjacent pixel with the smallest walking distance cost is selected as the next pixel i′ (or the current pixel at the next moment t+1). We continue this process until the current pixel falls into the ending IA which is determined by the related motion behavior. Following this heuristic learning way, each motion path of pedestrians in target environment, which is constituted by a series of consecutive pixels, can be obtained. Figure 4 gives an example of walking distance cost updating in the process of one motion path construction.Figure 4
Walking distance cost updating.In addition, in order to incorporate the randomness property into motion paths construction, a small proportion of accessible pixels are randomly converted into inaccessible ones, which will block the users’ motion paths in target environment. The pseudocode of pedestrian motion learning is shown in Algorithm1.Algorithm 1:Pseudocode of pedestrian motion learning.
Input: Starting and ending pixels, A and B Output: Motion path from A to B (1) Set starting pixel as A=(xA,yA); // Starting pixel (2) Set ending pixel as B=(xB,yB); // Ending pixel (3) A certain proportion of accessible pixels are converted into inaccessible ones; (4) Add A into Possible Path Location (PPL) set; (5) Initialize Existing Path Location (EPL) as an empty set; (6)  i←A; // Current pixel (7) while  i is not equal to B  do (8) for (each adjacent pixel around i, Pij) // Pixel traversal (9) if  Pij is an inaccessible pixel then (10) Continue; (11) else ifPij belongs to EPL set then (12) Continue; (13) else ifPij is neither in EPL set nor in PPL set then (14) Add Pij into PPL set; (15) Set i as the father pixel of Pij; (16) Calculate the Euclidean distance from Pij to A, Gij; (17) Calculate the Manhattan distance from Pij to B, Hij; (18) Set Fij=Gij+Hij; (19) else ifPij belongs to PPL set then (20)Calculate the distance from i to Pij, Dij; (21) G′ij←Gi+Dij; (22)IfG′ij<Gij  then (23) Gij←G′ij; (24) Fij←G′ij+Hij; (25)Set i as the father pixel of Pij; (26)end if (27)end if (28)end for (29)Add i into EPL set; (30)Remove i from PPL set; (31)Update i with the pixel with the smallest value Fij in PPL set; (32)end while (33) Nt=B; // Initialize traversal pixel (34)Add B into set Trace as the 1st pixel; (35) k←2; (36)whileNt is not equal to A (37)Add the father pixel of Nt into Trace as k-th pixel; (38) k←k+1; (39) Nt ← Father pixel of Nt; (40)end while (41)Consecutively connect the pixels in Trace as the constructed motion path.Figure5 shows an example of two different generated motion paths starting from the same staircase to a table, from which we can find that the randomness property results in different constructed motion paths even if the starting and ending pixels are the same.Figure 5
Construction of two motion paths with the same starting and ending locations.
(a)
Motion path #1 (b)
Motion path #2Finally, according to the transfer relations of motion paths between different physical subareas, the physical logic graph can be constructed, where a transfer between any two adjacent physical subareas is counted only if there is a pair of consecutive pixels located into these two subareas, respectively.


## 2.3. RSS Segments Construction and Clustering

Based on the pedestrian motion learning, some specific pixels on each motion path are labeled with the consideration of the statistical result corresponding to pedestrians’ motion velocities [17]. At the same time, the RSS data at each labeled pixel is calculated from the COST231 model [18, 19] which has a good compromise among the computation complexity, system flexibility, and practicability. The set of RSS data at the labeled pixels on the ith motion path forms the RSS sequence collected on the ith motion path, RSSi={rssi1,…,rssimi}, where rssij(j=1,…,mi) is the RSS data at the jth labeled pixel on the ith motion path and mi is the number of labeled pixels on the ith motion path, and rssij is the RSS value from the lth (l=1,…,NAP) AP which is calculated by(3)rssijl=rss0-10βlog⁡dld0-n0-Pa,where NAP is the number of APs, dl is the Euclidean distance between the target and lth AP, d0 is the reference distance which is usually set as 1 m, rss0 is the RSS at reference location, β is attenuation exponent, n0 is Gaussian noise, and Pa=Pawall+Pabody is the attenuation caused by walls and pedestrian’s body between the target and lth AP, where Pawall and Pabody (= 9.32 dB) stand for the attenuation factors with respect to the walls and human body, respectively, which are obtained from [20].After the RSS sequences are generated, the RSS segments are constructed with the timestamp relations of RSS sequences. In concrete terms, the RSS segments are constructed assegijrss=[rssij,rssi(j+1)], in which each RSS data is viewed as a vertex and the connection between every two consecutive RSS data is viewed as an edge in the NAP-dimensional space. To measure the similarity between two RSS segments, segijrss=[rssij,rssi(j+1)] and segpqrss=[rsspq,rssp(q+1)], we define a new NAP-dimensional linear distance as(4)dsegij-pq=∑l1,l2∈1,…,NAP;l1≠l2d-⊥l1l2+d-∥l1l2+d-θl1l2,where d-⊥l1l2, d-∥l1l2, and d-θl1l2 are the normalized values of the vertical distance d⊥l1l2, parallel distance d∥l1l2, and angle distances dθl1l2 between segijl1l2=[(rssijl1,rssijl2),(rssi(j+1)l1,rssi(j+1)l2)] and segpql1l2=[(rsspql1,rsspql2),(rssp(q+1)l1,rssp(q+1)l2)], which are the mapping data of segijrss and segpqrss in the 2-dimensional space with respect to the l1-th and l2-th APs. To be clearer, the geometric definition of d⊥l1l2, d∥l1l2, and dθl1l2 is shown in Figure 6. As can be seen from this figure, the smaller NAP-dimensional distance reflects the higher similarity of the RSS segments.Figure 6
Definition of the vertical, parallel, and angular distances.Based on the definition ofNAP-dimensional linear distance, the density based spatial clustering is conducted to merge the RSS linear segments corresponding to the similar motion patterns together. The pseudocode of density based spatial clustering is shown in Algorithm 2.Algorithm 2:Pseudocode of spatial clustering.
Input: RSS segments Output: Signal clusters (1)  m=1; // Initialize the number of RSS clusters (2) for (each RSS segment segijrss) do // Data traversal (3) Calculate the NAP-dimensional linear distance between segijrss and each of the rest RSS segments; (4) Save the RSS segments with the NAP-dimensional linear distance smaller than a given threshold, e, into set Cij; (5) if (the number of elements in Cij is not smaller than a given threshold, Min) then (6) continue; (7) else (8) for (each RSS segment in Cij, segpqrss) do // Data traversal (9) if (the number of RSS segments in Cpq is not smaller than the thresholdMin) then (10) Merge Cpq into Cij; (11) else (12) continue; (13) end if (14) end for (15) Set Cij as the m-th signal cluster; (16)  m←m+1; (17)  end if (18)  end forFinally, similar to physical logic graph, the RSS logic graph is constructed by selecting the RSS clusters and the corresponding transfer relations between them as the vertices and edges, respectively, where a transfer between any two RSS clusters is counted if and only if there is a pair of consecutive RSS segments falling into these two RSS clusters, respectively.


## 2.4. Hotspot Mapping between Physical and Signal Spaces

With the PageRank algorithm [15], a PageRank (PR) value is distributed to each physical subarea and RSS cluster, and then the hotspot mapping is performed between the physical and signal spaces. To achieve this goal, we first count the transfer number between every two adjacent physical subareas, Aη and Al, as TηlA(η,l∈{1,…,Narea};η≠l), where Narea is the number of physical subareas, and calculate the transfer probability, Pη→lA, as(5)Pη→lA=TηlA∑k=1NareaTηkAWhen the appearance probability of the pedestrian inAη at the moment t is PtA(Aη), the appearance probability in Al at the moment t+1, Pt+1A(Al) can be estimated by(6)Pt+1AAl=∑η=1NareaPtAAηPη→lAAs a special case, when a user is located inAη at the moment t, he/she may enter an anonymous physical subarea at the next moment. In this case, we assume that the user is equally likely to appear in every physical subarea at the moment t+1, such that(7)Pt+1AAl=1NareaThen, considering the movement trend of pedestrians in the target environment, the transfer relations between different physical subareas are obtained as follows [21]:(8)Pt+1A=QAPtA,where(9)PtA=PtA1,…,PtANareaT,P0A=1Narea,…,1Narea︸Nareain totalT,QA=θPA+esTNarea+1-θeeTNarea,and θ∈[0,1] is the proportion of users satisfying the transfer relations in (6), e=[1,…,1︸Nareain total]T, PA is a Narea×Narea matrix, in which Pη→lA is the element on the ηth row and the lth column, and s=[s1,…,sNarea]T, in which the ηth element satisfies(10)sη=1,If∑l=1NareaTηlA=00,OtherwiseAfter that, the set of the PR values of physical subareas,PhotA, is obtained as(11)PhotA=limtz→∞⁡PtzA=PA1,…,PANareaTSimilarly, in RSS logic graph, based on the transfer relations between different RSS clusters, we calculate the transfer frequency from the RSS clustersCη to Cl as(12)Pη→lC=TηlC∑k=1NclusterTηkC,where TηlC is the transfer number from Cη to Cl and Ncluster is the number of RSS clusters. Then, the set of the PR values of RSS clusters is obtained as(13)PhotC=limtz→∞⁡PtzC=PC1,…,PCNclusterTFinally, we construct the sets of the ranked PR values of physical subareas and RSS clusters asPRankA and PRankC, respectively, in (13).(14)PRankA=PRankA1,…,PRankANareaTPRankC=PRankC1,…,PRankCNclusterT,where PRankA1≥⋯≥PRankA(Narea) and PRankC1≥⋯≥PRankC(Ncluster). Then, the RSS clusters are mapped into the physical subareas with same order of PR values. By considering that Ncluster is generally larger than Narea, the RSS clusters having no physical subarea to be mapped into are discarded in the process of hotspot mapping.


## 2.5. Localization and Behavior Analysis

In online phase, for each RSS datarssjnew=[rssj1new,…,rssjNAPnew] in the newly collected RSS sequence, we calculate its confidence probability to each RSS cluster as(15)pjη=∏l=1NAPpljη,where pljη(η=1,…,Ncluster) is the confidence probability of the ηth RSS cluster with respect to rssjnew from the lth AP. Then, based on the established hotspot mapping relations between physical and signal spaces, the physical subarea corresponding to the RSS cluster with the highest confidence probability is chosen as the area where rssjnew is most probably to be collected.After that, according to the area-level localization results, we can analyze users’ motion behavior in the target environment by calculating the activity frequency in each physical subarea,FηA, and the transfer probability between adjacent physical subareas, Mη→lA, as follows:(16)FηA=Nηloc⁡∑k=1NareaNkloc⁡,where Nηloc⁡ is the number of the RSS data which are localized in the physical subarea Ak in the newly collected RSS sequence.(17)Mη→lA=TηlA∑k=1NareaTηkA,where TηlA is the number of the pairs of consecutive RSS data which are localized in the physical subareas Aη and Al, respectively, in the newly collected RSS sequence.


## 3. Experimental Results

### 3.1. Result of Pedestrian Motion Learning

As shown in Figure2, the target environment is divided into 10 physical subareas, notated as #1,…, and #10. Then, based on the heuristic pedestrian motion learning approach, we define 20% pixels as the inaccessible ones and construct 300 motion paths in the transformed image of floor map. The result of simulated motion paths under different types of users’ motion behavior is shown in Figure 7, where the pixels in darker color indicate the corresponding locations with higher appearance probabilities. As can be seen from this figure, 300 motion paths are capable of effectively describing the pedestrians’ movement trend in the target environment. After that, according to the transfer relations of motion paths between different physical subareas in Figure 2, we construct the physical logic graph in Figure 8.Figure 7
Motion paths construction.
(a)
From staircase or lift to office rooms (b)
Between different IAs (c)
From office rooms to staircase or lift (d)
All dayFigure 8
Physical logic graph.


### 3.2. Result of Hotspot Mappings

According to the analysis of users’ motion velocities [17], some specific pixels are labeled on each motion to calculate the RSS data from the placed APs as shown in Figure 9. This figure gives the result of pixel sampling under different motion velocities on the two constructed motion paths which are with the same starting and ending pixels.Figure 9
Sampled pixels on two motion paths with different motion velocity.
(a)
Motion velocityv = 2.3446 m/s (b)
Motion velocityv = 0.8502 m/sThen, Figure10 compares the probability of mapping the RSS data into the physical subareas which they actually belong to, namely, probability of correct indoor mapping. Since the defined NAP-dimensional linear distance in formula (4) is sum of the normalized values of different distance measurements, the distance threshold e may be negative. As shown in Figure 10, the highest probability of correct indoor mapping is obtained when the thresholds e andMinare set as −4.7192 and 40, respectively.Figure 10
Probability of correct indoor mapping with different thresholds.After obtaining the optimal thresholds corresponding to the highest probability of correct indoor mapping, we construct the signal logic graph in Figure11. In our experiment, the proportion of the users satisfying the transfer relations in formula (6), θ, which is much larger than that of other users, is set as 90%. Based on this, the hotspot mapping between the physical and signal spaces is established in Figure 12.Figure 11
Signal logic graph.Figure 12
Hotspot mapping between physical and signal spaces.


### 3.3. Result of Localization and Behavior Analysis

To examine the localization performance of the proposed approach, we collect some calibrated RSS sequences in the consecutive one, two, and three physical subareas, respectively. Figure13 shows the probabilities of locating the new RSS data into its actually belonging subarea which is defined as correct localization, as well as probabilities into its adjacent subareas which is defined as adjacently correct localization. In addition, combining with Table 1, we can find that compared with [12–14], the proposed approach can generally achieve higher localization accuracy with lower time complexity and without the demand for fingerprints calibration.Table 1
Comparison between different approaches.
Approach Fingerprints calibration Time complexity [12] No demand O ( n ) [13] No demand O ( n × log ⁡ ( n ) ) [14] Low calibration cost O ( n 3 ) Proposed No demand O ( n × log ⁡ ( n ) )Figure 13
Localization result of different approaches.Based on the area-level localization result, the users’ motion behavior can be preliminarily analyzed by calculating the activity frequency in each subarea and the transfer probability between different physical subareas as shown in Figure14. In this figure, the activity frequency in physical subarea #4 is much higher than the one in other subareas, which can be interpreted by the reason that #4 is with much larger PR value as illustrated in Figure 11. As a special case, the physical activity frequency is very low. This result is due to the fact that the similar RSS distributions in the physical subareas #1 and #2 increase the probability of mapping the RSS data in #2 into its adjacent physical subarea #1 by mistake.Figure 14
Motion behavior of users in the target environment.At the same time, with the transfer probability between different physical subareas, we can further explore some users’ motion preference in the target environment. As an example, when a user is located in the physical subarea #4, we can predict that he/she is most likely to move to subarea #3 with the confidence probability equalling 0.54. In addition, the nonzero transfer probability between the nonadjacent physical subareas (labeled with red dotted arrows) (i.e., #3 → #9 and #3 → #1 with the confidence probability 0.44 and 0.03, respectively) indicates that these nonadjacent physical subareas are with the similar RSS distributions.


## 3.1. Result of Pedestrian Motion Learning

As shown in Figure2, the target environment is divided into 10 physical subareas, notated as #1,…, and #10. Then, based on the heuristic pedestrian motion learning approach, we define 20% pixels as the inaccessible ones and construct 300 motion paths in the transformed image of floor map. The result of simulated motion paths under different types of users’ motion behavior is shown in Figure 7, where the pixels in darker color indicate the corresponding locations with higher appearance probabilities. As can be seen from this figure, 300 motion paths are capable of effectively describing the pedestrians’ movement trend in the target environment. After that, according to the transfer relations of motion paths between different physical subareas in Figure 2, we construct the physical logic graph in Figure 8.Figure 7
Motion paths construction.
(a)
From staircase or lift to office rooms (b)
Between different IAs (c)
From office rooms to staircase or lift (d)
All dayFigure 8
Physical logic graph.


## 3.2. Result of Hotspot Mappings

According to the analysis of users’ motion velocities [17], some specific pixels are labeled on each motion to calculate the RSS data from the placed APs as shown in Figure 9. This figure gives the result of pixel sampling under different motion velocities on the two constructed motion paths which are with the same starting and ending pixels.Figure 9
Sampled pixels on two motion paths with different motion velocity.
(a)
Motion velocityv = 2.3446 m/s (b)
Motion velocityv = 0.8502 m/sThen, Figure10 compares the probability of mapping the RSS data into the physical subareas which they actually belong to, namely, probability of correct indoor mapping. Since the defined NAP-dimensional linear distance in formula (4) is sum of the normalized values of different distance measurements, the distance threshold e may be negative. As shown in Figure 10, the highest probability of correct indoor mapping is obtained when the thresholds e andMinare set as −4.7192 and 40, respectively.Figure 10
Probability of correct indoor mapping with different thresholds.After obtaining the optimal thresholds corresponding to the highest probability of correct indoor mapping, we construct the signal logic graph in Figure11. In our experiment, the proportion of the users satisfying the transfer relations in formula (6), θ, which is much larger than that of other users, is set as 90%. Based on this, the hotspot mapping between the physical and signal spaces is established in Figure 12.Figure 11
Signal logic graph.Figure 12
Hotspot mapping between physical and signal spaces.


## 3.3. Result of Localization and Behavior Analysis

To examine the localization performance of the proposed approach, we collect some calibrated RSS sequences in the consecutive one, two, and three physical subareas, respectively. Figure13 shows the probabilities of locating the new RSS data into its actually belonging subarea which is defined as correct localization, as well as probabilities into its adjacent subareas which is defined as adjacently correct localization. In addition, combining with Table 1, we can find that compared with [12–14], the proposed approach can generally achieve higher localization accuracy with lower time complexity and without the demand for fingerprints calibration.Table 1
Comparison between different approaches.
Approach Fingerprints calibration Time complexity [12] No demand O ( n ) [13] No demand O ( n × log ⁡ ( n ) ) [14] Low calibration cost O ( n 3 ) Proposed No demand O ( n × log ⁡ ( n ) )Figure 13
Localization result of different approaches.Based on the area-level localization result, the users’ motion behavior can be preliminarily analyzed by calculating the activity frequency in each subarea and the transfer probability between different physical subareas as shown in Figure14. In this figure, the activity frequency in physical subarea #4 is much higher than the one in other subareas, which can be interpreted by the reason that #4 is with much larger PR value as illustrated in Figure 11. As a special case, the physical activity frequency is very low. This result is due to the fact that the similar RSS distributions in the physical subareas #1 and #2 increase the probability of mapping the RSS data in #2 into its adjacent physical subarea #1 by mistake.Figure 14
Motion behavior of users in the target environment.At the same time, with the transfer probability between different physical subareas, we can further explore some users’ motion preference in the target environment. As an example, when a user is located in the physical subarea #4, we can predict that he/she is most likely to move to subarea #3 with the confidence probability equalling 0.54. In addition, the nonzero transfer probability between the nonadjacent physical subareas (labeled with red dotted arrows) (i.e., #3 → #9 and #3 → #1 with the confidence probability 0.44 and 0.03, respectively) indicates that these nonadjacent physical subareas are with the similar RSS distributions.


## 4. Conclusion

In this paper, we propose a new pedestrian motion learning based indoor WLAN localization approach without the assistance of location fingerprinting or motion sensor. Combined with the pedestrian motion learning, density based spatial clustering on RSS segments, and hotspot mapping strategy, we construct the hotspot mapping between the physical and signal spaces to estimate the target’s location. In addition, the area-level localization result is utilized to explore the motion preference of pedestrians in indoor environment. In the future, we will pay more attention to the effective way of subareas division to enhance the hotspot mapping performance as well as reduce the wrong transfer probability between the nonadjacent physical subareas.



---

*Source: 2571671-2018-05-15.xml*