موضوع مقاله:

“پردازش موازی دادههای شبکه سنسور با استفاده از پایگاه دادههای مبتنی بر ستون”

بسیاری از برنامه های شبکه حسگر بی سیم (WSN) نیاز به اتصال داده های حسگر متعلق به گره های حسگرهای مختلف دارند. برای پردازش پیوستن، مهم است که هزینه های ارتباطی را به حداقل برسانید، زیرا مصرف کننده اصلی قدرت باتری است. در این مقاله، یک روش اتصال موازی برای شبکه های حسگر معرفی می کنیم. WSN شامل بسیاری از گره های حسگر مستقل است و یک پایگاه طبیعی برای یک معماری shared-nothing (نوعی معماری توزیع محاسباتی است که در آن هر گره مستقل و خودکفا است و هیچ نقطه ای از تناقض در سراسر سیستم وجود ندارد. به طور خاص، هیچ یک از گره ها حافظه یا ذخیره سازی دیسک را به اشتراک نمی گذارد0)را برای اجرای پردازش موازی فراهم می کند. الگوریتم پیشنهادی اتصال موازی بر اساس داده های حسگری است که در پایگاه داده های column-oriented (ستون گرا) ذخیره می شود. یک پایگاه داده ستون گرا، داده ها را به صورت ستونی ذخیره میکند نه مانند پایگاه داده های ارتباطی قدیمی که به صورت ردیفی بود. الگوریتم پیشنهادی به دو دلیل روشن، باعث صرفه جویی در انرژی میشود است. اول، بر خلاف پایگاه داده های ارتباطی، تنها ستون های مرتبط، برای پردازش نهایی اتصال، به منطقه اتصال ارسال میشوند. دوم، پردازش موازی با داده های حسگر، همچنین باعث افزایش کارایی می شود. تجزیه و تحلیل عملکرد نشان می دهد که الگوریتم پیشنهادی از الگوریتم های اتصال برای داده های حسگر که بر اساس پایگاه داده های ارتباطی استفاده می شوند، بهتر عمل می کند.

1) معرفی

بسیاری از برنامه های کاربردی شبکه های حسگر، نیاز به همبستگی خواندن سنسورهای پراکنده در گره های حسگر دارند. به عنوان مثال، در یک سیستم ردیابی شی، ممکن است به اشیایی که از یک منطقه مشخص به منطقه مشخص دیگر سفر کرده اند علاقه مند شوید تا میزان ترافیک و سرعت اشیاء خاص را کنترل کنید. شبکه حسگر می تواند به عنوان یک پایگاه داده توزیع شده مدل شود و خواندن سنسور ها با استفاده از پرس و جو ها جمع آوری و پردازش می شود. برای به کار بردن بهتر sensor reading ها، آنها می توانند به عنوان داده در یک پایگاه داده رابطه ای ذخیره شوند. پیوند، یک عمل مهم در پیدا کردن ارتباط sensor reading ها است.

یکی از مهمترین معیارهای کارایی در پردازش عملیات پیوست برای شبکه های حسگر ، کاهش هزینه کل ارتباطات است. هزینه کل ارتباطات، همان انتقال کل داده ها بین گره های حسگر همسایه است. صرفه جویی در هزینه ارتباطات مهم است زیرا هر گره سنسور توان باتری را محدود کرده و ارتباطات داده ها مصرف کننده اصلی انرژی باتری هستند. راه ساده ای برای پاسخ دادن به یک درخواست پیوست ad-hoc برای یک برنامه، مانند ردیابی شی، این است که sensor reading ها را به ایستگاه پایه انتقال دهید و پیوند را در ایستگاه پایه انجام دهید. این رویکرد ممکن است هزینه ی بالای ارتباطات را از بین ببرد زیرا تمام داده های سنسور باید به ایستگاه پایه منتقل شوند. یک رویکرد بهتر این است که پیوند را در داخل شبکه حسگر انجام دهید. در این رویکرد از شبکه، چندین گره حسگر برای عمل پیوند همکاری می کنند ، یعنی پیوند توزیع شده است. با توجه به محدودیت منابع، هیچ گره حسگر، به تنهایی قادر به پیوستن نیست. در نتیجه پیوندها به ایستگاه پایه منتقل می شوند.

