未知节点利用多跳节点缩小其可能位置区域的定位方法

摘要

本发明公开了一种未知节点利用多跳节点缩小其可能位置区域的定位方法，大体思路为：未知节点利用其锚点邻居和未知节点邻居相对于自己的虚拟通信圆以及锚点邻居和未知节点邻居的必然通信圆分别与未知节点的当前可能位置区域之间的位置关系来不断缩小未知节点的可能位置区域。未知节点遍历所有锚点邻居后，再遍历所有未知节点邻居，当未知节点的可能位置区域不再变化时，计算出此时未知节点的可能位置区域的质心作为未知节点的估计位置。本发明利用了网络中所有多跳节点来进行未知节点的可能位置区域的消除，有效地提高了定位精度；本发明基于对凸多边形的运算，计算量小，可以有效减小节点及网络的能量消耗，延长网络的生命周期。

主权项

一种未知节点利用多跳节点缩小其可能位置区域的定位方法，其特征在于包括以下步骤：步骤一、未知节点将假设为矩形的整个网络区域作为其初始可能位置区域；步骤二、未知节点搜集其在矩形网络区域中所有锚点邻居的位置信息以及这些锚点邻居距离自己的跳数信息；步骤三、未知节点按照每个锚点邻居到自己的跳数从小到大的顺序依次遍历自己的所有锚点邻居，未知节点对每个锚点邻居的处理过程具体为：A、求出锚点邻居相对于未知节点的虚拟通信圆；B、若该虚拟通信圆与未知节点的当前可能位置区域为部分相交，则继续执行C步骤；若该虚拟通信圆包含未知节点的当前可能位置区域，则不再作任何处理，直接跳到下一个锚点邻居；C、找到未知节点的当前可能位置区域位于该虚拟通信圆外的所有顶点，并将这些顶点与锚点邻居的位置坐标分别连接成直线；D、通过这些直线与虚拟通信圆的交点分别作虚拟通信圆的切线，这些切线分别将未知节点的当前可能位置区域切分为两部分；E、未知节点分别以这些切线为分界线，消除远离该虚拟通信圆的当前可能位置区域的部分，将剩余部分作为更新后的当前可能位置区域；步骤四、未知节点按照每个锚点邻居到自己的跳数从小到大的顺序依次遍历自己所有跳数大于1的锚点邻居，未知节点对每个锚点邻居的处理过程具体为：A、未知节点根据自己当前可能位置区域求出当前可能位置圆，并求出锚点邻居的必然通信圆；B、若该必然通信圆与未知节点的可能位置圆有交集区域，则继续执行C步骤；若该必然通信圆与未知节点当前的可能位置区域无交集区域，则不再作任何处理，直接跳到下一个锚点邻居；C、求出该必然通信圆与未知节点的当前可能位置圆的两个交点所在直线，该直线将未知节点的当前可能位置区域切分为两部分；D、未知节点以该直线为分界线，消除靠近必然通信圆的当前可能位置区域的部分，将剩余部分作为更新后的当前可能位置区域；步骤五、未知节点搜集其在矩形网络区域中所有未知节点邻居的当前可能位置区域信息以及这些未知节点邻居距离自己的跳数信息；步骤六、未知节点按照每个未知节点邻居距离自己的跳数从小到大的顺序依次遍历所有未知节点邻居，未知节点对每个未知节点邻居的处理过程具体为：A、求出未知节点邻居当前相对于未知节点的虚拟通信圆；B、若该虚拟通信圆与未知节点的当前可能位置区域为部分相交，则继续执行C步骤；若该虚拟通信圆包含未知节点的当前可能位置区域，则不做任何处理，直接跳到下一个未知节点邻居；C、找到未知节点的当前可能位置区域位于该虚拟通信圆外的所有顶点，并将这些顶点与该虚拟通信圆的圆心分别连接成直线；D、通过这些直线与虚拟通信圆的交点作虚拟通信圆的切线，这些切线将未知节点的当前可能位置区域切分为两部分；E、未知节点分别以这些切线为分界线，消除远离该虚拟通信圆的当前可能位置区域的部分，将剩余部分作为更新后的当前可能位置区域；步骤七、未知节点按照每个未知节点邻居距离自己的跳数从小到大的顺序依次遍历所有跳数大于1的未知节点邻居，未知节点对每个未知节点邻居的处理过程具体为：A、未知节点根据自己当前的可能位置区域求出当前可能位置圆，并求出未知节点邻居当前相对于未知节点的必然通信圆；B、若该必然通信圆与未知节点的当前可能位置区域有交集区域，则继续执行C步骤；若该必然通信圆与未知节点的当前可能位置区域无交集区域，则不做任何处理，直接跳到下一个未知节点邻居；C、求出必然通信圆与自己的当前可能位置圆的两个交点所在直线，该直线将未知节点的当前可能位置区域切分为两部分；D、未知节点分别以该直线为分界线，消除靠近必然通信圆的当前可能位置区域的部分，将剩余部分作为更新后的当前可能位置区域；步骤八、未知节点将自己更新后的当前可能位置区域广播给其他未知节点邻居，其他未知节点邻居根据本未知节点当前的可能位置区域更新自己的可能位置区域，然后再分别将结果广播给本未知节点，如此反复计算，一直到网络中所有未知节点的可能位置区域不再变化；步骤九、未知节点计算最后得到的可能位置区域的质心坐标，作为该未知节点的估计位置。