• مقدمه[1]

مسأله حفره انرژی یکی از عوامل اصلی محدودیت طول عمر شبکه‌های حسگر بی‌سیم (WSNs)[1] محسوب می‌شود [1]. مطابق شکل 1، در شبکه‌های سنتی مبتنی ‌بر یک گره چاهک ثابت، الگوی ترافیکی چندبه‌یک حاکم است. درواقع، حسگرهای مختلف پس از سنجش کمیتی از محیط و انجام پردازش‌های محلی، داده‌های خود را با استفاده از یک الگوریتم مسیریابی به گره چاهک ارسال می‌کنند؛ بنابراین، حسگرهای نزدیک به گره چاهک، مسئولیت خطیری در دریافت، تجمیع و ارسال داده سایر حسگرها بر عهده دارند. این مسأله باعث می‌شود این گره‌ها با سرعت بیشتری انرژی خود را از دست بدهند و نتوانند به فعالیت خود ادامه دهند. در این حالت، ارتباط چاهک با سایر گره‌های شبکه، قطع و شبکه دچار دوپارگی یا چندپارگی می‌شود. این در حالی است که مصرف عادلانه انرژی توسط همه حسگرها، مرگ اولین گره را به تعویق می‌اندازد و طول عمر شبکه را بهبود می‌بخشد. در این ارتباط، استفاده از گره چاهک متحرک ایده کارآمدی است که کمک شایانی به کاهش مصرف انرژی و توازن بار بهتر در شبکه می‌کند [2،3].

یک چاهک متحرک، حرکت خود را از نقطه‌ای در شبکه، آغاز و با توقف در نقاطی از پیش تعیین شده‌، داده حس‌شده توسط گره‌ها را جمع‌آوری می‌کند. مسلماً تعیین نقاط توقف[2] و طراحی مسیر حرکت چاهک، نقش مهمی در تأخیر جمع‌آوری داده و مصرف انرژی در شبکه دارد.

شکل (1): مسأله حفره انرژی در شبکه‌های حسگر بی‌سیم سنتی

تعامل مستقیم چاهک با هریک از حسگرها، با کاهش مصرف انرژی آنها همراه است؛ اما این راهکار به مسیرهای طولانی برای حرکت گره چاهک در شبکه منجر می‌شود. این در حالی است که تلفیق روش‌های مدرن و سنتی برای جمع‌آوری داده همچون استفاده همزمان از چاهک متحرک و خوشه‌بندی می‌تواند مصالحه‌ای بین مصرف انرژی و تأخیر برقرار کند. براساس این، گره‌های حسگر به شکل مناسبی خوشه‌بندی می‌شوند و داده‌های خود را ازطریق یک درخت مسیریابی درون‌خوشه‌ای کارآمد برای سرخوشه[3] (CH) ارسال می‌کنند. حال، چاهک به‌جای تعامل مستقیم با حسگرها، با پیمودن مسیر کوتاه‌تری، داده تجمیع‌شده در سرخوشه‌ها را جمع‌آوری می‌کند؛ بنابراین، تأخیر حرکت چاهک به شکل چشمگیری کاهش خواهد یافت.

به‌تازگی تحقیقات مختلفی در زمینة استفاده از گره چاهک متحرک در شبکه‌های حسگر بی‌سیم ارائه شده‌اند [4،5]؛ اما بهره‌گیری همزمان از یک الگوریتم‌ بهینه‌سازی کلونی مورچه[4] (ACO) اصلاح‌شده و یک خوشه‌بندی مناسب در کنار تعیین کارآمد مسیر گره چاهک متحرک و نقاط توقف آن به بهبود چشمگیر تأخیر و مصرف انرژی در شبکه منجر می‌شود. یکی از نقاط ضعف کارهای اخیر، توجه‌نکردن به این مهم در فرایند جمع‌آوری داده در شبکه است [6-8]. به این منظور، در این مقاله، الگوریتم کارآمدی موسوم به «جمع‌آوری گلبرگ‌گونه داده مبتنی بر الگوریتم ACO [5](ARPDA)» ارائه می‌شود که به‌طور همزمان به خوشه‌بندی، تعیین سرخوشه، مسیریابی درون‌خوشه‌ای مبتنی‌ بر الگوریتمACO ، تعیین نقاط توقف گره چاهک و طراحی مسیر حرکت گره چاهک می‌پردازد. در روش پیشنهادی، پس از خوشه‌بندی مناسب شبکه و تعیین سرخوشه‌ها، هر گره داده‌ خود را ازطریق یک درخت مسیریابی به سرخوشه ارسال می‌کند. در تعیین سرخوشه، علاوه بر مسأله انرژی، ملاحظاتی در ارتباط با حرکت چاهک نیز در نظر گرفته می‌شود. درخت مسیریابی در هر خوشه به شیوه‌ای ساخته می‌شود که ضمن کاهش مصرف انرژی، به توازن بار در خوشه منجر شود. شبکه به‌صورت فرضی به خطوط و دوایر متحدالمرکزی افراز می‌شود و براساس آنها و با توجه به موقعیت سرخوشه‌ها، مسیر حرکت گره چاهک به شیوه‌ای تعیین می‌شود که مصالحه بین مصرف انرژی و تأخیر برقرار شود. از دیگر قابلیت‌های الگوریتم پیشنهادی استفاده از حداقل تعداد نقطه توقف برای جمع‌آوری داده سرخوشه‌ها است.

ساختار این مقاله به شرح زیر سازمان‌دهی شده است: در بخش 2، کارهای مرتبط پیشین مرور می‌شود. مدل شبکه و مفروضات را می‌توان در بخش 3 دنبال کرد. در بخش 4، الگوریتم‌ پیشنهادی مفصل تشریح می‌شود. بخش 5، به شبیه‌سازی و ارزیابی عملکرد الگوریتم‌ پیشنهادی می‌پردازد. درنهایت، نتایج حاصل از این مقاله در بخش 6 ارائه خواهند شد.

2- کارهای پیشین

به‌تازگی تحقیقات جدیدی در ارتباط با استفاده از چاهک متحرک و الگوریتم بهینه‌سازی کلونی مورچه در شبکه‌های حسگر بی‌سیم ارائه شده است. در این بخش، ابتدا مرور جداگانه‌ای بر کارهای مرتبط با هر دو مسأله خواهیم داشت. سپس، تحقیقاتی که از الگوریتم ACO در جمع‌آوری داده مبتنی بر چاهک متحرک استفاده کرده‌اند را به‌طور اجمالی مطالعه می‌کنیم.

2-1- استفاده از گره چاهک متحرک

مراجع [9،10]، مسأله انتخاب مناسب نقاط ملاقات[6] در شبکه‌های حسگر بی‌سیم مجهز به گره چاهک متحرک را بررسی می‌کنند. در [9]، ابتدا با فرمول‌بندی مسأله براساس انرژی گره‌های حسگر، معیاری برای تعیین نقاط ملاقات مناسب از میان گره‌ها ارائه می‌شود. سپس با تعریف یک حد آستانه، نقش این نقاط را تغییر می‌دهد. درنهایت، با استفاده از الگوریتم فروشنده دوره‌‌گرد[7]، مسیر حرکت گره چاهک در شبکه را مشخص می‌کند. در [10]، از چاهک متحرک به‌منظور کاهش انرژی مصرفی و کاهش نرخ از دست رفتن بسته‌های داده استفاده می‌شود. این مرجع، الگوریتم کارآمدی موسوم به [8]PSOBS ارائه می‌دهد که مشتمل بر دو فاز است. در فاز اول الگوریتم، نقاط ملاقات براساس الگوریتم بهینه‌سازی ازدحام ذرات (PSO) به‌صورتی تعیین می‌شوند که استفاده مناسب‌تری از منابع شبکه حاصل شود. سپس در فاز دوم، یک مسیر کارآمد از بین این نقاط برای حرکت گره چاهک طراحی می‌شود. مرجع [11]، با تقسیم شبکه به چند سلول، از دو چاهک استفاده می‌کند. براساس ارتباط بین هر سلول و چاهک‌های موجود، سلول‌ها به دو دسته سلول با ارتباط تک‌‌پرشی و سلول با ارتباط چندپرشی تقسیم می‌شوند. هریک از چاهک‌ها روی مسیرهای لوزی شکل هم‌مرکز به‌گونه‌ای حرکت می‌کنند که همزمان، نیمی از شبکه را پوشش دهند. سپس ازطریق مخابرات تک‌پرشی یا چندپرشی به تجمیع داده‌ حسگرها می‌پردازند.

در [12،13]، با هدف کاهش تأخیر و مصرف انرژی در شبکه‌ حسگر بی‌سیم، از تئوری نمونه‌برداری فشرده، خوشه‌بندی و گره چاهک متحرک به‌صورت همزمان‌ استفاده می‌شود. مرجع [13]، با در نظر گرفتن چند توپولوژی خاص، تحلیلی به‌منظور تعیین تعداد بهینه خوشه‌ها ارائه می‌دهد. در این مرجع، گره چاهک در یک مسیر ثابت به‌صورت متناوب در حرکت است. هر حسگر داده‌ خود را بدون فشرده‌سازی به سرخوشه متناظر ارسال می‌کند. گره‌های سرخوشه‌ نیز پس از تجمیع داده اعضای خود، نتیجه را ازطریق سرخوشه‌های نزدیک به مسیر حرکت گره چاهک یا حسگرهایی که در فاصله تک‌پرشی این مسیر قرار دارند، به گره چاهک ارسال می‌کنند. مرجع [14]، از مزایای استفاده همزمان از خوشه‌بندی و گره‌‌های چاهک متحرک بهره می‌برد. در ابتدا مسیر حرکت گره‌های چاهک، با تقسیم‌ ناحیه مدنظر به چندین زیرناحیه نابرابر و محاسبه میانگین انرژی باقی‌مانده حسگرهای هر قسمت تعیین می‌شود. سپس خوشه‌بندی حسگرها با استفاده از پروتکل توزیع‌شده نابرابر مبتنی ‌بر منطق فازی انجام می‌گیرد؛ به‌طوری‌که تعداد خوشه‌‌های نزدیک به مسیر حرکت گره‌های چاهک بیشتر خواهد بود. الگوریتم پیشنهادی به افزایش طول عمر شبکه و رفع مشکل حفره انرژی در شبکه‌های مقیاس بزرگ منجر می‌شود. مطالعه تحقیقاتی ارائه‌شده در [15] با استفاده از الگوریتم ژنتیک، مسأله فروشنده دوره‌گرد را به‌منظور تعیین حرکت چاهک متحرک حل می‌کند. امکان تجمیع دادگان بافرشده چندین سرخوشه در یک نقطه توقف و همچنین، نگاه همزمان به دو مسأله انرژی و تأخیر در قالب یک مسیر گلبرگ‌گونه چاهک از مهم‌ترین تفاوت‌های روش پیشنهادی در این مقاله در مقایسه با [15] است.

نویسندگان در [16]، استفاده از گره‌های چاهک متحرک مجهز به چند کارت رادیویی را در شبکه‌های حسگر بی‌سیم پیشنهاد می‌دهند که در آن با به‌کارگیری از یک مدل MILP مناسب، حرکت گره‌های چاهک و نقاط توقف آنها طراحی می‌شود. در ابتدا شبکه به‌طور وفقی به چندین زیربخش تقسیم می‌شود و هر گره چاهک در بخش متناظر خود حرکت می‌کند. سپس در نقاطی برای جمع‌آوری داده‌های بافرشده در سرخوشه‌ها توقف می‌کند. زمان‌بندی دریافت داده‌های بافرشده از دیگر نقاط قوت این کار تحقیقاتی قلمداد می‌شود. مؤلفان نشان می‌دهند برخورداری گره چاهک از چند رادیو، با کاهش چشمگیر تأخیر جمع‌آوری داده همراه است. در [17] با هدف بهره‌گیری از گره چاهک متحرک، شبکه به سلول‌های مشبکی تقسیم و برای هریک، سرسلولی انتخاب می‌شود. مسیر حرکت گره چاهک با چرخه همیلتونی طراحی می‌شود؛ درنهایت، سلول‌های مجاور داده‌های خود را به‌صورت تک‌پرشی برای گره چاهک ارسال می‌کنند. مراجع [18] و [19]، استفاده از چندین گره چاهک به‌همراه خوشه‌بندی را یک روش کارآمد برای حل چالش‌ طول عمر در شبکه‌های حسگر بی‌سیم برمی‌شمارند؛ به‌طوری‌که روش پیشنهادی در [18] با امتیازدهی گره‌ها به انتخاب سرخوشه‌ها می‌پردازد. سپس با تقسیم‌بندی شبکه، هر چاهک متحرک را به یک قسمت تخصیص می‌دهد.

نویسندگان در [20] با اشاره به کاربردهای شبکه‌های حسگر، ابتدا به خوشه‌بندی شبکه با الگوریتم بهینه‌سازی ازدحام ذرات می‌پردازند. سپس تعداد بهینه نقاط توقف گره چاهک را محاسبه می‌کنند و براساس آن، مسیر کارآمدی را برای جمع‌آوری داده‌ سرخوشه‌ها در شبکه پیشنهاد می‌دهند. مرجع [21] ابتدا به خوشه‌بندی حسگر‌ها و انتخاب سرخوشه‌های آنها با استفاده از الگوریتم جست‌وجوی عقاب طاس می‌پردازد. سپس با بهره‌گیری از یک شبکه عصبی ترکیبی، مسیر حرکت گره چاهک را در میان نقاط توقف از قبل تعیین شده طراحی می‌کند.

2-2- مسیریابی مبتنی بر ACO

در [22] با ارائه الگوریتم کارآمدی موسوم به ^[9]EAACA، از روش ACO به‌منظور انتخاب کوتاه‌ترین مسیر از حسگر مبدأ تا گره چاهک استفاده می‌شود. بدین منظور، از دو معیار فاصله بین حسگر بعدی تا گره چاهک و انرژی باقی‌مانده آن حسگر استفاده شده است. نویسندگان مرجع [23] نیز از معیار فاصله و دو معیار انرژی (انرژی باقی‌مانده حسگرها و انرژی مورد نیاز برای ارسال با استفاده از پیوند ایجادشده) در تابع احتمال الگوریتم ACO استفاده می‌کنند. در این مرجع، با تلفیق انرژی مصرفی حسگرها و گام‌های موجود در مسیر انتخابی، روش جدیدی به‌منظور به‌روز‌رسانی فرومون^[10] مورچه‌ها پیشنهاد شده است. در [24]، الگوریتم کارآمدی مبتنی بر روش ACO به‌منظور مسیریابی داده در شبکه‌های حسگر بی‌سیم پیشنهاد می‌شود‌. در این الگوریتم با بهبود تابع احتمال، در نظر گرفتن فاصله ارتباطی، جهت ارسال داده و انرژی باقی‌مانده حسگرها، مسیر بهینه‌ای از حسگر مبدأ تا حسگر مقصد شکل می‌گیرد. نویسندگان در مرجع [25] یک الگوریتم مسیریابی مبتنی بر خوشه را پیشنهاد می‌کنند. آنها در فاز اول الگوریتم با در نظر گرفتن سه معیار انرژی باقی‌مانده حسگرها، تعداد حسگرهای همسایه هر گره و فاصله آن تا گره چاهک سرخوشه را تعیین می‌کنند. سپس در فاز دوم، از الگوریتم  ACOبه‌منظور ایجاد زنجیری مشابه روش PEGASIS^[11] بین سرخوشه‌ها و گره چاهک استفاده می‌شود. مرجع [26] با هدف کاهش مصرف انرژی و افزایش طول عمر شبکه، پارامترهای زاویه و فاصله بین حسگر‌ها را در الگوریتم کلونی مورچه به کار می‌گیرد. یک مورچه تعمیرکار در مسیرهای تصادفی برای شناسایی حسگر‌ها با سطح انرژی زیر یک آستانه مشخص فرستاده می‌شود. سپس مسیر ارتباطی براساس انرژی باقی‌مانده گره‌ها به‌روزرسانی می‌شود؛ به‌طوری‌که حالت بهینه خود را حفظ کند.

2-3- استفاده همزمان از ACO و گره چاهک متحرک

در کنار مراجع توصیف‌شده، به‌تازگی مطالعاتی نیز به استفاده همزمان از گره چاهک متحرک و الگوریتم ACO روی آورده‌اند؛ برای مثال، مؤلفان در [27] ابتدا از تئوری بازی به‌منظور تعیین نقاط ملاقات مناسب در شبکه حسگر بی‌سیم استفاده می‌کنند. به‌منظور تعیین بهترین نقاط ملاقات، تمامی حسگرها امکان شرکت در تئوری بازی را دارند. حسگری با بالاترین میزان بار تجمیع‌شده و انرژی باقی‌مانده، در فرایند تعیین نقاط ملاقات برنده می‌شود. انتخاب مؤثر این نقاط، گره چاهک را قادر می‌کند بدون طی مسافت‌های طولانی به تجمیع داده‌ حسگرها بپردازد. سپس با به‌کارگیری ACO، مسیر کارآمدی برای حرکت گره چاهک و تجمیع داده در شبکه‌ طراحی می‌شود. مرجع [28] استفاده از خوشه‌بندی و گره‌های چاهک متحرک را به‌عنوان روشی برای حل چالش‌های شبکه‌های حسگر بی‌سیم مطرح می‌کند. این مرجع ابتدا با استفاده از الگوریتم LEACH^[12] بهبودیافته، به خوشه­بندی و تعیین سرخوشه‌ها در شبکه می‌پردازد. سپس با استفاده از مسیریابی مبتنی بر ACO، مسیرهای مناسبی برای حرکت گره‌های چاهک در شبکه ارائه می‌دهد. در این راستا، خوشه‌ها در چندین دسته تقسیم‌بندی می‌شوند و هر دسته، به یک گره چاهک تخصیص می‌یابد. هر چاهک پس از تجمیع داده‌های سرخوشه‌های متناظرش به مکان اولیه خود برمی‌گردد.

مؤلفان در [29] با ارائه دو الگوریتم ابتکاری به‌دنبال حفظ تعادل بین تأخیر و مصرف انرژی در شبکه‌های حسگر بی‌سیم مجهز به گره چاهک متحرک هستند. برخلاف رویکرد این مقاله، آنها برای تجمیع داده‌های سنجش‌شده در شبکه پیشنهاد می‌کنند گره چاهک در نزدیکی همه گره‌های سرخوشه توقف کند. این در حالی است که کاهش تعداد نقاط توقف می‌تواند ضمن کاهش تأخیر شبکه، به کاهش پیچیدگی مسأله نیز منجر ‌شود. همچنین، آنها از ACO به‌منظور تعیین مسیر حرکت چاهک بهره می‌برند. این در حالی است که طرح پیشنهادی در این مقاله با در نظر گرفتن همزمان دو معیار انرژی و موقعیت نقاط توقف کاندید، از ACO برای مسیریابی و جمع‌آوری داده درون خوشه‌ها و برای تور چاهک از یک حرکت گلبرگ‌گونه ابتکاری بهره می‌گیرد. در [30]، با هدف کاهش اتلاف داده و بهبود طول عمر شبکه، از تعمیمی از الگوریتم ACO مبتنی بر گره چاهک متحرک استفاده می‌شود. بدین منظور، یک مسیر از پیش تعیین شده برای حرکت گره چاهک، طراحی و مسأله انتخاب نقاط توقف از میان حسگرها عنوان می‌شود. هدف اصلی، انتخاب دقیق نقاط توقف به صورتی است که با کاهش تعداد ارسال‌ها، میزان مصرف انرژی در شبکه کاهش یابد.

طرح پیشنهادی در [31]، الگوریتم مسیریابی کلونی مورچه‌ مبتنی بر چند گره چاهک را برای تجمیع مطمئن داده‌های یک شبکه حسگر بی‌سیم ارائه می‌دهد. از ویژگی‌های این طرح می‌توان به مقاوم‌بودن در برابر خطا و کارآمدی در انتقال داده قابل اعتماد در صورت مواجهه با یک مسیر معیوب اشاره کرد. نویسندگان در [32] ضمن اشاره به NP-hard بودن مسأله طراحی مسیر حرکت گره چاهک، استفاده از این گره را در شبکه روشی مؤثر برای افزایش اتصال شبکه بیان می‌کنند. آنها با در نظر گرفتن همزمان مسیریابی مبتنی بر خوشه و گره چاهک متحرک، یک مسیر کارآمد برای حرکت این گره با استفاده از الگوریتمACO  پیشنهاد می‌دهند. در این راستا، به‌منظور کاهش تأخیر و تعادل مصرف انرژی در شبکه، ابتدا سرخوشه‌های بهینه را انتخاب می‌کنند و سپس کوتاه‌ترین مسیر حرکت گره چاهک را ارائه می‌دهند.

3-  مدل شبکه و مفروضات

شبکه حسگر بی‌سیمی مشتمل بر گره همگن ثابت و یک گره چاهک متحرک را در نظر بگیرید. در این مقاله، فرض بر یک معماری دو سطحی برای شبکه است که در سطح اول، حسگرهای کاملاً مشابه به‌طور تصادفی در ناحیه مربعی به ضلع متر توزیع می‌‌شوند. این گره‌ها پس از خوشه‌بندی در قالب  خوشه، داده‌های سنجش‌شده خود را ازطریق یک درخت مسیریابی مناسب برای سرخوشه خود ارسال می‌کنند. سطح دوم شبکه مشتمل بر سرخوشه‌ها و گره چاهک است. شبکه توسط  دایره فرضی متحدالمرکزی افراز می‌شود که در فواصل مساوی  از هم قرار دارند. محل برخورد این دوایر با خطوط فرضی عبوری از مبدأ در زوایای  نقاط توقف مجاز گره چاهک را مشخص می‌کند. چاهک، حرکت خود را با سرعت  از مرکز شبکه آغاز می‌کند و با توقف در نقاط منتخب، داده‌های تجمیع‌شده در سرخوشه‌ها را دریافت می‌کند. شایان ذکر است چاهک، مجاز به پیمودن دو حرکت کمانی و خطی به‌ترتیب روی دوایر فرضی و خطوط فرضی مدنظر است.