در این مقاله، یک روش پیوند جدید برای شبکه های حسگر بی سیم برای به حداقل رساندن هزینه کل ارتباطات و بهبود عملکرد ارائه می کنیم. رویکرد ما بر اساس دو تکنیک است؛ ابتدا ما از پایگاه داده های ستونی به جای پایگاه داده های ارتباطی برای ذخیره داده های سنسور استفاده می کنیم و دوم، از یک روش پیوند موازی استفاده می کنیم. در سال های اخیر، افزایش توجه و کار تحقیقاتی بر روی پایگاه داده های ستون بندی شده دیده شده است. یک پایگاه اطلاعاتی ستون گرا ، داده ها را به صورت ستونی (به عنوان مثال column-wise) ذخیره میکند نه به صورت ردیفی مانند پایگاه های داده های رابطه ای سنتی. I / O بیشتر برای پرس و جو فقط خواندنی مفید است، زیرا آنها فقط به ستون ها (یا ویژگی های) مورد نیاز پرس و جو دسترسی دارند. پرس و جو فقط خواندنی در ظرفیت کاری و برنامه های موجود در تجزیه و تحلیل داده ها، شبکه های معنایی وب و شبکه های حسگر رایج هستند. از آنجا که شبکه حسگر می تواند به عنوان یک پایگاه داده توزیع شده مدل سازی شود و گره های حسگر مستقل باشند، پس یک پلت فرم طبیعی برای یک معماری share-nothing میباشد. با استفاده از معماری share-nothing، ما می توانیم داده های سنسور را برای عمل پیوند و انجام اتصال موازی به منظور بهبود عملکرد توزیع کنیم.

برای تست کارایی تکنیک پیوند پیشنهادی ما، یک تحلیل عملکرد انجام می شود. از طریق آزمایش های عملکردی، ما نشان می دهیم که روش ما از الگوریتم های پیوست کنونی، برای شبکه های حسگر بر اساس هر دو پایگاه داده های رابطه ای و پایگاه های ستون گرا برتر است.

بقیه مقاله به شرح زیر است: ما در مورد کارهای مرتبط، در بخش 2 بحث می کنیم. در بخش 3، ما یک الگوریتم پیوند جدید را بر اساس پایگاه داده های ستون گرا و متقارن ارائه می کنیم. عملکرد پرس و جو از الگوریتم پیشنهادی با الگوریتم های اتصال سنتی شبکه های حسگر در بخش 4 مقایسه شده است. نتیجه گیری در بخش 5 میباشد.

2) کارهای مرتبط

چندین تکنیک برای ساده تر شدن اتصالات، در شبکه های حسگر در آثار [1،2] ارائه شده است. استراتژی های پیوند عمومی در شبکه های حسگر می تواند به عنوان پیوند ساده، پیوند متوالی و پیوند مرکزی، بسته به موقعیت منطقه اتصال در شبکه حسگر، طبقه بندی شوند]2[. مشکل اصلی این رویکردهای عمومی، هزینه ارتباطی است که با کاهش ارتباط، مرتبط است. تیم هایی که نامزد پیوند نیستند می توانند به طور ناخواسته به منطقه پیوست منتقل شوند.

یک رویکرد بهتر اینست که تنها رکورد هایی را که درگیر پیوند هستند را به منطقه پیوند انتقال دهیم. چند تکنیک فیلترینگ پیشنهاد شد که تنها اطلاعات مربوط به سنسورهایی که در نتیجه پیوند مشارکت دارند، به منطقه اتصال در نزدیکی ایستگاه پایه منتقل می شوند. الگوریتم SNJ ، خلاصه ای از یک رویکرد پیوند است [3]. ایده کلیدی این است که از خلاصه ای از sensor reading استفاده کنید تا آن مطالعاتی را که غیر مرتبط با نتیجه پیوند هستند را هرس کنید. تکنیک دیگری الگوریتم RFB ، فیلتر کردن رکورد با استفاده از بردار بیتی است]4[. الگوریتم RFB با استفاده از بردارهای بیتی تولید شده پس از نیمه اتصال اجرا می شود تا داده های غیر ضروری را قبل از ارسال داده ها از هر گره به منطقه پیوند هرس کند.

تکنیک های بهینه سازی مهم برای پایگاه های ستون گرا وجود دارد. استراتژی های تحقق ، اوایل و اواخر، در بازسازی پرس و جو مهم هستند [5]. پیوند نامرئی [6] کار قبلی را در زمینه بهبود نمادهای طرحواره ستاره با استفاده از طرح ستون گرا گسترش می دهد. الگوریتم پیوند بر اساس پایگاه ستون گرا برای انجام پردازش داده ها در شبکه های حسگر پیشنهاد شده است [7]. الگوریتمی که ما به عنوان EM نامگذاری می کنیم، بر اساس یک استراتژی اولیه در نظر گرفته شده در پایگاه داده ستون گرا است.

3) الگوریتم پیشنهادی

