دوشنبه 25 تیر 1397 | Monday 16 th of July 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
3-1-2 پروتکل های سلسله مراتبی

در شبکه¬های مخابراتی دیگر، مقیاس¬پذیری یا قابلیت گسترش شبکه یکی از مهمترین پارامترهای طراحی در شبکه¬های حسگر بیسیم می¬باشد. اگر قرار باشد که همه¬ی بار شبکه روی یک یا چند مسیر خاص باشد، با گسترش شبکه حجم ترافیک در شبکه بشدت افزایش یافته و بدین ترتیب با بالارفتن تاخیر، کارایی شبکه افت خواهد کرد. بنابراین با توجه به اینکه حسگرها معمولا قابلیت ایجاد ارتباط راه دور را ندارند، استفاده از این روش قابلیت گسترش شبکه را محدود می¬سازد. برای بالا بردن قابلیت شبکه در پوشش   مناطق بزرگتر بدون اینکه مشکلی در کیفیت خدمات شبکه پیش بیاید، تقسیم¬بندی شبکه به چند خوشه پیشنهاد شده¬است. هدف اصلی پروتکل¬های سلسله مراتبی( مبتنی بر خوشه¬بندی) در واقع بکارگیری یک روش مناسب جهت استفاده¬ی بهینه از منابع انرژی می¬باشد. این کار با استفاده از ارسال بصورت چندگامی  در شبکه و همچنین ترکیب اطلاعات یک خوشه به جهت کم کردن داده¬های ارسالی صورت می¬گیرد. پروتکل LEACH یکی از اولین پروتکل¬های سلسله مراتبی بود که برای شبکه¬های حسگر بیسیم معرفی شد و بسیاری دیگر از پروتکل¬ها بر مبنای ان طراحی شده¬اند. در ادامه پروتکل LEACH و چند پروتکل سلسله مراتبی پرکاربرد دیگر معرفی شده¬اند.
3-1-2-1 [Heinzelma_00]  LEACH
این پروتکل یکی از معروف¬ترین پروتکل¬های سلسله مراتبی برای شبکه¬های حسگر بیسیم است.  در این پروتکل زمان به قسمت¬هایی به نام دور  تقسیم می¬شود. هر دور نیز به دو فاز تقسیم می¬شود. فاز اول، فاز راه اندازی  نام دارد که در واقع فاز تشکیل خوشه¬ها است و فاز دوم مربوط به عملکرد عادی شبکه است که فاز حالت پایدار  نام دارد. در فاز اول بنابر، یک تابع احتمال تطبیقی سرخوشه¬ها انتخاب می¬شوند. انتخاب سرخوشه¬ها بدین صورت است که هر گره¬ی حسگر یک عدد به صورت تصادفی بین صفر و یک انتخاب می¬کند. اگر این عدد کوچکتر از یک استانه¬ی تعیین شده باشد، درطول ان دور ان گره به عنوان سرخوشه انتخاب می¬شود.
این تابع احتمال طوری طراحی شده¬است که در ظرف تعداد مشخصی از دورها هر حسگر فقط یک بار سرخوشه شود و بدین صورت مصرف انرژی روی کل شبکه پخش شود. پس از  انکه در فاز راه اندازی سرخوشه¬ها انتخاب شدند، هر سرخوشه انتخاب خود را به عنوان سرخوشه به سایر گره¬ها اعلام می¬کند و هر گره نیز سرخوشه مناسب برای خود را انتخاب می¬کند و این امر را به سرخوشه مربوطه اعلام می¬کند و بدین صورت خوشه¬ها شکل می¬گیرند. سپس هر سرخوشه برای حسگرهای خوشه¬ی خود برنامه¬ریزی زمانی انجام می¬دهد و برای هر حسگر یک برش زمانی   تخصیص می¬دهد تا بواسطه ان از رخداد تصادم  بین داده¬های حسگرهای هر خوشه جلوگیری شود. همچنین برای جلوگیری از رخداد تصادم بین داده¬های خوشه¬های مختلف، از روش طیف گسترده با توالی مستقیم ( DSSS) استفاده می¬گردد.
در فاز دوم هر حسگر داده¬ی خود را در برش زمانی خودش می¬فرستد و سرخوشه پس از دریافت همه¬ی اطلاعات حسگرهای موجود در خوشه¬اش، ان¬ها را ترکیب کرده و به ایستگاه پایه می¬فرستد. با توجه به اینکه هر  سرخوشه همه داده¬های حسگرهای موجود در خوشه را ترکیب می¬کند، در حجم داده¬های ارسالی به ایستگاه پایه و در نتیجه در مصرف انرژی صرفه¬جویی قابل توجهی می-شود.
از مهمترین مزایای الگوریتم LEACH این است که اختلاف بین طول عمر گره¬های مختلف نسبت به پروتکل¬های پیشین کم شده¬است و طول عمر شبکه با استفاده از ایده خوشه¬بندی دینامیک، افزایش یافته¬است. اما همین شکل¬گیری خوشه¬ها در ابتدای هر دور باعث تلف شدن انرژی می¬شود. که از معایب این پروتکل به شمار می¬رود LEACH در جاهایی که حسگرها بصورت فشرده در کنار هم قرار گرفته¬اند عملکرد بهتری دارد. نتایج شبیه¬سازی¬ها عملکرد بسیار بهتر LEACH را نسبت به پروتکل¬های قدیمی¬تر مثل ارتباط مستقیم  و حداقل انرژی برای ارسال  نشان می¬دهند.
3-1-2-2 [Lindsey_02]  PEGASIS
این روش در واقع حالت پیشرفت داده شده¬ی پروتکل LEACH است. در این پروتکل به جای تشکیل خوشه¬های مختلف، یک زنجیره¬ی اتصال بین تمامی حسگرها در شبکه برقرار می¬شود، به طوری که هر حسگر با همسایه¬ی خود برای ارسال و دریافت داده¬ها در ارتباط است و در کل شبکه نیز فقط یک حسگر به عنوان فرستنده¬ی داده¬ها به ایستگاه پایه انتخاب می¬شود. داده¬های جمع¬اوری شده از حسگرها به حسگرهای همسایه فرستاده می¬شود. هر حسگری که داده¬ای را از همسایه خود دریافت کرد، ان را با داده¬ی خود ترکیب کرده و به حسگر بعدی می¬فرستد. این کار انقدر ادامه پیدا می¬کند تا داده¬ها به حسگری که با ایستگاه پایه در ارتباط است، برسند. ارتباط بین حسگرها با حسگرهای همسایه بدین صورت است که هر حسگر ان همسایه¬ای را برای اتصال به زنجیره (درخت) انتخاب می¬کند که به ان نزدیکتر باشد. مثال زیر (شکل3-4)عملکرد PEGASIS را بهتر نشان می¬دهد. همانطور که نشان داده شده است، حسگر c0 داده¬ی خود را به حسگر c1 می¬فرستد. حسگر c1 داده¬ی خود را با این داده ترکیب می¬کند و نتیجه را به حسگر c2 می¬فرستد. حسگر c4 نیز داده¬ی خود را به حسگر c3 می¬فرستد، و حسگر c3 پس از ترکیب کردن با داده¬ی خود ان را به c2 ارسال می¬کند. حسگر c2 نیز داده¬هایی را که از دو طرف دریافت کرده را باهم ترکیب کرده و انرا به ایستگاه پایه می¬فرستد.
 
شکل 3-4 نحوه عملکرد پروتکل .PEGASIS

تفاوت بین LEACH و PEGASIS در این است که PEGASIS به جای خوشه از زنجیره¬ی اتصال بین حسگرها استفاده می¬کند و در نهایت فقط یک حسگر کار ارتباط با ایستگاه پایه را به عهده می¬گیرد. نتایج شبیه¬سازی نشان می¬دهد که PEGASIS بین 100% تا 300%برای شبکه¬هایی با اندازه¬های مختلف بهتر از LEACH عمل می¬کند. این بهبود بخاطر حذف قسمت تشکیل خوشه¬ها در LEACH و همچنین کم کردن داده¬های ارسالی به ایستگاه پایه بدست می¬اید. اما مشکل اصلی PEGASIS بوجود امدن تأخیر زیاد در ارسال داده¬ی نهایی به ایستگاه پایه می¬باشد. در ضمن وجود تنها یک حسگر برای ارتباط با ایستگاه پایه، مانعی بزرگ برای مقیاس¬پذیری این پروتکل محسوب می¬شود.
PEGASIS سلسله مراتبی  روش بهبود یافته¬ی PEGASIS  می¬باشد که هدف ان کاهش تاخیر در زمان ارسال داده به ایستگاه پایه است. در این روش چندین حسگر به طور همزمان قادر به ارسال داده¬هایشان به حسگرهای همسایه¬ی خود می¬باشند. برای جلوگیری از تداخل داده¬ها دو راه پیشنهاد می¬شود. اول اینکه از روش¬های کدگذاری سیگنال مثل CDMA  استفاده کنیم، یا مطابق روش دوم در یک لحظه، تنها حسگرهایی قادر به ارسال باشند که از لحاظ مکانی از هم دیگر فاصله داشته باشند تا داده¬های ان¬ها باهم تلاقی پیدا نکند.
این نسخه از PEGASIS تلاش می¬کند تا با ارسال موازی اطلاعات از تاخیر بکاهد. در این روش، تاخیر از مرتبه ی O(log N) می¬باشد که N تعداد حسگرها در شبکه است. مثال زیر (شکل3-5) بیانگر نحوه¬ی عملکرد پروتکل است. حسگر c3 به عنوان حسگر برگزیده برای ارتباط با ایستگاه پایه در دور حاضر انتخاب شده¬است. با توجه به اینکه c3 در مکان سوم درخت قرار گرفته است، تمام حسگرهایی که شماره¬ی زوج دارند داده¬ی خود را به همسایه¬ی خود می¬فرستند. در مرحله¬ی بعدی تمام حسگرهایی که داده دریافت کرده¬اند، این داده¬ها را با داده¬ی خود ترکیب کرده و به نزدیکترین همسایه در جهت راست خود می¬فرستند. چون c1 همسایه سمت راست نزدیکتری که شماره ان فرد باشد ندارد، داده¬ی خود را در مرحله¬ی دوم به c3 می¬فرستد. اما در مرحله¬ی دوم c5 داده¬ی خود را به c7 که در سمت راست خود است می¬فرستد. C7 نیز در مرحله¬ی سوم ان را با داده¬ی خود ترکیب کرده و چون همسایه¬ی دیگری در سمت راست خود ندارد، انرا به c3 می¬فرستد و در نهایت c3 داده¬های دریافتی از c1 و  c7 را باهم ترکیب کرده و نتیجه را به ایستگاه پایه می¬رساند.
 
شکل 3-5 نحوه عملکرد پروتکل PEGASIS سلسله مراتبی

نتایج شبیه¬سازی¬ها نشانگر بهتر بودن این پروتکل نسبت به PEGASIS عادی می¬باشد. مشکلی که اساسا در PEGASIS وجود دارد این است که هر حسگر نیاز دارد تا موقعیت حسگر همسایه خود را بداند که بواسطه¬ی ان داده¬ی خود را ارسال کند. ارسال اطلاعات مکانی باعث افزایش ترافیک در شبکه می¬شود و در طراحی پروتکل برای شبکه¬های حسگر بیسیم سعی می¬شود که حتی الامکان از ارسال این اطلاعات جلوگیری شود.
3-1-2-3 [Manjeshwar_01]  TEEN
این پروتکل برای شرایطی طراحی شده است که قرار است تغییرات ناگهانی در پارامتر در حال اندازه¬گیری، سریع گزارش شود. در این کاربردها، شبکه دائما در شرایط فعال نیست بلکه وقتی تغییر مورد نظر حاصل شود، به ایستگاه پایه گزارش داده می¬شود.  TEEN یک پروتکل سلسله مراتبی است اما در ان از ترفندهای پروتکل¬های مبتنی بر داده نیز استفاده شده است. عملکرد این پروتکل بدین صورت است که حسگرهایی که نزدیک هم هستند باهم یک خوشه تشکیل می¬دهند و این کار یک مرحله¬ی دیگر نیز ادامه پیدا می¬کند و در نهایت به ایستگاه پایه می¬رسد. چگونگی این کار در شکل 3-6 نشان داده شده است.


 
شکل 3-6 نحوه خوشه بندی در پروتکل .TEEN


