一種基于分布式子空間的共享單車定位算法

何濤 張健 徐鶴 姜彥男

摘 要： 共享單車逐步成為中國規模最大的城市交通代步解決方案，為城市人群提供更加快捷、環保的城市出行服務。為了進一步提高共享單車的利用率和安全性，分析在城市復雜環境下影響定位的主要因素，結合現有的共享單車的定位方式，提出一種基于層次分布式子空間的定位算法。通過各點之間的接收信號強度指示以及標準點坐標定位實現共享單車的精準定位。仿真結果表明，所提出的算法較現有的方法具有較高精度的定位，能夠提高單車的使用率以及實現對單車狀態的實時反饋。

關鍵詞： 共享單車； 節點定位； 層次分布式子空間； 定位算法； 城市出行； 信號強度指示

中圖分類號： 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.