基于超宽带的无线传感器网络节点定位方法

摘要

本发明公开了一种基于超宽带的无线传感器网络节点定位方法，本发明用超宽带作为无线传感器节点的通信介质，通过正常的数据包收发测得节点对之间的无线信号强度指示值，采用非度量多维标度技术直接利用节点间的无线信号强度指示值进行定位。其中定位算法分为三大阶段：以簇为单位的局部相对坐标图定位阶段、局部图合并为全局相对坐标图阶段和相对坐标图到绝对坐标图的转换阶段。本发明结合了超宽带抗多径与干扰能力强、抗截获性好等诸多优点，使定位具有成本低、高精度、灵活性大等特点。

说明书

技术领域

本发明涉及超宽带(UWB)技术与无线传感器网络节点定位技术，具体是一种基于超宽带的无线传感器网络节点定位方法。

背景技术

节点的准确定位是无线传感器网络应用的重要条件。获得节点位置的一个直接想法是使用全球定位系统(GPS)来实现，但是在无线传感器网络中使用GPS来获得所有节点的位置受到价格、体积、功耗等因素限制，存在着一些困难，另外GPS也很难应用于室内无线传感器网络。根据定位机制，可将现有的无线传感器网络自身定位算法分为两类：Range-based和Range-free，即基于测距技术的定位算法和无需测距的定位算法。前者通过测量节点间点到点的距离或者角度信息，使用三边测量法、三角测量法或最大似然估计法计算节点位置；后者无需距离和角度信息，仅根据网络连通性等信息实现。无需测距定位机制在成本、功耗等方面具有优势，但精度较低，主要算法包括质心算法、凸规划算法、DV-Hop、Amorphous、MDS-MAP和APIT算法等。

超宽带(UWB)通信技术是一种非传统的、新颖的无线传输技术，它通常采用极窄脉冲或极宽的频谱传送信息。相对于传统的正弦载波通信系统，UWB无线通信系统具有高传输速率、高空间频谱效率、高测距精度、低截获概率、抗多径干扰等诸多优点。

发明内容

针对现有技术的缺陷，本发明提供一种基于超宽带的无线传感器网络节点定位方法，它结合了超宽带抗多径与干扰能力强、抗截获性好等优点，具有定位成本低、高精度、灵活性大等特点。

本发明提供的这种基于超宽带的无线传感器网络节点定位方法，利用超宽带作为传感器节点的底层无线通信介质，在无线传感节点与邻节点进行通信时，通过正常的数据包收发测得节点对之间的无线信号强度指示值，采用非度量多维标度技术，直接利用节点间的无线信号强度指示值来进行定位，其中定位算法分为三个阶段：以簇为单位的局部相对坐标图定位阶段、局部相对坐标图合并为全局相对坐标图阶段和相对坐标图到绝对坐标图的转换阶段。

进一步，其中局部相对坐标图定位阶段在节点上完成，一个簇包含的范围是该节点的一跳邻居节点，步骤包括：

1)在网络的边界处设定若干节点作为路由的终止节点，由sink节点作为始发节点发起洪泛路由，当碰到终止节点时，该方向上的洪泛结束，由此找到若干条由sink节点到终止节点的路由；

2)包含在每条始发节点到终节点路由上的每个节点分别以它自己为簇的簇首节点，依次加入它的一跳邻居节点进簇；

3)收集簇中各节点对之间的无线信号强度指示值构成稀疏矩阵，如果两个节点的距离超过节点无线通信半径，则对应的值为0；

4)由于簇中的一跳邻居节点不能保证都互相连通，因此利用最短路径算法求得簇中每个节点对之间的信号强度值来构造非度量多维标度中的相似性矩阵；

5)该路由上的每个节点以它自己为簇首，以簇为单位，分别用非度量多维标度计算出簇中包含的所有节点的相对坐标，即为簇局部相对坐标图；

进一步，其中局部相对坐标图合并为全局相对坐标图阶段是将计算出来的簇局部相对坐标图传到sink节点，由与sink节点相连的计算机对其进行合并处理。局部相对坐标图合并为全局相对坐标图时，首先选择一个包含节点最多的簇为起点，作为当前全局图。接下来，每次合并时优先选择与当前全局图的公共节点数最多的簇局部相对坐标图合并，把合并后的图再作为当前全局图，不断合并，直到当前全局图中已包含了所有节点。

进一步，其中合并处理是基于公共节点进行，采用最优线性转换，实现公共节点从一个图到另一个图的变换，公共节点在局图A和局图B中的坐标矩阵分别为X_A和X_B，确定从X_B到X_A的最优线性转换是使得转换前后的差别最小，即满足min_Q‖Q(X_B)-X_A‖²，其中Q为线性转换函数；

进一步，其中合并处理中基于公共节点进行合并时，确定节点X在合并后的新图中的坐标采用以下原则：如果X在图A中而不在图B中，取它在图A的坐标X_A；如果X在图B中而不在图A中，取它转换后的坐标Q(X_B)；如果X为图A和图B的公共节点，取它在图A的坐标X_A与它转换后的坐标Q(X_B)两者的平均值。

进一步地说，其中相对坐标图到绝对坐标图的转换阶段是在与sink相连的计算机上完成，该转换是基于信标节点(少量已知位置的节点)进行的：m个信标节点的相对位置为R＝[r_ij]_2×m＝(R₁，R₂，K，R_m)，其信标节点的真实位置为T＝[t_ij]_2×m＝(T₁，T₂，K，T_m)，先求出向量R变到向量T的转换函数Q，再把所有节点的相对坐标乘以转换函数Q得到所有节点的绝对坐标。

本发明的主要原理描述如下：在非度量多维标度中，实体间的相异(似)性只需满足一定的顺序等级关系，而不需要定量地表示出来。根据各实体间的相异性在多维空间上重构这些实体对应的点坐标时，满足各实体间的相异性p_ij与对应各点间的距离d_ij(X)保持相同的顺序等级关系，即对于任意i、j、k、l，如果p_ij＜p_kl，那么d_ij(X)＜d_kl(X)。选用无线信号强度来定位，是因为它相对于其它方法如信号到达时间差、信号到达角度等来说，对硬件要求最简单，满足低成本的要求，并且在无线传感节点与邻节点进行通信时，通过正常的数据包收发就能测得其无线信号强度指示值。超宽带由于具有多径分辨能力、抗干扰能力、穿透能力强的特点，使得它在复杂环境下能取得更准确得信号强度值。而无线信号传播通常具有以下特性：接收点离发送方越近，测得的信号强度越强；接收点离发送方越远，测得的信号强度越弱。无线信号强度指示值与距离的这种单调关系正好满足非度量多维标度中实体间相异性数据的要求，因此利用这个特性提出直接在节点间的无线信号强度值上运用非度量多维标度算法来定位节点。

运用非度量多维标度算法进行定位分为三个阶段：以簇为单位的局部相对坐标图定位阶段、局部图合并为全局相对坐标图阶段和相对坐标图到绝对坐标图的转换阶段：

1)在网络的边界处设定若干节点作为路由的终止节点，由sink节点作为始发节点发起洪泛路由，当碰到终止节点时，该方向上的洪泛结束，由此找到若干条由sink节点到终止节点的路由；

2)包含在每条始发节点到终节点路由上的每个节点分别以它自己为簇的簇首节点，依次加入它的一跳邻居节点进簇；

3)收集簇中各节点对之间的无线信号强度指示值构成稀疏矩阵，如果两个节点的距离超过节点无线通信半径，则对应的值为0；

4)由于簇中的一跳邻居节点不能保证都互相连通，所以利用最短路径算法求得簇中每个节点对之间的信号强度值来构造非度量多维标度中的相似性矩阵；

5)该路由上的每个节点以它自己为簇首，以簇为单位，分别用非度量多维标度计算出簇中包含的所有节点的相对坐标，即为簇局部相对坐标图；

6)计算出来的簇局部相对坐标图传到sink节点，由与sink节点相连的计算机进行合并处理；

7)在与sink相连的计算机上完成相对坐标图到绝对坐标图的转换阶段。

本发明结合了超宽带抗多径与干扰能力强、抗截获性好等优点，具有定位成本低、高精度、灵活性大等特点。

附图说明

图1是本发明的节点定位方法的流程图。

图2是本发明的簇形成的示意图。

图3本发明的实施例中簇2的局部相对坐标图。

图4本发明的实施例中簇1的局部相对坐标图。

图5本发明的实施例中合并坐标图。

图6为本发明最终的定位结果。

具体实施方式

下面，参照附图说明本发明的实施方式。

