ارتباط موثر برای زمان بندی گره (مقاله ترجمه شده)

چکیده

پیاده سازی شبکه ی سنسور بی سیم (WSN) رایج گره های بیشتری از تعداد گره های مورد نیاز برای حس کردن دقیق پدیده ی مطلوب استفاده می کند. این زیاده روی می تواند از طریق روشن کردن تنها زیر مجموعه ای از گره ها در هر لحظه (زمان بندی گره) و به خواباندن گره های باقی مانده، مورد استفاده قرار گیرد. این موضوع طول عمر شبکه را به طور کارآمد زیاد می کند. طرح های زمان بندی گره علاوه بر پوشش سنجش باید اطمینان حاصل کنند که i) شبکه متصل باقی می ماند و ii) زمان مورد نیاز برای بیداری کامل پشته ی پروتکل بعد از خوابیدن، حداقل می ماند. ما زیبای خفته را ارائه می کنیم، یک پروتکل جمع اوری داده با بازدهی بالا که به طرح های زمان بندی گره در هر دو جنبه کمک می کند.

زیبای خفته از یک ارتباطات اولیه ی شیار بندی و به دقت همگام شده استفاده می کند که در ان یک گره رادیوی خود را برای اکثر زمان ها به جز در شیارهایی که نیاز دارد تا ارتباطات موفق را پیش بینی کند، خاموش می نماید. علاوه بر این، یک مکانیزم کارآمد شناسایی همسایه نیز در نظر گرفته شده است که اطلاعات توپولوژی (والدین بالقوه) جزیی اما کافی  برای جلوگیری از تقسیم بندی شبکه فراهم می کند. علاوه براین، زیبای خفته یک روش تقریب انحراف کلاک جدید اما ساده را به کار می برد. این روش در دوره های زمانی بلند، با دقت بالا همگام زمانی باقی می ماند (کمتر از 500 میکرو ثانیه حتی بعد از 45 دقیقه خوابیدن) این روش، زمان اتلاف شده در همگام سازی مجددِ شبکه در بین راندهای جمع اوری داده را حداقل می نماید. ما از طریق آزمایشاتی روی دو بستر آزمایشی تصدیق کردیم که زیبای خفته چرخه ی وظیفه را در مقایسه با روش های مدرن،  تا فاکتوری از 3 کاهش می دهد، در حالیکه نرخ های انتقال مشابهی را بدست می آورد.

1. مقدمه

ارتباطات با انرژی موثر و جمع اوری داده به طور خاص حتی بعد از یک دهه تحقیق  هنوز در جامعه یک جام مقدس است. قسمتی از این چالش این است که پیاده سازی WSN رایج شامل گره هایی بیش از گره های مورد نیاز برای سنجش دقیق پدیده ی مطلوب می شود. از سوی دیگر، این مازاد حفاظی در برابر گره ها و پیوند های خراب است اما از سوی دیگر منجر به استفاده ای ناموثر از انرژی می شود. طرح های زمان بندی گره، جنبه ی دوم را توسط فعال نگه داشتن تنها یک زیرمجموعه ی (حداقل) در هر لحظه مورد خطاب قرار می دهد. آنها این کار را بوسیله ی گزینش نماینده از گروه سنجش رایج انجام می دهند. یک گروه سنجش رایج می تواند در زمان های پیش رو شکل گیرد: i) یک سطح یا هدف رایج از طریق مجموعه ای از گره شناسایی شود یا ii) داده ی تولید شده بوسیله ی گره ها، سطح بالایی از همبستگی نشان دهد به طوریکه داده ی سنجش شده برای چندین گره می تواند با استفاده ی داده از یک گره منفرد بازسازی شود. در هر دو حالت، گره (ها) نماینده از هر گروه ملزوم هستند تا در طول راند جمع اوری داده فعال باشند. بر مبنای سناریوی کاربرد، تنها یک یا چندین گره نماینده (مانند پوشش k) به صورت فعال گزینش می شوند. گره ها با تغییر وظایف در طول راندها انرژی را ذخیره می کنند و طول عمر شبکه را افزایش می دهند.

به عنوان یک مثال، شکل 1 شبکه ای از شش گره را نشان می دهد که در آن تنها یک زیر مجموعه از گره های فعال تحت رژیم گروه سنجش رایج کافی می باشد. شکل 1b یکی از چنین ترکیباتی را نشان می دهد. هر چند اگر گره های {3,4,5} به جای {1,4,5} شده باشند، همه ی گروه ها هنوز ارائه می شوند اما شبکه از مصرف کننده جدا می شود و این کار دریافت داده ی سنجش شده را غیر ممکن می کند.

