شکل ۳-۱٫نحوه‌ی حرکت ذرات در الگوریتم PSO

شکل۳-۲٫ مراحل الگوریتم PSO

۳-۴ مراحل الگوریتم پیشنهادی

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

گام اول: در این مرحله برای تمام گره‌حسگرهای شبکه مسیر(های) بعدی مشخص می‌شود. به‌طوریکه هر گره بر اساس یک سیستم وزن‌دهی مشخص، هربار یکی از همسایگان خود را به عنوان گره‌حسگر بعدی انتخاب می‌کند. در برخی کاربردها ایستگاه اصلی به تمام گره‌حسگرها دسترسی دارد و به طور معمول اندازه‌ی این شبکه‌ها کوچک است، اما در شبکه‌های بزرگتر ایستگاه اصلی فقط به بخشی از حسگرها دسترسی دارد، بنابراین در فاز اول الگوریتم دو حالت در نظر گرفته شده است:

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

         

         

     

     

آگاهی و یا عدم آگاهی ایستگاه اصلی از مکان حسگرها ویژگی دیگری است که در این قسمت بررسی می‌شود. بنابراین دو حالت زیر ممکن است رخ دهد:
ایستگاه اصلی مکان حسگرها را می‌داند: در این حالت ایستگاه گراف شبکه را می‌‌سازد و پس از اعمال الگوریتم پیشنهادی به گراف متناظر شبکه، مسیرها را به‌دست می‌آورد و به حسگرها اطلاع می‌دهد.
ایستگاه اصلی مکان حسگرها را نمی‌داند: در این حالت از روشی استفاده می‌شود که در آن حسگرها، اطلاعاتی را به همسایگان خود ارسال کرده و فاصله نسبت به هر همسایه را به‌دست می‌آورند، سپس مجموع اطلاعات به‌دست آمده از تمامی حسگرهای در دسترس ایستگاه اصلی به ایستگاه منتقل می‌گردد. نحوه‌ی جمع‌ آوری و ارسال اطلاعات به ایستگاه اصلی به این‌صورت است که:
حسگرهایی که به ایستگاه اصلی دسترسی مستقیم دارند به عنوان لایه‌ی اول در نظر گرفته می‌شوند. این حسگرها بسته‌ی داده‌ای حاوی زمان ارسال داده را به همسایگان خود می‌فرستند. حسگرهایی که این بسته‌ی داده را دریافت می‌کنند، در صورتی که عضو لایه‌ی اول نباشند به عنوان لایه‌ی دوم در نظر گرفته می‌شوند و بر اساس زمان دریافت بسته‌ی داده می‌توانند مسافت تقریبی خود را با همسایه‌ی ارسال کننده‌ی داده محاسبه کنند. پس از اینکه لایه‌ی مربوط به تمامی حسگرهای در دسترس ایستگاه اصلی مشخص شد هر حسگر اسامی همسایگان خود و فاصله‌ی محاسبه شده تا هر یک را در قالب پیامی به ایستگاه اصلی ارسال می‌کند. نحوه‌ی ارسال نیز به این‌صورت است که هر حسگر به صورت تصادفی یکی از همسایگان لایه‌ی پایین‌تر را انتخاب می‌کند و بسته‌ی داده را به آن تحویل می‌دهد. ایستگاه اصلی بر اساس اطلاعات ارسال شده از طرف حسگرها گراف متناظر شبکه را می‌سازد و بر اساس آن در مراحل بعدی الگوریتم، مسیرها را به‌دست می‌آورد. شکل ۳-۳ یک شبکه حسگر بی‌سیم و ساختار لایه‌های تشکیل شده در این گام را نشان می‌دهد.

