一种基于分布式子空间的共享单车定位算法

何涛 张健 徐鹤 姜彦男

摘 要： 共享单车逐步成为中国规模最大的城市交通代步解决方案，为城市人群提供更加快捷、环保的城市出行服务。为了进一步提高共享单车的利用率和安全性，分析在城市复杂环境下影响定位的主要因素，结合现有的共享单车的定位方式，提出一种基于层次分布式子空间的定位算法。通过各点之间的接收信号强度指示以及标准点坐标定位实现共享单车的精准定位。仿真结果表明，所提出的算法较现有的方法具有较高精度的定位，能够提高单车的使用率以及实现对单车状态的实时反馈。

关键词： 共享单车； 节点定位； 层次分布式子空间； 定位算法； 城市出行； 信号强度指示

中图分类号： TN953+.7?34 文献标识码： A 文章编号： 1004?373X（2018）18?0017?05

A shared bicycle localization algorithm based on distributed subspace

HE Tao1，2， ZHANG Jian2， XU He3， JIANG Yannan2

（1. Engineering Training Center， Nanjing University of Posts and Telecommunications， Nanjing 210003， China；

2. School of Electronic Science and Engineering， Nanjing University of Posts and Telecommunications， Nanjing 210003， China；

3. School of Computing， Nanjing University of Posts and Telecommunications， Nanjing 210003， China）

Abstract： The shared bicycle has gradually become China′s largest urban transport solution that can provide a more convenient and environmental?friendly going?out service for the urban population. To further improve the utilization rate and safety of the shared bicycle， a localization algorithm based on hierarchical distributed subspace is proposed by analyzing the main factors of affecting the localization in urban complex environments and combining with the current shared bicycle localization methods. Accurate localization of the shared bicycle is achieved by means of received signal strength indication among various points and coordinate positioning of standard points. The simulation results show that in comparison with the current methods， the proposed algorithm has higher accuracy in localization， can improve the utilization rate of the bicycle， and realize real?time feedback of bicycle status.

Keywords： shared bicycle； node localization； hierarchical distributed subspace； localization algorithm； urban travel； signal strength indication

随着经济的快速提升，汽车工业的生产制造迅猛发展，我国近些年来汽车的拥有量在急剧增加[1]，加之我国大量人口涌入城市，城市交通拥堵已成为正常现象。为了有效地缓解交通压力和解决短距离出行问题，一系列的共享单车出现在城市人口密集的地方，其提出“解决最后一公里出行问题”[2]的理念和操作便捷的软件为城市人群提供了更加快捷高效，绿色低碳的城市出行服务。目前，共享单车的定位方法为两种：

1） 基于GPS定位的共享单车在内部通过GSM模块发送信息与云端实现通信，实时将车辆所处的位置以及车辆当前状态上传云端数据库。实现对共享单车位置准确无时差监控和具体定位。但是此方法有许多不足。每一辆单车都需要内置电源、GPS模块、GSM模块以及智能锁，成本经调查大约3 000元，成本的上升意味着防盗风险的急剧提升；单车[3]重量为25 kg，严重影响了骑车用户的使用体验，在复杂的环境增加了骑行的难度。

2） 目前使用的GPS定位芯片，精度[4]大约10 m，与体积较小的单车相比会产生很大的误差，经实验数据显示，在高楼和立交桥等复杂环境下，集中摆放的装有GPS定位芯片的共享单车会产生60%～70%不同程度的定位漂移。

无GPS的共享单车定位方法只配有一个固定密码的机械锁，定位方法通过APP客户端或者微信公众号来访问骑车用户者的手机，通过获得手机GPS定位的位置，间接得到共享单车的起始和结束位置，来实现对单车位置的定位和监控。其较低的生产成本以及简单的使用方法得到了许多用户者的青睐。但是由于人为的因素、天气环境以及位置获取时差等因素，实际的位置和软件提供位置有很大的差距；在城市的早晚高峰，中转站会堆积大量单车，这样的效应称为“潮汐”现象[5]，反应了单车分布的不均匀以及无法及时调配单车数量的问题，不但造成了大量的资源浪费，同样影响了社会的正常运行；用于车辆采用的是有固定密码的机械锁和无法对车辆实现具体的定位，导致大量共享单车的破坏和丢失，增加了公司后期投入的运营成本和维修的成本。

1 新算法的提出

为了更好地提升共享单车的位置，降低成本，合理分配不同位置单车数量等一系列问题，结合机器学习[6]发展的思路，本文提出一种基于分布式子空间的单车定位算法（Localization based on Distributed Subspace， LDS）。把传统的定位方法转换成对不同节点分类学习问题，把未知节点与锚节点的距离作为特征向量，依据未知节点和锚节点的相似度对未知节点进行分类。算法流程图如图1所示。

