شکل ۳-۸: حرکت سه گره متحرک بر اساس مدل حرکتی رشته­ای [۲۶].
بعد از تغییر راستای قرار گرفتن گره‌ها، سرگروه بر اساس رابطه۳-۶ موقعیت خود را تغییر خواهد داد و در نتیجه گره‌های دیگر نیز موقعیت خود را به گونه‌ای تغییر می‌دهند که گره‌ها بر روی راستای مورد نظر قرار می­‌گیرند. در رابطه۳-۱۵، Advance_vector اشاره به میزان تغییر مکان سرگروه دارد.

 

 

 

 

 

 

 

(۳-۱۵)

۳-۶-۴- مدل حرکتی ردیفی

در مدل ردیفی، اعضای گروه در یک ردیف با سرگروه حرکت می‌کنند و این ردیف شامل سرگروه نیز است. در این مدل اعضای گروه و سرگروه در تمام اوقات حرکت گروه، تقریبا با هم در یک ردیف حرکت می‌کنند.

 

۳-۷- نتیجه‌گیری

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

 

۴-۱- مقدمه

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

 

برای دانلود متن کامل پایان نامه به سایت zusa.ir مراجعه نمایید.

 

۴-۲- الگوریتم خوشه‌بندی توزیع‌شده به صورت هم پوشانی:

در الگوریتم خوشه‌بندی توزیع‌شده به صورت هم پوشانی[۵۶](KOCA)[29]، هدف تقسیم‌بندی حسگرهای شبکه به چندین خوشه است به گونه‌ای که خوشه‌ها با یکدیگر اشتراک داشته باشند. از مزیت‌های این‌گونه خوشه‌بندی می‌توان به مقاوم بودن شبکه در برابر خطاهای احتمالی حسگرها و مصرف بهینه انرژی اشاره داشت. با توجه به اینکه این الگوریتم مبنای خوشه‌بندی در الگوریتم پیشنهادی است به شرح آن می‌پردازیم.
در مدل شبکه این الگویتم فرض گردیده است که هر کدام از حسگرها دارای یک زمان‌سنج می‌باشند. در این الگوریتم هنگامی‌که پیام خوشه‌بندی توسط حسگرها دریافت گردید، هر حسگر زمان‌سنج خود را راه‌اندازی می‌کنند. این زمان‌سنج حداکثر زمانی را نشان می‌دهد که طول می‌کشد تا یک پیام توسط حسگری با فاصله k یال تا حسگر مورد نظر، دریافت گردد. این الگوریتم به منظور خوشه‌بندی حسگرها از یک الگوریتم سه مرحله‌ای استفاده‌شده است که در ادامه توضیح داده می‌شود.
مرحله اول:
به منظور انتخاب حسگرهای سرخوشه به صورت توزیع‌شده، فرض گردیده است که هر حسگر خودش را با احتمال P به عنوان حسگر سرخوشه انتخاب می‌گردد. هر کدام از حسگرهای سرخوشه، پیام CH-ADVERTISE را به حسگرهایی که در برد نرمال آن قرار دارند ارسال می‌کند و این پیام به صورت همگانی به تمام حسگرهایی که تا حسگر سرخوشه مربوطه حداکثر k یال فاصله دارند ارسال می‌گردد. هنگامی‌که حسگری پیام CH-ADVERTISE را دریافت کرد شماره شناسایی سرخوشه و شماره شناسایی حسگر ارسال‌کننده این پیام را در جدول CH-Table خود ذخیره می‌کند و زمان‌سنج خود را نیز متوقف می‌کند.
مرحله دوم:
در صورتی که حسگری تایمر آن خاتمه یافته باشد و پیام CH-ADVERTISE را دریافت نکرده باشد، خود را به عنوان حسگر سرخوشه معرفی می‌کند، زمان‌سنج خود را مجددا راه‌اندازی می‌کند و پیام CH-ADVERTISE را برای حسگرهایی که تا k یال فاصله دارند، به صورت همگانی ارسال می‌کند.
مرحله سوم:
با توجه به اینکه حسگرهای غیر از حسگرهای سرخوشه در مراحل قبلی عضویت خود را به حسگرهای سرخوشه اعلام نکرده‌اند، بعد از اتمام مرحله دوم حسگرهای غیر از حسگرهای سرخوشه که پیام CH-ADVERTISE را دریافت کرده‌اند با توجه به جدول CH-Table خود به تمام حسگرهای سرخوشه‌ای که پیام CH-ADVERTISE را برای آن ارسال کرده‌اند، پیام عضویت(JREQ[57]) را به صورت Unicast ارسال می‌کنند تا حسگرهای سرخوشه را از عضویت خود باخبر کنند. بنابراین در صورتی که حسگری از دو سرخوشه پیام CH-ADVETISE را دریافت کرده باشد در این روش هر کدام از آنها را به عنوان نود سرخوشه خود انتخاب می‌کند. پیام عضویت شامل فیلدهای حسگرهای سرخوشه‌ای است که برای آن حسگر پیام CH-ADVERTISE ارسال کرده ­اند، شماره شناسایی حسگر ارسال‌کننده پیام، شماره شناسایی حسگر سرخوشه می‌باشد. بنابراین حسگر سرخوشه با دریافت این پیام، حسگرهای سرخوشه مجاورش را شناسایی می‌کند. این روند در شکل ۴-۱ نشان داده شده است.

