Minimum Data-Latency-Bound k-Sink Placement Problem in Wireless Sensor Networks
Minimum Data-Latency-Bound k-Sink Placement Problem in Wireless Sensor Networks
复制标题
无线传感器网络中受最小数据延迟限制的 k-Sink 放置问题
DOI：
10.1109/tnet.2011.2109394
复制
发表时间：
2011-10-01
影响因子：
3.7
通讯作者：
Du, Ding-Zhu
中科院分区：
文献类型：
--
作者：
Kim, Donghyun;Wang, Wei;Du, Ding-Zhu
在本文中，我们提出了一个新的多sink定位问题的无线传感器网络，以最好地支持实时应用。我们正式定义这个问题为k-汇点布局问题（k-SPP），并证明它是APX-完全的。我们表明，现有的近似算法的著名的k-中心问题是一个常数因子近似的k-SPP。此外，我们引入了一个新的贪婪算法的k-SPP，并证明其近似比是非常接近的最佳实现，2。通过模拟，我们表明我们的算法优于其竞争对手的平均。
In this paper, we propose a new multiple-sink positioning problem in wireless sensor networks to best support realtime applications. We formally define this problem as the k-Sink Placement Problem (k-SPP) and prove that it is APX-complete. We show that an existing approximation algorithm for the well-known k-center problem is a constant factor approximation of k-SPP. Furthermore, we introduce a new greedy algorithm for k-SPP and prove its approximation ratio is very near to the best achievable, 2. Via simulations, we show our algorithm outperforms its competitor on average.