دانلود ‫پروژه فراهم سازی مسیر های شبکه جاده ای محدود کننده جابه جایی ها به صورت زمینه سرویس موبایل

1-مقدمه:

نرخ پذیرش جهانی تلفن سیار بسیار وسیع است ودر حالیکه اخیرا"تلفن های همراه عمدتا"برای ارتباطات صوتی مورداستفاده قرار می گیرند حجم داده های ارتباطی در حال افزایش است.با فن آوری هایی از جمله GPRS,2.5G,3Gکاربرمیتواند همیشه هزینه اضافی پرداخت نکرده و پهنای باند هم در حال افزایش است.

با ظهور سیستم ناوبری جهانی ماهواره گالیله وهمچنین پیشرفت های تنظیم قانون از جمله فرمان USE911وپیشرفتهای مشابه در آسیا واروپا موجب افزایش دسترسی توانمندی های موقعیت یابی شده است.بنابر این یک ساختار زیر بنایی در حال ظهور است که دامنه ای از خدمات موبایل مستقیم در محل را پشتیبانی می کند.

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

مسیر ها به دو دلیل قابل توجه هستند نخست عقل سلیم حکم میکند کاربران موبایل به طور معمول به سوی یک

 مقصدسفر کنند (به جای این که بی هدف پرسه بزنند)واینکه هنگامی که کاربر از جایی به جایی دیگر میرود اغلب یا به طور معمول مسیر مشابهی را طی می کند.به عنوان مثال یک کاربر به طور معمول از خانه به محل کار میرود.دوم اینکه مسیر ها به عنوان زمینه برای انواع سرویس ها اهمیت دارند.فی المثل سرویسی که از مسیر کاربر اطلاع دارد ممکن است به کاربر در مورد شرایط مسیر هشدار دهد مثلا":ازدحام و ساخت و ساز و تصادف های مسیر در حالیکه کاربررا با شرایطی که مربوط به مسیر او نیستند آزار نمی دهد.

به عنوان مثالی دیگر ممکن است هنگامی که یک کاربر در مورد محل هایی جالب توجه که مجاور هستند درخواست کند از مسیر ها استفاده میشود.

به ویژه ممکن است یک سرویس به جای اینکه صرفا"رستوران ها و پمپ بنزین های نزدیک موقعیت فعلی کاربر

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

اهداف تحقیق:

این تحقیق تکنیک های اصلی موجود در یک نرم افزار را شرح می دهد تا بر اساس ردگیری موقعیتGPSمسیر های هر کاربر را میسازد.

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

در این ساختار کاربران ثبت مسیر را کنترل می کنند .مسائل مربوط به ساختن مسیر حاصل از موقعیت های GPS

تحلیل شدند.الگوریتم هایی که مسائل را حل میکنند بصورت مشروح پوشش داده شدند.این ها شامل الگوریتم هایی

جهت تطبیق نقشه ای, ساخت عناصر مسیر, تقریب عناصر مسیرو پرکردن شکاف ها می باشند.این مولفه با استفاده

ازJAVA,ORACLEPL/SQL, و اوراکل فضایی اجرا میشود.اثبات مفهوم آزمایشاتی که از سوابق سیستم موقعیت  جهانی استفاده می کنند از وسایل نقلیه موجود دریک منطقه وبا استفاده از یک شبکه جاده ای برای این منطقه بدست آمد.مولفه مطرح شده را میتوان در سیستم های بزرگ مورد استفاده قرار داد که سرویس های موبایل را تدارک می بینند .چنین سیستم هایی میتوانند مسیرهای کاربر را در خواست کنند تا بر مبنای زمان وموقعیت فعلی حرکت او را پیش بینی کنند تا شرایط ترافیکی مربوطه را کنترل کنند , پارکینگ پیدا کنند و...

.

ساختار تحقیق:

این تحقیق به صورت زیر ساختار بندی شده است.ساختار سیستم ومولفه ثبت مسیر در بخش دوم شرح داده شده اند.ساختار ضروری داده ها جهت بدست آوردن مسیرهااز جانب سرور در بخش سوم موجود است و و الگوریتم های اصلی مورد استفاده این مولفه جهت ثبت مسیرها در بخش چهارم پوشش داده شده اند.

اعمال مولفه ثبت مسیردر

بخش پنجم شرح داده شده است.بینش هایی از یک تصدیق آزمایشی در بخش ششم گزارش شده اند.

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

2.ساختار سیستم

