# US 10,771,983 B2 · System and method for optimizing placement and number of radio-frequency beacons to achieve better indoor localization > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,771,983 B2 - Document ID: US10771983B2 - Status: Granted - Kind: B2 - Application number: 15/942,543 - Filed: 2018-04-01 - Published: 2019-10-03 - Granted: 2020-09-08 - Earliest claimed: 2018-04-01 - Assignees: Fuji Xerox Co., Ltd. - Applicants: Fuji Xerox Co., Ltd. - Inventors: Raphael Guenot-Falque; Miteshkumar Patel; Jacob Biehl - Web page: https://patentgrep.com/patent/US10771983B2 ## CPC - H04W 4/33: for indoor environments, e.g. buildings - H04W 16/20: for indoor coverage or short range network deployment - G01S 1/0423: {Mounting or deployment thereof} - H04W 4/02: Services making use of location information - H04W 4/80: Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication - H04W 48/12: using downlink control channel - H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72) - G01S: RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES ## Abstract A novel solution to generate an optimal spatial placement map of Radio Frequency (RF) beacons, such as Bluetooth Low Energy (BLE) beacons, which can be used for indoor localization. A described embodiment solves for both generating optimal number of beacons required in a given environment and optimizing their location. The solution also incorporates behavior of RF signal due to various environmental factors such as signal reflection and absorption due to static and dynamic obstacles. In one embodiment, the framework is built upon Genetic Algorithm (GA) for optimization of beacon placement. The experimental results achieved using one implementation of the described method reduced the number of beacons by 50% as compared to beacons placed using expert knowledge. Furthermore, the overall localization error increased by ˜0.4 m when the results using the RF/BLE map generated by the described system were compared with the RF/BLE map generated using expert knowledge. ## Claims ### Claim 1 A computer-implemented method, the method being performed in a computerized system comprising a central processing unit, a localization signal receiver and a memory, the computer-implemented method comprising: a. using the central processing unit for determining an optimal number of beacons in a plurality of beacons to be placed in an environment to achieve an optimal localization, wherein the optimal number of beacons is determined based on a first cost function, which combines a beacon coverage requirement and a beacon spread requirement to determine the optimal number of beacons, wherein determining an optimal number of beacons comprises starting with a number of beacons and iteratively adding one beacon; and b. using the central processing unit for determining an optimal placement of the beacons from the plurality of beacons in the environment to achieve the optimal localization, wherein the optimal placement of the beacons is determining by iteratively solving a best global position for the beacons using a second cost function, which combines the beacon coverage requirement and the beacon spread requirement to determine the optimal placement of the beacons. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the beacons are Radio Frequency (RF) beacons. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein the beacons are Bluetooth Low Energy (BLE) beacons. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, wherein the localization signal receiver is a radiofrequency receiver and wherein the localization signal sources are radiofrequency sources. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, wherein determining an optimal number of beacons comprises starting with an empty set of beacons and iteratively adding one beacon at a time until a predefined termination criterion has been met. ### Claim 6 (depends on 1) The computer-implemented method of claim 1, wherein the beacon coverage requirement is set to three such that scans from at least three beacons of the plurality of beacons are available at any point in the environment. ### Claim 7 (depends on 1) The computer-implemented method of claim 1, wherein the beacon spread requirement ensures that the beacons are spread sufficiently apart from each other and the beacon coverage requirement is simultaneously maintained. ### Claim 8 (depends on 1) The computer-implemented method of claim 1, further comprising terminating the iterations based on a predetermined criterion. ### Claim 9 (depends on 8) The computer-implemented method of claim 8, wherein the predetermined criterion is a number of completed iterations. ### Claim 10 (depends on 1) The computer-implemented method of claim 1, wherein the beacon spread requirement ensures that the beacons are spread as far apart from each other and simultaneously maintain the beacon coverage requirement of at least three beacons. ### Claim 11 (depends on 10) The computer-implemented method of claim 10, wherein the cost function is further based on: a cell within the environment, an indication of coverage at the cell from different beacon locations in the environment based on a determination that a scan exists at the cell from each beacon, and a normalization parameter that is an inverse of inter beacon distance the number of beacons. ### Claim 12 (depends on 11) The computer-implemented method of claim 11, wherein the indication of coverage is a binary value generated by thresholding RF signals from each beacon at a predetermined value. ### Claim 13 A non-transitory computer-readable medium embodying a set of computer-executable instructions, which, when executed in connection with a system comprising a central processing unit, a localization signal receiver and a memory, cause the system to perform a method comprising: a. using the central processing unit for determining an optimal number of beacons in a plurality of beacons to be placed in an environment to achieve an optimal localization, wherein the optimal number of beacons is determined based on a first cost function, which combines a beacon coverage requirement and a beacon spread requirement to determine the optimal number of beacons, wherein determining an optimal number of beacons comprises starting with a number of beacons and iteratively adding one beacon; and b. using the central processing unit for determining an optimal placement of the beacons from the plurality of beacons in the environment to achieve the optimal localization, wherein the optimal placement of the beacons is determine by iteratively solving a best global position for the beacons using a second cost function, which combines the beacon coverage requirement and the beacon spread requirement to determine the optimal placement of the beacons. ### Claim 14 A computerized system comprising a central processing unit, a localization signal receiver and a memory, the memory storing a set of computer-readable instructions causing the system to perform a method comprising: a. using the central processing unit for determining an optimal number of beacons in a plurality of beacons to be placed in an environment to achieve an optimal localization, wherein the optimal number of beacons is determined based on a second cost function, which combines a beacon coverage requirement and a beacon spread requirement to determine the optimal number of beacons, wherein determining an optimal number of beacons comprises starting with a number of beacons and iteratively adding one beacon; and b. using the central processing unit for determining an optimal placement of the beacons from the plurality of beacons in the environment to achieve the optimal localization, wherein the optimal placement of the beacons is determine by iteratively solving a best global position for the beacons using a second cost function, which combines the beacon coverage requirement and the beacon spread requirement to determine the optimal placement of the beacons. ### Claim 15 (depends on 14) The computerized system of claim 14, wherein the localization signal receiver is a radiofrequency receiver and wherein the localization signal sources are radiofrequency sources. ### Claim 16 (depends on 14) The computerized system of claim 14, wherein determining an optimal number of beacons comprises starting with an empty set of beacons and iteratively adding one beacon at a time until a predefined termination criterion has been met. ### Claim 17 (depends on 14) The computerized system of claim 14, wherein the beacon coverage requirement is set to three such that scans from at least three beacons of the plurality of beacons are available at any point in the environment. ### Claim 18 (depends on 14) The computerized system of claim 14, wherein the beacon spread requirement ensures that the beacons are spread sufficiently apart from each other and the beacon coverage requirement is simultaneously maintained.