الگوریتم¬های خوشه¬بندی کارآمد با تعادل بار برای شبکه¬های حسگر بی¬سیم

شبکه¬های حسگر بی¬سیم در سال¬های اخیر به دلیل کاربردهای بالقوه¬شان در ایجاد ارتباطات پویا برای عملیات اورژانس/ نجات، تلاش¬های امداد رسانی و شبکه¬های نظامی مورد توجه قرار گرفته¬اند. این مقاله، مسئله گروه¬بندی گره¬های حسگر را در خوشه¬ها برای افزایش مقیاس¬پذیری کلی شبکه مورد بررسی قرار می¬دهد. مجموعه¬ای از گره¬ها موسوم به گره دروازه، به عنوان سرخوشه برای هر خوشه عمل می¬کنند و هدف این است که تعادل بار را در میان این دروازه¬ها برقرار کنیم. خوشه¬بندی با تعادل بار باعث افزایش ثبات سیستم و بهبود برقراری ارتباط بین گره¬های مختلف در شبکه می¬شود. مسئله¬ای که در این مقاله مطرح شده است را مسئله خوشه¬بندی با تعادل بار (LBCP ) می¬نامیم. برای اولین بار نشان می¬دهیم که حالتی خاص از LBCP (که در آن بار ترافیک ایجاد شده توسط تمام گره¬های حسگر یکسان است) در زمان چندجمله¬ای به¬طور مطلوب قابل حل است. پس از آن ثابت می¬کنیم که حالت کلی LBCP، NP-سخت است. سپس یک الگوریتم تقریبی کارآمد برای این مسئله پیشنهاد شد.

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 32-a