分布式无线传感器网络覆盖空洞识别方法

摘要

本发明提供了一种分布式无线传感器网络覆盖空洞识别方法，在边界节点集中以一个点为起始点在其1跳或2跳邻居节点中检索符合绝对角要求的后继，若搜索不到符合要求的后继则改变方向继续检索，在此过程中若后继为2跳邻居则插入最近公共1跳邻居，重复以上过程直到边界节点集为空，得到无线传感器网络的覆盖空洞。本发明解决了目前无线传感器网络中覆盖空洞识别精度低，能耗要求高的技术难题，将覆盖空洞的识别问题转化为环绕其的边界节点识别和聚类问题，有效降低了算法复杂度，减少了运行时间和覆盖空洞识别过程中节点间的通信与能量消耗，提高了识别精度。

主权项

一种分布式无线传感器网络覆盖空洞识别方法，其特征在于包括以下步骤：(1)以节点的位置信息建立无线传感器网络的全局坐标系，设无线传感器网络的节点集为S，边界节点集为BN_s，对于一个节点v，用visit(v)表示节点v的访问标识，其值为0表示节点v未访问，其值为1表示节点v已访问；将边界节点集BN_s中各节点的访问标识置为0，初始化一个空集作为最外层边界节点集BN_Cycle；在无线传感器网络的已知的边界节点集BN_s中选择坐标最小的节点v_st，将其置为当前节点v_cu，将当前节点加入最外层边界节点集BN_Cycle，置v_cu的访问标识为1；(2)从当前节点v_cu的访问标识为0的1跳邻居节点中搜寻是否存在绝对角属于的邻居节点，如果存在则从这些邻居节点中选取绝对角最小的节点v₁，将v₁作为当前节点v_cu的后继，以该后继作为当前节点v_cu，将当前节点v_cu加入最外层边界节点集BN_Cycle，将v_cu的访问标识置为1，进入步骤(3)；如果不存在，则从当前节点v_cu的访问标识为0的1跳邻居节点中搜寻是否存在绝对角属于的邻居节点，如果存在则从这些邻居节点中选取绝对角最小的节点v₁，将v₁作为当前节点v_cu的后继，以该后继作为当前节点v_cu，将当前节点v_cu加入最外层边界节点集BN_Cycle，将v_cu的访问标识置为1，进入步骤(3)；如果不存在，则从当前节点v_cu的访问标识为0的2跳邻居节点中搜寻是否存在绝对角属于的邻居节点，如果存在则从这些邻居节点中选取绝对角最小的节点v₁，将v₁作为当前节点v_cu的后继，在S中寻找当前节点v_cu和后继v₁的最近公共1跳邻居v₂，将v₂置为v₁的前驱，将v₂置为v_cu的后继，以v₁作为当前节点v_cu，将v_cu和v₂加入最外层边界节点集BN_Cycle，将v_cu的访问标识置为1，进入步骤(3)；如果不存在，则从当前节点v_cu的访问标识为0的2跳邻居节点中搜寻是否存在绝对角属于的邻居节点，如果存在则从这些邻居节点中选取绝对角最小的节点v₁，将v₁作为当前节点v_cu的后继，在S中寻找当前节点v_cu和后继v₁的最近公共1跳邻居v₂，将v₂置为v₁的前驱，将v₂置为v_cu的后继，以v₁作为当前节点v_cu，将v_cu和v₂加入最外层边界节点集BN_Cycle，将v_cu的访问标识置为1，进入步骤(3)；如果当前节点的访问标识为0的2跳邻居节点的绝对角均不属于则进入步骤(4)；(3)在当前节点v_cu的访问标识为0的1跳邻居节点和2跳邻居节点中搜寻是否存在绝对角属于或的邻居节点，如果存在则返回步骤(2)，否则将当前节点置为一个拐点然后执行步骤(4)；(4)从当前节点的访问标识为0的1跳邻居节点中搜寻是否存在绝对角属于[0,π]的邻居节点，如果存在则从这些邻居节点中选取绝对角最小的节点v₃，将v₃作为当前节点v_cu的后继，以该后继作为当前节点v_cu，将当前节点v_cu加入最外层边界节点集BN_Cycle，将v_cu的访问标识置为1，进入步骤(5)；如果不存在，从当前节点的访问标识为0的2跳邻居节点中搜寻是否存在绝对角属于[0,π]的邻居节点，如果存在则从这些邻居节点中选取绝对角最小的节点v₃，将v₃作为当前节点v_cu的后继，在S中寻找当前节点v_cu和后继v₃的最近公共1跳邻居v₄，将v₄置为v₃的前驱，将v₄置为v_cu的后继，以v₃作为当前节点v_cu，将v_cu和v₄加入最外层边界节点集BN_Cycle，将v_cu的访问标识置为1，进入步骤(5)；如果不存在，进入步骤(6)；(5)在当前节点v_cu的访问标识为0的1跳邻居节点和2跳邻居节点中搜寻是否存在绝对角属于[0,π]的邻居节点，如果存在则返回步骤(4)，否则将当前节点置为一个拐点然后执行步骤(6)；(6)检查v_st是否存在于当前节点的1跳或2跳邻居节点中，如果是则跳转至步骤(10)；否则，从当前节点的访问标识为0的1跳邻居节点中搜寻是否存在绝对角属于的邻居节点，如果存在则从这些邻居节点中选取绝对角最小的节点v₅，将v₅作为当前节点v_cu的后继，以该后继作为当前节点v_cu，将当前节点v_cu加入最外层边界节点集BN_Cycle，将v_cu的访问标识置为1，进入步骤(7)；如果不存在，从当前节点的访问标识为0的2跳邻居节点中搜寻是否存在绝对角属于的邻居节点，如果存在则从这些邻居节点中选取绝对角最小的节点v₅，将v₅作为当前节点v_cu的后继，在S中寻找当前节点v_cu和后继v₅的最近公共1跳邻居v₆，将v₆置为v₅的前驱，将v₆置为v_cu的后继，以v₅作为当前节点v_cu，将v_cu和v₆加入最外层边界节点集BN_Cycle，将v_cu的访问标识置为1，进入步骤(7)；如果不存在，进入步骤(8)；(7)检查v_st是否存在于当前节点的1跳或2跳邻居节点中，如果是则跳转至步骤(10)；否则，从当前节点v_cu的访问标识为0的1跳邻居节点和2跳邻居节点中搜寻是否存在绝对角属于的邻居节点，如果存在则返回步骤(6)，否则将当前节点置为一个拐点然后执行步骤(8)；(8)检查v_st是否存在于当前节点的1跳或2跳邻居节点中，如果是则跳转至步骤(10)；否则，从当前节点的访问标识为0的1跳邻居节点中搜寻是否存在绝对角属于[π,2π]的邻居节点，如果存在则从这些邻居节点中选取绝对角最小的节点v₇，将v₇作为当前节点v_cu的后继，以该后继作为当前节点v_cu，将当前节点v_cu加入最外层边界节点集BN_Cycle，将v_cu的访问标识置为1，进入步骤(9)；如果不存在，从当前节点的访问标识为0的2跳邻居节点中搜寻是否存在绝对角属于[π,2π]的邻居节点，如果存在则从这些邻居节点中选取绝对角最小的节点v₇，将v₇作为当前节点v_cu的后继，在S中寻找当前节点v_cu和后继v₇的最近公共1跳邻居v₈，将v₈置为v₇的前驱，将v₈置为v_cu的后继，以v₇作为当前节点v_cu，将v_cu和v₈加入最外层边界节点集BN_Cycle，将v_cu的访问标识置为1，进入步骤(9)；(9)如果当前节点的1跳邻居节点和2跳邻居节点包含节点v_st，进入步骤(10)，否则返回步骤(8)；(10)将最外层边界节点集BN_Cycle作为无线传感器网络的最外层边界输出，求取最外层边界节点集BN_Cycle和边界节点集BN_s的交集bounds＝BN_Cycle∩BNs，将bounds从边界节点集BN_s中移除得到剩余边界节点集BN_Remain＝BNs/bounds，将最外层边界节点集BN_Cycle重置为空集；(11)在BN_Remain集合中选取访问标识为0且坐标最小的节点作为当前节点v_cu，重复步骤(2)到步骤(10)，直到剩余边界节点集BN_Remain为空或者边界节点集BN_S为空，完成覆盖空洞识别。