الگوریتم های مسیریابی با بهره بری انرژی بالا برای شبکه های سنسوری بی سیم (1)

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

مقدمه

WSN ارتباط بی سیم ساده، تأسیسات محاسباتی بهینه ساز و برخی از انواع عملیات های حسگری محیط فیزیکی را به شکل جدیدی از شبکه، ترکیب می کند که می تواند به طور عمیقی در محیط فیزیکی ما وارد شوند. این شبکه ها دارای یک تعداد زیاد سنسورهای تعبیه شده هستند که دارای قابلیت ارتباط از طریق لینک های بی سیم هستند. این گره های سنسوری به یک پردازنده ی کوچک مجهزند و دارای حافظه ی محدود هستند. علاوه بر این، این گره ها دارای منبع انرژی محدودی هستند. آنها در نواحی مورد استفاده قرار می گیرند، که باید به طور مداوم محیط خود را مورد ارزیابی قرار دهند( مانند دما، حرکت، صدا، نور و غیره). هدف انتقال داده های ارزیابی شده از گره منبع به پایگاه اصلی( سینک) است( با کمک همسایه های آن که همسایه های آن گره، گره هایی هستند که به ناحیه ی ارتباطی تحت پوشش آن گره، متعلق هستند( یک ناحیه ی تحت پوشش گره سنسور، یک دایره با شعاع r تولید می کند) ). پایگاه اصلی مسئول دریافت تمام داده های جمع آوری شده بوسیله ی گره های سنسوری در WSN هستند و معمولا به یک برنامه ی کاربردی یا اینترنت در ارتباط است.
در شکل 1 یک انتقال داده از گره منبع A به پایگاه اصلی نشان داده شده است. پایگاه اصلی در داخل ناحیه ی پوشش داده شده توسط گره، قرار ندارد. از این رو A قادر به ارسال مستقیم داده های تشخیص داده ی خود را به پایگاه اصلی ندارد( در مورد F، این گره می تواند به طور مستقیم داده های خود را ارسال کند زیرا این بخش به طور مستقیم با پایگاه اصلی در تماس است). پس A می تواند داده های خود را با کمک همسایه ی خود ارسال کند. در این مورد، A داده های خود را به گره های B، B به C و C به D و D به E و در نهایت E به طور مستقیم داده ها را به پایگاه اصلی ارسال می کند. مسیر ایجاد شده میان گره سنسوری A و پایگاه اصلی عبارتند است از:
پایگاه اصلی A→B→C→D→E→
استراتژی پیدا کردن یک مسیر از یک گره خاص به پایگاه اصلی، الگوریتم مسیریابی نامیده می شود. این مسئله در نظر گرفته می شود که ویژگی های گره برای بهینه نمودن عمر مفید شبکه و نهفتگی( latency) در انتقال داده ها مورد استفاده قرار می گیرد.
الگوریتم های الهام گرفته شده از برخی از پدیده های بیولوژیک، در برخی ارتباطات هوش مصنوعی متداول گشته است که عمدتا این مسئله به دلیل این انجام شده است که آنها گزینه های مناسبی برای حل مسائل علمی و مهندسی هستند مخصوصا الگوریتم های ACO به طور موفقیت آمیز برای حل مسائل مسیریابی در شبکه های بی سیم و با سیم مورد استفاده قرار گرفته است.
در این کار، دو الگوریتم مسیریابی بر پایه ی ACO برای WSN انتخاب شده است که این الگوریتم ها در سطح شبیه سازی اجرا گشته است. از نظرما، طرح پیشنهادی اولیه نمی تواند در فاز عملی اجرایی شود زیرا در این کارها این مسئله فرض شده است که اندازه های بسته های داده ای انتقال یافته بر روی مصرف انرژی اثری ندارند. علاوه براین سه سناریوی مختلف شبیه سازی شده اند اما ما متوجه شدیم که هیچ کدام از آنها دارای وضعیت واقعی نیستند.
بخش های اصلی این مقاله، دو بخش هستند. از یک طرف، ما کارایی الگوریتم ها را با در نظر گرفتن انرژی مصرف شده بوسیله ی یک گره سنسور و بسته به اندازه ی داده ی انتقال یافته، مقایسه می کنیم. علاوه بر آن، ما یک سناریو تعریف می کنیم که در آن هر سنسور در ابتدای کار، دارای تغییر کامل در باطری خود است و سپس شبیه سازی تا زمانی انجام می شود که برخی گره ها از منبع جدا شوند.
به عبارت دیگربر اساس آزمایشات، برای تعیین استراتژی از هر یک از الگوریتم های انتخاب می شود که دارای عمر مفید بالاتر و تأخیر بهتری هستند. هدف روشن سازی کارکردهای واقعی و امکان پذیری استفاده از این الگوریتم هاست.

کارهای مربوطه

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

الگوریتم های مسیریابی مرتبه ای

الگوریتم های مرتبه ای دسته بندی سلسله مراتبی( LEA CH ) به طور تصادفی یک تعداد اندک از گره های سنسوری را به عنوان خوشه ها انتخاب می کند و این نقش را بر عهده دارد که مقدار بار انرژی را در میان سنسورهای شبکه توزیع کند. این الگوریتم، که الگوریتم های جمع آوری با مصرف بهینه در سیستم های اطلاعاتی سنسوری(PEGASIS) نامیده می شود، برای طولانی کردن عمر مفید شبکه، پیشنهاد می شوند. در این الگوریتم گره های سنسوری تنها نیازمند ایجاد ارتباط با نزدیک ترین همسایه های خود و پایگاه اصلی هستند. وقتی نوبت ارتباط تمام گره ها با پایگاه اصلی، پایان می یابد، یک نوبت جدید بوجود می آید. این مسئله میزان انرژی مورد نیاز برای انتقال داده ها را در هر دوره کاهش می دهد زیرا تخلیه ی انرژی در تمام گره ها به طور یکنواخت انجام می شود.

الگوریتم های مسیریابی فلت

در برخی از مقاله ها، الگوریتم نفوذ مستقیم ارائه شده است. این الگوریتم یک واسط داده( DC) است و دارای یک مثال کاربردی در تشخیص در زمان هایی است که تمام داده ها ایجاد شده بوسیله ی گره های سنسوری بوسیله ی جفت های مقداری مشخصه نامگذاری شده باشند. ایده ی اصلی مثال DC ترکیب داه های بوجود آمده از منابع موجود بر سر راه( در توده ی داخل شبکه) می باشد که این کار بوسیله ی زدایش تکرار اطلاعات میان فایلهای گوناگون، به حداقل رساندن تعداد انتقال ها و بنابراین کاهش مصرف انرژی در شبکه و بنابراین طولانی نمودن عمر مفید آنها، انجام می شود. مسیریابی رومر( Rumor routing) نیز که بوسیله ی برخی از محققین مورد استفاده قرار گرفته است، تعریف شده است. این نوع از مسیریابی عمدتا برای کاربردهایی مورد استفاده قرار می گیرند که در آنها مسیریابی جغرافیایی قابل اجرا نباشند. ایده ی کلیدی این مسیریابی از طریق جستجوی گره هایی است که در یک رویداد خاص مشاهده شده اند( به جای آنکه تمام شبکه به منظور بدست آوردن اطلاعات مورد بررسی قرارگیرد).

الگوریتم های مسیریابی بر پایه ی محل

الگوریتم های جغرافیایی سازگار فیدلیتی نیز مورد استفاده قرار می گیرند. این الگوریتم ها مسیریابی ایجاد شده بر پایه ی آگاهی از مکان انرژی در ابتدا برای شبکه های ad hoc و شبکه های سیار طراحی شدند اما ممکن است که در WSN نیز قابل استفاده باشند. ناحیه ی شبکه یک شبکه ی مجازی ایجاد می کنند. به جای هر ناحیه، گره ها با همدیگر مشارکت می کنند تا بتوانند نقش های مختلف را ایفا کنند. در برخی مقالات، الگوریتم مسیریابی آگاهی-انرژی و جغرافیایی( GEAR) بیان شده است. از این الگوریتم برای ایجاد ذهنیت به منظور انتخاب همسایه های مناسب مورد استفاده قرار می گیرد تا بدین وسیله مسیریابی یک بسته ی انتقال گیرنده به مقصد، تعیین گردد. ایده ی کلیدی منحصر کردن تعداد علاقه مندی ها در نفوذ جهت دار با استفاده از در نظر گرفتن تنها یک ناحیه ی معین به جای ارسال علاقه مندی ها به تمام شبکه، است. با انجام این کار، GEAR می تواند انرژی کمتری نسبت به روش نفوذ جهت دار مصرف کند.
انواع دیگری از الگوریتم های مسیریابی وجود دارد که بر اساس ACO کار می کنند( این الگوریتم ها نیز می تواند به الگوریتم های فلت، مرتبه ای یا مکانی تقسیم بندی شوند).

الگوریتم های بر پایه ی کلنی مورچه ها

