WO2020091590A1

WO2020091590A1 - A system and method for locating a device in an indoor environment

Info

Publication number: WO2020091590A1
Application number: PCT/MY2019/050077
Authority: WO
Inventors: Dr. Kee Ngoh TING; Dr. Heng Tze CHIENG
Original assignee: Mimos Bhd
Current assignee: Mimos Bhd
Priority date: 2018-10-30
Filing date: 2019-10-16
Publication date: 2020-05-07
Anticipated expiration: 2021-04-30

Abstract

The present invention relates to a system (100) and method for locating a device in an indoor environment. The system (100) comprising a plurality of transmitters (10), a processing module (30) configured for processing received strength signal indicator, RSSI of the wireless signal, a distance constraint estimation module (50) configured for estimating all possible areas reachable by a user within a period of time, a path estimation module (60) configured for estimating possible path taken by the user within a period of time based on the estimated possible areas reachable by the user; and a location prediction module (70) configured for predicting location of the user based on the estimated path. The system (100) further comprising a movement detection module (40) configured for detecting user movement by using all statistical information of the RSSI and detecting rotation of the user based on interference of body of the user on the RSSI.

Description

A SYSTEM AND METHOD FOR LOCATING A DEVICE IN AN INDOOR

ENVIRONMENT

FIELD OF INVENTION

The present invention relates to a system and method for locating a device in an indoor environment. More particularly, the present invention relates to a system and method for locating a device in an indoor environment using received signal strength indicator of wireless signal.

BACKGROUND OF THE INVENTION

Most of portable devices such as smartphones, tablets, smartwatches and fitness monitor which are carried around are equipped with a positioning system. The positioning system uses a global positioning system or a satellite-based tracking service to locate the portable devices. However, such positioning system usually cannot be used effectively in an indoor environment. Therefore, systems and method have been developed to locate the portable devices in the indoor environment by utilising wireless short-range networks such as Wi-Fi and Bluetooth.

An example of a system and method for locating a device in an indoor environment is disclosed in a United States Patent Publication No. 2018/0070212 A1 which relates to systems and methods to track a device in an indoor environment having polygonal obstruction. The system localises the device by receiving a signal strength profile from the device at a server. The system then determines a raw estimated location in a coordinate plane representing the indoor environment by using a K-nearest neighbour algorithm. Thereon, the system calculates a straight-line path in the coordinate plane from an immediately preceding location to the raw estimate location and selects the raw estimated location as a candidate location when the straight-line path connects the two location without intersecting any of the polygonal obstruction. Finally, the system calculates a weighted-average location using the immediately preceding location and the candidate location and stores the weighted average location as a new location when a hypothetical velocity is less than or equal to a saturation velocity. Another example of the system and method for locating a device in an indoor environment is disclosed in a Korean Patent Publication No. 2017009181 1 . The system uses a triangulation method and a plurality of received signal strength indicators, RSSI received through an application installed in a receiving terminal of a pedestrian. The system gives a weight to each indoor region through the analysis of the pattern of the movement of the pedestrian in real time to compensate the reliability of the system. The system designates unique number by dividing each region into cells by converting indoor information from the receiving terminal into a map. Finally, the system estimates an indoor position coordinate giving the probability of each region by analysing the pattern of the pedestrian using each application.

Although there are many systems and methods for locating a device in an indoor environment, most of the systems and methods face jumpiness problem. The jumpiness problem occurs due to fluctuation of wireless signal which is caused by shadowing or blockage of signal by objects or multipath fading reflection from the object. Additionally, most of the systems and methods do not consider the rotation of the user when predicting the movement of the user. Thus, causing in inaccuracy while predicting the location of the user. Hence, there is a need for a system and method which address the above-mentioned problems.

SUMMARY OF INVENTION

The present invention relates to a system (100) and method for locating a device in an indoor environment. The system (100) comprising, a plurality of transmitters (10), a processing module (30) a distance constraint estimation module (50), a path estimation module (60), and a location prediction module. The plurality of transmitters (10) are configured for transmitting wireless signal to a terminal or a user device, wherein the plurality of transmitters (10) are installed throughout an indoor environment to surround the terminal or user device. The processing module (30) is configured for processing received strength signal indicator, RSSI of the wireless signal. The distance constraint estimation module (50) is configured for estimating all possible areas reachable by a user within a period of time. The path estimation module (60) is configured for estimating possible path taken by the user within a period of time based on the estimated possible areas reachable by the user. The location prediction module (70) is configured for predicting location of the user based on the estimated path. The system (100) further comprising a movement detection module (40) configured for detecting user movement by using all statistical information of the RSSI and detecting rotation of the user based on attenuation effect on received RSSI due to blockage of a body of the user.

