دانلود پایان نامه ارشد با موضوع نودهاي، انرژي، معمولي

دانلود پایان نامه ارشد

اطلاعاتش را به نود سينك ارسال نمايد. لذا هر نود بايد يا خودش يك نود سرخوشه باشد و يا يكي از همسايگانش سرخوشه باشند بنابراين اگر نودي به عنوان معمولي انتخاب گرديد و هيچ همسايه سرخوشه اي نداشت جريمه مي گردد.
در ضمن براي اينكه تعداد سر خوشه هاي شبكه زياد نشود اگر نودي به عنوان سر خوشه انتخاب شده و نود همسايه سر خوشه اي نيز داشت بايد جريمه گردد.

به طور كلي مي توان پارامترهاي مذكور را به دو دسته كلي تقسيم بندي نمود: پارامترهاي مربوط به انرژي كه سعي در انتخاب نودهاي با انرژي بيشتر به عنوان سر خوشه دارند و پارامترهاي مربوط به چگونگي و كيفيت زير ساخت خوشه بندي كه اين پارامترها سعي در تشكيل تعداد مناسب خوشه ها و ايجاد خوشه هاي متوازي دارند كه دو مورد آخر ذكر شده در بالا از اين دسته اند. به جهت اينكه بتوان اين دو دسته پارامترها را به ميزان دلخواه در تشكيل خوشه ها شركت داد، دو ضريب براي اين دو دسته پارامترها در نظر گرفته ايم به گونه اي كه مجموع اين ضرايب برابر با يك مي شود.
با توجه به پارامترهاي ذكر شده، در بالا با انتخاب هر عمل توسط آتوماتاي نود ميزان احتمال انجام آن عمل تغيير مي يابد. براي پاداش يا جريمه عمل انتخاب شده از روابط 3-4 و 3-5 استفاده مي گردد. كه a ضريب پاداش و b ضريب جريمه مي باشد.
(‏3-4)

(‏3-5)

در هر دور هر نود پس از انتخاب يك عمل بر اساس روابط (3-6) و (3-7) سيگنال تقويتي را محاسبه مي نمايد. اگر برابر با يك شود عمل انتخابي با استفاده از رابطه (3-4) جريمه مي گردد. و اگر برابر با صفر شود طبق رابطه (3-5)پاداش دريافت مي كند.
اگر عمل انتخابي سرخوشه شدن نود باشد() مقدار از رابطه (4) بدست مي ايد:
(‏3-6)

به طوري كه

ميزان انرژي باقيمانده نود در دور nام مي باشد. و ميانگين انرژي همسايگان نود مي باشد.

تعداد همسايگان نود و ميانگين تعداد همسايگان نودهاي همسايه نود مي باشد.

عمل انتخابي نود j است.
ضريب ثابت ميزان وزن اختصاص داده شده به پارامتر انرژي در الگوريتم خوشه بندي است. و ضريب ثابت ميزان وزن اختصاص داده شده به پارامترهاي مربوط به كيفيت زير ساخت خوشه بندي مي باشد. اين دو ضريب اعدادي بين صفر و يك مي باشند ايم به گونه اي كه مجموع اين ضرايب برابر با يك مي شود.
اگر عمل انتخاب شده انتخاب نود به عنوان نود معمولي باشد () مقدار از رابطه (5) محاسبه مي شود:
(‏3-7)

