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

اختصاصی از اینو دیدی پایان نامه پروتکل های مسیر یابی در شبکه های حسگر بی سیم دانلود با لینک مستقیم و پر سرعت .

فایل:Word (قابل ویرایش و آماده پرینت) تعداد صفحه:74

مقدمه

امروزه امنیت شبکه یک مسأله مهم برای ادارات و شرکتهای دولتی و سازمان های کوچک و بزرگ است. تهدیدهای پیشرفته از سوی تروریست های فضای سایبر، کارمندان ناراضی و هکرها رویکردی سیستماتیک را برای امنیت شبکه می طلبد. در بسیاری از صنایع، امنیت به شکل پیشرفته یک انتخاب نیست بلکه یک ضرورت است.

در این سلسله مقالات رویکردی لایه بندی شده برای امن سازی شبکه به شما معرفی می گردد.  این رویکرد هم یک استراتژی تکنیکی است که ابزار و امکان مناسبی را در سطوح مختلف در زیرساختار شبکه شما قرار می دهد و هم یک استراتژی سازمانی است که مشارکت همه از هیأت مدیره تا قسمت فروش را می طلبد.

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

فهرست

عنوان                                                صفحه

مقدمه ................................................. 3

افزودن به ضریب عملکرد هکرها................................... 4

سطح 1 امنیت پیرامون........................................... 5

سطح 2 امنیت پیرامون .......................................... 7

استاندارد شبکه های محلی بی سیم ............................... 9

شبکه های بی سیم و انواع WPAN,WWAN.WLAN ...................... 11

مقدار بر شبکه خصوصی مجازی (VPN)................................................................. 12

دسته بندی VPN بر اساس رمزنگاری ............................... 12

دسته بندی VPN بر اساس لایه پیاده سازی ......................... 14

مقایسه تشخیص نفوذ و پیشگیری از نفوذ........................... 14

تفاوت شکلی تشخیص با پیشگیری................................... 14

تشخیص نفوذ.................................................... 16

نتیجه ی نهایی................................................. 17

مقدمه ای بر تشخیص نفوذ........................................ 17

انواع حملات شبکه ای با توجه به طریقه حمله ..................... 18

انواع حملات شبکه ای با توجه به حمله کننده ..................... 19

پردازه تشخیص نفوذ ............................................ 20

مقدمه ای بر IPSEC ............................................. 20

انواع IPSEC VPN ............................................... 21

کاربرد پراکسی در امنیت شبکه .................................. 23

برخی از انواع پراکسی.......................................... 24

SMTP proxy .................................................... 25

امنیت و پرتال ................................................ 27

امنیت و پرتال CMS PARS........................................ 27

راهکارهای شبکه های سیم ....................................... 28

نسب، طراحی و راه اندازی شبکه و ایرلس Multipoint Point o............ 29

نسب طراحی و راه اندازی شبکه های Hot spot........................ 29

مشاوره و تامین تجهیزات برای راه اندازی شبکه های وایرلس........ 29

شبکه های بیسیم................................................ 35

انواع شبکه های بی سیم ........................................ 36

شبکه های (MANET) Mobile ad hoc ................................... 38

کاربردهای شبکه Mobile ad hoc ................................... 39

پروتوکل های مسیریابی Routing proto cols............................ 39

پروتوکل TCP/IP................................................. 40

مقدمه......................................................... 40

معنی پروتوکل TCP/IP............................................ 41

لایه های پروتکل TCP/IP.......................................... 41

لایه Application.................................................. 42

لایه Transport................................................... 43

لایه اینترنت................................................... 43

لایه Network Interface.............................................. 43

مشخص نمودن برنامه ها ......................................... 43

آدرس IP........................................................ 44

یورت TCP/IP.................................................... 44

سوکت (Socket)................................................... 44

TCP/IP......................................................... 44

پروتکل:TCP لایه Transport........................................ 45

ارسال اطلاعات با استفاده از TCP................................ 45

پروتوکل: UUP لایه Internet ....................................... 46

پروتوکل: IP لایه Internet.......................................... 48

مسیر یابی .................................................... 49

معنای حمل..................................................... 49

توزیع توپولوژی................................................ 49

آلگوریتم برداری راه دور ...................................... 49

آلگوریتم حالت اینک............................................ 59

پروتوکل بردار مسیر............................................ 50

مقایسه الگوریتم مسیریابی ..................................... 50

انتخاب مسیر................................................... 51

عوامل چندگانه ................................................ 51

