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

( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

الگوریتم‌های توزیع شده: این الگوریتم‌ها به‌صورت توزیع شده در کل شبکه اجرا می‌گردند و گره‌ها برای ارتباط با یکدیگر از انتقال‌ پیام^[۲۵] استفاده می‌کنند.
الگوریتم‌های مبتنی برمکان: در این روش هر گره از محیط نزدیک خود اطلاعات محدودی به‌دست می‌آورد و سپس بر اساس این اطلاعات الگوریتم را اجرا می‌کند.
هریک از این روش های مسیریابی به شرایط خاص خود نیاز دارند. برای مثال الگوریتم‌های توزیع شده نیاز به ارتباط مناسب هر دو گره دارند، الگوریتم‌های مبتنی بر مکان وابسته به کارایی روش‌هایی هستند که اطلاعات جغرافیایی محلی را فراهم می‌کنند.

۳-۲ مفروضات در نظر گرفته شده درشبیه‌سازی

در این پژوهش برای بیان ویژگی‌های شبکه و نحوه‌ی کار الگوریتم پیشنهادی فرض‌هایی در نظر گرفته شده است که در ذیل به آنها اشاره شده است.

• • برای نمایش شبکه، گراف بدون جهتG(N,A) در نظر گرفته شده است که در آن N مجموعه‌ی تمام گره‌ها وA مجموعه‌ی تمام ارتباطات بین گره‌ها است. هر ارتباط به صورت(i,j) نمایش داده شده است وi,j ϵ N .

• • f_i مجموعه‌ی گره‌هایی است که از گره‌ی i قابل دسترسی هستند.

• • مقصد نهایی تمام اطلاعات به‌دست آمده ازمحیط ایستگاه اصلی است.

• • یک ایستگاه اصلی وجود دارد.

• • میزان انرژی هر گره در ابتدای قرار گرفتن در شبکه و شروع کار آن E_i است.

• • برای محاسبه‌ی میزان انرژی مصرف شده توسط هر گره‌ی حسگر، مدل انرژی رابطه‌ی(۱)، در نظر گرفته شده است]۲۷[. در این مدل، انرژی لازم E_Tx برای فرستادن l بیت داده به مسافت d به‌صورت رابطه‌ی (۱) می‌باشد.

E_Tx (l,d) =
lE_elec + lε_fsd² , d<d₀
lE_elec + lε_mp d⁴ , d>d₀
(۱)
همچنین انرژی لازم E_Rx برای دریافت l بیت داده از رابطه‌ی(۲) محاسبه می‌شود:
E_Rx (l) = lE_elec (۲)
در این روابطε_fs و ε_mp انرژی تقویت کننده‌ها^[۲۶] هستند و در کاربردهای مختلف متفاوتند. d₀ فاصله‌ی معینی است که با توجه به نوع حسگر مشخص می‌شود.

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

• • زمان‌محور^[۲۷]: هر گره با نرخ ثابت و مشخصی اطلاعات به‌دست آمده از محیط را گزارش می‌کند.

• • رویداد‌محور^[۲۸]: گره زمانی داده‌های خود را ارسال می‌کند که توسط یک رویداد خاص تحریک شود.

• • درخواست‌محور^[۲۹]: زمانی داده ارسال می‌شود که ایستگاه اصلی و یا گره‌ی دیگری درخواست اطلاعات کند.

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

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

• • محیط قرار گیری گره‌حسگرها به صورت دو بعدی در نظر گرفته شده است.

شکل?. لایه‌های معماری شبکه‌های حسگر بی‌سیم

۳-۳ الگوریتم PSO

در روش ارائه شده در این فصل از الگوریتم PSO^[30] استفاده شده است، بنابراین قبل از ارا‌ئه‌ی جزئیات روش پیشنهادی، الگوریتم PSOبه‌طور مختصر بررسی خواهد شد. Kenedy و Eberhart ]29،۳۰[ در سال ۱۹۹۷ الگوریتم PSO را معرفی کردند. این الگوریتم اولین بار برای شبیه‌‌سازی شبکه‌های اجتماعی استفاده شد. PSO از خانواده‌ی الگوریتم‌های تکاملی محسوب می‌شود و شباهت زیادی به الگوریتم ژنتیک دارد.
بر اساس نتایج به‌دست آمده در ]۳۲ ،۳۱[، برای مسائل پیوسته جوابهای به‌دست آمده از الگوریتم PSO نسبت به دیگر الگوریتم‌های تکاملی به مقدار بهینه نزدیکتر است واز نظر زمانی نسبت به روش های دیگر هزینه‌ی کمتری دارد.
الگوریتم PSO در ابتدا تعدادی از جواب‌های منتخب (و به‌طور معمول تصادفی و در یک بازه‌ی مشخص) را در نظر می‌گیرد. در این روش به هر جواب منتخب ذره^[۳۱] گفته می‌شود. این ذرات با یکدیگر در ارتباط هستند و پس از ارزیابی توسط یک تابع شایستگی^[۳۲] به سمت جواب بهینه حرکت می‌کنند. این روال با توجه به تعداد تکرارهای مشخص شده ادامه می‌یابد. مکان هر ذره بر اساس بردار شتاب‌‎^[۳۳] به‌دست آمده از تساوی (۳) تغییر می‌کند و تساوی (۴) تابع حرکت ذرات را نشان می‌دهد. همچنین شکل‌های ۳-۱ و۳-۲ به ترتیب بیانگرنحوه‌ی حرکت ذرات و مراحل الگوریتمPSO هستند.

(۳)
در تساوی (۳)، w ضریب سکون^[۳۴] ،c1 ضریب اعتماد محلی و c2 ضریب اعتماد سراسری را نشان می‌دهد. rand ( pi – xik)/ میزان تاثیر از بهترین ذره‌ی محلی و rand ( Pgk – xik)/ میزان تاثیر از بهترین ذره‌ در کل جمعیت است.
Xⁱ_k+1 = xⁱ_k + vⁱ_k+1 t (۴)
در تساوی (۴)، Xik+1 مکان بعدی ذره را نشان می‌دهد و xik بیانگر مکان فعلی ذره است.
ورژن‌های مختلفی از الگوریتم PSO معرفی شده اند. در ورژن استاندارد w در بازه‌ی ]۰٫۴ تا ۱٫۴ [، c1 در بازه‌ی ]۱٫۵ تا ۲[ و c2 در بازه‌ی] ۲ تا ۲٫۵[ قرار دارد.