بخشی از مقاله
الگوریتمی برای بهبود همگامسازی زمان در شبکههای حسگر بیسیم
چکیده: هدف از این طرح، ارائه راهکار همگامسازی زمـان در شـبکه-های حسگر بیسیم میباشد. روش پیشنهادی به صورت توزیعی بـوده و سربار پردازش و تبادل پیام محدودی را ایجاد میکند. برخی الگـوریتم-های همگامسازی در شبکههای حسگر, از زمان محلی برای همگامسازی استفاده میکنند که دارای مشکل رانـدگی سـاعت و همچنـین نیـاز بـه محاسبات پیچیده برای یافتن فاصله برای آنها دارند. در این مقاله, بـرای جلوگیری از بروز این مشکلات، از حالت زمان مرجع سراسـری اسـتفاده شده است. اصل مهم در اینگونه موارد، چگونگی ایجاد زمان مرجع است.
الگوریتم جدید از روش میانگینگیری برچسبهای زمان و بهینه سـازی آن توسط جداسازی دادههای نامطلوب ، استفاده میکند.
واژه های کلیـدی: همـهپخشـی، رانـدگی سـاعت، انحـراف سـاعت، همگامسازی زمان و برچسب زمانی.
مرجع را به حداقل رساند. بدلیل استفاده از ترکیب زمان نسـبی و زمـان گره ریشه در این روش، نیازی به تخمـین فاصـلههـای نسـبی در میـان گرههای گیرنده و طرحهای پیچیده برای تصحیح انحـرافسـاعت نمـی-
باشد. از آنجائیکه مسئله انـرژی در شـبکههـای حسـگر اهمیـت زیـادی دارد,[6,7,8] لذا با در نظر گرفتن این معیار در این روش, ذخیره انرژی را با صرفهجویی در بستههای تبادل شده برای همگامسازی موجب شده است.
بخش دوم مقاله, کارهای مربوطه در زمینه همگامسازی زمان در شبکه-هـای حســگر را بحــث مــیکنـد. در بخــش ســوم و چهــارم, الگــوریتم پیشنهادی, مطرح و با برخی از الگوریتمهای موجـود مقایسـه مـیشـود.
بخش پنجم نتایج شـبیهسـازی را نشـان مـیدهـد و در انتهـای مقالـه, نتیجهگیری از روش ارائه شده انجام شده است.
١- مقدمه
شـبکههـای حسـگر شـامل تعـداد و انـواع مختلفـی از حسـگرها ماننـد حسگرهای لرزه نگاری1، حرارتی، فشار، صوتی و ... میباشند و به کمـک این شبکهها میتوان کارهایی از قبیل نظارت بر مرزها، کشـف آتـش در جنگلها و مسائل پزشکی را آسانتر نمود.[11] در تمامی ایـن کاربردهـا شدیداَ لزوم همگامسازی زمان احساس میشود. نگهداری و تعمیـر یـک ساعت بلادرنگ برای فرآیند ترکیب دادهها در شبکههای حسگر ضروری است زیرا هر مشاهده بایددقیقاَ با زمان مرجع، برچسب زمان زده شـود.
این زمان مرجع میتواند با توجه به شرایط محیط به صورت سراسری یا محلی باشد.
در تمامی الگوریتمهای پیشنهاد شده برای همگامسازی زمان در شبکه های حسگر دو مشکل وجود دارد.[5] یکی از ایـن مشـکلات بـه دلیـل وجود راندگی ساعت است که ممکن است به دلیل تأثیر شـرایط محـیط (مانند دما، درجه حرارت، رطوبت و ...) بر روی کریستالهای نوسانسـاز ایجاد شود که اجتنابناپذیر است. دیگری عدم قطعیت است کـه بـدلیل تأخیرها ایجاد میشود و باعث کاهش روند بهینهسازی الگوریتمها مـی شود. در الگوریتم ارائه شده، سعی بر این اسـت کـه بـا تلفیـق دو روش موجود و ایجاد برخی تغییرات در آنها, خطاهای ممکن در محاسبه زمان
٢- کارهای مربوطه
در سالهای اخیر الگوریتمهای همگامسازی زمان صورت گرفته است کـه هریک علاوه بـر بهبودهـایی در زمینـه همگـامسـازی, دارای نواقصـاتی هستند که روش جدید سعی در رفع آنها دارد.
در پروتکل RBS[1,10]، گـرههـا بـا اسـتفاده از همـهپخشـی در لایـه فیزیکی، پیامهایی به همسایههای خود میفرستند. این پیامها نه شـامل برچسب زمانی صریح میباشـند و نـه دقیقـا شـامل زمـان ارسـال پیـام هستند. مهمترین محدوده در ,RBS نیاز به یک شبکه با کانال فیزیکـی همهپخشی است . این پروتکـل, روش NTP را بـه طـور قابـل تـوجهی بهبود داده است طوریکه در آن, زمان را در در اطـراف محـدوده انتشـار همهپخشی, همگام نگه میدارد.
در آزمایشاتی که در آزمایشـگاه HILL[2] روی گـرههـایی درون یـک قلمرو ساده همهپخشی انجام شد, دقتی در حـدود 2 میکـرو ثانیـه و در Ganeriwal[3] ، دقتی در حدود 25 میکرو ثانیه در هر گـام همگـام سازی با این روش بدست آمده است.
پروتکل RBS، بجای تخمین زدن خطـا، رفتـار همـهپخشـی در کانـال دسترسی به لایه فیزیکی را کنترل میکند. این امر, توسط مسیر بحرانی به گونه ای انجام میشود که مقدار زیادی از این خطاها از بین میروند .
شکل : 2-1 تحلیل مسیر بحرانی برای همگامسازی زمان، به صورت سنتی ( الف ) و RBS (ب )
همانگونه که در شکل 2-1 نشان داده شده اسـت بـا اسـتفاده از مسـیر بحرانی, زمان ارسال و دستیابی حذف میشود. زیرا خطای زمان ارسـال و دستیابی, بزرگترین عوامل ایجاد خطاهای غیرقابل پیشبینی هسـتند.
این مهمترین مزیت برای همگامسـازی در شـبکههـای بـیسـیم اسـت.
پروتکل RBS بر خلاف NTP، معمولا از زمـان نسـبی مرجـع اسـتفاده میکند و هرگز ارتباطی با زمان مطلق برقرار نمیکند. این دقیقـا همـان ویژگی برای تخمین خطای زمان ارسال و دستیابی است. هر گیرنـده بـا یک بسته مرجع, همگام میشود. این پیام نه شامل تولید برچسب زمانی توسط فرستنده میباشد و نه مهم است که دقیقا در چـه زمـانی ارسـال شده است. تقریبا هر همهپخشی موجود میتوانـد بـرای بهبـود دریافـت اطلاعات زمانی استفاده شود(مثلا، بستههای ARP در اترنت یـا کنتـرل همهپخشی در شبکههای بی سیم).
هدف اصلی پروتکل FTSP[4,9]، دست یافتن بـه یـک شـبکه وسـیعی است که گرههای شرکت کننده در آن, با ساعت محلی همگام شدهانـد.
از آنجائیکه ساعت محلی باعث ایجاد کریستالهای نوسـانسـاز و خطـا میشود، این پروتکل به فرسـتنده امکـان مـیدهـد کـه زمـان چنـدین گیرنده را به طور مفید با یک پیام رادیویی که برچسب زمانی زده شـده است همگام کند. برچسب زمانی لایه MAC میتواند بسیاری از خطاها را برطرف کند. برچسپ زمانی این لایـه, بسـیاری از خطاهـا را برطـرف میکند. در حالت عمومی, همگامسازی زمان در نقاط گسسته، فقط یک راه حل مقطعی است. جبران راندگیساعت در گرهها، قطعا دقت بـالایی بین نقاط همگام شده ایجاد میکند و ارتباطات را، در یک سربار انـدک نگه میدارد. تکنیک رگراسیون خطی برای جبران راندگیساعت در این پروتکل پیشنهاد شده است .
٣- الگوریتم پیشنهادی
همگامسازی در الگوریتم پیشنهادی، نیازی به هیچ منبع خـارجی زمـان ندارد و فقط به شرط داشتن شناسه منحصر بفرد بـرای هـر گـره انجـام میشود. در این روش، زمان سراسری توسط گـرههـای ریشـه در شـبکه پخش میشوند. به طوریکه این گرهها به صورت دورهای زمـان مرجـع را در شبکه همهپخشی نموده و هر گره بینیاز از تخمین فاصله و انحـراف از ساعت میباشد. از اینرو این روش بنام SBF2 نامگذاری شـده اسـت.
گره ریشه, زمـان مرجـع بـرای ارسـال در شـبکه را پـس از جمـعآوری تعدادی زمان محلی از گرههای مجاور خود، تخمین میزند.
برای شروع همگامسازی در این روش، ابتدا هر گره خود را ریشـه اعـلام نموده و پیام درخواست زمان محلی SRTS را همهپخشی میکنـد. هـر گرهی که زودتر رسانه در اختیار بگیرد این عمل را انجام مـیدهـد. هـر گره با دریافت این پیام، بسته SCTS که حاوی زمـان محلـی و شناسـه منحصر بفرد خودش است را به گره فرستنده SRTS ارسال میکند.
شکل : 3-1 چگونگی ارسال بستهها برای ایجاد زمان مرجع
در این روش, گره A دو کار اساسـی انجـام مـیدهـد. اولا, کـوچکترین شناسه منحصربفرد رسیده را به عنوان شناسه مورد نظر برای گروه خود و ریشه انتخاب میکند. باید توجه کرد که اگر خود A دارای کوچکترین شناسه نباشد، بدین معنی نیست که گره خودش، ریشه نمی باشد بلکـه این فقط عمل نمادین است تا سایر گرهها را برای دفعات بعدی همگـام-
سازی از ریشه گروه خود آگاه سازد. دوما, طبق مکانیزمی، زمان مرجـع را از روی زمانهای محلی محاسبه مینماید.
حال مطابق شکل 3-2 الف، A بستهای تحت عنـوان Time_Synch را همهپخشی مـیکنـد و مطـابق شـکل 3-2 ب، تمـام گـرههـایی کـه در محدودهاش است را با زمان مرجع خود هماهنگ میسازد. این عمـل بـه طور دورهای، بدون محاسبه مجدد زمان انجام میشود. هـر گـره نیـز بـا دریافت این پیغام, شناسه ریشه خود با شناسه بسته مقایسه نموده و در صورت تطبیق, زمان آنرا به عنوان مرجع زمان خود انتخـاب مـیکنـد و بسته را برای سایر گرهها همهپخشی میکند.
شکل 3-2 الف : چگونگی ارسال بسته همگام سازی توسط گره A
شکل 3-2 ب : گره های همجوار ، با گره A همگام شده اند
مطابق شکل 3-2 ب، اکنون هر یک از گرههای F,E,D,C,B با گـره A همگام شدهاند و آماده ارسال بستههای همگامسازی زمان به سایر گـره های همجوار خود میباشند. از آنجائیکه تمـام ایـن گـرههـا بـه صـورت همزمان, همگام شدهاند، همگی زمان یکسانی دارند و این زمان یکسـان را به بقیه گرهها نیز منتقل میکنند. با تکرار این عمل، تمـام گـرههـای همجوار نیز همزمان میشوند.
با این روش، هر گره میتواند خود را با ریشه یا گرههای نزدیک به ریشه همگام کند. هر گرهی که در شعاع همهپخشی یک ریشه باشد, قادر بـه دریافت پیامهای همگامسازی است و هر گرهی که بیرون از شعاع همه پخشی آن ریشه باشد، پیامهای همگامسازی را از طریق گرههای نزدیک به ریشه دریافت میکند.
-3-1 انواع پیام های موجود در SBF
در این الگوریتم، 5 نوع پیام وجـود دارد کـه شـکل کلـی یـک پیـام در شـکل 3-3 نشـان داده شـده اسـت. فیلـد ,Timestamp شـامل زمـان سراسری تخمین زده شده از طرف فرستنده در لحظه همهپخشی مـی-باشد. فیلد ,Root-ID شامل شناسه مخصوص ریشه در یک گروه مـی باشد که توسط فرستنده، ارسال شده و توسط گیرنده شناسایی میشود.
فیلد ,My-ID شامل شناسه منحصر بفرد هر گره میباشد. فیلد ,SeqN شمارندهای است که با ارسال پیام همگامسازی از طرف ریشه, یک واحد به آن اضافه میشود و ,Seq H شمارندهای اسـت کـه بـا دریافـت پیـام همگامسازی توسط گرهی، یک واحد به آن شمارنده اضـافه مـیکنـد. از روی این شمارنده هر گره متوجه میشود که این پیام بـا عبـور از چنـد گره به او رسیده است. فیلد ,K تعداد گرههایی که به پیام SRTS پاسخ دادهاند را نگهداری میکند.
زمانیکه گره فرستنده آمادگی خود را برای ریشـه شـدن همـه پخشـی میکند, پیام SCTS توسط گیرنده آمـاده شـده و بـه آدرس فرسـتنده ارسال میگردد. نکته مهم در این پیام این است که اگـر گـره فرسـتنده هنوز ریشه نداشته باشد, مجبور است شناسه خود را بـه عنـوان شناسـه ریشه در پیام SCTS قرار داده و ارسال نمایـد. پیـام Time-synch در گره ریشه آماده میگردد و سپس به صورت همهپخشی, تمام گـرههـای مجاور خود را همزمان میسازد. پیام Req Time برای درخواست زمان مرجع از گرههای موجود در شبکه میباشد و در موارد زیـر ارسـال مـی شود :
(A زمانیکه یک گره متوجه میشود ریشـه خـود را در شـبکه از دسـت داده است.
(B زمانیکه یک گره متوجه میشود هیچ پیام همگامسـازی جدیـدی از ریشه خود دریافت نکرده است.
(C زمانیکه گرهی, مدت زمانی را در حالت خواب یا بیکاری به سر برده و اکنون قصد دوباره فعال شدن در شبکه را دارد.
پیام ,Res_To_Req_Time پس از دریافت Req_Time در مـییابـد که فرستنده این پیام، نیاز به زمان مرجع شبکه دارد. ایـن پیـام حـاوی پیام مرجع و شناسه ریشه میباشد.
-3-2 نحوه انتخاب Root
یکی از مهمتـرین مـواردی کـه در ایـن پروتکـل وجـود دارد چگـونگی انتخاب ریشه و همچنین انتخاب مجدد آن در صورت خرابی است.
در لحظه شروع بکار شبکه، هر گره، زمان خود را به عنوان زمان مرجـع در نظر میگیرد. پس از یک دوره زمانی, اگر پیام همگامسـازی بـه گـره ریشه ارسال نگردد, آن گره خود را به عنوان ریشه در نظر مـیگیـرد. در این صورت, گره شناسه منحصر بفرد خود را در متغیر محلـی Root-ID خود قرار میدهد. همچنین متغیر HighsetSeqN خـود را یـک واحـد افزوده و آنرا درون SeqN پیام قرار داده و ارسال میکند.
زمانیکه گره ریشه, در اثر خالی شـدن بـاطری، خرابـی سـخت افـزار یـا جابجایی از کار بیافتد, باید ریشه دیگری جایگزین شود که به این عمـل انتخاب مجدد ریشه گویند که شامل سه حالت ممکن است.
(A اگر گرهی که قبلا با ریشه همگام شده بـود، پـس از سـپری شـدن دوره مهلت زمانی، پیامی دریافت نکرده و متوجـه از دسـت دادن ریشـه خود شود, خود را ریشه اعلام نموده و پیام SRTS ارسـال مـینمایـد و پس از دریافت، فقط عمل محاسبه زمان مرجع را بـدون اینکـه شناسـه جدیدی انتخاب کند، انجام میدهد.
(B اگرگرهی که قبلا با ریشه همگام شده بود، پس از سپری شدن دوره مهلت زمانی، پیامی دریافت نکرده و متوجه از بین
