Decentralized detection, localization, and tracking utilizing distributed sensors
A swarming agent architecture provides a distributed, decentralized, agent-based computing environment applicable to ground-based surveillance. The approach, called Sensor Network Integration through Pheromone Fusion, or “SNIPF,” provides an end-to-end demonstration that integrates self-contained sensor/communication nodes with novel swarming algorithms to detect foot and vehicular movement through a monitored area with minimal configuration and maintenance. A plurality of computational nodes distributed within the environment and, depending upon the way in which they are deployed, the various nodes are operative to sense the local environment, receive a message from a neighboring node, and transmit a message to a neighboring node. Given these capabilities, the nodes can collectively determine the presence and/or movement of a target and communicate this information to a user. Though not required, the system may include nodes that are capable of collectively determining the speed and heading of a target, and the gathered intelligence may be communicated to users within, and external to, the environment. A particularly useful configuration may include one or more ‘free’ nodes having relatively limited communications and computational power, and one or more anchor nodes equipped with GPS and/or long-distance communications capabilities.
1. A decentralized tracking system, comprising:
a plurality of computational nodes distributed within an environment, including nodes operative to perform the following functions:
a) sense the local environment,
b) receive a message from a neighboring node, and
c) transmit a message to a neighboring node; and
wherein at least a subset of the nodes are operative to:
a) define locally unique identifiers, and
b) collectively determine the presence and/or movement of a target and communicate this information to a user.
2. The system of claim 1 , including nodes that are capable of collectively determining the speed and heading of the target.
3. The system of claim 1 , including nodes that are capable of communicating the information to users within, and external to, the environment.
4. The system of claim 1 , including:
one or more free nodes having relatively limited communications and computational power; and
one or more anchor nodes equipped with long-distance communications capabilities.
5. The system of claim 1 , including:
one or more free nodes having relatively limited communications and computational power; and
one or more anchor nodes equipped with global-positioning satellite receiving and long-distance communications capabilities.
6. The system of claim 1 , wherein the environment is sensed using optical sensors.
7. A method of tracking the movement of a target within an environment, comprising the steps of:
distributed a plurality of self-contained computational nodes within the environment each node including a unique identifier, including free nodes having limited relatively limited communications capabilities;
sensing target information using local interactions among the free nodes.
8. The method of claim 7 , wherein the free nodes are accompanied by at least one anchor node equipped with long-distance communications capabilities; with the additional steps of
communicating the target information from each free node sensing the target to the anchor node; and
communicating the target information to an observer.
9. The method of claim 7 , wherein the target information is sensed visually.
10. The method of claim 7 , wherein the target information includes the directional movement of a person or object within the environment.
11. The method of claim 7 , wherein the target information includes velocity.
12. The method of claim 7 , wherein the nodes are randomly distributed within the environment.
13. The method of claim 7 , wherein the density of the nodes depends on sensing range.
14. The method of claim 7 , wherein the density of the nodes depends on communications range.
15. The method of claim 7 , wherein the density of the nodes depends on the nature of the targets.
16. The method of claim 7 , wherein the density of the nodes depends on the type of tracking.
17. The method of claim 7 , wherein the density is such that the target is visible to several nodes at a time.
18. The method of claim 7 , wherein the density is in the range of 1/10 m2 and 1/100 m2.
19. The method of claim 7 , wherein the nodes self-configure and construct gradients to the anchors.
20. The method of claim 7 , further including the step of repeating one or more operations to account for lost nodes.
21. The method of claim 7 , wherein each anchor broadcasts its identity and a hop count.
22. The method of claim 7 , wherein a node determines whether it detects a target by comparing its reading to a threshold.
23. The method of claim 7 , wherein a node determines whether it detects a target by comparing its reading to a threshold that varies depending on the percentage of its neighbors that also detect a target.
24. The method of claim 7 , wherein a node determines whether it detects a target by comparing its reading to a threshold that varies according to a sigmoid function depending on the percentage of its neighbors that also detect a target.
25. The method of claim 7 , wherein a node determines whether it is on an edge of the group of nodes that detect a target by comparing the percentage of its neighbors that also detect the target with a threshold.
26. The method of claim 7 , wherein a node estimates its distance from a detected target by propagating the estimates of its neighbors of how far they are from the nodes farthest from the target.
27. The method of claim 7 , wherein a node recognizes that it is as close as any other node to the target by listening to the edge distance estimates of its neighbors and hearing none that is greater than its own.
28. The method of claim 7 , wherein a node estimates the velocity of a target by tracking the rate of change of the node's distance from the edge of the set of nodes that detect the target.
29. The method of claim 7 , wherein a node estimates the velocity of a target by tracking the rate of change of the node's distance from the edge of the set of nodes that detect the target and disseminates this information to neighboring nodes with a gradient mechanism.
30. The method of claim 7 , wherein each receiving node performs a test to determine whether it has heard a higher hop count from the same anchor and, if not, concludes that it is on an expanding message front, increments the hop count and broadcasts the modified message.
31. The method of claim 7 , wherein each node remembers its minimum hop count from each anchor.
32. The method of claim 7 , wherein the counts define a gradient to route target reports to the anchor, and locate each node if there are at least three non-colinear anchors.
33. The method of claim 7 , wherein, once in position, the nodes interact in a sensing cycle whose frequency depends on the expected rate of change in the environment.
34. The method of claim 7 , using a sensing cycle on the order of 0.5 sec to track vehicles.
35. The method of claim 7 , using a sensing cycle on the order of 10 sec to track pedestrians.
36. The method of claim 7 , using a sensing cycle of several minutes to an hour or more to track the construction of a building or other facility.
37. The method of claim 7 , wherein the system tracks multiple target types by tagging messages among nodes to indicate the target type with which the message is concerned.