بعد از این که خوشه¬ها تشکیل شدند. سرخوشه¬ها دو استانه را به همه حسگرها می¬فرستند. اسامی این استانه¬ها، استانه¬ی نرم  و استانه¬ی سخت  می¬باشند.
استانه¬ی سخت در واقع مقداری از پارامتر در حال اندازه¬گیری است که اگر مقدار بدست امده از یک حسگر از این استانه بیشتر باشد، مقدار بدست امده گزارش می¬شود، ولی اگر کمتر باشد دیگر این اتفاق نمی¬افتد. در واقع این استانه باعث می¬شود که هر وقت مقدار پارامتر در محدوده دلخواه است گزارش شود و بدین صورت از حجم داد ه¬های ارسالی تا حد زیادی کاسته می¬شود. اما استانه¬ی نرم مقداری از پارامتر در حال اندازه¬گیری است که هر وقت مقدار بدست امده زیر استانه¬ی سخت باشد اما اختلاف پارامتر اندازه¬گیری شده با نمونه¬ی قبلی بیش از این مقدار باشد، حسگر باز هم مقدار پارامتر را گزارش می¬کند. وجود استانه¬ی نرم نیز باعث کاهش داده¬های ارسالی می¬شود. با تنظیم سطوح استانه¬ی نرم و سخت می¬توان حجم داده¬های ارسالی به ایستگاه پایه را تنظیم کرد. برای ارسال داده¬ها به ایستگاه پایه هر حسگر داده¬ی خود را به سرخوشه  مرحله اول می¬فرستد. سرخوشه مرحله اول نیز ان را به سرخوشه مرحله دوم می¬فرستد و در نهایت به ایستگاه پایه فرستاده می¬شود.
TEEN در کاربردهایی مناسب است که گزارش اطلاعات بصورت پریودیک مورد نظر نباشد. یعنی هر وقت اتفاق خاصی در شبکه رخ داد گزارش شود.

3-1-2-4 [Manjeshwar_02]  APTEEN
یک نسخه¬ی بهبود یافته از TEEN است که در ان شبکه علاوه برگزارش اتفاقات مهم، قادر است تا بصورت پریودیک اطلاعات حسگرها را بگیرد. در این پروتکل بعد از شکل گرفتن، خوشه¬ها سرخوشه¬ها پارامترهای مورد نظر، مقادیر استانه¬ها و زمانبندی ارسال حسگرها را به ان¬ها ، می¬فرستند. برای صرفه¬جویی در انرژی سرخوشه¬ها داده¬های حسگرهای هر خوشه را ترکیب می¬کنند و بعد می¬فرستند.
APTEEN سه نوع درخواست متفاوت به شبکه می¬فرستد. اول تاریخچه¬ای  که برای انالیز داده¬های گذشته است، دوم لحظه¬ای  که بصورت لحظه¬ای اطلاعات شبکه را جمع¬اوری می¬کند، و سوم دائمی  است که برای نظارت بر اتفاقات برای یک پریود زمانی می¬باشد.
APTEEN از نظر کارایی در مصرف انرژی و طول عمر شبکه بدتر از TEEN است و TEEN با کاهش اطلاعات ارسالی، کارایی بهتری را نشان می¬دهد. مشکل عمده¬ی هر دو پروتکل در شکل¬دهی خوشه¬ها است. در واقع تشکیل خوشه¬ها در TEEN و APTEEN کمی پیچیده و مشکل است

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26