1.1 锚节点部署

锚节点是无线传感器网络中已知自身位置的节点，其部署采用规则部署，依据采集的单车路线行驶以及车辆停放位置对锚节点的位置进行预估。假设在无线传感器网络平面中构建网格数据结构，由于每个网格单元都有相同的面积，因此网格单元中数据点的密度为落到单元中点个数，网格单元为稠密单元[7]的判决为：

式中：[NA]为网格单元的数据点数；[CA]为数据空间中总的数据点数；[ε]为密度阈值；density是在某一时刻t一个网络单元的密度。当密度大于设定的密度阈值[ε]，设定该单元为一个密集网络单元，部署锚节点，相对于稠密网格单元来说，大多数的网格单元包含非常少甚至空的数据点，这一类网格单元被称为稀疏网格单元。定义稀疏密度阈值为[θ]，当[density（t）≥θ]时，该网格单元是—个稀疏单元。对于稀疏网格单元的处理方法一般采用压缩的方法，在压缩后的稀疏网格单元部署锚节点。

1.2 分布式分类定位的实现

根据节点定位计算模式是由中心节点计算还是由节点自行计算，分为集中式定位（Centralized Localization）算法[8]和分布式定位（Distributed Localization）算法[9]。分布式定位的计算是在各个节点进行的，所以相比于集中式定位，整个网络的流量与计算量分布能够保持一个较为均衡的水平，降低能耗。

假设大规模无线传感器网络中，有M个节点部署在[L×L]的二维空间平面上。节点的通信距离r（[Xi]）（dis>0）相同，可以在理论通信范围内实现直接通信。假设存在k（k

1） 从未知节点集中选取一点为待分类点U，计算与锚节点集[X1，X2，…，XM]之间的距离，得到dis（U，X1），dis（U，X2），…，dis（U，XM）。

2） 将dis（U，X1），dis（U，X2），…，dis（U，XM）与通信距离r（[Xi]）比较，大于r（[Xi]）的值设定为离群值并且去除。

3） 对剩余的距离值从小到大排序，取前k个距离最小的样本以及对应的标签放入分布式分类集合NN中，最近邻数k值按剩余的距离值集合比例动态调整，避免因分类标签分布不均衡引起的分类错误。

4） 分布式分类集合NN中，对样本的标签计数，设定频率最高的类为待分类点U的标签。如果出现频率相同的类，则比较每个类中最小距离dis（U，La）的大小，距离最小的类为待分类点U的标签。

5） 返回步骤1），直到全部未知节点分类结束。

依据未知节点与锚节点的距离作为特征向量对未知节点进行分类，对相同类中的节点赋予相同的标签，实现对节点的分布式分类。

1.3 局部子空间定位的实现

对于分布式分类后的节点处于较小的通信范围，利用一定通信范围内的邻居节点构造一个局部子空间[10]。在子空间内，锚节点的具体位置可以依据子空间内不同环境做出对应的部署，然后参考全局结构和锚节点坐标，使用极大似然估计法迭代映射出类中所有未知节点的坐标。极大似然估计法（Maximum Likelihood Estimation）[11]是多边测量定位技术主要采用的方法。已知n个节点的坐标分别为（x1，y1），（x2，y2），…，（xn，yn），它们到节点D的距离分别为d1，d2，…，dn，假设节点D的坐标为（x，y）。则有如下公式：

根据标准的最小均值方差估计得线性公式为：

通过使用最小二乘法解[12]表达式可以计算得到公式为：[X=ATA-1ATB]。

局部子空间定位算法具有以下优势：

1） 在相同的测距方式下，两节点间的距离越接近，测距精度则越高，误差也就越小。

2） 通过已知局部子空间自身的范围判断节点位置的准确性，极大缩小节点坐标的误差，减少因为复杂环境带来的位置偏移。

3） 通过局部子空间可以最优化和最近化调配各个子空间单车的数量，保持每一个区域单车数量的相对平衡，防止“潮汐”现象的发生。

2 RSSI测距模型

RSSI（Received Signal Strength）基于接收信號强度指示信号[13]，通过测量从发送端到接收端的衰减来计算节点的距离。此测距方法实现比较简单，但信号强度易受环境等因素的影响，所以要根据具体环境构建传播模型，从而选定模型参数，然后使用Noisy Disk模型[14]模拟不同误差下的测量距离。

