دانلود مقاله راهکاری جدید برای شاخصگذاری دادههای خطسیر اشیاء متحرک ، برای پاسخگویی به پرسوجوها در سیستمهای هدایت و ناوبری

بخشی از مقاله

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

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

کلید واژه- ساختار شاخصگذاری، پایگاه دادههای زمان-مکانی، اشیاء متحرک، پرس و جو.

-1 مقدمه

امروزه حرکـت یکـی از واژههـای کلیـدی و مهـم اسـت کـه ابزارهای محاسباتی همه جا موجود (Ubiquitous) و سرویسهـای مبتنی بر مکان (LBS) پشـتیبانی خـوبی از آن دارنـد.[1 ] وجـود ابزارهــای نــوین و رشــد ســریع سیســتمهــای هــدایت و نــاوبری، تکنولوژی های ارتباطات بی سیم و دستگاه های آگاه از محل نظیـر GPS در راستای ثبت دادههای زمانی-مکانی، فضـای مناسـبی را برای استفادههای مختلف از این نوع دادهها محیا کرده اسـت-1] .[4 از این داده هـا مـی تـوان در سیسـتم هـای هـدایت و نـاوبری هواپیماها، هلیکوپترها، پهبادها سـود بـرد. در نبردهـای هـوایی و سیستمهای دفاع موشکی برای ردگیری مسیر حرکـت هواپیماهـا و موشک ها قابل استفاده است. همچنـین بـا ردگیـری خـط سـیر اشــیاء متحــرک و جمــعآوری، ثبــت، نگهــداری، تحلیــل و آنــالیز داده های این خط سیرها میتوان علاوه بر ارائه انواع سرویسهـای مرتبط به سازمانهـای ذیـربط و کمـک بـه امنیـت پروازهـا، بـه مسافران ایـن پروازهـا نیـز تسـهیلات جدیـدی ارائـه نمـود. ایـن تسهیلات علاوه بر افزایش سطح کیفیت خـدمات، باعـث کـاهش زمان و هزینه نیز میگردد.

خطسیر یـک شـیء متحـرک، از انـواع داده هـای پیچیـده و جدیــد اســت کــه دارای هــردو پــارامتر مکــان و زمــان اســت.

سیستمهای پردازش خطسیرها، از جملـه پایگـاهدادههـای اشـیاء متحرک (MOD) و پایگـاهدادههـای زمـانی-مکـانی نتوانسـتهانـد متناسب با مسائل طرح شده در این حوزه، پیشـرفت چشـمگیری داشته باشند. برای پشتیبانی از برنامـه هـای کـاربردی مـرتبط بـا سرویس های مبتنی بر مکان، پژوهشگران حوزه پایگـاه هـای داده در یک دهه گذشـته تـلاش هـای زیـادی بـرای توسـعه MOD و پایگاهدادههای زمانی-مکانی انجام داده اند. از موضـوعات مهـم در این پایگاهدادهها، انجام عملیـات هـای مختلـف همچـون دریافـت داده ها، پـیش پـردازش، شـاخص گـذاریداده هـا، ذخیـره سـازی و جستجو میباشد.

انجام پرسوجو در پایگاه داده هـای زمـانی-مکـانی بـه دلیـل ویژگیهای ذاتی دادهها، پرس وجوهای طرح شـده، حجـم بـالای دادههــا، پویــایی آنهــا، ســرعت تغییــرات آنهــا و پیچیــدگی الگــوریتم هــای پــردازش ایــن پــرسوجوهــا هزینــهبــر و ســنگین است.[5] در نتیجه افزایش کارایی در ایـن حجـم بـالا از دادههـا، یک مسئله مهـم بـرای پایگـاهدادههـای خـطسـیر اسـت و بـرای پاسخگویی به این حجم بالای داده، نیاز به اسـتفاده از روشهـای دسترســـی((Access Methods مناســـب و ارائـــه روشهـــای شاخصگذاری زمانی-مکانی مناسب اسـت. پایـه و اسـاس بیشـتر روشهــای شــاخصگــذاری در پایگــاهدادههــای زمــانی-مکــانی نســخههــای مختلــف و ســه بعــدی از R-tree و خــانواده R-tree

1

میباشد[6] که هدف آن کاهش دسترسی به دیسـک و درنتیجـه کاهش هزینه پرسوجو است.[7]

در این مقاله برای شاخصگذاری دادههـای زمـانی-مکـانی و پاسخگویی بـه پـرس و جوهـا روش IMORS توسـعه داده شـده است. از این روش بـرای شـاخص گـذاری موقعیـت جـاری اشـیاء استفاده میشـود. در ایـن نـوع از روشهـا سـرعت بروزرسـانی از اهمیت بالایی برخـوردار بـوده و از چـالشهـای اصـلی محسـوب میشود. به خصوص در بحث اشیاء متحرک که موقعیت اشیاء بـه سرعت در حال تغییر بوده و بروزرسانیها مکرراً انجام می شـود و درنتیجه نیاز به مکانیسمهای بروزرسانی سریع اسـت. بـرای ایـن منظور سعی شده تا بـا بهینـهسـازی ایـن روش و رفـع برخـی از مشــکلات آن عــلاوه بــر افــزایش ســرعت بروزرســانی، ســرعت پاسخگویی به پرسوجوها نیز افزایش یابد. همچنین زمان ساخت شاخص نیز بهبود یافته است. در آزمایشات نشان داده شده اسـت که اصلاحات انجام شده در این زمینه موفق عمل کرده است.

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

-2 پیشینه پژوهش

ساختارهای مختلفی بـرای شـاخص گـذاری داده هـای اشـیاء متحرک پیشنهاد شده است. این سـاختارهـا را مـیتـوان در سـه گروه دستهبندی نمود: ساختارهای شاخصگذاری موقعیت جاری اشیاء متحرک، ساختارهای شاخصگذاری موقعیت اشیاء متحرک در آینده و ساختار های شاخصگذاری موقعیت اشیاء متحـرک در گذشته یا خطسیر اشیاء متحرک.[9 ,8] در این مقالـه تاکیـد بـر ساختارهای شاخصگذاری موقعیت جاری اشـیاء متحـرک اسـت. در این حوزه ساختارهای مختلفی ارائه شده است که از آن جمله میتوان به LUGrid[10]، RUM-tree[11] و IMORS[12] اشاره داشت.

در [13] روشی برای بروزرسانی بهینـه شـاخصهـای اشـیاء متحــرک در شــبکه راههــا ارائــه شــده اســت. در ایــن روش داده ساختاری پویا به نام واحد تطبیق وجود دارد که اشیاء متحرک را با الگوهای حرکتی مشابه با هم در یک گروه قرار میدهد و بـرای کاهش بروزرسانی واحد تطبیق حد حرکت اشیاء را براساس یـک

روش پــیشبینــی بــا مشــاهده محــدودیتهــای شــبکه راههــا و رفتارهای ترافیکی تصادفی میگیرد. در [14] یک نـوع سـرویس پیشرفته که میتواند حجم ترافیک سـفرها را بـرای برنامـه ریـزی موثر سفر، پیش بینی نماید، ارائـه شـد. در ایـن روش از سـاختار ترکیبی متشکل از RD-tree برای شاخص گذاری شبکه و جـدول درهم سازی مبتنی بر مسیر برای مدیریت وسایل نقلیـه اسـتفاده شده است.

-3 مفاهیم پایه

در بسیاری از کاربردها نیـاز بـه نگهـداری و شـاخصگـذاری داده های اشیاء متحرک در زمان حال دارند. یکـی از چـالشهـای اصلی این کاربردها وجود عملیات بروزرسانیهای تکـراری و زیـاد است. به ویژه اینکه اشیاء متحرک برای بروزرسانیهای تکـراری در موقعیت خود، نیاز به اسـتفاده از روش هـا و تکنیـک هـایی بـرای بروزرسانی سریع در سیستم های پایگـاه داده هـای زمـانی-مکـانی دارند. روش های شاخصگذاری عادی مشکلات زیادی برای انجـام بروزرســانی بــا کــارایی بــالا دارنــد. IMORS یکــی از روشهــای مناسـب بــرای شـاخصگــذاری موقعیـت جــاری اشـیاء متحــرک است.[12] در این روش علاوه بـر بهبـود روش هـای بروزرسـانی، کارایی روشهای پردازش پرسوجو نیز بهبود یافته است.

شکل :1 داده ساختار روش [12] IMORS

تمرکز روش IMORS برروی نحوه کاهش هزینه بروزرسـانی در شاخص ها اسـت. ایـن روش شـاخص گـذاری دارای دو بخـش ایستا ( که صرف نظـر از بروزرسـانی بیشـتر بـدون تغییـر و ثابـت است.) و پویا (کـه بـه صـورت مسـتقیم بـا سـربار بروزرسـانی در ارتباط است.) میباشد.

این روش سـعی در حـداکثر کـردن بخـش ایسـتا وکمینـه ساختن بخش پویا دارد کـه باعـث کـاهش تعـداد بروزرسـانیهـا خواهد شد. این روش اشیاء متحرک را با استفاده از قطعـه راه هـا

2

شاخص گذاری می کند، با این فرض نزدیک بـه واقعیـت کـه ایـن اشیاء در شبکه ای از راه های از پیش تعریف شده قرار دارند. شکل 1 نمایی کلی از ساختار IMORS را نمایش میدهد که شـامل دو بخشی است که اشاره شد. در بخش اول که همـان بخـش ایسـتا است فقط یک R*-tree برای قطعه راهها ساخته مـیشـود و ایـن قطعه راه ها به کمک برگ های این R*-tree قابل دسترسی اسـت. در بخش دوم و پویا دو ساختمان داده اصلی برای اشیاء متحـرک وجود دارد: (Road Sector Block) و .(Data Block)

در این ساختار R*-tree مشـابه دیگـر R*-tree هـا اسـتفاده می شود، با این تفاوت که به جای نقاط یا چند ضلعی هـا، عناصـر آن قطعه راه ها هستند. هر قطعه راه به یـک بـلاک از اشـاره می کند که شامل شناسه اشیاء متحرک در آن قطعه راه است و با این اشارهگر مـیتـوان اشـیاء را از R*-tree بازیـابی نمـود. بـلاک

داده ای اشیاء متحرک ( ) نیز سـرعت و دیگـر ویژگـی هـای
مرتبط با هر شیء متحرک را ذخیره میکند.
وقتی که یک بروزرسانی در داده های موقعیت اشیاء متحرک
انجام شود، داده های مرتبط بـا مختصـات در و بـروز
رسانی می شـوند و همچنـین خـط ارتبـاط بـین شـیء متحـرک (اشاره گرها) و نیز در صورت لزوم تغییر میکند ولی تغییری در بخش ایسـتا رخ نمـیدهـد و ایـن همـان ایـده کلیـدی روش
IMORS است.

-4 روش پیشنهادی

در روش اصـــلی IMORS تعـــدادی از بلـــوکهـــای داده (DataBlock) که تشکیل دهنده پایگـاه داده هسـتند را بـر روی دیسک فرض کرده است، اما در روش پیشنهادی فرض شده همه داده ها، تـا حـد امکـان بـرای افـزایش سـرعت در حافظـه اصـلی نگهداری می شوند. همچنین برای دسترسـی بـه داده هـا و انجـام پرس وجو شناسه اشیاء مورد نظر، از کاربر گرفتـه شـده و از ایـن شناسه به عنوان شاخص دسترسـی در پایگـاه داده بـه داده هـای شیء متحرک مورد نظر استفاده میشود. به این صورت که کـاربر شناسهای را به سامانه ارسال کرده و این شناسه بـدون تغییـر بـه عنوان شاخص دسترسی استفاده میشود. همچنـین شناسـه وارد شده توسط کاربر توسط یک تـابع Hash بـه شـاخص دسترسـی تبدیل میگردد که در هر دو صورت شـاخص دسترسـی بـا O(1) قابل بازیابی خواهد بود. بـا توجـه بـه نکـات ذکـر شـده در روش پیشــنهادی داده ســاختار IMORS تغییــر یافتــه و درنهایــت الگوریتمهای درج، حذف و بروزرسانی IMORS با انجام تغییراتی

بهبود یافته است که در ادامه هریـک از آنهـا مـورد بررسـی قـرار گرفته است.

-1-4 بهینه سازی داده ساختار IMORS

در داده ساختار اصلی IMORS، یک اشاره گر به وجـود
دارد که با توجه به بررسیها و آزمایشهـای صـورت گرفتـه ایـن حذف گردید و اطلاعات موجود در آن به آخرین سـطح R*-

tree یعنی برگ ها اضافه گردید.
علاوه بر این اشارهگرهای موجود در که به اشاره

داشتند نیز با یک ساختار Vector جایگزین شـدند. ایـن Vector حاوی شناسه اشیاء متحـرک موجـود در اسـت. حـذف ایـن اشارهگرها با توجه به این موضوع که فرض شده شناسه هر شـیء متحرک از کاربر دریافت میگردد، انجام شده است.

بــا توجــه بــه تغییــرات انجــام شــده بــر روی داده ســاختار IMORS، الگوریتمهای درج و بروزرسانی در IMORS نیـز تغییـر داده شد.

-2-4 بهینه سازی درج و حذف

در الگوریتم ارایه شده در روش اصلی IMORS، اشارهگری با عنوان وجـود دارد کـه همـان اشـاره گـر از Leaf بـه Road Sector Block میباشد. در روش پیشنهادی بـا توجـه بـه حـذف Road Sector Block از داده ســاختار، ایــن اشــاره گــر حــذف میگردد. علاوه بر این، با توجه بـه جـایگزینی Vector بـه جـای اشارهگرهای موجود در که به اشاره دارد، دیگر نیازی به اشارهگر bptr نیست و میتوان آن را حذف نمود. این اشاره گر به Data Block موجود در پایگـاه داده اشـاره مـیکنـد. در روش پیشنهادی به جای ذخیره این اشارهگر، شناسه شیء متحـرک در Vector ذخیره میگردد.

در زیر الگوریتم درج در ساختار IMORS ارائه شده است. بـا استفاده از شناسه دریافتی از کاربر امکان حذف یکی از Register ها بر روی پایگاه داده، در الگوریتم زیر به وجود میآید.

Insertion Algorithm(m,R) m: new moving object, R: R*-tree

Begin Algorithm

m.oid← Register MO on DB(m);

bRS ←Search R*-tree(R,m.pos);

bptr ← Register on RSB (bRS,m.oid,m.pos);
Register Block Pointer on DB(m.oid,bptr);
End Insertion Algorithm×
الگوریتم اصلاح شده به صورت زیر خواهد بود:

Insertion Algorithm(m(oid),R) m: new moving object, R: R*-tree

3

Begin Algorithm bleaf ←Search R*-tree and Register on

Leaf(R, m.oid,m.pos); Register Block Pointer on DB(m,bleaf);
End Insertion Algorithm×

الگوریتم حذف نیز مشابه الگوریتم درج میباشـد و تغییـرات فوق در الگوریتم حذف نیز به این نحو انجام شده است.

-3-4 بهینه سازی بروزرسانی

در روش پیشنهادی با توجه بـه حـذف Road Sector Block از داده ساختار، بروزرسانی و بازیابی مختصات Sector قبلی شیء متحرک در یک مرحله انجام میشود و اشارهگـر بـه Leaf حـاوی شیء متحرک بازگردانده می شود. اگر مختصات جدید در Sector قبلـی وجـود نداشــت، بایــد اشـاره گــر bLeaf بروزرســانی شــود. الگوریتم بروزرسانی در ساختار اصلی IMORS به شکل زیر است:

Update Algorithm Input m : moving object with new position, R: R*-tree

Begin Algorithm

Update Position(m.oid, m.position);

bRS ←Get RoadSectorBlock(m.oid);

If ( Is on Road Sector(bRS.Sector,m.position) == NO ) { Remove from Road Sector Block(R , m.oid); bRS ← Search R*-tree( R,m.position); bptr ← Register on

RoadSectorBlock(bRS,m.oid,m.position); Register Block Pointer on DataBlock(m.oid,bptr);
}
End Update Algorithm×
الگوریتم بروزرسانی اصلاح شده به صورت زیر خواهد بود:

Update Algorithm Input m : moving object with new position, R: R*-tree

Begin Algorithm

bLeaf ←Update Position and Get Leaf Block(m.oid,

m.position);

If ( Is on Leaf (bLeaf.Sector,m.position) == NO ) { Remove from Leaf Block(R , m.oid); bLeaf ← Search R*-tree and Register on

Leaf(R,m.position); Register Block Pointer on DataBlock(m,bleaf);

}

End Update Algorithm

-5 پیاده سازی و ارزیابی روش پیشنهادی

در این بخش ارزیابی نتایج حاصل از آزمایشهای انجام شده برروی روش پیشنهادی ارائه شده است. آزمایشهای فوق بر روی سیسـتمی بــا پردازنـده اینتــل G2010 2.80 GHz، 4096 MB حافظه اصلی و با سیستم عامل ویندوز 7 انجام شده اسـت. زبـان برنامه نویسی اسـتفاده شـده بـرای آزمـایشهـا C++ مـیباشـد.

همچنین مجموعه داده موردنظر به صورت تصـادفی تولیـد شـده است. برای بررسی و آزمایش روشهای پیشنهادی و ارزیابی زمان اجرای هر روش پیشنهادی، در ایـن مجموعـه داده تعـداد اشـیاء متحرک ایجاد شده به ترتیب از 10شیء متحرک شـروع شـده و در نهایت بـه 1000 شـیء متحـرک افـزایش یافـت کـه در هـر آزمایش حرکت اشیاء دارای سرعتهای متفاوتی است. همچنـین تعداد Road Sector های مرتبط ایجاد شده با خطسیر این اشـیاء نیز به ترتیب از 100 سکتور شروع شده و در نهایت بـه 10000 سکتور رسید.

نتایج حاصل از آزمایش چهـار روش بروزرسـانی در IMORS در شکل های 1تا 4 ارائه شده است. در این آزمایش ها سرعت هـر شیء به طور متوسط نصف طول یک Road Sector است و اشـیاء به صورت تصادفی توزیع شدهاند. در این نمودارها RS بـه معنـای این است که از گره برگ اشاره گری به Road Sector وجـود دارد و Data به معنای این است که اشاره گـر بـه Data Block وجـود دارد. ID به معنای استفاده از شناسه به عنوان شاخص دسترسـی و DB به معنای عدم اسـتفاده از آن و تولیـد شـاخص دسترسـی توسط پایگاه داده است. به عبارت دیگر RSDB همان IMORS و DataID بهینهترین حالت ممکـن اسـت. شـکل 5 نیـز میـانگین زمانی هر چهار روش در کنار هم نمایش میدهد.

شکل :1 روش RSID

شکل :2 روش DataID

4

شکل :3 روش RSDB شکل :6 میانگین زمانی1000 شیء با سرعت متوسط یک برابر طول یک Road Sector و تعداد سکتورهای متغیر

شکل 7 نتایج بروزرسانی در IMORS را با 10000 سـکتور بـه طور ثابت و تعداد اشیاء متغییر نمایش میدهـد. در ایـن قسـمت سرعت هر شیء به طور متوسط 5 برابر طـول یـک Road Sector در نظر گرفته شده است.

شکل :4 روش DataDB

شکل :7 میانگین زمانی10000 سکتور ثابت و تعداد اشیاء متغیر با سرعت متوسط 5 برابر طول یک Road Sector

شکل :5 میانگین زمانی 4 روش پیشنهادی

همانطور که در شکلهای بالا مشخص است، افـزایش تعـداد اشیاء متحرک تاثیری در افزایش زمان بروزرسانیها ندارد، ولی بـا افزایش تعداد سکتورها، زمان بروزرسانیها نیز افزایش مییابد.

با افزایش سرعت اشیاء متحـرک تعـداد بروزرسـانی هـا و در نتیجه زمان نیز افزایش خواهد یافت. شکل 6 نتایج بروزرسانی در IMORS نمایش میدهد. در این نمودار تعداد اشیاء متحـرک بـه طور ثابت برابر با 1000 بوده و تعداد سکتورها متغییـر اسـت. در این قسمت سرعت هر شیء به طور متوسط یک برابر طـول یـک Road Sector در نظر گرفته شده است.

اگر حرکت اشیاء فقط به Road Sector خـود محـدود باشـند و ازآن خارج نشوند، در روشهایی که از شناسه به عنـوان شـاخص دسترسی استفاده نمودهانـد، زمـان بروزرسـانی نزدیـک بـه صـفر خواهد بود و در روشهایی که تولیـد شـاخص دسترسـی توسـط پایگاه داده انجام شده است، زمان بروزرسانی نیز بالا است. شـکل 8 نتایج بروزرسانی را در این حالت نمایش میدهد.

5

شکل :8 میانگین زمانی1000 شیء که حرکت آنها محدود به Road Sector خود است و تعداد سکتورهای متغیر

همانگونه که در بخش 2-4 اشاره شد، عملیـات درج نیـز در روش پیشنهادی بهبود یافته است. در شکل 9 مقایسه نتـایج درج در ســه روش IMORS، درج بهینــه شــده و همچنــین درج بــا استفاده از شناسـه وارد شـده توسـط کـاربر و اسـتفاده از آن بـه عنوان شاخص دسترسـی و در نهایـت اسـتفاده از روش