Query partitioning to decompose hotspots in sensor networks

• US 8,392,401 B1
• Filed: 10/19/2007
• Issued: 03/05/2013
• Est. Priority Date: 06/29/2007
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Aly, Mohamed, Youssef, Adel A.
• Primary Examiner(s): Btit, Jacob F
• Assistant Examiner(s): Shanmugasundaram, Kannan
• Application Number:
  US11/875,571
• Time in Patent Office: 1,964 Days
• Field of Search: 707/769, 707999001-999005, 707/713, 707/718
• US Class Current: 707/718
• CPC Class Codes: H04L 67/125 involving control of end-device applications over a network
• CPC Class Codes: H04L 67/566 Grouping or aggregating service requests, e.g. for unified processing

Abstract

A first query that is substantially similar to a second query is detected. A network of sensors includes a first sensor, a second sensor, and a data-source sensor, the first and second queries are addressed to the data-source sensor, and the first query is forwarded by the first sensor to the data-source sensor and the second query is forwarded by the second sensor to the data-source sensor. The data-source sensor provides, to the first sensor, results answering the first query. The first sensor provides the results to the second sensor.

Claims

1. A method comprising:

providing a network of sensors including a first sensor, a second sensor, and a data-source sensor, wherein each sensor is configured to transmit status information and operating data over the network to the data-source sensor as well as receive and respond to messages including queries from devices and commands from the data-source sensor;

receiving at the data-source sensor a first query at a first time from the first sensor;

processing the first query including storing the query and providing results answering the first query to the first sensor;

tracking with the data source sensor, that the data-source sensor provided the results to the first sensor including storing recent queries received from sensors in the sensor network, responses provided to the recent queries, and identifiers of the sensors to which the queries were provided;

receiving a second query at a second later time from the second sensor wherein the first and second queries are addressed to the data-source sensor and wherein the first query is forwarded by the first sensor to the data-source sensor and the second query is forwarded by the second sensor to the data-source sensor;

comparing the first query and the second query;

based on the comparing, detecting at the data-source sensor that the first query is substantially similar to the second query; and

when the first and second query are substantially similar, transmitting a message from the data source sensor to the first sensor instructing the first sensor to provide the results to the second sensor.

2. The method of claim 1, wherein the first query is substantially similar to the second query in the event that the first query and the second query request the same data from the data-source sensor.

3. The method of claim 1, wherein at least one of the first query and the second query requests data of a particular type stored on one or more sensors included in the sensor network.

4. The method of claim 1, wherein at least one of the first query and the second requests data related to a particular geographic area.

5. The method of claim 4, wherein the data related to a particular geographic area comprises at least one indication of an available capacity of the geographic area.

6. The method of claim 1, wherein:

the first query and the second query include more than one portion, and

the first query is substantially similar to the second query when the first query and the second query have at least one matching portion.

7. The method of claim 1 further comprising:

determining, by the data-source, that a predetermined number of queries were received in a predetermined time; and

sending an indicator to the first sensor to provide the results to the second sensor, and

wherein the results are provided to the second sensor based on the indicator.

8. The method of claim 1, wherein:

the network of sensors further includes devices configured to query the sensors included in the sensor network, and

the devices include at least one mobile device.

9. The method of claim 1, wherein:

the first query is forwarded using an underlying routing protocol of the sensor network, and

the results answering the query are provided to the first and second sensor using the underlying routing protocol of the sensor network.

10. The method of claim 9, wherein the underlying routing protocol is a point-to-point protocol.

11. The method of claim 1, wherein the first query and the second query are received at the data-source sensor within a predetermined amount of time relative to one another.

12. A system comprising:

a data-source sensor configured to;

receive a first query at a first time from a first sensor;

process the first query including storing the query;

receive a second query at a second later time from a second sensor;

wherein the first and second queries are addressed to the data-source sensor and wherein the first query is forwarded by the first sensor to the data-source sensor and the second query is forwarded by the second sensor to the data-source sensor, and wherein each of the first and second sensor is configured to transmit status information and operating data over a sensor network to the data-source sensor as well as receive and respond to messages including queries from devices and commands from the data-source sensor;

compare the first query and the second query;

detect that the first query is substantially similar to the second query;

provide, based on a determination that the first sensor and the second sensor are located in generally opposite directions relative to the data-source sensor, results answering the first query to an intermediate sensor that generally lies between a location of the first sensor and a location of the second sensor;

track that the data-source sensor provided the results to the intermediate sensor including storing recent queries received from sensors in the sensor network, responses provided to the recent queries, and identifiers of the sensors to which the queries were provided; and

transmit a message to the intermediate sensor instructing the intermediate sensor to provide the results both to the first sensor and the second sensor.

13. The system of claim 12, wherein the data-source sensor is further configured to:

determine a location of each of the first sensor, the second sensor, and the data-source sensor;

determine whether the locations of the first sensor, the second sensor, and the data-source sensor form an equilateral triangle;

send, if the locations form an equilateral triangle, the results answering the query to an intermediate sensor having a location between the first sensor and the second sensor; and

