张斌权，陈　永，张　安，陈光亭

(杭州电子科技大学理学院，浙江 杭州 310018)



无线传感器网络中的线段覆盖问题

张斌权，陈永，张安，陈光亭

(杭州电子科技大学理学院，浙江 杭州 310018)

摘要：线段覆盖问题是指用尽可能少的传感器覆盖某区域内的若干条线段，使得任意线段上的目标点均位于至少某一个传感器的覆盖区域内。主要讨论目标点位于水平或垂直方向线段上的情形，通过运用区域分层思想和传感器覆盖的几何特性设计了一个求解该问题的多项式时间近似算法，并在理论上证明了该近似算法的性能比为18。

关键词：无线传感器网络；线段覆盖；近似算法；性能比

0引言

无线传感器网络通过大量的廉价微型传感器节点，采集并处理网络覆盖区域中被感知对象的信息，从而实现信息传送的功能。基于微机电系统的微传感技术和无线联网技术为无线传感器网络赋予了广阔的应用前景，目前的应用领域主要包括环境检测、目标跟踪、医疗护理及军事领域等。覆盖问题是无线传感器网络中一类重要问题，在区域监控和环境检测等领域均有广泛应用[1]。区域覆盖问题是指用最少个数的传感器覆盖某区域内的若干个目标点[2-3]，而踪迹覆盖[4]和路径覆盖[5]均是考虑目标点位于某些道路或者通道的情形。本文所考虑的传感器覆盖问题中目标点均任意分布于某些水平或者垂直的道路上[6]，该情形在现实生活中较为常见。本文重点研究设计求解该问题的近似算法，并从理论上给出算法性能比的证明。……