مقاله در مورد بررسی نحوه انتخاب Data Storage در شبکه های حسگر

بخشی از مقاله

بررسی نحوه انتخاب Data Storage در شبکه های حسگر

شبکه هاي سنسور بي سيم شامل نودهاي کوچکي با توانايي حس کردن، محاسبه و ارتباط به زودي در همه جا خود را مي گسترانند. چنين شبکه هايي محدوديت منابع روي ارتباطات، محاسبه و مصرف انرژي دارند. اول اينکه پهناي باند لينکهايي که گرههاي سنسور را به هم متصل مي کنند

محدود مي باشد و شبکه هاي بيسيم اي که سنسورها را به هم متصل مي کنند کيفيت سرويس محدودي دارند و ميزان بسته هاي گم شده در اين شبکه ها بسيار متغير مي باشد. دوم اينکه گره هاي سنسور قدرت محاسبه محدودي دارند و اندازه حافظه کم نوع الگوريتمهاي پردازش داده اي که مي تواند استفاده شود را محدود مي کند. سوم اينکه سنسورهاي بي سيم باطري کمي دارند و تبديل انرژي يکي از مسائل عمده در طراحي سيستم مي باشد.

داده جمع آوري شده مي تواند در شبکه هاي سنسور ذخيره شود و يا به سينک منتقل شود وقتي داده در شبکه هاي سنسور ذخيره مي شود مشکلات عديده اي به وجود مي آيد:
• سنسورها ميزان حافظه محدودي دارند که اين باعث مي شود نتوانيم ميزان زيادي داده که در طول ماه يا سال جمع آوري شده را ذخيره کنيم

• چون منبع تغذيه سنسورها باطري مي باشد با تمام شدن باطري داده ذخيره شده در آن از بين مي رود.
• جستجو در شبکه گسترده و پراکنده آن بسيار مشکل مي باشد.
داده ها مي توانند به سينک منتقل شوند و در آنجا براي بازيابي هاي بعدي ذخيره شوند اين شما ايده آل مي باشد چون داده ها در يک محل مرکزي براي دسترسي دائمي ذخيره مي شوند. با اين حال، ظرفيت انتقال به ازاي هر نود در شبکه سنسور که به صورت تعداد بسته هايي که سنسور

مي تواند در هر واحد زماني به سينک منتقل کند تعريف مي شود، محدود مي باشد. حجم زيادي از داده نمي تواند به صورت موثر از شبکه سنسور به سينک منتقل شود علاوه بر اينها انتقال داده از شبکه سنسور به سينک ممکن است انرژي زيادي مصرف کند و اين باعث مصرف انرژي باطري شود.
بخصوص سنسورهاي اطراف سينک به طور وسيع مورد استفاده قرار مي گيرند وممکن است سريع خراب شوند و اين باعث پارتيشن شدن شبکه مي شود. اين امکان وجود دارد که با افزايش هزينه برخي از نودها با ظرفيت حافظه بيشتر و قدرت باطري بيشتر در شبکه هاي سنسور استفاده شود اين سنسور ها از اطلاعات موجود در سنسورهاي نزديک Backup مي گيرند و به Query ها جواب

مي دهند. داده جمع آوري شده در هر نود مي تواند به صورت پريوديک توسط رباتها به Data ware house منتقل شود چون نودهاي ذخيره داده را فقط از نودهاي همسايه جمع آوري مي کنند و از طريق فيزيکي منتقل مي کنند، مشکل ظرفيت محدود حافظه، ظرفيت انتقال و باطري تا حدودي بهبود مي يابد.

پرس و جوي کاربر ممکن است فرم هاي مختلفي داشته باشد براي مثال پرس و جوي کاربر ممکن است اين باشد که چه تعداد نود رخداد هاي انتقال را تشخيص مي دهند، ميانگين دماي فيلدهاي حسگر و يا ... ، در اين سناريو هر سنسور علاوه بر حس کردن درگير مسيريابي داده در دو زمينه مي باشد: داده خامي که به نودهاي ذخيره منتقل مي شود و انتقال براي Query Diffusion و جواب به پرس و جو ، هر کدام از دو مورد ممکن است داده را به سينک منتقل کند و يا به صورت

محلي در نود سنسور ذخيره کند، از طرف ديگر داده اي که منحصراً در سينک ذخيره شده است براي جواب به پرس و جو با صرفه تر است چون هيچ هزينه انتقال ندارد ولي تجمع داده در سينک هزينه زيادي دارد در طرف مقابل داده اي که به صورت محلي در سنسور ذخيره شده است هيچ هزينه اي براي تجمع داده ندارد ولي هزينه پرس و جو بسيار بالا مي باشد نودهاي ذخيره نه تنها يک محل ذخيره سازي دائمي فراهم مي کنند يک بافر بين سينک و نودهاي سنسور مي باشند.
در اينجا ما دو نوع از سنسورها را تعريف مي کنيم :

