چکیده 1
1- فصل اول: شبکه های Ad Hoc 2
1-1- تقسيم‌بندي شبكه‌هاي بي‌سيم 3
1-2- مروري بر پروتكلهاي مسيريابي در شبكه‌هاي MANET 7
1-3- الگوريتمهاي مسيريابي مسطح 7
1-4- پروتكلهاي مسيريابي Table Driven 8
1-5- پروتكل مسيريابي DSDV 8
1-6- پروتكل مسيريابي WRP 9
1-7-پروتكلهاي مسيريابي on-Demand 10
1-8-پروتكل مسيريابي AODV 11
1-9-پروتكل مسيريابي DSR 13
1-10- ظرفيت شبكه هاي بي‌سيم و محدوديت الگوريتمهاي On-Demand 16
1-11-الگوريتمهاي مسيريابي سلسله‌مراتبي 18
1-12-مفهوم خوشه‌يابي 20
1-13- مزاياي استفاده از خوشه‌يابي 21
1-14-الگوريتمهاي مسيريابي سلسله‌مراتبي مبتني بر خوشه‌يابي 23
2- فصل دوم: عناصر مورد استفاده جهت شبيه‌سازي شبكه‌هاي MANET 26
2-1-تكنولوژي بي‌سيم مورد استفاده در شبيه سازي شبكه هاي Ad Hoc 27
2-2-مدلهاي تحرك 32
2-3-مدلهاي تحرك تصادفي 32
2-4-مدل تحرك با وابستگي لحظه‌اي 34
2-5-مدل تحرك با وابستگي فضايي 35
2-6-مدلهاي تحرك با محدوديت جغرافيايي 36
2-7- خصوصيات مدل تحرك Random Waypoint 36
2-8-ابزار شبيه‌سازي 39
3- فصل سوم: خوشه یابی 43
3-1-مروري بر الگوريتمهاي خوشه‌يابي 44
3-2-پارامترهاي كارايي در روشهاي خوشه‌يابي 50
3-3-الگوريتم خوشه‌يابي پيشنهادی 52
3-4-گره‌های همسايه 54
3-5-شکل گيری خوشه‌ها 55
3-6-پيکربندی مجدد خوشه‌ها 58
3-7-ارزيابی کارايی
65
نتيجه‌گيري و پيشنهاد براي آينده 77
ضمیمه 1 80
ضمیمه 2 82
مراجع 84
فهرست شکل صفحه
شكل 1-1-1 مثالي از شبكه‌هاي داراي زيرساخت 4
شكل 1-1-2 نمونه‌اي از شبكه‌هاي فاقد زير ساخت 5
شكل 1-2-1 تقسيم‌بندي پروتكلهاي مسيريابي شبكه‌هاي MANET 7
شكل 1-8-1 (الف) ارسال RREQ در الگوريتم AODV 12
شكل 1-8-2- (ب) ارسال RREP در الگوريتم AODV 12
شكل 1-9-1- (الف) ارسال درخواست مسير در الگوريتم مسيريابي DSR 15
شكل 1-9-2- (ب) ارسال پاسخ درخواست مسير در الگوريتم مسيريابي DSR 16
شكل 1-10-1- افت گذردهي در يك شبكه بي‌سيم نمونه با افزايش تعداد گره‌هاي شبكه 17
شكل 1-11-1- شبكه مجازي ايجاد شده در يك شبكه MANET با استفاده از مسيريابي سلسله‌مراتبي 19
شكل 1-12-1- مثالي ازخوشه‌يابي در شبكه Ad Hoc 21
شكل 1-13-1- خوشه‌يابي در ساختار لايه‌اي 22
شكل 1-14-1- مثالي از الگوريتم مسيريابي CGSR 23
شكل 1-14-2- يافتن مسير در الگوريتم CBRP 25
شكل 2-1-1- زمان‌بندي ارسال بسته در استاندارد IEEE 802.11 29
شكل 2-1-2- تخمين مدت زمان اشغال خط با استفاده از RTS/CTS 30
شكل 2-1-3- مثالي از محدوديت IEEE 802.11 MAC 31
شكل 2-2-1- تقسيم‌بندي مدلهاي تحرك شبكه‌هاي Ad Hoc 32
شكل 2-3-1- الگوي حركتي يك گره متحرك در مدل Random Waypoint 33
شكل 2-5-1- مدل تحركي RPGM 36
شكل 2-7-1 تغيير متوسط سرعت با گذشت زمان در مدل تحرك Random Waypoint 38
شكل 2-7-2- تغيير تعداد متوسط گره‌هاي همسايه با گذشت زمان در مدل تحرك Random Waypoint 39
شكل 2-8-1- مراحل شبيه‌سازي از ديد كاربر NS-2 41
شكل 3-1-1 خوشه‌يابي به روش Lowest-ID 44
شكل 3-1-2- پارامتر تحرك تعريف شده در MOBIC 46
شكل 3-1-3- توان دريافتي هنگام دريافت بسته از گره‌هاي همسايه 47
شكل 3-1-4- مثالي از 2-hop Dominating Set 48
شكل 3-1-5- مثالي از تشكيل خوشه‌ها در روش max-min 49
شكل 3-3-1- ساختار پياده‌سازي شده جهت خوشه‌يابي 52
شكل 3-3-2- آرايش بستهBeacon 53
شکل 3-5-1- مثالی از خوشه‌يابي دوگامي در يک شبکه Ad Hoc 57
شکل 3-5-2- الگوريتم اجرائی در يک سرگروه با دريافت يک Beacon 58
شکل 3-6-1- الگوريتم اجرائی در يک گره عادی که Cluster-Agent خود را ازدست داده است. 59
شكل 3-6-2- مثالي از عملكرد الگوريتم در حالت مفقود شدن Cluster-Agent 61
شکل 3-6-3- الگوريتم اجرائی در گرهی که در CH مربوط به Cluster-Agent خودتغيير مشاهده نموده است. 62
شكل 3-6-4- مثالي از عملكرد الگوريتم در صورت تغيير CH در Cluster-Agent 64
شکل 3-7-1-. تعداد متوسط خوشه‌های ايجادشده برحسب تعداد گره‌های موجود درشبکه 67
شکل 3-7-2- طول عمرمتوسط Clusterهای ايجادشده برحسب تعداد گره‌های موجود در شبکه 68
شکل 3-7-3- مدت متوسط عضويت گره‌ها در خوشه‌های ايجادشده 69
شكل 3-7-4- تاثير Connectivity برروی تعداد خوشه‌های ايجاد شده (سرعت 20 متربرثانيه) 71
شكل 3-7-5- تاثير سرعت و Connectivity بر طول عمر خوشه‌ها 72
شكل 3-7-6-تاثير سرعت گره‌ها بر طول عمر خوشه‌ها 73
جدول 3-7-7- پارامترهاي شبيه‌سازي جهت مقايسه با LCC و MOBIC 73
شكل 3-7-8- تاثير Connectivity بر تعداد خوشه‌هاي ايجادشده در شبكه درسرعت 20 متربرثانيه 75
شكل 3-7-9- تاثير Connectivity بر تعداد تغيير خوشه‌ها در سرعت 20 متربرثانيه 75
شكل 3-7-10- تاثير سرعت گره‌هاي متحرك برروي تعداد تغييرات خوشه‌ها (TX-Range=250m) 76
فهرست جداول
جدول 3-1-1 مراحل انجام روش max-min 50
جدول 3-7-1- پارامترهاي مدل تحرك مورد استفاده درشبيه‌سازي 65
جدول 3-7-2- مقادير RXThresh و CSThresh مورد استفاده در شبيه‌سازي 70
جدول 3-7-3- پارامترهاي شبيه‌سازي جهت بررسي اثر Connectivity 71