دانلود رایگان ترجمه مقاله مسیریابی در شبکه های حسگر بی سیم (ساینس دایرکت – الزویر 2015)

مبتدی (مناسب برای درک مفهوم کلی مطلب) 

راه‌حل‌های NP-hard شامل جستجو در فضاهای گسترده می‌باشد. روش هوشمند ازدحامی نیز موفقیت بسیاری را در این‌گونه مسائل به دست آورده است.
بهینه‌سازی ازدحام ذرات (PSO) بر اساس روش‌های بهینه‌سازی می‌باشد. الگوریتم PSO مزایای زیادی در مقایسه با سایر الگوریتم‌ها مثل الگوریتم ژنتیک که دارای مراحل پردازشی بالایی است، دارد (Guo and Zhang, 2014). مزایای PSO شامل سهولت پیاده‌سازی سخت‌افزاری و نرم‌افزاری می‌باشد. همچنین کیفیت بالا داشته و توانایی عبور از نقاط بهینه محلی و یافتن نقطه بهینه سراسری را دارا می‌باشد (Kulkarni and Venayagamoorthy,2011; del Valle et al., 2008). از آنجا که حل مسائل NP مشکل بوده و الگوریتم PSO در حل آن می‌تواند مورد استفاده قرار گیرد. بنابراین PSO برای انتخاب CH به وسیله پروتکل خوشه تمرکز انتخاب شد. بنابراین، الگوریتم بهینه‌سازی ساده دارای بهره وری شبکه‌ی بیشتری است. این‌ها دلایلی برای انتخاب الگوریتم PSO برای خوشه‌بندی WSN ها هستند.

1.2. اظهارنظر نویسندگان
در این مقاله، ابتدا، ما دو فرموله بندی برنامه‌نویسی خطی (LP) برای خوشه‌بندی و مسئله مسیریابی ارائه می‌کنیم. سپس، دو پروتکل مبتنی بر PSO مسئله‌ی انتخاب CH که در بالا ارائه شد را به وسیله انتخاب گره‌هایی با انرژی بالا، پوشش شبکه و قابلیت اطمینان در انتقال شبکه به عنوان سرخوشه حل می‌کنند.
سپس، پروتکل مسیریابی مبتنی بر PSO، بهینه‌ترین مسیر درختی را انتخاب که CH ها و BS ها را به هم متصل می‌کنند، انتخاب می‌کنند. برای مسیریابی، ذرات، هوشمندانه کدگذاری می‌شوند تا کامل‌ترین مسیر درختی را بیایند. تابع fitness متفاوتی نیز برای ایجاد تعادل بین کارایی انرژی و کیفیت لینک درخت ساخته‌شده مورد استفاده قرار می‌گیرد.
علاوه بر این، ما پروتکل تنظیمات شبکه واقعی را توسعه داده‌ایم. هیچ فرضیاتی درباره مکان گره‌ها یا محدوده انتقال آن‌ها وجود ندارد. پروتکل با استفاده از مدل انرژی مصرفی واقعی و براساس ویژگی‌های فرستنده و گیرنده رادیویی مورد آزمایش قرار گرفت. شبیه‌سازی گسترده‌ای در 90 مدل همگن و ناهمگن شبکه‌های WSN ارزیابی و در برابر 7 پروتکل موجود با استفاده از معیارهای عملکرد متوسط مصرف انرژی، نرخ تحویل بسته (PDR)، توان و پوشش و پوشیدگی شبکه مقایسه گردید. اهداف اصلی ما در این مقاله می‌تواند به صورت زیر خلاصه گردند:
• ارائه دو فرموله بندی PSO برای مسئله خوشه‌بندی و مسیریابی
• ارائه پروتکل خوشه‌بندی مبتنی بر PSO با تعادل بین بهره وری انرژی و پوشش شبکه و قابلیت اطمینان انتقال
• پروتکل مسیریابی مبتنی بر PSO با رمزگذاری ذرات برای حل مشکل و یافتن درخت مسیریابی کامل و همچنین توابع هدف مناسب
• بررسی نتیجه استفاده از تنظیمان شبکه و نداشتن فرضیاتی در مورد مکان گره‌ها
• بررسی تأثیر انرژی مصرفی و ارتباط آن با خوشه‌بندی برای WSN ها
• شبیه‌سازی پروتکل پیشنهادی برای نشان دادن عملکرد آن در برابر برخی پروتکل‌های موجود همگن و ناهمگن دیگر.
ادامه مقاله به صورت زیر سازمان‌دهی شده است. بخش 2 راه‌کارهای پیشین در مورد پروتکل‌های خوشه‌بندی را بررسی می‌کند. بخش 3، یک مرور کلی از الگوریتم بهینه‌سازی ذرات را ارائه می‌دهد. مدل سیستم در بخش 4 نشان داده‌شده است. در بخش 5، ما فرموله بندی LP خود را برای دسته‌بندی مشکلات مسیریابی ارائه کرده‌ایم. بخش 6، جزئیاتی را در مورد پروتکل ارائه می‌دهد. در بخش 7، ما نتایج آزمایش‌ها را آورده‌ایم. بخش 8، شامل نتیجه‌گیری و تعدادی کار آتی می‌باشد.

