<p>Task offloading in fog computing has emerged as a pivotal solution to address the computational constraints of IoT devices, particularly for delay-sensitive applications. This paper introduces a distributed algorithm for Maximum Utility Task Offloading, where the utility is defined as the inverse of the service delay. Unlike existing centralized approaches, our method leverages a decentralized framework, enabling user devices and access points to collaboratively optimize task assignments without reliance on a central authority. The problem is modelled as a maximum-weight matching problem on bipartite graphs, and we present a deterministic distributed algorithm with a <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10922_2025_9918_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="67" /> </InlineMediaObject> <EquationSource Format="TEX">$(1/3-\varepsilon )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>3</mn> <mo>-</mo> <mi>ε</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-approximation ratio for any <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10922_2025_9918_Article_IEq2.gif" Format="GIF" Height="13" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">$\varepsilon > 0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> under the <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10922_2025_9918_Article_IEq3.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="89" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {CONGEST}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">CONGEST</mi> </math></EquationSource> </InlineEquation> model of computation in <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10922_2025_9918_Article_IEq4.gif" Format="GIF" Height="24" Rendition="HTML" Resolution="72" Type="Linedraw" Width="217" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {O}\left( \frac{1}{\varepsilon }\log ^2\left( {\Delta /\varepsilon }\right) \log _{1+\sqrt{\varepsilon }}{\left( 1/D\right) } \right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mfenced close=")" open="("> <mfrac> <mn>1</mn> <mi>ε</mi> </mfrac> <msup> <mo>log</mo> <mn>2</mn> </msup> <mfenced close=")" open="("> <mrow> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">/</mo> <mi>ε</mi> </mrow> </mfenced> <msub> <mo>log</mo> <mrow> <mn>1</mn> <mo>+</mo> <msqrt> <mi>ε</mi> </msqrt> </mrow> </msub> <mfenced close=")" open="("> <mn>1</mn> <mo stretchy="false">/</mo> <mi>D</mi> </mfenced> </mfenced> </mrow> </math></EquationSource> </InlineEquation>-round, where <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10922_2025_9918_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\Delta $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Δ</mi> </math></EquationSource> </InlineEquation> is the maximum degree of the network graph and <i>D</i> is the minimum service delay in the network. Our approach scales efficiently as it is independent of the network size and adapts to the dynamic nature of IoT environments, incorporating realistic constraints such as communication delays and heterogeneous resource availability. Extensive simulations validate the efficacy of the proposed algorithm across diverse scenarios, including varying workload distributions and network densities. Results demonstrate comparable performance with respect to centralized greedy approaches, while providing substantial benefits in terms of scalability and adaptability.</p>

Distributed Maximum Utility Task Offloading for Delay-Sensitive IoT Applications in Cloud and Edge Computing

期刊论文
发表日期：

2025年3月6日

查看全文

Subhas Kumar Ghosh,
Vijay Monic Vittamsetti

摘要

Task offloading in fog computing has emerged as a pivotal solution to address the computational constraints of IoT devices, particularly for delay-sensitive applications. This paper introduces a distributed algorithm for Maximum Utility Task Offloading, where the utility is defined as the inverse of the service delay. Unlike existing centralized approaches, our method leverages a decentralized framework, enabling user devices and access points to collaboratively optimize task assignments without reliance on a central authority. The problem is modelled as a maximum-weight matching problem on bipartite graphs, and we present a deterministic distributed algorithm with a $(1/3-\varepsilon )$ $(1 / 3 - ε)$ -approximation ratio for any $\varepsilon > 0$ $ε > 0$ under the $\mathcal {CONGEST}$ $CONGEST$ model of computation in $\mathcal {O}\left( \frac{1}{\varepsilon }\log ^2\left( {\Delta /\varepsilon }\right) \log _{1+\sqrt{\varepsilon }}{\left( 1/D\right) } \right) $ $O (\frac{1}{ε}, {log}^{2}, (Δ / ε), {log}_{1 + \sqrt{ε}}, (1 / D))$ -round, where $\Delta $ $Δ$ is the maximum degree of the network graph and D is the minimum service delay in the network. Our approach scales efficiently as it is independent of the network size and adapts to the dynamic nature of IoT environments, incorporating realistic constraints such as communication delays and heterogeneous resource availability. Extensive simulations validate the efficacy of the proposed algorithm across diverse scenarios, including varying workload distributions and network densities. Results demonstrate comparable performance with respect to centralized greedy approaches, while providing substantial benefits in terms of scalability and adaptability.