Sensor Deployment With Target Regions
First Claim
1. A system of determining a set of placement sites from a set of candidate sites {p1, p2, . . . , pm} for at least one sensing station in a workspace, comprising:
- a) at least one sensed station, each said sensed station in a target region in said workspace, said target regions represented by set X;
b) zero or more obstructions in said workspace;
c) at least one sensing region vk(p) around each said at least one sensing station when said sensing station is at a candidate site p in said workspace, as a collection of each said target region such that said sensing station is able to sense said target region if said sensing station can sense said at least one sensed station in said target region when said sensed station is located anywhere in a portion of said target region as given by a measure C of said target region above a predetermined threshold, notwithstanding said obstructions;
d) a sensing range and a sensing orientation of said at least one sensing station constraining its said at least one sensing region vk(p);
e) a composite sensing region v(p) of each said at least one sensing station as a collection of all said k sensing regions vk(p) when the corresponding sensing station is at said candidate site p in said workspace;
f) a set family ={R1, R2, . . . , Rm} whose union is said set X and said at least one sensing station at a candidate site pi in said workspace is able to sense each said target region in set Ri;
wherein said set of placement sites are chosen from said set of candidate sites {91, p2, . . . , pm} based on a minimum set-cover for set system Σ
={X, }.
1 Assignment
0 Petitions
Accused Products
Abstract
The invention teaches an effective deployment strategy for sensors based on finding a set-cover solution of computational geometry. The system and methods of the invention teach embodiments to deploy sensors of varying capabilities in a workspace with real-world constraints. The workspace comprises a set of target regions or cells that are required to be observed. Sensor capabilities include having sensing stations with different types of sensors operating simultaneously to provide sensing, network or other types of coverages. Constraints include having range and directional constraints on the sensors, requiring sensing stations to be placed only within certain predetermined regions or locations of the workspace, and having a limited number of a certain type of sensors available. The invention finds a variety of real-world applications including tracking, coverage, and social media.
13 Citations
35 Claims
-
1. A system of determining a set of placement sites from a set of candidate sites {p1, p2, . . . , pm} for at least one sensing station in a workspace, comprising:
-
a) at least one sensed station, each said sensed station in a target region in said workspace, said target regions represented by set X; b) zero or more obstructions in said workspace; c) at least one sensing region vk(p) around each said at least one sensing station when said sensing station is at a candidate site p in said workspace, as a collection of each said target region such that said sensing station is able to sense said target region if said sensing station can sense said at least one sensed station in said target region when said sensed station is located anywhere in a portion of said target region as given by a measure C of said target region above a predetermined threshold, notwithstanding said obstructions; d) a sensing range and a sensing orientation of said at least one sensing station constraining its said at least one sensing region vk(p); e) a composite sensing region v(p) of each said at least one sensing station as a collection of all said k sensing regions vk(p) when the corresponding sensing station is at said candidate site p in said workspace; f) a set family ={R1, R2, . . . , Rm} whose union is said set X and said at least one sensing station at a candidate site pi in said workspace is able to sense each said target region in set Ri; wherein said set of placement sites are chosen from said set of candidate sites {91, p2, . . . , pm} based on a minimum set-cover for set system Σ
={X, }.- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
-
33. A system of determining a set of placement sites from a set of candidate sites {p1, p2, . . . , pm} for at least one sensing station in a workspace, comprising:
-
a) at least one sensed station, each said sensed station in a target region in said workspace, said target regions represented by set X; b) zero or more obstructions in said workspace; c) at least one sensing region vk(p) around each said at least one sensing station when said sensing station is at a candidate site p in said workspace, as a collection of each said target region such that said sensing station is able to sense said target region if said sensing station can communicate with said at least one sensed station in said target region when said sensed station is located anywhere in a portion of said target region as given by a measure C of said target region above a predetermined threshold, notwithstanding said obstructions; d) a sensing range and a sensing orientation of said at least one sensing station constraining its said at least one sensing region vk(p); e) a composite sensing region v(p) of each said at least one sensing station as a collection of all said k sensing regions vk(p) when the corresponding sensing station is at said candidate site p in said workspace; f) a set family ={R1, R2, . . . , Rm} whose union is said set X and said at least one sensing station at a candidate site pi in said workspace is able to sense said target regions in set Ri; wherein said set of placement sites is chosen from said set of candidate sites {p1, p2, . . . , pm} based on a minimum set-cover for set system Σ
={X, }.
-
-
34. A method for determining a set of placement sites from a set of candidate sites {p1, p2, . . . , pm} for at least one sensing station in a workspace, comprising the steps of:
-
a) providing at least one sensed station in a target region in said workspace, and representing said target regions by set X; b) providing zero or more obstructions in said workspace; c) providing at least one sensing region vk(p) around each said at least one sensing station when said sensing station is at a candidate site p in said workspace, to be a collection of each said target region such that said sensing station is able to sense said target region if said sensing station can sense said at least one sensed station in said target region when said sensed station is located anywhere in a portion of said target region as given by a measure C of said target region above a predetermined threshold, notwithstanding said obstructions; d) providing a sensing range and a sensing orientation for each said at least one sensing station to constrain its said at least one sensing region vk(p); e) providing a composite sensing region v(p) for each said at least one sensing station to be a collection of all said k sensing regions vk(p) when said sensing station is at said candidate site p in said workspace; f) providing a set family ={R1, R2, . . . , Rm} whose union is said set X and said at least one sensing station at a candidate site pi in said workspace is able to sense each said target region in set Ri; and
choosing said placement sites from said candidate sites {p1, p2, . . . , pm} based on a minimum set-cover for set system Σ
={X, }.
-
-
35. A method for determining a set of placement sites from a set of candidate sites {p1, p2, . . . , pm} for at least one sensing station in a workspace, comprising the steps of:
-
a) providing at least one sensed station in a target region in said workspace, and representing said target regions by set X; b) providing zero or more obstructions in said workspace; c) providing at least one sensing region vk(p) around each said at least one sensing station when said sensing station is at a candidate site p in said workspace, to be a collection of each said target region such that said sensing station is able to sense said target region if said sensing station can communicate with said at least one sensed station in said target region when said sensed station is located anywhere in a portion of said target region as given by a measure C of said target region above a predetermined threshold, notwithstanding said obstructions; d) providing a sensing range and a sensing orientation for each said at least one sensing station to constrain its said at least one sensing region vk(p); e) providing a composite sensing region v(p) for each said at least one sensing station to be a collection of all said k sensing regions vk(p) when the corresponding sensing station is at said candidate site p in said workspace; f) providing a set family ={R1, R2, . . . , Rm} whose union is said set X and said at least one sensing station at a candidate site pi in said workspace is able to sense each said target region in set Ri; and choosing said placement sites from said candidate sites {p1, p2, . . . , pm} based on a minimum set-cover for set system Σ
={X, }.
-
Specification