— (309)

دانشگاه صنعتی اصفهان
دانشکده برق و کامپيوتر
ارائه یک الگوریتم رهگیری هدف پویا بر اساس پیش‌بینی در شبکه حسگر بی‌سیم
پايان‌نامه کارشناسی ارشد مهندسی کامپیوتر- معماری کامپیوتر
مهدی حیدری دهوئی
استاد راهنما
دکتر مهدی مهدوی
1391

دانشگاه صنعتی اصفهان
دانشکده برق و کامپيوتر
پايان‌نامه‌ی کارشناسی ارشد رشته‌ی مهندسی کامپیوتر – معماری کامپیوتر
آقای مهدی حیدری دهوئی
تحت عنوان
ارائه یک الگوریتم رهگیری هدف پویا بر اساس پیش‌بینی در شبکه حسگر بی‌سیم
در تاريخ 19/12/1391 توسط کميته‌ی تخصصی زير مورد بررسی و تصويب نهايی قرار گرفت.
1- استاد راهنمای پايان‌نامهمهدی مهدوی
2- استاد داور مسعود رضا هاشمی
3- استاد داور محمدحسین منشئی
سرپرست تحصيلات تکميلی دانشکدهمسعود عمومی
سپاس و ستایش خدایی را سزاست که با قلم توانای خویش مشتی خاک را توانی دگر بخشید تا بتوانم در صحنه زندگی بیاندیشم و با افکار خویش تصاویر زندگی را نقش بسته و استعدادها و توانائیها را به خدمت گیرم تا باقدرت اندیشه لحظات زندگی را حلاوتی دگر بخشم.
خالصانه‌ترین سلام‌ها را نثار اساتیدی می‌نمایم که برایم زندگی کردن و انسان بودن را معنا کردند و در لحظات سخت زندگی مرا یار و یاوری دلسوز و مشوقی اثرگذار بودند.
در خاتمه باید به خاطر محبتهای کریمانه و راهنمائیهای هدایتگرانه استاد راهنما جناب دکتر مهدی مهدوی ، مراتب تقدیر و تشکر و قدرشناسی خود را از آن بزرگوار بر خود واجب و سعادت و سربلندی و عزت را برای آن استاد فرهیخته مسئلت مینمایم.
کلیه حقوق مادی مترتب بر نتایج مطالعات،
ابتکارات و نوآوری‌های ناشی از تحقیق موضوع
این پایان‌نامه متعلق به دانشگاه صنعتی اصفهان
است.

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

فهرست مطالب
عنوان صفحه
فهرست مطالبهشتفهرست اشکالیازده
فهرست جداولچهارده
TOC h z t “Heading 1,2,Heading 2,3,No Spacing,1” چکیده PAGEREF _Toc353103012 h 14فصل اول: مقدمه1-1- شرح و اهمیت موضوع PAGEREF _Toc353103015 h 21-2- اهداف تحقیق PAGEREF _Toc353103016 h 51-3- ساختار پایان‌نامه PAGEREF _Toc353103017 h 5فصل دوم: رویکردهای رهگیری هدف2-1- مقدمه PAGEREF _Toc353103020 h 72-2- رویکرد مبتنی بر پیام PAGEREF _Toc353103021 h 82-2-1- پروتکل FAR PAGEREF _Toc353103022 h 82-2-2- پروتکل VE-mobicast PAGEREF _Toc353103023 h 92-2-3- پروتکل HVE-mobicast PAGEREF _Toc353103024 h 122-3- رویکرد مبتنی بر درخت PAGEREF _Toc353103025 h 132-3-1- الگوریتم DCTC PAGEREF _Toc353103026 h 132-3-2- الگوریتم STUN PAGEREF _Toc353103027 h 152-3-3- الگوریتم DAT PAGEREF _Toc353103028 h 162-4- رویکرد مبتنی بر پیش‌بینی PAGEREF _Toc353103029 h 182-4-1- الگوریتم TTMB PAGEREF _Toc353103030 h 182-4-2- الگوریتم کاهش خطا مکانی به صورت انرژی آگاه PAGEREF _Toc353103031 h 192-4-3- الگوریتم FTPS PAGEREF _Toc353103032 h 212-4-4- الگوریتم HPS PAGEREF _Toc353103033 h 222-4-5- الگوریتم PES PAGEREF _Toc353103034 h 232-4-6- الگوریتم DPR PAGEREF _Toc353103035 h 242-5- رویکرد مبتنی بر خوشه PAGEREF _Toc353103036 h 252-5-1- الگوریتم رهگیری اهداف سریع PAGEREF _Toc353103037 h 262-5-2- الگوریتم رهگیری هدف با همکاری خوشهها PAGEREF _Toc353103038 h 272-5-3- الگوریتم DELTA PAGEREF _Toc353103039 h 282-5-4- الگوریتم DPT PAGEREF _Toc353103040 h 282-5-5- الگوریتم CDTA PAGEREF _Toc353103041 h 302-6- نتیجه‌گیری PAGEREF _Toc353103042 h 32فصل سوم: مدل‌های حرکتی3-1- مقدمه PAGEREF _Toc353103045 h 333-2- مکان‌یابی در شبکه‌های حسگر PAGEREF _Toc353103046 h 343-2-1- الگوریتم زمان انتشار یک طرفه PAGEREF _Toc353103047 h 343-2-2- الگوریتم زمان انتشار رفت و برگشت PAGEREF _Toc353103048 h 343-2-3- الگوریتم فانوس دریایی PAGEREF _Toc353103049 h 343-2-4- الگوریتم تخمین فاصله از طریق اندازه‌گیری قدرت سیگنال دریافتی PAGEREF _Toc353103050 h 353-2-5- الگوریتم مکان‌یابی به وسیله GPS PAGEREF _Toc353103051 h 363-2-6- الگوریتم مکان‌یابی تک گامه با روش فانوس دریایی PAGEREF _Toc353103052 h 373-2-7- الگوریتم مکان‌یابی چند گامه بر مبنای فاصله PAGEREF _Toc353103053 h 383-3- مدل‌های حرکتی تصادفی PAGEREF _Toc353103054 h 383-3-1- مدل حرکتی نقطه راه تصادفی PAGEREF _Toc353103055 h 393-3-2- مدل حرکتی جهت تصادفی PAGEREF _Toc353103056 h 393-3-3- مدل حرکتی راهپیمایی تصادفی PAGEREF _Toc353103057 h 393-3-4- مدل حرکتی راهپیمایی جمع‌آوری PAGEREF _Toc353103058 h 403-4- مدل حرکتی شهری PAGEREF _Toc353103059 h 403-4-1- مدل حرکتی آزادراه PAGEREF _Toc353103060 h 413-4-2- مدل حرکتی منهتن PAGEREF _Toc353103061 h 413-5- مدل‌های حرکتی وابسته زمانی PAGEREF _Toc353103062 h 413-5-1- مدل حرکتی گاس- مارکوف PAGEREF _Toc353103063 h 423-5-2- مدل حرکتی راهپیمایی تصادفی احتمالی PAGEREF _Toc353103064 h 423-5-3- مدل حرکتی وابسته نمایی PAGEREF _Toc353103065 h 423-6- مدل‌های حرکتی گروهی PAGEREF _Toc353103066 h 433-6-1- مدل حرکتی نقطه مرجع PAGEREF _Toc353103067 h 433-6-2- مدل حرکتی تعقیب PAGEREF _Toc353103068 h 433-6-3- مدل حرکتی رشته‌ای PAGEREF _Toc353103069 h 443-6-4- مدل حرکتی ردیفی PAGEREF _Toc353103070 h 443-7- نتیجه‌گیری PAGEREF _Toc353103071 h 45فصل چهارم: تحقیقات مرتبط با الگوریتم پیشنهادی4-1- مقدمه PAGEREF _Toc353103074 h 464-2- الگوریتم خوشه‌بندی توزیع‌شده به صورت هم پوشانی: PAGEREF _Toc353103075 h 474-3- الگوریتم رهگیری اهداف سریع: PAGEREF _Toc353103076 h 484-4- الگوریتم رهگیری توزیع‌شده بر اساس پیش‌بینی: PAGEREF _Toc353103077 h 514-5- الگوریتم CDTA PAGEREF _Toc353103078 h 55فصل پنجم: معماری و شبیه‌سازی الگوریتم پیشنهادی5-1- مقدمه PAGEREF _Toc353103081 h 595-2- مقدمات الگوریتم پیشنهادی PAGEREF _Toc353103082 h 605-2-1- تعاریف PAGEREF _Toc353103083 h 605-2-2- فرضیات الگوریتم پیشنهادی PAGEREF _Toc353103084 h 645-3- معماری الگوریتم پیشنهادی PAGEREF _Toc353103085 h 665-3-1- رویه خوشه‌بندی PAGEREF _Toc353103086 h 705-3-2- رویه رهگیری هدفPDTA توسط حسگرهای عضو خوشه PAGEREF _Toc353103087 h 745-3-3- رویه رهگیری هدفPDTA توسط حسگرهای سرخوشه PAGEREF _Toc353103088 h 745-3-4- مدل مصرف انرژی: PAGEREF _Toc353103089 h 795-4- تنظیمات شبیه‌سازی PAGEREF _Toc353103090 h 805-5- پارامترهای شبیه‌سازی PAGEREF _Toc353103091 h 815-6- نتایج شبیه‌سازی PAGEREF _Toc353103092 h 82فصل ششم: نتیجه‌گیری6-1- جمع‌بندی کلی نتایج PAGEREF _Toc353103095 h 896-2- پیشنهادات PAGEREF _Toc353103096 h 91مراجع PAGEREF _Toc353103097 h 92
فهرست اشکال
عنوان صفحه
TOC f h z t “Subtitle,1” شکل2-1: نمونه‌ای از رهگیری هدف مبتنی بر پیام PAGEREF _Toc350882376 h 8شکل2-2: الگوریتم‌های ارسال ابتکاری و دوره‌ای در الگوریتم FAR PAGEREF _Toc350882377 h 9شکل2-3: چند پخشی مکان زمانی PAGEREF _Toc350882378 h 9شکل2-4: روند دوم مرحله تخمین تخممرغ. PAGEREF _Toc350882379 h 10شکل2-5: نواحی مختلف تقسیم‌کننده شبکه، a: ناحیه یک، b: ناحیه دو، c: ناحیه سه. PAGEREF _Toc350882380 h 11شکل2-6: مراحل الگوریتمDCTC ، a: مرحله جمع‌آوری داده، b: مرحله باز پیکربندی PAGEREF _Toc350882381 h 13شکل2-7: الگوریتم‌های هرس کردن درخت، a: الگوریتم محافظه‌کارانه، b: الگوریتم بر اساس پیش‌بینی PAGEREF _Toc350882382 h 14شکل2-8: الگوریتم باز پیکربندی کامل، الف:درخت همراه قبل از باز پیکربندی کامل، ب: درخت همراه بعد از باز پیکربندی کامل PAGEREF _Toc350882383 h 15شکل2-9: الگوریتم باز پیکربندی بر اساس قطع، الف: درخت همراه قبل از باز پیکربندی بر اساس قطع، ب: درخت همراه بعد از باز پیکربندی بر اساس قطع PAGEREF _Toc350882384 h 15شکل2-10: مثالی از شکل گرفتن درخت DAB، a: گراف وزن دار حسگر، b: درخت DAB بعد از اولین مرحله PAGEREF _Toc350882385 h 16شکل2- 11: الف: ارسال پیام جستجو توسط حسگر چاهک به منظور شناسایی هدف اول، ب: خارج شدن هدف اول از برد حسگرK و وارد شدن آن به برد حسگرG. PAGEREF _Toc350882386 h 17شکل2-12: ماشین حالت الگوریتم TTMB PAGEREF _Toc350882387 h 19شکل2-13: حوزه‌های بیدارباش کنونی و آینده PAGEREF _Toc350882388 h 19شکل2-14: انواع حسگرها در رویکرد اجتناب از خطا PAGEREF _Toc350882389 h 20شکل2-15: مثالی از پیش‌بینی سه سطحی. PAGEREF _Toc350882390 h 22شکل2- 16: تعیین برد مخابراتی خوشه PAGEREF _Toc350882391 h 23شکل2-17: توابع اکتشافی برای مکانیزم های بیدار کردن حسگرها PAGEREF _Toc350882392 h 24شکل2-18: مدل‌های مکانی PAGEREF _Toc350882393 h 25شکل2-19: ماشین حالت الگوریتم رهگیری اهداف سریع PAGEREF _Toc350882394 h 26شکل2-20: ماشین حالات الگوریتم DELTA PAGEREF _Toc350882395 h 28شکل2-21:جستجو برای حسگرهای مکان‌یابی با شعاع حسی کم PAGEREF _Toc350882396 h 29شکل2-22:جستجو برای حسگرهای مکان‌یابی با شعاع حداکثری PAGEREF _Toc350882397 h 29شکل2-23: جستجو برای حسگرهای مکان‌یابی در خوشه‌های مجاور PAGEREF _Toc350882398 h 30شکل2-24: سطح دوم از فرایند بازیابی هدف PAGEREF _Toc350882399 h 30شکل 3-1: الگوریتم فانوس دریایی PAGEREF _Toc350882400 h 35شکل 3-2: روش مثلث سازی PAGEREF _Toc350882401 h 37شکل 3-3: الگوریتم مکان‌یابی تک گامه با روش فانوس دریایی PAGEREF _Toc350882402 h 38شکل 3-4: الگوی حرکتی یک گره متحرک با استفاده از مدل حرکتی نقطه راه تصادفی PAGEREF _Toc350882403 h 39شکل 3-5: الگوی حرکتی مدل راهپیمایی تصادفی بازمان حرکت ثابت PAGEREF _Toc350882404 h 40شکل 3-6: انواع مدل‌های شهری، a: مدل آزادراه، b: مدل منهتن PAGEREF _Toc350882405 h 41شکل 3-7: تغییر مکان گروه در مدل گروهی نقطه مرجع PAGEREF _Toc350882406 h 43شکل 3-8: حرکت سه گره متحرک بر اساس مدل حرکتی رشتهای PAGEREF _Toc350882407 h 44شکل 4-1:دیاگرام حالت الگوریتم KOCA PAGEREF _Toc350882408 h 48شکل 4-2: رویه خوشه‌بندی مجدد در الگوریتم رهگیری اهداف سریع PAGEREF _Toc350882409 h 50شکل 4-3: الگوریتم رهگیری هدف در الگوریتم رهگیری سریع اهداف PAGEREF _Toc350882410 h 51شکل 4-4: جستجو سه حسگر شایسته در برد نرمال PAGEREF _Toc350882411 h 53شکل 4-5: جستجو سه حسگر شایسته در برد حداکثری PAGEREF _Toc350882412 h 53شکل 4-6: جستجو سه حسگر شایسته توسط خوشه‌های مجاور PAGEREF _Toc350882413 h 54شکل 4-7: شناسایی هدف توسط حسگرهایی که در فاصله برد نرمال تا هدف قرار دارند PAGEREF _Toc350882414 h 54شکل 4-8: رویه تصحیح خطا PAGEREF _Toc350882415 h 55شکل 4-9: معماری رهگیری هدف در الگوریتم CDTA PAGEREF _Toc350882416 h 56شکل 4-10: چگونگی تغییر حالات حسگرها PAGEREF _Toc350882417 h 57شکل 4-11: مکانیزم ارتباطی بین حسگرهای اجرایی و حسگرهای انتشاردهنده PAGEREF _Toc350882418 h 58شکل5-1: بسته پیام اعلان سرخوشه شدن ADV-Message PAGEREF _Toc350882419 h 60شکل5-2: جدول سرخوشه CH-Table PAGEREF _Toc350882420 h 61شکل5-3: بسته پیام عضویت JREQ-Msg PAGEREF _Toc350882421 h 61شکل5-4: جدول خوشه‌های مجاور AC-Table PAGEREF _Toc350882422 h 62شکل5-5:جدول حسگرهای عضو خوشه PAGEREF _Toc350882423 h 62شکل5-6: بسته پیام بیدارباش PAGEREF _Toc350882424 h 63شکل5-7:بسته ارسال اطلاعات توسط حسگرهای شناسایی کننده هدف PAGEREF _Toc350882425 h 64شکل5-8: بسته پیام انتخاب حسگرهای شایسته توسط خوشه‌های همسایه PAGEREF _Toc350882426 h 64شکل5-9: مدل شبکه: دایره‌ها نشان‌دهنده حسگرهای مرزی، مربع‌ها نشان‌دهنده حسگرهای عضو خوشه و شش ضلعی‌ها نشان‌دهنده حسگرهای سرخوشه است. PAGEREF _Toc350882427 h 65شکل5-10: دیاگرام کلی الگوریتم PDTA PAGEREF _Toc350882429 h 67شکل5-11: دیاگرام رویه خوشه‌بندی PAGEREF _Toc350882430 h 68شکل5-12: دیاگرام رویه رهگیری هدف PAGEREF _Toc350882431 h 69شکل5-13: روند اجرای ارسال پیام ADV در رویه خوشه‌بندی PAGEREF _Toc350882432 h 71شکل5-14: ماشین حالت نشان‌دهنده سازوکار خوشه‌بندی الگوریتم پیشنهادی PAGEREF _Toc350882433 h 72شکل5-15: شبه کد رویه خوشه‌بندی پیشنهادی PAGEREF _Toc350882435 h 73شکل5-16:محاسبه محل هدف توسط سه حسگر شایسته PAGEREF _Toc350882436 h 75شکل5-17:جستجوي سه حسگر شايسته رهگيري هدف در برد نرمال PAGEREF _Toc350882437 h 77شکل5-18: جستجوي سه حسگر شايسته رهگيري هدف در برد حداکثری PAGEREF _Toc350882438 h 77شکل5-19: جستجوي سه حسگر شايسته رهگيري هدف در بين خوشه‌ها PAGEREF _Toc350882439 h 78شکل5-20: مقایسه بین حرکت واقعی و حرکت پیش‌بینی‌شده توسط پیش‌بینی کننده برای هدف اول PAGEREF _Toc350882441 h 82شکل5-21: جزئیات مقایسه بین حرکت واقعی و حرکت پیش‌بینی‌شده توسط پیش بین برای هدف اول در مسیری از مکان (464و391) تا مکان (302و8) PAGEREF _Toc350882442 h 82شکل5-22: مقایسه بین حرکت واقعی و حرکت پیش‌بینی‌شده توسط پیش‌بینی کننده برای هدف دوم PAGEREF _Toc350882443 h 83شکل5-23: مقایسه بین حرکت واقعی و حرکت پیش‌بینی‌شده توسط پیش‌بینی کننده برای هدف سوم PAGEREF _Toc350882444 h 83شکل5-24:روش بدست آوردن اندازه خطا بین موقعیت واقعی و موقعیت پیش‌بینی‌شده PAGEREF _Toc350882446 h 85شکل5-25: رابطه بین احتمال گم شدن هدف و دقت رهگیری PAGEREF _Toc350882447 h 85شکل5-26: احتمال گم شدن هدف در برابر سرعت هدف PAGEREF _Toc350882448 h 86شکل5-27: حداکثر فاصله هدف تا سه حسگر شایسته را برای اهداف گم شده PAGEREF _Toc350882449 h 87شکل5-28: انرژی مصرف‌شده در شبکه برای 2000 نقطه شناسایی هدف PAGEREF _Toc350882450 h 88