بدنبال یک باز بینی از طرف ایستگاه پردازش و سرور این بخش شرح میدهد که چگونه طرفین طی ثبت مسیر

همکاری کرده وچگونه موارد ثبت شده مسیر در هر دو طرف ایستگاه پردازش وسرور انجام میشوند.

1-2:  طرف های ایستگاه پردازش و سرور

در این ساختار یک ایستگاه پردازش نازک موقعیت های GPSرا جمع آوری کرده سپس آنها را فیلتر کرده واطلاعات فیلتر شده را به سرور میفرستد.سرور از این اطلاعات جهت ایجاد مسیر استفاده میکند.فرض میکنیم که هر وسیله ایستگاه پردازش دارای یک گیرندهGPS, ارتباط داده ها به سرور, ومحاسبه وذخیره قابلیت های یک تلفن موبایل مدرن تیپیکال می باشد.مثال فعلی نوکیا3650 با یک ارتباط GPS GPRS, و blutooth Emtac است.گیرندگان GPSجملات NMEA را انتقال میدهد.موقعیت/زمان /تاریخ میباشندوهمچنین اطلاعات اضافی که بمنظور اهداف ما دارای اهمیت کمتری میباشند.ایستگاه پردازش اطلاعات شخصی کاربر, کد شناسایی سیستم کاربر ومقاصد ومسیر های کاربر را ثبت میکند.هر موضوع مقصد دارای کد شناسایی محلی – جهانی است.موقعیت به وسیله یک منطقه مدور و با یک توصیف داده میشود.کاربراطلاعات مشخص و نام مقاصد را هنگامی که توسط ایستگاه پردازش در خواست شوند را وارد میکند .این توصیف نامی است که برای کاربر معنی دار است .همچنین هر مسیردارای کد شناسایی محلی- جهانی است.مسیر ها دارای شروع و مقصد های مربوطه و زمان های استفاده میباشند.ولی ایستگاه پردازش بخش هایی از جاده را از مسیر بدست نمی آورند.

سرور اطلاعات در یافت شده از ایستگاه های پردازش را ثبت و آنالیزمیکند .همه چیز های مربوط به مسیر یعنی

قسمت های تشکیل دهنده, شبکه جاده ای, کاربردآن ومقاصد آن همچنین اطلاعات مشخص هر کاربر در سرور ذخیره میشوند.اینکار جهت اجتناب از فقدان اطلاعات انجام میشوند کاربرانی که یک ابزار ایستگاه پردازش جدید گزینش میکنند میتوانند کلیه اطلاعات مربوطه را از سرور بدست آورند.

در حالیکه در این رابطه بحث بیشتری در این تحقیق انجام نمیگیرد معتقدیم که امکان دارد رمزی کردن در پاسخ به نگرانی های حفظ حریم خصوصی مورد استفاده قرار گیرد.

2-2:عاملیت ثبت مسیر

ما نخست تعامل میان کاربر و سرور را پوشش میدهیم وسپس ثبت مسیر را از طرف ایستگاه پردازش وسرور پوشش

میدهیم.

2-2-1تعامل ایستگاه پردازش و سرور

کاربر فرآیند ثبت مسیر را فعال وغیر فعال میکند.هنگام فعال بودن دستگاه ایستگاه پردازش اطلاعات  زمانی-موقعیتی حاصل از گیرندهGPS رافیلتر ومیانگین گیری می کند.سر انجام این اطلاعات همراه با اطلاعات در مورد کاربر ومقاصد کاربر منتقل می شوند.                                                                                               توالی انتقال به طول مسیر, توانایی های تکنیکی دستگاه پردازش وکیفیت اتصال بستگی دارد.

هنگامی که سروراطلاعات ضروری داشته باشد سرورمسیرسازی را انجام داده وزمان استفاده راثبت کرده وبه مسیر

یک کد شناسایی می دهد.نتیجه در پایگاه داده ها ذخیره شده و به ایستگاه پردازش نیز ارسال میکند

اطلاعات ارسالی به سرور از ایستگاه پردازش از سه قسمت تشکیل شده اند:کاربروموضوع و اطلاعات استاندارد.

فرمت به این بستگی دارد که در که در حال حاضر چه اطلاعاتی موجود است.

اطلاعات کاربر:اگر کاربر ثبت نام کرده باشد, بلوک اطلاعاتی شامل یک IDخواهد بود.برای کاربران جدید شرح

کاربرگنجانده میشود.بنابراین در این بلوک IDکاربر وشرح کاربر را داریم .

