بخشی از مقاله
چکیده
شبکههای توری بیسیم یک ساختار جدید را به منظور ایجاد سرویسهای ارتباطی پهن باند و با قابلیت توسعه، فراهم میسازند. با توجه به این موضوع، تخصیص منابع به منظور بهبود گذردهی توام با رعایت انصاف بین جریانهای ترافیکی و توازن در استفاده از کانالها و گرههای شبکه، بعنوان یکی از مهمترین چالشهای پیش رو در این شبکهها مطرح میشود. در این مقاله، مسئلهی تخصیص منابع با در نظر گرفتن هدف مطرح شده و مدیریت شبکه در بخشهای توان، نرخ، زمانبندی، مسیریابی و تخصیص کانال فرمولبندی میشود. مسئلهی مطرح شده NP-Complete میباشد و با افزایش تعداد گرههای شبکه و تعداد تقاضاهای ترافیکی، مدت زمان پاسخگویی به صورت نمایی افزایش مییابد. برای حل این مشکل یک الگوریتم ابتکاری به منظور مدیریت دسترسی به منابع، ارائه میگردد. نتایج شبیهسازی عملکرد مناسب الگوریتم پیشنهادی را در مقایسه با رویکرد فرمولبندی شده بهینه نشان میدهد.
-1 مقدمه
شبکههای توری بیسیم - - Wireless Mesh Networks، شبکههای ترکیبی متشکل از مسیریابهای توری بیسیم و مجموعهای از مشتریهای بیسیم و با سیم میباشند. با توجه به محدودیتهای تعداد کانالهای ناهمپوشان و تعداد رابطهای رادیویی در مسیریابها، امکان ارسال همزمان تمام تقاضاهای ترافیکی به دلیل بحث تداخل وجود ندارد. از این رو لازم است به منظور دستیابی به گذردهی مناسب توام با رعایت انصاف بین جریانهای ترافیکی و توازن در استفاده از گرهها و کانالهای شبکه، مسئلهی مدیریت تخصیص منابع با رویکرد مقابله با خرابیهای احتمالی در برخی از گرههای ارتباطی شبکه به صورت توام در نظر گرفته شود.
مسئلهی بهبود گذردهی با رویکرد کنترل توان و نرخ در مراجع 1]و[2 مورد بررسی قرار گرفته است. در این مراجع تنها به وجود یک مسیر در جابهجاییهای تقاضاهای ترافیکی اکتفا شده است. به دلیل ساختار بزرگ شبکههای توری بیسیم، مقاومت شبکه در برابر بروز خرابی برخی از گرههای شبکه مسئلهی مهمی است. با توجه به مراجع 3]و[4، یک شبکه مقاوم است اگر با وجود خرابی K گره همچنان متصل باقی بماند. شبکه با این ویژگی K_Connected نامیده میشود. در مراجع 5]و[6، ویژگی K_Connected با استفاده از کنترل توان در شبکههای سنسور و موردی بیسیم بررسی شده است. از جمله ویژگیهای این مقاله نسبت به اکثر مراجع در حوزهی شبکههای توری بیسیم میتوان به در نظر گرفتن توام مسئله مدیریت جامع تخصیص منابع شامل کنترل توان، تطبیق نرخ، تخصیص کانال، زمانبندی و مسیریابی همراه با رعایت انصاف بین جریانهای ترافیکی و توازن در استفاده از گرهها و کانالهای شبکه با رویکرد مقابله با خرابی اشاره کرد.
این مقاله به صورت زیر سازمان دهی شده است: در بخش دوم مدل شبکه معرفی شده است. در بخش سوم مسئلهی تخصیص منابع با ویژگی مقابله در برابر خرابی گرهها فرمولبندی میشود. در بخش چهارم الگوریتم ابتکاری با هدف بهبود گذردهی با رعایت انصاف بین جریانهای ترافیکی و توازن در استفاده از کانالها و گرههای فرکانسی معرفی میگردد. تجزیه و تحلیل شبیهسازیها و در نهایت نتیجهگیری در بخش پنجم و ششم آورده شده است.
-2 مدل شبکه
در این مقاله، یک شبکه توری بیسیم چند رادیویی-چند کاناله با n مسیریاب در نظر گرفته میشود. هر گره در این شبکه به تعدادی رادیوی یک طرفه - - half-duplex به منظور ارسال یا دریافت مجهز شده است. هر رادیو با استفاده از آنتن همه جهته قابلیت ارسال در محدودهی توان مخابراتی[0,Pmax ] با یکی از M نرخ ,...,ρM } {ρ1 ,ρ2 R را دارد. به هر رادیو یکی از کانالهای ,w2 ,...,wΩ } {w1 Ω تخصیص داده میشود. بدلیل رخداد تصادم، میبایست به رابطهای رادیویی یک گره، کانالهای مجزا تخصیص داده شود. در این مقاله ترافیک به صورت تقاضاهای تک پخشی بین مجموعهای از جفت گرههای هم نوع در نظر گرفته میشود. این مجموعه از جفت گرهها را با Q و تقاضای ترافیکی بین هر جفت - u ,v - Qبا TDuv نشان داده میشود.
در این مقاله، شبکه با یک گراف جهتدار G - V,E - مدل میشود که {v 1 ,v2 , ...,v n } V نشاندهندهی n مسیریاب توری بیسیم میباشد که در یک ناحیه مفروض واقع شدهاند و E نشاندهندهی مجموعه پیوندهای مخابراتی بین گرههای مختلف شبکه است. شرط لازم برای برقراری پیوند بین دو گره، وجود حداقل یک کانال فرکانسی مشترک بین آنها میباشد. علاوه بر شرط وجود کانال فرکانسی مشترک به منظور وجود یک پیوند، گره گیرنده باید در برد مخابراتی گره فرستند باشد. برد مخابراتی بعنوان شعاعی تعریف میشود که گیرنده می تواند بستههای فرستنده را به طور صحیح دریافت کند. برای تعیین این برد از مدل تداخل فیزیکی که در ادامه مطرح خواهد شد استفاده میشود. به منظور ارزیابی ویژگی K_Connected بودن شبکه یا بعبارتی متصل بودن شبکه به ازای K-1 خرابی گره، از قضیه منجر[7] استفاده میکنیم. بر اساس این قضیه، یک شبکه K_Connected است اگر و تنها اگر، K مسیر با رئوس مجزا بین هر جفت گره در شبکه موجود باشد. شرط لازم برای این منظور این است که حداقل درجه گراف شبکه - - degGmin برابر K باشد. که degi درجه گره iام است که در واقع تعداد پیوندهای متصل به این گره میباشد.
-3 فرمولبندی مسئله تخصیص منابع
به منظور فرمولبندی مسئلهی تخصیص منابع با رعایت انصاف و توازن از تمامی ابزارهای کنترل توان، تطبیق نرخ، تخصیص کانال، زمانبندی و مسیریابی در مدل پیشنهادی استفاده شده است. در این مدل متغیرهای تصمیم به صورت زیر بیان میشوند:
· X wt یک متغیر باینری است که اگر ارسال از گره i به گره j در شکاف زمانی t و کانال فرکانسی w و با نرخ ρk زمانبندی شود برابر یک میباشد و در غیر اینصورت صفر است. • Pijt عددی حقیقی در بازهی [0,Pmax ] است که نشاندهندهی توان ارسالی روی پیوند eij در شکاف زمانی t میباشد. · fijtuv عدد حقیقی و غیرمنفی است که بیانگر مقدار ترافیک درخواستی جفت - u ,v - Q است که از پیوند eij در شکاف زمانی t عبور میکند.
برای مدلسازی این مسئله میبایست توپولوژی شبکه در ابتدا در نظر گرفته شود. توپولوژی شبکه باید به نحوی انتخاب شود که فقط پیوندهایی که پتانسیل فعال شدن دارند در گراف شبکه وارد شوند. این مجموعه از پیوندها با شرط - 2 - تعیین میشوند .[8] بهره انتشارمیباشد. بهره انتشار نشان دهندهی تلفات توان از گره i به j میباشد که با فاصلهی اقلیدسی بین دو گره رابطهی معکوس از مرتبه ε دارد. مقدار ε عددی وابسته به پدیدههای محوشدگی و سایه میباشد. - λ - ρ1 یک سطح آستانه متناظر با حداقل نرخ ارسال و ملزومات کیفیت خدمات میباشد. در ادامه در بخش 1-3 تمامی محدودیتهای مسئله به طور جامع تعریف میشوند و سپس در بخش 2 -3 تابع هدف مسئلهی تخصیص منابع با هدف حداکثر کردن گذردهی توام با رعایت انصاف و توازن معرفی میشود.
-1-3 محدودیتهای مسئله
محدودیتهای مسئله در مجموعه روابط - 3 - تا - 15 - آورده شده است.محدودیت - 7 - ناشی از دو طرفه غیر همزمان بودن رابطهای رادیویی هر گره میباشد. با توجه به این که کانالهای فرکانسی متفاوتی به رابطهای رادیویی یک گره تخصیص داده میشود، پس این محدودیت نشان میدهد که روی هر کانال فرکانسی میتوان در هر لحظه فقط ارسال یا دریافت را انجام داد. با توجه به محدودیت - 8 - ، حداکثر تعداد ارسالهای دو طرفه غیرهمزمان در یک گره به تعداد رابطهای رادیویی آن یعنی Inj محدود میشود.رابطهی - 9 - نشان میدهد که برای هر تقاضای ترافیکی، جریان ترافیکی کلی ارسالی از گره منبع - و یا دریافتی در گره مقصد - با مقدار ترافیک درخواستی هر تقاضا برابر است. همچنین این رابطه تضمین میکند که در گرههای میانی در مسیر یک تقاضای ترافیکی، توازن بین ورود و خروج بستهها برقرار است.
محدودیت - 10 - تضمین میکند که مجموعه تمامی تقاضاهای ترافیکی متعلق به Q - u ,v - عبوری از پیوند بین i و j در تمامی شکافهای زمانی نمیتواند از مجموع حداکثر داده قابل ارسال روی این پیوند در تمامی شکافهای زمانی با توجه به نرخ انتخابی آن بیشتر باشد. در این محدودیت - υ - ρk مقدار ترافیک ارسالی در نرخ ρk در یک شکاف زمانی روی پیوند میباشد. همچنین اگر حداقل یکی از تقاضاهای ترافیکی انتها به انتها از پیوند بین i و j عبور کند، این پیوند باید حداقل در یک شکاف زمانی فعال باشد. این مهم توسط محدودیت - 11 - محقق میشود.
در این رابطه uv Z یک متغیر باینری است که در - 12 - معرفی شده است.با فرض اینکه گراف شبکه به ازای ارسال با حداقل نرخ K_Connected باشد، برای حفظ این ویژگی باید بین هر جفت گره در گراف شبکه K مسیر با رئوس مجزا وجود داشته باشد. این شرط در عبارات - 13 - و - 14 - آورده شده است. رابطهی - - 13 نشان میدهد که هر تقاضای ترافیکی از گره منبع از طریق K مسیر ارسال میشود و در گره مقصد نیز از K مسیر دریافت میشود. رابطهی - 14 - نشان میدهد که در هر جریان ترافیکی، گرههای میانی متعلق به مسیرهای مختلف، مجزا هستند.
-2-3 تابع هدف مسئله
تابع هدف مسئله، با رویکرد حداکثر کردن گذردهی، رعایت انصاف بین جریانهای ترافیکی، توازن در استفاده از کانالها و گرههای شبکه به صورت رابطهی - 15 - فرمولبندی میشود.
