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

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

نود سر خوشه، کل خوشه از کار نيفتد و عمر خوشه تمام نشود، نودهاي با انرژي بالا در خوشه به صورت چرخشي و تصادفي سرخوشه مي شوند. به علاوه داده ها به صورت محلي با هم تجمع مي گردند تا مقدار داده هايي که بايد به ايستگاه پايه ارسال شوند و در نتيجه مصرف انرژي، کاهش يافته و عمر شبکه افزايش يابد. در اين روش حسگرها خود را با احتمال مشخصي به عنوان سرخوشه انتخاب مي کنند. اين سرخوشه ها وضعيت خودشان را به اطلاع نودهاي ديگر شبکه مي رسانند. هر نود بر اساس مينيمم انرژي ارتباطي يک سرخوشه را انتخاب مي کند و عضو آن خوشه مي گردد. زماني که همه نودها در خوشه ها سازماندهي شدند ،هر سرخوشه يک برنامه زمانبندي براي نودهاي خوشه اش مي سازد. نودهاي غيرسرخوشه براساس اين برنامه زمانبندي فقط زماني که نوبت ارسال آنهااست، قطعات راديويي خود را روشن مي سازند و در بقيه زمانها خاموشند كه باعث صرفه جويي در مصرف انرژي مي گردد.
زماني که نود سرخوشه، داده هاي همه اعضا را جمع آوري کرد، داده ها را تجميع نموده و داده هاي فشرده شده را به ايستگاه پايه مي فرستند. در اين روش نودها بر اساس انرژي باقيمانده شان تصميم مي گيرند که سرخوشه بشوند يا خير. هر نود مستقل از ساير نودها تصميم گيري مي کند. بنابراين براي تشخيص سرخوشه مذاکرات اضافي لازم است.
3-2-1-1- تشريح روش
عملکرد LEACH به چندين دور تقسيم مي گردد. که هر دور با يک فاز راه اندازي شروع مي گردد که در اين فاز خوشه ها سازماندهي مي گردند. سپس در فاز حالت پايدار عمل انتقال داده ها به ايستگاه پايه انجام مي گيرد به منظور کاهش بالاسري شبکه فاز حالت پايدار در مقايسه با فاز راه اندازي طولاني تر است.
* فاز اعلان:
در ابتدا هر نود بر اساس درصد سر خوشه شدن که از قبل مشخص است و تعداد دفعاتي که نود سرخوشه شده است، تصميم مي گيرد که آيا در دور جاري سرخوشه بشود يا خير. اين تصميم نود بر اساس انتخاب يک عدد تصادفي بين صفر و يک انجام مي شود اگر عدد کمتر از مقدار آستانه (n )T باشد، نود در دور جاري سرخوشه مي شود. مقدار آستانه به صورت زير محاسبه مي گردد:
(‏3-2)

