基于约束粒子群优化的三维无线传感器网络定位算法研究
|
摘要
无线传感器网络(Wireless Sensor Network, WSN)是一种新型网络技术,该技术集成了传感器技术、无线通信技术、微机电系统技术及嵌入式技术等技术于一体。主要是通过WSN中部署的传感器节点间的相互协作,对所检测的对象进行实时感知和信息采集,并将处理结果传送至网络终端用户。该技术己广泛应用在军事、环境监测、智能家居、智能交通、商业应用等各个领域。
对于WSN中传感器节点的信息采集工作,往往与节点定位技术相关,而没有位置信息的数据是毫无意义的。目前,大多数无线传感器网络定位算法都是基于二维平面的的算法,但在实际应用中,节点分布往往部署在地形较为复杂的三维空间环境中,因此,本论文重点探讨三维空间环境下节点位置的计算方法。
本论文首先阐述了WSN的概念、常用的定位算法、以及基于接受信号强度指示(Received Signal Strength Indicator, RSSI)的测距机制。重点研究了在三维空间环境下的两种定位算法：一是在传统定位算法之上,基于泰勒展开的加权最小二乘定位算法(Taylor Weighted-Least-Squares, Taylor-WLS);二是在粒子群优化算法(Particle Swarm Optimization, PSO)的基础上,引入了惩罚函数进行约束的思想,提出了基于惩罚函数的约束粒子群优化算法的无线传感器网络节点定位(Constraint Particle Swarm Optimization, CPSO)算法。
本文在MATLAB仿真平台上对提出的Taylor-WLS算法和CPSO算法进行仿真实验,分别从节点密度、锚节点密度、测距半径和测距误差四个因素的影响下进行对比,验证了CPSO算法在不同程度上都优于Taylor-WLS算法,该算法抗误差性较强、收敛性较好,同时对于无线传感器网络所需要的硬件设备也较少,节省了应用成本。
Wireless Sensor Network (WSN) is a new ad-hoc network technology whichcombines sensor technology, wireless communication, Micro-Electro-Mechanismsystem and embedded technology. In WSNs, lots of sensor nodes work cooperativelyto gather and process information in real-time, and send the results to network users.This technology can be widely applied in military applications, environmentmonitoring, smart home, intelligent transport system and other commercialapplications.
The information collection technology in WSNs, it often associated with the nodelocalization technology, as there is no sense in practical applications without nodeposition information. By now, most of positioning algorithms are based ontwo-dimensional space. But in practice, the distribution of nodes is discussed in thecomplex three-dimensional space. Therefore, it's a hot point to discuss the locationalgorithm in three-dimensional space.
This paper firstly states the concept of WSN and the basic positioning algorithms.Secondly, on the basis of Received Signal Strength Indicator (RSSI), we mainlydiscussed two positioning algorithms in three-dimensional space. The first algorithmis on the basis of traditional positioning algorithm, we put forward TaylorWeighted-Least-Squares (Taylor-WLS) positioning algorithm. Another algorithm isthe Constraint Particle Swarm Optimization (CPSO) positioning algorithm, which ison the basis of Particle Swarm Optimization (PSO), and introducing the penaltyfunction thought in dealing with constraint problem.
Finally, these two positioning algorithms are validated by MATLAB simulationexperiments from four factors: node density, anchor node density, distance radius andranging error. This shows that CPSO positioning algorithm is superior to Taylor-WLSin different degree, CPSO has more robust against errors, better convergence and lesshardware investment, etc.
对于WSN中传感器节点的信息采集工作,往往与节点定位技术相关,而没有位置信息的数据是毫无意义的。目前,大多数无线传感器网络定位算法都是基于二维平面的的算法,但在实际应用中,节点分布往往部署在地形较为复杂的三维空间环境中,因此,本论文重点探讨三维空间环境下节点位置的计算方法。
本论文首先阐述了WSN的概念、常用的定位算法、以及基于接受信号强度指示(Received Signal Strength Indicator, RSSI)的测距机制。重点研究了在三维空间环境下的两种定位算法：一是在传统定位算法之上,基于泰勒展开的加权最小二乘定位算法(Taylor Weighted-Least-Squares, Taylor-WLS);二是在粒子群优化算法(Particle Swarm Optimization, PSO)的基础上,引入了惩罚函数进行约束的思想,提出了基于惩罚函数的约束粒子群优化算法的无线传感器网络节点定位(Constraint Particle Swarm Optimization, CPSO)算法。
本文在MATLAB仿真平台上对提出的Taylor-WLS算法和CPSO算法进行仿真实验,分别从节点密度、锚节点密度、测距半径和测距误差四个因素的影响下进行对比,验证了CPSO算法在不同程度上都优于Taylor-WLS算法,该算法抗误差性较强、收敛性较好,同时对于无线传感器网络所需要的硬件设备也较少,节省了应用成本。
Wireless Sensor Network (WSN) is a new ad-hoc network technology whichcombines sensor technology, wireless communication, Micro-Electro-Mechanismsystem and embedded technology. In WSNs, lots of sensor nodes work cooperativelyto gather and process information in real-time, and send the results to network users.This technology can be widely applied in military applications, environmentmonitoring, smart home, intelligent transport system and other commercialapplications.
The information collection technology in WSNs, it often associated with the nodelocalization technology, as there is no sense in practical applications without nodeposition information. By now, most of positioning algorithms are based ontwo-dimensional space. But in practice, the distribution of nodes is discussed in thecomplex three-dimensional space. Therefore, it's a hot point to discuss the locationalgorithm in three-dimensional space.
This paper firstly states the concept of WSN and the basic positioning algorithms.Secondly, on the basis of Received Signal Strength Indicator (RSSI), we mainlydiscussed two positioning algorithms in three-dimensional space. The first algorithmis on the basis of traditional positioning algorithm, we put forward TaylorWeighted-Least-Squares (Taylor-WLS) positioning algorithm. Another algorithm isthe Constraint Particle Swarm Optimization (CPSO) positioning algorithm, which ison the basis of Particle Swarm Optimization (PSO), and introducing the penaltyfunction thought in dealing with constraint problem.
Finally, these two positioning algorithms are validated by MATLAB simulationexperiments from four factors: node density, anchor node density, distance radius andranging error. This shows that CPSO positioning algorithm is superior to Taylor-WLSin different degree, CPSO has more robust against errors, better convergence and lesshardware investment, etc.
引文
[1]陈敏,王擘,李军华,等.无线传感器网络原理与实践.北京：化学工业出版社,2011
[2]彭力.无线传感器网络技术.北京：冶金工业出版社,2011
[3]Kim K, Lew W.MBAL:mobile beacon-assisted localization scheme for wireless sensor network[C]. Proc. Of16th International Conference on Computer Communications and Networks, Hawaii USA,2007:57-62
[4]Steere DC, Baptista A, McNamee D. Research challenges in environmental observation and forecasting system[C]. Proc of the6th ACM/IEEE MobiCOM, Boston, MA, USA: ACM dPress,2000:292-299
[5]张荣磊,刘琳岚,舒坚,等.基于多维定标的无线传感器网络三维定位算法[J].计算机应用研究,2009,26(8)：3100-3105
[6]He Tian, Huang Chengdu, Blum B M, etc. Range-free localization schemes in largescale sensor networks [C] Proceeding of the9th Annual International Conference on Mobile computing and networking(MobiCom), SanDiego, California, USA:ACM Press,2003:81-95
[7]魏雄烈.基于粒子群算法的三维无线传感器网络定位方法研究：[硕士学位论文].北京：北京邮电大学,2011
[8]诸燕平.无线传感器网络节点定位算法研究：[博士学位论文].南京：南京航空航天大学,2009
[9]Grios L, Bychovskiy V.Esttrin D. Locating tiny sensors in time and space: A case study[C]. In:Werner B.ed.Proc.of the2002IEEE Int' Conf. on Computer Design: VLSI in Computers and processors. Freiburg: IEEE Computer society,2002,214-219.
[101高守玮,吴灿阳,杨超,等.Zigbee技术实践教程.北京：北京航空航天大学出版社,2011
[11]Andries P. Engelbrecht,谭营,等.计算群体智能基础.北京：清华大学出版社,2009
[12]Shi Y, Eberhart RC. A modified particle swarm optimizer[C]. In: Proc of IEEE International Conference on Evolutionary Computation, Anchorage,1988,69-73
[13]陈宝林.最优化理论与算法.北京：清华大学出版社,2005
[14]崔秀锋.无线传感器网络中基于RSSI的三维定位改进算法研究：[硕士学位论文].太原：太原理工大学,2011
[15]张荣磊,刘琳岚,舒坚,等.基于多维定标的无线传感器网络三维定位算法[J].计算机应用研究,200,26(8)：3100-3105
[16]杜巧玲.无线传感器网络三维节点定位问题的研究：[博士学位论文].吉林：吉林大学,2009
[17]黎大鹏,程良伦.基于锚节点动态选择和调整的传感器网络定位.计算机应用与软件,2010,27(3),32-34
[18]何坚勇.最优化方法.北京：清华大学出版社,2007
[19]Bulusu N, Heidemann J, Estrin D. GPS-Less low cost outdoor localization for very small devices. IEEE Personal Communications,2000,7(5),28-34
[20]张志勇.精通MATLAB6.5版.北京：北京航空航天大学出版社.2003
[2]彭力.无线传感器网络技术.北京：冶金工业出版社,2011
[3]Kim K, Lew W.MBAL:mobile beacon-assisted localization scheme for wireless sensor network[C]. Proc. Of16th International Conference on Computer Communications and Networks, Hawaii USA,2007:57-62
[4]Steere DC, Baptista A, McNamee D. Research challenges in environmental observation and forecasting system[C]. Proc of the6th ACM/IEEE MobiCOM, Boston, MA, USA: ACM dPress,2000:292-299
[5]张荣磊,刘琳岚,舒坚,等.基于多维定标的无线传感器网络三维定位算法[J].计算机应用研究,2009,26(8)：3100-3105
[6]He Tian, Huang Chengdu, Blum B M, etc. Range-free localization schemes in largescale sensor networks [C] Proceeding of the9th Annual International Conference on Mobile computing and networking(MobiCom), SanDiego, California, USA:ACM Press,2003:81-95
[7]魏雄烈.基于粒子群算法的三维无线传感器网络定位方法研究：[硕士学位论文].北京：北京邮电大学,2011
[8]诸燕平.无线传感器网络节点定位算法研究：[博士学位论文].南京：南京航空航天大学,2009
[9]Grios L, Bychovskiy V.Esttrin D. Locating tiny sensors in time and space: A case study[C]. In:Werner B.ed.Proc.of the2002IEEE Int' Conf. on Computer Design: VLSI in Computers and processors. Freiburg: IEEE Computer society,2002,214-219.
[101高守玮,吴灿阳,杨超,等.Zigbee技术实践教程.北京：北京航空航天大学出版社,2011
[11]Andries P. Engelbrecht,谭营,等.计算群体智能基础.北京：清华大学出版社,2009
[12]Shi Y, Eberhart RC. A modified particle swarm optimizer[C]. In: Proc of IEEE International Conference on Evolutionary Computation, Anchorage,1988,69-73
[13]陈宝林.最优化理论与算法.北京：清华大学出版社,2005
[14]崔秀锋.无线传感器网络中基于RSSI的三维定位改进算法研究：[硕士学位论文].太原：太原理工大学,2011
[15]张荣磊,刘琳岚,舒坚,等.基于多维定标的无线传感器网络三维定位算法[J].计算机应用研究,200,26(8)：3100-3105
[16]杜巧玲.无线传感器网络三维节点定位问题的研究：[博士学位论文].吉林：吉林大学,2009
[17]黎大鹏,程良伦.基于锚节点动态选择和调整的传感器网络定位.计算机应用与软件,2010,27(3),32-34
[18]何坚勇.最优化方法.北京：清华大学出版社,2007
[19]Bulusu N, Heidemann J, Estrin D. GPS-Less low cost outdoor localization for very small devices. IEEE Personal Communications,2000,7(5),28-34
[20]张志勇.精通MATLAB6.5版.北京：北京航空航天大学出版社.2003