In this paper, we study the coverage problem for hybrid networks which comprise both static and mobile sensors. We consider mobile sensors with limited mobility, i.e., they can move only once over a short distance. Such mobiles are simple and cheap compared to sophisticated mobile robots. In conventional static sensor networks, for a random deployment, the sensor density should increase asO(log L + k log log L) to provide k-coverage in a network with a size of L. As an alternative, an all mobile sensor network can provide k-coverage over the field with a constant density of O(k), independent of network size L. We show that the maximum distance that any mobile sensor will have to move is O(1 over √k log ^{3 over 4} (kL)). We then propose a hybrid network structure, comprising static sensors and a small fraction of O(1 over √(k)) of mobile sensors. For this network structure, we prove that k-coverage is achievable with a constant sensor density of O(k), independent of network size L. Furthermore, for this hybrid structure, we prove that the maximum distance which any mobile sensor has to move is bounded as O(log^{3 over 4} L). We then propose a distributed relocation algorithm, where each mobile sensor only requires local information in order to optimally relocate itself and characterize the algorithm's computational complexity and message overhead. Finally, we verify our analysis via extensive numerical evaluations

چکیده

ما در این مقاله، مشکل پوشش در شبکه­ های ترکیبی که از حسگرهای ثابت و متحرک تشکیل شده ­اند، بررسی می ­کنیم. ما حسگرهای متحرک با تحرک کم را مد نظر قرار می­ دهیم که فقط می ­توانند یک بار در فاصله­ ی کم جا به ­جا شوند. اینگونه حسگرها در مقایسه با ربات­ های متحرک و پیچیده، ساده­ و کم هزینه اند. در شبکه­ های معمولی حسگر ثابت، در استقرار تصادفی، تراکم حسگر باید با مرتبه O(log L + klog log L) افزایش یابد تا در شبکه­ ای با اندازه L، پوشش-k ایجاد شود. در روش جایگزین، تمام شبکه حسگر موبایل می ­تواند روی یک دامنه با تراکم ثابت O(k)، مستقل از اندازه شبکه (L)، پوشش-k ایجاد کند. ما نشان می ­دهیم حداکثر فاصله­ ای که هر حسگر متحرک باید حرکت کند O(k^-1/2log^3/4(kL) است. سپس یک ساختار ترکیبی شبکه ارائه می­ کنیم که از حسگرهای ثابت و تعداد کمی حسگر متحرک (O(k^-1/2)) تشکیل شده است. ما برای این ساختار شبکه ثابت می­ کنیم که با تراکم حسگر ثابت O(k)، و مستقل از اندازه شبکه (L)، می­ توان به پوشش-k دست یافت. علاوه­ بر این، ما برای این ساختار ترکیبی اثبات می­ کنیم که حداکثر فاصله ­ای که هر حسگر متحرک باید حرکت کند در حد  است. سپس یک الگوریتم جابجایی توزیع شده ارائه می ­کنیم که در آن، هر حسگر متحرک برای جابجایی بهینه خود، فقط به اطلاعات محلی نیاز دارد و پیچیدگی محاسباتی و سربار پیام الگوریتم را مشخص می­ کنیم. در نهایت، تحلیل خود را از طریق ارزیابی ­های عددی گسترده، بررسی می ­کنیم.

1-مقدمه

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