DOI: https://doi.org/10.1080/17445760.2025.2605530
تاريخ النشر: 2026-02-04
المؤلف: Duc A. Tran وآخرون
الموضوع الرئيسي: إنترنت الأشياء والحوسبة الحافة/الضباب
نظرة عامة
في سياق الحوسبة على حافة الهاتف المحمول، يتضمن نشر الخوادم اتخاذ قرارات حاسمة بشأن مكانة خوادم الحافة وتخصيص خلايا المستخدمين لهذه الخوادم. الأهداف الرئيسية هي تعزيز كفاءة الحوسبة من خلال زيادة الحمل المعالج عند الحافة وتحسين كفاءة الاتصال من خلال تقليل تكاليف الاتصال بين خلايا المستخدمين وخوادمهم المعينة. تتناول هذه الدراسة التعقيدات الناشئة عن الطبيعة غير المعروفة والمتغيرة بمرور الوقت لأحمال المستخدمين وقدرات الخوادم.
يقوم المؤلفون بصياغة مشكلة نشر الخوادم كتحدي تحسين عشوائي ذو مستويين، وهو صعب بشكل ملحوظ ولم يتم استكشافه سابقًا في الأدبيات. لمواجهة ذلك، يقومون بتقريب دالة الهدف باستخدام دوال فرعية، مما يسمح بتطبيق خوارزميات جشعة متقدمة لتعظيم الدوال الفرعية. يتم إثبات فعالية الخوارزمية المقترحة من خلال تقييمات باستخدام بيانات من العالم الحقيقي، مما يكشف عن تحسين في الأداء يصل إلى 55% مقارنة بالطرق البديلة.
مقدمة
تناقش مقدمة الورقة أهمية الحوسبة على حافة الهاتف المحمول (MEC) في تحسين تخصيص الموارد لمشغلي الهاتف المحمول من خلال نشر خوادم الحافة. تحدد مهمتين رئيسيتين تتعلقان بنشر خوادم MEC: وضع الخادم وتخصيص الخادم. تركز مهمة الوضع على اختيار مجموعة فرعية من الخوادم من مجموعة أكبر لتقليل المسافة المتوسطة إلى المستخدمين، على غرار مشكلة موقع المنشأة. على العكس، تتعلق مهمة التخصيص بتحديد التخصيص الأمثل للخوادم المحددة مسبقًا لتعظيم معالجة الحمل دون تجاوز السعة، مما يشبه مشكلة الحقيبة المتعددة. يؤكد المؤلفون على ضرورة معالجة هذه المهام بشكل مشترك لتعزيز الكفاءة في الحوسبة والاتصال والقدرة على التحمل ضد عدم اليقين في الحمل وسعة الخادم.
تقدم الورقة مشكلة نشر الخادم الاستراتيجي تحت عدم اليقين (SDU)، والتي يتم صياغتها كتحدي تحسين عشوائي ذو مستويين. هذه المشكلة معقدة بشكل خاص بسبب طبيعتها الصعبة والحاجة إلى استيعاب الأحمال المتغيرة بمرور الوقت وقدرات الخوادم. يقترح المؤلفون صياغة عشوائية جديدة تدمج معايير الكفاءة الثلاثة ويطورون خوارزمية تقريبية ذات تعقيد زمني متعدد الحدود لحل مشكلة SDU. تُظهر تقييماتهم باستخدام بيانات حركة المرور المحمولة من العالم الحقيقي أن النهج المقترح يتفوق على الطرق البديهية، محققًا تحسينًا متوسطًا قدره 19%، مع مكاسب محتملة تصل إلى 55%. ستتناول الأقسام التالية من الورقة الأعمال ذات الصلة، وصياغة المشكلة الرسمية، ومنهجية الحل، والنتائج العددية.
النتائج
في هذا القسم، يقدم المؤلفون نتائج خوارزمية SDU المقترحة، مقارنة أدائها ضد ثلاث خوارزميات أساسية: RAND وFACILITY وKNAPSACK. تركز المقارنة على الكفاءة التجريبية، المقاسة كمتوسط دالة الهدف \( \Pi \) على مدى 8 أيام، حيث تكون \( \Pi \) عبارة عن تركيبة خطية من كفاءات الحوسبة والاتصال. يستخدم المؤلفون طريقة تطبيع لموازنة الوحدات المختلفة لهذه الأهداف، مع تعديل الصيغة لـ \( \Pi \) بناءً على معاملات متغيرة \( \lambda \) (تم تعيينها إلى 0.2 و0.5 و0.8).
تكشف النتائج أن خوارزمية SDU تتفوق باستمرار على الطرق الأخرى، محققة تحسينات تصل إلى 55.68% مقارنة بالخوارزمية الثانية الأفضل، والتي تختلف اعتمادًا على أولوية الأهداف. من الجدير بالذكر أن كفاءة SDU تظل متفوقة عبر سعات خوادم الحافة المختلفة، مع أقل تحسين يُلاحظ في السيناريوهات ذات السعات المتغيرة بشكل كبير وعدد أقل من الخوادم. بشكل عام، تشير النتائج إلى أن خوارزمية SDU أكثر فعالية بشكل ملحوظ من الخوارزميات المرجعية، مما يُظهر قوتها في التعامل مع عدم اليقين في الأحمال وسعات الخوادم.
المناقشة
تسلط المناقشة الضوء على التعقيدات والتقدم في تخصيص موارد الحوسبة على حافة الهاتف المحمول (MEC)، مع التركيز على وضع الخادم وتخصيص الحمل. تناولت دراسات مختلفة هذه القضايا، مع أهداف تتراوح بين تقليل تأخير الشبكة وتأخير الحوسبة إلى تحسين التكاليف المرتبطة بتثبيت الخادم واستهلاك الطاقة. من الجدير بالذكر أن الأساليب الحالية غالبًا ما تعتمد على طرق تجريبية وتعديلات تدريجية لمراعاة حالات الشبكة الديناميكية، وهو ما يتناقض مع هدف المؤلفين المتمثل في اشتقاق حل استراتيجي طويل الأمد. يقترح المؤلفون صياغة رياضية جديدة تعالج الحمل وسعة الخادم كمتغيرات عشوائية، مما يتيح التقاط عدم اليقين الكامن فيها بشكل أكثر فعالية من النماذج السابقة.
يقدم المؤلفون إطار عمل لتحسين عشوائي ذو مستويين لنشر الخادم، والذي يهدف إلى تعظيم هدف مشترك من كفاءة الحوسبة والاتصال تحت أحمال وسعات غير مؤكدة. يحددون حدودًا لدالة الهدف الخاصة بهم باستخدام دوال فرعية، مما يسمح بتطوير خوارزمية جشعة تضمن حلولًا قريبة من المثلى. تقوم الخوارزمية المقترحة بتحسين تخصيصات الخادم بشكل تكراري لتعزيز الكفاءة، مع معالجة الطبيعة الصعبة للمشكلة من خلال الاستفادة من التقريبات التي تسهل الحسابات ذات الزمن المتعدد الحدود. لا يوفر هذا النهج حلاً قويًا لمشكلة نشر الخادم فحسب، بل يساهم أيضًا في المجال الأوسع للتحسين العشوائي في بيئات MEC.
DOI: https://doi.org/10.1080/17445760.2025.2605530
Publication Date: 2026-02-04
Author(s): Duc A. Tran et al.
Primary Topic: IoT and Edge/Fog Computing
Overview
In the context of mobile edge computing, server deployment involves critical decisions regarding the placement of edge servers and the assignment of user cells to these servers. The primary objectives are to enhance computing efficiency by maximizing the workload processed at the edge and to improve communication efficiency by minimizing the communication costs between user cells and their assigned servers. This research addresses the complexities arising from the unknown and time-varying nature of user workloads and server capacities.
The authors formulate the server deployment problem as a stochastic bilevel optimization challenge, which is notably NP-hard and has not been previously explored in the literature. To tackle this, they approximate the objective function using submodular functions, allowing the application of advanced greedy algorithms for submodular maximization. The effectiveness of the proposed algorithm is demonstrated through evaluations using real-world data, revealing a performance improvement of up to 55% compared to alternative methods.
Introduction
The introduction of the paper discusses the significance of Mobile Edge Computing (MEC) in optimizing resource allocation for mobile operators by deploying edge servers. It delineates two primary tasks involved in MEC server deployment: server placement and server assignment. The placement task focuses on selecting a subset of servers from a larger set to minimize the average distance to users, akin to the Facility Location Problem. Conversely, the assignment task involves determining the optimal allocation of pre-selected servers to maximize workload processing without exceeding capacity, resembling the Multiple Knapsack Problem. The authors emphasize the necessity of jointly addressing these tasks to enhance efficiency in computing, communication, and robustness against uncertainties in workload and server capacity.
The paper introduces the Strategic server Deployment under Uncertainty (SDU) problem, which is framed as a stochastic bilevel optimization challenge. This problem is particularly complex due to its NP-hard nature and the need to accommodate time-varying workloads and server capacities. The authors propose a novel stochastic formulation that integrates the three efficiency criteria and develop an approximate algorithm with polynomial time complexity to solve the SDU problem. Their evaluation using real-world mobile traffic data demonstrates that the proposed approach outperforms intuitive methods, achieving an average improvement of 19%, with potential gains of up to 55%. The subsequent sections of the paper will elaborate on related work, formal problem formulation, solution methodology, and numerical results.
Results
In this section, the authors present the results of their proposed SDU algorithm, comparing its performance against three baseline algorithms: RAND, FACILITY, and KNAPSACK. The comparison focuses on empirical efficiency, measured as the average of the objective function \( \Pi \) over an 8-day period, with \( \Pi \) being a linear combination of computing and communication efficiencies. The authors employ a normalization method to balance the differing units of these objectives, adjusting the formula for \( \Pi \) based on varying coefficients \( \lambda \) (set to 0.2, 0.5, and 0.8).
The findings reveal that the SDU algorithm consistently outperforms the other methods, achieving improvements of up to 55.68% compared to the second-best algorithm, which varies depending on the prioritization of objectives. Notably, the efficiency of SDU remains superior across different edge server capacities, with the least improvement observed in scenarios with highly variable capacities and fewer servers. Overall, the results indicate that the SDU algorithm is significantly more effective than the benchmark algorithms, demonstrating its robustness in handling uncertainties in workloads and server capacities.
Discussion
The discussion highlights the complexities and advancements in Mobile Edge Computing (MEC) resource allocation, focusing on server placement and workload assignment. Various studies have addressed these issues, with objectives ranging from minimizing network delay and computational delay to optimizing costs associated with server installation and energy consumption. Notably, existing approaches often rely on heuristic methods and incremental adjustments to account for dynamic network states, which contrasts with the authors’ goal of deriving a strategic, long-lasting solution. The authors propose a novel mathematical formulation that treats workload and server capacity as stochastic variables, thereby capturing their inherent uncertainties more effectively than previous models.
The authors introduce a stochastic bilevel optimization framework for server deployment, which aims to maximize a combined objective of computing and communication efficiency under uncertain workloads and capacities. They establish bounds for their objective function using submodular functions, allowing for the development of a greedy algorithm that guarantees near-optimal solutions. The proposed algorithm iteratively refines server assignments to enhance efficiency, addressing the NP-hard nature of the problem by leveraging approximations that facilitate polynomial-time computations. This approach not only provides a robust solution to the server deployment problem but also contributes to the broader field of stochastic optimization in MEC environments.