آگوست 6

شبکه‌های، بی‌سیم، تداخل، زمانبندی، گراف

نحوه دسترسی کارا[a16] ی گره‌‌‌ها به کانال و رزرو پنجره‌های زمانی در[a17] زیر فریم دیتا در متن استاندارد نیامده و به زمان پیاده‌سازی استاندارد موکول شده است. در این پایان نامه تمرکز بر روی جنبه دوم یعنی اختصاص پنجره‌های زمانی در زیر فریم دیتا با مدیریت متمرکز می باشد.
فرض کنیم درخواست پهنای باند انتها به انتهای گره‌‌‌ها توسط BS جمع‌آوری شده است. بر این اساس BS باید پنجره‌های زمانی بخش متمرکز زیرفریم دیتا در یک یا چند فریم را، به لینک‌ هایی که ارسال‌ها بر روی آنها انجام خواهد شد[a18]، تخصیص دهد. هدف آن است که:
تعداد پذیرش گره‌‌‌ با درخواست‌های انتها به انتهای ارسال در شبکه به/از BS با درنظرگرفتن سررسید11 بیشینه باشد.
بررسی پیشینه کار
مطالعه برروی زمانبندی در شبکه‌های مبتنی بر تکنولوژی TDMA سال‌های زیادی است که مورد توجه بوده و نتایج فراوانی[a19] ارائه شده است. الگوریتم‌های زمانبندی ارائه شده در برخی از[a20] این کارها، از روش‌های رنگ آمیزی گراف برای یافتن زمانبندی با مینیمم طول فریم، استفاده می‌نمایند. [12، 11، 10، 9، 8، 7، 6، 5] در این روش‌ها، شبکه بی‌سیم به شکل یک گراف تداخل مدل شده است. رئوس این گراف لینک‌ها هستند. همچنین لبههای گراف وجود تداخل مابین لینک‌هایی که در دو سر یک لبه هستند را نشان می دهند. دو لینک باهم تداخل دارند اگر ارسال همزمان آنها باعث تداخل بسته‌های ارسالی آنها شود. اگر در رنگ‌آمیزی رئوس گراف تداخل، رنگ‌ها به عنوان پنجره‌های زمانی در نظر گرفته شوند، حاصل یک زمانبندی TDMA عاری از تداخل است. یک رنگ‌آمیزی با مینیمم رنگ مورد نیاز، معادل یک زمانبندی با مینیمم طول است که گذردهی سیستم را ماکزیمم می‌نماید.
در [7]، الگوریتمی با زمان چند جمله‌ای ارائه شده است که می‌تواند یک زمانبندی با مینیمم طول را برای اختصاص پهنای باند درخواستی فراهم آورد. نویسندگان مقاله فرض کرده‌اند که تنها تداخلی که[a21] در شبکه وجود دارد مابین لینک‌هایی است که یک گره‌‌‌ مشترک دارند (تداخل نوع اول12). بنابراین با این فرض شرایط زمانبندی بدون تداخل را تعریف کرده‌اند. الگوریتم‌های زمانبندی مبتنی بر رنگآمیزی لبه در گراف همبندی، الگوریتمهای تطبیقی13 گفته میشوند. یک تطبیق، مجموعهای مستقل از لبههای گراف است. دو لبه مستقل هستند اگر یک راس مشترک نداشته باشند. اگر تداخل نوع اول را بایک گراف تداخل مدل کنیم، که در آن لینک‌ها رئوس و تداخل میان لینک‌ها لبه‌های گراف هستند، تطبیق در گراف همبندی متناظر با یک مجموعه مستقل رئوس در گراف تداخل می‌باشد.
در [10، 9] فرض شده است که تداخل نوع دوم را می‌توان در شبکه حذف کرد و زمانبندی را با رنگ آمیزی نسخه چند لبه‌ای14 از گراف همبندی، انجام داد. تعداد لبه‌های مابین دو گره‌‌‌، متناسب با نرخ ارسال درخواستی میان آن دو گره‌‌‌ است. باانجام عملیات لازم می‌توان تداخل نوع دوم را از زمانبندی به دست آمده با رنگ‌آمیزی لبه حذف کرد [12] ، ولی در این روش باید تمام لینک‌ها نرخ یکسانی داشته باشند. اگر برای لینک‌هایی که دو گام یا بیشتر باهم فاصله دارند، رنگ‌های متفاوتی در نظر گرفته شود، می‌توان روش رنگ‌آمیزی لبه را به گونه‌ای توسعه داد که تداخل نوع دوم را نیز مد نظر قرار دهد [11]. این روش تخمینی از تداخل نوع دوم ارائه می‌دهد. تعیین دقیق تداخل نوع دوم باتوجه به گراف تداخل شبکه صورت می‌گیرد [5].
با این حال بسیاری از الگوریتم‌هایی که برای زمانبندی TDMA ارائه شده است، قابل اعمال به مدل مسئله [a22]مورد بحث نیستند. دو دلیل اصلی برای این ادعا وجود دارد. اول اینکه، در بسیاری از این کارها [10، 9، 8، 7] مدل تداخل بکار برده شده ناقص بوده و تمام تداخل‌هایی که ممکن است در شبکه‌های بی‌سیم مبتنی بر TDMA به وجود بیاید را در نظر نگرفته‌اند. بلکه تنها تداخل مابین لینک‌هایی که یک گره‌‌‌ مشترک دارند، در نظر گرفته شده است. این[a23] امکان وجود دارد که با تخصیص فرکانس‌های متعامد به لینک‌هایی که دچار تداخل نوع دوم هستند، این تداخل را حذف کرد. با این حال، تخصیص این فرکانس کار آسانی نیست [14، 13] همچنین استانداردهای موجود موضوع فرکانس‌های چندگانه را به طور کامل روشن نکرده اند. این بدان معنا است که ارائه هر راه حلی که از فرکانس‌های مختلف استفاده می‌نماید، نیاز به تکمیل استاندارد دارد.
دومین دلیل این است که مطالعات صورت گرفته تضمین تأخیر انتها به انتها و سربار ارسال را نادیده گرفته‌اند. در روشهای رنگ آمیزی [10، 9، 8، 7] قبل از رنگآمیزی لینکها، به پنجرههای زمانی در فریم رنگ‌های متفاوتی تخصیص داده میشود. پس از رنگآمیزی، هر لینک مجموعهای از رنگهایی را در اختیار دارد که با رنگهای مورد استفاده توسط لینکهایی که با آنها تداخل دارد متفات است. از آنجا که رنگها متناظر با پنجرههای زمانی هستند، تخصیص پنجرههای زمانی نیز بدون تداخل میباشد. با این حال این روش به لینکها این اجازه را میدهد که چندین بار در یک فریم بدون درنظرگفتن کیفیت سرویس اقدام به ارسال کنند. برای مثال اگر به یک لینک دو رنگ برای ارسال تخصیص داده شده باشد و این رنگ متناظر با پنجرههای زمانی پشت سرهم نباشند، این لینک دوبار در فریم اقدام به ارسال هجمه[a24]15های دیتای خود می نماید. به عنوان مثال در استاندارد 802.16 با ارسال دوم، لینک حداقل پهنای باندی به اندازه 28.8 kbps را در مدولاسیون و کدینگ BPSK-1/2 از دست می‌دهد. در
مدولاسیون و کدینگ 64QAM-3/4، این میزان برای فریمی با طول 10ms، 259kbps است. الگوریتمهای مکاشفه‌ای16 متعددی نیز به طور مشخص برای شبکههای مش بی‌سیم ارائه شده است. البته کارهای انجام شده در زمینه زمانبندی توزیع شده با درنظر گرفتن تضمین تأخیر انتها به انتها بسیار محدود بوده [13] و الگوریتمهای موجود تلاشی در جهت ارائه بازدهی بیشتر هستند. الگوریتم‌های ارائه شده در مراجع [20، 19، 18، 17، 16، 15، 14] راهکارهایی را برای زمانبندی متمرکز ارائه می‌کنند که در مدل تداخل خود، تداخل نوع دوم را در نظر گرفته و از مزایای استفاده مجدد از فضای فرکانسی17 نیز در زمانبندی بهره میبرند. در [14] و [15] به منظور افزایش کارایی زمان‌بندی طرح لایه متقابل18 آگاه از تداخلی[a25] مورد مطالعه قرارگرفته است. در این مطالعات، مسیریابی براساس یک چارچوب درختی است که در کنار آن از یک زمانبند آگاه از تداخل استفاده میشود. در [16] نیز طراحی لایه متقابل دیگری میان لایههای شبکه (مسیریابی) و MAC (زمانبندی) معرفی شده است، که به مسئله تشکیل درخت مسیریابی و زمانبندی به طور همزمان پرداخته است. در[19] مسئله زمانبندی متمرکز و تخصیص کانال برای حالتی که از چند کانال دیتا برای ارسال استفاده می‌شود، مورد توجه قرار گرفته است. اگرچه این الگوریتمها استفاده مجدد از فضای فرکانسی را بکار میبرند ولی با این حال از آنجا که به هر گره‌‌‌ اجازه داده می‌شود که در یک فریم چندین بار ارسال کند، سربار سوئیچینگ بین گره‌‌‌ها، جهت ارسال و دریافت به علت وجود سمبل‌های محافظ19 بین پنجرههای زمانی گره‌‌‌های مختلف، در نظر گرفته نشده است. در مقابل [20] زمانبندی لینکها در فریم را به یکبار محدود میکند. این فرض نیز از بکارگیری موثر استفاده مجدد از فضای فرکانسی، جلوگیری میکند. مقاله [21] تحقیق و مطالعه ی ارزشمندی است که در زمینه تضمین تأخیر انتها به انتها صورت گرفته است.تلاش‌های قبلی در راستای ارائه خدمات سرویس صرفا تلاشی برای بهبود متوسط کل تأخیر شبکه بوده و تضمینی در ارائه خدمات سرویس انتها به انتهای کاربر ارائه ‌نکرده اند.
فصول بعدی این نوشتار
ساختار پایان نامه بدین شکل تدوین یافته است: در ادامه در فصل 2 شبکه‌های مش بی‌سیم با رویکردهای مختلفی مورد بحث و چالش قرار گرفته است. در فصل 3، مشخصات فنی استاندارد 802.16 به عنوان یک نمونه شبکه‌مش بی‌سیم پرکاربرد در زمان نگارش این پایان نامه تشریح شده است. در این فصل به بررسی لایه‌های فیزیکی و MAC توصیف شده توسط استاندارد 802.16 پرداخته و در ادامه جزئیات عملکرد مد مش استاندارد تشریح شده است. مفاهیمی که در این راستا آورده شده است، از جمله ساختار فریم در مد مش، بسته‌های کنترلی و نحوه ورود گره‌‌‌های تازه وارد به شبکه، پیش زمینه‌ای برای شروع بحث زمانبندی در مد مش استاندارد هستند. در فصل 4 با مروری بر تحقیقات قبلی این زمینه سعی بر آن است کارهای قبلی که در زمینه‌ی زمان‌بندی انجام شده است در قالب چهارچوب پیشنهادی ارائه، دسته بندی و مقایسه شوند. فصل 5 الگوریتم جدیدی را برای بهبود زمانبندی متمرکز در مد مش استاندارد 802.16 ارائه می‌کند. در این فصل ابتدا فلسفه‌ی طراحی الگوریتم پیشنهادی و نحوه پیاده‌سازی آن برپایه الگوریتم ژنتیک تشریح شده و سپس با تعریف انواع سناریوها و شرایط شبیه‌سازی به ارائه نتایج حاصل از شبیه‌سازی و مقایسه الگوریتم پیشنهادی با الگوریتم‌های موجود، بر اساس معیارهای ارزیابی، پرداخته شده است. در نهایت در فصل ۶ نیز جمع‌بندی مطالب و کارهای پیشرو بیان شده است.
شبکه‌های مش بی‌سیم یکی از فناوری‌های کلیدی و تاثیرگذار طی دهه پیش رو هستند و نقش بسیار مهمی‌ در نسل‌های آتی شبکه‌های بی‌سیم و سیار ایفا خواهند کرد. به کمک این شبکه‌ها رویایی که از دیرباز در ذهن بسیاری از کاربران گوناگون انواع شبکه‌ها در سرتاسر دنیا بوده به تحقق نزدیک‌تر می‌شود؛ و این رویا چیزی نیست جز اتصال به شبکه در هر زمان و هر لحظه و با نهایت سادگی و کمترین هزینه.
شبکه‌ی مش بی‌سیم برای پاسخگویی به نیازهای روزافزون کاربران باید بتواند سطوح مختلفی از کیفیت سرویس را ارائه و با برقراری آن کیفیت‌ها را تضمین کند .منابع شبکه می‌بایست به نحوی سازمان دهی و مدیریت شود که بتواند بهره‌‌‌وری و بازدهی بالایی داشته باشد، به نحوی که احتمال عدول از شرایط تضمین شده برای سرویس و هم چنین هزینه های لازم کمینه شود. هدف اصلی این پژوهش، ارائه‌ی پیشنهادی برای تضمین کیفیت سرویس در شبکه‌های مش بی‌سیم است. سعی بر آن است الگوریتم پیشنهادی ضمن دارا بودن شرایط مقیاس پذیری و نیز قابلیت استفاده در کنار سایر الگوریتم های موجود؛ تضمین خوب، قابل قبول و تا حد ممکن دقیقی را برای پارامتر تأخیر فراهم آورد. با توجه به این که تضمین کیفیت سرویس به صورت انتها به انتها عمدتا مبتنی بر زمان‌بندی مناسب رله‌ها و گره‌‌‌ها با BS در تخصیص و رزرو کردن کانال در مسیر بین مبدا تا مقصد است، در این پژوهش تلاش شد برپایه‌ی الگوریتم‌های بهینه سازی ژنتیک، قابلیت تضمین انتها به انتهای کیفیت سرویس در شبکه‌های مش بی‌سیم را فراهم آوریم.
شبکه‌های مش بی‌سیم
چشم‌انداز
شبکه‌های مش بی‌سیم 20 (WMN) یکی از فناوری‌های کلیدی و تاثیرگذار طی دهه پیش رو هستند و نقش بسیار مهمی‌ در نسل‌های آتی شبکه‌های بی‌سیم و سیار ایفا خواهند کرد و بر اساس پیش‌بینی آقای Akyildiz شبکه‌های مش بی‌سیم در دهه آینده تمامی‌شبکه‌های بی‌سیم را تحت تاثیر خود قرارخواهد داد و به جایگزینی مناسب برای آن‌ها تبدیل خواهد شد [3و22]. به کمک این شبکه‌ها رویایی که از دیرباز در ذهن بسیاری از کاربران گوناگون انواع شبکه‌ها در سرتاسر دنیا بوده به تحقق نزدیک‌تر می‌شود؛ و این رویا چیزی نیست جز اتصال به شبکه در هر زمان و هر لحظه و با نهایت سادگی و کمترین هزینه.
شکل ‏21- شبکه‌ بی‌سیم مش[a26]
با این تفاسیر شبکه‌های WMN نقش بسیار مهمی‌در نسل بعدی اینترنت ایفا می‌کنند. توانایی خود-سازماندهی21 این شبکه‌ها به طرز چشمگیری پیچیدگی استقرار، حفظ و نگهداری شبکه را کاهش داده و در نتیجه ضمن بالا بودن قابلیت اطمینان و بهبود بخشیدن به ظرفیت شبکه، هزینه‌های متصور را نیز کاهش می‌دهد.
این شبکه‌ها مشتمل[a27] بر مسیریاب‌های مش و نیز کاربران مش می‌شوند که در آن مسیریاب‌های مش کمترین تحرک ممکن را دارند و ستون فقرات WMN را شکل می‌دهند. آنها دسترسی به شبکه را هم برای کاربران مش و هم برای کاربران عادی فراهم می‌آورند.
شکل ‏22- کاربران مش (چهار عکس سمت راست) و مسیریاب‌های مش (دو عکس سمت چپ)[3]
در شکل (2-3) نمونه ای از شبکه مش بی‌سیم پیاده سازی شده در دانشگاه جورجیا نمایش داده شده است. این شبکه مش که BWN-Mesh نامیده شده است در واقع یک شبکه backhaul مش متشکل از 15 گره‌‌‌ بر اساس استاندارد IEEE 802.11b/g است. هدف از این پیاده سازی انتقال ترافیک شبکه برای دسترسی به اینترنت است.
شکل ‏23- شبکه مش BWN-Mesh تست شده در دانشگاه جورجیا[3]
ادغام شبکه‌های WMN با دیگر شبکه‌ها مانند اینترنت، IEEE802.16، IEEE802.15، IEEE802.11، شبکه‌های حسگر و … از طریق دروازه‌ها و پُل‌های موجود در مسیریاب‎های مش امکان‌پذیر است[22]. کاربران مش هم می‌توانند ثابت و یا متحرک باشند و به خودی خود یا در کنار مسیریاب‎های مش یک شبکه کاربر مش تشکیل دهند. انتظار می‌رود شبکه‌های WMN ، محدودیت‌های شبکه‌های Ad-Hoc، WLANها، WPANها و WMANها را برطرف کرده و کارکرد آنها را بهبود بخشند.
برخلاف شبکه‌های سلولی که از کار افتادگی یک ایستگاه پایه (BS)22 در شبکه، سبب قطع شدن ارتباط در محدوده جغرافیایی بزرگی می‌شود؛ در WMN‌ها اگر حتی درکار تعدادی از گره‌های23 شبکه اختلال پیش بیاید، مابقی شبکه کماکان ارتباط خود را حفظ کرده و انتقال ترافیک توسط سایر گره‌ها صورت می‌پذیرد.[23]
یکی از مهمترین کاربردهای شبکه‌های WMN، ایجاد زیرساخت بی‌سیم برای دسترسی به اینترنت در مناطقی است که زیرساخت24 سیمی‌(فیبر نوری، زوج سیم، کابل کواکسیال و …) وجود ندارد و یا از لحاظ اقتصادی به صرفه نیست. در این مناطق از این تکنولوژی که پیاده‌سازی بسیار ارزان‌تر و سریع‌تری نسبت به همتای سیمی‌خود دارد، استفاده می‌شود[22 و23] همچنین با گسترش[a28] شبکه‌های Ad-Hoc، WMN‌ها تبدیل به یک توپولوژی مهم در تکمیل زیرساخت شبکه‌های بی‌سیم شده اند.
آزمایشها و تجربیات به دست آمده از مطالعات و پیاده سازی این شبکه‌ها، نوید دهنده تحولی بزرگ در شبکه‌های بی‌سیم آتی است. از اینرو استفاده از این تکنولوژی با توجه به توزیع و پراکندگی شهرها و روستاها در کشورمان بسیار راهگشا و مفید به نظر می‌رسد.
علی رغم این که این شبکه‌ها براساس فن آوری‌های کنونی قابل پیاده سازی هستند، ولی نمونه‌های ساخته شده مختلف نشان می‌دهند که عملکرد این شبکه‌ها پایین تر از انتظارات می‌باشد لذا طراحی مجدد لایه‌های مختلف WMN‌ها از اهمیت خاصی برخوردار می‌باشد[a29][23]. به عنوان مثال یکی از این مشکلات که در این پایان نامه نیز بدان اشاره خواهد شد بحث زمان‌بندی ارسال گره‌‌‌های شبکه است که هنوز به عنوان یک موضوع تحقیقاتی پویا نظر محققان را در این زمان به خود جلب کرده است.
طراحی مسیریاب‌های مش قابل انعطاف جهت ایجاد یک شبکه زیرساخت قابل اعتماد که مسیریابی ترافیک در کل شبکه را به نحوی مناسب انجام دهند، از اهمیت زیادی برخوردار است لذا ارائه روش‌ها و پروتکل‌هایی جهت رویارویی با ترافیک‌های محلی و گذری در مسیریاب‌های مش حائز اهمیت خواهد بود.[2 ]
توپولوژی شبکه
توپولوژی نقطه به نقطه25 (PTP)
شبکه نقطه به نقطه از یک یا چند لینک ثابت تشکیل می‌شود و در این حالت معمولا آنتن‌های گیرنده و فرستنده با سمت گرایی بالا مورد استفاده قرار می‌گیردشکل(2-4[a30]).
شکل ‏24- توپولوژی شبکه نقطه به نقطه[23]
توپولوژی نقطه به چند نقطه26 (PMP)
در حالت نقطه به چند نقطه ایستگاه مبنا(BS)، نقش مهمی‌در هماهنگ کردن و برقراری ارتباطات دارد و ایستگاه‌های مشترک27[a31] (SS) باید قبل از این که با SS‌های دیگر تبادل داده داشته باشند تحت مدیریت ایستگاه مبنا ابتدا با BS ارتباط برقرار کنند و از طریق BS با SS دیگر تبادل داده کنند. این توپولوژی شبیه معماری شبکه‌های سلولی است[23] شکل (2-5).
توپولوژی مش
این توپولوژی به طور کلی هم به صورت حلقه و هم به صورت ساختارهای شاخه ای پیاده‌سازی می‌شود. مزیت عمده این مدل این است که شبکه مش مسیرهای غیرمستقیم برای اتصال کاربرانی را فراهم می‌کند که ممکن است دچار فقدان دید مستقیم28 نسبت به BS باشند. از این طریق تعداد کاربران متصل به شبکه را افزایش می‌دهد. لذا ترافیک هر کاربر[a32] باید در بعضی مواقع از طریق چندین گره مسیردهی شود. در این توپولوژی ممکن است به گذردهی کمتری نسبت به شبکه‌های PMP دست یابیم. زیرا در شبکه‌های PMP فقط یک گام29 برای اتصال SS به BS وجود دارد ولی در عوض پوشش بیشتری در شبکه‌های مش خواهیم داشت.
در این توپولوژی برخلاف حالت PMP در ارتباط SSها تفکیک واضحی میان لینک فروسو[a33]30 و لینک فراسو31 وجود ندارد و هرSS می‌تواند به صورت مستقیم با دیگر گره‌های همسایه اش بدون کمک BS ارتباط برقرار کند. در این توپولوژی عموما یک یا چند گره نقش BS را دارند و تشکیل زیرساخت شبکه بی‌سیم را داده و شبکه مش را به شبکه‌های[a34] دیگر مانند اینترنت متصل می‌کنند. همان طور که ملاحظه می‌کنید در این توپولوژی برخلاف دو حالت قبل بین BS و SS مقصد، چند گام می‌تواند قرار بگیرد. در بخش بعد شبکه‌های بی‌سیم چندگامی‌را معرفی می‌کنیم[24].
شکل ‏26- توپولوژی شبکه ی مش[2]
شبکه‌های بی‌سیم چندگامی32
شبکه‌های بی‌سیم چند گامی‌مطابق شکل (2-7 ) عمدتا به شبکه‌های زیر تقسیم می‌شوند[23]:
شبکه‌های بی‌سیم Ad-hoc
شبکه‌های بی‌سیم حسگر
شبکه‌های مش بی‌سیم
شبکه‌های بی‌سیم‌هایبرید33
شبکه‌های Ad-hoc اساسا شبکه‌های فاقد زیرساخت هستند ک



Copyright 2018. All rights reserved.

Posted آگوست 6, 2018 by 92 in category "مقالات

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *