一种基于质心定位改进的无线传感器网络节点定位算法

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN112462329A(43)申请公布日2021.03.09(21)申请号202011137808.6(22)申请日2020.10.22(71)申请人南京邮电大学地址210003江苏省南京市鼓楼区新模范马路66号(72)发明人万新旺　李逸玮　张海成　董帅　王鹤　(74)专利代理机构南京苏高专利商标事务所(普通合伙)32204代理人曹坤(51)Int.Cl.G01S5/12(2006.01)H04W64/00(2009.01)H04W84/18(2009.01)权利要求书2页说明书6页附图6页(54)发明名称一种基于质心定位改进的无线传感器网络节点定位算法(57)摘要本发明公开了一种基于质心定位改进的无线传感器网络节点定位算法。属于无线传感器网络应用技术领域，具体步骤：(1.1)、无线传感器网络的初始化；(1.2)、建立自身信标节点信息，构成初步的定位三角形区域ABC；(1.3)、切割三角形区域ABC形成若干个子区域，构建阶次序列表，选择相关度最高的子区域作为未知节点的定位区域1；(1.4)、通过RSSI测距得到未知节点与3个信标节点间的距离，将其作为未知节点的定位区域2；(1.5)、判断得到的定位区域1与定位区域2是否相交。本发明相较于经典质心节点定位以及二次质心定位，降低误差率，提高定位的准确性。这种算法的实现，有效地缩小了未知节点定位区域的大小。CN112462329ACN112462329A权　利　要　求　书1/2页1.一种基于质心定位改进的无线传感器网络节点定位算法，其特征在于，具体步骤包括如下：步骤(1.1)、无线传感器网络的初始化：通过信标节点向未知节点广播消息；使用未知节点接收并来自各信标节点的RSSI值；步骤(1.2)、未知节点将其接收到的所有信标节点按照其接收到的RSSI值的大小进行排序，建立自身信标节点信息表，选择RSSI值最大的3个信标节点A,B,C，构成初步的定位三角形区域ABC；步骤(1.3)、切割三角形区域ABC形成若干个子区域，构建阶次序列表；未知节点根据RSSI值确定自身的阶次序列，搜索阶次序列表，选择相关度最高的子区域作为未知节点的定位区域1；步骤(1.4)、通过RSSI测距得到未知节点与3个信标节点间的距离，并分别以3个距离为半径作圆，得到三圆的交点，连接交点得到一个体积小的三角形，将其作为未知节点的定位区域2；步骤(1.5)、判断得到的定位区域1与定位区域2是否相交，若相交，则取重叠区域质心为未知节点的估计位置，否则取定位区域1的质心与定位区域2的质心的中点为估计位置。2.根据权利要求1所述的一种基于质心定位改进的无线传感器网络节点定位算法，其特征在于，在步骤(1.1)中，所述未知节点接收到的广播消息包括各信标节点在网络中的ID及自身坐标信息。3.根据权利要求1所述的一种基于质心定位改进的无线传感器网络节点定位算法，其特征在于，在步骤(1.3)中，所述通过优化质心定位的定位区域1的计算过程包括：(1.3.1)、通过中垂线划分定位区域为含点、边和面3种类型的子区域，计算每个子区域的质心到信标节点间的欧氏距离,对得到的距离值按照升序进行排列从而得到唯一的一条阶次序列，构建阶次序列表；(1.3.2)、未知节点确定自身的阶次序列后，通过统计学中的Kendall的Tau指标搜索阶次序列表选择相关度最高的子区域。4.根据权利要求1所述的一种基于质心定位改进的无线传感器网络节点定位算法，其特征在于，在所述步骤(1.4)中，通过RSSI测距得到未知节点与3个信标节点间的距离，其如下式所述：式中，d0为单位距离；d为信标节点到未知节点的距离，Pt为发射节点的发射功率，PL(d0)为经过单位距离后的路径损耗，n为信号衰减因子，Xσ表示均值为0，差为σ的高斯随机数；分别以3个距离为半径作圆，其具体如下式所述：2CN112462329A权　利　要　求　书2/2页式中，三个已知信标节点的坐标分别为A(xA,yA),B(xB,yB),C(xC,yC),未知节点坐标假设为(x,y),未知节点到各信标节点之间的距离分别为dA,dB,dC。5.根据权利要求1所述的一种基于质心定位改进的无线传感器网络节点定位算法，其特征在于，在所述步骤(1.5)中，判断得到的定位区域1与定位区域2是否相交具体是引入对三个信标节点RSSI测距得到的三边质心定位区域2与定位区域1求重叠区域，通过缩小定位区域，提高其定位精度。3CN112462329A说　明　书1/6页一种基于质心定位改进的无线传感器网络节点定位算法技术领域[0001]本发明属于无线传感器网络应用技术领域，具体涉及一种无线传感器网络节点定位方法，特别是用于解决质心定位算法定位区域过大，定位精度低的问题。背景技术[0002]随着无线传感器网络(Wireless Sensor Network,WSN)与物联网(Internet of Things，LoT)技术的飞速发展，无线传感器凭借其体积小、耗能低、价格低且拥有通信、储存甚至移动的特点，被广泛应用于我们生活的方方面面，诸如军事侦察、医院检测、智能家居、环境感知等领域。其中，无线传感器网络的定位是至关重要的一部分。[0003]在无线传感器网络定位算法中，按照是否需要凭借测距分为基于测距的(range-based)和非基于测距的(Range-free)定位算法。基于测距的定位算法主要包括：接收信号强度定位(Received Signal Strength Indicator,RSSI)，信号传输时间定位(Time Of Arrival,TOA)，信号到达时间差定位(Time Difference Of Arrival,TDOA)，信号到达角度定位(Angle Of Arrival,AOA)；非基于测距的定位算法主要包括：质心算法(Centroid Localization,CL)，距离矢量跳数算法(Distance Vector Hop,DV-Hop)，近似三角形内点测试算法(Approximate PIT Test,APIT)。[0004]质心定位算法是一种基于网络连通性的定位算法。信标节点周期性地向邻居节点广播包含自身标识和位置信息的数据包，当未知节点接收到来自某一信标节点的数据包数量超过某个值或接收一定的时间后，就确定该信标节点处于自身的通信范围内，并将其通信范围内的所有信标节点构成的几何质心作为自身的估计位置。为了减少运算量，质心算法一般取接收到的信号能量值较大的三个信标节点构成三角形，将三角形的质心作为未知节点的估计位置。[0005]质心定位算法的误差主要来源于未知节点所在区域过大以及信标节点分布的不均匀性。一方面，质心算法直接定义未知节点所在区域质心为估计坐标，当信标节点距离较远时，区域过大会导致误差较大；另一方面，当信标节点分布不均匀的时候，质心定位算法的定位精度会大幅下降。发明内容[0006]针对上述问题，本发明提供了一种基于质心定位改进的无线传感器网络节点定位算法；在现有质心定位方法基础上进行改进，该方法引入阶次序列划分法以及RSSI测距，大大缩小了质心算法中未知节点所在区域的大小，有效地提高了节点定位精度。[0007]本发明的技术方案是：一种基于质心定位改进的无线传感器网络节点定位算法，具体步骤包括如下：[0008]步骤(1.1)、无线传感器网络的初始化：通过信标节点向未知节点广播消息；使用未知节点接收并记录来自各信标节点的RSSI值；[0009]步骤(1.2)、未知节点将其接收到的所有信标节点按照其接收到的RSSI值的大小4CN112462329A说　明　书2/6页进行排序，建立自身信标节点信息表，选择RSSI值最大的3个信标节点A,B,C，构成初步的定位三角形区域ABC；[0010]步骤(1.3)、切割三角形区域ABC形成若干个子区域，构建阶次序列表；未知节点根据RSSI值确定自身的阶次序列，搜索阶次序列表，选择相关度最高的子区域作为未知节点的定位区域1；[0011]步骤(1.4)、通过RSSI测距得到未知节点与3个信标节点间的距离，并分别以3个距离为半径作圆，得到三圆的交点，连接交点得到一个体积小的三角形，将其作为未知节点的定位区域2；[0012]步骤(1.5)、判断得到的定位区域1与定位区域2是否相交，若相交，则取重叠区域质心为未知节点的估计位置，否则取定位区域1的质心与定位区域2的质心的中点为估计位置。[0013]进一步的，在步骤(1.1)中，所述未知节点接收到的广播消息包括各信标节点在网络中的ID及自身坐标信息。[0014]进一步的，在步骤(1.3)中，所述通过优化质心定位的定位区域1的计算过程包括：[0015](1.3.1)、通过中垂线划分定位区域为含点、边和面3种类型的子区域，计算每个子区域的质心到信标节点间的欧氏距离,对得到的距离值按照升序进行排列从而得到唯一的一条阶次序列，构建阶次序列表；[0016](1.3.2)、未知节点确定自身的阶次序列后，通过统计学中的Kendall的Tau指标搜索阶次序列表选择相关度最高的子区域。[0017]进一步的，在所述步骤(1.4)中，通过RSSI测距得到未知节点与3个信标节点间的距离，其如下式所述：[0018][0019]式中，d0为单位距离；d为信标节点到未知节点的距离，Pt为发射节点的发射功率，PL(d0)为经过单位距离后的路径损耗，n为信号衰减因子，Xσ表示均值为0，标准差为σ的高斯随机数；[0020]分别以3个距离为半径作圆，其具体如下式所述：[0021][0022]式中，三个已知信标节点的坐标分别为A(xA,yA),B(xB,yB),C(xC,yC),未知节点坐标假设为(x,y),未知节点到各信标节点之间的距离分别为dA,dB,dC。[0023]进一步的，在所述步骤(1.5)中，判断得到的定位区域1与定位区域2是否相交具体是引入对三个信标节点RSSI测距得到的三边质心定位区域2与定位区域1求重叠区域，通过缩小定位区域，提高其定位精度。[0024]本发明的有益效果是：本发明相较于经典质心节点定位以及二次质心定位，降低误差率，提高定位的准确性。这种算法的实现，有效地缩小了未知节点定位区域的大小。5CN112462329A说　明　书3/6页附图说明[0025]图1为本发明的方法流程图；[0026]图2为经过阶次序列划分后三种情况的三角形质心区域图；[0027]图3为RSSI测距得到的四种情况的三边质心区域图；[0028]图4为锐角三角形下经过阶次划分后的质心区域与三边质心区域求重叠区域的示意图；[0029]图5为本发明在监测区域的节点分布示意图；[0030]图6为锚节点密度25％情况下本发明方法与经典质心定位方法以及二次质心定位方法的定位误差比较图；[0031]图7为锚节点密度25％情况下本发明方法与经典质心定位方法以及二次质心定位方法的定位误差区间图；[0032]图8为本发明方法与经典质心定位方法以及二次质心定位方法不同锚节点密度下的定位误差比较图；[0033]图9为本发明方法与经典质心定位方法以及二次质心定位方法不同噪声大小下的定位误差比较图。具体实施方式[0034]为了更清楚地说明本发明的技术方案，下面结合附图对本发明的技术方案做进一步的详细说明：[0035]如图1所示，一种基于质心定位改进的无线传感器网络节点定位算法，其在于引入阶次序列划分法以及RSSI测距，具体步骤包括如下：[0036]步骤(1.1)、无线传感器网络的初始化：通过信标节点向未知节点广播消息；使用未知节点接收并记录来自各信标节点的RSSI值；[0037]步骤(1.2)、未知节点将其接收到的所有信标节点按照其接收到的RSSI值的大小进行排序，建立自身信标节点信息表，选择RSSI值最大的3个信标节点A,B,C，构成初步的定位三角形区域ABC；[0038]步骤(1.3)、切割三角形区域ABC形成若干个子区域，构建阶次序列表；未知节点根据RSSI值确定自身的阶次序列，搜索阶次序列表，选择相关度最高的子区域作为未知节点的定位区域1；[0039]步骤(1.4)、通过RSSI测距得到未知节点与3个信标节点间的距离，并分别以3个距离为半径作圆，得到三圆的交点，连接交点得到一个体积小的三角形，将其作为未知节点的定位区域2；[0040]步骤(1.5)、判断得到的定位区域1与定位区域2是否相交，若相交，则取重叠区域质心为未知节点的估计位置，否则取定位区域1的质心与定位区域2的质心的中点为估计位置。[0041]进一步的，在步骤(1.1)中，所述未知节点接收到的广播消息包括各信标节点在网络中的ID及自身坐标信息。[0042]如图2(a)、(b)、(c)所示，在步骤(1.3)中，所述通过优化质心定位的定位区域1的计算过程包括：6CN112462329A说　明　书4/6页[0043](1.3.1)、利用有效三角形的三条中垂线将三角形ABC进行分割，由参考点间连线的垂直平分线切割定位三角形区域为含点、边和面3种类型的子区域，计算每个子区域的质心到信标节点间的欧氏距离，对得到的距离值按照升序进行排列，并将排序值填入对应信标节点的位置，从而得到唯一的一条阶次序列，所有的阶次序列构成了定位空间的阶次序列表；[0044](1.3.2)、未知节点根据RSSI值确定自身的阶次序列，其中当两点的RSSI差值小于阈值时，判断这两点的阶次相同，搜索阶次序列表，通过统计学中的Kendall的Tau指标选择相关度最高的子区域作为未知节点的定位区域1；[0045]具体的，如图2(a)中锐角三角形分为6个面区域，5个线区域以及1个点区域，图中子区域1为面子区域，其质心离C最近，A次之，B最远，故其阶次序列为231；子区域2为线子区域，其质心离A最近，离B,C距离相同，故其阶次序列为122；子区域3为点子区域，其质心离A，B,C距离相同，故其阶次序列为111；类似的可以把图2(b)直角三角形分为4个面区域，3个线区域以及1个点区域，图2(c)钝角三角形分为4个面区域，3个线区域；得到阶次序列表后，未知节点根据A,B,C三个信标节点的RSSI值确定自身的阶次序列，如RSSIA