.شکل ۳-۳٫ ساختار لایه‌بندی حسگرهای در دسترس ایستگاه اصلی
در هردو حالت ذکرشده در بالا، در نهایت ایستگاه اصلی از ارتباطات و فاصله‌ی گره‌ها از همسایگانشان آگاه می‌شود. در گام بعدی، برای هر گره، گره(ها)ی بعدی مشخص می‌گردد. انتخاب یک گره از میان مجموعه‌ی همسایگان مشخص شده در مرحله‌ی قبل، بر اساس یک سیستم وزن‌دهی پویا و مطابق با تغییرات شبکه صورت می‌گیرد. در نهایت هر گره‌ی ‌حسگر می‌تواند هزینه‌ی مربوط به یال‌های منتهی به همسایگانش را محاسبه کند و مسیری را انتخاب کند که هزینه‌ی کمتری دارد.
درالگوریتم پیشنهادی این پژوهش برای هریال i وزن Wi در نظر گرفته شده است که این وزن از رابطه‌ی (۵) به‌دست می‌آید:
W_i =k S_i + r R_i + m d_i (۵)
Si تعداد همسایگان رأس مقصد یال i را نشان می‌دهد، Ri میزان انرژی مصرف شده در رأس مقصد یال i را نشان می‌دهد وdi فاصله‌ی بین دو رأس یال i می‌باشد. هر سه مقدار Ri، Siو di نرمال شده‌اند به طوریکه هریک مقادیری در بازه‌ی ]۱٫٫۰[ دارند. k،r وm ضرایب ثابتی هستند که اگر به صورت مناسبی محاسبه شوند تأثیر قابل توجهی بر نتایج نهایی الگوریتم خواهند داشت. میزان انرژی باقیمانده بیانگر تاریخچه‌ای از میزان کارکرد یک گره است و میزان مصرف آن را می‌رساند، تعداد همسایگان گره می‌تواند میزان مصرف گره در آینده را نشان دهد و در نهایت فاصله دو گره هزینه‌ای است که تاثیر قابل توجه‌ای بر انرژی گره‌ی فرستنده دارد.
به طورمعمول در ایستگاه اصلی محدودیت انرژی مطرح نیست و ایستگاه از قابلیت پردازشی نرم‌افزاری و سخت‌افزاری بسیار بالاتری نسبت به گره‌حسگرها برخوردار است. انتخاب بهینه‌ی ضرایب ثابت تساوی (۵) نیاز به جستجو در یک فضای جستجوی بزرگ دارد. استفاده از الگوریتم‌های هوش مصنوعی برای یافتن این ضرایب مناسب است، به‌طوری که می‌توان شبکه را قبل از شروع به کار در محیط واقعی، در ایستگاه اصلی شبیه‌سازی کرد و ضرایب را به‌دست آورد. پس از محاسبه‌ی ضرایب، نتایج به دست آمده به اطلاع گره‌ها خواهد رسید. ارسال ضرایب به دست آمده به گره‌ها با توجه به دسترسی ایستگاه اصلی به حسگرها هزینه‌ی اندکی دارد. پس از ارسال نتایج به گره‌‌حسگرها، مراحل بعدی الگوریتم پیشنهادی به صورت توزیع شده در حسگرها اجرا خواهد شد .گامهای بعدی الگوریتم که برای تمامی شرایط یکسان خواهد بود، در ادامه‌ی همین فصل ارائه شده است.
پس از اجرای گام اول الگوریتم، تمام گره‌هایی که در دسترس ایستگاه اصلی هستند از نتایج آن مطلع خواهند شد. هر گره برای انتخاب گره‌ی بعدی، سه پارامتر فاصله، تعداد همسایه‌ی گره مقصد ومیزان انرژی مصرف شده را در نظر می‌گیرد. با توجه به اینکه وزن‌های تساوی (۵) نزدیک به مقدار بهینه و در جهت افزایش عمر شبکه هستند و همچنین با توجه به اینکه تمام گره‌ها بر اساس این سیستم وزن‌دهی عمل می‌کنند، در نهایت عمر شبکه به‌صورت قابل قبولی افزایش می‌یابد.

• • ایستگاه اصلی به بخشی از گره‌حسگرها دسترسی دارد: در این حالت نیز بر اساس آگاهی و یا عدم آگاهی ایستگاه اصلی از مکان گره‌حسگرها دو حالت ممکن است صورت ‌گیرد:

• • ایستگاه اصلی مکان همه‌ی گره‌حسگرها را می‌داند: در این حالت ایستگاه اصلی می‌تواند شبکه را شبیه‌سازی کرده و بر اساس تساوی (۵) مسیر بعدی هر ‌گره‌حسگر را مشخص نماید. سپس آن دسته از حسگرهایی که توسط ایستگاه اصلی قابل دسترسی هستند، به‌صورت مستقیم وزن‌های محاسبه شده در ایستگاه اصلی را دریافت می‌کنند و گره‌حسگرهایی که دردسترس ایستگاه اصلی نیستند از وزن‌هایی استفاده می‌کنند که قبلاً محاسبه شده‌اند. در بیشتر کاربردها، با توجه به اینکه مقصد همه‌ی اطلاعات گزارش شده توسط حسگرها ایستگاه اصلی است، بنابراین مصرف انرژی در گره‎‌حسگرهای نزدیک به ایستگاه بیشتراست. بر همین اساس گره‌حسگرهایی که به صورت مستقیم در دسترس ایستگاه اصلی نیستند اهمیت کمتری از نظر مصرف انرژی دارند و از وزن‌هایی استفاده می‌کنند که قبلاً محاسبه شده‌اند.

• • ایستگاه اصلی مکان گره‌حسگرها را نمی‌داند: در این حالت گره‌حسگرهایی که در دسترس ایستگاه اصلی هستند ساختار لایه‌ای که درقسمت قبل بیان شد را تشکیل می‌دهند و اطلاعات خود را به سوی ایستگاه اصلی ارسال می‌کنند. ایستگاه اصلی بر اساس اطلاعات ارسال شده از سوی حسگرها وزن‌های تساوی (۵) را محاسبه کرده و به حسگرهای در دسترس خود اطاع می‌دهد. حسگرهای خارج از دسترس ایستگاه اصلی نیز از وزن‌های که قبلاً محاسبه شده است استفاده می‌کنند.

سوالاتی که در این قسمت مطرح می‌شوند عبارتند از:
آیا وزن‌هایی که قبلاً محاسبه شده‌اند برای شبکه‌های دیگر نیز کارایی دارند؟
اندازه‌های متفاوت شبکه‌ها و نرخ‌های متفاوت گزارشات گره‌حسگرها بر مقادیر وزن‌های تساوی (۵) تأثیر گذاراست؟
افزایش نرخ گزارشات گره‌حسگرها به معنای افزایش مصرف انرژی در تمامی گره‌حسگرها است. اما در این شرایط نیز نرخ افزایش مصرف انرژی در گره‌حسگرهای نزدیک به ایستگاه اصلی و گره‌‌حسگرهایی که تعداد همسایه‌ی بیشتری نسبت به سایر گره‌ها دارند بیشتر خواهد بود. بنابراین وزن‌های به‌دست آمده در شبیه‌سازی‌هایی که نرخ‌گزارش متفاوتی دارندکارایی خود را حفظ می‌کنند، چون بر اساس میزان انرژی باقیمانده، فاصله و تعداد همسایه محاسبه شده‌اند. با توجه به جدول۵-۱ که در فصل چهارم آمده است، نرخ تولید گزارشات و اندازه‌ی شبکه تأثیر ناچیزی بر وزن‌های محاسبه شده‎ی تساوی(۵) دارد. بنابراین اگر درکاربردی شرایط شبیه‌سازی و اجرای الگوریتم‌های تکاملی وجود نداشت، می‌توان از وزن‌هایی که قبلاً محاسبه ‌شده‌اند استفاده کرد.
گام دوم: پس از مشخص کردن مسیرها برای تمام گره‌حسگرها، در مرحله‌ی بعدی نحوه‌ی ارتباط گره‌حسگرها برای مطلع کردن همسایگان خود از میزان انرژی مصرف شده مشخص می‌شود. با هربار ارسال بسته‌ی داده، از انرژی حسگر کاسته می‌شود، اما فرستادن پیامی حاوی میزان انرژی باقیمانده در گره‌حسگر پس از هربار ارسال هزینه‎‌ی زیادی دارد و عمر گره‌حسگرها را کاهش می‌دهد. وقتی گره‌ای دورترین همسایه‌ی خود را به عنوان گره‌ی بعدی انتخاب می‌کند، دیگر همسایگان گره نیز از این انتقال داده آگاه می‌شوند و پارامتری که در تساوی (۵) بیانگر میزان انرژی مصرف شده‌ در همسایه است در همه‌ی همسایگان به‌روز ‌می‌شود. با توجه به اینکه ممکن است در یک بازه‌ی زمانی، دورترین همسایه انتخاب نشود روشی جایگزین ارا‌ئه شده است که در ادامه بررسی می‌شود.
میزان مصرف انرژی حسگرهایی که در همسایگی یک‌دیگر قرار دارند نزدیک به‌هم است. بنابراین هر حسگر بر اساس میزان مصرف انرژی خود می‌تواند مصرف انرژی همسایگان خود را تخمین بزند. با توجه به اینکه حسگری که همسایه‌ی بیشتری دارد احتمال مصرف انرژی بیشتری نیز خواهد داشت از رابطه‌ی (۶) برای تخمین میزان مصرف انرژی همسایگان حسگر jاستفاده می‌شود:
CE_i ≈( n_i / n_j) * CEj (6)
در رابطه (۶) CE_i میزان انرژی مصرف شده‌ی حسگر iرا نشان می‌دهد که در همسایگی حسگر j قرار دارد. n_i تعداد همسایگان حسگر iو n_j تعداد همسایگان حسگر jرا نشان می‌دهد. Cej نیز میزان انرژی مصرف شده در حسگرi است.
برای مقابله با این کاهش دقت، هر بار که حسگری دورترین همسایه‌ی خود را به عنوان گره‌ی بعدی انتخاب می‌کند، میزان انرژی باقیمانده‌ی خود را در بسته‌ی داده قرار می‌دهد و همه‌ی همسایگان خود را از مقدار واقعی انرژی خود با خبر می‌سازد. در صورتی‌که در یک بازه‌ی زمانی مشخص حسگری دورترین همسایه‌ی خود را انتخاب نکند، پیغامی حاوی میزان انرژی باقیمانده‌ی حسگر به دورترین همسایه می‌فرستد و بدین وسیله همه‌ی همسایگان خود را از میزان انرژی واقعی خود مطلع می‌سازد.
در برخی شرایط ممکن است گره‌ی حسگرهمواره از میان همسایگان خود حسگری را انتخاب کند که فاصله‌ی بیشتری از ایستگاه اصلی دارد، بنابر این در هر بسته‌ی داده، سه بیت کنترلی منظور شده است. سه بیت کنترلی در واقع شمارنده‌ای سه بیتی می‌باشد که هر بار که حسگری همسایه‌ی دورتر از خود نسبت به ایستگاه اصلی را انتخاب می‌کند، یک واحد افزایش می‌یابد. در صورتی که این روال چندین بار تکرار شود و شمارنده به مقدار مشخص ‌شده‌ای برسد، از تکرار مجدد این سناریو خود‌داری می‌کند.