بخشی از مقاله
ارائه یک روش اختصاص کانال ابتکاری در شبکه های چند کانالی چند رادیویی مش بیسیم
چکیده
شبکه های مش بیسیم کاربردهای فراوانی همچون دسترسی به اینترنت را دارند. یکی از مهمترین معماریهای مطرح شده در این نوع شبکه ها، شبکه-های چند رادیویی چند کانالی مش بیسیم است. از مهمترین مسائل در این نوع معماری، مسئلهی تخصیص کانال است. از آنجایی که شبکههای مش بیسیم به صورت گسترده مورد استفاده قرار میگیرند مسئله تخصیص کانال نقش حیاتی را در این نوع شبکه ها دارد. در این مسئله، تداخل تاثیر معکوسی را بر کارایی شبکه دارد. ارائهی راه حلی جهت مسئلهی تخصیص کانال باید با هدف افزایش گذردهی و کاهش تداخل انجام شود. راهحلهای مختلفی برای حل این مسئله ارائه شده است که از آن جمله میتوان روشهای ابتکاری را نام برد. در این مقاله سعی شده است با استفاده از این روشها، اختصاص کانال با هدف افزایش گذردهی و کاهش تداخل انجام شود. برای این منظور جهت مدیریت سادهتر اختصاص کانال از یک روش خوشهبندی استفاده شده است. الگوریتم پیشنهادی، شامل چهار فاز است که در آن ارتباطات بین خوشهها بر اساس روش گروههای حداکثری در تئوری گراف و با استفاده از درجهی مرزی بودن هر گره مرزی انجام میشود. نتایج شبیه سازی نشان میدهد که روش پیشنهادی میتواند نرخ تحویل بستهها و همچنین میزان گذردهی را افزایش دهد. علاوه بر آن میزان از دست رفتن بستهها و تاخیر انتها به انتها را کاهش دهد. پس به صورت کلی کارایی شبکه مش را بهبود می بخشد.
معرفی
امروزه ارتباطات بیسیم به یکی از اجزای جدایی ناپذیر زندگی انسانها تبدیل شده است. افزایش روزافزون تقاضا برای خدمات بیسیم، باعث ظهور فناوریهای جدید در این حوزه شده است. یکی از این فناوریهای نوید بخش شبکههای مش بیسیم 1 است که در ارتباطات بیسیم مورد توجه میباشد. شبکههای مش به دلیل فواید فراوان و همین طور نرخ ارسال داده بالا و هزینه پایین و انعطافپذیری، بسیار مورد توجه هستند. یک شبکه مش متشکل از چندین گره2 است که عبارتند از: مسیریابهای مش3 و کاربران مش4 است. مسیریابها دارای حداقل قابلیت حرکت میباشند و زیربنای شبکه را تشکیل می-دهند. از کاربردهای این نوع شبکهها در زمینهی دسترسی به اینترنت است. (2005,Akyildiz, Wang and et al)
ظرفیت شبکههای مش به دلیل تداخل کاهش مییابد و این یکی از مسائل اساسی در این نوع شبکههاست. امروزه شبکههای چند کانالی چند رادیویی با گرههایی که مجهز به چندین واسط5 هستند مورد استفاده قرار میگیرند. در این صورت تداخل کاهش یافته و کارایی شبکه بالا میرود. در این حالت هر گره میتواند به صورت همزمان با گرههای همسایه خود ارسال و دریافت داشته باشد. بسیاری از روشهای اختصاص کانال با هدف بهبود کارایی شبکه طراحی شدهاند. در خیلی از این روشها از خوشهبندی استفاده شدهاست تا اینکه میزان پیچیدگی اختصاص کانال کاهش یابد. در این حالت شبکه به خوشه هایی تقسیم شده و اختصاص کانال به صورت محلی در هر کدام از خوشهها انجام میشود.
بر اساس مقاله2 ، بسته به مکان جغرافیایی، لینکهای متداخل میتوانند به دو دسته تقسیم شوند که عبارتند از لینکهای متداخل هماهنگ و لینک-های متداخل غیرهماهنگ. در مقایسه با لینکهای متداخل هماهنگ لینکهای متداخل غیر هماهنگ منجر به از دست رفتن میزان دادهی بالاتری میشوند و در نتیجه سبب توزیع ناعادلانه ظرفیت، بین لینکها میشوند. بر طبق مقاله (2009, Naveed and Kanhere) 3 که در آن روش CCAS مطرح شده است سطوح مختلف لینکهای متداخل بررسی میشوند. الگوریتم خوشهبندی این روش مشابه شبکههای سلولی است. اما اطلاعات مکانی گرهای که مورد استفاده-ی فرآیند خوشهبندی است مشکل به دست میآید. الگوریتم خوشهبندی بر اساس سلولهای ثابت که مورد استفادهی این روش است مناسب توپولوژی تصادفی نیست. گرههای موجود در خوشههای یکسان نمیتوانند با گرههایی که در دو گامی خود هستند ارتباط برقرار کنند.
در مقاله 2 یک روش خوشهبندی مبتنی بر گروهبندی6 با نام CCCA مطرح شد که در آن نیز سطوح مختلف لینکهای متداخل بررسی میشود. هدف این است که تداخل غیر هماهنگ حذف شده و تداخل هماهنگ کاهش یابد. در این روش شبکه بر اساس گراف تداخل و با استفاده از روش گروههای حداکثری7 به خوشههای مجزایی تقسیم میشود. از آنجایی که گراف تداخل به راحتی می تواند از روابط ارتباطی بین گرهها در شبکه به دست آید اطلاعات مکانی بیشتری مورد نیاز نیست. پس انعطافپذیری این روش از CCAS بیشتر است. در این روش هر خوشه نشاندهنده یک حوزه تداخلی است.
در این مقاله از روش خوشهبندی مطرح شده در مقاله2 استفاده شده است. گرهها در یک خوشه به جهت اینکه همواره متصل باقی بمانند از یک کانال پیش فرض برای ارتباطات درون خوشه ای استفاده میکنند. کانال های متعامد طوری به عنوان کانال پیش فرض خوشههای همسایه اختصاص پیدا میکنند که تداخل غیر هماهنگ تا حد امکان حذف شود. برخلاف مقاله 2 جهت کاهش تداخل از دو واسط جهت مرتبط ساختن خوشههای مجاور استفاده میشود. در این صورت با استفاده از روش ساختن حداکثر گروهها در تئوری گراف و از طریق درجهی مرزی بودن هر گره، برای هر گرهی مرزی، حداکثر دو گروه ساخته شده و به گرههای هر گروه کانالی اختصاص مییابد. کانالی که به واسطهای بین خوشهها اختصاص پیدا میکند باید متفاوت از کانال پیش فرض خوشههای همسایه باشد تا آنکه میزانتداخل کاهش یابد. نهایتاً به واسطهای درون خوشه ای باید کانالی اختصاص داده شود که در دو گامی یک گره حداقل استفاده را دارد. برای ارزیابی این روش از نرم افزار NS2 استفاده شده است . نتایج شبیهسازی نشان میدهد که این روش کارایی شبکه را بهبود میبخشد.
ادامه این مقاله به صورت زیر است : در قسمت 2 مفاهیم، مدل شبکه و فرمولسازی مسئله مطرح شده و در ادامه الگوریتم پیشنهادی در قسمت 3 بیان میشود. نتایج شبیهسازی و ارزیابی نیز در قسمت 4 مطرح شده و در قسمت 5 نتیجهگیری ارائه میگردد .
مفاهیم و مدلسازی شبکه
در این قسمت ابتدا مفاهیم مورد نیاز در مدلسازی شبکه مطرح شده و در ادامه مدل شبکه و فرموله سازی مساله ارائه میگردد.
گراف توپولوژی شبکه
اگر k کانال در یک شبکه به صورت C1، C2، C3، ..
محدودهی انتقالی مشترک، حداقل یک واسط داشته باشند خواهد داشت. (2008,Crichigno,Wu and et al)
، C k، موجود باشد و Ii تعداد واسطهای گرهی i باشد، در صورتیکه هرکدام از جفت گرهها درون که بر روی کانال مشترکی کار کند، در این صورت یالی بین آن دو گره در توپولوژی شبکه وجود
لینک های متداخل هماهنگ و لینک های متداخل غیر هماهنگ
به طور کلی لینکهای متداخل به دو گروه لینکهای متداخل هماهنگ و لینکهای متداخل غیرهماهنگ تقسیمبندی میشوند. این طبقهبندی بر اساس فاصلهی جغرافیایی دو لینک متداخل انجام میشود. بر اساس این تقسیمبندی در صورتیکه دو لینک (A,B) و (C,D) وجود داشته باشد و فاصلهی بین A و C کمتر از محدودهی تداخلی R' باشد، در این صورت این دو لینک در گروه لینکهای متداخل هماهنگ قرار داده میشوند و در غیر این صورت این لینکها در گروه لینکهای متداخل غیر هماهنگ قرار میگیرند. به عنوان مثال در شکلهای 1 و2 این دو گروه نشان داده شده است.
در این شکلها دایرهی پررنگ نشاندهندهی محدودهی انتقالی است و دایرهی نقطهچین نشاندهنده محدودهی تداخلی گرهی .A همانطور که در شکل 1 ملاحظه میشود لینک 2 یک لینک هماهنگ با لینک 1 است. در این حالت انتقالات دو جریان A و C در محدودهی انتقالی یکدیگر هستند. هر دو دسته از لینکهای متداخل کارایی شبکه را کاهش میدهند، اما لینکهای متداخل غیرهماهنگ منجر به از دست دادن نرخ بالاتری از بستهها میشوند. بنابراین در تخصیص کانال ابتدا باید اولویت با حذف لینکهای متداخل غیر هماهنگ باشد و پس از آن باید لینکهای متداخل هماهنگ تا حد امکان کاهش یابد.
مسئلهی گروهبندی
در تئوری گراف یک گروه عبارت است از گرافی غیرجهتدار که شامل زیرمجموعهای از رئوس میباشد که در آن هر دو راس توسط یالی به یکدیگر متصل شده باشند. به عبارت دقیقتر یک گروه در یک گراف غیر جهتی G(V,E) یک زیرمجموعه از رئوس مثل C است به طوریکه تمام اعضای C عضو مجموعهی V باشد و در آن به ازای هر دو راس در C یالی بین آنها در گراف G وجود داشته باشد. بر اساس تعریف ارائه شده نتیجه گرفته میشود که یک گروه گرافی کامل است. در گراف کامل بین تمام رئوس گراف حتماً یالی وجود خواهد داشت. (Tomita, Akutsa and et al)
گروهها یکی از مفاهیم اصلی در تئوری گراف هستند و کاربردهای زیادی در مسائلی که توسط گرافها مدل میشوند دارند. به طور کلی کاربرد مسئله-ی گروهبندی در علوم کامپیوتر در جاهایی مطرح میشود که در آن هدف پیدا کردن زیر گرافهایی کامل باشد. یکی از کاربردهای گروهبندی استفاده از آن در ساختن خوشهها و اختصاص کانال است. مسئلهی گروهبندی در حوزهی مسائل سخت قرار داده میشود. دو مفهوم اصلی در مسئلهی گروهبندی، گروههای حداکثری و بزرگترین گروه8 است. یک گروه حداکثری، گروهی است که نمیتواند با راس دیگری جز اعضای خودش گسترش یابد. به عبارت دیگر یک گروه حداکثری گروهی کامل است که خود نمیتواند زیر مجموعهی یک گراف کامل بزرگتر باشد. اگر تمامی گروههای حداکثری در گرافی محاسبه شوند در بین آنها گروهی که حداکثر اعضا را دارد بزرگترین گروه نامیده میشود. این دو مفهوم درگراف شکل 3 نشان داده میشود.
گراف تداخل
گراف تداخل، گراف غیرجهتی G(V,E) است که در آن V مجموعه مسیریابهای مش است و E هم مجموعه لینکهای متداخل است. لینکهای متداخل بین هر دو گرهای که در فاصله تداخلی هم باشند وجود خواهد داشت و این به معنای آن است که گرهها میتوانند انتقال یکدیگر را حس کرده و از برخورد جلوگیری کنند.(( 2011,Ding and Xiao
مدل شبکه
فرض بر این است که شبکهی مش از تعدادی مسیریاب تشکیل شده و هر گره حداقل به سه واسط مجهز شده است. تعداد کانالها مطابق با استاندارد 802.11a محدود و برابر با 12 کانال است. یکی از گرهها به عنوان دروازه در نظر گرفته میشود. هر گره توسط دروازه به اینترنت دسترسی پیدا میکند. تمامی گرهها میتوانند به صورت مستقیم یا غیرمستقیم به دروازه متصل گردند.
در این روش، توپولوژی شبکه با گراف غیرجهتی(GT(VT,ET نشان داده میشود به طوریکه در آن، مجموعهی VT={v1,v2,…,vn} مجموعهی رئوس گراف است که نشان دهندهی مسیریابهاست و مجموعهی V T } VT, vj ET={e(i,j)| vi، مجموعهی لینکهای بین گرهها را نشان میدهد. در این صورت vi گرهی مبدا و vj گرهی مقصد است. در صورتی بین دو گره لینکی موجود خواهد بود که این دو گره در حوزه فرکانسی یکدیگر بوده و از کانال مشترکی استفاده کنند. به واسطهای یک گره ممکن است کانالهای متفاوتی در صورتی که موجود باشد، اختصاص یابد.
در این الگوریتم یکی از واسطها به عنوان واسط پیش فرض تنظیم میشود. محدودهی انتقالی و محدودهی تداخلی ثابت هستند و همهی گرهها با توان ثابتی عملیات انتقال را انجام میدهند. محدودهی تداخلی دو برابر محدودهی انتقالی است. مدل تداخلی مورد استفاده در این روش، مدل پروتکلی است، در این صورت تداخل با گراف G(V, E) مدل میشود. به طوریکه در آن مجموعهی V={v1,v2,…,vn} مجموعهی مسیریابهاست و مجموعهی V V, vj E={e(i,j)| vi، مجموعه گرههایی را نشان میدهد که در فاصلهی دو گامی از یکدیگر هستند و با یکدیگر تداخل دارند.
بر اساس گراف توپولوژی تمامی همسایگان یک گامی با هر گرهی vi در مجموعهی OHNi قرار داده میشوند. علاوه بر آن با توجه به گراف تداخل تمامی همسایگان دو گامی با گرهی vi در مجموعهی THNi قرار میگیرند. همچنین برای هر گرهی vi مجموعهی CHi شامل تمام کانالهایی است که به واسطهای آن گره اختصاص داده میشود.
الگوریتم پیشنهادی
در این قسمت به اختصار الگوریتم اختصاص کانال پیشنهادی شرح داده میشود. الگوریتم پیشنهادی یک روش ایستا، مبتنی بر گراف و متمرکز است که در آن از یک دروازه جهت اتصال به اینترنت استفاده میشود. دروازه عملیات تخصیص کانال را نیز بر عهده دارد. روش پیشنهادی از یک روش خوشهبندی جهت ساختن گروههایی مجزا استفاده میکند. به طور کلی این روش شامل 4 فاز است که عبارتند از:
· فاز:1 خوشهبندی
· فاز:2 اختصاص کانال به واسط پیشفرض گرههای هر خوشه
· فاز:3 اختصاص کانال به گرههای مرزی، جهت ارتباط برقرار کردن بین خوشهها
· فاز:4 اختصاص کانال به سایر واسطهای درون هر خوشه
در ادامه جزئیات هر یک از این فازها به اختصار شرح داده خواهد شد.
فاز اول: خوشهبندی
در زمان راهاندازی شبکه، در ابتدا واسطهای پیشفرض تمامی گرهها به کانال مشترکی گوش میدهند تا آنکه ارتباط بین آنها برقرار گردد. در فاز نخست هر گره بستههای سلام9 را برای همسایگان یک گامی خود پخش همگانی میکند تا آنکه همسایگان خود را شناسایی کرده و لیستی از آنها را تولید کند و آن لیست را به همراه شناسهی خود به دروازه ارسال کند. دروازه با استفاده از این اطلاعات گراف توپولوژی شبکه یا GT=(VT,ET) را به دست آورده و در ادامه گراف تداخل یا G=(V,E) را با استفاده از گراف توپولوژی تولید میکند. همانطور که در قسمت قبل ذکر شد محدودهی تداخلی دو گام در نظر گرفته شده است. گراف تداخل میتواند توسط افزودن یالهایی بین یک گره و همسایگان دو گامی آن تولید شود. با استفاده از گراف توپولوژی تمام گرههایی که در فاصلهی دو گامی یکدیگر هستند شناسایی شده و یالی بین آنها در گراف تداخل ایجاد میگردد.
پس از طی این مراحل، دروازه الگوریتم خوشهبندی را با استفاده از گراف تداخل به صورتیکه در ادامه خواهد آمد اجرا میکند. اینکه شبکه چگونه به خوشههایی تقسیم شود که حداقل همپوشانی را با هم داشته باشند میتواند به عنوان یک مسئله گروهبندی مطرح گردد. اینگونه مسائل در طبقهی مسائل سخت هستند. در این فاز سعی شده است با هدف کاهش پیچیدگی مسئله از الگوریتم ابتکاری مطرح شده در مقاله 2 جهت عملیات خوشهبندی استفاده گردد.
الگوریتم خوشهبندی شامل دو فاز است که عبارتند از : محاسبه گروهها و تنظیم گروهها. در این الگوریتم جهت تولید هر خوشه از گرهی انتخابی vi دو مرحله طی میشود که عبارتند از: تولید یک زیرگراف از گرههایی که بر اساس گراف تداخل در فاصلهی دو گامی گرهی vi است و به دست آوردن یک حداکثر گروه در زیر گراف. پس از آن گرههای بررسی نشده در مجاورت گرهی vi بر اساس مجموعهی OHNi به حداکثر گروه ساخته شده اضافه میشوند و آن گروه به عنوان یک خوشه در نظر گرفته میشود. هر خوشه شامل شناسهی خوشه و لیست شناسهی گرههای آن خوشه است . در ادامه فرآیند تنظیم برای سایر گرههای باقیمانده و همچنین تمام خوشههایی که حداکثر دو عضو دارند، انجام میشود. در این صورت جهت متعادلسازی بار شبکه گرههای باقی مانده به نزدیکترین خوشههایی اضافه میشوند که حداقل تعداد گره را دارند. علاوه بر آن گرههای تمام خوشههایی که حداکثر دو عضو را دارند، به خوشههای مجاور افزوده میشود.
فاز دوم: اختصاص کانال به واسط پیش فرض گرههای هر خوشه
در فاز دوم لازم است جهت برقراری ارتباط اولیه بین گرههای درون هر خوشه به واسط پیش فرض گرههای هر خوشه کانالی اختصاص یابد. کانالی که به گرههای هر خوشه اختصاص مییابد باید متفاوت از کانالهایی باشد که به خوشههای مجاور هر خوشه اختصاص داده میشود. این عمل سبب کاهش تداخل میگردد. بر این اساس کانال اختصاص داده شده به گرهی vi به مجموعه کانالهای آن افزوده خواهد شد.
فاز سوم: اختصاص کانال به گرههای مرزی جهت ارتباط برقرار کردن بین خوشهها
در این فاز جهت برقراری ارتباط بین خوشههای مجاور لازم است به رادیوهای گرههای مرزی کانالی اختصاص داده شود. بر این اساس با توجه به گراف توپولوژی تمامی گرههای مرزی در مجموعهای با عنوان BOR قرار داده میشوند. از آنجایی که مبنای انتخاب گرههای مرزی جهت تخصیص کانال بر اساس درجهی مرزی بودن هر گره است، بنابراین لازم است با توجه به گراف توپولوژی درجهی مرزی بودن تمام گرههای مرزی مشخص شود. درجهی مرزی بودن با توجه به اینکه هر گره با چه تعداد گره در خوشههای دیگر همجوار است، مشخص میگردد. درجهی مرزی گرهی vi با BOi نمایش داده میشود. حداکثر تعداد واسطهایی که در این مرحله مورد استفاده قرار میگیرند 2 تاست. با توجه به این محدودیت، مجموعهای با نام LIM در نظر گرفته میشود. این مجموعه شامل تمامی گرههای مرزی است که مورد بررسی قرار نگرفتهاند و تعداد کانالهای اختصاص داده شده به آنها 3 تا خواهد شد. در ادامه تعداد اعضای مجموعهی LIM مورد بررسی قرار میگیرد. در صورتی که در این مجموعه عضوی وجود داشت یکی از گرههای موجود در این مجموعه انتخاب میشود اما اگر این مجموعه فاقد عضو باشد از بین اعضای مجموعهی BOR گرهای که بزرگترین درجهی مرزی بودن را داراست، انتخاب میگردد. بر اساس توضیحات فوق الگوریتم اختصاص کانال به گرههای مرزی و همچنین الگوریتم بررسی محدودیت گرههای مرزی بررسی نشده، مطابق شکل4و 5 خواهد بود.
در ادامه رویهی AssingChannels_Inter اجرا خواهد شد. بر این اساس به ازای هر گرهی انتخابی vi زیر گراف G'i با استفاده از تمامی همسایگان تک گامی همجوار در خوشههای دیگر تولید خواهد شد. در زیرگراف به دست آمده در صورتیکه هر یک از گرههای همجوار با گرهی انتخابی vi، در مجموعهی گرههای مرزی بررسی نشده موجود باشند و حداکثر با گرهی انتخابی vi یک کانال مشترک داشته باشند، الگوریتم حداکثر گروه برای آنها اجرا خواهد شد. نهایتاً تمام گروههای حداکثری گرهی vi به صورت MCLi,k از زیرگراف استخراج خواهند شد. در این حالت اگر تعداد گروههای حداکثری ساخته شده یا Ki بیش از 2 تا بود، ابتدا 2 تا از گروههایی که حداکثر تعداد اعضا را دارا هستند با نامهای A وB انتخاب میشوند. هر یک از اعضای سایر گروهها به گروهی اضافه میشوند که با تعداد کمتری از گرههای آن گروه در فاصلهی دو گامی باشد. اگر تعداد گروهها 2 تا بود یکی A و دیگری B نامگذاری میشود و اگر تنها یک گروه وجود داشت آن گروه A نامیده خواهد شد. در پایان اجرای الگوریتم، BOi برای گرهی vi صفر شده و گرهی vi از مجموعهی BOR و در صورت وجود از مجموعهی LIM نیز حذف خواهد شد. الگوریتم رویهی AssingChannels_Inter در شکل 6 و 7 نشان داده شده است.
