关键词: 有向传感器网络 连通k覆盖集 概率感知模型 覆盖效益

Abstract:

The fundamental issue in sensor networks provides a certain degree of coverage and maintains connectivity under the energy constraint, on which the mi nimal connected k-coverage set problem is proposed. The traditional problem studies the deterministic omni-directional sensing model which is too ideal   to adapt atrocious environments or directional sensor networks. To over- come the shortcomings, the connected k-coverage problem is investigated under t   he probabilistic sensing models in directional sensor networks in this paper. Because it is NP-hard, two approximate algorithms, IPA and CBDA, are propo  sed. IPA is a centralized so- lution based on 0-1 integer progmmming and minimum spanning tree. And CBDA is a distributed algorithm based on coverage be   nefit. It is proved that the solution gotten by IPA and CBDA are feasible. The time complexities, the communication complexities and the performance rat    io are theoretically analyzed, Simulation results show that IPA and CBDA significantly maintain coverage in the probabilistic sensing model and prolong   the network lifetime in some sense compared with the ILP and DGA.

Key words: directional sensor network, connected k-coverage set, probabilistic sensing model, coverage benefit