Because the base stations can only be placed at the border of the monitored area, the border placement problem was formally defined. For the goal to place the minimum number of base stations to cover as much as possible the monitored areas, an improved placement algorithm with polynomial time was proposed. The coverage percentage of initial algorithm was analyzed first. When initial coverage percentage is larger than guaranteed coverage percentage, it is possible to reduce the size of initial placement set. Finally, placement set was gradually improved to achieve the minimun of placement set. The results indicate that the coverage percentage and placement set of the proposed algorithm are superior to random algorithm in different test environments.%针对基站仅能部署在监控区域边缘这个新问题,形式化定义了节点边缘分布问题.为用最少的基站尽可能多地覆盖监控区域,提出了一个有多项式时间复杂性的部署算法.算法分为两个阶段,首先分析了初始部署的覆盖率,当初始覆盖率大于保证覆盖率时,减少初始部署集的大小是可能的;然后,改进算法以递增的方式来改进初始部署集,以实现在满足最大覆盖率的前提下最小化最终部署集.实验结果显示了在3种不同的测试环境下,算法的覆盖率和部署集均优于随机部署算法,是部署无线传感节点的有效方法.
展开▼