پایان نامه مسیریابی مبتنی بر ناحیه بندی در شبكه های Ad Hoc

پایان نامه مسیریابی مبتنی بر ناحیه بندی در شبكه های Ad Hoc 

قسمتی از متن:

• فاصله تا CH: این قسمت نشاندهنده فاصله گره فرستنده Beacon تا CH بر حسب تعداد گامهای میانی[1] می باشد. مقدار صفر در این حوزه، نشاندهنده این است که فرستنده Beacon خود CH است.
• CHS: این عدد صحیح نشاندهنده تعداد Beaconهایی است که CH از ابتدای شروع کار خود بعنوان CH تاکنون ارسال نموده است. به عبارتی این پارامتر در Beacon، سابقه پایداری CH را بیان مینماید.
• تعداد همسایه‌ها: هر گره در Beaconهای ارسالی، تعداد گره‌های همسایه CH خود را ثبت مینماید.
• ID: این یک عدد صحیح است که با ارسال هر Beacon، یک واحد افزایش می یابد. این پارامتر جهت تست اعتبار Beacon در گیرنده مورد استفاده قرار می گیرد.

بدین ترتیب با دریافت Beacon از گره‌های همسایه، هر گره تخمینی از سرگروه‌های نزدیک به خود و میزان فاصله خود تا آنها و پایداری نسبی آنها بدست خواهد آورد.

3-3-1 تشخیص گره‌های همسایه

