何濤 張健 徐鶴 姜彥男

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

關(guān)鍵詞： 共享單車； 節(jié)點定位； 層次分布式子空間； 定位算法； 城市出行； 信號強(qiáng)度指示

中圖分類號： TN953+.7?34 文獻(xiàn)標(biāo)識碼： 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

隨著經(jīng)濟(jì)的快速提升，汽車工業(yè)的生產(chǎn)制造迅猛發(fā)展，我國近些年來汽車的擁有量在急劇增加[1]，加之我國大量人口涌入城市，城市交通擁堵已成為正?，F(xiàn)象。為了有效地緩解交通壓力和解決短距離出行問題，一系列的共享單車出現(xiàn)在城市人口密集的地方，其提出“解決最后一公里出行問題”[2]的理念和操作便捷的軟件為城市人群提供了更加快捷高效，綠色低碳的城市出行服務(wù)。目前，共享單車的定位方法為兩種：

1） 基于GPS定位的共享單車在內(nèi)部通過GSM模塊發(fā)送信息與云端實現(xiàn)通信，實時將車輛所處的位置以及車輛當(dāng)前狀態(tài)上傳云端數(shù)據(jù)庫。實現(xiàn)對共享單車位置準(zhǔn)確無時差監(jiān)控和具體定位。但是此方法有許多不足。每一輛單車都需要內(nèi)置電源、GPS模塊、GSM模塊以及智能鎖，成本經(jīng)調(diào)查大約3 000元，成本的上升意味著防盜風(fēng)險的急劇提升；單車[3]重量為25 kg，嚴(yán)重影響了騎車用戶的使用體驗，在復(fù)雜的環(huán)境增加了騎行的難度。

2） 目前使用的GPS定位芯片，精度[4]大約10 m，與體積較小的單車相比會產(chǎn)生很大的誤差，經(jīng)實驗數(shù)據(jù)顯示，在高樓和立交橋等復(fù)雜環(huán)境下，集中擺放的裝有GPS定位芯片的共享單車會產(chǎn)生60%～70%不同程度的定位漂移。

無GPS的共享單車定位方法只配有一個固定密碼的機(jī)械鎖，定位方法通過APP客戶端或者微信公眾號來訪問騎車用戶者的手機(jī)，通過獲得手機(jī)GPS定位的位置，間接得到共享單車的起始和結(jié)束位置，來實現(xiàn)對單車位置的定位和監(jiān)控。其較低的生產(chǎn)成本以及簡單的使用方法得到了許多用戶者的青睞。但是由于人為的因素、天氣環(huán)境以及位置獲取時差等因素，實際的位置和軟件提供位置有很大的差距；在城市的早晚高峰，中轉(zhuǎn)站會堆積大量單車，這樣的效應(yīng)稱為“潮汐”現(xiàn)象[5]，反應(yīng)了單車分布的不均勻以及無法及時調(diào)配單車數(shù)量的問題，不但造成了大量的資源浪費，同樣影響了社會的正常運行；用于車輛采用的是有固定密碼的機(jī)械鎖和無法對車輛實現(xiàn)具體的定位，導(dǎo)致大量共享單車的破壞和丟失，增加了公司后期投入的運營成本和維修的成本。

1 新算法的提出

為了更好地提升共享單車的位置，降低成本，合理分配不同位置單車數(shù)量等一系列問題，結(jié)合機(jī)器學(xué)習(xí)[6]發(fā)展的思路，本文提出一種基于分布式子空間的單車定位算法（Localization based on Distributed Subspace， LDS）。把傳統(tǒng)的定位方法轉(zhuǎn)換成對不同節(jié)點分類學(xué)習(xí)問題，把未知節(jié)點與錨節(jié)點的距離作為特征向量，依據(jù)未知節(jié)點和錨節(jié)點的相似度對未知節(jié)點進(jìn)行分類。算法流程圖如圖1所示。

1.1 錨節(jié)點部署

錨節(jié)點是無線傳感器網(wǎng)絡(luò)中已知自身位置的節(jié)點，其部署采用規(guī)則部署，依據(jù)采集的單車路線行駛以及車輛停放位置對錨節(jié)點的位置進(jìn)行預(yù)估。假設(shè)在無線傳感器網(wǎng)絡(luò)平面中構(gòu)建網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，由于每個網(wǎng)格單元都有相同的面積，因此網(wǎng)格單元中數(shù)據(jù)點的密度為落到單元中點個數(shù)，網(wǎng)格單元為稠密單元[7]的判決為：

