# US 8,280,671 B2 · Compressive data gathering for large-scale wireless sensor networks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,280,671 B2
- Document ID: US8280671B2
- Status: Granted
- Kind: B2
- Application number: 12/696,415
- Filed: 2010-01-29
- Published: 2011-08-04
- Granted: 2012-10-02
- Earliest claimed: 2010-01-29
- Assignees: Microsoft Corporation
- Inventors: Chong Luo; Feng Wu
- Web page: https://patentgrep.com/patent/US8280671B2

## CPC

- G06F 15/16: Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs {(coordinating program control therefor G06F9/52; in regulating and control system G05B)}
- H04L 67/12: specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
- H04Q 9/00: Arrangements in telecontrol or telemetry systems for selectively calling a substation from a main station, in which substation desired apparatus is selected for applying a control signal thereto or for obtaining measured values therefrom
- H04W 4/38: for collecting sensor information
- H04W 4/70: Services for machine-to-machine communication [M2M] or machine type communication [MTC]
- H04W 84/18: Self-organising networks, e.g. ad-hoc networks or sensor networks
- H04Q 2209/40: using a wireless architecture
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04Q: SELECTING (switches, relays, selectors H01H; wireless communication networks H04W)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

Techniques for data gathering in large-scale wireless sensor networks are described. A data collection device receives aggregate data from at least one sensor node of a group of N sensor nodes. The aggregate data includes M weighted sums. Each of the M weighted sums includes a respective sum of N products each of which being a product of a respective coefficient and a sensor reading from a respective one of the N sensor nodes. M and N are positive integers and M is less than N. Computation is performed on the aggregate data to recover sensor readings from the N sensor nodes.

## Claims

### Claim 1

A method of data gathering by a data collection device in a sensor network, the method comprising:
receiving aggregate data from at least one sensor node of a group of N sensor nodes each of which including at least one respective sensor, the aggregate data including M weighted sums of sensor readings, each weighted sum including a respective sum of N products each of which being a product of a respective coefficient and a sensor reading from a respective one of the N sensor nodes, M and N being positive integers and M<N; and
performing computation on the aggregate data to recover sensor readings from the N sensor nodes.

### Claim 2 (depends on 1)

The method of claim 1, wherein the N sensor nodes form P clusters of sensor nodes, each ith cluster of the P clusters having a sensor node as the ith cluster head and at least one other sensor node transmitting respective sensor readings to the ith cluster head, the P cluster heads transmitting sensor readings either directly to the data collection device or to another one of the P cluster heads, P being a positive integer and P<N.

### Claim 3 (depends on 1)

The method of claim 1, wherein the aggregate data is received by the data collection device as one data packet.

### Claim 4 (depends on 1)

The method of claim 1, wherein the aggregate data is received by the data collection device from the Nth sensor node as M data packets each of which including a respective one of the M weighted sums.

### Claim 5 (depends on 1)

The method of claim 1, wherein the performing computation on the aggregate data to recover sensor readings from the N sensor nodes comprises reordering the sensor readings in a first domain to achieve sparsity of the sensor readings in a second domain.

### Claim 6 (depends on 1)

The method of claim 1, wherein the performing computation on the aggregate data to recover sensor readings from the N sensor nodes comprises decomposing the aggregate data into a first vector and a second vector, the first vector containing normal readings of the respective sensor that are sparse in a first transform domain, the second vector containing abnormal readings of the respective sensor that are sparse in a time domain.

### Claim 7 (depends on 1)

The method of claim 1, wherein at least one of the coefficients is generated by the respective sensor node using a random seed and an identification of the respective sensor node.

### Claim 8 (depends on 1)

The method of claim 1, wherein the performing computation on the aggregate data to recover the sensor readings comprises:
reproducing the respective coefficients of the sensor nodes; and
performing computation using the reproduced respective coefficients to recover the sensor readings.

### Claim 9 (depends on 1)

The method of claim 1, wherein the sensor readings are spatially correlated, and wherein the performing computation on the aggregate data to recover the sensor readings comprises:
performing a discrete cosine transform computation using a spatial correlation between at least two of the N sensor nodes to recover the sensor readings from the at least two of the N sensor nodes.

