الگوریتم های خوشه بندی کارآمد با تعادل بار برای شبکه حسگر بی سیم
چکیده
شبکه های حسگر بی سیم در سال های اخیر به دلیل کاربردهای بالقوه شان در ایجاد ارتباطات پویا برای عملیات اورژانس/ نجات، تلاش های امداد رسانی و شبکه های نظامی مورد توجه قرار گرفته اند. این مقاله، مسئله گروه بندی گره های حسگر را در خوشه ها برای افزایش مقیاس پذیری کلی شبکه مورد بررسی قرار می دهد. مجموعه ای از گره-ها موسوم به گره دروازه، به عنوان سرخوشه برای هر خوشه عمل می کنند و هدف این است که تعادل بار را در میان این دروازه ها برقرار کنیم. خوشه بندی با تعادل بار باعث افزایش ثبات سیستم و بهبود برقراری ارتباط بین گره های مختلف در شبکه می شود. مسئله ای که در این مقاله مطرح شده است را مسئله خوشه بندی با تعادل بار (LBCP ) می نامیم. برای اولین بار نشان می دهیم که حالتی خاص از LBCP (که در آن بار ترافیک ایجاد شده توسط تمام گره های حسگر یکسان است) در زمان چندجمله ای به طور مطلوب قابل حل است. پس از آن ثابت می-کنیم که حالت کلی LBCP، NP-سخت است. سپس یک الگوریتم تقریبی 3/2 کارآمد برای این مسئله پیشنهاد شد. الزویر 2007، کلیه حقوق محفوظ است.
1. مقدمه
در دسترس بودن پردازنده های جاسازی شده، رادیو ها، حسگرها و عملگرهای ارزان قیمت، کم قدرت و کوچک که اغلب در یک تراشه یکپارچه شده اند، منجر به استفاده از ارتباطات بی سیم و محاسبات برای برقراری ارتباط با دنیای فیزیکی در برنامه های کاربردی می شوند، نظیر برنامه های امنیتی و نظارتی، کلاس های هوشمند، نظارت بر زیستگاه های طبیعی و اکوسیستم ها و نظارت های پزشکی. این سیستم ها، اغلب شبکه های حسگر بی سیم نامیده می شوند که کاملاً متمایز با سیستم های شبکه شده و جاسازی شده کنونی هستند. آن ها مقیاس بزرگ و ماهیت توزیع شده سیستم های شبکه شده مانند اینترنت با محدودیت های شدید انرژی و ماهیت فیزیکی سیستم های کنترلی جاسازی شده را ترکیب می کنند.
8. نتیجه گیری
در این مقاله، مسئله ای را مطرح کردیم که در طراحی شبکه های حسگر بی سیم مبتنی بر خوشه مطرح است. به ویژه، مسئله اختصاص حسگرها به دروازه ها در شبکه حسگر بی سیم را با هدف توزیع بار ترافیکی در میان دروازه ها بررسی کردیم تا اطمینان حاصل شود که هیچ دروازه ای بیش از حد نباشد. نشان دادیم که این مسئله در زمان چندجمله ای به طور مطلوب قابل حل است، اگر همه حسگرها یک بار ترافیک یکسان داشته باشند. با این وجود، اگر حسگرها دارای بارهای مختلف ترافیکی باشند، مسئله به نظر می رسد NP-سخت باشد. ما الگوریتم تقریبی برای مسئله NP-سخت پیشنهاد کردیم و ثابت کردیم که الگوریتم پیشنهادی می تواند نسبت کارایی را تضمین کند. مطالعات تجربی نشان داده است که الگوریتم پیشنهادی می تواند به طور متوسط در مقایسه با بدترین حالت نسبت کارایی 3/2 به دست آمده، بهتر عمل کند. از این رو مسیری برای تحقیقات آتی، تجزیه و تحلیل کارایی متوسط الگوریتم پیشنهادی است. الگوریتم پیشنهادی رویکردی متمرکز را با فرض این که هر گره از توپولوژی شبکه آگاه است، اتخاذ می کند. مسیر دیگری برای کارهای آتی این است که الگوریتم توزیع شده ای را بسازیم که مقیاس-پذیری بیشتری برای طراحی شبکه های حسگر مبتنی بر خوشه داشته باشد.
Abstract
Wireless sensor networks have been receiving increasing attention in recent years due to their potential applications in the establishment of dynamic communications for emergency/rescue operations, disaster relief efforts, and military networks. In this paper, we investigate the problem of grouping the sensor nodes into clusters to enhance the overall scalability of the network. A selected set of nodes, known as gateway nodes, will act as cluster-heads for each cluster and the objective is to balance the load among these gateways. Load-Balanced Clustering increases system stability and improves the communication between the various nodes in the network. We call the problem addressed in this paper as the Load-Balanced Clustering Problem (LBCP). We first show that a special case of LBCP (whereby the traffic load contributed by all sensor nodes are the same) is optimally solvable in polynomial time. We next prove that the general case of LBCP is NP-hard. We then proposed an efficient -approximation algorithm for the problem.
1. Introduction
The availability of cheap, low power, and miniature embedded processors, radios, sensors, and actuators, often integrated on a single chip, is leading to the use of wireless communications and computing for interacting with the physical world in applications such as security and surveillance applications, smart classroom, monitoring of natural habitats and eco-systems, and medical monitoring. The resulting systems, often called wireless sensor networks, differ considerably from current networked and embedded systems. They combine the large scale and distributed nature of networked systems such as the Internet with the extreme energy constraints and physically coupled nature of embedded control systems.
8. Conclusion
In this paper, we address a problem that arise in the design of cluster-based wireless sensor networks. In particular, we consider the problem of assigning sensors to gateways in a wireless sensor network with the objective of distributing the traffic load among the gateways so as to ensure that no gateway is overloaded. We show that this problem is optimally solvable in polynomial time if all sensors have Uniform Traffic Load. However, the problem turns out to be NP-hard if the sensors have differing traffic loads. We proposed an approximation algorithm for the NP-hard problem and prove that our proposed algorithm is able to guarantee a performance ratio of 3/2 . Empirical studies have shown that our proposed algorithm is able to perform much better on the average as compared to the worst-case performance ratio derived. Hence one direction for future research is to analyse the average-case performance of our proposed algorithm. Our proposed algorithm adopts a centralized approach which assume that each node is aware of the network topology. Another direction for future work is to develop a distributed algorithm which would be more scalable for the design of cluster-based sensor networks.
چکیده
1. مقدمه
2. معماری سیستم
3. کارهای مرتبط
4. فرموله سازي مسئله
4-1. فرموله سازی به عنوان یک برنامه ریاضی
5. مسئله خوشه بندی با تعادل بار با ترافیک یکنواخت
6. مسئله خوشه بندی با بار متعادل (LBCP)
6-1. عدم پایداری LBCP
6-2. برخی از مشاهدات در مورد LBCP
6-3. الگوریتم تقریبی
6-4. الگوریتم حريصانه خوشه بندی با بار متعادل (GLBCA)
6-5. نسبت کارایی
7. نتایج شبیه سازی
8. نتیجه گیری
Abstract
1. Introduction
2. System architecture
3. Related work
4. Problem formulation
4.1. Formulation as a mathematical program
5. The Load-Balanced Clustering Problem with Uniform Traffic Load
6. The Load-Balanced Clustering Problem (LBCP)
6.1. The intractability of LBCP
6.2. Some observations about LBCP
6.3. An approximation algorithm
6.4. The Greedy Load-Balanced Clustering Algorithm (GLBCA)
6.5. Performance ratio
7. Simulation results
8. Conclusion
- ترجمه فارسی مقاله با فرمت ورد (word) با قابلیت ویرایش، بدون آرم سایت ای ترجمه
- ترجمه فارسی مقاله با فرمت pdf، بدون آرم سایت ای ترجمه