فهرست جداول
عنوان صفحه
جدول 5-1: رویدادهای بین حالات و حالات بعدی در هر یک از حالات PAGEREF _Toc349520500 h 72جدول 5-2: پارامترهای شبیه‌سازی PAGEREF _Toc349520505 h 81جدول 5-3: مشخصات الگوریتم پیش بین خطی PAGEREF _Toc349520509 h 84چکیدهبا پیشرفت تکنولوژی ساخت وسایل الکترونیکی و مقرون به صرفه شدن شبکه‌های حسگر در مقیاس‌های بزرگ، شبکههای حسگر بیسیم زمینه‌های تحقیقاتی را با رشد سریع و جذابیت بسیار فراهم میکنند که توجهات زیادی را در چندین سال اخیر به خود جلب کرده است. شبکه‌های حسگر بی‌سیم با مقیاس بزرگ حاوی چند صد تا چند ده هزار حسگر، پهنه وسیعی از کاربردها و البته چالش‌ها را به همراه دارند. ویژگی‌های خاص این شبکه‌ها، امکان استفاده از آن‌ها را در کاربردهایی مانند کنترل و بررسی مناطق حادثه‌خیز، حفاظت مرزها و مراقبت‌های امنیتی و نظامی فراهم میکنند. یکی از مهم‌ترین کاربردهای متصور برای این شبکه‌ها کاربرد رهگیری هدف می‌باشد. در این کاربرد، شبکه‌های حسگر بی‌سیم از حسگرهای تشکیل‌دهنده این شبکه جهت حس کردن و تشخیص یک هدف خاص و دنبال کردن آن در ناحیه تحت نظارت شبکه استفاده می‌شود. به دلیل اینکه حسگرهای موجود در این نوع شبکه‌ها دارای محدودیت انرژی می‌باشند و ارتباطات بین حسگرها به صورت بی‌سیم انجام میپذیرد، توجه به مسئله مصرف توان و رهگیری بدون خطا چندین هدف متحرک به صورت همزمان در این شبکه‌ها اهمیت فراوانی دارند. الگوریتم‌های رهگیری هدف در شبکه‌های حسگر، از نظر کاربرد و عملکرد آن‌ها، به چهار دستهی پروتکل مبتنی بر پیام، مبتنی بر درخت، مبتنی بر پیش‌گویی و مبتنی بر خوشه‌بندی، تقسیم میگردند. در این میان پروتکل‌های مبتنی بر خوشه‌بندی از نظر مصرف انرژی بهینه هستند. تاکنون برای رفع مشکل انرژی روش‌های زیادی طرح گردیده است که می‌توان به الگوریتم‌های رهگیری اهداف سریع، DPT و CDTA اشاره کرد. الگوریتم رهگیری اهداف سریع قابلیت رهگیری اهداف سریع را دارا می‌باشد ولی از معایب آن می‌توان به بالا بودن میزان ارتباطات در شبکه به دلیل کوچک بودن خوشه‌ها اشاره کرد. الگوریتم DPT دارای یک الگوریتم پیش بین با پیچیدگی کم می‌باشد ولی از معایب آن می‌توان به قادر نبودن آن به رهگیری چندین هدف به صورت همزمان اشاره کرد. از معایب الگوریتم CDTA می‌توان به عدم وجود رویه تصحیح خطا برای شناسایی مجدد هدف گم شده، تقسیم‌بندی شبکه بر اساس مدل شبکه و قادر نبودن آن به رهگیری چندین هدف به صورت همزمان اشاره کرد. در الگوریتم پیشنهادی از یک دیدگاه خوشه‌بندی بر اساس پیش‌بینی به منظور مقیاس‌پذیر بودن شبکه و مصرف بهینه انرژی استفاده گردیده است تا در برابر خرابی‌های احتمالی حسگرها و پیش‌بینی‌های اشتباه مکان هدف مقاوم باشد. در این الگوریتم، رویه تصحیح خطایی ارائه گردیده است تا در زمان‌هایی که هدف به دلیل سرعت بالای خود و یا تغییر جهت‌های ناگهانی از برد حسگرها خارج گردید، الگوریتم قادر به شناسایی مجدد هدف باشد. نتایج بدست آمده توسط شبیه‌ساز نشان میدهند که الگوریتم پیشنهادی قادر به رهگیری چندین هدف به صورت همزمان می‌باشد و همچنین الگوریتم پیشنهادی با کم کردن ارتباطات بین خوشهای و احتمال گمشدن هدف مصرف انرژی در شبکه‌های حسگر را تا حد امکان کاهش میدهد.
کلمات کلیدی: شبکه‌های حسگر، رهگيري اهداف متحرک، مقیاس‌پذیر بودن شبکه، مدل شبکه، الگوریتم پیش بین، الگوريتم تصحيح خطا

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

-38100-76073000فصل دومرویکردهای رهگیری هدف2-1- مقدمهامروزه در محیط‌های نظامی به دلیل پیچیده بودن و یا غیرعملی بودن پیاده‌سازی شبکههای سیمی در آنها، امکان پیادهسازی چنین شبکه‌هایی ناممکن گردیده است. توپولوژی شبکه‌ها در چنین محیط‌ها، به دلیل اینکه امکان از بین رفتن حسگرهای درون شبکه وجود دارد، باید قابلیت پیادهسازی به صورت پویا در شبکه موجود باشد، بنابراین امکان پیاده‌سازی شبکههای بی‌سیم دارای ساختار ثابت ناممکن می‌گردد و لزوم به وجود آمدن شبکههای حسگر بی‌سیم پیش از پیش احساس میگردید. یکی از مهمترین زمینه‌هایی که مزایای شبکه‌های حسگر بی‌سیم را نسبت به انواع دیگر شبکه‌های بی‌سیم نمایان کرده است، زمینه رهگیری اهداف متحرک است.رهگیری اهداف متحرک اشاره به دنبال کردن یک هدف خاص در یک فضای از پیش تعیین‌شده به نام میدان حسگر و تشخیص مسیر هدف دارد که در زمینه‌های نظامی به منظور ردیابی وسایل دشمن، تشخیص عبور غیرمجاز از مرزها و ردیابی عامل متجاوز و … و همچنین در زمینه‌های غیرنظامی به منظور ردیابی حیوانات وحشی و کمیاب در حیات وحش، تشخیص مسیر حرکت آتش در جنگل و … استفاده گردیده است. از آنجا که رهگیری هدف توسط شبکه‌های حسگر بی‌سیم، به کاهش یافتن تلفات انسانی در زمینه‌های نظامی و از بین بردن خطای دید انسان‌ها در رهگیری هدف در شب کمک کرده است و امکان رهگیری هدف با دقتی بالاتر از دقت انسان را فراهم می‌نماید، از اهمیت ویژه‌ای برخوردار گردیده است. در سال‌های اخیر، تحقیقات بی‌شماری درباره کاربرد رهگیری هدف در شبکه‌های حسگر بی‌سیم انجام گرفته است که هر یک بر روی اهداف خاصی تمرکز داشته‌اند. در این فصل الگوریتم‌های رهگیری هدف در چهار بخش مختلف بررسی می‌گردند. در بخش اول الگوریتم‌هایی بررسی میشوند که رهگیری هدف را مبتنی بر پیام انجام می‌دهند. الگوریتم‌های بخش دوم نیز از روشی مبتنی بر درخت جهت رهگیری هدف استفاده می‌کنند. الگوریتم‌های
بخش سوم هم از روش‌هایی مبتنی بر پیشگویی به منظور رهگیری هدف استفاده می‌کنند. الگوریتم‌های بخش چهارم از روش‌هایی مبتنی بر خوشه به منظور رهگیری هدف استفاده می‌کنند.
2-2-رویکرد مبتنی بر پیامدر رویکرد مبتنی بر پیام، گروهی از حسگرها قبل از اینکه هدف به آنها برسد از طریق ارسال چند پخشی به حالت فعال بروند تا در موقع رسیدن هدف به آنها بتوانند آن را مکان‌یابی کنند[3]. نمونه‌ای از رهگیری هدف مبتنی بر پیام در REF _Ref349434763 h شکل2-1 نشان داده شده است. در این شکل، حوزه‌های تحویل و ارسال با خطوط نقطه‌چین مشخص‌شده‌اند. حوزه تحویل حوزه‌ای است که در آن حسگرها در زمان جاری فعال هستند اما حوزه ارسال حوزه‌ای است که در آن حسگرها باید عمل ارسال پیام به حوزه تحویل در زمان بعدی را به عهده بگیرند.

شکل2- SEQ شکل2- * ARABIC 1: نمونهای از رهگیری هدف مبتنی بر پیام[4].2-2-1- پروتکل FARدر پروتکل FAR [5]، ابتدا شبکه به صورت یک گراف مسطح در نظر گرفته می‌شود و حسگری که حداقل یکی از همسایه‌های فضایی آن متعلق به حوزه تحویل باشد، بسته پیام خود را به صورت همگانی ارسال خواهد کرد. همسایه‌های فضایی حسگر i، حسگرهایی هستند که به حوزه‌های همسایه حسگر i تعلق دارند. بسته ارسالی توسط این پروتکل شامل فیلدهای موقعیت اولین ارسال‌کننده پیام، مختصات حوزه تحویل، سرعت حرکت حوزه تحویل، موقعیت آخرین ارسال‌کننده پیام می‌باشد. در این پروتکل در ابتدا بسته پیام به حسگرهایی که متعلق به حوزه‌های تحویل جاری و گذشته می‌باشند و یا حسگرهایی که حداقل یکی از همسایه‌های فضایی آن به حوزه‌های جاری و یا گذشته متعلق می‌باشند، ارسال می‌گردد که به این روش، ارسال ابتکاری گفته می‌شود. بعد از ارسال به روش ابتکاری، بسته پیام برای حسگرهایی که دارای همسایه فضایی متعلق به حوزه تحویل جاری نمی‌باشند ولی آن حسگر و یا حداقل یکی از همسایه‌های فضایی آن حسگر، متعلق به حوزه تحویل آینده می‌باشند ارسال می‌گردد که به این روش، ارسال دوره‌ای گویند. در REF _Ref349434822 h شکل2-2 مشاهده می‌شود که بسته پیام برای حسگرهای k،D،B، C و G به وسیله روش ابتکاری و برای حسگرهای G، L، M، E وF به وسیله روش دوره‌ای ارسال گردیده است.

شکل2- SEQ شکل2- * ARABIC 2: الگوریتم‌های ارسال ابتکاری و دوره‌ای در الگوریتم FAR[5].2-2-2- پروتکل VE-mobicastدر پروتکل VE-mobicast [6]، روشی ارائه گردیده است که در آن بر خلاف مقاله‌های قبل از آن، از جهت حرکت نیز به عنوان عاملی برای تعیین حوزه تحویل استفاده ‌شده است. نوآوری این مقاله در ایجاد شکل تخم‌مرغی متغییر حوزه تحویل است تا دقت در رهگیری هدف افزایش یابد. یک جلسه چند پخشی مکانی زمانی شامل پیام، حوزه تحویل، زمان ارسال پیام و زمان خود جلسه است. حوزه تحویل حوزهای است که در آن حسگرها در زمان جاری فعال هستند اما حوزه ارسال حوزهای است که در آن حسگرها باید عمل ارسال پیام به حوزه تحویل در زمان بعدی را به عهده بگیرند. در REF _Ref349434871 h شکل2-3 حوزه ارسال و حوزه تحویل نشان داده شده است.

