در این قسمت الگوریتم پیشنهادی PDTA(Prediction Based Dynamic Tracking Algorithm) شرح داده می‌شود که به منظور بالا بردن طول عمر شبکه و رهگیری مفید اهداف متحرک طراحی گردیده است. از مزایای این الگوریتم می‌توان به رهگیری چندین هدف به صورت همزمان، مقاوم بودن آن در برابر خطاهای احتمالی حسگرها و شناسایی مجدد هدف گمشده به وسیله رویه تصحیح خطا اشاره کرد. در الگوریتم PDTA به دلیل اینکه هر کدام از حسگرها با توجه به اطلاعات خود و مستقل از حسگرهای دیگر مسیر حرکت هدف را تشخیص می­ دهند به این دلیل الگوریتم PDTA با توجه به طبقه‌بندی‌های ارائه‌شده در فصل دوم در دسته الگوریتم‌های توزیع‌شده‌ای قرار می‌گیرد که در آنها خوشه‌بندی اصلی­ترین راهکار برای رهگیری هدف است. دیاگرام کلی الگوریتم PDTA در شکل۵-۱۰ نشان داده شده است. همان طور که در شکل۵-۱۰ مشاهده می­گردد الگوریتم PDTA دارای دو بخش کلی رویه خوشه‌بندی و رویه رهگیری هدف می­باشد.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

شکل۵-۱۰: دیاگرام کلی الگوریتم PDTA
الگوریتم PDTA از یک طرح خوشه‌بندی پویا به منظور خوشه‌بندی حسگرهای زنده استفاده می‌کند تا به دلیل مدیریت بهتر منابع، مصرف انرژی کاهش یابد و در نتیجه مدت زمانی که شبکه قادر به رهگیری اهداف متحرک است، افزایش می­یابد. دیاگرام الگوریتم خوشه‌بندی در شکل۵-۱۱ نشان داده شده است.

شکل۵-۱۱: دیاگرام رویه خوشه‌بندی
رویه رهگیری هدف در الگوریتم PDTA به دو بخش رویه رهگیری هدف توسط حسگرهای عضو خوشه و حسگرهای سرخوشه تقسیم می‌گردد که رویه رهگیری هدف توسط حسگرهای سرخوشه به سه بخش انتخاب حسگرهای شایسته، پیش‌بینی موقعیت آینده هدف و تصحیح خطای گم شدن هدف نیز تقسیم گردیده است. این روند در شکل۵-۱۲ نشان داده شده است.

شکل۵-۱۲: دیاگرام رویه رهگیری هدف
۵-۳-۱- رویه خوشه‌بندی
در الگوریتم PDTA شبکه به صورت یک گراف G=(V,E) مدل گردیده است که در این گراف دو حسگر توسط یک یال به یکدیگر متصل می‌گردند اگر و تنها اگر این دو حسگر توانایی ارتباط با یکدیگر را داشته باشند. در این رویه همان طور که ذکر شد ابتدا تمامی حسگرها در حالت خوابیده بسر می‌برند. به منظور رهگیری اهداف متحرک از رویه خوشه‌بندی پویایی استفاده گردیده است که حسگرها توسط الگوریتم PDTA بهتر مدیریت می­گردند و بدین ترتیب انرژی کمتری مصرف خواهد گردید. در این رویه خوشه‌بندی هر کدام از خوشه‌ها شامل موارد زیر می‌باشند:
برد خوشه^[۷۴]: میزان فضایی که توسط حسگرهای درون خوشه پوشش داده می‌شود.
شعاع خوشه^[۷۵]: حداکثر فاصله بر اساس تعداد یال، بین حسگرهای عضو خوشه تا حسگر سرخوشه. به منظور ساده­سازی شعاع خوشه را با k به آن اشاره می‌شود.
درجه حسگر^[۷۶]: تعداد حسگرهایی که همسایه یک حسگر می‌باشند. منظور از همسایه حسگرهایی می‌باشند که در فاصله یک یالی تا آن حسگر قرار دارند.
در رویه خوشه‌بندی پیشنهادی هر حسگر در شبکه به صورت مستقل از حسگرهای دیگر تصمیم‌گیری را انجام می­ دهند و بنابراین رویه خوشه‌بندی پیشنهادی جزء الگوریتم‌های توزیع‌شده در نظر گرفته می­ شود. در رویه­های خوشه‌بندی هر کدام از حسگرها دارای حالت عضو خوشه(CM) و یا حالت سرخوشه(CH) می‌باشند. در رویه خوشه‌بندی پیشنهادی در ابتدا فرض می‌گردد که حالت همه حسگرها حالت عضو سرخوشه است و هر حسگر با احتمال P می ­تواند به عنوان حسگر سرخوشه انتخاب گردد. مقدار P برابر با نسبت تعداد سرخوشه‌ها به تعداد کل حسگرها در نظر گرفته می‌شود که این مقدار با اندازه شبکه رابطه مستقیم دارد. هر حسگر مستقل از حسگرهای دیگر باید تصمیم بگیرد که آیا می‌تواند حالت خود را به سرخوشه تغییر دهد و یا خیر. بدین منظور هر کدام از حسگرها یک عدد تصادفی r بین ۰ تا ۱ تولید می‌کنند و در صورتی که مقدار تولیدشده از مقدار P کمتر باشد حالت خود را به عنوان سرخوشه تغییر می‌دهد ولی در صورتی که مقدار تصادفی تولیدشده از مقدار P بیشتر باشد حالت خود را تغییر نداده و در همان حالت عضو خوشه باقی می‌ماند. در مرحله بعد هر حسگری که سرخوشه گردیده است، زمان­سنجی را راه ­اندازی می‌کند و بعد از راه ­اندازی زمان­سنج پیام ADV را به تمام حسگرهایی که در فاصله k یالی^[۷۷] خود قرار دارند به صورت سیل‌آسا ارسال می‌کند. بدین منظور حسگر سرخوشه به حسگرهای همسایه خود پیام ADV را ارسال می­ کند. هنگامی‌که حسگری پیام ADV را دریافت کرد در جدول سرخوشه خود، شماره شناسایی حسگر سرخوشه را جستجو می­ کند. در صورت عدم وجود شماره شناسایی حسگر سرخوشه اطلاعات HC، شماره شناسایی حسگر و شماره شناسایی حسگر ارسال‌کننده پیام ADV را در جدول سرخوشه خود ذخیره می­ کند. در غیر این صورت فیلد HC در جدول سرخوشه با فیلد HC پیام ADV مقایسه می­گردد. در صورت بیشتر بودن فیلد HC جدول سرخوشه، اطلاعات جدید HC، شماره شناسایی حسگر سرخوشه و شماره شناسایی حسگر ارسال‌کننده پیام جایگزین اطلاعات قبلی در جدول سرخوشه می­گردد. بنابراین کوتاه‌ترین مسیر تا حسگر سرخوشه به عنوان مسیر ارتباطی حسگر تا سرخوشه انتخاب می­گردد. این روند در شکل۵-۱۳ نشان داده شده است.

