无线传感器网络广播与节点休眠算法中的节能覆盖问题研究

摘要

无线传感器网络在军民用领域有着广阔的应用前景，是目前学术界研究的热点之一。由于无线传感器网络中节点电池能量有限，节能问题受到了广泛的关注。降低节点射频通信部分的能耗是节能的关键，由于射频部分在发送状态功耗最高、休眠状态功耗最低，因此减少冗余通信量和使冗余节点休眠有助于节能。广播在传感器网络中被频繁应用于数据查询、路由发现、时钟同步等操作，广播流量是网络通信流量的重要组成部分。由于传感器网络通常采用高密度布撒，实际只需少量节点参与广播即可覆盖全网节点，广播中存在着大量的冗余。同样，对于目标区域的覆盖也只需少量节点处于活动状态即可完成，也存在着大量的冗余节点。降低冗余广播通信量和使冗余节点休眠有助于节能。如何削减冗余广播和发现可休眠的冗余节点，可归结为对节能覆盖问题的研究，具体包括以下两个问题。1.广播中的节能覆盖问题：如何用尽量少的节点覆盖网内全部节点，使得只需这些节点参与广播，网内节点都可以收到广播包。这是一个最小点集合覆盖问题，即对一个点集合而言，如何找出其最小连通支配集。2.休眠机制中的节能覆盖问题：如何使用尽量少的节点覆盖全部的探测区域，使得不出现覆盖盲点、不破坏网络的连通性，这可归结为一个最小区域覆盖问题，其关键是覆盖度和连通性。研究表明，这两个最小覆盖问题都是NP-HARD问题，只能采用启发式算法求次优解。基于此上考虑，本文主要研究连通支配集的启发式构造算法和冗余节点判定的启发式算法，并将之应用于广播和节点休眠机制中。