مقاله ردیابی اهداف متحرک مبتنی بر پیش بینی در شبکه های حسگر بی سیم

بخشی از مقاله

خلاصه

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

.1 مقدمه

ردیابی اهداف متحرک در شبکه های حسگر بیسیم از کاربردهای مهم شبکههای حسگر میباشد .[1] به علت محدودیتهای خاص شبکههای حسگر از نظر انرژی مصرفی، توان محاسباتی، حافظه گرههای حسگر و شعاع ارتباطی بین گرهها، همواره موازنهای میان میزان مصرف انرژی و دقت ردیابی وجود دارد .[11,14,15,16] ضمن اینکه روشهای ارائه شده برای ردیابی چندهدفی در شبکه های حسگر شامل تعداد زیادی انتقال پیغام بین گرهها می شوند که به سطح بالایی از همکاری آنها نیاز دارد و موجب افزایش مصرف انرژی در این شبکه ها میشود.

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

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

دستهای از الگوریتم های ردیابی هدف، الگوریتم های مبتنی بر پیشبینی هستند که در آنها، گرهها یک ساختار سلسله مراتبی را تشکیل میدهند[8] و .[9] هر گره سعی میکند که برای جلوگیری از انتقال دادههای قابل پیشبینی، یک مدل پیشبینی مناسب را بسازد. در نتیجه، مصرف توان هر گره کاهش یافته و افزایش طول عمر شبکههای حسگر بیسیم را به دنبال دارد. روشهای مبتنی بر پیشبینی متعددی تاکنون ارائه شده است همچون [2] HTTP، روش مبتنی بر نظریه بازی >3@ و >4@، [5] TCRP و روشهای ذکر شده در >12@ و .>13@ ولی نکته مهم استفاده از روشی است که در عین حال که پیچیدگی زیادی نداشته باشد بتواند محل آتی هدف را با دقت مناسبی تخمین بزند.

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

برای مقایسه نیز روش دیگری بنام استراتژی پیشبینی سلسلهمراتبی [6] انتخاب شده که تا حد زیادی مشابه اولی میباشد و از آنجا که در روش دوم، الگوریتم بازیابی مشخصی ارائه نشده، روشی نیز برای این منظور در آن ارائه شده است. در ادامهی ساختار مقاله، در بخش 2 خلاصهی الگوریتمهای DPT و HPS بیان میشود. در بخش 3، بهبودهای پیشنهادی روی این دو الگوریتم ارائه و در بخش 4 نتایج شبیهسازیها ذکر خواهند شد. در انتها و در بخش 5 نیز نتیجهگیری و کارهای آتی بیان میشوند.

.2 الگوریتمهای ردیابی DPT و HPS

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

در صورتی که سرخوشه نتواند سه گره، که فاصلهشان تا هدف کمتر از شعاع کوچک حسگری است، را پیدا کند، گستره و حسگری خود را افزایش میدهد و سعی میکند گرههای موجود در ناحیهای با شعاع R در اطراف خودش را جستجو کند. سرخوشه با استفاده از اطلاعات دریافتی از سه گره، سرعت و جهت حرکت هدف، محل بعدی آن را تخمین زده و به نزدیکترین سرخوشه بعدی که هدف به آن ناحیه میرود، اطلاعات را ارسال میکند. عملیات به همین ترتیب تکرار میشوند. علاوه بر این هر TD به سمت گره چاهک نیز فرستاده میشود تا پردازشهایی روی آن صورت گیرد. در این روش هر سرخوشه علاوه بر اطلاعات مکانی خود و گرههای خوشه خودش، نیاز به دانستن مکان سرخوشههای دیگر نیز دارد تا بتواند نزدیکترین خوشه را برای محل بعدی هدف پیدا کند.

در روش HPS گره های حسگر به دو گروه سرخوشه ها - CH - و گره های عادی - NN - تقسیم میشوند. فرض میشود شرخوشهها قادر به برقراری ارتباط با یکدیگر و ارسال دستورات/ پرس و جوها به گرههای عادی میباشند، در حالیکه گرههای عادی میتوانند مشاهدات را به سرخوشهها ارسال نمایند اما با دیگر گرههای عادی صحبت نمیکنند. خوشهها در دو مد کار میکنند: فعال و غیر فعال - بیکار - . خوشه زمانی از حالت غیر فعال به فعال جابجا میشود که رخداد هدف آشکار یا مسیر آتی پیش بینی شده توسط سرخوشه همسایه ناحیه پوشش اش را قطع کند. مدهای گرههای عادی در خوشه به فعال احتمالی و خواب تقسیم میشود. زمانی که خوشهای در حالت فعال باشد، به شیوهی متمرکز عمل میکند.

سرخوشه که رفتار کلی درون خوشه را مدیریت میکند، فعال احتمالی یا خواب را بر طبق مکان برآورد شده هدف، به گرههای عادی تخصیص میدهد. گرههای عادی که در مد فعال احتمالی عمل میکنند، دادهها را با احتمال p مورد ارزیابی قرار داده و با احتمال 1-p در هر دایره سنجش، وارد مد خواب میشوند. مقدار p بر طبق اهمیت هدف با هدف کاهش مصرف انرژی غیر ضروری اختصاص داده میشود.

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

.3 الگوریتم DPT توسعه یافته

از آنجا که روشهای مبتنی بر پیشبینی عمدتاً مبتنی بر خوشهبندی هستند، مفروضاتی در مورد گرهها و سرخوشهها لازم است درنظر گرفته شود که در توسعهی روش DPT نیز مورد استفاده واقع شدند. این فرضیات عبارتند از:

·    گرهها به دو نوع گره معمولی و سرخوشه تقسیم میشوند.

·    سرخوشهها دارای قدرت محاسباتی و انرژی بسیار بالایی میباشند

·    هر گره دارای شناسه منحصر به فرد است.

·    سرخوشه اطلاعات حسگرهای خوشه خود شامل - شناشه، زمان و مکان - را دارند.

·    سرخوشهها قادر به برقراری ارتباطات با یکدیگر هستند.

·    سرخوشهها قادر به برقراری ارتباط با گرهها و بلعکس میباشند.

·    گرهها قادر به برقراری ارتباطات با یکدیگر نیستند.

·    ارسال دادههای شبکه برای گره چاهک از طریق سرخوشه انجام میگیرد. باتوجه به فرضیات مذکور، الگوریتم DPT توسعه یافته شامل چهار مرحله زیر است:

·    استقرار و خوشهبندی

·    کشف هدف متحرک

·    ردیابی هدف متحرک

·    بازیابی هدف متحرک