بخشی از مقاله
چکیده
- شبکه هاي حسگر بی سیم متشکل از تعداد بسیار زیادي گره حسگر می باشند که معمولا در ناحیه اي دورازدسترس به صورت تصادفی پراکنده شده اند. اخیرا ایده استفاده از سینک متحرك براي جمع آوري داده هاي موجود در سطح شبکه در جهت افزایش طول عمر شبکه حسگر ارائه شده است. ما در این مقاله با استفاده از شبکه هاپفیلد - Hopfield Network - حرکت سینک را در شبکه هاي سلسله مراتبی دو سطحی مشخص خواهیم نمود. روش پیشنهادي مسیر حرکت سینک را که متشکل از نقاط توقف بهینه، زمان توقف در آن نقطه و شعاع سرخوشه هاي فعال در هر نقطه میباشد، مشخص می کند. روش ارائه شده در خصوص کاربردهاي مبتنی بر مهلت زمانی و نرخ بیت ثابت، انعطاف پذیري بالایی از خود نشان می دهد. در قسمت شبیه سازي روش ارائه شده را در سناریوي هاي متفاوتی شبیه سازي نموده و نتایج بدست آمده نشان از عملکرد بهینه شبکه هاپفیلد در خصوص تعیین مسیر حرکت سینک و افزایش طول عمر شبکه حسگر دارند.
کلید واژه- شبکه هاي حسگر بیسیم، حرکت سینک، کاربردهاي مبتنی بر مهلت زمانی، شبکه هاپفیلد
-1 مقدمه
درسالهاي اخیر حرکت سینک در شبکه هاي حسگر بی سیم، به عنوان یکی از مهمترین تکنیک ها براي افزایش طول عمر شبکه مطرح شده است 3]،2،.[1 حرکت سینک در داخل شبکه به علت کاهش فاصله حسگرها از سینک باعث صرفه جویی زیادي در مصرف انرژي میگردد. صرفه جویی در مصرف انرژي باعث افزایش عمر حسگرها و در نتیجه، افزایش عمر شبکههاي حسگر بیسیم میشود. سینک میتواند توسط ربات متحرك، حیوان و یا هواپیماي بدون سرنشین در شبکه حرکت کند4]،.[3 از آنجائیکه که شبکه هاي سلسله مراتبی به عنوان یکی از مهمترین زیرساخت هاي شبکه حسگر در بسیاري از کاربردها مورد استفاده قرار می گیرند، ما در این مقاله حرکت سینک را در شبکههاي سلسله مراتبی دو سطحی مورد بررسی قرار خواهیم داد. شبکه هاي سلسله مراتبی دو سطحی، متشکل از خوشههایی در سطح اول و سرخوشه هایی در سطح دوم می باشند.
بطوریکه دادههاي خوشهها پس از جمع آوري توسط سرخوشه آن خوشه، به صورت تک گامی براي سینک ارسال میگردد .[5] گرههاي سرخوشه به دلیل جمع آوري دادههاي خوشه، پردازش و ارسال به سینک، بیشترین مصرف انرژي را نسبت به اعضاء خوشه خود دارند7]،.[6 تکنیک هاي بسیاري براي کاهش مصرف انرژي سرخوشهها ارائه شده اند که در تمامی آنها سینک به صورت ثابت فرض شده است 8]،7،.[6 اما میتوان سینک را در شبکه به گونه-اي تغییر مکان داد که با مصرف انرژي کمتري در سرخوشهها، داده هاي شبکه حسگر را جمع آوري کند. در ادامه، در بخش دوم به معرفی کارهاي انجام شده خواهیم پرداخت. در بخش سوم فرضیات و طرح مساله و در بخش چهارم روش پیشنهادي را مطرح خواهیم نمود و در بخش پنجم نیز شبیه سازي و ارزیابی روش ارائه شده مطرح میگردد و در پایان به نتیجه گیري و پیشنهادات کارهاي آینده خواهیم پرداخت.
-2 کارهاي انجام شده
الگوریتم هایی که در خصوص حرکت سینک در شبکه ارائه شدهاند را می توان از نقطه نظر طرحریزي حرکت سینک به چهار هشمه دسته اصلی، متمرکز، مبتنی برهمکاري شبکه، تصادفی و مبتنی بر پویش منطقهاي تقسیم نمود.[9] در روشهاي متمرکز یک نهاد مرکزي اطلاعات مربوط به مکان حسگرها را نگهداري کرده و بر این اساس مسیر حرکت سینک را برنامهریزي و انتخاب می-کند. در بیشتر این روشها، سینک خود به عنوان تصمیم گیرنده عمل میکند.[10] در روش مبتنی برهمکاري شبکه، حسگرها با همکاري یکدیگر و به صورت پویا مسیر حرکت سینک را بر اساس توپولوژي فیزیکی شبکه انتخاب میکنند. همچنین گرهها با شیوهاي کاملا توزیع شده، سینک متحرك را در طول مسیري که از قبل محاسبه شده، هدایت میکنند. تطبیق مسیر در این روش میتواند بسیار راحتتر نسبت به روش متمرکز انجام شود. علاوه بر این، سیستمهاي راهنماي شبکه میتوانند بدون نیاز به سرویسهاي محلیابی طراحی شوند.[11] در روشهاي مبتنی بر تصادف، مسیریابی سینک از تعدادي مرحله تصادفی تشکیل شده است و در هر مرحله، سینک جهتی را به صورت تصادفی انتخاب کرده و به آن سمت حرکت و داده هاي آنها را جمع آوري می-کند. این روشها در کاربردهاي بلادرنگ کارایی چندانی ندارند.[12] در روش مبتنی بر پویش منطقهاي، ابعاد محیطی که حسگرها در آن قرار دارند، داده شده است و سینک مسیري را براي پیمایش این محدوده محاسبه میکند. مسیریابی در این روش بستگی به ابعاد این محیط و محدوده ارتباطات دارد.[13]
-3 فرضیات و طرح مساله
شبکهاي شامل یک سینک متحرك چندکاناله [5] با قابلیت حرکت آزادانه در شبکه و U گره حسگر Si, i=1…U که هر کدام داراي انرژي اولیهe0 میباشند، را در نظر بگیرد . گره ها قابلیت تنظیم شعاع ارسال خود را دارند. موقعیت گره ها در شبکه به صورت تصادفی تعیین میشود. همچنین K نقطه توقف را به صورت گریدي در شبکه در نظر بگیرید. همانند الگوریتمهاي سلسله مراتبی[15]، چرخه فعالیت شبکه به چندین راند - Round - تقسیم میگردد که زمان مصرف شده در هر یک از راندها، Tround فرض شده است. دریک زمان Tround، ابتدا گره هاي حسگر به خوشههایی تقسیم میشوند - زمان ایجاد خوشه . - - tcf - پس از جمع آوري دادههاي اعضاء هر خوشه در زمان tdc توسط سرخوشه، سینک به سمت یک یا چند نقطه توقف، حرکت می-کند و زمان مشخصی را در هر یک از ایستگاهها توقف کرده و دادههاي یک یا چند خوشه را از سرخوشهها دریافت مینماید - مهلت زمانی - . - - tdr - Deadline مهلت زمانی tdr متناسب با نوع کاربرد شبکه حسگر بیسیم تعیین میگردد؛ این زمان در هر راند با توجه به کیفیت دادههاي دریافتی میتواند تغییر نماید. ما در این مقاله براي سادگی در ارائه روش پیشنهادي، این زمان را در کل طول عمر شبکه ثابت در نظر گرفتهایم. با توجه به فرضیات بالا زمان Tround را میتوان به صورت زیر بیان نمود.
از میان زمانهاي tcf، tdc وtdr، تنها زمان tdr وابسته به نوع کاربرد شبکه حسگر میباشد و دو زمان دیگر وابسته به تعداد گره هاي حسگر در شبکه میباشند. با انتخاب کمترین مهلت زمانی - tdr - ، سینک باید با انتخاب نقاط توقف بهینه، تمامی دادههاي سرخوشهها را در مدت tdr و با کمترین مصرف انرژي در آنها، جمع آوري نماید. دراین حالت گرههاي سرخوشه باید شعاع ارسال خود را افزایش دهند چراکه سینک نقطه یا نقاطی را در ناحیه مشترك برخی و یا تمامی سرخوشهها انتخاب خواهد نمود. درحالیکه با انتخاب بیشترین زمان ممکن براي tdr، هریک از سرخوشهها میتوانند تا زمان رسیدن سینک در مجاورتشان، دادههاي اعضاء خوشه خود را در بافر نگهداري نمایند و پس از قرارگیري سینک در محلی مناسب، کل دادههاي بافر شده خود را با صرف کمترین انرژي - کمترین شعاع ارسال - براي آن ارسال نمایند. ماکزیمم مهلت زمانی براي جمع آوري دادههاي - - برابر است با مجموع زمان صرف شده براي جمع آوري داده هاي تکتک سرخوشه ها - در الگوریتم پیشنهادي همانند 13]،[12 از مدت زمان حرکت سینک بین نقاط توقف می توان صرفنظر کرد - به گونه اي که سینک در کنار هر سرخوشه قرار گرفته و داده هاي آن را جمع آوري نماید.
که در آن qi تعداد اعضاء خوشه iام، نرخ دریافت اطلاعات از محیط توسط اعضاء خوشه، £ ضریب ذوب داده ، سرعت انتقال داده برحسب بیت بر ثانیه در سرخوشه iام و M تعداد سرخوشه ها میباشد. همچنین کمترین مهلت زمانی - - نیز برابر خواهد بود با مدت زمان جمعآوري دادههاي بزرگترین سرخوشه از نظر تعداد اعضاء، به گونهاي که سینک در یک نقطه بهینه در شبکه توقف نماید و همه سرخوشهها دادههاي خود را به صورت همزمان به آن ارسال نمایند:ششمه ما در این قسمت مسیري را براي حرکت سینک در شبکه با الف - درنظر گرفتن در طراحی شبکه هاپفیلداستفاده از قابلیت بهینه سازي شبکه هاپفیلد [14] ارائه خواهیم درنظر گرفتن بیشترین زمان براي به این مفهوم میداد.
در این مسیر محل توقف سینک و مدت زمان توقف آن در هر نقطه و به دنبال آن شعاع ارسال گرههاي سرخوشه مشخص باشد که سینک براي جمع آوري دادههاي هر سرخوشه، میتواندخواهد شد. این حرکت باید به گونهاي باشد که: الف - کل مدت در نزدیکترین نقطه توقف به آنها قرار گرفته و داده هاي آنها را زمان توقف سینک در نقاط مشخص شده از مقدار tdr - مهلت جمع آوري نماید. با فرض اینکه تعداد نقاط توقف از تعداد گره زمانی - کوچکتر و یا مساوي باشد. ب - انرژي مصرفی ارسال داده- هاي سرخوشه در شبکه بزرگتر مساوي باشد، تعداد کل نرونها هاي گرههاي سرخوشه به سینک حداقل گردد. پ - تمامی داده-براي هر سرخوشه با فرض k نقطهتوقف برابر با هاي گرههاي سرخوشه توسط سینک دریافت شوند. خواهدشد. به عنوان مثال، همانطورکه در شکل 2 مشاهده می در ابتدا قصد داریم قید اول را در طراحی شبکه هاپفیلدشود،هر یک از گرههاي سرخوشه، دادههاي خود را در نقاط اعمال کنیم و به بیان دیگر تعداد نرونهاي شبکه هاپفیلد را به توقف متفاوت و در زمان τ×2 براي سینک ارسال خواهند کرد. از مقدار tdr وابسته نماییم. همانطور که در شکل 1 مشاهده می- آنجائیکه گره اول دادههاي خود را به نقطه توقف شماره یک نمایید، تعداد سطرهاي شبکه هاپفیلد برابر با تعداد گرههاي ارسال کرده است و دیگر گرهها به ترتیب به نقاط توقف شماره دو سرخوشه در شبکه M - گره - و تعداد ستونهاي آن برابر با K×S و سه ارسال کرده اند، انتظار داریم این نقاط توقف انتخاب شده که K تعداد نقاط توقف و S تعداد واحد زمانی که سینک میتواند فاصله کمتري از دیگر نقاط توقف نسبت به آن ها داشته باشند. در هرنقطه توقف کند. مدتτ زمان مجاز توقف سینک در هر تعداد کل نرون ها با درنظرگرفتن براي M گره سرخوشه، برابر است بامقدار ثابت میباشد - ستون برابر با - . روشن بودن نرون سطرx< ام<و1ستون مفهوم ارسال داده از سرخوشه ام به نقطه توقف می باشد.
-1-4 در نظر گرفتن زمان در طراحی شبکه هاپفیلد
ما در روش پیشنهادي، طراحی شبکه هاپفیلد و تعداد نرون-هاي آنرا وابسته به زمان tdr قرار دادهایم. براي این منظور بدون از دست دادن جامعیت مساله، بافرض qi=Q - i=1…N - و fi=F و همچنین با فرض اینکه در صورت فعال بودن نرون Vxy، سینک به مدت τ واحد زمان در موقعیت توقف خواهد نمود، تعداد نرون هاي فعال براي ارسال کل دادههاي یک سرخوشه به سینک - - از رابطه زیر بدست خواهد آمد:
شکل :2 شبکه هاپفیلد براي 3 گره و سه نقطه توقف با در نظر گرفتن ب - درنظر گرفتن در طراحی شبکه هاپفیلد با در نظر گرفتن سینک باید داده هاي گرههاي سرخوشه را در کمترین زمان ممکن جمع آوري نماید. به عبارت دیگر، تعدا کل نرون هاي موجود در هر سطر باید برابر با در - 4 - باشد. لذا تعداد کل نرون ها در این حالت برابر خواهد بود با :اگر مقدار τ را به گونه اي انتخاب نمود که برابر تعدادنقاط توقف گردد، در این صورت در هر نقطه توقف براي هر سرخوشه فقط یک نرون قرار خواهد گرفت. حال با در نظرگرفتن B نرون در هر نقطه توقف براي هر سرخوشه - 1<B<Von - زمان هاي متفاوتی از tdr را خواهیم داشت. - - < <
