Resolving SINR queries in a dynamic setting

Boris Aronov, Gali Bar-On, Matthew J. Katz

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We consider a set of transmitters broadcasting simultaneously on the same frequency under the SINR model. Transmission power may vary from one transmitter to another, and a signal's strength decreases (path loss or path attenuation) by some constant power α of the distance traveled. Roughly, a receiver at a given location can hear a specific transmitter only if the transmitter's signal is stronger than the signal of all other transmitters, combined. An SINR query is to determine whether a receiver at a given location can hear any transmitter, and if yes, which one. An approximate answer to an SINR query is such that one gets a definite yes or definite no, when the ratio between the strongest signal and all other signals combined is well above or well below the reception threshold, while the answer in the intermediate range is allowed to be either yes or no. We describe several compact data structures that support approximate SINR queries in the plane in a dynamic context, i.e., where both queries and updates (insertion or deletion of a transmitter) can be performed e ciently.

    Original languageEnglish (US)
    Title of host publication45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
    EditorsChristos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959770767
    DOIs
    StatePublished - Jul 1 2018
    Event45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic
    Duration: Jul 9 2018Jul 13 2018

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    Volume107
    ISSN (Print)1868-8969

    Other

    Other45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
    CountryCzech Republic
    CityPrague
    Period7/9/187/13/18

    Keywords

    • Deletion
    • Dynamic insertion
    • Interference cancellation
    • Range searching
    • SINR
    • Wireless networks

    ASJC Scopus subject areas

    • Software

    Fingerprint Dive into the research topics of 'Resolving SINR queries in a dynamic setting'. Together they form a unique fingerprint.

    Cite this