در الگوریتم [۳۴]CDTA[23]، به منظور کمینه کردن رابطه بین مصرف انرژی و دقت رهگیری هدف، فرستنده یک مجموعه کمینه از حسگرها را بر اساس مسیر حرکت هدف در فاصله زمانی نمونهبرداری بیدار میکند و وظیفه رهگیری هدف را بین حسگرهای فعال، زمانبندی میکند به گونهای که هدف به صورت پیوسته قابل رهگیری باشد. همچنین در این الگوریتم به منظور کاهش مصرف انرژی، یک حد آستانهای، برای مدت زمان شناسایی هدف توسط حسگرهای فعال در نظر گرفته شده است و در صورتی که حسگر فعال در مدت زمان حد آستانه قادر به شناسایی کردن هدف نباشد آن حسگر حالت خود را به حالت خواب تغییر خواهد داد.
در این الگوریتم فرض گردیده است که دو نوع حسگر در شبکه موجود میباشد: حسگرهای اجرایی و حسگرهای انتشاردهنده. حسگرهای اجرایی حسگرهایی میباشند که در شبکه پخش گردیدهاند به گونهای که بتوانند کل شبکه را تحت پوشش خود قرار دهند و وظیفه شناسایی اهداف متحرک و ارسال اطلاعات هدف به حسگرهای انتشاردهنده را بر عهده دارند. حسگرهای انتشاردهنده، حسگرهایی هستند که نسبت به حسگرهای اجرایی از انرژی بیشتری برخوردار خواهند بود و وظایف زیر را بر عهده خواهند داشت:
برای دانلود متن کامل پایان نامه به سایت tinoz.ir مراجعه کنید.
ارسال اطلاعات رسیده از حسگرهای اجرایی به حسگر چاهک
تعیین مجموعه کمینه از حسگرهای اجرایی به منظور رهگیری اهداف متحرک
ارسال پیام اخطار به حسگرهای انتشاردهنده همسایههایش در هنگام خروج هدف از ناحیه مربعی شکل تحت رهبری آن
اجرای الگوریتم تصحیح خطا به منظور پیدا کردن موقعیت هدف در صورتی که حسگرهای اجرایی قادر به رهگیری هدف در فاصله زمانی نمونهبرداری نباشند.
در این الگوریتم به منظور رهگیری هدف از دو رویه رهگیری هدف و رویه انتخاب حسگرها استفاده گردیده است. رویه رهگیری هدف از چهار فاز تشکیل گردیده است که در زیر هر کدام از این فازها توضیح داده شده است.
فاز اول: در این فاز هنگامیکه هدف در خارج از شبکه قرار دارد، تمام حسگرهای اجرایی که بر روی یالی از ناحیه که هدف به آن یال نزدیکتر است، قرار دارند توسط حسگر چاهک بیدار میگردند
فاز دوم: در این فاز هر کدام از حسگرهای اجرایی که قادر به شناسایی کردن هدف باشند به حسگر انتشاردهنده مربوط به خود پیامی را ارسال میکنند. این پیام شامل شماره شناسایی حسگر اجرایی شناسایی کننده هدف، انرژی باقیمانده آن حسگر و اطلاعات بدست آمده از هدف توسط آن حسگر میباشد. هنگام دریافت این اطلاعات توسط حسگر انتشاردهنده، با توجه به اینکه هدف به صورت پیوسته در حال حرکت میباشد در هر فاصله زمانی نمونهبرداری توسط حسگر انتشاردهنده مربوطه، سه حسگر اجرایی توسط رویه انتخاب حسگرها انتخاب میگردند و این سه حسگر وظیفه رهگیری هدف را بر عهده خواهند داشت. تا زمانی که جهت حرکت هدف بدست آورده نشده است حسگرهای انتخابشده در فاصله زمانی قبل فعال میباشند تا هدف را شناسایی کنند. در این الگوریتم با توجه به اینکه روشن و خاموش کردن واحد ارتباطی حسگرها انرژی زیادی را مصرف خواهد کرد، حسگرهایی که توسط حسگر انتشاردهنده فعال گردیدهاند حالت خود را تغییر نمیدهند.
فاز سوم: در این فاز به بررسی رهگیری هدف از یک ناحیه به ناحیه دیگر پرداخته شده است. با توجه به اینکه هر کدام از حسگرهای انتشاردهنده علاوه بر حسگرهای درون ناحیه تحت نظارت خود با حسگرهای مرزی نواحی همسایههای خود در ارتباط میباشند، در صورتی که هدف توسط حسگرهای مرزی همسایههای حسگر انتشاردهنده فعال شناسایی گردید حسگر انتشاردهنده فعال موقعیت هدف را به حسگر انتشاردهندهای که هدف در ناحیه آن قرار دارد ارسال میکند. هنگامیکه حسگر انتشاردهندهای این پیام را دریافت کرد، در فاصله زمانی نمونهبرداری توسط رویه انتخاب حسگر، سه حسگر انتخاب میگردد و حسگر انتشاردهنده این پیام حالت خود را به حالت خواب تغییر خواهد داد. این سه حسگر انتخابشده توسط حسگر انتشاردهنده جاری حالت خود را به حالت فعال تغییر خواهند داد و وظیفه شناسایی هدف بر عهده این سه حسگر گذاشته میشود.
فاز چهارم: در این فاز به بررسی الگوریتم تصحیح خطا پرداخته شده است. در صورتی که حسگر انتشاردهنده فعال قادر به رهگیری هدف نباشد در ابتدا حسگر انتشاردهنده به تمام حسگرهای تحت نظارت خود پیامی را به صورت سیلآسا ارسال میکند تا در صورت وجود هدف در ناحیه تحت نظارت خود آن هدف شناسایی گردد. در صورتی که هدف در مرحله قبل شناسایی نگردید، حسگر چاهک تمام حسگرهای انتشاردهنده موجود در شبکه را فعال میکند تا در کل شبکه به جستجو هدف مورد نظر پرداخته شود و هدف شناسایی گردد.
۲-۶- نتیجهگیری
در این فصل به بررسی تحقیقات انجامشده در زمینه رهگیری هدف در شبکههای حسگر همه جهته پرداخته شده است. چهار گروه اصلی الگوریتمهای رهگیری هدف در شبکههای حسگر همه جهته، معرفیشدهاند و نمونههایی از هر کدام آنها بررسی شد. این چهار گروه اصلی عبارتند از: الگویتم های مبتنی بر پیام، الگوریتمهای مبتنی بر درخت، الگوریتمهای مبتنی بر پیشبینی و الگوریتمهای مبتنی بر خوشه. طبقهبندی ارائهشده در این فصل برای شناخت الگوریتم پیشنهادی در این پایاننامه مورد استفاده قرار گرفته است.
فصل سوم
مدلهای حرکتی
۳-۱- مقدمه
در بسیاری از کاربردهای شبکه های حسگر مانند رهگیری اهداف متحرک، کشف رویدادها و … لازم است که حسگرهای شبکه از مکان فیزیکی خود باخبر باشند. به دلیل اینکه حسگرها دارای انرژی محدودی میباشند و با توجه به اینکه سیستم GPS دارای هزینه بالایی میباشد، مجهز کردن تمام حسگرها به سیستمهایی نظیر GPS امکانپذیر نمیباشد. بنابراین ضرورت وجود الگوریتمهای مکانیابی در شبکههای حسگر احساس میگردد. در این الگوریتمها با بهره گرفتن از مکان دقیق تعداد کمی از حسگرها و معیارهای اندازهگیری نظیر فاصله و جهت، مکان حسگرها بدست میآیند که در ادامه هر کدام از این الگوریتمها توضیح داده خواهد شد. به منظور شبیهسازی و ارزیابی کارایی سیستم های بیسیم متحرک و الگوریتمها و پروتکلها، از مدلهای حرکتی استفاده میگردد. در عمل دو نوع مدل برای شبیهسازی سیستم های متحرک وجود دارد: اثر حرکت[۳۵] و مدلهای ترکیبی[۳۶]. در یک مدل ترکیبی، یک سری از معاملات ریاضی بیانگر مدل میگردند درحالیکه در مدل اثر حرکت که دارای دقت بالاتری نسبت به روش مدل ترکیبی میباشد، با بهره گرفتن از مکانهای حسگر متحرک و ارتباطات میان آن ها مدل بیان میگردد. به منظور شبیهسازی کامل یک پروتکل جدید برای یک شبکه بیسیم باید یک مدل حرکتی انتخاب شود که نمایانگر حسگرهای متحرکی باشند که انتظار میرود در این شبکه حرکت کنند و از خصوصیات یک مدل حرکتی این است که حدالمقدور به حرکات واقعی یک حسگر متحرک نزدیک باشد و تغییرات در سرعت و جهت باید در بازههای زمانی منطقی اتفاق بیفتد. مدلهای حرکتی نیز از دیدگاه زمانی- مکانی به سه دسته تقسیم میگردد: وابستگی زمانی،
وابستگی مکانی، محدودیت جغرافیایی. مدلهای وابستگی زمانی، مدلهایی هستند که حرکت یک حسگر از تاریخچه حرکتی خود آن حسگر تاثیر میپذیرد. مدلهای وابستگی مکانی، مدلهایی هستند که حسگرها با یک وابستگی فضایی حرکت میکند و مدلهای محدودیت جغرافیایی مدلهایی هستند که حسگرها در محدوده جغرافیایی خاصی مانند خیابانها و آزادراهها و … حرکت میکند.
۳-۲- مکانیابی در شبکههای حسگر
در الگوریتمهای رهگیری هدف لازم است که حسگرها، مکان خود را به صورت فیزیکی بدانند و همچنین مجهز کردن تمام حسگرها به سیستمهایی نظیر [۳۷]GPS به دلیل پارهای محدودیتهایی چون عدم عملکرد GPS در محیطهای درونی، هزینه بالای این کار و اندازه و توان محدود حسگرها اصلا مقرون به صرفه نیست. بنابراین الگوریتمهای مکانیابی برای شبکههای حسگر که وظیفه رهگیری هدف را بر عهده دارند ضروری به نظر میرسد. این الگوریتمها با بهره گرفتن از مکان دقیق تعداد کمی از حسگرها و معیارهای اندازهی مابین حسگرها، مانند فاصله و جهت، مکان حسگرها را به دست میآورند. در زیر انواع الگوریتم مکانیابی در شبکههای حسگر ارائه گردیده است.
۳-۲-۱- الگوریتم زمان انتشار یک طرفه
در الگوریتم زمان انتشار یک طرفه[۳۸] [۲۴]، از اختلاف بین زمان ارسال سیگنال در فرستنده و زمان دریافت سیگنال در گیرنده برای محاسبه فاصله بین حسگرهای همسایه استفاده میگردد و در نتیجه این الگوریتم نیازمند این است که حسگرهای گیرنده و فرستنده با یکدیگر همگام باشند. این نیاز موجب افزایش قیمت حسگرها با توجه به تقاضای ساعتهای دقیقتر و یا افزایش پیچیدگی شبکهی حسگر با توجه به تقاضای روشهای همگامسازی سطح بالا میشود.
۳-۲-۲- الگوریتم زمان انتشار رفت و برگشت
در الگوریتم زمان انتشار رفت و برگشت[۳۹] [۲۴]، از اختلاف بین زمان ارسال سیگنال توسط حسگر ارسالکننده و زمانی که سیگنال بازتاب شده توسط حسگر ارسالکننده دریافت میشود برای محاسبه فاصله بین حسگرهای همسایه استفاده میگردد و بنابراین این الگوریتم نیازمند همگامسازی بین حسگرها نمیباشد. مهمترین خطایی که در این الگوریتم وجود دارد مربوط به تاخیر بازتاب سیگنال دریافتی توسط حسگر دوم میباشد و به منظور رفع این خطا، میزان تاخیر در حسگر دوم محاسبه میگردد و به حسگر اول ارسال میشود تا از زمان بدست آمده در اندازهگیری کاسته شود.
۳-۲-۳- الگوریتم فانوس دریایی
در الگوریتم فانوس دریایی[۴۰] [۲۴]، فاصله بین گیرنده و فرستنده نوری را با اندازهگیری دوره زمانی که گیرنده در پرتو ساکن است تخمین زده میشود. در این الگوریتم فرستنده Z به یک پرتو نوری موازی با پهنای ثابت b مجهز میباشد که این فرستنده در مبدا مستقر میباشد و این پرتو نور با سرعت زاویهای نامعلوم w به دور فرستنده Z در حال چرخش میباشد. در این الگوریتم به منظور بدست آوردن میزان سرعت زاویهای w از اختلاف زمانی بین لحظه زمانی که گیرنده نوری برای اولین بار پرتو را پیدا میکند و لحظهای که برای دومین بار پرتوی نوری توسط گیرنده نوری تشخیص داده میشود استفاده میگردد و با توجه به شکل ۳-۱ میتوان نشان داد که با بهره گرفتن از رابطه۳-۱ فاصله d که به فاصله بین گیرنده و فرستنده نوری اشاره دارد بدست آورده میشود.
(۳-۱)
مهمترین مزیت این روش این است که گیرنده نوری میتواند اندازههای کوچکی داشته باشد هرچند که فرستنده ممکن است بزرگ باشد ولی عیب این روش این است که خط دید بین گیرنده نوری و فرستنده باید مستقیم باشد.
شکل ۳-۱: الگوریتم فانوس دریایی[۲۴].
۳-۲-۴- الگوریتم تخمین فاصله از طریق اندازهگیری قدرت سیگنال دریافتی
در الگوریتم تخمین فاصله از طریق اندازهگیری قدرت سیگنال [۲۴]، فاصله بین حسگرهای همسایه را با اندازهگیری قدرت سیگنال دریافتی تخمین میزنند که این روش بر مبنای ویژگی استاندارد قدرت سیگنال دریافتی[۴۱] (RSSI) که در بسیاری از وسایل بیسیم یافت میشود، استوار میباشد زیرا نیاز به هیچ سختافزار اضافی ندارد و بعید است که اثر مهمی روی مصرف انرژی، اندازه حسگر و قیمت آن داشته باشد. با توجه به اینکه در فضای آزاد قدرت سیگنال دریافتی(RSS) با معکوس مجذور فاصله بین گیرنده و فرستنده متناسب میباشد میتوان توان دریافتی(Pr(d)) را از رابطه۳-۲ بدست آورد.
(۳-۲)
در رابطه۳-۲، Pt اشاره به توان فرستنده، Gt و Gr به ترتیب اشاره به بهرهی آنتن فرستنده و گیرنده و اشاره به طول موج سیگنال ارسالی بر حسب متر دارند. هرچند که مدل فضای آزاد به هر حال ایدهآل نیست و انتشار سیگنال با بازتاب، انکسار و تفریق تحت تاثیر قرار میگیرد، اما این موضوع به تجربه پذیرفته شده است که Pr(d) مربوط به قدرت سیگنال دریافتی در فاصله d از فرستنده در یک مکان خاص به صورت یک توزیع تصادفی lognormal میباشد که مقدار میانگین این توزیع وابسته به مکان میباشد. بنابراین Pr(d) را میتوان از رابطه۳-۳ بدست آورد.
(۳-۳)
در رابطه۳-۳، P0(d0) اشاره به توان مرجع شناختهشده بر مبنای دسیبل- میلی وات(dbm) در فاصله مرجع d0 از فرستنده دارد. np اشاره به افت توان در مسیر دارد. این پارامتر وابسته به محیط میباشد و نرخی را که قدرت سیگنال دریافتی با فاصله کم میگردد را محاسبه میکند. اشاره به متغییر تصادفی گوسی با میانگین صفر و انحراف معیار دارد که به منظور محاسبه اثر shadowing به کار گرفته شده است.
با بهره گرفتن از رابطه۳-۳ و قدرت سیگنال دریافتی بین فرستنده و گیرندهای که در فاصله dij از فرستنده قرار دارد، فاصله بین فرستنده و گیرنده به وسیله رابطه۳-۴ بدست آورده میگردد. در این رابطه Pij اشاره به قدرت سیگنال دریافتی بین فرستنده و گیرنده دارد.
(۳-۴)
۳-۲-۵- الگوریتم مکانیابی به وسیله GPS