ساختارهای جنبشی در مسيريابی شبکههای حسگر متحرک 5 ص - word (..doc) - عمران -

قسمتی از متن :

‏کاربرد ‏داده ساختارها‏ی‏ جنبش‏ی‏ در‏ مسيرياب‏ی‏ ‏شبکه‌‏ها‏ی‏ حسگر متحرک

‏کاميار رفعت‏ی‏ ‏دانشجوی کارشناسی ارشد مهندسی نرم‏‌‏افزار، دانشگاه صنعتی شريف، دانشکده‏‌‏ی کامپيوتر، rafati@ce.sharif.edu

‏، ‏نعيم اصفهان‏ی‏ ‏دانشجوی کارشناسی ارشد مهندسی نرم‏‌‏افزار، دانشگاه صنعتی شريف، دانشکده‏‌‏ی کامپيوتر، esfahani@ce.sharif.edu

‏، ‏محمد قدسی‏ ‏استاد‏، ‏دانش‏گاه صنعتی شريف، دانشکده‏‌‏ی کامپيوتر، ghodsi@sharif.edu

‏چكيده

‏يک‏ی‏ از موضوعات مطرح در طراح‏ی‏ الگوريتم‌ها بحث شبکه‌ها‏ی‏ حسگر م‏ی‏‌‏باشد‏. اين شبکه‌ها متشکل از مجموعه‌ا‏ی‏ از واحدها‏ی‏ متحرک و مستقل از هم با توان مصرف‏ی‏ و پردازش‏ی‏ محدود ‏است‏ ‏که از طريق فرستنده‌ها‏ی‏ راديوي‏ی‏ با يکديگر در ارتباطند و اقدام به جمع‌آور‏ی‏ اطلاع‏ات‏ م‏ی‏‌‏نمايند‏. مساله‌‏ی‏ مسيرياب‏ی‏ در اين شبکه‌ها به گونه‌ا‏ی‏ که حداقل انرژ‏ی‏ مصرف شود، از دسته مسائل غير چند جمله‏‌‏ا‏ی‏ سخت ‏می‏‌‏باشد‏ که ارائه راه حل‌ها‏ی‏ تقريب‏ی‏ مناسب موضوع ‏برخي‏ ‏از تحقيقات در اين زمينه است. در بيشتر مدل‌ها‏ی‏ ارائه شده فرض بر ثابت بودن حسگرها ا‏ست؛‏ در اين مقاله سع‏ی‏ م‏ی‏‌‏شود‏ الگوريتم‏ی‏ برا‏ی‏ مسيرياب‏ی‏ در شبکه‌‏ی‏ حسگرها‏ی‏ متحرک ارائه شود. با توجه به ماهيت جنبش‏ی‏ اين شبکه‏‌‏ها ، استفاده از داده ساختارهايي که بتواند ساختار زير درخت فراگير را به صورت بهينه نگاهدار‏ی‏ نمايند بسيار سودمند است. در اين تحقيق از داده ‏ساختار‏ جنبش‏ی‏ برا‏ی‏ نگاهدار‏ی‏ زير درخت فراگير استفاده ‏شد‏ه است‏. ‏در اين مقاله اين روش ارايه و بررسی می‏‌‏شود و نشان می‏‌‏دهيم‏‌‏ که‏ ‏باعث کاهش پيچيدگی محاسبات‏ی مسيريابی در اين شبکه‏‌‏ها می‏‌‏شود.

‏كلمات كليدي

‏الگوريتم، ‏شبکه‌‏ها‏ی‏ حسگر، مسيرياب‏ی‏،‏ داده ساختارها‏ی‏ جنبش‏ی‏،‏ کوچکترين زير درخت فراگير محل‏ی

Kinetic Data Structures for Routing Problem in Mobile Sensor Networks

Kamyar Rafati, Naeem Esfahani, Mohammad Ghodsi

Abstract

“Sensor networks” is an important topic in computer science and algorithm design. These networks are constructed from a set of independent mobile units with limited power and process capability. These units communicate and gather information using radio transmitters. The problem of routing in these networks with minimum power consumption is a NP-hard problem. Therefore, many researches use approximation algorithms for this problem. Most of the proposed models work with fixed sensors. In this paper, we propose an algorithm for routing in mobile sensor networks. According to the inherent kinetic structure of such networks, the use of a kinetic data structure which efficiently maintains minimum spanning tree (MST) is useful. In this paper, we present such structure for our problem and show that this method reduces the time complexity of routing in sensor networks.

Keywords

Algorithm, Sensor Networks, Routing, Kinetic Data Structures, Minimum Spanning Trees

‏مقدمه

‏با ظهور ارتباطات بیسيم بين عناصر مختلف و به دنبال آن مسئله شبکههای بی سيم و متحرک، توجه بسياری از انديشمندان رشته علوم کامپيوتر به مسائل موجود در اين شبکه از قبيل مسيريابی معطوف شد. اما اين شبکهها پاسخگوی تمام نيازها در زمينه ارتباطات بی سيم نبودند. به همين منظور مدل شبکههای ويژه‏ Ad‏-Hoc Networks

