Methods and system for dynamic reallocation of data processing resources for efficient processing of sensor data in a distributed network

• US 7,710,884 B2
• Filed: 09/01/2006
• Issued: 05/04/2010
• Est. Priority Date: 09/01/2006
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Ying, Lei, Towsley, Donald F., Xia, Honghui, Liu, Zhen
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): WOOD, JR, STEVEN A
• Application Number:
  US11/469,640
• Publication Number:
  US 20080056291A1
• Time in Patent Office: 1,341 Days
• Field of Search: None
• US Class Current: 370/238
• 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 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, including each of the plurality of data objects updating its respective data states;

each of the plurality of data objects distributing its respective data states to at least one of the plurality of data objects, including each of the plurality of data objects distributing its respective data states to a nearest neighbor data object;

the nearest neighbor data object receiving data states determining a data processing cost associated with the received data states, comprising;

determining a data transmission cost ft;

determining a data processing cost fp;

determining a data storage cost fs; and

determining a data query Q which minimizes f (ft+fp+fs), comprising;

determining an operator placement matrix;

routing data from the node where it is generated to the node where it is required as input; and

determining a data caching matrix; and

the 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;

wherein the distributed network is a sensor network, each of the data objects being one of relay node, a sensor node, or a fusion node;

reallocating data processing resources in response to minimization of network data transmission cost, data processing cost and data storage cost by the data query Q.

2. A method as in claim 1 wherein each of the plurality of data objects distributing its respective data states to the 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 object synchronously.

3. A method as in claim 1 wherein each of the plurality of data objects distributing its respective data states to the nearest neighbor data object further comprises each of the plurality of data objects distributing its respective data states to the nearest neighbor data asynchronously.

4. A method as in claim 1 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.

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

6. A system for dynamic reallocation of data processing resources for efficient processing of sensor data, the system comprising:

a distributed sensor network;

a plurality of networked data objects in the distributed network,

the 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 ft module for cost associated with transmission of the sensor data;

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

a data storage cost fs 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 data caching matrix, wherein the data caching matrix comprises;

at least one intermediate data caching matrix; and

at least one final data caching matrix;

wherein said reallocating data processing resources in response to minimization of network data transmission cost, data processing cost and data storage cost by the data query Q.