无线定位系统中最佳基站布设方法

摘要

本发明公开了无线定位系统中最佳基站布设方法，该方法根据无线传感器网络基站布设最优化求解的实际问题，提出用TFBCSS法和网格搜索法求解最优化模型，从而保证基站布设最优结果的有效性，可靠性。由于不同轨迹段对精度的要求不同，将基站布设问题转化为字典分层规划(LSP)模型，根据定位系统要求或根据基站布设中信号覆盖问题可得基站布设问题的可行域。用平均几何精度因子(GDOP)作为LSP模型的评价标准，运用宽容完全分层序列法(TFBCSS)和网格搜索法求出最优解，从而得出可能的最佳基站布设。LSP模型的应用，使得本发明适用于更多的应用场景，诸如不同轨迹段有不同精度要求这样的场景。从仿真结果可知，在给定轨迹情况下，本方法比已有方法有更好的基站布设结果。

说明书

技术领域

本发明涉及一种无线定位系统中最佳基站布设方法，属于通信定位技术领域。

背景技术

无线传感器网络(WirelessSensorNetworks,WSNs)是继互联网之后，对人类社会的生产，生活方式产生重大影响的一项重要技术。传感器网络技术是21世纪最具影响的二十一项技术之一，是对未来生活产生深远影响的十大新兴技术。2006年，我国发布的<<国家中长期科学与技术发展规划纲要>>中也将传感器技术列为信息技术的三个前沿方向之一。

作为一项全新的信息获取和处理技术，WSNs在全球范围内获得了广泛的研究与关注。目前WSNs在环境监测，目标跟踪，智能交通，入侵监测等定位相关领域得到了应用。在上述应用中，目标的位置信息对数据获取至关重要。因此，定位功能是WSNs应用中的关键技术之一。由于在功耗和器件复杂性上的限制，无线传感器的测量精度往往不是很高。无线传感器网络上发展的定位技术由于其网络器件本身的性质限制了其应用。因此，在无线传感器网络中定位精度是制约其应用的一个瓶颈性难题，至今未见突破性进展。

我们都知道，无线传感器定位系统的定位性能主要取决于下面几个要素：正确的测量参数估计(如接收时间，接收信号能量，接收角度等)，定位算法选择，目标节点和基站之间的几何关系。也就是说，对于给定的WSNs，定位性能仅仅跟定位方法选择和基站布设有关。因此，新的基站布设算法和技术将会进一步提高传感器网络的定位性能，进一步拓宽其应用领域和范围。

目前国内外的许多专家学者开展了针对定位系统基站布设的算法研究。对于单个的定位点下，B.Yang主要研究了通过最小化克拉美罗界(CRB)来设计基站位置，并且获得了在无限制条件下，基站布设的充分必要条件。对于给定的单个点，均匀角度阵列(uniformangulararrayUAA)模式是最优的基站布设。随后，他又讨论比较了不同的基站设置方法，如最大化Fisher信息矩阵，最小化CRLB等。对于给定定位区域的条件下，N.Salman给出了在矩形定位区域下，通过最小化CRB均值得到的3,4,5基站下的位置布设结果。A.Bais研究了通过最大化信号收敛区域和最小化定位错误准则下的基站布设问题。FBenbadis比较了在多跳定位系统下，基站均匀分布和基站随机分布下的位置估计结果。针对目标节点是轨迹的情况下，ISharp以几何淡化因子(GDOP)作为基站布设标准，分析了中短距离室外和室内定位系统下，目标节点在特殊轨迹情况下的基站布设问题。

通过进一步文献资料的阅读，我们发现目前的基站布设研究主要还是以单个点和定位区域为研究背景。对于在节点是轨迹的情况下，基站布设算法研究相当匮乏。因此，本发明研究的重点将放在目标节点在轨迹情形下，WSN中基站如何布设。考虑到随着WSN技术的发展，WSN定位将会有更为广泛的应用领域。比如在目标节点轨迹下，不同的轨迹分段区间可能会对应着不同的定位要求。因此，目标节点在不同的轨迹分段区间会有不同的定位要求。基站布设设计应该对于高定位要求的轨迹分段区间应该有高的权重。因此，在无线传感网定位系统中，根据目标在轨迹分段区间的不同的定位要求，将理论的基站布设方法和解决实际应用问题相结合，获得经济高效的定位服务，仍是一个具有挑战性的课题，但通过基站布设算法研究来提高无线传感器网络的定位性能，进而拓宽传感器网络的应用领域不失为一条可行之路。

