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

چکیده

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

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

1. مقدمه

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

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

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

A. انگیزه

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

B. رویکرد راه حل و چالش ها

         در این کار، زیبای خفته را ارائه می کنیم، یک پروتکل ارتباطاتی با انرژی کارآمد برای سناریوهای زمان بندی گره. این پروتکل از یک عملیات شیار بندی و به دقت همگام شده در میان گره ها استفاده می کند و در زمانی مصرف کننده آن را ملزوم می کند (بر مبنای ملزومات کاربرد)، مکانیزمی کشش بنیان، برای جمع آوری داده از هر گره فعال را به کار می برد. این موضوع، زمان روشن بودنِ بسیار فشرده ای از گره ها را تضمین می کند و زمان خاموش بودن در بین دو راند سنجش را افزایش می دهد. عملیات کارآمدِ زیبای خفته در مکانیزم سیلاب سریع فراهم شده بوسیله ی گلوسی (Glossy) مسیر یابی می شود. همانند LWB، که آن هم بر مبنای گلوسی است، زیبای خفته شامل یک بخش مرکزی است که اتفاق رخ داده در هر شیار را کنترل می نماید. به منظور کارآمد و منعطف بودن، مکانیزم های کنترل در مصرف کننده اجرا می شوند و طراحی شده اند تا چالش های پیش رو را مورد خطاب قرار دهند. اول، هر چقدر که ناکارآمدیِ ارتباطات چند هاپی در WSN که بوسیله ی ارسال مجدد و در هر هاپ ایجاد شده تاخیر یابد، پیامدهای این عوامل نیز باید محدود شود. علاوه بر این، در هر شیار ارتباطات، تنها آن گره هایی که روند مسیر یابی را فراهم می کنند باید در نظر گرفته شوند در حالیکه تاخیر و ارسال مجدد حداقل را نگه داری کنند. دوم، هر چقدر که توپولوژی شبکه در طول زمان تغییر کند (برای مثال، ناشی از نوسانات کیفیت پیوند)، مصرف کننده باید برای این موضوع به حساب آید و تضمین کند که در هر زمان مسیری معتبر از هر گره فعال به مصرف کننده وجود دارد. چالش، فراهم کردن شناسایی همسایه در کمترین هزینه است. سوم، از آنجایی که کارآمدی زیبای خفته ناشی از عملیات های فعال شونده با زمان است، لذا ملزوم می باشد تا همگام شدگی دقیقی میان گره ها حفظ شود. این اتفاق باید حتی در زمانی که گره ها برای مدت زمانی طولانی به خواب می روند نیز برقرار شود. به طور خاص، طرح های زمان بندی گره استاندارد فرض می کنند که وقتی گره ها بیدار می شوند، می توانند بلافاصله به شبکه ملحق شوند. بیدار کردن پشته ی پروتکل کامل، در واقعییت می تواند زمان بر باشد. بنابراین، مازاد حداقل/صفر باید در زمانی که یک گره پس از مدتی طولانی از غیر فعال بودن رادیو مجددا به شبکه ملحق می شود، تضمین گردد.

C. مشارکت ها

        زیبای خفته به صورت کارآمد به چالش های ذکر شده در بالا هجوم می برد. مخصوصا، روش های مدرن را با مشارکت های زیر بهبود می بخشیم:

1) جمع اوری داده ی کارآمد برای زمان بندی گره: طراحی و ارزیابیِ پروتکل ارتباطی را فراهم کرده ایم. این پروتکل زمان بندی سیلاب سریع و خاموش-روشن را در جهت پشتیبانی از سناریوهای پشتیبانی تجمیع می کند. لازم به ذکر است که تنها یک مجموعه ی کوچک و عامل از گره ها دراین سناریوهای پشتیبانی ملزوم هستند تا داده یخود را به مصرف کننده گزارش دهند. ما طراحی و ارزیابی پروتکل ارتباطی را بوسیله ی جداسازی ملاحظات گزینش گره و جمع آوری داده انجام داده ایم. با توجه به این موضوع، زیبای خفته یک زیر لایه ی ارتباطی شیار بنیان و کارآمد است که طرح های مختلف گزینش گره را پشتیبانی می کند.