یک شبکه حسگر که یک شبکه جاده ای را پوشش می دهد را در نظر بگیرید. هر گره سنسور وسایل نقلیه را شناسایی می کند، زمان شناسایی را ثبت می کند و پرونده های زمان بندی شده را برای مدت زمان ثابت نگه می دارد. فرض کنید که منطقه R و منطقه S نشان دهنده دو مجموعه از گره های حسگر است که در آن تشخیص خودرو اتفاق می افتد. query پیوند برای تعیین سرعت وسایل نقلیه مسافرت بین دو منطقه به شرح زیر است: R.vehicle_id را انتخاب کنید، R.time، S.time از R، S جایی که R.loc در R_region و S.loc در S_region و R.vehicle_id = S.vehicle_id .. برای ارزیابی query بالا، خواندن سنسور از منطقه R و منطقه S جمع آوری شده و در ویژگی vehicle_id پیوست شده است. مثال پیوند از [3] گرفته شده است.

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

Query هایی که در این مقاله در نظر گرفته شده اند به شرح زیر است: SELECT R.A1، R.A2، S.A2 از R، S که R.loc در R-region و S.loc در S-region و R.A1 = S .A1 R و S جداول همبستگی هستند و R-region (Sregion) R منطقه (S منطقه) در شبکه حسگر که در آن sensor reading ها گرفته شده اند. R.A1 و S.A1 به ترتیب در R و S ترکیب می شوند. query در گره حسگر آغاز شده و نتیجه آن در سینک query جمع آوری شده است. از آنجا که اندازه حافظه در هر گره محدود است، گره نزول قادر به انجام پیوست به صورت محلی است. پیوند باید با همکاری چندین گره به نام منطقه پیوست انجام شود.

الگوریتم پیشنهادی یک الگوریتم توزیع شده شامل منطقه R-region ، S-region ، منطقه اتصال و گره سینک است. منطقه (R) Sشامل تعدادی از گره های حسگر است، هر یک بخشی از رابطه(R) S را ذخیره می کند. علاوه بر این، منطقه اتصال F نیز دارای گره های حسگر متعددی است که برای پیاده سازی توزیع شده همکاری می کنند. الگوریتم پیوستن، یک استراتژی late materialization ، در سه مرحله اجرا می شود، یعنی مرحله انتخاب، مرحله پیوستن و مرحله نتیجه. در مرحله انتخاب، مقادیر ستون پیوست در ابتدا به منطقه اتصال F ارسال می شود. در مرحله پیوستن، نیمه پیوستن بین ستون های پیوست R و S انجام می شود تا فقط مقادیر ستون واجد شرایط را از منطقه R و S به گره پیوند F. در مرحله نتیجه، مقادیر ستون واجد شرایط R و S برای ساخت تپه ها به یکدیگر متصل می شوند و به گره سینک منتقل می شوند.

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

مرحله پیوستن الگوریتم پیشنهادی از سه مرحله تشکیل شده است. در مرحله اول، نیمه پیوست در هر گره انجام می شود. نتیجه پیوستن دو ساختار داده را تولید می کند. یکی لیست موقعیت است و دیگری bitmap (برای R و S) است. ما فرض می کنیم که ابرداده در حال حاضر برای محاسبه لیست موقعیت صحیح و bitmap در یک پرونده توزیع شده است. نتیجه نیمه پیوستن یک لیست موقعیت با دو ستون است، یکی برای ستون پیوست R و دیگری برای ستون join از S. هر جفت ورودی در لیست موقعیت حاوی موقعیت ستون پیوست R و S با همان مقدار پیوست پیوست. بیت مپ حاوی موقعیت ستون پیوست است که شرایط پیوست را رعایت می کند. در مرحله دوم، bitmap به یک گره در منطقه (R) S فرستاده می شود. گره دریافت کننده bitmap را به گره های دیگر در منطقه (R) S پخش می کند. در مرحله سوم، در هر گره، bitmap برای استخراج مقادیر از ستون های واجد شرایط در موقعیت های مربوطه که در آن بیت به 1 تنظیم شده است، استفاده می شود. مقادیر ستون های انتخاب شده به گره مشخص شده در منطقه اتصال F. ارسال می شود. فرض کنیم یک فراداده برای پوشاندن bitmap جدول به زیر جداول وجود دارد. طرح مبتنی بر هش در مرحلۀ دوم مرحله انتخاب برای ارسال مقادیر ستون انتخاب شده به همان گره در منطقه F به عنوان مقادیر پیوست با همان موقعیت استفاده می شود.

