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

قیمت: 44,000 تومان

دانلود رایگان مقاله

خرید ترجمه مقاله

عنوان فارسی

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

عنوان لاتین

Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks

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

Communication links connect pairs of wireless nodes in a wireless network. Links can interfere with each other due to their proximity and transmission power if they use the same frequency channel. Given that a frequency channel is the most important and scarce resource in a wireless network, we wish to minimize the total number of different frequency channels used. We can assign the same channel to multiple different links if the assignment is done in a way that avoids co-channel interference. Given a conflict graph which shows conflicts between pairs of links if they are assigned the same frequency channel, assigning channels to links can be cast as a minimum coloring problem. However the coloring problem is complicated by the fact that acceptably small levels of interference between pairs of links using the same channel can accumulate to cause an unacceptable level of total interference at a given link. In this paper we develop fast and effective methods for frequency channel assignment in multi-hop wireless networks via new heuristics for solving this extended coloring problem. The heuristics are orders of magnitude faster than an exact solution method while consistently returning near-optimum results.