نوع فایل: word
قابل ویرایش 90 صفحه
چکیده:
امروزه پیشرفت های چشمگیری در زمینه های الکترونیک و مخابرات به وقوع پیوسته است. تولید انبوه حسگرهایی که بتوانند محیط های عملیاتی را نظارت کنند یکی از این پیشرفت ها می باشد. حسگرها می-توانند فقط تا محدوده ی کوتاهی از محیط را نظارت کنند. ولی در محیط های عملیاتی به خاطر تعداد انبوه-شان می توانند با ارسال دست به دست داده ها، نتایج را به چاهک گزارش دهند. روش ارسال گام به گام می بایست توسط فرآیندی کنترل گردد. خوشه بندی، روش کارآمدی در این زمینه می باشد.
در این پایان نامه، سه روش خوشه بندی پیشنهاد شده است که هر سه بر پایه ی الگوریتم جستجوی ژنتیک پیاده سازی شده اند. روش اول بر روی پارامتر تجمیع داده ای تمرکز می کند و سعی بر انتخاب خوشه هایی است که فاصله ی گره های داخلی آنها به هم نزدیک باشند. روش دوم علاوه بر دنبال پارامتر روش اول، پارامترهای دیگری همچون انرژی باقیمانده و تعداد گره های خوشه ها از شبکه را مدنظر قرار می دهد و هم اینکه ماهیت جستجو را طوری تغییر می دهد که فضای حالت بسیار گسترده به فضای حالت محدودتر نگاشت شود. روش سوم که پاسخ سوال این پایان نامه می باشد، تعداد بهینه ی خوشه ها را به کمک الگوریتم ژنتیک جستجو می کند. روش سوم پیشنهادی بر پایه ی روش دوم استوار است با این تفاوت که چند پارامتر دیگر از شبکه به آن اضافه تر شده است.
در شبیه سازی های بعمل آمده از روش های پیشنهادی، ابتدا الگوریتم پیشنهادی اول با خوشه بندی مشبک مقایسه شده است. نتایج شبیه سازی حاکی از این است که در الگوریتم پیشنهادی اول نسبت به الگوریتم مشبک، تجمیع داده ای فراوانی حاصل شده است. سپس الگوریتم پیشنهادی دوم در راستای الگوریتم پیشنهادی اول مطرح گردیده است. نتایج نشان دهنده ی این است که از یک طرف سرعت اجرای برنامه سریع شده است و از طرف دیگر پارامترهای بیشتری در خوشه بندی منظور شده است. در نهایت الگوریتم پیشنهادی سوم که از دو روش قبلی دارای پارامترهای بیشتری است موجب بهبود طول عمر شبکه شده است. هدف اصلی این پایان نامه که یافتن تعداد بهینه ی خوشه ها است در الگوریتم پیشنهادی سوم حاصل شده است.
کلید واژه ها: شبکه های حسگر بی سیم، الگوریتم ژنتیک، خوشه بندی، چاهک، تابع برازش، تجمیع داده.
مقدمه:
پیشرفت‌های اخیر در زمینه الکترونیک و مخابرات بی سیم توانایی طراحی و ساخت حسگرهایی را با توان مصرفی پایین، اندازه کوچک، قیمت مناسب و کاربری‌های گوناگون داده است. این حسگرهای کوچک که توانایی انجام اعمالی چون دریافت اطلاعات مختلف محیطی (بر اساس نوع حسگر) پردازش و ارسال آن اطلاعات را دارند، موجب پیدایش ایده‌ای برای ایجاد و گسترش شبکه‌های موسوم به شبکه‌های حسگر بی سیم شده‌اند.
یک شبکه حسگر بی سیم متشکل از تعداد زیادی گره‌های حسگر است که در یک محیط به طور گسترده پخش شده و به جمع‌آوری اطلاعات از محیط می‌پردازند. لزوماً مکان قرار گرفتن گره‌های حسگر، از قبل تعیین شده و مشخص نیست. چنین خصوصیتی این امکان را فراهم می‌آورد که بتوان آنها را در مکان‌های خطرناک و یا غیرقابل دسترس رها کرد. از طرف دیگر این بدان معنی است که پروتکل‌ها و الگوریتم های شبکه‌های حسگر بی سیم باید دارای توانایی‌های خودساماندهی باشند. دیگر خصوصیت‌های منحصر بفرد شبکه‌های حسگر، توانایی همکاری و هماهنگی بین گره‌های حسگر می باشد. هر گره حسگر روی برد خود دارای یک پردازشگر است و به جای فرستادن تمامی اطلاعات خام به مرکز یا به گره‌ای که مسئول پردازش و نتیجه‌گیری اطلاعات است، ابتدا خود یک سری پردازش‌های اولیه و ساده را روی اطلاعاتی که به دست آورده است، انجام می‌دهد و سپس داده‌های نیمه پردازش شده را ارسال می‌کند.
با اینکه هر حسگر به تنهایی توانایی ناچیزی دارد، ترکیب صدها حسگر کوچک امکانات جدیدی را عرضه می کند. در واقع قدرت شبکه‌های حسگر بی‌سیم در توانایی بکارگیری تعداد زیاد گره کوچک است که خود قادرند سازماندهی شوند و در موارد متعددی چون مسیریابی هم‌زمان، نظارت برشرایط محیطی، نظارت بر سلامت ساختارها یا تجهیزات یک سیستم بکار گرفته شوند. گستره ی کاربری شبکه‌های حسگر بی‌سیم بسیار وسیع بوده و از کاربردهای کشاورزی، پزشکی و صنعتی تا کاربردهای نظامی را شامل می-شود. به عنوان مثال یکی از متداول‌ترین کاربردهای این تکنولوژی، نظارت بر یک محیط دور از دسترس است.
فهرست مطالب:
فصل اول: نگاهی بر شبکه‌های حسگر بی‌سیم
1-1مقدمه
1-2 ساختار کلی شبکه حسگر بی سیم
1-3 ساختمان گره حسگر
1-4 ویژگی‌های عمومی یک شبکه حسگر
1-5 فاکتورهای طراحی شبکه های حسگر بی سیم
1-6 کاربردهای شبکه های حسگر بی سیم
فصل دوم: بررسی پروتکل های خوشه بندی در شبکه های حسگر بی سیم
2-1 مقدمه
2-2 اهداف خوشه بندی
2-3 الگوریتم های خوشه بندی در شبکه های حسگر بی سیم
2-3-1 الگوریتم های همگرای زمانی متغیر
2-3-1-1 الگوریتم خوشه بندی پیوندی (LCA)
2-3-1-2 خوشه بندی مبتنی بر رقابت تصادفی (RCC)
2-3-1-3 الگوریتم انجمنی (CLUBS)
2-3-1-4 الگوریتم کنترل سلسله مراتبی خوشه بندی (HCC)
2-3-1-5 خوشه بندی سلسله مراتبی موثر انرژی (EEHC)
2-3-2 الگوریتم های همگرای زمانی ثابت
2-3-2-1 خوشه بندی سلسله مراتبی کم مصرف از نظر انرژی (LEACH)
2-3-2-2 سرویس خوشه بندی محلی سریع (FLOC)
2-3-2-3 خوشه بندی توزیعی با انرژی موثر ترکیبی (HEED)
2-3-2-4 خوشه بندی سلسله مراتبی با انرژی موثر توزیعی بر پایه وزن (DWEHC)
2-3-2-5 الگوریتم خوشه بندی همپوشانی چند گامی (MOCA)
2-4 نگاهی بر پردازش تکاملی و الگوریتم ژنتیک
2-4-1 کروموزوم
2-4-2 فضای جستجو
2-4-3 تابع شایستگی
2-4-4 رمزگذاری کروموزومی
2-4-5 عملگرهای ژنتیک
2-4-5-1 عملگر برش
2-4-5-2 انواع روش های عمل برش
2-4-5-3 عملگر جهش
2-4-6 شرط خاتمه الگوریتم ژنتیک
2-4-7 انواع روش های انتخاب
2-4-8 کاربردهای الگوریتم ژنتیک
2 -5 نتیجه گیری
فصل سوم: ارائه ی خوشه بندی جدید در شبکه های حسگر بی سیم به کمک الگوریتم ژنتیک
3-1 مقدمه
3-2خوشه بندی با استفاده از الگوریتم ژنتیک
3-3 نگاشت حالتی از شبکه به یک کروموزوم در ژنتیک
3-4 نحوه ی انتخاب سرخوشه ها
3-5 شبیه سازی، ارزیابی شبکه و مقایسه ی راهکار پیشنهادی
3-6 نتیجه گیری
فصل چهارم : تعیین روش جدید خوشه بندی بر مبنای سرخوشه به کمک الگوریتم ژنتیک
4-1 مقدمه
4-2 معرفی الگوریتم و مسائل چند معیاره
4-3 پارامترهای اصلی و رایج شبکه های حسگر بی سیم
4-4 مقایسه چند الگوریتم خوشه بندی با الگوریتم جدید
4-5 نتیجه گیری
فصل پنجم : تعیین تعداد بهینه ی خوشه ها در شبکه های حسگر بی سیم به کمک الگوریتم ژنتیک
5-1 مقدمه
5-2 معرفی الگوریتم
5-3 راهکار پیشنهادی
5-4 معیارهای اصلی به کار رفته در روش پیشنهادی
5-5 برازش نهایی شبکه بر اساس پارامترها
5-6 نتایج شبیه سازی
5-7 نتیجه گیری
نتیجه گیری کلی
پیوست الف : واژه نامه انگلیسی به فارسی
پیوست ب : واژه نامه فارسی به انگلیسی
فهرست منابع
فهرست جداول:
فصل سوم
جدول 3-1 مقادیر فرضی در شبیه سازی
جدول 3-2 نتایج حاصل از خروجی شبیه سازی شده
فصل چهارم
جدول 4-1 مقایسه ی روش های پیشنهادی
فهرست شکل ها:
فصل اول
شکل 1-1 ساختمان کلی شبکه حسگر بی سیم
شکل 1-2 ساختمان داخلی گره حسگر/کارانداز
فصل دوم
شکل 2-1 خوشه بندی سلسله مراتبی
شکل 2-2 مدل شبکه در الکوریتم LEACH
شکل 2-3 فازهای الکوریتم LEACH
شکل 2-4 فلوچارت عملیات الگوریتم LEACH
فصل سوم
شکل 3-1 نمونه ای از یک حالت شبکه
شکل 3-2 مقایسه الگوریتم ژنتیک و الگوریتم مشبک
شکل 3-3 الف) خوشه بندی با الگوریتم ژنتیک ب) خوشه بندی مشبک با 48 حسگر
شکل 3-4 الف) خوشه بندی با الگوریتم ژنتیک ب) خوشه بندی مشبک با 84 حسگر
فصل چهارم
شکل 4-1 خوشه بندی بدون پارامتر دوم
شکل 4-2 خوشه بندی با پارامتر دوم
شکل 4-3 خروجی شبکه ی خوشه بندی شده ی نهایی
شکل 4-4 دوره های مختلف مرگ گره ها برای نصف گره ها
شکل 4-5 الف) مصرف انرژی تا اولین گره مرده ب) میانگین مصرف انرژی تا اولین گره مرده
فصل پنجم
شکل 5-1 تفاوت ارسال مستقیم با ارسال چندگامی
شکل 5-2 دوره های مختلف مرگ گره ها برای نصف گره ها
شکل 5-3 الف) مصرف انرژی تا اولین گره مرده ب) میانگین مصرف انرژی تا اولین گره مرده
منابع و مأخذ:
[1] بابایی، ش. و شکرانه، س. و قاسم خانی، ب.، 1388، روش جدید مبتنی بر الگوریتم ژنتیک برای خوشه بندی و انتخاب سرخوشه برای شبکه های حسگر بی سیم، کنفرانس ملی نجف آباد.
[2] غفاری، ع.، گلسرخ تبار، م. و عبادی،س. 1389، ارائه ی الگوریتم خوشه بندی سلسله مراتبی مبتنی بر آگاهی از انرژی و گزینش بهترین سرخوشه جهت بهینه سازی مصرف انرژی در شبکه های حسگر بی سیم، هجدهمین کنفرانس مهندسی برق ایران، دانشگاه صنعتی اصفهان
[3] غفاری، ع.، رسولی، س. و گلسرخ تبار، م. 1388، ارائه ی الگوریتم مسیریابی سلسله مراتبی چندگامه جدید برای توازن انرژی مصرفی در شبکه های حسگر بی سیم، دومین کنفرانس ملی مهندسی برق ایران، دانشگاه آزاد اسلامی واحد نجف آباد.
[4] حسینعلی پور، ع.، 1388، بهبود کیفیت سرویس مسیریابی در شبکه های حسگر بی سیم، پایان نامه کارشناسی ارشدگروه کامپیوتر، دانشگاه آزاد اسلامی واحد تبریز.
[5] گلسرخ تبار، م.، 1389، ارائه الگوریتم خوشه‌بندی جدید، جهت کاهش مصرف انرژی در شبکه‌های حسگر بی‌سیم، پایان نامه کارشناسی ارشدگروه کامپیوتر، دانشگاه آزاد اسلامی واحد تبریز.
[6] Babaie, Sh., 2010, CCGA: Clustering based on Cluster head with Genetic Algorithm in Wireless Sensor Network, India, IEEE 2010 Paper 337.
[7] Heinzelman,W.R., Chandrakasan,A.P. and Balakrishnan,H., 2002, An application-specific protocol architecture for wireless microsensor networks, IEEE Transactions on Wireless Communications 660–670.
[8] Intanagonwiwat,C., Govindan and R., Estrin,D., 2000, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Mobile Computing and Networking, pp. 56–67.
[9] Younis, M. Akkaya, K. Kunjithapatham, A. Optimization of task allocation in a cluster–based sensor network, in: Proceedings of the 8th IEEE Symposium on Computers and Communications (ISCC’2003), Antalya, Turkey, June 2003.
[10] Banerjee, S. Khuller, S. A clustering scheme for hierarchical control in multi-hop wireless networks, in: Proceedings of 20th Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’ 01), Anchorage, AK, April 2001.
[11] Younis, O. Fahmy, S. HEED: A Hybrid, Energy-Efficient, Distributed clustering approach for Ad Hoc sensor networks, IEEE Transactions on Mobile Computing 3 (4) (2004) 366–379.
[12] Heinzelman, W.B. Chandrakasan, A.P. Balakrishnan, H. Application specific protocol architecture for wireless microsensor networks, IEEE Transactions on Wireless Networking (2002).
[13] Bandyopadhyay, S. E. Coyle, An energy efficient hierarchical clustering algorithm for wireless sensor networks, in: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2003), San Francisco, California, April 2003.
[14] Garcia, F. Solano, J. Stojmenovic, I. Connectivity based k-hop clustering in wireless networks, Telecommunication Systems 22 (1) (2003) 205–220.
[15] Fernandess, Y. Malkhi,D. K-clustering in wireless ad hoc networks, in: Proceedings of the 2nd ACM international Workshop on Principles of Mobile Computing (POMC ’02), Toulouse, France, October 2002.
[16] Amis, A.D. Prakash, R. T.H.P. Vuong, Huynh, D.T. Max-Min Dcluster formation in wireless ad hoc networks, in: Proceedings of 20th Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’2000), March 2000.
[17] IlkerOyman, CemErsoy, E. Multiple sink network design problem in large scale wireless sensor networks, in: Proceedings of the IEEE International Conference on Communications (ICC 2004), Paris, June 2004.
[18] Younis, M. Youssef, M. Arisha, K. Energy-aware management in cluster-based sensor networks, Computer Networks 43 (5) (2003) 649–668.
[19] IlkerOyman, CemErsoy, E. Multiple sink network design problem in large scale wireless sensor networks, in: Proceedings of the IEEE International Conference on Communications (ICC 2004), Paris, June 2004
[20] Dai, F. Wu, J. On constructing k-connected k-dominating set in wireless networks, in: Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05), Denver, Colorado, April 2005.
[21] Dasgupta, K. Kukreja, M. Kalpakis, K. Topology-aware placement and role assignment for energy-efficient information gathering in sensor networks, in: Proceedings of 8th IEEE Symposium on Computers and Communication (ISCC’03), Kemer-Antalya, Turkey, July 2003.
[22] Baker, D.J. Ephremides, A. The architectural organization of a mobile radio network via a distributed algorithm, IEEE Transactions on Communications, COM-29 (11) (1981) 1694– 1701.
[23] Xu, K. Gerla, M. A heterogeneous routing protocol based on a new stable clustering scheme, in: Proceeding of IEEE Military Communications Conference (MILCOM 2002), Anaheim, CA, October 2002.
[24] Nagpal, R. Coore, D. An algorithm for group formation in an amorphous computer, in: Proceedings of the 10th International Conference on Parallel and Distributed Systems (PDCS’98), Las Vegas, NV, October 1998.
[25] Bandyopadhyay, S. Coyle, E. An energy efficient hierarchical clustering algorithm for wireless sensor networks, in: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2003), San Francisco, California, April 2003.
[26] Baker, D.J. Ephremides, A. The architectural organization of a mobile radio network via a distributed algorithm, IEEE Transactions on Communications, COM-29 (11) (1981) 1694– 1701.
[27] Baker, D.J. Ephremides, A. Flynn, J.A. The design and simulation of a mobile radio network with distributed control, IEEE Journal on Selected Areas in Communications (1984) 226–237
پروژه ارائه الگوریتمی جهت کاهش مصرف انرژی در شبکه های حسگر بی سیم. doc
