论文部分内容阅读
摘 要：无线定位是车联网中各应用的基础，对实时性和精度要求更高。基于此，本文提出了一个在WAVE系统下基于混合高斯模型的位置指纹定位算法。该算法由离线训练和在线定位两部分组成，采用GMM对离线训练阶段的指纹数据库进行聚类建模处理，并在定位阶段对结果采用多点均值方法，不仅降到了系统定位误差，也减少了定位阶段的运算量，提高了定位的实时性。实验结果表明，该算法有较好的定位精度和实时性，为WAVE环境下的快速定位进一步研究提供有效参考价值。
关键词：车联网WAVE；高斯混合模型；EM算法；定位系统
Abstract：Wireless Location is the basis of each vehicle networking applications， needing real-time and high precision. So as，we propose an algorithm for fingerprint positioning based on a Gaussian mixture model（GMM） in the WAVE system，which consists of an offline training phase and a real time localization phase. On offline training phase， we use GMM clustering process the whole fingerprint database，and use the multi-point average method processing results of the positioning on a real time localization phase， which not only reduces the system positioning errors， but also reduces the amount of computation， and improves real-time positioning. Experimental results show that the algorithm has better performance in both accuracy and real-time， and also provides effective reference value for further researching the fast positioning in WAVE environment.
Key words：Internet of Vehicles；WAVE；GMM；EM；Positioning Systems
1 引言
2013年我国机动车数量突破2.5亿辆，较2012年增长了13.7%。随着汽车的普及，道路拥挤的加剧，平均每个驾驶员在汽车上的时间越来越多，车载导航和车载信息服务、娱乐服务等需求日益猛烈。而车联网显然是实现这种需求的最佳形式。所谓的车联网是指利用先进传感技术、网络技术、计算技术、控制技术、智能技术，对道路和交通进行全面感知，实现多个系统间大范围、大容量数据的交互，对每一辆汽车进行交通全程控制，对每一条道路进行交通全时空控制，以提供交通效率和交通安全为主的网络与应用[1]。目前，世界各国都在大力开展针对车联网的研究。为此，IEEE委员会制定了WAVE（Wireless Access in vehicular Environment）协议栈，专门用于车联网系统。WAVE协议栈将网络设备分为RSU（Road-Side Unit）和OBU（On-Board Unit）两类。其中，RSU所扮演角色即是AP，OBU设备属于车载设备。RSU一般安装固定在道路两侧，并利用有线或无线的方式将其与互联网联通。RSU和OBU之间基于WAVE协议栈定义的报文格式进行交互通信。如今，随着苹果CarPlay车载系统的发布，车联网必将加速普及。
在行车安全和各种车辆应用需求中，车辆移动定位正是其中的关键基础。目前广泛使用的是基于GPS的室外定位技术，然而，GPS信号很容易受到障碍物的干扰和阻断，在密集的城市地带、隧道、室内等环境中，定位误差比较大，精度难以满足实际要求。具体到WAVE技术，因为在实际使用中WAVE系统需要设置大量的RSU（Road-Side Unit），即路边单元设备，那么利用其进行行车定位将具有很好的研究和应用价值。
当前，可供WAVE系统使用的无线定位方式有多种，基于测距的定位方式主要有TOA（Time of Arrival）、TDOA（Time Difference of Arrival）、AOA （Angle of Arrival）和RSSI（Received Signal Strength Indicator）[2]。TOA需要精确的时钟同步，TDOA需要AP配备超声波收发装置，AOA需要有天线阵列或麦克风阵列，这三种定位对硬件要求较高，能量消耗较大。而WAVE协议栈是一系列无线通信协议标准的统称，其组成包括IEEE 802.11p协议及IEEE 1609系列协议。利用WAVE系统的RSSI进行定位是简单、经济的选择。基于RSSI测距定位的原理是已知发射节点的发射信号强度，接收节点根据收到信号的强度，计算出信号的传播损耗，利用理论或经验模型将传输损耗转化为距离[3]，再根据相关定位算法计算出位置，包括三边测量法，三角测量法，加权质心算法，极大似然值估值算法等。这些定位算法的关键是测出待定位点与发射点的物理距离，距离越精确，定位的精度就越高。但是无线信号传播环境复杂多变，信号强度通常会遭遇传播路径损耗、多径衰落以及慢衰落等。因此在WAVE系统中，基于RSSI的测距的定位方式，误差也很大。 在实际情况中，无线信号在传播过程中经过吸收衰减、反射、衍射、多径衰落和阴影效应后，在不同的物理位置形成特定的信号状态，常称为位置指纹信息。基于此，我们采用基于高斯混合模型（GMM，Gaussian Mixture Model）[4]的位置指纹的定位方式。
2 基于GMM的指纹定位算法
2.1 位置指纹定位原理
一般无线指纹定位主要分为离线训练和在线定位两个阶段。主要流程如图1所示。
⑴离线阶段：在目标区域内，WAVE终端在有限个样本点处从周围的AP采集信号，测量从邻近若干AP接收的信号强度，并记录自身位置（Lat，Lon）。同时，终端捕获观测AP MAC作为识别信息。然后将包含AP识别信息、AP信号强度和对应观测样本点位置等信息的先验数据保存，建立信号指纹数据库。第j次观测所得的原始数据M（j）可以描述为下述形式：
⑵在线定位阶段：定位终端扫描接收范围内的各个AP，并根据各AP的信号强度，在指纹数据库中找出与所观测AP信号强度最接近的一条指纹记录，并将此记录中的位置信息作为终端的位置。常用的匹配方法有最近邻法（NN，Nearest Neighborhood）、K近邻法（KNN，K Nearest Neighborhood）、K加权近邻法（WKNN，Weighted K Nearest Neighborhood）、贝叶斯概率算法[5]等。
2.2 GMM聚类模型及EM求解算法
位置指纹数据库建立之后，在线定位阶段需将待定位点所获得的RSSI矢量（RSSI1，RSSI2，RSSI3，…RSSIN）与指纹数据库中的指纹数据进行匹配。在匹配的处理过程中，RSSI矢量必需与每一个指纹数据进行匹配计算，才能找到最佳的估计位置坐标。如果数据库的指纹数据量很大，则匹配过程将非常的耗时，如果定位应用实时性要求较高，则根本无法满足使用。
基于以上原因，在利用位置指纹定位方法对行车进行定位时必须有效解决延时的问题。如果使用聚类的方法在离线训练时对采集到的指纹数据进行分类则可以有效的解决在线匹配时的数据处理量。
离线训练阶段对指纹数据进行聚类处理的方法有很多种，考虑到移动下的精度以及实用性，可以用GMM模型来进行比较完备的聚类。
2.2.1 GMM聚类模型
⑴针对整个数据样本，记共有N个位置点的指纹数据组成一个大样本，这个样本可以分成K个小分类，每个小分类自成一个小样本，记属于第i个小分类的样本集合为L（i）：
单个分类服从多维单高斯PDF（概率密度函数）：
现在把K个分类混合，得到每个位置点样本个体的混合PDF，也即GMM：
2.2.2 EM算法求解GMM模型参数
用EM算法求解GMM模型参数，令
⑴初始化，k个高斯成分，初始参数：
⑵E-步：对于每个rss的样本对象，计算每个对象属于每个分布的概率
⑶M-步：给定期望步得到的概率，找出最大化该期望似然的新的参数估计更新第j个分量的权重：
更新均值矢量：
更新协方差矩阵：
（4）若 满足下式收敛条件，迭代运算结束，则
期望步与最大化步交替迭代运算，直到系统似然函数不再增加或增加的很小
2.3 基于RSSI的GMM定位
本文用WAVE系统RSU的RSSI作为位置指纹，实现无线终端的定位。整个定位系统的架构如下图2所示：
其中，RSU即AP接入点放置在固定的位置，并用有线或无线方式将其与定位服务器连接；OBU代表移动设备，在离线训练阶段将每一个采样点的位置指纹信息提交到定位服务器构建指纹数据库，在线定位阶段OBU采集RSU的RSSI信息后请求定位服务器进行定位处理；定位服务器（Position Server）负责建立和维护位置指纹数据库，并处理定位信息。
系统工作过程如下：
⑴离线训练阶段，OBU设备在不同的位置采样点以主动方式扫描其所在范围内可以探测到的WSA（WAVE Service Announcement），分析其所收集到的WSA，选择加入某个RSU所建立的网络；然后设定此OBU设备的扫描时间间隔和扫描次数，扫描周围的RSU基站，收集其RSSI值并以此组成当前所在位置的指纹信息，最后通过网络通信经RSU提交至定位服务器。对每一个指纹采样点依次做同样的处理，最终采集的所有指纹信息构建成完整的指纹数据库。采集完毕后，采用上面的GMM聚类方法对指纹数据库进行处理。
⑵在线定位阶段，OBU设备以主动方式扫描其所在范围内可以探测到的WSA，然后选择加入某个 RSU所建立的网络；然后扫描周围的RSU基站，收集其RSSI值并以此组成当前所在位置的RSSI向量，通过RSU设备向定位服务器提交RSSI向量，定位服务器按照记录的GMM参数计算出待测点属于哪一分类。
在概率最大的L（i）分类中，再计算未知点位于分类样本中每个采样点的概率，结果中取概率最大的位置坐标
取前P个具有最大概率值的点的坐标均值为最终定位结果X：
（3）最后定位服务器通过RSU设备向OBU发送位置信息。
3 实验及评估
因硬件条件限制，以一个比较空旷的房间来模拟WAVE环境。本测试的结果将对于后续在动态车载环境下更进一步的研究和实验，提供有效参考作用。
本测试的平面示意图如下所示：
其中红点表示RSU，黄点表示采样点，蓝点表示测试点（蓝点也属于采样点）。位置信息没有使用GPS模块获得真正的位置信息，而是手动方式输入相对位置坐标。
离线训练阶段，取采样点的间隔为60cm，在每个采样的点上OBU扫描周围的RSU基站，设定描述次数为20次，每次时间间隔为10秒，记录各个RSU无线信号RSSI的平均值与方差。根据这些RSSI信息和当前的位置信息组成一条位置指纹信息。采样完毕后，进行数据GMM聚类处理。 在线定位阶段，OBU设备在不同的位置点进行定位测试。取前P个具有最大概率值的点的坐标平均值作为最终定位结果。在每个测试点，分别测试三次取平均结果。测试数据的平均误差统计结果如下表所示：
对测试数据处理，可得到定位结果平均精度如下图所示：
由表1可知，B点的误差最大，达6.36%，随着取最大概率值个数的增大，B点的误差有一个明显的下降，然后趋于稳定，保持在4%左右。观察其它位置点也有类似规律，说明GMM 概率最大的定位结果往往分布在真实位置的四周。结合图4也表明，随着取最大概率值个数的增大，平均误差也趋于稳定。从图4中也可以看出，平均误差维持在2.6米，这个误差值偏大，主要由室内环境的强反射、离RSU太近及采样间隔太近造成。后续研究，可以适当增大采样点间隔和数量，并在室外进行，以此降到误差，提高定位精度。
4 总结
本文提出了一个在WAVE系统下基于GMM的位置指纹定位方法，并通过实验验证和评估了该方法的可行性。实验结果表明，该方法在定位的精度和实时性方面均有较好的结果。此外在终端低速移动的情况下，该定位方法表现稳定。下一步工作是继续完善该算法，将多次聚类和快速聚类方法结合，以进一步缩减运算量，提高定位响应能力。同时将测试环境转移到户外，提高移动终端速度，来进一步检验该方法，并不断完善，以期符合WAVE环境下的应用。
[参考文献]
[1]百度百科.车联网[EB/OL].http：//baike.baidu.com/view/3162798.htm.
[2]董梅，杨曾，张健，等.基于信号强度的无线局域网定位技术[J].计算机应用，2004，24（12）：49-52.
[3]Bahl P，Padmanabhan V N.RADAR：An In-building RF-based User Location and Tracking System[C].Proc.of 2000 Annual Joint Conference of the IEEE Computer and Communications Societies.[S.l.]：IEEE Computer Society，2000.
[4]Roos T，Myllymaki P，Tirri H，et al.A Probabilistic Approach to WLAN User Location Estimation[J].International Journal of Wireless Information Networks，2002，9（3）：155-164.
[5]ITO S，KAWAGUCHI N.Bayesian Based Location Estimation System Using Wireless LAN.In Proceedings of the 3rd International Conference on Pervasive Computing and Communications Workshops，2005，273-278.
[6]谢鹏.基于WAVE协议栈的车联网通信终端研究及定位系统实现.华南理工大学.2013.
关键词：车联网WAVE；高斯混合模型；EM算法；定位系统
Abstract：Wireless Location is the basis of each vehicle networking applications， needing real-time and high precision. So as，we propose an algorithm for fingerprint positioning based on a Gaussian mixture model（GMM） in the WAVE system，which consists of an offline training phase and a real time localization phase. On offline training phase， we use GMM clustering process the whole fingerprint database，and use the multi-point average method processing results of the positioning on a real time localization phase， which not only reduces the system positioning errors， but also reduces the amount of computation， and improves real-time positioning. Experimental results show that the algorithm has better performance in both accuracy and real-time， and also provides effective reference value for further researching the fast positioning in WAVE environment.
Key words：Internet of Vehicles；WAVE；GMM；EM；Positioning Systems
1 引言
2013年我国机动车数量突破2.5亿辆，较2012年增长了13.7%。随着汽车的普及，道路拥挤的加剧，平均每个驾驶员在汽车上的时间越来越多，车载导航和车载信息服务、娱乐服务等需求日益猛烈。而车联网显然是实现这种需求的最佳形式。所谓的车联网是指利用先进传感技术、网络技术、计算技术、控制技术、智能技术，对道路和交通进行全面感知，实现多个系统间大范围、大容量数据的交互，对每一辆汽车进行交通全程控制，对每一条道路进行交通全时空控制，以提供交通效率和交通安全为主的网络与应用[1]。目前，世界各国都在大力开展针对车联网的研究。为此，IEEE委员会制定了WAVE（Wireless Access in vehicular Environment）协议栈，专门用于车联网系统。WAVE协议栈将网络设备分为RSU（Road-Side Unit）和OBU（On-Board Unit）两类。其中，RSU所扮演角色即是AP，OBU设备属于车载设备。RSU一般安装固定在道路两侧，并利用有线或无线的方式将其与互联网联通。RSU和OBU之间基于WAVE协议栈定义的报文格式进行交互通信。如今，随着苹果CarPlay车载系统的发布，车联网必将加速普及。
在行车安全和各种车辆应用需求中，车辆移动定位正是其中的关键基础。目前广泛使用的是基于GPS的室外定位技术，然而，GPS信号很容易受到障碍物的干扰和阻断，在密集的城市地带、隧道、室内等环境中，定位误差比较大，精度难以满足实际要求。具体到WAVE技术，因为在实际使用中WAVE系统需要设置大量的RSU（Road-Side Unit），即路边单元设备，那么利用其进行行车定位将具有很好的研究和应用价值。
当前，可供WAVE系统使用的无线定位方式有多种，基于测距的定位方式主要有TOA（Time of Arrival）、TDOA（Time Difference of Arrival）、AOA （Angle of Arrival）和RSSI（Received Signal Strength Indicator）[2]。TOA需要精确的时钟同步，TDOA需要AP配备超声波收发装置，AOA需要有天线阵列或麦克风阵列，这三种定位对硬件要求较高，能量消耗较大。而WAVE协议栈是一系列无线通信协议标准的统称，其组成包括IEEE 802.11p协议及IEEE 1609系列协议。利用WAVE系统的RSSI进行定位是简单、经济的选择。基于RSSI测距定位的原理是已知发射节点的发射信号强度，接收节点根据收到信号的强度，计算出信号的传播损耗，利用理论或经验模型将传输损耗转化为距离[3]，再根据相关定位算法计算出位置，包括三边测量法，三角测量法，加权质心算法，极大似然值估值算法等。这些定位算法的关键是测出待定位点与发射点的物理距离，距离越精确，定位的精度就越高。但是无线信号传播环境复杂多变，信号强度通常会遭遇传播路径损耗、多径衰落以及慢衰落等。因此在WAVE系统中，基于RSSI的测距的定位方式，误差也很大。 在实际情况中，无线信号在传播过程中经过吸收衰减、反射、衍射、多径衰落和阴影效应后，在不同的物理位置形成特定的信号状态，常称为位置指纹信息。基于此，我们采用基于高斯混合模型（GMM，Gaussian Mixture Model）[4]的位置指纹的定位方式。
2 基于GMM的指纹定位算法
2.1 位置指纹定位原理
一般无线指纹定位主要分为离线训练和在线定位两个阶段。主要流程如图1所示。
⑴离线阶段：在目标区域内，WAVE终端在有限个样本点处从周围的AP采集信号，测量从邻近若干AP接收的信号强度，并记录自身位置（Lat，Lon）。同时，终端捕获观测AP MAC作为识别信息。然后将包含AP识别信息、AP信号强度和对应观测样本点位置等信息的先验数据保存，建立信号指纹数据库。第j次观测所得的原始数据M（j）可以描述为下述形式：
⑵在线定位阶段：定位终端扫描接收范围内的各个AP，并根据各AP的信号强度，在指纹数据库中找出与所观测AP信号强度最接近的一条指纹记录，并将此记录中的位置信息作为终端的位置。常用的匹配方法有最近邻法（NN，Nearest Neighborhood）、K近邻法（KNN，K Nearest Neighborhood）、K加权近邻法（WKNN，Weighted K Nearest Neighborhood）、贝叶斯概率算法[5]等。
2.2 GMM聚类模型及EM求解算法
位置指纹数据库建立之后，在线定位阶段需将待定位点所获得的RSSI矢量（RSSI1，RSSI2，RSSI3，…RSSIN）与指纹数据库中的指纹数据进行匹配。在匹配的处理过程中，RSSI矢量必需与每一个指纹数据进行匹配计算，才能找到最佳的估计位置坐标。如果数据库的指纹数据量很大，则匹配过程将非常的耗时，如果定位应用实时性要求较高，则根本无法满足使用。
基于以上原因，在利用位置指纹定位方法对行车进行定位时必须有效解决延时的问题。如果使用聚类的方法在离线训练时对采集到的指纹数据进行分类则可以有效的解决在线匹配时的数据处理量。
离线训练阶段对指纹数据进行聚类处理的方法有很多种，考虑到移动下的精度以及实用性，可以用GMM模型来进行比较完备的聚类。
2.2.1 GMM聚类模型
⑴针对整个数据样本，记共有N个位置点的指纹数据组成一个大样本，这个样本可以分成K个小分类，每个小分类自成一个小样本，记属于第i个小分类的样本集合为L（i）：
单个分类服从多维单高斯PDF（概率密度函数）：
现在把K个分类混合，得到每个位置点样本个体的混合PDF，也即GMM：
2.2.2 EM算法求解GMM模型参数
用EM算法求解GMM模型参数，令
⑴初始化，k个高斯成分，初始参数：
⑵E-步：对于每个rss的样本对象，计算每个对象属于每个分布的概率
⑶M-步：给定期望步得到的概率，找出最大化该期望似然的新的参数估计更新第j个分量的权重：
更新均值矢量：
更新协方差矩阵：
（4）若 满足下式收敛条件，迭代运算结束，则
期望步与最大化步交替迭代运算，直到系统似然函数不再增加或增加的很小
2.3 基于RSSI的GMM定位
本文用WAVE系统RSU的RSSI作为位置指纹，实现无线终端的定位。整个定位系统的架构如下图2所示：
其中，RSU即AP接入点放置在固定的位置，并用有线或无线方式将其与定位服务器连接；OBU代表移动设备，在离线训练阶段将每一个采样点的位置指纹信息提交到定位服务器构建指纹数据库，在线定位阶段OBU采集RSU的RSSI信息后请求定位服务器进行定位处理；定位服务器（Position Server）负责建立和维护位置指纹数据库，并处理定位信息。
系统工作过程如下：
⑴离线训练阶段，OBU设备在不同的位置采样点以主动方式扫描其所在范围内可以探测到的WSA（WAVE Service Announcement），分析其所收集到的WSA，选择加入某个RSU所建立的网络；然后设定此OBU设备的扫描时间间隔和扫描次数，扫描周围的RSU基站，收集其RSSI值并以此组成当前所在位置的指纹信息，最后通过网络通信经RSU提交至定位服务器。对每一个指纹采样点依次做同样的处理，最终采集的所有指纹信息构建成完整的指纹数据库。采集完毕后，采用上面的GMM聚类方法对指纹数据库进行处理。
⑵在线定位阶段，OBU设备以主动方式扫描其所在范围内可以探测到的WSA，然后选择加入某个 RSU所建立的网络；然后扫描周围的RSU基站，收集其RSSI值并以此组成当前所在位置的RSSI向量，通过RSU设备向定位服务器提交RSSI向量，定位服务器按照记录的GMM参数计算出待测点属于哪一分类。
在概率最大的L（i）分类中，再计算未知点位于分类样本中每个采样点的概率，结果中取概率最大的位置坐标
取前P个具有最大概率值的点的坐标均值为最终定位结果X：
（3）最后定位服务器通过RSU设备向OBU发送位置信息。
3 实验及评估
因硬件条件限制，以一个比较空旷的房间来模拟WAVE环境。本测试的结果将对于后续在动态车载环境下更进一步的研究和实验，提供有效参考作用。
本测试的平面示意图如下所示：
其中红点表示RSU，黄点表示采样点，蓝点表示测试点（蓝点也属于采样点）。位置信息没有使用GPS模块获得真正的位置信息，而是手动方式输入相对位置坐标。
离线训练阶段，取采样点的间隔为60cm，在每个采样的点上OBU扫描周围的RSU基站，设定描述次数为20次，每次时间间隔为10秒，记录各个RSU无线信号RSSI的平均值与方差。根据这些RSSI信息和当前的位置信息组成一条位置指纹信息。采样完毕后，进行数据GMM聚类处理。 在线定位阶段，OBU设备在不同的位置点进行定位测试。取前P个具有最大概率值的点的坐标平均值作为最终定位结果。在每个测试点，分别测试三次取平均结果。测试数据的平均误差统计结果如下表所示：
对测试数据处理，可得到定位结果平均精度如下图所示：
由表1可知，B点的误差最大，达6.36%，随着取最大概率值个数的增大，B点的误差有一个明显的下降，然后趋于稳定，保持在4%左右。观察其它位置点也有类似规律，说明GMM 概率最大的定位结果往往分布在真实位置的四周。结合图4也表明，随着取最大概率值个数的增大，平均误差也趋于稳定。从图4中也可以看出，平均误差维持在2.6米，这个误差值偏大，主要由室内环境的强反射、离RSU太近及采样间隔太近造成。后续研究，可以适当增大采样点间隔和数量，并在室外进行，以此降到误差，提高定位精度。
4 总结
本文提出了一个在WAVE系统下基于GMM的位置指纹定位方法，并通过实验验证和评估了该方法的可行性。实验结果表明，该方法在定位的精度和实时性方面均有较好的结果。此外在终端低速移动的情况下，该定位方法表现稳定。下一步工作是继续完善该算法，将多次聚类和快速聚类方法结合，以进一步缩减运算量，提高定位响应能力。同时将测试环境转移到户外，提高移动终端速度，来进一步检验该方法，并不断完善，以期符合WAVE环境下的应用。
[参考文献]
[1]百度百科.车联网[EB/OL].http：//baike.baidu.com/view/3162798.htm.
[2]董梅，杨曾，张健，等.基于信号强度的无线局域网定位技术[J].计算机应用，2004，24（12）：49-52.
[3]Bahl P，Padmanabhan V N.RADAR：An In-building RF-based User Location and Tracking System[C].Proc.of 2000 Annual Joint Conference of the IEEE Computer and Communications Societies.[S.l.]：IEEE Computer Society，2000.
[4]Roos T，Myllymaki P，Tirri H，et al.A Probabilistic Approach to WLAN User Location Estimation[J].International Journal of Wireless Information Networks，2002，9（3）：155-164.
[5]ITO S，KAWAGUCHI N.Bayesian Based Location Estimation System Using Wireless LAN.In Proceedings of the 3rd International Conference on Pervasive Computing and Communications Workshops，2005，273-278.
[6]谢鹏.基于WAVE协议栈的车联网通信终端研究及定位系统实现.华南理工大学.2013.