دانلود پایان نامه ارشد با موضوع سلسله مراتب

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

دقيقه تکرار مي گردد. در روش GPSR و عدم استفاده از الگوريتمهاي پوشش محيط تمام نودهاي شبکه فعال بوده و طول عمر شبکه داراي کمترين مقدار است. در اين آزمايشات نودهاي فعال به صورت چندگامي اطلاعات را به نود سينک ارسال مي نمايند. در استفاده از الگوريتم CCP چون مسئله انرژي مد نظر قرار نمي گيرد، معمولا در هر بار اجراي الگوريتم، نودهايي مشخصي جهت فعال ماندن انتخاب مي گردند. که منجر به از بين رفتن سريع اين نودها مي گردد. ولي در روش پيشنهادي، چون در هر بار اجرا سعي مي گردد که نودهاي با انرژي بيشينه جهت فعال ماندن انتخاب شوند، طول عمر شبکه بيشتر خواهد بود. نتايج آزمايش الف، در شکل 2-17 و شکل ب در شکل 2-18 مشاهده مي گردد.

شکل‏2-17: مقايسه طول عمر شبكه(زمان از بين رفتن اولين نود) در حالتهاي مختلف: 1-استفاده از روش CCP 2-استفاده از روش مبتني بر آتوماتاهاي يادگير 3- بدون استفاده از الگوريتمهاي پوشش)روش GPSR )

شکل ‏2-18 : مقايسه طول عمر شبكه(ميزان پوشش شبکه) در حالتهاي مختلف: 1-استفاده از روش CCP 2-استفاده از روش مبتني بر آتوماتاهاي يادگير 3- بدون استفاده از الگوريتمهاي پوشش)روش GPSR )
2-4-3-4- آزمايش چهارم:
در آزمايش چهارم روش پيشنهادي از نظر ميزان انرژي مصرفي در الگوريتم پوشش نسبت به كل انرژي مصرفي در طول زمان حيات شبكه با روش CCP مقايسه مي گردد. بر اساس شكل 2-18 روش پيشنهادي نسبت به CCP از اين لحاظ بدتر عمل مي كند. ولي چون انرژي در نودهاي شبکه به صورت متعادل و بهينه مصرف مي گردد، با توجه به شکل2-17 ، طول عمر شبکه افزايش مي يابد.

شکل ‏2-19 : مقايسه ميزان انرژي مصرفي در الگوريتم پوشش نسبت به كل انرژي مصرفي در طول زمان حيات شبكه

2-5- جمع بندي
در اين فصل روشي جديد مبتني بر آتوماتاهاي يادگير سلولي براي حل مسئله پوشش با درجه پوشش k در شبکه هاي حسگر بي سيم ارائه گرديد. در اين روش به مسئله پوشش محيط ، مصرف انرژي نودها به صورت بهينه، تعداد نودهاي فعال و طول عمر شبکه که از پارامترهاي کيفيت سرويس در شبکه هاي حسگر مي باشند، توجه گرديده است. نتايج آزمايشات نشان داد که اين روش به ميزان قابل توجهي عمر شبکه حسگر را افزايش مي دهد. و در عين حال در زمان حيات شبکه، تمام محيط با درجه پوشش k تحت پوشش قرار مي گيرد.

3-
خوشه بندي در شبکه هاي حسگر بي سيم با استفاده از آتوماتاهاي يادگير سلولي
3-1- مقدمه
زمان حيات نودهاي حسگر در شبکه حسگر بي سيم، زمان حيات شبکه را مشخص مي کند و زمان حيات شبكه نيز يكي از پارامترهاي اصلي كيفيت سرويس در شبكه هاي حسگر مي باشد که در کاربردهاي حسگري از اهميت ويژه اي برخوردار است. زمان حيات نودها مستقيما به مصرف انرژي در آنها مربوط مي گردد. ما در شبکه هاي حسگر مايليم که تعداد زيادي از حسگرها را براي دستيابي به يک هدف راه اندازي کنيم. همه اطلاعات جمع آوري شده بوسيله حسگرها بايد به يک مرکز جمع آوري کننده اطلاعات منتقل شوند. فواصل طولاني تر انرژي بيشتري درارسال اطلاعات مصرف مي کنند. تخمين زده مي شود که براي ارسال يک پيام K بيتي در يک مسير به طول d انرژي مصرف شده مي تواند به صورت زير نشان داده شود:

