4-1-3 مقابله با حملات انسداد   ………………………………………………………………..   15

 

5-1-3 تکنیک های کاهش اثرات حمله در لایه ی فیزیکی   ………………………………..   15

 

1-5-1-3 تغییر کانال   …………………………………………………………………………….   16

 

2-5-1-3 عقب نشینی فضایی   ……………………………………………………………….   16

 

3-5-1-3 استفاده از کرم چاله ها   …………………………………………………………..   17

 

4-5-1-3 نقشه برداری منطقه ی مسدود شده   …………………………………………..   17

 

5-5-1-3 تکنیک های طیف گسترده   ………………………………………………………..   17

 

6-5-1-3 نظریه ی بازی   ………………………………………………………………………..   17

 

7-5-1-3 گره های عسل   ………………………………………………………………………   18

 

8-5-1-3 سایر استراتژی های موجود   …………………………………………………..   18

 

2-3 حملات در لایه ی MAC   ………………………………………………………………

 

1-2-3 تقسیم بندی حملات در لایه ی MAC   ………………………………………….

 

1-1-2-3 حملات نقض احراز هویت/نقض برقرای ارتباط   …………………………   18

 

2-1-2-3 حمله ی مدت زمان تورمی   …………………………………………………..   19

 

3-1-2-3 حمله بر علیه i802.11   …………………………………………………………….

 

4-1-2-3 حمله بر علیه گره های به خواب رفته   …………………………………..   19

 

5-1-2-3 حملات لایه ی MAC کامل   ………………………………………………….   19

 

2-2-3 مقابله در لایه ی MAC   …………………………………………………………..

 

1-2-2-3 شناسایی شنود آدرس MAC   ……………………………………………….

 

2-2-2-3 محافظت از فریم های کنترلی و مدیریتی از طریق رمز نگاری   …….   20

 

3-2-2-3 تعمیر پروتکل   ………………………………………………………………….   21

 

4-2-2-3 پازل رمز نگاری شده (کاربر)   ………………………………………………   21

 

5-2-2-3 سایر راه حل های رمز نگاری نشده   ………………………………………   21

 

3-3 حملات DOS به شبکه های 802.11، شامل لایه ی MAC و لایه های بالاتر….   22

 

1-3-3 اقدامات متقابل   ………………………………………………………………….   23

 

1-1-3-3 فیلترینگ   …………………………………………………………………………   23

 

2-1-3-3 سیستم های شناسایی نفوذ   …………………………………………………   23

 

4-3 اقدامات متقابل در لایه ی MAC با استفاده از لایه ی فیزیکی   …………..   23

 

1-4-3 شناسایی ایستگاه از طریق ویژگی های سیگنال   ………………………….   24

 

4- نتیجه گیری   ………………………………………………………………………..   25

 

5- مراجع   ……………………………………………………………………………………   27

 

چکیده:

 

در این سمینار به، شناخت، شناسایی و شیوه های کاهش اثرات حملات DOS در شبکه های بی سیم پرداخته شده است. کاهش اثرات و شناسایی حملات DOS عملیات دشواری خواهد بود، چرا که گره های مجاز نیز می توانند بسته های زیادی را در مدتی کوتاه تولید نمایند. دشواری تشخیص تمایز میان گره های غیر مجاز (حمله کننده یا تحت تاثیر حمله ی DOS) و مجاز و نیز دشواری در یافتن گره های غیرمجاز، همیشه سبب می گردد تا روش ها و راهکارهای شناسایی و کاهش اثرات حملات DOS به کارایی رضایت بخش و کاملی نائل نگردند. شبکه های بی سیم به دلیل ماهیت فیزیکی و پروتکل های ارتباطی به شدت در معرض حملات DOS قرار دارند. در این زمینه شبکه های بی سیم بدون زیرساخت پایدار[1]، پتانسیل بیشتری برای مواجهه با حملات DOS خواهند داشت. می توان دو نوع از حملات مهم DOS را در این شبکه ها نام برد، حملات مسیریابی و حملات ترافیکی؛ این حملات اهدافی نظیر اختلال در مسیریابی و غرق نمودن شبکه در ترافیک را، پی می گیرند، که یکی از راهکار های مقابله می تواند ایزوله نمودن گره های دخیل در حمله باشد. شبکه های بی سیم متمرکز[2] نیز به دلیل فیزیک بی سیم خود پتانسیل بیشتری برای حملات نسبت به شبکه های سیمی دارند. حملات در این شبکه ها می تواند از، لایه ی فیزیکی، لایه ی پیوند داده[3] یا لایه ی شبکه انجام شود. معروف ترین ابزار حملات DOS در شبکه های متمرکز، مسدود کننده های رادیویی[4]، ابزار سوء استفاد از نقاط ضعف مکانیسم CSMA/CA، حملات Deauth[5]، حملات سیاه چاله[6]، چاله ی خاکستری[7]، کرم چاله[8]، حملات تغریق و … می باشد. مقالات و تحقیقات بسیاری در زمینه ی روش های شناسایی و کاهش آسیب های این گونه حملات انجام گرفته است که می توان برخی از آن ها را نام برد؛ کنترل تراکم تجمیعی[9]، پازل تراکم[10]، ذخیره[11]، شیوه ی ارائه شده توسط مارتی و همکاران[12]، روش ارائه شده ی Zhu و دیگران[13]، پروتکل های مبتنی بر شهرت (اعتبار) [14]، راهکار ارائه شده ی M.Just[15]و پروتکل مسیریابی دوطرفه که برای حملات DDOS در لایه ی شبکه[16]، توسعه داده شده است. در بررسی های این سمینار سعی بر این بوده است تا جدیدترین حملات DOS در انواع شبکه های بی سیم، به وضوح مورد کنکاو قرار گرفته و راهکار های جدید و موثر شناسایی، مقابله و کاهش اثرات با بیان نقاط قوت و ضعف به تفکیک تشریح گردد، تا دیدگاهی روشن بر حفره های امنیتی پروتکل ها و زیر ساخت این تکنولوژی به دست آید.

 

1- تشریح مسئله

 