The method for locating a device in an indoor environment includes the steps of scanning surrounding wireless signal transmitted by a plurality of transmitters (10) by a scanning module (20), processing the wireless signal to compute an average and statistical information of received signal strength indicator, RSSI by a processing module (30), estimating all possible user movement based on the average and statistical information of the RSSI by a movement detection module (40), and computing all possible areas a user can travel from a previous location based on speed of user movement by a distance constraint estimation module (50). The method for locating a device in an indoor environment further includes the steps of estimating all possible paths taken by the user based on the possible areas the user can travel by a path estimation module (60) and predicting current location of the user by a location prediction module (70).

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate embodiments of the invention and, together with the description, serve to explain the principles of the invention.

FIG. 1 illustrates a block diagram of a system (100) for locating a device in an indoor environment according to an embodiment of the present invention.

FIG. 2 illustrates a flowchart of a method for locating a device in an indoor environment according to an embodiment of the present invention.

FIG. 3 illustrates an example of all possible areas a user can travel from previous location.

FIG. 4 illustrates an example of a floor plan of an indoor environment. FIG. 5 illustrates a flowchart of the sub-steps for estimating a user movement by a movement detection module (40) of the method of FIG. 2.

FIG. 6 illustrates a set of samples of received signal strength indicator, RSSI collected when the user is static.

FIG. 7 (a) illustrates an example of placement of a plurality of transmitters (10) and the user moving away from the previous location.

FIG. 7 (b) illustrates an example of placement of the transmitters (10) and the user rotating.

FIG. 8 illustrates changes of reference received signal strength indicator, RSSI value when the user is moving and rotating.

DESCRIPTION OF THE PREFERRED EMBODIMENT

A preferred embodiment of the present invention will be described herein below with reference to the accompanying drawings. In the following description, well known functions or constructions are not described in detail since they would obscure the description with unnecessary detail.

Initial reference is made to FIG. 1 which illustrates a block diagram of a system (100) for locating a device in an indoor environment according to an embodiment of the present invention. The system (100) may either be implemented on a user device or in a server. The system (100) comprises a plurality of transmitters (10), a scanning module (20), a processing module (30), a movement detection module (40), a distance constraint estimation, DCE module (50), a path estimation module (60), a location prediction module (70), and a repository (80).

The system (100) locates the position of the device which is held by or attached to a user inside an indoor environment such as an office, a shopping mall, an airport or other public or private building. The device may be any device that is capable of receiving a wireless signal. Examples of the terminal or user device include but not limited to a smartphone and a wearable wireless tag. Preferably, the wireless signal is a radio frequency transmitted in a form of a beacon or normal transmitter packets that carry communication data.

The transmitters (10) which are configured to transmit wireless signal are installed throughout the indoor environment to surround the device. The scanning module (20) is configured to periodically scan the indoor environment to detect the wireless signal transmitted by the transmitters (10). The scanning module (20) also detects received signal strength indicator, RSSI of the wireless signal. The scanning module (20) is further connected to the processing module (30) to send the RSSI to the processing module (30) to be processed.

The processing module (30) is configured to process the RSSI detected by the scanning module (20). The processing module (30) collects a number of samples RSSI and averages the sample of RSSI. Additionally, the processing module (30) computes statistical information such as standard deviation using the sample RSSIs.

The movement detection module (40) is connected to the processing module (30) and the DCE module (50). The movement detection module (40) is configured to detect the user movement by using all statistical information of the RSSI received from the processing module (30). Additionally, the movement detection module (40) is configured to detect the rotation of the user based on the attenuation effect on received RSSI due to the blockage of the user body. The movement detection module (40) sends all the possible user movement to the DCE module (50) for further processing.

The DCE Module (50) is configured to estimate all possible areas reachable by the user within a period of time. The DCE module (50) estimates how fast the user is moving by analysing the rate of changes of the signals strength. The user speed information is then used by the DCE module (50) to estimate all possible areas that the user can travel from previous location and constraint the search by location algorithm. The DCE module (50) is connected to the path estimation module (60) to send the estimated possible areas for path estimation.

