Treffer: Minimum delay Data Gathering in Radio Networks

Title:
Minimum delay Data Gathering in Radio Networks
Authors:
Bermond, Jean-Claude, Nisse, Nicolas, Reyes, Patricio, Rivano, Hervé
Contributors:
Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Centre Inria d'Université Côte d'Azur, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA), Smart Wireless Networking (SWING), Centre Inria de l'Université Grenoble Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)
Source:
ADHOC-NOW 2009 - 8th international conference on Ad Hoc Networks and Wireless. :69-82
Publisher Information:
CCSD; Springer Verlag, 2009.
Publication Year:
2009
Collection:
collection:UNICE
collection:CNRS
collection:INRIA
collection:INSA-LYON
collection:INRIA-SOPHIA
collection:INRIA-RHA
collection:I3S
collection:INRIASO
collection:INRIA_TEST
collection:TESTALAIN1
collection:INRIA2
collection:LABEXIMU
collection:UNIV-COTEDAZUR
collection:INRIA-RENGRE
collection:CITI
collection:INSA-GROUPE
collection:UDL
collection:TEST-NICE
Subject Terms:
ACM: C.: Computer Systems Organization, C.2: COMPUTER-COMMUNICATION NETWORKS, C.2.2: Network Protocols, C.2.2.3: Routing protocols, ACM: G.: Mathematics of Computing, G.2: DISCRETE MATHEMATICS, G.2.2: Graph Theory, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.2: Nonnumerical Algorithms and Problems, [INFO.INFO-IU]Computer Science [cs], Ubiquitous Computing, [INFO.INFO-NI]Computer Science [cs], Networking and Internet Architecture [cs.NI], [INFO.INFO-DS]Computer Science [cs], Data Structures and Algorithms [cs.DS]
Subject Geographic:
Murcia, Spain
Original Identifier:
HAL:
Document Type:
Konferenz conferenceObject<br />Conference papers
Language:
English
ISBN:
978-3-642-04382-6
Relation:
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-04383-3_6
DOI:
10.1007/978-3-642-04383-3_6
Access URL:
https://inria.hal.science/inria-00505522
https://inria.hal.science/inria-00505522v1/document
https://inria.hal.science/inria-00505522v1/file/1777-BNRR09b-gatheringradioadHocNow.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00505522v1
Database:
HAL

Weitere Informationen

The aim of this paper is to design efficient gathering algorithms (data collection) in a Base Station of a wireless multi hop grid network when interferences constraints are present. We suppose the time is slotted and that during one time slot (step) each node can transmit to one of its neighbours at most one data item. Each device is equipped with a half duplex interface; so a node cannot both receive and transmit simultaneously. During a step only non interfering transmissions can be done. In other words, the non interfering calls done during a step will form a matching. The aim is to minimize the number of steps needed to send to the base station a set of messages generated by the nodes, this completion time is also denoted makespan of the call scheduling. The best known algorithm for open-grids was a multiplicative 1.5-approximation algorithm [Revah, Segal 07]. In such topologies, we give a very simple +2 approximation algorithm and then a more involved +1 approximation algorithm. Moreover, our algorithms work when no buffering is allowed in intermediary nodes, i.e., when a node receives a message at some step, it must transmit it during the next step.