forward the results answering the query from the intermediate sensor to the first and second sensors.

14. The system of claim 12, wherein the first sensor and the second sensor are located in opposite directions relative to the data-source sensor if a distance from the data-source sensor to the first sensor is less than a distance from the data-source sensor to the second sensor.

15. The system of claim 14, wherein distance is based on a number of sensors a packet passes through when forwarded from the data-source sensor to the first or second sensor.

16. The system of claim 14, wherein distance is based on a geographic distance.

17. The system of claim 12, wherein the intermediate sensor generally lies between a location of the first sensor and a location of the second sensor in the event that:

the first sensor, the intermediate sensor, and the second sensor fall on a straight line, and

a distance from the intermediate sensor to either of the first or second sensors is not more than a distance from the first sensor to the second sensor.

18. A method comprising:

receiving at a data-source sensor a first query from a first sensor;

processing the first query including storing the query;

receiving a second query from a second sensor at a second later time from a second sensor;

wherein the first and second queries are addressed to the data-source sensor and wherein the first query is forwarded by the first sensor to the data-source sensor and the second query is forwarded by the second sensor to the data-source sensor, and wherein each of the first and second sensor is configured to transmit status information and operating data over a sensor network to the data-source sensor as well as receive and respond to messages including queries from devices and commands from the data-source sensor;

comparing the first query and the second query;

detecting at the data source sensor that the first query is substantially similar to the second query, wherein;

the second query is received before determining results answering the first query;

based on a determination that the first sensor and the second sensor are located in a same direction relative to the data-source sensor, the data-source sensor provides, to the first sensor, the results answering the first query;

tracking with the data source sensor that the data-source sensor provided the results to the first sensor including storing recent queries received from sensors in the sensor network, responses provided to the recent queries, and identifiers of the sensors to which the queries were provided; and

transmitting a message from the data source sensor to the first sensor instructing the first sensor to provide the results to the second sensor.

19. The method of claim 18, wherein the data-source sensor provides, to the first sensor, results answering the first query and a request to provide the results to the second sensor.

20. The method of claim 19, wherein the first sensor and the second sensor are located in same direction relative to the data-source sensor in the event that a distance from one of the first and second sensors to the data-source sensor is less than a distance from the other of the first and second sensors to the data-source sensor.

21. The method of claim 18, wherein the first query is substantially similar to the second query when the first query and the second query request the same data from the data-source sensor.

22. The method of claim 18, wherein at least one of the first query and the second query requests data related to a particular geographic area.

23. The method of claim 18, wherein:

the first query and the second query include more than one portion, and

the first query is substantially similar to the second query when the first query and the second query have at least one identical portion.

24. The method of claim 18, wherein:

the network of sensors further includes multiple devices configured to query the sensors included in the sensor network, and

the multiple devices include at least one mobile device.

25. The method of claim 18, wherein:

the first query is forwarded using an underlying routing protocol of the sensor network, and

the results answering the query are provided to the first and second sensor using the underlying routing protocol of the sensor network.

26. The method of claim 18, wherein the underlying routing protocol is a point-to-point protocol.

27. A non-transitory computer-readable storage medium having embodied thereon a computer program including instructions that, when executed perform operations comprising:

comparing a first query received by a data-source sensor from a first sensor to a second query received later by the data source sensor from a second sensor, wherein each of the first and second sensor is configured to transmit status information and operating data over a sensor network to the data-source sensor as well as receive and respond to messages including queries from devices and commands from the data-source sensor;

detecting that the first query is substantially similar to the second query, wherein;

the first and second queries are addressed to the data-source sensor;

the first query is forwarded by the first sensor to the data-source sensor and the second query is forwarded by the second sensor to the data-source sensor,

tracking that the data-source sensor provided the results to the first sensor including storing recent queries received from sensors in the sensor network, responses provided to the recent queries, and identifiers of the sensors to which the queries were provided; and

transmitting a message from the data source sensor to the first sensor instructing the first sensor to provide results answering the first query to the second sensor.

28. A non-transitory computer-readable storage medium having embodied thereon a computer program including instructions that, when executed perform operations comprising:

comparing a first query received by a data source sensor from a first sensor to a second query received later by the data source sensor from a second sensor, wherein each of the first and second sensor is configured to transmit status information and operating data over a sensor network to the data-source sensor as well as receive and respond to messages including queries from devices and commands from the data-source sensor;

detecting that the first query is substantially similar to the second query, wherein;

the first query and the second query are addressed to the data-source sensor,

the first query is forwarded by the first sensor to the data-source sensor and the second query is forwarded by the second sensor to the data-source sensor, and

the second query is received before determining results answering the first query; and

based on a determination that the first sensor and the second sensor are located in a same direction relative to the data-source sensor, the data-source sensor provides, to the first sensor, the results answering the first query;

tracking that the data-source sensor provided the results to the first sensor including storing recent queries received from sensors in the sensor network, responses provided to the recent queries, and identifiers of the sensors to which the queries were provided; and

transmitting a message from the data source sensor to the first sensor instructing the first sensor to provide the results to the second sensor.