22592

ارائه الگوريتمي جهت كاهش تاخير ذخيره سازي محتوا روي لبه شبكه هاي بي سيم مبتني بر تئوري بازي

كارشناسي ارشد

مهندسي فناوري اطلاعات - تجارت الكترونيك

1399

1399/6/23

دكتر محمد فتحيان

دكتر وصال حكمي

صنايع

با ظهور برنامه¬هاي چندرسانه¬اي جديد، ترافيك تحويل محتوا به كاربران شبكه¬هاي سلولي بي¬سيم با افزايش چشمگيري مواجه شده است. انتقال محتوا از سرويس¬دهنده¬هاي اصلي به كاربران سيّار، پهناي باند زيادي از لينك¬هاي پشتي (بَكهال) شبكه را مصرف مي¬كند و ضمناً مي¬تواند منجر به تجربه تأخير زياد از سوي كاربران گردد. براي مواجهه با اين چالش¬ها، ايده ذخيره¬سازي موقت (كَش) محتواهاي محبوب كاربران در تجهيزات موجود در لبه شبكه (مثل: ايستگاه¬هاي پايه كوچك يا SBSها) مطرح شده است. در واقع، نزديك كردن محتوا به كاربران از طريق جانمايي مؤثر آنها در لبه، باعث كاهش تأخير دريافت محتوا توسط كاربران نيز مي¬گردد. در اين پايان¬نامه، مسأله جانمايي كتابخانه¬اي از فايل¬هاي محتوا بصورت ذخيره شده در SBSها به شكل يك مسأله بهينه¬سازي با هدف كمينه كردن متوسط تأخير دسترسي كاربران سيّار مطرح مي¬شود. در طرح مسأله جانمايي محتوا، پارامترهايي مثل شهرت محتوا، وضعيت كانال بي¬سيم و وضعيت پهناي باند لينك¬هاي پشتي به عنوان ورودي مسأله هستند و محاسبه پيكربندي بهينه جانمايي به مقادير اين پارامترها وابسته است. اين پارامترها، ماهيت تصادفي دارند و مقادير لحظه¬اي آنها طي زمان، يك فرآيند تصادفي را شكل مي¬دهند. برخلاف كارهاي پيشين كه بر مبناي بهينه¬سازي برون¬خط (متكي به اطلاعات لحظه¬اي كامل) يا مبتني بر مدل (متكي به مدل احتمالاتي سيستم) هستند، در اين پايان¬نامه، يك رويكرد فارغ از مدل بر مبناي نظريه بازي و يادگيري چندعاملي اتخاذ مي¬گردد. در رويكرد پيشنهادي، محاسبه سياست جانمايي محتوا به صورت توزيع¬شده به خود SBSها محوّل مي¬شود تا بر اساس اطلاعات محلي به طور خودمختار درباره محتوايي كه بايد ذخيره كنند، تصميم بگيرند. مسأله جانمايي محتوا در اين شرايط با استفاده از فرمول¬بندي "بازي پتانسيل" ميان SBSها مدل¬سازي مي¬شود كه در آن، هر SBS در پي ذخيره¬سازي محتوايي است كه متوسط تأخير كاربرانِ در محدوده پوشش خود را كمينه كند. براي محاسبه تعادل نَش بازي، دو الگوريتم پيشنهاد مي¬شود كه مبتني بر روال¬هاي يادگيري چندعاملي ويژه بازي¬هاي پتانسيل هستند. الگوريتم اول در فضاي تصميم توأم و الگوريتم دوم در فضاي تصميم¬هاي مستقل SBSها، يادگيري تعادل را انجام مي¬دهد و به بهاي اندكي تاخير بيشتر، قادر است پروفايل استراتژي جانمايي SBSها را در سناريوهاي با مقياس بزرگ¬تر و حتي در شرايط عدم مشاهده¬پذيري تصميمات ساير SBSها، به سوي تعادل نَش تقريبي سوق دهد. لذا تمركز اين پايان¬نامه بر روش دوم است. نتايج شبيه سازي نشان مي¬دهند كه روش پيشنهادي كه متكي به نظريه بازي است، قادر است با حاشيه تقريبي حدود % 3/36، به روش¬ الگوريتم متمركز با در اختيار داشتن داده¬هاي دقيق لحظه¬اي، نزديك شود. همچنين، عملكرد روش¬ پيشنهادي در سناريوهاي مختلف بر حسب تغييرات پارامتر آماري شهرت محتوا، تعداد SBSها و نيز جمعيت كاربران سيّار آزمايش شده و مورد تحليل قرار گرفته است.

1399/07/30

A Game-Theoretic Algorithm for Delay Minimization in Content Caching at the Edge of the Wireless Networks

9/14/2021 12:00:00 AM

With the advent of new multimedia applications, content delivery traffic to wireless cellular networks users has increased dramatically. Transferring content from mainstream servers to mobile users consumes a significant part of bandwidth from the network backhaul, which can lead to a long latency experience for the users. To meet these challenges, the idea of temporarily storing (caching) users' popular content on equipment at the edge of the network (such as small base stations or SBSs) has been proposed. In fact, bringing content closer to users by effectively placing them on the edge also reduces the delay in receiving content by them. In this thesis, the issue of locating a library of content files stored in SBSs is raised as an optimization problem with the aim of minimizing the average latency of mobile users. In the content placement problem, parameters such as content popularity, wireless channel, and backhaul status are the inputs to the problem, and the calculation of the optimal location configuration depends on the values of these parameters. These parameters are random in nature and their instantaneous values over time form a random process. Unlike previous works based on offline optimization (based on complete instantaneous information) or model-based (based on the probabilistic model of the system), in this thesis, a model-based approach based on game theory and multi-agent learning is adopted. In the proposed approach, the calculation of the content placement policy is one of the the SBSs duties to decide automatically, based on local information about the content they should store. The issue of content placement in this context is modeled by using the "potential game" formalism between SBSs, in which each SBS seeks to store content that minimizes the average latency of users within its coverage area. To calculate the Nash equilibrium, two algorithms are proposed that are based on multi-agent learning procedures for potential games. The first algorithm in multi-agent joint action learning space and the second algorithm in multi-agent independent action learning space of SBSs by equilibrium learning, are able to bring the SBS content placement strategy profile to Nash equilibrium, especially in circumstances of larger-scale scenarios and even in the absence of observability of other SBS decisions. Therefore, the focus of this thesis is on the second method. The simulation results show that the proposed method, which is based on game theory, is able to approach the result of centralized algorithm with an approximate margin of about 36.3% with accurate instantaneous data. Also, the performance of the proposed method in different scenarios has been tested and analyzed in terms of changes in the statistical parameter of content popularity, number of SBS, and mobile user population.