Robust Location Detection Based on Identifying Codes

A method for positioning beacons in a target area of a location detection system, wherein location areas are associated with potential beacon positions in said target area and are represented by vertices of a graph, wherein reliable connectivity between location areas is represented by edges between vertices that represent said location areas, and wherein all vertices of said graph form a set V;

• said method comprising:
• determining a plurality of sets C, each of said sets C being determined by repeating, until a set A is determined to be empty, the following steps:
• determining said set A as a set of all vertices that, if removed from said set C, would still cause the remaining vertices in said set C to represent a t-vertex-robust 1-identifying code for said graph, wherein t is a pre-defined integer number, and wherein for the determining of each of said plurality of sets C, said set V is used as an initialization for said set C;
• removing, if said set A is non-empty, one randomly selected vertex of said set A from said set C to obtain said set C for said next determining of said set A;
• and
• returning, if said set A is empty, said set C as the result of said determining of said set C;
• and
• assigning said beacons to those location areas that are represented by vertices of that set C of said plurality of determined sets C that has the smallest cardinality.

A location detection system, comprising a plurality of beacons positioned in a target area, wherein said beacons are positioned in said target area according to an assignment of beacons to location areas of said target area, wherein said location areas are associated with potential beacon positions in said target area and are represented by vertices of a graph, wherein reliable connectivity between location areas is represented by edges between vertices that represent said location areas, wherein all vertices of said graph form a set V, and wherein a determination of said assignment of said beacons to said location areas comprises:

• determining a plurality of sets C, each of said sets C being determined by repeating, until a set A is determined to be empty, the following steps:
• determining said set A as a set of all vertices that, if removed from said set C, would still cause the remaining vertices in said set C to represent a t-vertex-robust 1-identifying code for said graph, wherein t is a pre-defined integer number, and wherein for the determining of each of said plurality of sets C, said set V is used as an initialization for said set C;
• removing, if said set A is non-empty, one randomly selected vertex of said set A from said set C to obtain said set C for said next determining of said set A;
• and
• returning, if said set A is empty, said set C as the result of said determining of said set C;
• and
• assigning said beacons to those location areas that are represented by vertices of that set C of said plurality of determined sets C that has the smallest cardinality.

A software application for positioning beacons in a target area of a location detection system, wherein location areas are associated with potential beacon positions in said target area and are represented by vertices of a graph, wherein reliable connectivity between location areas is represented by edges between vertices that represent said location areas, and wherein all vertices of said graph form a set V;

• said software application comprising:
• program code for determining a plurality of sets C, each of said sets C being determined by repeating, until a set A is determined to be empty, the following steps:
• determining said set A as a set of all vertices that, if removed from said set C, would still cause the remaining vertices in said set C to represent a t-vertex-robust 1-identifying code for said graph, wherein t is a pre-defined integer number, and wherein for the determining of each of said plurality of sets C, said set V is used as an initialization for said set C;
• removing, if said set A is non-empty, one randomly selected vertex of said set A from said set C to obtain said set C for said next determining of said set A;
• and
• returning, if said set A is empty, said set C as the result of said determining of said set C;
• and
• program code for assigning said beacons to those location areas that are represented by vertices of that set C of said plurality of determined sets C that has the smallest cardinality.