شبکه های حسگر بی سیم.......................................... 52

نگاهی به شبکه های بی سیم حسگر................................. 52

ویژگی های عمومی یک شبکه حسگر.................................. 54

ساختار ارتباطی شبکه های حسگر.................................. 54

فاکتورهای طراحی .............................................. 54

تحمل خرابی.................................................... 55

قابلیت گسترش.................................................. 55

هزینه تولید .................................................. 55

سخن پایانی.................................................... 57

منابع ........................................................ 58

44 - پایان نامه حسگر بی سیم

اختصاصی از اینو دیدی 44 - پایان نامه حسگر بی سیم دانلود با لینک مستقیم و پر سرعت .

کاهش مصرف انرژی در شبکه‌های حسگر بی‌ سیم با استفاده از شبکه‌های عصبی SOM

اختصاصی از اینو دیدی کاهش مصرف انرژی در شبکه‌های حسگر بی‌ سیم با استفاده از شبکه‌های عصبی SOM دانلود با لینک مستقیم و پر سرعت .

پروژه "کاهش مصرف انرژی در شبکه‌های حسگر بی‌سیم با استفاده از شبکه‌های عصبی SOM " یک تحقیق کامل و علمی برای رشته کامپیوتر ، شبکه و IT میباشد که بطور کامل بحث را مورد کنکاش و جستجو قرار داده و مطالب سطح بالایی را در پروژه آورده است.این پروژه با ارزش در 6 فصل تنظیم شده و بطور کامل ویرایش شده و در قالب Word آماده تحویل میباشد.

امروزه، در شبکه‌های حسگر بی‌سیم، پروتکل‌های مسیریابی مبتنی بر خوشه‌بندی از طریق تقسیم گره‌های همسایه به خوشه‌های مجزا و انتخاب سرخوشه‌های محلی برای ترکیب و ارسال اطلاعات هر خوشه به ایستگاه مبنا و سعی در مصرف متوازن انرژی توسط گره‌های شبکه، بهترین کارایی را از لحاظ افزایش طول عمر و حفظ پوشش شبکه‌ای در مقایسه با سایر روش‌های مسیریابی به‌ دست می‌آورند. با این وجود، همه پروتکل‌های خوشه‌بندی ارایه شده تاکنون، تنها نزدیکی جغرافیایی(همسایگی) را به عنوان پارامتر تشکیل خوشه‌ها در نظر گرفته‌اند. در این تحقیق، یک پروتکل جدید خوشه‌بندی متمرکز مبتنی بر انرژی با استفاده از شبکة عصبی نقشة خودسازماندهی برای شبکه‌های حسگر بی‌سیم ارایه می‌شود که قادر به خوشه‌بندی گره‌های شبکه بر اساس سطح انرژی و مختصات گره‌ها می‌باشد. این پروتکل با استفاده از تعداد مشخصی از گره‌های پرانرژی در شبکه و اعمال آن‌ها به عنوان وزن نورون‌های نقشة خودسازماندهی، نزدیک‌ترین گره‌های کم‌انرژی را جذب گره‌های پرانرژی می‌کند؛ به طوری که خوشه‌ها لزوماً از گره‌های مجاور تشکیل نشده و در واقع براساس دو پارامتر سطح انرژی و همسایگی، خوشه‌هایی با انرژی متوازن تشکیل خواهند شد. به علاوه یک تابع هزینه جدید به منظور تصمیم‌گیری در انتخاب گره‌های سرخوشه، پیشنهاد شده است که سعی در ترکیب معیارهای مختلف موثر در انتخاب بر اساس میزان اهمیت آن‌ها دارد. کارایی برتر این پروتکل از لحاظ افزایش طول عمر مفید شبکه و حفظ بهتر پوشش شبکه‌ای در مقایسه با پروتکل‌های پیشین نظیر LEACH و LEA2C و نیز تاثیر تابع هزینه پیشنهادی بر کارایی آن (با شبیه‌سازی) به اثبات رسیده است.

فهرست مطالب

عنوان صفحه

فصل1 مقدمه

1-1. مقدمه. 2

1-2. تعریف مساله و سئوالات اصلی تحقیق.. 3

1-3. فرضیه‌ها4

1-4. اهداف تحقیق.. 4

1-5. روش تحقیق.. 5

1-6. مراحل انجام تحقیق.. 5

1-7. ساختار پایان‌نامه. 6

فصل2 مروری بر منابع مطالعاتی 8

