基于凸半定规划的RSS测距的合作式定位方案

无线传感网中的多类应用均需要准确的定位算法。为了降低定位成本,减少能量消耗,常采用基于接收信号强度RSS(Received Signal Strength)测距,再利用最大似然ML (Maximum likelihood)估计法求解节点的位置。然而,ML估计为非线性、非凸性,难以获取全局最优解。为此,提出凸半定规划SDP(Semidefinite Programming)的合作式定位方案,利用凸半定规划策略将ML估计转换成凸优问题。同时,该方案考虑两类场景：源节点发射功率已知、未知。针对第一类场景,利用半凸松驰策略,并结合最小化最小二乘法,建立凸优表达式,最后利用CVX求解;针对第二类场景,先建立联合ML估计函数,再利用SDP估计,并结合起来简单的三步骤方案进行位置估计。仿真结果表明,提出的SDP算法的定位精度比SD/SOCP-1、SDPRSS平均提高了近15%至20%。此外,提出的SDP算法在所有场景的误差小于3m的出现概率占0.8,而SD/SOCP-1、SDPRSS算法小于0.5。     

基于半定规划的无线传感器网络节点定位算法

针对无线传感器网络节点定位,在最大似然估计(MLE)基础上提出了一种半定规划(SDP)的优化算法.结合有效的锚节点位置选择和比率范围设定,在放宽非凸约束的基础上,采用SDP求解算法,有效减少了误差的影响,得到被测节点的实际位置.改变锚节点的位置可以有效解决锚节点凸壳外的节点位置估计不精准问题.仿真结果表明,提出的SDP算法对未知节点的位置实现了高精度定位,改进了凸优化方法.     

协作定位在地下管廊监控中的优化研究

地下管廊是一种半封闭的窄长空间,其内情况复杂多变,由于非视距情况的出现,导致传感器节点定位困难、精度不高.针对地下管廊的多径干扰等特性,提出了最小二乘非凸估计算法(LSNCE).首先结合接收信号强度(RSSI)和到达角度信息(AOA),使用最小二乘法求出未知节点的位置估计.然后引入未知节点的辅助变量X及辅助向量z,通过应用半定规划松弛技术将位置估计转化为凸性,并得出上镜图(Epigraph)变量,再使用CVX工具箱(Matlab中包含)求出位置估计的最优解,即得到未知节点的最终位置.通过仿真验证,对比常规的选择混合加权算法(SHWA)和二次加权最小二乘算法(SWLS),最小二乘非凸估计算法能够有效地提高定位精度,同时表现出了良好的抗干扰能力.     

凸二次规划SDP松弛解的存在性证明

针对利用CVX软件求解半定规划问题的有效性依赖于该半定规划问题的原始-对偶性,提出利用半定规划问题的强对偶定理和Gershgorin圆盘定理证明在箱子约束及单位球形约束下的凸二次规划问题的半定规划松弛模型解的存在性。该证明方法为嵌入了SeDuMi和SDPT3这两种内点算法的CVX软件提供了有效求解半定规划松弛模型的理论依据;一旦利用该方法证明了半定规划问题解的存在,必然可利用CVX软件有效求解。     

一种利用可靠的锚节点的非测距定位算法

无线传感网中的多类应用均需要准确的定位算法。为了评估位置,普通节点需利用与锚节点间的距离信息,估计自己的位置。因此,距离的估计在无线传感网络定位中扮演着重要的角色。传统的各向同性网INT(isotropic networks)中定位算法是将欧式距离看成最短路径距离SPD(shortest path distances)。然而,这些算法在各向异性网ANT(anisotropic networks)不能准确地估计距离,因为ANT中最短路径距离SPD与欧式距离不成线性比例;并且两节点间的最短路径被迂回,其长度可能大于相应的欧式距离。针对此问题,正确选择可靠的锚节点RANs(reliable anchor nodes)用于准确地估计距离显得格外重要。为此,面向各向异性网ANT,提出基于可靠的锚节点选择的定位方案,记为Se_RANs。每个普通节点通过三角模型原则选择三个可靠锚节点,计算这三个锚节点估计离其他锚节点间的距离,进而利用Mix-max算法估计普通节点位置,从而提高估计的准确性。同时,通过数学分析,推导了普通节点周围存在三个可靠锚节点的概率;并验证了Se_RANs方案的可行性。仿真结果表明,与DV-Hop算法相比,提出的Se_RANs方案具有小的定位均方误差(MLE)。     

球约束加权极大极小离差问题的SDP松弛的注记