实验中通信节点选择CC2530芯片为通信芯片，CC2530是一款用于ZigBee技术[15]的2.4 GHz射频通信芯片，该芯片集成微处理器、模/数转化器、无线通信模块于一体，支持最新的ZigBee协议ZigBee 2007/PRO[16]，具有节点通信距离更远，组网性能更稳定可靠以及价格更低等诸多优势。

定义[Pij]为节点i接收到节点j的信号强度，并且假设[Pij]和[Pji]相等，[Pij]是对数正太随机分布随机变量，[Pij（dBm）=10lg Pij]服从高斯分布：

式中：[d0]为近地参考距离；[P0]是距离为[d0]时的接收信号强度；[dij]为距发射端的真实距离；[Pij]是距离为[dij]时的接收信号强度；[β]为以dB为单位的遮蔽因子；n是路径损耗指数，其大小取决于无线信号的传播环境，在室外遮蔽的城市空间内，n的取值为[2.7～5]之间。由于在实际环境中[β]是均值为0、标准差为[σ]的正态随机变量，为简化模型，将[σ]的影响忽略，选用以下模型：

式中：[d0]取值为1 m，参数A为节点i到节点j的距离[d0]为1 m测得平均接收信号强度；路径损耗指数n取值为3；[Pij]表示发射节点距离为[dij]时的接收信号强度。

3 算法实验及分析

在Matlab平台上通过使用RSSI测距模型对LDS算法进行仿真研究，分析算法的性能，所有算法都用Matlab语言编写。假设无线传感器网络部署在一个300 m[×]300 m的二维平面上，锚节点规则部署在设定位置，未知节点随机分布，每次的结果取10次仿真實验结果的均值。实验从以下三个方面对算法进行评价：锚节点数目；未知节点数；测距误差。

对于测距误差，不同技术的测距误差对实验仿真有很大的差别，因此在仿真实验中，节点间的通信距离使用Noisy Disk模型给出，如下：

式中：[dxi，xj]为节点i和j之间的实际距离；Noisy Disk模型假设距离测量值[dxi，xj]是以[dxi，xj]为均值，[ε]为方差的正态分布。

3.1 未知节点数量的变化对LDS算法的影响

在300 m[×]300 m的二维平面上，部署了12个锚节点，分别在未知节点数为80，100，120，140的情况下，对节点进行定位，得到的定位误差如表1所示。

由表1得，在未知节点数为80，100，120，140的情况下，得到的平均定位误差为1.604 m、1.523 m、1.585 m、1.657 m，相比于GPS导航中产生的十多米的误差，提高了定位精度，减小了单车的大距离“定位漂移”的现象。通过标准差可以显示LDS定位算法很稳定，数据集的离散程度小。不同未知节点数对LDS定位算法产生较小影响，相比于目前的共享单车定位方法在精度方面有了很大的提高。

3.2 锚节点数目的变化对LDS算法的影响

在300 m[×]300 m的二维平面上，部署了120个未知节点，分别在锚节点数为9，12，16的规则部署情况下，对节点进行定位，如图2所示。

图2中：十字标记为锚节点的位置；空心圆表示为未知节点的实际坐标；叉号表示为未知节点的预测坐标；空心圆和叉号相连的直线表示未知节点实际位置与估计位置的距离。测距误差[ε]为1。

在未知节点为120，未知节点数分别为9，12，16的情况下，LDS算法的误差如表2所示。锚节点数对定位误差结果的影响如图3所示。

从图3可知：

1） 未知节点数对LDS算法产生较小的影响，平均差和标准差保持水平。

2） 锚节点数为12和16的折线在锚节点数为9的下方，这是由于锚节点数目的增加，有效提高了定位精度，但是节点12和节点16的差距较小，显示一定区域内锚节点数目增加到一定值，定位精度保持平衡。

3.3 节点通信范围的变化对LDS算法的影响

当锚节点总数为12，在不同的节点通信半径下，未知节点总数为80，100，120对平均定位误差影响变化曲线如图4a）所示。当未知节点总数为100时，在不同的节点通信半径下，锚节点数为9，12，16对平均定位误差影响变化曲线如图4b）所示。从图4可以得知：通信半径越大，定位误差越小。当通信半径大于整个WSN区域长度的33%时，不同的未知节点数以及不同的锚点数对于LDS定位算法产生的误差较小，误差保持恒定不变。

4 结 论

