1.一种基于三角形内点测试的边界节点判定方法,其特征在于,
构建第一节点集合,所述第一节点集合为无线网络中任一节点A在其通信范围内所有一跳邻居节点的集合;
判断第一节点集合中一跳邻居节点的数量,若一跳邻居节点的数量小于3,节点A为边界节点,判断结束,否则进入以下步骤;
发送第一节点集合至集合内所有一跳邻居节点,以便获取第一节点集合中任一一跳邻居节点在其通信范围内与节点A共享的一跳邻居节点的标识和数量;
构建第二节点集合,所述第二节点集合为第一节点集合中不包含与节点A共享一跳邻居节点数量小于2的一跳邻居节点;
构建第一三角形集合,所述第一三角形集合为遍历第二节点集合内任意3个一跳邻居节点构成的所有三角形;
判断第一三角形集合内三角形的数量,若第一三角形集合为空集,节点A为边界节点,判断结束,否则进入以下步骤;
构建第二三角形集合,所述第二三角形集合为第一三角形集合中根据三角形内点测试法测试获得的围绕节点A的所有三角形;
判断第二三角形集合内三角形的数量,若第二三角形集合为空集,节点A为边界节点,判断结束,否则进入以下步骤;
判断第二三角形集合内是否存在合格三角形,若第二三角形集合内不存在任一合格三角形,节点A为边界节点,判断结束;
所述合格三角形为三角形的任一条边为合格边;
所述合格边包括第一类型边、第二类型边、第三类型边和第四类型边;所述第一类型边满足边的两侧端节点互为一跳邻居,所述第二类型边满足边的两侧端节点包含相同的一跳邻居节点,所述第三类型边满足边的两侧端节点包含互为一跳邻居的一跳邻居节点;所述第四类型边满足第二三角形集合内不存在以第四类型边的端节点以及第三节点为顶点的三角形,所述第三节点为第四类型边两侧端节点通信的最短路径上的节点;
所述第四类型边的判定过程为:
判断第二三角形集合中是否存在以判定边的端节点以及第三节点为顶点的三角形;若不存在,判定边为第四类型边,判断结束;所述以判定边的端节点以及第三节点为顶点的三角形,包括以判定边两侧端节点以及一个第三节点为顶点的三角形,和以判定边一侧端节点以及两个第三节点为顶点的三角形;
若存在,判断所述判定边是否为凹边;若不是,判定边为第四类型边,判断结束;
所述凹边的判定原理为:判定节点周围存在一个紧靠所述以判定边的端节点以及第三节点为顶点的三角形的U型环,并且判定节点位于U型环外的凹陷处;当判定边为凹边,且凹边的两个端点位于U型环的两个端点处,三角形除该凹边两个端点以外的第三个节点位于U型环上除端点以外的位置,则该判定节点为边界节点。
2.一种基于三角形内点测试的边界节点判定装置,其特征在于,包括
第一构建模块,用于构建第一节点集合,所述第一节点集合为无线网络中任一节点A在其通信范围内所有一跳邻居节点的集合;
第一判断模块,用于判断第一节点集合中一跳邻居节点的数量,若一跳邻居节点的数量小于3,节点A为边界节点,判断结束,否则进入以下步骤;
第一发送模块,用于发送第一节点集合至集合内所有一跳邻居节点,以便获取第一节点集合中任一一跳邻居节点在其通信范围内与节点A共享的一跳邻居节点的标识和数量;
第二构建模块,用于构建第二节点集合,所述第二节点集合为第一节点集合中不包含与节点A共享一跳邻居节点数量小于2的一跳邻居节点;
第三构建模块,用于构建第一三角形集合,所述第一三角形集合为遍历第二节点集合内任意3个一跳邻居节点构成的所有三角形;
第二判断模块,用于判断第一三角形集合内三角形的数量,若第一三角形集合为空集,节点A为边界节点,判断结束,否则进入以下步骤;
第四构建模块,用于构建第二三角形集合,所述第二三角形集合为第一三角形集合中根据三角形内点测试法测试获得的围绕节点A的所有三角形;
第三判断模块,用于判断第二三角形集合内三角形的数量,若第二三角形集合为空集,节点A为边界节点,判断结束,否则进入以下步骤;
第四判断模块,用于判断第二三角形集合内是否存在合格三角形,若第二三角形集合内不存在任一合格三角形,则节点为A边界节点,判断结束;
其中,所述合格三角形为三角形的任一条边为合格边;
所述合格边包括第一类型边、第二类型边、第三类型边和第四类型边;所述第一类型边满足边的两侧端节点互为一跳邻居,所述第二类型边满足边的两侧端节点包含相同的一跳邻居节点,所述第三类型边满足边的两侧端节点包含互为一跳邻居的一跳邻居节点;所述第四类型边满足第二三角形集合内不存在以第四类型边的端节点以及第三节点为顶点的三角形,所述第三节点为第四类型边两侧端节点通信的最短路径上的节点;
所述第四判断模块判定所述第四类型边的过程为:
判断第二三角形集合中是否存在以判定边的端节点以及第三节点为顶点的三角形;若不存在,判定边为第四类型边,判断结束;所述以判定边的端节点以及第三节点为顶点的三角形,包括以判定边两侧端节点以及一个第三节点为顶点的三角形,和以判定边一侧端节点以及两个第三节点为顶点的三角形;
若存在,判断所述判定边是否为凹边;若不是,判定边为第四类型边,判断结束;
所述凹边的判定原理为:判定节点周围存在一个紧靠所述以判定边的端节点以及第三节点为顶点的三角形的U型环,并且判定节点位于U型环外的凹陷处;当判定边为凹边,且凹边的两个端点位于U型环的两个端点处,三角形除该凹边两个端点以外的第三个节点位于U型环上除端点以外的位置,则该判定节点为边界节点。
3.一种基于三角形内点测试的边界节点判定装置,其特征在于,包括处理器,所述处理器用于执行存储在存储器中的以下程序模块:第一构建模块,用于构建第一节点集合,所述第一节点集合为无线网络中任一节点A在其通信范围内所有一跳邻居节点的集合;
第一判断模块,用于判断第一节点集合中一跳邻居节点的数量,若一跳邻居节点的数量小于3,节点A为边界节点,判断结束,否则进入以下步骤;
第一发送模块,用于发送第一节点集合至集合内所有一跳邻居节点,以便获取第一节点集合中任一一跳邻居节点在其通信范围内与节点A共享的一跳邻居节点的标识和数量;
第二构建模块,用于构建第二节点集合,所述第二节点集合为第一节点集合中不包含与节点A共享一跳邻居节点数量小于2的一跳邻居节点;
第三构建模块,用于构建第一三角形集合,所述第一三角形集合为遍历第二节点集合内任意3个一跳邻居节点构成的所有三角形;
第二判断模块,用于判断第一三角形集合内三角形的数量,若第一三角形集合为空集,节点A为边界节点,判断结束,否则进入以下步骤;
第四构建模块,用于构建第二三角形集合,所述第二三角形集合为第一三角形集合中根据三角形内点测试法测试获得的围绕节点A的所有三角形;
第三判断模块,用于判断第二三角形集合内三角形的数量,若第二三角形集合为空集,节点A为边界节点,判断结束,否则进入以下步骤;
第四判断模块,用于判断第二三角形集合内是否存在合格三角形,若第二三角形集合内不存在任一合格三角形,则节点为A边界节点,判断结束;
其中,所述合格三角形为三角形的任一条边为合格边;
所述合格边包括第一类型边、第二类型边、第三类型边和第四类型边;所述第一类型边满足边的两侧端节点互为一跳邻居,所述第二类型边满足边的两侧端节点包含相同的一跳邻居节点,所述第三类型边满足边的两侧端节点包含互为一跳邻居的一跳邻居节点;所述第四类型边满足第二三角形集合内不存在以第四类型边的端节点以及第三节点为顶点的三角形,所述第三节点为第四类型边两侧端节点通信的最短路径上的节点;
所述第四判断模块判定所述第四类型边的过程为:
判断第二三角形集合中是否存在以判定边的端节点以及第三节点为顶点的三角形;若不存在,判定边为第四类型边,判断结束;所述以判定边的端节点以及第三节点为顶点的三角形,包括以判定边两侧端节点以及一个第三节点为顶点的三角形,和以判定边一侧端节点以及两个第三节点为顶点的三角形;
若存在,判断所述判定边是否为凹边;若不是,判定边为第四类型边,判断结束;
所述凹边的判定原理为:判定节点周围存在一个紧靠所述以判定边的端节点以及第三节点为顶点的三角形的U型环,并且判定节点位于U型环外的凹陷处;当判定边为凹边,且凹边的两个端点位于U型环的两个端点处,三角形除该凹边两个端点以外的第三个节点位于U型环上除端点以外的位置,则该判定节点为边界节点。
4.一种计算机可读存储介质,所述计算机可读存储介质存储有计算机程序,其特征在于,所述计算机程序被处理器执行时实施如权利要求1所述的基于三角形内点测试的边界节点判定方法。