.

توسعه چارچوبی مبتنی بر رایانش ابری برای تحلیل انطباق نقشه داده های خودروهای شناور (بخش اول)

در این تحقیق یک چارچوب یکپارچه و توزیع یافته برای تحلیل انطباق نقشه داده های خودروهای شناور ارائه شده است. در چارچوب پیشنهادی، الگوریتمی بهبود یافته و یک معماری کلی و مفهومی برای سکوی رایانشی تحلیل انطباق نقشه ارائه شده است

توسعه چارچوبی مبتنی بر رایانش ابری برای تحلیل انطباق نقشه داده های خودروهای شناور (بخش اول)

چکیده

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

مقدمه

تراکم ترافیک یکی از چالش های کلیدی در سامانه های حمل و نقلی است که با افزایش تعداد خودروها در سطح راه اتفاق می افتد. در سال 2014 تراکم ترافیک 6.9 میلیارد ساعت زمان شهروندان و 3.1 میلیارد گالن سوخت را به هدر داده که این امر ضرری برابر 160 میلیارد دلار به اقتصاد ایالات متحده وارد کرده است. 
همچنین افزایش آلودگی های صوتی، بصری و محیطی، کاهش بهره وری و ناکاآمدی سامانه های امدادی نیز از دیگر عواقب منفی ترافکم ترافیک است. 
برای پاسخگویی به این مشکلات بهبود کیفیت زندگی انسان، حفظ محیط زیست، پاسخ به نیازهای جامعه، افزایش بهره وری، امنیت و رشد اقتصادی استراتژی های متعددی ارائه شده که از جمله آن ها می توان به توسعه سامانه های حمل و نقل هوشمند (ITS) اشاره نمود.
همگام با توسعه فناوری های موقعیت یابی و شبکه های ارتباطی، داده های خودروهای شناور (FCD) به عنوان یکی از منابع داده اصلی در سامانه های حمل و نقل هوشمند پدیدار شده اند. 
FCD جریانی از نقاط زمانی مکانی است که خط سیر یک وسیله نقلیه متحرک را به تصویر می کشد. FCD معمولا از یک ناوگان از وسایل نقلیه جمع آوری می شوند. هر کدام از خودروها به یک گیرنده سیستم موقعیت یاب جهانی GPS و یک دستگاه بی سیم مجهز شده اند. 
برتری FCD نسبت به سایر حسگرهای ترافیکی، ارائه آنی اطلاعات با کیفیت در کنار پوشش مکانی گسترده و هزینه راه اندازی پایین است. از این مجموعه داده های دقیق و آنی می توان در بسیاری از کاربردهای آنی ITS مانند مدیریت و نظارت آنی ترافیک استفاده نمود. 
همچنین با استفاده از خط سیرهای زمانی-مکانی FCD و با کمک روش های پس پردازشی و داده کاوی، کاربردهایی مانند مدل سازی انتخاب مسیر و پیشنهاد مسیر، تخمین ترافیک و زمان سفر، پیش بینی جریان ترافیک و غیره نیز برای این داده ها در نظر گرفته می شود. 
یکی از چالش های اساسی پیش روی کاربردهای داده های خودروهای شناور، عدم انطباق مکانی است. داده های خام خودروهای شناور دارای دقت محدود و نویز فراوان هستند. 
علت این خطا عمدتا خطای ایجاد شده توسط ماهواره ها و گیرنده های GPS و خطای موجود در تولید نقشه و رقومی سازی آن است. عدم انطباق مکانی در شبکه های متراکم شهری مقدار صحت کلی را در سطح اطمینان 95 درصد بین 0 تا 40 متر کاهش می دهد و مانع انطباق صحیح موقعیت حقیقی خودرو بر شبکه مکانی راه ها می شود. 
به کارگیری صحیح FCD مستلزم فرآیند پیش پردازشی به نام انطباق نقشه (MM) است. هدف از MM یکپارچه سازی موقعیت مکانی خودرو با شبکه راه ها، شناسایی یال حقیقی خودرو و تعیین مکان خودرو بر روی آن یال است. در سال های اخیر تحقیقات متعددی بر روی توسعه و بهبود الگوریتم های انطباق نقشه صورت گرفته است. 
بیشتر این تحقیقات بر روی انطباق نقشه یک خودرو تنها با نرخ نمونه برداری بالا متمرکز شده اند. تعدادی دیگر از تحقیقات نیز به مسئله انطباق نقشه با نرخ نمونه برداری پایین پرداخته اند. دسته دیگری از تحقیقات بر روی بهبود صحت انطباق نقشه با استفاده از حسگرهای موقعیت یابی اضافی متمرکز شده اند. 
با تحقیقات انجام شده می توان دریافت که امروزه کاربردهای نوین الگوریتم انطباق نقشه در کنار تلاش برای حفظ نرخ بالای موفقیت، با دو چالش نرخ های نمونه برداری متغیر و سرعت پردازش داده ها روبرو هستند.
در این پژوهش با بررسی شهر نیویورک به عنوان یک مطالعه موردی، چالش ها و الزامات یک چارچوب یکپارچه تحلیل انطباق نقشه تبیین شده است. نیویورک دارای بزرگترین ناوگان های حمل و نقل شهری در ایالات متحده آمریکا، بیش از 100000 تاکسی و سرویس حمل و نقلی عمومی و خصوصی، بیش از5700 اتوبوس و بیش از2.5 63  میلیون سفر روزانه درون شهری است .
اگر تمامی این ناوگان دارای تجهیزات ردیاب خودرو باشند و داده های آنها به صورت پیوسته و 24 ساعته به سیستم مدیریت اطلاعات ترافیک دپارتمان حمل و نقل نیویورک ارسال شود حجم بسیار بزرگ و با ارزشی از اطلاعات مکانی جمع آوری می شود که از آن می توان در بسیاری از کاربردهای سامانه های حمل و نقل هوشمند استفاده نمود.
در این سناریو چندین چالش اساسی پیش روی چارچوب یکپارچه تحلیل انطباق نقشه است:
  • نرخ نمونه برداری پایین و قیود وزن دهی: اگر یک خودرو با سرعت ثابت 54 کیلومتر بر ساعت در حال حرکت باشد و نرخ نمونه برداری آن بر روی دو دقیقه تنظیم شده باشد، فاصله میان دو نقطه GPS متوالی قرائت شده 1.8 کیلومتر است. بدین ترتیب خودرو در این بازه زمانی ممکن است چندین یال از شبکه راه ها را طی کرده باشد بدون آن که قرائتی از آنها در دسترس باشد. در این شرایط به کارگیری قیود توپولوژیک مانند اتصال و گردش ممنوع (مورداستفاده در بسیاری از الگوریتم های معمول انطباق نقشه) در این شرایط باعث بروز خطا در عملکرد الگوریتم می شود.
  • نرخ نمونه برداری بالا و تحلیل آنی: اگر نرخ نمونه برداری تمامی این 100000 خودرو به صورت میانگین بر روی 20 ثانیه تنظیم شده باشد نرخ بارگذاری داده در کارساز مرکزی به 5000 قرائت GPS در ثانیه نیز می رسد. لذا الگوریتم باید بتواند به صورت آنی این حجم از داده را پردازش و تحلیل کند. 
  • تحلیل و پردازش جمعی داده های بزرگ FCD: اگر نرخ نمونه برداری تاکسی ها بر روی یک ثانیه تنظیم شده باشد نرخ بارگذاری داده در کارساز مرکزی به بیش از 100000 رکورد در هر ثانیه نیز می رسد. می دانیم در بیشتر تجهیرات مکان یابی خودکار وسایل نقلیه (AVL) حجم داده خودرو شناور حدودا 140 بایت در هر پیام است. بدین ترتیب در هر ثانیه حدود 12 گیگابایت داده برای به کارگیری در کاربردهای آنی بالادستی ITS باید به صورت آنی و بی درنگ ذخیره سازی و پردازش شود. همچنین این داده ها را می توان برای کابردهای متعددی از ITS بر روی کارساز مرکزی تجمیع کرده و سپس بهصورت جمعی مورد پردازش قرارداد. لذا مدیریت، تحلیل و پردازش چنین حجم بالایی از این داده ها یک چالش اساسی است.