发明内容

本发明目的在于克服上述现有技术的不足，提出一种无线定位系统中最佳基站布设方法，该方法根据无线传感器网络基站布设最优化求解的实际问题，提出用TFBCSS法和网格搜索法求解最优化模型，从而保证基站布设最优结果的有效性，可靠性。

本发明解决其技术问题所采用的技术方案是：一种无线定位系统中最佳基站布设方法，该方法包括如下步骤：

步骤1：建立基于多目标的基站布设最优化模型；

步骤2：不同轨迹段对精度要求的不同，根据优先级参数将上述基于多目标的基站布设最优化模型进一步转化为基于字典分层规划的基站布设最优化模型；

步骤3：运用宽容完全分层序列法和网格搜索法求出最优解，从而得到最佳基站布设；

步骤4：对基站布设结果进行分析比较，建立无线传感器定位系统基站布设的评价体系。

进一步的，本发明步骤1所述的建立基于多目标的基站布设最优化模型包括：

步骤1-1：用(x_i,y_i)表示第i个基站的坐标位置，其中i1,2,...,n，将(X,Y)作为最优化模型的决策变量：

$>X\stackrel{\Delta }{=}(x_1,x_2,...x_n),Y\stackrel{\Delta }{=}(y_1,y_2,...y_n)$>

步骤1-2：预定义移动台在每段轨迹上接收到N个基站信号，从而得出最优化模型的可行域D(X,Y)：

$>D(X,Y)\stackrel{\Delta }{=}\left(\begin{array}{cc}\left(X,Y\right)|g_m\left(X,Y\right)\ge N& m=1,...M\end{array}\right)$>

其中，$>g_m(X,Y)=\underset{i=1}{\overset{n}{\Sigma }}ϵ\left(\sqrt{{\left(x_i-a_m\right)}^2+{\left(y_i-b_m\right)}^2}-R\right),$>$>ϵ\left(t\right)=\left(\begin{array}{cc}1& t\ge 0\\ 0& t<0\end{array}\right),$>(a_m,b_m)表示第m个移动台的坐标位置，R为基站的覆盖半径，N为基站总数。

步骤1-3：用f_j(x₁,y₁,x₂,y₂,...,x_n,y_n)表示移动台位置点在第j段轨迹上的平均几何精度因子，其中，j1,2,...,L，将平均几何精度因子作为标准来构建最优化模型的目标函数G(X,Y)，即：

$>G(X,Y)\stackrel{\Delta }{=}{\left(f_1\left(X,Y\right),...,f_L\left(X,Y\right)\right)}^T$>

进一步的，本发明步骤2所述的优先级参数是根据不同轨迹段对精度的不同要求而预定义，将基于多目标的基站布设最优化模型转化为基于LSP的基站布设最优化模型，包括：

假定移动台轨迹有k种不同的定位精度要求，则L个目标函数可表示为：

$>f_1^1(x,y),...f_{L_1}^1(x,y);f_1^2(x,y),...f_{L_2}^2(x,y);......f_1^k(x,y),...f_{L_k}^k(x,y);$>

L₁+L₂+...+L_k＝L

在约束条件下的分层多目标极小化问题表示为：

$>L-\underset{(X,Y)\in D}{min}{\left[P_s{F}_s\left(X,Y\right)\right]}_{s=1}^k$>

其中，P_s(s＝1,2…k)是优先层次的符号，表示后面括号中的目标函数属于第s优先层次，并且满足P_s＞＞P_s+1,s＝1,…k,符号“>>”表示第s优先层次优先于第(s+1)优先层次，是定性概念，并非数量关系。符号“L-min”表示按字典序极小化，即依次按P₁,…P_k的顺序逐层地先后极小化，