شکل۵-۱۳: روند اجرای ارسال پیام ADV در رویه خوشه­بندی
بعد از اینکه تمام حسگرهایی که در فاصله k یالی تا حسگرهای سرخوشه قرار دارند پیام ADV را دریافت کردند، در صورتی که حسگری وجود داشته باشد که پیام ADV سرخوشه‌ای را دریافت نکرده باشد حالت خود را به حالت سرخوشه تغییر می‌دهد و روند مرحله قبل تکرار می­گردد. بعد از اتمام مرحله قبل تمامی حسگرها دارای حالت سرخوشه و یا حالت عضو خوشه می‌باشند. حسگرهایی که دارای حالت عضو خوشه می‌باشند، خود را به عضویت یک خوشه در می‌آورند. بدین منظور حسگرهای حالت عضو سرخوشه با توجه به اطلاعات بدست آمده توسط جدول سرخوشه، حسگر سرخوشه­ای که به آن حسگر نزدیک‌تر است را به عنوان حسگر سرخوشه خود انتخاب می‌کند و پیام JREQ را به صورت unicast به حسگر سرخوشه انتخاب‌شده ارسال می‌کند. بدین منظور، بعد از انتخاب مناسب­ترین حسگر سرخوشه، پیام JREQ توسط حسگر ارسال‌کننده پیام JREQ به حسگرهای همسایه ارسال می­گردد. زمانی که پیام JREQ توسط حسگری دریافت گردید، آن حسگر پیام JREQ دریافت شده را به حسگر همسایه خود ارسال می‌کند و این روند ادامه می­یابد تا پیام JREQ به سرخوشه مربوطه تحویل داده شود. شماره شناسایی حسگر همسایه برابر با فیلد SID رکوردی از جدول سرخوشه می­باشد که فیلد CHID آن با شماره شناسایی مناسب­ترین حسگر سرخوشه برابر می­باشد. هر سرخوشه به منظور ذخیره اطلاعات حسگرهای سرخوشه خوشه‌های مجاورش بعد از دریافت پیام JREQ توسط “حسگرهای مرزی بین خوشه‌ها"، شناسه “حسگرهای مرزی بین خوشه” را در جدول AC-Table ذخیره می‌کنند. همچنین به منظور ذخیره اطلاعات حسگرهای عضو اطلاعات حسگرهای ایجادکننده پیام JREQ را در جدول CM-table خود ذخیره می‌کند. دیاگرام حالت و شبه کد رویه خوشه‌بندی را به ترتیب در شکل‌هایشکل۵-۱۴و شکل۵-۱۵ نشان داده شده است.

شکل۵-۱۴: ماشین حالت نشان‌دهنده سازوکار خوشه‌بندی الگوریتم پیشنهادی
در جدول ۵-۱رویدادهای دریافتی و صادره و حالت بعدی به تفکیک حالات نشان داده شده است.
جدول ۵-۱: رویدادهای بین حالات و حالات بعدی در هر یک از حالات