2) شناسایی همسایه ی کارآمد: شناسایی همسایگی، سرویسی ملزوم برای بسیاری از کاربردهای WSN است. ما یک مکانیزم پارازیت همگام شده پیشنهاد می دهیم که کارآمدانه به هر گره برای یادگیری در مورد همسایگی هایش کمک می کند. این کار بوسیله ی فعالیت رادیویی حداقل می باشد. این کار از طریق داشتن گره هایی که تنها روی والدین بالقوه تمرکز کرده اند و به روزرسانی اطلاعات به جای شناسایی آن از ابتدا در هر دفعه حاصل می شود. این موضوع به الگوریتم های زمان بندی گره ای که در مواجهه با اتصالات و پویایی شبکه هستند کمک می کند.

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

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

Abstract

        Typical Wireless Sensor Networks (WSN) deployments use more nodes than needed to accurately sense the phenomena of interest. This redundancy can be leveraged by switching-on only a subset of nodes at any time instant (nodescheduling) and putting the remaining nodes sleep. This effectively extends the network lifetime. In addition to sensing coverage, node-scheduling schemes must also ensure that (i) the network stays connected, and (ii) the time needed to wake-up the complete protocol stack after sleeping is minimized. We present Sleeping Beauty, a highly-efficient data collection protocol that aids node-scheduling schemes in both aspects.

         Sleeping Beauty uses a slotted and tightly synchronized communication primitive, where a node keeps its radio off for most of the time, except in the slots when it needs to participate for successful communication. Further, an efficient neighbor-discovery mechanism is included that provides partial, but sufficient topology information (potential parents) to avoid network partitions. Furthermore, Sleeping Beauty employs a novel, yet simple clock-offset estimation technique that maintains highly-accurate time synchronization over long radio-off periods (i.e., less than 500 µs deviation even after 45 min of sleeping). This minimizes time wasted in resynchronizing the network in between data collection rounds. Through experiments on two different testbeds, we verified that Sleeping Beauty decreases the duty cycle up to a factor of 3 compared to state-of-the-art techniques, while achieving similar delivery ratios.

I. INTRODUCTION

        Even after more than a decade of research, energy-efficient communication –and data collection in particular– is still a holy grail within the community. Part of the challenge is that typical WSN deployments include more nodes than needed to accurately sense the phenomena of interest. This redundancy safe guards, on the one hand, against failing nodes and links, but on the other hand leads to inefficient use of energy. Nodescheduling schemes address the latter aspect by keeping only a (minimal) subset of nodes active at any instant. They do so by selecting a representative from each so-called common sensing group. A common sensing group can be formed when (i) a common target or area is covered by a set of nodes [1], [2], or (ii) the data generated by the nodes show high degree of correlation such that sensed data for multiple nodes can be reconstructed using data from a single node [3], [4]. In either case, representative node(s) from each group needs to be active during the data collection round. Based on the application scenario, only one or multiple representative (such as k-coverage) nodes are selected active. By alternating duties across rounds, nodes save energy and extend the network lifetime.

        As an example, Fig. 1a shows a network of six nodes, where only a subset of active nodes is sufficient under the common sensing group regime (indicated by color). Fig. 1b shows one such combination. However, if nodes {3, 4, 5} are selected instead of {1, 4, 5}, all groups are still represented, but the network would be disconnected from the sink making it impossible for the application to receive the sensed data.

       Given such common sensing groups and network topology of a WSN, the selection of a minimal set of active nodes that guarantees both (a) the connectivity of active nodes to the sink, and (b) the representation of each group by active node(s), is shown to be NP-hard [5], [6]. Thus a number of heuristic algorithms have been proposed in the literature [7], [8] to select close to optimal sets of active nodes satisfying the above constraints. After selecting the active nodes for a round, usually by the centralized sink node, the sensed data from these nodes still need to be collected efficiently. That is the main challenge we address in this paper.

A. Motivation

       Based on the application scenario, a different node scheduling strategy has to be devised, e.g., k-coverage [7], pointcoverage [5], spatial correlation [3], etc. Node-scheduling algorithms, which select a subset of active nodes, follow two general strategies. Either they select the set of active nodes at the application layer and leave the routing to the underlying protocols [7], [5], or they jointly perform node selection and routing [1]. In the first case, an advanced routing protocol is required that should use a minimal number of relay nodes besides the chosen active nodes in order not to diminish the overall efficiency. In the second case, the cross-layer solution is tightly coupled to the particular scheduling scheme making it non-reusable for other scheduling strategies. Thus there is a need for a generic data-collection algorithm that ensures highly-efficient network operation irrespective of the nodescheduling policy.

