ارائۀ روشی بهینه، مبتنی بر کاربرد جهت حرکت سینک در شبکه های سلسله مراتبی حسگر بی سیم

مجله فناوری اطلاعات در طراحی مهندسی

مقاله 10، دوره 6، بهار و تابستان 1392 - شماره پیاپی 61، شهریور 1393، صفحه 40-68   

نوع مقاله: مقاله پژوهشی

چکیده

چکیده: استفاده از سینک متحرک یکی از مهمترین تکنیکها در جهت مصرف بهینۀ انرژی و به دنبال آن افزایش عمر شبکههای حسگر بیسیم می باشد. کارهای زیادی در خصوص قرارگیری سینک متحرک در شبکه و همچنین تعیین مسیری برای حرکت آن ارائه شده است. از آنجایی که ساختارهای سلسله مراتبی نیز به عنوان یکی از پرکاربردترین توپولوژیهای شبکههای حسگر بیسیم محسوب میگردد، ما در این مقاله حرکت سینک را در شبکههای سلسله مراتبی دو سطحی مورد بررسی قرار دادهایم. روش پیشنهادی که مبتنی بر مدل برنامه نویسی ریاضی MILP) Programming Linear Integer Mixed (میباشد، انعطاف پذیری مؤثری در خصوص نوع کاربرد شبکۀ حسگر دارد؛ به طوری که با توجه به نوع کاربرد شبکه و به تبع آن سطح بحرانی بودن زمان گزارش داده های شبکه ( tar (مسیری بهینه برای حرکت سینک در شبکه تعیین میکند و در زمان تعیین شده (tar (دادههای هر خوشه با مصرف بهینۀ انرژی توسط سینک جمع آوری میشوند. روش ارائه شده برای تعیین مسیر حرکت سینک، تعدادی نقطۀ بهینه را در شبکه مشخص میکند و برای هر نقطه، زمان توقف و سرخوشههای ارسال کننده را نیز تعیین میکند. در قسمت شبیه سازی، ابتدا به تحلیل کامل روش ارائه شده پرداختهایم، سپس روش ارائه شده را با روشهای دیگر کنترل حرکت سینک متحرک و همچنین روش حرکت سینک در مسیرهای مقید مقایسه نمودهایم. نتایج شبیه سازی نشان دادهاند که ایدة سینک متحرک در شبکههای سلسله مراتبی دو سطحی مبتنی بر روش ارائه شده، میتواند عمر شبکۀ حسگر را نسبت به مسیر های مبتنی بر قید بین دو تا چهار برابر و نسبت به روش سینک ثابت بین هشت تا ده برابر افزایش دهد.

کلیدواژه‌ها

شبکههای حسگر بیسیم؛ حرکت سینک مبتنی بر کاربرد؛ شبکههای سلسله مراتبی؛ مدل MILP

اصل مقاله

1 -مقدمه: در سالهای اخیر، پیشرفت تکنولوژی مخابرات و صنعت قطعات الکتریکی و الکترونیکی خرد، منجر به ساخت میکروحسگرهایی کوچک و نسبتاً ارزان شده که از طریق یک شبکۀ بیسیم با یکدیگر ارتباط برقرار میکنند [1و2 .[این شبکهها که شبکههای حسگر بیسیم خوانده میشوند، به ابزار مناسبی برای استخراج داده از محیط اطراف و نظارت بر رویدادهای محیطی تبدیل شدهاند. در تمام این کاربردها، میکروحسگرها در محل مورد نظر توزیع شده و بدون مراقبت رها میشوند تا به طور مرتب پارامترهای محیطی نظیر دما، فشار، رطوبت و فعالیتهای شیمیایی را گزارش دهند. سپس اطلاعات به دست آمده را به صورت گام به گام و یا تک گامی به گره جمعکنندة اطلاعات یا همان سینک ارسال نمایند. اما از آنجایی که این گره حسگرها از یک منبع محدود و حیاتی انرژی برخوردارند، نحوة جمعآوری داده ها، پردازش و ارسال آنها بسیار مهم است. در سالهای اخیر تکنیکهای بسیاری برای افزایش طول عمر این شبکهها ارائه شده است .[3،4،5،6،7،8،9] یکی از مهمترین این تکنیکها، استفاده از سینک متحرک در شبکه میباشد. حرکت سینک در داخل شبکه به علت کاهش فاصلۀ حسگرها از سینک، باعث صرفهجویی زیادی در مصرف انرژی میگردد. صرفه جویی در مصرف انرژی باعث افزایش عمر حسگرها و در نتیجه، افزایش عمر شبکههای حسگر بیسیم میشود. سینک میتواند توسط ربات متحرک یا وسیلۀ نقلیه حرکت کند و از انرژی نامحدودی برخوردار باشد. نقاط حرکت سینک میتواند به صورت تصادفی و یا توسط یک الگوریتم هوشمند تعیین شود. انتخاب نقاط بهینه برای توقف سینک بسیار مهم بوده و به بالا بردن کارایی شبکه کمک فراوانی میکند. ما در این مقاله حرکت سینک را در شبکههای سلسله مراتبی دو سطحی مورد بررسی قرار خواهیم داد. شبکههای سلسله مراتبی دو سطحی، متشکل از خوشههایی در سطح اول و سرخوشههایی در سطح دوم میباشند؛ به طوری که دادههای خوشهها پس از جمعآوری توسط سرخوشۀ آن خوشه، به صورت تک گامی برای سینک ارسال میگردد. [11،10) [شکل (1 (را مشاهده نمایید). شکل (1 :(ساختار شبکه سلسله مراتبی دو سطحی گرههای سرخوشه به دلیل جمعآوری دادههای خوشه، پردازش و ارسال به سینک، بیشترین مصرف انرژی را نسبت به اعضاء خوشۀ خود دارند. تکنیکهای بسیاری برای سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 41 کاهش مصرف انرژی سرخوشهها ارائه شده که در تمامی آنها سینک به صورت ثابت فرض شده است [14،13،12 ،[اما میتوان سینک را در شبکه به گونهای تغییر مکان داد که با مصرف انرژی کمتری توسط سرخوشهها، دادههای شبکۀ حسگر، جمعآوری شوند. ایدة اصلی این مقاله، ارائۀ روشی مبتنی بر مدل ریاضیMILP میباشد؛ به گونه ای که مسیر حرکت سینک را در شبکه به طور کامل مشخص کند. این مسیر از یک سری نقاط توقف تشکیل شده است. که در هر نقطه، سینک برای مدتی مشخص توقف کرده و دادههای برخی یا همۀ سرخوشهها را جمعآوری میکند. از امتیازات اصلی روش ارائه شده، این است که در کنار مشخص شدن مسیر حرکت سینک، زمان توقف در هر نقطه نیز مشخص خواهد شد. همچنین روش ارائه شده انعطافپذیری مؤثری با نوع کاربرد شبکه حسگر دارد؛ به طوریکه مسیر پیشنهادی حرکت سینک در کاربردهای بلادرنگ، متفاوت از کاربردهای غیر بلادرنگ میباشد. در ادامۀ بخش دوم به بررسی کارهای مرتبط در زمینۀ سینک متحرک در شبکه های سلسله مراتبی خواهیم پرداخت. در بخش سوم روش پیشنهادی را مطرح خواهیم نمود و در بخش چهارم نیز شبیهسازی و ارزیابی روش ارائه شده مطرح میگردد و در پایان به نتیجه گیری و پیشنهادات کارهای آینده خواهیم پرداخت. 2 -کارهای مرتبط الگوریتمهایی که در خصوص حرکت سینک در شبکه ارائه شدهاند را میتوان از نقطه نظر طرحریزی حرکت سینک به چهار دسته اصلی [23 ،[متمرکز ١ برهمکاری مبتنی]، 15،16،17،18] 2 شبکه [20،19 ،[مبتنی بر تصادف [21 [و مبتنی 3 بر پویش منطقهای [22 [تقسیم نمود. در روشهای متمرکز، یک نهاد مرکزی اطلاعات مربوط به مکان حسگرها را نگهداری کرده و بر این اساس مسیر حرکت سینک را برنامهریزی و انتخاب میکند. در بیشتر این روشها سینک به عنوان تصمیم گیرنده عمل میکند. در روش مبتنی برهمکاری شبکه، حسگرها با همکاری یکدیگر و به صورت پویا مسیر حرکت سینک را بر اساس توپولوژی فیزیکی شبکه انتخاب میکنند؛ همچنین گرهها با شیوهای کاملاً توزیع شده، سینک متحرک را در طول مسیری که از قبل محاسبه شده،هدایت میکنند. تطبیق مسیر در این روش میتواند نسبت به روش متمرکز بسیار راحتتر انجام شود. علاوه بر این، سیستمهای راهنمای شبکه میتوانند بدون نیاز به سرویسهای محلیابی طراحی شوند. در روشهای مبتنی بر تصادف، مسیریابی سینک از تعدادی مرحلۀ تصادفی تشکیل شده است و در هر مرحله، سینک جهتی را به صورت تصادفی انتخاب کرده و به آن سمت حرکت، و دادههای آنها را جمع آوری میکند. این روشها در کاربردهای بلادرنگ کارایی چندانی ندارند. در روش مبتنی بر پویش منطقهای، ابعاد محیطی که حسگرها در آن قرار دارند، داده شده است و سینک مسیری را برای 1- Network guided 2- Network guided 3- Area scanning ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 42 پیمایش این محدوده محاسبه میکند. مسیریابی در این روش بستگی به ابعاد این محیط و محدودة ارتباطات دار. Luo و همکارانش در [15 [روشی متمرکز را برای حرکت سینک در شبکه ارائه دادند. آنها نشان دادند که سینک متحرک میتواند ترافیک بین گرههای حسگر را متعادل نمایند و در نتیجه عمر شبکۀ حسگر را افزایش دهد. برای این کار در مدلی که برای شبکه ارائه داده بودند، ماکزیمم بار ترافیکی بین گرهها را مینیمم نمودند. مشکلی که در الگوریتم ارائه شده توسط Luo و همکارانش وجود داشت، استفاده از کوتاهترین مسیر برای جمعآوری داده بود که این برای تمامی ساختارهای شبکه، راه حل صحیحی نمیباشد. ١ همچنین این روش فقط خاص شبکههای تخت طراحی شده است. TTDD] 22 [که روشی مبتنی بر پویش منطقهای است، ابتدا در اطراف گره منبع (گرهای که یک رویداد را کشف کرده است) یک شبکه گرید ایجاد می کند و از گرههای موجود در نقاط تقاطع شبکه گرید به عنوان هشدار دهندههای داده در شبکه استفاده مینماید. سپس سینک متحرک با حرکت در بین این نقاط به جستجوی داده میپردازد. مشکلی که در این الگوریتم وجود دارد، افزایش دادههای کنترلی برای ایجاد شبکۀ گرید در اطراف گره منبع میباشد، خصوصاً در زمانی که نرخ گرههای منبع در شبکه بالا رود. 1- flat در [21 [روشی تصادفی برای حرکت سینک ارائه شده است که در آن، حرکت سینک به صورت تصادفی انجام میشود. هنگامی که شبکه ایجاد میشود، سینک در هر بازه زمانی، نقاطی را 2 به عنوان نقاط دسترسی انتخاب کرده و این نقاط را طی یک همه پخشی در شعاعی خاص اعلام میکند؛ سپس در هر نقطه دسترسی شروع به جمعآوری دادهها میکند. مشکل این روش انتخاب تصادفی نقاط جمعآوری داده میباشد. در [20 [نیز روش کارایی برای افزایش طول عمر شبکه حسگر بیسیم با استفاده از حرکت سینک ارائه شده است. در این روش که مبتنی بر ساختارهای سلسله مراتبی دو سطحی و همکاری شبکهای میباشد، هر یک از گرههای سرخوشه با توجه به تعداد رفت و آمدهای پیش رو و همچنین با توجه به انرژی باقیمانده خودشان، شعاع بهینهای را برای ارسال دادههای خوشه خود اعلام میکنند، سپس سینک متحرک در مکان اشتراکی که بین تمام گرههای سرخوشه به وجود خواهد آمد، توقف کرده و شروع به جمعآوری داده میکند. در [28 [روشی برای توقف سینک در شبکههای سلسله مراتبی ارائه شده است که در آن سینک در مرکز دایرة محاط کنندة سرخوشهها قرار میگیرد. این دایره، کوچکترین دایرهای است که میتواند سرخوشهها را در برگیرد. سپس سرخوشهها دادة خود را به صورت تگ گامی به سینک ارسال خواهند کرد. در ادامه مقالۀ [28 ،[ 2- Access point سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 43 موقعیت سینک در حالتی که سرخوشهها از لحاظ نسبت سطح انرژی به نرخ انتقال با یکدیگر متفاوت باشند، مطابق با یک ساختار و الگوریتم چند لایهای تعیین می گردد. حرکت سینک در شبکه گاهی به صورت کنترل شده و در برخی مواقع به صورت مقید و ثابت می باشد [29 .[ در [29 [الگوریتمی جهت جمعآوری بهینه داده ارائه شده است که درآن، سینک به طور دائم از یک مسیر ثابت و مقید عبور می کند. 1 به هر بار رفت و آمد سینک، یک ”راند“ گفته می شود. گرههای حسگری که در شعاع پوشش 2 سینک متحرک قرار گرفتهاند ”زیر سینک“ نامیده 3 می شوند و به صورت تگ اطلاعات خود را به سینک متحرک ارسال می کنند شکل (2 (را مشاهده نمایید). از آنجایی که انرژی مصرفی وابسته به تعداد گامها و طول مسیر ابتدا به انتها می باشد، هدف این مقاله کاهش تعداد مسیرهای کوتاه بین تمامی گره ها با گره های ”زیر سینک“ می باشد. این روش مبتنی بر همکاری شبکهای است؛ به گونهای که در ابتدای کار شبکه، کوتاهترین مسیرها از گرههای حسگر به تمامی گرههای ”زیر سینک“ ایجاد میشود؛ سپس سینک متحرک با دریافت اطلاعات مسیرها از ”زیر سینک“ها با استفاده از الگوریتم ژنتیک بهترین ”زیر سینک“ را با توجه به درصد آنها در شبکه تعیین میکند. مشکل اصلی این روش، ثابت بودن 1- Round 2- Sub Sink 3- Tag ”زیر سینک“ها در کل زمان عمر شبکه است که این خود نرخ کاهش انرژی را درآنها نسبت به سایر گرههای دیگر بالا میبرد. این روش را در قسمت شبیهسازی به طور کامل مورد ارزیابی قرار خواهیم داد. شکل (2 :(مسیر دائم حرکت سینک در شبکه 3 -الگوریتم پیشنهادی قبل از ارائۀ روش پیشنهادی در این بخش، مدل انرژی و فرضیات مسئله را به ترتیب در بخش های 3-1 و3 -2 بیان خواهیم کرد. سپس در قسمت 3 -3 مدل ریاضی روش ارائه شده را با بررسی کامل قیدها و محدودیتهای آن بحث کرده، عملکرد آن را با توجه به زمان های متفاوت در بخش 3-4 بررسی خواهیم کرد. 3-1 -مدل انرژی فرض کنید گرهiام دادههایی را با سرعت fij بیت بر ثانیه (bps (برای گره jام ارسال نماید. مدل مصرف انرژی گره iام را میتوان به صورت ذیل تعریف کرد [25،24 :[ (1) ௝௜ܧ ௧ = ܿ௜௝. ݂୧୨ ௝௜݀ଶߠ + ଵߠ = ௝௜ܿ ఉ و مقادیری ثابت برای انرژی مصرفی جهت راهاندازی مدار فرستنده و تقویتکننده توان ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 44 میباشند، فاصلۀ اقلیدسی بین دو گره حسگر i وj میباشد.β فاکتور اتلاف مسیر 1 بوده و در محدودة قرار میگیرد؛ به این گونه که اگر فاصله فرستنده تا گیرنده dij () بیشتر از مقدار ثابت d0 2 باشد از مدل چند مسیری و در غیر این صورت 3 از مدل فضای آزاد استفاده میشود. همچنین انرژی مصرفی گره iام جهت دریافت دادههایی با نرخ عبارتست از: ௜ܧ (2 ( ݂݅݇ ෍.ߩ = ௥ ௜ஷ௞ ௞∈ே که در آن ضریبی ثابت و برابر با مقدار انرژی مصرفی برای راه اندازی مدار گیرنده میباشد. 3-2 -فرضیات و طرح مسئله شبکهای شامل یک سینک متحرک با قابلیت حرکت آزادانه در شبکه و N گره حسگر N…1=i ,که هر کدام دارای انرژی اولیه e0 Si میباشند، را در نظر بگیرد. موقعیت گرههای حسگر در شبکه به صورت تصادفی تعیین میشود. همانند الگوریتمهای سلسله مراتبی، چرخه فعالیت شبکه به چندین راند تقسیم میگردد که زمان مصرف شده در هر یک از راندها، Tround فرض شده است (شکل (3 (را مشاهده کنید). دریک زمان Tround ،ابتدا گرههای حسگر به 4 خوشههایی تقسیم میشوند (زمان ایجاد خوشه (tcf ،((سپس هر یک از سرخوشهها، دادههای 1- path loss 2- Multi path 3- Free space 4- Cluster Formation time جمعآوری می 5 اعضاء خوشه خود را در زمان tdc کنند، سپس سینک متحرک، به سمت یک یا چند 6 نقطه توقف ، حرکت کرده و زمان مشخصی را در هر یک از ایستگاهها سپری کرده و داده های هر خوشه را از سرخوشه آن دریافت مینماید (زمان 7 گزارش داده (tdr) .((سینک با داشتن چندین ماژول فرستنده وگیرنده قادر میباشد، همانند روش ارائه شده در [26 [دادههای چندین سرخوشه را به صورت همزمان جمعآوری نماید). زمان tdr متناسب با نوع کاربرد شبکه حسگر بیسیم تعیین میگردد و در کل راندها یکسان میباشد؛ زیرا طراحی شبکه بر اساس کاربردی خاص صورت گرفته است و در طول مدت عمر شبکه ثابت خواهد ماند. با توجه به فرضیات بالا، زمان Tround را میتوان به صورت ذیل بیان نمود. ܶ௥௢௨௡ௗ = ݐ + ௙௖ݐௗ௖ + ݐௗ௥ (3) 5- Data Collection time 6 -نقطه توقف، مکانی جغرافیایی از شبکه میباشد که سینک در آن مکان قرار میگیرد و دادهها یک، چند و یا همه سرخوشه ها را دریافت میکند. 7- Data Reporting time سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 45 شکل (3 :(زمان یک راند (Tround (و اجزاء آن از میان زمانهای tcf،tdc وtdr ،تنها زمان tdr وابسته به نوع کاربرد شبکه حسگر میباشد و دو زمان دیگر وابسته به تعداد گرههای حسگر در شبکه میباشند. در کاربردهای بلادرنگ، زمان tdr باید کمترین مقدار خود را داشته باشد؛ به عبارت دیگر سرخوشهها میبایست در کمترین زمان ممکن tdr دادههای جمعآوری شده از گرههای خوشه خود را برای سینک در شبکه به صورت تک گامی ارسال نمایند؛ اما در کاربردهای غیر بلادرنگ، هر یک از سرخوشهها میتوانند تا زمان رسیدن سینک در مجاورتشان، دادههای اعضاء خوشه خود را در بافر نگهداری کنند و پس از قرارگیری سینک در محلی مناسب، کل دادههای بافرشدة خود را برای آن ارسال نمایند. در مثال شکل (4 ،(تأثیر حرکت سینک متحرک را در شبکههای سلسله مراتبی در سه سناریوی متفاوت بررسی خواهیم کرد. در یک شبکه مربع شکل به ضلع 2متر، چهار خوشه قرار گرفته اند و .شدهاند مشخص نیز g و a,b,c,d,e,f توقف نقاط با فرض اینکه هر کدام از سرخوشهها در زمان tdc ،500 بیت داده برای ارسال به سینک از اعضاء خوشه خود جمعآوری کرده باشند و با فرض اینکه انرژی ارسال هر بیت داده معادل مجذور طول مسیر مصرف شود، در سناریوی اول، سینک با توجه به سخت افزار ارتباطی کافی و نرخ سرویس بالا، در موقعیت d قرار گرفته و دادههای هر چهار سرخوشه را در مدت زمان 10 ثانیه دریافت می کند (سرعت ارسال سرخوشهها 50 بیت برثانیه فرض شده است) و در این موقعیت کل انرژی مصرفی سرخوشه ها برابر با 0.7 m×4) واحد 980 2 ×500bit (می باشد. در سناریوی دوم اگر سینک ابتدا در موقعیت b به مدت 10 ثانیه قرار گرفته باشد و دادههای سرخوشههای 1و2را دریافت نماید، سپس به موقعیت e تغییر مکان دهد و داده های بافر شده سرخوشههای 3 و4 را در مدت 10 ثانیه دریافت نماید، سینک توانسته است کل دادههای سرخوشهها را در مدت زمان 20 ثانیه و با صرف انرژی کل 0.5 m×4) واحد 500 با برابر 2 ×500bit (جمعآوری کند؛ اما در سناریوی سوم، سینک دادههای هر سرخوشه را در نزدیکترین مکان به آنها (1.0 متر) جمعآوری خواهد کرد؛ به طوری که دادههای سرخوشه 1 را در موقعیت a و به ترتیب داده های سرخوشه های 3،2 و4 را در موقعیتهای c ، f و g دریافت خواهد کرد. در این سناریو سینک در مدت زمان40 ثانیه توانسته است کل دادههای سرخوشهها را با مجموع انرژی مصرفی20 واحد 0.1 m×4) 2 ×500bit (جمعآوری نماید. ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 46 شکل (4 :(تاثیر حرکت سینک در شبکه های سلسله مراتبی در مجموع، سینک برای جمعآوری داده در کمترین زمان باعث بیشترین مصرف انرژی در سرخوشهها و برای جمعآوری دادهها در بیشترین زمان، باعث کمترین مصرف انرژی در سرخوشه ها خواهد شد. در کاربردهای شبکههای حسگر بیسیم بسیار مطلوب است که زمان گزارش داده ها به کاربر و یا به عبارت دیگر، زمان جمعآوری دادهها توسط سینک، همان ابتدای شروع به کار شبکه مشخص شود، لذا زمان tdr با توجه به نوع کاربرد در همان ابتدا مشخص خواهد شد. آنچه مهم است، جمع آوری دادههای سرخوشهها در مدت زمان tdr مشخص شده و با صرف کمترین مصرف انرژی در آنهاست. ما در این مقاله الگوریتمی مبتنی بر مدل برنامهنویسی ریاضی MILP ارائه نمودهایم که هدف آن افزایش طول عمر شبکه حسگر و تعیین مسیر حرکت سینک، تعیین زمان توقف در هر یک از نقاط توقف و مشخص کردن شعاع ارسال دادة هر یک از سرخوشهها به هریک از نقاط توقف میباشد. 3-3 -مدل ریاضی روش ارائه شده در این قسمت ما مدلی ریاضی برای حل مسئله ارائه نمودهایم که مبتنی بر مدل ریاضی MILP میباشد. در ابتدای هر راند، تمامی حسگرها بر اساس یک روش خوشهبندی در مدت به تعداد C 1 زمان tcf به C خوشه تقسیم میشوند. خوشۀ ایجاد شده، C سرخوشه وجود دارد. مجموعۀ تمامی سرخوشهها را با CH نمایش می (length(CH)=C) دهیم سرخوشهها دادههای اعضاء خوشۀ خود را در زمان tdc جمعآوری میکنند. سینک متحرک برای جمعآوری دادههای هر یک از خوشهها، مسیری را در شبکه برمیگزیند. این مسیر از نقاط توقف 1 -روش پیشنهادی مستقل از نوع الگوریتمهای خوشه بندی عمل خواهد کرد، به عبارت دیگر، روش ارائه شده قادر خواهد بود بر روی نتایج خوشه بندی هر نوع الگوریتم خوشه بندی اجرا شود. ما در اینجا از پروتکل LEACH]1 [که یکی از مهمترین پروتکلهای خوشهبندی در شبکههای حسگر بیسیم است، استفاده کردهایم. سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 47 متفاوتی تشکیل شده است. در الگوریتم پیشنهادی همانند [25،24 [از مدت زمان حرکت سینک بین نقاط توقف میتوان صرفنظر کرد. در کاربردهای غیر بلادرنگ، زمان tdr امکان جمعآوری دادههای هر خوشه را به صورت مجزا برای سینک متحرک به وجود میآورد؛ اما در کاربردهای بلادرنگ در کوتاهترین زمان ممکن باید دادههای تمامی خوشهها جمعآوری شوند و این کار با قرارگیری سینک متحرک در یک یا چند محل بهینه و دریافت همزمان از تمامی سرخوشهها امکان پذیر میباشد. مدل ریاضی بیان شده در این قسمت قادر خواهد بود نقاط توقف سینک متحرک را با توجه به زمان tdr دلخواه که متناسب با نوع کاربرد شبکه میباشد، به گونهای مشخص کند که در زمان تعیین شده tdr با بهینهترین مصرف انرژی، دادههای سرخوشهها جمعآوری گردند و در نهایت، عمر شبکۀ حسگر افزایش پیدا کند. در سطح یک شبکه حسگر به مساحت A ، تعداد K نقطه توقف را به صورت گرید در نظر خواهیم گرفت و مجموعه نقاط داخل شعاع ١ کاوش (R (سرخوشهها را به صورت ذیل تعریف میکنیم: H={Pj | D(Si (1) CH , Pj)< R;i=1…y.N,j=1…K} 1 -شعاع کاوش سرخوشهها (R ،(دایرهای به مساحت R 2 π به مرکزیت هر سرخوشه تعیین میکنیم که سینک باید مجموعهای از نقاط توقف موجود در آن ناحیه را جهت توقف خود به صورت بهینهای انتخاب کند. که D فاصلۀ اقلیدسی نقطۀ از سرخوشه بوده و تعداد کل سرخوشههای به دست آمده از عملیات خوشهبندی میباشد (درصد بهینه تعداد سرخوشهها میباشد که در الگوریتم خوشهبندی مشخص میشود). درشکل (5 (سه سرخوشه و به همراه، و مشخص شده است. سینک متحرک فقط نقاط، و را برای تعیین مسیر حرکت خود بررسی خواهد کرد. ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 48 شکل (5 :(نمایش نقاط توقف در شعاع پویش R هر یک از سرخوشه ها بافرض h به عنوان کمترین فاصله بین دو نقطه توقف، کمترین اندازه شعاع کاوش (R0 (را باید برابر با قرار داد تا مجموعه تهی نگردد. شکل (6 (را مشاهده نمایید. مسئله بهینه سازی طول عمر شبکه حسگر و تعیین مسیر حرکت سینک متحرک را میتوان به صورت ذیل بیان نمود. شکل (6 :(کمترین شعاع کاوش (R0 ( هش وخ رس A هش وخ A B A CH S 1 {1,...,4,10,...,14,19,...,23,28,...,31,39} 3  CH V {7,8,9,16,17,18,24,...,27,34,35,36,43,44,45} 1  CH V 1 2 3 9 10 18 19 28 37 46 55 64 27 36 45 54 63 70 71 72 CH S2 CH S 3 {29,...,32,38,...,41,47,...,51,56,...,59,66,67} 2  CH V R 4 11 12 13 20 21 22 23 29 30 31 39 14 38 40 41 47 48 49 50 56 57 58 59 66 67 51 32 7 8 16 17 25 26 34 35 43 44 24 h 2 2 / 2 0 R h 0 R سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 49 (5) MILP ݀ (1.5) ௦ ௝ݒ௜݂௝ݐ෍ − £௜ݍ௖ௗݐ ௜ = 0 ௞ ௝ୀଵ ܪܥ ∋ ݅∀ ܾ௝ܽ௠௜௡ஸ௧ (2.5) ೕ ≤ ܾ௝ܽ௠௔௫݆ = 1: ݇ ௝ݒ௜݂௝௜ܿ ௝ݐ෍ (5.3( (௜)ு஼ܧ = ௜ ௧ ௞ ௝ୀଵ ܪܥ ∋ ݅∀ (4.5) ௥ௗݐ ≥ ௝ݐ෍ ௞ ௝ୀଵ :ݏ݈ܾ݁ܽ݅ݎܽݒ ܭ:1݆ = 0௝ ≥ ݐ ܾ௝ ∈ {0,1}݆ = 1:ܭ در فرمول بهینه سازی بالا، هدف ما مینیمم کردن ماکزیمم مصرف انرژی ارسال دادههای سرخوشهها) به سینک متحرک میباشد. دلیل در نظر گرفتن انرژی سرخوشهها به عنوان هدف، بالابودن مصرف انرژی آنها در شبکه میباشد؛ زیرا سرخوشهها باید کل دادههای به دست آمده از خوشۀ خود را پس از بافر کردن برای سینک ارسال کنند. درنتیجه انرژی مصرفی آنها در مقایسه با سایر گرهها بسیار بالا میباشد .[12،13] حال با کاهش بیشترین مصرف انرژی سرخوشهها به متعادل کردن انرژی مصرفی در سطح شبکه کمک خواهد شد و این عمل طول عمر شبکه حسگر را افزایش خواهد داد. قید شماره (5.1 ،(تضمین میکند که کل دادههای موجود در بافر هر سرخوشه، در پایان زمان حرکت سینک در سطح شبکه به آن ارسال شود که در آن qi تعداد اعضاء خوشه i ام، نرخ دریافت اطلاعات از 1 محیط توسط اعضاء خوشه، ضریب ذوب داده و سرعت انتقال داده برحسب بیت بر ثانیه در سرخوشه iام میباشد. همچنین ti مدت زمان توقف سینک در نقطه توقف j ام میباشد. نیز به صورت ذیل تعریف میگردد: ௝ݒ ௜ = ൜ 1 ݂݅ܲ௝ ∈ ܸ௜ ஼ு ݁ݏ݈݁ 0 (6) اگر نقطه توقف jام متعلق به نقاط تحت پوشش باشند، مقدار برابر با یک ு ஼سرخوشه i ام ௜ܸ است؛در غیر این صورت مقدار آن برابر با صفر میباشد. در قید شماره (5.2 ،(متغیر باینری bj توقف و یا عدم توقف سینک را در نقطه Pj مشخص میکند. در صورت توقف، مقداری تصادفی برای tj در بازه minα و maxα انتخاب 1- Data Fusion ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 50 میگردد و در این نقطه قسمتی و یا تمامی دادههای سرخوشههایی که این نقطه را پوشش میدهند، توسط سینک جمعآوری میگردد minα و maxα مقادیری ثابت میباشند. در قید (5.3 (انرژی مصرفی سرخوشه iام جهت ارسال دادههای اعضاء خوشه خود به سینک متحرک در مدت زمان tj با سرعت fi بیت بر ثانیه مشخص میشود. نیز انرژی لازم برای ارسال 1 بیت از سرخوشه iام به سینک در موقعیت jام میباشد. قید (5.4 (تضمین خواهد کرد که کل زمان حرکت سینک در بین سرخوشهها از مدت زمان کوچکتر و یا مساوی باشد؛ زیرا دادههای به tdr دست آمده پس از این زمان مورد استفاده قرار نمیگیرند و همانطور که در قسمت قبل اشاره شد، این زمان با توجه به نوع کاربرد شبکۀ حسگر بیسیم مشخص خواهد شد. واضح است شعاع کاوش سرخوشهها (R( عامل مهمی در انتخاب محلهای توقف سینک میباشد. برای مثال در شکل (7 (اگر هر سرخوشه دارای 5000 بیت داده باشد و سرعت ارسال داده به سینک در همۀ آنها برابر با bps 1000=f ،باشد، با درنظر گرفتن زمان گزارش دادهها tdr برابر با 11 ثانیه، تابع MILP مقدار صفر را به عنوان خروجی برمیگرداند؛ زیرا با توجه به شعاع کاوش R و هر یک از مجموعههای، سینک باید دادههای سرخوشهها را به صورت خصوصی جمعآوری کند و هیچ نقطۀ توقف مشترکی وجود ندارد که سینک بتواند دادههای چند سرخوشه را در آن نقطه به 1).زیرا صورت مشترک و همزمان دریافت نماید ↓ اشتراک ܸൣ ݅ ↑ 3൧,2,1, ݅ = ܪܥ برابر با تهی میباشد). شکل (7 :(تهی بودن اشتراک مجموعه های ܸ௜ ஼ு , ݅ = 1,2,3 در این صورت برای به دست آوردن جوابی منطقی باید شعاع کاوش R را افزایش داد، مجدداًرا برای تمامی سرخوشهها محاسبه کرد، تابع بهینهسازی MILP بالا را مجدداً فراخوانی نمود و این عمل را تا به دست آوردن جوابی مشخص و منطقی تکرار کرد (شعاع R را تا به دست آوردن جوابی بهینه و منطقی افزایش ٢ داد) .پس از آنکه MILP به جواب بهینهای دست یافت، هر یک از سرخوشهها شعاع ارسال خود را (ri (به صورت (7 (تنظیم خواهد نمود. ݅ܵቀܦ = ݅ݎ ܪܥ ,ܲ෡݆ቁ (7) 1 -همانطور که قبلاً اشاره شد، سینک با داشتن چندین ماژول فرستنده/گیرنده و نرخ سرویس بالا قادر میباشد همانند روش ارائه شده در [26 [دادههای چندین سرخوشه را به صورت همزمان جمعآوری کند. 2 -مقدارشعاع کاوش در مرحله ام، افزایش، برابر است با CH S1 CH S2 CH S3 سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 51 که در آن نقطۀ توقف سینک در شعاع کاوش R از سرخوشه iام است. شکل (8 (را مشاهده نمایید. ri شکل (8 :(شعاع کاوش R و شعاع ارسال اگر اشتراک تمامی غیر تهی باشد و تابع بهینه سازی MILP بالا جوابی بهینه و منطقی نداشته باشد، بهاین مفهوم است که سینک قادر نخواهد بود دادههای تمامی سرخوشهها را به صورت همزمان در زمانی کمترمساوی از tdr جمع آوری نماید. سه راه حل برایرفع این مشکل وجود دارد: 1 -حجم دادههای سرخوشهها را کاهش دهیم. ( با افزایش نرخ و یا کاهش زمان tdc ( 2 -سرعت ارسال داده در سرخوشه را افزایش دهیم. 3 -حداقل زمانی برای tdr با توجه الگوریتم خوشهبندی و اندازه خوشهها مشخص کنیم. در راه حل اول، افزایش نرخ ذوب داده باعث افزایش محاسبات سرخوشهها ودرنهایت افزایش زمان tdc را به دنبال خواهد داشت. همچنین کاهش زمان tdc بستگی به میزان دریافت داده در هر راند دارد که کاهش آن باعث کاهش میزان اطلاعات دریافتی میگردد. راه حل دوم نیزبه شرایط سختافزاری حسگرها دارد و در تمامی حالتها امکانپذیر نمیباشد؛ اما میتوان یک حد پایینی برای tdr با توجه به الگوریتم خوشهبندی و اندازة خوشهها در شبکه در نظر گرفت. این حد پایین را با نمایش خواهیم داد و به صورت (8 (محاسبه خواهد شد. (8) ܶௗ௥ ௜߮£}ݔܽ݉ = ௡௜௠ (ܪܥ)ℎݐ݈݃݊݁ , ... ,1} ݅ = ߮௜ = (௜ݍ௦௖݀ௗݐ) ݂௜ ൘ همچنین میتوان ماکزیمم زمانی را برای سینک در نظر گرفت که بتواند در کنار هر سرخوشه قرار گیرد و دادههای آنرا به صورت خصوصی دریافت کند. (9) ܶୢ୰ ୫ୟ୶ = ෍ £φ୧ ௟௘௡௚௧௛(஼ு) ୧ୀଵ 3-4 -عملکرد الگوریتم پیشنهادی در زمان های متفاوت tdr در شکل (9 (شبکهای متشکل از 60 گره حسگر که در شبکهای با ابعاد 100 × 100 مترمربع پخش شدهاند، مشاهده میشود. در این شبکه مطابق با پارامترهای قسمت شبیهسازی، 80=tdc ثانیه، نرخ دریافت اطلاعات از محیط 2Kpbs.0=ds ،نرخ ارسال داده سرخوشهها به سینک 20Kbps=dt ،در صد مطلوب سرخوشهها برابر با 5 %و نرخ ذوب داده برابر با یک در نظرگرفته شده است. در شکل (9 (نمونهای از خروجی روش ارائه شده ௥ௗ برای زمانی که ܶ = ௥ௗݐ ௠௔௫ ،باشد = 45.6 مشاهده میگردد. همانطور که انتظار میرود، CH i S Pj ˆ ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 52 الگوریتم پیشنهادی در اولین مرحله با اختیار کردن کمترین مقدار: مسیری بهینه برای جمعآوری دادههای سرخوشهها تولید خواهد نمود. همان طور که در این شکل مشاهده میشود. سینک فرصت کافی برای جمعآوری دادههای هر سرخوشه به صورت خصوصی دارد؛ به عبارت دیگر سینک در مجاورت هر یک از سرخوشهها قرار میگیرد و دادههای آن سرخوشه را بدون دخالت سرخوشههای دیگر جمعآوری میکند. با در نظر ௥ௗ گرفتن زمان ܶ = ௥ௗݐ بیشترین مصرف انرژی ௫௠௔ سرخوشهها (خروجی تابع بهینه سازی در (5 ( برابر با 0151/0 ژول به دست آمده است. ௫ ௠௔شکل (9 :(نقاط توقف سینک با فرض ௥ௗ௥ = ܶௗݐ در ادامه، tdr را برابر با کمترین مقدار ممکن (ܶௗ௥ (4.18 = قرار دادیم. در این حالت روش ௫௠௔ ارائه شده باسه مرحله افزایش شعاع کاوش R (42R.42=R0×3 (=نقاطی را مورد پردازش قرار خواهد داد که اولاً بتواند دادههای تمامی سرخوشهها را با توقف در آن نقاط جمعآوری نماید. همچنین در این جمع آوری، بالاترین انرژی مصرفی سرخوشه، کمینه گردد؛ لذا همان طور که در شکل (10 (مشاهده می کنید، این نقاط بیشتر در سمت سرخوشه C قرار گرفتهاند؛ چون بالاترین تعداد اعضا و به دنبال آن بالاترین مصرف انرژی را در زمان انتقال اطلاعات به سینک صرف خواهد نمود. در این حالت، بیشترین مصرف انرژی سرخوشهها برابر 0205/0 ژول به دست آمده است. R= R0 Cluster Head (CH) Sink Stop Point A C Cluster Member (CM) h=20 m B سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 53 ௫ ௠௔شکل (10 :(نقاط توقف سینک با فرض ௥ௗ௥ = ܶௗݐ در ارزیابی دیگری، tdr را برابر با 35 ثانیه انتخاب نمودیم. در این حالت، الگوریتم پیشنهادی پس از دو مرحله افزایش شعاع کاوش R (28.28=R0×2=R (به جواب بهینه دست یافت. همانطور که در شکل (11 (مشاهده میکنید، با افزایش شعاع R ،خوشه C و B به صورت مشترک قسمتی از دادههای خود را در نقطۀ توقف ‘bc ‘به صورت همزمان به سینک تحویل میدهند و خوشۀ A به صورت مجزا تمامی دادههای خود را به سینک در نقطۀ مشخص شده ارسال خواهد کرد. در این حالت بیشترین مصرف انرژی سرخوشهها برابر 019/0 ژول به دست آمده است. شکل (11 :(نقاط توقف سینک با فرض در پایان این قسمت، مراحل کار الگوریتم ارائه شده را در شکل (12 (نشان داده ایم.از آنجایی که کاربرد یک شبکۀ حسگر در طول عمر آن ثابت در نظر گرفته میشود، زمان tdr توسط کاربر سیستم متناسب با نوع کاربرد آن در همان ابتدای شروع به کار شبکه تعیین می گردد. C A B Common Point B A C bc ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 54 شکل (12 :(فلوچارت الگوریتم ارائه شده ݎ݀ در زمانی که ܶ =< انتخاب شده باشد، ݎ݀ݐݔܽ݉ مسیر حرکت، مسیر نرمال الگوریتم ارائه شده میباشد که با انتخاب R0=R ،بهترین نقاط جهت توقف سینک به دست خواهد آمد؛اما در صورتی که زمان tdr در بازه انتخاب شده باشد، حلقه A در بلاک دیاگرام بالا، با افزایش شعاع کاوش R و به روز رسانی باعث خواهد شد که نقاط بهینه توقف توسط تابع بهینهسازی انتخاب شوند. الگوریتم پیشنهادی مسیر B را در مواقعی که زمان جمعآوری دادههای سرخوشهها بیشتر از زمان tdr انتخاب شده توسط کاربر باشد، طی خواهد نمود؛ به طوری که در این حالت مقدار R ١ بیشتر از Rmax خواهد شد و سینک با دریافت 2 اطلاعات سرخوشهها، مقدار موقتی را محاسبه 1 -طولانیترین فاصلۀ بین دو گره در شبکه؛ به عنوان مثال در شبکهای مستطیل شکل به طول و عرض (y,x (آنگاه Rmax=sqrt(x2 +y2 ) 2 -زمان موقتی است، از آن جهت که در راند بعدی همچنان زمان tdr وارد شده در مرحلۀ 1 بلاک دیاگرام مورد توجه قرارخواهد گرفت. خواهد کرد و سپس مسئلۀ بهینهسازی را مجدداً از R0=R اجرا خواهد نمود. 4 -شبیه سازی و ارزیابی در این قسمت، ابتدا به ارزیابی و تحلیل الگوریتم پیشنهادی خواهیم پرداخت و در بخش دوم، الگوریتم پیشنهادی را با کارهای مرتبط مقایسه خواهیم نمود. در این شبیهسازی اندازه شبکه را 600*400 متر مربع و انرژی اولیه گرههای حسگر را یک ژول در نظر گرفتهایم. دیگر پارامترهای شبیهسازی در جدول (1 (آورده شده است. همچنین برای اجرای تابع بهینهسازی MILP از تابع کتابخانهای solve_lp]30 [استفاده نمودهایم. CH i min v dr t سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 55 جدول (1 :(پارامترهای شبیه سازی Value Parameters 100 N (Number of Sensors) CH’s bit rate (f 20Kbps i) 1J Energy 1000 bit Control Packet size 90. £(Data fusion rate) 50 nJ/bit θ1 10 pJ/bit/m θ2 2 50 m (default) H 2 Β 0.0001 αmin 1000 αmax (400×600) m Network Area 2 0.2 Kbps Sensing rate 80 tdc second (desired number of CH) 0.05 4-1 -ارزیابی روش پیشنهادی 4-1 -1 -بررسی تأثیر تعداد خوشهها بر مقدار R و tdr در این قسمت با در نظر گرفتن تعداد 200 گره حسگرو3=tdcثانیه، کمترین مقدارممکن tdr و همچنین مقدار شعاع کاوش R را با فرض تعداد خوشههای متفاوت، اندازهگیری نمودیم. نتایج به دست آمده از میانگین 10 بار اجرا را در شکل (13 (مشاهده می کنید. همانطور که مشاهده میشود، زمانی که تعداد خوشهها افزایش پیدا میکند، سینک برای دست یافتن به کمترین مقدار tdr باید در نقاطی مشترک بین سرخوشهها قرار گیرد، لذا شعاع کاوش R برای جستجوی این نقاط باید افزایش پیدا کند؛ اما هر چه اندازة خوشهها کوچکتر گردد یا تعداد آنها افزایش پیدا نماید، سینک در مدت زمان کوتاهتری می تواند دادههای خوشهها را جمعآوری نماید، زیرا طبق رابطه 8 ، کاهش بیشتری پیدا خواهد نمود. شکل (13 :(تاثیر تعداد خوشه ها بر R و tdr 1 2 3 4 5 6 7 8 9 10 100 101 102 103 Number of Clusters Values t dr R ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 56 4-1 -2 -تأثیر تعداد نقاط توقف بر شعاع کاوش R و در زمان های متفاوتی از tdr در این قسمت، شعاع کاوش R و ماکزیمم مصرف انرژی ارسال سرخوشهها را برای مقادیر متفاوت h و در زمانهای tdr مشخصی اندازهگیری نمودیم. پارامتر h فاصله بین نقاط توقف را مشخص میکند. واضح است که با افزایش h ،تعداد نقاط توقف در سطح شبکه کاهش پیدا خواهند کرد و با کاهش h ،تعداد نقاط افزایش پیدا میکند. تاثیر این پارامتر را بر روی شعاع R و به ترتیب در شکل های (14 (و (15 (مشاهده می نمایید. همانطور که در شکل (14 (مشاهده می کنید، در هر زمان tdr مشخص، افزایش h افزایش R را به دنبال خواهد داشت؛ زیرا افزایش R در هر مرحله از الگوریتم پیشنهادی ارتباط مستقیمی با R0 دارد و کمترین اندازة شعاع کاوش (R0 (برابر با میباشد. اما افزایش شعاع کاوش R با توجه به افزایش مقدار h در زمان tdr ثابت، تأثیر خود را بر مقدار به دست آمده از تابع بهینه سازی (5 (در شکل (15 (نشان داده است. همانطور که مشاهده میشود، در یک زمان tdrثابت، افزایش h باعث افزایش مصرف انرژی سرخوشهها میگردد، زیرا نقاط توقف به دست آمده، فاصله بیشتری با سرخوشهها خواهند داشت؛ از اینرو باعث افزایش مصرف انرژی در آنها خواهد شد. شکل (14 :(تأثیر تعداد نقاط توقف بر R در زمان های متفاوت tdr 50 75 100 125 150 0 20 40 60 80 100 120 140 160 180 t dr (second) R(meter) h=20 h=30 h=40 h=50 سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 57 شکل (15 :(تأثیر تعداد نقاط توقف بر در زمان های متفاوتtdr ،R کاوش برشعاع tdr تأثیر بررسی- 3 -1-4 و تعداد نقاط توقف در دو حالت در رابطه (9 (و (8 (به ترتیب یک مقدار کمینه و بیشنه برای tdr با توجه به اندازة خوشهها ارائه شده است. ما در این قسمت از شبیهسازی قصد داریم میانگین زمان جمعآوری دادههای سرخوشهها را توسط سینک تا زمان مرگ اولین گره حسگر در دو حالت برای شبکههایی با تعداد متفاوتی از گرهها اندازه گیری نماییم. شکل (16 :(مقدار tdrدر دو حالت 50 75 100 125 150 10-1.6 10-1.5 10-1.4 10-1.3 10-1.2 t dr (second) Maximum of ECH h=20 h=30 h=40 h=50 100 200 300 400 500 600 0 50 100 150 200 250 300 350 400 450 The total time of CHs dara reporting to the mobile sink The Number of Sensor Nodes t dr >maximum(tdr ) t dr <minimum(tdr )="" ی="" ـ="" مهندس="" در="" طراحـی="" ات="" اوری="" اطلاع="" ه="" فن="" مجل="" 58="" همانطور="" که="" شکل="" (16="" (مشاهده="" می="" شود،="" اگر="" زمان="" tdr="" را="" از="" بیشتر="" نظر="" بگیریم،="" سینک="" با="" پهلو="" گرفتن="" کنار="" هر="" سرخوشه،="" دادههای="" آنرا="" جمعآوری="" کند.="" توجه="" به="" اینکه="" شبکه="" پنج="" درصد="" گرهها="" عنوان="" سرخوشه="" انتخاب="" خواهند="" شد.="" طور="" میانگین="" اندازة="" خوشه="" ها="" تعداد="" متفاوت="" گره="" حسگر،="" برابر="" خواهد="" بود.="" نتیجه="" افزایش="" های="" حسگر="" و="" دنبال="" آن="" خوشهها،="" مشخص="" است="" نیز="" پیدا="" کرد.="" مثال="" 5="" 95="" کل="" مدت="" داده="" همان="" (17="" میشود،="" مقدار="" r="" برای="" این="" حالت="" ثابت="" 35="" متر="" می-="" باشد.="" :(مقدار="" دو="" حالت()="" و()="" (زمان="" سرخوشهها،="" حالتی="" گرفته="" راندهای="" صفر="" تا="" 150="" شده="" است.="" مشاهده="" متناسب="" گرههای="" 100="" 200="" 300="" 400="" 500="" 600="" 0="" 50="" 250="" the="" number="" of="" sensor="" nodes="" (meter)="" t="" dr="" <minimum(tdr="">maximum(tdr ) سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 59 شکل (18 :(مقدار tdr در حالت() برای شبکه ای با تعدادگره حسگر متفاوت اما در حالتی که زمان tdr را از کوچکتر در نظر گرفته شود، الگوریتم پیشنهادی با افزایش مقدار R به جواب نخواهد رسید؛ چرا که برای دریافت همزمان دادههای خوشهها نیاز به مدت زمانی برابر با دارد. در این حالت الگوریتم پیشنهادی با محاسبه موقتی که وابسته به شرایط خوشهها میباشد، مجدداً اجرا خواهد کرد. مقادیر به دست آمده جهت جمعآوری دادههای سرخوشهها در حالتهای متفاوت از نظر تعداد گرهها، در شکل 16 مشاهده میشود. کمترین زمان به دست آمده برای tdr برای تمامی حالتهای تقریباً برابر است؛ چرا که کمترین زمان وابسته به اندازه بزرگترین خوشه است و از آنجایی که اندازه خوشهها با توجه به درصد بهینه سرخوشهها برابر است؛ لذا کمترین مقدار زمان جمعآوری دادههای سرخوشهها در تمامی حالتها تقریباً برابر است؛ اما از سویی دیگر، مقدار شعاع کاوش برای جستجوی نقاط توقف افزایش پیدا خواهد کرد و دلیل آن افزایش، تعداد خوشهها در شبکه میباشد (شکل (17 (را مشاهده نمایید). شکل (19 :(تعداد نقاط توقف در دو حالت() و() 0 25 50 75 100 125 150 0 50 100 150 200 250 300 350 400 450 Round The total time of CHs dara reporting to the mobile sink nodes=100 nodes=200 nodes=300 nodes=400 nodes=500 nodes=600 100 200 300 400 500 600 0 5 10 15 20 25 The Number of Sensor Nodes The Numbber of Stop Point t dr <minimum(tdr )="" t="" dr="">maximum(tdr ) ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 60 در شکل (19 ،(میانگین تعداد نقاط توقف سینک برای جمعآوری دادههای سرخوشهها تا مرگ اولین گره حسگر مشاهده میشود؛ در حالتی که زمان tdr از مقدار بیشتر در نظر گرفته شود، ماکزیمم تعداد نقاط توقف برابر است با تعداد سرخوشهها، اما این امکان وجود دارد که در برخی از نقاط دادههای سرخوشهها به صورت مشترک جمعآوری گردد؛ چرا که ممکن است فاصلۀ سرخوشهها از مقدار R0 کمتر قرار گیرد. در حالتی که زمان tdr از مقدار کمتر باشد، سینک با توقف در تعداد نقاط کمتری، دادههای سرخوشهها را در کمترین مدت زمان ممکن و با مصرف بهینه انرژی جمعآوری خواهد نمود. 4-1 -1 -بررسی انرژی مصرفی الگوریتم پیشنهادی در دو حالت در این قسمت از شبیه سازی، انرژی مصرفی و فاز ٢٤ در فاز حالت دائمی (Phase State Steady( (Phase Setup (را برای 25 حالت راه اندازی شبکهای با 200 گره برای دو حالت در طی 200 راند اندازهگیری نمودیم. با توجه به نتایج به دست آمده در قسمتهای قبل، در حالتی که زمان بیشتر در نظر گرفته شود، tdr از مقدار سرخوشهها انرژی کمتری را برای گزارش دادهها استفاده خواهند کرد و به این ترتیب عمر شبکه در این حالت طولانیتر خواهد شد؛ ولی در 1 -در این فاز سرخوشه ها داده های اعضاء خود را جمع آوری کرده و برای سینک ارسال خواهند کرد. 2 -در این فاز سرخوشه ها انتخاب شده و به دنبال آن خوشهها و اعضاء آنها نیز مشخص خواهند شد. حالت دیگر به دلیل افزایش فاصله سینک از سرخوشهها، انرژی مصرفی آنها در فاز حالت دائمی بالاتر خواهد بود. در خصوص مصرف انرژی فاز راهاندازی، در هر دو حالت انرژی نسبتاً برابری مصرف میگردد؛ زیرا انرژی فاز راهاندازی ارتباطی به حرکت سینک در شبکه نخواهد داشت. (شکل (20 (را مشاهده نمایید). سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 61 شکل (20 :(مصرف انرژی ارسال داده و ایجاد سرخوشه ها در در دو حالت() و() 4-2 -عملکرد الگوریتم پیشنهادی در مقایسه با کارهای مرتبط در این قسمت از شبیه سازی، الگوریتم پیشنهادی را از لحاظ عمر شبکه (مرگ اولین گره حسگر)، کل دادههای دریافتی از محیط، کل دادههای گزارش شده به سینک و انرژی مصرفی فاز راه اندازی شبکه با یکدیگر مقایسه خواهیم نمود. برای این مقایسه، چهار الگوریتم مرتبط با روش ارائه شده را در نظر گرفتهایم. سه روش ارائه شده در [20]،[28 [و [29 [ در قسمت کارهای مرتبط بررسی شده اند و سینک ایستا که سینک در یک مکان (معمولاً خارج از شبکه) تا مرگ آخرین گره حسگر به طور ثابت قرار گرفته است. 4-2 -1 -مقایسۀ عمر شبکه در بسیاری از روشهای ارائه شده، مرگ اولین گره حسگر را به عنوان طول عمر شبکه حسگر در نظر گرفتهاند. در این قسمت، روش پیشنهادی را در دو حالت () و() با سینک ایستا و روشهای ارائه شده در [20]،[28 [و[29 [مقایسه نمودهایم. همانطور که در شکل (21 (مشاهده میشود، روش پیشنهادی در هر دو حالت از دیگر روشهای ارائه شده بهتر عمل کرده و زمان مرگ اولین گره را طولانیتر کرده است. دلیل این برتری را میتوان در حرکت بهینۀ سینک در شبکه و در نظر گرفتن انرژی مصرفی سرخوشهها دانست. روش ارائه شده در [28 [نیز با در نظر گرفتن فاصله و به دنبال آن انرژی مصرفی سرخوشهها مکان بهینۀ سینک را در مرکز دایرة محاط کننده سرخوشهها تعیین میکند. روش [20 [نیز بر مبنای انرژی باقیماندة سرخوشهها و تعداد راندهای باقیمانده، محل سینک را مشخص میکند؛ اما روش ارائه شده در 0 20 40 60 80 100 120 140 160 180 200 10-3 10-2 10-1 100 101 Round Energy(Joule) Steady State (tdr >maximum(tdr )) Setup Phase(tdr >maximum(tdr )) Steady State (tdr <minimum(tdr ))="" setup="" phase="" (tdr="" <minimum(tdr="" ی="" ـ="" مهندس="" در="" طراحـی="" ات="" اوری="" اطلاع="" ه="" فن="" مجل="" 62="" [29="" [یک="" مسیر="" برای="" حرکت="" سینک="" شبکه="" تعیین="" کرده="" است="" و="" گرههایی="" موجود="" شعاع="" پوشش="" سینک،="" دادههای="" خود="" را="" به="" صورت="" تگ="" گامی="" آن="" ارسال="" میکنند.="" داده="" های="" دیگر="" گرهها="" باید="" از="" طریق="" یک="" چند="" بهینه="" این="" انتقال="" یابند.="" مشکل="" اساسی="" روش،="" ثابت="" ماندن="" گره="" تحت="" تخلیه="" هر="" چه="" سریعتر="" انرژی="" درآنهاست.="" اما="" روش="" پیشنهادی="" که="" مبتنی="" بر="" الگوریتمهای="" خوشهبندی="" میباشد،="" با="" تعویض="" سرخوشهها="" راند="" دریافت="" بهینۀ="" آنها="" زمان="" مشخص="" شده="" tdr="" توانسته="" مرگ="" اولین="" حسگر="" بین="" 2="" تا="" 4="" برابر="" نسبت="" [="" افزایش="" دهد.="" همانطور="" شکل="" (21="" (مشاهده="" میشود،="" حالت="" ،="" <طولانیتر="" حالتی="" مقدار="" کمتر="" نظر="" گرفته="" شود،="" زیرا="" مدت="" کافی="" جمعآوری="" دارد.="" مقایسه="" نشان="" میدهد="" الگوریتم="" کنترل="" شبکه،="" روشی="" متحرک="" مسیری="" مقید="" قبل="" طی="" می="" کند،="" مانند="" [بسیار="" کارآتر="" بهینهتر="" عمل="" میکند.="" ایستا="" هشت="" ده="" :(مقایسۀ="" حسکر="" 4-2="" -2="" -مقایسۀ="" کل="" دریافتی="" محیط="" همراه="" گزارش="" قسمت،="" چهار="" نمودهایم.="" (22="" 100="" 200="" 300="" 400="" 500="" 600="" 10="" 20="" 30="" 40="" 50="" 60="" 70="" 80="" 90="" 110="" 120="" the="" number="" of="" sensor="" nodes="" first="" node="" dies="" (round)="" algorithm="" in="" [29]="" proposed="" <="" minimum(tdr=""> maximum(tdr )) Algorithm in [28] Static Sink Algorithm in [20] سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 63 میشود، کل دادههای دریافتی از محیط و دادههای گزارش شده به سینک در روش پیشنهادی از دیگر روشها بیشتر میباشد. اما دلیل کاهش دادههای گزارش شده نسبت به دادههای دریافت شده از محیط را میتوان مرگ سرخوشه در زمان، گزارش داده و همچنین ذوب داده در سرخوشهها دانست، اما در خصوص روش ارائه شده در [29 [این اختلاف بسیار بیشتر می باشد؛ زیرا مرگ برخی از گرههای حسگر در مرکز شبکه باعث قطع ارتباط دیگر حسگرها با گره های تحت پوشش سینک میشود. شکل (22 :(مقایسۀ کل داده های دریافتی از محیط وکل داده های گزارش شده در شکل (23 ،(شبکهای متشکل از 200 گره حسگر را مشاهده میکنید که مطابق با روش [29 [ سینک در یک مسیر مشخص (از نقطه (10،550 ( به (10،10 (و برعکس)، دائماً در حال حرکت است و دادههای گرههای موجود در شعاع پوشش خود را جمعآوری میکند. در شکل (24 (سطح انرژی باقیمانده در شبکه را در زمان مرگ اولین گره حسگر نشان دادهایم. همانطور که مشاهده میشود، گرهها در محلی قرار گرفتهاند که چگالی حسگرها در آنجا کمتر است و تحت فشار انتقال بستههای گرههای دیگر، سریعتر از بین خواهند رفت و در نتیجه کل دادههای گرفته شده از محیط که میبایست از این گره عبور میکردند، از دست خواهند رفت. لذا این اختلاف بین دادههای دریافتی از محیط و گزارش شده به سینک به وجود خواهد آمد. 100 200 300 400 500 600 0 2 4 6 8 10 12 14 x 108 The Number of Sensor Nodes Data volume (bit) Proposed (Reported Data) Algorithm in [29] (Reported Data) Proposed (Sensed Data) Algorithm in [29] (Sensed Data) Algorithm in [28] (Reported Data) Algorithm in [28] (Sensed Data) Static Sink (Reported Data) Static Sink (Sensed Data) Algorithm in [20] (Reported Data) Algorithm in [20] (Sensed Data) ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 64 شکل (23 :(توپولوژی شبکه در روش [29 [شکل (24 :(سطح انرژی باقی مانده در شبکه شکل 23 همانطور که در شکل (23 (مشاهده می شود، گره حسگر تحت پوشش سینک نیز جزء اولین گرههای از بین رفته میباشد. مشخص است سینک از هر مسیری که عبور کند، گرههای اطراف آن مسیر انرژی خودرا به سرعت از دست خواهند داد. در شبیه سازی دیگری، سطح انرژی یک شبکه که گره ها به صورت گریدی پخش شدهاند شکل (25 .(در زمان مرگ اولین حسگر مشخص شده است، شکل (26 .(همانطور که مشاهده میشود، کاهش سطح انرژی از سمت گرههای انتهایی شبکه به سمت گرههای تحت پوشش سینک صورت میگیرد. البته در [29 [ روشهایی مانند استفاده از مسیرهای متفاوت برای حرکت سینک و یا حرکت چندین سینک در سطح شبکه، ارائه شده است. شکل (25 :(توپولوژی شبکه گریدی در روش [29 [شکل (26 :(سطح انرژی باقی مانده در شبکه گریدی شکل 25 0 50 100 150 200 250 300 350 400 0 100 200 300 400 500 600 Dead Nodes Sink Trajectory Gateway Node 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 0 50 100 150 200 250 300 350 400 0 100 200 300 400 500 600 Sink Trajectory Gateway Node 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 سیم های سلسله مراتبی حسگر بی ه ارائه روشی بهینه و مبتنی بر کاربرد جهت حرکت سینک در شبک 4 -2 -3 -مقایسۀ انرژی مصرفی فاز راه اندازی در این قسمت از شبیهسازی، انرژی مصرفی در خصوص راهاندازی شبکه را در روش ارائه شده و دیگر روشها اندازهگیری کردهایم. همانطور که در شکل (27 (نشان داده شده است، انرژی روش ارائه شده و روش های [20 [و[28 [ تقریباً با هم برابر است؛ اما به دلیل انتقال یکسری پیامهای کنترلی در خصوص محل قرارگیری سینک، در مقایسه با روش سینک ایستا، بالاتر میباشد. این چهار روش (روش ارائه شده، [20 ،[ [28 [و سینک ایستا) در مقایسه با روش ارائه شده در [29 [از مصرف انرژی بالاتری برخوردارند؛ زیرا در روش ارائه شده [29 [همان ابتدای کار مسیریابی بین گرهها تعیین میشود و تا پایان عمر، شبکه ثابت خواهد بود؛ اما در سه روش دیگر در هر راند جهت ایجاد خوشهها و اعلام محل قرارگیری سینک (روش ارائه شده و روش [28 ([انرژی بیشتری مصرف خواهد شد. شکل (27 :(مقایسه انرژی مصرفی راه اندازی از آنجا که ساختارهای سلسله مراتبی به عنوان یکی از پرکاربردترین توپولوژیهای شبکههای حسگر بیسیم محسوب میگردد، در این مقاله روشی مبتنی بر مدل برنامه نویسی ریاضی MILP برای حرکت سینک در شبکههای سلسله مراتبی و با در نظر گرفتن نوع کاربرد شبکه پیشنهاد گردید. در شبکههای سلسله مراتبی گرههای حسگر به خوشههایی مجزا تقسیم میشوند و در هر خوشه، گره سرخوشه موظف به مدیریت خوشه و جمعآوری و پردازش اولیۀ داده خوشه خود میباشد. پس از اینکه دادههای هر خوشه توسط سرخوشۀ آن، در زمان tdc جمعآوری گردید، حرکت سینک با انتخاب مسیری برای تخلیه دادههای سرخوشهها، آغاز میشود. این مسیر حرکت سینک متشکل از تعدادی نقاط توقف میباشد که سینک، مدت زمانی را برای توقف در هر نقطه مشخص میکند؛ اما مهمترین پارامتری 100 200 300 400 500 600 10-3 10-2 10-1 100 101 The Number of Sensor Nodes Energy consumption (Joule) Proposed algorithm Algorithm in [29] Algorithm in [28] Static Sink Algorithm in [20] ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 66 که سینک در تعیین مسیر خود در نظر میگیرد، زمان tdr می باشد. tdr زمان وابسته به نوع کاربرد بوده به این مفهوم که سینک کل داده های شبکه را باید در این زمان جمعآوری کند و دادههایبه دست آمده پس از این زمان، مورد استفاده قرار نخواهد گرفت. در قسمت شبیه سازی، ابتدا روش پیشنهادی را به طور کامل ارزیابی نمودیم. در این ارزیابی تأثیر پارامترهایی مانند اندازه خوشه، تعداد نقاط توقف، انتخاب زمانهای متفاوت tdrو افزایش تعداد گرههای حسگر در شبکه، را بر عملکرد الگوریتم مورد بررسی قرار دادیم. در ادامه، الگوریتم پیشنهادی را با سه کار مشابه در سناریویهای متفاوتی با یکدیگر مقایسه نمودیم. نتایج شبیهسازی افزایش حداقل هشت برابری طول عمر شبکه حسگر را نسبت به روش سینک ایستا و افزایش دو تا چهار برابری را نسبت به حرکت سینک در مسیر مقید، نشان میدهد. روش پیشنهادی، روشی مرکزی بوده که در آن سینک، کلیۀ عملیات مربوط به تعیین مسیر را خود انجام میدهد و زمان حرکت سینک بین نقاط توقف و بررسی ترافیکهای متفاوت شبکه، در نظر گرفته نشده است؛ لذا ارائۀ یک روش توزیع شده برای حرکت سینک در شبکههای حسگر بیسیم، به خصوص در توپولوژیهای سلسله مراتبی، و مد نظر قرار دادن مدت زمان حرکت سینک بین نقاط توقف و در نظر گرفتن ترافیکهای متفاوت در شبکه به عنوان کارهای آینده پیشنهاد می گردند. 

مراجع

1. W. Heinzelman, “Application-specific protocol architectures for wireless networks”, Ph.D. Dissertation, Massachusetts Institute of Technology, June 2000. 2. O. Younis, M. Krunz and S.Ramasubramanian, “Node clustering in wireless sensor networks: recent developments and deployment challenges”, IEEE Transactions on Networking, volume 20, pages 20-25, June 2006. 3. Z.M. Wang, S. Basagni, E. Melachrinoudis, and C. Petrioli, “Exploiting Sink Mobility for Maximizing Sensor Network Life-time,” Proc. 38th Hawaii Int’l Conf. System Sciences, 2005. 4. M. Gatzianas and L. Georgiadis, “A Distributed Algorithm for Maximum Lifetime Routing in Sensor Networks with MobileSink,” IEEE Trans. Wireless Comm., vol. 7, no. 3, pp. 984-994, Mar. 2008. 5. J. Luo and J.-P. Hubaux, “Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks,” Proc. IEEE INFOCOM, 2005. 6. R.C. Shah, S. Roy, S. Jain, andW. Brunette, “DataMules:Modeling a Three-Tier Architecture for Sparse Sensor Networks,” Proc. First IEEE Int’l Workshop Sensor Network Protocols and Applications (SNPA ’03), pp. 30-41, May 2003. 7. S. Basagni, A. Carosi, E. Melachrinoudis, C. Petrioli, and Z.M. Wang, “A New MILP Formulation and Distributed Protocols for Wireless Sensor Networks Lifetime Maximization” Proc. IEEE Int’l Conf. Comm., pp. 3517-3524, June 2006. سیم های سلسله مراتبی حسگر بی حرکت سینک در شبکه ارائه روشی بهینه و مبتنی بر کاربرد جهت 67 8. W. Wang, V. Srinivasan, and K.-C. Chua, “Using Mobile Relays to Prolong the Lifetime of Wireless Sensor Networks,” Proc. ACM MobiCom, pp. 270-283, 2005. 9. I. Papadimitriou and L. Georgiadis, “Maximum Lifetime Routing to Mobile Sink in Wireless Sensor Networks,” Proc. 13th IEEE Int’l Conf. Software, Telecomm. and Computer Networks (SoftCom ’05), 2005. 10. Farzad Tashtarian, A. T. Haghighat, Mohsen Tolou Honary, Hamid Shokrzadeh, “A New EnergyEfficient Clustering Algorithm for Wireless Sensor Networks”, Proc. of international Conference on Software, Telecommunications and Computer Networks (SoftCOM2007), Croatia, 27 - 29, September 2007. 11. Farzad Tashtarian, M. Tolou Honary, A. Haghighat and J. Chitizadeh, “A New Energy-Efficient Level-based Clustering Algorithm for Wireless Sensor Networks”, Proc. of Sixth International Conference on Information, Communications and Signal Processing (ICICS2007), Singapore, 10- 13 , Dec. 2007. 12. Farzad Tashtarian, A.T Haghighat, M.H. Yaghmaee, M. Tolou Honary, M. Mazinani, “On global clustering algorithm: layer-oriented approach for multi hop wireless sensor network”, published on the International Review on Computers and Software (IRECOS) vol. 6, N. 2, page: 209-220 , may 2009. 13. M. Mazinani, M.H. Yaghmaee, Farzad Tashtarian M. Tolou Honary and J. Chitizadeh, “On global clustering algorithm: layer-oriented approach for First /Last node dying applications” published on the International Review on Computers and Software (IRECOS) vol. 4, N. 2, page: 229-240, march 2009. 14. A. Mohebi, Farzad Tashtarian, M.H. Yaghmaee Moghaddam, M.T Honary, “EELLER: Energy Efficient-Low Latency Express Routing for Wireless Sensor Networks” accepted and will be published on the The 2nd International Conference on Computer Engineering and Technology (ICCET 2010), 16-18, Chengdu, China, April 2010 15. J. Luo and J.-P. Hubaux, “Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks,” Proc. IEEE INFOCOM, 2005. 16. L. Sun, Y. Bi, J. Ma, “A Moving Strategy for Mobile Sinks in Wireless Sensor Networks”, In proceeding of 2nd IEEE Workshop on Wireless Mesh Networks(WiMesh), pages 151-153, September 2006. 17. Y. Bi, J. Niu, L. Sun, W. Huangfu, Y. Sun, “Moving Schemes for Mobile Sinks in Wireless Sensor Networks”, In proceeding of IEEE Performance, Computing, and Communications Conference(IPCCC) , pages 101-108 , April 2007. 18. Stefano Basagni, Alessio Carosi, Emanuel Melachrinoudis, Chiara Petrioli and Z. Maria Wang, “Controlled sink mobility for prolonging wireless sensor networks lifetime,” Springer Science Wireless Netw, 2008. 19. J. CHOI, Y. CHO, S. CHOI, S. LEE, “A Cluster Header-based Energy-efficient Mobile Sink Supporting Routing Protocol in Wireless Sensor Networks”,In proceeding of Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology, 2009. Page(s): 648 - 651 ,2009. 20. M. H. Khodashahi, F. Tashtarian, M. H. Yaghmaee Moghaddam, M. Tolou Honary, “Optimal Location for Mobile Sink in Wireless Sensor Networks”, In proceeding of Wireless Communications and Networking Conference (WCNC), IEEE,pages 1-6, 2010 ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 68 21. R. Zhang, M. J. Lee, S. Soon Joo, “Distributed mobile sink support in wireless sensornetworks”, In proceeding of IEEE Military Communications Conference(MILCOM) , pages 1-6, November 2008. 22. H. Luo, F. Ye, J. Cheng, S. Lu and L. Zhang, “TTDD: Twotier Data Dissemination in Large-scale Wireless Sensor Networks”, ACM/Kluwer Mobile Networks and Applications(MONET), pp. 148- 159, Sept. 2003. 23. J.RAO, S. BISWAS, “Data Harvesting in Sensor Networks Using Mobile Sinks”, IEEE Wireless Communications, December 2008 24. Y. Shi and Y.T. Hou, “Theoretical Results on Base StationMovement Problem for Sensor Network,” Proc. The 27th Conference on Computer Communications. IEEE INFOCOM2008,Page(s): 1 - 5 2008. 25. YoungSang Yun, Ye Xia, “Maximizing the Lifetime of Wireless Sensor Networks with Mobile Sink in Delay-Tolerant Applications” IEEE Transaction on Mobile Computing, pp: 1308 – 1318,Sept. 2010. 26. J. Luo, J. Panchard, M. Piorkowski, M. Grossglauserand J. Hubaux. MobiRoute: Routing towards a Mo-bile Sink for Improving Lifetime in Sensor Networks.2nd IEEE/ACM Intl Conf. on Distributed Computing inSensor Systems(DCOSS), pp. 480-497, 2006. 27. W. B. Heinzelman, A. P. Chandrakasan, H. Balakrishnan, “Anapplication-specific protocol architecture for wireless micro sensor networks,” IEEE Trans. Wireless Commun., vol. 1, no. 4, pp. 660-670,October 2002. 28. Pan, J.; Cai, L.; Hou, Y.T.; Shi, Y.; Shen, S.X. “Optimal base-station locations in two-tiered wireless sensor networks” IEEE Transaction on Mobile Computing, Vol. 4, No.5 September 2005. 29. Shuai Gao; Hongke Zhang; Das, S.K.” Efficient Data Collection in Wireless Sensor Networks with Path-Constrained Mobile Sinks” IEEE Transaction on Mobile Computing, Vol. 10, No.5 April 2011. 30. http://lpsolve.sourceforge.net/5.5/