带时延约束的连通目标覆盖最大化生命周期问题

摘要

在无线传感器网络中，如何确保网络服务质量（如覆盖、连通）同时最大化网络生命周期是研究的热点和难点。在延时敏感的应用（如火灾、爆炸等灾害监测）中，传感器节点必须在有限的时间内传送它们的数据到汇聚节点。为了研究这种应用下的连通目标覆盖，提出了一种带时延约束的连通目标覆盖问题（ DCCTC）。首先，将DCCTC建模成为限高的最大覆盖树问题（ HLMCT），并证明它是NP-Complete的。然后，设计了一种快速启发式算法HLCWGC求解HLMCT问题。仿真实验和理论证明，HLCWGC在时延约束下获得的网络生命周期比已有的算法要好。具有较高的应用价值和理论意义。%The issue of guarantying the QoS ( target coverage, network connectivity, etc.), and simultaneously maximizing the lifetime in wireless sensor network is a hot topic, yet difficult subject of study. In some delay-sensi-tive sensor networks, sensors must transmit data to sink-node within a limited time in order to monitor the critical physical environment (fires, explosions, etc.). To study connected target coverage in such delay-sensitive sensor networks, we propose to examine the delay-constraint connected target coverage ( DCCTC ) problem. The study, specifically, includes of:1) modelling DCCTC problem as a Height Limited Maximum Cover Tree ( HLMCT) prob-lem and proving it is NP-complete 2) developping a fast heuristic algorithm, named HLCWGC( height-limited com-munication weighted greedy cover) to solve the HLMCT problem. Simulation results and theoretical researches show that HLCWGC algorithm is better than the existing algorithms in the delay-constraint sensor networks.