Abstract: To solve the surface coverage problem of the heterogeneous multi sensor network on rolling terrains, a multi-sensor multi-stage cluster deployment method is presented. Firstly, considering the effect of terrain occlusion, sensor reconnaissance and communication models in rolling terrain environment are put forward. To determine sensor coverage region rapidly, an improved visual region solving algorithm called d-Xdraw is built based on the similarity judgment of sight intersection points. Moreover, in order to enhance the coverage rate, a clustering deployment strategy is introduced and the sensor deployment process is divide into several stages. According to the characteristics of each stage, the particle swarm optimization and improved virtual force algorithms are used to solve the stage 2 and stage 3, respectively. Experiment results show that the improved d-Xdraw algorithm can greatly improve the solving speed of the visible region at the expense of a little precision. Compared with the direct optimal deployment method, the multi-stage cluster deployment method can save at most 26.7% of computing time, and the coverage rate can be increased by 10.9%.

Key words: rolling terrain, sensor network, surface coverage, visible region, virtual force algorithm