برای روشن‌ترشدن مسأله، شکل 2، مثالی از حرکت چاهک در شبکه‌ای مشتمل بر سه دایره را به تصویر می‌کشد که خطوط فرضی آن در زوایای ^ᵒ180 ، ^ᵒ 90، ^ᵒ0 و ^ᵒ270 در نظر گرفته شده‌اند. هریک از نقاط 1 تا 12، محلی برای توقف چاهک محسوب می‌شوند؛ هرچند طبق مسیر، فقط نقاط خاکستری 11، 2، 9، 5 و 8 برای توقف این گره و جمع‌آوری داده انتخاب شده‌اند.

طول مسیر حرکت به‌عنوان عامل تعیین‌کننده در تأخیر شبکه لحاظ می‌شود. دو نقطه متوالی i و j را روی کمان یک دایره در نظر بگیرید. چاهک برای پیمودن مسیر کمانی بین این دو نقطه باید مسافتی به طول  را طی کند که شعاع دایره متناظر و  زاویه کمان متصل‌کننده دو نقطه i و j است. این در حالی است که اگر نقاط توقف متوالی روی خطوط فرضی واقع باشند، چاهک مسیر خطی به فاصله اقلیدسی دو گره را می‌پیماید. بدین ترتیب، کل مسافت طی‌شده توسط چاهک ( ) با جمع مسافت مربوط به هریک از حرکت‌های کمانی و خطی آن به دست می‌آید؛ بنابراین، برای تأخیر کل حرکت گره چاهک ( ) می‌توان نوشت:

شکل(2): مثالی از حرکت گره چاهک براساس مدل پیشنهادی

برای مثال، تأخیر چاهک در شکل 2 ناشی از 3 حرکت کمانی (2 و 3)، (9 و 10) و (8 و 5) و 5 حرکت خطی (11 و چاهک)، (3 و 11)، (10 و 2)، (9 و 5) و (چاهک و 8) است که با فرض  به‌صورت زیر محاسبه می‌شود:

گره‌های شبکه مجهز به آنتن‌های همه‌جهته هستند. براساس این، شبکه توسط گراف  مدل می‌شود که در آن مجموعه رئوس    شامل  حسگر و یک چاهک متحرک و مجموعه یال‌های  بیان‌کنندة پیوندهای بی‌سیم بین گره‌های شبکه‌اند. پیوند  بین دو گره  و  به این معنی است که دو حسگر در برد مخابراتی یکدیگر قرار دارند و می‌توانند به‌طور مستقیم تبادل داده کنند. همچنین، فرض بر آن است که از پروتکل IEEE802.15.4 برای زمان‌بندی در ارسال داده حسگرها بهره گرفته می‌شود.

در این مقاله، برای محاسبه میزان انرژی مصرفی گره‌ها از مدل معروف رادیویی مرتبه اول استفاده می‌شود [33]. براساس این مدل، انرژی لازم برای ارسال و دریافت داده به‌‌ترتیب از روابط 3 و 4 محاسبه می‌‌شوند:

که  بیان‌کنندة انرژی مصرفی برای ارسال بسته L بیتی روی پیوندی به طول d متر است و  انرژی برای دریافت یک بسته L بیتی را نشان می‌دهد. همچنین،  و  به‌ترتیب انرژی ارسال یا دریافت توسط مدارات الکتریکی و انرژی مصرفی تقویت‌کننده‌های انتقال‌اند.

تعامل مستقیم چاهک با حسگرها با کاهش مصرف انرژی آنها همراه است؛ اما به مسیرهای طولانی‌تر و تعداد نقطه توقف بیشتر برای چاهک منجر می‌شود؛ بنابراین، لازم است کنار مصرف انرژی، تعداد توقف چاهک نیز لحاظ شود. بدین منظور، از معیار «ناکارآمدی شبکه (NI)^[13]» استفاده می‌شود که به‌صورت ضرب کل مصرف انرژی در تعداد نقاط توقف گره چاهک تعریف شده و بیان‌کنندة مصالحه بین این دو عامل است:

که در آن،  و   به‌ترتیب کل انرژی مصرفی توسط گره‌ها و تعداد نقاط توقف گره چاهک‌اند. بدیهی است کوچک‌تربودن NI بیان‌کنندة عملکرد بهتر شبکه است.

• الگوریتم‌ ARPDA

در این بخش، الگوریتم ARPDA به‌منظور کاهش همزمان مصرف انرژی و تأخیر در شبکه‌های حسگر بی‌سیم مجهز به گره چاهک متحرک به‌طور جامع معرفی می‌شود. این الگوریتم‌ در سه فاز متوالی، در دو سطح شبکه اجرا می‌شود.

4-1- فاز اول: خوشه‌بندی و انتخاب سرخوشه

در فاز اول، حسگرها خوشه‌بندی و برای هر خوشه، یک سرخوشه مناسب انتخاب می‌شود. با هدف سادگی و تطابق مسأله با مدل رادیویی مرتبه اول، از روش K-means برای تشکیل خوشه‌های شبکه استفاده می‌شود؛ به‌طوری‌که مجموع فاصله حسگرها تا مرکز خوشه کمینه شود. بدین منظور، ابتدا N_c نقطه تصادفی به‌عنوان مراکز خوشه انتخاب می‌شوند. سپس تمامی حسگرها، فاصله اقلیدسی خود را تا این نقاط محاسبه می‌کنند. هر حسگر به خوشه‌ای می‌پیوندد که کوتاه‌ترین فاصله را تا مرکز مربوطه داشته باشد. با میانگین‌گیری روی فاصله بین نقاط متعلق به هر خوشه، برای هر خوشه، نقاط جدیدی به‌عنوان مرکز انتخاب می‌شوند. با تکرار این فرایند تا یکسان‌شدن مراکز خوشه‌ها در دو تکرار متوالی، خوشه‌بندی نهایی شبکه محقق خواهد شد. با توجه به عدم تحرک حسگرها، خوشه‌بندی شبکه ثابت است و صرفاً یک‌بار پس از چیدمان گره‌ها اجرا می‌شود. این در حالی است که نقش سرخوشه‌ در هر خوشه، دوره به دوره به‌صورت وفقی تغییر می‌کند تا علاوه بر متعادل‌شدن مصرف انرژی حسگرها، طول مسیر حرکت چاهک نیز حداقل شود.

با توجه به نقش خطیر سرخوشه در تجمیع داده‌ اعضای خود و ارسال نتیجه به گره چاهک، این گره نسبت به سایر حسگر‌های خوشه، انرژی بیشتری مصرف می‌کند. هرچه یک حسگر انرژی باقی‌مانده بیشتری داشته باشد کاندید شایسته‌تری برای ایفای نقش سرخوشه محسوب می‌شود؛ همچنین، بررسی تعداد نقاط توقف همسایگی در یک حسگر می‌تواند عامل مؤثری برای کاهش تأخیر ناشی از حرکت گره چاهک باشد؛ زیرا احتمال انتخاب نقاط توقف مشترک بین سرخوشه‌ها افزایش می‌یابد. این امر، به حذف بخش‌های غیرضروری مسیر منجر می‌شود و تأخیر حرکت چاهک کاهش می‌یابد. در هر خوشه s، گره‌ای به‌عنوان سرخوشه انتخاب می‌شود که:

 و به‌ترتیب انرژی باقی‌مانده و تعداد نقاط توقف پیرامون حسگر‌ n هستند. همچنین،  و  به‌ترتیب سرخوشه انتخاب‌شده و مجموعه اعضای خوشه s را نشان می‌دهند. گره‌ای نقش سرخوشه را بر عهده می‌گیرد که از انرژی باقی‌مانده بیشتری برخوردار باشد و تعداد نقاط توقف بیشتری در اطراف خود نسبت به سایر اعضا داشته باشد. بدیهی است با تغییر تدریجی انرژی گره‌ها در هر دوره، گره‌های متفاوتی نقش سرخوشه را بر عهده می‌گیرند.