شکل2- SEQ شکل2- * ARABIC 3: چند پخشی مکان زمانی[6].در الگوریتم پیشنهادی شکل حوزه ارسال مانند یک تخم‌مرغ است که می‌تواند با مرور زمان تغییر کند. حوزه نگهداشت و ارسال به حوزه فصل مشترک مناطق ارسال زمان جاری و زمان بعدی گفته می‌شود. این راه حل دارای دو مرحله است. در مرحله اول که تخمین تخم‌مرغ نام دارد اندازه حوزه تخم‌مرغی ارسال زمان بعد توسط حسگرها در حوزه نگهداشت و ارسال زمان جاری، توسط رابطه2-1 تخمین زده می‌شود.
(2-1)
در رابطه بالا e اشاره به نصف فاصله مراکز حوزه ارسال زمان جاری و زمان بعدی دارد. حوزه ارسال فرستادن مجدد پیام را به یک حوزه خاص محدود می‌کند درحالی‌که مطمئن می‌شود تمام حسگرهای موجود در حوزه ارسال، پیام را دریافت می‌کنند. در مرحله دوم که ارسال پیام توزیع‌شده نام دارد الگوریتمی توزیع‌شده برای تمام حسگرها در حوزه نگهداشت و ارسال اجرا می‌شود. این عملیات می‌تواند شکل حوزه ارسال زمان بعدی را تنظیم کند.
در پروتکل بالا، مرحله تخمین تخم‌مرغ به دو مرحله تقسیم می‌گردد. در مرحله اول باید حسگرهایی که در حوزه نگهداشت و ارسال قرار دارند تشخیص داده شوند. بدین منظور ابتدا با توجه به رابطه 2-2 تشخیص داده می‌گردد که حسگری با موقعیت(a,b) در حوزه ارسال در زمان جاری قرار دارد و یا خیر. در صورت اثبات وجود حسگر در حوزه ارسال جاری با توجه به رابطه2-3 نشان داده می‌شود که آیا حسگر مورد نظر در حوزه ارسال در زمان بعدی است و یا خیر. در صورتی که حسگر مورد نظر در هر دو حوزه موجود باشد، بنابراین حسگر مورد نظر به دو حوزه نگهداشت و حوزه ارسال زمان جاری تعلق دارد.
(2-2)
(2-3)
در مرحله دوم تخمین تخم‌مرغ تعداد گام‌های ارسال تخمین زده می‌شود. در این مرحله ابتدا توسط یک حسگر که در حوزه نگهداشت و ارسال قرار دارد (P1)، اندازه گام ارسال به حسگر همسایه در حوزه تحویل آینده (P2) و موقعیت آن حسگر محاسبه می‌گردد. با بدست آوردن نقطه تلاقی حاصل از برخورد منحنی‌های حوزه ارسال در زمان بعدی و امتداد مسیر توسط رابطه2-4 تعداد گام‌ها تخمین زده می‌شود.
(2-4)
در رابطه 2-4، P3 اشاره به نقطه تلاقی حاصل از برخورد منحنی‌های حوزه ارسال در زمان بعدی و امتداد مسیر اشاره دارد و d نیز به اندازه گام اشاره دارد. روند مرحله دوم تخمین تخم‌مرغ در REF _Ref349434886 h شکل2-4 نشان داده شده است.

شکل2- SEQ شکل2- * ARABIC 4: روند دوم مرحله تخمین تخممرغ [6].در مرحله ارسال پیام به صورت توزیع‌شده، توسط حسگرهای موجود در حوزه نگهداشت و ارسال جاری به صورت سیل‌آسا پیام فعال‌سازی به حسگرهای موجود در حوزه ارسال زمان بعدی ارسال می‌گردد تا حسگرهای این حوزه فعال گردند. یک بسته کنترلی برای کنترل کردن تعداد بسته‌های پخش‌شده در شبکه ارائه‌شده است. این بسته شامل فیلدهای زمان ارسال بسته، تاریخچه‌ای از مسیر طی شده توسط بسته و نسبت برای کنترل تعداد بسته‌های ارسالی از این نوع می‌باشد. در الگوریتم VE-mobicast حسگرهای شبکه به سه ناحیه تقسیم می‌گردند که این نواحی عبارتند از:
حسگرهای موجود در داخل مسیر حرکتی حوزه تحویل در زمان جاری تا زمان بعدی.
حسگرهای موجود در اجتماع حوزه‌های ارسال در زمان فعلی و زمان بعدی منهای ناحیه اول.
حسگرهایی موجود در شبکه به جز حسگرهای موجود در اجتماع حوزه ارسال زمان فعلی و زمان فعلی.
REF _Ref349435267 h شکل2-5 تقسیم‌بندی نواحی سه‌گانه شبکه را نشان می‌دهد.

شکل2- SEQ شکل2- * ARABIC 5: نواحی مختلف تقسیم‌کننده شبکه، a: ناحیه یک، b: ناحیه دو، c: ناحیه سه [6].مرحله ارسال پیام به صورت توزیع‌شده از دو مرحله تشکیل شده است. در مرحله اول حسگرهای حوزه نگهداشت و ارسال زمان جاری به تمام حسگرهای همسایه‌های خود که در حوزه ارسال در ناحیه آینده قرار دارند به صورت سیل‌آسا پیام کنترلی ارسال می‌گردد. در مرحله دوم حسگرهای دریافت‌کننده پیام کنترلی، در صورتی که چندین پیام را دریافت کرده باشند پیام‌ها را با یکدیگر ترکیب کرده و پیام جدید را به حسگرهای همسایه خود ارسال می‌کند و این روند ادامه پیدا می‌کند تا نسبت بزرگتر از یک گردد. به منظور ترکیب پیام‌ها توسط حسگرهای دریافت‌کننده پیام کنترلی با توجه به رابطه 2-5 نسبت جدیدی برابر با را برای نسبت محاسبه می‌گردد.
(2-5) hmergH=min1≤i≤mhimax1≤i≤mhiاگر حسگر دریافتکننده پیام در ناحیه 1 باشد: hmergH=min1≤i≤mhimin1≤i≤mhiاگر حسگر دریافتکننده پیام در ناحیه 2 باشد : hmergH=max1≤i≤mhimin1≤i≤mhiاگر حسگر دریافتکننده پیام در ناحیه 3 باشد : رابطه فوق نشان می‌دهد، اگر حسگر دریافت‌کننده پیام در ناحیه اول باشد بسته در ابتدای مسیر طولانی‌ترین مسیر خود است. در صورتی که حسگر دریافت‌کننده پیام کنترلی در ناحیه دوم است بسته در ابتدای کوتاه‌ترین مسیر خود قرار دارد و اگر حسگر دریافت‌کننده پیام کنترلی در ناحیه سوم قرار داشت، بسته در انتهای مسیر خود است. بنابراین هر چه بسته از حوزه‌های ارسال زمان‌های فعلی و بعدی دور می‌شوند کمتر ارسال مجدد می‌شوند.
2-2-3-پروتکل HVE-mobicastپروتکل HVE-mobicast [7]، نسخه تغییریافته VE-mobicast است که در این پروتکل ارسال پیام به وسیله خوشه‌بندی صورت می‌پذیرد. حوزه ارسال در این الگوریتم در دو مرحله خوشه به خوشه و خوشه به حسگر حرکت میکند. در مرحله خوشه به خوشه، سرخوشه جاری به سرخوشه جدید پیام بیدارباش ارسال می‌کند تا سرخوشه جدید به حالت فعال برود و در مرحله خوشه به حسگر، سرخوشه جدید به اعضای خوشه خود پیام بیدارباش ارسال می‌کند تا حسگرهای عضو خود به حالت فعال بروند. با توجه به اینکه پیام‌رسانی در پروتکل VE-mobicast به صورت حسگر به حسگر می‌باشد بنابراین پروتکلVE-mobicast به صورت بهینه انرژی را مصرف نمیکند. بنابراین، رویکردهایی مبتنی بر خوشه تعداد حسگرهای محدودتری را فعال کرده که باعث کاهش مصرف انرژی می‌شود. در این مقاله مناطق ارسال و تحویل همانند پروتکل VE-mobicast تعریف‌شده‌اند با این تفاوت که مناطق به خوشه‌هایی نیز تقسیم گردیدهاند. حسگرها به دو گروه تقسیم می‌شوند، گروه اول شامل تمام سرخوشهها و گروه دوم شامل تمام حسگرهای عضو این خوشه‌ها می‌شوند. در ابتدا حسگرهای گروه اول فعال میگردند و پس از یک دوره زمانی حسگرهای عضو این خوشه‌ها فعال میگردند. این امر باعث می‌شود نسبت به پروتکل VE-mobicast انرژی کمتری مصرف شود.
عیب الگوریتمهای مبتنی بر پیام این است که فرض می‌گردد هدف با سرعت ثابتی در حرکت است. در صورتی که سرعت هدف افزایش پیدا کند حوزه تحویل زودتر از آن چیزی که مورد انتظار است به حوزه ارسال میرسد، در نتیجه تمام حسگرهای حوزه ارسال فرصت پیدا نمیکنند که فعال گردند و بنابراین اطلاعات اشتباه تولید میگردد. این طرح نیز همانند پروتکل VE-mobicast دارای دو مرحله می‌باشد. مرحله اول را تخمین تخم‌مرغ و مرحله دوم را ارسال پیام به صورت توزیعشده مینامند. تفاوت پروتکل HVE-mobicast با پروتکل VE-mobicast در مرحله ارسال پیام به صورت توزیعشده می‌باشد. در مرحله ارسال پیام به صورت توزیعشده تمام حسگرهای موجود در حوزه نگهداشت و ارسال زمان جاری به سرخوشه حوزه ارسال زمان بعدی پیام بیدارباش ارسال می‌کنند. سرخوشه حوزه ارسال زمان آینده بعد از دریافت پیام بیدارباش به حسگرهای سرخوشه عضو حوزه ارسال در زمان بعدی پیام بیدارباش فعالسازی میفرستد تا تمام حسگرهای این حوزه در گروه یک را فعال سازد. حسگرهای سرخوشه نیز پس از زمانی مشخص برای حسگرهای عضو خود پیام بیدارباش را ارسال میکنند. در پروتکل HVE-mobicast یک بسته کنترلی برای کنترل کردن تعداد بسته‌های پخش‌شده در شبکه ارائه گردیده است. این بسته شامل فیلدهای زمان ارسال بسته، تاریخچه‌ای از مسیر طی شده توسط آن بر حسب خوشه‌ها و یک شمارنده برای کنترل تعداد بسته‌های ارسالی از این نوع میباشد. در این الگوریتم همانند الگوریتم VE-mobicast حسگرهای شبکه به سه ناحیه تقسیم می‌گردند که در هر کدام از این نواحی نحوه ارسال متفاوت است. مرحله ارسال پیام به صورت توزیعشده از پنج مرحله تشکیل شده است. در مرحله اول حسگرها در حوزه نگهداشت و ارسال زمان فعلی به سرخوشه های تمام خوشه‌های مجاور پیامی را ارسال میکنند. در مرحله دوم هر سرخوشه زمانی را قبل از رسیدن حوزه تحویل و بعد از دریافت تمام بسته‌های چند پخشی قبل از اینکه حسگرهای درون خوشه‌اش فعال گردد صبر می‌کند. در مرحله سوم در صورتی که حسگر همسایه بسته‌ای را دریافت کرد که حسگر همسایه دریافت‌کننده پیام و حسگر ارسال‌کننده پیام کنترلی در ناحیه سه باشند آن بسته به سرخوشه بعدی ارسال نمیگردد. در مرحله چهارم با توجه به اینکه سرخوشه در کدام ناحیه باشد و چندین بسته در یافت کرده باشد، با استفاده از رابطه2-5، بسته باهم ادغام میگردند. در مرحله نهایی وقتی زمان انتظار سرخوشه به اتمام رسید، هر سرخوشه حسگرهای عضو خوشه خود را فعال می‌کند.
2-3-رویکرد مبتنی بر درختدر رویکرد مبتنی بر درخت، حسگرها به صورت مجازی یک درخت تشکیل می‌دهند و اطلاعات را از هدف جمعآوری کرده و به ریشه درخت مجازی می‌رسانند. ریشه از این اطلاعات برای هرس کردن درخت یعنی کم کردن حسگرهایی که از هدف دورند و اضافه کردن حسگرهای جدیدی که هدف به آنها نزدیک شده است استفاده می‌کند. مزیت این روش این است که با توجه به خاصیت بدون دور بودن درخت، داده اضافی به یک حسگر خاص نخواهد رسید.
2-3-1-الگوریتم DCTCدر الگوریتم DCTC [8]، الگوریتمی برای پردازش داده رهگیری به صورت محلی و ارسال نتایج به حسگر مقصد ارائه گردیده است. در این روش گروهی از حسگرها یک هدف را تشخیص داده و آن را رهگیری می‌کنند و برای کسب اطلاعات از محیط اطراف آنها با هم تبادل اطلاعات کرده و یکی از آنها(ریشه) اطلاعات مفید را به حسگر چاهک ارسال میکند. این روش بر مبنای یک درخت مجازی بنام درخت همراه استوار است که در REF _Ref349467140 h شکل2-6، نمایی کلی از این طرح نشان داده شده است.

شکل2- SEQ شکل2- * ARABIC 6: مراحل الگوریتمDCTC ، a: مرحله جمع‌آوری داده، b: مرحله باز پیکربندی[8].به منظور تشکیل درخت همراه، هنگامی‌که یک هدف داخل شبکه میشود حسگرهایی که آن را تشخیص دادند باید یک ریشه انتخاب کنند. بدین منظور حسگری که از همه به هدف نزدیک‌تر باشد به عنوان ریشه برگزیده می‌شود و حسگرهای دیگر حسگرهایی که در فاصله کمتری نسبت به هدف هستند را به عنوان حسگر پدر خود در درخت همراه انتخاب می‌کنند. همگام با حرکت هدف برخی از حسگرها از آن دور می‌شوند و باید از این درخت هرس شوند و بجای آنها حسگرهای جدیدی به هدف نزدیک شده که باید به درخت همراه اضافه شوند. در این پروتکل به منظور اضافه کردن و هرس کردن درخت همراه از دو روش محافظه‌کارانه و بر اساس پیش‌بینی استفاده می‌گردد. در روش محافظه‌کارانه تمام حسگرهایی که فاصله آنها تا هدف از مقدار خاصی بیشتر نیست به درخت اضافه می‌شوند. این مقدار تابعی از سرعت هدف و شعاع ناحیه نظارت هدف و یک عدد ثابت میباشد. یکی از ویژگی‌های مهم درخت همراه میزان پوشش آن است که از تقسیم اندازه اشتراک مجموعه حسگرهایی که در تشخیص یک هدف دخالت دارند(مجموعه حسگرهای درخت همراه) و مجموعه حسگرهایی که میتوانند هدف را شناسایی کنند بر اندازه مجموعه حسگرهای درخت همراه بدست میآید و عدد ثابت با پوشش درخت نسبت مستقیم دارد. همان طور که در REF _Ref349467208 h شکل2-7 مشاهده می‌گردد، به دلیل گسترش درخت در تمام جهات بدون توجه به جهت حرکت هدف، الگوریتم محافظه‌کارانه باعث به وجود آمدن افزونگی در ارسال پیام گردیده است. در این پروتکل نیز روشی بر اساس پیش‌بینی به منظور کاهش افزونگی ناشی از روش اول ارائه گردیده است. در روش بر اساس پیش‌بینی، مکان‌های آینده هدف پیش‌بینی‌شده و تنها حسگرهایی که در نواحی تحت نظارت مربوط به مکان‌های پیش‌بینی‌شده قرار دارند به درخت اضافه میشوند. شعاع دایره حسگرهایی که به درخت اضافه می‌شوند، شعاع ناحیه تحت نظارت هدف است[8].
بعد از اضافه کردن و هرس کردن درخت، باز پیکربندی درخت در صورتی که فاصله ریشه تا هدف از یک مقدار ثابت بیشتر شود، رخ خواهد یافت. برای اینکه حسگرهایی موجود در ناحیه تحت نظارت به ریشه این درخت بپیوندند از الگوریتمی استفاده می‌شود که در آن ریشه، پیام باز پیکربندی را به تمام همسایگانش ارسال کند و این همسایگان این پیام بعلاوه مکان خود و هزینه ارسال پیام از طریق خود به ریشه، را به تمام همسایگان خود ارسال می‌کند. سپس حسگرهای دریافت‌کننده برای مدتی صبر کرده تا تمام پیام‌ها را دریافت کنند، سپس همسایه‌ای را که هزینه‌اش از همه کمتر است را به عنوان پدر خود انتخاب می‌کنند. این روند تا آنجا ادامه پیدا می‌کند که تمام حسگرهای موجود در ناحیه تحت نظارت هدف به درخت بپیوندند.

