بخشی از مقاله
چکیده -
تخصیص توان در شبکههای بیسیم چند زیر حاملی یکی از چالشهای اساسی است که برای رفع آن روشهای متعددی معرفی شده است. در این مقاله دو الگوریتم ارائه شده که عملکرد آنها به گونهایست که با در نظر گرفتن کارایی کاربران به آنها منابع اختصاص میدهند. به این ترتیب به کاربرانی که شرایط مناسبی ندارند و اختصاص طیف به آنها باعث کاهش کارایی سیستم و عدم استفاده بهینه از منابع موجود میشود، توان کمتری نسبت به کاربرانی که دارای شرایط خوب هستند، تخصیص مییابد. همچنین سعی میشود به کاربران متناسب با ضرایب نیازمندی به نرخ داده، پهنای باند اختصاص یابد. از مزیتهای این دو الگوریتم نسبت به دیگر الگوریتمها میتوان به بازدهی طیفی بهتر و کاهش پیچیدگیهای محاسباتی آن نسبت به الگوریتمهای قبلی اشاره کرد.
-1 مقدمه
توزیع و تخصیص بهینه منابع رادیویی همواره یکی از اساسیترین مشکلات بر سر راه طراحی سیستمهای بیسیم بوده است. تخصیص بهینه منابع در یک شبکه عبارت است از تخصیص بهینه توان ، نرخ داده و زیر حاملها به کاربران با در نظر گرفتن قیود م حدود یت توان، حداقل نرخ داده مورد انت ظار کاربران. با توجه به شرایط کانال مخابراتی و رعایت انصاف در توزیع منابع الگوریتمهای پویای تخصیص منابع به دو دسته کلی متمرکز و غیرمتمرکز تق سیم می شوند
روشهای غیر متمرکز علاوه بر داشتن مزایایی نظیر کاهش بار محاسباتی درایستگاه مرکزی BS، معایبی نظیر اشغال قسمتی از طیف و منابع به علت وجود سربار ارتباطی بین ایستگاه مرکزی و کاربران را ندارد. با این وجود الگوریتم های متمرکز به علت سادگی پیاده سازی و مدیریت بهتر کاربران مورد توجه می باشند.
در این مقاله ضمن بررسی تخصیص توان متمرکز در شبکههای بیسیم و بررسی محدودیتهای آن، یک الگوریتم ساده با کارایی نسبتاً بالا در مقایسه با سایر روشها ارائه میشود. این الگوریتم به گونه ای ست که شانس د ستیابی کاربران دارای شرایط منا سب را به زیر حاملها را افزایش داده و ضمن افزایش نرخ بیت کلی شبکه ، یک تخصیص منابع عادلانه در شبکه را ارائه میدهد.
در ادامه این مقاله در بخش دوم چند الگوریتم تخصیص توان در شبکههای بی سیم چند زیر حاملی معرفی می شود. بخش سوم الگوریتمی با پیچیدگی محا سبتی کم و پا سخ قابلقبول پی شنهاد میگردد. در بخش چهارم شبیهسازی و مقایسه روشهای مرسوم و روش پیشنهادی صورت گرفته است. بخش پنجم به نتیجهگیری اختصاص دارد.
-2 مروری بر الگوریتمهای تخصیص توان
طراحی و بهینهسازی سیستمهای ارتباطی چند زیرحامله ، اغلب شامل بیشینه سازی مجموع نرخ اطلاعات کاربران مشروط به قیودی روی منابع سیستم است . این منابع عبارتاند از توان ، زیر حامل و نرخ دادهها. متأسفانه در سیستمهای چند کاربره هم تابع هدف و هم قیود مسئله غیر محدب هستند و بنابراین حل عددی م سئله بهینه سازی بسیار پیچیده خواهد بود
در این سیستمها باید زیر حاملهای در دسترس را به خوبی و عادلانه بین کاربران تقسیم کرد [4] و همچنین توان مناسب برای هر کاربر روی هر زیر حامل را به گونهای اختصاص داد که محدودیت توان کل برقرار شود. بنابراین مسئله عملاً شامل دو قسمت تخصیص زیر حامل مناسب به کاربران و تخصیص توان به شرط محدود بودن توان کل در دسترس است .
جدول :1 مقایسه پیچیدگی محاسباتی الگوریتمها مختلف
تاکنون الگوریتمهای فراوانی برای حل این مسئله ارائه شده است که هر کدام مزایا و معایبی دارند. از روشهای موجود میتوان به الگوریتمSRA1 ا شاره کرد 6 که به صورت متمرکزعمل میکند و کلیه محاسبات و تصمیمگیریهای آن در یک مرکز اصلیSMC2 انجام می شود. در این الگوریتم بدون در نظر گرفتن شرایط کانال و همچنین عدالت در توزیع منابع ، کل کانالها و همچنین توان موجود به طور مساوی بین کاربران تقسیم میشود. این روش سادهترین و در عین حال کم بازدهترین الگوریتم است. یکی دیگر از روشهای مطرح الگوریتمIWF3 است که در آن هر کاربر با فرض اینکه تخصیص زیر حاملها بهینه است ، به طور مستقل و بدون تو جه به تاثیری که روی سایر کاربران دارد، الگوریتم Water filling را به صورت تکرار شونده اجرا و به هر زیر حامل توانی اختصاص میدهد که با حفظ محدودیت توان کل ، حداکثر نرخ اطلاعات حاصل می شود.
برای یک سیستم با K کاربر و N زیر حامل، بد ست آوردن تخ صیص بهینه زیر حاملها م ستلزم محاسبه NK حالت مختلف تخصیص و سپس محاسبه تابع هدف روی هر مجموعه است . که محاسبات بسیار پیچیده و برای سی ستمهای عملی غیر قابلا ستفاده ا ست. این روش ن سبت به روش SRA عملکرد بسیار بهتری دارد زیرا به دلیل متمرکز بودن الگوریتم SRA، ضروریست پس از اضافه یا کم شدن تعداد کاربران الگوریتم مجددا اجرا شود و این یکی از معایب روش SRA نسبت به الگوریتمهای غیرمتمرکز مانند IWF است.
از معایب دیگر این روش نیاز به وجود یک مرکز مدیریت است که متأسفانه در بیشتر شبکهها وجود ندارد. الگوریتمISB4 نیز روشی متمرکز است که نتیجه آن نزدیک به نقطه بهینه الگوریتمOSB5 است که در بین روشهای متمرکز بهترین کارایی را دارد 8 ، بنابراین ISB یک الگوریتم زیر بهینه است
جدول 1 مقایسه الگوریتمهای معرفی شده را از نظر پیچیدگی محا سباتی ن شان میدهد. نحوه محا سبه پیچیدگی محا سبات به عنوان نمونه برای روش ISB به این ترتیب است که اگر حداکثر بیت مجاز B باشد یافتن حداکثر برای یک تابع هدف برای کل کاربران دارای BK سری محاسبه است و با توجه به اینکه این کار باید T1 بار تکرار شود خواهد شد . T1BK این الگوریتم باید برای همه زیرحامل ها اجرا شود و نیاز ا ست که مجموعه های k ضریب مربوط به کاربران به تعداد T2 بار به روزرسانی شوند. بنابراین کل پیچیدگیهای مسئله برابر با T1T2NKB خواهد شد. توجه شود که T3در این جدول تعداد تکرار های الگوریتم IWF است.
در ادامه رو شی برای تخ صیص منابع ارائه گردیده ا ست که علاوه بر تخصیص عادلانه منابع در بین کاربران پیچیدگی محاسباتی را به اندازه قابل ملاحظهای کاهش داده است.
-3 روش پیشنهادی
در این بخش دو روش پیشنهاد شده است. در حالت کلی مسئله تخصیص منابع بهصورت معادله - 1 - است.
در این مسئله Pn,k توان اختصاص داده شده به کاربر kام در کانال nام و gn,k نسبت گین کانال به نویز آن است. Ptotal میزان توان کل در دسترس است.
الگوریتم اول: کانال ها به طریقی به کاربران تخصیص داده میشوند که هیچ کانالی به دو کاربر نمیرسد و همواره هرکانال فقط به یک کاربر تعلق میگیرد. در این الگوریتم پس از م شخص کردن کانالهای اختصاص داده شده به هر کاربر، از طریق الگوریتم water-filling به تخصیص توان روی هر کانال پرداخته شده است.
فرض کنید مجموعه Ak شماره کانالهای اختصاص یافته به کاربر kام وpk توان اختصاصی را نشان دهد. در اولین گام= 0 , = 0 است. در این مرحله به هر کاربر بایستی یک کانال اختصاص یابد. بنابراین، کاربری بصورت تصادفی انتخاب شده - کاربر - k و بهترین کانال، یعنی کانال n از مجموعه کانالهای آزاد، A، که از رابطه k = max gn,k محاسبه می شود،
به کاربر اختصاص می یابد. این عمل برای تمام کاربران انجام میشود بنابراین به روز رسانی ضرایب به صورت مجموعه معادلات - 2 - خواهد شد.
به منظور تخصیص عادلانه منابع، ضرایب{ α1, α2, … . . , αk } که میزان اهمیت هر کاربر را نشان می دهند، تعریف میشود و تا زمانی که ≠ ∅ خواهیم داشت:
که در آن مقدار Pn,i با الگوریتم water-filling مشخص میشود. پس به طور خلاصه، در این مرحله، با توجه به نرخ داده دریافتی هر کاربردر مرحله اول و همچنین میزان اولویت آن برای تخصیص عادلانه منابع سایر کانالهای باقیمانده به کاربران اخت صاص داده میشود. یعنی ابتدا کاربری که در مرحله قبل کمترین نرخ داده را بد ست آورده انتخاب شده و از بین کانالهای باقیمانده بهترین کانال به آن اختصاص داده می شود و نرخ دریافتی کاربر را به روز رسانی میگردد. این کار ادامه یافته تا همه ی کانال ها اختصاص داده شوند.
الگوریتم دوم: در این الگوریتم بخش تخصیص کانال مشابه الگوریتم قبل است با این تفاوت که در هنگام تخصیص توان از الگوریتم ISB ا ستفاده می شود. در واقع این الگوریتم ترکیبی از الگوریتم اول پی شنهادی ، IWF و ISB می با شد و به این ترتیب، از مزایای الگوریتم ها استفاده کرده و نتیجه بهتری ارائه میگردد.
-4 نتایج شبیهسازی
در این مقاله کلیه شبیه سازی ها تو سط نرم افزار متلب ویرایش 2010 ان جام گرف ته است و در کل یه ن تایج، په نای با ند برابر 1MHz، نویز 1 μW/Hz، SNR برابر 10dB و تعداد کانالها 64 و توان کل موجود 10 وات در نظر گرفته شده و همچنین کانال فرکانس گزین فرض شده است.
در شکل - 1 - ، به دلیل اختصاص یک کانال به تنها یک کاربر در الگوریتم ارائه شده الگوریتم ارائه شده کارایی بهتری دارد در حالی که با افزایش تعداد کاربران بازدهی طیفی الگوریتم های ISB و IWF به سر عت کاهش مییابد و هنگامی که تعداد کاربران بیشتر از تعداد کانال میشود، بازدهی آن به علت عدم اخت صاص کانال به کاربران مازاد بر تعداد کانال ها به شدت افت کرده و زیر بازدهی الگوریتم ISB قرار میگیرد.
در شکل - 2 - الگوریتم یک ارائه شده و همچنین ISB وقتی که تعداد کانالها کمتر از تعداد کاربران است بازدهی مناسبی ندارند ولی الگوریتم دوم ارائه شده به دلیل اینکه در واقع ترکیبی از الگوریتم یک و ISB است به مراتب پاسخ بهتری ارائه میدهد.
