عنوان پایان‌نامه
طراحی کار آمد کدهای شبکه
- رشته تحصیلی
- مهندسی برق-مخابرات-سیستم
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 35348
- تاریخ دفاع
- ۳۱ مرداد ۱۳۸۶
- دانشجو
- محمد جباری حق
- چکیده
- در مسأله کدینگ خطی شبکه مورد نظر در این پایان‌نامه، شبکه‌ها به صورت گراف‌های جهت‌دار بدون حلقه مدل می‌شوند و از گره‌ها (مشتمل بر گرههای منبع، گرههای میانی و گرههای مقصد) و لینک‌های بین گره‌ها تشکیل می‌شوند. این لینک‌ها بدون خطا و با ظرفیت معین فرض می‌شوند. کدینگ شبکه در کاربردهای چندپخشی و تک‌پخشی که مورد نظر این پایان‌نامه است، مساله تخصیص کدهای مناسب به گرههای میانی است به قسمی که حداکثر نرخ انتقال اطلاعات از گرههای منبع به گرههای مقصد تامین شود. سمبل‌های اطلاعاتی که منتقل می‌شوند عناصری از یک میدان متناهی هستند که اندازه آن با توجه به تعداد گرههای مقصد تعیین می‌گردد. در شرایط مفروض فوق، ظرفیت چندپخشی شبکه با استفاده از قضیه حداکثر جریان - حداقل برش محاسبه می‌شود و بیانگر حداکثر تعداد سمبل‌های قابل انتقال در واحد زمان به گرههای مقصد است. ثابت شده است این ظرفیت با استفاده از کدینگ شبکه و به خصوص کدینگ شبکه خطی قابل دستیابی است. در این پایان‌نامه روش جدید و مؤثری برای کدینگ شبکه با استفاده از روش‌های یادگیری تقویتی ارایه شده است. این روش «کدینگ شبکه بر مبنای یادگیری تقویتی» نامگذاری شده است. در بخش‌هایی از الگوریتم مفاهیم نظریه بازار نیز مورد استفاده قرار می‌گیرد. روش یادگیری استفاده شده باعث می‌شود یک نوع جستجوی تصادفی هوشمند توسط الگوریتم انجام شود. به‌علاوه نشان داده می‌شود که الگوریتم پیشنهادی غیرمتمرکز است و از پیچیدگی چندجمله‌ای برخوردار است. روش کدینگ شبکه بر مبنای یادگیری تقویتی در مقایسه با دیگر روش‌های کدینگ شبکه تصادفی، کدهای شبکه را سریع‌تر ولی با همان درجه پیچیدگی می‌سازد و به‌خصوص در شبکه‌های بزرگ و اندازه میدان‌های کوچک برتری محسوسی بر روش‌های رقیب دارد. در ضمن نشان داده می‌شود که الگورتیم پیشنهادی قادر به بازسازی کدهای شبکه بعد از رخداد خرابی کانال است و این بازسازی پیچیدگی کمتری از قسمت طراحی داشته و نیازی به اطلاع از الگوهای خرابی ندارد. انعطاف‌پذیری الگوریتم برای ایجاد یک تعادل بین پیچیدگی الگوریتم و تعداد گرههای کدکننده‌ی شبکه بررسی می‌شود و در نهایت کاربرد الگوریتم در شبکه‌های تک‌پخشی چندگانه توضیح داده می‌شود.
- Abstract
- This thesis deals with the problem of network coding, in an acyclic directed graph. Such a graph, consists of a set of nodes that includes the source nodes, the intermediate nodes and the sink nodes; and a set of directed error-free edges. The task is to multi-cast a common information from the source nodes to the sink nodes through intermediate nodes. The sources can be independent or linearly correlated. The transmitting symbols are the elements of a finite element field, which is selected with respect to the number of network sinks. The network capacity for multicast is given by the Max-flow Min-cut Theorem and indicates the maximum number of simultaneously transmittable symbols from the source nodes to the sink nodes. It is shown that the network capacity given by the Max-flow Min-Cut theorem is achievable with network coding. In this thesis, we introduce a new efficient method based on reinforcement learning to construct linear network codes, referred to as the Reinforcement Learning Network Code (RLNC) design. We will make use of the market theory concepts in the learning section of the algorithm. The learning approach results in a smart random search and we demonstrate that the proposed algorithm is decentralized and polynomial time complex. The RLNC algorithm constructs network codes faster than the other random methods with the same complexity order, especially in large networks with small field sizes. It is also shown that the algorithm can re-construct the network code in the presence of link failures with a small complexity and without previously being aware of error patterns even in very large networks. Further extension to achieve the objective of decreasing the number of encoding nodes in a network and use of the algorithm in non-multicast networks are discussed.