انگیزه

استراتژی برنامه ریزی گره  باید براساس سناریوی کاربرد استنتاج شود (برای مثال، پوشش k، پوشش نقطه، همبستگی فضایی و غیره). الگوریتم های برنامه ریزی گره که زیرمجموعه ی گره های فعال را انتخاب می کنند، دو استراتژی کلی را دنبال می کنند. یا مجموعه ی گره های فعال در لایه ی کاربرد را انتخاب کرده و مسیر یابی را به پروتکل های اساسی محول می نمایند و یا گزینش و مسیر یابی گره را به صورت مشترک اجرا می کنند. در حالت اول، یک پروتکل مسیر یابی پیشرفته ای که باید علاوه بر گره های فعال گزینش شده از تعداد حداقلی گره های رله استفاده کند، ملزوم است. در حالت دوم، راه حل لایه ی متقابل به به دقت با طرح زمان بندی خاص تزویج شده است. این امر باعث می شود تا این راه حل برای دیگر استراتژی های زمان بندی غیر قابل استفاده ی مجدد شود. بنابراین، نیازی برای الگوریتم جمع اوری داده ی کلی که عملیات شبکه با بازدهی بالا را بدون توجه به سیاست زمان بندی گره تضمین کند، وجود دارد.

2. پیش زمینه

در این بخش، پروتکل های جمع آوری داده ی مدرن را با توجه به محدودیت هایشان برای زمان بندی گره مرور می کنیم. پروتکل درخت جمع آوری (CTP) یک پروتکل جمع آوری داده ی تطبیقی است که درخت پوشا را ساخته و حفظ می کند. این پروتکل نرخ ارسال بسته ی خوبی را برای آرایش های متعددی فراهم می کند اما تحت ترافیک افزایش یافته و دینامیک شبکه کم می شود. به منظور مورد خطاب قرار دادن محدودیت دوم، لندزیدل (Landsiedel) و دیگران یک پروتکل جمع آوری داده ی فرصت طلب با نام ORW را پیشنهاد کردند. این پروتکل بسته ها را تا اولین گره قابل دسترسی از یک مجموعه از ارسال کننده های ممکن مسیر یابی می کند. اگرچه ORW در جنبه های متعددی بهتر از CTP عمل می کند، اما مازاد مقیاس های نگهداری مسیر یابی را به اشتراک می گذارد. این کار خصوصا در زمانی که مجموعه های گره روشن و خاموش می شوند، بازدهی را تعدیل می کند.

3. نکاه اولیه به زیبای خفته

تعریف خود از زیبای خفته را با نگاهی مفهومی که در شکل 2 نشان داده شده شروع می کنیم. چاله همه ی عملیات ها را با پر کردن متناوب شبکه با بسته های همگام هماهنگ می کند. زمانی که یک گره چنین بسته ی همگام سازی ای را دریافت کرده باشد، می تواند با درخواست دادن شیار خودش در زمان بندی سراسری به شبکه ملحق شود. این گره در ادامه می تواند داده ی سنجش شده اش را در هر فاصله ی زمانی ورود بسته به چاله گزارش دهند(I). بهرحال این گره چنین کاری انجام می دهد اگر یکی از گره های فعال مشخص شده بوسیله ی چاله در هر فاصله ی زمانی زمان بندی شده باشد (S). چاله این مجموعه و یک زمان بندی همراه با بسته های همگام را منتشر می کند. گزینش مجموعه ی متصل شده ی گره های فعال برمبنای اطلاعات همسایه ی تک هاپی پایه (والدین محتمل) است که بوسیله ی گره ها و از طریق پارازیت محلی جمع آوری شده اند. برخلاف شیار همگام، که در آن همه ی شیار ها در سیلاب مشارکت می کنند، تنها مجموعه ی گره های فعال در طول شیارهای داده در سیلاب مشارکت می کنند. این سیلاب حداقل در مقایسه با دیگر پروتکل های گلوسی بنیان، باعث تضمین بازدهی انرژی بالاتری می شود.

اهداف طراحی

