بررسی راهکارهای مناسب جهت بهینه سازی مصرف انرژی در شبکه های حسگر …

سیاستهای تصدیق وصول بسته ها
سیاستهای کنترل جریان
۳-۷ روشهای مسیریابی
۳-۷-۱ روش ارسال سیل آسا
ارسال سیل آسا، یک تکنیک متداول است که غالباً برای کشف مسیر و انتشار اطلاعات در شبکه های باسیم و یا شبکه های موردی بیسیم به کار گرفته می شود.استراتژی مسیریابی در این روش بسیار ساده است و بر روی نگهداری توپولوژی شبکه به صورت هزینه بر و با الگوریتمهای کشف مسیر پیچیده تکیه نمی کند. ارسال سیل آسا، در حقیقت روش ساده ای را به کار می گیرد. به این ترتیب که هر گرهی که یک بسته داده و یا یک بسته کنترلی را دریافت می کند آن بسته را برای همه همسایه هایش می فرستد. بعد از انتقال، یک بسته همه مسیرهای ممکن را دنبال می کند. مگر این که شبکه قطع شود وگرنه بسته سرانجام به مقصدش می رسد. به علاوه چنان چه توپولوژی شبکه تغییر کند، بسته ای که انتقال داده شده است، مسیرهای جدید را دنبال می کند. شکل (۳-۱ ) اصول روش ارسال سیل آسا را در یک شبکه مخابره داده نشان می دهد.
 
شکل ( ۳-۱ ) : اصول روش ارسال سیل آسا
همان طور که در شکل (۳-۱) ملاحظه می شود، ارسال سیل آسا در ساده ترین شکلش، ممکن است باعث شود که بسته ها به وسیله گره های شبکه به صورت نا محدود برگردانده شوند. برای جلوگیری از این که یک بسته در داخل شبکه به طور نامحدود بچرخد، معمولاً یک رشته شماره پرش[۳۶] در داخل بسته قرار داده می شود.
به صورت اولیه، شماره پرش به صورت تقریبی برابر با قطر شبکه قرار داده می شود. هنگامی که بسته، در داخل شبکه حرکت می کند، شماره پرش به ازای هر پرشی که بسته می پیماید، یک واحد کاهش مییابد، هنگامی که شماره پرش بسته به صفر برسد، بسته به سادگی از پرش دست می کشد و دور انداخته می شود. یک روش دیگر برای حل این مشکل استفاده از یک رشته زمان برای زندگی[۳۷] یا رشته طول عمر است که این رشته، تعداد واحدهای زمانی که یک بسته مجاز است در داخل شبکه زندگی کند را نگه می دارد. بعد از سپری شدن این زمان و اتمام آن، بسته دیگر فرستاده نمی شود. روش ارسال سیل آسا، می تواند از طریق مشخص کردن بسته های داده به صورت منحصر به فرد از یکدیگر و وادار کردن هر گره شبکه برای دور انداختن همه بسته هایی که قبلاً فرستاده شده اند، بهبود یابد. البته چنین استراتژیهای، نیازمند نگه داشتن حداقل تاریخچه آخرین ترافیک است، به این منظور که مشخص شود کدامیک از بسته های داده قبلاً فرستاده شده اند. علیرغم سادگی قواعد انتقال و جلو بردن داده و هزینه نسبتاً پایین نگهداری که برای روش ارسال سیل آسا لازم است، این روش هنگام استفاده در شبکه های حسگر بیسیم، نقصها و کاستی هایی نیز دارد. اولین عیب روش ارسال سیل آسا، آمادگی و قابلیت این روش برای انفجار ترافیکی[۳۸] ، همان طور که در شکل(۳-۲ ) آمده، می باشد.
 
شکل ( ۳-۲ ) : انفجار ترافیکی در روش ارسال سیل آسا
این اثر نامطلوب، در اثر فرستاده شدن نسخه های تکراری بسته های داده و یا کنترلی به گره یکسان به وجود می آید.
دومین عیب عمده روش ارسال سیل آسا، مسئله اصطکاک و یا روی هم افتادگی[۳۹] است. در شکل (۳-۳) مسئله اصطکاک و روی هم افتادگی نشان داده شده است.
 
