Graph-Based Heuristic Solution for Placing Distributed Video Processing Applications on Moving Vehicle Clusters
- 9 May 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network and Service Management
- Vol. 19 (3) , 3076-3089
Abstract
Vehicular fog computing (VFC) is envisioned as an extension of cloud and mobile edge computing to utilize the rich sensing and processing resources available in vehicles. We focus on slow-moving cars that spend a significant time in urban traffic congestion as a potential pool of onboard sensors, video cameras, and processing capacity. For leveraging the dynamic network and processing resources, we utilize a stochastic mobility model to select nodes with similar mobility patterns. We then design two distributed applications that are scaled in real-time and placed as multiple instances on selected vehicular fog nodes. We handle the unstable vehicular environment by a), Using real vehicle density data to build a realistic mobility model that helps in selecting nodes for service deployment b), Using community-detection algorithms for selecting a robust vehicular cluster using the predicted mobility behavior of vehicles. The stability of the chosen cluster is validated using a graph centrality measure, and c), Graph-based placement heuristics is developed to find the optimal placement of service graphs based on a multi-objective constrained optimization problem with the objective of efficient resource utilization. The heuristic solves an important problem of processing data generated from distributed devices by balancing the trade-off between increasing the number of service instances to have enough redundancy of processing instances to increase resilience in the service in case of node or link failure, versus reducing their number to minimize resource usage. We compare our heuristic to a mixed integer program (MIP) solution and a first-fit heuristic. Our approach performs better than these comparable schemes in terms of resource utilization and/or has a lesser service latency when compared to an edge computing-based service placement scheme.Keywords
All Related Versions
Funding Information
- European Regional Development Fund (13/RC/2077)
This publication has 31 references indexed in Scilit:
- Optimization-Oriented Resource Allocation Management for Vehicular Fog ComputingIEEE Access, 2018
- Folo: Latency and Quality Optimized Task Allocation in Vehicular Fog ComputingIEEE Internet of Things Journal, 2018
- Collaborative Task Offloading in Vehicular Edge Multi-Access NetworksIEEE Communications Magazine, 2018
- Fog Following Me: Latency and Quality Balanced Task Allocation in Vehicular Fog Computing2018
- Task Offloading for Mobile Edge Computing in Software Defined Ultra-Dense NetworkIEEE Journal on Selected Areas in Communications, 2018
- Parkmaster2017
- Specification, composition, and placement of network services with flexible structuresInternational Journal of Network Management, 2017
- A Smart Parking Lot Management System for Scheduling the Recharging of Electric VehiclesIEEE Transactions on Smart Grid, 2015
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Analysis of weighted networksPhysical Review E, 2004