چكيده

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

كلمات كليدي

الگوريتم، شبکه‌های حسگر، مسيريابی، داده ساختارهای جنبشی، کوچکترين زير درخت فراگير محلی

Kinetic Data Structures for Routing Problem in Mobile Sensor Networks

Kamyar Rafati, Naeem Esfahani, Mohammad Ghodsi

Abstract

“Sensor networks” is an important topic in computer science and algorithm design. These networks are constructed from a set of independent mobile units with limited power and process capability. These units communicate and gather information using radio transmitters. The problem of routing in these networks with minimum power consumption is a NP-hard problem. Therefore, many researches use approximation algorithms for this problem. Most of the proposed models work with fixed sensors. In this paper, we propose an algorithm for routing in mobile sensor networks. According to the inherent kinetic structure of such networks, the use of a kinetic data structure which efficiently maintains minimum spanning tree (MST) is useful. In this paper, we present such structure for our problem and show that this method reduces the time complexity of routing in sensor networks.

Keywords

Algorithm, Sensor Networks, Routing, Kinetic Data Structures, Minimum Spanning Trees