4-2- فاز دوم: ارسال درون‌خوشه‌ای

با مشخص‌شدن خوشه‌ها‌ و سرخوشه‌ آنها، هر حسگر باید داده‌های خود را ازطریق یک درخت مسیریابی کارآمد به سرخوشه متناظر خود ارسال کند. بدین منظور، ما از یک الگوریتم کلونی مورچه اصلاح‌شده برای ساخت درخت مسیریابی و ارسال‌ داده‌های درون‌خوشه‌ای بهره می‌بریم.

ساخت درخت مدنظر از گره سرخوشه آغاز می‌شود و در هر گام، حسگرها به‌واسطه یک مسیر مناسب به درخت جاری اضافه می‌شوند. در ابتدا درخت فقط شامل گره سرخوشه است. معیار اولویت‌ بررسی حسگرها برای تعیین مسیر اتصال آنها به گره سرخوشه، فاصله است؛ به‌طوری‌که اولویت با حسگرهایی است که بیشترین فاصله را تا سرخوشه داشته باشند. فرض کنید حسگرn  به‌عنوان دورترین حسگر نسبت به سرخوشه قصد پیوستن به درخت مسیریابی را داشته باشد، براساس الگوریتم پیشنهادی، تعداد B مورچه را روی این حسگر قرار می‌دهیم. هر مورچه برای تعیین گام بعدی خود، از میان حسگر‌های همسایه، حسگری را انتخاب می‌کند و این فرایند را تا اتصال مسیر ایجادشده به سرخوشه یا درخت جاری ادامه می‌دهد. در هر مرحله، با استفاده از تابع احتمال  و الگوریتم چرخ رولت^[14] [34]، احتمال حرکت kامین مورچه از حسگرn  به حسگر همسایه m، در tامین تکرار محاسبه می‌شود:

که در آن،  و به‌ترتیب میزان فرومون موجود روی پیوند حسگر n به m در تکرار t و فاصله بین آن دو حسگر هستند.  و  نیز دو ثابت کنترل‌کننده وزن عامل مربوطه در تابع احتمال‌اند. همچنین،  شامل حسگر‌هایی است که توسط مورچه kام ملاقات نشده‌اند. طبیعی است که احتمال انتخاب حسگری که در همسایگی حسگرn  نباشد یا در مسیر جاری انتخاب شده باشد، برابر صفر است. این مهم، از ایجاد دور در درخت مسیریابی جلوگیری می‌کند. دو معیار اصلی استفاده‌شده در تابع احتمال فوق، یعنی انرژی باقی‌مانده حسگرها و فاصله‌های بین آنها، شانس انتخاب حسگری با بیشترین انرژی و کمترین فاصله تا حسگر فعلی و تشکیل مسیر ازطریق آن حسگر را افزایش می‌دهد. این مسأله ضمن توازن بهتر انرژی بین حسگرها، به کاهش مصرف انرژی منجر خواهد شد. از طرف دیگر، این تابع احتمال با میزان فرومون اضافه‌شده بر مسیر‌های عبوری توسط مورچه‌ها رابطه مستقیم دارد؛ بنابراین، هرچه میزان فرومون موجود روی یک پیوند بیشتر باشد، آن پیوند ازنظر مورچه‌ها محبوب‌تر شمرده ‌‌می‌شود و احتمال انتخاب آن توسط سایر مورچه‌ها افزایش می‌یابد. فرومون اضافه‌شده روی پیوند دو حسگر n  و m هنگام عبور هر مورچه از آن برابر است با:

که در آن، نشان‌دهندة حداکثر تعداد گام‌های مجاز برای مورچه‌ها است و  و  به‌ترتیب بیان‌کنندة تعداد گام‌ها و میانگین انرژی حسگر‌هایی‌اند که kامین مورچه برای رسیدن به مقصد، از آنها عبور می‌کند. همچنین، یک مقدار ثابت است. براساس این، در هر تکرار، میزان فرومون موجود روی هر پیوند به‌روزرسانی می‌شود [23]:

که در آن، ثابت تبخیر عدد ثابتی بین صفر و یک است.

فرایند توصیف‌شده برای تمامی مورچه‌ها تا همگرایی کامل آن در تعداد تکرار مشخص ( ) تکرار می‌شود. در فرایند همگرایی، با مقایسه مسیرهای ایجادشده از حسگر n تا سرخوشه مربوطه ( )، مسیری که بتواند بهتر از سایر مسیرها معیار  را برآورده کند، به‌عنوان مسیر بهینه به درخت جاری افزوده می‌شود. سپس دورترین حسگر بعدی برای تعیین مسیر آن تا سرخوشه متناظرش انتخاب خواهد شد.

شکل 3، مثالی از خوشه‌بندی و تشکیل درخت مسیریابی مبتنی بر الگوریتم ACO در هر خوشه از شبکه را نشان می‌دهد؛ برای نمونه، خوشه شماره 6 را در نظر بگیرید که در آن، ابتدا مسیر حسگر x به‌عنوان دورترین حسگر تا سرخوشه تعیین می‌شود. این حسگر، 6 همسایه دارد که با استفاده از تابع احتمال توصیف‌شده، احتمال انتخاب هریک از همسایگان محاسبه می‌شود. استفاده از چرخ رولت منجر می‌شود هر مورچه، همسایه متفاوت و درنتیجه، مسیر متفاوت را انتخاب کند. درنهایت، با همگرایی الگوریتم و انتخاب بهترین مسیر که با رنگ قرمز مشخص شده است، این حسگر به سرخوشه 6 متصل می‌شود. این فرایند تا تشکیل کامل درخت مسیریابی برای سایر حسگرهای پوشش داده نشده خوشه، ادامه می‌یابد.

پس از تشکیل درخت، گره‌های والد میانی موظف به تجمیع بسته‌های داده فرزندان خود هستند. در شکل 3، شماره نوشته‌شده کنار هر پیوند، تعداد بسته‌های ارسالی توسط آن پیوند را نشان می‌دهد. هر حسگر، داده دریافتی از فرزندانش را با داده خود، ترکیب و مجموع آنها را برای گره والد ارسال می‌کند؛ برای مثال، حسگرهای A، B و D هر کدام یک بسته داده به والد خود ارسال می‌کنند. حسگر C، بسته‌های دریافتی از A و B را با داده‌ خود، ترکیب و سه بسته به گره E منتقل می‌کند. درنهایت، 5 بسته داده ازطریق حسگر E به سرخوشه‌ متناظر ارسال می‌شود.

4-3- فاز سوم: تعیین مسیر حرکت گره چاهک