目前共享单车的定位采用用户定位估算法，使得距离定位有较大的定位误差，为了有效地解决共享单车定位的问题，通过机器学习和无线传感器的有机结合，提出基于分布式子空间的单车定位算法。本算法的意义在于，相比于GPS高成本和低精度的环境下，降低成本并提升定位精度，有效解决“位置漂移”和“潮汐”等影响。在锚节点数越多的情况下，这种优势越明显，并且区域内的未知节点数的数目不会影响定位精度。实验结果表明，本文算法有效地提高了定位精度。

参考文献

[1] ZHOU Wei， MAJOR M， JIANG Yulin， et al. Special policy research of China Environment and Development International Cooperation Committee： Report on promoting urban green travel [R/OL]. （2013?11?13） [2015?03?23]. http：//www.docin.com/p?1101475823.html.

[2] TOMER A. Where the jobs are： employer access to labor by transit [R]. Washington， D.C.： Brookings Institution， 2012.

[3] 中商产业研究院.2017全球与中国市场共享单车深度研究报告[R].深圳：中商产业研究院，2017.

ASKCI Consulting. 2017 research report on shared bicycles in global and Chinese markets [R]. Shenzhen： ASKCI Consulting， 2017.

[4] 张锐，周崟，李庚基，等.GPS差分定位方法研究及其应用[J].山西电子技术，2017（1）：56?57.

ZHANG Rui， ZHOU Yin， LI Gengji， et al. Research and application of GPS differential positioning method [J]. Shanxi electronic technology， 2017（1）： 56?57.

[5] MA T， LIU C， ERDO?AN S. Bicycle sharing and transit： does capital bikeshare affect metrorail ridership in Washington， D.C.？ [J]. Transportation research record： journal of the transportation research board， 2015， 2534： 1?20.

[6] NGUYEN X， JORDAN M I， SINOPOLI B. A kernel?based learning approach to ad hoc sensor network localization [J]. ACM transactions on sensor networks， 2005， 1（1）： 134?152.

[7] 张净，孙志挥.GDLOF：基于网格和稠密单元的快速局部离群点探测算法[J].东南大学学报（自然科学版），2005，35（6）：863?866.

ZHANG Jing， SUN Zhihui. GDLOF： fast local outlier detection algorithm with grid?based and dense cell [J]. Journal of Southeast University （Natural science edition）， 2005， 35（6）： 863?866.

[8] 石欣，印爱民，张琦.基于K最近邻分类的无线传感器网络定位算法[J].仪器仪表学报，2014，35（10）：2238?2247.

SHI Xin， YIN Aimin， ZHANG Qi. Localization in wireless sensor networks based on K?nearest neighbor [J]. Chinese journal of scientific instrument， 2014， 35（10）： 2238?2247.

[9] ECKERT J， VILLANUEVA F， GERMAN R， et al. Distributed mass?spring?relaxation for anchor?free self?localization in sensor and actor networks [C]// Proceedings of 20th International Conference on Computer Communications and Networks. Maui： IEEE， 2011： 1?8.

[10] SAFA H. A novel localization algorithm for large scale wireless sensor networks [J]. Computer communications， 2014， 45（3）： 32?46.

[11] CHEN Xiaohui， HE Jing， CHEN Jinpeng. An improved localization algorithm for wireless sensor network [J]. Intelligent automation & soft computing， 2011， 17（6）： 675?685.

[12] 王书锋，侯义斌，黄樟钦，等.无线感知网络最小二乘法定位算法的误差分析与优化[J].系统仿真学报，2009，21（19）：6211?6215.

WANG Shufeng， HOU Yibin， HUANG Zhangqin， et al. Error analysis of least squares method and optimization for WSN [J]. Journal of system simulation， 2009， 21（19）： 6211?6215.

[13] 孙立民，李健中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005.

SUN Limin， LI Jianzhong， CHEN Yu， et al. Wireless sensor network [M]. Beijing： Tsinghua University Press， 2005.

[14] WHITEHOUSE K， KARLOF C， WOO A， et al. The effects of ranging noise on multihop localization： an empirical study [C]// Proceedings of 4th International Symposium on Information Processing in Sensor Networks. Boise： IEEE， 2005： 73?80.

[15] ZHOU Huachun. Research on design and implementation of ZigBee gateway system based on Internet of Things [C]// Proceedings of 4th International Conference on Electrical & Electronics Engineering and Computer Science. [S.l. ： s.n.]， 2016： 2?5.

[16] 姚国风，庄斌，赵大明，等.基于ZigBee无线技术的智能家居系统设计[J].现代电子技术，2016，39（22）：81?84.

YAO Guofeng， ZHUANG Bin， ZHAO Daming， et al. Design of intelligent home system based on ZigBee wireless technology [J]. Modern electronics technique， 2016， 39（22）： 81?84.