شکل2- SEQ شکل2- * ARABIC 7: الگوریتم‌های هرس کردن درخت، a: الگوریتم محافظه‌کارانه، b: الگوریتم بر اساس پیش‌بینی[9].به منظور باز پیکربندی درخت همراه روش جدیدی ارائه گردیده است که امکان تغییر ریشه درخت همراه در آن وجود دارد [9]. در این روش جدید یک درخت همراه در دو مرحله باز پیکربندی میگردد، در مرحله اول ریشه جدید انتخاب میشود و در مرحله دوم باقیمانده درخت برای کاهش سربار انرژی باز پیکربندی می‌شود. در مرحله اول بعد از تشخیص اجرای الگوریتم باز پیکربندی توسط ریشه، پیامی به حسگر سرخوشه که هدف در آن قرار دارد توسط ریشه ارسال میشود و سرخوشه نیز حسگری را که به هدف نزدیک‌تر است را به عنوان ریشه انتخاب کرده و پیام تغییر ریشه، را به همسایگان خود ارسال می‌کند. در این پروتکل مرحله باز پیکربندی به دو صورت باز پیکربندی کامل و باز پیکربندی بر اساس قطع انجام می‌گیرد. در روش باز پیکربندی کامل الگوریتم باز پیکربندی با ارسال یک پیام باز پیکربندی توسط ریشه به حسگرهای مجاور انجام می‌گردد. سپس هر حسگری که پیام را دریافت می‌کند برای مدتی صبر کرده تا تمام پیام‌ها را دریافت کنند، سپس همسایه‌ای را که هزینه‌اش از همه کمتر است را به عنوان پدر خود انتخاب می‌کنند. REF _Ref349467277 h شکل2-8 این عملیات را نشان می‌دهد.

شکل2- SEQ شکل2- * ARABIC 8: الگوریتم باز پیکربندی کامل، الف:درخت همراه قبل از باز پیکربندی کامل، ب: درخت همراه بعد از باز پیکربندی کامل[9]در مرحله باز پیکربندی کامل [9]، چون تمام حسگرها در باز پیکربندی دخالت دارند باز پیکربندی کامل سربار زیادی را به شبکه تحمیل می‌کند. بنابراین، یک طرح باز پیکربندی بر اساس قطع ارائه‌شده است. که در آن تنها قسمت کوچکی از درخت باز پیکربندی می‌شود. همان طور که در REF _Ref349467347 h شکل2-9 مشاهده می‌گردد در ابتدا ریشه آینده، پیامی مبنی بر باز پیکربندی به همسایگانش ارسال می‌کند و حسگرهایی که در ناحیه نظارت مکان هدف هستند و در بازه بین خطوط l1 و l0 قرار دارند، خود را از ریشه قدیم جدا کرده و به ریشه جدید الحاق می‌کنند.

شکل2- SEQ شکل2- * ARABIC 9: الگوریتم باز پیکربندی بر اساس قطع، الف: درخت همراه قبل از باز پیکربندی بر اساس قطع، ب: درخت همراه بعد از باز پیکربندی بر اساس قطع[9].2-3-2-الگوریتم STUNدر الگوریتم STUN [10]، روشی به منظور رهگیری قابل‌تغییر اندازه در شبکه‌های حسگر ارائه گردیده است که الگوریتم خود را با تعداد حسگرها و اهداف وفق میدهد. در این الگوریتم به منظور تشکیل درخت همراه از یک الگوریتم سلسله مراتبی استفاده میگردد که توسط آن حسگرها به یکدیگر وصل میگردند. درخت همراه یک درخت دودویی است که ریشه آن نقطه پرسوجو را تشکیل میدهد و برگ‌های این درخت گره‌های حسگر و دیگر رئوس این درخت حسگرهای میانی را تشکیل میدهند. به منظور رهگیری هدف، اطلاعات در مورد حضور یک هدف که توسط گروهی از برگ‌های درخت جمعآوری میگردد، در حسگرهای میانی مربوط به همان برگها نیز نگهداری می‌شوند. هنگامی‌که دادهای در حسگرهای میانی تغییر یافت، پیام‌های به روز کردن مجموعه‌ای از اهداف که توسط یک برگ تشخیص داده شده است بنام پیام مجموعه تشخیص، از برگ‌ها به سمت ریشه ارسال می‌گردد وگرنه در همان حسگر میانی حذف می‌شوند که این کار موجب کاهش تبادل اطلاعات در شبکه می‌شود.
در این الگوریتم به منظور ساختن درختهای سلسله مراتبی هرس پیام، از رویه تخلیه و تعادل(DAB) استفاده گردیده است. بدین منظور ابتدا گراف وزن داری به نام گراف حسگر تشکیل میگردد که در این گراف یک حسگر با حسگر دیگری مجاور است در صورتی که هدف بتواند از برد حسی یک حسگر به برد حسی یک حسگر وارد گردد بدون اینکه به برد حسی حسگر سومی وارد شود و هر یال وزنی برابر با ریت تشخیص توسط حسگرهایش به آن تخصیص داده میشود. در مرحله تشکیل درخت سلسله مراتبی، ابتدا آستانههای تخلیه به صورت نزولی مرتب میگردد و در هر مرحله برای هر یک از آستانههای تخلیه یک‌بار فرایند تخلیه و یک‌بار فرایند تعادل انجام میشود. در فرایند تخلیه، حسگرهایی از گراف حسگرها که حداقل به یک یال متصلند و وزن آن یال بزرگتر یا مساوی آستانه تخلیه میباشد به درخت اضافه می‌گردند. در فرایند تعادل زیر درخت‌های مجاور از طریق یک حسگر میانی ادغام می‌شوند به طوری که درخت ادغام‌شده از تمام حالات ادغام ممکن دیگر دارای حسگر کمتری میباشد. در REF _Ref349467414 h شکل2-10 یک گراف حسگر و نحوه تشکیل درخت سلسله مراتبی نشان داده شده است.

شکل2- SEQ شکل2- * ARABIC 10: مثالی از شکل گرفتن درخت DAB، a: گراف وزن دار حسگر، b: درخت DAB بعد از اولین مرحله2-3-3-الگوریتم DATدر الگوریتم DAT [11]، ابتدا شبکه به صورت یک گراف veroni در نظر گرفته می‌شود و به وسیله این گراف یک درخت وزن دار تشکیل می‌گردد که ریشه این درخت حسگر چاهک می‌باشد. گراف veroni، یک گراف وزن دار است که فضا را به چندین ناحیه تقسیم می‌کند و در این گراف دو حسگر دارای یال مشترک می‌باشند اگر و تنها اگر این دو حسگر در شبکه همسایه باشند. به منظور شناسایی هدف توسط یک حسگر با توجه به موقعیت هدف، حسگر چاهک یک پیام جستجو برای حسگری که به هدف نزدیک‌تر می‌باشد، از طریق درخت همراه ارسال می‌گردد و این روند در REF _Ref349467466 h شکل2- 11 قسمت (الف) نشان داده شده است. در صورتی که هدف o1 از ناحیه حسگرa خارج گردید و به ناحیه تحت نظارت حسگرb وارد گردید یک پیام dep(o1,a,b) توسط حسگرa به حسگر چاهک ارسال می‌گردد. در این الگوریتم به منظور شناسایی اهدافی که تحت نظارت آن حسگر هستند، هر کدام از حسگرهای شبکه دارای لیست شناسایی Dlx=(l0,l1,…,lk) هستند که در این لیست l0 اشاره به مجموعه‌ای از اهداف دارد که در ناحیه حسگرx قرار دارند و نیز l1,..,lk اشاره به مجموعه‌ای از اهداف دارند که در ناحیه حسگرهای فرزند حسگرx قرار دارند. در صورتی که پیام dep(o1,a,b) توسط حسگرx دریافت گردید، اگر هدف o1 متعلق به مجموعه L0 باشد آن هدف از لیست L0 حذف می‌گردد و ارسال پیام از حسگرx به حسگر چاهک تا زمانی ادامه می‌یابد که هدف در لیست شناسایی آن حسگر نباشد. هنگامی‌که هدف در برد حسگرb قرار گرفت، حسگرb پیام arv(o1,b,a) را از طریق درخت همراه به حسگر چاهک ارسال می‌کند. هر حسگری که در مسیر حسگرb به حسگر چاهک این پیام را دریافت کند، در صورتی که هدف o1 در لیست شناسایی آن حسگر نباشد، آن هدف را به لیست شناسایی حسگر اضافه می‌کند و پیام arv(o1,b,a) توسط حسگر به سمت گره چاهک ارسال می‌گردد. همان طور که در REF _Ref349467466 h شکل2- 11 قسمت (ب) نشان داده شده است با حرکت هدف1 از حسگرk به j پیام‌های dep(o1,a,b) و arv(o1,b,a) به حسگر چاهک ارسال گردیده است.

شکل2- SEQ شکل2- * ARABIC 11: الف: ارسال پیام جستجو توسط حسگر چاهک به منظور شناسایی هدف اول، ب: خارج شدن هدف اول از برد حسگرK و وارد شدن آن به برد حسگرG[11].2-4-رویکرد مبتنی بر پیش‌بینی2-4-1-الگوریتم TTMBدر الگوریتم TTMB[12]، روشی با استفاده از حسگرهای ناظر و پشتیبان ارائه گردیده است. در این الگوریتم از روشهای رهگیری بر مبنای پیش‌بینی ساده برای این کار استفاده گردیده است. در روشهای رهگیری مبتنی بر پیشبینی ساده یک حسگر اطلاعات را از دیگر حسگرها دریافت میکند و با اطلاعات خود مقایسه می‌کند. در این شبکه موجودیتی بنام رهگیر که قصد رهگیری هدفی را دارد تعریف می‌شود و حسگر پشتیبان نیز در حالاتی که ناظر دچار مشکل می‌شود جایگزین حسگر ناظر میگردد. فرض می‌شود که هر ناظر حسگرهای همسایهاش را می‌شناسد. وقتی یک حسگر توسط رهگیر مورد پرسش قرار می‌گیرد بررسی می‌کند که آیا هدف مورد نظر در نزدیکی‌اش است و یا خیر. در صورت وجود هدف مورد نظر در نزدیکی آن حسگر، حسگر به عنوان ناظر انتخاب می‌شود. اگر هدف در همسایگی ناظر باشد، ناظر به رهگیری خود ادامه می‌دهد. در همین هنگام ناظر یک ناظر و پشتیبان جدید را بر اساس مسیر حرکت هدف انتخاب می‌کند که این دو حسگر به ترتیب متعلق به حسگرهای مجموعه همسایگی جاری و یکی از حسگرهای مجموعه همسایگیهای مجاور میباشد. وقتی هدف از همسایگی ناظر خارج شد ناظر به رهگیر، ناظر جدید را معرفی میکند. زوج حسگرهای ناظر و پشتیبان یک زوج منطقی را تشکیل می‌دهند که یک لیست پیوندی از آنها که در هر مرحله به صورت تدریجی ساخته می‌شود مسیر طی شده توسط هدف را تعیین می‌کند. در این الگوریتم هدف می‌تواند سرعت متغییری داشته باشد و همچنین، از تبادلات میان حسگری بهره می‌برد. اگر حسگری ناظر باشد و هدف در یکی از وجوهی باشد که حسگر ناظر یکی از رئوس آن‌ وجوه میباشد، وجوهی که هدف در آن‌ها نیست وجوه همسایه تلقی می‌شوند. وجه به چندضلعی‌هایی گفته می‌شود که حسگرها رئوس آنها بشمار می‌آیند. حسگر ناظر اطلاعات مربوط به این وجوه را نگهداری می‌کند. همسایگان فوری یک ناظر، حسگرهایی میباشند که فاصله آنها تا حسگر ناظر یک پیوند ارتباطی می‌باشد. بنابراین همسایگان فوری رئوس وجهی هستند که هدف در آن قرار دارد و بقیه رئوس این وجه همسایگان دور ناظر نامیده می‌شوند. این الگوریتم برای صرفه‌جویی در مصرف توان از یک ماشین حالت استفاده می‌کند که دارای سه حالت فعال، بیدار و غیرفعال است که REF _Ref349470343 h شکل2-12، ماشین حالت الگوریتم TTMB را نشان می‌دهد. در حالت فعال حسگرها می‌توانند اطلاعات را ارسال و دریافت کنند و همچنین توانایی تشخیص هدف را دارند ولی در حالت بیدارباش حسگر فقط توانایی تشخیص هدف را دارد و در حالت خواب حسگر هیچ‌گونه عملی انجام نمی‌دهد. در REF _Ref349470343 h شکل2-12 حالت S0 اشاره به این دارد که حسگر در حالت فعال قرار دارد، حالت S1 اشاره به این دارد که حسگر در حالت بیدارباش قرار دارد و حالت S2 اشاره به این دارد که حسگر در حالت خواب قرار دارد. در این الگوریتم با استفاده از مکان کنونی هدف و مکان آن در یک واحد زمانی قبل سرعت و جهت حرکت هدف را به دست میآورد و با استفاده از یک توزیع دو بعدی گوسی موقعیت آینده هدف پیش‌بینی می‌گردد و حسگری که به هدف پیش‌بینی‌شده نزدیک‌تر است به عنوان ناظر جدید انتخاب می‌گردد. بنابراین در پروتکل TTMB ابتدا رهگیر یک پیام را با روش سیل‌آسا به تمام حسگرها می‌فرستد تا از محل هدف مطلع شود. حسگری که به هدف از همه نزدیک‌تر است به عنوان ناظر انتخاب می‌شود. در هنگام گم شدن هدف، به منظور شناسایی اهداف گم شده اگر ناظر نتواند هدف را شناسایی کند کارها بدست ناظر پشتیبان سپرده میشود. در صورتی که پشتیبان نیز موفق به شناسایی هدف نگردید، به ناظر قبلی پیامی ارسال میگردد و ناظر قبلی از تمام همسایگان دورن وجهی‌اش می‌خواهد تا به دنبال هدف بگردند و اگر آن‌ها نیز موفق به شناسایی هدف نگردیدند از حسگرهای وجوه همسایه ناظر قبلی به منظور شناسایی هدف کمک گرفته میشود و در صورتی که آن‌ها هم هدف را شناسایی نکردند پیامی به رهگیر ارسال میگردد تا پرسش را دوباره تکرار کند.

