لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه5
بخشی از فهرست مطالب
الگوریتم، شبکههای حسگر، مسیریابی، داده ساختارهای جنبشی، کوچکترین زیر درخت فراگیر محلی
1- مقدمه
کوچکترین درخت فراگیر محلی
کوچکترین درخت فراگیر محلی با نگهداری به کمک داده ساختار جنبشی
2- پیچیدگی الگوریتم
با ظهور ارتباطات بیسیم بین عناصر مختلف و به دنبال آن مسئله شبکههای بی سیم و متحرک، توجه بسیاری از اندیشمندان رشته علوم کامپیوتر به مسائل موجود در این شبکه از قبیل مسیریابی معطوف شد. اما این شبکهها پاسخگوی تمام نیازها در زمینه ارتباطات بی سیم نبودند. به همین منظور مدل شبکههای ویژه[i] ارائه شد که در آنها ارتباطات از طریق فرستندهها و گیرندههای رادیویی با فاصله ارتباطی محدود انجام میگرفت و در ضمن ساختار یکپارچه مرکزی برای مسیریابی و مدیریت ندارند. در قدم بعدی محدودیت توان مصرفی و عملیاتی نیز به مدل فوق افزوده شد و مدل شبکه حسگر معرفی شد.
شبکه های حسگر کاربرد بسیار وسیعی دارند. مثلا حسگرهای تشخیص آتش سوزی در یک جنگل و یا شهر همچنین حسگرهای تشخیص تشعشعات هستهای در یک رآکتور هستهای، نمونههایی از این کاربردها هستند.
ویژگیهای شبکههای حسگر را میتوان به اجمال به این موارد تقسیم نمود: 1. انرژی محدود عناصر .2. پهنای باند محدود .3. شبکه بدون ساختار و متغیر با زمان .4. کیفیت پایین ارتباطات .5. قدرت محاسبات محدود در عناصر.
از جمله مسائل مطرح در زمینه شبکههای حسگر، بحث مسیریابی در این شبکهها است. الگوریتمهای متفاوتی برای این مسئله ارائه شده است. الگوریتمهای ارائه شده را میتوان به دو دسته همگن و ناهمگن تقسیم نمود. الگوریتمهای همگن فرض را بر یکسان بودن عناصر شبکه (از نظر برد فرستنده) میگذارند. الگوریتمهای ناهمگن از انعطافپذیری بیشتری برخوردار هستند. الگوریتمهای ناهمگن با توجه به اطلاعاتی استفاده میکنند به سه دسته تقسیم میشوند. 1- بر مبنای محل : در آنها محل دقیق عناصر مشخص میباشد. 2- بر مبنای جهت : در آنها فرض میشود که هر کس جهت نسبی همسایگانش را نسبت به خود میداند. 3- بر مبنای همسایه : در آنها فرض میشود که شناسه همسایهها در اختیار است.
الگوریتمهای ارائه شده را از یک منظر دیگر میتوان به دو دسته متمرکز و نامتمرکز نیز تقسیم نمود. در الگوریتمهای متمرکز، یک ناظر خارجی در سیستم وجود دارد که مسئولیت مسیریابی را به عهده دارد. البته فرض وجود چنین ناظری اولا با ماهیت شبکههای حسگر سازگار نیست در ضمن قابلیت مقیاسپذیری ندارد.
از جمله روشهای رایج در زمینه مسیریابی استفاده از درخت فراگیر کمینه است. اما به دو دلیل که در ادامه خواهیم دید، استفاده از آنها در این شبکهها محبوبیت پیدا نکرده است. اولا پیدا کردن کوچکترین درخت فراگیر یک الگوریتم ماهیتا متمرکز است و دوما به علت آنکه هزینه ساخت آن بالاست و در این شبکهها - به علت متحرک بودن عناصر - نیاز است که مرتبا این درخت ساخته شود.
در این مقاله یک الگوریتم برای مسیریابی در شبکههای حسگر بر مبنای کوچکترین درخت فراگیر ارائه میشود ولی سعی شده که مشکلات ذکر شده در بالا در آن پاسخ داده شود. برای این منظور اولا از کوچکترین درخت فراگیر محلی استفاده شده است که نیاز ناظر را از بین میبرد و همچنین از یک ساختار جنبشی برای نگهداری آن استفاده میشود که مشکل هزینه تغییرات را از بین میبرد.
در زمینه مسیریابی در شبکههای حسگر کارهای گوناگونی انجام شده است ولی در تمام آنها فرض بر ثابت بودن ساختار شبکه در طول حیات شبکه است. همچنین داده ساختارهای گوناگونی برای نگاهداری اجزای شبکه مطرح شده است ولی اکثر آنها هزینه به روز رسانی بالایی دارند و همچنین برای مسئله مسیریابی مناسب نیستند. لذا در این مقاله تلاش شد تا فرضهای مطرح شده بسیار به محیط واقعی شبیه باشند که تا زمان نوشتن این مقاله کاری با این درجه شباهت با محیط واقعی پیدا نکردیم. نتیجه حاصل نیز هزینه نگاهداری و به روز رسانی کمینهای دارد که برای حسگر های با انرژی محدود مناسب است.
در بخشهای بعدی ابتدا یک الگوریتم برای کوچکترین درخت فراگیر محلی ارائه میشود. سپس یک روش جنبشی برای نگهداری کوچکترین درخت فراگیر ارائه میشود. در ادامه الگوریتم اصلی که ترکیبی از این دو روش است معرفی میشود و بعضی خواص آن اثبات میشود . در انتها پیچیدگی الگوریتم و نتیجهگیری
مقاله در مورد کاربرد داده ساختارهای جنبشی در مسیریابی شبکههای حسگر متحرک