Exploiting geometry in the SINRk model

Rom Aschner, Gui Citovsky, Matthew J. Katz

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We introduce the SINRk model, which is a practical version of the SINR model. In the SINRk model, in order to determine whether s’s signal is received at c, where s is a sender and c is a receiver, one only considers the k most significant senders w.r.t. to c (other than s). Assuming uniform power, these are the k closest senders to c (other than s). Under this model, we consider the well-studied scheduling problem: Given a set L of sender-receiver requests, find a partition of L into a minimum number of subsets (rounds), such that in each subset all requests can be satisfied simultaneously. We present an O(1)- approximation algorithm for the scheduling problem (under the SINRk model). For comparison, the best known approximation ratio under the SINR model is O(log n). We also present an O(1)-approximation algorithm for the maximum capacity problem (i.e., for the single round problem), obtaining a constant of approximation which is considerably better than those obtained under the SINR model. Finally, for the special case where k = 1, we present a PTAS for the maximum capacity problem. Our algorithms are based on geometric analysis of the SINRk model.

اللغة الأصليةإنجليزيّة أمريكيّة
عنوان منشور المضيفAlgorithms for Sensor Systems - 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2014, Revised Selected Papers
المحررونJie Gao, Alon Efrat, Sándor P. Fekete, Yanyong Zhang
ناشرSpringer Verlag
الصفحات125-135
عدد الصفحات11
رقم المعيار الدولي للكتب (الإلكتروني)9783662460177
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يناير 2015
الحدث10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2014 - Wroclaw, بولندا
المدة: ١٢ سبتمبر ٢٠١٤١٢ سبتمبر ٢٠١٤

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت8847

!!Conference

!!Conference10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2014
الدولة/الإقليمبولندا
المدينةWroclaw
المدة١٢/٠٩/١٤١٢/٠٩/١٤

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “Exploiting geometry in the SINRk model'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا