اکتشافات سریع برای مساله تخصیص کانال فرکانس در شبکه های بی سیم چندهاپ

چکیده

کلمات کلیدی

1.مقدمه

1.1. مدل های تداخلی

2.1. گراف اتصال و مسیریابی

3.1. گراف تراکم و تداخل تجمعی

2. فرمولاسیون دقیق QCBP

3. اکتشافات حریصانه تصادفی

4. ارزیابی عملکرد

1.4. تداخل های مستقیم

2.4. نتایج

5. نتیجه گیری

لینک های ارتباطی جفت گره های بی سیم یک شبکه بی سیم را به یکدیگر متصل می کنند. لینک ها اگر از یک کانال فرکانس یکسان استفاده کنند، به دلیل وجود قدرت انتقال و نزدیک خود می توانند با یکدیگر تداخل داشته باشند. با توجه به اینکه یک کانال فرکانس مهمترین و کمیاب ترین منبع یک شبکه بی سیم است، امیدواریم بتوانیم تعداد کل کانال های فرکانس مختلف مورد استفاده را به حداقل برسانیم. اگر عمل تخصیص به شیوه ای انجام شود که مانع تداخل کانال گردد، می توانیم از یک کانال مشترک در لینک های متعددی استفاده نماییم. یک گراف متداخل، تداخل میان لینک هایی که به یک کانال فرکانس مشترک تخصیص یافته اند را نشان می دهد و تخصیص کانال به لینک ها را می توان به صورت مساله حداقل رنگ آمیزی تعیین نمود. با این حال، به دلیل اینکه پذیرش سطوح اندکی از تداخل میان جفت لینک هایی که از یک کانال استفاده می کنند می تواند سطح غیرقابل قبولی از تداخل را در یک لینک مشخص ایجاد نماید، مساله رنگ آمیزی می تواند پیچیده تر شود. در این مقاله، ما با استفاده از اکتشافات جدید برای حل مساله رنگ آمیزی پیشرفته، روش های سریع و موثری را برای تخصیص کانال فرکانس در شبکه های بی سیم چندهاپ ایجاد نمودیم. اکتشافات روش های سریع تری نسبت به روش حل دقیق هستند و در عین حال این نتایج جزو نتایج بهینه محسوب می شوند.

در شبکه های بی سیم بهتر است که از حداقل تعداد کانال برای ارتباطات درون دستگاهی استفاده شود. معمولا یک دستگاه مشخص با انتشار در کانال فرکانس خاص، یک لینک ارتباطی با یک گره همسایه ایجاد خواهد کرد؛ از این کانال می توان برای لینک های دیگر نیز دوباره استفاده نمود و به دلیل قدرت انتقال و نزدیکی آن، تداخلی نیز روی لینک هایی که از همان کانال استفاده می کنند ایجاد نمی شود. این باعث می شود که مساله تخصیص کانال برتری یابد و کانال های فرکانس را به نحوی به لینک های ارتباطی تخصیص دهد که تعداد کل کانال های مورد استفاده به حداقل برسند و در عین حال، از بروز تداخل پیشگیری شود. راه حل های این مساله را به سرعت می توان یافت برای اینکه شبکه های بی سیم نسبتا به سرعت تغییر پیدا می کنند (دستگاه های بی سیم ممکن است در هر زمانی شبکه را ترک کنند و یا به آن متصل شوند). با توجه به موقعیت دستگاه های ارتباطی بی سیم، به روش های مختلفی می توان یک نمودار درگیری ایجاد نمود که در آن گره ها نشان دهنده لینک های ارتباطی میان جفت دستگاه ها هستند و کمان های غیرمستقیم گره هایی که در صورت تخصیص به یک کانال فرکانس مشترک، سطح تداخل غیرقابل قبولی دارند را به یکدیگر متصل می کنند. مساله تخصیص کانال، مستلزم تخصیص یک کانال به هر گره در نمودار درگیری است به نحوی که تعداد کل کانال ها به حداقل برسد اما هیچ کمانی دو گره از یک کانال را به یکدیگر متصل ننماید. این یک مساله حداقل رنگ آمیزی استاندارد است که در آن رنگها نشان دهنده فراوانی هستند. مساله حداقل رنگ آمیزی برای نمودارهای عمومی به NP سخت شناخته می شوند (کارپ، 1972). با این حال، مشکل دیگری نیز مطرح است: "عدم تداخل" به این معناست که مقدار تداخل میان دو لینکی که از یک کانال مشترک استفاده می کنند، از یک حد آستانه خاص کمتر است اما معمولا به صفر نمی رسد. از این رو، هنگامی که چند لینک از یک کانال فرکانس استفاده می کنند، تداخل تجمعی می تواند برای ایجاد سطح غیرقابل قبولی از تداخل روی همان لینکی که از کانال استفاده می نماید، کافی باشد، حتی اگر تداخل روی هر جفت لینک کمتر از حد تحمل باشد. این باعث پیچیده شدن مساله رنگ آمیزی می شود. در این مقاله با توسعه اکتشافات سریع برای حل مساله رنگ آمزی پیشرفته، به مساله تخصیص کانال فرکانس روی شبکه های بی سیم چند هاپ می پردازیم. در این راستا از الگوریتم های اکتشافی تصادفی استفاده می کنیم که دنباله ای از مجموعه های مستقل با حداکثر مقدار (WMalSs) در نمودار درگیری پیدا می کنند و ضمن در نظر گرفتن ثابت تداخل تجمعی، یک کانال مشترک را به تمام گره های موجود در هر WMaIS تخصیص می دهند. ما نتایج خود را با یک فرمولاسیون برنامه نویسی باینری دقیق (QCBP) مقایسه می کنیم. نتایج اکتشافات ما خیلی خوب بوده است (حداکثر به دو کانال بیش از روش بهینه درست نیاز دارد) و سرعت آن نیز چند برابر فرمولاسیون QCBP بوده است. اقدامات اولیه مربوط به این موضوع در مقاله چائودری، حافظ و چینک (2015) موجود است. روش های دقیق می توانند ما را به حداقل رنگ آمیزی نمودار درگیری برسانند اما به زمان محاسبه خیلی بیشتری نیاز دارند، در حالی که اکتشافات می توانند روش های معقول را با سرعت مطلوب تری پیدا کنند. در این مقاله چند روش اکتشافی برای مساله حداقل رنگ آمیزی کلاسیک پیشنهاد شده است. برخی از نمونه های شناخته شده آن عبارتند از: SEQ (کوکرا، 1991)، DSATUR (برلاز، 1979)، RLF (لیتون، 1979) و IGA (کولبرسون و لو، 1996). SEQ یک الگوریتم رنگ آمیزی اکتشافی محبوب و ساده است که هر راس گراف را به صورت متوالی می گیرد و کوچکترین رنگ شاخص را که در یکی از همسایه های آن دیده نمی شود، به آن تخصیص می دهد. DSATUR رئوس را به ترتیب درجات نزولی مرتب می کند. یک راس با بالاترین درجه با رنگ 1 رنگ آمیزی می شود. یک راس با بالاترین درجه اشباع انتخاب می شود که در آن درجه اشباع یک راس به صورت تعداد رنگ های مختلفی که مجاور آن هستند، تعریف می گردد. راس انتخابی با کمترین شماره رنگی که درگیر نیست، رنگ آمیزی می شود. این الگوریتم زمانی متوقف می شود که تمام رئوس رنگ آمیزی شده باشند. RLF (Recursive Largest First) رئوس یک کلاس را در یک زمان با استفاده از روند زیر رنگ آمیزی می کند. فرض می کنیم که C کلاس رنگی باشد که در ابتدا تهی است. فرض می کنیم که V’ مجموعه رئوس نامرتبی باشد که می تواند در C جایگزین شود؛ V’ در ابتدا شامل تمام رئوس بی رنگ است. فرض می کنیم که U مجموعه رئوس بی رنگی باشد که نمی تواند در C قرار گیرد؛ U در ابتدا تهی است. اولین راس x0 از V’ را که دارای بیشترین راس مجاور به V’ است را انتخاب می کنیم. x0 را در C قرار داده و تمام رئوس V’ که مجاور x0 هستند را از V’ به U حرکت می دهیم. در حالی که V’ غیرتهی باقی می ماند: اولین راس x در V’ را که دارای بیشترین رئوس مجاور در U هستند انتخاب کنید؛ x را به C اضافه کرده و تمام رئوس موجود در V’ را که مجاور x هستند را از V’ به U منتقل کنید. با توجه به رئوس موجود در V\C، مجموعه مستقل بعدی را به عنوان کلاس رنگی دوم و ... می سازد. IGA (Iterated Greedy Algorithm) گراف را با استفاده از الگوریتم SEQ به صورت مکرر رنگ آمیزی می کند. در هر تکرار، ترتیب کلاس های رنگی مطابق با معیارهایی که ممکن است منجر به کاهش تعداد رنگ های مورد استفاده شود، تغییر می کند. مرتب سازی اکتشافات شامل این موارد است: وارونه سازی ترتیب کلاس های رنگی، جایگزینی کلاس های رنگی در یک ترتیب تصادفی، قرار دادن کلاس ها با بزرگترین کاردینالیته یا بزرگترین تناسب، قرار دادن کوچکترین کلاس کاردینالیته یا کوچکترین تناسب، قرار دادن کلاس ها به ترتیب افزایشی با جمع درجه گروه و قرار دادن کلاس ها در ترتیب نزولی با جمع درجه گروه. نویسندگان از یک انتخاب احتمالاتی مرتب سازی استفاده نمودند. مشخص شد که نسبت 50:50:30 (بزرگترین نخست:معکوس:تصادفی) بسیار موثر است. الگوریتم موجود در پژوهش بولوباس و توماسون (1985) حداکثر مجموعه مستقل را از مجموعه رئوس غیر رنگی انتخاب می کند. رئوس مجموعه انتخابی به یک رنگ جدید تخصیص داده می شوند. این روند تا زمانی تکرار می شود که کل گراف رنگ آمیزی شود. از یک پروسه جستجوی تطابقی تصادفی (فئو و رسنده، 1989؛ فئو و رسنده، 1995) (GRASP) در تحقیق لاگونا و مارتی (2001) برای رنگ آمیزی گراف های اسپارس استفاده شده است. این روش از دو مرحله تشکیل می شود: مرحله ساخت و مرحله توسعه. مرحله فاز از یک نسخه تصادفی RLF برای تولید رنگ آمیزی های اولیه استفاده می نماید. مرحله توسعه نیز از یک پروسه جستجوی محلی در راه حل اولیه به امید ایجاد یک توسعه استفاده می کند. GRASP یک تکنیک تکرارشونده است که در آن هر تکرار یک راه حل تولید می کند. راه حل حاکم در تکرارهای GRASP نتیجه نهایی است. راه حل ابتکاری ما متعلق به کلاس اکتشافات حداقل رنگ آمیزی سازنده است اما برای کنترل درگیری تجمعی در تخصیص کانال بی سیم اصلاح شده است. به دلیل وجود ماهیت پویای شبکه های بی سیم، به یک راه حل سریع نیاز است، بنابراین باید روش های ابتکاری اعمال گردند اما عدم وجود اکتشافات موجود برای حل مرحله حداقل رنگ آمیزی مساله تخصیص کانال شبکه بی سیم می تواند تداخل تجمعی را تکمیل شده فرض کند (چائودری و همکاران، 2015). در مقالات آردال، ون هاسل، کوستر، مانینو و ساسانو (2007) یک مرور کلی از تکنیک های راه حل برای مساله تخصیص فراوانی در شبکه های بی سیم تک هاپ مبتنی بر زیرساخت ارائه شده است. روش های راه حل دقیق و اکتشافی ما نیز با تخصیص کانال فرکانس در شبکه های بی سیم چندهاپ (به ویژه شبکه های مش بی سیم) سروکار دارد. مدل های آردال و همکارانش (2007) فرض می کند که هر آنتن را می توان توسط یک راس در گراف تداخل نشان داد در حالیکه هر راس در گراف تداخل ما نشان دهنده یک ارتباط بی سیم میان یک جفت از گره های مش بی سیم است. مدل های موجود در آردال و همکارانش (2007) با الزامات مربوط به تخصیص کانال های فرکانس چندگانه به آنتن یک گره بی سیم سروکار دارند، در حالی که روش های راه حل دقیق و اکتشافی ما یک کانال تک فرکانس به لینک بی سیم نیمه دوبلکس میان یک جفت از گره های مش بی سیم تخصیص می دهد. علاوه بر این در آردال و همکارانش (2007) ذکر شده که فرمولاسیون هایی که در آنها تنها یک فرکانس به یک راس در گراف تداخل تخصیص داده شده است مد نظر نمی باشند برای اینکه آنها منجر به بروز مشکلات غیرخطی شده که حل آنها بسیار دشوار است. با توجه به موقعیت های بالقوه ایستگاه های سلولی، گره های مورد تقاضا مناطقی را نشان می دهند که شامل تعداد خاصی از درخواست ها در هر واحد زمانی، تعداد کانال های فرکانس موجود، اطلاعات تداخل و همگرایی ایستگاه ها و کانال های اصلی هستند. آکلا، باتا، سودیت، روگرسون و بلات (2008) با مساله تعیین موقعیت تعداد خاصی از ایستگاه های اصلی برای پوشش دهی به گره های مورد تقاضا که در معرض تداخل بودند، کار کردند. یک مورد ساده تر از این مساله نیز در نظر گرفته می شود که در آن یک ایستگاه پایه می توان حداکثر با دو پایگاه دیگر تداخل داشته باشد و درجه گراف تداخل نیز محدود به 2 است. یک راه حل اکتشافی مبتنی بر بازپخت شبیه سازی شده برای حل این مساله در نظر گرفته شده است. به جای ساخت یک گراف تداخل مبتنی بر یک مدل انتشار رادیویی، درگیری های موجود در گراف تداخل به صورت تصادفی ایجاد می شوند. فرض می کنیم که تعداد کانال های فرکانسی موجود برابر 41، 61 و 70 باشد تا نتایج را برای سه مساله با اندازه های مختلف ایجاد نمایند. مساله پیکربندی سطوح قدرت انتقال دهنده ها برای همگراسازی سرویس به مجموعه ای از گیرنده ها، در تحقیق دآندرجیوانی؛ مانینو و ساسانو (2011 و 2013) به نحوی مطرح شده است که امکانات یک شبکه محدود، مثل تعداد فروشندگان یا تقاضای ترافیک مورد نظر به حداکثر مقدار خود باشد. یک فرمولاسیون 0-1 از این مساله نیز در مقاله دآندرجیوانی (2011) ارائه شده است و یک تکنیک نیز برای شناسایی زیرمجموعه ای از محدودیت های نقض شده توسعه یافته است. این تداخل به این شکل تقریب زده می شود که فرض می کنیم سیگنال دریافتی در گیرنده ای با قویترین تداخل دریافت شود. برای کاهش مشکلات عددی ایجاد شده، هنگامی که توان انتقالی توسط متغیرهای مستمر نشان داده شود، یک فرمولاسیون 0-1 برای این مساله توسط دآندرجیوانی و همکارانش (2013) ضمن در نظر گرفتن یک مجموعه متناهی از مقادیر برای سطوح توان فرستنده ها پیشنهاد شده است. از یک مدل SINR (نسبت نویز پالس سیگنال به تداخل) برای مدل سازی تداخل استفاده شده است اما فرمولاسیون آن بر اساس یک مورد خاصی است که در آن سیگنال مطلوب در گیرنده تداخل را از یک فرستنده واحد دریافت می نماید. یک الگوریتم ایجاد شده که از اکتشافات برای جستجوی محدودیت های نقض شده استفاده می نماید. این فرمول ها (دآندرجیوانی و همکاران، 2011، 2013) گسترش یافته اند تا شامل کانال های فرکانسی مختلف باشند (دآندرجیوانی و مانینو، 2009) تا بتوانند عملکرد راه حل های پیشنهادی را در یک سناریوی شبکه WiMAX ارزیابی نمایند. سه کانال فرکانس 7 مگاهرتزی یا 6 کانال 3.5 مگاهرتزی در باند 3.4-3.6 گیگاهرتزی برای ایجاد نتایج آزمایشی در نظر گرفته شده اند. مساله تخصیص فرکانس برای حداقل سازی هزینه SIRs (نسبت سیگنال به تداخل) در نقاطی که در آن به پذیرش نیاز است در مقالات گراهام، مونتمانی، مون و اسمیت (2008) در نظر گرفته شده است. الگوریتم های مبتنی بر بازپخت شبیه سازی شده و سیستم کولونی نیز ایجاد شده اند که رویکرد تابع هزینه مبتنی بر SIR را با رویکرد محدودیت باینری ترکیب می نمایند و به این صورت باعث کاهش زمان اجرا می گردند. تعداد ثابتی از کانال های فرکانس برای تست الگوریتم ها در حالات مختلف مورد استفاده قرار گرفتند. برای مثال، سناریوی 1 از سه دامنه فرکانس 117، 72 و 72 استفاده می کند؛ سناریوی 3 یک دامنه فرکانس از 24 کانال فرکانس دارد و ... . در مقاله مونتمانی و اسمیت (2010) یک مساله تخصیص فرکانس طیفی ثابت در نظر گرفته شده است که در آن طیف داده شده است و هدف نیز یافتن یک تخصیص فرکانس به فرستنده ها می باشد تا اندازه کلی تداخل در شبکه به حداقل برسد. نویسندگان از یک تکنیک کنترل اکتشافی همراه با جستجوی تابو برای حل این مساله استفاده نمودند. یک مدل ساده مشابه با مدل پروتکل (گوپا و کومار، 2000) نیز برای مدل سازی تداخل به کار گرفته شده است که در آنها تنها تداخل میان جفت فرستنده ها لحاظ شده است. نمونه مساله های مختلفی از یک حالت آزمایشی با تغییر تعداد خاصی از کانال های فرکانس داده شده است. مساله طرح شبکه سلولی در مقاله کالونس، کنینگتون و اولینیک (2005) بررسی شده است. با توجه به مجموعه ای از مکان های سلولی برگزیده با هزینه های مربوط به خود، تعداد کانال های فرکانسی موجود، حداکثر تقاضا برای سرویس در هر حوزه جغرافیایی و پتانسیل درآمد در هر منطقه مشتری، متوجه می شویم که مشکل مربوط به تعیین اندازه و مکان سلول ها و کانال های خاصی است که باید به هر سلول تخصیص داده شود. این مساله به عنوان یک برنامه عدد صحیح ترکیب بزرگ که با استفاده از نرم افزار بهینه سازی استاندارد قابل حل نمی باشد، فرمولاسیون شده است. برای ایجاد کرانه های بالاتر یک روش دیگر پیشنهاد می شود. تعداد کانال های فرکانسی موجود 100 در نظر گرفته می شود و تداخل از منابع متعدد نیز لحاظ نمی گردد. مساله تخصیص فرکانس در مقالات آکلا و همکاران (2008)، دآندرجیوانی و مانینو (2009)، دآندرجیوانی و همکاران (2011، 2013)، گراهام و همکاران (2008)، کالونس و همکاران (2005) و مونتمانی و اسمیت (2010) شامل تخصیص مجموعه ای از کانال های فرکانس به فرستندگان بی سیم است و در عین حال محدودیت های تداخل را در شبکه های بی سیم تک هاپ مبتنی بر زیرساخت در آن ها در نظر گرفته می شود. برخلاف این اقدامات، مشکل ما یافتن حداقل تعداد کانال های فرکانسی مورد نیاز است که در عین حال محدودیت های تداخلی تجمعی در لینک های بی سیم شبکه های بی سیم چندهاپ را رعایت نماید. این ها اولین روش های موجود برای حل این مساله است که از یک مدل SIR واقعی تر استفاده می نماید که شامل سایه سازی (چائودری و همکاران، 2015) و یک گراف/ماتریس درگیری با یک درجه گره نامحدود می باشند.