سولماز محمدی - دانشجوی کارشناسی ارشد، سازمان پژوهشهای علمی و صنعتی ایران-پژوهشکده برق و فناوری اطلاعات،
غلامرضا فراهانی - استادیار، سازمان پژوهشهای علمی و صنعتی ایران-پژوهشکده برق و فناوری اطلاعات

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

شبکه های حسگر بی سیم، چندجمله ای-زمان غیرقطعی سخت1 ، الگوریتم ها فراابتکاری، گره رله