ارسال متناوب پیامهایی به گره‌های همسایه كه مستقیما در حوزه دید گره قرار دارند، جهت وقوف گره‌ها از گره‌های همسایه خود، در كلیه روشهای خوشه‌یابی مرسوم است]39[. در الگویتم پیشنهادی نیز از Beacon جهت تشخیص گره‌های همسایه استفاده می‌شود. هرگره با دریافت Beacon از یک گره متحرک، آدرس گره ارسال کننده Beacon را در فهرست همسایگان خود قرار میدهد. درصورتیکه به اندازه معینی Beacon از یکی از گره‌های همسایه دریافت نشود، بدین معنی است که گره مزبور دیگر در همسایگی قرار ندارد که این امر ممکن است بدلیل تحرک خود گره و یا گره همسایه باشد. اطلاعاتی که هرگره درمورد گره همسایه خود ذخیره مینماید به قرار زیر است:

• آدرس گره همسایه
• آدرس CH گره همسایه
• CHS مربوط به CH گره همسایه
• ID آخرین Beacon دریافتی از گره همسایه

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

3-3-2 شکل گیری خوشه‌ها[2]

شکل گیری خوشه‌ها در الگوریتم پیشنهادی از دو فاز تشکیل شده است:

• فاز رقابتی[3]

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

• فاز پایداری[4]

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

زمانیکه یک گره با دریافت Beacon از همسایه خود، تصمیم به عضو شدن در Cluster عنوان شده در Beacon مینماید، اطلاعات خود از سرگروه را براساس اطلاعات موجود در Beacon بروز مینماید. در اینحالت گره همسایه که Beacon را ارسال نموده است اصطلاحا Cluster-Agent نامیده میشود و اطلاعات مربوط به این همسایه تحت عنوان Cluster-Agent در گره عضو شده ثبت میشود. به عبارتی عضو جدید بواسطه Cluster-Agent خود با Cluster-Head در ارتباط است. نقش Cluster-Agent در الگوریتم پیشنهادی تا حدی شبیه به نقش گره Next-Hop در الگوریتمهای مسیریابی DV  میباشد. به عنوان مثال در شکل 3-8، شمائی از خوشه‌یابی دوگامی را مشاهده مینمایید. در این شکل، گره 7 نقش سرگروه را بازی می‌نماید. گره 4 بعنوان عضوی ازسرگروه مربوطه معرفی میشود و گره 9 بعنوان سرگروه آن درنظرگرفته میشود زیرا تنها با دریافت Beacon های گره 9، گره 4 میتواند اطلاعات خوشه‌یابی مربوط به گره 7 را دریافت نماید. همانگونه كه در این شكل قابل مشاهده است، گره 5 كه قبل از این خود را سرگروه معرفی نموده‌بود، اكنون با توجه به تعداد همسایه‌ها، تغییر نقش داده، به عضوی از اعضای خوشه مربوط به سرگروه 7 تبدیل می‌شود.

[1] - Hop Count

[2] - Cluster Formation

[3] - Contention Phase

[4] - Stability Phase

[5] - Stability Threshold

فهرست مطالب

پیشگفتار.............................................................................................................................................................1

فصل اول ...............................................................................................................................................................2

شبكه‌های Ad Hoc...........................................................................................................................................2

1-1 تقسیم‌بندی شبكه‌های بی‌سیم ..................................................................................................................2

1-2 مروری بر پروتكلهای مسیریابی در شبكه‌های MANET ...........................................................6
1-2-1 الگوریتمهای مسیریابی مسطح.............................................................................................................6

1-2-1-1 پروتكلهای مسیریابی Table Driven...............................................................................................7

1-2-1-1-1  پروتكل مسیریابی DSDV ............................................................................................................8

1-2-1-1-2 پروتكل مسیریابی WRP .................................................................................................................8

1-2-1-2 پروتكلهای مسیریابی on-Demand .................................................................................................9

1-2-1-2-1 پروتكل مسیریابی AODV ..........................................................................................................10

1-2-1-2-2 پروتكل مسیریابی DSR ...............................................................................................................12

1-2-1-2-3 ظرفیت شبكه های بی‌سیم و محدودیت الگوریتمهای On-Demand ........ ....................14

1-2-2 الگوریتمهای مسیریابی سلسله‌مراتبی .........................................................................................15

1-2-2-1 مفهوم خوشه‌یابی ...................................................................................................................................18

1-2-2-2 مزایای استفاده از خوشه‌یابی ..............................................................................................................20

1-2-2-3 الگوریتمهای مسیریابی سلسله‌مراتبی مبتنی بر خوشه‌یابی .........................................................22

فصل دوم ..........................................................................................................................................................25

عناصر مورد استفاده جهت شبیه‌سازی شبكه‌های MANET........................................25

2-1 تكنولوژی بی‌سیم مورد استفاده در شبیه سازی شبكه های  Ad Hoc ............................25

2-2 مدلهای تحرك .............................................................................................................................................30

2-2-1 مدل‌های تحرك تصادفی .........................................................................................................................31

2-2-2 مدل تحرك با وابستگی لحظه‌ای ...........................................................................................................32

2-2-3 مدل تحرك با وابستگی فضایی ..............................................................................................................33

2-2-4 مدلهای تحرك با محدودیت جغرافیایی ...............................................................................................35

2-2-5 خصوصیات مدل تحرك Random Waypoint ...........................................................................35

2-3 ابزار شبیه‌سازی ........................................................................................................................................38

فصل سوم .......................................................................................................................................................42

خوشه‌یابی ..........................................................................................................................................................42

3-1 مروری بر الگوریتمهای خوشه‌یابی .....................................................................................................42

3-2 پارامترهای كارایی در روشهای خوشه‌یابی ...................................................................................50

3-3 الگوریتم خوشه‌یابی پیشنهادی ........................................................................................................52

3-3-1 تشخیص گره‌های همسایه .....................................................................................................................54

3-3-2 شکل گیری خوشه‌ها ..............................................................................................................................55

3-3-3 پیکربندی مجدد خوشه‌ها .....................................................................................................................58

3-3-4 ارزیابی کارایی ..........................................................................................................................................65

فصل چهارم.................................................................................................................................................77

نتیجه‌گیری و پیشنهاد برای آینده ....................................................................................................77

ضمیمه 1 ( واژه‌نامه ) ..................................................................................................................................80.

ضمیمه 2 ( عبارتهای اختصاری ) .......................................................................................................82

مراجع ................................................................................................................................................................86

مقاله خلاصه پایان نامه.................................................................................................................89