شکل ۴-۱:دیاگرام حالت الگوریتم KOCA[29].

 

۴-۳- الگوریتم رهگیری اهداف سریع:

در الگوریتم رهگیری اهداف سریع[۵۸][۱۸]، هدف کاهش احتمال گم شدن هدف و افزایش دقت رهگیری هدف متحرک می‌باشد تا الگوریتم مورد نظر قادر به رهگیری اهداف خیلی سریع در شبکه باشد. این الگوریتم شامل ۴بخش رویه انتخاب رهبر[۵۹]، رویه شکل‌گیری اولیه خوشه و موقعیت‌یابی[۶۰] ، رویه شکل‌گیری مجدد خوشه و تعیین مسیر حرکت هدف[۶۱] و در نهایت رویه رهگیری هدف[۶۲] می‌باشد که در ادامه این بخش‌ها توضیح داده شده است.

 

 

رویه انتخاب رهبر:

هنگامی‌که هدف وارد شبکه می‌گردد حسگرهای فعالی که نزدیک هدف قرار دارند، هدف را شناسایی می‌کنند و الگوریتم انتخاب رهبر را فراخوانی می‌کنند. در فاز اول این الگوریتم هر حسگر i که هدف را تشخیص داد با توجه به قدرت سیگنال دریافتی از هدف یک شمارنده را راه‌اندازی می‌کند به گونه‌ای که هر چقدر قدر سیگنال دریافتی بیشتر باشد مقدار اولیه شمارنده کمتر خواهد بود. بنابراین حسگری که شمارنده آن زودتر از حسگرهای دیگر به پایان برسد، حسگری است که به هدف نزدیک‌تر است. در این الگوریتم حسگر i که شمارنده آن به اتمام رسیده است و پیام “CANDIDATE” توسط آن حسگر دریافت نگردیده است حالت خود را به سرخوشه تغییر می‌دهد و پیام “CANDIDATE” را به تمام همسایه‌های خود ارسال می‌کند. پیام “CANDIDATE” ارسالی توسط حسگر i شامل قدرت سیگنال دریافتی از هدف و شماره شناسایی حسگر i می‌باشد. حسگرهایی که پیام “CANDIDATE” را دریافت کرده‌اند، شمارنده خود را متوقف می‌کنند و حسگر ارسال‌کننده این پیام را به عنوان حسگر سرخوشه خود انتخاب می‌کنند. در فاز اول به دلیل اینکه حسگرها در فاصله چند یالی تا حسگرهای سرخوشه قرار دارند، بنابراین امکان انتخاب چندین حسگر به عنوان حسگر سرخوشه وجود خواهد داشت و در نتیجه چندین پیام “CANDIDATE” توسط یک حسگر دریافت می‌گردد. در فاز دوم به منظور انتخاب یک سرخوشه، هر کدام از حسگرهایی که پیام “CANDIDATE” را ارسال کرده‌اند و کاندید سرخوشه شدن می‌باشند یک شمارنده ثانویه را بر اساس قدرت سیگنال دریافتی از هدف راه‌اندازی می‌کنند. بنابراین هر حسگر سرخوشه­ای که هدف به آن نزدیک‌تر است شمارنده ثانویه آن نیز زودتر به اتمام خواهد رسید. این حسگر بعد از اتمام شمارنده ثانویه خود برای تمام حسگرهایی که کاندید سرخوشه شدن هستند پیامی ارسال می‌کند و حسگرهای کاندید سرخوشه با دریافت این پیام شمارنده ثانویه خود را متوقف کرده است و بنابراین یک حسگر که دارای قدرت سیگنال دریافتی بیشتری از هدف است به عنوان حسگر سرخوشه انتخاب می‌گردد.

 

 

