توسعه يك چارچوبي مبتني بر رايانش ابري براي تحليل انطباق نقشه داده‌هاي خودروهاي شناور

An Integrated Framework based on Cloud Computing for Map Matching Analysis of Floating Car Data

امروزه كاربردهاي نوين الگوريتم انطباق نقشه در كنار تلاش براي حفظ نرخ بالاي موفقيت، با دو چالش نرخ‌هاي نمونه‌برداري متغير و سرعت پردازش داده‌ها روبرو هستند. در اين تحقيق يك چارچوب جامع، توزيع يافته، كارآمد و صحيح براي تحليل انطباق نقشه ارائه‌شده است. چارچوب پيشنهادي در مواجهه با نرخ‌هاي نمونه‌برداري متفاوت و فارغ از وابستگي به حسگرهاي اضافي توانسته به نرخ موفقيت مناسبي دست پيدا كند. همچنين استفاده از روش وزن دهي پويا باعث استقلال چارچوب از پارامترهاي محلي شده است. استفاده از مفاهيم سطوح اطمينان صحت و سرعت عملكرد چارچوب را افزايش داده است. در اين چارچوب براي پاسخ به چالش نرخ نمونه‌برداري پايين از الگوريتم كوتاه‌ترين مسير A* با روش وزن دهي پويا استفاده مي شود. وزن دهي قيد كوتاه ترين مسير با كمك اطلاعات HDOP انجام مي شود. يكي از چالش‌هاي اصلي در به‌كارگيري داده‌هاي بزرگ FCD، ذخيره‌سازي، مديريت، تحليل و پردازش جمعي آن‌ها است. بدين منظور در اين چارچوب از اصول رايانش ابري و الگوي نگاشت كاهش بر روي سكوي هدوپ (Hadoop) استفاده‌شده است. بدين ترتيب چارچوب فوق تحليلي توزيع يافته، مقياس‌پذير و كارآمد را بر روي سخت‌افزارهاي معمولي ممكن مي‌سازد. جهت ارزيابي عملكرد چارچوب ناوگان حمل و نقل شهر نيويورك به عنوان يكي از بزرگترين ناوگان هاي حمل و نقلي جهان مورد مطالعه قرار گرفته است. نتايج ارزيابي ها بيانگر نرخ موفقيت 95.2 درصدي در نرخ نمونه برداري بالا (10 ثانيه) و 89.5 درصدي در نرخ نمونه برداري پايين (120ثانيه) است. همچنين مقايسه نتايج روش پيشنهادي با يكي از روش هاي شناخته شده نشان مي‌دهد در نرخ نمونه‌برداري 120 ثانيه روش پيشنهادي صحت انطباق نقشه را تا 9.7 درصد بهبود داده است. ارزيابي‌ها نشان مي‌دهد با حضور 5 گره پردازشي چارچوب پيشنهادي توانسته بيش از 7000 نقطه در هر ثانيه را بر روي نقشه منطبق كند.

These days Floating Car Data (FCD) is one of the major data sources in Intelligent Transportation System (ITS) applications like route suggestion, traffic monitoring, traffic flow analysis and etc. Due to GPS limited accuracy and noises and road network errors, utilizing of FCD in ITS applications needs an efficient and accurate map matching framework. Map matching is a well-established problem which deals with mapping raw time stamped location traces to edge of road network graph. Along with high success rate, novel map matching applications faces several challenges including variable sampling frequency and processing speed of FCD big data. In this paper we have proposed a general, efficient, accurate and distributed map matching framework. The proposed framework can handle variable sampling frequency data accurately. Although this framework does not depend on additional data other than road network and GPS, achieved high success rate shows effectiveness of our system. We have used spatial proximity, heading difference, bearing difference and shortest path as our matching criteria. We also employed dynamic weights for each criteria to make our framework independent from local parameters. We have also employed confidence levels to improve our matching success rate. To answer low frequency data challenges, we have present an extra criteria based on A* shortest path method with dynamic weighting method. We have used HDOP for weighting shortest path criteria. When we are not confident enough about a point matching, we use shortest path criteria to improve success rate and by this method we keep our overhead low. For the evaluation we have studied New York City (NYC) OSM trajectories as the case study. We also used OSM NYC road network as the base map. The evaluation results indicate 95.2% MM success rate in high sampling mode (10s) along with 89.5% success rate in low sampling frequency (120s). We have compared our method with a known map matching method that In the case of low sampling frequency, our method has improved matching accuracy up to 9.7%. We have evaluated the effect of utilizing shortest path criteria in low frequency scenario. Our results show that using shortest path have improved our result up to 3.5%. One of the major challenges in using FCD is storage, managing, analysis and batch processing of this big data. To face this challenge in this framework we have used cloud computing technologies along with MapReduce paradigm based on Hadoop framework. The proposed cloud computing based framework can answer technical challenges for efficient and real-time storage, management, process and analyze of traffic big data. Our evaluation results indicate we have matched 7000 points/second on a cluster with 5 processing nodes. We have also processed 5 million records in 530 seconds using a cluster with 5 processing nodes. The main contributions are as follows: 1) we have proposed a general, distributed map matching framework using cloud computing technologies to answer to upstream ITS applications, 2) We have improved an efficient and accurate map matching algorithm which can handle different sampling frequencies using shortest path method and confidence level, 3) we have used dynamic method for weighting geometric, directional and shortest path constrains.