برخی از نمونه ها از الگوریتم های بر پایه ی ACO به صورت زیر هستند. اولین الگوریتم بر پایه ی ACO بوسیله ی Dorigo و Di Caro پیشنهاد شده است که شبکه ی مورچه نامیده می شود. این الگوریتم یک الگوریتم ابداعی برای مسیریابی بسته ها در شبکه های ارتباطاتی است. در شبکه ی مورچه، یک گروه از عوامل متحرک( یا مورچه های مصنوعی) مسیرهایی را در میان جفت گره ها ایجاد می کنند و شبکه را به طوریکجا مورد جستجو قرار می دهند و همچنین اطلاعات بدست آورده را برای بروزرسانی جداول مسیریابی در گره ها، مورد تبادل قرار می دهند. الگوریتمی که ARA نامیده می شود، الگوریتمی است که در شبکه های ad hoc و سیار( MANETs) مورد استفاده قرار می گیرند. در این الگوریتم از رفتار لایه ای فرمون های مورچه ها استفاده می شود. به هر حال دو الگوریتم بالا برای WSN ها مناسب نیستند. در مرجع ، یک الگوریتم ACO( PACO) برای جستجوی مسیرهای چندگانه میان گره های منبع و پایگاه اصلی در MANETs استفاده می شود. اگرچه PACO انتقال داده را به طور مؤثر بهبود می دهد، تعداد مورچه های مورد نیاز زیاد تر است و در نتیجه مصرف انرژی در مرحله ی شروع، بیشتر است. در مقاله ای، یک الگوریتم مسیریابی خود بهینه و بهبود یافته با الهام گرفتن از کلنی مورچه ی برای WSN ارائه شده است. این مکانیزم بر پایه ی کیفیت اتصال، پارامترهای انرژی و سرعت پایه گذاری شده اند. معماری لایه های متقاطع مورد استفاده به WSN کمک می کند تا بازده ی کلی داده را بهبود دهد مخصوصا در موارد ترافیک زمانی واقعی. در مقاله ای دیگر، یک الگوریتم مسیریابی چند مسیره( MRP) بر پایه ی خوشه ای شدن دینامیک و ACO بیان شده است. یک چنین روشی می تواند عمر مفید شبکه را ماکزیمم کند و مصرف انرژی را کاهش دهد. در مقاله ای دیگر، یک روش مسیریابی با استفاده از یک الگوریتم ACO برای WSN پیشنهاد شده است که شامل گره های سیار محدود شده یا پایدار است. این روش همچنین در یک جزء سخت افزاری کوچک به عنوان چیپ روتر مورد استفاده قرار می گیرد. محققین همچنین یک روش مسیریابی برپایه ی محل- آگاهی بهینه شده را با الهام گرفتن از کلنی مورچه ها( ACLR) ارائه کرده اند. در واقع این الگوریتم یک الگوریتم مکان- آگاهی و یک الگوریتم فلت است. این الگوریتم مقدار انرژی اضافی را با اطلاعات مکان محلی و مکان کلی گره ها ترکیب می کند و احتمال انتخاب گره سنسوری بعدی که پرش به آن انجام می شود، را تعریف می کند. در مقاله ای دیگر، یک تأخیر زمانی را به منظورماکزیمم کردن عمر مفید شبکه، پیشنهاد می کند. این مقاله همچنین سرویس های انتقال داده ای در زمان واقعی مهیا نموده است. یک الگوریتم مسیریابی برای توده ی داده ای و بر اساس ACO ( ACAR) نیز ارائه شده است. ایده ی اصلی این الگوریتم بهینه سازی مسیر تجمع داده با استفاده از برخی از عوامل مشارکت کننده بود که مورچه نامیده می شدند. در این روش فاکتورهایی مانند انرژی، فاصله، و افزایش بازده مورد استفاده قرار می گیرد. در مقاله ای ارائه شده است که در آن، نویسندگان یک فرمون را بر اساس الگوریتم نفوذ جهت دهی شده با ویژگی آگاهی از انرژی( PEADD) را برای WSN پیشنهاد کردند که در آن با استفاده از مقادیر فرمون، عمر مفید شبکه بالا می رود و قابلیت اطمینان شبکه نیز با استفاده از حفظ توزیع انرژی یکنواخت در گره های سنسوری شبکه، افزایش می یابد. در مقاله ای دیگر، این دیده می شود که نویسندگان یک الگوریتم بر پایه ی ACO برای معماری های فلت و آگاهی دهی از ایجاد تمرکز، پیشنهاد کردند. این ارائه سعی می کند تا عمر مفید شبکه را ماکزیمم کند و همچنین این الگوریتم توانایی واکنش نشان دادن در برابر تغییرات در شبکه را نیز دارد. در مقاله ای دیگر، یک کیفیت از راه حل مسیریابی سرویسی( QoS) پیشنهاد شده است. این روش الگوریتم مسیریابی QoS بر پایه ی ACO نامیده می شود و بهترین مسیرهایی را جستجو می کند که نیازمندی های QoS را با استفاده از مورچه های با هوش مصنوعی، برطرف می کند. الگوریتم QoSR بر پایه ی ACO، سبک و سنگین کردن در میان یک نیازمندی QoS معین و پیچیدگی محاسباتی قابل قبول است. در مقاله ای دیگر، الگوریتم با مصرف انرژی بهینه ی مسیریابی بر پایه ی مورچه ی( FEABR ) می تواند پدیدار شود و برای معماری های آگاهی دهنده ی مکانی و الگوریتم های فلت مورد استفاده قرار گیرد. در این ارائه، مورچه های مصنوعی مسیرهای با مصرف کمتر انرژی را در شبکه جستجو می کنند در حالی که اندازه ی مورچه های مصنوعی در طی ارتباط میان گره های سنسوری، کاسته می شود. سایر الگوریتم های مسیریابی مشابه که بر پایه ی ACO وبرای WSN هستند، در مقاله ای دیگر، آورده شده اند. در این مقاله نویسندگان مکانیزمهای بیولوژیک الهام گرفته شده و تکنیک های مربوطه برای حل مسئله ی مسیریابی داده در WSN را نشان داده اند که این تکنیک ها شامل روش های عمومی و بر پایه ی مورچه است. در مقاله ای دیگر ، نویسندگان مثال های اصلی از الگوریتم های مسیریابی شبکه ای را بیان نموده اند که در آنها طراحی پایین به بالا از رفتارهای جمعی کلنی های حشراتی مانند مورچه و زنبور عسل، الهام گرفته شده است.
در زیر الگوریتم ACO به طور پایه ای آورده شده است.
خطوط کلی الگوریتم های مسیریابی بر پایه ی ACO برای WSN
الگوریتم ACO از رفتار طبیعی کلنی مورچه ها الهام گرفته شده است.