اين مرحله درچندين دور انجام مي گيرد در هر دور هر نود حسگر براساس بردار احتمالاتش يكي ازوضعيتهاي سر خوشه شدن و سر خوشه نشدن را انتخاب مي كند و يك پيام به صورت پخشي به تمام همسايگان ارسال مي نمايد كه پيام حاوي عمل انتخابي نود ، ميزان انرژي باقيمانده و تعداد همسايگانش مي باشد. پس از مدت زماني مشخص كه تمام نودها پيامهاي همسايگانشان را دريافت كردند. هر نود به عمل انتخابي اش براساس روابط (3-4) و (3-5) پاداش يا جريمه مي دهد و در حقيقت احتمال سر خوشه شدن نود را افزايش يا كاهش مي دهد و در دور بعد نودها براساس احتمال جديد حالت جديدي را انتخاب نموده و عمليات تكرار مي گردد.
هر نود كه احتمال سرخوشه شدنش به نزديك صفر يا يك برسد. بر اساس بردار احتمال يك حالت را انتخاب مي كند و به وضعيت پايدار مي رسد. اين الگوريتم ادامه مي يابد تا زماني كه درصد مشخصي از نودها(در ازمايشات انجام شده 95 درصد) به وضعيت پايدار برسند. در اين زمان تمام نودها حالتشان را انتخاب نموده و اين مرحله به پايان مي رسد.

مرحله 3:
در دو مرحله قبل قسمت اعظم سرخوشه هاي شبكه شناسايي گرديده اند. ولي هنوز اين امكان وجود دارد كه بعضي از نودهايي كه به عنوان نود معمولي انتخاب گرديده اند در همسايگي هيچ نود سرخوشه اي نباشند. بنابراين در اين مرحله جهت پوشش چنين نودهايي تعدادي نود سرخوشه ديگر نيز به نودهاي سرخوشه افزوده مي گردند.
بدين منظور نودهايي كه نود معمولي هستند و در همسايگي هيچ نود سرخوشه اي قرار ندارند، اگر داراي بيشترين تعداد همسايه، نسبت به نودهاي مجاور باشد، خود را به عنوان سرخوشه انتخاب نموده و وضعيتش را به اطلاع نودهاي همسايه مي رساند. در غير اين صورت، نود همسايه اي كه داراي بيشترين تعداد همسايه است را انتخاب كرده و با پيغام You_Cluster به نود مذكور اطلاع مي دهد. اين نود نيز خود را به عنوان نود سرخوشه انتخاب نموده و وضعيتش را به اطلاع نودهاي همسايه مي رساند. بدين ترتيب تمام نودهايي كه عضو هيچ خوشه اي نيستند نيز به عضويت يك خوشه درخواهند امد.
مرحله 4:
پس از مشخص شدن وضعيت نودها و تعيين سرخوشه ها در سه مرحله قبلي نوبت به شكل گيري خوشه ها مي رسد. در اين مرحله نودهايي سرخوشه پيامهايي حاوي موقعيت جغرافيايي شان را به نودهاي همسايه به صورت پخشي ارسال مي نمايند. سپس نودهاي معمولي از بين همسايگان سرخوشه نزديكترين نود را به عنوان سر خوشه انتخاب مي نمايند. جهت ايجاد خوشه هر نود معمولي يك بسته JOIN_PACKET به سر خوشه اش ارسال مي كند و نودهاي سر خوشه با جمع آوري اين بسته ها اعضاي خوشه را شناسايي و خوشه را شكل مي دهند و سپس يك برنامه زمانبندي ايجاد نموده و با ارسال پخشي يك بسته زمانبندي (SCH_PACKET) به اعضاي خوشه ، زمان ارسال داده هاي هر عضو خوشه را به آنها اعلام مي دارند.