رویه شکل‌گیری اولیه خوشه و موقعیت‌یابی:

به منظور خوشه‌بندی اولیه، بعد از اجرای الگوریتم انتخاب رهبر حسگری که سرخوشه گردیده است به تمام همسایه‌های خود که تا آن حسگر یک یال فاصله دارند پیام “I AM LEADER” ارسال می‌کند که این پیام شامل شماره شناسایی حسگر سرخوشه می‌باشد. حسگرهای همسایه در صورت دریافت این پیام به عضویت خوشه در می‌آیند و این حسگرها در زمان‌های از پیش تعیین‌شده، جهت نمونه‌برداری هدف را شناسایی می‌کنند و پیام “INFORMATION” را برای حسگر سرخوشه ارسال می‌کنند که این پیام شامل قدرت سیگنال دریافتی از هدف و شماره شناسایی آن حسگر می‌باشد. حسگر سرخوشه بعد از دریافت پیام “INFORMATION” از اعضاء خوشه خود، با توجه به اطلاعات بدست آمده از سه حسگر که به هدف نزدیک‌تر هستند، موقعیت هدف بدست آورده می‌شود و این موقعیت هدف را به وسیله درخت پوشایی که ریشه آن حسگر چاهک است، ارسال می‌کند. حسگر چاهک، حسگری است که با ایستگاه پایه که در خارج از شبکه‌های حسگر مستقر می‌باشد، در ارتباط می‌باشد.

 

 

رویه شکل‌گیری مجدد خوشه و تعیین مسیر حرکت هدف:

در این رویه ابتدا سرعت و مسیر حرکت هدف با توجه به ۲ موقعیت متوالی هدف توسط حسگر سرخوشه بدست آورده می‌شود. با توجه به سرعت محاسبه‌شده جاری هدف، یک متغییر بنام [۶۳]HC مقداردهی می‌گردد. متغییر HC به تعداد خوشه ­هایی اشاره دارد که قرار است در مسیر هدف پیش‌بینی را انجام دهند. هر چقدر که سرعت بالاتر رود به دلیل اینکه هدف کمتر گم گردد و قابل‌شناسایی باشد، مقدار آن نیز بیشتر می‌گردد. در این رویه به منظور بدست آوردن خوشه‌های آینده[۶۴]، حسگر سرخوشه با توجه به اینکه از مسیر پیش‌بینی‌شده حرکت هدف و موقعیت همسایه‌های خود اطلاع دارد پیام “YOU ARE LEADER” را به همسایه‌ای که به مسیر پیش‌بینی‌شده حرکت هدف نزدیک‌تر است ارسال می‌کند. این پیام شامل معادله مسیر پیش‌بینی‌شده حرکت هدف و HC می‌باشد. هنگام دریافت این پیام توسط حسگر i، حسگر i حالت خود را به سرخوشه تغییر داده و به تمام همسایه‌هایی که تا حسگر i یک یال فاصله دارند پیام “I AM LEADER” را ارسال می‌کند. حسگرهای همسایه i در صورت دریافت این پیام از حالت خواب بیدار شده و به حالت فعال رفته و تا زمانی که هدف را شناسایی نکرده باشند در حالت فعال باقی خواهد ماند. حسگر i نیز مقدار HC را یک واحد کاهش می‌دهد و پیام “YOU ARE LEADER” را به حسگر همسایه‌ای که به مسیر پیش‌بینی‌شده حرکت هدف نزدیک‌تر است ارسال می‌کند و این روند ادامه پیدا می‌کند تا مقدار HC برابر با صفر گردد. بنابراین در این الگوریتم هنگامی‌که هدف در خوشه ابتدایی قرار دارد خوشه‌های آینده ایجاد گردیده می‌شوند و در نتیجه توانایی رهگیری اهداف با سرعت بالا امکان‌پذیر می‌گردد. این روند در شکل ۴-۲ نشان داده شده است.

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

 

 

رویه رهگیری هدف:

در این رویه تا زمانی که هدف در مسیر حرکت پیش‌بینی‌شده خود به حرکت خود ادامه می‌دهد توسط حسگر سرخوشه آینده که هدف در برد خوشه آینده آن قرار دارد موقعیت هدف بدست آورده می‌گردد و هنگامی‌که در سرخوشه آینده تغییر مسیر هدف تشخیص داده شود، رویه شکل‌گیری مجدد خوشه برای مسیر جدید هدف اجرا خواهد گردید و بنابراین الگوریتم توانایی شناسایی اهدافی که به صورت پیوسته تغییر مسیر می‌دهند را نیز دارا می‌باشد.این روند در شکل ۴-۳ نشان داده شده است. همان طور که در شکل ۴-۳ نشان داده شده است هدف هنگامی‌که حسگر n11، حسگر سرخوشه است هدف تغییر مکان داده است و به سمت حسگر n9 نرفته است و به سمت حسگر n6 حرکت کرده است. در این هنگام حسگر n11 برای حسگر n6 که نزدیک‌ترین حسگر به هدف می‌باشد پیام “you are leader” را ارسال می‌کند و رویه شکل‌گیری مجدد خوشه و تعیین مسیر حرکت هدف توسط حسگر n6 اجرا می‌گردد.

شکل ۴-۳: الگوریتم رهگیری هدف در الگوریتم رهگیری سریع اهداف[۱۸].

 

۴-۴- الگوریتم رهگیری توزیع‌شده بر اساس پیش‌بینی:

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

 

 

رویه تولید توصیف‌کننده هدف:

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

 

 

شماره شناسایی هدف:

هنگامی‌که هدف برای اولین بار توسط خوشه جاری(خوشه iام) شناسایی گردید توسط حسگر سرخوشه جاری(CHi) یک شناسه یکتا به آن اختصاص داده می‌شود و تمام سر خوشه‌هایی که به صورت همزمان این هدف را رهگیری می‌کنند از این شناسه به منظور تشخیص هدف مورد نظر استفاده می‌کنند. i به تعداد دفعاتی اشاره دارد که هدف مورد شناسایی قرار گرفته است و برای اولین شناسایی i=1 در نظر گرفته می‌شود.

 

 

موقعیت فعلی هدف:

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

 

 

موقعیت پیش‌بینی‌شده آینده هدف:

در رویه پیش‌بینی موقعیت آینده هدف، به منظور بدست آوردن موقعیت آینده هدف، از یک تخمین زننده خطی استفاده گردیده است که در این تخمین زننده سرعت و جهت حرکت با بهره گرفتن از دو موقعیت متوالی هدف که توسط توصیف‌کننده فعلی(TDi) و توصیف‌کننده قبلی(TDi-1) بدست آورده می‌شوند، تخمین زده می­شوند. متغیر i به تعداد دفعاتی اشاره دارد که هدف مورد شناسایی قرار گرفته است. روند بدست آوردن سرعت و جهت حرکت توسط تخمین زننده خطی در رابطه‌های ۴-۱ و ۴-۲ ارائه گردیده است.