انجام پایان نامه

درخواست همکاری انجام پایان نامه  بانک مقالات رایگان انجام پایان نامه

سفارش پایان نامه

|

انجام پایان نامه ارشد

 پایان نامه 

پایان نامه‏ کامپیوتر

انجام پایان نامه‏ ارشد کامپیوتر

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

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
 
1- مقدمه
با ظهور ارتباطات بی¬سيم بين عناصر مختلف و به دنبال آن مسئله شبکه¬های بی سيم و متحرک، توجه بسياری از انديشمندان رشته علوم کامپيوتر به مسائل موجود در اين شبکه از قبيل مسيريابی معطوف شد. اما اين شبکه¬ها پاسخگوی تمام نيازها در زمينه ارتباطات بی سيم نبودند. به همين منظور مدل شبکه¬های ويژه  ارائه شد که در آنها ارتباطات از طريق فرستنده¬ها و گيرنده¬های راديويي با فاصله ارتباطی محدود انجام می¬گرفت و در ضمن ساختار يکپارچه مرکزی برای مسيريابی و مديريت ندارند. در قدم بعدی محدوديت توان مصرفی و عملياتی نيز به مدل فوق افزوده شد و مدل شبکه حسگر معرفی شد.
شبکه های حسگر کاربرد بسيار وسيعی دارند. مثلا حسگرهای تشخيص آتش سوزی در يک جنگل و يا شهر همچنين حسگرهای تشخيص تشعشعات  هسته¬ای در يک رآکتور هسته¬ای، نمونه¬هايي از اين کاربردها هستند.
ويژگي¬های شبکه¬های حسگر را می¬توان به اجمال به اين موارد تقسيم نمود: 1. انرژی محدود عناصر .2. پهنای باند محدود .3. شبکه بدون ساختار و متغير با زمان .4. کيفيت پايين ارتباطات .5. قدرت محاسبات محدود در عناصر.
از جمله مسائل مطرح در زمينه شبکه-های حسگر، بحث مسيريابی در اين شبکه¬ها است. الگوريتم¬های متفاوتی برای اين مسئله ارائه شده است. الگوريتم¬های ارائه شده را می¬توان به دو دسته همگن و ناهمگن تقسيم نمود. الگوريتم¬¬های همگن فرض را بر يکسان بودن عناصر شبکه (از نظر برد فرستنده) می¬گذارند. الگوريتم¬های ناهمگن از انعطاف¬پذيری بيشتری برخوردار هستند. الگوريتم¬های ناهمگن با توجه به اطلاعاتی استفاده می¬کنند به سه دسته تقسيم می¬شوند. 1- بر مبنای محل : در آنها محل دقيق عناصر مشخص می¬باشد. 2- بر مبنای جهت : در آنها فرض می¬شود که هر کس جهت نسبی همسايگانش را نسبت به خود می¬داند. 3- بر مبنای همسايه : در آنها فرض می¬شود که شناسه همسايه¬ها در اختيار است.
الگوريتم¬های ارائه شده را از يک منظر ديگر می¬توان به دو دسته متمرکز و نامتمرکز نيز تقسيم نمود. در الگوريتم¬های متمرکز، يک ناظر خارجی در سيستم وجود دارد که مسئوليت مسيريابی را به عهده دارد. البته فرض وجود چنين ناظری اولا با ماهيت شبکه¬های حسگر سازگار نيست در ضمن قابليت مقياس¬پذيری ندارد.
از جمله روش¬های رايج در زمينه مسيريابی استفاده از درخت فراگير کمينه است. اما به دو دليل که در ادامه خواهيم ديد، استفاده از آنها در اين شبکه¬ها محبوبيت پيدا نکرده است. اولا پيدا کردن کوچکترين درخت فراگير يک الگوريتم ماهيتا متمرکز است و دوما به علت آنکه هزينه ساخت آن بالاست و در اين شبکه¬ها - به علت متحرک بودن عناصر - نياز است که مرتبا اين درخت ساخته شود.
در اين مقاله يک الگوريتم برای مسيريابی در شبکه¬های حسگر بر مبنای کوچکترين درخت فراگير ارائه می¬شود ولی سعی شده که مشکلات ذکر شده در بالا در آن پاسخ داده شود. برای اين منظور اولا از کوچکترين درخت فراگير محلی استفاده شده است که نياز ناظر را از بين می¬برد و همچنين از يک ساختار جنبشی برای نگهداری آن استفاده می¬شود که مشکل هزينه تغييرات را از بين می¬برد.
در زمينه مسيريابی در شبکه¬های حسگر کارهای گوناگونی انجام شده است ولی در تمام آنها فرض بر ثابت بودن ساختار شبکه در طول حيات شبکه است. همچنين داده ساختارهای گوناگونی برای نگاهداری اجزای شبکه مطرح شده است ولی اکثر آنها هزينه به روز رسانی بالايي دارند و همچنين برای مسئله مسيريابی مناسب نيستند. لذا در اين مقاله تلاش شد تا فرض¬های مطرح شده بسيار به محيط واقعی شبيه باشند که تا زمان نوشتن اين مقاله کاری با اين درجه شباهت با محيط واقعی پيدا نکرديم. نتيجه حاصل نيز هزينه نگاهداری و به روز رسانی کمينه¬ای دارد که برای حسگر های با انرژی محدود مناسب است.
در بخش¬های بعدی ابتدا يک الگوريتم برای کوچکترين درخت فراگير محلی ارائه می¬شود. سپس يک روش جنبشی برای نگهداری کوچکترين درخت فراگير ارائه می¬شود. در ادامه الگوريتم اصلی که ترکيبی از اين دو روش است معرفی می-شود و بعضی خواص آن اثبات می¬شود . در انتها پيچيدگی الگوريتم و نتيجه-گيری آورده شده ¬است.
2- کوچکترين درخت فراگير محلی
در اين قسمت روشی برای ساخت کوچکترين زير درخت فراگير به صورت محلی ارائه می¬شود. ايده اصلی از روش ارائه شده توسط لی و همکارانش [1] گرفته شده است.
الگوريتم ساخت اين درخت در دو فاز انجام می¬شود. در مرحله اول اطلاعات بين عناصر شبکه تبادل می¬شود و در مرحله دوم هر عنصر به صورت مجزا کوچکترين زير درخت فراگير را برای خود می¬سازد. در ادامه هر يک از دو فاز را به تفضيل شرح می¬دهيم.
فاز تبادل اطلاعات : در اين فاز همانند مدل بردار فاصله  در مسيريابی درون دامنه¬ای عمل  می¬شود. به اين صورت که هر عنصر در شبکه اطلاعات خود را از تمام عناصر شبکه به صورت يک بردار فاصله به همسايگانش می فرستد. به علت اينکه عناصر از وجود تمام عناصر ديگر آگاه نيستند استفاده از شناسه الزامی است. پس از اتمام اين فاز ، تمام عناصر و يا گره‌های شبکه ، اطلاعات کل شبکه را در اختيار دارند.
فاز ساخت کوچکترين زير درخت فراگير : در اين فاز ، همانند فاز دوم در روش ارائه شده توسط لی و همکارانش [1] ، هر گره با استفاده از الگوريتمی مانند پريم [4] کوچکترين زير درخت فراگير را می سازد. در الگوريتم پريم درخت حاصل يکتا نيست زيرا در مواردی که فاصله دو گره از يک گره يکسان باشد به صورت اتفاقی يکی از آنها انتخاب می¬شود. ولی به منظور اينکه تمام عناصر ديد يکسانی از اين درخت داشته باشند ، ما تابع فاصله را به صورت زير تغيير داده¬ايم تا هميشه درخت يکتايي توليد شود.
 