کهP درصد مطلوب براي سرخوشه ها است (مثلا P =0/05 ) و r مرحله جاري است و G مجموعه نودهايي است که در 1/P مرحله آخر به عنوان سرخوشه انتخاب نشده اند در مرحله صفر هر نود با احتمال P سرخوشه مي گردد. نودهايي که در يک مرحله سرخوشه مي شوند تا 1/P مرحله بعد سرخوشه نمي شوند بنابراين احتمال سرخوشه شدن نودهاي ديگر افزايش مي يابد زيرا نودهاي کمتري شايستگي سرخوشه شدن را دارند . بعد از 1/(p-1) مرحله، براي همه نودهايي که هنوز سرخوشه نشده اند ، T=1 مي شود و پس از 1/P مرحله، همه نودها يک بار شايستگي سرخوشه شدن را پيدا کرده اند. نسخه بعدي اين کار شامل يک آستانه مبتني بر انرژِي جهت استفاده براي نودهاي با انرژي غير يکنواخت است.
هر نودي که در اين مرحله خودش را به عنوان سرخوشه انتخاب کرد يک آگهي به بقيه نودها ارسال مي نمايد. نودهاي غير سرخوشه ،آگهي هاي دريافتي از نودهاي سرخوشه را براي استفاده در فاز راه اندازي نگه مي دارند. بعد از اينکه اين فاز کامل شد، هر نود غير سرخوشه يک سرخوشه را براي اين مرحله انتخاب مي کند. اين تصميم بر اساس قدرت سيگنالهاي دريافتي آگهي ها از سرخوشه ها گرفته مي شود. در صورت وجود گره(خوشه بدون سرخوشه) يک سرخوشه به صورت تصادفي انتخاب مي گردد.
* فاز راه اندازي خوشه:
پس از آنکه هرنود تصميم گرفت که به کدام خوشه تعلق دارد به اطلاع نود سرخوشه اش مي رساند. در اين فاز تمام نودهاي سرخوشه بايد دريافت کننده هايشان را روشن نگه دارند.
* ساخت برنامه زمانبندي:
نود سرخوشه پيا مهاي اعضاي خوشه را دريا فت مي کند و بر اسا س تعداد نود هاي خوشه يک برنامه زمانبندي مي سازد که مشخص مي کند که هرنود در چه زماني مي تواند اطلاعاتش را ارسال نمايد اين برنامه زمانبندي به تمام نودهاي خوشه ارسال مي گردد.
* انتقال داده ها :
پس از آن که خوشه ها ايجاد شدند انتقال داده ها مي تواند شروع شود با فرض اينکه نودها هميشه داده اي جهت ارسال دارند آنها در طول زماني که به آنها تخصيص دارد داده هايشان را به سرخوشه ارسال مي کنند. اين ارسال از مينيمم مقدار انرژي استفاده مي کند پس از ارسال داده قطعات راديويي هر نود غير سرخوشه مي تواند خاموش شود. نود سرخوشه بايد گيرنده اش را جهت دريافت اطلاعات از نودها در خوشه روشن نگه دارد. زمانيکه همه داده ها دريافت شدند نود سرخوشه عمل پردازش سيگنال را انجام مي دهد تا داده ها را به يک سيگنال واحد فشرده نمايد. اين عمل حالت پايدار شبکه است. بعد از يک زمان خاص که از قبل مشخص شده است مرحله بعدي شروع مي شود با نودهاي سرخوشه اي که در فاز اعلان شناسايي گرديده اند.

3-2-2- پروتکل خوشه بندي HEED
روش خوشه بندي HEED يک روش خوشه بندي توزيع شده است که هم انرژي و هم هزينه ارتباطات را در نظر مي گردد.
اين پروتکل چهار هدف دارد:
1) افزايش طول عمر شبکه با توزيع مصرف انرژي.
2) خاتمه دادن به فرايند خوشه بندي باتعداد ثابتي مرحله.
3) مينيمم کردن سرايند کنترل(که نسبت به تعداد نودها خطي باشد).
4) توليد سرخوشه هاي خوب توزيع شده و خوشه هاي فشرده.
HEED در مورد نحوه توزيع و چگالي نودها يا توانا ييهاي نودها مثلا آگاهي نسبت به مکانشان هيچ فرضي را در نظر نمي گيرد.
3-2-2-1- بيان مسئله
الف) مدل شبکه:
فرض کنيد که مجموعه اي از حسگر ها بر يک محيط مستطيلي پخش شده اند. خواص زير را در مورد شبکه در نظر مي گيريم:
1) نودهاي شبکه ثابت هستند.
2) شبکه از چندين ايستگاه پايه استفاده مي کند که مي توانند ثابت يا متحرک باشند. که باعث مي شود مصرف انرژي براي تمام نودها يکسان نباشد.
3) نودها ازمکان و موقعيتشان آگاهي ندارند يعني مجهز به GPS نيستند.
4) همه نودهاتواناييهاي(پردازشي/ ارتباطي) يکسان دارند.
5) پس از استقرار نودها به صورت خودکار و بدون کنترل کار مي کنند.
6) هر نود از تعداد ثابتي سطوح انتقال برخوردار است.