‏ ارائه شد که در آنها ارتباطات از طريق فرستندهها و گيرندههای راديويي با فاصله ارتباطی محدود انجام میگرفت و در ضمن ساختار يکپارچه مرکزی برای مسيريابی و مديريت ندارند. در قدم بعدی محدوديت توان مصرفی و عملياتی نيز به مدل فوق افزوده شد و مدل شبکه حسگر معرفی شد.

‏شبکه های حسگر کاربرد بسيار وسيعی دارند. مثلا حسگرهای تشخيص آتش سوزی در يک جنگل و يا شهر همچنين حسگرهای تشخيص تشعشعات هستهای در يک رآکتور هستهای، نمونههايي از اين کاربردها هستند.

‏ويژگيهای شبکههای حسگر را میتوان به اجمال به اين موارد تقسيم نمود: 1. انرژی محدود عناصر .2. پهنای باند محدود .3. شبکه بدون ساختار و متغير با زمان .4. کيفيت پايين ارتباطات .5. قدرت محاسبات محدود در عناصر.

‏از جمله مسائل مطرح در زمينه شبکههای حسگر، بحث مسيريابی در اين شبکهها است. الگوريتمهای متفاوتی برای اين مسئله ارائه شده است. الگوريتمهای ارائه شده را میتوان به دو دسته همگن و ناهمگن تقسيم نمود. الگوريتمهای همگن فرض را بر يکسان بودن عناصر شبکه (از نظر برد فرستنده) میگذارند. الگوريتمهای ناهمگن از انعطافپذيری بيشتری برخوردار هستند. الگوريتمهای ناهمگن با توجه به اطلاعاتی استفاده میکنند به سه دسته تقسيم میشوند. 1- بر مبنای محل : در آنها محل دقيق عناصر مشخص میباشد. 2- بر مبنای جهت : در آنها فرض میشود که هر کس جهت نسبی همسايگانش را نسبت به خود میداند. 3- بر مبنای همسايه : در آنها فرض میشود که شناسه همسايهها در اختيار است.

‏الگوريتمهای ارائه شده را از يک منظر ديگر میتوان به دو دسته متمرکز و نامتمرکز نيز تقسيم نمود. در الگوريتمهای متمرکز، يک ناظر خارجی در سيستم وجود دارد که مسئوليت مسيريابی را به عهده دارد. البته فرض وجود چنين ناظری اولا با ماهيت شبکههای حسگر سازگار نيست در ضمن قابليت مقياسپذيری ندارد.

‏از جمله روشهای رايج در زمينه مسيريابی استفاده از درخت فراگير‏ ‏کمينه‏ است. ا‏ما به دو دليل که در ادامه خواهيم ديد، استفاده از آنها در اين شبکهها محبوبيت پيدا نکرده است. اولا پيدا کردن ‏کوچکترين‏ درخت فراگير يک الگوريتم ماهيتا متمرکز است و دوما به علت آنکه هزينه ساخت آن بالاست و در اين شبکهها - به علت متحرک بودن عناصر - نياز است که مرتبا اين درخت ساخته شود.

‏در اين مقاله يک الگوريتم برای مسيريابی در شبکههای حسگر بر مبنای ‏کوچکترين‏ درخت فراگير ارائه میشود ولی سعی شده که مشکلات ذکر شده در بالا در آن پاسخ داده شود. برای اين منظور اولا از ‏کوچکترين‏ درخت فراگير محلی استفاده شده است که نياز ناظر را از بين میبرد و همچنين از يک ساختار جنبشی برای نگهداری آن استفاده میشود که مشکل هزينه تغييرات را از بين میبرد.

‏در زمينه مسيريابی در شبکههای حسگر کارهای گوناگونی انجام شده است ولی در تمام آنها فرض بر ثابت بودن ساختار شبکه در طول حيات شبکه است. همچنين داده ساختارهای گوناگونی برای نگاهداری اجزای شبکه مطرح شده است ولی اکثر آنها هزينه به روز رسانی بالايي دارند و همچنين برای مسئله مسيريابی مناسب نيستند. لذا در اين مقاله تلاش شد تا فرضهای مطرح شده بسيار به محيط واقعی شبيه باشند که تا زمان نوشتن اين مقاله کاری با اين درجه شباهت با محيط واقعی پيدا نکرديم. نتيجه حاصل نيز هزينه نگاهداری و به روز رسانی کمينه‏‏ای دارد که برای حسگر های با انرژی محدود مناسب است.

‏در بخشهای بعدی ابتدا يک الگوريتم برای کوچکترين درخت فراگير محلی ارائه میشود. سپس يک روش جنبشی برای نگهداری کوچکترين درخت فراگير ارائه میشود. در ادامه الگوريتم اصلی که ترکيبی از اين دو روش است معرفی میشود و بعضی خواص آن اثبات میشود . در انتها پيچيدگی الگوريتم و نتيجهگيری آورده شده است.

دانلود,مقاله,ساختارهای,جنبشی,در,مسيريابی,شبکههای,حسگر,متحرک,5,ص,دانلود

تصاویری از چند صفحه نخست فایل :

توجه فرمایید بدلیل تهیه ی تصویر با نرم افزار های خارجی متن نمایش داده شده در تصاویر ممکن است دارای اشکالاتی در نمایش برخی حروف باشد که در فایل اصلی بدون مشکل است