《基于最小二乘测距定位算法信标最优部署模型.pdf》由会员分享，可在线阅读，更多相关《基于最小二乘测距定位算法信标最优部署模型.pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 卷第期 年月计算机学报 收稿日期：；最终修改稿收到日期：本课题得到国家自然科学基金（）、北京市自然科学基金（）、“新一代宽带无线移动通信网”国家科技重大专项（，）、广东省中国科学院全面战略合作项目（）、江苏省科技支撑计划项目（）、国家物联网发展专项资金项目（物专 合同 号）、天津市滨海新区科技小巨人成长计划项目（）资助 刘书静，女，年生，硕士研究生，主要研究方向为无线传感器网络、无线定位 ：罗海勇，男，年生，博士，高级工程师，主要研究方向为无线传感器网络、嵌入式系统、多媒体技术吴彬，男，年生，硕士研究生，主要研究方向为无线传感器网络、无线定位刘晓明，男，年生，硕士研究生，主要研究方向为嵌入
2、式系统、无线传感器网络、基于位置服务赵方，女，年生，博士，副教授，主要研究方向为计算机网络、移动计算基于最小二乘测距定位算法信标最优部署模型刘书静）罗海勇）吴彬）刘晓明）赵方）（中国科学院计算技术研究所移动计算与新型终端重点实验室北京 ）（北京邮电大学软件学院北京 ）摘要无线定位系统的信标部署方案对未知节点的定位性能有着重要影响文中基于线性最小二乘定位算法的定位误差上界（该上界与信标部署拓扑结构和信标测距误差相关），首次演绎推导出矩形区域内信标最优部署模型以及信标数为，的最优部署拓扑 实验结果表明，采用文中所提的最优部署策略获得的平均定位精度比其它优化信标部署方案提高 关键词无线定位；最小二乘
3、；信标部署；伪逆矩阵；物联网中图法分类号 号 ）（，）（，），；引言作为物联网的核心支撑技术及重要应用之一，无线定位技术及基于位置的服务（，）目前得到学术界的广泛关注 以全球定位系统（，）为代表的卫星定位技术尽管已能在室外开阔环境提供高精度的定位服务，但在室内、地下等封闭环境下，由于卫星定位信号受到障碍物阻挡、多径传播等因素影响，难以有效定位 伴随 、等短距离无线通信技术的不断发展，基于这些短距离无线通信技术的室内定位技术研究不断升温，以满足日益增长的高精度室内定位导航应用需求室内定位系统大多需要部署信标节点，与卫星定位系统的星座部署一样，无线定位系统中信标节点的部署拓扑对未知节点的定位性能有
4、着较大的影响良好的信标部署拓扑结构不仅可以让未知节点获得较好的平均定位性能，而且可获得更高的定位覆盖度，而不良的信标部署方案往往导致较大的定位误差，有时甚至导致无法定位 目前无线定位系统信标节点最优部署策略已成为节点定位技术研究的一个重要方向，受到较大关注相关研究近年来，在一跳网络（即未知节点可接收到所有信标节点发射的信号）节点定位信标优化部署方面已经有了一些相关研究工作，其中大部分工作主要集中在对有限几种典型信标部署拓扑进行定位性能比较方面，少部分工作则采用搜索方法，在信标部署组合空间内查找优化的信标部署方案，而基于理论演绎推理信标优化部署工作较少 等人通过构建基于平均测距相对误差的定位性能
5、模型，采用计算机仿真方法，对信标非线性、正方形等部署拓扑的定位性能进行了比较，得出信标不共线、信标位于网络中间、信标连线成直角的启发式优化部署策略，但并未给出最佳的信标部署方案 等人使用多个测距环带相交产生的交点集合求取平均不确定距离（任两个交点距离的平均值），并以最小化平均不确定距离为优化目标求解侦测节点（即信标）的位置部署，论文在比较了个信标共线、构成锐角三角形、钝角三角形以及个信标构成梯形、平行四边形等部署方案的平均不确定距离后，得出等边三角形信标部署拓扑以及信标拓扑重心与定位区域重心重合的结论上述方案仅仅枚举了几种典型的信标部署拓扑，受所选拓扑数目的限制，本质上是一种局部最优部署方案，
6、并不能从理论上确保所选部署方案是全局最优的 为获得理论上全局最优的信标部署方案，文献 基于 （）定位性能模型，采用穷尽搜索的方法，全面研究对矩形区域内信标节点部署对定位性能的影响，得出所有信标对称分布于矩形定位区域长边特定位置的最优部署拓扑，该结论与本文解析推导出的最优部署理论模型有一定的相似性 从理论上讲，采用穷尽搜索方法遍历所有的信标部署组合，是可以获得最优的信标部署拓扑的，不过时间复杂度较高（），其中、分别为信标数目和网格数目），可扩展性较差 为减少穷尽搜索计算开销量，等人采用局部搜索、模拟退火、禁忌搜索等局部搜索启发式算法，通过最小化与信标部署拓扑相关的平均定位误差代价函数，获取信标部
7、署的局部优化方案由于不能遍历整个信标部署的解空间，这类搜索算法并不能保证能获得全局最优的信标部 署 拓 扑 文 献 则 通 过 构 建 定 位 误 差 与 伪逆矩阵之间的解析关系，把定位误差转化为第二大特征值的最大化问题，并给出了使用线性最小二乘定位算法的最佳信标部署方案不过该文献采用的启发式思路存在明显的理论缺陷，即矩阵特征值表达式的多个参数之间相互耦合，不能仅仅以非正数项的最大化（即取值为）来替代整个表达式的最大化以上信标部署模型主要适用于跳网络，不适用于多跳网络（例如传感器网络）节点定位在多跳网络定位信标优化部署方面，等人 采用极大似然估计定位算法，通过构建节点定位误差与最近信标节点间平
8、均距离的近似解析式，得到了满足指定定位性能的信标部署拓扑方案，即信标部署于矩形分割区域的中心 文献 则使用 算法获取未知节点到信标的距离估计后，采用基于最小二乘矩阵条件数最小准则推导出信标最优部署需要满足的约束条件，给出了一个信标位于定位区域中心，其它信标均匀分布于内接圆周上的优化部署方案 上述两个文献都是研究直接使用多跳测距估计实现绝对定位的信标优化部署问题，这类方法需要部署的信标数较多，精度相对较低 与此不同，还有一类信标优化部署问题是解决多跳传感器网络所有节点相互协同完成相对定位后，如何实现相对坐标到绝对坐标的最佳转换 文献 采用最小化信标约束子空间与变换子空间最大主角的方法，得到信标均
9、匀分布在传感网部署区域外沿的信标优化部署方案 文献 则探讨了在信标部署尽可能少的多跳传感器网络，采用无需测距曲元分析定位算法 获得节点的相对坐标系后，不同信标部署拓扑对定位性能的影响问题，论文给出了信标期刘书静等：基于最小二乘测距定位算法信标最优部署模型优化部署应满足的两个启发式条件：（）信标间距至少是传输半径的 倍；（）信标所处平面高度至少等于传输半径以定位性能优化为目标的信标部署模型一般与采用的定位技术密切相关，考虑到最小二乘定位算法应用较为广泛，故本文选取单跳网络中基于最小二乘的信标最优部署作为研究点，论文通过构建定位误差与 伪逆矩阵之间的解析关系，首次从理论上演绎推导出信标最优部署策略
10、，并给出了信标节点数为，时的最优部署方案目前作者尚未在公开文献中发现其它类似研究成果本文主要贡献是采用理论分析方法，演绎推导了节点均匀部署在矩形区域内的信标最优部署策略及信标数为，个时的最优部署拓扑，并通过与其它几种优化信标部署方案进行实验对比，验证了本文所提最优部署方案的正确性本文第节介绍信标部署模型；第节将详细证明最优部署策略；第节的实验仿真部分对多种优化部署方案进行性能比较，验证本文所提最优部署策略的有效性；最后是论文总结信标最优化部署模型由于大多数室内定位场景都可以简化为简单的矩形区域或者多个矩形区域的组合，不失一般性，本文主要研究二维（）矩形区域内跳测距定位的信标最优部署问题图 定位
11、区域及信标部署假设所有信标节点和未知节点都位于同一高度，所有信标与未知节点位置均采用 笛卡尔直角坐标系，如图所示 定位区域的几何中心为坐标原点，矩形长度为，宽度为，四条边分别为，个信标节点部署在矩形区域内，其坐标分别为（，）（，），图中给出了个信标的示例情况 未知节点（，）位于定位区域内通过测量未知节点与信标节点之间的距离（基于无线信号的飞行时间或信号强度测距），使用线性最小二乘算法对未知节点的位置进行估计假定没有测距误差，在获得未知节点（，）到个信标节点（，）（）的测距，后，可得如下方程组（）（）（）（）（）（）烅烄烆（）将式（）中的个公式相加并取平均可得式（）：（）（）（）将式（）中的个方
12、程两边同时减去式（），使用最小二乘估计方法，可求得未知节点的坐标估计（，），（）（）其中，（）（）（）（）（）（）熿燀燄燅（）（）（）（）（）（）（）（）（）（）熿燀燄燅（）在实际环境中，受环境噪声等因素的影响，测距不可避免地存在误差，对矩阵的准确性产生影响（这里假设信标坐标无误差）假设测量误差为（注：此处的不是简单的值，可能是高斯分布或者指数分布的量，但是文中考虑的重点并不是通过减少测距误差以减少定位误差，故此处不再展开描述），则珘，此时使用线性最小二乘获得的未知节点位置估计珟（）珘，则未知节点的定位误差可表示为计算机学报 年珟（）其中为的 伪 逆 矩 阵（逆 矩阵），其二次范式（和为矩阵的
13、两个奇异值，且）考虑到矩阵的奇异值是矩阵的特征值的方根，故定位误差可使用矩阵的特征值进行评估（）（）其中（）（）（）（）（）（）（）的特征值可以表示为（）（）（）对式（）进行求解得（）（）槡（）（）槡烅烄烆（）信标最优化部署的目标是使节点的平均定位误差最小，由于（），而槡，其中为矩阵两个特征值中的较小值由式（）可知，未知节点的定位误差由两部分组成，即由信标部署拓扑所决定的以及由环境因素和测量方式决定的测量误差，假设二者相互独立，当定位环境以及测距方式确定之后，影响定位误差的因素只有信标的部署方式 此时，使槡取得最小值的信标布署为信标最佳部署方式，即信标最优化部署问题转化为式（）所示的最大化问题
14、 （）（）槡 （）最优信标部署策略 信标最优部署准则信标部署的目标是使得定位误差最小，即优化求解和使最大，由式（）所表示的优化目标可知，要使取得最大值，则要（）尽可能大，而及尽可能小，由式（）（）可知的取值与、相关，而和的取值相互独立 对式（）所示的个信标最优部署模型进行如下处理：（）（）槡（），（，）（）即对进行放大，得到的上界 （，）（当且仅当 时等号成立）可见，如果 （，）能取得最大值的同时，则可取得最大值 考虑到在矩形定位区域内，使得 （，）取得最大值的信标位置为一个集合，在该解集内可能存在部分解使得，此时 （，）对应信标最优部署拓扑为此，先求 （，）的最大值对应的解空间，然后在解空间
15、搜索的解本文引入如下定理定理 当或者取得最大值时，所有的信标节点都位于定位区域的边界上即当取得最大值时，所有节点位于图中的边、（不能都位于同一条边上，因为此时，取得最小值）；当取得最大值时，所有节点位于图中的边、（不能都位于同一条边上，因为此时，取得最小值）证明 由函数的海塞矩阵性质可知，当函数的海塞矩阵为半正定 时，函数为凸函数，而由函数的凹凸性可知，凸函数取得最大值时，自变量位于边界上，由此本文将通过证明函数（）的海塞矩阵为半正定来证明本定理 不失一般性，这里仅证明当取得最大值时，即位于边界上问题论述：按照式（），设函数（）（）（）其中，求当（）取得最大值时，自变量的值函数（）的海赛（）矩
16、阵为（）（）（）（）（）（）（）（）（）（）熿燀燄燅（）将式（）求偏导后可得期刘书静等：基于最小二乘测距定位算法信标最优部署模型 熿燀燄燅（）设，则二次型 为（）（）（）（）可见，矩 阵半 正 定，由 于，故（）也是半正定的由函数的凹凸性判定理论可知，当函数（）的海赛矩阵（）在上半正定时，函数（）为上的凸函数，凸函数的性质之一是函数的最大值位于边界上，即（，）同理可证，当取得最大值时，证毕定理 当取得最大值时，若为偶数，则有个信标的纵坐标为，其余个信标的纵坐标为；若为奇数，则有（）个信标的纵坐标为，其余（）个信标的纵坐标为（或者（）个信标的纵坐标为，其余（）个信标的纵坐标为）；当取得最 大 值
17、时，情 况相似证明 考虑到取最大值与取最大值情况类似，本文仅证明取最大值的情形 由定理可得，当取最大值时，信标的纵坐标（）当为偶数时，设一组信标满足有个信标的纵坐标为，其余个信标的纵坐标为；不失一般性假设另一组信标，有（）个信标的纵坐标为，其余个信标的纵坐标为 根据两组信标节点的纵坐标分别求值，第组，第组（），则（）（）（）由于（），即（）（），故，当且仅当时等号成立，即时，取得最大值（）当为奇数时，设一组信标满足（）个信标的纵坐标为，其余（）个信标的纵坐标为；不失一般性假设另一组信标，有（）个信标的纵坐标为，其余个信标的纵坐标为 经计算（），（），则（）（）（）（）由二次函数的单调性可得，当
18、（）或者（）时，（），即（）或（）时取得最大值证毕定理 如果定位区域为矩形，当信标节点取得最优部署时，信标位于矩形长边上证明 由式（）可知，当取得最大值时，可获得最优部署由式（）可知，的上限为或，如果能求解或取得最大值的信标部署集合，再从中选择使得的值等于它的上限的那部分部署，即可获得信标的最优部署下面分情况讨论最优部署当时，由定理和定理可知，当取得最大值时，其纵坐标为，此时由定理可知，可得的最大值为，即，由以上条件得，简化之后可得，即信标节点位于矩形长边上同理当，由定理和定理可得，取得最大值，且，此时满足，即，即信标节点位于矩形长边上证毕 信标数为，个时的最优部署拓扑信标最优部署的目标是使定
19、位误差最小，由式（）可知，定位误差由和共同决定，其中前者由测距误差决定，后者由信标部署位置决定，在测距误差（与使用的测距技术密切相关）不变的情况下，优化信标部署以减小的值是减小定位误差的关键，即求和使得槡取得最小值在 节中证明了获得最优部署的个定理，本小节将基于这个定理演绎推导信标数分别为、时的信标优化部署方案由定理可知，信标节点取得最优部署时，节点总是位于长边上，不失一般性，假设定位区域的长宽比（），即矩形区域长度大于宽度，定位区域相应参数参见图推论 当信标数为时，此时，此时定位误差的上限趋于无穷大实际上，在 空间，当只有两个信标时，未知节点无法完成计算机学报 年定位推论 当信标数为时，最优
20、信标拓扑结构呈等腰三角形结构，其中顶点位于矩形的一条长边上，底边两个端点共同位于另一条长边上 三角形底边长度槡 当槡，该三角形为正三角形证明 由定理可知，个信标点中有一个位于边上，其余两个位于边上（或者一个位于上，其余两个位于上），此时取得最大值，要使得取得最大值，则要满足以下两个条件 ，当点成对称分布时，即满足等腰三角形分布，设顶点坐标为（，），底边的两点为（，），（，），此时，故槡，如图（）所示，此时三角形底边长度槡问题得证以下推论证明过程与此推论证明过程类似，不再赘述，只给出结论 证毕图信标数分别为，个时的最优部署拓扑推论 当信标数为时，个信标组成矩形，两两分布于部署区域的两条长边上，矩
21、形宽度为，长度如图（）所示推论 当信标数为时，其中个信标呈矩形两两分布于部署区域的两条长边上，第个点落于上述矩形任一条长边的中点，由信标节点构成的矩形宽度为，长度槡如图（）所示推论 当信标节点个数为时，四点呈矩形两两分布于部署区域的两条长边上，第个点落于由信标节点构成的矩形一条长边的中点，第个点位于矩形另一条长边的中点，矩形宽度为，长度槡 如图（）所示推论 当信标节点个数大于时，需要添加其它限制条件或者使用搜索法才能得到最优部署方案实验结果及分析为了验证本文所提的最优部署准则以及特定信标个数的最优部署方案的有效性，本文使用最小二乘定位算法进行实验仿真，并采用累积误差分布函数（，）和均方根误差（
22、，）进行定位性能评估 定位性能评估标准本文采用式（）所示的均方根误差衡量标准，式中为节点的真实坐标，为节点的估计坐标，为未知节点数目（）槡（）测距模型本文采用如式（）所示的基于 的测距模型，它根据节点接收信号功率来获取节点间的距离估计 其中（）为节点发射、节点接收的信号功率，（）为自由空间条件下参考接收点接收的信号强度，为信标节点到参考接收点的距离，为无线传输衰减系数，与无线传输环境有关，接收功率服从（珚，）分布，珚 为接收功率均值，为方差期刘书静等：基于最小二乘测距定位算法信标最优部署模型（珚，）珚 （）（）使用极大似然估计方法，由式（）可推得节点，间 的距离估计，如 式（）所 示，其 中珚
23、 为接收功率测量误差，分布为（，），为节点间距离估计，为 测量误差，其标准偏差为 （对应单位为）（珚 ）（）（）（）不失一般性，本文所提部署模型同样适用于各种 测距模型 实验结果及分析本文使用 进行实验仿真 在满足 节各项推论所述信标间距约束条件下，假定部署区域的长宽比 ，将部署区域划分为 个网格，每次定位实验均在格子中心位置进行 针对不同部署方案，在所有网格进行定位仿真，并进行定位性能统计，其中每个格子的定位误差为 次仿真实验的平均值 不同信标部署方案性能比较为了验证 节提出的个定理（定理、），并评估不同部署方案对定位性能的影响，本文设计了如图所示的信标数分别为，个时的部署方案 论文中除特别
24、指出外，假定标准偏差 为 实验中的部署方案如图所示：（最优部署方案）本文所提最优部署方案（均采用 节中最优部署方案取等号的情况）（中间部署方案）部署方案，即信标节点 的 拓 扑 结 构 不 变，但 是 整 体 缩 小 为 原 来 的，中心位置与 中相同（反定理）（非平均部署方案）不满足两边平分信标个数，即信标节点为偶数时，位于两条长边的个数分别为和，信标个数为奇数时分别为（）和（）（反定理）（短边部署方案）不满足信标部署于长边上的这一要求，把信标部署在矩形区域短边上（反定理）（均匀部署方案）主要包括个和个信标情形当信标为个时，个信标位于矩形长边上，个信标位于部署区域中心；当信标为个时，矩形两个
25、长边上各自对称部署个，短边上各自部署个，整体构成一个六边形拓扑结构 （随机部署方案）在部署区域内随机放置信标节点，实验结果选取 组随机部署结果的平均图仿真实验中的不同信标部署拓扑计算机学报 年不同部署方案定位性能的仿真实验结果如图所示 从图中可以看出，采用本文所提的部署方案（）可获得最佳的定位精度，而采用信标位于矩形短边的方案（），定位精度相对较差 按照定位性能从优到劣的顺序对这几种部署方案进行排序可得：（本文所提最优部署方案）、（平均部署方案）、（非平均部署方案）、（中间部署方案）、（短边部署方案）（随机部署方案）在信标数分别为，个时，采用本文所提的最优部署方案（）获得的定位性能，比采用 拓
26、扑结构获得的定位性能分别提升，当信标数为和时，增加了均匀部署拓扑结构，如图（）和（）所示，它们的定位性能同样低于本文所提的最优部署策略，不过比其它信标部署策略好 由图（）和（）可以看出，比 有的性能提升除了对于上述非常规则的拓扑部署方案进行了定位性能比较之外，本文对随机部署策略的定位性能也进行了测试和比较，如图中 所示当信标数为或时，随机部署拓扑获得的定位性能都是最差的，而当信标数增加到个或个时，随机部署的策略比短边部署（）策略的定位性能好这是因为当信标数目较少时，随机部署形成较好拓扑结构的概率较低，信标分布在定位中心区域内的概率较大，导致定位性能较差 随着信标数的增加，多个信标将更加均匀地分
27、布在定位区域，消除了不良拓扑结构的影响，因而定位性能也随之提高 不过总的来讲，采用随机部署策略的定位性能仍然不如其它几个部署策略由以上实验可知，信标位于长边且均匀分配的部署策略是最优的，比目前比较常用的优化部署方案定位性能更好，验证了定理，图不同信标部署方案下的定位误差累积分布函数（）信标间距对定位性能的影响在信标部署拓扑满足 节定理，所述限制条件下，位于部署区域同一条边上的信标之间的距离对定位性能有一定影响，本节将通过实验评估该距离对定位性能的影响按照 节推论对不同数目信标部署位置的限制要求，图给出了不同信标数目下平均定位误差随信标间距参数 （）的变化情况由图中可以看出，随着 的增加，定位误
28、差逐渐降低，然后趋于稳定 而随着信标数的增加，未知节点可获得的测距信息不断增加，故定位性能不断提高当信标由个增加至个时，定位性能改善期刘书静等：基于最小二乘测距定位算法信标最优部署模型图不同信标间距 对定位性能的影响（：）的幅度比信标由个增加至个的幅度大很多，这是由于当信标数较多时，未知节点已获取了足够的高精度定位所需的信息，再增加信标数时定位精度并不会明显提高 当 较小时，两个信标间距离过小，极限情况下重合，仅能发挥一个信标的作用，未知节点获得的测距信息下降，导致定位性能降低 噪声对定位性能的影响本小节比较了在信标最优部署情况下，不同大小测距噪声对定位性能的影响，如图所示由图中可以看出，随着
29、测量噪声的增加，定位误差不断增加当噪声增加时，测距信息受到噪声污染的程度不断增大，导致定位误差明显下降 而增加信标数目，平均定位误差有所下降图不同数目信标条件下噪声对定位性能的影响（；）相同信标数目条件下，噪声对不同信标部署方案的定位性能影响对比情况如图所示 可见，随着噪声的增加，所有部署方案的定位误差都增加，而在相同噪声影响下，本文所提最优部署方案的定位性能最优，表现出较强的定位鲁棒性在所有部署方案中，随机部署的定位性能最差，这与 节的实验结果相吻合图噪声对不同部署方案定位性能的影响（个信标，）总结本文从理论上证明了基于最小二乘测距定位算法信标最优部署策略，演绎推导出了矩形区域内信标最优部署
30、的个定理以及信标数为、时的最优拓扑结构，这些结论有助于提高高精度定位系统信标规划部署的有效性，从而提高定位性能和定位鲁棒性计算机仿真实验验证了最优部署的三条准则的有效性，论文下一步工作将在节点上进行实际物理实验，测试部署策略的有效性致谢在此，向我的导师罗海勇老师表示感谢，在罗老师的辛勤指导下才得以完成该文章 此外，向对于本文工作给予支持和建议的课题组的其他老师和同学表示感谢！参考文献 ，（），：，（）：，：，（）：，（）：计算机学报 年 ，（），：，（），：，（）：，：，（），：，（），：，（），：，（），：，（），：，（）：，：（）（张贤达矩阵分析与应用第版北京：清华大学出版社，：），：，：（）（甘应爱，田丰运筹学第版北京：清华大学出版社，：），：，：（）（孙利民，李建中，陈渝，朱红松无线传感器网络第版北京：清华大学出版社，：），期刘书静等：基于最小二乘测距定位算法信标最优部署模型 ，（），计算机学报 年