### Claim 10 (depends on 1)

The method of claim 1, further comprising:
transmitting a random seed from the data collection device to the N sensor nodes before the N sensor nodes transmit data to report sensor readings to the data collection device; and
generating the respective coefficients by individual sensor nodes of the N sensor nodes using the random seed and an identification of the respective sensor node.

### Claim 11 (depends on 1)

The method of claim 1, further comprising:
receiving second aggregate data from at least one sensor node of a group of T sensor nodes each of which including at least one respective sensor, the group of T sensor nodes not including any sensor node of the group of N sensor nodes, the second aggregate data including Q weighted sums of sensor readings, each weighted sum including a respective sum of Q products, each of the T products being a product of a respective coefficient and a sensor reading from a respective one of the T sensor nodes, Q and T being positive integers and Q<R; and
performing computation on the second aggregate data to recover the sensor readings from the T sensor nodes.

### Claim 12

A method of data gathering in a sensor network, the method comprising:
receiving first data from a first sensor node by a second sensor node of a group of N sensor nodes, N being a positive integer, the first data including a product of a first coefficient and data collected by a first sensor, the first coefficient generated by the first sensor node using a random seed;
generating second data by the second sensor node, the second data including a product of a second coefficient and data collected by a second sensor, the second coefficient generated by the second sensor node using the random seed;
summing the first data and the second data to provide aggregate data; and
transmitting the aggregate data to report the aggregate data to a data collection device.

### Claim 13 (depends on 12)

The method of claim 12, wherein each of the first data and the second data includes M products each of which being a product of a respective coefficient and the data collected by the respective first or second sensor, M being a positive integer less than N, wherein individual coefficients in the respective first or second data are generated using the random seed, and wherein at least one coefficient in the respective first or second data is different from one other coefficient in the respective first or second data.

### Claim 14 (depends on 12)

The method of claim 12, wherein at least one of the first sensor node or the second sensor node includes a plurality of sensors, at least one sensor of the plurality of sensors being of a first type, at least one other sensor of the plurality of sensors being of a second type different from the first type.

### Claim 15 (depends on 12)

The method of claim 12, further comprising:
generating the first coefficient by the first sensor node using the random seed and an identification of the first sensor node; and
generating the second coefficient by the second sensor node using the random seed and an identification of the second sensor node.

### Claim 16 (depends on 12)

The method of claim 12, further comprising:
selecting a fourth sensor node to be a parent node by the second sensor node between the fourth sensor node and a fifth sensor node; and
transmitting a subscribe notification from the second sensor node to the fourth sensor node before transmitting the second data from the second sensor to the fourth sensor node.

### Claim 17 (depends on 12)

The method of claim 12, further comprising:
transmitting an unsubscribe notification from the second sensor node to a fourth sensor node; and
transmitting a subscribe notification from the second sensor node to a fifth sensor node before transmitting the second data from the second sensor node to the fifth sensor node.

### Claim 18

One or more computer readable media storing computer-executable instructions that, when executed, perform acts comprising:
receiving aggregate data from at least one sensor node of a group of N sensor nodes each of which including at least one respective sensor, the aggregate data including M weighted sums of sensor readings and sensor readings from M of the N sensor nodes, each weighted sum including a respective sum of N−M products, each of the N−M products being a product of a respective coefficient and a sensor reading from a respective one of the N−M sensor nodes, M and N being positive integers and M<N; and
performing computation on the aggregate data to recover the sensor readings from the N sensor nodes.

### Claim 19 (depends on 18)

The computer readable media of claim 18, wherein the performing computation on the aggregate data comprises performing computation on the aggregate data using a measurement matrix that has coefficients with which sensor readings are multiplied as entries of the measurement matrix, and wherein at least some of the entries of the measurement matrix are drawn from Gaussian distribution N(0, 1/M).

### Claim 20 (depends on 19)

The computer readable media of claim 19, wherein a maximum of M columns of the measurement matrix are drawn from an identity matrix of dimension M, and wherein the remaining of the entries of the measurement matrix are drawn from Gaussian distribution N(0, 1/M).