ظهور شبکه های بی سیم، مجموعه ای از مشکلات امنیتی را به همراه آورد. سهولت استفاده و قیمت های پایین شبکه های مبتنی بر 802.11 سبب گسترش وسیع استفاده از آن شده است، اما در گسترش شبکه های بی سیم، در درجه ی اول باید آسیب پذیری های مربوط به دسترسی غیر مجاز و نقض محرمانگی رسیدگی گردد]2 [. واسط انتقال که توسط همه ی کاربران شبکه به اشتراک گذاشته می شود، راهی جذاب برای حملات به سرویس های بی سیم را ارائه می کند]2,8,9[. شبکه های بی سیم به دلیل طبیعت داده پراکنی خود، نسبت به حملات DOS آسیب پذیرند. حملات DOS گونه از حملات هستند که قابلیت دسترسی را هدف قرار می دهند و تلاش می کنند از دسترسی کاربران مجاز به شبکه جلوگیری نمایند]4[.

 

تجهیزات تخصصی و یا مهارت های بالای خاصی برای از کار انداختن شبکه های بی سیم از طریق حمله ی DOS نیاز نیست، تعداد زیادی آسیب پذیری در 802.11 وجود دارد که در سال های اخیر به صورت تجربی نشان داده شده است]4[.

 

1-1 انواع فریم در شبکه های 802.11]4[

 

سه نوع فریم (بسته) در شبکه های 802.11 وجود دارد: فریم های مدیریتی، کنترلی و داده. هر نوع فریم شامل زیر فریم هایی نیز می شود. فریم های مدیریتی برای مدیریت شبکه و پذیرش کنترل، به کار گرفته می شوند، فریم های کنترلی برای کنترل دسترسی و فریم های داده برای حمل داده به کار می روند. در حملات DOS از فریم های مدیریتی خاصی استفاده می گردد]4[. بنابراین در بین این سه نوع فریم، فریم های مدیریتی بیشتر مورد بررسی قرار خواهند گرفت.

 

[1] – ad-hoc

 

[2] – centralized networks

 

[3] – Data Link Layer (MAC)

 

[4] – RF Jammers

 

[5] – Deauthentication Attacks

 

[6] – Blackhole attack  

 

[7] – Greyhole attack

 

 

[8] – Wormhole attack

 

[9] – The Aggregate-based Congestion Control (ACC) was proposed by R. Mahajan, S. Bellovin, S. Floyd, J.Ioannidis, V. Paxson, and S. Shenker

 

[10] – Congestion Puzzles (CP) was proposed by X. Wang, M.K. Reiter

 

[11] – Save was proposed by J. Li, J. Mirkovic, and M. Wang

 

[12] – S. Marti, T.J. Giuli, K. Lai, and M. Baker

 

[13] – Hop-by-hop Authentication proposed by S. Zhu, S. Setia, S. Jajodia, and P. Ning

 

[14] – CONFIDANT proposed by S. Buchegger and J.Y. Le Boudec,SORI proposed by Q. He, D. Wu, and P. Khosla, Catch proposed by Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan

 

[15] – M. Just, E. Kranakis, and T. Wan

 

[16] – Network Layer (IP)در این سمینار به، شناخت، شناسایی و شیوه های کاهش اثرات حملات DOS در شبکه های بی سیم پرداخته شده است. کاهش اثرات و شناسایی حملات DOS عملیات دشواری خواهد بود، چرا که گره های مجاز نیز می توانند بسته های زیادی را در مدتی کوتاه تولید نمایند. دشواری تشخیص تمایز میان گره های غیر مجاز (حمله کننده یا تحت تاثیر حمله ی DOS) و مجاز و نیز دشواری در یافتن گره های غیرمجاز، همیشه سبب می گردد تا روش ها و راهکارهای شناسایی و کاهش اثرات حملات DOS به کارایی رضایت بخش و کاملی نائل نگردند. شبکه های بی سیم به دلیل ماهیت فیزیکی و پروتکل های ارتباطی به شدت در معرض حملات DOS قرار دارند. در این زمینه شبکه های بی سیم بدون زیرساخت پایدار[1]، پتانسیل بیشتری برای مواجهه با حملات DOS خواهند داشت. می توان دو نوع از حملات مهم DOS را در این شبکه ها نام برد، حملات مسیریابی و حملات ترافیکی؛ این حملات اهدافی نظیر اختلال در مسیریابی و غرق نمودن شبکه در ترافیک را، پی می گیرند، که یکی از راهکار های مقابله می تواند ایزوله نمودن گره های دخیل در حمله باشد. شبکه های بی سیم متمرکز[2] نیز به دلیل فیزیک بی سیم خود پتانسیل بیشتری برای حملات نسبت به شبکه های سیمی دارند. حملات در این شبکه ها می تواند از، لایه ی فیزیکی، لایه ی پیوند داده[3] یا لایه ی شبکه انجام شود. معروف ترین ابزار حملات DOS در شبکه های متمرکز، مسدود کننده های رادیویی[4]، ابزار سوء استفاد از نقاط ضعف مکانیسم CSMA/CA، حملات Deauth[5]، حملات سیاه چاله[6]، چاله ی خاکستری[7]، کرم چاله[8]، حملات تغریق و … می باشد. مقالات و تحقیقات بسیاری در زمینه ی روش های شناسایی و کاهش آسیب های این گونه حملات انجام گرفته است که می توان برخی از آن ها را نام برد؛ کنترل تراکم تجمیعی[9]، پازل تراکم[10]، ذخیره[11]، شیوه ی ارائه شده توسط مارتی و همکاران[12]، روش ارائه شده ی Zhu و دیگران[13]، پروتکل های مبتنی بر شهرت (اعتبار) [14]، راهکار ارائه شده ی M.Just[15]و پروتکل مسیریابی دوطرفه که برای حملات DDOS در لایه ی شبکه[16]، توسعه داده شده است. در بررسی های این سمینار سعی بر این بوده است تا جدیدترین حملات DOS در انواع شبکه های بی سیم، به وضوح مورد کنکاو قرار گرفته و راهکار های جدید و موثر شناسایی، مقابله و کاهش اثرات با بیان نقاط قوت و ضعف به تفکیک تشریح گردد، تا دیدگاهی روشن بر حفره های امنیتی پروتکل ها و زیر ساخت این تکنولوژی به دست آید.

 

[1] – ad-hoc

 

[2] – centralized networks

 

[3] – Data Link Layer (MAC)

 

[4] – RF Jammers

 

2-1-1-    اشكال مختلف طراحی………………………………. 51

 

2-2-  دسته بندی مسائل پوشش در شبکه های حسگر………………. 52

 

2-2-1-   پوشش ناحیه ای………………………………. 53

 

2-2-2-   پوشش نقطه ای……………………………. 56

 

2-2-3-  پوشش مرزی……………………………. 57

 

2-3-  روش پوشش CCP………………………………

 

2-3-1-   فرضیات مسئله……………………………… 59

 

2-3-2-  تشریح روش……………………………. 59

 

2-4-  حل مسئله پوشش(k-پوششی ) با استفاده از آتوماتاهای یادگیر………….. 61

 

2-4-1-   فرضیات و مدل مسئله……………………………… 63

 

2-4-2-   روش تشخیص افزونه بودن نود حسگر…………………………….. 64

 

2-4-3-  شبیه سازی ……………………………. 72

 

2-5-  جمع بندی……………………………. 79

 

3-  خوشه بندی در شبکه های حسگر بی سیم با استفاده از آتوماتاهای یادگیر سلولی….. 80

 

3-1-  مقدمه……………………………. 80

 

3-2-  کارهای انجام شده…………………………….. 83

 

3-2-1-   پروتکل خوشه بندی LEACH………………………………

 

3-2-2-  پروتکل خوشه بندی HEED………………………………

 

3-3- خوشه بندی در شبکه های حسگر بی سیم با استفاده از آتوماتاهای یادگیر سلولی….. 93

 

3-3-1-   روش خوشه بندی پیشنهادی………………………………. 94

 

3-3-2-  شبیه سازی……………………………. 102

 

3-4-  جمع بندی …………………………….107

 

4-  تجمیع داده ها در شبكه های حسگر با استفاده از آتوماتاهای یادگیر……. 108

 

4-1-   مقدمه……………………………. 108

 

4-2-  كارهای انجام گرفته…………………………….. 109

 

4-3-  تجمیع داده ها در شبكه های حسگر با استفاده از آتوماتاهای یادگیر….. 112

 

4-3-1-   بیان مسئله و مفروضات آن……………………………… 113

 

4-3-2-  تشریح روش پیشنهادی………………………………. 115

 

4-4-  شبیه سازی…………………………….119

 

4-4-1-   آزمایش اول……………………………. 122

 

4-4-2-   آزمایش دوم ……………………………. 122

 

4-4-3-  آزمایش سوم……………………………. 123

 

4-5-  جمع بندی ……………………………. 125

 

5-  نتیجه گیری……………………………… 126

 

6-  پیوست اول: شبكه های حسگر بی سیم……………………………… 127

 

6-1-   تاریخچه شبكه های حسگر…………………………….. 127

 

6-2-  ساختار هر گره حسگر…………………………….. 128

 

6-2-1-   اجزاء درونی یک گره حسگر…………………………….. 128

 

6-2-2-   محدودیتهای سختافزاری یک گره حسگر…………………………….. 130

 

6-3-  پشته پروتکلی  ……………………………. 131

 

6-4-  مزایای شبکه های حسگر بیسیم……………………………… 132

 

6-5-  کاربردهای شبکه های حسگر بیسیم……………………………… 134

 

7-  پیوست دوم:آتوماتای یادگیرسلولی……………………………… 138

 

7-1-  تاریخچه آتوماتای یادگیر…………………………….. 138

 

7-2-  معیار‌های رفتار اتوماتای یادگیر…………………………….. 139

 

7-3- آتوماتای یادگیر با عملهای متغیر…………………………….. 141

 

7-4-  آتوماتای یادگیر تعقیبی……………………………… 142

 

7-5-  آتوماتای یادگیر سلولی (CLA)……………………………..

 

7-6-  آتوماتای یادگیر سلولی باز(OCLA)……………………………..

 

7-7- آتوماتای یادگیر سلولی ناهمگام (ACLA)……………………………..

 

8-  پیوست سوم: شرح نرم افزار J-Sim و پیاده سازی الگوریتمهای پیشنهادی با آن…… 155

 

8-1-  مقدمه ……………………………. 155

 

8-2-  شبیه ساز J-Sim …………………………….

 

 

8-2-1-   شبیه سازی شبکه های حسگر بی سیم با استفاده از J-sim……………………………….

 

8-2-2-  نصب و اجرا…………………………….162

 

8-3- پیاده سازی الگوریتم خوشه بندی پیشنهادی………………… 163

 

8-4-  پیاده سازی الگوریتم پوشش پیشنهادی…………………….. 185

 

8-5-  پیاده سازی الگوریتم تجمیع پیشنهادی……………………………… 190

 

9-  واژه نامه…………………………….. 195

 

مراجع…………………………….. 199

 

چکیده:

 

کیفیت سرویس در شبکه های حسگر بی سیم نسبت به شبکه های سنتی بسیار متفاوت است. بعضی از پارامترهایی که در ارزیابی کیفیت سرویس در این شبکه ها مورد استفاده قرار می گیرند عبارتند از: پوشش شبکه, تعداد بهینه نودهای فعال در شبکه, طول عمر شبکه و میزان مصرف انرژی. در این پایان نامه سه مسئله اساسی شبكه ها ی حسگر بی سیم مطرح گردیده و با هدف بهبود پارامترهای کیفیت سرویس، برای این مسائل، راه حلهایی کارا با استفاده از روش هوشمند آتوماتاهای یادگیرسلولی ارائه شده است. ابتدا مسئله پوشش محیط در شبكه های حسگر را با استفاده از غیر فعال نمودن نودهای غیر ضروری و فعال نگه داشتن بهینه نودها حل می گردد، تا در مصرف انرژی صرفه جویی به عمل آمده و عمر شبکه افزایش یابد. سپس به مسئله خوشه بندی در شبکه حسگر پرداخته شده و با استفاده از آتوماتاهای یادگیرسلولی, شبکه های حسگر به گونه ای خوشه بندی می شوند که انرژی به صورت یکنواخت در شبکه بمصرف رسیده وعمر شبکه افزایش یابد. پس از آن با استفاده از آتوماتاهای یادگیر یک روش تجمیع داده های محیط حسگری پیشنهاد می گردد که در مصرف انرژی شبکه صرفه جویی به عمل آورده و عمر شبکه را افزایش می دهد. همه روشهای ارائه شده با استفاده از نرم افزار J-Sim شبیه سازی گردیده اند. نتایج شبیه سازی ها نشان دهنده عملکرد بهتر روشهای پیشنهادی نسبت به روشهای مشابه می باشد.

 

1- مقدمه

 

1-1- شبکه های حسگر بیسیم

 

شبكه های حسگر بی سیم[1] جهت جمع آوری اطلاعات در مناطقی كه كاربر نمی تواند حضورداشته باشد، مورد استفاده قرار می گیرند. در یك شبكه حسگر، حسگرها به صورت جداگانه مقادیر محلی را نمونه برداری (اندازه گیری) می كنند و این اطلاعات را درصورت لزوم برای حسگرهای دیگر و در نهایت برای مشاهده گر اصلی ارسال می نمایند. عملكرد شبكه این است كه گزارش پدیده هایی راكه اتفاق می افتد به مشاهده گری بدهد كه لازم نیست از ساختار شبكه و حسگرها به صورت جداگانه و ارتباط آنها چیزی بداند. این شبکه ها مستقل و خودگردان بوده وبدون دخالت انسان کار می کنند. معمولا تمامی گره­ها همسان می­باشند و عملاً با همکاری با یكدیگر، هدف كلی شبكه را برآورده می‌سازند. هدف اصلی در شبکه­های حسگر بی­سیم نظارت و کنترل شرایط و تغییرات جوی، فیزیکی و یا شیمیائی در محیطی با محدوده معین، می­باشد[1, 2]. شبکه­ حسگر بی­سیم نوع خاصی از شبکه­های موردی[2] است. مبحث شبکه های حسگر بی سیم یکی از موضوعات جدید در زمینه مهندسی شبکه و فناوری اطلاعات می باشد.

 

پیشرفتهای اخیر در طراحی و ساخت تراشه های تجاری این امكان را به وجود آورده است كه عمل پردازش سیگنال و حس كنندگی در یك تراشه یعنی حسگر شبكه بی سیم انجام گردد، كه شامل سیستم های میكروالكترومكانیكی [3](MEMS) مانند حسگرها، محرک ها[4] و قطعات رادیویی RF می باشد.

 

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

 

در شبكه های بی سیم حسگر معمولا فقط یك یا دو ایستگاه پایه‌ وجود دارد و تعداد زیادی نودهای حسگر در محیط پخش گردیده اند. به علت محدودیت برد این حسگرها و انرژی باطری خیلی از نودها قادر به ارتباط مستقیم با ایستگاه پایه‌ نمی باشند. اما با تكیه بر نودهای نظیر خود و نودهای حسگر دیگر، به ارتباط با ایستگاه پایه‌ می پردازد كه در شبكه های [5]MANET نیز این عمل توسط نودهای معمولی انجام می شود.

 

معماری ارتباطات شبکه­های حسگر بی­سیم در شکل 1-1 دیده می­شود[1]. در شبکه­های حسگر بی­سیم، تعداد زیادی گره با امکانات مخابره، پردازش، حس کردن محیط و … در محیطی با چهارچوب معین پراکنده شده­اند. رویداد اتفاق افتاده و یا سوالات پرسیده شده از سوی گره مرکزی[6] و ماموریت محوله به هر گره موجب می­شود، ارتباطاتی بین گره­ها برقرار شود. اطلاعات رد و بدل شده می‌تواند گزارشی از وضیعت محدوده ای كه زیر نظر گره­های حسگر می­باشد به گره مرکزی و یا درخواستی از سمت گره مرکزی به سمت گره­های حسگر باشد. گره مرکزی به عنوان درگاه ارتباطی شبکه حسگر با سایر سیستم­ها و شبکه­های مخابراتی، در واقع گیرنده نهایی گزارش از گره­های حسگر می­باشد و بعد از انجام یکسری پردازش­ها، اطلاعات پردازش شده را به کاربر ارسال می­کند (با استفاده از یک رسانه ارتباطاتی مانند اینترنت، ماهواره و …). از سوی دیگر، درخواست­های کاربر نیز توسط این گره به شبکه انتقال می­یابد.

 

یك گره حسگر می‌تواند یكی از دو نقش تولید كننده داده‌ها و یا رله كننده داده‌های تولید شده توسط سایر گره‌ها را بر عهده بگیرد. عموماً در شبكه‌های حسگر، اغلب گره‌ها هر دو نقش را به صورت توأم ایفا می‌كنند. برپایی و طراحی ساختار و معماری ارتباطات بین گره­های شبکه نیازمند رعایت فاکتورهای مختلف و زیادی از جمله تحمل­پذیری خطا، مقیاس پذیری، هزینه تولید، محیط عملیات، توپولوژی شبکه حسگر، محدودیت­های سخت افزاری، ابزار و رسانه ارتباط، انرژی مصرفی و … می­باشد. جهت آشنایی بیشتر با شبکه های حسگر بی سیم به پیوست اول مراجعه گردد.

 

1-1-1- مسائل مطرح در شبکه های حسگر بیسیم

 

عوامل متعددی در طراحی شبکه­های حسگر موثر است و موضوعات بسیاری در این زمینه مطرح است که بررسی تمام آنها در این نوشتار نمی­گنجد از این رو تنها به ذکر برخی از آنها بطور خلاصه اکتفا می­کنیم.

 

1-مسیریابی: ماهیت اصلی شبکه­های حسگر به این صورت است که کارهایی که انجام می­دهند باید به صورت محلی باشد چرا که هر گره تنها می­تواند با همسایه ­های خود ارتباط برقرار کند و اطلاعات کلی و سراسری از شبکه چندان در دسترس نیست (جمع­آوری این اطلاعات هزینه و زمان زیادی را مصرف می­کند). اطلاعات بدست آمده توسط گره ­ها، باید با استفاده از تکنیک­های مسیریابی، به نحوی به گره مرکزی ارسال گردد.

 

2- تنگناهای سخت­ افزاری: هرگره ضمن اینكه باید كل اجزاء لازم را داشته باشد باید بحد كافی كوچك، سبك و كم حجم نیز باشد. در عین حال هر گره باید انرژی مصرفی بسیار كم و قیمت تمام شده پایین داشته و با شرایط محیطی سازگار باشد. اینها همه محدودیت­هایی است كه كار طراحی و ساخت گره‌های حسگر را با چالش مواجه می­كند. ارائه طرح­های سخت­افزاری سبک و کم حجم در مورد هر یک از اجزای گره بخصوص قسمت ارتباط بی­سیم و حسگرها از جمله موضوعات تحقیقاتی است که جای کار بسیار دارد. پیشرفت فن­آوری ساخت مدارات مجتمع با فشردگی بالا و مصرف پایین، نقش بسزایی در كاهش تنگناهای سخت­افزاری داشته است.

 

3- تحمل­پذیری خطا و قابلیت اطمینان[1]: هر گره ممكن است خراب شود یا در اثر رویدادهای محیطی مثل تصادف یا انفجار بكلی نابود شود یا در اثر تمام شدن منبع انرژی از كار بیفتد. منظور از تحمل‌پذیری یا قابلیت اطمینان این است كه خرابی گره­ها نباید عملكرد كلی شبكه را تحت تاثیر قرار دهد. در واقع می­خواهیم با استفاده از اجزای غیر قابل اطمینان یك شبكه قابل اطمینان بسازیم.

 

4- توپولوژی: توپولوژی شبکه یکی از مفاهیم اولیه در شبکه­های حسگر است که دیگر موارد نظیر مسیریابی و … بر روی آن تعریف می­شود. ساختارهای زیادی در توپولوژی مطرح است که بر اساس اولویت­های مختلف و در شرایط متفاوت یکی بر دیگری برتری دارد. از جمله مواردی که در انتخاب یک ساختار تاثیر می­گذارد می­توان به مصرف انرژی کمتر، تنک بودن ساختار، کم بودن درجه گره، تحمل­پذیری خطا و تداخل اشاره کرد.

 

5- مقیاس­پذیری[2]: شبكه باید هم از نظر تعداد گره و هم از نظر میزان پراكندگی گره­ها مقیاس­پذیر باشد. بعبارت دیگر شبكه حسگر از طرفی باید بتواند با تعداد صدها، هزارها و حتی میلیون­ها گره كار كند و از طرف دیگر، چگالی توزیع متفاوت گره­ها را نیز پشتیبانی كند. در بسیاری كاربردها توزیع گره­ها تصادفی صورت می­گیرد و امكان توزیع با چگالی مشخص و یكنواخت وجود ندارد یا گره­ها در اثر عوامل محیطی جابجا می­شوند. بنابراین چگالی باید بتواند از چند عدد تا چند صد گره تغییر كند. موضوع مقیاس­پذیری به روش­ها نیز مربوط می­شود برخی روش­ها ممكن است مقیاس­پذیر نباشند یعنی در یك چگالی با تعداد محدود از گره كار كند. در مقابل برخی روش­ها مقیاس­پذیر هستند.

 

6- شرایط محیطی: طیف وسیعی از كاربرد­های شبكه ­های حسگر مربوط به محیط­هایی می­شود كه انسان نمی­تواند در آن حضور داشته باشد. مانند محیط­های آلوده از نظر شیمیایی، میكروبی، هسته­ای و یا مطالعات در كف اقیانوس­ها و فضا و یا محیط­های نظامی به علت حضور دشمن و یا در جنگل و زیستگاه جانوران كه حضور انسان باعث فرار آنها می­شود. در هر مورد، شرایط محیطی باید در طراحی گره­ها در نظر گرفته شود مثلا در دریا و محیط­های مرطوب گره حسگر در محفظه­ای كه رطوبت را منتقل نكند قرار می‌گیرد.

 

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

 

8- افزایش طول­ عمر شبكه: طول­عمر گره­ها بعلت محدودیت انرژی منبع تغذیه كوتاه است. علاوه بر آن در برخی مواقع، موقعیت ویژة یك گره در شبكه مشكل را تشدید می­كند. مثلاً گره­ای كه در فاصله یك قدمی گره مرکزی قرار دارد از یك طرف بخاطر بار كاری زیاد خیلی زود انرژی خود را از دست می­دهد و از طرفی از كار افتادن آن باعث قطع ارتباط گره مرکزی با كل شبكه و در نتیجه موجب از كار افتادن شبكه می­شود. مشكل تخلیه زود هنگام انرژی در مورد گره­های نواحی كم تراكم در توزیع غیر یكنواخت گره­ها نیز صدق می­كند در اینگونه موارد داشتن یك مدیریت انرژی در داخل گره­ها و ارائه راه­حل­های انرژی­آگاه بطوری كه از گره­های بحرانی كمترین استفاده را بكند مناسب خواهد بود. با توجه به مطالب بیان شده تمام الگوریتم­ها و تکنیک­های مورد استفاده در شبکه­های حسگر به انرژی بعنوان یک محدودیت جدی نگاه می­کنند و سعی می­کنند با آگاهی از سطح انرژی مصرفی عمل کنند تا کمترین انرژی مصرف گردد و در نتیجه افزایش طول­عمر شبکه حسگر را به دنبال داشته باشد.

 

2-6- الگوها و مدلهای سنجش رضایت‌مندی در مدیریت مؤثر ارتباط با مشتری……………………. 28

 

2-7- فنآوریهای مدرن و به روز و مدیریت ارتباط با مشتری……………………………………………. 30

 

2-8- فناوری اطلاعات و بهره‌وری بنگاههای اقتصادی و بهبود CRM………………………………… 33

 

2-9- مدیریت دانش و مدیریت ارتباط با مشتری………………………………………………………….. 38

 

2-10- مدیریت دانش مشتری در راستای حفظ و وفاداری مشتری…………………………………….. 45

 

2-11- مدیریت ارتباط و تمركز بر مشتریان كلیدی………………………………………………………… 46

 

2-12- پیشینه تحقیق………………………………………………………………………………………………. 49

 

 فصل سوم: روش تحقیق (متدولوژی)

 

3-1- مقدمه…………………………………………………………………………………………………………. 54

 

3-2- روش تحقیق ……………………………………………………………………………………………….. 55

 

3-3- جامعه آماری………………………………………………………………………………………………… 55

 

3-4- حجم نمونه و روش اندازه‌گیری………………………………………………………………………… 55

 

3-5- روش گردآوری اطلاعات………………………………………………………………………………… 55

 

3-6- ابزار جمع‌آوری اطلاعات ……………………………………………………………………………….. 55

 

3-7-روائی و پایائی ابزار سنجش………………………………………………………………………………. 56

 

3-8- روش تجزیه و تحلیل داده‌ها …………………………………………………………………………… 57

 

فصل چهارم: تجزیه و تحلیل داده‌های تحقیق  

 

4-1- مقدمه ………………………………………………………………………………………………………… 72

 

4-2- بخش توصیفی پرسشنامه ………………………………………………………………………………… 73

 

4-3- توصـیف آماری شاخصهای مركزی و پراكندگی متغیرهای تحقیق………………………………. 75

 

4-4- آزمون كولموگوروف ـ اسمیرنوف برای تعیین نرمال بودن توزیع متغیرهای تحقیق………….. 78

 

4-5- تجـزیه و تحلیل استنباطی داده‌های آماری (آزمون فرضیه‌های تحقیق)…………………………. 79

 

 

فصل پنجم: نتیجه‌گیری و پیشنهادات    

 

5-1- مقدمه…………………………………………………………………………………………………………. 84

 

5-2-نتیجه‌گیری…………………………………………………………………………………………………….. 85

 

5-3- پیشنهادات ………………………………………………………………………………………………….. 85

 

5-4- محدودیتهای تحقیق ………………………………………………………………………………………. 87

 

منابع و مأخذ………………………………………………………………………………………………………… 72

 

چكیده

 

مدیریت ارتباط با مشتری یكی از دستاوردهای عصر اطلاعات و دانش است و با توجه به ویژگیهای آن، امروزه سازمانها با جدیت به دنبال بهره‌مندی از نتایج آن هستند. تحقیق حاضر با هدف بررسی عوامل مؤثر بر استقرار فرایند مدیریت ارتباط با مشتری در بانک کشاورزی شهرستان اردبیل انجام پذیرفته است. جامعة آماری تحقیق حاضر شامل کلیة كاركنان مدیریت شعب بانک كشاورزی شهرستان اردبیل بوده كه از مجموع پرسشنامه‌های منتشره (49 نفر جامعة آماری)، به دلیل عدم حضور برخی مسئولین و در مواردی عدم همكاری از سوی برخی از آنها از یك سو و وجود برخی پرسشنامه‌های ناقص از سوی دیگر موجب گردید كه در كل تعداد 44 پرسشنامه گردآوری و مورد تجزیه و تحلیل قرار گیرد. ابزار جمع‌آوری اطلاعات پرسشنامه استاندارد نیلوسن (1996) بوده و برای تجزیه و تحلیل داده‌ها از آمارة آزمون t بهره گرفته شده است. نتایج حاصل از آزمون متغیرهای تحقیق نشان داد كه تمرکز بر مشتریان اصلی و کلیدی، توجه به مدیریت دانش، برخورداری از فناوری مدرن و به روز و سازماندهی فرایندهای کسب و کار در استقرار مدیریت ارتباط با مشتری در بانک کشاورزی تأثیر می‌گذارد.

 

2-1- محاسبات ابری………………………………………………………………………… 29

 

2-2- مجازی سازی…………………………………………………………………………… 30

 

2-3- مدیریت انرژی در مرکز داده اینترنت IDC………………………………………..

 

2-4- مدیریت انرژی ماشین مجازی و مهاجرت……………………………………. 32

 

2-5- الگوریتم MBFD……………………………………………………………………

 

2-6- الگوریتم ST…………………………………………………………………………

 

2-7- الگوریتم MM………………………………………………………………………

 

2-8- الگوریتم هریسانه……………………………………………………………………. 41

 

2-9- الگوریتمMEF(تغییر اولین تناسب)……………………………………………. 42

 

2-10- نتیجه گیری……………………………………………………………………….. 43

 

فصل سوم- ارائه الگوریتم پیشنهادی

 

3-1- مقدمه………………………………………………………………………………… 45

 

3-2- الگوریتم پیشنهادی……………………………………………………………….. 45

 

فصل چهارم- نتایج شبیه سازی

 

4-1- مقدمه……………………………………………

 

4-2- ویژگی های شبیه سازی تخصیص و مهاجرت ماشین های مجازی… 55

 

4-3- نرم افزار متلب…………………………………………………………………… 59

 

4-4- نتایج شبیه سازی………………………………………………………………… 61

 

4-5- نتیجه گیری……………………………………………………………………….. 66

 

فصل پنجم- نتیجه گیری و پیشنهادات

 

5-1- نتیجه گیری………………………………………………………………………. 68

 

5-2- کار آینده…………………………………………………………………………….. 68

 

چکیده:

 

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

 

راه حل های مجازی سازی به طور گسترده ای برای حل مشکلات مختلف مراکز داده مدرن بکار می روند که شامل : استفاده کمتر از سخت افزار، استفاده بهینه از فضای مراکز داده , مدیریت بالای سیستم و هزینه نگهداری می شوند.

 

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

 

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

 

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

 

در این پایان نامه تمرکز ما روی زمانبندی مهاجرت ماشین های مجازی در مرکز داده ابر با استفاده از الگوریتم وراثتی می باشد . نتایج شبیه سازی موید امکان پذیری و کارایی این الگوریتم زمانبندی می باشد و منجر به کاهش قابل توجه مصرف انرژی کل در مقایسه با استراتژی های دیگر می شود.و از آنجا که تمرکز ما روی انرژی عملیاتی مراکز داده است با کاهش مصرف انرژی عملیاتی, تولید آلاینده زیستی کربن نیز کاهش یافته که در کاهش هزینه کاربر نقش بسزایی ایفا می کند.

 

مقدمه:

 

در سال 1969 Leonard Kleinrock [1]، یکی از دانشمندان ارشد شبکه اصلی پروژه های پیشرفته پژوهشی آژانس (ARPANET) که پایه گزار اینترنت است ، گفت : ” هم اکنون ، شبکه های رایانه ای هنوز در مراحل ابتدایی خود هستند ، اما هنگامیکه رشد کنند و پیچیده شوند ، ما احتمالا گسترش صنایع همگانی کامپیوتر ” را خواهیم دید که ، مانند برق و تلفن در حال حاضر ، که به منازل و دفاتر در کشور خدمات ارائه می کنند. این بینش از صنایع همگانی محاسبات بر اساس مدل تأمین کننده خدمات ,تحول عظیم از کل صنعت محاسبات در قرن 21 که به موجب آن خدمات کامپیوتری برحسب تقاضا[1] خواهد شد را پیش بینی می کند، مانند خدمات ابزار دیگر موجود در جامعه امروز به راحتی در دسترس است. به طور مشابه ، کاربران (مصرف کنندگان) تنها زمانی که به خدمات محاسبات فراهم کنندگان دسترسی داشته باشند به آنها پرداخت می کنند. علاوه بر این ، مصرف کنندگان دیگر نیازی به سرمایه گذاری زیادی در ساخت و نگهداری پیچیده زیرساخت های فناوری اطلاعات نخواهند داشت.
در چنین مدلی ، کاربران به خدمات مورد نیاز خود دسترسی می یابند بدون در نظر گرفتن اینکه آن خدمات میزبانی کجا هستند. از این مدل به عنوان محاسبات همگانی یا اخیرا محاسبات ابری[2] یاد می شود [2]. دومی نشان دهنده زیرساخت به عنوان یک “ابر” است که از آن کاربران می توانند برحسب تقاضا به برنامه های کاربردی به عنوان خدمات از هر نقطه جهان دسترسی یابند. از این رو ، محاسبات ابری را می توان به عنوان یک پارادایم جدید برای تأمین پویای خدمات کامپیوتری با حمایت مراکز داده معرفی کرد که معمولا تکنولوژی ماشین مجازی3 را برای تثبیت و اهداف محیط زیست بکار می گیرد.[3] .

 

تا همین اواخر ، تنها نگرانی , استقرار مراکز داده ابر با کارایی بالا بدون هیچ گونه توجهی به مصرف انرژی بوده است. مراکز داده به طور متوسط انرژی زیادی به اندازه 25000 خانوار مصرف می کنند[4]
بخش قابل توجهی از انرژی الکتریکی مصرف شده توسط منابع محاسباتی به گرما تبدیل می شود. دمای بالا منجر

 

 

 

 

 

 

به تعدادی از مشکلات ، مانند کاهش قابلیت اطمینان سیستم و در دسترس پذیری، و همچنین کاهش طول عمر دستگاه ها می شود.

 

مراکز داده ها فقط پرهزینه نیستند ، بلکه آسیبی جدی به محیط زیست نیز وارد می کند. کربن تولیدی این مراکز در حال حاضر بیش از کربن تولیدی یک کشور با تمام تاسیسات صنعتی است [5]. میزان کربن زیاد بخاطر حجم زیاد برق مورد نیاز برای خنک کردن سرورهای متعدد میزبان در مراکز داده ها است. ارائه دهندگان سرویس ابری برای اطمینان از این که سود شان به دلیل هزینه های بالای انرژی به طرز چشمگیری کاهش پیدا نکند ودرعین حال بتوانند خدمات را با کیفیت و سرعت بالاتری ارائه دهند همچنین باتوجه به افزایش فشار از سوی دولت های جهان به منظور کاهش میزان کربن ، که تاثیر قابل توجهی در تغییرات آب و هوایی دارد, نیاز به اتخاذ اقدامات لازم دارند. [6].

 

در این بین راه حلهای مجازی سازی , علاوه بر كاهش هزینه های انرژی در زیرساختهای مراكز داده ,به طرز چشمگیری بهره برداری و كارایی سرور را افزایش می دهد. مجازی سازی با استفاده از تکنیک مهاجرت ماشینهای مجازی ,با ادغام و موازنه بار بین سرورهای فیزیكی و اجرای ده برنامه كاربردی یا بیشتر ماشینهای مجازی برروی یك سرور x86 , می تواند منابع مجازی را با انعطاف زیاد بین سرور های فیزیکی منتقل کند [7].

 

کاری که در این تحقیق انجام می شود ارائه الگوریتم زمانبندی مهاجرت ماشین های مجازی جهت حل معضل انرژی و آلودگی در محیط محاسباتی ابراست.

 

فصل اول: کلیات

 

1-1- مقدمه

 

در این فصل مقدمه ای در مورد پیدایش شبکه محاسبات ابری و یکسری از بحث های کلی در مورد مجازی سازی[1] و مهاجرت ماشین های مجازی[2] در محیط ابر و الگوریتم ژنتیک[3] بیان شده است. در ادامه مروری بر ابر, آشنایی با مسائل و چالش های مهم موجود در ابر , ضرورت انجام این تحقیق و اهداف پژوهش آورده شده است. این فصل با خلاصه و نتیجه گیری از فصل و نیز تشریح ساختار پایان نامه به پایان رسیده است.

 

2-1- مروری بر محاسبات ابری

 

سیر تکاملی محاسبات به گونه ای است که می توان آن را پس از آب , برق , گاز و تلفن به عنوان عنصر اساسی پنجم فرض نمود.در چنین حالتی , کاربران سعی می کنند براساس نیازهایشان و بدون توجه به اینکه یک سرویس در کجا قرار دارد و یا چگونه تحویل داده می شود , به آن دسترسی یابند. نمونه های متنوعی از سیستم های محاسباتی ارائه شده است که سعی دارند چنین خدماتی را به کاربران ارائه دهند . برخی از این سیستم های محاسباتی عبارتند از : محاسبات خوشه ای[4], محاسبات شبکه ای[5] و اخیرا محاسبات انبوه[6] که از آن به عنوان محاسبات ابر یاد می شود. محبوبیت این سه رویکرد محاسباتی , از دید موتور جستجوی گوگل مورد ارزیابی قرار گرفته است که نتیجه آن در شکل 1-1 نمایش داده شده است و حاکی از آن است که محبوبیت محاسبات ابری , پس از ظهور مفاهیم اولیه آن در سال 2007 , با فاصله زیادی نسبت به سایر رویکردهای محاسباتی در حال افزایش است [8].

 

برای شناخت بهتر محاسبات ابری از دید زیرساخت , ابتدا نگاهی به سیر تکاملی سیستم های محاسباتی از ابتدا تاکنون می اندازیم تا بتوانیم جایگاه آن را در بین دیگر سیستم ها تشخیص دهیم . اگر کامپیوتر های اصلی[1] را بعنوان نسل اول سیستم های محاسباتی در نظر بگیریم , ما با یک سیستم بسیار بزرگ مواجه بودیم که کاربران از طریق یک پایانه[2] واحد به آن دسترسی پیدا می کردند. به مرور این سیستم ها کوچکتر شدند و با توان پردازشی بیشتر بصورت رایانه های شخصی در اختیار همه کاربران قرار گرفتند. سپس این امکان فراهم شد که با اتصال مجموعه ای از این سیستم های کوچک , شبکه ای با توان پردازشی بیشتر فراهم نمود تا پاسخگوی نیازهای پردازشی بیشتر و سنگین تر باشند.اما نیازهای پردازشی به شکل فزاینده ای درحال افزایش بودند و نیاز به سیستم های محاسباتی بزرگتر و قوی تر احساس شد. بنابراین تعداد زیادی از این شبکه ها بصورت اختصاصی در سرتاسر اینترنت به هم متصل شدند و شبکه محاسباتی گرید را بوجود آوردند. در این بین مشاهده شد که میلیون ها کاربر در اینترنت وجود دارند که در اکثر اوقات از تمام توان رایانه خود استفاده نمی کنند و سیستم محاسباتی دیگری شکل گرفت تا کاربرانی که تمایل داشته باشند , زمان های بیکار سیستم خود را برای کارهای محاسباتی عام المنفعه هدیه کنند. بنابراین تعداد بسیار زیادی منبع محاسباتی کوچک در شبکه ای تحت عنوان محاسبات داوطلبانه به هم پیوستند و توان پردازشی عظیمی بوجود آوردند .

 

3- پیشینه پژوهشی …………………………………………………………………………………….. 23

 

3-1 مقدمه ……………………………………………………………………………………………………………. 23

 

3-2 الگوریتم­های حریصانه ………………………………………………………………………………….. 23

 

3-3 الگوریتم­های تکاملی …………………………………………………………………………………….. 26

 

3-3-1 راه­کارهای مبتنی بر جستجوی محلی ………………………………………… 26

 

3-3-2 راه­کارهای جمعیت محور ……………………………………………………………. 28

 

3-4 جمع­بندی …………………………………………………………………………………………………… 31

 

4- الگوریتم­های پیشنهادی ………………………………………………………………………….. 33

 

4-1 مقدمه ……………………………………………………………………………………………………………. 33

 

4-2 فرضیات وتعاریف …………………………………………………………………………………………… 34

 

4-3 الگوریتم­ Asuffrage ……………………………………………………………………………………..

 

4-4 الگوریتم­ MaxSuffrage ………………………………………………………………………………..

 

4-5 الگوریتم توازن نسخه یک …………………………………………………………………………….. 38

 

4-6 الگوریتم توازن نسخه دو ………………………………………………………………………………. 40

 

4-7 الگوریتم ژنتیک و توازن بار ………………………………………………………………………….. 41

 

4-8 جمع­بندی ……………………………………………………………………………………………………… 46

 

5- نتایج حاصل از ارزیابی………………………………………………………………………………. 47

 

5-1 مقدمه ……………………………………………………………………………………………………………. 47

 

5-2 محک ارزیابی براون ……………………………………………………………………………………… 47

 

5-3 ارزیابی الگوریتم Asuffrage …………………………………………………………………………

 

5-4 ارزیابی الگوریتم MaxSuffrage ……………………………………………………………………

 

5-5 ارزیابی الگوریتم توازن نسخه یک …………………………………………………………………. 53

 

5-6 ازریابی الگوریتم توازن نسخه دو …………………………………………………………………… 54

 

5-7 ارزیابی الگوریتم ژنتیک به همراه توازن بار……………………………………………………. 55

 

5-8 پیشنهادات برای آینده …………………………………………………………………………………. 57

 

6- منابع ……………………………………………………………………………………………………… 58

 

چکیده:

 

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

 

1- مقدمه

 

1-1- مقدمه

 

کامپیوترهای امروزی مانند مغز انسان معمولا از بخش کوچکی از توانایی‌های خود استفاده می‌کنند و اغلب به‌ صورت غیرفعالند و منتظر اطلاعات ورودی می‌مانند. تصور کنید که اگر از منابع سخت‌افزاری این همه کامپیوتر غیرفعال استفاده شود و همه در یک کامپیوتر جمع شوند، چه دستگاه پرقدرتی خواهیم داشت. شبکه­های محاسباتی (گرید)[1] زمینه‌ای را فراهم آورده است که بتوان از منابع (کامپیوتری) سیستم‌های دیگر نیز استفاده نماییم. اغلب مسائل پیچیده علمی، مهندسی و تجارت احتیاج به میزان زیادی از منابع برای اجرا دارند، بهترین راه حل برای اینگونه مسائل استفاده از گرید می­باشد[1].

 

هدف شبکه­های محاسباتی (گرید) به اشتراک گذاشتن منابع کامپیوتری در نقاط مختلف جغرافیایی با مدیریت­های مختلف بین کاربران است. کاربران درخواست­های خود را پیوسته برای محیط گرید ارسال می­کنند و بخش مدیریت منابع[2] این کارها را به گره های محاسباتی[3] موجود در شبکه اختصاص می­دهد. به چگونگی تخصیص این درخواست­ها روی گره­های محاسباتی مختلف زمانبندی[4] می­گویند.

 

اعمال سیاست­های مختلف برای عملیات زمانبندی نتایج متفاوتی را خواهد داشت که این سیاست با توجه به اهداف مشخص شده برای گرید اتخاذ می­شوند. عملیات زمانبندی در سیاست­های مختلف از فاکتورهای متفاوتی برای تخصیص کارها روی منابع مختلف استفاده می­کند. امکان دارد یک فاکتور نقش تعیین کننده­ای در یکی از سیاست­ها داشته باشد ولی در سیاست دیگر اصلا به آن توجه نشود، از اینرو هدف هر الگوریتم بهینه کردن سیاست مورد نظر خود است.

 

 1-2 هدف از اجرای پایان نامه

 

 

با توجه به تاثیر بالای عملیات زمانبندی در عملکرد بهینه گرید و مزایایی که برای گرید در قسمت قبل ذکر شد، ارائه یک روش کارا در زمانبندی می تواند تاثیر زیادی در حل مسائل بزرگ در شاخه های مختلف داشته باشد.

 

در گریدهای محاسباتی هدف بالا بردن درصد استفاده از منابع در کنار کاهش زمان اتمام آخرین کار می­باشد. در این طرح تحقیق همین اهداف را دنبال می­کنیم و سعی داریم نگاشتی از کارها را ارائه دهیم که هم باعث بالا رفتن بهره­وری از منابع شود و هم کمترین زمان را برای اتمام آخرین کار داشته باشد.

 

1-3 مراحل انجام پایان نامه

 

برای انجام پایان­نامه ابتدا مفاهیم گرید و روش­های موجود مطالعه و بررسی شدند و بعد از مقایسه صورت گرفته روی روش­های مختلف، الگوریتم ژنتیک برای تولید نگاشت انتخاب شد. در کنار الگوریتم ژنتیک الگوریتمی را ارائه کردیم که به توازن بار روی منابع کمک می­کند و با استفاده از مزایای دو الگوریتم نام برده شده نگاشت بهینه­ای را برای کارها بدست آوردیم. برای پیاده­سازی الگوریتم­ها از زبان برنامه نویسی java شده است.

 

 1-4 ساختار پایان نامه

 

در فصل دوم الگوریتم ژنتیک، پارامترهای موثر در این الگوریتم و مفاهیم اولیه­ی زمانبندی مورد بررسی قرار می­گیرد. در فصل سوم گذری بر تحقیقات پیشین خواهیم داشت. الگوریتم­های پیشنهادی در فصل چهارم ارائه شده است و در فصل پنجم نتایج حاصل از ارزیابی و مقایسه الگوریتم­های پیشنهادی آورده شده است.

 

2- ادبیات موضوعی

 

1-2- مقدمه

 

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

 

الگوریتم ژنتیك، الهامی از علم ژنتیك و نظریة تكامل داروین است و بر اساس بقای برترین‏ها یا انتخاب طبیعی استوار است. یك كاربرد متداول الگوریتم ژنتیك، استفاده از آن بعنوان تابع بهینه‏كننده است. الگوریتم ژنتیك ابزار سودمندی دربازشناسی الگو، انتخاب ویژگی، درك تصویر و یادگیری ماشینی است[3-8]. در الگوریتم‏ ژنتیك[1]، نحوه تكامل ژنتیكی موجودات زنده شبیه‏سازی می‏شود.

 

اگرچه كارهایی توسط یك زیست­شناس به نام Fraser در زمینه مدل­سازی تكامل در سیستم‌های بیولوژیك در دهه 60 میلادی صورت گرفت ولی الگوریتم ژنتیك برای كاربردهای مهندسی و به صورت امروزی آن، نخستین بار توسط جان هلند[9] متخصص علوم كامپیوتر دانشگاه میشیگان در سال 1975 پیشنهاد گردید. كار وی آغاز تمامی كوشش­ها برای كاربرد الگوریتم ژنتیك در مهندسی است. پس از آن كارهای Dejong [10]در سال 1975 در زمینه بررسی و مقایسه چندین روش الگوریتم ژنتیك پایه‌های نظری بحث را فراهم آورد. این الگوریتم با الهام از طبیعت بر پایه اصل تكاملی «پایداری بهترین‌ها»[2] استوار است. الگوریتم ژنتیك اگرچه پس از الگوریتم استراتژی تكاملی پیشنهاد گردید ولی مشهورترین روش از بین الگوریتم‌های تكاملی است. در یك الگوریتم ژنتیك یك جمعیت از افراد طبق مطلوبیت آنها در محیط بقا می­یابند. افرادی با قابلیت­های برتر، شانس ازدواج وتولید مثل بیشتری را خواهند یافت. بنابراین بعد از چند نسل فرزندانی با كارایی بهتر بوجود می‌آیند. در الگوریتم ژنتیك هر فرد از جمعیت بصورت یك كروموزوم معرفی می‌شود. كروموزوم­ها در طول چندین نسل كامل­تر می‌شوند. در هر نسل كروموزوم­ها ارزیابی می‌شوند و متناسب با ارزش خود امكان بقا و تكثیر می‌یابند. تولید نسل در بحث الگوریتم ژنتیك با عملگرهای آمیزش و جهش صورت می‏گیرد. والدین برتر بر اساس یك تابع برازندگی انتخاب می‌شوند.

 

در هر مرحله از اجرای الگوریتم ژنتیك، یك دسته از نقاط فضای جستجو مورد پردازش‏های تصادفی قرار می‏گیرند. به این صورت كه به هر نقطه دنباله‏ای از كاراكترها نسبت داده می‏شود و بر روی این دنباله‏ها، عملگرهای ژنتیكی اعمال می‏شوند. سپس دنباله‏های بدست آمده رمزگشایی می‏گردد تا نقاط جدیدی در فضای جستجو بدست آید. در آخر براساس این كه تابع هدف در هر یك از نقاط چه مقدار باشد، احتمال شركت نمودن آنها در مرحله بعد تعیین می‏گردد[11-14].

 

الگوریتم‏ ژنتیك را می‏توان یك روش بهینه‏سازی تصادفی جهت‏دار دانست كه به تدریج به سمت نقطه بهینه حركت می‏كند. در مورد ویژگی‌های الگوریتم ژنتیك در مقایسه با دیگر روش‌های بهینه سازی می‌توان گفت كه الگوریتمی است كه بدون داشتن هیچ گونه اطلاعی از مسئله و هیچ گونه محدودیتی بر نوع متغیرهای آن برای هر گونه مسئله ای قابل اعمال است و دارای كارآیی اثبات شده‌ای در یافتن بهینه كلی[3] می‌باشد. توانایی این روش در حل مسائل پیچیده بهینه‌سازی است كه روش‌های كلاسیك یا قابل اعمال نیستند و یا دریافتن بهینه كلی قابل اطمینان نیستند[15].