بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بهبود روش جمع آوري داده در LEACH-C با استفاده از عدم ارسال داده هاي همبسته و تخمين انرژي در شبکه هاي حسگر بيسيم
چکيده : جمع آوري داده در شبکه هاي حسگر بيسيم مستلزم مصرف انرژي است . بدليل محدوديت انرژي گره ها، بهره وري انرژي بايد بعنوان يک هدف کليدي مدنظر قرار گيرد. از اينرو کلاستربندي يک روش مناسب در مديريت مصرف انرژي، مورد استفاده قرار ميگيرد. براي اين منظور الگوريتم LEACH بعنوان روش پايه مورد توجه قرار گرفته است . اين الگوريتم از روش کلاستربندي توزيع شده براي جمع آوري داده ها و تجميع آنها استفاده ميکند. در LEACH-C کلاستربندي را به صورت متمرکز انجام ميشود. در روش LEACH-CE تعيين انرژي گره ها در دو دوره اول جمع آوري ميشود و دوره هاي بعدي با استفاده از دوره هاي قبلي تخمين زده ميشود. وجود داده هاي همبسته زماني در همه اين روش ها موجب اتلاف انرژي ميشود. روش TINA و بهبود آن براي عدم ارسال داده هاي همبسته مطرح شده است . اين روش ها خطاي گزارش دهي دارند. در اين مقاله ايده عدم ارسال داده هاي همبسته زماني گره ها با استفاده از سريهاي زماني مطرح شده است . همچنين مدلي جهت تخمين انرژي باقيمانده گره ها توسط ايستگاه پايه ارائه شده است . در نهايت روشي براي آگاهي ايستگاه پايه از تعداد داده هاي همبسته هرگره براي تخمين دقيقتر انرژي پيشنهاد شده است . نتايج ارزيابي نشان ميدهد که روش پيشنهادي کارايي بهتري از نظر ميزان مصرف انرژي و طول عمر شبکه نسبت به روش هاي مشابه دارد.
کلمات کليدي: کلاستربندي، همبستگي داده اي، سريهاي زماني، تخمين انرژي.
١- مقدمه
شبکه هاي حسگر بيسيم ، کلاسي از شبکه هاي موردي بيسيم هستند. در اين شبکه ها گره هاي حسگر داده ها را از محيط فيزيکي جمع آوري و پردازش نموده و به ايستگاه پايه ارسال مينمايند. بنابراين اجازه مانيتورينگ و کنترل انواع پارامترهاي فيزيکي را ميدهند.
هرگره حسگر انرژي محدودي دارد و در اغلب کاربردها امکان جايگزيني منابع انرژي نيست . بنابراين عمرگره هاي حسگر بشدت به انرژي ذخيره شده در باتري آن وابسته است . کلاستربندي يکي از روش هاي طراحي است که براي مديريت در شبکه هاي حسگر بيسيم استفاده ميشود. در اين روش شبکه به تعدادي مجموعه مستقل تقسيم مي شود که به اين مجموعه ها کلاستر گفته ميشود. پس هر کلاستر داراي تعدادي گره حسگر و يک گره سرکلاستر است . گره هاي عضو يک کلاستر، داده هاي خود را به گره سرکلاستر مربوطه شان ارسال ميکنند. گره سرکلاستر داده ها را تجميع نموده [١] و آنرا به ايستگاه پايه ميفرستد. بنابراين کلاستربندي در شبکه هاي حسگر داراي مزايايي مانند پشتيباني از تجميع داده ، تسهيل جمع آوري اطلاعات ، سازماندهي يک ساختار مناسب براي مسيريابي مقياس پذير، و انتشار کاراي داده بروي شبکهميباشد. جمع آوري داده در شبکه هاي حسگر بيسيم يکي از عمليات مهم اين شبکه ها ميباشد و براي اين منظور روش هاي زيادي پيشنهاد شده است . پروتکل LEACH١ [٣] بعنوان يک روش پايه سلسله مراتبي در نظر گرفته شده است .
اين روش براي کاربردهاي مانيتورينگ مناسب ميباشد. هر گره به صورت دوره اي اطلاعات را حس کرده و ارسال ميکند. در اين الگوريتم از روش کلاستربندي براي جمع آوري داده ها و تجميع آنها استفاده ميشود. انتخاب کلاستر و سرکلاستر به صورت تصادفي صورت ميپذيرد، لذا هيچ تضميني براي انتخاب دقيق تعداد بهينه سرکلاسترها و همچنين توزيع يکنواخت آنها در سرتاسر شبکه وجود ندارد. بهبودهاي بسياري در مورد پروتکل LEACH ارائه شده است . روش LEACH-C٢ [٤] نمونه اي از اين بهبود است .
درLEACH-C، شکل دهي کلاسترها در آغاز هردوره با استفاده از الگوريتم متمرکز بوسيله ايستگاه پايه انجام ميشود. ايستگاه پايه از اطلاعات رسيده از گره ها براي پيداکردن تعداد از پيش تعيين شده سرکلاسترها و پيکربندي شبکه درون کلاسترها استفاده ميکند. اين اطلاعات شامل موقعيت و انرژي گره ها است . بهبود ديگري که بر روي اين الگوريتم صورت پذيرفته است استفاده از تخمين ميباشد.
يکي از اين الگوريتم ها،LEACH-CE٣ [٥] است . در تکنيک پيشنهاد شده سطح انرژي گره ها در دو دوره اوليه از تمامي گره ها جمع - آوري ميشود و در دوره هاي ديگر جمع آوري نميشود. بجاي آن ، ميانگين انرژي دوره هاي اوليه بکار ميرود. با توجه به اينکه تخمين انرژي در اين روش دقيق نيست ، اين طرح کلاستربندي کارا و مناسب نميباشد.
هر گره حسگر مشاهده کننده يک پديده فيزيکي است . پديده هاي فيزيکي مانند درجه حرارات و ... نيز بصورت پيوسته با زمان تغيير ميکنند. بنابراين اطلاعات دريافت شده توسط گره حسگر با همديگر وابستگي دارند. الگوريتم هايي مبني بر عدم ارسال داده هاي همبسته مطرح شده است . الگوريتم TINA٤ [٧] يکي از آنها ميباشد. در اين الگوريتم گره حسگر مقدار داده نمونه برداري شده را با داده قبلياش مقايسه ميکند، اگر فرق کند ارسال ميکند در غير اينصورت به خواب ميرود. بهبودي که براي اين الگوريتم مطرح شده ، اين است که گره حسگر با مقايسه مقدار نمونه برداري جديد با آخرين داده گزارش داده شده تصميم به ارسال ميگيرد[٨]. الگوريتم - هاي ذکرشده به خاطر وجود خطاي گزارش دهي ، مناسب بنظر نمي رسند. بنابراين براي تخمين حتيالامکان دقيق انرژي گره ها و با وجود داده هاي وابسته زماني، روش سريهاي زماني [٩] مطرح شده است . اين روش از يک خط روند براي ارسال داده استفاده ميکند ولي نحوه شکل گيري خط روند در روش پيشنهادي مناسب بنظر نميرسد. لذا روشي پيشنهاد ميشود تا دقت گزارش دهي داده را بالا ببرد. سازماندهي بقيه مقاله به شرح زير است : در بخش ٢ کارهاي مرتبط را مرور ميکنيم . در بخش ٣ الگوريتم داده هاي همبسته ، تکنيک پيشگويي انرژي و روش ترکيبي معرفي ميشود. در بخش ٤ آناليز آزمايشات با گره هاي موجود ارائه شده است . نهايتا در بخش ٥ جمع بندي و بحث و گفتگو را بيان ميکنيم .
٢- مرور کارهاي مرتبط
LEACH 1-2
يکي از معروفترين پروتکل هاي مسيريابي سلسله مراتبي بر مبناي کلاستربندي، پروتکل LEACH ميباشد. در اين روش اعضاي هر کلاستر داده هاي خود را به سرکلاستر ميدهند. سرکلاستر بعد از تجميع آنها، اطلاعات تجميع شده را به BS ارسال ميکند.(شکل ١)
عمليات شکل گيري کلاستر و انتقال داده درLEACH در دو فاز صورت ميگيرد که اين فازها در شکل هاي ٢ و٣ نشان داده شده است . فاز Setup مرحله شکل گيري کلاستر و سرکلاستر مي باشد. در اين مرحله انتخاب کلاستر و سرکلاستر بصورت تصادفي صورت ميگيرد. بعد از شکل گيري کلاستر، سرکلاستر زمانبند TDMA را انتشار ميدهد تا زمان انتقال داده را براي گره هاي عضو مشخص نمايد. سپس وارد فاز Steady-state ميشود. در فاز steady- state، هر گره عضو کلاستر فقط در تکه زماني خودش داده را به سرکلاسترش انتقال ميدهد و در بقيه تکه هاي زماني جهت ذخيره انرژياش به حالت خواب ميرود. در اين روش ، سرکلاستر انرژي بيشتري را براي دريافت ، پردازش و ارسال مستقيم داده ها به گره BS مصرف ميکند. بنابراين براي افزايش طول عمر شبکه لازم است که نقش سرکلاستر بين گره هاي شبکه تعويض شود. بهبودهاي بسياري در مورد روش LEACH ارائه شده است که اولا حتي الامکان بهترين کلاستربندي و انتخاب سرکلاستر صورت پذيرد، ثانيا تا حدامکان سربار اين پروتکل کاهش پيدا کند. روش LEACH-C نمونه - اي از اين بهبود است .
LEACH-C 2-2
درLEACH-C، شکل دهيکلاسترها در آغاز هردوره با استفاده از الگوريتم متمرکز بوسيله ايستگاه پايه انجام ميشود. ايستگاه پايه از اطلاعات رسيده از گره ها که شامل موقعيت و انرژي آنها است ، در طول فاز آماده سازي براي پيداکردن تعداد از پيش تعيين شده سرکلاسترها و پيکربندي شبکه درون کلاسترها استفاده ميکند. بعدا گروه بندي گره ها در کلاسترها براي کمينه کردن مصرف انرژي به منظور انتقال داده هاي خود به سر کلاسترهاي مربوطه انجام ميشود. نتايج نشان ميدهد که کارايي کليLEACH-C بخاطر شکل دهي بهينه کلاسترها بوسيله ايستگاه پايه بهتر از LEACH است . ولي مصرف انرژي بالايي دارد.
LEACH-CE 3-2
در روش LEACH-CE [٥]، سطح انرژي فقط در فاز تنظيمات دو دوره اوليه از تمامي گره ها جمع آوري ميشود و در دوره هاي ديگر جمع آوري نميشود. بجاي آن بخاطر اطلاع از سطح انرژي باقيمانده هر گره ، ميتوانيم از اطلاعات دو دوره اوليه ، ميانگين مصرف انرژي هر گره را محاسبه کنيم . يعني کسر ميزان انرژي محاسبه شده از سطح انرژي گره موجب پيش بيني سطح انرژي فعلي ميشود. مشکلي که براي اين الگوريتم مطرح ميشود اينست که اولا تخمين انرژي دقيق صورت نميگيرد و ثانيا اگر گره ها داده همبسته داشته باشند و عدم ارسال داده همبسته به منزله اعتبار اطلاعات قبلي ميباشد، در اين صورت اين طرح کلاستربندي کارا و مناسب نميباشد.
TINA 4-2
گرههاي حسگر پديده هايي را که مشاهده ميکنند بصورت پيوسته با زمان تغيير ميکند. بنابراين اطلاعاتي که توسط گره دريافت مي - شود با همديگر وابستگي دارند. اين حالت ها براي پديده هاي فيزيکي که متوالي يا تکراري هستند و يا در يک کاربرد که دقت زياد مهم نباشد و يا اينکه در شبکه اي که در يک ناحيه تراکم گره ها زياد باشد بيشتر اتفاق ميافتد. دو نوع وابستگي داده اي وجود دارد: ١.
وابستگي مکاني ٢. وابستگي زماني. در وابستگي مکاني تجميع در داخل شبکه توسط سرکلاسترها صورت ميگيرد[٦ ]. اين يکي از روشهايي است که براي کاهش مصرف انرژي مطرح شده است . بنابراين سرکلاستر داده هاي همبسته گره ها را تجميع کرده و به ايستگاه پايه ارسال ميکند. اين باعث ميشود تا از اتلاف انرژي جلوگيري شود. اين روش در پروتکل LEACH پياده سازي شده است . اما در وابستگي زماني هر گره ميتواند در زمان هاي متوالي داده هاي همبسته داشته باشد. ايده اصلي الگوريتم TINA اين بود که گره هاي حسگر زماني داده شان را ارسال کنند که فقط اگر داده خوانده شده توسط حسگر با داده خوانده شده قبلي فرق کند، در غير اينصورت به حالت خواب ميرود. اين الگوريتم داراي خطاي گزارش دهي ميباشد. يک بهبود براي اين الگوريتم ارائه شده است .
٢-٥ بهبود TINA
در اين روش گره حسگر با مقايسه مقدار نمونه برداري جديد با آخرين داده گزارش داده شده تصميم به ارسال ميگيرد. با اين حال گره - هاي حسگر آخرين داده گزارش شده را نگه مي دارند[٨]. براي درک بهتر، اين قسمت را با يک مثال شرح ميدهيم . فرض کنيد داده - هايي که يک گره حسگر دريافته است بترتيب ١.٠، ٠.٩٥، ١.٠٥، ٠.٩٥، ١.٠٥ باشد. يک حد آستانه در نظر گرفته شده است که تا اين حد، تغييرات داده مهم نيست . مقدار اين حدآستانه ١٠% در نظر گرفته شده است . اولين داده يعني ١.٠ با موفقيت ارسال ميشود، در دوره بعدي داده ٠.٩٥ ، زماني که ارسال نخواهد شد در غير اينصورت ارسال خواهد شد. همانطور که قبلا 1.0اشاره شد اغلب پديده ها بصورت پيوسته با زمان تغيير ميکنند. بنابراين اکثر داده ها در فاصله هاي زماني يا حالت صعودي دارند يا حالت نزولي. يا اينکه مثلا در يک کاربرد مانند دما در يک فاصله زماني معين اتفاق خاصي رخ دهد. در اين صورت روش هاي مطرح شده خطا- دار بوده و مناسب نمي باشند. روشي را پيشنهاد ميدهيم تا اين الگوريتم را بهبود داده و از اتلاف انرژي جلوگيري نمايد.
٣- روش پيشنهادي
٣-١ ارائه روش ها
سه تا ايده پيشنهاد شده است . ١- همبستگي زماني داده اي ٢- مدل تخمين انرژي گره ها ٣- روش ترکيبي. درالگوريتم وابستگي داده اي زماني، از روش پيش بيني سري هاي زماني (TSF٥) جهت ارسال يا عدم ارسال داده استفاده شده است . پس در لحظه t يعني شروع هر دوره ايستگاه پايه درصد خطا را به تمامي گره ها ارسال ميکند. اولين داده توسط گره حس شده و ارسال ميشود. داده هاي دوم و سوم و چهارم براساس الگوريتم TINA بهبود يافته ارسال ميشوند. سپس گره تابع سريهاي زماني را براي تعيين مقدار پيش بيني مدل خط روند اجرا ميکند، تا مدل روند را ايجاد نمايد. در لحظات بعدي داده حس شده با مقدار پيش - بيني مدل روند مقايسه ميشود. اگر اختلاف بين اين دو مقدار از يک حد آستانه اي تجاوز کند، داده به گره مورد نظر ارسال ميشود و گره تابع پيش بيني مدل روند را مجددًا محاسبه مي نمايد تا مدل خط روند را به روز نمايد. در غير اينصورت گره حسگر داده حس شده را به گره مورد نظر ارسال نميکند. مدل پيشنهادي پيشگويي انرژي گره ها را LEACH-CES٦ ناميده و به اين صورت توضيح ميدهيم .
براي انجام بهترين کلاستربندي لازم است انرژي گره ها را بدانيم . روش تخمين يکي از روش هايي هست که کم هزينه بوده و مناسب ميباشد. بنابراين از روش تخمين انرژي استفاده ميکنيم . براي اين کار پروتکل LEACH-C را به سه فاز تقسيم کرده ايم . فاز توپولوژي سازي، setup-state و steady-state. در فاز اول گره ها در شروع شبکه موقعيت خودشان را به ايستگاه پايه ارسال ميکنند. BS با توجه به موقعيت گره ها توپولوژي شبکه را ايجاد مينمايد. بعد از اينکه توپولوژي در ايستگاه پايه تشکيل شد، ايستگاه پايه فاصله گره ها را از همديگر محاسبه ميکند. در فاز تنظيمات با استفاده از يک مدل رياضي ساده مقدار انرژي مصرفي هر گره محاسبه ميشود و از انرژي اوليه اش کسر شده و مقدار انرژي باقيمانده محاسبه ميگردد. در نهايت کلاستربندي را انجام داده و به فاز steady-state ميرود.
در اين فاز هم براي هر گره ، الگوريتم داده هاي همبسته زماني طبق روش زير بکار گرفته ميشود.
٣-٢ فرايند روش هاي پيشنهادي
٣-٢-١ روش پيش بيني خطي با استفاده از سريهاي زماني
روش پيش بيني خطي يک تکنيک قوي براي پيش بيني سريهاي
زماني در يک محيط تغييرپذير با زمان ميباشد. اين روش توسط معادله (١) بيان شده است که يک روش بازگشتي است [٩]:
مقدار تخميني در زمان t بصورت يک تابع خطي از مقادير قبلي آن که در زمانهاي توليد شده است بدست ميآيد. در اين معادله متغيرهاي ضرايب پيش بيني خطي هستند، m درجه مدل ، T زمان نمونه برداري، تخمين مشاهده بعدي مقادير مشاهده شده حال و گذشته مي باشند. خطاي پيش بيني که معادل اختلاف بين مقادير واقعي و پيش بيني هست ، (٢) بايد به مينيمم برسد.
براي تخمين ضرايب مدل پيشگويي خطي، از روش کمترين مربعات خطا استفاده مي کنيم و معادله (١) را با در نظر گرفتن خطاي
مدل سازي در معادله (٣) بازنويسي ميکنيم :
خطاي ايجاد شده به خاطر منطبق نشدن مقدار واقعي با مدل پيش گويي ميباشد. پس براي محاسبه ضرايب am...,a٢,a١ از معادله (٣) روش کمترين مجموع مربعات خطا را بکار برده و از مجموعه دستگاه هاي معادلات خطي در (٤) استفاده ميکنيم :
عناصر ماتريس A ضرايبي هستند که ميتوانند با روش کمترين مربعات خطا با فرمول (٥) محاسبه شوند.
در رابطه (٥)، ترانهاده ماتريس هست و معکوس ماتريس هست . در عمل :
• اگر m بزرگتر از مقدار مورد نياز انتخاب شود، رابطه (٥) نميتواند براي هر مجموعه يکتايي از ضرايب قابل حل باشد، براي اينکه برخي ستونها در ماتريس از همديگر مستقل نيستند. از اينرو منحصربفرد شده و معکوس نخواهد شد. اين بدين معني است که تعداد نامحدودي جواب براي ضرايب بدست خواهد آمد. در اين حالت تعداد معادلات مستقل ، از تعداد مجهولات کمتر ميشود. به بيان هندسي، تطبيق يک يا چندين خط بر يک نقطه منفرد ميباشد.
