Skip to main content
SUPERVISOR
عیسی نخعی (استاد مشاور) سیدجمال الدین گلستانی (استاد راهنما)
 
STUDENT
Naghmeh Sadat Moayedian
نغمه السادات مؤیدیان

FACULTY - DEPARTMENT

دانشکده مهندسی برق و کامپیوتر
DEGREE
Doctor of Philosophy (PhD)
YEAR
1380

TITLE

A Unified Theory of Scheduling, Routing, Flow Control and ‍Channel Assignment in Wireless Networks
In wireless networks, resource allocation includes scheduling, routing, flow control, channel assignment and power control. These problems are fundamentally interrelated and any scheme used to address one of them, will impact the others. Therefore, using separate algorithms for each part may cause inefficiency or inconsistency. A joint approach to these issues can cause either higher throughput or less usage of resources. In this dissertation , we attain a joint formulation of scheduling, routing, flow control and channel assignment. Our approach is novel in that it integrates optimal scheduling with a modified version of distributed minimum delay routing. We propose a convex optimization formulation and solve it through two different methods. Based on these methods, we develop a heuristic algorithm for the solution which is distributed as far as its routing and flow control is concerned. Performance of proposed algorithm is better than the previous algorithms in many ways. We demonstrate by analysis and simulation, that the algorithm achieves fairness and/or priorities among users in accordance with pre-assigned user parameters. In sharp contrast to alternative algorithms that perform scheduling and packet routing based on per-session queue differential between adjacent nodes, our algorithm uses a complete multi-hop view of network conditions for packet routing. Numerical and simulation studies show that our algorithm, when compared to a rival algorithm, essentially achieves the same throughput, is somewhat better in terms of fairness/priority properties, and is far superior with respect to queue sizes, end-to-end delays, packet misordering, energy consumption and convergence speed. In addition, simulation results do not report any reduction in the throughput. Finally, we extend our formulation to also include power control and come up with an integrated algorithm for the combined problem. Key Words: Routing, Flow Control, Scheduling, Channel Assignment, Wireless Networks, Convex Optimization.
در شبکه‌های بی‌سیم، تخصیص مناسب امکانات مستلزم طراحی الگوریتم‌های مسیریابی، کنترل نرخ ورودی، زمان‌بندی، تخصیص کانال و کنترل توان می‌باشد. اگر این الگوریتم‌ها هر یک به صورت جداگانه طراحی شوند و سپس در شبکه مورد استفاده قرار گیرند، تخصیص امکانات به صورت غیر بهینه خواهد بود و علاوه بر آن، چندباره کاریهای غیر ضروری در پیاده‌سازی این الگوریتم‌ها رخ می‌دهد. حال اگر الگوریتم‌های فوق بطور مشترک با هم طراحی شوند، می‌توان هم گذردهی بالاتری بدست آورد و هم اختصاص امکانات را بهتر انجام داد. نکته دیگری که توجه به آن در حل مسئله تخصیص امکانات در شبکه‌های بی‌سیم ضروری است، امکان پیاده‌سازی توزیع شده الگوریتم‌های تخصیص امکانات است. اجرای متمرکز یک الگوریتم نیاز به مبادله پیام‌های کنترلی و ارتباطی زیادی دارد که در شبکه‌های بی‌سیم با توجه به کمبود امکانات، چندان مناسب نخواهد بود. طی 30 سال گذشته تلاشهای تحقیقاتی متعددی در یافتن الگوریتم‌های توزیع شده برای مسیریابی، کنترل نرخ ورودی، زمان‌بندی و تخصیص کانال و نیز در جهت ترکیب این الگوریتم‌ها صورت گرفته است. این تحقیقات به روشن شدن بسیاری از پیچیدگی‌ها و ظرایف بحث کمک نموده‌اند. در عین حال هنوز دشواری‌های متعددی در یکپارچه سازی کامل این الگوریتم‌ها و اجرای غیر متمرکز و با قید پیچیدگی قابل قبول برای آنها وجود دارد. در این رساله ما سعی کرده‌ایم با بهره‌گیری از تحقیقات قبلی و توجه به نقاط ضعف و قوت هر یک از آنها، نگاه جدیدی به مسئله تخصیص امکانات در شبکه‌های بی‌سیم داشته باشیم. ما مسائل زمان‌بندی، مسیریابی، کنترل نرخ ورودی و تخصیص کانال را در شبکه‌های بی‌سیم بطور توأمان به صورت یک فرمول‌بندی واحد بهینه‌سازی محدب مورد بررسی قرار می‌دهیم. این روش به دلیل ترکیب شدن تخصیص کانال، زمان‌بندی بهینه و کنترل نرخ ورودی با یک شکل اصلاح شده از الگوریتم مسیریابی با کمترین تأخیر که پیشتر در شبکه‌های سیمی مطرح بوده است، بدیع است. ما با دو روش مختلف بهینه‌سازی به حل این مسئله پرداخته‌ایم و در ادامه یک الگوریتم ابتکاری برای پیاده‌سازی آن ارائه کرده‌ایم. بدین ترتیب تمایز آشکاری بین عملکرد الگوریتم ارائه شده با الگوریتم‌های مختلف قبلی بدست آمده است. ما با تحلیل ریاضی و همچنین شبیه‌سازی نشان داده‌ایم که الگوریتم توزیع‌شده بدست آمده می‌تواند با تنظیم برخی پارامترهای از پیش تعیین شده، عدالت و اولویت‌دهی را بین کاربران مختلف شبکه ایجاد کند. در مقایسه با الگوریتم‌های مطرح دیگری که زمان‌بندی و مسیریابی را بر اساس تفاضل طول صف هر محاوره در گره‌های همسایه انجام می‌دهند، الگوریتم ما با بهره‌گیری از الگوی ترافیکی در کل طول مسیرهای مختلف بین مبدأ و مقصد، اقدام به انتخاب بهترین مسیر برای هر بسته می‌کند. درنتیجه آن طور که شبیه‌سازی‌ها نشان می‌دهند، الگوریتم ما در موارد زیادی به مراتب بهتر از الگوریتم‌های رقیب عمل می‌کند، از جمله در زمینه تأخیر بسته‌ها، تعداد بسته‌های گم شده، تعداد گام‌‌های طی شده تا مقصد، جابجایی ترتیب بسته‌ها، میزان مصرف انرژی در شبکه و بالاخره سرعت همگرایی الگوریتم. بعلاوه از نظر ناحیه ظرفیت، نتایج شبیه‌سازی کاهشی را در الگوریتم ارائه شده گزارش نمی‌کنند. کلمات کلیدی: مسیریابی، کنترل نرخ ورودی، زمان‌بندی، تخصیص کانال، شبکه‌های بی‌سیم، بهینه‌سازی محدب.

ارتقاء امنیت وب با وف بومی