【目的】研究利用CVX软件有效求解球约束下的加权极大极小离差问题的SDP松弛模型。【方法】应用半定规划的强对偶定理和Gershgorin圆盘定理。【结果】证明了Haines等人给出的球形约束下离差问题的SDP松弛的解的存在性;同时提出了另一个球形约束下的离差问题,并给出了它的SDP松弛模型的解的存在性证明。【结论】提出的新的证明方法为CVX中嵌入的SeDuMi和SDPT3这两种内点算法提供了有效求解SDP松弛模型的理论依据。     

一种基于遗传算法的无线传感器网络节点定位技术研究

本文分析了基于误差的最小二乘估计定位原理,提出一种基于遗传算法的无线传感器网络节点定位技术。建立所有节点的定位误差之和最小的数学模型,利用遗传算法求解模型的最优解,从而得到未知节点的最优的估计位置。实验仿真结果表明该算法对未知节点的定位精度高,条件简单,适合各种规模的无线传感网络节点的定位。     

一种无线传感器网络自身节点定位算法

基于无线传感器网络定位中半定优化算法的特点,提出了一种基于信号到达角信息的无线传感器网络节点自身定位算法,将所有节点之间的角度关系表述为凸规划约束条件,从而将定位问题转化为一个凸集优化问题,节点间的几何关系也相应地转化成为线性或二次约束条件.在理想情况下,该算法将定位问题转化为一个线性规划问题.实际情况中考虑到测量误差,通过引入辅助变量,将定位问题转化为一个二次规划问题.仿真结果表明,当信号到达角测量误差增加10°左右时,该算法仍可取得满意的定位精度.     

无源标签多径环境下基于凸优化的定位算法

在室内无源超高频RFID定位中,多径传播对定位结果的影响不可忽视.为了提高复杂多径环境下的定位精度,提出了基于半定规划(SDP)和二阶锥规划(SOCP)的相位差欧式距离拟合定位算法.运用参考标签的位置信息,对参考标签之间的理想相位差欧氏距离与实际距离进行拟合,实现标签之间的距离估计.建立待定位标签与阅读器、参考标签距离估计模型,将多径传播、高斯白噪声、相位差欧氏距离拟合引起的距离估计误差等效为正态分布,利用参考标签的相位差信息和位置信息计算出正态分布参量.仿真结果表明,提出的算法在最大多径数目为7时,定位误差有90%,的概率低于2.3,m,定位性能优于传统的基于测距的定位算法.     

一种求解QoS路由问题的半定规划算法

QoS路由的主要问题是求源节点到目的节点满足QoS多个约束的优化问题。由于半定规划在求解组合优化问题和NP-完全问题时具有收敛速度快,迭代步数少等优点。本文基于QoS路由问题的线性整数规划网络模型,利用半定规划方法研究了时延约束的代价最小问题。把QoS路由的一般模型松弛为半定规划的标准形式,利用半定规划内点方法进行求解,然后利用随机扰动方法得到原问题的近似最优解.数值试验表明了算法的有效性。     

基于测距的地面网络化弹药节点自定位算法

分析了极大似然估计算法中测距误差对定位误差的影响,提出了基于LMS（最小均方差）的自适应滤波原理的测距误差修正的自定位算法. 利用极大似然估计法初步估计节点位置,并得到定位误差信息,建立测距误差矩阵并更新网络中的滤波参数,完成对网络中测距误差的抑制,从而优化节点定信息. 实验仿真表明,优化处理使定位精度得到提高. 结果表明算法适用于锚节点密度较小的、低信噪比的网络化弹药系统.     

半定规划的改进的外梯度法

利用半定规划的最优性条件,对其进行有效变换,把求解半定规划问题转化为求解变分不等式问题,再给出一个改进的求解变分不等式问题的外梯度法,从而得到半定规划问题的最优解.结果表明:改进的算法是求解半定规划的有效方法.     

基于扩散策略的分布式多维尺度节点定位算法

针对无线传感器网络节点自身定位问题,提出了一种基于扩散策略的分布式多维尺度定位算法,给出了扩散策略和局部网络信息融合的方法.与传统多维尺度定位算法相比,该算法无须将所有信息集中到中心节点进行定位计算,而是在局部网络内进行定位迭代解算及信息交换再进行坐标信息融合.该算法在迭代过程中将未知节点视为锚节点,将原算法中被忽略的参数量引入优化目标方程,采用一组凸组合权值系数对交换后信息进行加权融合以得到节点自身坐标.仿真结果表明:改进算法与原算法相比在测量噪声较大时平均与最大定位误差均下降约10%,特别是当网络连通度较低时改进算法定位精度更高.     

