[0005] 本发明提出了一种基于可调感知半径模型的连通目标K覆盖方法，该方法通过多轮次调度传感器的工作状态和工作半径，来尽可能延长网络的生命周期。首先，根据采集到的传感器的位置信息和状态信息来构建网络图，其中状态信息主要指传感器当前剩余的能量；其次，根据网络图中边的信息，计算任意传感器节点到汇点之间的最短路径，形成最小能量通信树，从而得到每个传感器到汇点的通信路由以及单位时间的通信能量代价；然后，采集每个传感器周围目标点的分布情况，即传感器在不同工作功率对应的监测半径下所能监测到的目标点集合以及每个目标点当前被监测的状态信息；接着，根据采集到的信息，得到每个未满足K覆盖需求的目标点的候选传感器集合；再次，逐个选择目标点，在该目标点的候选传感器集合中，选择一组传感器和工作半径，使得该目标点满足K覆盖需求，直到所有目标点都能被K个活跃传感器监测到。最后，得到一组满足网络覆盖和连通需求的传感器集合后，根据传感器的能耗模型计算该传感器集合所能工作的最长时间，然后更新每个传感器的剩余能量，重复上述步骤选出新的工作传感器集合，直到无法选出一组传感器集合为止，从而得到网络中每个传感器工作状态和工作时间的调度方案。
[0006] 本发明解决其技术问题采用的技术方案步骤如下：
[0007] 一种基于可调感知半径模型的连通目标K覆盖方法，采用的无线传感网络为：在一个感兴趣的平面区域中，存在M个位置已知的目标点O＝{o1,o2,…,oM}和一个汇点Sink，初始时，每个目标点的覆盖度deg(o)＝0。向该区域中随机部署了N个全向传感器S＝{s1,s2,…,sN}，每个传感器存在P个工作功率，每个功率对应一个监测半径，因此每个传感器有一个可调的感知半径集R＝{r1,r2,…,rP}。每个传感器存在一个固定的通信半径为Rtra，初始状态下，每个传感器si的剩余能量 相同， Einit为传感器的初始能量值。所有的传感器具有相同的数据采集速率,假设单位时间采集一个单位的数据。目标点的覆盖度阈值为K，即需要满足deg(o)≥K。具体的步骤如下：
[0008] 步骤1：根据网络中传感器的位置信息和剩余能量信息构建网络图；
[0009] 步骤2：从网络图中找出任意传感器到Sink的最短路径并计算根据当前路径传输一个单位的数据所花费的通信代价；
[0010] 步骤3：计算每个传感器在每个监测半径下所能监测到的不满足K覆盖需求的目标点集合；
[0011] 步骤4：计算每个目标点的候选传感器集合；
[0012] 步骤5：选择一个具有最少的候选传感器的目标点。
[0013] 步骤6：计算该目标点的候选传感器集合中每个传感器的覆盖效用，并选择一个具有最大覆盖效用的传感器和半径，更新该传感器在当前半径下覆盖的目标的覆盖度状态，更新每个目标点的候选传感器集合。重复该步骤直到当前目标点满足K覆盖。
[0014] 步骤7：重复步骤5-6，直到选择出一个连通K覆盖集合为止，计算该集合的工作时间并更新传感器的剩余能量信息。
[0015] 步骤8：判断网络中是否还存在连通K覆盖集合。如果存在，重复步骤1至步骤7；不存在，算法结束，给出传感器的状态调度策略。
[0016] 步骤1所述得到构建网络图分一下步骤：
[0017] 1-1、将剩余能量低于阈值χ的传感器设为死亡传感器，在网络图中表现为孤立点，不和任何传感器存在通信边；
[0018] 1-2、针对非死亡节点，我们构造无向权值图G＝(V,E,W)，图的顶点V为场景中所有非死亡节点和Sink的集合；边E代表顶点间是否连通；权值W代表两顶点间的通信代价。若两顶点si与sj相邻(两顶点距离d(si,sj)≤Rtra)，则为其添加一条边E＝E∪e(si,sj)，边的权值为ω(si,sj)＝eTr(Si,sj)+eRe，其中单位数据的传输能量代价eTr(si,sj)＝a+b·d(si,sj)β，a,b,β为常数，可根据传感器物理特性设置，单位数据的接收能量代价eRe为常数，可根据传感器物理特性设置；若顶点si与sj不相邻，则认为边e(si,sj)不存在，即令边权ω(si,sj)＝+∞；若任意顶点si与Sink相邻，则添加边E＝E∪e(si,Sink)，边的权值为ω(si,Sink)＝eTr(si,Sink)+eRe。
[0019] 步骤2所述的计算最短路径和能量代价，使用求解最短路径的Dijkstra算法，计算出无向权值图G中任意顶点si与Sink间的最短路径，并计算路径的长度，该路径长度表示从si向Sink传输一个单位的数据所花费的能量代价，记做e(path(si)。若si与Sink不存在通信路径，将si设为死亡传感器。
[0020] 步骤3所述的计算监测目标点集合，根据位置信息计算非死亡传感器在不同的功率对应的感知区域内存在的目标点，并将传感器si在第p个功率下感知到的目标点集合记为OCov(i,p)。
[0021] 步骤4所述的计算目标点的候选传感器集合，根据步骤3中的信息，将在最大功率下能监测到目标点oj的传感器放入集合 中。对于满足 的目标点，其候选传感器集合 中的传感器必须全部激活并覆盖到oj，才能满足oj的覆盖度需求。将这类目标点定义为危险目标。
[0022] 步骤5所述的选择具有最少的候选传感器的目标点oCri，也就是：
[0023] 步骤6所述从目标点oCri的候选传感器集合中选择覆盖集的步骤如下：
[0024] 6-1计算传感器在每个功率下的单位时间能耗，第p个功率下单位时间内的监测能耗为eSe(p)＝δ·rp2。
[0025] 其中，δ为常数，与传感器物理特性有关。
[0026] 6-2计算集合中每个传感器可开启的最小功率。根据步骤3和步骤4所得到的集合，判断传感器的最大覆盖范围内是否存在危险目标。若不存在，传感器可开启的最小功率为能监测到oCri的最小功率；若存在，传感器可开启的最小功率为能监测oCri以及所有危险目标的最小功率。
[0027] 6-3计算集合中每个传感器在可开启的最小功率到最大功率中，每个功率下的覆盖效用，将传感器si在第p个功率下的覆盖效用设为 其公式表述为：
[0028]
[0029] 其中， 代表OCov(i,p)中deg(0)＜K的目标点的个数， 代表OCov(i,p)中deg(0)≥K的目标点的个数，e(path(si)为传感器si向Sink传输一个单位数据的能量代价。
[0030] 6-4选择具有最大效用值的传感器和功率，将该传感器在该功率下监测到的所有目标点的覆盖度+1，并将该传感器从所有目标点的候选传感器中移除。
[0031] 6-5判断deg(oCri)≥K是否成立。若不成立，重复执行步骤6-1至步骤6-4；若成立，结束步骤6。
[0032] 步骤7所述选择出一个连通K覆盖集合C，计算该集合的工作时间并更新传感器的剩余能量信息，详细步骤如下：
[0033] 7-1判断是否存在deg(o)＜K的目标点。若存在，重复执行步骤5和步骤6；若不存在，执行下一步；
[0034] 7-2将当前选择出来的传感器集合与集合中每个传感器的通信路径结合，构成连通K覆盖集C；
[0035] 7-3计算连通K覆盖集合C中每个传感器单位时间的能量代价。对于只监测不接收信息的传感器，其能量代价公式为ecost(si)＝eSe+eTr；对于不监测的传感器，其能量代价为ecost(si)＝(eRe+eTr)·|SDes(si)|，其中，SDes(si)为si的后代传感器集合，si需要接收并传输这些传感器对目标点的监测信息，|SDes(si)|等价于si所在的通信路径个数；对于既监测又接收信息的传感器，其能量代价为ecost(si)＝eSe+eTr+(eRe+eTr)·SDes(si)。
[0036] 7-4计算该连通K覆盖集合C的运行时间，即C中所有传感器能够持续运行的最大时长T，
[0037] 步骤8判断网络中是否还存在其他连通K覆盖集合，即判断所有目标点的候选传感器个数是否大于K。如果是，重复步骤1至步骤7；否则，算法结束，给出传感器的状态调度策略。
[0038] 本发明的有益效果：
[0039] 1.本发明针对二维地形应用场景，提出基于可调感知半径模型的连通目标K覆盖方法，通过K覆盖的形式，极大增强了网络的容错性，防止了因工作传感器损坏所导致的网络监控盲区。
[0040] 2.本发明基于可调感知半径模型的覆盖方法，减少了网络工作能耗，从而在能量有限无线传感器网络中，延长网络工作时长，减少了网络成本。
