فهرست مطالبعنوانصفحهفهرست مطالب.. هشتفهرست اشکال.. یازدهفهرست جداول.. چهاردهچکیده.. 14فصل اول: مقدمه1-1- شرح و اهمیت موضوع.. 21-2- اهداف تحقیق.. 51-3- ساختار پایاننامه.. 5فصل دوم: رویکردهای رهگیری هدف2-1- مقدمه.. 72-2- رویکرد مبتنی بر پیام.. 82-2-1- پروتکل FAR 82-2-2- پروتکل VE-mobicast92-2-3- پروتکل HVE-mobicast122-3- رویکرد مبتنی بر درخت.. 132-3-1- الگوریتم DCTC 132-3-2- الگوریتم STUN 152-3-3- الگوریتم DAT 162-4- رویکرد مبتنی بر پیشبینی.. 182-4-1- الگوریتم TTMB 182-4-2- الگوریتم کاهش خطا مکانی به صورت انرژی آگاه 192-4-3- الگوریتم FTPS 212-4-4- الگوریتم HPS 222-4-5- الگوریتم PES 232-4-6- الگوریتم DPR 242-5- رویکرد مبتنی بر خوشه.. 25 2-5-1- الگوریتم رهگیری اهداف سریع 262-5-2- الگوریتم رهگیری هدف با همکاری خوشهها 272-5-3- الگوریتم DELTA 282-5-4- الگوریتم DPT 282-5-5- الگوریتم CDTA 302-6- نتیجهگیری.. 32فصل سوم: مدلهای حرکتی3-1- مقدمه.. 333-2- مکانیابی در شبکههای حسگر.. 343-2-1- الگوریتم زمان انتشار یک طرفه 343-2-2- الگوریتم زمان انتشار رفت و برگشت 343-2-3- الگوریتم فانوس دریایی 343-2-4- الگوریتم تخمین فاصله از طریق اندازهگیری قدرت سیگنال دریافتی 353-2-5- الگوریتم مکانیابی به وسیله GPS 363-2-6- الگوریتم مکانیابی تک گامه با روش فانوس دریایی 373-2-7- الگوریتم مکانیابی چند گامه بر مبنای فاصله 383-3- مدلهای حرکتی تصادفی.. 383-3-1- مدل حرکتی نقطه راه تصادفی 393-3-2- مدل حرکتی جهت تصادفی 393-3-3- مدل حرکتی راهپیمایی تصادفی 393-3-4- مدل حرکتی راهپیمایی جمعآوری 403-4- مدل حرکتی شهری.. 403-4-1- مدل حرکتی آزادراه 413-4-2- مدل حرکتی منهتن 413-5- مدلهای حرکتی وابسته زمانی.. 413-5-1- مدل حرکتی گاس- مارکوف 423-5-2- مدل حرکتی راهپیمایی تصادفی احتمالی 423-5-3- مدل حرکتی وابسته نمایی 42 3-6- مدلهای حرکتی گروهی.. 433-6-1- مدل حرکتی نقطه مرجع 433-6-2- مدلحرکتیتعقیب 433-6-3- مدل حرکتی رشتهای 443-6-4- مدل حرکتی ردیفی 443-7- نتیجهگیری.. 45فصل چهارم: تحقیقات مرتبط با الگوریتم پیشنهادی4-1- مقدمه.. 464-2- الگوریتم خوشهبندی توزیعشده به صورت هم پوشانی:.. 474-3-الگوریتم رهگیری اهداف سریع:.. 484-4-الگوریتم رهگیری توزیعشده بر اساس پیشبینی:.. 514-5-الگوریتم CDTA.. 55فصل پنجم: معماری و شبیهسازی الگوریتم پیشنهادی5-1- مقدمه.. 595-2- مقدمات الگوریتم پیشنهادی.. 605-2-1- تعاریف 605-2-2- فرضیات الگوریتم پیشنهادی 645-3- معماری الگوریتم پیشنهادی.. 665-3-1- رویه خوشهبندی 705-3-2- رویه رهگیری هدفPDTA توسط حسگرهای عضو خوشه 745-3-3- رویه رهگیری هدفPDTA توسط حسگرهای سرخوشه 745-3-4- مدل مصرف انرژی: 795-4- تنظیمات شبیهسازی.. 805-5- پارامترهای شبیهسازی.. 815-6- نتایج شبیهسازی.. 82فصل ششم:نتیجهگیری6-1- جمعبندی کلی نتایج.. 896-2- پیشنهادات.. 91مراجع.. 92 فهرست اشکالعنوانصفحهشکل2-1: نمونهای از رهگیری هدف مبتنی بر پیام.. 8شکل2-2: الگوریتمهای ارسال ابتکاری و دورهای در الگوریتم FAR.. 9شکل2-3: چند پخشی مکان زمانی.. 9شکل2-4: روند دوم مرحله تخمین تخممرغ... 10شکل2-5: نواحی مختلف تقسیمکننده شبکه، a: ناحیه یک، b: ناحیه دو، c: ناحیه سه... 11شکل2-6: مراحل الگوریتمDCTC ، a: مرحله جمعآوری داده، b: مرحله باز پیکربندی.. 13شکل2-7: الگوریتمهای هرس کردن درخت، a: الگوریتم محافظهکارانه، b: الگوریتم بر اساس پیشبینی.. 14شکل2-8: الگوریتم باز پیکربندی کامل، الف:درخت همراه قبل از باز پیکربندی کامل، ب: درخت همراه بعد از باز پیکربندی کامل.. 15شکل2-9: الگوریتم باز پیکربندی بر اساس قطع، الف: درخت همراه قبل از باز پیکربندی بر اساس قطع، ب: درخت همراه بعد از باز پیکربندی بر اساس قطع 15شکل2-10: مثالی از شکل گرفتن درخت DAB، a: گراف وزن دار حسگر، b: درخت DAB بعد از اولین مرحله.. 16شکل2- 11: الف: ارسال پیام جستجو توسط حسگر چاهک به منظور شناسایی هدف اول، ب: خارج شدن هدف اول از برد حسگرK و وارد شدن آن به برد حسگرG. 17شکل2-12: ماشین حالت الگوریتم TTMB.. 19شکل2-13: حوزههای بیدارباش کنونی و آینده.. 19شکل2-14: انواع حسگرها در رویکرد اجتناب از خطا.. 20شکل2-15: مثالی از پیشبینی سه سطحی... 22شکل2- 16: تعیین برد مخابراتی خوشه.. 23شکل2-17: توابع اکتشافی برای مکانیزم های بیدار کردن حسگرها.. 24شکل2-18: مدلهای مکانی.. 25شکل2-19: ماشین حالت الگوریتم رهگیری اهداف سریع.. 26شکل2-20: ماشین حالات الگوریتم DELTA.. 28 شکل2-21:جستجو برای حسگرهای مکانیابی با شعاع حسی کم.. 29شکل2-22:جستجو برای حسگرهای مکانیابی با شعاع حداکثری.. 29شکل2-23: جستجو برای حسگرهای مکانیابی در خوشههای مجاور.. 30 شکل2-24: سطح دوم از فرایند بازیابی هدف.. 30شکل 3-1: الگوریتم فانوس دریایی.. 35شکل 3-2: روش مثلث سازی.. 37شکل 3-3: الگوریتم مکانیابی تک گامه با روش فانوس دریایی.. 38شکل 3-4: الگوی حرکتی یک گره متحرک با استفاده از مدل حرکتی نقطه راه تصادفی.. 39شکل 3-5: الگوی حرکتی مدل راهپیمایی تصادفی بازمان حرکت ثابت.. 40شکل 3-6: انواع مدلهای شهری، a: مدل آزادراه، b: مدل منهتن.. 41شکل 3-7: تغییر مکان گروه در مدل گروهی نقطه مرجع.. 43شکل 3-8: حرکت سه گره متحرک بر اساس مدل حرکتی رشتهای.. 44شکل 4-1:دیاگرام حالت الگوریتم KOCA.. 48شکل 4-2: رویه خوشهبندی مجدد در الگوریتم رهگیری اهداف سریع.. 50شکل 4-3: الگوریتم رهگیری هدف در الگوریتم رهگیری سریع اهداف.. 51شکل 4-4: جستجو سه حسگر شایسته در برد نرمال.. 53شکل 4-5: جستجو سه حسگر شایسته در برد حداکثری.. 53شکل 4-6: جستجو سه حسگر شایسته توسط خوشههای مجاور.. 54شکل 4-7: شناسایی هدف توسط حسگرهایی که در فاصله برد نرمال تا هدف قرار دارند.. 54شکل 4-8: رویه تصحیح خطا.. 55شکل 4-9: معماری رهگیری هدف در الگوریتم CDTA.. 56شکل 4-10: چگونگی تغییر حالات حسگرها.. 57شکل 4-11: مکانیزم ارتباطی بین حسگرهای اجرایی و حسگرهای انتشاردهنده 58شکل5-1: بسته پیام اعلان سرخوشه شدن ADV-Message. 60شکل5-2: جدول سرخوشه CH-Table. 61شکل5-3: بسته پیام عضویت JREQ-Msg. 61شکل5-4: جدول خوشههای مجاور AC-Table. 62شکل5-5:جدول حسگرهای عضو خوشه.. 62شکل5-6: بسته پیام بیدارباش.. 63شکل5-7:بسته ارسال اطلاعات توسط حسگرهای شناسایی کننده هدف.. 64شکل5-8: بسته پیام انتخاب حسگرهای شایسته توسط خوشههای همسایه.. 64 شکل5-9: مدل شبکه: دایرهها نشاندهنده حسگرهای مرزی، مربعها نشاندهنده حسگرهای عضو خوشه و شش ضلعیها نشاندهنده حسگرهای سرخوشه است... 65شکل5-10: دیاگرام کلی الگوریتم PDTA.. 67شکل5-11: دیاگرام رویه خوشهبندی.. 68شکل5-12: دیاگرام رویه رهگیری هدف.. 69شکل5-13: روند اجرای ارسال پیام ADV در رویه خوشهبندی.. 71شکل5-14: ماشین حالت نشاندهنده سازوکار خوشهبندی الگوریتم پیشنهادی 72شکل5-15: شبه کد رویه خوشهبندی پیشنهادی.. 73شکل5-16:محاسبه محل هدف توسط سه حسگر شایسته.. 75شکل5-17:جستجوي سه حسگر شايسته رهگيري هدف در برد نرمال.. 77شکل5-18: جستجوي سه حسگر شايسته رهگيري هدف در برد حداکثری.. 77شکل5-19: جستجوي سه حسگر شايسته رهگيري هدف در بين خوشهها.. 78شکل5-20: مقایسه بین حرکت واقعی و حرکت پیشبینیشده توسط پیشبینی کننده برای هدف اول.. 82شکل5-21: جزئیات مقایسه بین حرکت واقعی و حرکت پیشبینیشده توسط پیش بین برای هدف اول در مسیری از مکان (464و391) تا مکان (302و8).. 82شکل5-22: مقایسه بین حرکت واقعی و حرکت پیشبینیشده توسط پیشبینی کننده برای هدف دوم.. 83شکل5-23: مقایسه بین حرکت واقعی و حرکت پیشبینیشده توسط پیشبینی کننده برای هدف سوم.. 83شکل5-24:روش بدست آوردن اندازه خطا بین موقعیت واقعی و موقعیت پیشبینیشده.. 85شکل5-25: رابطه بین احتمال گم شدن هدف و دقت رهگیری.. 85شکل5-26: احتمال گم شدن هدف در برابر سرعت هدف.. 86شکل5-27: حداکثر فاصله هدف تا سه حسگر شایسته را برای اهداف گم شده 87شکل5-28: انرژی مصرفشده در شبکه برای 2000 نقطه شناسایی هدف.. 88 فهرست جداولعنوانصفحهجدول 5-1: رویدادهای بین حالات و حالات بعدی در هر یک از حالات.. 72جدول 5-2: پارامترهای شبیهسازی.. 81جدول 5-3: مشخصات الگوریتم پیش بین خطی.. 84چکیدهبا پیشرفت تکنولوژی ساخت وسایل الکترونیکی و مقرون به صرفه شدن شبکههای حسگر در مقیاسهای بزرگ، شبکههای حسگر بیسیم زمینههای تحقیقاتی را با رشد سریع و جذابیت بسیار فراهم میکنند که توجهات زیادی را در چندین سال اخیر به خود جلب کرده است. شبکههای حسگر بیسیم با مقیاس بزرگ حاوی چند صد تا چند ده هزار حسگر، پهنه وسیعی از کاربردها و البته چالشها را به همراه دارند. ویژگیهای خاص این شبکهها، امکان استفاده از آنها را در کاربردهایی مانند کنترل و بررسی مناطق حادثهخیز، حفاظت مرزها و مراقبتهای امنیتی و نظامی فراهم میکنند. یکی از مهمترین کاربردهای متصور برای این شبکهها کاربرد رهگیری هدف میباشد. در این کاربرد، شبکههای حسگر بیسیم از حسگرهای تشکیلدهنده این شبکه جهت حس کردن و تشخیص یک هدف خاص و دنبال کردن آن در ناحیه تحت نظارت شبکه استفاده میشود. به دلیل اینکه حسگرهای موجود در این نوع شبکهها دارای محدودیت انرژی میباشند و ارتباطات بین حسگرها به صورت بیسیم انجام میپذیرد، توجه به مسئله مصرف توان و رهگیری بدون خطا چندین هدف متحرک به صورت همزمان در این شبکهها اهمیت فراوانی دارند. الگوریتمهای رهگیری هدف در شبکههای حسگر، از نظر کاربرد و عملکرد آنها، به چهار دستهی پروتکل مبتنی بر پیام، مبتنی بر درخت، مبتنی بر پیشگویی و مبتنی بر خوشهبندی، تقسیم میگردند. در این میان پروتکلهای مبتنی بر خوشهبندی از نظر مصرف انرژی بهینه هستند. تاکنون برای رفع مشکل انرژی روشهای زیادی طرح گردیده است که میتوان به الگوریتمهای رهگیری اهداف سریع، DPT و CDTA اشاره کرد. الگوریتم رهگیری اهداف سریع قابلیت رهگیری اهداف سریع را دارا میباشد ولی از معایب آن میتوان به بالا بودن میزان ارتباطات در شبکه به دلیل کوچک بودن خوشهها اشاره کرد. الگوریتم DPT دارای یک الگوریتم پیش بین با پیچیدگی کم میباشد ولی از معایب آن میتوان به قادر نبودن آن به رهگیری چندین هدف به صورت همزمان اشاره کرد. از معایب الگوریتم CDTA میتوان به عدم وجود رویه تصحیح خطا برای شناسایی مجدد هدف گم شده، تقسیمبندی شبکه بر اساس مدل شبکه و قادر نبودن آن به رهگیری چندین هدف به صورت همزمان اشاره کرد. در الگوریتم پیشنهادی از یک دیدگاه خوشهبندی بر اساس پیشبینی به منظور مقیاسپذیر بودن شبکه و مصرف بهینه انرژی استفاده گردیده است تا در برابر خرابیهای احتمالی حسگرها و پیشبینیهای اشتباه مکان هدف مقاوم باشد. در این الگوریتم، رویه تصحیح خطایی ارائه گردیده است تا در زمانهایی که هدف به دلیل سرعت بالای خود و یا تغییر جهتهای ناگهانی از برد حسگرها خارج گردید، الگوریتم قادر به شناسایی مجدد هدف باشد. نتایج بدست آمده توسط شبیهساز نشان میدهند که الگوریتم پیشنهادی قادر به رهگیری چندین هدف به صورت همزمان میباشد و همچنین الگوریتم پیشنهادی با کم کردن ارتباطات بین خوشهای و احتمال گمشدن هدف مصرف انرژی در شبکههای حسگر را تا حد امکان کاهش میدهد.کلمات کلیدی:شبکههای حسگر، رهگيري اهداف متحرک، مقیاسپذیر بودن شبکه، مدل شبکه، الگوریتم پیش بین، الگوريتم تصحيح خطا فصل اولیکی از شبکههایی که در سالهای اخیر توجهات زیادی را به خود جلب کرده است، شبکههای حسگر بیسیم[1] (WSN) میباشند. شبکههای حسگر از تعداد زیادی حسگر تشکیل شدهاند که پس از توزیع در منطقه، حسگرهایی که در نزدیکی یک رویداد قرار دارند بعد از شناسایی آن رویداد به جمعآوری اطلاعات رویداد مورد نظر در محیط میپردازند و اطلاعات بدست آمده از رویداد را به حسگر چاهک ارسال میکنند.حسگر چاهک، حسگری است که با ایستگاه پایه[2] که در خارج از شبکههای حسگر مستقر میباشد، در ارتباط میباشد[1]. حسگرهای این شبکهها دارای یک واسط بیسیم میباشند که همین امر باعث گردیده است که این شبکهها در سطح زمین، زیر آب و دیگر مکانهای خطرناک و یا غیرقابلدسترس راهاندازی گردند. بنابراین شبکههای حسگر قادر به پوشش مناطقی هستند که شبکههای دیگر از عهده پوشش آن مناطق بر نمیآیند و در واقع شبکههای حسگر امکان تعامل بین انسان، محیط و ماشین را فراهم میکنند. گسترش شبکههای حسگر بیسیم با کاربردهای نظامی آغاز گردید ولی امروزه با گسترش سریع کاربردهای شبکههای حسگر، در زمینههای رهایی از سانحه، کنترل محیطی و نگاشت تنوع زیستی، سازههای هوشمند، مدیریت تأسیسات، کشاورزی، پزشکی و بهداشت، حملونقل، پردازش از راه دور و رهگیری هدف از شبکههای حسگر بیسیم استفاده میگردد. به همین دلیل امروزه پیشرفتهای زیادی در حوزه زیرسیستمهای الکترومکانیکی صورت پذیرفته است تا امکان توسعه حسگرهای هوشمند فراهم گردد [1].یکی از کاربردهای ذکرشده برای شبکههای حسگر، رهگیری اهداف متحرک میباشد که هدف از آن دنبال کردن یک شی خاص در یک فضای از پیش تعیینشده به نام میدان حسگر و تشخیص مسیر آن شی است. این کاربرد میتواند با قابلیت شناسایی یک هدف خاص در میان اهداف گوناگون کاملتر گردد. بدین منظور از حسگرهایی با فناوریهای متفاوت که ویژگیهای گوناگون یک پدیده را میتوانند اندازهگیری کنند در امر رهگیری هدف استفاده میگردد. این حسگرها از چهار واحد: واحد توان، واحد پردازش اطلاعات، واحد ارتباطات و واحد حس کردن تشکیل شده است. این حسگرها میتوانند از نوع حسگرهای حضور، لرزش، نور، صوت، لیزری و تصویر باشند که در این میان حسگرهای تصویری به دلیل اینکه حامل اطلاعات بسیاری هستند از اهمیت بالایی در کاربردهای رهگیری هدف برای شناسایی یک هدف خاص در میدانهای نبرد و یا ساختمانها و مکانهای عمومی برخوردارند [2].با توجه به محدودیت واحد توان حسگرها و بالا بودن مصرف انرژی حسگرهای تصویری نسبت به انواع دیگر حسگرها، بهینه مصرف شدن انرژی یکی از چالشهای مهم شبکههای حسگر محسوب میگردد. در این راستا باید مصرف انرژی اجزا حسگرها شامل ریز حسگرها، مبدل آنالوگ به دیجیتال، پردازنده سیگنال، فرستنده و گیرنده را تا حد امکان کاهش داد. تحقیقات نشان دادهاند که انرژی مورد نیاز برای ارتباطات از سایر واحدهای مصرفکننده انرژی حسگرها به دلیل بالا بودن حجم دادههای صوتی و تصویری ارسالشده توسط حسگرهای تصویری و در نتیجه تحمیل شدن سربار زیادی به سیستم انتقال داده، بیشتر میباشد [2].از آنجا که کاربردهای رهگیری هدف نیازمند ارسال اطلاعات به صورت بلادرنگ به کاربر است و بنابراین محاسبات بسیاری به صورت بلادرنگ در هر حسگر صورت میپذیرد همواره توان بسیاری در شبکه حسگر در حال مصرف است و به همین دلیل رهگیری هدف یکی از کاربردهایی است که مصرف توان آن بالا میباشد. با توجه به اینکه مصرف بهینه توان باعث پایداری و قابلیت اطمینان شبکههای حسگر در شرایط سخت میگردد و بالا بودن میزان مصرف انرژی در شبکههای حسگر، اهمیت ارائه الگوریتمهای رهگیری هدف با مصرف توان پایین را دو چندان میکند.در روشهای سنتی رهگیری هدف، از رویکردهای مرکزی برای انجام این پژوهش استفاده میگردیده است. در رویکردهای مرکزی در هر زمان تنها یک حسگر وظیفه شناسایی هدف را بر عهده دارد و بنابراین دقت رهگیری هدف پایین خواهد آمد و انرژی حسگرها به دلیل تحمیل شدن محاسبات سنگین به صورت بهینه مصرف نخواهد گردید. در این روشها با افزایش تعداد گرههای حسگر در شبکه، پیام بیشتری به سویحسگر چاهک هدایت میشوند که سبب استفاده زیاد از پهنای باند شبکه میگردد و بنابراین این رویکردها در برابر خطا مقاوم نیستند. در الگویتم های رهگیری هدف جدید، گرههای حسگری که میتوانند هدف را تشخیص دهند در حالت فعال نگه داشته میشوند و مابقیحسگرها برای صرفهجویی در مصرف توان به حالت غیرفعال میروند. برای اینکه هدف به صورت پیوسته رهگیری شود باید گروهی از حسگرها قبل از رسیدن هدف به آنها به حالت فعال بروند. این گروه ازحسگرها با توجه به سرعت و مسیر هدف تعیین میگردند. بنابراین عمده پژوهشها در زمینه رهگیری هدف برای بدست آوردن یک الگوریتم مناسب برای انتخاب بهینه این گروه ازحسگرها صورت پذیرفته است. در این تحقیقات با استفاده از حدس نزدیک به بهینه این گروه از حسگرها میزان تبادل اطلاعات میان حسگرها را به حداقل میرسانند و بنابراین زیرسیستم مخابراتی که اصلیترین منبع مصرفکننده توان حسگرها میباشد کمتر فعال میگردد و در نتیجه مصرف انرژی به صورت چشمگیری کاهش مییابد. اما دستهای دیگر از الگوریتمهای رهگیری هدف با توجه به اینکه در نظر نگرفتن کاهش مصرف انرژی در زیرسیستمهای حسی و پردازشی حسگرها ما را از امکان کاهش بیشتر مصرف توان شبکه دور میسازد، بر روی مصرف توان درون یکحسگر تمرکز کردهاند. در این الگوریتمها مصرف توان زیرسیستمهای حسگرها با ارائه الگوریتمهایی که هدف آنها رهگیری هدف با سربار پردازشی حداقل و نحوه نمونهبرداری مناسب با زمانبندی و بسامد مناسب فعالسازی زیرسیستم حسگر میباشد، کاهش مییابند [3].در پژوهشهای انجامشده در رابطه با رهگیری هدف در شبکههای حسگر بیسیم چهار رویکرد کلی وجود دارد. این رویکردها شامل رویکردهای بر مبنای پیام، بر مبنای درخت، بر مبنای پیشبینی و بر مبنای خوشهبندی میباشند. در رهگیری هدف بر مبنای پیام فرض میگردد که هدف متحرک سرعت و جهت حرکت جاری خود را برای چند لحظه حفظ میکند و از تاریخچه حرکتی هدف به منظور پیشبینی حرکت بعدی هدف استفاده میشود. بعد از تخمین حرکت بعدی هدف با استفاده از یک روش پیامرسانی همه جهته به گروهی از حسگرها که در حوزه تحویل قرار دارند پیامی را ارسال میکنند و این گروه ازحسگرها با دریافت این پیام پیش از رسیدن هدف به آنها حسگرها، فعال میگردند [3].
ارائه یک الگوریتم رهگیری هدف پویا بر اساس پیشبینی در شبکه حسگر بیسیم word
فهرست مطالبعنوانصفحهفهرست مطالب.. هشتفهرست اشکال.. یازدهفهرست جداول.. چهاردهچکیده.. 14فصل اول: مقدمه1-1- شرح و اهمیت موضوع.. 21-2- اهداف تحقیق.. 51-3- ساختار پایاننامه.. 5فصل دوم: رویکردهای رهگیری هدف2-1- مقدمه.. 72-2- رویکرد مبتنی بر پیام.. 82-2-1- پروتکل FAR 82-2-2- پروتکل VE-mobicast92-2-3- پروتکل HVE-mobicast122-3- رویکرد مبتنی بر درخت.. 132-3-1- الگوریتم DCTC 132-3-2- الگوریتم STUN 152-3-3- الگوریتم DAT 162-4- رویکرد مبتنی بر پیشبینی.. 182-4-1- الگوریتم TTMB 182-4-2- الگوریتم کاهش خطا مکانی به صورت انرژی آگاه 192-4-3- الگوریتم FTPS 212-4-4- الگوریتم HPS 222-4-5- الگوریتم PES 232-4-6- الگوریتم DPR 242-5- رویکرد مبتنی بر خوشه.. 25 2-5-1- الگوریتم رهگیری اهداف سریع 262-5-2- الگوریتم رهگیری هدف با همکاری خوشهها 272-5-3- الگوریتم DELTA 282-5-4- الگوریتم DPT 282-5-5- الگوریتم CDTA 302-6- نتیجهگیری.. 32فصل سوم: مدلهای حرکتی3-1- مقدمه.. 333-2- مکانیابی در شبکههای حسگر.. 343-2-1- الگوریتم زمان انتشار یک طرفه 343-2-2- الگوریتم زمان انتشار رفت و برگشت 343-2-3- الگوریتم فانوس دریایی 343-2-4- الگوریتم تخمین فاصله از طریق اندازهگیری قدرت سیگنال دریافتی 353-2-5- الگوریتم مکانیابی به وسیله GPS 363-2-6- الگوریتم مکانیابی تک گامه با روش فانوس دریایی 373-2-7- الگوریتم مکانیابی چند گامه بر مبنای فاصله 383-3- مدلهای حرکتی تصادفی.. 383-3-1- مدل حرکتی نقطه راه تصادفی 393-3-2- مدل حرکتی جهت تصادفی 393-3-3- مدل حرکتی راهپیمایی تصادفی 393-3-4- مدل حرکتی راهپیمایی جمعآوری 403-4- مدل حرکتی شهری.. 403-4-1- مدل حرکتی آزادراه 413-4-2- مدل حرکتی منهتن 413-5- مدلهای حرکتی وابسته زمانی.. 413-5-1- مدل حرکتی گاس- مارکوف 423-5-2- مدل حرکتی راهپیمایی تصادفی احتمالی 423-5-3- مدل حرکتی وابسته نمایی 42 3-6- مدلهای حرکتی گروهی.. 433-6-1- مدل حرکتی نقطه مرجع 433-6-2- مدلحرکتیتعقیب 433-6-3- مدل حرکتی رشتهای 443-6-4- مدل حرکتی ردیفی 443-7- نتیجهگیری.. 45فصل چهارم: تحقیقات مرتبط با الگوریتم پیشنهادی4-1- مقدمه.. 464-2- الگوریتم خوشهبندی توزیعشده به صورت هم پوشانی:.. 474-3-الگوریتم رهگیری اهداف سریع:.. 484-4-الگوریتم رهگیری توزیعشده بر اساس پیشبینی:.. 514-5-الگوریتم CDTA.. 55فصل پنجم: معماری و شبیهسازی الگوریتم پیشنهادی5-1- مقدمه.. 595-2- مقدمات الگوریتم پیشنهادی.. 605-2-1- تعاریف 605-2-2- فرضیات الگوریتم پیشنهادی 645-3- معماری الگوریتم پیشنهادی.. 665-3-1- رویه خوشهبندی 705-3-2- رویه رهگیری هدفPDTA توسط حسگرهای عضو خوشه 745-3-3- رویه رهگیری هدفPDTA توسط حسگرهای سرخوشه 745-3-4- مدل مصرف انرژی: 795-4- تنظیمات شبیهسازی.. 805-5- پارامترهای شبیهسازی.. 815-6- نتایج شبیهسازی.. 82فصل ششم:نتیجهگیری6-1- جمعبندی کلی نتایج.. 896-2- پیشنهادات.. 91مراجع.. 92 فهرست اشکالعنوانصفحهشکل2-1: نمونهای از رهگیری هدف مبتنی بر پیام.. 8شکل2-2: الگوریتمهای ارسال ابتکاری و دورهای در الگوریتم FAR.. 9شکل2-3: چند پخشی مکان زمانی.. 9شکل2-4: روند دوم مرحله تخمین تخممرغ... 10شکل2-5: نواحی مختلف تقسیمکننده شبکه، a: ناحیه یک، b: ناحیه دو، c: ناحیه سه... 11شکل2-6: مراحل الگوریتمDCTC ، a: مرحله جمعآوری داده، b: مرحله باز پیکربندی.. 13شکل2-7: الگوریتمهای هرس کردن درخت، a: الگوریتم محافظهکارانه، b: الگوریتم بر اساس پیشبینی.. 14شکل2-8: الگوریتم باز پیکربندی کامل، الف:درخت همراه قبل از باز پیکربندی کامل، ب: درخت همراه بعد از باز پیکربندی کامل.. 15شکل2-9: الگوریتم باز پیکربندی بر اساس قطع، الف: درخت همراه قبل از باز پیکربندی بر اساس قطع، ب: درخت همراه بعد از باز پیکربندی بر اساس قطع 15شکل2-10: مثالی از شکل گرفتن درخت DAB، a: گراف وزن دار حسگر، b: درخت DAB بعد از اولین مرحله.. 16شکل2- 11: الف: ارسال پیام جستجو توسط حسگر چاهک به منظور شناسایی هدف اول، ب: خارج شدن هدف اول از برد حسگرK و وارد شدن آن به برد حسگرG. 17شکل2-12: ماشین حالت الگوریتم TTMB.. 19شکل2-13: حوزههای بیدارباش کنونی و آینده.. 19شکل2-14: انواع حسگرها در رویکرد اجتناب از خطا.. 20شکل2-15: مثالی از پیشبینی سه سطحی... 22شکل2- 16: تعیین برد مخابراتی خوشه.. 23شکل2-17: توابع اکتشافی برای مکانیزم های بیدار کردن حسگرها.. 24شکل2-18: مدلهای مکانی.. 25شکل2-19: ماشین حالت الگوریتم رهگیری اهداف سریع.. 26شکل2-20: ماشین حالات الگوریتم DELTA.. 28 شکل2-21:جستجو برای حسگرهای مکانیابی با شعاع حسی کم.. 29شکل2-22:جستجو برای حسگرهای مکانیابی با شعاع حداکثری.. 29شکل2-23: جستجو برای حسگرهای مکانیابی در خوشههای مجاور.. 30 شکل2-24: سطح دوم از فرایند بازیابی هدف.. 30شکل 3-1: الگوریتم فانوس دریایی.. 35شکل 3-2: روش مثلث سازی.. 37شکل 3-3: الگوریتم مکانیابی تک گامه با روش فانوس دریایی.. 38شکل 3-4: الگوی حرکتی یک گره متحرک با استفاده از مدل حرکتی نقطه راه تصادفی.. 39شکل 3-5: الگوی حرکتی مدل راهپیمایی تصادفی بازمان حرکت ثابت.. 40شکل 3-6: انواع مدلهای شهری، a: مدل آزادراه، b: مدل منهتن.. 41شکل 3-7: تغییر مکان گروه در مدل گروهی نقطه مرجع.. 43شکل 3-8: حرکت سه گره متحرک بر اساس مدل حرکتی رشتهای.. 44شکل 4-1:دیاگرام حالت الگوریتم KOCA.. 48شکل 4-2: رویه خوشهبندی مجدد در الگوریتم رهگیری اهداف سریع.. 50شکل 4-3: الگوریتم رهگیری هدف در الگوریتم رهگیری سریع اهداف.. 51شکل 4-4: جستجو سه حسگر شایسته در برد نرمال.. 53شکل 4-5: جستجو سه حسگر شایسته در برد حداکثری.. 53شکل 4-6: جستجو سه حسگر شایسته توسط خوشههای مجاور.. 54شکل 4-7: شناسایی هدف توسط حسگرهایی که در فاصله برد نرمال تا هدف قرار دارند.. 54شکل 4-8: رویه تصحیح خطا.. 55شکل 4-9: معماری رهگیری هدف در الگوریتم CDTA.. 56شکل 4-10: چگونگی تغییر حالات حسگرها.. 57شکل 4-11: مکانیزم ارتباطی بین حسگرهای اجرایی و حسگرهای انتشاردهنده 58شکل5-1: بسته پیام اعلان سرخوشه شدن ADV-Message. 60شکل5-2: جدول سرخوشه CH-Table. 61شکل5-3: بسته پیام عضویت JREQ-Msg. 61شکل5-4: جدول خوشههای مجاور AC-Table. 62شکل5-5:جدول حسگرهای عضو خوشه.. 62شکل5-6: بسته پیام بیدارباش.. 63شکل5-7:بسته ارسال اطلاعات توسط حسگرهای شناسایی کننده هدف.. 64شکل5-8: بسته پیام انتخاب حسگرهای شایسته توسط خوشههای همسایه.. 64 شکل5-9: مدل شبکه: دایرهها نشاندهنده حسگرهای مرزی، مربعها نشاندهنده حسگرهای عضو خوشه و شش ضلعیها نشاندهنده حسگرهای سرخوشه است... 65شکل5-10: دیاگرام کلی الگوریتم PDTA.. 67شکل5-11: دیاگرام رویه خوشهبندی.. 68شکل5-12: دیاگرام رویه رهگیری هدف.. 69شکل5-13: روند اجرای ارسال پیام ADV در رویه خوشهبندی.. 71شکل5-14: ماشین حالت نشاندهنده سازوکار خوشهبندی الگوریتم پیشنهادی 72شکل5-15: شبه کد رویه خوشهبندی پیشنهادی.. 73شکل5-16:محاسبه محل هدف توسط سه حسگر شایسته.. 75شکل5-17:جستجوي سه حسگر شايسته رهگيري هدف در برد نرمال.. 77شکل5-18: جستجوي سه حسگر شايسته رهگيري هدف در برد حداکثری.. 77شکل5-19: جستجوي سه حسگر شايسته رهگيري هدف در بين خوشهها.. 78شکل5-20: مقایسه بین حرکت واقعی و حرکت پیشبینیشده توسط پیشبینی کننده برای هدف اول.. 82شکل5-21: جزئیات مقایسه بین حرکت واقعی و حرکت پیشبینیشده توسط پیش بین برای هدف اول در مسیری از مکان (464و391) تا مکان (302و8).. 82شکل5-22: مقایسه بین حرکت واقعی و حرکت پیشبینیشده توسط پیشبینی کننده برای هدف دوم.. 83شکل5-23: مقایسه بین حرکت واقعی و حرکت پیشبینیشده توسط پیشبینی کننده برای هدف سوم.. 83شکل5-24:روش بدست آوردن اندازه خطا بین موقعیت واقعی و موقعیت پیشبینیشده.. 85شکل5-25: رابطه بین احتمال گم شدن هدف و دقت رهگیری.. 85شکل5-26: احتمال گم شدن هدف در برابر سرعت هدف.. 86شکل5-27: حداکثر فاصله هدف تا سه حسگر شایسته را برای اهداف گم شده 87شکل5-28: انرژی مصرفشده در شبکه برای 2000 نقطه شناسایی هدف.. 88 فهرست جداولعنوانصفحهجدول 5-1: رویدادهای بین حالات و حالات بعدی در هر یک از حالات.. 72جدول 5-2: پارامترهای شبیهسازی.. 81جدول 5-3: مشخصات الگوریتم پیش بین خطی.. 84چکیدهبا پیشرفت تکنولوژی ساخت وسایل الکترونیکی و مقرون به صرفه شدن شبکههای حسگر در مقیاسهای بزرگ، شبکههای حسگر بیسیم زمینههای تحقیقاتی را با رشد سریع و جذابیت بسیار فراهم میکنند که توجهات زیادی را در چندین سال اخیر به خود جلب کرده است. شبکههای حسگر بیسیم با مقیاس بزرگ حاوی چند صد تا چند ده هزار حسگر، پهنه وسیعی از کاربردها و البته چالشها را به همراه دارند. ویژگیهای خاص این شبکهها، امکان استفاده از آنها را در کاربردهایی مانند کنترل و بررسی مناطق حادثهخیز، حفاظت مرزها و مراقبتهای امنیتی و نظامی فراهم میکنند. یکی از مهمترین کاربردهای متصور برای این شبکهها کاربرد رهگیری هدف میباشد. در این کاربرد، شبکههای حسگر بیسیم از حسگرهای تشکیلدهنده این شبکه جهت حس کردن و تشخیص یک هدف خاص و دنبال کردن آن در ناحیه تحت نظارت شبکه استفاده میشود. به دلیل اینکه حسگرهای موجود در این نوع شبکهها دارای محدودیت انرژی میباشند و ارتباطات بین حسگرها به صورت بیسیم انجام میپذیرد، توجه به مسئله مصرف توان و رهگیری بدون خطا چندین هدف متحرک به صورت همزمان در این شبکهها اهمیت فراوانی دارند. الگوریتمهای رهگیری هدف در شبکههای حسگر، از نظر کاربرد و عملکرد آنها، به چهار دستهی پروتکل مبتنی بر پیام، مبتنی بر درخت، مبتنی بر پیشگویی و مبتنی بر خوشهبندی، تقسیم میگردند. در این میان پروتکلهای مبتنی بر خوشهبندی از نظر مصرف انرژی بهینه هستند. تاکنون برای رفع مشکل انرژی روشهای زیادی طرح گردیده است که میتوان به الگوریتمهای رهگیری اهداف سریع، DPT و CDTA اشاره کرد. الگوریتم رهگیری اهداف سریع قابلیت رهگیری اهداف سریع را دارا میباشد ولی از معایب آن میتوان به بالا بودن میزان ارتباطات در شبکه به دلیل کوچک بودن خوشهها اشاره کرد. الگوریتم DPT دارای یک الگوریتم پیش بین با پیچیدگی کم میباشد ولی از معایب آن میتوان به قادر نبودن آن به رهگیری چندین هدف به صورت همزمان اشاره کرد. از معایب الگوریتم CDTA میتوان به عدم وجود رویه تصحیح خطا برای شناسایی مجدد هدف گم شده، تقسیمبندی شبکه بر اساس مدل شبکه و قادر نبودن آن به رهگیری چندین هدف به صورت همزمان اشاره کرد. در الگوریتم پیشنهادی از یک دیدگاه خوشهبندی بر اساس پیشبینی به منظور مقیاسپذیر بودن شبکه و مصرف بهینه انرژی استفاده گردیده است تا در برابر خرابیهای احتمالی حسگرها و پیشبینیهای اشتباه مکان هدف مقاوم باشد. در این الگوریتم، رویه تصحیح خطایی ارائه گردیده است تا در زمانهایی که هدف به دلیل سرعت بالای خود و یا تغییر جهتهای ناگهانی از برد حسگرها خارج گردید، الگوریتم قادر به شناسایی مجدد هدف باشد. نتایج بدست آمده توسط شبیهساز نشان میدهند که الگوریتم پیشنهادی قادر به رهگیری چندین هدف به صورت همزمان میباشد و همچنین الگوریتم پیشنهادی با کم کردن ارتباطات بین خوشهای و احتمال گمشدن هدف مصرف انرژی در شبکههای حسگر را تا حد امکان کاهش میدهد.کلمات کلیدی:شبکههای حسگر، رهگيري اهداف متحرک، مقیاسپذیر بودن شبکه، مدل شبکه، الگوریتم پیش بین، الگوريتم تصحيح خطا فصل اولیکی از شبکههایی که در سالهای اخیر توجهات زیادی را به خود جلب کرده است، شبکههای حسگر بیسیم[1] (WSN) میباشند. شبکههای حسگر از تعداد زیادی حسگر تشکیل شدهاند که پس از توزیع در منطقه، حسگرهایی که در نزدیکی یک رویداد قرار دارند بعد از شناسایی آن رویداد به جمعآوری اطلاعات رویداد مورد نظر در محیط میپردازند و اطلاعات بدست آمده از رویداد را به حسگر چاهک ارسال میکنند.حسگر چاهک، حسگری است که با ایستگاه پایه[2] که در خارج از شبکههای حسگر مستقر میباشد، در ارتباط میباشد[1]. حسگرهای این شبکهها دارای یک واسط بیسیم میباشند که همین امر باعث گردیده است که این شبکهها در سطح زمین، زیر آب و دیگر مکانهای خطرناک و یا غیرقابلدسترس راهاندازی گردند. بنابراین شبکههای حسگر قادر به پوشش مناطقی هستند که شبکههای دیگر از عهده پوشش آن مناطق بر نمیآیند و در واقع شبکههای حسگر امکان تعامل بین انسان، محیط و ماشین را فراهم میکنند. گسترش شبکههای حسگر بیسیم با کاربردهای نظامی آغاز گردید ولی امروزه با گسترش سریع کاربردهای شبکههای حسگر، در زمینههای رهایی از سانحه، کنترل محیطی و نگاشت تنوع زیستی، سازههای هوشمند، مدیریت تأسیسات، کشاورزی، پزشکی و بهداشت، حملونقل، پردازش از راه دور و رهگیری هدف از شبکههای حسگر بیسیم استفاده میگردد. به همین دلیل امروزه پیشرفتهای زیادی در حوزه زیرسیستمهای الکترومکانیکی صورت پذیرفته است تا امکان توسعه حسگرهای هوشمند فراهم گردد [1].یکی از کاربردهای ذکرشده برای شبکههای حسگر، رهگیری اهداف متحرک میباشد که هدف از آن دنبال کردن یک شی خاص در یک فضای از پیش تعیینشده به نام میدان حسگر و تشخیص مسیر آن شی است. این کاربرد میتواند با قابلیت شناسایی یک هدف خاص در میان اهداف گوناگون کاملتر گردد. بدین منظور از حسگرهایی با فناوریهای متفاوت که ویژگیهای گوناگون یک پدیده را میتوانند اندازهگیری کنند در امر رهگیری هدف استفاده میگردد. این حسگرها از چهار واحد: واحد توان، واحد پردازش اطلاعات، واحد ارتباطات و واحد حس کردن تشکیل شده است. این حسگرها میتوانند از نوع حسگرهای حضور، لرزش، نور، صوت، لیزری و تصویر باشند که در این میان حسگرهای تصویری به دلیل اینکه حامل اطلاعات بسیاری هستند از اهمیت بالایی در کاربردهای رهگیری هدف برای شناسایی یک هدف خاص در میدانهای نبرد و یا ساختمانها و مکانهای عمومی برخوردارند [2].با توجه به محدودیت واحد توان حسگرها و بالا بودن مصرف انرژی حسگرهای تصویری نسبت به انواع دیگر حسگرها، بهینه مصرف شدن انرژی یکی از چالشهای مهم شبکههای حسگر محسوب میگردد. در این راستا باید مصرف انرژی اجزا حسگرها شامل ریز حسگرها، مبدل آنالوگ به دیجیتال، پردازنده سیگنال، فرستنده و گیرنده را تا حد امکان کاهش داد. تحقیقات نشان دادهاند که انرژی مورد نیاز برای ارتباطات از سایر واحدهای مصرفکننده انرژی حسگرها به دلیل بالا بودن حجم دادههای صوتی و تصویری ارسالشده توسط حسگرهای تصویری و در نتیجه تحمیل شدن سربار زیادی به سیستم انتقال داده، بیشتر میباشد [2].از آنجا که کاربردهای رهگیری هدف نیازمند ارسال اطلاعات به صورت بلادرنگ به کاربر است و بنابراین محاسبات بسیاری به صورت بلادرنگ در هر حسگر صورت میپذیرد همواره توان بسیاری در شبکه حسگر در حال مصرف است و به همین دلیل رهگیری هدف یکی از کاربردهایی است که مصرف توان آن بالا میباشد. با توجه به اینکه مصرف بهینه توان باعث پایداری و قابلیت اطمینان شبکههای حسگر در شرایط سخت میگردد و بالا بودن میزان مصرف انرژی در شبکههای حسگر، اهمیت ارائه الگوریتمهای رهگیری هدف با مصرف توان پایین را دو چندان میکند.در روشهای سنتی رهگیری هدف، از رویکردهای مرکزی برای انجام این پژوهش استفاده میگردیده است. در رویکردهای مرکزی در هر زمان تنها یک حسگر وظیفه شناسایی هدف را بر عهده دارد و بنابراین دقت رهگیری هدف پایین خواهد آمد و انرژی حسگرها به دلیل تحمیل شدن محاسبات سنگین به صورت بهینه مصرف نخواهد گردید. در این روشها با افزایش تعداد گرههای حسگر در شبکه، پیام بیشتری به سویحسگر چاهک هدایت میشوند که سبب استفاده زیاد از پهنای باند شبکه میگردد و بنابراین این رویکردها در برابر خطا مقاوم نیستند. در الگویتم های رهگیری هدف جدید، گرههای حسگری که میتوانند هدف را تشخیص دهند در حالت فعال نگه داشته میشوند و مابقیحسگرها برای صرفهجویی در مصرف توان به حالت غیرفعال میروند. برای اینکه هدف به صورت پیوسته رهگیری شود باید گروهی از حسگرها قبل از رسیدن هدف به آنها به حالت فعال بروند. این گروه ازحسگرها با توجه به سرعت و مسیر هدف تعیین میگردند. بنابراین عمده پژوهشها در زمینه رهگیری هدف برای بدست آوردن یک الگوریتم مناسب برای انتخاب بهینه این گروه ازحسگرها صورت پذیرفته است. در این تحقیقات با استفاده از حدس نزدیک به بهینه این گروه از حسگرها میزان تبادل اطلاعات میان حسگرها را به حداقل میرسانند و بنابراین زیرسیستم مخابراتی که اصلیترین منبع مصرفکننده توان حسگرها میباشد کمتر فعال میگردد و در نتیجه مصرف انرژی به صورت چشمگیری کاهش مییابد. اما دستهای دیگر از الگوریتمهای رهگیری هدف با توجه به اینکه در نظر نگرفتن کاهش مصرف انرژی در زیرسیستمهای حسی و پردازشی حسگرها ما را از امکان کاهش بیشتر مصرف توان شبکه دور میسازد، بر روی مصرف توان درون یکحسگر تمرکز کردهاند. در این الگوریتمها مصرف توان زیرسیستمهای حسگرها با ارائه الگوریتمهایی که هدف آنها رهگیری هدف با سربار پردازشی حداقل و نحوه نمونهبرداری مناسب با زمانبندی و بسامد مناسب فعالسازی زیرسیستم حسگر میباشد، کاهش مییابند [3].در پژوهشهای انجامشده در رابطه با رهگیری هدف در شبکههای حسگر بیسیم چهار رویکرد کلی وجود دارد. این رویکردها شامل رویکردهای بر مبنای پیام، بر مبنای درخت، بر مبنای پیشبینی و بر مبنای خوشهبندی میباشند. در رهگیری هدف بر مبنای پیام فرض میگردد که هدف متحرک سرعت و جهت حرکت جاری خود را برای چند لحظه حفظ میکند و از تاریخچه حرکتی هدف به منظور پیشبینی حرکت بعدی هدف استفاده میشود. بعد از تخمین حرکت بعدی هدف با استفاده از یک روش پیامرسانی همه جهته به گروهی از حسگرها که در حوزه تحویل قرار دارند پیامی را ارسال میکنند و این گروه ازحسگرها با دریافت این پیام پیش از رسیدن هدف به آنها حسگرها، فعال میگردند [3].