بخشی از مقاله
فراهم سازی مسیر های شبکه جاده ای محدود کننده جابه جایی ها به صورت زمینه سرویس موبایل
-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<j≤n ، رابطه Lm(pl, bi) – Lm(pl,bj) حد اقل فاصله اقلیدسی(Euclidation distance) بین bi , bj است. علاوه بر این، اگر Lm(pl,bi)=1 باشد، پس
، به عبارت دیگر، برای هر base pointاز پلی لاین، مقیاس و اندازه ای وجود دارد و تنها یک اندازه را می توان به نقطه مبنا در رابطه با همان پلی لاین متصل کرد.
در مرحله بعدی، یک زیر پلی لاین، بخشی از یک جاده را نمونه سازی می کند( طرح ریزی می کند). یک زیر پلی لاین، سه جمله ای است که حاوی یک خط مبنا و دو عدد واقعی است. عدد واقعی اول نمایانگر فاصله ای است که بر روی آن زیر پلی لاین بر روی پلی لاین آغاز شده است و عدد واقعی دوم نمایانگر فاصله ای است که زیر پلی لاین بر روی پلی لاین خاتمه می یابد.
تعریف2-3 :subpolyline(زیر- چند خطی).
قرار دهید SPL CPL×R² ، مجموعه بی انتهایی از زیر پلی لاین ها را.
یک زیر پلی لاینSPL=(PL , ) ، که در آن 0≤ < ≤Lm (Pl,Bn) است، بخشی از پلی لاین (PL) است که در اندازه آغاز و و در اندازه پایان می یابد.
ارزش نهایی ساب پلی لاین همیشه بزرگتر از ارزش آغازین آن است و اندازه نهایی نمی تواند از اندازه نقطه مبنای نهایی پلی لاین تجاوز کند.
در شکل، قسمت برجسته پلی لاین PL2 ، یک زیر پلی لاین SPL2 است. ما ارتباط بین جاده ها را به دست خواهیم آورد.برای این کار ارتباطی را به صورت مجموعه ای از چند خطی ها، فواصلی که نشانگر محل ارتباط بر روی پلی لاین ویژه می باشند را طراحی می کنیم.