2-1. مقدمه. 9

2-2. طبقه‌بندی روش‌های کاهش مصرف انرژی در شبکه‌های حسگر. 13

2-2-1. چرخة وظایف... 16

2-2-2. روش‌های داده‌گرا18

2-2-3. روش‌های مبتنی بر قابلیت تحرک... 21

2-3. نقش شبکه‌های عصبی در کاهش مصرف انرژی شبکه‌های حسگر. 22

2-3-2. شبکه‌های عصبی در طرح‌های چرخه وظایف... 27

2-3-3. شبکه‌های عصبی در کاهش داده. 28

2-3-4. شبکه‌های عصبی در شبکه‌های حسگر متحرک... 38

2-4. نتیجه‌گیری... 40

فصل3 نقش شبکه‌های عصبی در مسیریابی انرژی آگاه 41

3-1. مقدمه. 42

3-2. ویژگی‌های مسیریابی در شبکه حسگر بی‌سیم.. 43

3-3. روش‌های مسیریابی در شبکه‌های حسگر بی‌سیم.. 45

3-3-1. مسیریابی مسطح.. 46

3-3-2. مسیریابی مبتنی بر مکان.. 47

3-3-3. مسیریابی سلسه مراتبی(مبتنی بر خوشه‌بندی)48

3-3-4. پروتکل خوشه‌بندیLEACH... 49

3-3-5. پروتکل خوشه‌بندیLEACH متمرکز. 51

3-4. شبکه‌های عصبی در الگوریتم‌های مسیریابی آگاه از انرژی... 52

3-4-1. شبکة عصبی انتشار معکوس در کشف مسیر. 52

3-4-2. شبکة عصبی نقشة خودسازماندهی در مسیریابی.. 54

3-4-3. پروتکل‌های مسیریابی مبتنی بر نقشة خودسازماندهی.. 56

3-5. پروتکل خوشه‌بندی پیوندگرا وفقی با انرژی پایین.. 60

3-6. جمع‌بندی... 63

فصل4 پروتکل جدید پیشنهادی 64

4-1. مقدمه. 65

4-2. پروتکل مسیریابی خوشه‌بندی مبتنی بر انرژی خودسازمانده. 66

4-3. فرضیات الگوریتم.. 66

4-4. مرحلة خوشه‌بندی... 68

4-4-2. مرحلة اول : خوشه‌بندی با شبکة عصبی نقشة خودسازماندهی.. 69

4-4-3. مرحلة دوم : خوشه‌بندی با الگوریتم K-means. 76

4-4-4. مرحلة انتخاب سرخوشه. 78

4-5. مرحلة انتقال داده. 81

4-6. مرحلة خوشه‌بندی مجدد. 82

4-7. جمع‌بندی... 87

فصل5 نتایج شبیه‌سازی و تحلیل آن‌ها88

5-1. مقدمه. 89

5-2. پارامترهای شبیه‌سازی... 89

5-2. نتایج شبیه‌‌سازی... 91

5-2-1. مقایسة نحوة تشکیل خوشه‌ها در EBCS با پروتکل LEACH... 91

5-2-2. مقایسة کارایی EBCS با پروتکل‌های پیشین از لحاظ طول عمر شبکه. 93

5-2-3. ارزیابی تابع هزینه انتخاب سرخوشهبرکارایی EBCS.. 96

5-2-4. ارزیابی کارایی پروتکلEBCS در افزایش پوشش شبکه‌ای... 99

5-3. جمع بندی... 102

فصل6 جمع‌بندی و پیشنهاد‌ها104

6-1. مقدمه. 105

6-2. یافته‌های تحقیق.. 107

6-3. نوآوری تحقیق.. 108

6-4. پیشنهاد‌ها109

مراجع 111

واژه‌نامه 116

دانلودمقاله کاربرد داده ساختارهای جنبشی در مسیریابی شبکههای حسگر متحرک

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

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

Kinetic Data Structures for Routing Problem in Mobile Sensor Networks
Kamyar Rafati, Naeem Esfahani, Mohammad Ghodsi
Abstract
“Sensor networks” is an important topic in computer science and algorithm design. These networks are constructed from a set of independent mobile units with limited power and process capability. These units communicate and gather information using radio transmitters. The problem of routing in these networks with minimum power consumption is a NP-hard problem. Therefore, many researches use approximation algorithms for this problem. Most of the proposed models work with fixed sensors. In this paper, we propose an algorithm for routing in mobile sensor networks. According to the inherent kinetic structure of such networks, the use of a kinetic data structure which efficiently maintains minimum spanning tree (MST) is useful. In this paper, we present such structure for our problem and show that this method reduces the time complexity of routing in sensor networks.
Keywords
Algorithm, Sensor Networks, Routing, Kinetic Data Structures, Minimum Spanning Trees

