44 - پایان نامه حسگر بی سیم
چکیده
یکی از موضوعات مطرح در طراحی الگوریتمها بحث شبکههای حسگر میباشد. این شبکهها متشکل از مجموعهای از واحدهای متحرک و مستقل از هم با توان مصرفی و پردازشی محدود است که از طریق فرستندههای رادیویی با یکدیگر در ارتباطند و اقدام به جمعآوری اطلاعات مینمایند. مسالهی مسیریابی در این شبکهها به گونهای که حداقل انرژی مصرف شود، از دسته مسائل غیر چند جملهای سخت میباشد که ارائه راه حلهای تقریبی مناسب موضوع برخی از تحقیقات در این زمینه است. در بیشتر مدلهای ارائه شده فرض بر ثابت بودن حسگرها است؛ در این مقاله سعی میشود الگوریتمی برای مسیریابی در شبکهی حسگرهای متحرک ارائه شود. با توجه به ماهیت جنبشی این شبکهها ، استفاده از داده ساختارهایی که بتواند ساختار زیر درخت فراگیر را به صورت بهینه نگاهداری نمایند بسیار سودمند است. در این تحقیق از داده ساختار جنبشی برای نگاهداری زیر درخت فراگیر استفاده شده است. در این مقاله این روش ارایه و بررسی میشود و نشان میدهیم که باعث کاهش پیچیدگی محاسباتی مسیریابی در این شبکهها میشود.
کلمات کلیدی
الگوریتم، شبکههای حسگر، مسیریابی، داده ساختارهای جنبشی، کوچکترین زیر درخت فراگیر محلی
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] استفاده میکنیم که در آن به جای در نظر گرفتن معادلهی حرکت یک گره، تغییرات وزن یک یال را داریم و آن را یک تابع خطی در نظر میگیریم و برای گسسته کردن این تابع از رابطهی برای یال استفاده میکنیم. در این تابع دو عدد و دو عدد حقیقی هستند و به عنوان یک پارامتر گسسته تغییر کرده و باعث تغییر وزن یالها میشود. به طور کلی دو دسته الگوریتم جنبشی برای حل مسالهی کوچکترین درخت فراگیر داریم که هر کدام را میتوان با دیگری شبیهسازی نمود:
• الگوریتم جنبشی ساختاری: که در آن یالها اضافه و حذف میشوند و تغییر وزن را با حذف و اضافه کردن یال شبیهسازی میکنیم.
• الگوریتم جنبشی تابعی: که توانایی تغییر وزن یالها را دارد و اضافه و حذف یالها را با استفاده از یک عدد بسیار بزرگ به عنوان وزن یال حذف شده شبیهسازی میکند.
یکی از تکنیکهایی که در این روش استفاده میشود روش تنک کردن است که عملا روش تقسیم و حل میباشد. در این روش گراف را به صورت بازگشتی به تعدادی دسته تقسیم میکنیم. نکتهای این تقسیم بندیها دارند این است که درخت نهایی حاصل از گراف به راحتی از کنار هم قرار دادن جوابهای زیر درختها حاصل از زیر گرافها بدست میآید. اپستین و همکارانش [7] نشان دادند که این عمل نتیجهی درستی میدهد. فرناندز و همکارانش [8] نیز نشان دادند که این روش برای مسالهی پارامتری نیز درست کار میکند و هزینهی آن را نیز محاسبه کردند.
نقطهی عطف این روش مطرح کردن ایدههای هندسهی محاسباتی در کاربرد تئوری گرافهاست؛ نشان داده میشود که میتوان اطلاعات مربوط به گرهها را توسط پوش محدب نگهداری کرد؛ به این ترتیب که با توجه به دستهبندی که انجام میشود، مجموعههایی داریم که برای داشتن درخت فراگیر باید یکی از یالها را انتخاب و حذف کرد. اگر در این انتخاب بزرگترین عنصر مجموعه را حذف کنیم درخت ما کمینه خواهد بود. در اینجا جنبش باعث میشود که این بزرگترین عنصر با تغییر که حاصل از جنبش است عوض شود و برای داشتن کوچکترین درخت فراگیر مجبور به تعویض یال شویم. با استفاده از پوش محدب میتوانیم در زمان بزرگترین یال جدید را پیدا کنیم و جای یال قبلی را با آن عوض کنیم. روند کار به این ترتیب است که با استفاده از تبدیل هو [Hough59] معادلهی وزن یالها بر اساس را تبدیل به نقاط میکنیم. در مسالهی دوگان بدست آمده خطی که بر دو پوش محدب مماس میشود مشخص میکند کدام دو خط باید جابجا شوند. این دو نقطهی پیدا شده در عمل نشان دهندهی بیشترین رشد وزن در یالهایی که در درخت هستند و بیشترین کاهش وزن در یالهایی که در درخت نیستند میباشند و اگر قرار باشد جای دو یال عوض شود باید این دو یال باشند. دو یال میتوانند در جابجایی روابط زیر را با هم داشته باشند:
• جابجایی درون افرازی: هر دو در یک افراز هستند.
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 6 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
این برنامه شامل حسگرهای مختلفی میباشد ک شاید ب کارتان بیاید
مقدمه 1
فصل اول
شبکه های حسگربی سیم 2
چرا شبکه های حسگر؟ 2
تاریخچة شبکه های حسگر 3
ساختار کلی شبکه حسگر بی سیم 4
ساختمان گره 6
ویژگی ها 7
موضوعات مطرح_ 7
عوامل پیش بینی نشده 11
نمونه ی پیاده سازی شده شبکه حسگر 12
بررسی نرم ا فزارهای شبیه سازی شبکه 14
خصوصیات لازم برای شبیه سازهای شبکه 15
شبیه ساز NS(v2) 16
معماری درونی NS_ 16
مدل VuSystem_ 16
شبیه ساز OMNeT++_ 17
شبیه ساز Ptolemy II 18
مدل سازی شبکه های بی سیم 20
اجرای یک مدل پیش ساخته 20
تغییر پارامترها 22
ساختار یک مدل پیش ساخته 23
قابلیت های مدل سازی_ 41
ساختار نرم افزار 50
چند مثال و کاربرد 54
فهمیدن تعامل (واکنش) در شبکه های حسگر 54
نقایص شبکه های حسگر 54
توانایی های توسعه یافته شبکه های حسگر 54
طراحی ومدل کردن ناهمگن پتولومی_ 54
مدل شبکه حسگر 55
نمونه های ایجاد شده توسط نرم افزار 55
فصل دوم
امنیت در شبکه های حسگر بی سیم 61
مقدمه 61
چالش های ایمنی حسگر 63
استقرار نیرومند 63
محیط مهاجم 64
نایابی منبع 64
مقیاس بزرگ_ 64
حملات و دفاع_ 64
لایه فیزیکی_ 65
تراکم 65
کوبش_ 66
لایه اتصال_ 67
برخورد 67
تخلیه 67
لایه شبکه 68
اطلاعات مسیر یابی غلط_ 68
عملیات انتخابی حرکت به جلو 68
حمله چاهک_ 69
حمله سایبیل_ 69
حمله چاهک پیچشی_ 69
حمله جریان آغازگر 69
اعتبار و رمز گذاری_ 70
نظارت_ 70
پروب شدن_ 71
فراوانی_ 71
راه حل های پیشنهادی_ 71
پروتکل های ارتباط_ 71
معماری های مدیریت کلیدی_ 75
LEAP_ 75
LKHW_ 75
پیش نشر کلیدی به صورت تصادفی_ 76
Tiny PK_ 76
نتیجه گیری_ 77
فصل سوم
بهبود تحمل پذیری خطا در شبکه های حسگر بی سیم 78
کارهای انجام شده 78
سازمان دهی گره ها و عملکرد سیستم 79
روش پیشنهادی_ 81
4-1 شبیه سازی دو روش_ 83
4-2 ارزیابی_ 83
نتیجه گیری_ 84
فصل چهارم
مقاله انگلیسی Security in Wireless Sensor Networks_ 96
منابع 98
نوع مطلب: مقاله انگلیسی Elsevier
زبان مقاله: انگلیسی
سال انتشار: 2015
قالب : پی دی اف (PDF)
تعداد صفحات: 12 صفحه دو ستونی
محل ارائه: ژورنال بین المللی توان الکتریکی و سیستم های انرژی International Journal of Electrical Power & Energy Systems
کلمات کلیدی:
تولید انرژی بادی، انرژی های جدید، شبکه حسگر بی سیم، شبکه حسگر بیسیم، مقاله انگلیسی شبکه حسگر بیسیم، مقاله جدید شبکه حسگر بیسیم، مقاله 2015 شبکه حسگر بیسیم، الگوریتم ژنتیک در شبکه حسگر بیسیم، مکانیابی در شبکه حسگر بیسیم به کمک الگوریتم ژنتیک، مقاله کامپیوتر، مقاله ISI کامپیوتر، مقاله آی اس آی کامپیوتر، مقاله 2015 کامپیوتر، مقاله ISI 2015 کامپیوتر، شبکه های کامپیوتری، دانلود مقاله آی اس آی، ISI ، شبکه حسگر بیسیم، سنسور، تقسیم بندی شبکه، تعمیر توپولوژی، تحمل پذیری خطا، شبکه سنسور بی سیم، یادگیری ماشین، الگوریتم های مسیریابی در شبکه های حسگر بیسیم، الگوریتم های مکانیابی در شبکه های حسگر بیسیم، گره های انکر، گره های لنگرگاه، گره های تکیه گاه، مشخص کردن موقعیت، دانلود رایگان مقاله 2015، مقالات جدید کامپیوتر، شبکه های حسگر بیسیم، سیستم های توزیع شده، دانلود مقاله 2015 کامپیوتر، مقاله 2015 رایگان، دانلود رایگان مقاله 2015 کامپیوتر، کاربرد یادگیری ماشین در شبکه های کامپیوتری، کاربرد یادگیری ماشین در شبکه های حسگر بیسیم، الگوریتم های یادگیری ماشین، شبکه های عصبی مصنوعی، مقاله مکانیابی در شبکه حسگر بیسیم، مقاله مکانیابی در شبکه سنسور، مشخص کردن موقعیت، wireless sensor networks, wsn, localization in wireless sensor network, localisation in wireless sensor networks, artificial neural networks, ann, feed forward neural networks, tansigmoid transfer function, tan sigmoid transfer function, training algorithms, Bayesian regularization, back propagation algorithms, multi-layer perceptron , ، Network partitioning ، Topology repair ، 2-Vertex connectivity، Fault tolerance ، Relay node placement
قیمت ترجمه این مقاله با بهترین کیفیت، کاملا تخصصی و تایپ شده: (حدود 90 هزار تومان)
پس از خرید از درگاه امن بانکی لینک دانلود در اختیار شما قرار میگیرد و همچنین به آدرس ایمیل شما فرستاده میشود.
تماس با ما برای راهنمایی، درخواست مقالات و پایان نامه ها و یا ترجمه با آدرس ایمیل:
ArticleEbookFinder@gmail.com
شماره تماس ما در نرم افزار واتس آپ:
+98 921 764 6825
شماره تماس ما در نرم افزار تلگرام:
+98 921 764 6825
توجه: اگر کارت بانکی شما رمز دوم ندارد، در خرید الکترونیکی به مشکل برخورد کردید و یا به هر دلیلی تمایل به پرداخت الکترونیکی ندارید با ما تماس بگیرید تا راههای دیگری برای پرداخت به شما پیشنهاد کنیم.