ورد

موضوع کارآموزی هزینه الگوریتم جستجوی حلقه ای برای شبکه Adhoc موبایل وانرژی موثر پروتکل مسیریابی آن

 مهدی بنی حسن 
  بازدید : 1439
شنبه 06 دی 1393 زمان : 9:54 
 نظرات (0)

موضوع کارآموزی: هزینه الگوریتم جستجوی حلقه ای برای شبکه Adhoc موبایل وانرژی موثر پروتکل مسیریابی آن

قالب فایل : word ----تعداد صفحات:38 صفحه

مهتدس فرزاد جاویدپور

چکیده

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

نتایج شبیه سازی نشان می دهد که بسته های پیام برای مسیریابی به وسیله ی الگوریتم ما به طور قابل توجهی در مقایسه با روش ERS کاهش پیدا کرده است.

معرفی مقاله

شبکه های Adhoc سیار سیستمی از نودهای سیار بی سیم است که می توانند به طور آزادانه و پویا به صورت خود سازماندهی باشند. در توپولوژی شبکه موقتی و ارادی، کاربران و وسیله ها می توانند internet worked(کار کردن با اینترنت) در مناطقی که بدون زیرساخت ارتباطی پیش خروج (pre-exiting) یا وقتی که استفاده از زیرساخت نیاز به توسعه بی سیم دارد.

محقق

…………………

رشته

مهندسی کامپیوتر 87

شماره دانشجویی

………….

استاد مربوطه

مهندس …………

تیرماه 91

An Expending Ring Search Algorithm For Mobile Adhoc Network

چکیده

معرفی مقاله

MANET با چالش های زیر روبرو شده است:

پهنای باند و نسبت انتقال پایین، واسط بالا، تغییرات زیاد در وضعیت شبکه ها، امنیت پایین، range انتقال محدود، توان مصرفی محدود، منابع انرژی محدود و ....

در این مقاله روی طراحی یک پروتکل مسیریابی که از انرژی( توان ) در یک راه کارآمد و موثر استفاده می کند ، تمرکز می کنیم. فرآیند کشف بهینه شده است به طوری که تعداد بسته های درخواست مسیر را کاهش می دهد، بنابراین نوده اتنها بسته های لازم را پردازش می کنند و بسته های دوگانه را دور می اندازند. بنابراین نودها انرژیشان را برای کارهای بعدی ذخیره می کنند.

پروتکل مسیریابی که هم اینک توضیح داده شد از پروتکل مسیریابی AODV توسعه داده شده است. AODV ترکیبی از دو پروتکل مسیریابی DSR (پروتکل مسیریابی منبع پویا) و DSDV است. به طوری که پایه کشف مسیر و تعمیر و نگهداری مسیر از پروتکل DSR است و از مسیریابی گام به گام و sequence number استفاده می کند.

II) A preview of expanding Ring Search algorithm

ERS وابسته به پروتکل های واکنشی(reactive) است. پیام درخواست مسیر به وسیله ي flooding پخش می شود و از یک نود میانی به دیگر نودها منتشر می شود. بری اینکه اطلاعات مسیر را پیدا کند در original flooding پیام EERQ درخواست مسیر به داخل شبکه پخش می شود، بنابراین هر گره همسایه آن را دریافت و پردازش می کند که این منجر به مصرف انرژی در تمام گره ها می شود.

ERS با استفاده از مکانیزم TTL از انرژی به طور کارآمدی استفاده می کند. ارزش TTL ماکزیمم تعداد گره هایی که پیام RREQ می تواند از طریق آن گره عبور کند را تعیین می کند. در وضعیت اولیه شمای ERS، TTL با مقدار N تنظیم می شود بنابراین پیام در یک حلقه با شعاع گام های N‌ پخش می شود. اگر مسیر مقصد پیدا نشود N به وسیله k افزایش پیدا میکند و پیام دوباره پخش می شود.

این گام تا زمانی تکرار می شود که ارزش TTL بیشتر از ارزشی باشد که به عنوان "threshold" نامیده شده اش نشود و راهی نیز پیدا نشده باشد. در این مورد ارزش TTL به یک "limited value" تنظیم می شود سپس پیام RREQ به داخل شبکه پخش می شود.شکل یک مثالی از مفهوم ERS را نشان می دهد.

فرض می کنیم نودS می خواهد یک پیام را به نود D بفرستد، برای این کار مجبور است با استفاده از مکانیزم ERS راهی به D پیدا کند.

در ابتدا گره S پیام RREQ که TTL آن را به N تنظیم کرده است را پخش می کند. برای سادگی ما در این مثال ا= Nقرار می دهیم بنابراین شعاع حلقه ی جستجو یک گام همسایه است.

چون گروه D در جستجوی حلقه نیست و هیچ گره ای در حلقه وجود ندارد که اطلاعاتی در مورد D بداند بنابراین مسیر به D پیدا نشده است در بار دوم TTL به Z افزایش پیدا می کند. گره S به پخش پیام RREQ با TTL ای که به Z تنظیم شده بود ادامه می دهد. در این مورد هم هیچ راهی به D پیدا نشد نهایتاً TTL به "limited valve" تنظیم می شود. پیام RREQ به داخل شبکه پخش می شود. D پیام RREQ را دریافت می کند سپس به گره S به وسیله ی فرستادن RREP پاسخ می دهد. پیام RREP که شامل راهی به D می شود. جزئیات الگوریتم برای ERS در figure3 شرح داده شده است. در گام اولیه گره منبع یک پیام تولید می کند. محل t ، زمان واقعی شبکه را نشان می دهد و C آمدن زمانی است که گره منبع می تواند منتظر RREP بماند قبل از این دوباره پیام RREQ را پخش کند. اگر گره منبع پیام RREP را بین این زمان دریافت کند مسیر به طور موفقیت آمیزی پیدا شده و بسته می تواند به مقصد فرستاده شود.