The path estimation module (60) is further connected to the repository (80) which stores a map and a path of the indoor environment. The path estimation module (60) is configured to estimate possible path taken by the user within a period of time based on the estimated possible areas obtained from the DCE module (50), map and path of the indoor environment obtained from the repository (80). The path estimation module (60) is also connected to the location prediction module (70) to send the estimated path to the location prediction module (70) for location prediction.

The location prediction module (70) is configured to obtain the estimated path from the path estimation module (60) and predict the location of the user. The location prediction module (70) uses a prediction algorithm that relies on wireless fingerprints such as a Bayesian algorithm, K-nearest neighbour algorithm, and neural algorithm. Preferably, the location of the user is in the form of latitude and longitude.

Reference is now made to FIG. 2 which illustrates a flowchart of a method for locating a device in an indoor environment according to an embodiment of the present invention. Initially, the scanning module (20) scans surrounding wireless signal transmitted by the transmitters (10) as in step 1100. The scanning module (20) also detects the RSSI of the wireless signal transmitted by each transmitter (10).

The scanning module (20) then sends the detected RSSI to the processing module (30) for the processing module (30) to determine user location as in step 1200. The processing module (30) collects a number of samples of the RSSI and averages the samples of the RSSI. The processing module (30) also computes statistical information such as a standard deviation and co-relation matrix of the wireless signal.

The movement detection module (40) receives the average and statistical information of the RSSI and estimates all possible user movement as in step 1300. There are several types of movement, wherein the types of movement include but not limited to static or no movement, moving away from the original position and rotating. When the user is static, the user is said to remain as same posture, move from standing to sitting or move from sitting to standing. When the user is moving away from the original position, the user may either be walking or running. Additionally, when the user is rotating, the user is said to remain at the original position but has changed the direction in which the user is heading. The sub-steps for estimating the user movement by the movement detection module (40) are further explained in relation to FIG. 5.

Thereon, the DCE module (50) computes all possible areas the user can travel from the previous location based on the speed of user movement as in step 1400. Distance, d as shown in the FIG. 3 is a vector distance the user can possibly travel depending on the mode of movements such as walking, jogging or fast running. In order to compute the distance, d which is a variable that is based on the determined mode of movement. The mode of movement may be determined by using a sensor accelerator, gyroscope or step sensor. However, if there is no sensor to determine the mode of movement, the DCE module (50) fixes the mode of movement to the fastest type of movement. Once the mode of movement is determined, the speed of user movement can be estimated based on the typical speed of each type of movement.

The distance, of is then estimated by multiplying the speed of user movement and time. If the mode of movement cannot be determined, the distance, d can be estimated by assuming the fastest movement mode. Once a circular area with a radius similar to the distance, d is identified as shown in FIG. 3, the circular area which represents all possible areas the user can travel from the previous location is passed to the path estimation module (60).

Once the path estimation module (60) receives the circular areas from the DCE module (50), the path estimation module (50) retrieves a floor plan of a specific area of the indoor environment from the repository (80). The floor plan is then fed to the location algorithm to estimate all possible paths taken by the user as in step

1500.

FIG. 4 illustrates an example of the floor plan of the indoor environment within the circular area. The floor plan confines the movement of the user inside the indoor environment. The path estimation module (60) estimates the path of the user as the dotted lines which is within the distance, d meters from the previous location. By estimating the path of the user within the circular area, the system (100) reduces the search area and increases the search speed. The accuracy of the path estimation also increases as it reduces the user possible position. Referring back to FIG. 2, after all possible paths taken by the user are estimated, the location prediction module (70) obtains the RSSI information. Thereon, the location prediction module (70) predicts the current location of the user based on the estimated possible path taken by the user and the RSSI information as in step 1600. Preferably, the location prediction module (70) uses a prediction algorithm that relies on wireless fingerprints such as the Bayesian algorithm, K nearest neighbour algorithm, and neural algorithm.

Finally, the location prediction module (70) outputs the current location of the user as in step 1700. Preferably, the location of the user is in the form of longitude and latitude.