(‏3-1)
که در آن Eelec اتلاف انرژي الکترومغناطيسي و Eamp اتلاف انرژي تقويت کننده ارسال مي باشد.
در ارسال مستقيم، هر حسگر مستقيماً اطلاعات را به مرکز مي فرستد. شبکه هاي ارسال مستقيم براي طراحي بسيار ساده و سر راست مي باشند. اما به دليل فاصله زياد حسگرها از مرکز انرژي زيادي مصرف مي کنند. در مقابل طراحي هايي که فواصل ارتباطي را کوتاهتر مي کنند، مي توانند دوره حيات شبکه را طولاني تر کنند. بدليل تراكم بالاي گرههاي حسگر در واحد سطح و در نتيجه نزديکي آنها با يکديگر، ارتباطهاي چندگامي66 در اين گونه شبكهها مفيدتر و مقرون به صرفهتر از ارتباطهاي تكگامي67 هستند. اما با توجه به انرژي محدود هر يک از حسگرها و اينکه بيشترِ انرژي آنها صرف ايجاد ارتباط با حسگرهاي ديگر ميشود، استفاده از ارتباطهاي چندگامي نيز باعث مصرف زياد انرژي در حسگرها و در نتيجه کاهش عمر شبکة حسگر ميگردد.
به کار گيري خوشه ها براي ارسال اطلاعات به يک ايستگاه پايه با ملزوم کردن تنها تعداد کمي گره براي ارسال از فواصل دور به ايستگاه اصلي، مزاياي فواصل ارسال کوتاه را براي اکثر گره ها افزايش مي دهد. خوشه بندي کردن به اين صورت است که شبکه را به يک تعداد خوشه هاي مستقل قسمت بندي مي کنيم كه هر کدام يک سر خوشه دارند که همه اطلاعات را از گره هاي داخل خوشه اش جمع آوري مي کند. اين سر خوشه ها سپس اطلاعات را فشرده مي کنند و(در ارتباطات تک گامي) مستقيماً و يا (در ارتباطات چند گامي) به صورت گام به گام با تعداد گامهاي کمتر و صرفا با استفاده از نودهاي سرخوشه به مرکز اصلي ارسال مي کنند. خوشه بندي کردن مي تواند به ميزان زيادي هزينه هاي ارتباطي اکثر گره ها را کاهش دهد. زيرا آنها تنها لازم است اطلاعات را به نزديک ترين سر خوشه برسانند، به جاي اينکه آنها را مستقيماً به مرکز اصلي که ممکن است خيلي دور باشد بفرستند.
شکل ‏3-1: و 3-2 نشان مي دهند که چگونه خوشه بندي سرايند ارتباطي را در ارتباطات تک گامي و چند گامي کاهش مي دهد[54].

شکل ‏3-1: ارتباطات تک گامي و چندگامي بدون خوشه بندي

