31005

طراحي الگوريتم هاي مسيريابي بهينه در شبكه هاي مخابراتي با درنظر گرفتن محدوديت هاي لايه فيزيكي

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

مهندسي برق - گرايش مخابرات - سيستم

1399

1402/12/20

دكتر شاهرخ فرهمند

ندارم

مهندسي برق

امروزه ترافيك انتقال داده شده در شبكه هاي مخابرات بي سيم رو به گسترش است و افزايش تعداد كاربردهاي اين شبكه ها و نياز مبرم به انتقال حجم زياد داده در اين شبكه ها، اهميت زيادي به طراحي نزديك به بهينه آن ها بخشيده است و در نتيجه طراحي بهينه الگوريتم هاي مسيريابي به يكي از دغدغه هاي اصلي تبديل شده است. در طراحي الگوريتم هاي مسيريابي چالش هاي بسياري وجود دارد كه يكي از اين چالش ها، لايه فيزيكي و محدوديت هاي آن مي باشد. از مهم ترين محدوديت هاي لايه فيزيكي در شبكه هاي مخابراتي بي سيم مي توان به اثر محو شدگي اشاره كرد كه باعث مي شود نسبت سيگنال به نويز تغيير كند و در نتيجه هزينه لينك هاي شبكه مخابراتي را تحت تاثير خود قرار مي دهد. در مواردي كه اطلاعات آماري اثر محو شدگي در دسترس باشد، الگوريتم هاي بهينه مسيريابي مانند بلمن فورد و بلمن فورد غيرسنكرون كه بر اساس بهينه سازي پويا طراحي شده اند، اين اطلاعات را در نظر نمي گيرند و الگوريتم هاي مبتني بر يادگيري تقويتي نيز كه از اين اطلاعات استفاده مي كنند، نياز به آزمون و خطاي زيادي تا رسيدن به همگرايي و جواب بهينه دارند. يكي ديگر از محدوديت هاي لايه فيزيكي در شبكه هاي مخابراتي بي سيم اثر تداخل است كه بر اثر آن ممكن است علاوه بر تغيير بهره كانال مخابراتي، نسبت سيگنال به تداخل هم تغيير كند و كيفيت لينك هاي شبكه را تحت تاثير خود قرار دهد. چالش ديگر موجود در طراحي الگوريتم هاي مسيريابي، تغييرات توپولوژي و الگوهاي ترافيكي شبكه است. در شبكه هايي كه الگوهاي ترافيكي نامنظم بوده و توپولوژي آن ها دائما در حال تغيير است، مسيريابي تطبيقي ضروري مي باشد. تطبيق ممكن است در شبكه هاي سنتي به دليل خرابي پيوندها يا گره ها ضروري باشد. همچنين در شبكه‌هاي اقتضايي متحرك، مسيرياب ها مي‌توانند به‌طور تصادفي حركت كنند، بنابراين توپولوژي شبكه دائم به صورت غيرقابل پيش‌بيني تغيير مي كنند. در اين پايان نامه تمركز بر روي طراحي الگوريتم مسيريابي در لايه شبكه است كه محدوديت هاي لايه فيزيكي شبكه هاي مخابراتي بي سيم نيز در طراحي آن در نظر گرفته شده است و فرض مي شود لايه فيزيكي به صورت جداگانه طراحي و ساخته شده است. پس در حالي كه نياز به طراحي لايه فيزيكي نيست، محدويت هاي لايه فيزيكي در مسيريابي، در نظر گرفته شده است. الگوريتم طراحي شده در اين پايان نامه علاوه بر ظرفيت لينك هاي شبكه، كيفيت لايه فيزيكي آن ها از نظر ميزان نرخ خطاي بيت را نيز در نظر مي گيرد. پس از تعيين مدل براي گراف شبكه، الگوريتم بهينه سازي پوياي تصادفي جهت حل بهينه مساله مسيريابي با نرخ خطاي بيت هاي متفاوت استفاده شده است. نتايج شبيه سازي نشان مي دهد الگوريتم مسيريابي پيشنهادي بهتر از الگوريتم بلمن فورد عمل مي كند و اگر قابليت اطمينان همه لينك ها يك باشد كه متناظر با نرخ خطاي بيت صفر يا لينك هاي بدون خطا مي باشد، عملكردي برابر بلمن فورد خواهد داشت.

1403/04/13

Optimal Routing in Telecommunication Networks Subject to Physical Layer Constraints

3/10/2025 12:00:00 AM

Nowadays, the transmitted traffic in wireless communication networks is expanding dramatically. At the same time, the number of applications that utilize these networks are skyrocketing. Both of these observations point to the great importance of near-optimal design of these networks. Subsequently, the optimum design of routing algorithms has been a major concern. One of the challenges in designing satisfactory network layer routing protocols is to incorporate the physical layer and its limitations in the design. One of the most important limitations concerns with small-scale fading which causes the instantaneous signal-to-noise ratio to fluctuate and thus negatively affects the cost of wireless link. When the small-scale fading statistics is available, current routing algorithms, such as Bellman-Ford and Dijkstra, can not utilize this information. On the other hand, reinforcement learning-based algorithms assume that this information is not available and learn it from trial and error leading to excessive delays until convergence is reached. Other physical layer effects which should be incorporated in the design of routing algorithms are interference, topology changes, and varying network traffic patterns. Under these circumstances adaptive routing becomes a necessity. In this thesis, we focus on the optimal design of network layer routing protocols, while incorporating these limitations of the physical layer. We do not pursue a cross-layer design as the layering approach enables easy reconfiguration and module updates. However, we take the physical layer constraints into account. To be more specific, in addition to the capacity of network links, the quality of the link in terms of bit error rate (BER) is also considered in our design. We apply a stochastic dynamic programming algorithm to solve the routing problem with a varying BER per link. The numerical results corroborate the better performance of the proposed routing algorithm compared to the Bellman-Ford in general. Furthermore, it is revealed that if all links reliabilities are set to one, which corresponds to a zero BER for all links, our proposed approach will boil down to the traditional Bellman-Ford.

الگوريتم مسيريابي بهينه , شبكه هاي مخابراتي بي سيم , محدوديت لايه فيزيكي

Optimal routing algorithm , wireless telecommunication networks , physical layer constraints

Mahdi Nasiri

Dr. Shahrokh Farahmand