مقاله روشی جدید برای ردیابی هدف در شبکه های حسگر بی سیم با رویکرد بهینه سازی مصرف انرژی

بخشی از مقاله

چکیده

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

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

-1 مقدمه

شبکههای حسگر بی سیم از تعداد زیادی گره با قابلیتهای محدود حسگری، پردازشی و برقراری ارتباط بی سیم تشکیل شده اند. ویژگی مهم این گرهها، محدود بودن منابع انرژی است که باعث میشود گرهها و لذا شبکهها عمر مشخصی داشته باشند. علاوه بر این، از نظر پردازشی و گستره ارتباط رادیویی، نسبت به شبکههای موردی، نیز محدودیت بیشتری دارند .[1] شبکههای حسگر بی سیم،صولاًا برای نظارت بر محیطهای گسترده شامل پدیدههای مشخص و نیز ردیابی هدفهای متحرک به کار میروند.

همانطور که اشاره شد، ردیابی هدف یکی از چالشهای مهم در شبکههای حسگر بی سیم است. روش های مختلفی برای ردیابی اهداف با در نظر گرفتن معیارهای متنوعی مانند مقیاسپذیری، سربارهای ارتباطی، مصرف انرژی و دقت ردیابی هدف مورد بررسی قرار گرفتهاند .[2] در یک دستهبندی کلی، بیهاتی و همکارانش روشهای ردیابی هدف را به روشهای مبتنی بر خوشهبندی، مبتنی بر درخت - درختی - ، مبتنی بر پیامهای Mobicast، مبتنی بر پیش بینی و روشهای ترکیبی طبقهبندی کردهاند .[3]

در الگوریتمهای ردیابی مبتنی بر پیش بینی، موقعیت بعدی هدف با توجه به سرعت و مسیر حرکت فعلی - اخیر - هدف پیش بینی میشود . بر این اساس گرههای نواحی دیگر،که عمدتاً ناحیههای همسایه هستند و احتمال رفتن هدف به آنها بیشتر است، پیش از رسیدن هدف به آن ناحیه فعال میشوند و پساز عبور هدف از آن ناحیه مجدداً این گرهها به حالت خواب میروند . حالت خواب در این روشها حالتی است که در آن حسگر هیچ هدفی را نه دنبال میکند و نه حس میکند و لذا تمام اجزای حسگری آن خاموش میشوند، تنها قسمت رادیویی حسگر در حالت Idle قرار گرفته و منتظر سیگنالی از طرف دیگر گرهها میماند تا دوباره به ردیابی و دیدهبانی اهداف بپردازد .[4]

همچنین دیگر گرهها که در مسیر حرکت هدف قرار نمی گیرند نیز در حالت خواب نگهداشته میشوند که در نتیجه مصرف انرژی هر گره کاهش و طول عمر شبکه افزایش می یابد . یکی از چالشهای پیش روی الگوریتمهای مبتنی بر پیشبینی، فعال شدن تعداد زیادی از گرهها در فرایند اجرای آن است .[5] دلیل این امر آن است که چون محدوده مکان قرارگیری هدف در موقیت بعدی اش بر اساس پیشبینی مشخص میشود، این مکان محدودهی بزرگی را میتواند شامل شود که دربرگیرندهی تعداد زیادی از گرههای حسگر است. این در حالی است که با توجه به جهتگیری حرکت هدف، فعال شدن بسیاری از این گرهها ضروری نیست.

سیستم ردیابی هدف در شبکهای حسگر بی سیم معمولاً شامل سه گام میشود: تشخیص هدف، مکانیابی هدف، پیش بینی و اعلام مکان جدید. در فاز اول گرههای انتخاب شده، فعال میشوند. واضح است که تعداد بیشتر گرههای فعال در اطراف هدف دقت ردیابی بهتری را فراهم می-کند، اما فعال کردن گرههای حسگر، انرژی بر است. بنابراین، انتخاب حداقل تعداد گرههای لازم برای ردیابی هدف مد نظر است تا گرههای دیگر، جهت کاهش مصرف انرژی و در نتیجه افزایش طول عمر شبکه، در حالت خواب باشند. استراتژی کارایی بالای انرژی، یکی از مهمترین جنبههای پروتکلهای ردیابی هدف است. چگونگی ایجاد توازن بین کیفیت ردیابی هدف و مصرف انرژی شبکه به یک موضوع مورد توجه در تحقیقات تبدیل شده است. جهت کاهش مصرف انرژی، دادههای رد و بدل شده، تکرار ارتباطات و تعداد گرههای درگیر در ردیابی را با استفاده از پیش بینی کم خواهیم کرد.

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

با تعیین سقف مشخصی برای سرعت حرکت هدف و با این فرض که حرکت هدف در طول بازه تصمیمگیری برای انتخاب گرههای فعال بعدی تغییر نخواهد کرد، میتوان نشان داد - در بخش 2-3 ارائه شده است - که این ناحیه در فضای مشترک تشکیل شده از دامنه ارتباطی دو نزدیک ترین گره به هدف قرار میگیرد . بر این اساس، الگوریتمی را پیشنهاد دادهایم که با استفاده از نتایج این استدلال سعی نماید تعداد گره های فعال شده برای ردیابی هدف در بازه ی زمانی بعدی را تا حد ممکن کاهش دهد. بدیهی است که کاهش گرههای فعال در ردیابی تا جایی که به کیفیت ردیابی لطمهای وارد نیاورد، باعث افزایش مفید طول عمر شبکه خواهد شد. در ادامه ی این مقاله در بخش بعد، روشهای پیشین ردیابی هدف را بررسی میکنیم. در دو بخش بعدی به توضیح طرح پیشنهادی و ارزیابی کارآیی آن میپردازیم و در انتها نتیجه-گیری ارائه می شود.

