Distributed transforms for efficient data gathering in sensor networks

• US 8,855,011 B2
• Filed: 07/12/2011
• Issued: 10/07/2014
• Est. Priority Date: 07/12/2010
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Ortega, Antonio, Narang, Sunil K., Shen, Godwin, Perez-Trufero, Javier
• Primary Examiner(s): WILSON, ROBERT W
• Application Number:
  US13/181,493
• Publication Number:
  US 20120014289A1
• Time in Patent Office: 1,183 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04W 28/06 Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365
• CPC Class Codes: H04W 52/04 TPC
• CPC Class Codes: H04W 52/325 Power control of control or pilot channels
• CPC Class Codes: H04W 52/367 Power values between minimum and maximum limits, e.g. dynamic range
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Devices, systems, and techniques for data collecting network such as wireless sensors are disclosed. A described technique includes detecting one or more remote nodes included in the wireless sensor network using a local power level that controls a radio range of the local node. The technique includes transmitting a local outdegree. The local outdegree can be based on a quantity of the one or more remote nodes. The technique includes receiving one or more remote outdegrees from the one or more remote nodes. The technique includes determining a local node type of the local node based on detecting a node type of the one or more remote nodes, using the one or more remote outdegrees, and using the local outdegree. The technique includes adjusting characteristics, including an energy usage characteristic and a data compression characteristic, of the wireless sensor network by selectively modifying the local power level and selectively changing the local node type.

Claims

1. A method implemented by a local node in a wireless sensor network, the method comprising:

transmitting, from the local node, a first pilot signal using a local power level that controls a radio range of signals transmitted from the local node;

detecting, at the local node, one or more remote nodes included in the wireless sensor network, wherein detecting the one or more remote nodes comprises receiving one or more second pilot signals from the one or more remote nodes;

transmitting a local outdegree to the one or more detected remote nodes, the local outdegree being based on a quantity of the one or more detected remote nodes;

receiving one or more remote outdegrees from the one or more detected remote nodes;

determining a local node type of the local node, wherein determining the local node type comprises (i) exchanging messages with at least a portion of the one or more detected remote nodes, the messages indicating a node type, (ii) selectively assigning the local node type as a raw type based on information comprising the local outdegree, the one or more remote outdegrees, and one or more of the messages, and (iii) selectively assigning the local node type as an aggregation type based on a neighbor node being of the raw type, wherein a node of the raw type sends raw data to a node of the aggregation type, wherein the node of the aggregation type aggregates and compresses raw data; and

adjusting characteristics, including an energy usage characteristic and a data compression characteristic, of the wireless sensor network by (i) selectively modifying the local power level and (ii) selectively changing the local node type.

2. The method of claim 1, wherein the first pilot signal comprises an indication of the local power level, wherein the one or more received second pilot signals each comprise an indication of a power level, and wherein detecting the one or more remote nodes comprises:

transmitting an acknowledgement message based on a maximum power level indicated by the one or more received second pilot signals; and

receiving one or more acknowledgements from at least a portion of the one or more remote nodes.

3. The method of claim 2, wherein the local node type is the raw type, and wherein adjusting the characteristics comprises:

increasing the local power level to increase the radio range to reach one or more additional remote nodes; and

transmitting an additional signal at the increased local power level to cause at least a portion of the one or more additional remote nodes to become the aggregation type.

4. The method of claim 1, wherein adjusting the characteristics comprises performing an approximation-based distributed minimum set cover modification algorithm to change one or more node type assignments within the wireless sensor network to increase a data compression ratio.

5. The method of claim 4, wherein performing the approximation-based distributed minimum set cover modification algorithm comprises increasing the local power level to increase the radio range to reach one or more additional remote nodes.

6. The method of claim 1, wherein the node of the aggregation type is configured to perform a portion of a distributed wavelet transform to generate compressed data.

7. An apparatus comprising:

transceiver electronics to communicate with a wireless sensor network; and

processor electronics configured to (i) control the transceiver electronics to transmit a first pilot signal using a local power level that controls a radio range of signals transmitted via the transceiver electronics, (ii) detect one or more nodes of the wireless sensor network based on a reception, via the transceiver electronics, of one or more second pilot signals from the one or more nodes of the wireless sensor network, (iii) control the transceiver electronics to transmit a local outdegree to the one or more detected nodes, the local outdegree being based on a quantity of detected nodes, (iv) receive, via the transceiver electronics, one or more remote outdegrees from the one or more detected nodes, (v) determine a local node type of the apparatus based on the local outdegree, the one or more remote outdegrees, and one or more detected node types corresponding to at least a portion of the one or more detected nodes, respectively, and (vi) adjust characteristics, including an energy usage characteristic and a data compression characteristic, of the network by selectively modifying the local power level and selectively changing the local node type.

