خلاصة:
هنگامی که یک کاربر در محیط تحت پوشش یک شبکه بیسیم حرکت میکند، برای دریافت سرویسهای مورد نظر خود ممکن است پیوسته به نقاط دسترسی متعددی متصل شود و عملیات تحویل را موجب شود. وقوع تحویلها میتواند باعث ایجاد اختلال در ارتباط کاربر با شبکه شود. هدف ما در این مقاله کمینهسازی برخط تکرار تحویلها در شبکههای بیسیم با ظرفیت سرویسدهی محدود نقاط دسترسی است. ما این مسئله را با در نظر گرفتن دو حالت روی حرکت کاربران تحلیل میکنیم: 1- هر کاربر بتواند درون شبکه مسیر حرکت دلخواه خود را داشته باشد. 2- کاربران به صورت گروهی و با هم حرکت کنند. در حالت اول با فرض اینکه اگر کاربری به نقطه دسترسی متصل شود تا هنگامی که این نقطه دسترسی برای کاربر مذکور در دسترس است باید اتصال خود را به آن ادامه دهد، ثابت میکنیم که هیچ الگوریتم رقابتی نمیتواند در حالت برخط این مسئله را با ضریب رقابتی محدود حل کند. در حالت دوم ما یک الگوریتم بهینه در حالت برونخط ارائه میدهیم و همچنین در حالت برخط ما یک الگوریتم جدید برای کاهش تعداد تحویلهایی که برای تمام کاربران در شبکه بیسیم رخ میدهد، ارائه میدهیم و ثابت میکنیم ضریب رقابتی الگوریتم ارائه شده، یک حد پایین برای تمامی الگوریتمهای رقابتی در حالت برخط میباشد.
ملخص الجهاز:
در حالت اول با فرض اینکه اگر کاربری به نقطه دسترسی متصل شود تا هنگامی که این نقطه دسترسی برای کاربر مذکور در دسترس است باید اتصال خود را به آن ادامه دهد، ثابت میکنیم که هیچ الگوریتم رقابتی نمیتواند در حالت برخط این مسئله را با ضریب رقابتی محدود حل کند.
در حالت اول با فرض اینکه بعد از اختصاص یک کاربر به یک نقطه دسترسی که توانایی ارائه سرویس به آن را دارد، تا زمانی که این نقطه دسترسی در دسترس این کاربر میباشد اتصال آن به این نقطه دسترسی ادامه دارد، ثابت میکنیم که هیچ الگوریتمی با ضریب رقابتی محدود نمیتواند به صورت برخط این مسئله را حل کند.
در این قسمت ما با فرض "پیوستگی ارتباط" که به صورت زیر تعریف میشود: اگر کاربری به نقطه دسترسی متصل شود تا هنگامی که قدرت سیگنال دریافتی از این نقطه دسترسی از یک حد آستانه مشخص کمتر نشود کاربر مذکور باید اتصال خود را به آن ادامه دهد [4، 9]، مسئله حرکت دلخواه کاربران را بررسی میکنیم.
با توجه به این مثال با فرض پیوستگی ارتباط برای هر کاربر، هیچ الگوریتمی چه در حالت متمرکز چه غیرمتمرکز نمیتواند به صورت رقابتی مسئله کمینهسازی برخط تحویلها با حرکت دلخواه کاربران و ظرفیت محدود نقاط دسترسی را حل کند.
الگوریتم برونخط به صورت زیر کار میکند: برای این منظور ما در هر بش زمانی و برای هر نقطه دسترسی مانند مقداری را به عنوان "اندازه " به صورت زیر تعریف میکنیم: اندازه در برش زمانی برابر است با تعداد برشهای زمانی بعد از برش زمانی که به صورت پیوسته برای کاربر در دسترس باشد.