Optimal deployment of fog computations in IoT environments

• US 10,439,890 B2
• Filed: 07/18/2017
• Issued: 10/08/2019
• Est. Priority Date: 10/19/2016
• Status: Active Grant

• Current Assignee: TATA Consultancy Services Limited (Tata Sons Pvt Ltd.)
• Original Assignee: TATA Consultancy Services Limited (Tata Sons Pvt Ltd.)
• Inventors: Kattepur, Ajay, Rath, Hemant Kumar, Simha, Anantha
• Primary Examiner(s): Nguyen, Quang N
• Application Number:
  US15/653,190
• Publication Number:
  US 20180109428A1
• Time in Patent Office: 812 Days
• Field of Search: 703203, 703206, 703217, 703219, 703223, 703224, 703226, 703228, 703230, 703232, 703238, 713168, 370252
• CPC Class Codes: G06F 9/45504 Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/0823 characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability for optimising operational conditions of wireless networks H04W24/02
• CPC Class Codes: H04L 41/0886 Fully automatic configuration
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04W 4/70 Services for machine-to-machine communication [M2M] or machine type communication [MTC]
• CPC Class Codes: H04W 52/0254 detecting a user operation or a tactile contact or a motion of the device
• CPC Class Codes: H04W 52/0261 managing power supply demand, e.g. depending on battery level
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

This disclosure relates to managing Fog computations between a coordinating node and Fog nodes. In one embodiment, a method for managing Fog computations includes receiving a task data and a request for allocation of at least a subset of a computational task. The task data includes data subset and task constraints associated with at least the subset of the computational task. The Fog nodes capable of performing the computational task are characterized with node characteristics to obtain resource data associated with the Fog nodes. Based on the task data and the resource data, an optimization model is derived to perform the computational task by the Fog nodes. The optimization model includes node constraints including battery degradation constraint, communication path loss constraint, and heterogeneous computational capacities of Fog nodes. Based on the optimization model, at least the subset of the computational task is offloaded to a set of Fog nodes.

Claims

1. A processor-implemented method for dynamically managing Fog computations between a coordinating node and a plurality of Fog nodes, the method at the coordinating node comprising:

receiving, a request for allocation of at least a subset of a computational task, and a task data associated with the computational task, via one or more hardware processors, the task data comprising data subset and one or more task constraints associated with at least the subset of the computational task;

characterizing the plurality of Fog nodes capable of performing the computational task with a plurality of node characteristics to obtain a resource data associated with the plurality of Fog nodes, via the one or more hardware processors;

deriving, based on the task data and the resource data, an optimization model for performing the computational task by the plurality of Fog nodes, via the one or more hardware processors, the optimization model comprises a plurality of node constraints including battery degradation constraint, communication path loss constraint, and heterogeneous computational capacities of the plurality of Fog nodes;

offloading at least the subset of the computational task to a set of Fog nodes from the plurality of Fog nodes based on the optimization model, via the one or more hardware processors; and

collating output of performing of the subset of computational task from the set of Fog nodes to obtain result of offloaded subset of the computational task.

2. The method of claim 1, further comprising communicating with the plurality of Fog nodes while receiving the request and offloading at least the subset of the computational task using one of a proxy-based communication topology, peer-based communication topology and clone-based communication topology.

3. The method of claim 2, wherein the resource data comprises node location, current drawn during performing the computational task and communication, total battery capacity, number of CPU cores and CPU operating frequency associated with the plurality of Fog nodes.

4. The method of claim 1, wherein deriving the optimization model comprises deriving a battery optimization model for optimizing battery consumed in performing the computational task and a communication between the coordinating node and the plurality of Fog nodes, based on the resource data.

5. The method of claim 4, wherein deriving the battery optimization model comprises minimizing an objective function associated with the battery consumption based on an equation:

min P₁^C.r1+Σ

_i=2^N(P_i^C+2.P₁^t{f,d_1i}).r_i

Such that, Σ

_i=1^Nr_i=C

P_i.r_i≤

P_i^Cap,∀

i∈

N

r_i≥

0,∀

i∈

N

where, P_i^c is battery consumed as a result of computation C for ith fog node, and P_i^cap is the battery capacity.

6. The method of claim 1, wherein deriving the optimization model comprises deriving a latency optimization model for optimizing a time to complete the computational task based on the resource data by the set of Fog nodes.

7. The method of claim 6, wherein deriving the latency optimization model comprises minimizing an objective function associated with a transmission throughput of the resource data based on an equation:

$\min <br><br>\left(\frac{1}{{\mathrm{CC}}_1·<br><br>h_1}\right)·<br><br>r_1+\underset{i=2}{\overset{N}{\sum <br><br>}}<br><br>\left(\frac{1}{{\mathrm{CC}}_i·<br><br>h_i}+\frac{1}{t_{1_i}}\right)·<br><br>r_i+$
Such that, Σ

_i=1^Nr_i=C

r_i≥

0,∀

i∈

N3,

where, CC_i represents number of CPU cores and corresponding operating frequency h_i associated with ith Fog node, and t_ji represents transmission throughput.

8. The method of claim 1, wherein deriving the optimization model comprises:

deriving a battery optimization model for optimizing battery consumed in performing the computational task based on the resource data by the set of Fog nodes; and

deriving a latency optimization model for optimizing a time to complete the computational task based on the resource data by the set of Fog nodes, wherein deriving the battery optimization model and the latency optimization model comprises minimizing an objective function defined as;

$\min <br><br><br><br>P_1^C·<br><br>r_1+\underset{i=2}{\overset{N}{\sum <br><br>}}<br><br>\left(P_i^C+P_i^C+2·<br><br>P_1^t<br><br>\left\{f,d_{1_i}\right\}\right)·<br><br>r_i$
Such that, Σ

_i=1^Nr_i=C

9. A system for dynamically managing Fog computations between a coordinating node and a plurality of Fog nodes, the system comprising:

one or more memories storing instructions; and

one or more hardware processors coupled to the one or more memories, wherein said one or more hardware processors are configured by said instructions to;

receive, a request for allocation of at least a subset of a computational task, and a task data associated with the computational task, the task data comprising data subset and one or more task constraints associated with at least the subset of the computational task;

characterize the plurality of Fog nodes capable of performing the computational task with a plurality of node characteristics to obtain a resource data associated with the plurality of Fog nodes;

derive, based on the task data and the resource data, an optimization model for performing the computational task by the plurality of Fog nodes, the optimization model comprises a plurality of node constraints including battery degradation constraint, communication path loss constraint, and heterogeneous computational capacities of the plurality of Fog nodes;

offload at least the subset of the computational task to a set of Fog nodes from the plurality of Fog nodes based on the optimization model; and

collate output of performing of the subset of computational task from the set of Fog nodes to obtain result of offloaded subset of the computational task.

10. The system of claim 9, wherein the one or more hardware processors are further configured by the instructions to to communicate with the plurality of Fog nodes while receiving the request and offloading at least the subset of the computational task using one of a proxy-based communication topology, peer-based communication topology and clone-based communication topology.

11. The system of claim 10, wherein the resource data comprises node location, current drawn during performing the computational task and communication, total battery capacity, number of CPU cores and CPU operating frequency associated with the plurality of Fog nodes.

12. The system of claim 9, wherein to derive the optimization model, wherein the one or more hardware processors are further configured by the instructions to derive a battery optimization model for optimizing battery consumed in performing the computational task and a communication between the coordinating node and the plurality of Fog nodes, based on the resource data.

13. The system of claim 12, wherein to derive the battery optimization model, the one or more hardware processors are further configured by the instructions to minimize an objective function associated with the battery consumption based on an equation:

min P₁^C.r1+Σ

_i=2^N(P_i^C+2.P₁^t{f,d_1i}).r_i

Such that, Σ

_i=1^Nr_i=C

P_i.r_i≤

P_i^Cap,∀

i∈

N

r_i≥

0,∀

i∈

N

where, P_i^c is battery consumed as a result of computation C for ith fog node, and P_i^cap is the battery capacity.

14. The system of claim 9, wherein to derive the optimization model, the one or more hardware processors are further configured by the instructions to derive a latency optimization model for optimizing a time to complete the computational task based on the resource data by the set of Fog nodes.

15. The system of claim 14, wherein to derive the latency optimization model, the one or more hardware processors are further configured by the instructions to minimize an objective function associated with a transmission throughput of the resource data based on an equation:

$\min <br><br>\left(\frac{1}{{\mathrm{CC}}_1·<br><br>h_1}\right)·<br><br>r_1+\underset{i=2}{\overset{N}{\sum <br><br>}}<br><br>\left(\frac{1}{{\mathrm{CC}}_i·<br><br>h_i}+\frac{1}{t_{1_i}}\right)·<br><br>r_i+$
Such that, Σ

_i=1^Nr_i=C

r_i≥

0,∀

i∈

N3,

Where, CC_i represents number of CPU cores and corresponding operating frequency h_i associated with ith Fog node, and t_ji represents transmission throughput.

16. The system of claim 9, wherein to derive the optimization model, wherein the one or more hardware processors are further configured by the instructions to:

derive a battery optimization model for optimizing battery consumed in performing the computational task based on the resource data by the set of Fog nodes; and

derive a latency optimization model for optimizing a time to complete the computational task based on the resource data by the set of Fog nodes, wherein deriving the battery optimization model and the latency optimization model comprises minimizing an objective function defined as;

$\min <br><br><br><br>P_1^C·<br><br>r_1+\underset{i=2}{\overset{N}{\sum <br><br>}}<br><br>\left(P_i^C+P_i^C+2·<br><br>P_1^t<br><br>\left\{f,d_{1_i}\right\}\right)·<br><br>r_i$
Such that, Σ

_i=1^Nr_i=C

17. A non-transitory computer-readable medium having embodied thereon a computer program for executing a method for dynamically managing Fog computations between a coordinating node and a plurality of Fog nodes, the method comprising:

receiving, a request for allocation of at least a subset of a computational task, and a task data associated with the computational task, the task data comprising data subset and one or more task constraints associated with at least the subset of the computational task;

characterizing the plurality of Fog nodes capable of performing the computational task with a plurality of node characteristics to obtain a resource data associated with the plurality of Fog nodes;

deriving, based on the task data and the resource data, an optimization model for performing the computational task by the plurality of Fog nodes, the optimization model comprises a plurality of node constraints including battery degradation constraint, communication path loss constraint, and heterogeneous computational capacities of the plurality of Fog nodes;

offloading at least the subset of the computational task to a set of Fog nodes from the plurality of Fog nodes based on the optimization model; and

collating output of performing of the subset of computational task from the set of Fog nodes to obtain result of offloaded subset of the computational task.