进一步的，本发明步骤3所述的运用TFBCSS法和网格搜索法求出最优解过程，包括：

步骤3-1：确定初始可行域；

D¹(X,Y)＝D(X,Y),s＝1

步骤3-2：在同一优先层中，通过线性加权和法将F_s(X,Y)转化为单目标最优化函数，因此LSP模型中不同优先层的单目标最优化函数Q_s(X,Y)定义为：

$>Q_s(X,Y)=w_1{f}_1^s(X,Y)+...+w_{L_s}{f}_{L_s}^s(X,Y),s=1,...k,w_1+w_2+...+w_{L_s}=1$>

其中w_i(i＝1,...L_s)为目标函数f_i^s(X,Y)的权重。

步骤3-3：按字典顺序极小化；

$>\underset{(X,Y)\in D^S}{min}{Q}_s(X,Y)$>

利用网格搜索法可求得目标函数Q_s(X^s,Y^s)的最优解(X^s,Y^s)和最优值。

步骤3-4：检验分层数；

当s＝k时，输出(X,Y)＝(X^s,Y^s)，当s<k时，转步骤3-5

步骤3-5：建立下一层次的可行域(即加以宽容)

D^s+1＝{(X,Y)∈D^s|Q_s(X,Y)≤Q_s(X^s,Y^s)+δ_k}

其中δ_k是宽容因子。

令s＝s+1，转步骤3-3。

有益效果：

1.本发明根据目标轨迹不同分段区间上的定位服务/精度要求，从理论上建立基于多目标的基站布设最优化模型。

2.本发明从理论的多目标基站布设最优化模型出发，设计基于实际应用场景的基站布设最优化实际模型。

3.本发明根据无线传感器网络基站布设最优化求解的实际问题，提出用TFBCSS法和网格搜索法求解最优化模型，从而保证基站布设最优结果的有效性，可靠性。

4.本发明在实际基站布设应用模型的基础上，对基站布设结果进行分析比较，从而建立无线传感器定位系统基站布设的评价体系。

附图说明

图1是本发明基站布设方法的总体框架图。

图2是本发明仿真区域和移动台轨迹图。

图3是本发明基站覆盖范围图。

图4是本发明基站布设算法与另外两种算法的GDOP对比示意图。

图5是本发明不同精度要求对基站覆盖范围的影响示意图。

图6是本发明不同精度要求对GDOP的影响示意图。

图7是本发明容限因子对基站覆盖范围的影响示意图。

图8是本发明容限因子对GDOP的影响示意图。

图9是本发明目标轨迹采样间隔对基站覆盖范围的影响示意图。

图10是本发明定位区域采样间隔对基站覆盖范围的影响示意图。

图11是本发明定位区域采样间隔对GDOP的影响示意图。

图12是本发明不同基站布设方法均方根误差(RMSE)的对比示意图。

图13是本发明不同基站布设方法平均RMSE的对比示意图。

具体实施方式

下面结合说明书附图对本发明创造作进一步的详细说明。

如图1所示，本发明具体实施步骤如下：

1.从理论上建立基于多目标的基站布设最优化模型

(1)模型变量：根据本发明需要解决的实际问题，将模型变量定义为需要优化的基站位置，用(x_i,y_i)表示第i个基站的坐标位置，其中i＝1,2,...,n将(X,Y)作为基于多目标的基站布设最优化模型的决策变量：

$>X\stackrel{\Delta }{=}\left(x_1,x_2,\mathrm{...}{x}_n\right),Y\stackrel{\Delta }{=}\left(y_1,y_2,\mathrm{...}{y}_n\right)$>

(2)可行域：与传统的基站布设优化问题不一样，我们并没有把整个给定区域都作为最优化求解的可行域。本发明将可行域限制在能够覆盖定位范围的所有可能基站坐标的集合。也就是说，基站只能布设在给定区域的某些特定的位置上，它必须能够覆盖整个定位范围，用D(X,Y)表示可行域：

