Source-linked AI summary
Edge-Fog Cloud: A Distributed Cloud for Internet of Things Computations
Nitinder Mohan, Jussi Kangasharju
TL;DR
IoT applications need to process large volumes of distributed sensor data despite network delay and centralized-cloud dependence. The paper proposes a decentralized Edge-Fog cloud with LPCF task assignment, and reports near-optimal networking costs alongside effective task-assignment performance across evaluated scenarios.
Problem
IoT computation can be constrained by network delay, network load, and centralized-cloud dependence when processing large volumes of distributed data.
Method
The paper proposes a decentralized Edge-Fog cloud and LPCF, which assigns tasks by first minimizing processing cost and then optimizing network cost.
Results
LPCF achieves near-optimal networking costs in polynomial time and performs effectively against related assignment approaches across evaluated scenarios.
Takeaways & Limitations
Edge-Fog cloud provides a decentralized model for computation-based, high-volume, distributable IoT data while retaining a centralized store for data resilience.
Abstract
from arXiv · showhide
Internet of Things typically involves a significant number of smart sensors sensing information from the environment and sharing it to a cloud service for processing. Various architectural abstractions, such as Fog and Edge computing, have been proposed to localize some of the processing near the sensors and away from the central cloud servers. In this paper, we propose Edge-Fog Cloud which distributes task processing on the participating cloud resources in the network. We develop the Least Processing Cost First (LPCF) method for assigning the processing tasks to nodes which provide the optimal processing time and near optimal networking costs. We evaluate LPCF in a variety of scenarios and demonstrate its effectiveness in finding the processing task assignments.
I. Introduction
IoT computation can suffer from network delay and centralized-cloud dependence when processing distributed, high-volume data. The paper proposes a decentralized Edge-Fog cloud and LPCF task assignment method to address these constraints.
- IoT systems generate data across many sensors, making network delay and network load important processing constraints.Data must often be shared with a cloud service for processing, while time-critical applications can be limited by offloading delay.
- Existing Edge and Fog approaches localize preprocessing but retain dependence on a centralized cloud for computationally intensive tasks.This works for tightly coupled data and computation but is disadvantageous for applications with large distributed data and interactive users.
- Edge-Fog cloud is a fully decentralized hybrid with volunteer edge devices, capable fog devices, and a central store for raw and computed data.The architecture handles processing close to data generators while retaining centralized data storage.
- LPCF assigns tasks to available nodes while minimizing processing time and network costs, achieving near-optimal networking costs in polynomial time.The method is presented as an alternative to exponential-time assignment approaches.
- The authors develop a simulator integrated with LPCF and compare its efficiency with related approaches across multiple parameters and simulations.
II. Edge-Fog Cloud
The Edge-Fog cloud uses a node-oriented, three-layer architecture that combines nearby volunteer resources, capable fog devices, and centralized data storage. Its layers divide computation and storage according to resource capabilities and roles.
- The Edge-Fog cloud is organized as three resource layers using a node-oriented rather than network-oriented model.
- Edge Layer: The Edge layer contains volunteer, human-operated devices near IoT sensors, with heterogeneous computational capabilities and device-to-device connectivity.These resources are assumed to connect reliably to the Fog layer.
- Fog Layer: The Fog layer comprises managed routers and switches with high computing capabilities, native cloud-logic support, and high-speed reliable interconnections.Fog devices are farther from the edge than Edge resources but closer than a central cloud, handling computationally intensive tasks.
- Edge Layer: The paper leaves incentive or credit mechanisms for volunteering Edge devices outside its scope.
- Data Store: The Data Store has no computational capabilities and centrally archives cloud data for reliable access by both Edge and Fog resources.
B. Benefits of the Edge-Fog cloud
The Edge-Fog cloud is presented as a decentralized platform that reduces network load while supporting mobility, context, reliability, and distributed IoT applications.
- Computation near IoT data generators reduces the amount of data flowing through the network.
- Edge resources such as smartphones and laptops provide native physical and virtual mobility for mobile IoT applications.
- Edge resources can combine sensor data using location or application context, while decentralized computation avoids a single point of failure.Multiple application snapshots can be deployed to increase reliability.
- Distributed, network-constrained applications such as connected vehicles, energy monitoring, and automated traffic control can benefit from the model.
III. Task Deployment on Edge-Fog Cloud
Task deployment maps jobs to Edge-Fog resources while minimizing processing and networking costs. The assignment problem grows factorially, and QAP-based optimization becomes impractical for large deployments.
- Deployment model: Deployment maps each job in a job graph to an Edge or Fog resource while accounting for device processing power and communication costs.The deployment cost depends on both resource properties and task coordination requirements.
- NOC assignment: NOC minimizes networking cost by assigning N jobs to N devices using device-connectivity and job-dependency relationships.The formal model uses Dconn, Jconn, and an assignment constraint f(i).
- NOC assignment: The number of possible NOC assignments is N!, making exhaustive search impractical as the number of jobs and devices increases.A naive NOC implementation searches the entire assignment space.
- Computational challenge: QAP formulations are NP-hard, and computing optimal assignments for large Edge-Fog deployments can require prohibitive time.A 30-node QAP instance may take up to a week on a 2500-machine computational grid.
B. Least Processing Cost First (LPCF) Assignment
LPCF first minimizes processing cost with a polynomial-time linear assignment step, then searches equivalent low-processing-cost assignments for the lowest networking cost. This yields minimum processing cost with near-optimal networking cost while accounting for limited Edge capacity.
- Processing-cost optimization: LPCF first minimizes processing cost because Edge resources may have limited processing capability.The approach prioritizes processing cost before network optimization.
- Processing-cost optimization: LPCF uses a linear assignment objective with job sizes, device processing power, and binary assignment variables.The variables and matrices define the processing-cost objective.
- Processing-cost optimization: The first LPCF step solves the linear assignment problem optimally in O(n^3) worst-case time using algorithms such as Kuhn-Munkres or Hungarian.Unlike QAP, the linear assignment formulation is polynomial.
- Search-space reduction: LPCF reduces the search space by enumerating assignments equivalent in processing cost across homogeneous devices or jobs.Interchanging jobs among homogeneous devices does not change the processing cost.
- Network-cost optimization: LPCF selects the lowest-network-cost assignment from the reduced space, producing minimum processing cost and almost optimal network cost.A branch-and-bound variant can reduce search time for large reduced spaces.
- Advantages: Unlike NOC-based algorithms, LPCF guarantees polynomial-time assignment and incorporates processing cost as well as networking cost.This addresses both scalability and heterogeneous device capabilities.
IV. Evaluation
The evaluation uses a Python simulator that generates Edge-Fog networks and job-dependence graphs, then compares LPCF with permutation-based and QAP-based NOC solvers.
- Experimental setup: The Python simulator generates Edge-Fog resource networks and job-dependence graphs from user-defined parameters.Default evaluation parameters are reported in Table II.
- Experimental setup: The evaluation compares LPCF with permutation-based and QAP-based variants of the NOC task-assignment solver.The QAP-based comparison uses an open-source Kuhn-Munkres implementation from QAPLIB.
A. Processing time analysis
Processing-time analysis compares LPCF with NOC solvers across topology sizes under a one-hour computation limit. LPCF is much faster on medium deployments but can exceed the limit on large reduced search spaces.
- Processing-time analysis: The analysis measures assignment-computation time across problem sizes with a maximum completion time of one hour.Results are reported in Table III.
- Results: For approximately 30-node topologies, LPCF finds an assignment in under a second while both NOC solvers exceed the time limit.This comparison concerns finding an optimal assignment under the stated limit.
- Results: For approximately 150-node topologies, LPCF exceeds the allotted time because its reduced search space remains large.The authors identify branch-and-bound as a potential way to reduce search time.
B. Comparative study of associated costs
LPCF prioritizes processing cost while maintaining near-optimal network cost, and its processing assignment cost is lower than NOC’s.
- Figure 3 compares network and processing costs against NOC, minimum-bound, and maximum-bound assignments.
- For large topologies under equal computation-time limits, LPCF yields lower associated network cost than NOC.
- LPCF’s associated processing cost is always lower than NOC’s.
V. Discussion
Network cost decreases as Edge, Fog, and inter-layer connection densities increase, while greater job dependence raises and eventually stabilizes assignment cost.
- The study varies each layer’s connection density from 20% to 80% and job-graph interdependence from 10% to 100%.
- Increasing Edge, Fog, and interconnection densities decreases network cost by ~21%, ~9%, and ~17%, respectively.Inter-layer density has the largest reported effect among the three connection types.
- Inter-layer connections have a larger effect on overall network cost than Edge or Fog connection density.
- Higher job dependence increases network cost because dependence links map onto device links and larger dependencies create denser link meshes.
- After a particular job-dependency value, assignment network cost stabilizes because all heavy device-graph links are already included.
VI. Related Work
Edge-Fog cloud differs from prior edge and fog approaches by combining layered resources with an entirely decentralized mechanism for distributed IoT computation.
- Prior work brings cloud resources closer to the network edge through fog, edge, cloudlet, peer, nano-data-center, micro-cloud, and community-cloud models.
- Unlike approaches that rely on a central entity to schedule and process tasks, Edge-Fog cloud uses an entirely decentralized computing mechanism.
- Its nodular, layered architecture supports computations on distributed, semi-dependent data produced by IoT.
VII. Conclusion
The paper proposes Edge-Fog cloud as a decentralized model for high-volume, distributable IoT data and introduces task allocation that reduces deployment time without sacrificing associated cost.
- Edge-Fog cloud is a decentralized cloud model for computation-based, high-volume, distributable data such as IoT-generated data.
- The model builds on Edge and Fog approaches and provides data resilience through a centralized data store.
- Its task allocation mechanism significantly reduces deployment time without sacrificing associated cost compared with related approaches.
- Future work includes practical implementation and deployment issues for LPCF in a realistic Edge-Fog scenario.