نقشه راه GIS

درخواست مشاوره

09120049370

8 صبح تا 12 شب

09120049370

Telegram Whatsapp Youtube
کاربرد جی ای اس

 

خلاصه

در محاسبات فراگیر، خدمات مبتنی بر مکان (LBS) برای مشتریان تلفن همراه بر اساس مکان فعلی آنها ارزشمند است. LBS ها از پرس و جوهای پنجره فضایی برای فعال کردن برنامه های کاربردی مفید برای مشتریان تلفن همراه استفاده می کنند. بر اساس الگوهای دسترسی اریب مشتریان تلفن همراه، پخش بی سیم غیر مسطح نشان داده شده است که اشیاء فضایی را به طور موثر به مشتریان تلفن همراه منتشر می کند. در این مقاله، ما سناریویی را در نظر می گیریم که در آن اشیاء فضایی برای پردازش پرس و جوهای پنجره به مشتریان تلفن همراه از طریق یک کانال بی سیم به شیوه ای غیر مسطح پخش می شوند. برای چنین سناریویی، ما یک روش شاخص هوای فضایی کارآمد برای رسیدگی به دسترسی پرس و جوی پنجره در محیط‌های پخش بی‌سیم غیر مسطح پیشنهاد می‌کنیم. مفهوم بزرگترین مستطیل خالی برای جلوگیری از بررسی غیر ضروری محتوای پخش استفاده می شود. بنابراین زمان پردازش درخواست های پنجره کاهش می یابد. نتایج شبیه‌سازی نشان می‌دهد که روش شاخص هوای فضایی پیشنهادی از روش‌های موجود در تنظیمات مختلف بهتر عمل می‌کند.
کلید واژه ها: 

خدمات مبتنی بر مکان ؛ پخش بی سیم غیر مسطح ; شاخص هوای فضایی ; پرس و جوهای پنجره

 

1. معرفی

در محاسبات فراگیر، خدمات مبتنی بر مکان (LBSs) خدمات ارزشمندی را به مشتریان تلفن همراه بر اساس مکان فعلی آنها ارائه می دهند. LBS های تحویل داده شده از طریق پخش داده های بی سیم می توانند به طور کارآمد و همزمان برنامه ها را به تعداد زیادی از مشتریان تلفن همراه ارائه دهند [ 1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ]. علاوه بر این، LBSها سیستم‌های آگاه از زمینه را قادر می‌سازند تا برنامه‌هایی را ارائه دهند که بتوانند بر اساس مکان‌های فعلی مشتریان تلفن همراه واکنش نشان دهند. LBSها برای ارائه برنامه های کاربردی مفید به مشتریان تلفن همراه بر پرس و جوهای پنجره فضایی تکیه می کنند [ 8 ]. چنین پرس و جوهایی اشیاء فضایی را در یک منطقه مستطیلی ثابت بر اساس مکان های فعلی کلاینت ها بازیابی می کنند [1 ، 2 ]. به عنوان مثال، یک کاربر ممکن است از سرویس گیرنده تلفن همراه خود برای صدور پرس و جو برای مکان یابی دستگاه های خودپرداز در یک کیلومتری مکان فعلی خود استفاده کند.
الگوهای دسترسی منحرف مشتریان سیار منجر به بازیابی اشیاء فضایی با نرخ فرکانس نسبتاً بالا می‌شود (مثلاً رستوران‌هایی که برای یک منطقه خاص بررسی شده‌اند). چنین اشیاء “گرم” باید بیشتر در یک چرخه پخش ظاهر شوند تا منجر به پخش غیر مسطح شوند [ 9 ]، بنابراین میانگین زمان انتظار مشتری برای بازیابی داده ها از کانال بی سیم کاهش می یابد. در این مقاله، به این موضوع می پردازیم که چگونه از دسترسی کارآمد برای پردازش درخواست های پنجره در سیستم های پخش بی سیم غیر مسطح پشتیبانی کنیم. در چنین سیستم‌هایی، سرور مجهز به آنتن به صورت دوره‌ای مجموعه‌ای از اشیاء فضایی انتخاب شده را پخش می‌کند، بنابراین یک چرخه پخش بر روی یک کانال بی‌سیم برای تولید یک جریان پخش تشکیل می‌دهد و کلاینت‌های موبایل برای بازیابی داده‌های مورد نظر، کانال را تنظیم می‌کنند.
برای به حداکثر رساندن عمر باتری، دستگاه های تلفن همراه باید در صورت امکان در حالت چرت زدن باقی بمانند و فقط در صورت لزوم به حالت فعال تبدیل شوند [ 10 ، 11 ، 12 ، 13 ]. درهم تنیدگی شاخص های فضایی با اشیاء فضایی می تواند به دستگاه های تلفن همراه کمک کند تا زمان رسیدن اشیاء فضایی و شاخص های مربوط به آنها را پیش بینی کنند. این به دستگاه های تلفن همراه اجازه می دهد تا داده های ناخواسته را نادیده بگیرند و در نتیجه مصرف انرژی را کاهش دهند [ 14 ، 15 ، 16]]. زمان دسترسی و تنظیم دو معیار عملکرد اصلی برای روش‌های شاخص هوای فضایی در سیستم‌های پخش بی‌سیم هستند. زمان دسترسی نشان‌دهنده مدت زمان مورد نیاز از مشتری تلفن همراه است که درخواستی را صادر می‌کند تا زمانی که تمام داده‌های پاسخ به طور کامل بازیابی شوند. زمان تنظیم نشان‌دهنده مدت زمانی است که دستگاه تلفن همراه برای بازیابی شاخص‌ها و داده‌های مرتبط برای پردازش یک پرس و جو فعال است.
تلاش های قبلی شاخص های فضایی را برای پشتیبانی از پردازش پرس و جو فضایی در سیستم های پخش بی سیم غیر مسطح ایجاد کرده اند. Im و Choi (2012) یک طرح شاخص هوای چند سطحی ( MLAIN ) [ 17 ] را پیشنهاد کردند که یک تقسیم بندی چند سطحی را برای فضا برای عملکرد بهتر از روش های قبلی اتخاذ می کند. با این حال، MLAIN فقط دو گروه، داده های داغ و معمولی را پارتیشن بندی می کند، و همه داده های داغ به طور مکرر در یک فرکانس در یک چرخه پخش پخش می شوند. این باعث افزایش طول چرخه پخش می شود و باعث افزایش شدید زمان دسترسی می شود. برای رسیدگی به این مشکل، شن و جیان یک شاخص فضایی اریب ( SSI ) را پیشنهاد کردند [ 18]] برای تقسیم بیشتر داده های داغ به چند گروه، و تکرار داده های داغ در یک چرخه پخش با فرکانس های مختلف.
با این حال، هر دوی این روش های مبتنی بر سلول از نظر پردازش پرس و جو دارای ضعف جدی هستند. در هر دو روش، برای پردازش یک پرس و جو پنجره، دستگاه های تلفن همراه باید تمام سلول های همپوشانی با منطقه پرس و جو را بررسی کنند، حتی اگر برخی از سلول ها حاوی اشیاء مربوطه نیستند و می توان آنها را رد کرد. این منجر به بررسی غیر ضروری سلول های پخش شده در کانال بی سیم می شود و در نتیجه زمان دسترسی و تنظیم را افزایش می دهد. بنابراین، با توجه به الگوهای دسترسی اریب مشتریان سیار، یک روش شاخص هوای فضایی بر اساس بزرگترین مستطیل‌های خالی، به نام LER پیشنهاد می‌کنیم.، برای پردازش کارآمد پرس و جوهای پنجره فضایی صادر شده توسط مشتریان تلفن همراه در سیستم های پخش بی سیم غیر مسطح. بزرگترین مستطیل خالی، مستطیلی با حداکثر اندازه را نشان می دهد که از حداقل مستطیل مرزی حاوی اشیاء در سلول داغ، بدون تماس با هیچ جسم فضایی گسترش می یابد [ 19 ]. اگر ناحیه پرس و جو یک پرس و جو پنجره در بزرگترین مستطیل خالی سلول باشد، اشیاء مربوطه قطعاً در این سلول قرار دارند و سلول های دیگر را می توان نادیده گرفت. به این ترتیب، دستگاه های تلفن همراه می توانند به سرعت پردازش پرس و جو را به پایان برسانند، زمان دسترسی و تنظیم را کوتاه کنند و در نتیجه مصرف انرژی را به حداقل برسانند.
مشارکت های پژوهشی ما به شرح زیر خلاصه شده است.

  • برای پردازش درخواست‌های پنجره، اطلاعات مربوط به بزرگترین مستطیل خالی سلول‌ها در فهرست هوای فضایی ارائه می‌شود تا منطقه جستجو را بیشتر محدود کند و از محتوای پخش نامربوط رد شود، بنابراین زمان دسترسی و تنظیم را کاهش می‌دهد.
  • آزمایش‌های مختلف با تنظیمات مختلف، اثربخشی روش شاخص هوای فضایی پیشنهادی را تأیید می‌کند، که از روش‌های موجود SSI و MLAIN بهتر عمل می‌کند .
این مقاله به کارهای قبلی گزارش شده در [ 20 ] می پردازد و بحث مفصل تری از کار مرتبط ارائه می دهد. روش شاخص هوای فضایی پیشنهادی دوباره سازماندهی شده است و ما آزمایش‌ها و بحث‌های جامع دیگری را ارائه می‌کنیم.
بقیه این مقاله به شرح زیر سازماندهی شده است. در بخش 2 ، کار مرتبط را بررسی می کنیم. بخش 3 روش شاخص هوای فضایی پیشنهادی ما را ارائه می‌کند. بخش 4 آزمایش ها را مورد بحث قرار می دهد. در نهایت، این مقاله را در بخش 5 به پایان می‌رسانیم .

2. کارهای مرتبط

اخیراً بسیاری از روش‌های شاخص هوا برای سازمان‌دهی داده‌های مکانی برای حل مسائل مربوط به کارایی انرژی و پردازش پرس و جو در پخش داده‌های بی‌سیم طراحی و اجرا شده‌اند. روش های پخش داده های بی سیم را می توان بر اساس فرکانس پخش همه اقلام داده به روش های مسطح و غیر مسطح طبقه بندی کرد. در رویکرد پخش داده های مسطح، همه اقلام داده با یک فرکانس پخش می شوند. در رویکرد غیر مسطح، موارد داده داغ بیشتر پخش می شوند.

2.1. پخش داده های مسطح

سیستم‌های پخش داده‌های بی‌سیم را می‌توان بر اساس این‌که آیا مشتریان برای آیتم‌های داده خاصی ترجیح دارند یا خیر، به‌صورت مسطح و غیر مسطح طبقه‌بندی کرد [ 9 ، 17 ، 21 ، 22 ، 23 ]. یک سیستم پخش داده مسطح ترجیحات کلاینت ها را برای اقلام داده در نظر نمی گیرد: سرور همه اقلام داده را تنها یک بار در یک چرخه پخش پخش می کند، و زمانی که کلاینت ها به اقلام داده ای خاص بیشتر از سایرین دسترسی پیدا می کنند ناکارآمد می شود.
از نظر رویکردهای پخش داده های مسطح، ژنگ و همکاران. (2004) از شاخص منحنی هیلبرت ( HCI ) برای بهبود کارایی پردازش پرس و جوهای پنجره و پرس و جوهای kNN [ 24 ] استفاده کرد. HCI بر اساس ساختار داده درختی B+ اجرا شد و با اقلام داده در یک طرح تخصیص شاخص (1، متر ) در هم آمیخت . اگرچه HCI می‌تواند دسترسی خطی مشتریان را شبیه‌سازی و تقریبی کند، اما مقادیر قابل‌توجهی انرژی در محاسبه آیتم‌های درخواست شده مصرف می‌کند. ژنگ و همکاران (2009) بعداً HCI و شاخص فضایی توزیع شده ( DSI ) را برای رسیدگی به این موضوع ادغام کرد [ 22 ]. این دو طرح از منحنی هیلبرت (HC ) مقادیری برای نشان دادن محل اقلام داده برای جایگزینی مختصات واقعی اقلام داده است. DSI در یک نوع جدول در یک طرح توزیع شده تخصیص داده می شود. اگرچه این رویکرد پخش داده‌های مسطح ترکیبی می‌تواند آیتم‌های درخواست‌شده را گسترش دهد و پردازش پرس و جو را با گوش دادن به آیتم‌های کاندید به اندازه کافی بزرگ بهبود بخشد، اما در حین محاسبه مقادیر HC برای اقلام داده به جای مختصات واقعی، مقادیر قابل توجهی انرژی مصرف می‌کند .
لی و ژنگ (2005) همچنین از مقادیر DSI و HC برای مدیریت پردازش پرس و جو در یک سیستم پخش داده مسطح استفاده کردند [ 25 ]. آنها یک جدول توزیع شده طراحی کردند و اقلام داده را برای پرس و جو سریع ثبت کردند. اگرچه این روش می تواند عملکرد بهتری نسبت به روش سنتی HCI داشته باشد ، اما مصرف انرژی سمت مشتری را کاهش نمی دهد. من و همکاران [ 26 ] تحقیقات لی و ژنگ [ 25 ] را گسترش داد و یک روش جدید شاخص توزیع شده مبتنی بر سلول ( CEDI ) را با استفاده از دو جدول سطح برای ثبت فضای شبکه برای درخواست های پنجره ارائه کرد. برای بهبود زمان دسترسی، جداول دو سطح می توانند یک طرح داده را با استفاده از n × n اختصاص دهندپارتیشن شبکه برای پردازش پرس و جوهای داده شده، CEDI از مختصات واقعی اقلام داده برای عملکرد بهتر از HCI و DSI استفاده می کند .
اشکال اصلی این رویکردها این است که نمی توانند به طور موثر زمان دسترسی را کاهش دهند، به ویژه برای توزیع غیریکنواخت اقلام داده، که منجر به مصرف انرژی قابل توجهی در سمت مشتری می شود.

2.2. پخش داده های غیر مسطح

سیستم‌های پخش غیر مسطح ترجیحات مشتری را برای اقلام داده در نظر می‌گیرند و دسترسی سریع‌تری به اقلام داده داغ را برای مشتریان فراهم می‌کنند [ 21 ]. در یک چرخه پخش واحد، سرور به جای استفاده از فرکانس یکنواخت برای همه اقلام داده، آیتم های داده داغ را برای انتشار بیشتر در اولویت قرار می دهد. مشتریان از طریق یک کانال آپلینک با پهنای باند کم، سرور را از ترجیحات آیتم داده خود مطلع می کنند [ 21 ]. سرور با پخش موارد درخواستی از طریق یک کانال پایین لینک با پهنای باند بالا به صورت غیر مسطح پاسخ می دهد [ 21 ]. این باعث کاهش زمان دسترسی برای پردازش پرس و جو می شود [ 9 ، 21 ].
من و همکاران (2011) یک شاخص توزیع شده مبتنی بر شبکه ( GDIN ) [ 21 ] برای پرس و جوهای پنجره در سیستم های پخش غیر مسطح با استفاده از یک پارتیشن فضایی منظم پیشنهاد کرد. در این تحقیق سلول های شبکه ای حاوی سلول های منظم و سلول های داغ هستند. این روش را می توان به راحتی پیاده سازی کرد زیرا سلول های داغ برای حمل اقلام داده داغ و سلول های معمولی فقط برای فهرست بندی اقلام داده معمولی استفاده می شوند. با این حال، زمان دسترسی به GDIN را نمی توان بهبود بخشید زیرا فرکانس های انتشار مختلف را برای سلول های گرم و معمولی اجازه نمی دهد.
Im و Choi (2012) بعداً یک طرح شاخص هوای چند سطحی ( MLAIN ) [ 17 ] برای حل اشکال GDIN با استفاده از یک پارتیشن فضایی چند سطحی ارائه کردند. اخیرا، Im و Hwang (2014) تحقیقات خود را گسترش دادند و یک شاخص فضایی دو لایه ( TTSI ) [ 27 ] برای تمایز بین داده های داغ و معمولی ارائه کردند. اگرچه MLAIN و TTSI انواع داده های مختلف را به خوبی مدیریت می کنند، اما این روش ها اجازه نمی دهند که داده های داغ در فرکانس های مختلف ارائه شوند. شن و جیان (در حال چاپ) یک شاخص فضایی اریب ( SSI ) پیشنهاد کردند [ 18] برای رفع این مشکل با طبقه بندی داده های محبوب به گروه های متعدد و تکرار این گروه ها در چرخه پخش با توجه به فرکانس های پخش آنها.
اشکال اصلی روش های پخش غیر مسطح هزینه محاسباتی بالای آنها به دلیل همپوشانی زیاد بین سلول های پخش و منطقه پرس و جو است. پرس و جو اجرا می شود حتی اگر برخی از سلول ها حاوی اقلام داده مورد نظر نباشند، زمان دسترسی و تنگنای زمان تنظیم را ایجاد می کند، که می تواند به عنوان یک مبادله در روش های پخش غیر مسطح تلقی شود. برای پرداختن به این موضوع، این مقاله یک روش شاخص هوای فضایی را بر اساس بزرگترین مستطیل‌های خالی پیشنهاد می‌کند.

3. روش پیشنهادی شاخص هوای فضایی

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

3.1. مدل سیستم

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

3.2. نگاشت داده های مکانی از دو بعدی به یک بعدی

از آنجایی که دسترسی به کانال بی سیم خطی است، در مرحله اول روش پیشنهادی، داده های مکانی در یک فضای دو بعدی باید با استفاده از یک منحنی پرکننده فضا برای تقسیم دو بعدی به ترتیب خطی در یک فضای یک بعدی تبدیل شوند. فضای داخل سلول‌ها را فراهم می‌کند، به هر سلول یک شماره دنباله ارائه می‌کند، و هر سلول را یک بار به ترتیب خاصی بازدید می‌کند. در میان منحنی‌های پرکننده فضا، منحنی هیلبرت ( HC ) به خوبی برای حفظ موقعیت مکانی داده‌های مکانی برای تبدیل شناخته شده است، و اطمینان می‌دهد که نزدیکی نسبی بین اقلام داده‌های مکانی از طریق تبدیل حفظ می‌شود. بنابراین، روش پیشنهادی ما از HC برای نگاشت داده های مکانی از دو بعدی به یک بعدی استفاده می کند.
در روش پیشنهادی، ما به صورت بازگشتی یک فضا را به چهار سلول با اندازه مساوی با توجه به HC تقسیم می کنیم تا زمانی که هر سلول در سطح n دارای حداکثر اشیاء فضایی η باشد. یعنی فضا به سلول های 2 n در 2 n تقسیم می شود . برای هر پارتیشن در سطح i ، 1 ≤ i ≤ n ، یک شماره دنباله بازدید شده به نام مقدار HC به هر سلول اختصاص داده می شود. در سطح i ، مقدار HC از 0 تا (2 i ×2 –1) متغیر است. در روش پیشنهادی ما، هر سلول در سطح i با C (i ، j )، که در آن j مقدار HC در سطح i است . ما از مثال نشان داده شده در شکل 2 a برای نشان دادن پارتیشن فضا استفاده می کنیم. در شکل 2 الف، 13 رستوران مورد علاقه، { d 1 , …, d 13 } وجود دارد که به سه نوع داغ ترین، داغ و معمولی طبقه بندی می شوند. اجسام فضایی d 2 و d 3 داغ ترین ها، اجسام فضایی d 8 و d 12 گرم ترین و بقیه معمولی هستند. در این مورد، با η= 2، به دنبال پارتیشن بندی فضایی، هر سلول باید حداکثر دو شیء داشته باشد. طبق HC ، در سطح 1، فضا به چهار سلول با اندازه مساوی تقسیم می شود که با C (1،0)، C (1،1)، C (1،2) و C (1،3) مشخص شده اند. همانطور که در شکل 2 ب نشان داده شده است، جایی که توالی بازدید از سلول ها به ترتیب HC از یک خط نقطه چین با یک فلش پیروی می کند. از آنجایی که هر سلول در سطح 1 حاوی بیش از دو شی است، هر سلول بیشتر به چهار سلول با اندازه مساوی در سطح 2 تقسیم می شود، همانطور که در شکل 2 ج نشان داده شده است. در سطح 2، برای بازدید مداوم از سلول ها، ترتیب بازدید از سلول های فرعی در سلول های C (1,0) و C(1،3) از سطح 1 با پیروی مناسب از چرخش/تغییر سلول سطح 1 تغییر می کند. پس از تقسیم بندی فضایی در سطح 2، هر سلول حداکثر دارای دو شی است و نیازی به پارتیشن بندی بیشتر نیست. در شکل 2 c، سلول های حاوی اجسام داغ، سلول های داغ نامیده می شوند که با H ( i ، j )، به عنوان مثال، H (2،2) مشخص شده اند.

3.3. تولید برنامه پخش غیر مسطح

در مرحله دوم، بر اساس احتمالات دسترسی اریب داده های مکانی، روش پیشنهادی یک برنامه پخش غیر مسطح در یک چرخه پخش تولید می کند. روش دیسک های پخش ( BD ) آچاریا و همکاران [ 9 ] به طور موثر داده های مکانی را به گروه ها (دیسک ها) تقسیم می کند و یک برنامه پخش غیر مسطح را بر اساس الگوهای دسترسی اریب آنها تولید می کند، بنابراین دسترسی سریع به داده های فضایی داغ را به دست می آورد. بنابراین، روش پیشنهادی ما از روش BD برای تولید برنامه غیر مسطح استفاده می‌کند. تولید یک برنامه پخش در یک چرخه پخش به صورت زیر پردازش می شود [ 9 ]. ابتدا سلول های سطح n در S گروه بندی می شونددیسک‌ها با توجه به احتمال دسترسی‌شان به‌طوری‌که دیسک سریعی که بارها بیشتر تکرار می‌شود سلول‌های کمی دارد و دیسک‌هایی که تعداد دفعات کمتری تکرار می‌شوند سلول‌های زیادی دارند. هر دیسک k دارای فرکانس نسبی λ k ، 1 ≤ k ≤ S است ، که تعداد دفعاتی است که در یک چرخه پخش ظاهر می شود. در هر دیسک، سلول ها احتمال دسترسی مشابهی دارند و به ترتیب HC اختصاص داده می شوند . ثانیاً، کمترین مضرب مشترک، LCM ، فرکانس‌های نسبی برای تعیین اینکه هر دیسک به چند تکه تقسیم می‌شود، محاسبه می‌شود. هر دیسک k بیشتر به ( LCM / λ k) تقسیم می شود) تکه ها. در نهایت، یک تکه از هر دیسک به‌صورت جداگانه به‌صورت دوره‌ای برنامه‌ریزی می‌شود تا یک چرخه کوچک، Bl, 1≤l≤ LCM را تشکیل دهد تا آخرین تکه از آخرین دیسک زمان‌بندی شود . یعنی چرخه های فرعی LCM در یک چرخه پخش وجود دارد.
S = 3 دیسک و D 1 ، D 2 و D 3 را به ترتیب با λ 1 = 4، λ 2 = 2 و λ 3 = 1 فرض کنید . داده های مکانی در شکل 2 c را به عنوان مثال در نظر بگیرید. این سلول ها همانطور که در شکل 3 الف نشان داده شده است به سه دیسک گروه بندی می شوند ، جایی که سلول های داغ نسبتاً بیشتر ظاهر می شوند. در این مورد، از آنجایی که LCM = 4، دیسک های D 1 ، D 2 و D 3همانطور که در شکل 3 ب نشان داده شده است، به ترتیب به 4/4 (= 1)، 4/2 (= 2)، و 4/1 (= 4) تقسیم می شوند . پس از آن، هر تکه از هر دیسک به صورت جداگانه به ترتیب دایره ای برنامه ریزی می شود تا یک برنامه پخش غیر مسطح را تشکیل دهد تا زمانی که آخرین قطعه از دیسک D 3 برنامه ریزی شود، همانطور که در شکل 3 ج نشان داده شده است. در این مورد، چهار چرخه فرعی در یک چرخه پخش وجود دارد ، B1 ، B2 ، B3 و B4 .

3.4. ساخت ساختار شاخص و بزرگترین مستطیل های خالی

در نظر بگیرید که یک کلاینت تلفن همراه در شکل 2 ج، یک درخواست پنجره با منطقه پرس و جو QR صادر کرده است . در روش های قبلی مبتنی بر سلول مانند MLAIN [ 17 ] و SSI [ 18 ]، تمام سلول هایی که با ناحیه پرس و جو همپوشانی دارند باید بررسی شوند. در شکل 2 c، اگرچه سلول های H (2،2)، C (2،3)، C (2،4)، و C (2،7) با QR همپوشانی دارند ، تنها شی مرتبط برای این منطقه پرس و جو، شی d است. 3 که در H (2،2) است. در این صورت نیازی به بررسی سلول ها نیستC (2،3)، C (2،4)، و C (2،7)، که زمان دسترسی و تنظیم را افزایش می دهد. برای غلبه بر این مشکل، از بزرگترین مستطیل های خالی [ 19 ] استفاده می کنیم تا از بررسی غیرضروری محتوای پخش جلوگیری کنیم. بزرگترین مستطیل خالی بزرگترین مستطیل است که هیچ جسمی را لمس نمی کند. سلول H (2،2) را در شکل 4 به عنوان مثال برای نشان دادن بزرگترین مستطیل خالی در نظر بگیرید. توجه داشته باشید که سلول های شکل 4 بخشی از سلول های شکل 2 ج هستند. در شکل 4 ، حداقل مستطیل مرزی، MBR 1 ، برای شامل اجسام d 2 و d تولید شده است.3 در سلول H (2،2). پس از آن، مستطیل با حداکثر اندازه که از لبه های MBR 1 امتداد می یابد بدون تماس با هیچ جسم دیگری، بزرگترین مستطیل خالی سلول H را تشکیل می دهد (2،2). در شکل 4 ، از ناحیه QR پرس و جوکاملاً در این بزرگ‌ترین مستطیل خالی قرار دارد، شی مربوط به این پرس و جو پنجره در این سلول محدود شده است و هیچ سلول دیگری نباید بررسی شود. در نتیجه، زمان دسترسی و تنظیم را می توان کاهش داد. با این حال، اگر تمام مستطیل‌های خالی بزرگ‌تر در ساختار نمایه درج شوند، اندازه یک پخش بیش از حد بزرگ می‌شود و منجر به افزایش گسترده زمان دسترسی می‌شود. از آنجایی که سلول های داغ بیشتر از سلول های معمولی بازیابی می شوند، تنها بزرگترین مستطیل های خالی سلول های داغ در ساختار شاخص روش پیشنهادی ارائه شده است.
در روش پیشنهادی، سه نوع اطلاعات شاخص در ساختار شاخص هوای فضایی ارائه می شود: شاخص جهانی، شاخص سلول گرم و شاخص سلول. این نمایه ها با برنامه پخش غیر مسطح در یک چرخه پخش درهم می آمیزند. درج سه نوع شاخص در بین برنامه های پخش به شرح زیر است. شاخص سراسری قبل از هر چرخه کوچک و شاخص سلول داغ قبل از هر سلول داغ درج می شود. علاوه بر این، روش پیشنهادی شاخص‌های سلولی را از سطح 1 تا ( n -1) قبل از اولین سلول فرزند سطح بعدی که یک سلول غیر داغ است وارد می‌کند. علاوه بر این، شاخص سلول مربوطه از سطح n قبل از هر سلول از سطح n درج می شود . شکل 5برنامه پخش غیر مسطح برای اشیاء فضایی نشان داده شده در شکل 2 ج را با توزیع شاخص هوای فضایی نشان می دهد. در شکل 5 ، چهار شاخص سراسری، GI 1 ، GI 2 ، GI 3 و GI 4 قبل از چهار چرخه فرعی، و شاخص های سلول داغ مربوطه قبل از هر سلول داغ درج شده اند. سپس نمایه سلولی سطح 1 قبل از اولین سلول فرزند مربوطه در سطح 2 که حاوی اشیاء است و یک سلول غیر داغ است درج می شود. به عنوان مثال، در شکل 5 ، از آنجایی که سلول C (2،4) حاوی شی d 5 ، اولین سلول فرزند داخل سلول است.C (1،1)، شاخص سلول برای C (1،1) قبل از سلول C (2،4) درج می شود . در نهایت، شاخص سلول مربوطه در سطح 2 قبل از هر سلول از سطح 2 درج می شود.
ساختارهای شاخص پیشنهادی به شرح زیر است.

  • شاخص جهانی: G = < C t , HL >

    • C t زمان رسیدن نزدیکترین نمایه سلولی آینده سطح 1 در کانال بی سیم است. به عنوان مثال، C t در اولین شاخص جهانی در شکل 5 به ابتدای شاخص سلولی C (1،0)، t 5 اشاره می کند.
    • HL حاوی زمان رسیدن شاخص های سلولی برای همه سلول های داغ است. به عنوان مثال، HL در اولین شاخص جهانی در شکل 5 حاوی اطلاعاتی در مورد تمام سلول های داغ، H (2،2)، H (2،8) و H (2،13) است.
  • شاخص سلول داغ: H ( i ، j ) = < G t ، C t ، SL ، DL ، LERI >

    • G t زمان رسیدن نزدیکترین شاخص جهانی آینده است. به عنوان مثال، در شکل 5 ، G t در شاخص سلول داغ H (2،2) در ردیف دوم به ابتدای شاخص جهانی آینده، t 16 اشاره می کند.
    • SL حاوی اطلاعاتی در مورد سلول های خواهر و برادر هم سطح است.
    • DL شامل مختصات اشیاء فضایی در آن سلول و زمان رسیدن مربوط به آنها است. از DL ، دستگاه تلفن همراه می تواند تعیین کند که آیا اشیاء فضایی قبل از بازیابی آنها از کانال، در منطقه پرس و جو قرار دارند یا خیر.
    • LERI اطلاعات مربوط به بزرگترین مستطیل خالی این سلول داغ را نشان می دهد. مختصات پایین-چپ و بالا-راست بزرگترین مستطیل خالی در LERI ثبت شده است .
  • شاخص سلول: C ( i ، j ) = < G t ، C t ، SL ، CL ، DL >

    • CL حاوی اطلاعاتی در مورد سلول های فرزند مربوطه در سطح بعدی است. به عنوان مثال، در شکل 5 ، CL در شاخص سلولی C (1،0) از سطح 1 حاوی اطلاعاتی در مورد سلول های فرزند سطح 2، C (2،1)، H (2،2)، و C (2) است. ، 3).

3.5. پردازش دسترسی برای پرس و جوهای پنجره

برای پاسخ به یک درخواست پنجره فضایی، سلول های سطح n که با ناحیه پرس و جو همپوشانی دارند باید بررسی شوند تا اشیاء فضایی مربوطه فیلتر شوند. با استفاده از بزرگ‌ترین مستطیل‌های خالی سلول‌های داغ، پرس و جو ممکن است به سرعت خاتمه یابد، بنابراین از بررسی غیرضروری سایر سلول‌های همپوشانی جلوگیری می‌شود. اطلاعات مربوط به سلول های همپوشانی در مجموعه معاینه، ES درج می شود . پس از دریافت پرس و جو، دستگاه تلفن همراه ابتدا به کانال بی سیم متصل می شود تا زمان رسیدن نزدیکترین شاخص جهانی آینده، G t را بدست آورد.و به حالت چرت زدن بروید تا منتظر شاخص جهانی باشید. توجه داشته باشید که زمان رسیدن نزدیکترین شاخص جهانی آینده نیز در بخش داده در برنامه پخش ارائه شده است که در شکل 5 نشان داده نشده است . سپس رویه های پردازش توسط الگوریتم 1 مدیریت می شوند.
به عنوان مثال پرس و جو پنجره با منطقه پرس و جو QR در شکل 2 ج را در نظر بگیرید. سلول های H (2،2)، C (2،3)، C (2،4)، و C (2،7) که با QR همپوشانی دارند ، باید بررسی شوند، به عنوان مثال، ES = { H (2،2)، C ( 2،3)، C (2،4)، C (2،7)}. دستگاه تلفن همراه در کانال بی سیم در نقطه a در شکل 5 تنظیم می شود و این شاخص جهانی را بازیابی می کند. پس از بررسی HL در این شاخص جهانی، دستگاه تلفن همراه دارای EQ = [ t 1] و استES = { C (2،3)، C (2،4)، C (2،7)}. از آنجایی که ES خالی نیست، C t در EQ قرار می گیرد ، یعنی EQ = [ t 1, t5]. سپس دستگاه تلفن همراه شاخص سلول داغ H (2،2) را در t 1 بازیابی می کند. پس از بررسی H (2،2)، دستگاه تلفن همراه تأیید می کند که منطقه پرس و جو QR در LERI H (2،2) موجود است ، که در شکل نشان داده شده است. 4 ، و پردازش پرس و جو را می توان پس از بازیابی شی مربوطه در این سلول داغ به پایان رساند. سپس دستگاه تلفن همراه DL را بررسی می کنددر H (2،2) با QR ، و تصمیم می گیرد که فقط شی فضایی d 3 باید بازیابی شود، یعنی EQ = [ t 3]. پس از آن، دستگاه تلفن همراه به حالت چرت زدن می رود و در t 3 برای بازیابی شی فضایی d 3 بیدار می شود و پردازش پرس و جو را در نقطه b در شکل 5 به پایان می رساند . در این حالت، اگر اطلاعاتی در مورد بزرگترین مستطیل خالی در شاخص هوای فضایی ارائه نشده باشد، فرآیند پرس و جو در نقطه c در شکل 5 به پایان می رسد.. بدیهی است که روش پیشنهادی از استفاده از بزرگترین مستطیل خالی برای به حداقل رساندن زمان دسترسی سود می برد. علاوه بر این، برخی از شاخص های سلول ممکن است برای کاهش زمان تنظیم نادیده گرفته شوند.
الگوریتم 1. یک پرس و جو پنجره را پردازش کنید
ورودی: مجموعه امتحانی ES .
خروجی: اشیاء مربوطه.
  • HL را در شاخص سراسری بررسی کنید تا زمان رسیدن سلول های داغ در ES را بدست آورید، آن زمان های ورود را در EQ صف معاینه قرار دهید و آن سلول ها را از ES حذف کنید . توجه داشته باشید که EQ یک صف مرتب شده است که زمان رسیدن نمایه یا شیء بازدید شده بعدی را به ترتیب صعودی ثبت می کند.

    • اگر ES خالی است، زمان رسیدن را در EQ دنبال کنید تا شاخص های سلولی را برای به دست آوردن اشیاء مربوطه بازیابی کنید. یعنی ناحیه پرس و جو فقط با سلول های داغ همپوشانی دارد. در غیر این صورت، زمان رسیدن را در C t در EQ قرار دهید .
  • زمان رسیدن را در EQ دنبال کنید تا نمایه های سلولی را برای به دست آوردن اشیاء مربوطه بازیابی کنید تا زمانی که ES خالی شود. توجه داشته باشید که عنصر بازدید شده در EQ پس از بازدید حذف می شود.

    • اگر نمایه بازدید شده، نمایه سلول داغ است، تعیین کنید که آیا منطقه پرس و جو در LERI وجود دارد یا خیر . اگر چنین است، اشیاء مربوطه به این سلول داغ محدود می شوند. برای بازیابی اشیاء مربوطه و پایان دادن به پردازش پرس و جو، DL را در این فهرست سلول داغ دنبال کنید . توجه داشته باشید که فقط اشیاء فضایی با مختصات ارائه شده در DL موجود در منطقه پرس و جو بازیابی می شوند. در غیر این صورت، SL را در این سلول داغ با ES بررسی کنید ، زمان ورود مربوطه را در EQ قرار دهید و تصمیم بگیرید که آیا C t باید در EQ قرار داده شود یا خیر .
    • اگر نمایه بازدید شده، نمایه سلولی است، SL ، CL و DL را در این فهرست سلولی با ES بررسی کنید ، زمان ورود مربوطه را در EQ قرار دهید و تصمیم بگیرید که آیا Ct باید در EQ قرار داده شود یا خیر . DL را در این فهرست سلولی دنبال کنید تا در صورت لزوم اشیاء مربوطه را بازیابی کنید.

4. مطالعه شبیه سازی

نتایج تجربی نشان داده شده در [ 17 ] تأیید کرد که MLAIN از HCI [ 24 ]، DSI [ 22 ] و GDIN [ 21 ] بهتر عمل می کند . علاوه بر این، نتایج نشان داده شده در [ 18 ] تأیید کرد که SSI بهتر از MLAIN عمل می کند . بنابراین، در ارزیابی عملکرد، این دو روش شاخص هوای فضایی، MLAIN [ 17 ] و SSI [ 18 ] را برای پخش بی‌سیم غیر مسطح انتخاب می‌کنیم تا با روش پیشنهادی خود، LER مقایسه کنیم.. میانگین زمان دسترسی، زمان تنظیم و مصرف انرژی در نتایج تجربی نگران کننده است.

4.1. مدل شبیه سازی

در مطالعه شبیه سازی ما، برای ارزیابی عملکرد در بین روش های تفاوت، از یک مجموعه داده واقعی همانطور که در شکل 6 نشان داده شده است ، استفاده می کنیم که شامل 5922 نقطه مورد علاقه در یونان است. سطل ها واحدهای انتقال منطقی در یک کانال پخش بی سیم هستند و شاخص های فضایی و اشیاء به سطل ها اختصاص داده می شوند. در شبیه سازی ما، فرض می کنیم که یک سطل 64 بایت و یک شی فضایی 1024 بایت را اشغال می کند. علاوه بر این، مختصات یک شی فضایی با دو عدد صحیح یک بایتی نشان داده می شود.
در نظر بگیرید که مجموعه داده شامل N شی فضایی است. برای شبیه‌سازی الگوهای دسترسی اریب اشیاء فضایی برای کلاینت‌های سیار، احتمال دسترسی، Pr ( i )، 1 ≤ i ≤ N را برای هر شی فضایی i با معادله (1)، که از توزیع Zipf پیروی می‌کند [ 9 ] اختصاص می‌دهیم:

پr ( i ) =( 1 / من )θ∑نj = 1( 1 / j )θ،پ�(من)=(1/من)�∑�=1ن(1/�)�،

که در آن θ ضریب Zipf برای کنترل چولگی توزیع است . با افزایش مقدار θ ، توزیع احتمالات دسترسی اجسام فضایی بسیار کج خواهد شد. با توجه به الگوهای دسترسی اریب اشیاء فضایی تولید شده توسط توزیع Zipf در معادله (1)، الگوریتم یی و همکاران [ 28 ] GREEDY را برای تقسیم بندی این اشیاء فضایی به دیسک های S اعمال می کنیم ، که می تواند میانگین زمان دسترسی را به حداقل برساند. برنامه پخش غیر مسطح تولید شده توسط روش دیسک های پخش [ 9]. در آزمایش خود، ما در نظر می گیریم که هر شی فضایی روی یک دیسک به طور یکنواخت قابل دسترسی است. بنابراین، با توجه به توزیع Zipf با ضریب Zipf φ توسط معادله (2) برای هر دیسک k ، 1≤ k ≤ S ، احتمال دسترسی تقاضا، D _ Pr ( k ) را نیز اختصاص می دهیم . یعنی چولگی صدور کوئری های پنجره در بین دیسک ها اعمال می شود. D _ Pr ( k ) بر نسبت کوئری های صادر شده در بین دیسک ها تأثیر می گذارد. با افزایش مقدار φپرس‌وجوهای بیشتری روی دیسک‌های سریع و نسبتاً کمی روی دیسک‌های کند صادر می‌شوند.

د _ پr ( k ) =( 1 / k )φ∑اسj = 1( 1 / j )φ�_پ�(ک)=(1/ک)�∑�=1اس(1/�)�
علاوه بر این، فرکانس نسبی، Rk ، هر دیسک k، 1 ≤ k ≤ S را با رابطه (3) [ 9 ] اختصاص می دهیم.

آرک/آراس= ( S− k ) Δ+1،آرک/آراس=(اس–ک)Δ+1،

که در آن R S = 1 و Δ عاملی برای کنترل فرکانس های نسبی در بین دیسک ها است. در نتایج تجربی ما، تعداد دیسک‌ها، S ، روی 3، و مقدار ضریب برای فرکانس‌های نسبی، Δ ، روی 1 تنظیم شده است.

در مطالعه شبیه سازی خود، از پارامتر WinLengthRatio برای کنترل منطقه جستجوی یک درخواست پنجره استفاده می کنیم. WinLengthRatio نسبت طول ضلع ناحیه پرس و جو به طول یک نقشه است. با فرض اینکه طول ضلع یک نقشه SL باشد ، منطقه پرس و جو مربعی با طول ضلع برابر با ( SL * WinLengthRatio ) است. علاوه بر این، از آنجایی که روش LER ما برای جلوگیری از بررسی غیرضروری سلول‌های مجاور سلول تعیین‌شده پیشنهاد شده است، از پارامتر Crosspro برای کنترل احتمال عبور یک ناحیه پرس و جو از بیش از یک سلول استفاده می‌کنیم. به عنوان مثال، اگر Crossproبر روی 60% تنظیم شده است، منطقه پرس و جو دارای 60% احتمال دربرگیرنده دو سلول است. جدول 1 پارامترهای مورد استفاده در آزمایشات ما را خلاصه می کند.
برای هر نتیجه آزمایشی، 10000 پرس و جو پنجره در میان مجموعه داده واقعی صادر می شود و نتایج عملکرد میانگین در بین این پرس و جوها است. میانگین زمان دسترسی و تنظیم بر حسب سطل اندازه گیری می شود [ 15 ]. در [ 17 ، 18]، برای ارزیابی مصرف انرژی دستگاه های تلفن همراه، مصرف انرژی CPU و کارت رابط شبکه آنها در نظر گرفته شده است. CPU در حالت فعال و doze به ترتیب 400 میلی وات بر ثانیه و 0.16 میلی وات بر ثانیه مصرف می کند. کارت رابط شبکه در حالت فعال و دوز به ترتیب 750 میلی وات بر ثانیه و 25 میلی وات بر ثانیه مصرف می کند. بنابراین، یک دستگاه تلفن همراه در حالت فعال و دوز به ترتیب 1150 میلی وات بر ثانیه و 25.16 میلی وات بر ثانیه مصرف می کند. در شبیه سازی خود، از همان فرضیه مصرف انرژی یک دستگاه تلفن همراه استفاده می کنیم، همانطور که در [ 17 ، 18 ] استفاده شده است. علاوه بر این، پهنای باند کانال downlink را 1 مگابیت بر ثانیه فرض می کنیم. در نتیجه، میانگین مصرف انرژی، Avg_E ، در واحد ژول (J) برای پردازش درخواست‌های پنجره را می‌توان با معادله (4) تعیین کرد، جایی که Avg_ATو Avg_TT به ترتیب میانگین زمان دسترسی و تنظیم بر حسب ثانیه هستند.

Avg_E = 1150 × Avg_TT + 25.16 × ( Avg_AT – Avg_TT )

4.2. نتایج شبیه سازی

در نتایج تجربی خود، تأثیر پارامترهای عملکرد Crosspro ، WinLengthRatio ، θ و φ را ارزیابی می‌کنیم . با تغییر مقدار هر پارامتر بالا، سایر پارامترها به مقادیر پیش فرض مطابق جدول 1 تنظیم می شوند .

4.2.1. تاثیر Crosspro

در اولین نتیجه تجربی، ما تاثیر Crosspro را با مقادیر 20٪، 40٪، 60٪، 80٪ و 100٪ ارزیابی می کنیم. شکل 7 میانگین زمان دسترسی را نشان می دهد. میانگین زمان دسترسی سه روش با افزایش ارزش Crosspro از 20٪ به 100٪ افزایش می یابد. با افزایش مقدار Crosspro ، احتمال اینکه یک ناحیه پرس و جو از بیش از یک سلول عبور کند افزایش می یابد، بنابراین احتمال بررسی سلول های مجاور افزایش می یابد. در نتیجه، میانگین زمان دسترسی با مقدار Crosspro افزایش می‌یابد . با این حال، شکل 7 نشان می دهد که میانگین زمان دسترسی MLAIN و SSIبا مقدار Crosspro به طور چشمگیری افزایش می یابد ، در حالی که ارزش LER به دلیل استفاده از بزرگترین مستطیل های خالی به آرامی افزایش می یابد. اگر ناحیه پرس و جو به بزرگترین مستطیل خالی محدود شود، LER سلول های دیگر را پردازش نمی کند، بنابراین میانگین زمان دسترسی را به ترتیب 56.4% و 24.2% کاهش می دهد، برخلاف MLAIN و SSI .
جدول 2 میانگین زمان تنظیم مربوطه را فهرست می کند. با افزایش مقدار Crosspro ، احتمال همپوشانی ناحیه پرس و جو با بیش از یک سلول افزایش می یابد. در چنین مواردی، اشیاء مرتبط تری در ناحیه پرس و جو بازیابی می شوند و میانگین زمان تنظیم را افزایش می دهند. این روند را می توان در جدول 2 برای سه روش مشاهده کرد . علاوه بر این، از آنجایی که LER پیشنهادی ما بزرگ‌ترین مستطیل‌های خالی را در شاخص فضایی می‌پذیرد، در صورتی که ناحیه پرس و جو در یک محدوده محدود شود، پردازش پرس و جو پایان می‌یابد. بنابراین، در جدول 2 ، با افزایش مقدار Crosspro ، درصد میانگین زمان تنظیم LER به MLAIN و SSIکاهش می دهد. توجه داشته باشید که در جدول 2 ، درصد کاهش میانگین زمان تنظیم LER در مقایسه با روش های دیگر در پرانتز نشان داده شده است. به طور متوسط، LER کاهش میانگین زمان تنظیم 8.6% و 8.2% را نسبت به MLAIN و SSI ایجاد می کند . علاوه بر این، شکل 8 میانگین مصرف انرژی مربوطه را نشان می دهد. به طور متوسط، LER در مقایسه با MLAIN و SSI به ترتیب 55.8٪ و 23.2٪ کاهش در مصرف انرژی متوسط ​​ایجاد می کند .

4.2.2. تاثیر WinLengthRatio

ما تأثیر WinLengthRatio را با مقادیر 0.08٪، 0.095٪، 0.11٪، 0.125٪ و 0.14٪ ارزیابی کردیم. شکل 9 میانگین زمان دسترسی را نشان می دهد. در بین سه روش، LER کمترین میانگین زمان دسترسی را دارد. علاوه بر این، به طور متوسط، LER به ترتیب 57٪ و 25.4٪ کاهش در میانگین زمان دسترسی نسبت به MLAIN و SSI ایجاد می کند . سه روش افزایش قابل توجهی را برای میانگین زمان دسترسی به عنوان مقدار WinLengthRatio نشان نمی دهندافزایش. این مشاهده را می توان به صورت زیر توضیح داد. گستره اشیاء مربوطه در یک منطقه پرس و جو تأثیر عمیقی بر زمان دسترسی دارد. توجه داشته باشید که دهانه به فاصله بین اولین شی مرتبط و آخرین در کانال بی سیم اشاره دارد. در نتیجه تجربی، گستره اشیاء مربوطه برای مناطق پرس و جو با مقادیر مختلف WinLengthRatio کاملاً مشابه است. بنابراین، میانگین زمان دسترسی برای هر روش با افزایش مقادیر WinLengthRatio اندکی افزایش یافت .
جدول 3 میانگین زمان تنظیم مربوطه را فهرست می کند. میانگین زمان تنظیم برای سه روش با مقدار WinLengthRatio افزایش می یابد . با افزایش مقدار WinLengthRatio ، ناحیه پرس و جو افزایش می یابد و اشیاء مربوطه را بیشتر پوشش می دهد. بنابراین، شاخص های فضایی بیشتری و اشیاء فضایی مربوطه باید مورد بررسی قرار گیرند که منجر به افزایش میانگین زمان تنظیم می شود. با این حال، به دلیل بهره مندی از درج اطلاعات در مورد بزرگترین مستطیل های خالی در ساختار شاخص، LER می تواند زمان تنظیم را مانند حالت مشابه در MLAIN و SSI کاهش دهد . در جدول 3 ، LERکمترین میانگین زمان تنظیم را در بین سه روش دارد. به طور متوسط، LER نسبت به MLAIN و SSI به ترتیب 9.8% و 9.6% کاهش نسبت به میانگین زمان تنظیم ایجاد می کند . علاوه بر این، شکل 10 میانگین مصرف انرژی مربوطه را نشان می دهد. به طور متوسط، روش پیشنهادی ما به ترتیب 55.2% و 24.4% کاهش میانگین مصرف انرژی را نسبت به MLAIN و SSI ایجاد می کند .

4.2.3. تاثیر θ

در سومین نتیجه تجربی، تأثیر θ را با مقادیر 2.1، 2.3، 2.5، 2.7 و 2.9 ارزیابی می کنیم. شکل 11 میانگین زمان دسترسی را نشان می دهد. با افزایش مقدار θ ، احتمال دسترسی اشیاء فضایی کج می شود. یعنی تعداد کمی از اشیاء فضایی در سلول های داغ با احتمال دسترسی بالا بیشتر در چرخه پخش ظاهر می شوند. این منجر به کاهش میانگین زمان دسترسی می شود. در شکل 11 ، با افزایش مقدار θ ، میانگین زمان دسترسی سه روش اندکی کاهش می یابد، به جز موارد MLAIN و SSI ، که برای آنها مقدار θاز 2.1 به 2.3 افزایش می یابد. علاوه بر این، زمان دسترسی MLAIN بسیار طولانی تر از LER و SSI است . در MLAIN ، اشیاء فضایی به دو گروه تقسیم می شوند: گرم و عادی. تمام اشیاء فضایی در گروه داغ بارها در یک فرکانس پخش نسبتاً بالا در یک چرخه پخش ظاهر می شوند. بنابراین، تعداد اشیاء فضایی در این گروه داغ تأثیر زیادی بر اندازه چرخه پخش دارد که زمان دسترسی را تعیین می کند. از سوی دیگر، در هر دو LER و SSI ، اشیاء فضایی به جای تنها دو گروه، به چند گروه با روش BD [ 9 ] تقسیم می‌شوند. در نتیجه، چرخه پخش در هر دوLER و SSI کوچکتر از MLAIN است . بنابراین، زمان دسترسی برای MLAIN بسیار بیشتر از LER و SSI است . علاوه بر این، با استفاده از بزرگترین مستطیل های خالی در شاخص هوای فضایی، LER زمان دسترسی کوتاه تری نسبت به SSI دارد . نتایج تجربی ما نشان می دهد که به طور متوسط، LER میانگین زمان دسترسی را به ترتیب 57.4٪ و 27.6٪ در مقایسه با MLAIN و SSI کاهش می دهد . جدول 4 میانگین زمان تنظیم مربوطه را فهرست می کند. به طور متوسط، LER به ترتیب 9.8% و 9.6% نسبت به میانگین زمان تنظیم تولید می کند.MLAIN و SSI . علاوه بر این، شکل 12 نشان می دهد که به طور متوسط، LER به ترتیب 55.6% و 26.6% کاهش مصرف انرژی را برای MLAIN و SSI ایجاد می کند .

4.2.4. تاثیر φ

در نتیجه آزمایشی نهایی، تأثیر φ را با مقادیر 1، 1.5، 2، 2.5 و 3 ارزیابی می کنیم. شکل 13 میانگین زمان دسترسی را نشان می دهد. چولگی پرس و جوهای پنجره در بین دیسک ها با مقدار φ افزایش می یابد . یعنی تعداد درخواست‌های پنجره صادر شده برای سلول‌های روی دیسک سریع رشد می‌کند و برای سلول‌های روی دیسک کند کاهش می‌یابد. از آنجایی که اشیاء فضایی روی دیسک سریع بارها در یک چرخه پخش ظاهر می شوند، زمان دسترسی برای بازیابی آنها کوتاهتر از دیسک کند است. در نتیجه، با افزایش مقدار φ ، میانگین زمان دسترسی کاهش می یابد . این روند را می توان در سه روش در شکل 13 مشاهده کرد . LERکمترین میانگین زمان دسترسی را در بین این سه روش دارد. به طور متوسط، LER نسبت به MLAIN و SSI به ترتیب 56.2% و 25.2% کاهش نسبت به میانگین زمان دسترسی ایجاد می کند . جدول 5 میانگین زمان تنظیم مربوطه را فهرست می کند. مشابه میانگین زمان دسترسی، میانگین زمان تنظیم با افزایش مقدار φ کاهش می‌یابد . از آنجایی که LER از بزرگترین مستطیل های خالی برای سلول های داغ استفاده می کند تا از بررسی غیرضروری محتوای پخش جلوگیری کند، LER می تواند زمان تنظیم برای پردازش درخواست های پنجره را کاهش دهد. در جدول 5 ، LER کمترین میانگین زمان تنظیم را در بین سه روش دارد، 8.8٪ کمتر از هر دو.MLAIN و SSI . علاوه بر این، شکل 14 نشان می دهد که میانگین مصرف انرژی LER به ترتیب 54.8% و 24.2% کمتر از MLAIN و SSI است .

5. نتیجه گیری ها

این مقاله الگوهای دسترسی اریب مشتریان تلفن همراه را در پیشنهاد یک روش شاخص هوای فضایی برای مدیریت موثر پردازش دسترسی درخواست‌های پنجره در محیط‌های پخش بی‌سیم غیر مسطح در نظر می‌گیرد. روش شاخص هوای فضایی پیشنهادی ما از بزرگترین مستطیل‌های خالی سلول‌های داغ برای کاهش دسترسی غیرضروری سلول‌های نامعتبر پخش شده در کانال بی‌سیم استفاده می‌کند. بنابراین، در حین پردازش درخواست‌های پنجره، دستگاه‌های تلفن همراه می‌توانند از بررسی غیرضروری محتوای پخش صرف نظر کنند و در نتیجه پایان پردازش پرس و جو را تسریع کنند و زمان دسترسی، زمان تنظیم و مصرف انرژی را کاهش دهند. ارزیابی عملکرد نشان می‌دهد که روش شاخص هوای فضایی پیشنهادی ما از روش‌های موجود MLAIN و SSI بهتر عمل می‌کند.از نظر میانگین زمان دسترسی، زمان تنظیم و مصرف انرژی، با میانگین بهبودهای مربوط به 57.4٪، 9.8٪ و 55.8٪ نسبت به MLAIN ، و 27.6٪، 9.6٪ و 26.6٪ نسبت به SSI . کار آینده چگونگی پشتیبانی از انواع مختلف پرس و جوهای فضایی را با استفاده از بزرگترین تکنیک حداکثر مستطیل بررسی خواهد کرد.

منابع

  1. شن، جی اچ. لو، CT; جیان، ام اس; Huang, TC یک شاخص فضایی اریب برای درخواست‌های پنجره پیوسته در محیط‌های پخش بی‌سیم. لکت. یادداشت ها انتخاب کنید. مهندس 2013 ، 253 ، 702-715. [ Google Scholar ]
  2. شن، جی اچ. لو، CT; Jian، روش MS Neighbor-index برای درخواست‌های پنجره پیوسته از طریق بی‌سیم. Appl. مکانیک. ماتر 2013 ، 284 ، 3295-3299. [ Google Scholar ] [ CrossRef ]
  3. دانکد، اس. تکنیک های هشینگ برای پخش در محیط داده های بی سیم. در مجموعه مقالات کنفرانس بین المللی مسائل و چالش ها در تکنیک های محاسبات هوشمند، قاضی آباد، هند، 7-8 فوریه 2014.
  4. گائو، ایکس. یانگ، ی. چن، جی. Lu, X. بهینه سازی جهانی برای پخش داده های بی سیم چند کانالی با طرح نمایه سازی درخت AH. IEEE Trans. محاسبه کنید. 2016 ، 65 ، 2104-2117. [ Google Scholar ] [ CrossRef ]
  5. گوئل، وی. احالوات، AK; گوپتا، MN طرح نمایه سازی هوای توزیع شده برای جستجوی متن کامل در چندین کانال بی سیم. در فن آوری ها و کاربردهای سیستم های هوشمند ; Berretti, S., Thampi, SM, Dasgupta, S., Eds. Springer: برلین، آلمان، 2016; صص 125-135. [ Google Scholar ]
  6. ویشنوی، س. Goel, V. تکنیک نمایه سازی هوا مبتنی بر جدول جدید برای جستجوی متن کامل. در مجموعه مقالات کنفرانس بین المللی هوش محاسباتی و فناوری ارتباطات، قاضی آباد، هند، 13 تا 14 فوریه 2015.
  7. ژونگ، جی. وو، دبلیو. گائو، ایکس. شی، ی. Yue, X. ارزیابی و مقایسه طرح های نمایه سازی مختلف در محیط ارتباطی پخش تک کاناله. بدانید. Inf. سیستم 2014 ، 40 ، 375-409. [ Google Scholar ] [ CrossRef ]
  8. راکوتونیرینی، آ. Obst، P. Loke، SW سازه‌های محاسباتی آگاه اجتماعی. بین المللی J. Soc. اومانیست. محاسبه کنید. 2012 ، 1 ، 375-395. [ Google Scholar ] [ CrossRef ]
  9. آچاریا، اس. فرانکلین، ام. زدونیک، س. همچنین R. Broadcast disk: مدیریت داده برای محیط های ارتباطی نامتقارن. در مجموعه مقالات کنفرانس بین المللی ACM SIGMOD 1995 در مدیریت داده ها، سن خوزه، کالیفرنیا، ایالات متحده آمریکا، 22 تا 25 مه 1995.
  10. شن، جی اچ. Chang، YI یک نمایه سازی توزیع شده اریب برای الگوهای دسترسی اریب در پخش بی سیم. جی. سیست. نرم افزار 2007 ، 80 ، 711-723. [ Google Scholar ] [ CrossRef ]
  11. من، اس. جو، KH; Choi, J. پردازش پرس و جو ویندوز کارآمد با سلول های شبکه گسترده در پخش داده های فضایی بی سیم برای محاسبات فراگیر. تحقیر کردن مهندس علمی 2014 ، 7 ، 785-790. [ Google Scholar ] [ CrossRef ]
  12. پارک، ک. والدوریز، P. یک شاخص شبکه سلسله مراتبی (HGI)، پرس و جوهای فضایی در پخش داده های بی سیم. توزیع کنید. پایگاه های داده موازی 2013 ، 31 ، 413-446. [ Google Scholar ] [ CrossRef ]
  13. Park, K. جستجوی داده‌های مکانی مقیاس‌پذیر کارآمد برای سرویس‌های تلفن همراه آگاه از مکان. J. Inf. علمی مهندس 2015 ، 31 ، 165-178. [ Google Scholar ]
  14. یونگ، اس. Mo, H. یک طرح نمایه سازی فضایی برای جستجوهای خدمات مبتنی بر مکان در یک کانال پخش بی سیم واحد. J. Inf. علمی مهندس 2014 ، 30 ، 1945-1963. [ Google Scholar ]
  15. شن، جی اچ. Chang، YI یک شاخص غیریکنواخت کارآمد در محیط های پخش بی سیم. جی. سیست. نرم افزار 2008 ، 81 ، 2091-2103. [ Google Scholar ] [ CrossRef ]
  16. آهنگ، دی. پارک، K. یک شاخص جزئی برای پخش توزیع شده در شبکه های تلفن همراه بی سیم. Inf. علمی 2016 ، 348 ، 142-152. [ Google Scholar ] [ CrossRef ]
  17. من، اس. Choi, J. MLAIN: طرح نمایه سازی هوای چند سطحی در پخش داده های بی سیم غیر مسطح برای پردازش جستجوی پنجره کارآمد. محاسبه کنید. ریاضی. Appl. 2012 ، 64 ، 1242-1251. [ Google Scholar ] [ CrossRef ]
  18. شن، جی اچ. Jian، MS پردازش پرس و جو فضایی برای الگوهای دسترسی اریب در محیط های پخش داده های بی سیم غیریکنواخت. بین المللی J. Ad Hoc Ubiquitous Comput. 2016 ، در دست چاپ. [ Google Scholar ]
  19. آگاروال، ا. سوری، اس. الگوریتم های سریع برای محاسبه بزرگترین مستطیل خالی. در مجموعه مقالات سومین سمپوزیوم سالانه هندسه محاسباتی، واترلو، ON، کانادا، 8 تا 10 ژوئن 1987.
  20. شن، جی اچ. لو، CT; Mai, CT پردازش کارآمد پرس و جوهای پنجره فضایی برای پخش بی سیم غیر مسطح. در مجموعه مقالات پنجمین کنفرانس بین المللی محاسبات مرزی، توکیو، ژاپن، 13 تا 15 ژوئیه 2016.
  21. من، اس. جوان، هی. چوی، جی. Ouyang, J. یک طرح نمایه سازی هوای جدید برای پرس و جو پنجره در پخش داده های فضایی بی سیم غیر مسطح. J. Commun. خالص. 2011 ، 13 ، 400-407. [ Google Scholar ] [ CrossRef ]
  22. ژنگ، بی. لی، WC; لی، CK; لی، دی ال. Shao, M. یک شاخص فضایی توزیع شده برای پخش داده های بی سیم مستعد خطا. VLDB J. 2009 ، 18 ، 959-986. [ Google Scholar ] [ CrossRef ]
  23. وایدیا، NH; Hameed, S. زمانبندی پخش داده ها در محیط های ارتباطی نامتقارن. سیم. خالص. 1999 ، 5 ، 171-182. [ Google Scholar ] [ CrossRef ]
  24. ژنگ، بی. لی، WC; Lee, DL پرس و جوهای فضایی در سیستم های پخش بی سیم. سیم. خالص. 2004 ، 10 ، 723-736. [ Google Scholar ] [ CrossRef ]
  25. لی، دبلیو. Zheng, B. DSI: یک شاخص فضایی کاملاً توزیع شده برای خدمات پخش بی سیم مبتنی بر مکان. در مجموعه مقالات کنفرانس بین المللی IEEE در مورد سیستم های محاسباتی توزیع شده (ICDCS)، کلمبوس، OH، ایالات متحده، 6 تا 10 ژوئن 2005.
  26. من، م. آهنگ، جی. کیم، اسکی. Hwang, C. یک شاخص توزیع شده مبتنی بر سلول مقاوم در برابر خطا برای خدمات پخش بی سیم مبتنی بر مکان. در مجموعه مقالات پنجمین کارگاه بین المللی ACM در زمینه مهندسی داده برای دسترسی بی سیم و موبایل، شیکاگو، IL، ایالات متحده آمریکا، 25-28 ژوئن 2006.
  27. من، اس. Hwang، H. یک شاخص فضایی دو لایه برای پخش داده‌های فضایی غیرمسطح در هوا. IEICE Trans. اشتراک. 2014 ، 97 ، 2809-2818. [ Google Scholar ] [ CrossRef ]
  28. بله، WG; نواته، اس بی. Omiecinski، E. تخصیص کارآمد داده در چندین کانال در سرورهای پخش. IEEE Trans. محاسبه کنید. 2002 ، 51 ، 1231-1236. [ Google Scholar ]
Ijgi 05 00211 g001 550
شکل 1. مدل سیستم مورد استفاده در روش پیشنهادی.
Ijgi 05 00211 g002 550
شکل 2. تقسیم بندی فضایی بر اساس HC : ( الف ) نقشه اصلی. ( ب ) پارتیشن بندی فضایی در سطح 1. ( ج ) پارتیشن بندی فضایی در سطح 2.
Ijgi 05 00211 g003 550
شکل 3. استفاده از BD برای تولید یک برنامه پخش غیر مسطح: ( الف ) گروه بندی سلول ها به دیسک. ( ب ) تقسیم دیسک به قطعات. ( ج ) تکه‌ها را به هم بریزد تا یک چرخه پخش تشکیل دهد.
Ijgi 05 00211 g004 550
شکل 4. بزرگترین مستطیل خالی سلول H (2،2).
Ijgi 05 00211 g005 550
شکل 5. برنامه پخش غیر مسطح با توزیع شاخص هوای فضایی.
Ijgi 05 00211 g006 550
شکل 6. مجموعه داده واقعی از یونان.
Ijgi 05 00211 g007 550
شکل 7. میانگین زمان دسترسی برای تغییر مقادیر Crosspro .
Ijgi 05 00211 g008 550
شکل 8. میانگین مصرف انرژی برای تغییر مقادیر Crosspro .
Ijgi 05 00211 g009 550
شکل 9. میانگین زمان دسترسی برای تغییر مقادیر WinLengthRatio .
Ijgi 05 00211 g010 550
شکل 10. میانگین مصرف انرژی برای تغییر مقادیر WinLengthRatio .
Ijgi 05 00211 g011 550
شکل 11. میانگین زمان دسترسی برای تغییر مقادیر θ .
Ijgi 05 00211 g012 550
شکل 12. میانگین مصرف انرژی برای تغییر مقادیر θ .
Ijgi 05 00211 g013 550
شکل 13. میانگین زمان دسترسی برای تغییر مقادیر φ .
Ijgi 05 00211 g014 550
شکل 14. میانگین مصرف انرژی برای تغییر مقادیر φ .
جدول
جدول 1. پارامترهای عملکرد و مقادیر پیش فرض آنها.
جدول
جدول 2. میانگین زمان تنظیم برای تغییر مقادیر Crosspro .
جدول
جدول 3. میانگین زمان تنظیم برای تغییر مقادیر WinLengthRatio .
جدول
جدول 4. میانگین زمان تنظیم برای تغییر مقادیر θ .
جدول
جدول 5. میانگین زمان تنظیم برای تغییر مقادیر φ .

;کاربردهای GISمقالات

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

بدون نظر

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

همواره حمایت دانشجویان عزیزمان همراه ما بوده و این سببب شده که گامی محکم به‌سوی ایجاد یک مرجع برای آموزش GIS برداریم. با این امید که بتوانیم قدردان حمایت شما بزرگواران باشیم.

  • خانه
  • آموزش
  • فیلم آموزشی
  • تماس با ما
  • درباره ما
  • وبلاگ
  • سمنان /خیابان کاشانی/ساختمان فناوری اطلاعات/پ 8
  • 09120049370