شکل ‏3-2: ارتباطات تک گامي و چندگامي با استفاده از خوشه بندي
تکنيکهاي خوشه بندي، قابليت مقياس پذيري و گسترش به صدها و هزاران نود را نيز دارا هستند. يعني با استفاده از اين تکنيکها مي توان با افزايش اندازه شبکه، توازن بار در شبکه را رعايت نموده و منابع را به صورت کارا استفاده نمود. کاربردهايي که به تجمع داده ها به صورت مؤثر احتياج دارند نيز کانديداي مناسبي جهت استفاده از خوشه بندي مي باشند. پروتکل هاي مسيريابي نيز مي توانند تکنيکهاي خوشه بندي را بکار ببرند[54].
از آنجا که در خوشه بندي جمع آوري و ارسال اطلاعات به ايستگاه پايه بر عهده سر خوشه ها است، بار کاري سرخوشه ها در مقايسه با ديگر نودها افزايش مي يابد و در نتيجه مصرف انرژي در سرخوشه ها بيش از ساير نودهاي خوشه مي باشد. به منظوريکنواخت کردن مصرف انرژي درنودها لازم است که سرخوشه ها و شکل خوشه ها در طول زمان حيات شبکه حسگرتغييرکند. طراحي شماي خوشه بندي با دو مسئله اساسي روبرو است: 1) چه تعداد خوشه بايد ايجاد گردد. 2)خوشه ها چطوربايد ايجاد شوند. براي پاسخ به سوال اول،تلاشهايي جهت مشخص کردن تعداد بهينه سرخوشه ها درسناريوهاي مختلف صورت گرفته است. در]55[ يک الگوريتم توزيع شده در شبکه هاي حسگر بي سيم پيشنهاد گرديده است که در ان هر حسگربا يک احتمال خودش را به عنوان سرخوشه انتخاب مي کند وتصميمش رابه اطلاع ديگران مي رساند. اين الگوريتم امکان ايجاد خوشه هاي تک گامي را فراهم مي آوردکه ممکن است باعث شود تعداد خوشه ها خيلي زياد شود و در مورد چگونگي محاسبه تعداد بهينه سرخوشه ها صحبتي نمي گردد. در آنجا مورد تک گامي تحليل مي گردد و يک مدل تحليل براي بدست آوردن تعداد بهينه سرخوشه هابه صورت يک تابع ازچندين پارامتر شامل اندازه ميدان حسگري، تعداد نودها و انرژي محاسبات و ارتباطات ارائه گرديده است. در [56] يک مدل رياضياتي براي محاسبه تعداد بهينه سرخوشه ها در شبکه حسگر بي سيم چند گامي ايجاد شده است. نتايج آنها نشان مي دهد که براي خوشه بندي سلسله مراتبي نيروي لازم براي هر سطح از خوشه متفاوت است. آنها همچنين نشان دادند که انرژي سرخوشه ها سريعتر از ديگر نودها تمام مي شود. آنها همچنين پيشنهاد دادند که براي ايجاد توازن بار الگوريتم به صورت متناوبي اجرا گردد. در کارهاي[57,58,59,60] نيز برروي اين موضوع تمرکز شده است. سوال دوم دو جنبه دارد: چطور يک سرخوشه انتخاب گردد؟ و چطور يک نود معمولي به يک سر خوشه مربوط گردد؟ بسته به اهداف و کاربرد هاي طراحي، شماهاي خوشه بندي موجود به دو دسته مختلف مي توانند تقسيم بندي گردند. يک روش خوشه بندي ممکن است به شيوه متمرکز و يا توزيع شده کار کند. خوشه بندي مي تواند در شبکه هاي همگن به کار رود و يا در شبکه هاي نا همگن. روال انتخاب سرخوشه ممکن است که در يک مرحله کامل گردد و يا به صورت تکراري انجام گردد. ساختار سلسله مراتبي خوشه مي تواند يک لايه و يا چند لايه باشد. مد انتخابات در خوشه مي تواند تک گامي، چند گامي و يا ترکيبي از هر دو باشد. هريک از اين شيوه ها مزايا و معايبي دارند.
در مورد اين سوال بعضي ملاحظات را بايد مد نظر قرار داد: اولا به طور عمومي استفاده از کنترل کننده مرکزي براي انتخاب سرخوشه ها در شبکه هاي حسگر بزرگ عملي و اقتصادي نيست.
ثانيا يک سر خوشه انرژي بيشتري از نودهاي عضو مصرف مي کند. به منظور مصرف انرژي در شبکه به صورت يکنواخت، بهتر است سر خوشه هابه صورت پويا انتخاب گردند تا به صورت ايستا. ثالثا نودهاي سرخوشه بايد به صورت يکنواخت در سراسر شبکه پخش گردند. بنابراين الگوريتم انتخاب سرخوشه در شبکه هاي حسگر بايد به صورت توزيع شده بوده و به صورت پويا بايد توپولوژي شبکه را تغيير دهد.
3-2- کارهاي انجام شده
تعدادي از کارهاي انجام شده در اين زمينه خوشه بندي در شبكه هاي حسگر بي سيم عبارتند از:
الگوريتم خوشه بندي توزيع شده در [61] نودهارا ثابت و با وزنهاي مقدار داده شده در نظر مي گيرد. الگوريتم خوشه بندي وزن دهي شده چندين خصوصيت را در يک پارامتر (وزن ) ترکيب مي کند که اين پارامتر در خوشه بندي استفاده مي شود.
در [62] استفاده از يک درخت پوشا پيشنهاد شده است تا خوشه هاي با خواص مناسب ايجاد گردد. در اين الگوريتم انرژي به عنوان پارامتر اصلي مورد تاکيد قرار نمي گيرد.
در [63] يک الگوريتم خوشه بندي غير فعال براي استفاده در مسيريابي مبتني بر درخواست در شبکه هاي حسگر پيشنهاد گرديده است.
در [64] يک روش خوشه بندي ارائه گرديده است که مبتني است بر درجه (متصل بودن) و پايينترين شناسه نود.
LEACH68 [65] يک پروتکل توزيع داده با کاربرد ويژه است که با استفاده از خوشه بندي عمر شبکه را افزايش مي دهد.
در[66] ارائه دهنده گان از يک روش خوشه بندي تصادفي شبيه LEACH استفاده کرده اند اما روشي جهت محاسبه مقادير بهينه پارامترهاي الگوريتم از قبل بکار برده اند و از ارسال چند گامي براي ارتباطات درون خوشه اي و بين خوشه اي استفاده نموده اند.
در [67] يک ساختار سلسله مراتبي چند سطحي پيشنهاد گرديده است که سرخوشه ها بر اساس درجه و انرژي باقيمانده شان انتخاب مي گردند.
ACE [68] شبکه حسگر را در تعداد ثابتي تکرار با استفاده از درجه نود به عنوان پارامتر اصلي خوشه بندي مي کند.
در[69] نويسنده گان تاثير روش هاي ارتباطي مختلف (تک گامي و چند گامي ) بر روي کارايي پروتکلهاي خوشه بندي را مورد مطالعه قرار مي دهند.
پروتکل HEED69 که در [54] آمده است يک پروتکل توزيع شده است که مستقل از نحوه توزيع نودها بر اساس پارامتر اصلي مقدار انرژي باقيمانده، سرخوشه ها را انتخاب مي نمايد. در اين پروتکل يک پارامتر دوم نيز مورد استفاده قرار مي گيرد: درجه نود و يا نزديکي به همسايه باشد.
يونيس و همکارانش در [70] يک معماري مسيريابي سلسله مراتبي بر پايه مدل سه لايه اي ارائه دادند که خوشه ها بر اساس فاکتورهاي زيادي از قبيل دامنه ارتباطي، تعداد و نوع نودهاي حسگر و مکان جغرافيايي ايجاد مي گردند.
جهت روشن شدن بحث و آشنايي بيشتر با نحوه انجام عمل خوشه بندي در کارهايي که تا کنون صورت گرفته اند، در ادامه دو روش مشهورتر و پرکاربردتر خوشه بندي(LEACH و HEED)، با جزئيات بيشتر تشريح مي گردند.
3-2-1- پروتکل خوشه بندي LEACH
LEACH يک پروتکل خوشه بندي خود سازمانده است که بار انرژي را بر روي حسگرهاي شبکه توزيع مي کند. در LEACH نودها خودشان را در خوشه هاي محلي سازماندهي مي کنند به گونه اي که يک نود در خوشه به عنوان سرخوشه عمل مي کند. براي اينکه با تمام شدن انرژي

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