عنوان پایان‌نامه
بهینه سازی استراتژدی در بازیهای دستیابی چند گانه در شبکه های کامپیوتری با استفاده از روشهای یادگیری تقویتی
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 43..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 59762
- تاریخ دفاع
- ۲۳ شهریور ۱۳۹۲
- دانشجو
- حسین بیات یگانه
- استاد راهنما
- علی معینی, حامد کبریائی
- چکیده
- شبکههای کامپیوتری بی‌سیم در دنیای امروز اهمیت بسزایی دارند. همانطور که به نظر می‌آید به علت محدود بودن ظرفیت وسایل ارتباطی در این شبکه‌ها، رقابتی بین انواع دستگاه‌های فرستنده، به وجود خواهد آمد. به طور مثال، یکی از رقابت‌ها، بازی دستیابی ِچندگانه در شبکههای کامپیوتری بی‌سیم است. که یکی از مهم‌ترین پرتکل‌های آن، پرتکل CSMA-p-Persistent است. که این پرتکل موضوع بحث این تحقیق است. در این تحقیق سعی شده است که بازیکنان با روشهای یادگیری تقویتی طراحی گردند که، قصد بهینه کردن استراتژی خود را در این رقابت‌ها دارند. این تلاش در مقالاتی، ولی در شرایط یادگیری تک حالته انجام شده است. نکته امتیاز این تحقیق این است که سعی کرده بازیکن، وضعیت خود را بررسی کند تا بسته به وضعیت خود اقدام به ارسال کند، یعنی یادگیری چند حالته. حال این مسئله پیش می‌آید که وقتی بازیکن اطلاعات دقیقی از محیط و همچنین از حالت دیگر بازیکنان ندارد، اکنون چه چیزی را به عنوان حالت خویش در نظر بگیرد، تا بهترین پیامد را نسبت به بازیکنان دیگر به دست بیاورد؟ در این تحقیق سعی بر آن شده است که مهم‌ترین و بهترین متغیرها در تصمیم‌گیری بازیکن مشخص شود و به بهترین نحو در حالت بازیکن اِعمال شود. بدین صورت که هم تعداد متغیرهای مناسب در تصمیم‌گیری اعمال گردد و هم تعداد حالات که با افزایش اِعمال متغیرهای مختلف افزایش می‌یابد، در شرایط قابل قبولی باشد. که تضمینی برای همگرایی یادگیری داشته باشد. بدین منظور بازیکنان مختلفی طراحی شد. هر کدام از این بازیکنان بر اساس متغیرهایی که در تصمیم‌گیری اعمال می‌کردند شخصیتی داشتند، که تعدادی از آن‌ها بازیکنان محتاط و کم خطر برای دیگران و تعدادی به نوعی بازیکن مهاجم بودند. بازیکن صدوده حالته و بازیکن بیست‌ودو حالته جدید، با ترکیب متغیرهای عامل در تصمیم‌گیریِ بازیکنان مهاجم و محتاط، شخصیتی بینابین دارند. که در این بین بازیکن بیست‌ودو حالته جدید بهترین نوع ترکیب را دارد. چون هم تعداد حالات متعادلی برای همگرایی یادگیری دارد و هم متغیرهای مناسبی را از ترکیب وضعیت خط و گذشته خود به بهترین نحو در تصمیم‌گیری اعمال می‌کند. نکته مهم این که، این بازیکن علاوه بر این که پیامدی بهتر از تمام بازیکنان طراحی شده دارد، برخلاف بازیکنان مهاجم، پیامد دیگر بازیکنان را کاهش نمی‌دهد. که می‌توان گفت بهترین بازیکن هم از لحاظ عاقل بودن و هم کم ضرر بودن برای دیگر بازیکنان است. مسئله مهم دیگر در این تحقیق نامحدود بودن تعداد استراتژی‌های موجود در بازه احتمال ارسال بین 0 و 1 بود. برای حل این مشکل روش‌هایی موسوم به گسترش عمل آورده شده که سعی بر مرتفع کردن این مسئله کرده است.
- Abstract
- We study Multiple Access Game in Wireless Network which allows multiple nodes to share a set of available channels for data transmission. The nodes can either compete or cooperate with each other to access the channel(s) so that either an individual or a group objective can be achieved. Game Theory, which is a mathematical tool developed to understand the interaction among rational entities, can be applied to model and to analyze individual or group behavior of nodes for multiple access in wireless networks. Game theory also enables us to model the selfish/malicious behavior of nodes, and subsequently design the punishment or defense mechanisms for robust multiple access in wireless networks. In addition, game models can provide distributed solutions to the multiple access problems, which are based on solid theoretical foundations. In this article we designed new algorithm based on reinforcement learning which all the players optimize their strategies. This approach was studied however they focus on single state learning. Most notably, we designed new algorithm based on multiple state learning which each players change his strategy based on channel and his currently situation. In this algorithm we studied some parameters of player’s history which have influence on their decision and we attempt to select and use these parameters in their strategies so that the number of them and the new states, was created, will be efficient. We defined new players belonged one of these groups, the first group has aggressive attribute and the second has conservative attitude and the final group has combination of past two player’s attitude, which select some attitude from past aggressive and conservative players. Our new players have logical and efficient states to converge our learning to the best action. Contrasts to previous aggressive players, the third groups’ players don’t have negative influence on other players. Also we solved infinity of our player strategies by designed new algorithms named Extension Action.
