پروژه ارائه یک الگوریتم رهگیری هدف پویا بر اساس پیش‌بینی در شبکه حسگر بی‌سیم

پروژه ارائه یک الگوریتم رهگیری هدف پویا بر اساس پیش‌بینی در شبکه حسگر بی‌سیم

فرمت : ورد (قابل ویرایش)عنوان : ارائه یک الگوریتم رهگیری هدف پویا بر اساس پیش‌بینی در شبکه حسگر بی‌سیمتعداد صفحه : 108چکیدهبا پیشرفت تکنولوژی ساخت وسایل الکترونیکی و مقرون به صرفه شدن شبکه‌های حسگر در مقیاس‌های بزرگ، شبکه­ های حسگر بی­سیم زمینه‌های تحقیقاتی را با رشد سریع و جذابیت بسیار فراهم می­کنند که توجهات زیادی را در چندین سال اخیر به خود جلب کرده است. شبکه‌های حسگر بی‌سیم با مقیاس بزرگ حاوی چند صد تا چند ده هزار حسگر، پهنه وسیعی از کاربردها و البته چالش‌ها را به همراه دارند. ویژگی‌های خاص این شبکه‌ها، امکان استفاده از آن‌ها را در کاربردهایی مانند کنترل و بررسی مناطق حادثه‌خیز، حفاظت مرزها و مراقبت‌های امنیتی و نظامی فراهم می­کنند. یکی از مهم‌ترین کاربردهای متصور برای این شبکه‌ها کاربرد رهگیری هدف می‌باشد. در این کاربرد، شبکه‌های حسگر بی‌سیم از حسگرهای تشکیل‌دهنده این شبکه جهت حس کردن و تشخیص یک هدف خاص و دنبال کردن آن در ناحیه تحت نظارت شبکه استفاده می‌شود. به دلیل اینکه حسگرهای موجود در این نوع شبکه‌ها دارای محدودیت انرژی می‌باشند و ارتباطات بین حسگرها به صورت بی‌سیم انجام می­پذیرد، توجه به مسئله مصرف توان و رهگیری بدون خطا چندین هدف متحرک به صورت همزمان در این شبکه‌ها اهمیت فراوانی دارند. الگوریتم‌های رهگیری هدف در شبکه‌های حسگر، از نظر کاربرد و عملکرد آن‌ها، به چهار دسته­ی پروتکل مبتنی بر پیام، مبتنی بر درخت، مبتنی بر پیش‌گویی و مبتنی بر خوشه‌بندی، تقسیم می­گردند. در این میان پروتکل‌های مبتنی بر خوشه‌بندی از نظر مصرف انرژی بهینه هستند. تاکنون برای رفع مشکل انرژی روش‌های زیادی طرح گردیده است که می‌توان به الگوریتم‌های رهگیری اهداف سریع، DPT و CDTA اشاره کرد. الگوریتم رهگیری اهداف سریع قابلیت رهگیری اهداف سریع را دارا می‌باشد ولی از معایب آن می‌توان به بالا بودن میزان ارتباطات در شبکه به دلیل کوچک بودن خوشه‌ها اشاره کرد. الگوریتم DPT دارای یک الگوریتم پیش بین با پیچیدگی کم می‌باشد ولی از معایب آن می‌توان به قادر نبودن آن به رهگیری چندین هدف به صورت همزمان اشاره کرد. از معایب الگوریتم CDTA می‌توان به عدم وجود رویه تصحیح خطا برای شناسایی مجدد هدف گم شده، تقسیم‌بندی شبکه بر اساس مدل شبکه و قادر نبودن آن به رهگیری چندین هدف به صورت همزمان اشاره کرد. در الگوریتم پیشنهادی از یک دیدگاه خوشه‌بندی بر اساس پیش‌بینی به منظور مقیاس‌پذیر بودن شبکه و مصرف بهینه انرژی استفاده گردیده است تا در برابر خرابی‌های احتمالی حسگرها و پیش‌بینی‌های اشتباه مکان هدف مقاوم باشد. در این الگوریتم، رویه تصحیح خطایی ارائه گردیده است تا در زمان‌هایی که هدف به دلیل سرعت بالای خود و یا تغییر جهت‌های ناگهانی از برد حسگرها خارج گردید، الگوریتم قادر به شناسایی مجدد هدف باشد. نتایج بدست آمده توسط شبیه‌ساز نشان می­دهند که الگوریتم پیشنهادی قادر به رهگیری چندین هدف به صورت همزمان می‌باشد و همچنین الگوریتم پیشنهادی با کم کردن ارتباطات بین خوشه­ای و احتمال گم­شدن هدف مصرف انرژی در شبکه‌های حسگر را تا حد امکان کاهش می­دهد.فصل اول: مقدمه1-1- شرح و اهمیت موضوع1-2- اهداف تحقیق1-3- ساختار پروژهفصل دوم: رویکردهای رهگیری هدف2-1- مقدمه2-2- رویکرد مبتنی بر پیام2-2-1- پروتکل FAR 2-2-2- پروتکل VE-mobicast 2-2-3- پروتکل HVE-mobicast 2-3- رویکرد مبتنی بر درخت2-3-1- الگوریتم DCTC 2-3-2- الگوریتم STUN 2-3-3- الگوریتم DAT 2-4- رویکرد مبتنی بر پیش‌بینی2-4-1- الگوریتم TTMB 2-4-2- الگوریتم کاهش خطا مکانی به صورت انرژی آگاه 2-4-3- الگوریتم FTPS 2-4-4- الگوریتم HPS 2-4-5- الگوریتم PES 2-4-6- الگوریتم DPR 2-5- رویکرد مبتنی بر خوشه2-5-1- الگوریتم رهگیری اهداف سریع 2-5-2- الگوریتم رهگیری هدف با همکاری خوشه ها 2-5-3- الگوریتم DELTA 2-5-4- الگوریتم DPT 2-5-5- الگوریتم CDTA 2-6- نتیجه‌گیریفصل سوم: مدل‌های حرکتی3-1- مقدمه3-2- مکان‌یابی در شبکه‌های حسگر3-2-1- الگوریتم زمان انتشار یک طرفه 3-2-2- الگوریتم زمان انتشار رفت و برگشت 3-2-3- الگوریتم فانوس دریایی 3-2-4- الگوریتم تخمین فاصله از طریق اندازه‌گیری قدرت سیگنال دریافتی 3-2-5- الگوریتم مکان‌یابی به وسیله GPS 3-2-6- الگوریتم مکان‌یابی تک گامه با روش فانوس دریایی 3-2-7- الگوریتم مکان‌یابی چند گامه بر مبنای فاصله 3-3- مدل‌های حرکتی تصادفی3-3-1- مدل حرکتی نقطه راه تصادفی 3-3-2- مدل حرکتی جهت تصادفی 3-3-3- مدل حرکتی راهپیمایی تصادفی 3-3-4- مدل حرکتی راهپیمایی جمع‌آوری 3-4- مدل حرکتی شهری3-4-1- مدل حرکتی آزادراه 3-4-2- مدل حرکتی منهتن 3-5- مدل‌های حرکتی وابسته زمانی3-5-1- مدل حرکتی گاس- مارکوف 3-5-2- مدل حرکتی راهپیمایی تصادفی احتمالی 3-5-3- مدل حرکتی وابسته نمایی 3-6- مدل‌های حرکتی گروهی3-6-1- مدل حرکتی نقطه مرجع 3-6-2- مدل حرکتی تعقیب 3-6-3- مدل حرکتی رشته‌ای 3-6-4- مدل حرکتی ردیفی 3-7- نتیجه‌گیریفصل چهارم: تحقیقات مرتبط با الگوریتم پیشنهادی4-1- مقدمه4-2- الگوریتم خوشه‌بندی توزیع‌شده به صورت هم پوشانی4-3- الگوریتم رهگیری اهداف سریع4-4- الگوریتم رهگیری توزیع‌شده بر اساس پیش‌بینی4-5- الگوریتم CDTAفصل پنجم: معماری و شبیه‌سازی الگوریتم پیشنهادی5-1- مقدمه5-2- مقدمات الگوریتم پیشنهادی5-2-1- تعاریف 5-2-2- فرضیات الگوریتم پیشنهادی 5-3- معماری الگوریتم پیشنهادی5-3-1- رویه خوشه‌بندی 5-3-2- رویه رهگیری هدفPDTA توسط حسگرهای عضو خوشه 5-3-3- رویه رهگیری هدفPDTA توسط حسگرهای سرخوشه 5-3-4- مدل مصرف انرژی: 5-4- تنظیمات شبیه‌سازی5-5- پارامترهای شبیه‌سازی5-6- نتایج شبیه‌سازیفصل ششم: نتیجه‌گیری6-1- جمع‌بندی کلی نتایج6-2- پیشنهاداتمراجعفهرست اشکالشکل2-1: نمونه‌ای از رهگیری هدف مبتنی بر پیامشکل2-2: الگوریتم‌های ارسال ابتکاری و دوره‌ای در الگوریتم FARشکل2-3: چند پخشی مکان زمانیشکل2-4: روند دوم مرحله تخمین تخم­ مرغشکل2-5: نواحی مختلف تقسیم‌کننده شبکه، a: ناحیه یک، b: ناحیه دو، c: ناحیه سهشکل2-6: مراحل الگوریتمDCTC ، a: مرحله جمع‌آوری داده، b: مرحله باز پیکربندیشکل2-7: الگوریتم‌های هرس کردن درخت، a: الگوریتم محافظه‌کارانه، b: الگوریتم بر اساس پیش‌بینیشکل2-8: الگوریتم باز پیکربندی کامل، الف:درخت همراه قبل از باز پیکربندی کامل، ب: درخت همراه بعد از باز پیکربندی کامل شکل2-9: الگوریتم باز پیکربندی بر اساس قطع، الف: درخت همراه قبل از باز پیکربندی بر اساس قطع، ب: درخت همراه بعد از باز پیکربندی بر اساس قطع شکل2-10: مثالی از شکل گرفتن درخت DAB، a: گراف وزن دار حسگر، b: درخت DAB بعد از اولین مرحلهشکل2- 11: الف: ارسال پیام جستجو توسط حسگر چاهک به منظور شناسایی هدف اول، ب: خارج شدن هدف اول از برد حسگرK و وارد شدن آن به برد حسگرGشکل2-12: ماشین حالت الگوریتم TTMBشکل2-13: حوزه‌های بیدارباش کنونی و آینده شکل2-14: انواع حسگرها در رویکرد اجتناب از خطا شکل2-15: مثالی از پیش‌بینی سه سطحی. شکل2- 16: تعیین برد مخابراتی خوشهشکل2-17: توابع اکتشافی برای مکانیزم های بیدار کردن حسگرها شکل2-18: مدل‌های مکانیشکل2-19: ماشین حالت الگوریتم رهگیری اهداف سریعشکل2-20: ماشین حالات الگوریتم DELTAشکل2-21:جستجو برای حسگرهای مکان‌یابی با شعاع حسی کمشکل2-22:جستجو برای حسگرهای مکان‌یابی با شعاع حداکثریشکل2-23: جستجو برای حسگرهای مکان‌یابی در خوشه‌های مجاورشکل2-24: سطح دوم از فرایند بازیابی هدفشکل 3-1: الگوریتم فانوس دریاییشکل 3-2: روش مثلث سازیشکل 3-3: الگوریتم مکان‌یابی تک گامه با روش فانوس دریاییشکل 3-4: الگوی حرکتی یک گره متحرک با استفاده از مدل حرکتی نقطه راه تصادفیشکل 3-5: الگوی حرکتی مدل راهپیمایی تصادفی بازمان حرکت ثابتشکل 3-6: انواع مدل‌های شهری، a: مدل آزادراه، b: مدل منهتنشکل 3-7: تغییر مکان گروه در مدل گروهی نقطه مرجعشکل 3-8: حرکت سه گره متحرک بر اساس مدل حرکتی رشته ­ایشکل 4-1:دیاگرام حالت الگوریتم KOCAشکل 4-2: رویه خوشه‌بندی مجدد در الگوریتم رهگیری اهداف سریع شکل 4-3: الگوریتم رهگیری هدف در الگوریتم رهگیری سریع اهدافشکل 4-4: جستجو سه حسگر شایسته در برد نرمالشکل 4-5: جستجو سه حسگر شایسته در برد حداکثریشکل 4-6: جستجو سه حسگر شایسته توسط خوشه‌های مجاورشکل 4-7: شناسایی هدف توسط حسگرهایی که در فاصله برد نرمال تا هدف قرار دارندشکل 4-8: رویه تصحیح خطا شکل 4-9: معماری رهگیری هدف در الگوریتم CDTAشکل 4-10: چگونگی تغییر حالات حسگرها شکل 4-11: مکانیزم ارتباطی بین حسگرهای اجرایی و حسگرهای انتشاردهنده شکل5-1: بسته پیام اعلان سرخوشه شدن ADV-Messageشکل5-2: جدول سرخوشه CH-Tableشکل5-3: بسته پیام عضویت JREQ-Msgشکل5-4: جدول خوشه‌های مجاور AC-Tableشکل5-5:جدول حسگرهای عضو خوشه. شکل5-6: بسته پیام بیدارباششکل5-7:بسته ارسال اطلاعات توسط حسگرهای شناسایی کننده هدفشکل5-8: بسته پیام انتخاب حسگرهای شایسته توسط خوشه‌های همسایهشکل5-9: مدل شبکه: دایره‌ها نشان‌دهنده حسگرهای مرزی، مربع‌ها نشان‌دهنده حسگرهای عضو خوشه و شش ضلعی‌ها نشان‌دهنده حسگرهای سرخوشه است. شکل5-10: دیاگرام کلی الگوریتم PDTAشکل5-11: دیاگرام رویه خوشه‌بندیشکل5-12: دیاگرام رویه رهگیری هدفشکل5-13: روند اجرای ارسال پیام ADV در رویه خوشه‌بندیشکل5-14: ماشین حالت نشان‌دهنده سازوکار خوشه‌بندی الگوریتم پیشنهادیشکل5-15: شبه کد رویه خوشه‌بندی پیشنهادیشکل5-16:محاسبه محل هدف توسط سه حسگر شایستهشکل5-17:جستجوی سه حسگر شایسته رهگیری هدف در برد نرمالشکل5-18: جستجوی سه حسگر شایسته رهگیری هدف در برد حداکثریشکل5-19: جستجوی سه حسگر شایسته رهگیری هدف در بین خوشه‌ها شکل5-20: مقایسه بین حرکت واقعی و حرکت پیش‌بینی‌شده توسط پیش‌بینی کننده برای هدف اولشکل5-21: جزئیات مقایسه بین حرکت واقعی و حرکت پیش‌بینی‌شده توسط پیش بین برای هدف اول در مسیری از مکان (464و391) تا مکان (302و8) شکل5-22: مقایسه بین حرکت واقعی و حرکت پیش‌بینی‌شده توسط پیش‌بینی کننده برای هدف دومشکل5-23: مقایسه بین حرکت واقعی و حرکت پیش‌بینی‌شده توسط پیش‌بینی کننده برای هدف سومشکل5-24:روش بدست آوردن اندازه خطا بین موقعیت واقعی و موقعیت پیش‌بینی‌شده شکل5-25: رابطه بین احتمال گم شدن هدف و دقت رهگیریشکل5-26: احتمال گم شدن هدف در برابر سرعت هدفشکل5-27: حداکثر فاصله هدف تا سه حسگر شایسته را برای اهداف گم شده شکل5-28: انرژی مصرف‌شده در شبکه برای 2000 نقطه شناسایی هدففهرست جداولجدول 5-1: رویدادهای بین حالات و حالات بعدی در هر یک از حالاتجدول 5-2: پارامترهای شبیه‌سازیجدول 5-3: مشخصات الگوریتم پیش بین خطی