شکل ( ۳-۳ ) : اصطکاک و همپوشانی در روش ارسال سیل آسا
این مشکل هنگامی اتفاق می افتد که دو گره که ناحیه یکسانی را می پوشانند، بسته هایی که شامل اطلاعات یکسانی هستند را به گره یکسان می فرستند. سومین و مهم ترین عیب روش ارسال سیل آسا، کوری منابع است از آن جایی که روش و قاعده انتقال بسیار ساده ای که روش ارسال سیل آسا، برای مسیردهی بسته ها استفاده می کند، به بررسی محدودیت انرژی گره های حسگر نمی پردازد. این امر ممکن است منجر به تخلیه سریع انرژی گره ها شود و لذا طول عمر شبکه را کاهش بخشد. با توجه به عیبهای روش ارسال سیل آسا، روش جدیدی که از همین روش مشتق شد پیشنهاد گردید. این روش گوسیپینگ[۴۰] این روش نیز، مشابه با روش ارسال سیل آسا، یک راه ساده (روش خبرکشی ) نامیده شد.این روش نیز، مشابه با روش ارسال سیل آسا، یک راه ساده برای انتقال و به جلو بردن داده استفاده می کند و مشابه روش قبلی، نیازی به نگهدارنده گران قیمت توپولوژی و یا الگوریتمهای کشف مسیر پیچیده ندارد. اما برخلاف روش ارسال سیل آسا، که یک بسته داده را به سمت همه همسایه هایش می فرستد، در این روش هر گره، بسته های دریافت شده اش را به طرف یکی از همسایه هایش که به طور تصادفی انتخاب شده است، می فرستد. به محض دریافت بسته، همسایه ای که به صورت تصادفی انتخاب شده بود، یکی از همسایگانش را تصادفاً انتخاب کرده و بسته را برای آن گره انتخاب شده می فرستد. این فرآیند، تا زمانی که بسته به آن مقصد مورد نظرش برسد و یا شماره پرش ماکزیمم شود، ادامه پیدا می کند. روش گوسیپینگ، از معضل انفجار ترافیکی به وسیله محدود کردن تعداد بسته هایی که هر گره به طرف همسایه اش می فرستد به یک نسخه، جلوگیری می کند. یکی از مشکلات این روش آن است که، میزان تاخیری که یک بسته تا زمان رسیدن به مقصد تحمل می کند، ممکن است بیش از اندازه زیاد شود و این موضوع به ویژه در شبکه های بزرگ، بیشتر نمایان می شود و این به دلیل طبیعت تصادفی پروتکل که به صورت ذاتی، در یک لحظه یک مسیر را پیدا می کند، به وجود آمده است.
۳-۷-۲ روش های مبتنی بر خوشه بندی[۴۱]
یکی از معروفترین و بهترین روشهایی که به منظور مسیریابی داده ها

برای دانلود متن کامل پایان نامه به سایت zusa.ir مراجعه نمایید.

در شبکه های حسگر بیسیم پیشنهاد شد، روشهایی بود که بر مبنای دسته بندی کردن گره ها و یا به عبارت دیگر بر مبنای خوشه بندی کار می کند. در این روش ها، ابتدا همه گره های داخل شبکه بر اساس روشی خاص به دسته هایی تفکیک می شوند که در هر دسته که اغلب آن را خوشه می نامند، یک گره به عنوان سرگروه دسته انتخاب می شود و بقیه گره ها، گره های عادی نامیده می شوند. روش انتخاب سرگروه در هر روش، معیارهای متفاوتی را مدنظر قرار می دهد. در اکثر روشهای مبتنی بر خوشه، هدف اصلی آن است که توزیع مصرف انرژی بین همه گره ها یکنواخت گردد .
اولین و معروفترین روش مبتنی بر خوشه بندی روشی است که LEACH[42] خوانده می شود . این روش به عنوان اولین روش دسته بندی کردن گره های حسگر به وسیله Heinzelman و همراهانش پیشنهاد گردید.در حقیقت در روشهایی که بر اساس دسته بندی کردن گره ها کار می کنند، گره های حسگر نقشهای مختلفی را ایفا می کنند و بنا به نقشهایی که می گیرند ممکن است مصرف انرژی متفاوتی نیز داشته باشند. این دسته از روشها، جز بهترین الگوریتمهای مسیریابی در این شبکه هاست و هم اکنون نیز با الهام گرفتن از آنها روشهای جدیدی برای افزایش طول عمر شبکه پیشنهاد می شوند. روش سلسله ای خوشه بندی وفقی با انرژی پایین (LEACH ) الگوریتم مسیریابی است که به منظور جمع آوری و تحویل داده به یک ایستگاه پایه، طراحی شده است اهداف اصلی این روش عبارتند از:
افزایش طول عمر شبکه
کاهش مصرف انرژی برای هر گره حسگر شبکه
استفاده از متراکم نمودن داده به منظور کاهش تعداد پیغامهای مخابراتی
برای رسیدن به این اهداف LEACH یک روش سلسله مراتبی را به منظور سازماندهی شبکه به صورت مجموعه ای از خوشه ها اتخاذ می کند. هر خوشه به وسیله یک سرگروه خوشه انتخاب شده،مدیریت می شود. سرگروه خوشه، مسئول اجرای وظایف مختلفی فرض می شود. اولین وظیفه سرگروه خوشه، جمع آوری متناوب داده از اعضای خوشه است. به محض جمع آوری کردن داده، سرگروه خوشه، داده جمع آوری شده را به وسیله حذف کردن افزونگی بین مقادیر همبسته داده، متراکم می کند. دومین وظیفه اصلی سرگروه ها، انتقال مستقیم داده متراکم شده به سمت ایستگاه پایه است. انتقال داده متراکم شده به وسیله یک تک پرش انجام می شود. مدل شبکه ای که به وسیله این روش، استفاده می شود در شکل (۳- ۴) نمایش داده شده است.
 
شکل (۳-۴ ) : عملکرد روش سلسله ای خوشه بندی وفقی با انرژی پایین
سومین وظیفه اصلی سرگروه ها، ساختن یک برنامه زمانی مبتنی بر تسهیم سازی زمانی است که در این روش، به هر گره داخل خوشه، یک شیار زمانی[۴۳] تخصیص داده می شود که هر گره میتواند از شیار زمانی مربوط به خودش برای انتقال داده استفاده کند. سرگروه خوشه، برنامه زمانی را برای اعضای خوشه مربوطه اش، از طریق پخش همگانی[۴۴] ، اعلان می کند. به منظور کاهش دادن احتمال تصادف و برخورد بین حسگرهای داخل و خارج خوشه ها، گره های لیچ، یک طرح مبتنی بر دسترسی چندگانه[۴۵] و تقسیم بندی –کد[۴۶] را برای انجام ارتباطات خود به کار می گیرند. به طور خلاصه می توان گفت که عملیات اساسی این روش لیچ، در دو فاز مجزا سازماندهی شده است.
فاز اول که فاز شروع[۴۷] است، شامل دو گام است: گام انتخاب سرگروه و گام ساختن خوشه فاز دوم که فاز حالت پایدار[۴۸] نام دارد، بر روی جمع آوری داده، متراکم نمودن داده و تحویل داده بهایستگاه پایه، متمرکز است.
این دو فاز در شکل زیر به طور خلاصه نشان داده شده اند:
 
شکل (۳-۵ ) : دو فاز استفاده شده در روش سلسله ای خوشه بندی وفقی با انرژی پایین
طول دوره فاز شروع، نسبتا کوتاهتر از فاز حالت پایدار فرض می شود و این امر با هدف مینیمم کردن سربار پروتکل است. در ابتدای فاز شروع، یک دوره ای از انتخاب سرگروه ها شروع می شود. فرآیند انتخاب سرگروه خوشه ها، این اطمینان را به ما می دهد که این نقش در بین گره های حسگرها می چرخد و در نتیجه مصرف انرژی به طور یکنواخت در بین همه گره های شبکه پخش خواهد شد. به منظور مشخص کردن این که آیا نوبت یک گره است که سرگروه شود یا خیر، هر گره n ، یک عدد تصادفی بین صفر ویک مانند v را تولید می کند و آن را با آستانه انتخاب سرگروه خوشه یعنی T(n) ، مقایسه می کند. گره در صورتی سرگروه خوشه خواهد شد که مقدار تصادفی تولید شده اش یعنی v ، کمتر از آستانه مورد نظر گردد. آستانه انتخاب سرگروه خوشه، طوری طراحی شده است که با احتمال بالایی تضمین کند که کسر از قبل تعیین شده ای از گره ها مثلا p ، در هر دوره ای به عنوان سرگروه خوشه انتخاب شوند. همچنین، آستانه تضمین می کند که گره هایی که در آخرین p /1 دوره های قبلی، به کار گرفته شده اند در دوره فعلی به عنوان سرگروه انتخاب نشوند. به منظور رسیدن به این اهداف، آستانه T(n) یک گره مد نظر مانند n ، به کمک معادله زیر بیان می شود .
(۳-۱ )
که در این رابطه متغیر G ، مجموعه گره هایی را بیان می کند که در آخرین p /1 ، دوره ها [۴۹]، به عنوان سرگروه خوشه انتخاب نشده اند وr به دوره )راوند( جاری اشاره می کند. پارامتر از قبل تعریف شدهp ، احتمال سرگروه شدن را نشان می دهد. واضح است که اگر گرهی در آخرین p/1 دوره به عنوان سرگروه خوشه به کار گرفته شده باشد، در این دوره انتخاب نخواهد شد. در انتهای فرآیند انتخاب سرگروه خوشه، هر گرهی که به عنوان سرگروه خوشه انتخاب شده بود، نقش جدیدش را برای بقیه شبکه اعلان می کند. به محض دریافت
اعلان عنوان سرگروه خوشه، هر گره باقیمانده، یک خوشه را برای متصل شدن به آن خوشه، انتخاب می کند. معیار انتخاب، ممکن است براساس قدرت سیگنال دریافت شده در بین دیگر فاکتورها باشد. سپس گره ها، سرگروه خوشه انتخاب شده شان را از تصمی مشان برای عضویت در آن خوشه ، مطلع میکنند. به محض تشکیل خوشه، هر سرگروه خوشه، بسته های تسهیم سازی زمانی را ساخته و پخش میکند. این برنامه زمانی، شیارهای زمانی را که برای هر کدام از اعضای آن خوشه، تخصیص داده شده اند، مشخص میکند. همچنین هر سرگروه خوشه ، یک تقسیم بندی کد با دسترسی چندگانه[۵۰] را انتخاب می کند که این کد، سپس برای همه اعضای خوشه اش فرستاده می شود. این کد، با دقت، طوری انتخاب شده است که تداخل بین خوشه ها را کاهش می دهد. انتهای سیگنالهای فاز شروع، آغاز فاز حالت پایدار است. در این فاز، گره ها به جمع آوری اطلاعات می پردازند و شیاراختصاص داده شده به خودشان را برای انتقال داده های جمع آوری شده به سرگروه هایشان، استفاده می کنند. این جمع آوری داده به صورت متناوب انجام می پذیرد.
کاملاً واضح است که روش LEACH در مقایسه با روشهای قبلی همچون ارسال سیل آسای داده باعث صرفه جویی مشخصی در مصرف انرژی می شود. مقدار صرفه جویی انرژی، ابتدا بستگی به نسبت تراکم داده ای دارد که به وسیله سرگروه خوشه ها، به دست آمده است. علیرغم همه این منافع، به هرحال این الگوریتم نیز دارای معایبی است. این فرض که همه گره ها با یک پرش میتوانند به ایستگاه پایه برسند، ممکن است منطقی نباشد، زیرا که قابلیتها و ذخایر انرژی گره ها ممکن است در طول زمان و از یک گره به گره دیگر تغییر کند. به علاوه طول دوره حالت پایدار، نسبت به مقدار کاهش انرژی لازم برای جبران سرباری که در اثر فرآیند انتخاب خوشه به وجود آمده است، متغیر وبحرانی است.یک پریود حالت پایدار کوتاه، سربار پروتکل را افزایش می دهد همان گونه که، یک پریود طولانی، ممکن است منجر به تخلیه انرژی سرگروه خوشه گردد. الگوریتمهای متعددی برای غلبه بر ای نگونه مشکلات، پیشنهاد شده اند. پروتکل لیچ گسترش یافته یا ،X-LEACH به منظور توجه و رسیدگی به سطح انرژی گره ها در فرآیند انتخاب سرگروه خوشه ها، معرفی شد.
در این پروتکل، آستانه انتخاب سرگروه خوشه منتج شده یعنی T(n) ، که به وسیله گره n ،برای تعیین این که آیا آن گره در دوره جاری، یک سرگروه خوشه خواهد بود یا نه،با استفاده از معادله زیر تعریف میشود :
(۳-۲)
که در این معادله ، En,current ، انرژی جاری و En,max انرژی اولیه گره حسگر است. متغیرrn,s تعداد دوره های متوالی است که یک گره در آن دوره ها، سرگروه خوشه نبوده است. هنگامی که مقدار rn,s ، به p /1 برسد، آستانه T(n) ، به مقداری که قبل از وارد شدن انرژی باقیمانده درمعادله آستانه داشت، تنظیم شده و مجدداً مساوی با این مقدار قرار داده می شود. به علاوه rn,s هنگامی که یک گره، سرگروه خوشه می شود برابر با صفر قرار داده می شود. پروتکل X-LEACH خواص زیادی دارد که منجر به کاهش مصرف انرژی در این پروتکل می شود. نیازمندی انرژی برای این پروتکل، در بین همه گره های حسگر توزیع شده است،این از آنجایی است که آنها، نقش سرگروه خوشه را در یک مد گردشی نوبتی[۵۱] و بر اساس انرژی باقیمانده شان درنظر می گیرند.در واقع این الگوریتم، یک الگوریتم کاملا توزیع شده است که نیاز به هیچگونه اطلاعات کنترلی ازایستگاه پایه ندارد. در این روش مدیریت خوشه ها به صورت محلی انجام می شود و در نتیجه نیاز برای دانستن اطلاعات کلی درباره شبکه را از بین می برد. به علاوه متراکم کردن داده به وسیله خوشه ها، به طور گسترده ای به صرفه جویی در انرژی کمک خواهد کرد.از آنجایی که با متراکم شدن داده ها طول بسته هایی که در این حالت فرستاده می شود در مقایسه با طول بسته های داده متراکم نشده کمتر است. لذا انرژی لازم برای انتقال آنها نیز نسبت به حالتی که بسته متراکم نشده فرستاده شود کمتر خواهد بود.
۳-۷-۳ روش مبتنی بر زنجیر
یکی دیگر از روشهای مفیدی که به منظور کاهش مصرف انرژی در شبکه های حسگر بیسیم پیشنهاد شد روشی است که بر اساس یک ساختار زنجیری عمل می کند. در این روش در ابتدای عملکرد شبکه، همه گره ها بصورت یک ساختار زنجیری با طول حداقل در نظر گرفته میشوند و سپس یک گره به عنوان رهبر زنجیر انتخاب می شود. این گره، مسئولیت انتقال اطلاعات نهایی شبکه به سمت ایستگاه پایه را بر عهده خواهد داشت. روش مبتنی بر زنجیر PEGASIS [۵۲] از لحاظ مصرف انرژی بهتر از روش LEACH عمل می کند اما یکی از مهمترین عیبهای این روش، تاخیر زیاد در انتقال نهایی داده به سمت ایستگاه پایه است علت این تاخیر آن است که فقط یک گره همه داده ها را بعد از متراکم نمودن به ایستگاه نهایی خواهد فرستاد.
روش جمع آوری کارامد از لحاظ توان در سیستمهای اطلاعاتی حسگر (PEGASIS) یک روش مسیریابی مبتنی بر ساختار زنجیری در شبکه های حسگر بیسیم هستند اهداف اصلی این پروتکل ، در دو مورد خلاصه می شود: