مسیریابی آگاهانه بار برای شبکه های مش بی سیم غیرمداوم کوچک Load-aware Routing for Non-Persistent Small-World Wireless Mesh Networks
- نوع فایل : کتاب
- زبان : فارسی
- ناشر : آی تریپل ای IEEE
- چاپ و سال / کشور: 2014
توضیحات
رشته های مرتبط: مهندسی کامپیوتر و فناوری اطلاعات، شبکه های کامپیوتری و مهندسی الگوریتم ها و محاسبات
مقدمه شبکه مش بی سیم (WMN) شامل سه نوع گره است: روتر مش دروازه، روتر مش و مش مشتری[۱]. روتر دروازه مش به سایر شبکه های ارتباطی یا اینترنتی از طریق لینک های سیمی متصل می شوند. روترهای مش بی سیم در WMN ها به عنوان گره های جزئی و یا به طور کامل ایستا اعمال می شوند در حالیکه مشتری های مش گره های پویا در شبکه هستند. WMN دارای مزایای فراوانی مانند پیش هزینه اندک، پشتیبانی آسان شبکه و تقویت در عملکرد شبکه هستند. میانگین طول مسیر (APL) که توسط فاصله پیوسته هاپ (EHD) به طورمیانگین بر روی شبکه تعریف می شود، ارزش بیشتری در متن WMN به علت توپولوژی شبکه منظم آن دارد. برای کاهش ارزش APL WMN، EHD بین منبع گره (SN) و گره مقصد (DN) باید به حداقل برسد. بنابراین، پیوندهای طولانی (LL) را می توان در میان گره های روتر دور (به عنوان موقعیت آنها عمدتا در WMN استاتیک هستند) برای کاهش APL و ترکیب ویژگی های کوچک جهان (SW) در WMNs ایجاد شده است. ویژگی های دنیای کوچک را می توان با کاهش ارزش APL در یک شبکه منظم به دست آورد. میلگرام [۲] ابتدا ویژگی های کوچک جهان را در آزمایش خود در سال ۱۹۶۷ مشاهده کرد، جایی که وی نتیجه گرفت که مردم با “شش درجه جدایی” به یکدیگر متصل می شوند، بنابراین جهان های کوچک را تشکیل می دهند. در [۳]، نویسندگان ویژگی های SW را با ایجاد چند LL توسط بازنویسی لینک های عادی (NLs) در یک شبکه منظم، حاصل شد که منجر به کاهش APL، می شود و برای ضریب متوسط خوشه کارآمد (ACC)، کمتر است که اندازه گیری گره های همسایه متصل به طور متوسط در شبکه است. در [۴] – [۱۰] نویسندگان ویژگی های SW با افزودن چند LL در شبکه ایجاد کردند. به هرحال، ایجاد استراتژی های LL مذکور با LL های ثابت یا دائمی مقابله می کنند، همانطورکه LL برای همیشه برای تمام جلسه انتقال داده در شبکه ایجاد می شود. ما در این مقاله LLs غیر پایدار (NPLLs) را بررسی می کنیم که در آن LLs به طور موقت بین گره ها ایجاد و زمانی که ترافیک از آنها تقاضا می کند. بنابراین، پس از یک دوره زمانی خاص، LLs ممکن است LL را با ایجاد ارتباط بین جفت گره های مختلف در شبکه تغییر دهند. بنابراین، برای ایجاد NPLL ها، ما آنتن های هوشمند را برای ایجاد پرتوهای هدفمند جهت اتصال به جفت گره دور در شبکه بررسی می کنیم. آنتن های هوشمند [۱۱] – [۱۴] یا آنتن های آرایه انطباق را می توان برای ردیابی دینامیکی گره های دور از طریق پردازش سیگنال هوشمند در شبکه برای ایجاد NPLLs توسط پرتو سابق بسیار هدفمند استفاده کنیم. SW-WMN ها برنامه های کاربردی را در زمینه شبکه های روستایی یا شبکه های اجتماعی پیدا می کنند. در عملکرد مناطق روستایی یا اجتماع، دسترسی به شبکه های زیربنایی یا دسترسی به آنها بسیار محدود است، بنابراین گسترش SWWMN ها می تواند ارتباط هزینه موثر را در سراسر این مناطق فراهم کند. در این مقاله الگوریتم LNPR را در زمینه SW-WMN پیشنهاد می کنیم. الگوریتم بار ترافیکی را در بین LLs و NLs بهتر توزیع می کند، به این ترتیب توازن بار در شبکه را در بر می گیرد. بقیه این مقاله به شرح زیر سازماندهی می شود. بخش دوم، الگوریتم های مسیریابی موجود برای WMN را توضیح می دهد و مشکلات را برای اجرای آنها در زمینه SW-WMN توصیف می کند. بخش سوم الگوریتم LNPR را برای SWWMN غیر قابل تنظیم توصیف می کند. در بخش چهارم نتایج عملکرد الگوریتم از لحاظ معیارهای مختلف ارائه شده است که با نتیجه گیری در بخش V دنبال می شود. مسیر در SW-WMNS: ویژگی های دنیای کوچک می تواند در WMN با اجرای چند LL در شبکه حاصل شود همانطورکه در [۵] – [۱۰]، [۱۵ [بررسی می شود. LLS در WMN می تواند به دو صورت اجرا شود. در ایجاد LL پایدار، مکان های LL در میان جفت SN و DN برای مدت زمان عمل در WMN تغییر نمی کنند. در حالی که، در ایجاد LL غیر پایدار، موقعیت خود را پس از مقدار مشخصی از زمان تغییرمی دهد. بنابراین، آنتن های هوشمند مجهز به چند روتر شبکه در WMN، پرتوهای هدفمند جهت ایجاد LL های غیر ثابت در جهت مشخص با توجه به الزامات ترافیکی ایجاد می کنند. مسیریابی برای WMN ها [۱] را می توان به دو دسته تقسیم کرد: (i) مسیریابی واکنشی [۱۷] مبتنی بر استراتژی مسیر داده بر اساس تقاضا از SN تا DN است (به عنوان مثال، Ad-hoc بر اساس بردار مسیریابی تقاضا از راه دور (AODV) [18] یا مسیریابی منبع پویا (DSR) [19] )، در حالی که (ii) در مسیریابی پیشگیرانه [۲۰]، مسیر داده ها به طور مستقل از تقاضا محاسبه می شود و اطلاعات مسیریابی در هر گره در شبکه (به عنوان مثال مسیریابی بردار فاصله توالی- مقصد (DSDV) [21] یا لینک بهینه شده مسیریابی دولتی به روز می شود. (OLSR) [22]) با این حال، این راهبردهای مسیریابی راه حل های کارآمد را برای SW-WMN ها ارائه نمی دهند شکل ۱ مثالی از وضعیت را توضیح می دهد که در آن الگوریتم های مسیریابی معمولی، LLs غیر پایدار را بارگیری می کند تا کوتاه ترین مسیر ها را در میان جفت های SN و DN در SW-WMN مبتنی بر شبکۀ نوع شناسی پیدا کنند. در شکل ۱ روترهای هوشمند (SRs) روتر های مشبک بی سیم مجهز به آنتن های هوشمند هستند که قادر به ایجاد پرتو بسیار جهت مند هستند و تغییر جهت تابش را به صورت سازگار برای ایجاد LL های غیر قابل مداوم در SW-WMN می کنند. بنابراین، برای مدت زمانی خاص، LL های غیر پایدار را می توان در میان SR ها برای انتقال بسته های داده در میان مجموعه SNs و DN در WMN ایجاد کرد. مسیریابی معمولی مانند مسیریابی حالت لینک (LSR) [23] بر اساس استراتژی حریصانه برای یافتن کوتاه ترین مسیر بین جفت SN-DN است. از این رو، برای یافتن کوتاه ترین مسیر، راهبردهای مسیریابی می توانند همان LL را بدون توجه به بار ترافیک بارگیری مجدد کنند. شکل ۱ همچنین انتقال داده ها در سه جفت SN-DN را با استفاده از استراتژی های مسیریابی معمولی در زمینه SW-WMN نشان می دهد. در شکل ۱، جلسه انتقال داده بین منطقه ۱ و منطقه ۲ ایجاد می شود که در آن بسته های داده SN1 به DN1 از طریق LL1 انتقال داده می شود که بین SR1 و SR2 ایجاد می شود. به طور مشابه، بسته های داده از SN2 به DN2 از طریق LL1 منتقل می شود. به هر حال، زمانیکه SN3 باید داده ها را به DN3 ارسال کند، LL1 دوباره برای ارسال بسته های داده به DN3 با حداقل آپ ها استفاده می شود، همانطور که در شکل ۱ نشان داده شده است. بنابراین، مسیر برای دوره انتقال داده ها در بین SN و DN مختلف ممکن است شامل LL مشابه باشد. در نتیجه ، LL ممکن است به شدت بارگیری شود، بنابراین LL ها باید به گونه ای استفاده شوند تا از بارگیری اضافی اجتناب شود. از این رو، الگوریتم های مسیریابی معمول WMN در زمینه SW-WMN کارایی ندارند. تعداد محدودی از راه حل های مسیریابی موجود در زمینه SW-WMN برای استفاده از LL ها در شبکه وجود دارد. در [۱۰]، نویسندگان الگوریتم مسیریابی تعاونی (SCR) مبتنی بر جهان – کوچک را در زمینه شبکه های بی سیم چند هاب نشان دادند، که چند گره بی سیم به نام گره های تعاونی وجود دارد، دارای قابلیت رله برای برخی از گره های تعاونی دور در شبکه هستند. گره های تعاونی به ایجاد ارتباطات طولانی مدت دور در میان جفت SN-DN با انتقال بسته های داده به DN های دور با قابلیت تعاونی یا به نزدیکترین گره های تعاونی DNs کمک می کند کند. به هر حال، اطلاعات جهانی برای اجرای مسیر یابی تعاونی در زمینه SW-WMN مورد نیاز است. علاوه بر این، گره تعاونی باید داده های خود و همسایه خود را انتقال دهند، بنابراین، پهنای باند نیاز به اجرای مسیرهای تعاونی بیشتری دارد. جیانگ و همکاران [۱۶] داده های مول یا داده های آزاد را مبتنی بر ایجاد NPLL در شبکه های بی سیم چند هاپ بررسی می کنند. داده مول که در شبکه تلفن همراه است، دارای اطلاعات مکان یابی برای مسیر سفر آن است. بسته به اطلاعات مکان DN ( یعنی اینکه آیا DN در مسیر راه عبور داده شده توسط داده مول می باشد)، بار داده مول و ارسال داده به DN یا نزدیکترین گره DN در شبکه می باشد. به هر حال، گره های روتر در WMN ها عمدتا ایستا و یا با تحرک کمتر هستند، بنابراین گره های روتر نمی توانند به عنوان LLs غیر پایدار یا دینامیکی در شبکه استفاده شوند. در این مقاله ما الگوریتم مسیریابی LL جهان کوچک غیر قابل انطباق بارآگاه (LNPR) برای SW-WMNs را ارائه می دهیم. ما تعدادی LL غیر پایدار را در میان جفت گره SR و احتمال بلوک تماس NPLL ها را در زمینه SW-WMN بررسی می کنیم.
مقدمه شبکه مش بی سیم (WMN) شامل سه نوع گره است: روتر مش دروازه، روتر مش و مش مشتری[۱]. روتر دروازه مش به سایر شبکه های ارتباطی یا اینترنتی از طریق لینک های سیمی متصل می شوند. روترهای مش بی سیم در WMN ها به عنوان گره های جزئی و یا به طور کامل ایستا اعمال می شوند در حالیکه مشتری های مش گره های پویا در شبکه هستند. WMN دارای مزایای فراوانی مانند پیش هزینه اندک، پشتیبانی آسان شبکه و تقویت در عملکرد شبکه هستند. میانگین طول مسیر (APL) که توسط فاصله پیوسته هاپ (EHD) به طورمیانگین بر روی شبکه تعریف می شود، ارزش بیشتری در متن WMN به علت توپولوژی شبکه منظم آن دارد. برای کاهش ارزش APL WMN، EHD بین منبع گره (SN) و گره مقصد (DN) باید به حداقل برسد. بنابراین، پیوندهای طولانی (LL) را می توان در میان گره های روتر دور (به عنوان موقعیت آنها عمدتا در WMN استاتیک هستند) برای کاهش APL و ترکیب ویژگی های کوچک جهان (SW) در WMNs ایجاد شده است. ویژگی های دنیای کوچک را می توان با کاهش ارزش APL در یک شبکه منظم به دست آورد. میلگرام [۲] ابتدا ویژگی های کوچک جهان را در آزمایش خود در سال ۱۹۶۷ مشاهده کرد، جایی که وی نتیجه گرفت که مردم با “شش درجه جدایی” به یکدیگر متصل می شوند، بنابراین جهان های کوچک را تشکیل می دهند. در [۳]، نویسندگان ویژگی های SW را با ایجاد چند LL توسط بازنویسی لینک های عادی (NLs) در یک شبکه منظم، حاصل شد که منجر به کاهش APL، می شود و برای ضریب متوسط خوشه کارآمد (ACC)، کمتر است که اندازه گیری گره های همسایه متصل به طور متوسط در شبکه است. در [۴] – [۱۰] نویسندگان ویژگی های SW با افزودن چند LL در شبکه ایجاد کردند. به هرحال، ایجاد استراتژی های LL مذکور با LL های ثابت یا دائمی مقابله می کنند، همانطورکه LL برای همیشه برای تمام جلسه انتقال داده در شبکه ایجاد می شود. ما در این مقاله LLs غیر پایدار (NPLLs) را بررسی می کنیم که در آن LLs به طور موقت بین گره ها ایجاد و زمانی که ترافیک از آنها تقاضا می کند. بنابراین، پس از یک دوره زمانی خاص، LLs ممکن است LL را با ایجاد ارتباط بین جفت گره های مختلف در شبکه تغییر دهند. بنابراین، برای ایجاد NPLL ها، ما آنتن های هوشمند را برای ایجاد پرتوهای هدفمند جهت اتصال به جفت گره دور در شبکه بررسی می کنیم. آنتن های هوشمند [۱۱] – [۱۴] یا آنتن های آرایه انطباق را می توان برای ردیابی دینامیکی گره های دور از طریق پردازش سیگنال هوشمند در شبکه برای ایجاد NPLLs توسط پرتو سابق بسیار هدفمند استفاده کنیم. SW-WMN ها برنامه های کاربردی را در زمینه شبکه های روستایی یا شبکه های اجتماعی پیدا می کنند. در عملکرد مناطق روستایی یا اجتماع، دسترسی به شبکه های زیربنایی یا دسترسی به آنها بسیار محدود است، بنابراین گسترش SWWMN ها می تواند ارتباط هزینه موثر را در سراسر این مناطق فراهم کند. در این مقاله الگوریتم LNPR را در زمینه SW-WMN پیشنهاد می کنیم. الگوریتم بار ترافیکی را در بین LLs و NLs بهتر توزیع می کند، به این ترتیب توازن بار در شبکه را در بر می گیرد. بقیه این مقاله به شرح زیر سازماندهی می شود. بخش دوم، الگوریتم های مسیریابی موجود برای WMN را توضیح می دهد و مشکلات را برای اجرای آنها در زمینه SW-WMN توصیف می کند. بخش سوم الگوریتم LNPR را برای SWWMN غیر قابل تنظیم توصیف می کند. در بخش چهارم نتایج عملکرد الگوریتم از لحاظ معیارهای مختلف ارائه شده است که با نتیجه گیری در بخش V دنبال می شود. مسیر در SW-WMNS: ویژگی های دنیای کوچک می تواند در WMN با اجرای چند LL در شبکه حاصل شود همانطورکه در [۵] – [۱۰]، [۱۵ [بررسی می شود. LLS در WMN می تواند به دو صورت اجرا شود. در ایجاد LL پایدار، مکان های LL در میان جفت SN و DN برای مدت زمان عمل در WMN تغییر نمی کنند. در حالی که، در ایجاد LL غیر پایدار، موقعیت خود را پس از مقدار مشخصی از زمان تغییرمی دهد. بنابراین، آنتن های هوشمند مجهز به چند روتر شبکه در WMN، پرتوهای هدفمند جهت ایجاد LL های غیر ثابت در جهت مشخص با توجه به الزامات ترافیکی ایجاد می کنند. مسیریابی برای WMN ها [۱] را می توان به دو دسته تقسیم کرد: (i) مسیریابی واکنشی [۱۷] مبتنی بر استراتژی مسیر داده بر اساس تقاضا از SN تا DN است (به عنوان مثال، Ad-hoc بر اساس بردار مسیریابی تقاضا از راه دور (AODV) [18] یا مسیریابی منبع پویا (DSR) [19] )، در حالی که (ii) در مسیریابی پیشگیرانه [۲۰]، مسیر داده ها به طور مستقل از تقاضا محاسبه می شود و اطلاعات مسیریابی در هر گره در شبکه (به عنوان مثال مسیریابی بردار فاصله توالی- مقصد (DSDV) [21] یا لینک بهینه شده مسیریابی دولتی به روز می شود. (OLSR) [22]) با این حال، این راهبردهای مسیریابی راه حل های کارآمد را برای SW-WMN ها ارائه نمی دهند شکل ۱ مثالی از وضعیت را توضیح می دهد که در آن الگوریتم های مسیریابی معمولی، LLs غیر پایدار را بارگیری می کند تا کوتاه ترین مسیر ها را در میان جفت های SN و DN در SW-WMN مبتنی بر شبکۀ نوع شناسی پیدا کنند. در شکل ۱ روترهای هوشمند (SRs) روتر های مشبک بی سیم مجهز به آنتن های هوشمند هستند که قادر به ایجاد پرتو بسیار جهت مند هستند و تغییر جهت تابش را به صورت سازگار برای ایجاد LL های غیر قابل مداوم در SW-WMN می کنند. بنابراین، برای مدت زمانی خاص، LL های غیر پایدار را می توان در میان SR ها برای انتقال بسته های داده در میان مجموعه SNs و DN در WMN ایجاد کرد. مسیریابی معمولی مانند مسیریابی حالت لینک (LSR) [23] بر اساس استراتژی حریصانه برای یافتن کوتاه ترین مسیر بین جفت SN-DN است. از این رو، برای یافتن کوتاه ترین مسیر، راهبردهای مسیریابی می توانند همان LL را بدون توجه به بار ترافیک بارگیری مجدد کنند. شکل ۱ همچنین انتقال داده ها در سه جفت SN-DN را با استفاده از استراتژی های مسیریابی معمولی در زمینه SW-WMN نشان می دهد. در شکل ۱، جلسه انتقال داده بین منطقه ۱ و منطقه ۲ ایجاد می شود که در آن بسته های داده SN1 به DN1 از طریق LL1 انتقال داده می شود که بین SR1 و SR2 ایجاد می شود. به طور مشابه، بسته های داده از SN2 به DN2 از طریق LL1 منتقل می شود. به هر حال، زمانیکه SN3 باید داده ها را به DN3 ارسال کند، LL1 دوباره برای ارسال بسته های داده به DN3 با حداقل آپ ها استفاده می شود، همانطور که در شکل ۱ نشان داده شده است. بنابراین، مسیر برای دوره انتقال داده ها در بین SN و DN مختلف ممکن است شامل LL مشابه باشد. در نتیجه ، LL ممکن است به شدت بارگیری شود، بنابراین LL ها باید به گونه ای استفاده شوند تا از بارگیری اضافی اجتناب شود. از این رو، الگوریتم های مسیریابی معمول WMN در زمینه SW-WMN کارایی ندارند. تعداد محدودی از راه حل های مسیریابی موجود در زمینه SW-WMN برای استفاده از LL ها در شبکه وجود دارد. در [۱۰]، نویسندگان الگوریتم مسیریابی تعاونی (SCR) مبتنی بر جهان – کوچک را در زمینه شبکه های بی سیم چند هاب نشان دادند، که چند گره بی سیم به نام گره های تعاونی وجود دارد، دارای قابلیت رله برای برخی از گره های تعاونی دور در شبکه هستند. گره های تعاونی به ایجاد ارتباطات طولانی مدت دور در میان جفت SN-DN با انتقال بسته های داده به DN های دور با قابلیت تعاونی یا به نزدیکترین گره های تعاونی DNs کمک می کند کند. به هر حال، اطلاعات جهانی برای اجرای مسیر یابی تعاونی در زمینه SW-WMN مورد نیاز است. علاوه بر این، گره تعاونی باید داده های خود و همسایه خود را انتقال دهند، بنابراین، پهنای باند نیاز به اجرای مسیرهای تعاونی بیشتری دارد. جیانگ و همکاران [۱۶] داده های مول یا داده های آزاد را مبتنی بر ایجاد NPLL در شبکه های بی سیم چند هاپ بررسی می کنند. داده مول که در شبکه تلفن همراه است، دارای اطلاعات مکان یابی برای مسیر سفر آن است. بسته به اطلاعات مکان DN ( یعنی اینکه آیا DN در مسیر راه عبور داده شده توسط داده مول می باشد)، بار داده مول و ارسال داده به DN یا نزدیکترین گره DN در شبکه می باشد. به هر حال، گره های روتر در WMN ها عمدتا ایستا و یا با تحرک کمتر هستند، بنابراین گره های روتر نمی توانند به عنوان LLs غیر پایدار یا دینامیکی در شبکه استفاده شوند. در این مقاله ما الگوریتم مسیریابی LL جهان کوچک غیر قابل انطباق بارآگاه (LNPR) برای SW-WMNs را ارائه می دهیم. ما تعدادی LL غیر پایدار را در میان جفت گره SR و احتمال بلوک تماس NPLL ها را در زمینه SW-WMN بررسی می کنیم.
Description
WIRELESS mesh network (WMN) consists of three types of nodes: gateway mesh router, mesh router and mesh client [1]. Gateway mesh routers are connected to other communication networks or the internet through wired links. Wireless mesh routers are deployed in the WMNs as partially mobile or fully static nodes whereas mesh clients are dynamic nodes in the network. WMNs have many advantages such as low up-front cost, easy network maintenance and robustness in network operation. Average path length (APL) which is defined by the end-to-end hop distance (EHD) averaged over the network, has greater value in the context of WMN due to its regular network topology. To reduce the APL value of the WMN, EHD between source-node (SN) and destinationnode (DN) has to be minimized. Therefore, long-links (LLs) can be established among the distant router nodes (as their positions are mostly static in the WMN) to reduce the APL and incorporate the small-world (SW) characteristics in the WMNs. Small-world characteristics can be achieved by lowering the value of APL in a regular network. Milgram [2] first observed the small-world characteristics in his 1967 experiment where he concluded that people are connected to each other with “six degrees of separation,” thus forming the smallworlds. In [3], the authors achieved SW characteristics by creating a few LLs by rewiring the normal-links (NLs) in a regular network which resulted in reduced APL, and low to moderate average clustering co-efficient (ACC), which is the measure of the connecting neighbor nodes averaged over the network. In [4]–[۱۰], the authors created the SW characteristics by adding a few LLs in the network. However, the above LL creation strategies deal with static or permanent LLs, as the LLs are established permanently for the whole data-transfer session in the network. We consider non-persistent LLs (NPLLs) in this paper where LLs are formed temporarily between nodes as and when traffic demands them. Therefore, after certain time interval, the LLs may change the directions of LL formation by creating connections among different node-pairs in the network. Therefore, to create NPLLs, we consider smart antennas to form directional beams for connecting the distant node-pairs in the network. Smart antennas [11]–[۱۴] or adaptive array antennas can be used to dynamically track the distant nodes by smart signal processing in the network to form NPLLs by highly directional beamformer. SW-WMNs find applications in the context of rural networks or community networks. In rural or community regions of operation, there are very limited access or no access of the infrastructure networks, therefore, the deployment of SWWMNs can provide cost-effective connectivity throughout such regions. In this paper, we propose LNPR algorithm in the context of SW-WMN. The algorithm better distributes the traffic load among the LLs and NLs, thus incorporate load-balancing in the network. The rest of this paper is structured as follows. Section II describes existing routing algorithms for WMN along with the difficulties to implement them in the context of SW-WMN. Section III describes LNPR algorithm for non-persistent SWWMN. In Section IV performance results of the algorithm is presented in terms of different metrics, which is followed by conclusion in Section V.