پس از تجمیع داده در هر خوشه توسط سرخوشه‌ مربوطه، این گره نتیجه را در قالب یک ارتباط تک‌پرشی برای گره چاهک ارسال می‌کند. همان‌طور که در بخش 3 اشاره شد، شبکه مدنظر به‌واسطه دایره‌های متحدالمرکز فرضی با فواصل یکسان و خطوط فرضی افراز می‌شود؛ به‌طوری‌که محل تلاقی این دوایر و خطوط، نقاط توقف مجاز برای گره چاهک را تعیین می‌کند. با این حال، لزومی به توقف گره چاهک در همه این نقاط نیست و لازم است ضمن انتخاب نقاط توقف کارآمد، مسیر مناسبی برای حرکت این گره تعیین شود؛ برای مثال، اگر در همسایگی یکی از نقاط توقف، سرخوشه‌ای قرار نداشته باشد، طبیعی است توقف گره چاهک در آن نقطه علاوه بر اینکه منفعتی ندارد، به افزایش پیچیدگی مسأله منجر می‌شود. الگوریتم ARPDA با نگاه همزمان به دو مسأله انرژی و تأخیر، در دو مرحله، نقاط توقف مناسب را انتخاب و مسیر حرکت گره چاهک را طراحی می‌کند. در مرحله اول، تمامی نقاط منتخب برای توقف گره چاهک تعیین می‌شوند. سپس در مرحله دوم، مسیر حرکت گره چاهک طراحی می‌شود. برای روشن‌شدن موضوع، عملکرد الگوریتم پیشنهادی را به‌همراه یک مثال جامع در شکل 4 تشریح می‌کنیم. شکل 4-الف، شبکه‌ای متشکل از 5 دایره متحدالمرکز را نشان می‌دهد که خطوط فرضی آن در زوایایی به فاصله عبور می‌کنند. در چنین شبکه‌ای، 40 نقطه توقف مجاز برای گره چاهک در نظر گرفته می‌شود.

مرحله 1: تشکیل مجموعه نقاط توقف منتخب

 ابتدا با تعیین مجموعه نقاط توقف منتخب، نقاط توقف متناظر با هر سرخوشه مشخص می‌شوند. در هر گام، از سرخوشه‌هایی که نقطه توقف مربوط به آنها تعیین شده باشد، با عنوان سرخوشه‌های «پوشش داده شده» یاد می‌شود. گره چاهک، حرکت خود را از مرکز آغاز می‌کند و با توقف در نقاط منتخب به تجمیع داده سرخوشه‌ها می‌پردازد. قبل از شروع حرکت گره چاهک، سرخوشه‌هایی که در برد مخابراتی این گره قرار دارند، داده‌ خود را در قالب یک ارسال تک‌پرشی به چاهک منتقل می‌کنند؛ برای مثال، در شکل 4، سرخوشه‌های 1، 3، 4، 17 و 25 داده‌ خود را قبل از شروع حرکت چاهک، برای این گره ارسال می‌کنند. این مسأله با حذف بخش‌های اضافی مسیر برای رسیدن به این سرخوشه‌ها، تأخیر را به حداقل می‌رساند.

در گام نخست، نزدیک‌ترین سرخوشه پوشش داده نشده به چاهک تعیین تکلیف می‌شود. با بررسی نقاط توقف مجازی که در برد مخابراتی این سرخوشه قرار دارند، نقطه‌ای به‌عنوان نقطه توقف انتخابی جدید برگزیده می‌شود که بتواند بیشترین سرخوشه پوشش داده نشده را پوشش دهد. در این صورت، چاهک با توقف در این نقطه می‌تواند داده تعداد سرخوشه بیشتری را جمع‌آوری کند؛ بنابراین، با کوتاه‌ترشدن مسیر حرکت چاهک، تأخیر در شبکه کاهش می‌یابد. اگر چند نقطه توقف تعداد برابری سرخوشه جدید را پوشش دهند، نقطه‌ای انتخاب می‌شود که مجموع فاصله سرخوشه‌ها تا آن نقطه کمتر باشد. طبق مدل رادیویی مرتبه اول، سرخوشه‌ها انرژی کمتری برای ارسال داده‌ خود به چاهک مصرف می‌کنند. براساس استراتژی فوق در شکل 4، ابتدا لازم است نقطه توقف مناسبی برای سرخوشه 7 (یعنی نقطه 40) تعیین شود. بدیهی است تمام سرخوشه‌های پوشش داده نشده موجود در برد مخابراتی نقطه انتخابی، با توقف گره چاهک در این نقطه می‌توانند داده‌های خود را ارسال کنند. این سرخوشه‌ها نیز به مجموعه سرخوشه‌های پوشش داده شده ملحق می‌شوند؛ به این ترتیب، این نقطه به‌عنوان اولین نقطه در مجموعه نقاط توقف منتخب قرار می‌گیرد. با انتخاب یک نقطه توقف، تمامی نقاط توقف دیگر در راستای خط فرضی عبوری از آن نقطه بررسی می‌شوند. اگر نقطه‌ای در این راستا بتواند سرخوشه جدیدی را پوشش دهد، به مجموعه نقاط منتخب و سرخوشه‌های متناظر با آن نیز به سرخوشه‌های پوشش داده شده اضافه می‌شوند. دو نقطه توقف 16 و 24، در راستای نقطه توقف 40 هستند که به‌طور مشترک 5 سرخوشه 6، 13، 19، 20 و 27 را پوشش می‌دهند (شکل 4-ب). با مقایسه مجموع فاصله این سرخوشه‌ها تا هریک از نقاط توقف 16 و 24، نقطه 24 انتخاب و به مجموعه نقاط توقف منتخب اضافه می‌شود. در گام بعدی، نزدیک‌ترین سرخوشه پوشش داده نشده به نقطه توقف منتخب فعلی (یعنی سرخوشه 15) برگزیده می‌شود و مجدداً تمامی نقاط توقف پیرامون آن سنجیده می‌شوند. براساس معیار توصیف‌شده، نقطه 23 نسبت به سایر نقاط، سرخوشه بیشتری را دربرمی‌گیرد؛ بنابراین، به‌عنوان سومین توقف تعیین می‌شود. با تکرار فرایند فوق، نقاط 40 (با سرخوشه 7)، 24 (با سرخوشه‌های 6، 13، 19، 20 و 27)، 23 (با سرخوشه‌های 5، 12 و 15)، 6 (با سرخوشه‌های 24، 31 و 32)، 13 (با سرخوشه‌های 10، 11، 22 و 23)، 4 (با سرخوشه) ، 11 (با سرخوشه‌های 14 و 18)، 27 (با سرخوشه‌های 21، 29، 30 و 34)، 10 (با سرخوشه‌های 26، 28 و 33) و 9 (با سرخوشه‌های 8 و 16) برای توقف چاهک انتخاب می‌شوند.

شکل(3): مثالی از تشکیل درخت مسیریابی درون‌خوشه‌ای مبتنی بر الگوریتمACO  پیشنهادی

شکل (4): مسیر حرکت گره چاهک در الگوریتم ARPDA

مرحله 2: طراحی مسیر حرکت گره چاهک

حال، لازم است مسیر حرکت گره چاهک برای توقف در این نقاط و دریافت داده تجمیع‌شده از سرخوشه‌های متناظر مشخص شود. مسیر حرکت گره به دو دسته حرکت خطی و حرکت کمانی تقسیم‌بندی می‌شود؛ در دسته اول، این گره روی خطوط فرضی موجود از سمت دایره کوچک‌تر به سمت دایره بزرگ‌تر (جهت بیرونی) یا برعکس (جهت درونی) جابه‌جا می‌شود. حرکت گره چاهک از مرکز شبکه به‌سمت اولین نقطه منتخب به‌صورت حرکت بیرونی خواهد بود. در ادامه، حرکت این گره روی کلیه خطوط فرضی، یکی در میان، به‌صورت حرکت درونی و بیرونی تنظیم می‌شود؛ برای مثال، حرکت روی خطوط فرضی در زوایای 315، 270، 225، 180، 135، 90، 45 و 0 درجه به‌ترتیب بیرونی، درونی، بیرونی، درونی، بیرونی، درونی، بیرونی و درونی است (شکل 4-ج). دسته دوم، حرکت‌های کمانی ساعت‌گرد یا پادساعت‌گرد هستند. تعیین جهت این نوع حرکت به اولین نقاط منتخبی وابسته است که در دو زاویه متفاوت واقع شده‌اند. در صورتی که زاویه‌ اولین و دومین نقطه توقف منتخب برابر با  باشد این حرکت، ساعت‌گرد و در غیر این ‌صورت، حرکت کمانی به پادساعت‌گرد تغییر خواهد کرد. مطابق شکل 4، دو نقطه 40 و 24 نمی‌توانند تعیین‌کنندة این حرکت باشند؛ زیرا در یک زاویه مشترک ^ᵒ135 قرار دارند. پس باید دو نقطه منتخب بعدی، یعنی 24 و 23 را بررسی کنیم که به‌ترتیب در ^ᵒ135 و^ᵒ270 قرار دارند. از آنجا ‌که تفاضل این دو زاویه  است، حرکت ساعت‌گرد اتخاذ می‌شود.

بدین ترتیب، با تعیین نقاط توقف و مسیر حرکت چاهک، فرایند جمع‌آوری داده توسط این گره شروع می‌شود. چاهک برای توقف در نقاط 40 و 24، باید مسیری خطی را در جهت بیرونی طی کند. سومین نقطه منتخب روی دایره مشترک با نقطه توقف 24 قرار دارد. پس چاهک همان مسیر کمانی را در جهت ساعت‌گرد برای رسیدن به این نقطه می‌پیماید. با توجه به اینکه نقاط 23 و 6 روی دایره‌های متفاوت قرار دارند، باید چاهک ازطریق مسیر خطی به دایره مدنظر برسد. مسیر خطی در راستای نقطه 6، در جهت بیرونی تنظیم شده است. پس ابتدا باید گره چاهک با طی مسیر کمانی بین نقاط 23 و 22 در مسیر خطی نقطه منتخب 6 قرار بگیرد و سپس در جهت بیرونی به این نقطه برسد. این در حالی است که سمت مسیر خطی نقطه منتخب 13 درونی است. مطابق حالت قبل، به‌علت تفاوت دایره‌های دو نقطه 6 و 13 و جهت درونی نقطه 13، چاهک با پیمودن کمان بزرگ‌ترین دایره به نقطه 5 می‌رسد و سپس در نقطه 13 به جمع‌آوری داده‌ می‌پردازد. نقطه 9 آخرین نقطه‌ای‌‌ است که چاهک روی آن توقف می‌کند؛ درنهایت، ازطریق مسیر خطی درونی به مرکز شبکه بازمی‌گردد. حرکت گلبرگ‌گونه چاهک، وجه تسمیه الگوریتم پیشنهادی است.

5-  نتایج شبیه‌سازی

در این بخش، الگوریتم پیشنهادی‌ در مقایسه با الگوریتم‌های EDT [9]، ^[xv]EGRPM [11] و ^[xvi]EMPAR [33] و از منظر ناکارآمدی شبکه، مصرف انرژی و مسافت حرکت گره چاهک ارزیابی می‌شود. به‌طور پیش‌فرض، قطر شبکه، برد مخابراتی، زاویه بین خطوط فرضی و تعداد دایره‌ها به‌ترتیب 500 متر، 50 متر، 45 درجه و 5 در نظر گرفته می‌شوند. انرژی اولیه حسگرها 2J، ،  و طول بسته‌های داده برابر با 1024 بیت فرض می‌شوند. همچنین، پارامترهای B، ، ، ، ،  و   در الگوریتم ACO به‌ترتیب برابر 50، 01/0، 1، 5/1، 0001/0 و 100 انتخاب می‌شوند. حسگرها دوره به دوره کمیتی در محیط را اندازه‌گیری می‌کنند و آن را به سرخوشه خود تحویل می‌دهند. این گره داده تجمیع‌شده را توسط یک ارسال تک‌پرشی به چاهک منتقل می‌کند. سرعت چاهک  فرض می‌شود؛ ازاین‌رو، مسافت طی‌شده توسط گره چاهک با تأخیر ناشی از حرکت آن برابر است. با توجه به چیدمان تصادفی حسگرها، هر سناریو حداقل 30 مرتبه تکرار و میانگین نتایج ارائه می‌شود.

سناریو 1: در اولین سناریو، با فرض 400 حسگر، 30 خوشه و برد مخابراتی 50 متر، ابعاد شبکه را به‌طور تدریجی از 100 تا 700 متر تغییر می‌دهیم. شکل‌های 5 و 6، به‌ترتیب ناکارآمدی شبکه و مسافت طی‌شده گره چاهک (تأخیر) را برای دو الگوریتم  ARPDAو EDT به‌ازای ابعاد مختلفی از شبکه مقایسه می‌کنند. براساس مدل رادیویی مرتبه اول، مصرف انرژی به مربع فاصله بین دو گره حسگر وابسته است؛ بنابراین، طبیعی است با افزایش ابعاد شبکه و درنتیجه، افزایش فاصله بین حسگرها، میزان مصرف انرژی افزایش یابد. این در حالی است که به‌دلیل فرض ثابت‌ماندن برد مخابراتی، میزان اتصالات در گراف شبکه کاهش می‌یابد که عاملی بر افزایش تعداد نقاط توقف گره چاهک متحرک است؛ بنابراین، همان‌گونه که در شکل 5 مشخص است، این روند ناکارآمدی شبکه را افزایش می‌دهد؛ اما مهم این است که روش پیشنهادی در مقایسه با EDT توانسته است ناکارآمدی شبکه را به‌طور چشمگیری کاهش دهد. این مهم، در شبکه‌های مقیاس بزرگ بهتر دیده می‌شود. درواقع، ARPDA با به‌کارگیری از یک ساختار دو سطحی مناسب و با خوشه‌بندی کارآمد حسگرها و تعیین مناسب سرخوشه‌ها در هر دوره، تعداد توقف گره چاهک را به‌شدت کاهش می‌دهد.

مطابق شکل‌ 6، با افزایش ابعاد شبکه، مسافت طی‌شده گره چاهک (تأخیر) در هر دو الگوریتم‌ افزایش می‌یابد. با این حال، الگوریتم ARPDA تأخیر کمتری در مقایسه با EDT دارد. دلیل این مسأله، استراتژی روش پیشنهادی در تجمیع داده سرخوشه‌های مختلف با طی‌کردن حداقل مسافت ممکن است. ملاحظات توصیف‌شده در مرحله 2 الگوریتم پیشنهادی و استفاده از دوایر و خطوط فرضی علاوه بر اینکه به کاهش نقاط توقف منجر شده است، مسیر چاهک را نیز کوتاه می‌کند.

سناریو 2: در این سناریو، با فرض شبکه‌ای به قطر 500 متر و 30 خوشه، تأثیر تعداد حسگرهای شبکه بر عملکرد دو الگوریتم‌ ARPDA و EDT را ‌بررسی می‌کنیم. با افزایش حسگرها، بسته‌های ارسالی و درنتیجه، میزان مصرف انرژی در شبکه افزایش می‌یابد. ضمن اینکه این روند با افزایش تعداد نقاط توقف چاهک نیز همراه خواهد بود؛ بنابراین، همان‌طور که در شکل 7 مشاهده می‌شود، با افزایش حسگرها، ناکارآمدی شبکه در هر دو الگوریتم افزایش می‌یابد. این در حالی است که به‌ازای تعداد مختلف حسگرها نیز روش پیشنهادی از ناکارآمدی شبکه پایین‌تری برخوردار است. نکته قابل تأمل دیگر این است که مطابق شکل‌ 8، در الگوریتم پیشنهادی، افزایش تعداد حسگرها تغییر محسوسی در تأخیر ناشی از حرکت چاهک ایجاد نمی‌کند؛ اما این افزایش، به بالارفتن چشمگیر تأخیر الگوریتم EDT منجر می‌شود. در الگوریتم EDT، تعیین نقاط توقف متناسب با تعداد حسگرها است؛ درحالی‌که در ARPDA، چاهک به‌جای تعامل مستقیم با حسگرها فقط با سرخوشه‌های شبکه در ارتباط است. به‌دلیل رویکرد خوشه‌بندی، افزایش حسگرها تأثیری بر تعداد خوشه‌ها ندارد و تأخیر شبکه ثابت می‌ماند.