عدف فراگیر برابر با مقدور سازی گره های غیر فعال به خوابدن برای تناوب های زمانی طولانی شده است در حالیکه از سیلاب کارآمد و سریع اولیه ی گلوسی بهره می برد. این هدف به دو هدف طراحی پیش رو می رسد. اول ، یک مکانیزم شناسایی همسایه ی کارآمد نیاز داریم تا اطلاعات جزیی اما کافی توپولوژی را جمع آوری کند. به طور خاص، علاقه مندیم تا لیست هایی از والدین بالقوه ی الگوریتم گزینش گرهی که در چاله راه اندازی می شود را فراهم کنیم به طوریکه هر طرح زمان بندی گره بتواند در شبکه به کار گرفته شود. دوم، طرح همگام سازی گرهی را می طلبیم که به گره ها امکان آفلاین بودن برای تناوب زمانی طولانی مدتی را بدهد در حالی که سطح مطلوب همگام سازی دقیق را حفظ نماید. به همین دلیل است که ملزومات ارسال مکرری بسته های همگام سازی بوسیله ی پروتکل گلوسی بنیان باید با روش که در فواصل زمانی بزرگتر (و حتی غیر منظم) ی کار کند، جایگزین شود.

4. خود راه انداز چکمه ای

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

ملحق کردن گره

از آنجایی که همه ی ارتباطات همگام هستند و با زمان فعال می شوند، لذا هر گره ای نیاز دارد تا خودش را پیش از شروع انتقال با چاله همگام کند. بنابراین، بعد از اینکه یک گره روشن می شود، به بسته های همگام گوش میدهد. به محض اینکه گره چنین بسته ای را دریافت کند، با شبکه همگام می شود و درباره ی ساختار فراچارچوب یاد میگیرد. همان طور که پیش از ایت ذکر شد، یک گره برای شیار داده درخواست می دهد و به ترتیب در شیارهای فرد و زوج RR پاسخ می گیرد. وقتی که یک گره یک شیار را بدست آورد، دیگر درخواست نمی فرستد و فرایند الحاق را تکمیل می نماید. بهر حال، به مشارکت در همه ی شیارهای RR دیگر ادامه می دهد تا به انتقال دادن پیام های درخواست/پاسخ به گیرنده ی مورد نظر کمک کند.

5. عملیات فضای ماندگار

آغاز فضای ماندگار با گزینش مجموعه ای از گره های فعال مشخص شده است. چاله لیستی از گره های فعال را با استفاده از بسته ی همگام سازی منتشر می کند. چاله مجموعه ی جدیدی از گره های فعال را در هر تناوب زمان بندی انتخاب می کند. مقدار این تناوب تا ثانیه می شود (شکل 4). به یاد داشته باشید که این پروتکل به اندازه ی کافی منعطف است تا همان طور که در نرم افزار در نظر گرفته شده، پاسخ گوی هر مقداری از S و I باشد.

گزینش متناوب گره فعال

از آنجایی که گزینش گره فعال خارج از محدوده ی این مقاله است، لذا از الگوریتم زمان بندی گره موجودی در بالای زیبای خفته استفاده می کنیم تا مشخص کند که چگونه می تواند با چنین روش هایی ادغام شود. گروه های سنجش رایج معلوم فرض شده اند یا می توانند در زمان اجرا بر مبنای داده ی سنجیده شده شکل گیرد. در ادامه، گره های فعال بوسیله ی الگوریتم تعریف شده در 6 گزینش می شوند. لیست گره های فعال با استفاده از یک طرح بیتی در بسته ی همگام سازی منتشر می شوند. اگر (مجرد بر دریافت یک بسته ی همگام سازی) یک گره، یک صفر را در موقعیت شیار داده اش پیدا کند، به خواب می رود (گره خفته). گره های فعال به بیدار شدن در هر I ثانیه ادامه می دهند تا داده هایشان را بدون نیاز به هر گونه بسته ی همگام سازی ارسال کنند (شکل 4). به یاد داشته باشید که گره های فعال رادیوی خود را در شیار داده ی تخصیص داده شان روشن نگه می دارند تا داده ی مختص به خودشان را ارسال کنند. آنها رادیوی خود را در شیارهای داده ی همراه با دیگر گره های فعال نیز روشن نگه می دارند تا داده را از آنها ارسال کنند.

6. تقریب کم هزینه ی انحراف کلاک

سناریوی نشان داده شده در شکل 5 را در نظر می گیریم، که در آن چاله (خط ممتد) بسته ها را به گره های حس گر ارسال می کند. برای ساده سازی، پیوند ارتباطی تک هاپی را نشان داده ایم. بهر حال، در سناریو های چند هاپی، با توجه به تاخیر ارسال جمع پذیر بین هاپ ها، تفسیری مشابه در نظر گرفته می شود. به یاد داشته باشید انحراف زمان می تواند با توجه به چاله مثبت یا منفی باشد.

در ارسال Kth، گره چاله زمان ارسال می کند. این زمان بوسیله ی گره i در زمان محلی دریافت می شود. گره چاله، یک بسته را به گره محلی i در هر برای طول زمان کل ارسال می کند. لازم به ذکر است که در ، k انتقال رخ می دهد.ذکر این مورد که ارتباط بین گره ها در فواصل زمانی ثابت لازم نیست ارزشمند است. این اتفاق امکان تغییر پویای چرخه ی وظیفه ی ارتباط بین گره ها به ازای ملزوماتمان را فراهم می کند.