1- مقدمه
با ظهور ارتباطات بی¬سیم بین عناصر مختلف و به دنبال آن مسئله شبکه¬های بی سیم و متحرک، توجه بسیاری از اندیشمندان رشته علوم کامپیوتر به مسائل موجود در این شبکه از قبیل مسیریابی معطوف شد. اما این شبکه¬ها پاسخگوی تمام نیازها در زمینه ارتباطات بی سیم نبودند. به همین منظور مدل شبکه¬های ویژه ارائه شد که در آنها ارتباطات از طریق فرستنده¬ها و گیرنده¬های رادیویی با فاصله ارتباطی محدود انجام می¬گرفت و در ضمن ساختار یکپارچه مرکزی برای مسیریابی و مدیریت ندارند. در قدم بعدی محدودیت توان مصرفی و عملیاتی نیز به مدل فوق افزوده شد و مدل شبکه حسگر معرفی شد.
شبکه های حسگر کاربرد بسیار وسیعی دارند. مثلا حسگرهای تشخیص آتش سوزی در یک جنگل و یا شهر همچنین حسگرهای تشخیص تشعشعات هسته¬ای در یک رآکتور هسته¬ای، نمونه¬هایی از این کاربردها هستند.
ویژگی¬های شبکه¬های حسگر را می¬توان به اجمال به این موارد تقسیم نمود: 1. انرژی محدود عناصر .2. پهنای باند محدود .3. شبکه بدون ساختار و متغیر با زمان .4. کیفیت پایین ارتباطات .5. قدرت محاسبات محدود در عناصر.
از جمله مسائل مطرح در زمینه شبکه-های حسگر، بحث مسیریابی در این شبکه¬ها است. الگوریتم¬های متفاوتی برای این مسئله ارائه شده است. الگوریتم¬های ارائه شده را می¬توان به دو دسته همگن و ناهمگن تقسیم نمود. الگوریتم¬¬های همگن فرض را بر یکسان بودن عناصر شبکه (از نظر برد فرستنده) می¬گذارند. الگوریتم¬های ناهمگن از انعطاف¬پذیری بیشتری برخوردار هستند. الگوریتم¬های ناهمگن با توجه به اطلاعاتی استفاده می¬کنند به سه دسته تقسیم می¬شوند. 1- بر مبنای محل : در آنها محل دقیق عناصر مشخص می¬باشد. 2- بر مبنای جهت : در آنها فرض می¬شود که هر کس جهت نسبی همسایگانش را نسبت به خود می¬داند. 3- بر مبنای همسایه : در آنها فرض می¬شود که شناسه همسایه¬ها در اختیار است.
الگوریتم¬های ارائه شده را از یک منظر دیگر می¬توان به دو دسته متمرکز و نامتمرکز نیز تقسیم نمود. در الگوریتم¬های متمرکز، یک ناظر خارجی در سیستم وجود دارد که مسئولیت مسیریابی را به عهده دارد. البته فرض وجود چنین ناظری اولا با ماهیت شبکه¬های حسگر سازگار نیست در ضمن قابلیت مقیاس¬پذیری ندارد.
از جمله روش¬های رایج در زمینه مسیریابی استفاده از درخت فراگیر کمینه است. اما به دو دلیل که در ادامه خواهیم دید، استفاده از آنها در این شبکه¬ها محبوبیت پیدا نکرده است. اولا پیدا کردن کوچکترین درخت فراگیر یک الگوریتم ماهیتا متمرکز است و دوما به علت آنکه هزینه ساخت آن بالاست و در این شبکه¬ها - به علت متحرک بودن عناصر - نیاز است که مرتبا این درخت ساخته شود.
در این مقاله یک الگوریتم برای مسیریابی در شبکه¬های حسگر بر مبنای کوچکترین درخت فراگیر ارائه می¬شود ولی سعی شده که مشکلات ذکر شده در بالا در آن پاسخ داده شود. برای این منظور اولا از کوچکترین درخت فراگیر محلی استفاده شده است که نیاز ناظر را از بین می¬برد و همچنین از یک ساختار جنبشی برای نگهداری آن استفاده می¬شود که مشکل هزینه تغییرات را از بین می¬برد.
در زمینه مسیریابی در شبکه¬های حسگر کارهای گوناگونی انجام شده است ولی در تمام آنها فرض بر ثابت بودن ساختار شبکه در طول حیات شبکه است. همچنین داده ساختارهای گوناگونی برای نگاهداری اجزای شبکه مطرح شده است ولی اکثر آنها هزینه به روز رسانی بالایی دارند و همچنین برای مسئله مسیریابی مناسب نیستند. لذا در این مقاله تلاش شد تا فرض¬های مطرح شده بسیار به محیط واقعی شبیه باشند که تا زمان نوشتن این مقاله کاری با این درجه شباهت با محیط واقعی پیدا نکردیم. نتیجه حاصل نیز هزینه نگاهداری و به روز رسانی کمینه¬ای دارد که برای حسگر های با انرژی محدود مناسب است.
در بخش¬های بعدی ابتدا یک الگوریتم برای کوچکترین درخت فراگیر محلی ارائه می¬شود. سپس یک روش جنبشی برای نگهداری کوچکترین درخت فراگیر ارائه می¬شود. در ادامه الگوریتم اصلی که ترکیبی از این دو روش است معرفی می-شود و بعضی خواص آن اثبات می¬شود . در انتها پیچیدگی الگوریتم و نتیجه-گیری آورده شده ¬است.
2- کوچکترین درخت فراگیر محلی
در این قسمت روشی برای ساخت کوچکترین زیر درخت فراگیر به صورت محلی ارائه می¬شود. ایده اصلی از روش ارائه شده توسط لی و همکارانش [1] گرفته شده است.
الگوریتم ساخت این درخت در دو فاز انجام می¬شود. در مرحله اول اطلاعات بین عناصر شبکه تبادل می¬شود و در مرحله دوم هر عنصر به صورت مجزا کوچکترین زیر درخت فراگیر را برای خود می¬سازد. در ادامه هر یک از دو فاز را به تفضیل شرح می¬دهیم.
فاز تبادل اطلاعات : در این فاز همانند مدل بردار فاصله در مسیریابی درون دامنه¬ای عمل می¬شود. به این صورت که هر عنصر در شبکه اطلاعات خود را از تمام عناصر شبکه به صورت یک بردار فاصله به همسایگانش می فرستد. به علت اینکه عناصر از وجود تمام عناصر دیگر آگاه نیستند استفاده از شناسه الزامی است. پس از اتمام این فاز ، تمام عناصر و یا گره‌های شبکه ، اطلاعات کل شبکه را در اختیار دارند.
فاز ساخت کوچکترین زیر درخت فراگیر : در این فاز ، همانند فاز دوم در روش ارائه شده توسط لی و همکارانش [1] ، هر گره با استفاده از الگوریتمی مانند پریم [4] کوچکترین زیر درخت فراگیر را می سازد. در الگوریتم پریم درخت حاصل یکتا نیست زیرا در مواردی که فاصله دو گره از یک گره یکسان باشد به صورت اتفاقی یکی از آنها انتخاب می¬شود. ولی به منظور اینکه تمام عناصر دید یکسانی از این درخت داشته باشند ، ما تابع فاصله را به صورت زیر تغییر داده¬ایم تا همیشه درخت یکتایی تولید شود.