رفتار کلنی مورچه ها

مورچه ها حشراتی هستند که به صورت کلنی زندگی می کنند. به خاطر همکاری دو طرفه ی آنها، این حشرات رفتارهای پیچیده ای از خود نشان می دهند که نیازمند هیچگونه کنترل و برنامه ریزی نیست. یک جنبه ی جالب از رفتار بسیاری از مورچه ها، قابلیت پیدا کردن کوتاه ترین راه در میان منبع غذایی ولانه ی آنهاست. در حالی که مورچه ها در میان لانه و منبع غذایی خود در حال حرکت هستند، برخی انواع مورچه ها مانند مورچه های آرژآنتینی یک ماده به نام فرمون از خود متصاعد می کنند. اگر هیچ فرمونی در مسیر قرار نداشته باشد، مورچه ها معمولا به صورت تصادفی حرکت می کنند اما اگر در مسیر فرمون وجود داشته باشد، آنها تمایل دارند تا آن را دنبال کنند. بیشتر مورچه ها مسیرهایی را ترجیح می دهند که دارای مقدار فرمون بالاتری است.
شکل 2 نحوه ی پیدا کردن کوتاه ترین مسیر میان منبع غذایی و لانه ی مورچه ها( A) را بوسیله ی این مورچه ها نشان می دهد. به دلیل آنکه در موقعیت B، مورچه ها تصمیم می گیرند تا به راست حرکت کنند یا بله چپ. سطح بیشتر فرمون در سمت راست به مورچه انگیزه ی بیشتری می دهد و بنابراین احتمال به راست پیچیدن بیشتر می شود. به دلیل آنکه مسیر B→C→D از مسیر B→H→D کوچک تر است، مورچه ی اول آن را دنبال می کند تابه D برسد. نتایج نشان می دهد که یک مورچه ی بازگشت کننده از E به D میزان فرمون بالاتری را در مسیر D→C→B دریافت می کند که بوسیله ی نیمی از مورچه هایی که شانس تصمیم گیری مسیر D→C→B→A را داسته اند و آنهایی که از مسیر B→C→D آمده اند، ایجاد شده است. آنها بنابراین مسیر D→C→B را نسبت به مسیر D→H→B ترجیح می دهند زیرا یک تعداد از مورچه ها از مسیر B→C→D را در واحد زمان عبور کرده اند که تعداد این مورچه ها از تعداد مورچه های عبور کرده از مسیر B→H→D بیشتر است. این مسئله موجب می شود تا مقدار فرمون در مسیر با کوتاه ترین طول افزایش یابد. نتایج نهایی این است که خیلی سریع تمام مورچه ها کوتاه ترین راه را انتخاب می کنند.
استفاده از مطالب این مقاله، با ذکر منبع راسخون، بلامانع می باشد.