با شناخت این چالش ها الزامات یک چارچوب یکپارچه تحلیل انطباق نقشه عبارت اند از:
  1. الگوریتم پیاده سازی شده در چارچوب باید سراسری بوده و مستقل از پارامترهای محلی باشد.
  2. چارچوب باید فارغ از وابستگی به حسگرهای اضافی بتواند نرخ موفقیت مناسبی را ارائه کند.
  3. چارچوب باید بتواند به صورت آنی و موثر پاسخگوی نیاز تحلیل های بالا دستی ITS باشد
  4. چارچوب باید داده هایی با نرخ نمونه برداری بالا یا پایین را دریافت و آنها را با دقت و سرعت مناسبی تحلیل کند.
  5. چارچوب باید بتواند مجموعه داده های بزرگ FCD را ذخیره سازی، مدیریت، تحلیل و پردازش جمعی کند. 
در این مقاله ما الزامات و چالش های نوین پیش روی تحلیل انطباق نقشه را در نظر گرفته و یک چارچوب یکپارچه برای پاسخ به نیازهای مسئله انطباق نقشه ارائه کرده ایم.
در چارچوب پیشنهادی برای پاسخ به چالش ذخیره سازی، مدیریتف تحلیل و پرازش داده های بزرگ FCD یک الگوریتم نوین MM توسعه یافته و بر روی سکویی مبتنی بر فناوری های رایانش ابری موازی سازی و پیاده سازی شده است. پیدایش فناوری رایانش ابری راه حلی سودمند، مقیاس پذیر و به صرفه در پاسخگویی به چالش های داده های بزرگ در کاربردهای حمل و نقلی و مکانی است. 
راه حل پیشنهادی این مقاله برای پاسخ به چالش مذکور تقسیم بندی مجموعه داده بزرگ و معرفی هر قسمت از پردازش به یک رایانه برای افزایش توان رایانشی است. عمده مشارکت های مقاله عبارتند از: 
  1. ارائه یک چارچوب یکپارچه و توزیع یافته تحلیل انطباق نقشه مبتنی بر فناوری های رایانش ابری برای پاسخ آنی به کاربردهای نوین تحلیل های بالادستی
  2. ارائه یک الگوریتم انطباق نقشه بهبود یافته و سازگار با انواع داده های FCD با نرخ های نمونه برداری متفاوت
  3. به کارگیری روش وزن دهی پویا برای قیود اختلاف میان زاویه های حامل راستای دو نقطه قرائت شده متوالی و راستای نقطه منطبق شده قبلی با نقطه کاندیدا و اختلاف کوتاه ترین مسیر باهدف بهبود صحت الگوریتم در مواجهه با داده های با نرخ نمونه برداری پایین. 
در ادامه مقاله ابتدا مروری بر تحقیقات اخیر انجام شده بر روی MM خواهیم داشت. سپس الگوریتم بهبود یافته و معماری چارچوب پیشنهادی را بررسی خواهیم نمود و در انتها صحت و عملکرد چارچوب پیشنهادی را مورد بررسی قرار خواهیم داد.

پیشینه تحقیق

در سال های اخیر تحقیقات متعددی برای بهبود الگوریتم های انطباق نقشه انجام شده است. در این بخش تعدادی از تحقیقات اخیر انجام شده بر روی MM را بررسی و نقاط ضعف و قوت آن ها را بررسی خواهیم نمود. 
یکی از مهم ترین روش های ارائه شده اخیر برای مسئله MM روش ولاگا و همکاران است. در این تحقیق از همسایگی مکانی و اختلاف راستا به همراه روش امتیازدهی مثبت و منفی به یال های کاندیدا استفاده شده است. 
ازجمله نواقص روش ولاگا و همکاران می توان به ضرایب وزن دهی ثابت محلی، وابستگی الگوریتم به اتصال یال های کاندیدا با یال منطبق شده برای قرائت پیشین و لذا ناتوانی در مواجهه با داده های با نرخ نمونه برداری پایین اشاره نمود که این نواقص در روش ارائه شده در این پژوهش به کمک وزن دهی پویا، بهره گیری از معیارهای هندسی و استفاده از معیار کوتاه ترین مسیر پاسخ داده شده اند.
هاشمی و کریمی یک الگوریتم وزن مبنا برای موقعیت یابی خودرو در شبکه های شهری پیچیده ارائه داده اند. هدف اصلی در این تحقیق ارائه یک الگوریتم کارآمد با حفظ صحت و نرخ موفقیت الگوریتم است. آن ها از سه قید فاصله مسان نقطه GPS و قطعه راه، اختلاف میان نقطه GPS و مسیر و اختلاف میان راستای نقاط متوالی GPS و راستای قطعات راه برای شناسایی بهترین قطعه راه در میان سایر کاندیداها استفاده کرده اند.
مهم ترین خاصیت این الگوریتم نرخ بالای تشخیص صحیح قطعه راه در مناطق شهری است. ازجمله معایب این روش همبستگی میان پارامترهای جهتی و به کارگیری پارامترهای توپولوژیک است که موجب ناکارآمدی الگوریتم در مواجهه با داده های با نرخ نمونه برداری پایین می گردد.
بدین منظور در این مقاله از شباهت میان زاویه حامل میان راستای دو نقطه قرائت شده متوالی و راستای نقطه منطبق شده قبلی با نقطه کاندیدا استفاده شده است.
همچنین در این پژوهش از معیار قید اختلاف کوتاه ترین مسیر برای مواجهه با نرخ های نمونه برداری متفاوت استفاده شده است. بهره گیری از فناوری های رایانش ابری پردازش توزیع یافته MM را نیز ممکن کرده است. 
لئو و همکاران روشی برای انطباق نقشه وزن مبنا در کنار یک روش درون یابی بر پایه الگوریتم انطباق توسعه داده اند. آنها از اطلاعات هندسی و توپولوژیک شبکه راه ها و بهره گیری از اطلاعات تاریخی خط سیر خودروها برای بهبود دقت روش خود بهره برده اند. 
ازجمله نقایص عمده این روش می توان به استفاده از ضرایب وزن مساوی و استفاده از پارامترهای توپولوژیک اشاره نمود که در پژوهش حاضر نواقص مذکور به کمک مفاهیم سطوح اطمینان، روش وزندهی پویا و استفاده از معیارهای هندسی پاسخ داده شده است.

توسعه چارچوبی مبتنی بر رایانش ابری برای تحلیل انطباق نقشه داده های خودروهای شناور
https://www.sid.ir/fa/journal/ViewPaper.aspx?ID=316069
 
كلمات كليدی: رایانش ابری، محاسبات ابری، سرور مجازی، رایانش ابری خودرو، رایانش ابری خودرویی

مقالات مرتبط

SIGMACloud

SIGMACloud

شرکت سیگما ITID در سال 1383 تاسیس شد. طی 15 سال فعالیت، سیگما عمدتا بر طراحی، توسعه و استقرار پورتال سازمانی، خدمات آنلاین و محصولات و خدمات محاسبات ابری تمرکز داشت. ما به 150+ سازمان و شرکت های بزرگ در ارتباطات مخابراتی، بانکی، پرداخت و صنایع دولتی برای دستیابی به اهداف خود کمک کردیم.