که در آن برابر فاصله راس از راس است. در انتهای این فاز هر عنصر یک درخت فراگیر دارد که در تمام گره¬های مختلف شبکه یکسان هستند و در حقیقت روی آن توافق شده است. در صورتی که عناصر شبکه در یک صفحه باشند اثبات می شود که بزرگترین درجه راس¬های درخت حداکثر 6 می¬شود. این نکته باعث کاهش قابل توجهی از انرژی مصرفی هر گره می¬شود.
تا این مرحله هر گره ، کوچکترین زیر درخت فراگیر لازم برای مسیریابی را ساخته است. در بخش بعد روشی برای نگهداری بهینه این درخت در موارد وجود حرکت و یا حذف و ایجاد گره¬های جدید با کمک یک داده ساختار جنبشی ارائه می¬شود.
3- کوچکترین درخت فراگیر پارامتری و جنبشی
برای مدل کردن ساختار جنبشی گره‌ها می‌توان روش‌های مختلفی را پیش گرفت. در ابتدایی‌ترین حالت می‌توان فرض کرد معادله‌ی حرکت گره‌ها دقیقا مشخص است و بر پایه‌ی آن داده ساختار مساله را حل کرد. مشکل این روش این است که اولا معادله‌ی حرکت یک گره ممکن است بسیار پیچیده باشد و بدست آوردن اطلاعات لازم از آن کار ساده‌ای نباشد؛ دوما ماهیت معادله‌ی حرکت یک گره یک مفهوم پیوسته است و برای ما مناسب‌تر است اگر بتوانیم آن را به صورت یک مفهوم گسسته مدل کنیم. بنابراین از مدل معرفی شده توسط آگاروال و همکارانش [2] استفاده می‌کنیم که در آن به جای در نظر گرفتن معادله‌ی حرکت یک گره، تغییرات وزن یک یال را داریم و آن را یک تابع خطی در نظر می‌گیریم و برای گسسته کردن این تابع از رابطه‌ی برای یال استفاده می‌کنیم. در این تابع دو عدد و دو عدد حقیقی هستند و به عنوان یک پارامتر گسسته تغییر کرده و باعث تغییر وزن یال‌ها می‌شود. به طور کلی دو دسته الگوریتم جنبشی برای حل مساله‌ی کوچکترین درخت فراگیر داریم که هر کدام را می‌توان با دیگری شبیه‌سازی نمود:
• الگوریتم جنبشی ساختاری: که در آن یال‌ها اضافه و حذف می‌شوند و تغییر وزن را با حذف و اضافه کردن یال شبیه‌سازی می‌کنیم.
• الگوریتم جنبشی تابعی: که توانایی تغییر وزن یال‌ها را دارد و اضافه و حذف یال‌ها را با استفاده از یک عدد بسیار بزرگ به عنوان وزن یال حذف شده شبیه‌سازی می‌کند.
یکی از تکنیک‌هایی که در این روش استفاده می‌شود روش تنک کردن است که عملا روش تقسیم و حل می‌باشد. در این روش گراف را به صورت بازگشتی به تعدادی دسته تقسیم می‌کنیم. نکته‌ای این تقسیم بندی‌ها دارند این است که درخت نهایی حاصل از گراف به راحتی از کنار هم قرار دادن جواب‌های زیر درخت‌ها حاصل از زیر گراف‌ها بدست می‌آید. اپستین و همکارانش [7] نشان دادند که این عمل نتیجه‌ی درستی می‌دهد. فرناندز و همکارانش [8] نیز نشان دادند که این روش برای مساله‌ی پارامتری نیز درست کار می‌کند و هزینه‌ی آن را نیز محاسبه کردند.
نقطه‌ی عطف این روش مطرح کردن ایده‌های هندسه‌ی محاسباتی در کاربرد تئوری گراف‌هاست؛ نشان داده می‌شود که می‌توان اطلاعات مربوط به گره‌ها را توسط پوش محدب نگهداری کرد؛ به این ترتیب که با توجه به دسته‌بندی که انجام می‌شود، مجموعه‌هایی داریم که برای داشتن درخت فراگیر باید یکی از یال‌ها را انتخاب و حذف کرد. اگر در این انتخاب بزرگترین عنصر مجموعه را حذف کنیم درخت ما کمینه خواهد بود. در این‌جا جنبش باعث می‌شود که این بزرگ‌ترین عنصر با تغییر که حاصل از جنبش است عوض شود و برای داشتن کوچکترین درخت فراگیر مجبور به تعویض یال شویم. با استفاده از پوش محدب می‌توانیم در زمان بزرگ‌ترین یال جدید را پیدا کنیم و جای یال قبلی را با آن عوض کنیم. روند کار به این ترتیب است که با استفاده از تبدیل هو [Hough59] معادله‌ی وزن یال‌ها بر اساس را تبدیل به نقاط می‌کنیم. در مساله‌ی دوگان بدست آمده خطی که بر دو پوش محدب مماس می‌شود مشخص می‌کند کدام دو خط باید جابجا شوند. این دو نقطه‌ی پیدا شده در عمل نشان دهنده‌ی بیش‌ترین رشد وزن در یال‌هایی که در درخت هستند و بیش‌ترین کاهش وزن در یال‌هایی که در درخت نیستند می‌باشند و اگر قرار باشد جای دو یال عوض شود باید این دو یال باشند. دو یال می‌توانند در جابجایی روابط زیر را با هم داشته باشند:
• جابجایی درون افرازی: هر دو در یک افراز هستند.

فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد

تعداد صفحات این مقاله  6  صفحه

پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید