Optimal deployment of fog computations in IoT environments

{
  "publication_number": "US10439890B2",
  "country": "US",
  "kind": "B2",
  "title": "Optimal deployment of fog computations in IoT environments",
  "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 1 C.r 1+Σ i=2 N (P i C +2. P 1 t {f,d 1 i }). r i Such that, Σ i=1 N r 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 ⁡ (1 CC 1 · h 1) · r 1 + ∑ i = 2 N ⁢ (1 CC i · h i + 1 t 1 i) · r i + Such that, Σ i=1 N r i =C r i ≥0,∀ i∈N 3, where, CC i represents number of CPU cores and corresponding operating frequency h i associated with ith Fog node, and t j i 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 ⁢ ⁢ P 1 C · r 1 + ∑ i = 2 N ⁢ (P i C + P i C + 2 · P 1 t ⁢ { f, d 1 i }) · r i Such that, Σ i=1 N r i =C (1 CC 1 · h 1) · r 1 + ∑ i = 2 N ⁢ (1 CC i · h i + 1 t 1 i) · r i ≤ L 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, CC i represents number of CPU cores and corresponding operating frequency h i associated with ith Fog node, and t j i represents transmission throughput.",
    "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 1 C.r 1+Σ i=2 N (P i C +2. P 1 t {f,d 1 i }). r i Such that, Σ i=1 N r 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 ⁡ (1 CC 1 · h 1) · r 1 + ∑ i = 2 N ⁢ (1 CC i · h i + 1 t 1 i) · r i + Such that, Σ i=1 N r i =C r i ≥0,∀ i∈N 3, Where, CC i represents number of CPU cores and corresponding operating frequency h i associated with ith Fog node, and t j i 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 ⁢ ⁢ P 1 C · r 1 + ∑ i = 2 N ⁢ (P i C + P i C + 2 · P 1 t ⁢ { f, d 1 i }) · r i Such that, Σ i=1 N r i =C (1 CC 1 · h 1) · r 1 + ∑ i = 2 N ⁢ (1 CC i · h i + 1 t 1 i) · r i ≤ L 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, CC i represents number of CPU cores and corresponding operating frequency h i associated with ith Fog node, and t j i represents transmission throughput.",
    "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."
  ],
  "description_excerpt": "This disclosure relates generally to Fog computing, and more particularly to system and methods for optimal deployment of Fog computations in Internet of Things (IoT) environments.\n\nTypically, cloud computing has been utilized as a central storage repository for Internet of things (IoT) devices since with cloud computing, data stored centrally can be accessed for computation or actuation. However, the data of high volume, velocity, variety, variability that is produced in IoT applications, additional architectural modifications to storage and processing architectures may be desirable.\n\nIn order to extend the cloud to be closer to the things that produce and act on IoT data, Fog computing can be used. Fog computing is particularly suited for IoT applications where sensors are typically mobile and produce data at large volumes and/or velocity. Moving the control and actuation servers to nodes nearer to the edge devices also reduces traffic on the cloud data centre, while still maintaining low latency overheads. Typically any device with computing, storage, and network connectivity can be a Fog node. For instance, devices such as industrial controllers, switches, routers, embedded servers, video surveillance cameras, and so on, may be example of Fog nodes. As the number of IoT devices scales to trillions of devices, various performance bottlenecks in last mile connectivity and central cloud access may occur.\n\nEmbodiments of the present disclosure present technological improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems.",
  "cpc": [
    "H04L 41/145",
    "G06F 9/45504",
    "H04L 41/0213",
    "H04L 41/0823",
    "H04L 41/0886",
    "H04L 43/0852",
    "H04L 43/10",
    "H04L 67/10",
    "H04W 4/70",
    "H04W 52/0254",
    "H04W 52/0261",
    "Y02D 30/70",
    "Y02D 70/142",
    "Y02D 70/144",
    "Y02D 70/162"
  ],
  "ipc": [
    "G06F 9/455",
    "H04L 12/24",
    "H04L 29/08",
    "G06F 15/16",
    "H04L 12/26",
    "H04W 4/70"
  ],
  "assignees": [
    "Tata Consultancy Services Ltd"
  ],
  "inventors": [
    "Ajay KATTEPUR",
    "Hemant Kumar RATH",
    "Anantha SIMHA"
  ],
  "filing_date": "2017-07-18",
  "publication_date": "2019-10-08",
  "grant_date": "2019-10-08",
  "priority_date": "2016-10-19",
  "application_number": "US-201715653190-A",
  "family_id": "61904120",
  "cited_by_count": 3,
  "citations": [
    "US7197639B1",
    "US8984500B2",
    "US8014308B2",
    "US9049248B2",
    "US20120331144A1",
    "US9641431B1",
    "DE102013001107A1",
    "US20160124407A1",
    "US9584876B2",
    "US9734659B2",
    "US20170228258A1",
    "US20160112518A1",
    "US20170250873A1",
    "US20170116526A1",
    "US20180146058A1"
  ]
}