-2 کارهای پیشین

دستهبندی روشهای ردیابی شبکهای، میتواند مبتنی بر خوشه و یا مبتنی بر درخت انجام شود. هر کدام از این روشها میتواند با استفاده از پیشبینی و یا بدون آن پیادهسازی شود. روشهای مبتنی بر خوشه به سه دسته ایستا1، پویا2 و پیوندی3 - ایستا-پویا - تقسیم میشوند. با ترکیب هر دستهبندی با پیشبینی، در صورت درست بودن پیشبینی مکان بعدی هدف، به میزان قابل توجهی در مصرف انرژی صرفهجویی خواهد شد. در صورت نادرست بودن پیشبینی، احتمال گم شدن هدف افزایش یافته و الگوریتمهای بازیابی1 هدف موردنیاز خواهد بود .[6]

از دیدگاه نحوه پردازش و شکلگیری ساختار شبکه نیز الگوریتمها را میتوان به دو دسته توزیعشده و متمرکز تقسیم کرد. در روش متمرکز، یک گره - یا یک موجودیت مرکزی - اطلاعاتی از تمام شبکه به دست میآورد - با ارسال اطلاعات از تمام گرهها به این گره مرکزی - و سپس بر اساس این اطلاعات سراسری، ساختار بهینه - درخت یا خوشه - تشکیل میشود. در روش توزیعشده، گرهها با تبادل اطلاعات با همسایههای خود، ساختار مورد نظر را برای ردیابی تشکیل میدهند. هر چند که ممکن است ساختار ایجاد شده در روشهای توزیعشده بهینه نباشد، با این حال استفاده از اطلاعات محلی، سربار تبادل اطلاعات و مصرف انرژی تا حد زیادی کاهش مییابد، به گونهای کهعملاً در پیادهسازی یک روش ردیابی، روشهای متمرکز به صرفه نیستند .[7]

روش ردیابی بر اساس فعالسازی ساده [8] NA2 - یا ارتباط مستقیم - یک روش بسیار ساده است برای اینکه همواره تمام گرهها در حالت ردیابی هستند. هر گره اندازه گیری محلی را به گرهی چاهک یا ایستگاه پایه ارسال میکند. سپس ایستگاه پایه وضعیت هدف را طبق اندازهگیریهای محلی رسیده، تخمین زده و پیشبینی میکند. از آنجا که بهترین نتایج ردیابی از این روش حاصل میشود، پایهای برای مقایسه است. اما، این روش بدترین کارآیی انرژی را نشان میدهد و سربار سنگینی را صرف ارتباطات و محاسبات بر روی ایستگاه پایه میکند.

روش ارائه شده در [9] یک الگوریتم ردیابی بر اساس پیشبینی ارائه داده است که در آن از بین گرههای ردیاب و شناسایی کنندهی هدف، دو گرهی نزدیک به هدف مسئول بیدار کردن سایر حسگرها هستند. در این روش به جای پیشبینی مکان دقیق هدف، ناحیهای که هدف در آن قرار دارد فعال میشود. این روش بر طبق یک برهان ریاضی اثبات میکند که هدف در بازهی زمانی بعدی با یک سرعت محدود، در ناحیهی مشترک دو نزدیک ترین گره به هدف قرار میگیرد. این موضوع در برخی حالات ممکن است صدق نکند.

روش ارائه شده در [10] یک روش ردیابی هدف بر پایهی خوشه بندی است. در این روش هر سر خوشه ای که هدف را شناسایی میکند برای ردیابی هدف سه گره از اعضای خودش را انتخاب میکند که نزدیک گره به هدف باشند و همچنین از نظر انرژی محدودیتی نداشته باشند. ضعف عمدهی این روش کم بودن بیش از حد گرههای ردیاب و همچنین ایستا بودن خوشههاست. در مقاله [11] جهت ردیابی هدف تکنیک بیدار یا خواب بودن گرهها به منظور کاهش مصرف انرژی به کار گرفته شده است.

از آنجا که جهت حرکت اهدافی مانند انسان یا حیوانات چموش مشخص نیست در نتیجه تکنیکهای پیشبینی هدف در این موارد نتایج مطلوبی را حاصل نمیکنند. در این مقاله مدل ادراک شناسایی دودویی استفاده میشود که این یعنی حسگر هر بار که هدف در ناحیهی ادراک - sensing scope - آن وارد شود، آن را شناسایی میکند. در این روش تعدادی از گرهها هدف را هنگامی که وارد ناحیهی ادراکشان میشود شناسایی میکنند، آنگاه پیام بیدارباش به همسایگان گام اول خود ارسال میکنند. گرههای در این ناحیه جهت تشخیص هدف بیدار میشوند، - این الگوریتم اصطلاحا DSA نامیده میشود. این روش یکی از روشهای معتبر در زمینه ردیابی هدف است - . در ضمن این گرهها سینکهای اطراف خود را جهت حس کردن فعال میکنند.

-3 روش پیشنهادی ردیابی هدف

-1-3 فرضیات و مدل

در مدلی که راجع به آن بحث خواهیم کرد، فرض کردهایم که دامنهی ارتباطی گرههای حسگر Rc و دامنهی حس کردن گرهها Rs است - شکل. - 1 لازم به یادآوری است که گرههای حسگر برای ارتباط با سایر گرهها در شبکه حسگر بی سیم از تجهیزات مخابراتی با بردی محدود استفاده میکنند . برد محدود این گرهها به چند عامل بستگی دارد. یکی از این عوامل ظاهر فیزیکی گرهها است که باعث میشود نتوان تجهیزاتی که از نظر حجم ظاهری بزرگ هستند را بر روی کیت کوچک گره تعبیه کرد.