شکل2- SEQ شکل2- * ARABIC 12: ماشین حالت الگوریتم TTMB [12].2-4-2-الگوریتم کاهش خطا مکانی به صورت انرژی آگاهدر الگوریتم کاهش خطای مکانی به صورت انرژی آگاه[13]، یک چارچوب کاهش خطای مکانی برای رهگیری اهداف ارائه گردیده است که در این چارچوب کاهش خطای مکانی از دو رویکرد اجتناب از خطا و تصحیح خطا استفاده گردیده است. رویکرد اجتناب از خطا شامل یک روش جلوگیری از خطا به وسیله بیدار کردن گروهی از حسگرها پیش از رسیدن هدف به موقعیت پیش‌بینی‌شده هدف است که اگر تغییر جهتی بر خلاف پیش‌بینی به وجود آمد هدف قابل‌شناسایی باشد. بنابراین رویکرد تصحیح خطا به دلیل پیچیدگی زمانی و محاسباتی آن در بدترین حالت استفاده می‌شود. وقتی رویکرد اجتناب از خطا جواب نداد ناحیه بیدارباش حسگرها به اندازه مناسب بزرگ می‌شود. با توجه به اینکه برای رهگیری هدف، پیش‌بینی صحیح مکان بعدی هدف و حوزه مناسب برای بیدار کردن حسگرها مهم میباشد و در صورت انتخاب مناسب حوزه بیدارباش، تغییر اندک در جهت حرکت هدف، باعث گم شدن هدف نمی‌شود بنابراین اندازه حوزه بیدارباش بسیار مهم میباشد و بر اساس عوامل گوناگونی مانند سرعت هدف، زمان سپری‌شده، نرخ خطای قابل‌تحمل و غیره بدست آورده میگردد. REF _Ref349472766 h شکل2-13 حوزه‌های بیدارباش کنونی و آینده را نشان میدهد.

شکل2- SEQ شکل2- * ARABIC 13: حوزه‌های بیدارباش کنونی و آینده[13].در REF _Ref349472766 h شکل2-13 منطقه سایه‌دار محل وجود هدف است و دایره با خط ممتد حوزه بیدارباش هدف در زمان کنونی است. اما دایره خط چین حوزه بیدارباش برای زمان آینده هدف را نشان میدهد. θ زاویه‌ای است که با آن مقدار دقت در رهگیری و اندازه خطای قابل‌تحمل طرح تنظیم می‌شود. هر چه مقدار آن بزرگتر باشد احتمال گم شدن هدف کمتر می‌شود اما انرژی بیشتر در شبکه مصرف می‌شود. در الگوریتم کاهش خطای مکانی به صورت انرژی آگاه، در رویکرد اجتناب از خطا باید هدف به اندازه کافی در حوزه بیدارباش کنونی باقی بماند تا بتوان پیام بیدارباش به حسگرهای حوزه بیدارباش بعدی ارسال گردد. حسگرها در این روش به چهار گروه تقسیم می‌شوند: حسگرهای خوابیده، حسگرهای فعال بدون خطا، حسگرهای فعال با خطا و حسگرهای در حوزه آینده. این گروه‌بندی در REF _Ref349472878 h شکل2-14 نشان داده شده است.

شکل2- SEQ شکل2- * ARABIC 14: انواع حسگرها در رویکرد اجتناب از خطا [13].همان طور که در REF _Ref349472878 h شکل2-14 نشان داده شده است حسگرهای فعال بدن خطا می‌توانند هدف را تشخیص دهند ولی حسگرهای فعال با خطا نمی‌توانند هدف را تشخیص دهند. حسگرهای فعال آینده، مربوط به حسگرهای فعالی هستند که در حوزه آینده قرار دارند و مسئولیت ردیابی هدف در زمان آینده را بر عهده خواهند داشت. اگر هدف در ناحیه قطاع سایه‌دار باشد در نتیجه در زمان بعدی در حوزه بیدارباش پیش‌بینی‌شده خواهد بود اما اگر نباشد الگوریتم تصحیح خطا اجرا می‌گردد. اگر زمان کافی برای محاسبه مجدد وجود داشته باشد فرایند پیش‌بینی دوباره تکرار شده و مکان جدید بدست آمده و حسگرهای آن حوزه به حالت بیدارباش می‌روند. ولی اگر زمان کافی برای این کار نباشد یعنی خطا در مکان‌های نزدیک مرز حوزه بیدارباش فعلی تشخیص داده شد خود حسگر مرزی حوزه بیدارباش خود را تشکیل می‌دهد تا زمانی کافی برای بیدار کردن حوزه پیش‌بینی‌شده قبل از رسیدن هدف به آن را مهیا کند. پس از این کار فرایند تکنیک اجتناب از خطای معمول ادامه می‌یابد. در مکانیزم تصحیح خطا اگر هدف در مدت زمان معینی به حوزه بیدارباش پیش‌بینی‌شده نرسید سرخوشه فعلی باید یک حوزه بیدارباش جدید و بزرگتر تعریف کرده تا بتوان هدف را ردیابی کرد. این امر از طریق تنظیم یک زمان‌سنج در سرخوشه در حوزه بیدارباش پیش‌بینی‌شده میسر است. اگر این زمان‌سنج به انتها رسید و هدف پیدایش نشد به سرخوشه قبلی خبر می‌دهد تا حوزه جدیدتر و بزرگتر را تشکیل دهد. در این الگوریتم با استفاده از آخرین سرعت بدست آمده و سرعت حداکثری و شتاب هدف، یک شعاع بهینه که از شعاع حداکثری کمتر است بدست آورده میشود و بدین ترتیب انرژی کمتری در شبکه مصرف میگردد.
2-4-3-الگوریتم FTPSدر الگوریتم FTPS [14]، یک رویکرد رهگیری هدف مقاوم در برابر بروز خطا در شبکه حسگر بی‌سیم ارائه گردیده است تا بتواند از گم شدن هدف جلوگیری گردد. این رویکرد با استفاده از تکنیک پیش‌بینی رشدی چند سطحی، قابلیت اطمینان پیشبینی را افزایش و تعداد حسگرهای فعال‌شده را کاهش میدهد و بدین طریق انرژی را به صورت بهینه مصرف می‌کند.
در الگوریتم FTPS فرض گردیده است که شبکه به خوشه‌هایی تقسیمبندی گردیده است. در این الگوریتم فرض گردیده است که تمام حسگرها مکان خود را میدانند و هر خوشه نیز دارای یک سرخوشه میباشد که از اعضای خوشه خود باخبر میباشد. در سازوکار رهگیری هدف به منظور صرفه‌جویی در مصرف انرژی، تمام حسگرها بجز یک حسگر که هدف را دنبال می‌کند خواب هستند. رهگیری هدف هنگامی‌که سرخوشه پیامی مبنی بر اینکه هدف احتمالا در خوشه تحت نظارت آن است دریافت کرد شروع می‌گردد، سپس سرخوشه تمام حسگرهای خوشه خود را به منظور تشخیص هدف به حالت فعال می‌برد. بنابراین سرخوشه تمام پردازش‌های رهگیری هدف را انجام میدهد و اعضای آن فقط داده‌های حس شده از هدف را به آن ارسال می‌کنند. به منظور انجام مکانیزم های رهگیری هدف و بازیابی از دو زمان‌سنج به نام‌های زمان‌سنج رهگیری و زمان‌سنج بازیابی به ترتیب به منظور تشخیص پایان زمان رهگیری و زمان بازیابی توسط سرخوشه استفاده می‌گردد. در صورتی که سرخوشه پیام تشخیص هدفی را از اعضایش دریافت نکند بررسی می‌کند که آیا امکان پیشبینی با سطوح بالاتر و دقیقتر وجود دارد و یا خیر. اگر امکان پیش‌بینی با سطوح بالاتر وجود داشت فرایند رهگیری ادامه می‌یابد و سرخوشه جاری سرخوشه بعدی را بیدار می‌کند. در غیر این صورت هدف گم شده تلقی می‌شود و سرخوشه فرایند بازیابی هدف را آغاز میکند. در فرایند بازیابی ابتدا برد حوزه بازیابی بر اساس آخرین سرعتهای ثبت‌شده هدف محاسبه میگردد. سپس پیام بیداری توسط سرخوشه جاری به تمام سرخوشه های درون حوزه بازیابی فرستاده می‌شود و زمان‌سنج بازیابی راهاندازی می‌گردد. در این هنگام هر سرخوشه که این پیام را دریافت می‌کند به اعضایش می‌گوید که به دنبال هدف بگردند و زمان‌سنج رهگیری خود را راه‌اندازی می‌کند. وقتی زمان‌سنج به پایان رسید، اگر هدف در خوشه پیدا شد یک پیام تایید به سرخوشه جاری ارسال می‌کند تا از محاسبه مجدد برد حوزه بازیابی و فرستادن پیام بیدارباش جلوگیری کند و سرخوشهای که هدف در برد خوشه تحت نظارت آن قرار دارد به عنوان سرخوشه جاری انتخاب می‌شود و رهگیری از این سرخوشه ادامه می‌یابد. اگر قبل از پایان زمان‌سنج بازیابی سرخوشه جاری هیچ پیام تاییدی مبنی بر پیدا شدن هدف دریافت نکرد، سرخوشه جاری برد حوزه بازیابی خود را افزایش داده و پیام بیدارباش را برای سرخوشه های درون برد حوزه بازیابی ارسال می‌کند. اگر چند خوشه بتوانند هدف را تشخیص دهند سرخوشه فعلی برای جلوگیری از ثبت چند مسیر برای هدف هنگام دریافت اولین پیام تایید، پیامی به دیگر خوشه‌ها ارسال می‌کند تا از ادامه جستجوی هدف منصرف شوند. در سازوکار پیش‌بینی ارائه شده در این الگوریتم تعداد سطوح پیش‌بینی بر اساس حرکت هدف بعد از فاز یادگیری محاسبه می‌گردد و بدین منظور حسگرها تعداد شکست‌ها در پیدا کردن هدف را ثبت می‌کنند. بعد از ثبت هر خطای پیشبینی، در آخر با یک آستانه خطا مقایسه می‌شود و اگر از آن بیشتر بود یکی به سطوح پیش‌بینی اضافه می‌شود و هر تشخیص صحیح پیش‌بینی نیز ثبت می‌گردد و در انتها با یک آستانه موفقیت مقایسه می‌شود و اگر از آن بیشتر بود از سطوح پیش‌بینی یکی کم می‌گردد. REF _Ref349474674 h شکل2-15 مثالی را نشان می‌دهد که در آن تعداد سطوح پیش‌بینی، برابر سه است.

شکل2- SEQ شکل2- * ARABIC 15: مثالی از پیش‌بینی سه سطحی [14].2-4-4-الگوریتم HPS
در الگوریتمHPS [15]، یک رویکرد پیش‌بینی سلسله مراتبی به منظور رهگیری هدف در شبکه‌های حسگر سلسلهمراتبی ارائه گردیده است. در این الگوریتم فرض گردیده است که شبکه به خوشه‌هایی تقسیمبندی گردیده است و هر کدام از این خوشه‌ها دارای یک سرخوشه میباشند. در این الگوریتم از یک رویه پیشبین استفاده شده است که این رویه با استفاده از تکنیک کمترین مربعات بازگشتی و مکان‌های پیشین بدست آمده هدف، مکان بعدی هدف پیش‌بینی میشود. در این معماری دو لایه، حسگرهای شبکه به دو دسته سرخوشه‌ها و حسگرهای معمولی تقسیم گردیدهاند که سرخوشهها میتوانند با حسگرهای معمولی عضو خود در ارتباط باشند و همچنین سرخوشه‌ها میتوانند با یکدیگر ارتباط داشته باشند. حسگرهای معمولی عضو خوشه، حسگرهایی از نوع حسگرهای دودویی فرض شده‌اند که اگر هدف در برد حسی آن‌ها قرار دارد عدد یک و در غیر این صورت عدد صفر را برای سرخوشه خودشان ارسال میکنند. حسگرهای سرخوشهها دارای توان پردازشی بالاتری نسبت به حسگرهای معمولی هستند و از منبع انرژی بی‌نهایتی برخوردارند ولی حسگرهای معمولی، حسگرهایی هستند که دارای زیرسیستم‌هایی با توان پردازشی و انرژی محدودی میباشند. در این معماری فرض گردیده است که سرخوشه‌ها و حسگرهای معمولی می‌توانند در دو حالت خوابیده و فعال، به فعالیت خود ادامه دهند. حسگرهای سرخوشه هنگامی در حالت فعال قرار می‌گیرند که یک سرخوشه همسایه‌اش به آن اطلاع دهد که هدف از خوشه تحت نظارت آن عبور خواهد کرد و هنگامی‌که یک سرخوشه در حالت فعال قرار گرفت، بر مبنای حرکت هدف برای حسگرهای عضو خود را که در مسیر حرکت هدف قرار دارند، پیام بیدارباش را ارسال میکند. حسگرهای عضو سرخوشه فعال با دریافت پیام بیدارباش از حسگر سرخوشه خود حالت خود را به حالت فعال تغییر می‌دهند. در این الگوریتم به منظور مصرف غیرضروری انرژی، از بین حسگرهای معمولی که سرخوشه پیام فعال شدن را به آن‌ها ارسال میکند، فقط حسگرهایی که دارای احتمال بالاتر از p هستند حالت خود را به حالت فعال تغییر می‌دهند. حسگرهای معمولی طوری پیاده‌سازی شده‌اند که هر حسگر، عضو خوشه‌ای قرار میگیرد که کمتری فاصله را تا حسگر سرخوشه دارد. سرخوشه به منظور ارسال اطلاعات به حسگرهای عضو خود یک برد مخابراتی که برابر با قطر دایره محیطی محدب خوشه تعیین می‌کند. این برد در REF _Ref349483800 h شکل2- 16 نشان داده شده است.

شکل2- SEQ شکل2- * ARABIC 16: تعیین برد مخابراتی خوشه [15]. در این الگوریتم به منظور مکان‌یابی هدف از الگوریتم مکان‌یابی مرکز جرم استفاده‌شده است. در این الگوریتم مکان هدف با استفاده از میانگین حسابی طول و عرض جغرافیایی حسگرهایی که هدف را تشخیص داده‌اند تخمین زده می‌شود و به منظور صرفه‌جویی در مصرف انرژی حسگرهایی که فعال هستند و نتوانستند هدف را تشخیص دهند اطلاعاتی را به سرخوشه ارسال نمیکند. در الگوریتم پیشگویی با استفاده از الگوریتم RLS، حسگرهایی که از زمان جاری روشن هستند و تعدادی دیگر که از زمان قبل روشن بوده‌اند سرخوشه جاری مکان بعدی هدف پیش‌بینی می‌گردد. سرخوشه در این مکان به عنوان سرخوشه پیشرو جدید انتخاب می‌گردد. سپس حسگرهای این مکان تا شعاع مخابراتی تعیین‌شده فعال می‌گردند. از حسگرهای فعال‌شده، حسگرهایی که در حوزه نظارت سرخوشه پیشرو نیستند سرخوشه های آن‌ها به عنوان زیر پیشروها به سرخوشه پیشرو شناخته می‌شوند. هنگامی که هدف توسط سرخوشه پیشرو تشخیص داده شد حسگرهایی که از دو زمان قبل فعال بوده‌اند خاموش می‌گردند و بعد از آن حسگرهایی که در زمان قبل و زمان جاری فعال هستند اطلاعات حسی خود را به سرخوشه های خود می‌فرستند و سرخوشه‌ها اطلاعات خود را به سرخوشه پیشرو ارسال می‌کنند. در نهایت سرخوشه پیشرو مکان بعدی هدف را پیش‌بینی کرده و این روند ادامه پیدا خواهد کرد. در این الگوریتم در صورت از کار افتادن حسگر سرخوشهای به منظور جلوگیری از به وجود آمدن اختلال در رهگیری هدف یک سرخوشه جدید برای آن خوشه در نظر گرفته می‌شود و حسگرها تحت نظارت آن سرخوشه به کار خود ادامه می‌دهند.
2-4-5-الگوریتم PESدر الگوریتم PES [16]، به منظور رسیدن به حالت ایدهآل مصرف انرژی در شبکه، الگوریتمی ارائه گردیده است که توسط آن تعداد دفعات نمونه‌برداری توسط حسگرها و تعداد حسگرهایی که در امر رهگیری شرکت دارند، کاهش یافته است. این الگوریتم از سه قسمت تشکیل شده است که عبارتند از: بخش پیشبینی برای پیشبینی حرکت هدف، مکانیزم بیدار سازی حسگرهای مورد نظر و مکانیزم بازیابی هدف. در الگوریتم PES ابتدا مکان بعدی هدف توسط حسگر جاری که هدف را تشخیص داده است پیش‌بینی می‌گردد و قبل از اینکه به خواب برود موعد بیداری آن‌ها را محاسبه کرده و به حسگرهای مورد نظر پیام بیدارباش ارسال می‌کند. پس از گذشتن زمان خواب، حسگر جاری به همراه حسگرهای مورد نظر بیدار می‌گردند و اگر در تشخیص هدف موفقیتی کسب نگردید مکانیزم بازیابی هدف اجرا می‌گردد.
در این الگوریتم به منظور پیش‌بینی مکان آینده هدف از سه نوع الگوریتم اکتشافی استفاده گردیده است. در الگویتم اول که اکتشاف فوری نام دارد فرض می‌شود که سرعت و جهت حرکت هدف در طول پیش‌بینی ثابت است و بر این اساس مکان آینده هدف پیش‌بینی می‌گردد. این الگوریتم به دلیل اینکه حسگر جاری نیازی به دانستن تاریخچه حرکتی هدف ندارد، بسیار ساده و از نظر مصرف انرژی بسیار مناسب است. در الگوریتم دیگری با نام اکتشاف میانگین با توجه به تاریخچه سرعت و جهت آن در چند نمونه‌برداری اخیر و میانگین‌گیری از آن‌ها مکان آینده هدف پیش‌بینی می‌شود. بنابراین، این الگوریتم به دلیل اینکه نیاز به انتقال اطلاعات مربوط به حرکت هدف به حسگرهای دیگر وجود دارد، دارای سربار مخابراتی بیشتری نسبت به الگوریتم اکتشاف فوری است. ولی در الگوریتم آخر که میانگین نمایی نام‌گذاری شده است، بر اساس وزن‌هایی که به نقاط مختلف نمونه‌برداری داده می‌شود میانگین‌گیری انجام می‌گیرد.
در این الگوریتم به منظور بیدار سازی مجموعه حسگرها نیز از سه رویکرد استفاده گردیده است. در رویکرد اول حسگر جاری تنها حسگر مقصد پیش‌بینی‌شده را فعال میکند. در رویکرد دوم، علاوه بر حسگر مقصد تمام حسگرهای موجود در مسیر بین حسگر جاری و حسگر مقصد فعال می‌گردند تا احتمال گم شدن هدف کاهش یابد. بنابراین این رویکرد قادر است تغییرات مقدار سرعت را نیز پیش‌بینی کند. در رویکرد سوم بیدار سازی حسگرهای همسایه مسیر پیش‌بینی‌شده علاوه بر بیدار سازی حسگرهای موجود در مسیر پیش‌بینی‌شده صورت می‌پذیرد تا این رویکرد تغییرات مقدار و جهت سرعت هدف را بتوانند پوشش دهند و در صورت تغییرات جزئی حرکت هدف، هدف قابل‌شناسایی باشد. REF _Ref349486030 h شکل2-17 رویکردهای بیدارسازی را نشان می‌دهد.

شکل2- SEQ شکل2- * ARABIC 17: توابع اکتشافی برای مکانیزم های بیدار کردن حسگرها [16].در صورت گم شدن هدف حسگر جاری از رویکرد بیدارسازی آخر استفاده می‌گردد تا هدف پیدا شود و در صورت شکست این روش تمام حسگرهای شبکه فعال می‌گردند تا مکان هدف مورد نظر تشخیص داده شود. این امر از طریق یک ارسال پیام سیلآسا به تمام حسگرها صورت می‌پذیرد. به منظور جلوگیری از رفتن به مرحله پرهزینه آخر، هنگامی‌که هدفی در مرحله اول پیدا شد حسگری که آن را پیدا میکند به حسگر شروع‌کننده فرایند بازیابی هدف اطلاع می‌دهد تا حسگر شروع‌کننده فرایند بازیابی مرحله پرهزینه آخر بازیابی هدف را اجرا نکند.
2-4-6-الگوریتم DPRدر الگوریتم DPR [17]، به منظور گزارش موثر مکان هدف به ایستگاه پایه الگوریتمی بر مبنای پیش‌بینی دوگانه ارائه گردیده است، تا مصرف انرژی به حداقل رسانده شود. در این روش ایستگاه پایه و حسگرها مسیر حرکت هدف را پیش‌بینی می‌کنند تا از تبادلات میان آن‌ها کاسته شود. بدین منظور یک مدل پیش‌بینی در حسگرها و ایستگاه پایه پیاده‌سازی میگردد و حسگرها و ایستگاه پایه با استفاده از تاریخچه هدف موقعیت هدف را به صورت دائم پیش‌بینی میکنند. در این حالت تا وقتی که داده‌های جمع‌آوری شده توسط حسگرها با دادههای خروجی پیش‌بینی کننده یکی باشد نیازی نیست که حسگرها داده‌ای به ایستگاه پایه ارسال کنند. اما اگر تطابق نداشته باشند حسگرها باید داده جمعآوری شده را به ایستگاه پایه بفرستند. با توجه به اینکه سربار بسته‌های انتقالی میان حسگرهای حسگر کمتر از انتقال بسته‌ها به ایستگاه پایه است بنابراین این الگوریتم قادر است در مصرف توان صرفه‌جویی کند. یکی از عواملی که بر دقت این پیش‌بینی‌ها اثر میگذارد مدلی است که برای پیش‌بینی مکان اهداف در نظر گرفته می‌شود. دو نوع مدل مکانی وجود دارد که شامل مدل‌های جغرافیایی و نمادین می‌شوند. مدل جغرافیایی همان مختصات دقیق هدف است درحالی‌که مدل نمادین که بر اساس روشهایی مکان هدف تخمین زده میشود دارای دقت و پیچیدگی کمتری میباشند. این مدلها در REF _Ref349487324 h شکل2-18 نشان داده شده است.

شکل2- SEQ شکل2- * ARABIC 18: مدل‌های مکانی [17].مدل‌های نمادین به چهار دسته تقسیم می‌گردند که عبارتند از:
مدل سلول حسگر که ساده‌ترین و بی‌دقت ترین مدل نمادین بشمار میرود و در آن مکان هدف را به وسیله شناسه هر حسگر که هدف در آن قرار دارد مشخص می‌گردد.
مدل مثلث که از اتصال نقاط پایانی مرز میان دو حسگر با مرکز سلول حسگر، شکل می‌گیرد. این مدل باعث کاهش منطقه شناسایی‌شده و سادگی تخمین مثلث مربوطه می‌شود.
مدل شبکه که از خطوط مشبک فرضی در شبکه بدست میآید. هر چه تعداد این مشبکها بیشتر باشد دقت مدل بیشتر می‌گردد و به مدل جغرافیایی نزدیک‌تر می‌گردد.
مدل مختصات که دقیق‌ترین مدل نمادین محسوب می‌گردد و مختصات دقیق هدف را نشان می‌دهد.
2-5-رویکرد مبتنی بر خوشهدر رویکرد مبتنی بر خوشه، شبکه به گروه‌هایی از حسگرها تقسیم می‌شود که هر گروه خوشه نامیده می‌شود. این کار برای صرفه‌جویی در مصرف انرژی انجام می‌شود. هر خوشه دارای یک سرخوشه است که وظیفه رهگیری هدف و انجام محاسبات مربوطه را به عهده دارد. در این قسمت، برخی از پژوهشهای ارائه‌شده مربوط به این رویکرد بررسی می‌گردد.
2-5-1-الگوریتم رهگیری اهداف سریعدر الگوریتم رهگیری اهداف سریع [18]، به دلیل کاهش دادن احتمال گم شدن هدف، حرکت هدف پیش‌بینی میگردد و حسگرهایی که در مسیر هدف قرار دارند قبل از رسیدن هدف به آن‌ها فعال می‌گردند. هنگامی‌که هدف وارد شبکه می‌شود حسگری که از همه به هدف نزدیک‌تر است به عنوان سرخوشه انتخاب می‌شود. بدین منظور حسگری که هدف را تشخیص داده است بر اساس قدرت سیگنال دریافتی از هدف یک زمانسنج را راه‌اندازی می‌کند به طوری که هر چه قدرت سیگنال دریافتی بیشتر باشد مقدار اولیه زمانسنج کمتر خواهد بود. بنابراین اگر یک حسگر تا اتمام زمانسنج خود پیامی مبنی بر اینکه حسگر دیگری سرخوشه شده است را دریافت نکند خود را به عنوان سرخوشه اعلام کند و این مطلب را با دادن یک پیام به همسایگانش اطلاع دهد. در الگوریتم به دلیل اینکه ممکن است فواصل بین حسگرهایی که هدف را تشخیص داده‌اند بیش از یک پرش فاصله داشته باشند و احتمال اینکه بیش از یک حسگر، کاندید سرخوشه باشند وجود خواهد داشت بنابراین زمانسنج دومی بین کاندیدها راه‌اندازی می‌گردد تا با مکانیزم فوق یک حسگر سرخوشه گردد.
هنگامی‌که سرخوشه انتخاب شد سرخوشه یک پیام مبنی بر اینکه سرخوشه شده است را برای تمام همسایگانش که یک یال با آن فاصله دارند می‌فرستد. هر حسگری که این پیام را دریافت می‌کند به عنوان یک عضو از این خوشه قرار میگیرد. سپس، این اعضا قدرت سیگنال دریافتی خود را در زمان‌های مشخصی به سرخوشه می‌رسانند تا سرخوشه قادر به مکان‌یابی هدف باشد. سرخوشه پس از دریافت این اطلاعات از تمام حسگرهای عضو خوشه خود برای تعیین محل هدف، سه پیام که حسگرهای ارسال‌کننده آن به هدف نزدیک‌تر میباشند را انتخاب می‌کند و مکان جاری هدف و سرعت و جهت حرکت هدف را با استفاده از تکنیک های مکان‌یابی هدف بدست می‌آورد. سرخوشه جاری با توجه به سرعت و مسیر حرکت هدف که محاسبه می‌گردد، تعداد خوشه‌های مورد نیاز برای تشکیل در مسیر هدف را مشخص می‌کند. هر چه سرعت هدف بالاتر باشد تعداد این خوشه‌ها نیز بیشتر خواهد شد. حسگرهای موجود در این خوشه‌ها به حالت فعال میروند و تا وقتی که هدف را تشخیص نداده‌اند حالت خود را به حالت خوابیده تغییر نمیدهند. REF _Ref349488720 h شکل2-19 ماشین حالت این الگوریتم را نشان می‌دهد.

شکل2- SEQ شکل2- * ARABIC 19: ماشین حالت الگوریتم رهگیری اهداف سریع [18].در صورتی که هدف از مسیر پیش‌بینی‌شده خود منحرف شود یکی از خوشهها به این موضوع پی می‌برد. بنابراین حسگر سرخوشهای که هدف در برد خوشه آن قرار دارد جهت جدید حرکت هدف را محاسبه میکند و خوشهها در جهت جدید فعال میگردند. این فرایند بدین گونه انجام میشود که سرخوشه فعلی با توجه به مسیر حرکت محاسبه‌شده نزدیک‌ترین حسگر به این مسیر را به عنوان سرخوشه انتخاب میکند و پیام سرخوشه شدن را برای آن ارسال می‌کند. سرخوشه جدید، خوشه‌های جدید خود را توسط الگوریتم تشکیل خوشه ایجاد می‌کند و با توجه به فعال بودن حسگرهایی که در مسیر قدیمی قرار داشته‌اند و به منظور جلوگیری از هدر رفتن انرژی در صورتی که حسگرها هدف را تا مدت زمان معینی تشخیص ندهند حالت خود را به حالت خوابیده تغییر می‌دهند.
2-5-2-الگوریتم رهگیری هدف با همکاری خوشههادر الگوریتم رهگیری هدف با همکاری خوشهها [19]، یک معماری رهگیری هدف ارائه گردیده است که بر اساس مصرف انرژی الگوریتم سعی در بهینهسازی آن شده است. در این الگوریتم فرض می‌گردد هنگامی تشخیص هدف صورت گرفته است که فاصله حسگر پیشرو تا هدف از یک حد آستانه کمتر باشد. بعد از تشخیص هدف الگوریتم خوشه‌بندی پویا به منظور خوشهبندی حسگرها و رهگیری هدف بکار برده می‌گردد. در الگوریتم خوشهبندی پویا به منظور شکل‌گیری خوشه ابتدا حسگری که قدرت سیگنال شناسایی هدف آن از یک حد آستانه بیشتر میباشد خود را به عنوان سرخوشه موقتی اعلام میکند. به دلیل اینکه امکان دارد بیش از یک حسگر سرخوشه گردد از یک روش انتخاب سرخوشه دو مرحله‌ای که بر اساس تاخیر تصادفی است، استفاده می‌گردد تا فقط یک حسگر به عنوان سرخوشه در هر مرحله انتخاب گردد. در روش انتخاب سرخوشه ابتدا حسگرهای سرخوشه موقتی بر اساس قدرت سیگنال دریافتی از هدف یک زمانسنج را راه‌اندازی می‌کند به طوری که هر چه قدرت سیگنال دریافتی بیشتر باشد مقدار اولیه زمانسنج کمتر خواهد بود. هر کدام از حسگرهای سرخوشه موقتی تا اتمام زمان‌سنج خود پیامی را ارسال نمیکنند. اگر در زمان اتمام زمانسنج پیامی توسط حسگر سرخوشه موقتی دریافت گردیده شده باشد، این حسگر پیامی را به همسایگان خود ارسال نخواهد کرد. در صورتی که زمانسنج یک حسگر سرخوشه موقتی خاتمه یافت و آن حسگر پیامی را دریافت نکرده باشد، بسته‌ی انرژی که حاوی اطلاعات حسی هدف میباشد را برای تمام همسایگان خود ارسال میکند و زمانسنج دومی را بر اساس قدرت سیگنال دریافتی از هدف راه‌اندازی می‌کند. در صورتی که زمانسنج دوم یک حسگر سرخوشه موقتی خاتمه یافت و آن حسگر پیامی را دریافت نکرده باشد، خود را به عنوان سرخوشه معرفی کرده و بسته حاوی اثر که حاوی اطلاعات کامل اثر میباشد ارسال میگردد [20]. هنگامی‌که سرخوشه انتخاب گردید حسگرهایی برای عضویت در خوشه تحت نظارت آن سرخوشه انتخاب می‌شوند که دارای شرایط زیر باشند:
مقدار سیگنال دریافتی آن‌ها از حد آستانه مورد نظر بیشتر باشد.
برد ارتباطی آن‌ها از فاصله آن‌ها از سرخوشه بیشتر باشد.
مقدار انرژی باقیمانده در آن‌ها بیش از حد آستانه باشد.
در این الگوریتم در صورتی که سرخوشه جدیدی ایجاد گردید، به منظور بالا بردن دقت در مکان‌یابی هدف، سرخوشه جدید اطلاعات هدف را از حسگرهایی که در خوشه قبلی به هدف نزدیک‌تر بودند بدست می‌آورد و با استفاده از آن‌ها مکان‌یابی را انجام می‌دهد.
2-5-3-الگوریتم DELTAدر الگوریتم DELTA [21]، رویدادهای موجود بین حسگرها به وسیله روش توزیع‌شده‌ای سازماندهی می‌گردند تا سربار ارتباطی موجود بین حسگرها کاهش یابد و در نتیجه دقت رهگیری هدف بالا رود. در این الگوریتم ابتدا همه حسگرها در حالت بیکار قرار دارند و هر کدام از حسگرها در فاصله‌های زمانی نمونه‌برداری هدف را شناسایی می‌کنند. در صورتی که هدفی برای اولین بار توسط حسگری شناسایی گردید، آن حسگر حالت خود را به حالت انتخاب تغییر خواهد داد. حسگرهایی که حالت آنها، حالت انتخاب می‌باشد بر اساس قدرت سیگنال دریافتی از هدف، زمان‌سنجی را راه‌اندازی می‌کنند و هنگامی‌که زمان‌سنج خاتمه می‌یابد، پیام رهبر شدن خود را مکررا به صورت همگانی به حسگرهایی که در برد ارتباطی آن قرار دارند ارسال می‌کنند. در صورتی که حسگری پیام رهبر شدن را دریافت کرد حالت خود را به حالت عضو تغییر می‌دهد و آن حسگر را به عنوان رهبر خود انتخاب می‌کند. در نهایت در صورتی که هدف توسط حسگرهای عضو شناسایی گردید، فاصله نسبی خود تا هدف را برای حسگر رهبر ارسال می‌کنند و آن حسگر نیز با استفاده از اطلاعات بدست آورده شده از حسگرهای عضو، موقعیت هدف را به ایستگاه پایه ارسال می‌کند. در صورتی که حسگر رهبر قادر به شناسایی هدف نباشد پیام انتخاب مجدد رهبر را به صورت همگانی به حسگرهای عضو خود ارسال می‌کند و حالت خود را به حالت بیکار تغییر می‌دهند. در صورت دریافت این پیام، حسگرهای عضو حالت خود را به حالت انتخاب تغییر می‌دهند تا حسگر جدیدی را به عنوان رهبر خود انتخاب کنند. REF _Ref349491468 h شکل2-20 روند تغییرات حالات حسگرها را نشان می‌دهد.