* فاز حالت پايدار
پس از فاز خوشه بندي و تشكيل خوشه ها، فاز حالت پايدار شروع مي شود، در فاز حالت پايدار، نودهاي معمولي به صورت تناوبي و با فواصل زماني مشخص داده هايشان را به نودهاي سر خوشه ارسال مي نمايند و نودهاي سر خوشه نيز داده ها را به نود سينك مي فرستند. جهت جلوگيري از تداخل در ارسال داده ها، نودهاي عضو خوشه از يك برنامه زمانبندي جهت ارسال داده ها استفاده مي كنند بدين ترتيب كه در انتهاي فاز خوشه بندي و پس از تشكيل خوشه ها، نود سر خوشه يك بسته SCH_PACKET حاوي ليست اعضاي خوشه به تمام اعضاي خوشه ارسال مي نمايد. شماره ترتيب هر نود در ليست، نوبت ارسال داده توسط آن نود به نود سر خوشه را مشخص مي كند. بنابراين هر نود معمولي پس از دريافت بسته زمانبندي غير فعال مي گردد و زماني كه نوبت ارسال به او برسد دوباره فعال مي شود و داده ها را ارسال كرده و مجدد غير فعال مي گردد تا دوره بعد. بدين ترتيب در مصرف انرژي نودهاي معمولي به ميزان زيادي صرفه جويي به عمل مي آيد. نودهاي سر خوشه نيز در تمام دوره فعال نيستند بلكه نود سر خوشه فقط زماني فعال مي گردد كه بخواهد داده هاي نودهاي عضو را دريافت نمايد. اگر يك خوشه n عضو معمولي داشته باشد، نود سر خوشه يك دوره زماني را به n+1 بازه زماني مساوي تقسيم نموده و در ابتداي دوره غير فعال مي گردد و در پايان هر بازه فعال شده و داده هاي يك نود را دريافت كرده و دوباره غير فعال مي شود و بدين ترتيب نود سر خوشه در طول يك دوره زماني داده هاي تمام نودهاي عضو را جمع آوري مي نمايد و در پايان دوره دوباره فعال گرديده و داده ها را به نود سينك ارسال مي نمايد. بنابراين با استفاده از اين روش زمانبندي در مصرف انرژي سر خوشه ها نيز به ميزان زيادي صرفه جويي به عمل مي آيد. ولي بهر حال ميزان مصرف انرژي در سر خوشه ها نسبت به نودهاي معمولي بيشتر است كه اين امر سبب مي شود نودهاي سر خوشه سريعتر از بقيه نودها از بين رفته و شبكه مختل گردد. جهت جلوگيري از بوجود آمدن اين مشكل، ما از تغيير نودهاي سرخوشه در يك خوشه استفاده مي كنيم. بدين صورت كه نودهاي عضو خوشه هر گاه كه داده هايشان را به سر خوشه ارسال مي نمايند، مقدار انرژي باقيمانده خود را نيز همراه آنها ارسال مي كنند و در پايان هر دوره، نود سر خوشه، ميانگين ميزان انرژي اعضاي خوشه را محاسبه مي كند و اگر اين مقدار، از مقدار انرژي خودش بيش از يك حد آستانه بيشتر باشد، سر خوشه بودن را به نودي كه بيشترين انرژي را دارا است، واگذار مي كنند و يك پيغام Get_Clustering به آن نود ارسال مي دارد و در دوره زماني جديد، به هر نودي كه برايش داده ارسال مي كند با يك پيغام Change_Clustering پاسخ مي دهد و بدين گونه، نود سر خوشه جديد را معرفي مي نمايد. بنابراين پس از انتهاي دوره زماني تمام نودها متوجه تغيير سر خوشه شده و از اين به بعد داده هايشان را به سر خوشه جديد ارسال مي كنند.
3-3-2- شبيه سازي
در اين بخش کارايي الگوريتم پيشنهادي با استفاده از آزمايشات مختلف مورد ارزيابي قرار مي گيرد. جهت انجام آزمايشات از نرم افزار شبيه ساز شبکه J-Sim استفاده شده است.
در اين آزمايشات نتايج حاصل از عملکرد الگوريتم خوشه بندي پيشنهادي را با الگوريتمهاي خوشه بندي LEACH ، HEED و Extended HEED و الگوريتم مبتني بر اتوماتاهاي يادگير ارائه شده در[73] (ICLA) مقايسه نموده ايم.
در شبيه سازي انجام شده محيط حسگري 100100 متر در نظر گرفته شده است و فرض گرديده است که تعداد n حسگردر اين محيط به صورت تصادفي پخش شده اند وبرد راديويي حسگرها20 متر در نظر گرفته شده است. درضمن انرژي اوليه هريک ازنودهاي حسگر به صورت تصادفي از بازه [1.8 , 2] انتخاب مي گردد.
آزمايشات براي تعداد گره هاي حسگر Nبرابربا 50,100,200,300,400,500 انجام گرفته است وهر آزمايش براي هر تعداد حسگر 10بار تکرار گرديده است ونتايج حاصل ميانگين نتايج در 10 اجرا مي باشد. مقادير و را برابر با 0.5 و مقادير a و b را برابر 0.1 در نظر گرفته ايم. در ازمايشات اندازه بسته هاي داده اي برابر با 526 بايت و اندازه بسته هاي كنترلي 8 بايت منظور گرديده است. مقادير پارامترهاي انرژي مطابق با جداول 2-2 و 2-3 مي باشد.
جهت مقايسه عملکرد الگوريتم معيارهاي متفاوتي مد نظر قرار گرفته شده اند. معيارهاي مورد نظر عبارتند از 1) تعداد خوشه ها 2) درصد خوشه هاي خالي 3) ضريب تغييرات اندازه خوشه ها 4) نسبت سطح انرژي ميانگين سرخوشه ها به سطح انرژي ميانگين اعضا 5) طول عمر شبکه.
معيارهاي عنوان شده که در آزمايشات مدنظر قرار گرفته اند، به دو دسته اصلي تقسيم مي گردند: دسته اول معيارهاي مربوط به چگونگي و کيفيت زيرساخت خوشه بندي مي باشند. که اين معيارها عبارتند از: تعداد خوشه ها، درصد خوشه هاي خالي، ضريب تغييرات اندازه خوشه ها و نسبت سطح انرژي ميانگين سرخوشه ها به سطح انرژي ميانگين اعضا. اين معيارها ميزان مناسب بودن خوشه بندي از نظر متوازن بودن خوشه ها، تعداد کم خوشه ها و انرژي بالاتر سرخوشه ها نسبت به نودهاي معمولي را ارزيابي مي کنند.
دسته دوم معيارهاي مربوط به طول عمر شبکه مي باشند. ما طول عمر شبکه را فاصله زماني بين شروع به کار شبکه تا ازبين رفتن اولين نود در شبکه در نظر مي گيريم.
به منظور ارزيابي اين دو دسته معيارها، دو نوع آزمايش انجام گرفته است که در ادامه شرح مي دهيم.
آزمايش اول:
در آزمايش اول هدف مقايسه چگونگي وکيفيت زير ساخت خوشه بندي روش پيشنهادي با روشهاي LEACH، HEED , Extended HEED و ICLA مي باشد. که اين کيفيت بر اساس معيارهاي تعداد سرخوشه ها ، درصد خوشه هاي خالي ، و نسبت ميانگين سطح انرژي سرخوشه ها به ميانگين سطح انرژي اعضا مورد ارزيابي قرار مي گيرد.
نتايج اين دسته از آزمايشات در اشکال 3-4 تا 3-7 نمايش داده شده است. شکل 3-4 تعداد سرخوشه هاي ايجاد شده در روش پيشنهادي را در مقايسه با روشهاي مورد مقايسه را با تعداد نودهاي مختلف نشان مي دهد. همانگونه که مشاهده مي گردد تعداد نودهاي سرخوشه ايجاد شده در روش پيشنهادي نسبت به بقيه روشها کمتر مي باشد و تقريبا برابر با روش ICLA مي باشد.

شکل ‏3-4 : مقايسه تعداد خوشه هاي ايجاد شده در روشهاي مختلف خوشه بندي
شکل3-5 درصد خوشه هاي خالي ايجاد شده و شکل 3-6 نسبت ميانگين انرژي سرخوشه ها نسبت به ميانگين انرژي نودهاي معمولي در روش خوشه بندي پيشنهادي را در مقايسه با روشهاي LEACH، HEED , Extended HEED و ICLA نشان مي دهند که نتايج حاکي از عملکرد بهتر روش پيشنهادي

پایان نامه
Previous Entries دانلود پایان نامه ارشد با موضوع نودهاي، انرژي، بندي Next Entries دانلود پایان نامه ارشد با موضوع انرژي، تجميع، سينك