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

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

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

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

عنوان:

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

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

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

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

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

چکیده:

با پیشرفت تکنولوژی ساخت وسایل الکترونیکی و مقرون به صرفه شدن شبکه‌های حسگر در مقیاس‌های بزرگ، شبکه­های حسگر بی­سیم زمینه‌های تحقیقاتی را با رشد سریع و جذابیت بسیار فراهم می­کنند که توجهات زیادی را در چندین سال اخیر به خود جلب کرده می باشد. شبکه‌های حسگر بی‌سیم با مقیاس بزرگ حاوی چند صد تا چند ده هزار حسگر، پهنه وسیعی از کاربردها و البته چالش‌ها را به همراه دارند. ویژگی‌های خاص این شبکه‌ها، امکان بهره گیری از آن‌ها را در کاربردهایی مانند کنترل و مطالعه مناطق حادثه‌خیز، حفاظت مرزها و مراقبت‌های امنیتی و نظامی فراهم می­کنند. یکی از مهم‌ترین کاربردهای متصور برای این شبکه‌ها کاربرد رهگیری هدف می‌باشد. در این کاربرد، شبکه‌های حسگر بی‌سیم از حسگرهای تشکیل‌دهنده این شبکه جهت حس کردن و تشخیص یک هدف خاص و دنبال کردن آن در ناحیه تحت نظارت شبکه بهره گیری می گردد. به دلیل اینکه حسگرهای موجود در این نوع شبکه‌ها دارای محدودیت انرژی می‌باشند و ارتباطات بین حسگرها به صورت بی‌سیم انجام می­پذیرد، در نظر داشتن مسئله مصرف توان و رهگیری بدون خطا چندین هدف متحرک به صورت همزمان در این شبکه‌ها اهمیت فراوانی دارند. الگوریتم‌های رهگیری هدف در شبکه‌های حسگر، از نظر کاربرد و عملکرد آن‌ها، به چهار دسته­ی پروتکل مبتنی بر پیام، مبتنی بر درخت، مبتنی بر پیش‌گویی و مبتنی بر خوشه‌بندی، تقسیم می­گردند. در این بین پروتکل‌های مبتنی بر خوشه‌بندی از نظر مصرف انرژی بهینه هستند. تاکنون برای رفع مشکل انرژی روش‌های زیادی طرح گردیده می باشد که می‌توان به الگوریتم‌های رهگیری اهداف سریع، 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

قیمت : چهارده هزار و هفتصد تومان