基于EMD算法的切換系列區分及時空轉換參數選取仿真

劉中游， 曾大堃

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

基于EMD算法的切換系列區分及時空轉換參數選取仿真

劉中游， 曾大堃

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

鑒于由于個人隱私而導致的數據獲取困難問題，依托基于無線通信網絡與交通集成仿真的手機切換數據平臺采集手機數據，用EMD算法將不同道路切換序列的差異程度進行量化區分，根據時空轉換參數ρ的不同取值得到相鄰道路、不同道路之間手機切換序列對的EMD。結果表明：將EMD算法應用于不同道路序列的區分是可行的，ρ的選值不影響該算法應用的效果。

手機切換；EMD算法；仿真平臺；選值分析

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

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

1 基于交通仿真與無線通信仿真的手機切換數據平臺

1.1手機切換定位技術原理

切換是指手機由于當前基站接收的信號強度逐漸下降而將手機與基站之間的通信鏈路從當前基站轉移到另一個信號強度較高的目標基站的過程[4]。由于真實道路網絡環境中分布著許多無線通信信號基站，不同基站根據其服務范圍相互構成了整個無線通信的覆蓋系統。車輛在道路網絡的移動過程中，車載手機必然要在無線網絡系統的不同基站之間進行切換，通過對車載手機的切換進行連續追蹤，再根據道路匹配方法確定不同手機切換與道路之間的歸屬情況，即可實現車輛的定位及相關交通流參數的獲取。

1.2基于無線通信和交通流集成仿真的手機切換數據平臺

在智能交通領域中，利用手機定位技術獲取交通流參數具有較好的發展潛力和價值，但是近年來國內外大量相關的理論研究和實踐項目都遭遇難題。例如2004年，美國馬里蘭州交通部與Delcan公司、IT IS公司合作的手機項目因雙方未達成一致協議而停滯；2005年12月，美國密蘇里州開展的手機定位技術應用項目也因技術問題沒有順利進行，其瓶頸都在于數據來源[5]。近年來學術界采用仿真手段進行該領域的研究，既能有效解決數據來源問題，也能在平臺中建立數據評估系統，對仿真參數進行影響評估。

建立仿真平臺的基礎是深入剖析手機切換機理以及研究道路交通和無線通信雙網結合的關系，分別構建微觀交通仿真系統和無線通信仿真系統，從交通仿真系統中獲取車輛軌跡數據，輸入無線通信仿真系統中，后者基于路網中的基站分布情況和實際的通信協議、切換流程、控制準則[6]，逐點判斷手機是否發生基站切換，生成手機切換樣本數據，其建模過程如圖1所示。

圖1 基于無線通信網與道路交通網絡仿真的手機切換數據仿真建模

2 EMD算法分析及其應用

2.1 EMD算法原理

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

假設有2種模式分別為P、Q，表達式為

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

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

約束條件為

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

(1)

(2)

(3)

(4)

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

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

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

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

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

式中 (xi,yi)、(xj,yj)為基站坐標;(ti,tj)為對應于基站pi和pj的手機切換發生時刻;ρ為時空轉換系數，為了將時間和空間距離對應，ρ將時間和空間2個維度的單位統一，理論上ρ是一個自由的轉換系數。

3 基于EMD的不同道路手機切換區分和參數分析試驗

3.1試驗背景

圖2為某城市道路網絡交通仿真示意圖，同時建立了對應于道路網絡的無線通信網絡仿真，仿真建模完全按照真實無線通信網絡環境的參數進行設置[8]。選取該城市道路網絡中的3條具體道路作為目標分析道路，如圖3所示，分別為：①old(Old midleton rd)，②odana(Odana rd)，③spark(Spark st 1)。

圖2 道路交通網絡仿真模型示意圖

圖3 某城市目標分析道路分布示意圖

表1手機切換序列數據信息

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

通過手機切換仿真平臺隨機抽取每條道路上的一個手機切換序列作為基礎數據，將這些手機切換序列進行相互間的EMD計算，得到的結果以 EMD矩陣形式進行分析。手機切換序列的數據形式如表1所示。

3.2ρ的不同取值下EMD算法對切換序列區分的結果分析

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

從表2可以看出，相同道路上的手機切換序列對之間的EMD值最小，而且遠小于不同道路之間手機切換序列對。因此，在EMD矩陣的每行中選中最小值，就實現了不同道路的手機切換序列的區分。這說明了ρ的不同取值不會改變EMD算法用于手機切換序列區分的可行性。

表2 ρ的不同取值下手機切換序列對之間的EMD計算結果

4 結語

通過仿真建模構建手機基礎數據平臺，將EMD算法很好地應用于不同道路切換序列的區分。而且，從ρ的不同取值結果來看，相同道路上的手機切換序列對之間的EMD最小，而且遠小于不同道路之間手機切換序列對的EMD，EMD算法的應用是可行的，證明了在EMD算法模型中，ρ的選值并不影響算法的應用技術效果。

[1]楊飛，裘煒毅. 基于手機定位的實時交通數據采集技術[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].系統工程, 2007, 25(11): 6-13.

[4]楊飛，惠英，楊東援. 基于手機切換定位的交通路網標定方法[J].同濟大學學報:自然科學版, 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]上海西門子移動通信有限公司. 無線網絡參數設置手冊[K]. 上海：上海西門子移動通信有限公司，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.

(責任編輯：郎偉鋒)

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—)，男，福建漳平人，西南交通大學碩士研究生，主要研究方向為交通運輸規劃與管理、智能交通.

10.3969/j.issn.1672-0032.2014.01.010

U491

A

1672-0032(2014)01-0044-05