1.一种无线传感器网络覆盖空洞检测方法,其特征在于,包括:
根据无线传感器网络中各节点之间的连通信息构建整个无线传感器网络所对应的Rips复形;所述Rips复形包括0-单形,1-单形,2-单形以及3-单形;所述0-单形为所述无线传感器网络中任一节点,1-单形为所述无线传感器网络中两个邻居节点形成的边,2-单形为三个互为邻居的节点构成的三角图形,3-单形为四个互为邻居的节点构成的四边图形;
在所述无线传感器网络中删除所述Rips复形中的冗余节点,确定删除冗余点后的简化无线传感器网络结构;
在所述简化无线传感器网络结构内的所述3-单形所构成的四边图形中,判断所述四边图形中的对角边所组成的所有2-单形是否在所述四边图形中,得到第一判断结果;
若所述第一判断结果表示为所述四边图形中的对角边所组成的所有2-单形在所述四边图形中,删除所述简化无线传感器网络结构中的冗余边;
获取删除所述冗余节点以及所述冗余边之后的剩余无线传感器网络结构;
根据所述剩余无线传感器网络结构确定覆盖空洞。
2.根据权利要求1所述的无线传感器网络覆盖空洞检测方法,其特征在于,所述在所述无线传感器网络中删除所述Rips复形中的冗余节点,确定删除冗余点后的简化无线传感器网络结构,具体包括:计算所述Rips复形内所有节点的度以及聚类系数;
根据所述度以及所述聚类系数确定确定节点集合和非确定节点集合;
判断所述确定节点集合和所述非确定节点集合中的节点是否满足删点规则,得到第二判断结果;
若所述第二判断结果表示为所述确定节点集合和所述非确定节点集合中的节点满足删点规则,将满足删点规则的确定节点与非确定节点分别放入第一待筛选序列和第二待筛选序列;其中,所述删点规则为①节点v的邻居图连通;②节点v的邻居图中的所有环路均可三角化即节点v的邻居图中的每个环路均可由长度为3的环构成。
3.根据权利要求2所述的无线传感器网络覆盖空洞检测方法,其特征在于,所述将满足删点规则的确定节点与非确定节点分别放入第一待筛选序列和第二待筛选序列,之后还包括:①判断所述第一待筛选序列中第一节点的邻居图中是否有聚类系数比第一节点的聚类系数大的且满足删点规则的确定节点,得到第三判断结果;
②若所述第三判断结果表示为第一节点的邻居图中有聚类系数比所述第一节点的聚类系数大的且满足删点规则的确定节点,删除所述第一节点的邻居节点中聚类系数最大的且满足删点规则的确定节点,同时将删除节点的所有邻居节点分别移出所述第一待筛选序列和所述第二待筛选序列;
③若所述第三判断结果表示为第一节点的邻居图中没有聚类系数比所述第一节点的聚类系数大的且满足删点规则的确定节点,删除所述第一节点,同时将所述第一节点的所有邻居节点分别移出所述第一待筛选序列和所述第二待筛选序列。
④重复步骤①②③,直到第一待筛选序列中的节点全部检查完毕;
⑤判断所述第二待筛选序列中第一节点的邻居图中是否有聚类系数比所述第一节点的聚类系数大的且满足删点规则的非确定节点,得到第四判断结果;
⑥若所述第四判断结果表示为所述第二待筛选序列中第一节点的邻居图中有聚类系数比所述第一节点的聚类系数大的且满足删点规则的非确定节点,删除所述第一节点的邻居节点中聚类系数最大的且满足删点规则的非确定节点,同时将所述删除节点的所有邻居节点移出所述第二待筛选序列;
⑦若所述第四判断结果表示为所述第二待筛选序列中第一节点的邻居图中没有聚类系数比所述第一节点的聚类系数大的且满足删点规则的非确定节点,删除所述第一节点,同时将所述第一节点的所有邻居节点移出所述第二待筛选序列。
⑧重复步骤⑤⑥⑦,直到第二待筛选序列中的节点全部检查完毕。
4.根据权利要求3所述的无线传感器网络覆盖空洞检测方法,其特征在于,所述删除所述简化无线传感器网络结构中的冗余边,具体包括:获取所述3-单形中的两条对角边,并根据所述对角边删除冗余边。
5.根据权利要求4所述的无线传感器网络覆盖空洞检测方法,其特征在于,所述根据所述剩余无线传感器网络结构确定覆盖空洞,具体包括:获取所述剩余无线传感器网络的边界边;
删除所述边界边内的假边界边,确定剩余边界边;
根据所述剩余边界边确定边界环路;
对所述边界环路进行筛选处理,确定筛选后的边界环路;
缩短所述筛选后的边界环路,确定覆盖空洞。
6.一种无线传感器网络覆盖空洞检测系统,其特征在于,包括:
Rips复形构建模块,用于根据无线传感器网络中各节点之间的连通信息构建整个无线传感器网络所对应的Rips复形;所述Rips复形包括0-单形,1-单形,2-单形以及3-单形;所述0-单形为所述无线传感器网络中任一节点,1-单形为所述无线传感器网络中两个邻居节点形成的边,2-单形为三个互为邻居的节点构成的三角图形,3-单形为四个互为邻居的节点构成的四边图形;
冗余节点删除模块,用于在所述无线传感器网络中删除所述Rips复形中的冗余节点,确定删除冗余点后的简化无线传感器网络结构;
第一判断模块,用于在所述简化无线传感器网络结构内的所述3-单形所构成的四边图形中,判断所述四边图形中的对角边所组成的所有2-单形是否在所述四边图形中,得到第一判断结果;
冗余边删除模块,用于若所述第一判断结果表示为所述四边图形中的对角边所组成的所有2-单形在所述四边图形中,删除所述简化无线传感器网络结构中的冗余边;
剩余无线传感器网络结构获取模块,用于获取删除所述冗余节点以及所述冗余边之后的剩余无线传感器网络结构;
覆盖空洞确定模块,用于根据所述剩余无线传感器网络结构确定覆盖空洞。
7.根据权利要求6所述的无线传感器网络覆盖空洞检测系统,其特征在于,所述冗余节点删除模块具体包括:度以及聚类系数计算单元,用于计算所述Rips复形内所有节点的度以及聚类系数;
确定节点集合和非确定节点集合确定单元,用于根据所述度以及所述聚类系数确定确定节点集合和非确定节点集合;
第二判断单元,用于判断所述确定节点集合和所述非确定节点集合中的节点是否满足删点规则,得到第二判断结果;
冗余节点删除单元,用于若所述第二判断结果表示为所述确定节点集合和所述非确定节点集合中的节点满足删点规则,将满足删点规则的确定节点与非确定节点分别放入第一待筛选序列和第二待筛选序列;其中,所述删点规则为①节点v的邻居图连通;②节点v的邻居图中的所有环路均可三角化即节点v的邻居图中的每个环路均可由长度为3的环构成。
8.根据权利要求7所述的无线传感器网络覆盖空洞检测系统,其特征在于,还包括:第三判断单元,用于①判断所述第一待筛选序列中第一节点的邻居图中是否有聚类系数比第一节点的聚类系数大的且满足删点规则的确定节点,得到第三判断结果;
第一移除单元,用于②若所述第三判断结果表示为第一节点的邻居图中有聚类系数比所述第一节点的聚类系数大的且满足删点规则的确定节点,删除所述第一节点的邻居节点中聚类系数最大的且满足删点规则的确定节点,同时将删除节点的所有邻居节点分别移出所述第一待筛选序列和所述第二待筛选序列;
第二移除单元,用于③若所述第三判断结果表示为第一节点的邻居图中没有聚类系数比所述第一节点的聚类系数大的且满足删点规则的确定节点,删除所述第一节点,同时将所述第一节点的所有邻居节点分别移出所述第一待筛选序列和所述第二待筛选序列。
第一待筛选序列确定单元,用于④重复步骤①②③,直到第一待筛选序列中的节点全部检查完毕;
第四判断单元,用于⑤判断所述第二待筛选序列中第一节点的邻居图中是否有聚类系数比所述第一节点的聚类系数大的且满足删点规则的非确定节点,得到第四判断结果;
第三移除单元,用于⑥若所述第四判断结果表示为所述第二待筛选序列中第一节点的邻居图中有聚类系数比所述第一节点的聚类系数大的且满足删点规则的非确定节点,删除所述第一节点的邻居节点中聚类系数最大的且满足删点规则的非确定节点,同时将所述删除节点的所有邻居节点移出所述第二待筛选序列;
第四移除单元,用于⑦若所述第四判断结果表示为所述第二待筛选序列中第一节点的邻居图中没有聚类系数比所述第一节点的聚类系数大的且满足删点规则的非确定节点,删除所述第一节点,同时将所述第一节点的所有邻居节点移出所述第二待筛选序列。
第二待筛选序列确定单元,用于⑧重复步骤⑤⑥⑦,直到第二待筛选序列中的节点全部检查完毕。
9.根据权利要求8所述的无线传感器网络覆盖空洞检测系统,其特征在于,所述冗余边删除模块具体包括:冗余边删除单元,用于获取所述3-单形中的两条对角边,并根据所述对角边删除冗余边。
10.根据权利要求9所述的无线传感器网络覆盖空洞检测系统,其特征在于,所述覆盖空洞确定模块具体包括:边界边获取单元,用于获取所述剩余无线传感器网络的边界边;
剩余边界边确定单元,用于删除所述边界边内的假边界边,确定剩余边界边;
边界环路确定单元,用于根据所述剩余边界边确定边界环路;
筛选后的边界环路确定单元,用于对所述边界环路进行筛选处理,确定筛选后的边界环路;
覆盖空洞确定单元,用于缩短所述筛选后的边界环路,确定覆盖空洞。