8. The apparatus of claim 7, wherein the processor electronics are configured to (i) exchange messages with at least a portion of the detected nodes, the messages indicating a node type, (ii) selectively assign the local node type as a raw type based on information comprising the local outdegree, the one or more remote outdegrees, and one or more of the messages, and (iii) selectively assign the local node type as an aggregation type based on a neighbor node being of the raw type, wherein a node of the raw type sends raw data to a node of the aggregation type, wherein the node of the aggregation type aggregates and compresses raw data.

9. The apparatus of claim 7, wherein the first pilot signal comprises an indication of the local power level, wherein the one or more second pilot signals each comprise an indication of a power level, and wherein the processor electronics are configured to transmit an acknowledgement message based on a maximum power level indicated by the one or more received second pilot signals, and receive one or more acknowledgements from the one or more detected nodes.

10. The apparatus of claim 7, wherein the processor electronics are configured to (i) cause an increase of the local power level to increase the radio range to reach one or more additional nodes and (ii) control a transmission of an additional signal at the increased local power level to cause the one or more additional nodes to become an aggregation type, wherein the local node type is a raw type, wherein a node of the aggregation type aggregates and compresses raw data.

11. The apparatus of claim 10, wherein the node of the aggregation type is configured to perform a portion of a distributed wavelet transform to generate compressed data.

12. The apparatus of claim 7, wherein the processor electronics are configured to perform an approximation-based distributed minimum set cover modification algorithm to change one or more node type assignments within the network to increase a data compression ratio.

13. The apparatus of claim 12, wherein the approximation-based distributed minimum set cover modification algorithm includes increasing the local power level to increase the radio range to reach one or more additional nodes.

14. A system comprising:

one or more first nodes, comprising first processor electronics and first transceiver electronics, configured to collect data, route data, or collect and route data within a wireless sensor network; and

a second node, comprising second processor electronics and second transceiver electronics, configured to collect data, route data, or collect and route data within the wireless sensor network, wherein the second processor electronics are configured to perform operations comprising;

controlling the second transceiver electronics to transmit a first pilot signal using a local power level that controls a radio range of signals transmitted from the second node;

detecting one or more of the first nodes based on a reception, via the second transceiver electronics, of one or more second pilot signals from at least a portion of the first nodes;

controlling the second transceiver electronics to transmit a local outdegree, the local outdegree being based on a quantity of the one or more detected first nodes;

controlling the second transceiver electronics to receive one or more remote outdegrees from the one or more detected first nodes;

controlling the second transceiver electronics to exchange messages with at least a portion of the one or more detected first nodes, wherein the messages comprise an indication of a node type of a transmitting node, the node type being selected from a group comprising an aggregation type and a raw type, wherein a node of the raw type is configured to send raw data to a node of the aggregation type, wherein a node of the aggregation type is configured to aggregate and compress raw data;

determining the node type of the second node based on information comprising the local outdegree, the one or more remote outdegrees, and one or more of the messages; and

adjusting characteristics, including an energy usage characteristic and a data compression characteristic, of the wireless sensor network by transmitting one or more additional messages based on (i) selectively modifying the local power level and (ii) selectively changing the node type of the second node.

15. The system of claim 14, wherein determining the node type of the second node comprises (i) detecting, via one or more of the messages, whether at least one of the detected first nodes is of the raw type, (ii) selectively assigning the node type of the second node as the raw type based on information comprising the local outdegree, the one or more remote outdegrees, and a lack of a detection that at least one of the detected first nodes is of the raw type, and (iii) selectively assigning the node type of the second node as an aggregation type based on a detection that at least one of the detected first nodes is of the raw type.

16. The system of claim 15, wherein the first pilot signal comprises an indication of the local power level, wherein the one or more received second pilot signals each comprise an indication of a power level, and wherein detecting the one or more of the first nodes comprises:

controlling the second transceiver electronics to transmit an acknowledgement message based on a maximum power level indicated by the one or more received second pilot signals; and

controlling the second transceiver electronics to receive one or more acknowledgements from at least a portion of the first nodes.

17. The system of claim 15, wherein the node type of the second node is the raw type, and wherein adjusting the characteristics comprises:

increasing the local power level to increase the radio range to reach one or more additional nodes; and

controlling the second transceiver electronics to transmit an additional signal at the increased local power level to cause at least a portion of the one or more additional nodes to become the aggregation type.

18. The system of claim 15, wherein the node of the aggregation type is configured to perform a portion of a distributed wavelet transform to generate compressed data.

19. The system of claim 14, wherein adjusting the characteristics comprises performing an approximation-based distributed minimum set cover modification algorithm to change one or more node type assignments of nodes within the system to increase a data compression ratio.

20. The system of claim 19, wherein performing the approximation-based distributed minimum set cover modification algorithm comprises increasing the local power level to increase the radio range to reach one or more additional nodes.