A Bifactor Approximation Algorithm for Cloudlet Placement in Edge Computing

Author(s)Bhatta, Dixit
Author(s)Mashayekhy, Lena
Date Accessioned2022-02-02T20:07:58Z
Date Available2022-02-02T20:07:58Z
Publication Date2021-11-15
DescriptionThis article was originally published in IEEE Transactions on Parallel and Distributed Systems. The version of record is available at: https://doi.org/10.1109/TPDS.2021.3126256en_US
AbstractEmerging applications with low-latency requirements such as real-time analytics, immersive media applications, and intelligent virtual assistants have rendered Edge Computing as a critical computing infrastructure. Existing studies have explored the cloudlet placement problem in a homogeneous scenario with different goals such as latency minimization, load balancing, energy efficiency, and placement cost minimization. However, placing cloudlets in a highly heterogeneous deployment scenario considering the next-generation 5G networks and IoT applications is still an open challenge. The novel requirements of these applications indicate that there is still a gap in ensuring low-latency service guarantees when deploying cloudlets. Furthermore, deploying cloudlets in a cost-effective manner and ensuring full coverage for all users in edge computing are other critical conflicting issues. In this article, we address these issues by designing a bifactor approximation algorithm to solve the heterogeneous cloudlet placement problem to guarantee a bounded latency and placement cost, while fully mapping user applications to appropriate cloudlets. We first formulate the problem as a multi-objective integer programming model and show that it is a computationally NP-hard problem. We then propose a bifactor approximation algorithm, ACP, to tackle its intractability. We investigate the effectiveness of ACP by performing extensive theoretical analysis and experiments on multiple deployment scenarios based on New York City OpenData. We prove that ACP provides a (2,4)-approximation ratio for the latency and the placement cost. The experimental results show that ACP obtains near-optimal results in a polynomial running time making it suitable for both short-term and long-term cloudlet placement in heterogeneous deployment scenarios.en_US
SponsorThis research was supported in part by National Science Foundation grant CNS-1755913.en_US
CitationD. Bhatta and L. Mashayekhy, "A Bifactor Approximation Algorithm for Cloudlet Placement in Edge Computing," in IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 8, pp. 1787-1798, 1 Aug. 2022, doi: 10.1109/TPDS.2021.3126256.en_US
ISSN1558-2183
URLhttps://udspace.udel.edu/handle/19716/30247
Languageen_USen_US
PublisherIEEE Transactions on Parallel and Distributed Systemsen_US
Keywordsedge computingen_US
Keywordscloudletsen_US
Keywordsplacement costen_US
Keywordslatencyen_US
Keywordsapproximation algorithmen_US
TitleA Bifactor Approximation Algorithm for Cloudlet Placement in Edge Computingen_US
TypeArticleen_US
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
A Bifactor Approximation Algorithm for Cloudlet Placement.pdf
Size:
2.81 MB
Format:
Adobe Portable Document Format
Description:
Main article
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.22 KB
Format:
Item-specific license agreed upon to submission
Description: