ایران سرفراز- نرم افزار وپروژهای دانشجویی


نرم افزار وپروژهای دانشجویی

پیش بینی اطلاعات جهت کش کردن در تراکنشهای سیار

152

پیش بینی اطلاعات جهت کش کردن در تراکنشهای سیار

 

چکیده

پیشرفتهای سریع در ارتباطات سلولی، شبکههای بیسیم و سرویسهای ماهوارهای، منجر به ظهور سیستمهای

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

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

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

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

دارد، ارائه شده است تا در زمان قطع ارتباط، دادههای مورد نیاز کاربر، تا حد ممکن در دسترس باشند و از به تعویق افتادن

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

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

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

Microsoft SQL مد نظر نیست. در انتها شبیه سازی این روش با یکی از روشهای موجود با استفاده از بانک اطلاعاتی

انجام شده است که تشابه نتایج روش ارائه شده را نشان میدهد. Server

کلید واژه

متحرک، ایستگاههای پشتیبانی متحرک، تراکنش، کشکردن، عامل سیار.

-1 مقدمه

در سیستمهای بانک اطلاعاتی متحرک، کش کردن اطلاعات می-

تواند نقش سازندهای را در کاهش ارتباطات میان سرویس دهنده-

ها و سرویس گیرندهها و همچنین افزایش خودمختاری واحدهای

جهت پذیرش محلی تراکنشها، ایفا کند. در یک (MU) متحرک

محیط پردازشی متحرک، دادهها بر روی ایستگاههای پشتیبانی

نگهداری میشوند و کنترل اصلی دادهها و انجام (MSS) متحرک

ها بررسی شده و در MSS هر نوع عملیات بر روی دادهها توسط

5,7,10 ]. کش - صورت تأیید در بانک اطلاعاتی ثبت میشود[ 12

کردن اقلام دادهای که به طور مکرر و به میزان زیاد مورد استفاده

واحدهای متحرک قرار میگیرند، میتواند روشی مؤثر در کاهش

ها و واحدهای متحرک و MSS هزینههای ارتباطی میان

.[ همچنین استفاده بهتر از منابع واحدهای متحرک باشد[ 18

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

ها است، کش کنند. با MSS که مشابه بانک اطلاعاتی موجود در

این کار دسترسی به دادههای مورد نیاز در واحد متحرک سریعتر

صورت گرفته و تعداد تقاضاها برای دریافت داده از شبکه کاهش

مییابد.

جهت اجرای تراکنش در بانکهای اطلاعات متحرک، الگوریتم-

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

حرکت و قطع ارتباط واحدهای متحرک را مورد بحث قراردادهاند

و روشی را برای اجرای صحیح تراکنش مطرح نمودهاند. هر یک از

این الگوریتمها، تکنیکهایی را جهت کنترل اجرای تراکنش

متحرک ارائه دادهاند. در مدل کانگورو، تراکنش از واحد متحرک

انتقال یافته و بر روی شبکه ثابت و سرویس دهندهها MSS به

اجرا شده و نتیجه برای واحد متحرک ارسال میشود؛ و هیچگونه

.[ دادهای در واحد متحرک جهت اجرای تراکنش کش نمیشود[ 9

با دریافت تقاضای واحد MSS ،PRO-MOTION در مدل

یی را بر اساس دادههای تقاضا شده ایجاد compact ، متحرک

کرده و به واحد متحرک ارسال میکند. واحد متحرک، تراکنش

اجرا کرده و compact مورد نظر را بر اساس اطلاعات موجود در

نتایج را جهت تأیید نهایی به سرویس دهنده ارسال میکند و در

واقع فقط دادههایی که هم اکنون مورد نیاز است کش می-

نیز، تراکنش از واحدهای TOGGLE شوند[ 6]. در مدل

متحرک به سرویس دهنده منتقل شده و اجرا میشود. این مدل

از بانکهای اطلاعاتی چندگانه پشتیبانی کرده و با حرکت واحد

دیگر اجرای تراکنش متحرک MSS به MSS متحرک از یک

جدید منتقل میشود[ 14 ]. در مدل خوشهای ، MSS نیز به

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

روی سرویس دهندههای متصل توزیع میشوند. دادههای درون

هر خوشه با توجه به مفهوم یا مکان دادهها با هم مرتبط می-

باشند. واحد متحرک با اتصال به هر میزبان، در صورت نیاز به

دادههای آن، خوشه مربوطه را به درون خود منتقل کرده و در

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

کند[ 5]. در مدل پردازش تراکنش متحرک به کمک کش، داده-

های مورد نیاز واحدهای متحرک توسط لیستهایی بر روی آنها

کش میشود (داده ها میتوانند به صورت اشتراکی بین واحدهای

متحرک منتشر شوند). هر داده توسط یک مقدار زمانی بر چسب

گذاری میشود و سرویس دهندهها به کمک این برچسبهای

زمانی صحت و اعتبار دادههای کش شده را در هنگام اجرای

.[ تراکنش کنترل میکنند[ 18

در مدلهایی که برای بانکهای اطلاعات متحرک ارائه شده است

اکثرًا به کنترل اجرای تراکنش متحرک توجه شده[ 8,9,14 ] و

در صورت کش کردن دادهها نیز فقط دادههایی کش میشوند که

هم اکنون مورد نیاز واحد متحرک میباشد[ 6,15,18 ]. در

الگوریتمهای مطرح شده، روشهایی جهت کنترل دادههای کش

شده ارائه شده است و این روشها بیشتر به بررسی صحت داده

کش شده میپردازند؛ در واقع دادههایی کش میشوند که هم

اکنون مورد نیاز واحد متحرک است. در حالت واقعی معمو ً لا

کاربران کامپیوتر، در یک مقطع زمانی خاص، با دادههای مشخص

و در حیطه یک زمینه کاری/مفهومی، سروکار دارند. این موضوع

کمک میکند تا با توجه به دانستههای گذشته، یعنی عملیاتها و

تقاضاهایی که در گذشته توسط یک کاربر خاص و یا سایر

کاربران استفاده شدهاند، بتوان روند کاری یک کاربر خاص را تا

حدی پیش بینی نمود و به محدودهی دادههایی که مورد نیاز وی

میباشند پی برد. در حقیقت این پیش بینی جهت کش کردن

زود هنگام دادههایی است که احتما ً لا در آیندهای نزدیک توسط

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

در سیستمهای پیشبینی کننده و پیشنهاد کننده موجود، معمو ً لا

ایجاد پیشبینیها و پیشنهادات را بر اساس یک سیستم خاص

انجام میدهند؛ به این معنی که سیستمی خاص را درنظر گرفته

و با توجه به دادههایی که این سیستم در طول زمان تولید می-

کند و همچنین با توجه به نحوه استفاده کاربران از دادههای این

سیستم، اطلاعاتی آماری را استخراج کرده و این اطلاعات را داده-

نموده و به نتایج مورد انتظار دست می- (Data Mining) کاوی

یابند. تفاوت کار ارائه شده در این مقاله با سایر کارها این است که

سعی شده است سیستم خاصی مد نظر نباشد و فقط با توجه به

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

پذیرد؛ همچنین انجام پیشبینی در بانکهای اطلاعات متحرک

1 5 4

تاکنون در مدلهای ارائه شده مطرح نشده است.

-2 معماری بانکهای اطلاعات متحرک

در معماری بانکهای اطلاعاتی متحرک(شکل ١)، هر واحد

متحرک جهت استفاده از دادههای موجود در بانک اطلاعاتی، می-

ها متصل شده و تقاضاهای خود را به آنها MSS بایست به یکی از

داده و اطلاعات مورد نیاز خود را از آنها دریافت نماید؛ البته

ارسال تقاضا و دریافت داده توسط واحد متحرک، و از طریق

شبکه بیسیم انجام میشود

10,7,5 ]. هر تقاضا در بانکهای اطلاعاتی، در قالب یک ]

تراکنش ارائه میشود. هر تراکنش شامل چندین عملیات میباشد

که بر روی دادههای بانک اطلاعاتی اعمال میشوند. بانک

اطلاعاتی هر تراکنش را به عنوان یک واحد در نظر میگیرد؛ به

این معنا که تمام عملیاتهای تراکنش با موفقیت به پایان می-

رسند و تراکنش پذیرفته میشود و در صورتی که اجرای حتی

یکی از عملیاتهای تراکنش دچار اشکال شود، تمامی عملیات-

های تراکنش لغو خواهند شد. مدلهای ارائه شده برای بانکهای

اطلاعات متحرک سعی در کنترل اجرای درست تراکنشهای ارائه

شده توسط کاربران دارند.

اجرای یک تراکنش میتواند به این صورت باشد: هنگامی که

واحد متحرکی تقاضای دادهای میکند در صورتی که این داده در

دسترس باشد، میتواند آن را مورد استفاده قرار داده و نتایج را

جهت تأیید به سرویس دهنده ارسال نماید. در صورتی که دادهی

مورد نیاز در دسترس نباشد و یا بخشی از آن موجود باشد، واحد

متحرک تقاضای دادههای مورد نیاز خود را برای سرویس دهنده

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

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

یکی از مشکلات بانکهای اطلاعات متحرک، قطع شدن اتصال

ها میباشد. این قطع ارتباط موجب MSS واحدهای متحرک از

میشود که اجرای تراکنش دچار مشکل شده و لغو تراکنش را

موجب شود.

در بانکهای اطلاعاتی متحرک تراکنشها معمو ً لا به دو صورت

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

ها منتقل شده و پس از اجرای کامل نتایج ایجاد شده به MSS

واحد متحرک ارسال میشوند؛ که این موجب زیاد شدن حجم

ها میشود. در حالت دیگر دادههای مورد نیاز MSS کاری

تراکنش به واحد متحرک منتقل شده و تراکنش در واحد متحرک

منتقل می- MSS اجرا شده و نتایج حاصله جهت تأیید نهایی به

شوند و در صورت تأیید اجرای تراکنش، دادهها در بانک اطلاعاتی

اصلی ثبت میشوند؛ که این حالت موجب کاهش بار کاری

ها شده و استفادهی بهینه از امکانات واحد متحرک را در MSS

پی خواهد داشت. در مدلهای ارائه شدهای که تراکنش را به این

صورت اجرا میکنند، فقط دادههایی در واحد متحرک کش می-

شوند که برای اجرای تراکنش جاری مورد نیاز میباشند و پس از

انجام تراکنش دادههای استفاده شده کاربردی ندارند.

-3 اصول کار در روش پیشنهادی

ها، توزیع شده است. MSS در این معماری بانک اطلاعاتی برروی

البته هر یک از واحدهای متحرک نیز بر روی خود ساختاری

مشابه بانک اطلاعات اصلی را دارند که جهت کش کردن اطلاعات

MSS و پذیرش محلی تراکنشها مورد استفاده قرار میگیرد. هر

مسئول مدیریت ارتباط بر قرار شده با واحدهای متحرک میباشد.

ها مسئول بررسی صحت تراکنشهای اجرا شده MSS همچنین

و ثبت نتایج تراکنشها در بانک اطلاعاتی میباشند. در هنگام

مسئولیت ایجاد MSS ،MSS برقراری ارتباط واحد متحرک با

یک عامل جدید جهت کنترل کش، اجرای تراکنشها و مدیریت

تحرک واحد متحرک را بر عهده دارد(شکل ٢). در واقع برای هر

واحد متحرک، یک عامل ایجاد میشود؛ و وجود هر عامل درون

MSS نشان دهنده واحد متحرکی میباشد که به آن MSS

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

واحد متحرک میباشد، به این معنی که با حرکت واحد متحرک

دیگر، کلیه اطلاعات عامل مربوط به این MSS به MSS از یک

MSS جدید منتقل میشوند و MSS مبدأ به MSS متحرک از

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

میگیرد.

MSS1 MSS2

MSS3

Fixed Network

Wireless Network

MU2

MU1

شکل 1: معماری بانک اطلاعاتی

[5,7,10- متحرک[ 12

1 5 5

هر عامل، نگهدارنده نمایهای از اطلاعاتی است که جهت انجام

پیشبینی دادههایی که باید کش شوند مورد استفاده قرار می-

گیرد. عاملها میتوانند اطلاعات خود را در اختیار سایر عاملها

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

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

عامل و با توجه به دادههایی که واحد متحرک تاکنون مورد

استفاده قرار داده است ایجاد و تکمیل شده و خود عامل نیز

تصمیم گیری جهت حذف این دادهها را انجام میدهد. عامل می-

بایست با دریافت هر تقاضا از واحد متحرک به آن پاسخ داده و

اطلاعات مربوط به تکمیل نمایه را در نمایه ثبت کند. سپس،

عامل سعی در پیشبینی اطلاعات مورد نیاز واحد متحرک در

آینده نماید و پس از تکمیل پیشبینی، اطلاعات به دست آمده را

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

مورد بررسی قرار گرفتهاند:

١- مشخص کردن همسایههای واحد متحرک.

٢- یافتن دسته اطلاعاتی مربوط به دادههایی که کاربر

بیشترین علاقه را به آنها دارا میباشد و سپس گزینش

دادههایی که دارای رابطهای منطقی با اطلاعات استفاده

شده هستند.

چگونگی انجام این دو مرحله در ادامه شرح داده میشوند.

-1-3 عملیاتهای جابجایی مکان متحرک

درصورتی که ،MSS هر واحد متحرک در هنگام برقرار ارتباط با

عامل MSS ، ارتباط برقرار میکند MSS اولین باری باشد که با

جدیدی را برای این متحرک ایجاد مینماید و عامل را آماده

هنگام ایجاد MSS . کنترل و مدیریت واحد متحرک میکند

عامل برای اینکه واحد متحرک عامل خود را شناسایی نماید، به

هر عامل شمارهای منحصربهفرد را اختصاص میدهد؛ این شماره

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

زیر ایجاد میشود:

Agent_ID =MSS_Number + (Count_Agents+1)

شماره سرویس دهنده میباشد، زیرا MSS_Number ، در اینجا

به هر سرویس دهنده شمارهای واحد اختصاص مییابد.

را مشخص میکند MSS تعداد عاملهای Count_Agents

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

مشخص شدن شماره عامل، این شماره به واحد متحرک ارسال

میشود و واحد متحرک با توجه به این شماره قادر به شناسایی

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

تقاضا به عامل مربوطه داده شده و عامل جهت ،MSS برای

ارسال اطلاعات به واحد متحرک تصمیمگیری نموده و با هر تقاضا

نمایهی خود را جهت تصمیمگیریهای بهتر کامل مینماید.

قطع شود، پس از MSS در صورتی که ارتباط واحد متحرک با

قبلی و MSS برقراری ارتباط، واحد متحرک ابتدا میبایست

عامل خود را شناسایی نماید. برای این کار با ارسال شماره

در صورتی که متحرک از محدوده ،MSS شناسایی عامل خود به

شماره را شناخته و ارتباط MSS ، قبلی خارج نشده باشد MSS

ناشناخته MSS برقرار میشود. در غیر اینصورت شماره برای

جدید وظیفه دارد از طریق شماره شناسایی، MSS است و

پیشین را مشخص کرده و تقاضایی را مبنی بر دریافت MSS

MSS . پیشین ارسال مینماید MSS اطلاعات آن عامل به

جدید با دریافت اطلاعات عامل، شماره شناسایی عامل را بر اساس

شماره خود و تعداد عاملهای خود تغییر داده و این شماره را

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

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

-2-3 ساختار نمایه

با توجه به مطالب گفته شده در قبل، هر عامل دارای نمایهای

است که در برگیرنده اطلاعاتی جهت انجام پیشبینی دادههای

مورد نیاز در آینده میباشد. اطلاعات این نمایه با توجه به داده-

های مورد استفاده در گذشته ایجاد میشوند. هر نمایه دارای

ساختاری به صورت جدول زیر میباشد:

A جدول 1: ساختار نمایهی مربوط به عامل

ا Agent(A)

TC کد جدول

RC کد رکورد

TR زمان آخرین ارسال

WR وزن تقاضا

WU وزن استفاده

Vote رأی

MSS

Profile1

Agent1

Profile2

Agent2

Profile3

Agent3

Profilen

Agentn

MSS شکل 2: عاملهای درون یک

1 5 6

بطوریکه:

واحد متحرکی که پیشبینی برای آن انجام میشود را : A

مشخص مینماید.

در اینجا برای هر جدول در ساختار بانک : (TC) کد جدول

نشان دهنده TC اطلاعاتی یک شناسه در نظر گرفته میشود؛ و

جدولی است که رکوردهای آن مورد استفاده قرار گرفتهاند.

با توجه به تعاریف بانکهای اطلاعاتی، هر : (RC) کد رکورد

رکورد(یا نمونه موجودیت) میبایست دارای شناسهای واحد به نام

نشان دهنده شناسهی رکوردی است که RC کلید باشد. در اینجا

مورد استفاده قرار گرفته است. TC از جدول

آخرین زمانی است که عامل رکورد : (TR) زمان آخرین ارسال

به واحد متحرک ارسال نموده است. این زمان TC را از جدول RC

برای عامل مشخص میکند که کدامیک از رکوردها جدیدًا مورد

استفاده قرار گرفتهاند و یا جدیدًا مورد استفاده قرار نگرفتهاند؛ و

عامل رکوردهایی که با زمان جاری، دارای تفاوتی معین باشند را

از درون نمایه حذف میکند. زیرا این رکوردها احتما ً لا دیگر مورد

نبوده و مورد استفاده قرار نمیگیرند. A علاقه واحد متحرک

نشان دهنده تعداد دفعاتی است که واحد : (WR) وزن تقاضا

احتیاج TC از جدول RC متحرک در تقاضاهای خود به رکورد

داشته و آن را درخواست نموده است.

نشان دهنده تعداد دفعاتی است که واحد : (WU) وزن استفاده

استفاده نموده و این رکورد را TC در جدول RC متحرک از رکورد

در این است که WU و WR تغییر داده/ بروز کرده است. تفاوت

ممکن است یک کاربر، رکوردی را تقاضا نماید ولی آن را تغییر

ندهد.

عامل با داشتن اطلاعت نمایه خود، میتواند : (Vote) رأی

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

((WU) و وزن استفاده (WR) وزن تقاضا ،(TR) توجه به زمان ارسال

مشخص کند. برای اینکار به هر یک از مقادیر فوق ضریبی با

عنوان ضریب اهمیت به صورت زیر اختصاص میدهیم:

۰,۶ * (TR) - زمان ارسال

۰,۲۵ * (WR) - وزن تقاضا

۰,۱۵ * (WU) - وزن استفاده

ام نمایه به صورت زیر i مربوط به رکورد Vote حال مقدار

محاسبه میشود:

Votei = (TR *0.6) + (WR *0.25) + (WU *0.15) (۱)

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

نمایه تغییر داده میشوند؛ و مقدار (WU،WR،TR) از اطلاعات

مربوط به هر سطر از نمایه با تغییرات آن سطر مجددًا Vote

میتوان نظر/علاقه کاربر(یا واحد Vote بدست میآیند. از مقدار

فهمید. با ایجاد شدن عامل و RC متحرک) را نسبت به رکورد

عامل با دریافت هر تقاضا از واحد ،A همچنین نمایهی مربوط به

متحرک، نمایه را تکمیل کرده و همچنین سعی در مشخص

کردن محدوده کاری واحد متحرک میکند.

-4 انجام پیشبینی

همانگونه قب ً لا گفته شد، در اینجا دو مرحله جهت پیشبینی انجام

میشوند. چگونگی انجام این دو مرحله و الگوریتم پیشبینی در

ادامه شرح داده شدهاند.

-1-4 گزینش همسایهها

در اینجا همسایه به معنای واحدهای متحرک نزدیک از نظر

فیزیکی و مکانی نیست؛ بلکه همسایه بودن و نزدیک بودن از نظر

اطلاعات و دادههایی است که متحرک مورد نظر و سایر متحرک-

ها به صورت مشابه استفاده کردهاند. همانطور که قب ً لا گفته شد،

یی که باشند میتوانند اطلاعات نمایههای MSS عاملها در هر

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

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

نزدیکترین همسایهها را انتخاب کرد. چون ممکن است تعداد

عامل را به صورت تصادفی از بین N عاملها زیاد باشد، میتوان

یی که باشند) انتخاب نمود و عمل MSS تمامی عاملها(در هر

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

نمایه میتواند با استفاده از یک تابع فاصله اقلیدسی(البته تغییر

داده شده)، که بر روی رکوردهای نمایه کار میکند، صورت گیرد.

میباشد: j و کاربر A تشابه بین کاربر فعال euclidean(A,j)

) ۲ ( Σ=

= −

k

i

euclidean A j TRA i VoteA i Vote j i

1

2

( , ) , *( , , )

بطوریکه:

و A مشخص کننده تعداد رکوردهای مشابهی است که عامل : k

استفاده نمودهاند. j

را برای واحد متحرک i رکورد A زمانی است که عامل : TRA,i

ارسال نموده است.

i رأیی است که با توجه به میزان استفاده از رکورد : VoteA,i

برای این رکورد مشخص شده است. A توسط عامل

میباشد، که در O(NK) عامل N زمان اجرای این معادله برای

نشان دهنده kj میباشد که K=Average(k1,k2,…,kn) اینجا

است. j و عامل A تعداد رکوردهای مشابه عامل

1 5 7

معمو ً لا فاصله بدست آمده بزرگتر یا مساوی صفر است. عاملهایی

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

عامل را که دارای کمترین فاصله M ، عامل انتخاب شده N بین

هستند انتخاب نمود و جهت تهیه پیشبینی مورد استفاده قرار

داد.

-2-4 مشخص کردن دستههای اطلاعاتی

در این روش میتوان طبقهبندیی را برای اطلاعات در نظر گرفت.

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

برای سیستم تعریف شود. از این اطلاعات طبقه بندی شده برای

کشف دستههای اطلاعاتی که واحد متحرک در حال کار کردن با

آنها میباشد، استفاده میشود. برای توضیح بهتر مفهوم این

طبقهبندی، مثالی در ادامه آورده شده و سعی میشود که طبقه

بندی اطلاعات با یک مثال تشریح شود. بعنوان نمونه بانک

اطلاعاتی زیر را در نظر بگیرید:

D = {T1 , T2 , … , Tn} ا

ها نشان دهنده جداول موجود در این Ti ،D در بانک اطلاعاتی

بانک اطلاعاتی میباشند. فرض کنید که این بانک اطلاعاتی

مربوط به یک سیستم کتابخانه است. اطلاعات این سیستم به

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

از اطلاعات جانبی سیستم کتابخانه صرف نظر شده است):

اعضاء : C1

کارکنان : C2

ٌ کتب : C3

هر یک از این دستهها نیز خود به دستههای کوچکتری به صورت

زیر تقسیم میشوند:

اعضاء دانشجو : C11

اعضاء هیأت علمی : C12

اعضاء کارمند : C13

کارکنان رسمی : C21

کارکنان قراردادی : C22

کارکنان کارآموز : C23

کتبکامپیوتر : C31

کتب ریاضی : C32

کتب شیمی : C33

کتب فیزیک : C34

کتب عمران : C35

...

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

کامپیوتر هم به دو دسته زیر تقسیم شوند:

کتب کامپیوتر زبان فارسی : C311

کتب کامپیوتر زبان انگلیسی : C312

افراز اطلاعات را میتوان تا هر سطح که مورد نیاز سیستم و

کاربران آن باشد انجام داد. در واقع هر چه در افراز به سمت پائین

میرویم، به اطلاعات دقیقتری میرسیم. میتوان این دستهبندی-

ها را به صورت زیر که سلسله مراتب/طبقهبندی اطلاعات را نیز

.( مشخص میکند نشان داد(شکل ٣

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

تعریف این دستهها را با تعیین اطلاعات زیر انجام داد:

جدول 2. ساختار مورد نیاز برای تعریف دستههای اطلاعاتی

Category_Name . مشخص کننده نام دسته میباشد

مشخص کننده دسته والد می باشد (اولین

سطح بدون والد است).

Parent_Category

مشخص کننده مجموعه جداولی می باشد که

در آن دسته قرار دارند (اولین سطح تمامی

جداول بانک اطلاعاتی را شامل میشود).

Tables

مشخص کننده شرایط جدا کننده اطلاعات

آن دسته از سایر اطلاعات موجود در جداول

میشود(برای مشخص کردن شرایط از قواعد

استفاده می - SQL مربوط به دستورات

.((Select در دستور where شود(بخش

Conditions

با توجه به مثال فوق فرض میشود، اطلاعات مربوط به اعضاء در

مشخص کننده MemberType قرار دارند و فیلد T جدول 1

فیلد ،T نوع عضویت باشد، همچنین اطلاعات کتب در جدول 3

زبان چاپ شده باشد، LType نوع کتاب و فیلد BookType

جدول ٣ و شکل ۴ نشان دهنده ساختار تعریف شده برای این

اطلاعات میباشند:

C

C11 C12

C1

C2

C21 C22 C23 C3

C31 C32 C33

C311 C312

شکل 3: ساختار درختی اطلاعات طبقهبندی شدهی مثال فوق

1 5 8

جدول 3: ساختار مورد نیاز برای تعریف دستههای اطلاعاتی

پس از مشخص شدن طبقهبندی اطلاعات و دستههای اطلاعاتی،

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

میکند، میتوان پیشبینی دقیقتری را در مورد اطلاعاتی که

متحرک در آینده قصد استفاده از آنها را دارد انجام داد.

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

که مورد استفاده واحد متحرک قرار گرفته است، با استفاده از

ساختاری که معرفی شد(جدول ٢)، مشخص میکنیم که این

رکرود از کدامین دسته و طبقه میباشد؛ برای انجام اینکار از

روش بالا به پائین استفاده میکنیم؛ یعنی از بالاترین سطح،

رکورد و جدول را بررسی میکنیم و به سطوح پائینتر میرویم.

بعنوان نمونه(با توجه به شکل ۴)، فرض کنید رکورد انتخاب شده

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

شروع میکنیم. رکورد مورد نظر در این سطح C منظور از سطح

را (C فرزندان ) C یافت میشود، بنابراین تمامی سطوح بعدی

موجود نیست ولی C و 2 C بررسی میکنیم. این رکورد در دسته 1

C یافت میشود. بنابراین تمامی سطوح بعدی 3 C در دسته 3

یافت C را بررسی میکنیم. این رکورد در دسته 31 (C (فرزندان 3

بررسی میشوند و C میشود. به همین ترتیب سطوح بعدی 31

یافت میشود. این دسته نیز دارای C این رکورد در دسته 312

سطوح دیگری نیست، بنابراین دسته اطلاعاتی که این رکورد از

میباشد. C آن مورد استفاده قرار گرفته، 312

-3-4 الگوریتم پیشبینی

انجام پیشبینی هنگامی صورت میگیرد که واحد متحرک

تقاضایی را ارائه نماید و اطلاعات مورد نیاز این تقاضا در واحد

متحرک موجود نباشد. در این صورت واحد متحرک برای به دست

مربوطه ارسال MSS آوردن اطلاعات مورد نیاز خود، تقاضا را به

وظیفه دارد علاوه MSS کرده و در این هنگام عامل موجود در

بر اطلاعات مورد نیاز واحد متحرک اطلاعات دیگری را نیز پیش-

بینی نموده و به واحد متحرک ارسال نماید.

جهت پیشبینی میتوان:

و شماره (TC) - با توجه به اطلاعات نمایه، شماره جدول

است را Vote مربوط به سطری که دارای بیشترین (RC) رکورد

به دست آورد.

میبایست دسته اطلاعاتی این RC و TC - با مشخص شدن

رکورد را مشخص کرد. پس از مشخص شدن دسته اطلاعاتی،

رکوردهایی را که از این دسته تاکنون توسط واحد متحرک

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

- پس از مشخص شدن طبقه اطلاعاتی، میبایست نزدیکترین

همسایهها را به صورتی که در بالا ذکر شد مشخص کنیم.

- حال رکوردهایی را از دسته اطلاعاتی مشخص شده، به واحد

متحرک ارسال میکنیم که توسط تعداد بیشتری از نزدیکترین

همسایهها مورد استفاده قرار گرفتهاند و واحد متحرک آنها را

تاکنون استفاده نکرده است. اولویت ارسال را هم میتوان به

رکوردهایی تخصیص داد که توسط تعداد بیشتری از همسایهها

مورد استفاده قرار گرفتهاند.

انتخاب شده، میتوان Vote پس از اتمام عملیات مربوط به اولین

بعدی که دارای بیشترین مقدار است انتخاب کرد و Vote

ها Vote الگوریتم را برای آن انجام داد. میتوان تعداد مشخصی از

هایی که مقدارشان از حد معینی بیشتر است را Vote و یا فقط

مورد بررسی قرار داد.

در زیر(شکل ۵) مراحل کلی عملیات پیشبینی نشان داده شده

Tables Conditions Parent_

Category

Category_

# Name

{ALL records in all

1 C - {All} tables}

2 C1 C {T1} {ALL records in T1}

3 C3 C {T3} {ALL records in T3}

4 C11 C1 {T1} {MemberType=' {'دانشجو

{MemberType=' هیأت

{'علمی

5 C12 C1 {T1}

6 C31 C3 {T3} {BookType=' {'کامپیوتر

7 C33 C3 {T3} {BookType=' {'شیمی

8 C311 C31 {T3} {LType=' {'فارسی

9 C312 C31 {T3} {LType=' {'انگلیسی

Name=C Parent=nil

Tables={T1,T2,…,Tn}

C={ALL records in all tables}

Name=C1 Parent=C

Tables={T1}

C={ALL records in T1}

Name=C3 Parent=C

Tables={T3}

C={ALL records in T3}

Name=C11 Parent=C1

Tables={T1}

C={MemberType=' {'دانشجو

Name=C12 Parent=C1

Tables={T1}

C={MemberType=' {'هیأت علمی

Name=C31 Parent=C3

Tables={T3}

C={BookType=' {'کامپیوتر

Name=C33 Parent=C3

Tables={T3}

C={BookType=' {'شیمی

Name=C311 Parent=C31

Tables={T3}

C={LType=' {'فارسی

Name=C312 Parent=C31

Tables={T3}

C={LType=' {'انگلیسی

شکل 4: ساختار درختی ایجاد شده برای برخی از دستههای اطلاعاتی

٨ ۶􀰮 جان آ 􀣌􀦘 لا􀭃􀰔 ی کا 􀨉 ند􀩀􀥟 س 􀦿ا􀶢􀡶􀣡􀨯 ن 􀲻􀱱 او

1 5 9

است.

-5 آزمایشات انجام شده

جهت بررسی روش ارائه شده، آزمایشاتی بر روی دادههای یک

سیستم کتابخانه که دارای تعداد ١١٠ عضو و تعداد ١۶٨٢ جلد

کتاب بوده است، انجام گردید که نتایج آن در ادامه آورده شده

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

صورت C#.NET و زبان برنامه نویسی SQL Server 2005

گرفته است. در این سیستم، اطلاعات کتابها به تعدادی دستهی

اطلاعاتی تقسیم بندی شده است و هر یک از کاربران میتوانند

کتابهای مختلفی از این دستههای اطلاعاتی را انتخاب کنند؛

این انتخاب میتواند به صورت تکراری هم انجام شود. به این

معنی که هر عضو میتواند کتابی را چندین بار انتخاب نماید.

در دو آزمایش اول رکوردهایی که کاربر در آینده نیاز دارد به

صورت تصادفی انتخاب شدهاند(در صورتی که اطلاعات توسط

انسان و هدفمندتر انتخاب شوند، قویًا به نتایج بهتری خواهیم

رسید). در الگوریتم اجرا شده برای هر آزمایش، با ارائه هر تقاضا

توسط کاربر، نمایه جهت اطمینان از وجود یا عدم وجود اطلاعات

تقاضا شده بررسی میشود؛ در صورت وجود اطلاعات در نمایه،

رکورد مرتبط، در نمایه بروزرسانی میشود و در صورت عدم وجود

تقاضا در نمایه، اطلاعات مورد تقاضا از اطلاعات اصلی انتخاب

شده و به کاربر تحویل میشود، سپس سیستم پیشبینی خود را

انجام داده و تعدادی از رکوردهای پیشبینی شده را برای کاربر

ارسال میکند. در آزمایش سوم روش پیشنهادی و روش خوشه

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

مدل خوشهای دادهها در قالب ١۵ خوشه، خوشه بندی شدهاند.

این خوشهها دارای اطلاعات تکراری میباشند. به این معنی که

یک داده خاص ممکن است در چندین خوشه تکرار شده باشد. در

نتایج به دست آمده نسبت برخورد تقاضاها یعنی مواردی که

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

است. در ادامه اطلاعات مربوط به هر یک از آزمایشها آورده شده

است.

: -1-5 آزمایش ۱

تعداد کاربران : ۵ کاربر

تعداد تقاضاهای هر کاربر : ١٠٠٠ تقاضا

اندازه نمایه هر کاربر : ١۵٠ رکورد

تعداد رکورد خروجی در هر پیشبینی : ١۵ رکورد

: -2-5 آزمایش ۲

تعداد کاربران : ١٠ کاربر

تعداد تقاضاهای هر کاربر : ٢٠٠٠ تقاضا

اندازه نمایه هر کاربر : ٢٠٠ رکورد

تعداد رکورد خروجی در هر پیش بینی

:

١۵ رکورد

و A بدست آوردن فاصله اقلیدسی عامل

عاملهای دیگر

انتخاب نمایه واحد متحرک

بدست آوردن دستههای اطلاعاتی با توجه

A به نمایه عامل

انجام پیشبینی

انتخاب نمایه واحد متحرک

مجموعه همسایهها

i دسته 1 دسته 2 دسته

شکل 5: مراحل کلی پیشبینی

0

5

10

15

20

25

30

35

40

45

1 2 3 4 5 6 7 8 9 10

Agent A Agent B Agent C Agent D Agent E

نمودار 1: درصد برخورد برای هر کاربر در آزمایش اول

تعداد تقاضاها

درصد برخورد

0

5

10

15

20

25

30

35

40

1 2 3 4 5 6 7 8 9 10

Agent A Agent B Agent C Agent D Agent E

Agent F Agent G Agent H Agent I Agent J

نمودار 2: درصد برخورد برای هر کاربر در آزمایش دوم

تعداد

تقاضاها

درصد

٨ ۶􀰮 جان آ 􀣌􀦘 لا􀭃􀰔 ی کا 􀨉 ند􀩀􀥟 س 􀦿ا􀶢􀡶􀣡􀨯 ن 􀲻􀱱 او

1 6 0

: -3-5 آزمایش ۳

در این آزمایش تعداد ٢٠٠٠ تقاضا در هر یک از روشها جهت

ارزیابی مورد استفاده قرار گرفته است. هر بازه نشان دهنده ٢٠٠

تقاضا میباشد.

جدول 4: درصد برخورد حاصل از آزمایش سوم برای دو مدل

Prediction Clustering

21.5 20.5

23.5 22

17.5 23

25 23

14 20

22 22.5

24.5 23

21.5 24

14 22

22 19

-6 نتایج و کارهای آینده

همانگونه که دیده میشود هریک از الگوریتمهای مطرح شده در

بالا و حتی آنهایی که در اینجا مطرح نشدهاند، فقط اطلاعاتی را

کش میکنند که در تراکنش جاری مورد نیاز میباشد، و از

تکنیکهای پیش بینی جهت کش کردن استفاده نمینمایند. در

این کار، علاوه بر اطلاعاتی که هم اکنون مورد نیاز واحدهای

متحرک میباشد، دادههای دیگر نیز که احتمال استفاده از آنها

توسط واحد متحرک وجود دارد پیش بینی شده و بر روی بانک

اطلاعاتی واحد متحرک کش میشوند.

با توجه به آزمایشات انجام شده بر روی دادههای تصادفی(داده-

هایی که در آینده مورد نیاز میباشند) میتوان مشاهده نمود

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

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

به صورت تصادفی انتخاب شدهاند؛ با این حال میتوان مشاهده

نمود که تقریبًا در حدود ٢٠ الی ٣٠ درصد تقاضاهای ارائه شده،

در درون واحد متحرک موجود بودهاند و در واقع ٢٠ تا ٣٠ درصد

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

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

میتواند مزایایی را برای بانکهای اطلاعاتی متحرک دارا باشد. در

آزمایش سوم نیز مشاهده میشود که اختلاف روش خوشهای و

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

زیادی از لغو تراکنشهای در حال اجرا جلوگیری کرد. البته این

جلوگیری از لغو شدن برای زمانهایی میباشد که ارتباط واحد

قطع شده است. به این صورت که دادههایی که MSS متحرک با

پیشبینی میشوند بر روی واحد متحرک کش میشوند و واحد

متحرک میتواند در زمان قطع ارتباط، از این دادهها به عنوان

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

دادهی جدیدی نباشد اجرا کرده و به پیش ببرد.

همچنین این پیشبینی میتواند تا حد زیادی ترافیک موجود در

شبکه بیسیم را کاهش دهد. در این کار، برای پیشبینی از روشی

خاص استفاده شده است که میتوان جهت بهتر نمودن پیشبینی

اطلاعات از روشها و الگوریتمهایی مثل الگوریتمهای

Learning ) یادگیری ،(Genetic Algorithms) ژنتیک

و (Neural Networks) شبکههای عصبی ،(Algorithms

نیز استفاده نمود. با هر یک از این (Fuzzy Logic) منطق فازی

الگوریتمها نیز میتوان ایدههایی را جهت انجام عمل پیشبینی

ارائه داد. مث ً لا با استفاده از الگوریتمهای یادگیری، میتوان عامل

را جهت یادگیری و تعقیب کردن رفتارهای کاربران و دادههای

مورد دسترس آنان تکمیل نمود. هر یک از این الگوریتمها

تواناییهایی را جهت انجام اینگونه کارها دارا هستند.

مراجع

[1] B. Liu, W. Lee, D. Lun Lee, "Distributed Caching of

Multi-dimensional Data in Mobile Environments",

Proceedings of the ACM 2005.

[2] B. Sarwar, G Karypis, J Konstan, J Riedl, "Analysis

of Recommendation Algorithms for E-Commerce",

Minnesota, Proceedings of the ACM, 2000.

[3] B. Y. Chan, A. Si, H.V.Leong, "Cache Management

for Mobile Database:Design and Evaluation", IEEE,

1998.

[4] D. Barbara, T. Imielifiski, "Sleepers and

Workaholics: Caching Strategies in Mobile

Environments", VLDB Journal,4, 567-602, 1995.

[5] E. Pitoura, B. Bhargava, "Maintaining Consistency

of Data in Mobile Distributed Environments",

Proceeding in 15thInternational Conference on

Distributing Computing Systems, 1995.

0

5

10

15

20

25

30

1 2 3 4 5 6 7 8 9 10

Prediction Clustering

نمودار 3: درصد برخورد برای هر مدل در آزمایش سوم

تعداد تقاضاها

درصد برخورد

٨ ۶􀰮 جان آ 􀣌􀦘 لا􀭃􀰔 ی کا 􀨉 ند􀩀􀥟 س 􀦿ا􀶢􀡶􀣡􀨯 ن 􀲻􀱱 او

1 6 1

[6] G. D. Walborn, P. K. Chrysanthis, "PRO-MOTION:

Management of Mobile Transactions", Proceeding of

the ACM Symposium on Applied Computing, 1999.

[7] G. F. Forman, J. Zahorjan, "The Challenges of

Mobile Computing", IEEE Computer, April 1994.

[8] L. H. Yeo, A. Zaslavsky, "Submission of

Transactions from Mobile Workstations in a

Cooperative Multidatabase Processing

Environment", Proceedings of the 14th International

Conference on Distributed Computing Systems, June

21-24, 1994, IEEE Computer Society Press, Los

Almaitos, California, p.372-379.

[9] M. H. Dunham, A. Helal, S, Balakrishnan, "A mobile

transaction model that captures both the data and

movement behavior", Mobile Networks and

Applications 2, 1997, 149–162.

[10] M.Satyanarayanan, "Fundamental Challenges in

Mobile Computing", Proceedings of the 15th Annual

ACM Symposium on Principles of Distributed

Computing, 1996.

[11] N. Santos, L. Veiga, P. Ferreira, "Transaction

Policies for Mobile Networks", Proceedings of the

Fifth IEEE International Workshop on Policies for

Distributed Systems and Networks, IEEE, 2004.

[12] N. Prabhu, V. Kumar, I. Ray, Gi-Chul Yang,

"Concurrency Control in Mobile Database Systems",

Proceedings of the 18th International Conference on

Advanced Information Networking and Application,

IEEE, 2004.

[13] R. Lee, K. Goshima, Y. Kambayashi, H Takakura,

"Caching Schema for Mobile Web Information

Retrieval", 2003.

[14] R. A. Dirckze, L. Gruenwald, "A Toggle Transaction

Management Technique for Mobile Multidatabases",

Proceedings of the CIKM, 1998.

[15] S. K. Madria, B. Bhargava, "A Transaction Model

for Mobile Database", IEEE 1998.

[16] Sheng-Uei Guan, Ping Cheng Tan, Tai Kheng Chan,

"Intelligent product brokering for e-commerce: an

incremental approach to unaccounted attribute

detection", ELSEVIER, Electronic Commerce

Research and Applications 3, 2004, 232–252.

[17] S. Ujjin, P. J. Bentley, "Evolving Good

Recommendations", 2002.

[18] Y. Chung, B. Bhargava, M. Mahoui, L. Lilien,

"Autonomous Transaction Processing Using Data

Dependency in Mobile Environments", Department

of Computer Sciences Purdue University, 2002

mohsen_mahyar@yahoo.com

 

 

 

   + MOHSEN GHASEMI - ٩:٠٩ ‎ق.ظ ; ۱۳۸٩/٥/۱۱