فاز نتیجه الگوریتم پیشنهاد شده از دو مرحله تشکیل شده است. در مرحله اول، در هر گره در F، لیست موقعیت و بیت مپ در مرحله اول فاز پیوستن برای ترکیب کردن مقادیر ستون های R و S برای ساخت مجسمه ها استفاده می شود. دوخت قوسی به صورت موازی در هر گره در F انجام می شود. فرض می کنیم که یک فراداده برای نمایش مقادیر ستون های R و S با توجه به لیست موقعیت و بیت مپ موجود است. در مرحله دوم، تپه های ساخته شده از هر گره در F به عنوان نتیجه جستجو به گره سینک منتقل می شود.

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

4) تجزیه و تحلیل عملکرد

برای تست هزینه بهره وری از الگوریتم پیوست پیشنهاد شده در این مقاله، تجزیه و تحلیل عملکرد با الگوریتم های SNJ، RFB و EM موجود است. الگوریتم SNJ و الگوریتم RFB مبتنی بر پایگاه داده های ارتباطی هستند در حالی که الگوریتم EM از استراتژی materialization early در پایگاه های ستون گرا استفاده می کند. الگوریتم های مختلف با توجه به هزینه ارتباطی که تعداد بایت هایی که به گره های مختلف منتقل می شوند برای به دست آوردن نتیجه پیوند مقایسه شده است.

1-4) محیط آزمایش

الگوریتم های پیوست برای اندازه جدول های مختلف (2000 تاپول و 5000 تن) از R و S برای تعیین تاثیر افزایش تعداد در جدول های R و S با توجه به هزینه ارتباط مقایسه شد. همچنین هزینه ارتباطی الگوریتم های پیوست مختلف را برای انتخاب چندگانه پیوست (0.01، 0.05، 0.1، 0.5) آزمایش کردیم. کاندیدهای پیوند کسری از دسته های جدول است که شرایط عضویت را ارضا می کند. عضویت 0.05 به این معنی است که فقط 5٪ از تجمع ها را واجد شرایط می دانند.

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

2-4) نتیجه آزمایش

در اجرای query، هزینه ارتباطات برابر مجموع هزینه های ارتباطی برای مرحله انتخاب، مرحله پیوستن و مرحله نتیجه است. هزینه ارتباطات برای هر فاز هزینه حمل داده ها را به گره های دیگر برای آن مرحله می دهد. واحد هزینه ارتباطات تعداد بایت از یک گره به گره های دیگر منتقل می شود. شکل 1 هزینه ارتباط الگوریتم های پیوست برای انتخاب نوع پیوستگی مختلف را نشان می دهد و زمانی که توانمندی جدول R و جدول S به ترتیب 2000 تن و 5000 تن است. کاندیدا های پیوند مورد استفاده در آزمایش از 0.01، 0.05، 0.1 تا 0.5 است. پیوستن به انتخابی از 0.1 به این معنی است که فقط 10٪ از خلبانها شرایط عضویت را رعایت می کنند. اندازه bitmap در الگوریتم پیشنهادی ما تعداد بیت هایی است که هر بیت مربوط به موقعیت ستون است. آزمایشات نشان می دهد که الگوریتم پیشنهادی هر دو الگوریتم SNJ و الگوریتم RFB را برای همه ی انتخاب های مختلف پیوستگی مورد آزمایش تست می کند. همچنین الگوریتم EM را که بر پایه پایگاه داده های ستون محور است نیز بهتر عمل می کند. همانطور که مشاهده می شود، عملکرد الگوریتم پیشنهاد شده برای کم شدن کاندید پیوند بهتر می شود. به عبارت دیگر، همانطور که تجمع های پیوند کم می شوند، هزینۀ ارتباط الگوریتم پیشنهادی بیشتر کاهش می یابد.