اطلاعات موضوع:نقاط شروع و پایان مسیرها موضوعات میباشند.موضوعات مقصد یک مسیر جدید ممکن است در

 حال حاضر جهت تعیین نقاط شروع و پایان سایرمسیرها استفاده شود.در این مورد سرور میتواند خودش مطابق با

 مختصاتGPSمقصد را تعیین کند.اگر هر دو مقصد ومبدا معلوم باشند این بلوک خالی است و اگر یک مقصد را تعیین کند.اگریک مقصد تعیین شده باشد بلوک حاوی یک شرح مبدا یا مقصد است.اگر نقاط شروع وپایان هنوز تعریف نشده باشند برای هر دو آنها داریم :

اطلاعات استاندارد:اطلاعات موقعیتGPS ،زمان وتاریخ همیشه موجود هستند .این بلوک شامل سه عنصر

GPS]،زمان و تاریخ[ است.

هنگامی که سرور اطلاعات را به یک ایستگاه پردازش میفرستد همیشهIDرا برای یک مسیر که به تازگی ثبت شده

است بر میگرداند.اگر هر یک از پارامتر های مسیر تعریف نشده باشد ایستگاه پردازش فرض میکند که جریان حاصل

از سرور شامل اطلاعات گم شده است.سرور IDها را برای کاربران ایجاد کرده و کاربران موضوعات مقصد را بوجود می آورند.اینIDها به ایستگاه پردازش باز میگردند.

همچنین سرور یک موقعیت مرکزی را برای یک مقصد جدیدا"ثبت شده باز میگرداند در صورتی که موقعیت مرکزی

موضوع با مختصات GPSنخست ونهایی متفاوت باشند.

اگر سرور شعاعی را انتخاب کند که با مقدار تعریف شده متفاوت باشد یک شعاع را همراه با موقعیت مرکز باز میگرداند.

بنابر این از سرورID ]کاربر ،موضوع شروع،موضوع پایان، IDمسیر،مختصات شعاع شروع،مختصات پایان[میباشد

که IDمسیر تنها پارامتری است که همیشه موجود است .ایستگاه پردازش جریان را از سرور دریافت کرده،آنالیز میکندواطلاعات موجود در آن را ثبت میکند.

2-2-2ثبت مسیر از طرف ایستگاه پردازش

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

اگر کاربر در سیستم ثبت نام کرده باشد IDکاربر به جریان افزوده میشودو در غیر این صورت ایستگاه پردازش در

خواست شرح کاربر را میکند.دستگاه شرح محلی را ثبت کرده،کاربر را به صورت تعریف نشده در جریان قرار داده،

وتوصیف را به جریان می افزاید

آخرین وظیفه ساختن بلوک موضوع مقصد است اگر موضوعات مبداءو مقصدبه صورت تعریف نشده باشند یا کاربر جدید باشد ابزار توصیفات را از موضوعات مقصد بدست می آورد.موضوعات مقصد به صورت تعریف نشده در جریان قرار داده می شوند و توصیفات آنها به جریان افزوده می گردد.دستگاه توصیفات ،شعاع های از پیش تعیین شده و و موقعیت های محلی را همراه با IDمحلی ثبت میکند.اگر فقط یک موضوع مقصد ثبت نشده باشد ،همان مراحل ولی فقط برای یک موضوع انجام میشود .اگر هر دو موضوع مقصد تعریف نشده باشند ،بلوک خالی است.

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

2-2-3ثبت مسیر از طرف سرور سرور ثبت مسیر اصلی را انجام می دهد که از تبدیل اطلاعات در یافتی از بعضی ایستگاه های پردازش به مسیر معین به وسیله یک توالی قسمتهای شبکه جاده ای می باشد.همچنین یک IDبرای مسیر تولید میشود و هر گونه داده دریافتی از ایستگاه پردازش که موضوعات مقصد را شرح داده وکاربر ثبت کرده را شرح میدهد.

ثبت مسیر از طرف سرور در شکل 2 موجود است.با داشتن اطلاعات حاصل از یک ایستگاه پردازش سرور چک میکند که کاربر جدید است یا نیست اگر چنین بود سرور شرح کاربر را از جریان دریافت کرده،یک IDبه کاربر اختصاص داده ،این اطلاعات را ذخیره وIDکاربر را در جریان ارسالی به ایستگاه پردازش می گنجاند.

سپس سرور به بررسی موضوعات مقصد می پردازد .اگر هر دو (مقصد و مبداء) تعریف نشده باشند.سرور اطلاعات موضوع مقصد را از جریان استخراج ،IDها را ایجاد کرده ،موضوعات مقصد جدید را ثبت وID ها را به جریان ایستگاه پردازش می افزاید.

اگر فقط یک موضوع مقصد تعریف نشده باشد این مراحل برای یک موضوع انجام میشوند اگر نقطه شروع معلوم نباشد اطلاعات مربوط به آن تولید شده و ثبت می گردد.

سپس موضوع پایانی با استفاده از آگاهی ها پیرامون موضوعات کاربر تعیین میشوند اگر فقط موضوع مقصد تعیین نشده باشد مراحل مشابه اتخاذ می گردد.

اگر هر دو موضوع مقصد تعیین شده باشند با استفاده از اطلاعات ذخیره شده معین میشوند.

بالاخره سرور قسمت سوم جریان اطلاعات را که شامل اطلاعات استاندارد است را آنالیز میکند سرور مسیر را از اطلاعات GPS کشف کرده،یک ID برای مسیر ایجاد کرده و این ID را به جریان ارسالی به ایستگاه پردازش می افزاید و مسیر را در پایگاه داده ها ثبت میکند و اگر مختصات آنها با نقطه شروع یا پایانی جریان GPSمتفاوت باشد و یا اگر شعاع ها مقادیر از پیش تعیین شده نباشند شعاع آنها را اضافه میکند .سپس سرور اولین زمان کاربرد از مسیر را ثبت میکند.جریان ساخته شده برای پایان رساندن ثبت مسیر به ایستگاه پردازش ارسال میگردد.

3.مسیرها وشبکه های جاده ای ما ساختارهای اصلی داده های مورد استفاده جهت بدست آوردن مسیرها در سمت سرور را تعیین کردیم.ما شبکه واقعی جاده ای را در فضای دو بعدی ترسیم کردیم و نتیجه را بصورت یکسری پلی لاین نمایش دادیم .

یک پلی لاین توالی Base Point است که به B c متعلق می با شند.انتخاب Base Point های متفاوت منجر به نمایش شبکه جاده ای متفاوت میشود.به طور کلی،استفاده از Base Point های فراوان منجر به صحت بالاتر میشود.

مجموعه پلی لاین ها به صورت تعریف میشود که و به ترتیب نقاط شروع وپایان پلی لاین می باشند .

مثال 3-1 :شکل 3 دو پلی لاین متقاطع را ترسیم کرده است.

( =( و ( =( نقطه شروع ، و نقطه پایان آن است .

در مدل شبکه جاده ای ما هر پلی لاین بیانگر یک جاده دو طرفه است.بدون مراجعه به جهات ترافیکی جاده ها پلی لاین ها دارای "جهت هایی" هستند که از نقطه شروع به Base Point پایانی میرود.

با وجود آنکه شکل جغرافیایی جاده بطور تقریبی در پلی لاین موجود است ،محاسبه فواصل در طول جاده با جمع فواصل اقلیدسی قسمتها بسیار کم دقت است.به جای آن ما فرض میکنیم فواصل دقیق نقطه شروع به تمام یا بعضی Base Pointها را در پلی لاین تقریبی جاده داریم ،و این فواصل را به Base Point ها ارتباط میدهیم.این امر تصویر پلی لاین جاده را از بدست آوردن فواصل در طول جاده ،مجزا کرده ومدیریت جاده ای فعلی را حفظ می کند.استفاده از فواصل واقعی جاده محاسبات را دقیق تر می کند.معیار یک Base point ،به صورت داده شده است.این معیار بر آخرین نقطه یک پلی لاین مربوط است.و نشاندهنده طول واقعی جاده ارائه شده توسط پلی لاین می باشد.همیشه مقدار مربوط به اولین Base Point صفر است.اگر یک مقدار برای در پلی لاین موجود نباشد نزدیکترین نقاط Base point قبلی وبعدی با مقادیر مشخص را تعیین میکنیم معیاررابه وسیله میان یابی خطی تقریب میزنیم.

طول واقعی پلی لاین میان نقاط Base point با مقادیر معلوم تقسیم بر فاصله اقلیدسی جاده ما بین این نقاط میشود.این مقدار در فاصله اقلیدسی روی جاده میان دو نقطه با مقدار معلومو نقطه قبلی با مقدار معلوم ضرب میشود.حاصل به مقدار نقطه پیشین افزوده میشود.اگر وجود نداشت از فاصله اقلیدسیرو بجلو استفاده میکنیم.

مثال 2-3:شکل 4 محاسبه طول base pointهای( pl=(را مثال زده است.اعداد فوق قسمت های خط نشاندهنده فواصل اقلیدسی میان جفت های base pointمیباشند.اعداد زیریbase pointها مقادیر دقیق ترمقایسه شده توسط اطلاعات جاده را نشان میدهند.در شکل 4-الف هنگام محاسبه مقدار برای و i=2وj=4است.

با استفاده از فرمول تایید میشود که=10.4 میباشد.شکل 4bفاقد مقادیر دو base pointپایانی واست.

بمنظور محاسبات طولی از ساختار داده ای Mاستفاده میکنیم که مجموعه متناهی از نقاط سه گانه I،b،plاست که pl є PLیک پلی لاین است.b єBیک base pointاز plاست و l єRمقدار base point ،bروی پلی لاین pl است.

تعریف 1-3 : تابع(طول): Lm :PL×B→R ، شناسه ها را به عنوان یک پلی لاین (b1,…bn)=pl و یک نقطه مبنا bi، 1≤ i ≤ n در نظر می گیرد.

تابع ، فاصله راه، از آغاز پلی لاین را به نقطه ی مبناbase poin باز می گرداند.

در این جا ، Lm(pl,b1)=◦ و Lm(pl, bn)، طول پلی لاین است.

برای نقاط bi و bj که 1≤i ، به عبارت دیگر، برای هر base pointاز پلی لاین، مقیاس و اندازه ای وجود دارد و تنها یک اندازه را می توان به نقطه مبنا در رابطه با همان پلی لاین متصل کرد.

در مرحله بعدی، یک زیر پلی لاین، بخشی از یک جاده را نمونه سازی می کند( طرح ریزی می کند).

یک زیر پلی لاین، سه جمله ای است که حاوی یک خط مبنا و دو عدد واقعی است.

عدد واقعی اول نمایانگر فاصله ای است که بر روی آن زیر پلی لاین بر روی پلی لاین آغاز شده است و عدد واقعی دوم نمایانگر فاصله ای است که زیر پلی لاین بر روی پلی لاین خاتمه می یابد.

تعریف2-3 :subpolyline(زیر- چند خطی).

قرار دهید SPL CPL×R² ، مجموعه بی انتهایی از زیر پلی لاین ها را.

یک زیر پلی لاینSPL=(PL , ) ، که در آن 0≤ ارزش نهایی ساب پلی لاین همیشه بزرگتر از ارزش آغازین آن است و اندازه نهایی نمی تواند از اندازه نقطه مبنای نهایی پلی لاین تجاوز کند.

در شکل، قسمت برجسته پلی لاین PL2 ، یک زیر پلی لاین SPL2 است.

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

تعریف3-3 : (ارتباط).

قرار دهید: بنابراین، C مجموعه نامتناهی از رابطه ها است.

شکل الف را نگاه کنید، پلی لاین های PL1 و PL2 هر یک دارای نقطه اتصالی در محل تقاطع خود می باشند.

در فاصله از آغاز PL1 ، یک خط اتصال وجود دارد و در فاصله از آغاز PL2 نیز یک نقطه اتصال وجود دارد.

بنابراین ما دارای اتصال C={(PL1 , ) , (PL2 , )}ЄC می باشیم.

نقاط اتصال در شکل های ب و ج، مشابه هم اند اما شرایطی را نمایان می سازند که در آن نقاط اتصال با نقاط مبنا منطبق می شوند.

به خاطر داشته باشید وقتی ما اتصالات را به دست می آوریم، در واقع نمایش نموداری شبکه جاده ای را به دست می آوریم.

همانگونه که قبلاً توضیح داده شد، کاربران خدماتی ما از طریق شبکه جاده ای سفر خود را به مقاصد دیگر یا از مقاصد دیگر آغاز می کنند.

این مقصد ها را ما «اشیاء مقصد» (Destination Objects) می نامیم.

ما شیء مقصد را به عنوان دایره ای با زیرچندخط هایی می نامیم که داخل دایره وجود دارند.

هر شیء مقصد، به یک کاربر مربوط می شود.

تعریف 4-3 (شیء مقصد): قرار دهید Do را مجموعه بی انتهایی از اشیاء مقصد.

هر شیء مقصد، odo є D ، 3 جمله ای (SPLS ، دایره ، U ( است که: (1) u به U متعلق است، مجموعه کاربران خدماتی.

(2) circle=(xo , yo , rd)ЄR2×R ، دلالت گر دایره تعریف شده از طریق (x-xo)2 + (y-yo)2= rd2 می باشد.

(3) ، که در آن تابع gєt SPLS ، مجموعه همه زیر چند خط های SPLS که درون دایره وجود دارند را باز می گرداند.

ما می گوییم شیء مقصد do به کاربر u تعلق دارد و در ناحیه دورانی با مرکز (xo , yo) و شعاع rd قرار گرفته است.

به خاطر بسپارید درست است که طراحی اشیاء مقصد به صورت نقاط، ساده تر از طراحی نواحی دورانی است، اما چندان مناسب نیست.

برای نمونه، ممکن است هر روز یک کاربر در نواحی مختلف در همان پارکینگ پارک کند و یا حتی در پارکینگ دیگری در نزدیکی محل کار کاربران.

بنابراین، مقصد مشابه ممکن است انتهاهای مختلفی داشته باشد و در روزهای مختلف، موقعیت های مختلفی را آغاز کند.

به اشیاء مقصد می توان شعاع های مختلفی داد که به الگوهای کاربری و تعداد پلی لاین های اطراف آنها بستگی دارند.

در مرحله بعدی، ما زمان های کاربری به جاده ها ربط می دهیم.

برای به دست آوردن ترتیب های کاربری از جاده ها، ما سال، ماه، روز، ساعت، دقیقه و ثانیه هر کاربری را به طور جداگانه به دست می آوریم( به خاطر داشته باشید که زمان کاربری یک جاده، زمان آغاز استفاده از جاده است).

تعریف 5-3 (زمان کاربری): بگذارید زمان کاربری T مجموعه متناهی از 6 جمله ای (y, m, d, h, m n, s) به ترتیب دلالت گر سال، ماه، روز، ساعت، دقیقه و ثانیه می باشند.

با تعاریف قبلی در خصوص مکان، ما می توانیم مفهوم مسیر را تعریف کنیم.

یک مسیر دنباله ای از زیر پلی لاین های متصل به هم می باشد.

نیمه پلی لاین اول در یک شیء مقصد آغازین آغاز می شود و انتهاهای نیمه چند خط آخر در شیء مقصد نهایی خاتمه می یابد.

تعریف 6-3 (مسیر): بگذارید R، مجموعه متناهی از مسیرها باشد، هر مسیر یک 4تایی (RE, dos, doe, ST) است که در آن: (1) RE=((spl1 , dir1),…,(splN , dirN) ، توالی زیر چند خط هایی با مسیرهای حرکتی مرتبط با هم می باشد.

توالی، مسیر را شکل می بخشد.

برای عناصر مسیر (spli , diri) که در آن SPL є spli =(pli , ,) ، diri مسیری حرکتی در طول pli مورد استفاده می باشد: چنانچه مسیر حرکتی بر روی زیر پلی لاین spli با مسیر پلی لاین pli منطبق شود :1 diri = و اگر نه :-1 آیتم (1) تضمین می کند که یک مسیر، توالی زیر چند خط هایی است که با مسیرهای حرکتی ارتباط دارند.

به یک زیر نیمه خط با یک مسیر حرکتی ارتباطی، عنصر مسیر (route element) می گویند.

آیتم (2) تضمین می کند که عنصر مسیر نخست با شیء مقصد آغازین مرتبط است.

عنصر مسیر نخست در صورتی در شیء مقصد آغازین آغاز می شود که مسیر حرکت، 1 باشد( مسیر حرکت پلی لاین نیز باید عدد یک باشد) و عنصر در صورتی در شیء مقصد پایان می یابد که مسیر حرکت 1- باشد( درست عکس حالت پلی لاین).

آیتم (3) تضمین می کند که عنصر مسیر نهایی با شیء مقصد نهایی در ارتباط است.

عنصر در صورتی در شیء مقصد نهایی پایان می یابد که مسیر حرکتی 1 باشد(درست مانند مسیر حرکت پلی لاین) و عنصر در صورتی در شیء مقصد نهایی آغاز می شود که مسیر حرکت 1- باشد(عکس مسیر پلی لاین).

آیتم (4) تضمین می کند که عناصر مسیر به هم ربط دارند.

یک عنصر مسیر جایی آغاز می شود که عنصر قبلی پایان می یابد: در اتصالی که در آن پلی لاین ها متفاوتند و یا در صورت تعلق عناصر مسیر به همان پلی لاین، در نقطه ای بر روی یک پلی لاین قرار می گیرند.

بر اساس تعریف ما از یک پلی لاین، فاصله آغازین باید همیشه کمتر از فاصله انتهایی باشد.

بنابراین فواصل آغازین و انتهایی توسط مسیر حرکت تعریف می شوند.

مثال 3-3 : در شکل 6 شبکه جاده ای آمده است که شامل سه پلی لاین ذیل می باشد: PL1 = (b11, b8, b4, b12) PL2 = (b1, b2, b3, b4, b) PL3 = (b6, b2, b7, b8, b9, b10) مسیر برجسته r =(RE, uos, uoc, ST) از بخش های هر سه پلی لاین استفاده می کند.RE ، توالی 4 عنصر مسیر است.

زیر پلی لاین عنصر مسیر اول توسط (PL3, L, Lm(pl3,b2)) تعیین می شود، که در آن L اندازه ای در طول زیرپلی لاینsub poly line است.

این زیرپلی لاین نقطه ای را مشخص می کند که به ناحیه دورانی شیء مقصد کاربر uos تعلق دارد.

مسیر حرکتی زیر چند خط با مسیر پلی لاین pl3 منطبق است.

4.

روش های ساخت مسیر: نخست روش هایی را ارائه می دهیم که شناسائی کننده چندخطی هائی اند که بر روی آنها یک کاربر حرکت می کند.

سپس به معرفی بخش ها و الگوریتم های پوششی چرخشی (turn cover algorithms) می پردازیم و سپس به تعریف ساب پلی لاین هایی که عناصر مسیر هستند که این عناصر در تمامی مسیرها ترکیب می شوند و مسیر را می سازند.

ما بین موقعیت ها و نقاط GPS تمایز ایجاد می کنیم.

بنابراین «GPS position» به جملات NMEA حاصل از یک گیرنده GPS نمونه گفته می شود و «GPS point» به جفت مختصات (x , y) که بخشی از موقعیت GPS است اطلاق می گردد.

در الگوریتم مختص این قسمت تنها از اطلاعات مربوط به نقطه استفاده می شود، بنابراین، آنها از نقاط GPS استفاده می کنند.

14- : شناسائی پلی لاین: مرحله اول در ایجاد یک مسیر از داده های دریافت شده از یک مشتری، شناسائی پلی لاین هایی است که بر روی آنها مشتری در حال حرکت است و از طرف دیگر شناسائی موقعیت های مشتری بر روی پلی لاین ها.

ما فرض می کنیم که نقاط GPS دقیق نیستند و نقاط GPS در محدوده فاصله D مربوط به موقعیت واقعی هستند.

تصویر نقطه در بخش خط point projection on to line segment:در الگوریتم های بعدی باید یک نقطه GPS در بخش خطی یک پلی لاین project شوند.

Project باید به عنوان اندازه ای در طول پلی لاین تعریف شود و فاصله بین نقطه GPS و project آن را باید محاسبه کرد.

در شکل 7 سه حالت برای این project آمده است.

پاره خط bibi+1 مشخص شده است و دایره های کوچک نشان گر توالی نقاط GPS می باشند که از میان آنها g ,g1 ,g2، مطلوب می باشند.

دایره های بزرگ با شعاع D یا همان maximum بی دقتی مجاز، نشانگر بی دقتی نقاط GPS می باشد.

می توان یک نقطه GPS را در طول پاره خط به دست آورد، همانند g در شکل الف.

تصویر آن، موقعیت o است و فاصله اقلیدسی بین موقعیت های o و g به صورت d مختصات ممکن است قبل یا پس از پاره خط باشد، به طوریکه در شکل ب به صورت g1 و g2 مشخص شده است.

با توضیح مسأله تصویر، اینک می خواهیم به مسأله تصویر کردن نگاه دقیق تری بیندازیم.

ما به فاصله d از یک نقطه GPS به تصویر آن نیاز داریم.

از این حالت برای تعیین تصویر نقطه GPS در شبکه جاده ای استفاده می کنیم.

علاوه بر این، ما به فاصله از آغاز پلی لاین تا تصویر نیاز داریم.

فاصله d را می توان با استفاده از حسابان بردار محاسبه کرد.

قرار دهید پاره خط bibi+1 بخشی از یک پلی لاین (b1,…,bn) باشد.

پاره خط مسیر پلی لاین را تعیین می کند.

با bi که نقطه آغاز است، ما دو بردار داریم که از bi ساطع می شوند.

یکی از این بردارها در bi+1 پایان می یابد و دیگر در نقطه GPS (g) (رجوع کنید به شکل8).

از زاویه α بین این بردارها در محاسبه فاصله d استفاده می شود.

محاسبه با استفاده از ضرب اسکالر صورت می گیرد: چنانچه زاویه، منفرجه باشد(شکل الف)، لذا فاصله d فاصله اقلیدسی از نقطه GPS به آغاز پاره خط است.

اندازه نقطه project شده، اندازه نقطه آغاز پاره خط است: چنانچه زاویه حاده باشد، دو احتمال وجود دارد که در شکل ب و ج آمده است.

اگر طول تصویر big در 1bibi+ (|big′| )از 1bibi+ تجاوز کند(شکل b)، فاصله d همان فاصله بین نقطه انتهایی bi+1 مربوط به پاره خط و نقطه GPS (g) است.

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

ما محاسبه های انجام شده در بالا را در یک تابع Calc param (رجوع کنید به الگوریتم 1-4) خلاصه بندی می کنیم.

تابع سه جمله ای (g, pl, pls) را به عنوان شناسه در نظر می گیرد و زوج (d , ) را باز می گرداند، در اینجا d فاصله نقطه GPS به پاره خط pls بر روی پلی لاین pl است و اندازه در طول pl مربوط به فراکنش g در pls است.

الگوریتم 1-4: محاسبه پارامتر های تصویر(تابع Calc param).

کار ما بهتر از طراحی نقطه های GPS در نزدیکترین چندخطی با کمترین مقدار d است.

برای نمونه، وقتی که نقطه یک GPS نزدیک یک چهارراه است، پلی لاین واقعی، پلی لاین است که از نزدیک پلی لاین عبور می کند.

نمونه دیگر زمانی رخ می دهد که جاده ها نزدیک هم باشند.

در شکل 9 نشان می دهد که چطور دو نقطه GPS (g2 , g1) در نزدیک ترین حالت به یک جاده نادرست اند.

برای بررسی صحیح این موارد، نقاط قبلی GPS را برای نقاط GPS قبلی طراحی می کنیم.

نقطه GPS ابتدایی :برای نقطه GPS اولیه، هیچ داده جمع آوری شده ای، در زمان طراحی آن برای یک پلی لاین وجود ندارد.

نقطه GPS ابتدایی در صورتی برای یک پلی لاین طراحی می شود که یک پلی لاین دارای بخشی با فاصله تصویر d ≤ D باشد.

اگر چندین پلی لاین های این چنینی وجود داشته باشند، تا زمانی که چند موقعیت دیگر به طور صحیح طراحی نشوند، موقعیت مذکور طراحی نمی شود.

تابع «polycand» (به الگوریتم 2-4 رجوع کنید) یک نقطه GPS (g) را به عنوان یک شناسه در نظر می گیرد و مجموعه ای از پلی لاین های نامزد را با اندازه های تصویر g در بخش های پلی لاین بازگشت می دهد.

الگوریتم 2-4: یافتن چندخطی های نامزد(تابع polycand) تابع، از تابع Calc param استفاده می کند.

همه خطوط پاره خط های هر پلی لاین مورد تحلیل قرار گیرند اما تنها پاره خط پلی لاین که نزدیکترین فاصله به نقطه g را دارا می باشد به عنوان کاندیدا انتخاب می شود.

تابع از دو متغیر موقتی d و l استفاده می کند.

متغیر d فاصله موجود از شروع پلی لاین تا نقطه تصویر شده بر روی نزدیکترین پاره خط را ذخیره می کند.

در خط 5 ، پارامترهای (cd , cl) برای هر پاره خط spli ، محاسبه می شود.

اگر فاصله cd تا پاره خط فعلی کمتر یا برابر با مقدار بی دقتی D برابر باشد و برای برخی از پاره خط های قبلی همان پلی لاین کمتر از فاصله d باشد، فاصله فعلی cd در کنار cl و اندازه تصویر ذخیره می شوند(خطوط 8-6).

پلی لاین که دارای پاره خط هایی در فاصله بی دقتی از نقطه g می باشد، در فهرست پلی لاین های کاندیدا یا همان Cand گنجانده می شود( رجوع کنید به خطوط 11-10).