式中：[NA]為網(wǎng)格單元的數(shù)據(jù)點數(shù)；[CA]為數(shù)據(jù)空間中總的數(shù)據(jù)點數(shù)；[ε]為密度閾值；density是在某一時刻t一個網(wǎng)絡(luò)單元的密度。當(dāng)密度大于設(shè)定的密度閾值[ε]，設(shè)定該單元為一個密集網(wǎng)絡(luò)單元，部署錨節(jié)點，相對于稠密網(wǎng)格單元來說，大多數(shù)的網(wǎng)格單元包含非常少甚至空的數(shù)據(jù)點，這一類網(wǎng)格單元被稱為稀疏網(wǎng)格單元。定義稀疏密度閾值為[θ]，當(dāng)[density（t）≥θ]時，該網(wǎng)格單元是—個稀疏單元。對于稀疏網(wǎng)格單元的處理方法一般采用壓縮的方法，在壓縮后的稀疏網(wǎng)格單元部署錨節(jié)點。

1.2 分布式分類定位的實現(xiàn)

根據(jù)節(jié)點定位計算模式是由中心節(jié)點計算還是由節(jié)點自行計算，分為集中式定位（Centralized Localization）算法[8]和分布式定位（Distributed Localization）算法[9]。分布式定位的計算是在各個節(jié)點進(jìn)行的，所以相比于集中式定位，整個網(wǎng)絡(luò)的流量與計算量分布能夠保持一個較為均衡的水平，降低能耗。

假設(shè)大規(guī)模無線傳感器網(wǎng)絡(luò)中，有M個節(jié)點部署在[L×L]的二維空間平面上。節(jié)點的通信距離r（[Xi]）（dis>0）相同，可以在理論通信范圍內(nèi)實現(xiàn)直接通信。假設(shè)存在k（k

1） 從未知節(jié)點集中選取一點為待分類點U，計算與錨節(jié)點集[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]）的值設(shè)定為離群值并且去除。

3） 對剩余的距離值從小到大排序，取前k個距離最小的樣本以及對應(yīng)的標(biāo)簽放入分布式分類集合NN中，最近鄰數(shù)k值按剩余的距離值集合比例動態(tài)調(diào)整，避免因分類標(biāo)簽分布不均衡引起的分類錯誤。

4） 分布式分類集合NN中，對樣本的標(biāo)簽計數(shù)，設(shè)定頻率最高的類為待分類點U的標(biāo)簽。如果出現(xiàn)頻率相同的類，則比較每個類中最小距離dis（U，La）的大小，距離最小的類為待分類點U的標(biāo)簽。

5） 返回步驟1），直到全部未知節(jié)點分類結(jié)束。

依據(jù)未知節(jié)點與錨節(jié)點的距離作為特征向量對未知節(jié)點進(jìn)行分類，對相同類中的節(jié)點賦予相同的標(biāo)簽，實現(xiàn)對節(jié)點的分布式分類。

1.3 局部子空間定位的實現(xiàn)

對于分布式分類后的節(jié)點處于較小的通信范圍，利用一定通信范圍內(nèi)的鄰居節(jié)點構(gòu)造一個局部子空間[10]。在子空間內(nèi)，錨節(jié)點的具體位置可以依據(jù)子空間內(nèi)不同環(huán)境做出對應(yīng)的部署，然后參考全局結(jié)構(gòu)和錨節(jié)點坐標(biāo)，使用極大似然估計法迭代映射出類中所有未知節(jié)點的坐標(biāo)。極大似然估計法（Maximum Likelihood Estimation）[11]是多邊測量定位技術(shù)主要采用的方法。已知n個節(jié)點的坐標(biāo)分別為（x1，y1），（x2，y2），…，（xn，yn），它們到節(jié)點D的距離分別為d1，d2，…，dn，假設(shè)節(jié)點D的坐標(biāo)為（x，y）。則有如下公式：

根據(jù)標(biāo)準(zhǔn)的最小均值方差估計得線性公式為：

通過使用最小二乘法解[12]表達(dá)式可以計算得到公式為：[X=ATA-1ATB]。

局部子空間定位算法具有以下優(yōu)勢：

1） 在相同的測距方式下，兩節(jié)點間的距離越接近，測距精度則越高，誤差也就越小。

2） 通過已知局部子空間自身的范圍判斷節(jié)點位置的準(zhǔn)確性，極大縮小節(jié)點坐標(biāo)的誤差，減少因為復(fù)雜環(huán)境帶來的位置偏移。

3） 通過局部子空間可以最優(yōu)化和最近化調(diào)配各個子空間單車的數(shù)量，保持每一個區(qū)域單車數(shù)量的相對平衡，防止“潮汐”現(xiàn)象的發(fā)生。

2 RSSI測距模型

RSSI（Received Signal Strength）基于接收信號強(qiáng)度指示信號[13]，通過測量從發(fā)送端到接收端的衰減來計算節(jié)點的距離。此測距方法實現(xiàn)比較簡單，但信號強(qiáng)度易受環(huán)境等因素的影響，所以要根據(jù)具體環(huán)境構(gòu)建傳播模型，從而選定模型參數(shù)，然后使用Noisy Disk模型[14]模擬不同誤差下的測量距離。

實驗中通信節(jié)點選擇CC2530芯片為通信芯片，CC2530是一款用于ZigBee技術(shù)[15]的2.4 GHz射頻通信芯片，該芯片集成微處理器、模/數(shù)轉(zhuǎn)化器、無線通信模塊于一體，支持最新的ZigBee協(xié)議ZigBee 2007/PRO[16]，具有節(jié)點通信距離更遠(yuǎn)，組網(wǎng)性能更穩(wěn)定可靠以及價格更低等諸多優(yōu)勢。

定義[Pij]為節(jié)點i接收到節(jié)點j的信號強(qiáng)度，并且假設(shè)[Pij]和[Pji]相等，[Pij]是對數(shù)正太隨機(jī)分布隨機(jī)變量，[Pij（dBm）=10lg Pij]服從高斯分布：

式中：[d0]為近地參考距離；[P0]是距離為[d0]時的接收信號強(qiáng)度；[dij]為距發(fā)射端的真實距離；[Pij]是距離為[dij]時的接收信號強(qiáng)度；[β]為以dB為單位的遮蔽因子；n是路徑損耗指數(shù)，其大小取決于無線信號的傳播環(huán)境，在室外遮蔽的城市空間內(nèi)，n的取值為[2.7～5]之間。由于在實際環(huán)境中[β]是均值為0、標(biāo)準(zhǔn)差為[σ]的正態(tài)隨機(jī)變量，為簡化模型，將[σ]的影響忽略，選用以下模型：

式中：[d0]取值為1 m，參數(shù)A為節(jié)點i到節(jié)點j的距離[d0]為1 m測得平均接收信號強(qiáng)度；路徑損耗指數(shù)n取值為3；[Pij]表示發(fā)射節(jié)點距離為[dij]時的接收信號強(qiáng)度。

3 算法實驗及分析

在Matlab平臺上通過使用RSSI測距模型對LDS算法進(jìn)行仿真研究，分析算法的性能，所有算法都用Matlab語言編寫。假設(shè)無線傳感器網(wǎng)絡(luò)部署在一個300 m[×]300 m的二維平面上，錨節(jié)點規(guī)則部署在設(shè)定位置，未知節(jié)點隨機(jī)分布，每次的結(jié)果取10次仿真實驗結(jié)果的均值。實驗從以下三個方面對算法進(jìn)行評價：錨節(jié)點數(shù)目；未知節(jié)點數(shù)；測距誤差。

對于測距誤差，不同技術(shù)的測距誤差對實驗仿真有很大的差別，因此在仿真實驗中，節(jié)點間的通信距離使用Noisy Disk模型給出，如下：

式中：[dxi，xj]為節(jié)點i和j之間的實際距離；Noisy Disk模型假設(shè)距離測量值[dxi，xj]是以[dxi，xj]為均值，[ε]為方差的正態(tài)分布。

3.1 未知節(jié)點數(shù)量的變化對LDS算法的影響

在300 m[×]300 m的二維平面上，部署了12個錨節(jié)點，分別在未知節(jié)點數(shù)為80，100，120，140的情況下，對節(jié)點進(jìn)行定位，得到的定位誤差如表1所示。

由表1得，在未知節(jié)點數(shù)為80，100，120，140的情況下，得到的平均定位誤差為1.604 m、1.523 m、1.585 m、1.657 m，相比于GPS導(dǎo)航中產(chǎn)生的十多米的誤差，提高了定位精度，減小了單車的大距離“定位漂移”的現(xiàn)象。通過標(biāo)準(zhǔn)差可以顯示LDS定位算法很穩(wěn)定，數(shù)據(jù)集的離散程度小。不同未知節(jié)點數(shù)對LDS定位算法產(chǎn)生較小影響，相比于目前的共享單車定位方法在精度方面有了很大的提高。

3.2 錨節(jié)點數(shù)目的變化對LDS算法的影響

在300 m[×]300 m的二維平面上，部署了120個未知節(jié)點，分別在錨節(jié)點數(shù)為9，12，16的規(guī)則部署情況下，對節(jié)點進(jìn)行定位，如圖2所示。

圖2中：十字標(biāo)記為錨節(jié)點的位置；空心圓表示為未知節(jié)點的實際坐標(biāo)；叉號表示為未知節(jié)點的預(yù)測坐標(biāo)；空心圓和叉號相連的直線表示未知節(jié)點實際位置與估計位置的距離。測距誤差[ε]為1。

在未知節(jié)點為120，未知節(jié)點數(shù)分別為9，12，16的情況下，LDS算法的誤差如表2所示。錨節(jié)點數(shù)對定位誤差結(jié)果的影響如圖3所示。

從圖3可知：

1） 未知節(jié)點數(shù)對LDS算法產(chǎn)生較小的影響，平均差和標(biāo)準(zhǔn)差保持水平。

2） 錨節(jié)點數(shù)為12和16的折線在錨節(jié)點數(shù)為9的下方，這是由于錨節(jié)點數(shù)目的增加，有效提高了定位精度，但是節(jié)點12和節(jié)點16的差距較小，顯示一定區(qū)域內(nèi)錨節(jié)點數(shù)目增加到一定值，定位精度保持平衡。

3.3 節(jié)點通信范圍的變化對LDS算法的影響

當(dāng)錨節(jié)點總數(shù)為12，在不同的節(jié)點通信半徑下，未知節(jié)點總數(shù)為80，100，120對平均定位誤差影響變化曲線如圖4a）所示。當(dāng)未知節(jié)點總數(shù)為100時，在不同的節(jié)點通信半徑下，錨節(jié)點數(shù)為9，12，16對平均定位誤差影響變化曲線如圖4b）所示。從圖4可以得知：通信半徑越大，定位誤差越小。當(dāng)通信半徑大于整個WSN區(qū)域長度的33%時，不同的未知節(jié)點數(shù)以及不同的錨點數(shù)對于LDS定位算法產(chǎn)生的誤差較小，誤差保持恒定不變。

4 結(jié) 論

目前共享單車的定位采用用戶定位估算法，使得距離定位有較大的定位誤差，為了有效地解決共享單車定位的問題，通過機(jī)器學(xué)習(xí)和無線傳感器的有機(jī)結(jié)合，提出基于分布式子空間的單車定位算法。本算法的意義在于，相比于GPS高成本和低精度的環(huán)境下，降低成本并提升定位精度，有效解決“位置漂移”和“潮汐”等影響。在錨節(jié)點數(shù)越多的情況下，這種優(yōu)勢越明顯，并且區(qū)域內(nèi)的未知節(jié)點數(shù)的數(shù)目不會影響定位精度。實驗結(jié)果表明，本文算法有效地提高了定位精度。

參考文獻(xiàn)

[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] 中商產(chǎn)業(yè)研究院.2017全球與中國市場共享單車深度研究報告[R].深圳：中商產(chǎn)業(yè)研究院，2017.

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

[4] 張銳，周崟，李庚基，等.GPS差分定位方法研究及其應(yīng)用[J].山西電子技術(shù)，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：基于網(wǎng)格和稠密單元的快速局部離群點探測算法[J].東南大學(xué)學(xué)報（自然科學(xué)版），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最近鄰分類的無線傳感器網(wǎng)絡(luò)定位算法[J].儀器儀表學(xué)報，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] 王書鋒，侯義斌，黃樟欽，等.無線感知網(wǎng)絡(luò)最小二乘法定位算法的誤差分析與優(yōu)化[J].系統(tǒng)仿真學(xué)報，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] 孫立民，李健中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，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] 姚國風(fēng)，莊斌，趙大明，等.基于ZigBee無線技術(shù)的智能家居系統(tǒng)設(shè)計[J].現(xiàn)代電子技術(shù)，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.