METHODS AND SYSTEM FOR DYNAMIC REALLOCATION OF DATA PROCESSING RESOURCES FOR EFFICIENT PROCESSING OF SENSOR DATA IN A DISTRIBUTED NETWORK

• US 20080056291A1
• Filed: 09/01/2006
• Published: 03/06/2008
• Est. Priority Date: 09/01/2006
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Xia, Honghui, Liu, Zhen, Ying, Lei, Towsley, Donald F.
• Granted Patent: US 7,710,884 B2
• Time in Patent Office: Days
• US Class Current: 370/431
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/5088 involving task migration

Abstract

Methods and system for dynamic reallocation of data processing resources for efficient processing of sensor data in a distributed network is provided. The methods and system include determining a data transmission cost f_t; determining a data processing cost f_p; determining a data storage cost f_s; and determining a data query Q which minimizes f(f_t+f_p+f_s) for a system of networked data processing resources.

Claims

1. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for dynamic reallocation of data processing resources for efficient distributed processing of sensor data within a plurality of nearest neighbor nodes, the method comprising:

determining a data transmission cost f_t of the sensor data for each of the plurality of nearest neighbor nodes;

determining a data processing cost f_p of the sensor data for each of the plurality of nearest neighbor nodes;

determining a data storage cost f, of the sensor data for each of the plurality of nearest neighbor nodes; and

determining a data query Q which minimizes f(f_t+f_p+f_s).

2. The program storage device readable by a machine as in claim 1, tangibly embodying a program of instructions executable by the machine to perform the method for dynamic reallocation of data processing resources for efficient distributed processing of sensor data within the plurality of nearest neighbor nodes, wherein determining the data query Q which minimizes f(f_t+f_p+f_s) further comprises:

determining an operator placement matrix;

determining a node routing matrix; and

determining a data caching matrix.

3. The program storage device readable by a machine as in claim 1, tangibly embodying a program of instructions executable by the machine to perform the method for dynamic reallocation of data processing resources for efficient distributed processing of sensor data within the plurality of nearest neighbor nodes, wherein determining the operator placement matrix further comprises assigning a unit value to each of the plurality of nearest neighbor nodes generating sensor data.

4. The program storage device readable by a machine as in claim 1, tangibly embodying a program of instructions executable by the machine to perform the method for dynamic reallocation of data processing resources for efficient distributed processing of sensor data within the plurality of nearest neighbor nodes, wherein determining the node routing matrix further comprises:

determining at least one generating node within the plurality of nearest neighbor nodes; and

determining at least one receiving node within the plurality of nearest neighbor nodes.

5. The program storage device readable by a machine as in claim 1, tangibly embodying a program of instructions executable by the machine to perform the method for dynamic reallocation of data processing resources for efficient distributed processing of sensor data within the plurality of nearest neighbor nodes, wherein determining the data caching matrix further comprises:

determining at least one intermediate data caching matrix; and

determining at least one final data caching matrix.

6. A method for dynamic reallocation of data processing resources for efficient processing of sensor data in a distributed network, the method comprising:

networking a plurality of data objects

each of the plurality of data objects initializing its respective data states; and

each of the plurality of data objects distributing its respective data states to at least one of the plurality of data objects.

7. A method as in claim 6 wherein each of the plurality of data objects initializing its respective data states further comprises each of the plurality of data objects updating its respective data states.

8. A method as in claim 7 wherein each of the plurality of data objects distributing its respective data states to at least one of the plurality of data objects further comprises each of the plurality of data objects distributing its respective data states to at least one nearest neighbor data object.

9. A method as in claim 8 wherein each of the plurality of data objects distributing its respective data states to at least one nearest neighbor data object further comprises each of the plurality of data objects distributing its respective data states to at least one nearest neighbor data synchronously.

10. A method as in claim 8 wherein each of the plurality of data objects distributing its respective data states to at least one nearest neighbor data object further comprises each of the plurality of data objects distributing its respective data states to at least one nearest neighbor data asynchronously.

11. A method as in claim 8 wherein each of the plurality of data objects distributing its respective data states to the at least one nearest neighbor data object further comprises:

the at least one nearest neighbor data object receiving data states determining a data processing cost associated with the received data states; and

the at least one nearest neighbor data object receiving data states updating its respective data states if the data processing cost associated with the received data states is reduced.

12. A method as in claim 11 wherein determining the data processing cost associated with received data states further comprises:

determining a data transmission cost f_t;

determining a data processing cost f_p;

determining a data storage cost f_s; and

determining a data query Q which minimizes f(f_t+f_p+f_s).

13. A method as in claim 11 wherein determining the data query Q which minimizes f(f_t+f_p+f_s) further comprises:

determining an operator placement matrix;

determining a node routing matrix; and

determining a data caching matrix.

14. A method as in claim 6 wherein networking the plurality of data objects further comprises:

networking at least one sensor node;

networking at least one relay node; and

networking at least one data fusion center.

15. A method as in claim 6 wherein networking the plurality of data objects further comprises wireless networking the plurality of data objects.

16. A system for dynamic reallocation of data processing resources for efficient processing of sensor data in a distributed network, the system comprising:

a plurality of networked data objects initializing and distributing its respective data states to at least one of the plurality of data objects, wherein each of the plurality of networked data objects comprises a node selected from the group consisting of a sensor node, a relay node and a data fusion center, wherein each of the plurality of networked data objects comprise;

a data transmission cost f_t module for cost associated with transmission of the sensor data;

a data processing cost f_p module for cost associated with data processing of the sensor data;

a data storage cost f_s module for cost associated with data storage of the sensor data; and

a data query Q minimization module for minimizing cost associated with data transmission cost, data processing cost, and data storage cost, wherein the data query minimization module comprises;

an operator placement matrix;

a node routing matrix;

a data caching matrix, wherein the data caching matrix comprises;

at least one intermediate data caching matrix; and

at least one final data caching matrix.