شکل 1. هزینه های ارتباطی برای کاندیداهای پیوند

شکل 1 هزینه ارتباط الگوریتم های مختلف را برای انواع مختلفی از جداول که باید پیوست شوند نشان می دهد. انتخاب نوع پیوستگی مورد استفاده برابر 0.1 است و توانایی های آن از 2000 تجمع برای R و S تا 5000 تجمع و هر تکرار 8000 متغیر است. الگوریتم پیشنهادی ما هر دو SNJ و الگوریتم RFB را برای همه انواع مختلفی که مورد آزمایش قرار می گیرند، بهتر می کند. در مقایسه با الگوریتم SNJ، هزینه ارتباطات در حدود 18 درصد برای همه کارایی ها کاهش می یابد. در مقایسه با الگوریتم RFB، هزینه ارتباطات در حدود 13 درصد برای هر کاردیابی کاهش می یابد. همانطور که مشاهده می شود، عملکرد الگوریتم پیشنهادی ما بهتر است، اما هزینه ارتباطات برای سایر توانایی های یکسان باقی می ماند. نتیجه عملکرد نشان می دهد که انتخاب انتخاب پیوست، هزینه های ارتباطی را بیشتر از اندازه جداول پیوست می کند.

ما آزمایش زمان پاسخ query برای تکنیک های مختلف پیوستن شبکه های حسگر انجام ندادیم. دلیل این است که ما بر این باوریم که مهمترین معیار عملکرد برای شبکه های حسگر هزینه کل ارتباطات است. با این حال، آسان است که توجه داشته باشید که زمان پاسخ پرس و جو با استفاده از نسخه موازی الگوریتم پیشنهادی ما سریع تر از الگوریتم های دیگر است که براساس محاسبات موازی نیستند. با استفاده از الگوریتم، گره های حسگر بیشتر در پردازش query دخالت دارند، زمان پاسخ پرس و جو سریع تر از زمان پیوستن و انتقال اطلاعات می تواند به طور موازی انجام شود.

5) نتیجه

در این مقاله الگوریتم توزیع شده برای پردازش داده ها در شبکه های حسگر ارائه شده است. الگوریتم پیشنهادی بر اساس یک استراتژی late در پایگاه داده ستونی که در آن داده ها به صورت ستونی ذخیره می شوند، استوار است. الگوریتم توزیع شده را به یک نسخه موازی تبدیل می کنیم، با فرض یک معماری shared-nothing برای شبکه حسگر. الگوریتم پیشنهادی باعث صرفه جویی در انرژی می باشد؛ زیرا تنها آن ستون ها و مقادیر ستون درگیر در query به گره های حسگر در منطقه پیوست منتقل می شوند. چندین نتیجه گزارش شده (به عنوان مثال SNJ، RFB) در مورد استفاده از تکنیک های فیلترینگ بر پایه پایگاه داده های ارتباطی برای جلوگیری از تجمع های ​​غیر ضروری قبل از ارسال کاندیداهای نامزد به منطقه پیوست. روش مشابهی نیز براساس پایگاه داده های ستون گرا پیشنهاد شده است (به عنوان مثال EM).

نتایج تجربی نشان داد که الگوریتم پیشنهادی ما از الگوریتم های SNJ، RFB و EM در هزینه های ارتباطات بهتر است. الگوریتم SNJ و الگوریتم RFB مبتنی بر پایگاه داده های رابطه ای است و EM بر اساس پایگاه داده های ستون گرا است. برای تایید آزمایش ما، از مقادیر مختلف برای انتخواب پیوست و همچنین اندازه جداول مختلف استفاده کردیم. در تجزیه و تحلیل عملکرد، ما نشان دادیم که عملکرد الگوریتم پیشنهادی، برای کاهش انتخاب پیوست بهتر می شود. به عبارت دیگر، در صورت پیوستن و خروجی بیشتر در نتیجه پیوستن، هزینه ارتباط الگوریتم پیشنهادی کاهش می یابد. علاوه بر این، با استفاده از الگوریتم، گره های حسگر بیشتری در پردازش query دخالت دارند، زمان پاسخ query سریع تر از زمان پیوستن و انتقال داده به گره های اتصال می تواند همه به صورت موازی انجام شود.