基于定位误差估计的锚节点布局优化
|
摘要
大多数现有研究忽略了室内定位系统的最佳锚节点布局问题,传统多边测量定位算法误差分析中,存在误差面积不规则、计算困难等问题,作者提出了一种实现最小定位误差的锚节点布局方法。使用几何分析和实验分析相组合的方法研究定位误差和锚节点布局之间的关系,通过几何面积关系精确计算了双锚节点定位误差,提出了一种新的误差上限估计方法,这一误差上限反映了锚节点的位置和锚节点处的误差,可以用于比较任意两个锚节点布局之间的最大误差,描述误差的立体分布。引入耗散均匀搜索粒子群算法(dissipative uniform search particle swarm optimization,DUPSO),提出了一种新的多锚节点空间布局优化算法,找到了一种可以最大限度减少最大定位误差的最优布局。为了验证本文方法适用于各种规则、不规则环境以及不同数量锚节点最优布局的求解,仿真实现了不同数目锚节点和不同环境下锚节点的最优布局,并对不同的锚节点布局方法进行了比较。实验结果表明,使用锚节点的最佳布局,室内定位系统可以获得更高的定位精度。本文的布局优化算法是通用的,在实践中具有可行性和有效性。
In order to solve the problem of optimal anchor node layout in indoor positioning system, an anchor node layout method was proposed in this paper by deploying anchor nodes to achieve the minimum positioning error. Based on the multi-measurement positioning algorithm, for the problems of irregular measurement area, difficulty in calculation and so on, a combination of geometric analysis and experimental analysis was used to study the relationship between positioning error and the layout of anchor nodes. The positioning error of double-anchor nodes was accurately calculated by the geometric area relationship,and a new error upper limit estimation method was proposed for node positioning error. This error upper limit reflected the position of the anchor node and the error at the anchor node. The maximum error between any two anchor node layouts was compared and the three-dimensional distribution of errors was presented. Then, in this paper, DUPSO(dissipative uniform search particle swarm optimization) algorithm was introduced, a new multi-anchor node spatial layout optimization algorithm was proposed, and an optimal layout that can minimize the maximum positioning error was found. In order to verify that the algorithm of this paper is applicable to the solution of various rules, irregular environments and the optimal layout of different number of anchor nodes, the optimal layout of anchor nodes and different numbers of anchor nodes in different environments and the layout of different anchor nodes were simulated, and the layout methods of different anchor nodes were compared. The experimental results showed that with the optimal layout of the anchor nodes, the indoor positioning system can obtain higher positioning accuracy. The layout optimization algorithm presented in the paper is universal, feasible and effective in practice.
In order to solve the problem of optimal anchor node layout in indoor positioning system, an anchor node layout method was proposed in this paper by deploying anchor nodes to achieve the minimum positioning error. Based on the multi-measurement positioning algorithm, for the problems of irregular measurement area, difficulty in calculation and so on, a combination of geometric analysis and experimental analysis was used to study the relationship between positioning error and the layout of anchor nodes. The positioning error of double-anchor nodes was accurately calculated by the geometric area relationship,and a new error upper limit estimation method was proposed for node positioning error. This error upper limit reflected the position of the anchor node and the error at the anchor node. The maximum error between any two anchor node layouts was compared and the three-dimensional distribution of errors was presented. Then, in this paper, DUPSO(dissipative uniform search particle swarm optimization) algorithm was introduced, a new multi-anchor node spatial layout optimization algorithm was proposed, and an optimal layout that can minimize the maximum positioning error was found. In order to verify that the algorithm of this paper is applicable to the solution of various rules, irregular environments and the optimal layout of different number of anchor nodes, the optimal layout of anchor nodes and different numbers of anchor nodes in different environments and the layout of different anchor nodes were simulated, and the layout methods of different anchor nodes were compared. The experimental results showed that with the optimal layout of the anchor nodes, the indoor positioning system can obtain higher positioning accuracy. The layout optimization algorithm presented in the paper is universal, feasible and effective in practice.
引文
[1]Shahra E Q,Sheltami T R,Shakshuki E.A comparative study of range-free and range-based localization protocolsfor wireless sensor network:Sing COOJA simulator[J].International Journal of Distributed Systems and Technologies,2017,8(1):1-16.
[2]Moreno-Salinas D,Crasta N,Ribeiro M,et al.Integrated motion planning,control,and estimationfor range-based marine vehicle positioning and target localization[J].IFAC-PapersOnLine,2016,49(23):34-40.
[3]Liao Zhuolan,Wang Jianxin,Zhang Shigeng,et al.Minimizing movement for target coverage and network connectivity in mobile sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2015,26(7):1971-1983.
[4]Mao G,Fidan B,Anderson B D O.Wireless sensor network localization techniques[J].Computer Networks,2007,51(10):2529-2553.
[5]孙利民.无线传感网络[M].北京:清华大学出版社,2005:135-155.
[6]Song Shuang,Qiu Xiaoxiao,Wang Jiaole,et al.Design and optimization strategy of sensor array layout for magnetic localization system[J].IEEE Sensors Joumal,2017,17(6):1849-1857.
[7]Muhammad Farooq-i-Azam,Muhammad N A.Location and position estimation in wireless sensor networks[M]//Wireless Sensor Networks:Current Status and Future Trends.Boca Raton:CRC Press,2013:179-214.
[8]Domingo-Perez F,Lazaro-Galilea J L,Wieser A,et al.Sensor placement determination for range-difference positioning using evolutionary multi-objective optimization[J].Expert Systems with Applications,2016,47(C):95-105.
[9]Huang Rui,Zaruba G V.Beacon deployment for sensor network localization[C]//Proceedings of the 2007 Wireless Communications and NETWORKING Conference.Hong Kong:IEEE,2007:3188-3193.
[10]Meng Wei,Xie Lihua,Xiao Wendong.Optimal TDOA sensor-pair placement with uncertainty in source location[J].IEEE Transactions on Vehicular Technology,2016,65(11):9260-9271.
[11]Chen Yingying,Francisco J A,Trappe W,et al.A practical approach to landmark deployment for indoor localization[C]//Proceedings of the 2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks,2006(SECON'06).Reston:IEEE,2006:365-373.
[12]Yuan Zimu,Li Wei,Xu Zhiwei,et al.Beacon node placement for minimal localization error[EB/OL].(2017-07-10)[2015-03-29].https://arxiv.org/abs/1503.08404.
[13]Wang Riming,Shen Baihua,Liu Yang.Optimization of sensor deployment for localization accuracy improvement[C]//Proceedings of the 2016 IEEE International Conference on Consumer Electronics-China(ICCE-China).Guangzhou:IEEE,2016:1-4.
[14]Liu Juan,Zhang Ying,Zhao Feng.Robust distributed node localization with error management[C]//Proceedings of the7th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York:ACM,2006:250-261.
[15]Yang Zheng,Liu Yunhao.Quality of trilateration:Confidence-based iterative localization[J].IEEE Transactions on Parallel and Distributed Systems,2010,21(5):631-640.
[16]Aomumpai S,Kondee K,Prommak C,et al.Optimal placement of reference nodes for wirelessindoor positioning systems[C]//Proceedings of the 2014 11th International Conference on Electrical Engineering/Electronics,Computer,Telecommunications and Information Technology.Nakhon Ratchasim:IEEE,2014:1-6.
[17]Moore D,Leonard J,Rus D,et al.Robust distributed network localization with noisy range measurements[C]//Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems.New York:ACM,2004:50-61.
[18]Chen Yourong,Lu Siyi,Chen Junjie,et al.Node localization algorithm of wireless sensor networks with mobile beacon node[J].Peer-to-Peer Networking and Applications,2017,10(3):795-807.
[19]Xia Xinjiang,Hu Gang,Wang Yehua.Study on improved algorithm based on concentric circles localization[J].Computer Science,2012,39(6):68-71.[夏心江,胡钢,王烨华.基于同心圆定位算法的改进算法研究[J].计算机科学,2012,39(6):68-71.]
[20]Zhou Yan,Zhao Hai,Zhang Jun,et al.Location error analysis of pervasive computing[J].Acta Electronica Sinica,2009,37(2):382-386.
[21]Xiong Zhiguang,Shi Weiren,Xu Lei,et al.Trilateration localization algorithm based on weighted disposal[J].Computer Engineering and Applications,2010,46(22):99-102.[熊志广,石为人,许磊,等.基于加权处理的三边测量定位算法[J].计算机工程与应用,2010,46(22):99-102.]
[22]Zhao Hai,Sun Peigang,Zhang Wenbo,et al.Research on reference nodes placement and selection of ubiquitous computing locating service[J].Frontiers of Electrical and Electronic Engineering,2007,2(1):13-22.
[23]Li Haicheng,Zhang Rui,Zhou Yan.Research on deployment of locating unit in ubiquitous computing[J].Computer Science,2010,37(1):142-145.[李海成,张锐,周艳.普适计算中定位单元布局研究[J].计算机科学,20 10,37(1):142-145.]
[24]Sun Peigang,Zhao Hai,Zhang Wenbo,et al.Research on reference nodes placement and selection of ubiquitious computing locating service[J].Acta Electronica Sinica,2006,34(8):1456-1463.[孙佩刚,赵海,张文波,等.普适计算中定位服务的参考点布置及选择算法[J].电子学报,2006,34(8):1456-1463.]
[25]Kim S W,Lee B T.Scalable DV-Hop localization algorithm with constrained multilateration for wireless sensor network[J].IEICE Transactions on Communications,2009,E92.B(10):3075-3078.
[26]Zhao Hao,Zhang Kuan,Zhu Jian,et al.Error analysis and improvement of ultrasonic distance measuring based on TDOA[J].Journal of Northeastern University(Natural Science),2011,32(6):802-805.[赵海,张宽,朱剑,等.基于TDOA的超声波测距误差分析与改进[J].东北大学学报(自然科学版),2011,32(6):802-805.]
[27]Wu Xiaojun,Yang Zhanzhong,Zhao Ming.A uniform searching particle swarm optimization algorithm[J].Acta Electronica Sinica,2011,39(6):1261-1266.[吴晓军,杨战中,赵明.均匀搜索粒子群算法[J].电子学报,2011,39(6):1261-1266.]
[2]Moreno-Salinas D,Crasta N,Ribeiro M,et al.Integrated motion planning,control,and estimationfor range-based marine vehicle positioning and target localization[J].IFAC-PapersOnLine,2016,49(23):34-40.
[3]Liao Zhuolan,Wang Jianxin,Zhang Shigeng,et al.Minimizing movement for target coverage and network connectivity in mobile sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2015,26(7):1971-1983.
[4]Mao G,Fidan B,Anderson B D O.Wireless sensor network localization techniques[J].Computer Networks,2007,51(10):2529-2553.
[5]孙利民.无线传感网络[M].北京:清华大学出版社,2005:135-155.
[6]Song Shuang,Qiu Xiaoxiao,Wang Jiaole,et al.Design and optimization strategy of sensor array layout for magnetic localization system[J].IEEE Sensors Joumal,2017,17(6):1849-1857.
[7]Muhammad Farooq-i-Azam,Muhammad N A.Location and position estimation in wireless sensor networks[M]//Wireless Sensor Networks:Current Status and Future Trends.Boca Raton:CRC Press,2013:179-214.
[8]Domingo-Perez F,Lazaro-Galilea J L,Wieser A,et al.Sensor placement determination for range-difference positioning using evolutionary multi-objective optimization[J].Expert Systems with Applications,2016,47(C):95-105.
[9]Huang Rui,Zaruba G V.Beacon deployment for sensor network localization[C]//Proceedings of the 2007 Wireless Communications and NETWORKING Conference.Hong Kong:IEEE,2007:3188-3193.
[10]Meng Wei,Xie Lihua,Xiao Wendong.Optimal TDOA sensor-pair placement with uncertainty in source location[J].IEEE Transactions on Vehicular Technology,2016,65(11):9260-9271.
[11]Chen Yingying,Francisco J A,Trappe W,et al.A practical approach to landmark deployment for indoor localization[C]//Proceedings of the 2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks,2006(SECON'06).Reston:IEEE,2006:365-373.
[12]Yuan Zimu,Li Wei,Xu Zhiwei,et al.Beacon node placement for minimal localization error[EB/OL].(2017-07-10)[2015-03-29].https://arxiv.org/abs/1503.08404.
[13]Wang Riming,Shen Baihua,Liu Yang.Optimization of sensor deployment for localization accuracy improvement[C]//Proceedings of the 2016 IEEE International Conference on Consumer Electronics-China(ICCE-China).Guangzhou:IEEE,2016:1-4.
[14]Liu Juan,Zhang Ying,Zhao Feng.Robust distributed node localization with error management[C]//Proceedings of the7th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York:ACM,2006:250-261.
[15]Yang Zheng,Liu Yunhao.Quality of trilateration:Confidence-based iterative localization[J].IEEE Transactions on Parallel and Distributed Systems,2010,21(5):631-640.
[16]Aomumpai S,Kondee K,Prommak C,et al.Optimal placement of reference nodes for wirelessindoor positioning systems[C]//Proceedings of the 2014 11th International Conference on Electrical Engineering/Electronics,Computer,Telecommunications and Information Technology.Nakhon Ratchasim:IEEE,2014:1-6.
[17]Moore D,Leonard J,Rus D,et al.Robust distributed network localization with noisy range measurements[C]//Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems.New York:ACM,2004:50-61.
[18]Chen Yourong,Lu Siyi,Chen Junjie,et al.Node localization algorithm of wireless sensor networks with mobile beacon node[J].Peer-to-Peer Networking and Applications,2017,10(3):795-807.
[19]Xia Xinjiang,Hu Gang,Wang Yehua.Study on improved algorithm based on concentric circles localization[J].Computer Science,2012,39(6):68-71.[夏心江,胡钢,王烨华.基于同心圆定位算法的改进算法研究[J].计算机科学,2012,39(6):68-71.]
[20]Zhou Yan,Zhao Hai,Zhang Jun,et al.Location error analysis of pervasive computing[J].Acta Electronica Sinica,2009,37(2):382-386.
[21]Xiong Zhiguang,Shi Weiren,Xu Lei,et al.Trilateration localization algorithm based on weighted disposal[J].Computer Engineering and Applications,2010,46(22):99-102.[熊志广,石为人,许磊,等.基于加权处理的三边测量定位算法[J].计算机工程与应用,2010,46(22):99-102.]
[22]Zhao Hai,Sun Peigang,Zhang Wenbo,et al.Research on reference nodes placement and selection of ubiquitous computing locating service[J].Frontiers of Electrical and Electronic Engineering,2007,2(1):13-22.
[23]Li Haicheng,Zhang Rui,Zhou Yan.Research on deployment of locating unit in ubiquitous computing[J].Computer Science,2010,37(1):142-145.[李海成,张锐,周艳.普适计算中定位单元布局研究[J].计算机科学,20 10,37(1):142-145.]
[24]Sun Peigang,Zhao Hai,Zhang Wenbo,et al.Research on reference nodes placement and selection of ubiquitious computing locating service[J].Acta Electronica Sinica,2006,34(8):1456-1463.[孙佩刚,赵海,张文波,等.普适计算中定位服务的参考点布置及选择算法[J].电子学报,2006,34(8):1456-1463.]
[25]Kim S W,Lee B T.Scalable DV-Hop localization algorithm with constrained multilateration for wireless sensor network[J].IEICE Transactions on Communications,2009,E92.B(10):3075-3078.
[26]Zhao Hao,Zhang Kuan,Zhu Jian,et al.Error analysis and improvement of ultrasonic distance measuring based on TDOA[J].Journal of Northeastern University(Natural Science),2011,32(6):802-805.[赵海,张宽,朱剑,等.基于TDOA的超声波测距误差分析与改进[J].东北大学学报(自然科学版),2011,32(6):802-805.]
[27]Wu Xiaojun,Yang Zhanzhong,Zhao Ming.A uniform searching particle swarm optimization algorithm[J].Acta Electronica Sinica,2011,39(6):1261-1266.[吴晓军,杨战中,赵明.均匀搜索粒子群算法[J].电子学报,2011,39(6):1261-1266.]