$>D(X,Y)\stackrel{\Delta }{=}\left(\begin{array}{cc}\left(X,Y\right)|g_m\left(X,Y\right)\ge N& m=1,...M\end{array}\right)$>

其中$>g_m(X,Y)=\underset{i=1}{\overset{n}{\Sigma }}ϵ\left(\sqrt{{\left(x_i-a_m\right)}^2+{\left(y_i-b_m\right)}^2}-R\right),$>$>ϵ\left(t\right)=\left(\begin{array}{cc}1& t\ge 0\\ 0& t<0\end{array}\right),$>(a_m,b_m)表示第m个移动台的坐标位置，m＝1,2,...M，R为基站的覆盖半径，N为基站总数。

(3)目标函数：用f_j(x₁,y₁,x₂,y₂,...,x_n,y_n)表示移动台在第j段轨迹上的平均GDOP，其中j＝1,2,...,L，选择每条轨迹的平均GDOP作为标准来构建最优化模型的目标函数G(X,Y)：

$>G(X,Y)\stackrel{\Delta }{=}{\left(f_1\left(X,Y\right),...,f_L\left(X,Y\right)\right)}^T$>

2.将字典分层规划(lexicographicalstratifiedprogramming,LSP)模型用于基站布设

为适应不同轨迹段对精度的不同要求，将多目标最优化模型转化为LSP模型，根据精度要求不同给每一段轨迹预定义一个优先级参数。假定移动台轨迹有k个不同的定位精度要求，则L个目标函数可表示为：

$>f_1^1(x,y),...f_{L_1}^1(x,y);f_1^2(x,y),...f_{L_2}^2(x,y);......f_1^k(x,y),...f_{L_k}^k(x,y);$>

L₁+L₂+...+L_k＝L

第一优先层次：$>f_1^1(X,Y),...f_{L_1}^1(X,Y);$>

第二优先层次：$>f_1^2(X,Y),...f_{L_2}^2(X,Y);$>

………，

第k优先层次：$>f_1^k(X,Y),...f_{L_k}^k(X,Y)$>

它们在约束条件下的分层多目标极小化问题记为：

$>L-\underset{(X,Y)\in D}{min}[P_1\left(f_1^1\left(X,Y\right),...f_{L_1}^1\left(X,Y\right)\right),...P_k\left(f_1^k\left(X,Y\right),...f_{L_k}^k\right)]$>

其中P_s(s＝1,2…k)是优先层次的符号，表示后面括号中的目标函数属于第s优先层次，并且满足P_s＞＞P_s+1,s＝1,…k,符号“>>”表示第s优先层次优先于第(s+1)优先层次，是定性概念，并非数量关系。符号“L-min”表示按字典序极小化，即依次按P₁,…P_k的顺序逐层地先后极小化。

令$>F_1(X,Y)=\left(f_1^1\left(X,Y\right),...f_{L_1}^1\left(X,Y\right)\right),F_2\left(X,Y\right)=\left(f_1^2\left(X,Y\right),...f_{L_2}^2\left(X,Y\right)\right)$>

$>,\mathrm{....},F_k(X,Y)=\left(f_1^k\right(X,Y),...f_{L_k}^k(X,Y\left)\right),$>

则上述问题可缩写为：

$>L-\underset{(X,Y)\in D}{min}{\left[P_s{F}_s\left(X,Y\right)\right]}_{s=1}^k$>

至此，本发明建立了基于分层多目标最优化的基站布设模型。

3.LSP模型的求解

为避免中间优先层唯一解的问题，并减少计算复杂性，利用TFCSS法和网格搜索法求解LSP模型最优化问题。基本思路是根据预定义的优先级，按照优先级的先后顺序求解每个目标函数，则最后一层优先层的最优解即为LSP模型的最优解，LSP模型算法步骤，包括如下：

步骤1：确定初始可行域

D¹(X,Y)＝D(X,Y),s＝1

其中D(X,Y)是多目标数学模型的初始可行域。

步骤2:在同一优先层中，通过线性加权和法将F_s(X,Y)转化为单目标最优化函数，因此LSP模型中不同优先层的极小化函数Q_q(X,Y)可定义为：

