Method of beacon-based positioning system

Patent metadata

Field	Value
Publication number	US-11567158-B2
Application number	US-202017006764-A
Country	US
Kind code	B2
Filing date	Aug 28, 2020
Priority date	Aug 28, 2020
Publication date	Jan 31, 2023
Grant date	Jan 31, 2023

Abstract

Disclosed is a beacon-based positioning system. A beacon position in which a beacon is installable is defined in a target space, and a path loss model of radio frequency (RF) signals between all beacon positions and all observation positions of a scanner is determined. Among all possible installation plans for the beacon positions, an installation plan in which different beacon signals, whose RSSIs calculated using the path loss model have significant values, are received in a number greater than or equal to a minimum reference number and a total number of the beacons installed is minimum is determined as an optimal installation plan. The optimization problem of determining the optimal installation plan may be expressed by binary linear programming.

First claim

What is claimed is:

1. A method of designing a positioning system in a target space by a modeling guide device having a beacon driver and a scanner communicator, the method comprising:
receiving, by the scanner communicator, information on a received signal strength indicator (RSSI) measured by a particular scanner at a sampled observation position in a target space from a signal transmitted by a particular beacon at a sampled beacon position in the target space;
determining, by the modeling guide device, a path loss model of a radio frequency (RF) signal for all combinations of beacon positions and observation positions defined in the target space by determining parameters of the path loss model using the measured RSSIs transmitted by scanners;
determining, by the modeling guide device, significant RSSIs which are selected from the calculated RSSIs and are greater than or equal to a reference value, wherein the calculated RSSIs are calculated using the path loss model for all combinations of the beacon positions and the observation positions defined in the target space;
determining, by the modeling guide device, a constraint in which a number of the significant RSSIs for each observation position is greater than or equal to a minimum reference number; and
determining, by the modeling guide device, an optimal installation plan for the beacon positions, which minimizes an objective function expressing the number of beacons, among candidates for the optimal installation plan, which satisfy the constrain.

2. The method of claim 1 , further comprising:
communicating, by a beacon driver, the beacons to select a particular beacon to set parameters of wireless communication or instruct start or end of transmission.

3. The method of claim 1 , wherein the objective function is expressed as a function of summing binary function terms having a value of 1 when a beacon is installed at a beacon position i defined in the target space and having a value of 0 when a beacon is not installed at the beacon position i with respect to all the beacon positions for each of the beacon installation plans.

4. The method of claim 1 , wherein the constraint is expressed using a constraint matrix in which an element (j, i) has a value expressing whether the RSSI value of a signal received at an observation position j upon being transmitted from a beacon position i is greater than or equal to a reference value.

5. The method of claim 4 , wherein the constraint is expressed as an inequality expression that a product of the constraint matrix and an installation plan vector in which an element (i) has a value of 1 when a beacon is installed at a beacon position I and has a value zero (0) when a beacon is not installed at the beacon position i is greater than or equal to a lower limit reference vector in which all elements are the same minimum reference number.

6. The method of claim 4 , wherein the constraint matrix is a matrix in which each of the corresponding elements has one value among a predetermined number of values in a range of 0 to 1 according a range of the calculated RSSI value of the signal received at the observation position j upon being transmitted from the beacon position i.

7. The method of claim 6 , wherein the constraint matrix is a matrix in which the element (j, i) has a value of 1 when the calculated RSSI value of the signal received at the observation position j upon being transmitted from the beacon position i is greater than or equal to a reference value and has a value of 0 otherwise.

8. The method of claim 6 , wherein the constraint matrix is a matrix in which the element (j, i) has a value of 0 when the calculated RSSI value of the signal received at the observation position j upon being transmitted from the beacon position i is less than a first reference value, has a value of 0.5 when the calculated RSSI value of the received signal is greater than or equal to the first reference value and less than or equal to a second reference value, and has a value of 1 when the calculated RSSI value of the received signal is greater than the second reference value.

9. The method of claim 7 , wherein determining the optimal installation plan includes calculating a beacon installation plan that minimizes the objective function by binary linear programming.

10. The method of claim 1 , wherein the objective function is obtained by subtracting the number of predetermined beacons which are to be installed at particular beacon positions from a total number of beacons installed in an area of a new target space except for a position that is determined for installation of predetermined beacons in advance in an area of the target space.

11. The method of claim 10 , wherein the constraint is expressed as an inequality expression including a constraint matrix that expresses whether the calculated RSSI value of a signal received at an observation position j upon being transmitted from a beacon position i is greater than or equal to a reference value in the area of the new target space except for the position determined for installation of predetermined beacons in advance in an area of the target space.

12. The method of claim 1 , wherein the constraint is defined according to two dimensional directions with X and Y direction of the target space.

13. The method of claim 12 , wherein the constraint is expressed using a X directional constraint matrix in which an element (j, i) has a value of square of projection in the X direction of 1 when the calculated RSSI value of a signal received at an observation position j upon being transmitted from a beacon position i is greater than or equal to a reference value, and a Y direction constraint matrix in which an element (j, i) has a value of square of projection in the Y direction of 1 when the calculated RSSI value of a signal received at an observation position j upon being transmitted from a beacon position i is greater than or equal to a reference value.

14. A computer program storage device using the method according to claim 1 .

15. A computer program storage device using the method according to claim 9 .

Assignees

• Solid Inc

Inventors

• Cho Young Man
• Cho Yvonne Hee Jun

Classifications

• H04W16/18

  Network planning tools · CPC title

• H04B17/318

  Received signal strength · CPC title

• G01S5/0242

  Determining the position of transmitters to be subsequently used in positioning (G01S5/0289 takes precedence) · CPC title

• G01S1/0423 Primary

  Mounting or deployment thereof · CPC title

• H04W16/20

  for indoor coverage or short range network deployment · CPC title