نودهاي ذخيره ( Storage Node ) : اين گره ها تمام داده هايي که از ساير دريافت کرده اند و نيز داده هايي که خود توليد کرده اند را ذخيره مي کنند و هيچ چيزي را قبل از اينکه پرس و جو دريافت کنند نمي فرستند با توجه به تعريف پرس و جو آنها نتايج مورد دلخواه را از داده خام بدست مي آورند و نتايج مربوطه را به سينک منتقل مي کنند. سينک هم خودش به عنوان نود ذخيره تعبير مي شود.

نودهاي فوروارد ( Forwarding Node ) : اين نودها داده دريافتي از نودهاي ديگر يا داده هاي توليدي خود را دوباره از طريق مسير هاي خاص به سينک منتقل مي کنند اين عمل تا زماني که داده به يک نود ذخيره منتقل شود ادامه پيدا مي کند عمليات ارسال دوباره مستقل از پرس و جو مي باشد و بنابراين نياز به هيچ پردازشي ندارد. شکلهاي زير اين تعريف ها را به خوبي نمايان مي کند.

شکل2:قرار دادن گره های storage در شبکه شکل1: تپولوژی گره های شبکه های سنسوری

در شبکه هاي سنسوري که در آن مقادير زيادي داده جمع آوري و براي بازيابي در آينده ذخيره مي شوند، ذخيره سازي به عنوان موضوع مهمي مطرح شده است .
اخيراً براي ذخيره داده در شبکه هاي حسگر ( سنسور ) مفهوم Storage Network ارائه شده است . Storage Node بار بالاي انتقال تمام داده ها به يک مکان مرکزي براي ذخيره را تعديل مي کند . داده جمع آوري شده در شبکه سنسور يا بايد به يک مکان مرکزي ( Sink ) انتقال داده شود يا اينکه در خود گره ها ذخيره شود .

مشکلاتي براي ذخيره داده در سنسور ها وجود دارد : اول اينکه يک سنسور تنها فضاي حافظه محدودي در اختيار دارد که از ذخيره مقادير زيادي داده جلوگيري مي کند. دوم اينکه سنسور ها توسط باطري عمل مي کنند و داده ذخيره شده هنگام اتمام باطري از بين مي رود سوم اينکه جستجوي داده ها در شبکه اي با تجمع داده هاي پخش شده ( Scattered ) مستلزم صرف هزينه انتقال بالايي است.
روش ديگر يعني ذخيره در Sink مستلزم انتقال تمام داده ها به گره مرکزي ( Sink ) است.
اين يک روش ايده آل براي ذخيره داده ها است. زيرا که ذخيره به صورت دائمي است. با اين حال قابليت انتقال هر گره در شبکه بسيار محدود است و ميزان زيادي داده نمي تواند به صورت کارا از شبکه به سينک انتقال داده شود. بعلاوه انتقال داده مستلزم صرف انرژي زيادي است و در نتيجه خالي شدن باطري سنسور به صورت سريع است به ويژه سنسورهاي اطراف سينک بسيار استفاده مي شود و در نتيجه با از بين رفتن آنها شبکه به سرعت تجزيه مي شود.
مي توان با افزايش کمي در هزينه هاي مالي بعضي گره هاي خاص با حافظه دائمي بيشتر مانند Flash Memory و همچنين با توان باطري بيشتر را در شبکه سنسور استفاده کرد. اين گره ها از داده سنسور هاي نزديک خود پشتيبان تهيه مي کنند و جستجو ها را پاسخ مي دهند.
داده ذخيره شده در هر Storage Node را مي توان به صورت دوره اي و با استفاده از ربوت ها به يک Data Ware House انتقال داد. فرضيات ما درباره ويژگي توليد داده، پخش Query و پاسخ به Query ها به شرح زير است

• براي توليد داده فرض مي کنيم هر گره نرخ rd داده در واحد زماني مي خواند و سايز داده ها در مرحله خواندن به اندازه sd است.
• براي پخش Query ها ، rq جستجو در واحد زماني از طرف کاربران ارائه مي شود و سايز Query ها sq است.
• براي پاسخ به Query ها فرض مي کنيم که اندازه داده ها براي پاسخ به Query نسبت از داده خام است که به آن نرخ کاهش ( Reduction Rate ) مي گوييم. نشانگر پاسخ به Query براي جستجوهايي از نوع تجمعي ( Aggregate ) است که جستجوي غالب در Sensor Network است.