$>Q_q(X,Y)=w_1{f}_1^q(X,Y)+...+w_{L_q}{f}_{L_q}^q(X,Y)q=1,...{\mathrm{kw}}_1+w_2+...+w_{L_q}=1$>

本发明为了简便，假设同一优先层中每一个目标函数权重相同。

步骤3:按字典顺序极小化

$>\underset{(X,Y)\in D^S}{min}{Q}_s(X,Y)$>

利用网格搜索法可求得Q_s(X^s,Y^s)的最优解(X^s,Y^s)和最优值。

步骤4:检验分层数

当s＝k时，输出(X,Y)＝(X^s,Y^s)，当s<k时，转步骤5.

步骤5:建立下一层次的可行域(加以宽容)

D^s+1＝{(X,Y)∈D^s|Q_s(X,Y)≤Q_s(X^s,Y^s)+δ_k}

令s＝s+1，转步骤3

图2是仿真区域和移动台轨迹，定位区域设为2000m×2000m的方形区域，其中X轴，Y轴的范围都为[0,2000]，划分的网格数为100，在指定的定位区域内一共有4个基站，3条不同的轨迹段，其中基站覆盖半径都是1200m，轨迹段分别为Load1，Load2，Load3，他们对精度的要求分别是高，中，低，长度都为200m，采样间隔都是20m，预定义每条轨迹段上移动台可接收到4个基站信号，容限因子δ_k＝0.1，将上述仿真条件记为例1。为方便性能的比较，算法中只考虑最小平均GDOP，不考虑优先级。

实验1：基站覆盖范围和GDOP性能分析

图3是基站覆盖范围，由图可知，每条轨迹段上移动台都可接收到4个基站信号，与预定义条件相符合，图4是本发明基站布设算法与另外两种算法的GDOP值，由图可知，与无优先级的轨迹段相比，Load1的GDOP值更加接近理论值，即GDOP越小，定位系统的定位性能越高，说明本发明的基站布设算法适用于不同轨迹段有不同精度要求这样的场景。

实验2：稳健性分析

假设Load1，Load2，Load3对精度的要求分别为中，低，高，其他条件与例1相同，将上述仿真条件记为例2。图5是不同精度要求对基站覆盖范围的影响，图6是不同精度要求对GDOP的影响。由图可知，轨迹段的优先级越高，其GDOP值越接近理论值，说明本发明的基站布设算法在不同精度要求下是稳健的。

假设容限因子δ_k＝0.15，其他条件与例1相同，将上述仿真条件记为例3。图7是容限因子对基站覆盖范围的影响，由图可知，容限因子δ_k对基站覆盖范围没有任何影响。图8是容限因子对GDOP的影响，由图可知，随着容限因子δ_k减小，优先级越高的轨迹段其GDOP越接近相应的理论值，优先级低的轨迹段其GDOP远离其对应的理论值。由于容限因子越小，每一层目标函数的可行域就越小，即下一层目标函数的极小值可能丢失，说明容限因子的选择对于基站布设至关重要。

假设目标轨迹采样间隔为30m，其他条件与例1相同，将上述仿真条件记为例4。图9是目标轨迹采样间隔对基站覆盖范围的影响，在例4情况下Load3部分轨迹未收到4个基站信号，说明基站布设对目标轨迹采样间隔相当敏感。

假设定位区域X轴的采样间隔是20m，Y轴的采样间隔是40m，其他条件与例1相同，将上述仿真条件记为例5。图10，图11分别是定位区域采样间隔对基站覆盖范围和GDOP的影响，由图可知，基站可能位置坐标越大，GDOP就越大，基站覆盖范围却不受影响。

实验3：定位性能分析

图12是不同基站布设方法RMSE的对比，由图可知，本发明基站布设算法的RMSE和CRLB明显小于无优先级的基站布局算法。图13是Load1在不同测量噪声标准偏差下的平均RMSE，由图可知，本发明基站布设算法定位结果优于无优先级的基站布设算法，并接近Load1的理论值，说明定位精度要求高时，本发明的定位性能越好。