B. Solution approach and challenges

       In this work we present Sleeping Beauty, an energy-efficient communication protocol for node-scheduling scenarios. It uses a slotted and tightly synchronous operation among the nodes, and deploys a pull-based mechanism to collect data from every active node when the sink requires it (based on application requirements). This ensures a highly compact radio-on time of the nodes and increases radio-off time in-between two sensing rounds. The efficient operation of Sleeping Beauty is rooted in the fast-flooding mechanism provided by Glossy [9]. Like LWB [10], which is also based on Glossy, Sleeping Beauty contains a central part controlling what happens in every slot. In order to be flexible and efficient, the control mechanism runs at the sink and has been designed to address the following challenges. First, as the inefficiency of multihop communication in WSN caused by retransmissions and per-hop delays, repercussion of these factors need to be restrained. Moreover, in every communication slot, only those nodes that provide routing progress need to be involved while maintaining minimal retransmission and delay. Second, as the network topology varies over time (e.g., due to link quality fluctuations), the sink should account for this and ensure that a valid path exists from any active node to the sink at all times. The challenge is to provide neighbor discovery at minimal cost. Third, since the efficiency of Sleeping Beauty stems from time-triggered operations, a tight synchronization among the nodes needs to be maintained, even when nodes go to sleep for long duration. If not, what was gained in node-scheduling will be lost in trying to synchronize again. In particular, standard node-scheduling schemes assume that once nodes wake-up they can instantly join the network. In reality, however, waking up the complete protocol stack can be time consuming. Thus, zero/minimal overhead should be ensured when a node rejoins the network after long periods of radio inactivity.

C. Contributions

        Sleeping Beauty efficiently tackles the challenges mentioned above. Specifically, we improve state-of-the-art with these contributions:

1) Efficient data collection for node scheduling: We provide the design and evaluation of a communication protocol that combines fast flooding and on-off scheduling to support scenarios where only a small, representative set of nodes need to report their data to the sink. We do so by separating the concerns of node selection and data collection. In that respect Sleeping Beauty is an efficient, slot-based communication substrate supporting different node selection schemes.

2) Efficient neighbor discovery: Neighborhood discovery is a required service for many WSN applications. We propose a synchronized strobing mechanism that helps every node to learn about its neighborhood efficiently, that is, with minimal radio activity. This is achieved by having nodes focus only on potential parents and update information instead of discovering it every time from scratch. This aids node-scheduling algorithms in coping with network connectivity and dynamics.

3) Accurate and long-lasting time synchronization: Much of Sleeping Beauty’s efficiency stems from the fact that operations are tightly synchronized. To counter the drifts of the hardware clocks in nodes, Glossy (who pioneered this style of communication) utilizes frequent network-wide floods, taking up a significant amount of energy. To avoid this overhead we propose a simple clock estimation algorithm with which nodes – even after 45 min – are still synchronized within an error bound of 500 µs.

        We substantiate our claims by evaluating the performance of Sleeping Beauty on two public testbeds –Indriya [11] and FlockLab [12]– and on a local setup. We compare against two Glossy-based communication protocols LWB [10] and Forwarder Selection [13], showing overall reductions in energy consumption.

چکیده

1. مقدمه

A. انگیزه

B. رویکرد راه حل و چالش ها

C. مشارکت ها

2. پیش زمینه

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

A. اهداف طراحی

B. معماری

C. فراچارچوب به عنوان بلوک ساختمانی

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

A. ملحق کردن گره

B. ساخت یک دیدگاه جزیی از شبکه

C. ارزیابی انحراف کلاک

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

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

B. به روز رسانی لیست والدین

C. تصحیح انحراف کلاک

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

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

B. به روز رسانی حداقل مربعات تکراری

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

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

B. ارزیابی پلتفرم ها

C. دقت تقریب انحراف کلاک

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

8. نتیجه گیری

منابع

Abstract

1. INTRODUCTION

A. Motivation

B. Solution approach and challenges

C. Contributions

2. BACKGROUND

3. A FIRST LOOK AT SLEEPING BEAUTY

A. Design goals

B. Architecture

C. Superframe as a building block

4. BOOTSTRAPPING

A. Node joining

B. Building a partial view of the network

C. Clock-offset estimation

5. STEADY-STATE OPERATION

A. Periodic active node selection

B. Updating the list of parents

C. Clock-offset correction

6. LOW-COST CLOCK-OFFSET ESTIMATION

A. Least squares estimator

B. Iterative Least Square update

7. PERFORMANCE EVALUATION OF SLEEPING BEAUTY

A. Implementation details

B. Evaluation platforms

C. Accuracy of clock-offset estimation

D. Sleeping Beauty’s performance

8. CONCLUSIONS

REFERENCES