شکل2- SEQ شکل2- * ARABIC 20: ماشین حالات الگوریتم DELTA [21].2-5-4-الگوریتم DPTدر الگوریتم DPT [22]، به منظور اینکه امکان رهگیری هدف با تغییرات در مسیر حرکت و اندازه سرعت هدف امکانپذیر باشد یک معماری برای مدیریت و هماهنگ‌سازی حسگرهای موجود در شبکه‌های حسگر بیسیم ارائه گردیده است. این الگوریتم بر اساس پیشبینی عمل کرده و از خوشه‌بندی به منظور ایجاد قابلیت گسترش و قابلیت اطمینان استفاده گردیده است. در این الگوریتم سرخوشه یک توصیفگر هدف برای هر هدفی که تشخیص داده می‌شود تعریف می‌کند. توصیفگر حاوی اطلاعاتی مانند شناسه هدف، محل کنونی هدف، محل پیش‌بینی‌شده هدف و برچسب زمانی است. در هر زمان هر سرخوشه یک توصیفگر هدف به عنوان نتیجه حس کردن خوشه‌اش را به حسگر مقصد ارسال می‌کند. اولین فیلد در یک توصیف گر شناسه هدف است که برای شناسایی بدون ابهام یک هدف در بین سرخوشه های مختلف استفاده می‌شود. با استفاده از داده‌های حسی سه حسگر توسط سرخوشه و بکار بردن یکی از روش‌های موجود برای مکان‌یابی مکان فعلی هدف تعیین می‌شود. فیلد دیگر، مکان بعدی هدف است که باید با استفاده از مکان‌های قبلی محاسبه‌شده پیش‌بینی شود. در این الگوریتم به منظور جلوگیری از استفاده بیش از حد انرژی از پیش‌بینی کننده‌ای استفاده‌شده است که بر اساس دو نقطه(مکان هدف در دو موقعیت قبل) مکان آینده هدف را پیشبینی میکند. پس از اینکه محل هدف توسط سرخوشه جاری پیشبینی شد به سرخوشهای که در نزدیکی این محل است پیامی ارسال می‌گردد. آن سرخوشه نیز سه حسگری که در برد خوشه تحت نظارت سرخوشه قرار دارند و از تمام حسگرهای عضو سرخوشه به مکان پیش‌بینی‌شده هدف نزدیک‌تر هستند به عنوان حسگرهای محاسبه کننده مکان هدف فعال می‌گردند. این روند در REF _Ref349497279 h شکل2-21 نشان داده شده است.

شکل2- SEQ شکل2- * ARABIC 21:جستجو برای حسگرهای مکان‌یابی با شعاع حسی کم [22].حال اگر سرخوشه نتوانست سه حسگر مناسب برای مکان‌یابی هدف را پیدا کند به دلیل اینکه ارتباطات بین حسگرهای داخل خوشه نسبت به ارتباطات بین خوشه‌های متفاوت، انرژی کمتری استفاده می‌کنند بنابراین به منظور صرفه‌جویی در مصرف انرژی فرض گردیده است که حسگرها دارای دو شعاع حسی میباشند و در این مرحله حسگرهایی برگزیده می‌گردند که مکان پیش‌بینی‌شده هدف در برد حسی حداکثر حسگر باشند. این روند در REF _Ref349497256 h شکل2-22 نشان داده شده است.

شکل2- SEQ شکل2- * ARABIC 22:جستجو برای حسگرهای مکان‌یابی با شعاع حداکثری[22].حال اگر پس از طی مرحله دوم سرخوشه نتوانست سه حسگر مناسب برای مکان‌یابی هدف را پیدا کند از خوشه‌های همسایه بدین منظور استفاده می‌گردد. این روند در REF _Ref349497244 h شکل2-23 نشان داده شده است

شکل2- SEQ شکل2- * ARABIC 23: جستجو برای حسگرهای مکان‌یابی در خوشه‌های مجاور[22].در هنگام بروز خطا باید یک طرح بازیابی هدف وجود داشته باشد که این خطا ممکن است ناشی از بروز اشکال در حسگر با پیوند ارتباطی آن باشد. یک راه حل ساده برای این کار فعال کردن عده‌ای از حسگرها که در نزدیکی مکان مورد پیش‌بینی هدف هستند، میباشد. شعاع محل در برگیرنده این حسگرها بستگی زیادی به سرعت هدف و مدت زمان گذشته از آخرین باری که هدف تشخیص داده شده است، دارد. به منظور صرفه‌جویی در مصرف انرژی در ابتدا حسگرهایی که وظیفه شناسایی هدف را دارند برد حسی خود را به برد حسی حداکثری تغییر داده تا هدف را تشخیص دهند، در صورت عدم یافت شدن هدف حسگرهایی که در رنج برد حسی نرمال حسگرهایی که وظیفه شناسایی هدف را بر عهده دارند، فعال گردیده تا جستجوی هدف در ناحیه‌ای با شعاع دو برابر برد نرمال ادامه پیدا کند و در صورت عدم یافت شدن هدف این شعاع تا آنجا افزایش می‌یابد تا هدف پیدا شود. این فرایند در REF _Ref349491582 h شکل2-24 نشان داده شده است

شکل2- SEQ شکل2- * ARABIC 24: سطح دوم از فرایند بازیابی هدف[22].2-5-5-الگوریتم CDTAدر الگوریتم CDTA[23]، به منظور کمینه کردن رابطه بین مصرف انرژی و دقت رهگیری هدف، فرستنده یک مجموعه کمینه از حسگرها را بر اساس مسیر حرکت هدف در فاصله زمانی نمونه‌برداری بیدار می‌کند و وظیفه رهگیری هدف را بین حسگرهای فعال، زمان‌بندی می‌کند به گونه‌ای که هدف به صورت پیوسته قابل رهگیری باشد. همچنین در این الگوریتم به منظور کاهش مصرف انرژی، یک حد آستانه‌ای، برای مدت زمان شناسایی هدف توسط حسگرهای فعال در نظر گرفته شده است و در صورتی که حسگر فعال در مدت زمان حد آستانه قادر به شناسایی کردن هدف نباشد آن حسگر حالت خود را به حالت خواب تغییر خواهد داد.
در این الگوریتم فرض گردیده است که دو نوع حسگر در شبکه موجود می‌باشد: حسگرهای اجرایی و حسگرهای انتشاردهنده. حسگرهای اجرایی حسگرهایی می‌باشند که در شبکه پخش گردیده‌اند به گونه‌ای که بتوانند کل شبکه را تحت پوشش خود قرار دهند و وظیفه شناسایی اهداف متحرک و ارسال اطلاعات هدف به حسگرهای انتشاردهنده را بر عهده دارند. حسگرهای انتشاردهنده، حسگرهایی هستند که نسبت به حسگرهای اجرایی از انرژی بیشتری برخوردار خواهند بود و وظایف زیر را بر عهده خواهند داشت:
ارسال اطلاعات رسیده از حسگرهای اجرایی به حسگر چاهک
تعیین مجموعه کمینه از حسگرهای اجرایی به منظور رهگیری اهداف متحرک
ارسال پیام اخطار به حسگرهای انتشاردهنده همسایه‌هایش در هنگام خروج هدف از ناحیه مربعی شکل تحت رهبری آن
اجرای الگوریتم تصحیح خطا به منظور پیدا کردن موقعیت هدف در صورتی که حسگرهای اجرایی قادر به رهگیری هدف در فاصله زمانی نمونه‌برداری نباشند.
در این الگوریتم به منظور رهگیری هدف از دو رویه رهگیری هدف و رویه انتخاب حسگرها استفاده گردیده است. رویه رهگیری هدف از چهار فاز تشکیل گردیده است که در زیر هر کدام از این فازها توضیح داده شده است.
فاز اول: در این فاز هنگامی‌که هدف در خارج از شبکه قرار دارد، تمام حسگرهای اجرایی که بر روی یالی از ناحیه که هدف به آن یال نزدیک‌تر است، قرار دارند توسط حسگر چاهک بیدار می‌گردند
فاز دوم: در این فاز هر کدام از حسگرهای اجرایی که قادر به شناسایی کردن هدف باشند به حسگر انتشاردهنده مربوط به خود پیامی را ارسال می‌کنند. این پیام شامل شماره شناسایی حسگر اجرایی شناسایی کننده هدف، انرژی باقیمانده آن حسگر و اطلاعات بدست آمده از هدف توسط آن حسگر می‌باشد. هنگام دریافت این اطلاعات توسط حسگر انتشاردهنده، با توجه به اینکه هدف به صورت پیوسته در حال حرکت می‌باشد در هر فاصله زمانی نمونه‌برداری توسط حسگر انتشاردهنده مربوطه، سه حسگر اجرایی توسط رویه انتخاب حسگرها انتخاب می‌گردند و این سه حسگر وظیفه رهگیری هدف را بر عهده خواهند داشت. تا زمانی که جهت حرکت هدف بدست آورده نشده است حسگرهای انتخاب‌شده در فاصله زمانی قبل فعال می‌باشند تا هدف را شناسایی کنند. در این الگوریتم با توجه به اینکه روشن و خاموش کردن واحد ارتباطی حسگرها انرژی زیادی را مصرف خواهد کرد، حسگرهایی که توسط حسگر انتشاردهنده فعال گردیده‌اند حالت خود را تغییر نمی‌دهند.
فاز سوم: در این فاز به بررسی رهگیری هدف از یک ناحیه به ناحیه دیگر پرداخته شده است. با توجه به اینکه هر کدام از حسگرهای انتشاردهنده علاوه بر حسگرهای درون ناحیه تحت نظارت خود با حسگرهای مرزی نواحی همسایه‌های خود در ارتباط می‌باشند، در صورتی که هدف توسط حسگرهای مرزی همسایه‌های حسگر انتشاردهنده فعال شناسایی گردید حسگر انتشاردهنده فعال موقعیت هدف را به حسگر انتشاردهنده‌ای که هدف در ناحیه آن قرار دارد ارسال می‌کند. هنگامی‌که حسگر انتشاردهنده‌ای این پیام را دریافت کرد، در فاصله زمانی نمونه‌برداری توسط رویه انتخاب حسگر، سه حسگر انتخاب می‌گردد و حسگر انتشاردهنده این پیام حالت خود را به حالت خواب تغییر خواهد داد. این سه حسگر انتخاب‌شده توسط حسگر انتشاردهنده جاری حالت خود را به حالت فعال تغییر خواهند داد و وظیفه شناسایی هدف بر عهده این سه حسگر گذاشته می‌شود.
فاز چهارم: در این فاز به بررسی الگوریتم تصحیح خطا پرداخته شده است. در صورتی که حسگر انتشاردهنده فعال قادر به رهگیری هدف نباشد در ابتدا حسگر انتشاردهنده به تمام حسگرهای تحت نظارت خود پیامی را به صورت سیل‌آسا ارسال می‌کند تا در صورت وجود هدف در ناحیه تحت نظارت خود آن هدف شناسایی گردد. در صورتی که هدف در مرحله قبل شناسایی نگردید، حسگر چاهک تمام حسگرهای انتشاردهنده موجود در شبکه را فعال می‌کند تا در کل شبکه به جستجو هدف مورد نظر پرداخته شود و هدف شناسایی گردد.
2-6- نتیجه‌گیریدر این فصل به بررسی تحقیقات انجام‌شده در زمینه رهگیری هدف در شبکه‌های حسگر همه جهته پرداخته شده است. چهار گروه اصلی الگوریتم‌های رهگیری هدف در شبکه‌های حسگر همه جهته، معرفی‌شده‌اند و نمونه‌هایی از هر کدام آنها بررسی شد. این چهار گروه اصلی عبارتند از: الگویتم های مبتنی بر پیام، الگوریتم‌های مبتنی بر درخت، الگوریتم‌های مبتنی بر پیش‌بینی و الگوریتم‌های مبتنی بر خوشه. طبقه‌بندی ارائه‌شده در این فصل برای شناخت الگوریتم پیشنهادی در این پایان‌نامه مورد استفاده قرار گرفته است.

فصل سوممدل‌های حرکتی3-1- مقدمهدر بسیاری از کاربردهای شبکههای حسگر مانند رهگیری اهداف متحرک، کشف رویدادها و … لازم است که حسگرهای شبکه از مکان فیزیکی خود باخبر باشند. به دلیل اینکه حسگرها دارای انرژی محدودی می‌باشند و با توجه به اینکه سیستم GPS دارای هزینه بالایی می‌باشد، مجهز کردن تمام حسگرها به سیستمهایی نظیر GPS امکان‌پذیر نمی‌باشد. بنابراین ضرورت وجود الگوریتم‌های مکان‌یابی در شبکه‌های حسگر احساس می‌گردد. در این الگوریتم‌ها با استفاده از مکان دقیق تعداد کمی از حسگرها و معیارهای اندازه‌گیری نظیر فاصله و جهت، مکان حسگرها بدست می‌آیند که در ادامه هر کدام از این الگوریتم‌ها توضیح داده خواهد شد. به منظور شبیه‌سازی و ارزیابی کارایی سیستم های بی‌سیم متحرک و الگوریتم‌ها و پروتکل‌ها، از مدل‌های حرکتی استفاده می‌گردد. در عمل دو نوع مدل برای شبیه‌سازی سیستم های متحرک وجود دارد: اثر حرکت و مدل‌های ترکیبی. در یک مدل ترکیبی، یک سری از معاملات ریاضی بیانگر مدل می‌گردند درحالی‌که در مدل اثر حرکت که دارای دقت بالاتری نسبت به روش مدل ترکیبی میباشد، با استفاده از مکان‌های حسگر متحرک و ارتباطات میان آن‌ها مدل بیان می‌گردد. به منظور شبیه‌سازی کامل یک پروتکل جدید برای یک شبکه بی‌سیم باید یک مدل حرکتی انتخاب شود که نمایانگر حسگرهای متحرکی باشند که انتظار می‌رود در این شبکه حرکت کنند و از خصوصیات یک مدل حرکتی این است که حدالمقدور به حرکات واقعی یک حسگر متحرک نزدیک باشد و تغییرات در سرعت و جهت باید در بازههای زمانی منطقی اتفاق بیفتد. مدلهای حرکتی نیز از دیدگاه زمانی- مکانی به سه دسته تقسیم میگردد: وابستگی زمانی،
وابستگی مکانی، محدودیت جغرافیایی. مدلهای وابستگی زمانی، مدلهایی هستند که حرکت یک حسگر از تاریخچه حرکتی خود آن حسگر تاثیر میپذیرد. مدل‌های وابستگی مکانی، مدل‌هایی هستند که حسگرها با یک وابستگی فضایی حرکت می‌کند و مدل‌های محدودیت جغرافیایی مدل‌هایی هستند که حسگرها در محدوده جغرافیایی خاصی مانند خیابانها و آزادراهها و … حرکت می‌کند.
3-2-مکان‌یابی در شبکه‌های حسگردر الگوریتم‌های رهگیری هدف لازم است که حسگرها، مکان خود را به صورت فیزیکی بدانند و همچنین مجهز کردن تمام حسگرها به سیستم‌هایی نظیر GPS به دلیل پاره‌ای محدودیت‌هایی چون عدم عملکرد GPS در محیط‌های درونی، هزینه بالای این کار و اندازه و توان محدود حسگرها اصلا مقرون به صرفه نیست. بنابراین الگوریتم‌های مکان‌یابی برای شبکه‌های حسگر که وظیفه رهگیری هدف را بر عهده دارند ضروری به نظر می‌رسد. این الگوریتم‌ها با استفاده از مکان دقیق تعداد کمی از حسگرها و معیارهای اندازه‌ی مابین حسگرها، مانند فاصله و جهت، مکان حسگرها را به دست می‌آورند. در زیر انواع الگوریتم مکان‌یابی در شبکه‌های حسگر ارائه گردیده است.
3-2-1-الگوریتم زمان انتشار یک طرفهدر الگوریتم زمان انتشار یک طرفه [24]، از اختلاف بین زمان ارسال سیگنال در فرستنده و زمان دریافت سیگنال در گیرنده برای محاسبه فاصله بین حسگرهای همسایه استفاده می‌گردد و در نتیجه این الگوریتم نیازمند این است که حسگرهای گیرنده و فرستنده با یکدیگر همگام باشند. این نیاز موجب افزایش قیمت حسگرها با توجه به تقاضای ساعت‌های دقیق‌تر و یا افزایش پیچیدگی شبکه‌ی حسگر با توجه به تقاضای روش‌های همگام‌سازی سطح بالا می‌شود.
3-2-2-الگوریتم زمان انتشار رفت و برگشتدر الگوریتم زمان انتشار رفت و برگشت [24]، از اختلاف بین زمان ارسال سیگنال توسط حسگر ارسال‌کننده و زمانی که سیگنال بازتاب شده توسط حسگر ارسال‌کننده دریافت می‌شود برای محاسبه فاصله بین حسگرهای همسایه استفاده می‌گردد و بنابراین این الگوریتم نیازمند همگام‌سازی بین حسگرها نمی‌باشد. مهمترین خطایی که در این الگوریتم وجود دارد مربوط به تاخیر بازتاب سیگنال دریافتی توسط حسگر دوم می‌باشد و به منظور رفع این خطا، میزان تاخیر در حسگر دوم محاسبه می‌گردد و به حسگر اول ارسال می‌شود تا از زمان بدست آمده در اندازه‌گیری کاسته شود.
3-2-3-الگوریتم فانوس دریاییدر الگوریتم فانوس دریایی [24]، فاصله بین گیرنده و فرستنده نوری را با اندازه‌گیری دوره زمانی که گیرنده در پرتو ساکن است تخمین زده می‌شود. در این الگوریتم فرستنده Z به یک پرتو نوری موازی با پهنای ثابت b مجهز می‌باشد که این فرستنده در مبدا مستقر می‌باشد و این پرتو نور با سرعت زاویه‌ای نامعلوم w به دور فرستنده Z در حال چرخش می‌باشد. در این الگوریتم به منظور بدست آوردن میزان سرعت زاویه‌ای w از اختلاف زمانی بین لحظه زمانی که گیرنده نوری برای اولین بار پرتو را پیدا می‌کند و لحظه‌ای که برای دومین بار پرتوی نوری توسط گیرنده نوری تشخیص داده می‌شود استفاده می‌گردد و با توجه به REF _Ref348476284 h شکل 3-1 می‌توان نشان داد که با استفاده از رابطه3-1 فاصله d که به فاصله بین گیرنده و فرستنده نوری اشاره دارد بدست آورده می‌شود.
(3-1)
مهمترین مزیت این روش این است که گیرنده نوری می‌تواند اندازه‌های کوچکی داشته باشد هرچند که فرستنده ممکن است بزرگ باشد ولی عیب این روش این است که خط دید بین گیرنده نوری و فرستنده باید مستقیم باشد.

شکل 3- SEQ شکل_3- * ARABIC 1: الگوریتم فانوس دریایی[24].3-2-4-الگوریتم تخمین فاصله از طریق اندازه‌گیری قدرت سیگنال دریافتیدر الگوریتم تخمین فاصله از طریق اندازه‌گیری قدرت سیگنال [24]، فاصله بین حسگرهای همسایه را با اندازه‌گیری قدرت سیگنال دریافتی تخمین می‌زنند که این روش بر مبنای ویژگی استاندارد قدرت سیگنال دریافتی (RSSI) که در بسیاری از وسایل بی‌سیم یافت می‌شود، استوار میباشد زیرا نیاز به هیچ سخت‌افزار اضافی ندارد و بعید است که اثر مهمی روی مصرف انرژی، اندازه حسگر و قیمت آن داشته باشد. با توجه به اینکه در فضای آزاد قدرت سیگنال دریافتی(RSS) با معکوس مجذور فاصله بین گیرنده و فرستنده متناسب می‌باشد می‌توان توان دریافتی(Pr(d)) را از رابطه3-2 بدست آورد.
(3-2)
در رابطه3-2، Pt اشاره به توان فرستنده، Gt و Gr به ترتیب اشاره به بهرهی آنتن فرستنده و گیرنده و اشاره به طول موج سیگنال ارسالی بر حسب متر دارند. هرچند که مدل فضای آزاد به هر حال ایدهآل نیست و انتشار سیگنال با بازتاب، انکسار و تفریق تحت تاثیر قرار می‌گیرد، اما این موضوع به تجربه پذیرفته شده است که Pr(d) مربوط به قدرت سیگنال دریافتی در فاصله d از فرستنده در یک مکان خاص به صورت یک توزیع تصادفی lognormal می‌باشد که مقدار میانگین این توزیع وابسته به مکان می‌باشد. بنابراین Pr(d) را می‌توان از رابطه3-3 بدست آورد.
(3-3)
در رابطه3-3، P0(d0) اشاره به توان مرجع شناخته‌شده بر مبنای دسی‌بل- میلی وات(dbm) در فاصله مرجع d0 از فرستنده دارد. np اشاره به افت توان در مسیر دارد. این پارامتر وابسته به محیط می‌باشد و نرخی را که قدرت سیگنال دریافتی با فاصله کم می‌گردد را محاسبه می‌کند. اشاره به متغییر تصادفی گوسی با میانگین صفر و انحراف معیار دارد که به منظور محاسبه اثر shadowing به کار گرفته شده است.
با استفاده از رابطه3-3 و قدرت سیگنال دریافتی بین فرستنده و گیرنده‌ای که در فاصله dij از فرستنده قرار دارد، فاصله بین فرستنده و گیرنده به وسیله رابطه3-4 بدست آورده می‌گردد. در این رابطه Pij اشاره به قدرت سیگنال دریافتی بین فرستنده و گیرنده دارد.
(3-4)
3-2-5-الگوریتم مکان‌یابی به وسیله GPSدر این الگوریتم مکان‌یابی به وسیله GPS [24]، از 24 ماهواره که در مدار میانی زمین قرار دارند استفاده می‌گردد. مدار میانی زمین در فاصله 20200 کیلومتری از زمین قرار دارد. هر کدام از ماهواره‌ها به منظور همگام‌سازی بین ماهواره‌ها مجهز به چندین ساعت اتمی با دقت بسیار بالا می‌باشند. در این الگوریتم یک گیرنده GPS در سطح زمین قرار دارد فاصله خود را از ماهواره‌های GPS از طریق الگوریتم زمان انتشار یک طرفه بدست می‌آورد و بنابراین به صورت ایده آل با استفاده از اطلاعات بدست آمده توسط سه ماهواره، گیرنده GPS می‌تواند موقعیت خود را بدست می‌آورد. با توجه به اینکه در همگام‌سازی ساعت گیرنده و ماهواره‌ها خطاهای محاسباتی وجود خواهد داشت از الگویتم های تصحیح خطا مانند روش‌های مثلث سازی استفاده میگردد تا ساعت گیرنده با دقت بیش از ns100 به ماهواره‌ها همگام شود.
روش مثلث سازی [25]:
در این روش به منظور بدست آوردن موقعیت حسگر غیر مرجع که دارای مکان نامشخص می‌باشد از حسگرهای مرجعی که مکان آنها مشخص می‌باشد استفاده می‌گردد. همان طور که در REF _Ref348476339 h شکل 3-2 نشان داده شده است در این روش فرض گردیده است که حسگر غیر مرجع دارای موقعیت (x,y) می‌باشد و هر کدام از حسگرهای مرجع i دارای موقعیت (xi,yi) و زاویه با محور x می‌باشند. در REF _Ref348476339 h شکل 3-2، S1 و S2 حسگرهای مرجع،و به ترتیب زاویه حسگر مرجع 1 و 2 با محور x می‌باشند و X نیز به حسگر غیر مرجع اشاره دارد.

شکل 3- SEQ شکل_3- * ARABIC 2: روش مثلث سازی[25].بنابراین در این روش با مشخص بودن موقعیت حسگرهای مرجع و زاویه آنها با محور x و با توجه به رابطه3-5 می‌توان موقعیت حسگر غیر مرجع x را بدست آورد.
(3-5)
در این روش به وسیله هر کدام از زوج حسگرهای مرجع (Si,Sj) موقعیت حسگر غیر مرجع بدست آورده می‌شود و به وسیله رابطه3-6 دقت تخمین بدست آوردن موقعیت حسگر غیر مرجع توسط آن زوج حسگر مرجع بدست آورده می‌شود. هر کدام از زوج حسگرهای مرجعی که دقت تخمین آن‌ها کمتر از دیگر زوج حسگرهای مرجع باشد به عنوان زوج حسگر مناسب انتخاب می‌گردد و به وسیله این زوج حسگر موقعیت حسگر غیر مرجع بدست آورده می‌شود.
(3-6)
همان طور که در REF _Ref348476339 h شکل 3-2 نشان داده شده است، در رابطه بالا اشاره به زاویه بین حسگرهای مرجع Si و Sj با حسگر غیر مرجع x دارد.
3-2-6-الگوریتم مکان‌یابی تک گامه با روش فانوس دریاییدر روش فانوس دریایی [24]، از یک ایستگاه پایه مجهز به سه پرتو نوری استفاده می‌شود که این پرتوها در جهت‌های محورهای x و y و z و به صورت دوطرفه انتشار می‌یابند. هنگامی‌که یک گیرنده نوری که در برد مستقیم ایستگاه پایه قرار دارد این سه پرتو را دریافت کند، مکان گیرنده نوری(Xt) متناسب با فاصله‌ی اندازه‌گیری شده از محورهای x، y، z است که آنها را به ترتیب با ، و نشان می‌دهیم. این روند در REF _Ref348476392 h شکل 3-3 نشان داده شده است. بعد از حل معادلات رابطه‌های 3-7، 3-8 و 3-9 هشت جواب بدست خواهد آمد که هر یک از این جواب‌ها در یک ناحیه از فضای سه بعدی قرار دارد. بنابراین با داشتن اطلاعات پیشین در مورد فضایی که گیرنده در آن قرار دارد تنها یک جواب صحیح بدست خواهد آمد.
(3-7)
(3-8)
(3-9)

شکل 3- SEQ شکل_3- * ARABIC 3: الگوریتم مکان‌یابی تک گامه با روش فانوس دریایی[24].3-2-7-الگوریتم مکان‌یابی چند گامه بر مبنای فاصلهشالوده‌ی اصلی این روش استفاده از اندازه‌گیری فاصله‌ی بین حسگرها در شبکه‌ی حسگر برای مکان‌یابی درست شبکه است. بر اساس روش پردازش داده‌ها، الگوریتم‌های مکان‌یابی بر مبنای فاصله به دو دسته تقسیم می‌شوند: الگوریتمهای متمرکز، الگوریتم‌های توزیع‌شده.
الگوریتم‌های متمرکز، الگوریتم‌هایی هستند که در آنها از یک پردازشگر مرکزی برای جمع‌آوری تمام فاصله بین حسگرها و فراهم ساختن یک نقشه از کل شبکه‌ی حسگر استفاده می‌شود. مزایای این الگوریتم عبارت است:
پیاده‌سازی این الگوریتم نسبت به الگوریتم‌های توزیع‌شده راحت‌تر می‌باشد.
دقت تخمین روش‌های متمرکز بهتر از الگوریتم‌های توزیع‌شده می‌باشد.
احتمال انتشار خطا در الگوریتم‌های متمرکز کمتر از الگوریتم‌های توزیع‌شده می‌باشد.
الگوریتم‌های توزیع‌شده، الگوریتم‌هایی هستند که مکان‌یابی هر حسگر بر عهده خود حسگر می‌باشد و با استفاده از فاصله‌های اندازه‌گیری شده توسط حسگر و اطلاعاتی که از همسایگانش بدست آورده است مکان خود را بدست میآورد. مزایای این الگوریتم عبارت است:
این الگوریتم‌ها برخلاف الگوریتم‌های متمرکز مشکل مقیاس‌پذیری را ندارند و در شبکه‌های بزرگ کارایی دارند.
انرژی مصرفی در این شبکه‌ها به علت انتشار محلی اطلاعات نسبت به الگوریتم‌های متمرکز کمتر می‌باشد.
زمان اجرای الگوریتم‌های توزیع‌شده نسبت به الگوریتم‌های متمرکز کمتر است .
3-3-مدل‌های حرکتی تصادفیدر مدل‌های تصادفی گره‌های متحرک به صورت تصادفی و آزاد بدون محدودیت حرکت می‌کنند. به طور دقیق‌تر مقصد، سرعت و جهت حرکت گره به صورت تصادفی و مستقل از دیگر گره‌ها انتخاب می‌شود. از انواع مدل‌های حرکتی در این زمینه می‌توان به مدل‌های نقطه راه تصادفی، جهت تصادفی، راهپیمایی تصادفی و راهپیمایی جمع‌آوری اشاره کرد.
3-3-1-مدل حرکتی نقطه راه تصادفیدر مدل نقطه راه تصادفی [26]، [27]، هر گره متحرک به صورت تصادفی یک مکان را انتخاب می‌کند و با یک سرعت ثابت که به صورت تصادفی از یک بازه بین صفر تا حداکثر سرعت مجاز گره انتخاب می‌شود، حرکت می‌کند. هنگامی‌که گره به مقصد رسید به مدت زمانی برابر بازمان مکث میایستد و پس از این مدت دوباره یک مکان تصادفی انتخاب میکند و به سمت آن با سرعت ثابت حرکت می‌کند. این فرایند آن قدر تکرار می‌گردد تا شبیه‌سازی به اتمام برسد. REF _Ref348476436 h شکل 3-4 الگوی حرکتی این مدل را نشان می‌دهد.