مسائل مطرح شده در اين زمينه عبارتند از :
1. مسئله قرار دهي گره هاي Storage در شبکه
2. نحوه گزينش بهترين گره Storage ( از لحاظ هزينه ) توسط گره هاي ديگر که به آنها Forwarding Node مي گوييم

اين نحوه گزينش با توجه به شرايط پوياي شبکه هاي سنسوري از قبيل خرابي يا اتمام باطري گره ها و يا سرعت توليد داده تاثير مستقيم در ميزان مصرف انرژي و در نتيجه بازه حيات شبکه دارد در اين پروژه الگوريتم ارائه شده در مقاله Adaptive and Decentralized Data Storage Selection In Sensor Network پياده سازي شده است در اين مقاله الگوريتم ADSS ارائه شده است و هر Forwarding Node به صورت پيوسته شرايط محيط را چک مي کند و با توجه به آن بهترين گره Storage را براي خود به صورت Local انتخاب مي کند.

اولين بخش برنامه توليد گراف آغازين ( اوليه ) براي کارگذاري سنسورها در محيط است. محيط به شکل دايره و با مرکزيت گره Sink مي باشد. سنسورها با فرآيند تصادفي پوواسن دوبعدي در محيط قرار داده مي شوند. پس از قرار دادن سنسورها با توجه به انتقال داده سنسورها و يالها بين گره ها رسم مي شوند. بدين ترتيب که ابتدا با مرکزيت هر يک از سنسورها دايره اي با شعاع طول انتقال فرض مي شود گره هايي که درون مساحت يک دايره قرار مي گيرند به هم متصل مي شوند اين فرايند را در شکلهاي زير مشاهده مي کنيد:

شکل 2: رسم دايره های با شعاع طول انتقال شکل1: گره های شبکه

شکل 3: تشکيل گراف اتصال

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

استراتژي شناسايي ( Exploration )
اين ايده به اين صورت مي باشد که نود فعال نرخ داده خود را به نودهاي ديگر مي فرستد براي اينکه هزينه ها مقايسه شوند از آنجائيکه يک مجموعه از نودهاي جايگزين به هر ند فعال مربوط مي باشد ما اين نودها را به عنوان tentative node معرفي مي کنيم هزينه درست به همان روشي که براي نودهاي فعال محاسبه مي شود تعيين مي گردد ما نياز داريم که موارد زير را تعريف کنيم :

1. سياست شناسايي ( Exploration Policy ) براي انتخاب اينکه کدام نودها به عنوان tentative node بايستي انتخاب شوند. پيچيدگي ظريف فضاي راه حل مانع از در نظر گرفتن کسر کم مي شود بنابراين سياست بايستي براي انتخاب tentative node هيوريستکي انتخاب کند که به راه حل بهينه نزديک باشد بر طبق استراتژي شناسايي همسايه نودهاي همسايه نود فعال به عنوان tentative node انتخاب مي شوند.

2. ما همچنين نياز به سياست اقتباس ( Adoption Policy ) براي انتخاب نود فعال از بين ندهاي tentative node داريم در انجا ما فقط دو عمل ممکن را در نظر مي گيريم : يا اينکه اجراي پرس و جو را با نود فعال ادامه دهيم و يا اينکه به يک نود فعال جديد برويم و براي اين انتخاب از الگوريتمهاي حريصانه استفاده مي کنيم طوري که هزينه اين انتقال کمترين باشد.

هزينه جواب دادن به Query

c : ( روي تمام لبه هاي درخت پوشاي مينيمم که تمام نودهايي ذخيره اي که فرزند فورواردينگ دارند به هم متصل کرده است)
هزينه انتشار پرس وجو :

ساختن درخت پاسخ به پرس و جو : متد انتخاب پدر

الگوريتم 1 :

i : Storage Node;
: distance between i and j ;
: distance between i and sink;
: distance between j and sink;
foreach j in adjacency of i
if ( and )
if ( ( ( ) . + ( ) . ) <
(( ). + ( ) . ) )
i = j’s parent ;
else j = i’s parent

انتخاب Data Storage :

raw data transfer from fn to i : raw_transfn,i :
raw data transfer from fn to j : raw_transfn,j :

reply_costfn,i : cost of reply for from storage node i to sink after recomputing reply tree in each round
reply_costfn,j : cost of reply for from storage node j to sink after recomputing reply tree in each round

: shortest path of i to an SN ancestor in query diffusion tree
diffusion cost of i :

: shortest path of j to an SN ancestor in query diffusion tree
diffusion cost of j :