FIG. 5 illustrates a flowchart of the sub-steps for estimating the user movement by the movement detection module (40) of the step 1300 of the method of FIG. 2. Initially, when the movement detection module (40) receives average and statistical information from the processing module (30), the movement detection module (40) scans through the RSSI signals to detect a number of healthy transmitters (10) to be used as reference transmitters (10) as in step 1310. The healthy transmitter (10) is a transmitter (10) that has low signal fluctuation, strong signal strength and is highly detectable. The healthy transmitter (10) is required in order to have a stable and reliable system (100). A set of healthy transmitters (10) is monitored and updated periodically when the user moves to a different location.

When the set of healthy transmitters (10) is identified, the movement detection module (40) records the latest average RSSI value as a current average RSSI value which is also known as a current reference RSSI value as in step 1320. After a reference time has lapsed, the current reference RSSI value is recorded as a previous reference RSSI value as in step 1330. The reference time refers to the time interval between two movement detections processes.

Simultaneously, after the set of healthy transmitters (10) is identified, the movement detection module (40) compares the previous reference RSSI value and the current reference RSSI value as in step 1340. Thereon, the movement detection module (40) determines whether there is any difference between the current reference RSSI value with the previous reference RSSI value as in decision 1345. If there is no difference between the current reference RSSI value with the previous reference RSSI value, the movement detection module (40) classifies the type of movement of the user as idle as in step 1350. Thereon, the type of movement of the user is sent to the DCE module (50) as in step 1360. For example, FIG. 6 illustrates a set of samples of RSSI collected from the transmitters (10) Tx1 , Tx2, Tx3, Tx4, Tx5, and Tx6. The x-axis represents the transmitters (10), while the y-axis represents the RSSI in decibel relative to one milliwatt, dBm. The sample of the RSSI signal for each transmitter (10) is represented as dot, while the average RSSI value for each transmitter (10) is represented as triangle.

Typically the processing module (30) collects a number of samples of the RSSI signals for each transmitter (10) as seen in FIG. 6. For example, the RSSI signals fluctuate around 10dB, over the period of 10 samples in FIG. 6. The processing module (30) computes the average RSSI value for each transmitter (10) and the movement detection module (40) records the average RSSI value for each transmitter (10) as the current reference RSSI value. Since the user is static, the average RSSI value for each transmitter (10) remains the same.

Referring back to FIG. 5, if there is any difference between the current reference RSSI value with the previous reference RSSI value as in decision 1345, the movement detection module (40) determines whether a full set of signals have changed as in decision 1375. If the full set of signals have changed, the type of movement of the user is classified as moving as in step 1380.

Flowever, if only parts of the set of signals have changed, the type of movement of the user is classified as rotating or changing direction in which the user is heading as in step 1390. Once the type of movement has been classified, the movement detection module (40) sends the type of movement to the DCE module (50) as in step 1360.

An example on how the movement detection module (40) determines whether a full set of signals have changed is explained in relation to FIG. 7 (a), FIG. 7 (b), and FIG. 8. FIG. 7 (a) and FIG. 7 (b) illustrate examples of placement of the transmitters (10). As shown in FIG. 7 (a) and FIG. 7 (b), there are six transmitters (10) known as Tx1 , Tx2, Tx3, Tx4, Tx5, and Tx6, wherein all six transmitters (10) are placed all around the user. FIG. 8 illustrates changes of reference RSSI value for each transmitter (10) Tx1 , Tx2, Tx3, Tx4, Tx5, and Tx6 when the user is moving and rotating. The x-axis represents the transmitters (10), while the y-axis represents the RSSI in decibel relative to one milliwatt, dBm. The triangles represent the previous reference RSSI value, the squares represent the current reference RSSI value when the user moves and the dots represent current reference RSSI value when the user rotates.

In the event when the user moves from one position to another position as shown in FIG. 7 (a), the samples of RSSI signals are collected when the user is moving from position 1 to position 2. The previous reference RSSI value represents the average RSSI value for each transmitter (10) when the user is in position, whereas the current reference RSSI value represents the average RSSI value for each transmitter (10) when the user is in position 2. As seen in FIG. 8, all current reference RSSI values for all transmitters (10) are different from the previous reference RSSI values. The reference RSSI values for Tx1 , Tx2, Tx3, and Tx4 drop while the reference RSSI values for Tx5 and Tx6 increase. This is because the user movement causes the user device to move further away from Tx1 , Tx2, Tx3 and Tx4 but closer to Tx5 and Tx6.

