| خانم زهرا رشیدی دانشجوی دکترای آقای دکتر وصال حکمی مورخ ۱۴۰۲/۰۸/۲۰ ساعت ۱۷:۰۰ از رساله دکتری خود با عنوان "بهینهسازی جانمایی محتوا در شبکه‌های سلولی کوچکِ مجهّز به کش با اطلاعات ناکامل" دفاع خواهند نمود. |
ارائه دهنده:
زهرا رشیدی
اساتید راهنما:
دکتر وصال حکمی
هیات داوران:
دکتر اکبری، دکتر مزینی،
دکتر خونساری (دانشگاه تهران)، دکتر صفایی (دانشگاه شهید بهشتی)
زمان : ۲۰ آبان ماه ۱۴۰۲
ساعت ۱۷:۰۰
چکیده پایان نامه :
با ﻇﻬﻮر و گسترش ﺑﺮﻧﺎﻣﻪﻫﺎی کاربردی و ﭼﻨﺪرﺳﺎﻧﻪای ﺟﺪﻳﺪ، یکی از چالشهای عمده شبکه های سلولی، رشد فزاینده ﺗﺮاﻓﻴﻚ تحویل محتوا به دستگاه های سیّار است که میتواند منجر به افزایش تأخیر دسترسی به محتوا شود. از ﻃﺮف دﻳﮕﺮ، اﻧﺘﻘﺎل محتوا از ﺳِﺮورﻫﺎی مبدأ ﺑﻪ ﻛﺎرﺑﺮان، ﭘﻬﻨﺎی ﺑﺎﻧﺪ زیادی را از پیوندهای پُشتی شبکه اِشغال ﻣﻰﻛﻨﺪ. ﺑﺮای ﻣﻘﺎﺑﻠﻪ ﺑﺎ اﻳﻦ ﭼﺎﻟﺶﻫﺎ، ایده ذﺧﻴﺮهﺳﺎزی (کَش) ﻣﺤﺘﻮا در ایستگاههای پایه کوچک (SBSها) مطرح شده است. در این رساله، مسئله جانمایی محتواها در کَش SBSها به شکل یک مسئله بهینه سازی با هدف کمینه کردن متوسط تأخیر دسترسی کاربران سیّار به محتوا فرمول بندی میشود. برخلاف رویکردهای غالب در کارهای پیشین که بر مبنای بهینهسازی برون خط یا مبتنی بر مدل هستند، در این رساله، رویکرد مبتنی بر یادگیری ماشین اتخاذ شده است. در این رویکرد، مسئله جانمایی محتوا به هر دو صورت متمرکز و توزیع شده، تحت اطلاعات ناکامل فرمول بندی شده و سیاست بهینه جانمایی محاسبه میشود. در فرمول‌بندی متمرکز، مسئله جانمایی بر اساس فُرمالیسم فرآیند تصمیم مارکُف مدل‌سازی میگردد که در آن، محبوبیت لحظهای محتوا، پروفایل CSI کاربران و نیز ظرفیت لحظهای پیوندهای پُشتی SBSها به عنوان بردار وضعیت لحظهای سیستم، به صورت پویا و تصادفی با زمان تغییر میکند. با توجه به بُعدیت بزرگ فضای وضعیت سیستم، سیاست بهینه جانمایی با استفاده از تقریب تابع ارزش و بر مبنای تکنیکهای یادگیری تقویتی عمیق محاسبه میشود. در فرمول بندی توزیع شده، محاسبه سیاست جانمایی محتوا به خود SBSها محوّل میشود تا بر اساس اطلاعات محلی به طور خودمختار درباره محتوایی که باید کَش کنند، تصمیم بگیرند. در این فرمول بندی، مسئله جانمایی با استفاده از فُرمالیسم بازی پتانسیل میان SBSها مدل میشود که در آن، هر SBS در پی ذخیره سازی محتوایی است که متوسط تأخیر کاربرانِ در محدوده پوشش آن را کمینه کند. برای محاسبه تعادل نَش بازی، الگوریتمی مبتنی بر روال یادگیری چندعاملی ویژه بازیهای پتانسیل ارائه شده که قادر است تحت اطلاعات ناکامل از پارامترهای توابع هزینه SBSها، تصمیمات جانمایی آنها را به سوی تعادل سوق دهد. تحت اطلاعات ناکامل، SBSها با پیچیدگی دیگری نیز برای کَش محتوا مواجه هستند و آن، عدم قطعیت در مورد ماهیت یا ترکیب جمعیتی کاربران سیّار میباشد. در واقع، ممکن است کسری از کاربران تحت عنوان کاربران متخاصم با ارسال درخواست برای محتواهایی که در SBS پوشش دهنده آنها کَش نشده اند، موجب بالا رفتن نسبت عدم موفقیت کَش و ازدحام در پیوندهای پُشتی شوند. فرمول بندی این مسئله بر اساس فُرمالیسم یک بازی سلسله مراتبی دو-سطحی (اِستَکِلبِرگ) ارائه شده که علاوه بر یک بازی که در سطح بالا میان خود SBSها برای تعیین جانمایی محتوا در جریان است، یک بازی در سطح دوم میان گروه SBSها در مواجهه با کاربران متخاصم نیز انجام میشود. در این حالت، محاسبه تعادل اِستَکِلبِرگ از طریق الگوریتم پویایی بهترین پاسخ انجام میشود و در صورت عدم پیروی درخواست‌های این کاربران از یک الگوی استراتژیک، مسئله با استفاده از روش قمار چند-بازویی تخاصمی-ترکیبیاتی مدل شده و یک الگوریتم یادگیری برخط با معیار پشیمانی ضعیف جهت ارزیابی آن ارائه میشود.
Abstract:
With the exponential proliferation of mobile users (MUs) and the emergence of many new applications and multimedia services, the content delivery traffic over cellular networks is explosively growing. Such rapid growth increases the content downloading latency as well as the congestion in the backhaul links. To deal with these challenges, caching popular files at the small base stations (SBSs) has proved to be an effective strategy to reduce the content delivery delay and to alleviate the backhaul congestion. In this dissertation, the SBS content placement problem is formulated as an optimization problem with the objective of minimizing the average content delivery latency. Unlike mainstream research, which is mostly based on offline or model-based optimization, we adopt the machine-learning-based approach. The content placement problem with incomplete information is formulated in both centralized and distributed fashions. In the centralized formulation, the placement problem is modeled based on the formalism of Markov decision process (MDP) in which the time-varying system state captures the instantaneous content popularity, the CSI profile of the MUs, and the instantaneous capacity of the SBS backhaul links. Due to the large dimensionality of the system state space, the optimal placement policy will be determined using the approximation of the value function by deep reinforcement learning techniques. In the distributed formulation, the computation of the content placement policy is delegated to the SBSs themselves. To this end, the placement problem is modeled as a potential game among SBSs in which the objective of each SBS is to minimize the average delay of the MUs within its coverage range. In order to compute the Nash equilibrium of the game, we present two algorithms based on multi-agent learning techniques for potential games. Both algorithms can shape the placement strategies of the SBSs to induce a global equilibrium behavior under the incomplete information of the cost function parameters. The first algorithm learns the equilibrium in the joint action space of the SBSs, and the second one operates in the independent action space. Under incomplete information, there is yet another complexity imposed on caching, which concerns the behavioral model of the MUs in fetching contents. In open access cellular communications, the SBSs may be uncertain about whether all MUs whiten their coverage behave legitimately. In fact, some MUs may send requests for contents not cached in their associated SBSs, aiming at increasing the cache miss ratio, and at aggravating the congestion in backhaul links. More precisely, the probability distribution of such requests does not necessarily follow the standard content popularity distribution. When the adversary users’ objective is maximizing the delay in backhaul links, we formulate the problem as a two-level hierarchical game (Steckelberg). In fact, in addition to the game played at the top level by the SBSs to place the appropriate content into their caches, there is a second game played between the SBSs as a group and the adversary users at the bottom level. In this case, the Stackelberg equilibrium is computed through the best response dynamics algorithm. However, when the requests of the adversary users do not follow a strategic pattern, the problem is modeled using the adversarial-combinatorial multi-armed bandit problem and an online learning algorithm is presented with a weak regret criterion to evaluate it.
|