در غیر این صورت گره منبع TTL آن به وسیله ی x افزایش خواهد یافت و T به تنطیم می شود اگر ارزش TTL بزرگتر از Threshold باشد ارزش TTL به limited value تنظیم خواهد شد و پیام RREQ به داخل شبکه پخش خواهد شد.

وقتی یک گره میانی پیام RREQ را دریافت می کند آن با فرش را نگاه خواهد کرد که اطلاعات مسیر را پیدا کند اگر اطلاعات مسیر پیدا شد گره میانی به گره منبع پاسخ می دهد اگر نه ارزش TTL را چک می کند اگر ارزش TTL برابر با صفر باشد گره میانی پیام RREQ را حذف می کند در غیر این صورت ارزش TTL یک واحد کم می شود.

لگوریتم یک گره میانی برای جستجوی اطلاعات مسیر در Figure 3 شرح داده شده است.

در این الگوریتم وقتی یک گره یک پیام RREQ را دریافت می کند گره آدرس خودش را با آدرس گره منبعی گردد پیام RREQ قرار داده شده است را مقایسه می کند اگربا یکدیگر مطابقت داشتند بنابراین گره منبع است و بنابراین پیام حذف خواهد شد. اگر نه، گره میانی چک می کند که آیا پیام دو گانه است (duplicated) اگر گره برای بار دوم این پیام را دریافت کرده باشد بسته حذف خواهد شد. در غیر اینصورت گره یک مسیر معکوس برگشت به گره را به وجود می آورد. مسیر معکوس برای پیام RREP برگشت به مسیر منبع استفاده می شود. سپس گره با فرش را برای این که اطلاعات مسیر را پیدا کند جستجو می کند. اگر اطلاعات مسیر به مقصد باشد آن به گره منبع پاسخ خواهد داد. اگر نه ارزش TTL را چک می کند. اگر ارزش TTL بزرگ تر از صفر بود سپس گره پیام را پخش خواهد کرد و ارزش TTL یکی کاهش پیدا می کند. روش ERS دارای محدودیت هایی است: اگر گره مقصد دور از گره منبع باشد پس گره منبع مجبور است پیام RREQ چند گانه (multiple) را پخش کند. گره های میانی مجبورند پیام ها را به طور تکراری دریافت و پردازش کنند. که این منجر به مصرف انرژی در گره ها می شود. الگوریتمی که در بخش بعد توضیح داده می شود این مشکل را حل خواهد کرد.

(III)Efficient expanding ring search For Saving energy ConsumpHo.

درروش ERS وقتی یک گره یک پیام را پخش می کند هر گره همسایه پیام را دریافت و پردازش خواهند کرد. اگر یک گره پیام را برای بار اول دریافت کند آن پیام رادوباره پخش می کند در غیر این صورت پیام حذف خواهد شد. اگر پیام شامل اطلاعات مربوط به فرستنده باشد مانند ED گره، حذف کردن پیام های دو گانه (duplicate) اطلاعات همسایه به هدر می رود. بنابراین ما یک روش را پیشنهاد می دهیم که می تواند از اطلاعات پیام هایی که می آیند قبل از حذفشان استفاده کند. این روش روش ERS را بهبود می دهد و اسمش EERS گذاشته شده است. در روش ERS هر گره میانی در جستجوی حلقه مجبور است به پیام پاسخ دهد. اما درروش EERS بعضی از نودها به پیام پاسخ می دهند و مابقی ساکت(silent) می مانند. که این وابسته به اطلاعات پیام هایی است که می آیند.

بنابراین انرژی در هر گره به طور موثری استفاده می شود. در EERS وضعیت گره به عنوان پاسخ دهنده silent,(relying) تعیین می شود که مبتنی بر متغیری به نام "relay" است.

اگر ارزش True,"relay" باشد وضعیت گره relying خواهد بود در غیر این صورت وضعیت گره silent است. این فیلر به وسیله ی فیلری که در پیامی که به دست گره می رسد معین می شود این فیلر Predecessor است که آدرس گره ای که پیام را به فرستنده می فرستد است. برای مثال گره A پیام را به گره B می فرستد گره B پیام را به C می فرستد. گره Predecessor,A گره C می شود وقتی که آن پیام داده می شود به C. در گره منبع ارزش Predecessor به آدرس اش تنظیم می شود. در گره های میانی ارزش Predecessor به آدرس فرستنده اش تنظیم می شود.

آدرس فرستنده از یک گره دریافت کننده می تواند به طور آسانی از پیام دریافت شده استخراج شود.

این است چون قبل از پخش یک گره یک گره مجبور است آدرس اش را به فیلر منبع header بسته اضافه کند. وقتی یک گره پیام را دریافت می کند ارزش فیلر Predeecessor با آدرس اش مقایسه می کند اگر با یکدیگر مطابقت داشته باشد وضعیت true,"relay" تغییر پیدا خواهد کرد.

با تشکر از مهندس فرزاد جاویدپور که این فایل را در اختیار ما قرار دادند.

روش دانلود فایل جامع :

1. کلیک گزینه خرید

2. پرداخت توسط کلیه کارت های عضو شتاب

3. کلیک بر گزینه ( بازگشت به سایت پذیرنده )

4. دانلود فایل مورد نظر