Another scenario is when the user is turning around, for example by 180 degree from its original position as shown in FIG. 7 (b). The samples of RSSI signals are collected before the user turns around and after the user has turned around. The previous reference RSSI value represents the average RSSI value for each transmitter (10) before the user turns around, while the current reference RSSI value when the user rotates represents the average RSSI value for each transmitter (10) after the user has turned around. As seen in FIG. 8, some of the current reference RSSI values when the user rotates are different from the previous reference RSSI value. The reference RSSI values for Tx1 , Tx2, and Tx3 which are blocked previously have increased as the user now has a direct path to Tx1 , Tx2, and Tx3. However, different from Tx6, the reference value for Tx6 has now decreased because the wireless signal transmitted by Tx6 is now blocked by the body of the user. The reference RSSI values for Tx4 and Tx5 which are on top of the user remain unchanged as the wireless signal transmitted by Tx4 and Tx5 is not affected by the rotation of the user. While embodiments of the invention have been illustrated and described, it is not intended that these embodiments illustrate and describe all possible forms of the invention. Rather, the words used in the specifications are words of description rather than limitation and various changes may be made without departing from the scope of the invention.

Claims

1 . A system (100) for locating a device in an indoor environment comprising:

a) a plurality of transmitters (10) configured for transmitting wireless signal to a terminal or a user device, wherein the plurality of transmitters (10) are installed throughout the indoor environment to surround the terminal or user device;

b) a processing module (30) configured for processing received strength signal indicator, RSSI of the wireless signal;

c) a distance constraint estimation module (50) configured for estimating all possible areas reachable by a user within a period of time;

d) a path estimation module (60) configured for estimating possible path taken by the user within a period of time based on the estimated possible areas reachable by the user; and

e) a location prediction module (70) configured for predicting location of the user based on the estimated path;

characterised in that the system (100) further comprising:

f) a movement detection module (40) configured for detecting user movement by using all statistical information of the RSSI and detecting rotation of the user based on attenuation effect on received RSSI due to blockage of a body of the user.

2. The system (100) as claimed in claim 1 , wherein the system (100) further comprising a scanning module (20) configured for scanning the indoor environment periodically to detect the wireless signal transmitted by the plurality of transmitters (10).

3. The system (100) as claimed in claim 1 , wherein the system further comprising a repository (80) configured for storing a map and a path of the indoor environment.

4. A method for locating a device in an indoor environment is characterised by the steps of:

a) scanning surrounding wireless signal transmitted by a plurality of transmitters (10) by a scanning module (20); b) processing the wireless signal to compute an average and statistical information of received signal strength indicator, RSSI by a processing module (30);

c) estimating all possible user movement based on the average and statistical information of the RSSI by a movement detection module (40);

d) computing all possible areas user can travel from a previous location based on speed of user movement by a distance constraint estimation module (50);

e) estimating all possible paths taken by the user based on the possible areas the user can travel by a path estimation module (60); and f) predicting current location of the user by a location prediction module

(70).

5. The method as claimed in claim 4, wherein processing the wireless signal to compute an average and statistical information of received signal strength indicator, RSSI by the processing module (30) includes the step of collecting a number of samples of the RSSI.

6. The method as claimed in claim 4, wherein estimating all possible user movement based on the average and statistical information of the RSSI by the movement detection module (40) includes the steps of:

a) detecting a number of healthy transmitters (10) to be used as reference transmitter (10), wherein the healthy transmitters (10) refer to the transmitters (10) with low signal fluctuation, strong signal strength and is highly detectable;

b) recording a current average RSSI value as reference received strength signal, RSSI value;

c) recording current RSSI value as previous reference RSSI value after a reference time has lapsed, wherein the reference time refer to the time interval between two movement detections are performed; d) comparing the previous reference RSSI value and the current reference RSSI value;

e) determining whether there is any difference between the current reference RSSI value with the previous reference RSSI value; and f) classifying type of movement of the user as idle if there is no difference between the current reference RSSI value with the previous reference RSSI value. 7. The method as claimed in claim 6, wherein if there is any difference between the current reference RSSI value with the previous reference RSSI value the steps include:

a) determining whether a full set of signals have changed;

b) classifying the type of movement of the user as moving the full set if signals have changed; and

c) classifying the type of movement of the user as rotating if parts of the signals have changed.