تقریب کمترین مربعات

همه ی کلاک ها به طور ذاتی غیر خطی هستند، بهر حال با توجه به انحراف آلن کم برای دوره ی زمانی کوتاه، مدل کلاک می تواند خطی سازی شود تا به شکل یک مدل مرتبه اول در آید.

7. ارزیابی عملکرد زیبای خفته

عملکرد زیبای خفته را براساس مصرف انرژی سراسری گره ها در یک WSN ارزیابی کرده ایم. در همین رابطه، کاهش چرخه ی وظیفه ی گره ها در تناوب زمانی بزرگتری را مورد پژوهش قرار داده ایم. علاوه بر این، عملکرد را به لحاظ نرخ دریافت بسته (PRR) نظارت کرده ایم.

جزییات پیاده سازی

زیبای خفته روی پلتفرم Tmote Sky و با استفاده از سیستم عملیاتی Contiki پیاده سازی می شود. قابلیت های هسته ی گلوسی را با استفاده از سیلاب سریع برای بدست آوردن همگام سازی کلاک دقیق به کار برده ایم. علاوه بر این از پیاده سازی های LWB و FS-LWB پیشین نیز اتخاذ کرده ایم. از آنجایی که زیبای خفته دارای هرگونه مولفه ی خاص پلتفرم نیست، از این رو مستقیما روی هر پلتفرمی که گلوسی به ان انتقال داده شود قابل استفاده است.

8. نتیجه گیری

برای اماده سازی در برابر شرایط مختلف شبکه و خرابی های گره، پیاده سازی WSN معمولا شامل گره های مازاد می شود. زمان بندی گره از این ویژگی با محدود کردن تعداد گره های فعال استفاده می کند. این محدود کردن در جهت حاصل کردن عملیات شبکه با انرژی کارآمد و بدون تخطی کردن از ملزومات پوشش نرم افزار می باشد. بهر حال، تنها محدود کردن تعداد گره های فعال کافی نیست؛ گره های فعال باید یک (زیر)شبکه ی متصل را شکل دهند. بدنه ی بزرگی از کار روی گزینش یک زیرمجموعه از گره هایی که آرایش کامل را پوشش می دهند وجود دارد. این روش های بهینه سازی شده ی زمان بندی گره به طور کلی قابل استفاده برای آرایش دنیای واقعی نیستند چون نیازمند اطلاعات توپولوژی کامل می باشند که بدست آوردن دقیق آن سخت و پرهزینه است.

زیبای خفته که چروتوکل ارتباطی با انرژی کارآمد است را ارائه می کنیم، این پروتکل با اطلاعات توپولوژی جزیی کار می کند و از پروتکل های مدرن بر پایه ی سیلاب (LWB و FS-LWB) در سناریوهای زمان بندی گره بهتر کار می کند. زیبای خفته این مسئله را با در نظر گرفتن موارد پیش رو به دست اورده است i) یک مکانیزم کارآمد شناسایی همسایه که گزینش یک مجموعه ی حداقلی اما مرتبط از گره های فعال را مقدور می سازد و ii) یک روش تقریب زنی انحراف کلاک ساده اما استادانه که به گره ها امکان خوابیدن برای مدت زمانی بیشتر بدون نیاز به همگام سازی مجدد آشکار را می دهد. مورد دوم برای ایجاد امکان استفاده از سیلاب کارآمد تحریک شونده با زمانِ گلوسی مهم است. روش همگام سازی زمان ما می تواند در هر نرم افزاری به کار گرفته شود. عملکرد زیبای خفته را با پروتکل های مدرن در دو بستر آزمایش (ایندریا و فلاکلب) مقایسه کردیم. این مقایسه نشان داد که در کسری از انرژی مصرف شده، عملکردی مشابه (PRR) می تواند حاصل شود. فاکتور کاهش سه را برای بهترین سناریو با 5% گره فعال ثبت کردیم.

این مقاله ISI در سال 2016 در نشریه آی تریپل ای و در کنفرانس بین المللی Adhoc، توسط دانشگاه صنعتی دلفت منتشر شده و در سایت ای ترجمه جهت دانلود ارائه شده است. در صورت نیاز به دانلود رایگان اصل مقاله انگلیسی و ترجمه آن می توانید به پست دانلود ترجمه مقاله ارتباط موثر برای زمان بندی گره در سایت ای ترجمه مراجعه نمایید.