图1是本发明的节点定位方法的流程图。本定位算法分为三个阶段：以簇为单位的局部相对坐标图定位阶段、局部相对坐标图合并为全局相对坐标图阶段和相对坐标图到绝对坐标图的转换阶段。其具体步骤包括：

1)在网络的边界处设定若干节点作为路由的终止节点。由sink节点作为始发节点发起洪泛路由，当碰到终止节点时，该方向上的洪泛结束，由此找到若干条由sink节点到终止节点的路由；

2)包含在每条始发节点到终节点路由上的每个节点分别以它自己为簇的簇首节点，依次加入它的一跳邻居节点进簇；

3)收集簇中各节点对之间的无线信号强度指示值构成稀疏矩阵，如果两个节点的距离超过节点无线通信半径，则对应的值为0；

4)由于簇中的一跳邻居节点不能保证都互相连通，所以利用最短路径算法求得簇中每个节点对之间的信号强度值来构造非度量多维标度中的相似性矩阵；

5)该路由上的每个节点以它自己为簇首，以簇为单位，分别用非度量多维标度计算出簇中包含的所有节点的相对坐标，即为簇局部相对坐标图；

6)计算出来的簇局部相对坐标图传到sink节点，与sink节点相连的计算机对其进行合并处理；

7)在与sink相连的计算机上完成相对坐标图到绝对坐标图的转换阶段。

图2是本发明的簇形成示意图。图中16个节点放置成字母L型的不规则网格形状，节点的无线通信半径为9，节点之间的连线表示连通情况。其中节点1为sink节点，在网络的边界处设置节点5和节点15为终止节点。由sink节点1发起洪泛路由，找到始发节点1到终止节点5和15的路由分别为1→3→5和1→11→15。沿每条由始发节点到终止节点的路由上的每个节点分别为节点1、3、5、11、15，以自己为簇首节点，依次加入它的一跳邻居节点进簇，由此形成5个簇，在图中分别用5个圆表示。由节点1为簇首的簇1包含节点1、2、3、6、7、8、11、12，由节点3为簇首的簇2包含节点1、2、3、4、5、6、7、8、9、10、12，由节点5为簇首的簇3包含节点3、4、5、8、9、10，由节点11为簇首的簇4包含节点1、2、6、7、8、11、12、13、14、15、16，由节点15为簇首的簇5包含节点11、12、13、14、15、16。对5个簇分别用非度量多维标度计算簇局部相对坐标。

图3是以节点3为簇首的簇2的局部相对坐标图，图4是以节点1为簇首的簇1的局部相对坐标图。簇局部相对坐标图合并时以包含节点数目最多的簇为基准，选择与之公共节点最多的簇进行合并。图中以簇2为基准，公共节点从簇1到簇2的最优线性转换函数为

$Q(x,y)=\left(\begin{array}{cc}x& y\end{array}\right)\left(\begin{array}{cc}0.687& -0.444\\ 0.444& 0.687\end{array}\right)+\left(\begin{array}{cc}-48.096& 5.591\end{array}\right)$

图5为两个簇局部相对坐标图合并以后的坐标，其中簇1和簇2的公共节点1、2、3、6、7、8、12合并以后的坐标取它们在簇2的坐标X₂与簇1转换后的坐标Q(X₁)两者的平均值；节点4、5在簇2中而不在簇1中，取它原来在簇2的坐标X₂；节点11在簇1中而不在簇2中，取它转换后的坐标Q(X₁)。

图6为最终的定位结果。图中选取节点7、10、16为三个位置已知的信标节点，用五角星表示，带箭头的实线表示估计的位置与真实位置的误差。3个信标节点的相对位置为$R={\left[r_{\mathrm{ij}}\right]}_{2\times m}=\left(\begin{array}{cc}0& -20.96\\ 121.63& 49.58\\ -121.63& 49.58\end{array}\right),$其信标节点的真实位置为$T={\left[t_{\mathrm{ij}}\right]}_{2\times m}=\left(\begin{array}{cc}4& 4\\ 16& 4\\ 4& 16\end{array}\right),$先求出向量R变到向量T的最优转换函数Q，再把所有节点的相对坐标通过转换函数Q得到所有节点的绝对坐标，其中转换函数Q为

$Q(x,y)=\left(\begin{array}{cc}x& y\end{array}\right)\left(\begin{array}{cc}0.053& -0.053\\ 0.053& 0.053\end{array}\right)+\left(\begin{array}{cc}6.621& 6.621\end{array}\right).$