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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 ינו׳ 2015
אירוע10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2014 - Wroclaw, פולין
משך הזמן: 12 ספט׳ 201412 ספט׳ 2014

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך8847

כנס

כנס10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2014
מדינה/אזורפולין
עירWroclaw
תקופה12/09/1412/09/14

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Exploiting geometry in the SINRk model'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי