基于EMD算法的切換系列區(qū)分及時(shí)空轉(zhuǎn)換參數(shù)選取仿真

劉中游， 曾大堃

(西南交通大學(xué)交通運(yùn)輸與物流學(xué)院，四川成都 610031)

基于EMD算法的切換系列區(qū)分及時(shí)空轉(zhuǎn)換參數(shù)選取仿真

劉中游， 曾大堃

(西南交通大學(xué)交通運(yùn)輸與物流學(xué)院，四川成都 610031)

鑒于由于個(gè)人隱私而導(dǎo)致的數(shù)據(jù)獲取困難問(wèn)題，依托基于無(wú)線通信網(wǎng)絡(luò)與交通集成仿真的手機(jī)切換數(shù)據(jù)平臺(tái)采集手機(jī)數(shù)據(jù)，用EMD算法將不同道路切換序列的差異程度進(jìn)行量化區(qū)分，根據(jù)時(shí)空轉(zhuǎn)換參數(shù)ρ的不同取值得到相鄰道路、不同道路之間手機(jī)切換序列對(duì)的EMD。結(jié)果表明：將EMD算法應(yīng)用于不同道路序列的區(qū)分是可行的，ρ的選值不影響該算法應(yīng)用的效果。

手機(jī)切換；EMD算法；仿真平臺(tái)；選值分析

利用手機(jī)切換定位技術(shù)獲取交通基礎(chǔ)數(shù)據(jù)是近年來(lái)智能交通領(lǐng)域研究的熱點(diǎn)[1-2]，但也面臨著諸多難題，手機(jī)切換道路匹配是其中之一。關(guān)于無(wú)線定位的地圖匹配已提出多類算法, 比較簡(jiǎn)單的有早期的基于道路幾何信息的估計(jì)算法，后來(lái)在不斷追求提升匹配正確率的基礎(chǔ)上又加入一些權(quán)重因子，出現(xiàn)了更加復(fù)雜的算法，近年來(lái)提出模糊邏輯以及模式識(shí)別等方法[3]。在不斷追求匹配正確率的同時(shí)，計(jì)算量和經(jīng)費(fèi)投入也不斷增加。

目前已有的匹配方法大都關(guān)注車輛軌跡和路網(wǎng)幾何屬性而沒有考慮通信網(wǎng)絡(luò)中手機(jī)切換機(jī)理，也沒有充分利用手機(jī)切換數(shù)據(jù)信息，難以從根本上達(dá)到較理想的效果。而EMD算法則可以從切換序列的參數(shù)信息角度出發(fā)，充分利用切換發(fā)生時(shí)間、基站服務(wù)時(shí)間以及基站的位置坐標(biāo)等參數(shù)進(jìn)行不同切換之間的差異度衡量，以此進(jìn)行不同道路上手機(jī)切換序列的區(qū)分。而通過(guò)對(duì)時(shí)空轉(zhuǎn)換參數(shù)ρ的不同取值得到多組不同道路切換序列對(duì)之間EMD結(jié)果的分析，分析ρ的不同選值影響。

1 基于交通仿真與無(wú)線通信仿真的手機(jī)切換數(shù)據(jù)平臺(tái)

1.1手機(jī)切換定位技術(shù)原理

切換是指手機(jī)由于當(dāng)前基站接收的信號(hào)強(qiáng)度逐漸下降而將手機(jī)與基站之間的通信鏈路從當(dāng)前基站轉(zhuǎn)移到另一個(gè)信號(hào)強(qiáng)度較高的目標(biāo)基站的過(guò)程[4]。由于真實(shí)道路網(wǎng)絡(luò)環(huán)境中分布著許多無(wú)線通信信號(hào)基站，不同基站根據(jù)其服務(wù)范圍相互構(gòu)成了整個(gè)無(wú)線通信的覆蓋系統(tǒng)。車輛在道路網(wǎng)絡(luò)的移動(dòng)過(guò)程中，車載手機(jī)必然要在無(wú)線網(wǎng)絡(luò)系統(tǒng)的不同基站之間進(jìn)行切換，通過(guò)對(duì)車載手機(jī)的切換進(jìn)行連續(xù)追蹤，再根據(jù)道路匹配方法確定不同手機(jī)切換與道路之間的歸屬情況，即可實(shí)現(xiàn)車輛的定位及相關(guān)交通流參數(shù)的獲取。

1.2基于無(wú)線通信和交通流集成仿真的手機(jī)切換數(shù)據(jù)平臺(tái)

在智能交通領(lǐng)域中，利用手機(jī)定位技術(shù)獲取交通流參數(shù)具有較好的發(fā)展?jié)摿蛢r(jià)值，但是近年來(lái)國(guó)內(nèi)外大量相關(guān)的理論研究和實(shí)踐項(xiàng)目都遭遇難題。例如2004年，美國(guó)馬里蘭州交通部與Delcan公司、IT IS公司合作的手機(jī)項(xiàng)目因雙方未達(dá)成一致協(xié)議而停滯；2005年12月，美國(guó)密蘇里州開展的手機(jī)定位技術(shù)應(yīng)用項(xiàng)目也因技術(shù)問(wèn)題沒有順利進(jìn)行，其瓶頸都在于數(shù)據(jù)來(lái)源[5]。近年來(lái)學(xué)術(shù)界采用仿真手段進(jìn)行該領(lǐng)域的研究，既能有效解決數(shù)據(jù)來(lái)源問(wèn)題，也能在平臺(tái)中建立數(shù)據(jù)評(píng)估系統(tǒng)，對(duì)仿真參數(shù)進(jìn)行影響評(píng)估。

建立仿真平臺(tái)的基礎(chǔ)是深入剖析手機(jī)切換機(jī)理以及研究道路交通和無(wú)線通信雙網(wǎng)結(jié)合的關(guān)系，分別構(gòu)建微觀交通仿真系統(tǒng)和無(wú)線通信仿真系統(tǒng)，從交通仿真系統(tǒng)中獲取車輛軌跡數(shù)據(jù)，輸入無(wú)線通信仿真系統(tǒng)中，后者基于路網(wǎng)中的基站分布情況和實(shí)際的通信協(xié)議、切換流程、控制準(zhǔn)則[6]，逐點(diǎn)判斷手機(jī)是否發(fā)生基站切換，生成手機(jī)切換樣本數(shù)據(jù)，其建模過(guò)程如圖1所示。

圖1 基于無(wú)線通信網(wǎng)與道路交通網(wǎng)絡(luò)仿真的手機(jī)切換數(shù)據(jù)仿真建模

2 EMD算法分析及其應(yīng)用

2.1 EMD算法原理

EMD(Earth Mover′s Distance)算法最早于1781年由Gaspard Monge 提出，描述一種運(yùn)輸問(wèn)題，即用不同地點(diǎn)的泥土填補(bǔ)不同地點(diǎn)的坑洞時(shí)選取的最優(yōu)運(yùn)輸方案，后來(lái)廣泛應(yīng)用于圖像檢索領(lǐng)域[7]。目前EMD算法的應(yīng)用已經(jīng)進(jìn)入許多領(lǐng)域的模式識(shí)別中，成為量化不同模式之間差異度的重要方法，可以將不同形式的排列或組合之間的差異度進(jìn)行量化計(jì)算(用EMD的值表示)。EMD算法的本質(zhì)是線形規(guī)劃問(wèn)題。

假設(shè)有2種模式分別為P、Q，表達(dá)式為

P={(p1,wp1),…,(pm,wpm)},
Q={(q1,wq1),…,(qm,wqm)},

式中pi和pj分別為P、Q中的元素；m、n分別為P、Q中元素的數(shù)量；wpi、wpj分別為pi和pj在模式中所占的權(quán)重。

約束條件為

fij≥0,(1≤i≤m,1≤j≤n),

(1)

(2)

(3)

(4)

最后得到2個(gè)分布模式之間的差異度量化為EMD值，表達(dá)式為

2.2基于EMD算法的手機(jī)切換序列差異度衡量

把上述EMD模型引入手機(jī)切換領(lǐng)域，將手機(jī)切換序列定義成一種切換排列模式，那么手機(jī)切換模式的不同特征分布也可以表示為

P={(p1,wp1),…,(pm,wpm)},
Q={(q1,wq1),…,(qm,wqm)}.

pi、qj之間的距離為歐氏幾何地面距離dij，計(jì)算式為

式中 (xi,yi)、(xj,yj)為基站坐標(biāo);(ti,tj)為對(duì)應(yīng)于基站pi和pj的手機(jī)切換發(fā)生時(shí)刻;ρ為時(shí)空轉(zhuǎn)換系數(shù)，為了將時(shí)間和空間距離對(duì)應(yīng)，ρ將時(shí)間和空間2個(gè)維度的單位統(tǒng)一，理論上ρ是一個(gè)自由的轉(zhuǎn)換系數(shù)。

3 基于EMD的不同道路手機(jī)切換區(qū)分和參數(shù)分析試驗(yàn)

3.1試驗(yàn)背景

圖2為某城市道路網(wǎng)絡(luò)交通仿真示意圖，同時(shí)建立了對(duì)應(yīng)于道路網(wǎng)絡(luò)的無(wú)線通信網(wǎng)絡(luò)仿真，仿真建模完全按照真實(shí)無(wú)線通信網(wǎng)絡(luò)環(huán)境的參數(shù)進(jìn)行設(shè)置[8]。選取該城市道路網(wǎng)絡(luò)中的3條具體道路作為目標(biāo)分析道路，如圖3所示，分別為：①old(Old midleton rd)，②odana(Odana rd)，③spark(Spark st 1)。

圖2 道路交通網(wǎng)絡(luò)仿真模型示意圖

圖3 某城市目標(biāo)分析道路分布示意圖

表1手機(jī)切換序列數(shù)據(jù)信息

oldodanaspark基站編號(hào)時(shí)間/s基站編號(hào)時(shí)間/s基站編號(hào)時(shí)間/s34217．653229．551459．254376．052798．8513133．505506．4024178．0512277．0522217．6511415．6521321．609420．6020529．508504．7517544．059524．85

通過(guò)手機(jī)切換仿真平臺(tái)隨機(jī)抽取每條道路上的一個(gè)手機(jī)切換序列作為基礎(chǔ)數(shù)據(jù)，將這些手機(jī)切換序列進(jìn)行相互間的EMD計(jì)算，得到的結(jié)果以 EMD矩陣形式進(jìn)行分析。手機(jī)切換序列的數(shù)據(jù)形式如表1所示。

3.2ρ的不同取值下EMD算法對(duì)切換序列區(qū)分的結(jié)果分析

對(duì)ρ分別取值為1，5，10，100 m/s。ρ的不同取值下所有道路之間的手機(jī)切換序列對(duì)EMD值的計(jì)算結(jié)果如表2所示。

從表2可以看出，相同道路上的手機(jī)切換序列對(duì)之間的EMD值最小，而且遠(yuǎn)小于不同道路之間手機(jī)切換序列對(duì)。因此，在EMD矩陣的每行中選中最小值，就實(shí)現(xiàn)了不同道路的手機(jī)切換序列的區(qū)分。這說(shuō)明了ρ的不同取值不會(huì)改變EMD算法用于手機(jī)切換序列區(qū)分的可行性。

表2 ρ的不同取值下手機(jī)切換序列對(duì)之間的EMD計(jì)算結(jié)果

4 結(jié)語(yǔ)

通過(guò)仿真建模構(gòu)建手機(jī)基礎(chǔ)數(shù)據(jù)平臺(tái)，將EMD算法很好地應(yīng)用于不同道路切換序列的區(qū)分。而且，從ρ的不同取值結(jié)果來(lái)看，相同道路上的手機(jī)切換序列對(duì)之間的EMD最小，而且遠(yuǎn)小于不同道路之間手機(jī)切換序列對(duì)的EMD，EMD算法的應(yīng)用是可行的，證明了在EMD算法模型中，ρ的選值并不影響算法的應(yīng)用技術(shù)效果。

[1]楊飛，裘煒毅. 基于手機(jī)定位的實(shí)時(shí)交通數(shù)據(jù)采集技術(shù)[J].城市交通,2005,3(4)：65-68.

[2]Brain L Smith, Han Zhang, Michael D Fontaine, et al. Wireless Location Technology-Based Traffic Monitoring: Critical Assessment and Evaluation of an Early-Generation System[J]. Journal of Transportation Engineering, 2004,130(5):576-584.

[3]楊飛，惠英. 基于手機(jī)切換變化模式的道路匹配方法[J].系統(tǒng)工程, 2007, 25(11): 6-13.

[4]楊飛，惠英，楊東援. 基于手機(jī)切換定位的交通路網(wǎng)標(biāo)定方法[J].同濟(jì)大學(xué)學(xué)報(bào):自然科學(xué)版, 2009, 37(1): 67-72.

[5]Smith B, Fontaine M, Beaton J,et al. NCHRP 70-01: Private-Sector Provision of Congestion Data[R].Virginia: University of Virginia, 2007.

[6]上海西門子移動(dòng)通信有限公司. 無(wú)線網(wǎng)絡(luò)參數(shù)設(shè)置手冊(cè)[K]. 上海：上海西門子移動(dòng)通信有限公司，2001.

[7]Rubner Y, Guibas L J, Tomasi C. The Earth Mover′s Distance, Multi-Dimensional Scaling, and Color-Based Image Retrieval [J]. Proceeding of ARPR Image Understanding Workshop, 1997(01)：661-668.

[8]Srinivasan R, Zhuang J, Jalloul L, et al. Project 802.16m Evaluation Methodology Document (EMD)[R].New York: IEEE, 2008.

(責(zé)任編輯：郎偉鋒)

OnParameterSelectionSimulationofHandoverSequencesandSpace-TimeTransformationBasedonEMDAlgorithm

LIUZhong-you,ZENGDa-kun

(CollegeofTransportationandLogistics,SouthwestJiaotongUniversity,Chengdu610031,China)

As the difficulty of the current data acquisition due to the personal privacy, the data collection of mobile phone relies on the handover data platform based on a wireless communication network and integrated traffic simulation. In this paper, the EMD algorithm is used to quantify the differences of the handover sequences of different roads and the value-choosing influence of different parameters is analyzed according to the calculations of the different values of the space-time transformation parameters in the algorithm.

mobile phone handover; EMD algorithm; simulation platform; value-choosing analysis

2014-02-28

劉中游(1989—)，男，福建漳平人，西南交通大學(xué)碩士研究生，主要研究方向?yàn)榻煌ㄟ\(yùn)輸規(guī)劃與管理、智能交通.

10.3969/j.issn.1672-0032.2014.01.010

U491

A

1672-0032(2014)01-0044-05