ب) مسئله خوشه بندي:
فرض کنيد که N نود در محيط پراکنده شده اند و فرضيات بالا برقرارند. هدف اين است که مجموعه اي از سرخوشه ها که کل محيط را پوشش مي دهند، شناسايي گردند به گونه اي که هر نود Vi () به يک خوشه Cj () نگاشت گردد کهNc تعداد خوشه ها است(). هر نود مي تواند مستقيما با نود سرخوشه اش ارتباط برقرار نمايد. حال ملزومات زير بايد رعايت گردند:
1) خوشه بندي کاملا توزيع شده است. و هر نود مستقلا بر اساس اطلاعات محلي اش تصميم گيري مي کند.
2) خوشه بندي در تعداد ثابتي مرحله(مستقل از اندازه شبکه)پايان مي يابد.
3) در پايان هر TCP ، هر نود خواه سرخوشه باشد يا نود معمولي، متعلق به يک خوشه است.
4) خوشه بندي بايد از نظر پيچيدگي پردازشي و تبادل پيام کارآمد باشد.
5) نود هاي سرخوشه بايد بر روي محيط حسگري به صورت مناسب توزيع شده باشند.
بازه فرآيند خوشه بندي را TCP در نظر مي گيريم که زمان داده شده به وسيله پروتکل خوشه بندي به خوشه هاي شبکه است. و بازه عمليات شبکه ،TNO را زمان بين پايان يک TCP و شروع بازه TCP بعدي در نظر مي گيريم. ما بايد مطمئن باشيم کهTNO خيلي بيشتر از TCP است تا بالاسري کاهش يابد.
3-2-2-2- تشريح پروتکل
در اين قسمت جزئيات پروتکل HEED بيان مي گردد. ابتدا پارامترهايي که در فرايند خوشه بندي استفاده مي گردند تعريف مي شوند و سپس طراحي پروتکل و شبه کد آن بيان مي شود.
الف) پارامترهاي خوشه بندي :
از آنجاييکه هدف پروتکل افزايش طول عمر شبکه است، انتخاب سرخوشه، در اصل بر اساس انرژي باقيمانده هر نود صورت مي گيرد. جهت افزايش کارايي مصرف انرژي و در نتيجه افزايش طول عمر شبکه، ما هزينه ارتباطات بين خوشه ها را به عنوان پارامتر دوم خوشه بندي در نظر مي گيريم. به عنوان مثال، هزينه مي تواند تابعي از تراکم خوشه و يا ميزان نزديکي همسايه ها باشد. ما ازپارامتر اوليه استفاده مي کنيم تا يک مجموعه از سرخوشه ها را ايجاد کنيم و با استفاده از پارامتر دوم گره ها يا نودهايي که در محدوده بيش از يک سرخوشه قرار مي گيرند را کاهش مي دهيم.
معمولا هر نود تعداد محدودي سطوح توان انتقال دارد(مثلا شش تا). هر چه سطح توان افزايش مي يابد، محدوده پوشش نيز رشد مي کند. بنابراين محدوده يا دامنه خوشه با سطح توان انتقالي که در ارتباطات بين خوشه اي و در حين خوشه بندي استفاده مي گردد، تعيين مي شود. در عمل تشخيص سطح توان بهينه براي خوشه مشکل است. زيرا توپولوژي شبکه در نتيجه خرابي نودها و کاهش انرژي تغيير مي کند.
وقتي چندين نود براي سرخوشه شدن کانديدا مي گردند، نودي که هزينه ارتباطي بين خوشه اي کمتري دارد به عنوان سرخوشه انتخاب مي گردد. اين هزينه تابعي است از:
1) خصوصيات خوشه مثل اندازه خوشه.
2) متغير يا نا متغير بودن سطوح تواني که در ارتباطات درون خوشه اي استفاده مي گردند.
اگر سطح تواني که براي ارتباطات بين خوشه ها استفاده مي شود براي همه نودها ثابت باشد. آنگاه هزينه مي تواند متناسب باشد با :
1) درجه نود، اگر لازم است که بار بر روي سر خوشه ها توزيع گردد.
2) (درجه نود/1) ،اگر لازم است که خوشه هاي متراکم ايجاد گردد.
ملاحظه نماييد که ارتباطات بين خوشه ها در تابع هزينه لحاظ نمي گردد. زيرا اطلاعات محلي براي اين مورد کافي نيستند.
حال موردي را در نظر بگيريد که بتوان از سطوح تواني متغير براي ارتباطات درون خوشه اي استفاده کرد. در اين حالت MinPwri را به عنوان مينيمم سطح توان مورد نياز براي نود i () براي ايجاد ارتباط با يک سرخوشه u در نظر مي گيريم که M تعداد نودها در محدوده خوشه است. ما متوسط مينيمم توان قابل حصول ( (AMRPرا به عنوان ميانگين مينيمم سطوح توان مورد نياز براي همه M نود در محدوده خوشه براي رسيدن به u در نظر مي گيريم يعني :
اگر هر نود اجازه داشته باشد که يک سطح انرژي خاص را انتخاب کند ،AMRP يک تخمين خوب براي هزينه ارتباطات است.
اگر يك نود، سرخوشه شود، AMRP نود معيار مصرف انرژي مورد انتظار در ارتباطات درون خوشه اي است.
استفاده از AMRP به عنوان هزينه در انتخاب سرخوشه ها، فقط در انتخاب سرخوشه نيست. بلکه مکانيزم واحدي براي همه نودها ارائه مي دهد تا گره ها را بين سرخوشه هاي مختلف بشکنند.
ب) عملکرد پروتکل:
الگوريتم خوشه بندي هر TPC+TNO ثانيه يکبار اجرا مي گردد تا سرخوشه هاي جديد را انتخاب نمايد. در هر نود فرآيند خوشه سازي به چند مرحله نياز دارد که تعداد مراحل را باNiter نمايش مي دهيم. که هر مرحله به اندازهtc طول مي کشد که tc برابر با زمان کافي جهت رسيدن پيامها از هر يک همسايه هاي واقع در دامنه خوشه مي باشد. ما با اين فرض که يک درصد بهينه نمي تواند از قبل مشخص گردد، قبل از اينکه شروع به اجراي heed نماييم، يک درصد اوليه براي سر خوشه شدن نودها مشخص مي کنيم (Cprob برابر با 5 درصد). احتمال سرخوشه شدنش (CHprob ) به صورت زير به دست مي آيد:
(‏3-3)

که Eresidual انرژي باقيمانده جاري تخمين زده شده در نود مي باشد و Emax مقدار انرژي ماکزيمم نود مي باشد. مقدارCHprob يک نود از يک مقدار آستانه Pmin (معادل 4-10 ) کمتر نمي باشد که متناسب است با معکوس Emax. اين محدويت بدين جهت در نظر گرفته شده است که الگوريتم در زمان Niter=O(1) تکرار خاتمه يابد. در هر تکرار i هر نود پوشش داده نشده با احتمال CHprob خود را به عنوان سرخوشه انتخاب مي کند. بعد از مرحله i سرخوشه ها ي SCH برابر مي شود با مجموعه سر خوشه ها بعد از مرحله i – 1 اجتماع سر خوشه هاي جديد در مرحله i. هر نود Vi ، نودي با کمترين هزينه درSCH را به عنوان سرخوشه اش انتخاب مي کند که مي تواند خود نود نيز باشد. سپس هر نود مقدار CHprob اش را دو برابر مي کند و به مرحله بعد مي رود. شبه کد

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