中文摘要：

传感器节点的部署包括连通网络和非连通网络2种情况．为了最小化网络部署开销，对非连通网络的传感器节点部署问题进行了研究，建立了整数线性规划模型，并证明该问题为NP-complete问题．为找到该问题的近似最优解，通过理论分析确定了传感器节点的候选部署区域，提出了一种启发式的传感器节点贪婪部署算法，迭代地将传感器节点部署到覆盖目标点数最多的候选部署区域，直到覆盖所有目标点．通过仿真实验将所提出的贪婪部署算法和现有的遗传算法以及问题模型的最优解进行了比较，验证了算法的有效性．

英文摘要：

Two cases are included in the minimum sensor deployment problems, according to whether the deployed network is desired connected or not. The non-connected case is studied, to minimize the deployment cost. The proposed problem is formulated as an integer linear program problem, which is proved to be an NP-complete problem. To approximately derive the optimal solution, the candidate deployment regions are theoretically derived and computed. A greedy algorithm is proposed, where one sensor is iteratively deployed into the maximal coverage number candidate region until all targets are covered. Compared with existing genetic algorithm and the optimal solution, simulation results confirm the effectiveness of the proposed algorithm.