شکل(5): مقایسه ناکارآمدی شبکه در‌ARPDA  و EDT با تغییر ابعاد شبکه

شکل(6): مقایسه مسافت طی‌شده توسط گره چاهک در‌ARPDA  و EDT با تغییر ابعاد شبکه

سناریو 3: در این سناریو، عملکرد الگوریتم ARPDA از منظر مصرف انرژی و مسافت طی‌شده گره چاهک، به‌ازای 10، 20، 30 و 40 خوشه بررسی می‌شود. تعداد حسگرها 200 و اندازه شبکه 500 متر فرض می‌شوند. همان‌طور که در شکل 9 مشاهده می‌شود، با افزایش تعداد خوشه‌ها در شبکه، انرژی مصرفی کاهش می‌یابد؛ اما مسافت طی‌شده گره چاهک افزایش می‌یابد. درواقع، ما شاهد یک مصالحه بین مصرف انرژی و تأخیر گره چاهک هستیم. با افزایش تعداد خوشه‌ها، اندازه آنها کوچک‌تر می‌شود و تعداد کمتری حسگر را دربرمی‌گیرند. این مسأله با کاهش تعداد بسته‌های ارسالی به سرخوشه و کاهش مصرف انرژی همراه است. این در حالی است که با افزایش تعداد سرخوشه‌ها، چاهک مجبور به پیمودن مسیرهای طولانی‌تری است و تأخیر شبکه تشدید می‌شود. واضح است برای شبکه و تعداد حسگر مفروض، تعداد 20 خوشه توانسته‌اند تعادلی بین مصرف انرژی و تأخیر شبکه ایجاد کنند.

سناریو 4: درنهایت، انرژی مصرفی ARPDA در مقایسه با الگوریتم‌های EGRPM [11] و EMPAR [33] به‌ازای 9 تا 36 سرخوشه ارزیابی می‌شود. بدین منظور، 400 حسگر با برد مخابراتی 50 متر در محیطی با ابعاد 500×500 مترمربع توزیع می‌شود. مطابق شکل 10، افزایش تعداد سرخوشه‌ها، انرژی مصرفی در شبکه را کاهش می‌دهد؛ زیرا روش‌های خوشه‌بندی با کاهش فاصله ارتباطی و تعداد بسته‌های ارسالی در سطح خوشه‌ها، به کاهش انرژی مصرفی در شبکه منجر خواهند شد. براساس مدل رادیویی مرتبه اول، هرچه فاصله ارتباطی بیشتر باشد، مصرف انرژی گره‌ها نیز بیشتر می‌شود. نکته قابل تأمل دیگر این است که انرژی مصرفی در ARPDA، به‌مراتب کمتر از دو الگوریتم EGRPM و EMPAR است. دلیل این امر، استفاده از چاهک متحرک، انتخاب کارآمد نقاط توقف و مسیریابی درون‌خوشه‌ای مبتنی بر ACO در ARPDA است. این در حالی است که در الگوریتم EMPAR، چاهک‌ها ثابت بوده‌اند و سرخوشه‌ها داده‌های خود را ازطریق ارسالات چندپرشی به هریک از گره‌های چاهک می‌فرستند. از طرف دیگر، EGRPM [11] با انتخاب تعداد محدودی نقطه توقف، از مسیر‌های چندپرشی و تک‌پرشی برای ارسال داده‌های سرخوشه به گره‌های چاهک استفاده می‌کند؛ به‌طوری‌که سرخوشه‌های دورتر، داده‌ خود را ازطریق سرخوشه‌های نزدیک به نقاط توقف برای گره چاهک ارسال می‌کنند و سرخوشه‌های نزدیک به نقاط توقف، داده خود را با ارسال تک‌پرشی برای چاهک می‌فرستند. همین امر، به مصرف انرژی بیشتر نسبت به الگوریتم ARPDA منجر می‌شود. شایان ذکر است این روش به‌‌واسطه بهره‌گیری از چاهک‌های متحرک، میزان انرژی مصرفی کمتری در مقایسه با الگوریتم EMPAR نشان می‌دهد.

6-  نتیجه‌گیری

در این مقاله، الگوریتم جدیدی با عنوان ARPDA پیشنهاد شد که با بهره‌گیری از یک معماری دو سطحی به جمع‌آوری گلبرگ‌گونه داده در شبکه‌های حسگر بی‌سیم می‌پردازد. در سطح اول، گره‌های حسگر به تعدادی خوشه افراز شده‌اند و برای هریک، سرخوشه مناسبی انتخاب می‌شود. در تعیین سرخوشه‌ها، علاوه بر انرژی باقی‌مانده حسگرها، مکان‌های احتمالی توقف چاهک نیز در نظر گرفته می‌شوند. گره‌های حسگر داده‌های خود را ازطریق یک درخت مسیریابی مبتنی بر ACO به سرخوشه‌ منتقل می‌کنند. در سطح دوم، با توجه به موقعیت سرخوشه‌ها، جهت و مسیر حرکت چاهک تعیین می‌شود. گره چاهک با حرکت در شبکه و توقف در نقاط منتخب، داده‌های بافرشده در سرخوشه‌ها را جمع‌آوری می‌کند.

شکل(7): مقایسه ناکارآمدی شبکه در‌ARPDA  و EDT با تغییر تعداد حسگرها

 شکل(8): مقایسه مسافت طی‌شده توسط گره چاهک در‌ARPDA  و EDT با تغییر تعداد حسگرها

شکل(9): اثر تعداد خوشه‌ها بر انرژی مصرفی و مسافت طی‌شده توسط گره چاهک در ARPDA

شکل (10): مقایسه انرژی مصرفی ARPDA،  EGRPM و EMPAR با تغییر تعداد سرخوشه‌ها

نتایج حاصل از شبیه‌سازی‌ بیان‌کنندة یک مصالحه بین میزان مصرف انرژی و تأخیر ناشی از حرکت چاهک‌اند. با این حال، روش پیشنهادی به‌خوبی توانسته است با کنترل این مصالحه در مقایسه با دیگر روش مشابه عملکرد بهتری از خود نشان دهد.

[1] تاریخ ارسال مقاله: 10/05/1400

تاریخ پذیرش مقاله: 30/11/1401

نام نویسندۀ مسئول: آوید آوخ

نشانی نویسندۀ مسئول: ایران، نجف آباد، دانشگاه آزاد اسلامی، واحد نجف آباد، دانشکده مهندسی برق

[1] Wireless Sensor Networks

[2] Polling points

[3] Cluster Head

[4] Ant Colony Optimization algorithm

[5] ACO-based Routing and Petal-shaped Data Aggregation

[6] Rendezvous points

[7] Travel Salesman Problem

[8] Particle Swarm Optimization Based Selection

[9] Energy Aware Ant Colony Algorithm

[10] Pheromone

[11] Power Efficient Gathering in Sensor Information Systems

[12] Low-energy adaptive clustering hierarchy 

[13] Network Inefficiency

[14] Roulette wheel

15 Energy Efficient Geographic Routing Protocol based on Mobile Sink

16 Multi-sink Placement and Anycast Routing