شکل۲-۲۱:جستجو برای حسگرهای مکان‌یابی با شعاع حسی کم [۲۲].

حال اگر سرخوشه نتوانست سه حسگر مناسب برای مکان‌یابی هدف را پیدا کند به دلیل اینکه ارتباطات بین حسگرهای داخل خوشه نسبت به ارتباطات بین خوشه‌های متفاوت، انرژی کمتری استفاده می‌کنند بنابراین به منظور صرفه‌جویی در مصرف انرژی فرض گردیده است که حسگرها دارای دو شعاع حسی می­باشند و در این مرحله حسگرهایی برگزیده می‌گردند که مکان پیش‌بینی‌شده هدف در برد حسی حداکثر حسگر باشند. این روند در شکل۲-۲۲ نشان داده شده است.

شکل۲-۲۲:جستجو برای حسگرهای مکان‌یابی با شعاع حداکثری[۲۲].
حال اگر پس از طی مرحله دوم سرخوشه نتوانست سه حسگر مناسب برای مکان‌یابی هدف را پیدا کند از خوشه‌های همسایه بدین منظور استفاده می‌گردد. این روند در شکل۲-۲۳ نشان داده شده است

شکل۲-۲۳: جستجو برای حسگرهای مکان‌یابی در خوشه‌های مجاور[۲۲].
در هنگام بروز خطا باید یک طرح بازیابی هدف وجود داشته باشد که این خطا ممکن است ناشی از بروز اشکال در حسگر با پیوند ارتباطی آن باشد. یک راه حل ساده برای این کار فعال کردن عده‌ای از حسگرها که در نزدیکی مکان مورد پیش‌بینی هدف هستند، می­باشد. شعاع محل در برگیرنده این حسگرها بستگی زیادی به سرعت هدف و مدت زمان گذشته از آخرین باری که هدف تشخیص داده شده است، دارد. به منظور صرفه‌جویی در مصرف انرژی در ابتدا حسگرهایی که وظیفه شناسایی هدف را دارند برد حسی خود را به برد حسی حداکثری تغییر داده تا هدف را تشخیص دهند، در صورت عدم یافت شدن هدف حسگرهایی که در رنج برد حسی نرمال حسگرهایی که وظیفه شناسایی هدف را بر عهده دارند، فعال گردیده تا جستجوی هدف در ناحیه‌ای با شعاع دو برابر برد نرمال ادامه پیدا کند و در صورت عدم یافت شدن هدف این شعاع تا آنجا افزایش می‌یابد تا هدف پیدا شود. این فرایند در شکل۲-۲۴ نشان داده شده است
شکل۲-۲۴: سطح دوم از فرایند بازیابی هدف[۲۲].
۲-۵-۵- الگوریتم CDTA
در الگوریتم ^[۳۴]CDTA[23]، به منظور کمینه کردن رابطه بین مصرف انرژی و دقت رهگیری هدف، فرستنده یک مجموعه کمینه از حسگرها را بر اساس مسیر حرکت هدف در فاصله زمانی نمونه‌برداری بیدار می‌کند و وظیفه رهگیری هدف را بین حسگرهای فعال، زمان‌بندی می‌کند به گونه‌ای که هدف به صورت پیوسته قابل رهگیری باشد. همچنین در این الگوریتم به منظور کاهش مصرف انرژی، یک حد آستانه‌ای، برای مدت زمان شناسایی هدف توسط حسگرهای فعال در نظر گرفته شده است و در صورتی که حسگر فعال در مدت زمان حد آستانه قادر به شناسایی کردن هدف نباشد آن حسگر حالت خود را به حالت خواب تغییر خواهد داد.
در این الگوریتم فرض گردیده است که دو نوع حسگر در شبکه موجود می‌باشد: حسگرهای اجرایی و حسگرهای انتشاردهنده. حسگرهای اجرایی حسگرهایی می‌باشند که در شبکه پخش گردیده‌اند به گونه‌ای که بتوانند کل شبکه را تحت پوشش خود قرار دهند و وظیفه شناسایی اهداف متحرک و ارسال اطلاعات هدف به حسگرهای انتشاردهنده را بر عهده دارند. حسگرهای انتشاردهنده، حسگرهایی هستند که نسبت به حسگرهای اجرایی از انرژی بیشتری برخوردار خواهند بود و وظایف زیر را بر عهده خواهند داشت:
ارسال اطلاعات رسیده از حسگرهای اجرایی به حسگر چاهک
تعیین مجموعه کمینه از حسگرهای اجرایی به منظور رهگیری اهداف متحرک
ارسال پیام اخطار به حسگرهای انتشاردهنده همسایه‌هایش در هنگام خروج هدف از ناحیه مربعی شکل تحت رهبری آن
اجرای الگوریتم تصحیح خطا به منظور پیدا کردن موقعیت هدف در صورتی که حسگرهای اجرایی قادر به رهگیری هدف در فاصله زمانی نمونه‌برداری نباشند.
در این الگوریتم به منظور رهگیری هدف از دو رویه رهگیری هدف و رویه انتخاب حسگرها استفاده گردیده است. رویه رهگیری هدف از چهار فاز تشکیل گردیده است که در زیر هر کدام از این فازها توضیح داده شده است.
فاز اول: در این فاز هنگامی‌که هدف در خارج از شبکه قرار دارد، تمام حسگرهای اجرایی که بر روی یالی از ناحیه که هدف به آن یال نزدیک‌تر است، قرار دارند توسط حسگر چاهک بیدار می‌گردند
فاز دوم: در این فاز هر کدام از حسگرهای اجرایی که قادر به شناسایی کردن هدف باشند به حسگر انتشاردهنده مربوط به خود پیامی را ارسال می‌کنند. این پیام شامل شماره شناسایی حسگر اجرایی شناسایی کننده هدف، انرژی باقیمانده آن حسگر و اطلاعات بدست آمده از هدف توسط آن حسگر می‌باشد. هنگام دریافت این اطلاعات توسط حسگر انتشاردهنده، با توجه به اینکه هدف به صورت پیوسته در حال حرکت می‌باشد در هر فاصله زمانی نمونه‌برداری توسط حسگر انتشاردهنده مربوطه، سه حسگر اجرایی توسط رویه انتخاب حسگرها انتخاب می‌گردند و این سه حسگر وظیفه رهگیری هدف را بر عهده خواهند داشت. تا زمانی که جهت حرکت هدف بدست آورده نشده است حسگرهای انتخاب‌شده در فاصله زمانی قبل فعال می‌باشند تا هدف را شناسایی کنند. در این الگوریتم با توجه به اینکه روشن و خاموش کردن واحد ارتباطی حسگرها انرژی زیادی را مصرف خواهد کرد، حسگرهایی که توسط حسگر انتشاردهنده فعال گردیده‌اند حالت خود را تغییر نمی‌دهند.
فاز سوم: در این فاز به بررسی رهگیری هدف از یک ناحیه به ناحیه دیگر پرداخته شده است. با توجه به اینکه هر کدام از حسگرهای انتشاردهنده علاوه بر حسگرهای درون ناحیه تحت نظارت خود با حسگرهای مرزی نواحی همسایه‌های خود در ارتباط می‌باشند، در صورتی که هدف توسط حسگرهای مرزی همسایه‌های حسگر انتشاردهنده فعال شناسایی گردید حسگر انتشاردهنده فعال موقعیت هدف را به حسگر انتشاردهنده‌ای که هدف در ناحیه آن قرار دارد ارسال می‌کند. هنگامی‌که حسگر انتشاردهنده‌ای این پیام را دریافت کرد، در فاصله زمانی نمونه‌برداری توسط رویه انتخاب حسگر، سه حسگر انتخاب می‌گردد و حسگر انتشاردهنده این پیام حالت خود را به حالت خواب تغییر خواهد داد. این سه حسگر انتخاب‌شده توسط حسگر انتشاردهنده جاری حالت خود را به حالت فعال تغییر خواهند داد و وظیفه شناسایی هدف بر عهده این سه حسگر گذاشته می‌شود.
فاز چهارم: در این فاز به بررسی الگوریتم تصحیح خطا پرداخته شده است. در صورتی که حسگر انتشاردهنده فعال قادر به رهگیری هدف نباشد در ابتدا حسگر انتشاردهنده به تمام حسگرهای تحت نظارت خود پیامی را به صورت سیل‌آسا ارسال می‌کند تا در صورت وجود هدف در ناحیه تحت نظارت خود آن هدف شناسایی گردد. در صورتی که هدف در مرحله قبل شناسایی نگردید، حسگر چاهک تمام حسگرهای انتشاردهنده موجود در شبکه را فعال می‌کند تا در کل شبکه به جستجو هدف مورد نظر پرداخته شود و هدف شناسایی گردد.
۲-۶- نتیجه‌گیری
در این فصل به بررسی تحقیقات انجام‌شده در زمینه رهگیری هدف در شبکه‌های حسگر همه جهته پرداخته شده است. چهار گروه اصلی الگوریتم‌های رهگیری هدف در شبکه‌های حسگر همه جهته، معرفی‌شده‌اند و نمونه‌هایی از هر کدام آنها بررسی شد. این چهار گروه اصلی عبارتند از: الگویتم های مبتنی بر پیام، الگوریتم‌های مبتنی بر درخت، الگوریتم‌های مبتنی بر پیش‌بینی و الگوریتم‌های مبتنی بر خوشه. طبقه‌بندی ارائه‌شده در این فصل برای شناخت الگوریتم پیشنهادی در این پایان‌نامه مورد استفاده قرار گرفته است.
فصل سوم
مدل‌های حرکتی
۳-۱- مقدمه
در بسیاری از کاربردهای شبکه ­های حسگر مانند رهگیری اهداف متحرک، کشف رویدادها و … لازم است که حسگرهای شبکه از مکان فیزیکی خود باخبر باشند. به دلیل اینکه حسگرها دارای انرژی محدودی می‌باشند و با توجه به اینکه سیستم GPS دارای هزینه بالایی می‌باشد، مجهز کردن تمام حسگرها به سیستم­هایی نظیر GPS امکان‌پذیر نمی‌باشد. بنابراین ضرورت وجود الگوریتم‌های مکان‌یابی در شبکه‌های حسگر احساس می‌گردد. در این الگوریتم‌ها با بهره گرفتن از مکان دقیق تعداد کمی از حسگرها و معیارهای اندازه‌گیری نظیر فاصله و جهت، مکان حسگرها بدست می‌آیند که در ادامه هر کدام از این الگوریتم‌ها توضیح داده خواهد شد. به منظور شبیه‌سازی و ارزیابی کارایی سیستم های بی‌سیم متحرک و الگوریتم‌ها و پروتکل‌ها، از مدل‌های حرکتی استفاده می‌گردد. در عمل دو نوع مدل برای شبیه‌سازی سیستم های متحرک وجود دارد: اثر حرکت^[۳۵] و مدل‌های ترکیبی^[۳۶]. در یک مدل ترکیبی، یک سری از معاملات ریاضی بیانگر مدل می‌گردند درحالی‌که در مدل اثر حرکت که دارای دقت بالاتری نسبت به روش مدل ترکیبی می­باشد، با بهره گرفتن از مکان‌های حسگر متحرک و ارتباطات میان آن‌ها مدل بیان می‌گردد. به منظور شبیه‌سازی کامل یک پروتکل جدید برای یک شبکه بی‌سیم باید یک مدل حرکتی انتخاب شود که نمایانگر حسگرهای متحرکی باشند که انتظار می‌رود در این شبکه حرکت کنند و از خصوصیات یک مدل حرکتی این است که حدالمقدور به حرکات واقعی یک حسگر متحرک نزدیک باشد و تغییرات در سرعت و جهت باید در بازه­های زمانی منطقی اتفاق بیفتد. مدل­های حرکتی نیز از دیدگاه زمانی- مکانی به سه دسته تقسیم می­گردد: وابستگی زمانی،
وابستگی مکانی، محدودیت جغرافیایی. مدل­های وابستگی زمانی، مدل­هایی هستند که حرکت یک حسگر از تاریخچه حرکتی خود آن حسگر تاثیر می­پذیرد. مدل‌های وابستگی مکانی، مدل‌هایی هستند که حسگرها با یک وابستگی فضایی حرکت می‌کند و مدل‌های محدودیت جغرافیایی مدل‌هایی هستند که حسگرها در محدوده جغرافیایی خاصی مانند خیابان­ها و آزادراه­ها و … حرکت می‌کند.
۳-۲- مکان‌یابی در شبکه‌های حسگر
در الگوریتم‌های رهگیری هدف لازم است که حسگرها، مکان خود را به صورت فیزیکی بدانند و همچنین مجهز کردن تمام حسگرها به سیستم‌هایی نظیر ^[۳۷]GPS به دلیل پاره‌ای محدودیت‌هایی چون عدم عملکرد GPS در محیط‌های درونی، هزینه بالای این کار و اندازه و توان محدود حسگرها اصلا مقرون به صرفه نیست. بنابراین الگوریتم‌های مکان‌یابی برای شبکه‌های حسگر که وظیفه رهگیری هدف را بر عهده دارند ضروری به نظر می‌رسد. این الگوریتم‌ها با بهره گرفتن از مکان دقیق تعداد کمی از حسگرها و معیارهای اندازه‌ی مابین حسگرها، مانند فاصله و جهت، مکان حسگرها را به دست می‌آورند. در زیر انواع الگوریتم مکان‌یابی در شبکه‌های حسگر ارائه گردیده است.
۳-۲-۱- الگوریتم زمان انتشار یک طرفه
در الگوریتم زمان انتشار یک طرفه^[۳۸] [۲۴]، از اختلاف بین زمان ارسال سیگنال در فرستنده و زمان دریافت سیگنال در گیرنده برای محاسبه فاصله بین حسگرهای همسایه استفاده می‌گردد و در نتیجه این الگوریتم نیازمند این است که حسگرهای گیرنده و فرستنده با یکدیگر همگام باشند. این نیاز موجب افزایش قیمت حسگرها با توجه به تقاضای ساعت‌های دقیق‌تر و یا افزایش پیچیدگی شبکه‌ی حسگر با توجه به تقاضای روش‌های همگام‌سازی سطح بالا می‌شود.
۳-۲-۲- الگوریتم زمان انتشار رفت و برگشت
در الگوریتم زمان انتشار رفت و برگشت^[۳۹] [۲۴]، از اختلاف بین زمان ارسال سیگنال توسط حسگر ارسال‌کننده و زمانی که سیگنال بازتاب شده توسط حسگر ارسال‌کننده دریافت می‌شود برای محاسبه فاصله بین حسگرهای همسایه استفاده می‌گردد و بنابراین این الگوریتم نیازمند همگام‌سازی بین حسگرها نمی‌باشد. مهمترین خطایی که در این الگوریتم وجود دارد مربوط به تاخیر بازتاب سیگنال دریافتی توسط حسگر دوم می‌باشد و به منظور رفع این خطا، میزان تاخیر در حسگر دوم محاسبه می‌گردد و به حسگر اول ارسال می‌شود تا از زمان بدست آمده در اندازه‌گیری کاسته شود.
۳-۲-۳- الگوریتم فانوس دریایی
در الگوریتم فانوس دریایی^[۴۰] [۲۴]، فاصله بین گیرنده و فرستنده نوری را با اندازه‌گیری دوره زمانی که گیرنده در پرتو ساکن است تخمین زده می‌شود. در این الگوریتم فرستنده Z به یک پرتو نوری موازی با پهنای ثابت b مجهز می‌باشد که این فرستنده در مبدا مستقر می‌باشد و این پرتو نور با سرعت زاویه‌ای نامعلوم w به دور فرستنده Z در حال چرخش می‌باشد. در این الگوریتم به منظور بدست آوردن میزان سرعت زاویه‌ای w از اختلاف زمانی بین لحظه زمانی که گیرنده نوری برای اولین بار پرتو را پیدا می‌کند و لحظه‌ای که برای دومین بار پرتوی نوری توسط گیرنده نوری تشخیص داده می‌شود استفاده می‌گردد و با توجه به شکل ۳-۱ می‌توان نشان داد که با بهره گرفتن از رابطه۳-۱ فاصله d که به فاصله بین گیرنده و فرستنده نوری اشاره دارد بدست آورده می‌شود.

مهمترین مزیت این روش این است که گیرنده نوری می‌تواند اندازه‌های کوچکی داشته باشد هرچند که فرستنده ممکن است بزرگ باشد ولی عیب این روش این است که خط دید بین گیرنده نوری و فرستنده باید مستقیم باشد.
شکل ۳-۱: الگوریتم فانوس دریایی[۲۴].