الگوریتم مشارکتی مبتنی بر کیفیت خدمت (QoS) برای مسئلهٔ جریان چندکالایی صحیح

نویسنده: Mehdi Ghatee

منتشرشده در: Computer Communications، جلد 34، شمارهٔ 7، 16 مهٔ 2011، صفحات 835–846.

چکیده:

این مقاله به جریان چندکالایی عددصحیح در یک شبکه می‌پردازد. برای ارتقای کیفیت خدمت (QoS) کانال‌ها، لازم است تأخیر و تراکم کمینه شوند. کاهش تأخیر سرتاسری و مصرف پهنای باند در کانال‌ها به یکدیگر وابسته‌اند و ممکن است در معادلات ریاضی بسیار پیچیده‌ای بیان شوند. برای پرداختن به این مسئله، مدلی از جریان چندکالایی معرفی می‌شود که هدف‌های آن، کمینه‌سازی تأخیر و تراکم در یک مدل واحد است. جریان عبوری از شبکه، مانند بسته‌ها، نیز باید مقادیر عددصحیح بگیرد. مدلی که این مفاهیم را پوشش دهد NP-hard است، درحالی‌که یافتن راهبردهای انتقال به‌صورت بلادرنگ اهمیت بسیار زیادی دارد. برای این منظور، الگوریتمی مشارکتی را توسعه می‌دهیم که شامل برنامه‌ریزی ریاضی سنتی، مانند شمارش مسیرها، و یک الگوریتم فراابتکاری، مانند الگوریتم ژنتیک، است. برای یافتن جواب عددصحیحی که تقاضای گره‌ها را برآورده کند، یک الگوریتم ژنتیک ترکیبی را تعمیم می‌دهیم تا کالاها را به‌صورت عددصحیح به محل‌های موردنیاز تخصیص دهد. در این الگوریتم ترکیبی، از کدگذاری شدنی استفاده می‌کنیم و می‌کوشیم شدنی‌بودن کروموزوم‌ها را در طول تکرارها حفظ کنیم. با بررسی چند شبکهٔ تصادفی نشان می‌دهیم که الگوریتم پیشنهادی در تعداد کمی تکرار، نتایج معقولی تولید می‌کند. همچنین ازآنجاکه این الگوریتم می‌تواند برای دامنهٔ گسترده‌ای از توابع هدف برحسب تأخیر و تراکم به کار رود، می‌توان برای هر کالا چند مسیر با کیفیت خدمت بالا یافت. بر پایهٔ این نتایج، مدل و الگوریتم ارائه‌شده را می‌توان در کاربردهای گوناگون شبکه‌های رایانه‌ای و سامانه‌های حمل‌ونقل برای کاهش تراکم و افزایش استفاده از کانال‌ها به کار گرفت.

کلیدواژه‌ها

تراکم، توزیع ترافیک، مسیریابی، شاخص عملکرد، کنترل