که در آن   برابر فاصله راس   از راس   است. در انتهای اين فاز هر عنصر يک درخت فراگير دارد که در تمام گره¬های مختلف شبکه يکسان هستند و در حقيقت روی آن توافق شده است. در صورتی که عناصر شبکه در يک صفحه باشند اثبات می شود که بزرگترين درجه راس¬های درخت حداکثر 6 می¬شود. اين نکته باعث کاهش قابل توجهی از انرژی مصرفی هر گره می¬شود.
تا اين مرحله هر گره ، کوچکترين زير درخت فراگير لازم برای مسيريابی را ساخته است. در بخش بعد روشی برای نگهداری بهينه اين درخت در موارد وجود حرکت و يا حذف و ايجاد گره¬های جديد با کمک يک داده ساختار جنبشی ارائه می¬شود.
3- کوچکترين درخت فراگير پارامتری و جنبشی
برای مدل کردن ساختار جنبشی گره‌ها می‌توان روش‌های مختلفی را پيش گرفت. در ابتدايی‌ترين حالت می‌توان فرض کرد معادله‌ی حرکت گره‌ها دقيقا مشخص است و بر پايه‌ی آن داده ساختار مساله را حل کرد. مشکل اين روش اين است که اولا معادله‌ی حرکت يک گره ممکن است بسيار پيچيده باشد و بدست آوردن اطلاعات لازم از آن کار ساده‌ای نباشد؛ دوما ماهيت معادله‌ی حرکت يک گره يک مفهوم پيوسته است و برای ما مناسب‌تر است اگر بتوانيم آن را به صورت يک مفهوم گسسته مدل کنيم. بنابراين از مدل معرفی شده توسط آگاروال و همکارانش [2] استفاده می‌کنيم که در آن به جای در نظر گرفتن معادله‌ی حرکت يک گره، تغييرات وزن يک يال را داريم و آن را يک تابع خطی در نظر می‌گيريم و برای گسسته کردن اين تابع از رابطه‌ی   برای يال   استفاده می‌کنيم. در اين تابع دو عدد   و   دو عدد حقيقی هستند و   به عنوان يک پارامتر گسسته تغيير کرده و باعث تغيير وزن يال‌ها می‌شود. به طور کلی دو دسته الگوريتم جنبشی برای حل مساله‌ی کوچکترين درخت فراگير داريم که هر کدام را می‌توان با ديگری شبيه‌سازی نمود:
•    الگوريتم جنبشی ساختاری: که در آن يال‌ها اضافه و حذف می‌شوند و تغيير وزن را با حذف و اضافه کردن يال شبيه‌سازی می‌کنيم.
•    الگوريتم جنبشی تابعی: که توانايی تغيير وزن يال‌ها را دارد و اضافه و حذف يال‌ها را با استفاده از يک عدد بسيار بزرگ به عنوان وزن يال حذف شده شبيه‌سازی می‌کند.







انجام پایان نامه

انجام پایان نامه کامپیوتر، انجام پایان نامه ارشد کامپیوتر، انجام پایان نامه، پایان نامه

برای دیدن ادامه مطلب از لینک زیر استفاده نمایید

 

سفارش پایان نامه