2. راه‏کارهای پیشین
روش‌های خوشه‌بندی به طور گسترده به منظور بهبود عملکرد WSN ها مورد مطالعه قرار گرفته است (Tyagi and Kumar, 2013; Younis et al., 2006;Abbasi and Younis, 2007). ما تعدادی از راه‌کارهای پیشین را براساس روش‌های اکتشافی و فرا اکتشافی مورد بررسی قرار داده‌ایم.

2.1. روش‌های اکتشافی
خوشه‌بندی سلسله مراتبی انرژی پایین (LEACH) () یکی از اغلب الگوریتم‌های مسیریابی مبتنی بر خوشه‌بندی توزیع‌شده در WSN ها است که روش‌هایی تأثیرگذار در طول عمر شبکه می‌باشند. هر گره، از یک الگوریتم تصادفی در هر دور برای تعیین اینکه آیا در این دور باید به عنوان یک CH باشد یا خیر، استفاده می‌کند. گره‌هایی که به عنوان CH بودند، مجدداً نمی‌توانند در دور P به عنوان CH انتخاب گردند و P درصد مورد نیاز برای ایجاد سرخوشه است. بنابراین، هر نود دارای احتمالی برابر با 1/P است که به عنوان سرخوشه در هر دور انتخاب گردد. CH ها، بدون بررسی انرژی باقیمانده یا ویژگی‌های دیگر انتخاب می‌شوند. این مکانیزم تصادفی در انتخاب سر خوشه‌ها، توزیع خوشه‌ها در شبکه را تضمین نمی‌کند (Arboleda and Nasser, 2006).
خوشه‌بندی توزیع‌شده هیبریدی (HEED) (Younis and Fahmy, 2004) پروتکل خوشه‌بندی دیگری است که از روش LEACH به دست آمده است. تشکیل خوشه‌بندی با یک روش تکراری می‌باشد. انتخاب سرخوشه در این پروتکل براساس انرژی هر گره می‌باشد. برای افزایش بهره وری انرژی و افزایش طول عمر شبکه، یک پارامتر خوشه‌بندی ثانویه با نام “هزینه‌های ارتباطی” معرفی شده است که می‌تواند عملکرد نزدیکی همسایه‌ها و تراکم خوشه‌ها را بررسی نماید. اهداف اصلی HEED، توزیع مصرف انرژی در طول عمر شبکه و به حداقل رساندن انرژی در طول عمر و کاهش سربار کنترل شبکه می‌باشد. بهبود LEACH این است که HEED می‌تواند به طور مساوی در منطقه حاوی سر خوشه‌ها توزیع گردد.
طرح خوشه‌بندی مبتنی بر بهره وری انرژی (EECS) ((Ye et al., 2005 یک پروتکل توزیع‌شده غیرتکراری خوشه‌بندی است. EECS الگوریتم LEACH را به وسیله تغییر اندازه خوشه‌ها براساس فاصله خوشه از ایستگاه پایه، توسعه می‌دهد. برخلاف LEACH، سرخوشه به وسیله رقابت محلی و بدون تکرار مراحل انتخاب می‌شود و این امر باعث تفاوت آن با LEACH شده است. این رقابت منجر به این می‌شود که تمامی کاندیداها، انرژی باقی‌مانده خود را به همسایگان خود ارسال همه پراکن می‌کنند. اگر یک گره نتواند گره دیگری را با انرژی باقیمانده بیشتر بیابد، آن به عنوان سرخوشه انتخاب می‌گردد. به هر حال، پروتکل EECS ویژگی‌های ساختاری توپولوژی شبکه را بررسی نمی‌کند و بنابراین سر خوشه‌ها براساس انتخاب انرژی خواهند بود. علاوه براین، مجموعه‌ی گره‌های کاندید در رقابت به طور تصادفی قبل از شروع رقابت انتخاب می‌شوند، در نتیجه این مورد به عنوان انتخاب سرخوشه غیر بهینه شهرت دارد.
درحالی‌که طرح‌های بالا به عنوان شبکه‌های بی‌سیم همگن طبقه‌بندی می‌شوند. چندین طرح دیگر در دسته ناهمگن که در آن انرژی دارای عدم تجانس و ناهمگن می‌باشد، بررسی شده است.
Kumar et al. (2009)، یک طرح خوشه‌بندی همگن و دارای کارایی انرژی را برای wSN ها (EEHC) برای مطالعه تأثیر ناهمگنی گره‌ها در میزان مصرف انرژی در شبکه‌های خوشه‌بندی ارائه کردند. آن‌ها فرض کردند که درصد جمعیت گره‌های حسگر برابر با انرژی مصرفی گره‌های موجود در شبکه است. سه نوع از سنسور نودها با سطح انرژی متفاوتی مورد استفاده قرار گرفتند. گره‌ها در مرحله اول به عنوان گره‌های استاندارد شناخته می‌شوند. در سطح دوم، گره‌ها، به عنوان گره‌های پیشرفته و در سطح سوم به عنوان سوپر رگه‌ها شناخته می‌شوند. آن‌ها نشان می‌دهند که چطور فرآیند انتخاب سرخوشه باید به صورت مناسبی انجام گیرد، وقتی با شبکه‌های ناهمگن کار می‌کنند. احتمال انتخاب سر خوشه‌ها توسط انرژی اولیه و وزن هر گره نسبت به دیگر گره‌ها در شبکه می‌باشد.
مانند EEHC، پروتکل LEACH ناهمگن پیشرفته، برای افزایش طول عمر شبکه‌های حسگر بی‌سیم (EHE-LEACH) (Tyagi et al., 2013) در انتخاب CH در شبکه‌های ناهمگن کارهایی را انجام می‌دهد که دارای دو تفاوت اساسی با حالت همگن می‌باشد. اولاً، نویسنده، دو سطح برای نودهای ناهمگن در نظر می‌گیرد، گره‌ها در زیر سطح اول به عنوان گره‌های نرمال و استاندارد شناخته می‌شوند و گره‌ها در سطح دوم به عنوان گره‌های پیشرفته می‌باشند. دوما، یک آستانه فاصله ثابت توسط هر گره برای ارتباط مستقیم بین BSها و خوشه‌ها انتخاب می‌شود. گره‌های حسگر که در نزدیکی BS باشند، داده‌های خود را به طور مستقیم به BS ها ارسال می‌کنند و کسانی که دورتر از BS هستند، از ارتباطات مبتنی بر خوشه‌بندی استفاده می‌کنند.
کومار (2014) دو پروتکل توزیع‌شده ارائه کرد، پروتکل خوشه‌بندی کارای انرژی تک گامه (S-EECP) و پروتکل خوشه‌بندی کارای انرژی چندگامه (M-EECP). او همچنین با گره‌ها به صورت گره‌های همگن رفتار کرد. S-EECP از وزن یکسانی با احتمال موجود در EEHC استفاده می‌کند و دارای سه نوع سطح گره یکسان با آن است. به هر حال، آن‌ها انرژی گره‌ها را محاسبه کرده و در احتمال وزن آن‌ها دخالت می‌دهند. آن‌ها مشاهده کردند که در ارتباطات تک گامه که بسته‌های داده به طور مستقیم به BS ها بدون وابستگی به سایر گره‌ها منتقل می‌شوند. گره‌هایی که دورتر از BS قرار می‌گیرند، دارای انرژی مصرفی بیشتری هستند، زیرا برای انتقال بسته‌ها، باید مسیر بیشتری را طی کنند و این گره‌ها، ممکن است در مراحل اولیه بمیرند. آن‌ها این مسئله را در M-EECP به وسیله استفاده از ارتباطات چندگامه با BSها حل کردند. M-EECP از یک روش حریصانه برای حل مسئله کوتاه‌ترین مسیر منفرد استفاده می‌کند تا کوتاه‌ترین مسیر را از هر CH تا BS بیاید. اگرچه، S-EECP، در بهره وری انرژی، از EECH پیشی گرفته است، فرضیات بر این اصل استوار است که هر گره، سطح انرژی تمام گره‌های دیگر را می‌داند. علاوه بر این، M-EECP از مسئله S-EECP و فرضیات اینکه مکان گره‌ها از قبل مشخص نیست، بهره می‌گیرد.