摘要
线段覆盖问题是指用尽可能少的传感器覆盖某区域内的若干条线段,使得任意线段上的目标点均位于至少某一个传感器的覆盖区域内。主要讨论目标点位于水平或垂直方向线段上的情形,通过运用区域分层思想和传感器覆盖的几何特性设计了一个求解该问题的多项式时间近似算法,并在理论上证明了该近似算法的性能比为18。
The coverage problem is an important problem in many wireless sensor network applications involving surveillance or environmental monitoring of an area. In this paper, we address the problem of covering a set of line segments with minimum number of sensors. A line segment is said to be covered if it is contained in the sensing region of at least one among the sensors. For this problem, a polynomial time approximation algorithm is proposed based on the layered design idea and geometry property of sensor covering. It is proved that the performance ratio of this algorithm is 18.
出处
《杭州电子科技大学学报（自然科学版）》
2015年第6期93-95,共3页
Journal of Hangzhou Dianzi University：Natural Sciences
基金
国家自然科学基金资助项目(11401149)
关键词
无线传感器网络
线段覆盖
近似算法
性能比
wireless sensor networks
line segment coverage
approximation algorithm
performance ratio