解半定规划的带筛子的正则化方法

研究了求解半定规划问题的一个带有筛子的正则化方法,该方法是基于经典的二次正则化方法,将半定规划问题转化为目标函数为凸的、可微的无约束优化问题。利用筛选信赖域方法来解这个无约束优化问题,并给出算法及其收敛性分析。     

解非凸半定规划的一个Lagrange方法

基于一个求解一般非凸半定规划问题的非线性Lagrange函数,给出了其相关算法,研究了函数的性质,证明了算法的收敛性。在适当的条件下,当罚参数大于某一阈值时,算法产生的序列局部收敛,由此给出了与罚参数相关的解的误差估计。     

异步无线传感网络同时定位与跟踪算法

针对异步无线传感网络环境下同时节点定位和目标跟踪问题,提出了一种可以同时进行传感器节点定位和目标跟踪的算法.该算法利用增广状态向量法对目标状态和节点位置进行同时估计,并利用固定点平滑算法对目标状态进行最优估计,实现了异步无线传感网络环境下的目标状态的最优估计以及节点位置的估计.结合节点位置和目标状态的增广状态向量取代了传统目标跟踪算法中的状态向量,在滤波算法中被用于节点位置和目标状态的同时估计.仿真实验证明:在相同的测量次数和通信次数情况下,本算法不但能够取得更高的节点位置估计精度和目标状态估计精度,而且能够取得更多目标状态的估计结果.     

求解最优潮流全局最优解的二阶半定规划方法

【目的】半定规划凸松弛方法是求取电力系统最优潮流(Optimal power flow, OPF)问题全局最优解的有效技术手段，但解的秩为1的条件难以满足，导致应用具有一定的局限性。针对这一求解困境，提出了一种新的半定规划凸松弛方法。【方法】基于变量扩展，将原变量对应的二阶单项式扩展为新的变量，扩展后可构造一阶及二阶的半正定扩展矩阵，在此基础上将不等式约束转化为矩阵不等式约束，从而形成二阶半定规划凸松弛模型。【结果】为验证所提方法的有效性，求解了常规半定规划方法应用失败的一些反例，结果表明：二阶半定规划松弛模型能更可靠地求得秩为1的扩展矩阵，从而直接获得原OPF问题精确的全局最优解。【结论】二阶半定规划松弛方法为电力系统OPF问题提供了一种更可靠的全局最优算法，具有更好的应用前景。     

基于交替修正牛顿法的分布式传感器定位算法

为了克服锚节点位置误差影响定位精度这一问题,提出了一种基于交替修正牛顿法的分布式定位算法。首先,将无线传感器网络表示的无向图划分成多个部分重叠的子图,建立可独立求解的子图内定位问题,子图内未知节点根据不准确的锚节点位置和测距信息采用修正牛顿法得到初步估计位置,再融合求平均得到估计位置;其次,根据第一步结果和测距信息采用修正牛顿法更新锚节点位置,使其位置更为精准;最后,未知节点再根据相对准确的锚节点位置更新估计位置。实验结果表明,与现有的分布式算法相比,所提算法具有更好的定位性能和扩展性,能够应用于较大规模的无线传感器网络。     

利用半无限规划的离散化方法求解半定规划问题

【目的】对半定规划的强对偶定理以及求解半定规划近似解的算法进行讨论。【方法】利用求解半无限规划的近似解的离散化思想,及线性规划的强对偶定理。【结果】得到了半定规划强对偶定理一种新的证明方法以及求解半定规划近似解的离散化算法,给出了该算法的数值实验结果。【结论】为半定规划问题提供了一种新的近似求解算法。     

错误测量下节点选择策略对跟踪精度的影响

为了实现一定比例错误测量下的目标跟踪,构造了节点与目标的简化模型;在粒子滤波基础上,采用贝叶斯估计获得先验概率;利用前一时刻的位置、速度估计和估计因子,得到每一个在探测范围内的节点到目标的最远和最近距离;再结合节点本身的测量值计算每一粒子相应的权值,然后加权得到范围内节点测量值的可靠性集合,从该集合中选择可靠的测量值作为跟踪估计依据.根据不同的权值计算方法,分为节点关联选择策略和二进制节点选择策略.仿真结果表明：在目标运动速度〈3m/s和错误测量概率〉0.1的情况下,采用节点关联选择策略的RBMCDA算法的跟踪精度优于单纯选择3个较大RSSI值的RBMCDA算法至少1倍.