پایان نامه ارشد رشته معماری کامپیوتر: ارائه یک الگوریتم رهگیری هدف پویا بر اساس پیش‌بینی در شبکه حسگر بی‌سیم

دانلود متن کامل پایان نامه با فرمت ورد

پایان نامه مقطع کارشناسی ارشد رشته کامپیوتر

دانشگاه صنعتی اصفهان

دانشکده برق و کامپیوتر

پایان‌نامه کارشناسی ارشد مهندسی کامپیوتر- معماری کامپیوتر

عنوان:

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

استاد راهنما:

دکتر مهدی مهدوی

برای رعایت حریم خصوصی نام نگارنده درج نمی شود

تکه هایی از متن به عنوان نمونه :

چکیده:

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

فصل اول: مقدمه

1-1- شرح و اهمیت موضوع

یکی از شبکه‌هایی که در سال‌های اخیر توجهات زیادی را به خود جلب کرده است، شبکه‌های حسگر بی­سیم[1] (WSN) می‌باشند. شبکه‌های حسگر از تعداد زیادی حسگر تشکیل شده‌اند که پس از توزیع در منطقه، حسگرهایی که در نزدیکی یک رویداد قرار دارند بعد از شناسایی آن رویداد به جمع­آوری اطلاعات رویداد مورد نظر در محیط می­پردازند و اطلاعات بدست آمده از رویداد را به حسگر چاهک ارسال می‌کنند. حسگر چاهک، حسگری است که با ایستگاه پایه[2] که در خارج از شبکه‌های حسگر مستقر می‌باشد، در ارتباط می‌باشد[1]. حسگرهای این شبکه‌ها دارای یک واسط بی­سیم می‌باشند که همین امر باعث گردیده است که این شبکه‌ها در سطح زمین، زیر آب و دیگر مکان‌های خطرناک و یا غیرقابل‌دسترس راه‌اندازی گردند. بنابراین شبکه‌های حسگر قادر به پوشش مناطقی هستند که شبکه‌های دیگر از عهده پوشش آن مناطق بر نمی‌آیند و در واقع شبکه‌های حسگر امکان تعامل بین انسان، محیط و ماشین را فراهم می­کنند. گسترش شبکه‌های حسگر بی­سیم با کاربردهای نظامی آغاز گردید ولی امروزه با گسترش سریع کاربردهای شبکه‌های حسگر، در زمینه‌های رهایی از سانحه، کنترل محیطی و نگاشت تنوع زیستی، سازه‌های هوشمند، مدیریت تأسیسات، کشاورزی، پزشکی و بهداشت، حمل‌ونقل، پردازش از راه دور و رهگیری هدف از شبکه‌های حسگر بی­سیم استفاده می‌گردد. به همین دلیل امروزه پیشرفت‌های زیادی در حوزه زیرسیستم‌ های الکترومکانیکی صورت پذیرفته است تا امکان توسعه حسگرهای هوشمند فراهم گردد [1].

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

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

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

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

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

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

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

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

1-2- اهداف تحقیق

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

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

[1] Wireless Sensor Network

[2] Base stattion

[3] Scalability

***ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل و با فرمت ورد موجود است***

متن کامل را می توانید دانلود نمائید

چون فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به طور نمونه)

ولی در فایل دانلودی متن کامل پایان نامه

 با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود است

تعداد صفحه : 108

قیمت : 14700 تومان

***

—-

پشتیبانی سایت :       

****         serderehi@gmail.com