Optimal gathering protocols on paths under interference constraints
Identifieur interne : 001996 ( Main/Exploration ); précédent : 001995; suivant : 001997Optimal gathering protocols on paths under interference constraints
Auteurs : RBID : Pascal:10-0048776Descripteurs français
- Pascal (Inist)
- Wicri :
- topic : Protocole.
English descriptors
- KwdEn :
Abstract
We study the problem of gathering information from the nodes of a multi-hop radio network into a predefined destination node under reachability and interference constraints. In such a network, a node is able to send messages to other nodes within reception distance, but doing so it might create interference with other communications. Thus, a message can only be properly received if the receiver is reachable from the sender and there is no interference from another message being transmitted simultaneously. The network is modeled as a graph, where the vertices represent the nodes of the network and the edges, the possible communications. The interference constraint is modeled by a fixed integer d ≥ 1, which implies that nodes within distance d in the graph from one sender cannot receive messages from another node. In this paper, we suppose that each node has one unit-length message to transmit and, furthermore, we suppose that it takes one unit of time (slot) to transmit a unit-length message and during such a slot we can have only calls which do not interfere (called compatible calls). A set of compatible calls is referred to as a round. We give protocols and lower bounds on the minimum number of rounds for the gathering problem when the network is a path and the destination node is either at one end or at the center of the path. These protocols are shown to be optimal for any d in the first case, and for 1 ≤ d ≤ 4, in the second case.
Links toward previous steps (curation, corpus...)
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Optimal gathering protocols on paths under interference constraints</title><author><name sortKey="Bermond, Jean Claude" uniqKey="Bermond J">Jean-Claude Bermond</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>MASCOTTE, joint project 13S (CNRS-UNSA) and INRIA, 2004 Route des Lucioles, BP 93</s1><s2>06902 Sophia-Antipolis</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Provence-Alpes-Côte d'Azur</region><settlement type="city">Sophia-Antipolis</settlement></placeName></affiliation></author><author><name sortKey="Correa, Ricardo C" uniqKey="Correa R">Ricardo C. Correa</name><affiliation wicri:level="2"><inist:fA14 i1="02"><s1>Universidade Federal do Ceará. Mestrado e Doutorado em Ciência da Computação, Campus do Pici, Bloco 910</s1><s2>60455-760 Fortaleza, CE</s2><s3>BRA</s3><sZ>2 aut.</sZ></inist:fA14><country>Brésil</country><placeName><region type="state">Ceará</region></placeName></affiliation></author><author><name>MINLI YU</name><affiliation wicri:level="1"><inist:fA14 i1="03"><s1>University College of the Fraser Valley, Department of Mathematics and Statistics</s1><s2>Abbotsford. BC, V2S 4N2</s2><s3>CAN</s3><sZ>3 aut.</sZ></inist:fA14><country>Canada</country><wicri:noRegion>Abbotsford. BC, V2S 4N2</wicri:noRegion></affiliation></author></titleStmt><publicationStmt><idno type="inist">10-0048776</idno><date when="2009">2009</date><idno type="stanalyst">PASCAL 10-0048776 INIST</idno><idno type="RBID">Pascal:10-0048776</idno><idno type="wicri:Area/Main/Corpus">001964</idno><idno type="wicri:Area/Main/Curation">000F75</idno><idno type="wicri:Area/Main/Exploration">001996</idno></publicationStmt><seriesStmt><idno type="ISSN">0012-365X</idno><title level="j" type="abbreviated">Discrete math.</title><title level="j" type="main">Discrete mathematics</title></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term><term>Combinatorics</term><term>Communication</term><term>Constraint</term><term>Discrete mathematics</term><term>Distance graph</term><term>Integer</term><term>Interference</term><term>Lower bound</term><term>Node</term><term>Optimal path</term><term>Protocols</term><term>Radio</term><term>Reachability</term><term>Unit</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Chemin optimal</term><term>Protocole</term><term>Interférence</term><term>Contrainte</term><term>Noeud</term><term>Radio</term><term>Atteignabilité</term><term>Communication</term><term>Nombre entier</term><term>Graphe distance</term><term>Unité</term><term>Borne inférieure</term><term>Algorithme</term><term>Mathématiques discrètes</term><term>Combinatoire</term><term>68R10</term><term>68Wxx</term></keywords><keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Protocole</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We study the problem of gathering information from the nodes of a multi-hop radio network into a predefined destination node under reachability and interference constraints. In such a network, a node is able to send messages to other nodes within reception distance, but doing so it might create interference with other communications. Thus, a message can only be properly received if the receiver is reachable from the sender and there is no interference from another message being transmitted simultaneously. The network is modeled as a graph, where the vertices represent the nodes of the network and the edges, the possible communications. The interference constraint is modeled by a fixed integer d ≥ 1, which implies that nodes within distance d in the graph from one sender cannot receive messages from another node. In this paper, we suppose that each node has one unit-length message to transmit and, furthermore, we suppose that it takes one unit of time (slot) to transmit a unit-length message and during such a slot we can have only calls which do not interfere (called compatible calls). A set of compatible calls is referred to as a round. We give protocols and lower bounds on the minimum number of rounds for the gathering problem when the network is a path and the destination node is either at one end or at the center of the path. These protocols are shown to be optimal for any d in the first case, and for 1 ≤ d ≤ 4, in the second case.</div></front></TEI><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0012-365X</s0></fA01><fA02 i1="01"><s0>DSMHA4</s0></fA02><fA03 i2="1"><s0>Discrete math.</s0></fA03><fA05><s2>309</s2></fA05><fA06><s2>18</s2></fA06><fA08 i1="01" i2="1" l="ENG"><s1>Optimal gathering protocols on paths under interference constraints</s1></fA08><fA09 i1="01" i2="1" l="ENG"><s1>Combinatorics 2006, A Meeting in Celebration of Pavol Hell's 60th Birthday (May 1-5, 2006)</s1></fA09><fA11 i1="01" i2="1"><s1>BERMOND (Jean-Claude)</s1></fA11><fA11 i1="02" i2="1"><s1>CORREA (Ricardo C.)</s1></fA11><fA11 i1="03" i2="1"><s1>MINLI YU</s1></fA11><fA12 i1="01" i2="1"><s1>HORAK (Peter)</s1><s9>ed.</s9></fA12><fA12 i1="02" i2="1"><s1>STACHO (Ladislav)</s1><s9>ed.</s9></fA12><fA14 i1="01"><s1>MASCOTTE, joint project 13S (CNRS-UNSA) and INRIA, 2004 Route des Lucioles, BP 93</s1><s2>06902 Sophia-Antipolis</s2><s3>FRA</s3><sZ>1 aut.</sZ></fA14><fA14 i1="02"><s1>Universidade Federal do Ceará. Mestrado e Doutorado em Ciência da Computação, Campus do Pici, Bloco 910</s1><s2>60455-760 Fortaleza, CE</s2><s3>BRA</s3><sZ>2 aut.</sZ></fA14><fA14 i1="03"><s1>University College of the Fraser Valley, Department of Mathematics and Statistics</s1><s2>Abbotsford. BC, V2S 4N2</s2><s3>CAN</s3><sZ>3 aut.</sZ></fA14><fA15 i1="01"><s1>Interdisciplinary Arts and Sciences, University of Washington</s1><s2>Tacoma, WA</s2><s3>USA</s3><sZ>1 aut.</sZ></fA15><fA15 i1="02"><s1>Department of Mathematics, Simon Fraser University</s1><s2>Burnaby, BC</s2><s3>CAN</s3><sZ>2 aut.</sZ></fA15><fA20><s1>5574-5587</s1></fA20><fA21><s1>2009</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA43 i1="01"><s1>INIST</s1><s2>15322</s2><s5>354000170270050090</s5></fA43><fA44><s0>0000</s0><s1>© 2010 INIST-CNRS. All rights reserved.</s1></fA44><fA45><s0>16 ref.</s0></fA45><fA47 i1="01" i2="1"><s0>10-0048776</s0></fA47><fA60><s1>P</s1></fA60><fA61><s0>A</s0></fA61><fA64 i1="01" i2="1"><s0>Discrete mathematics</s0></fA64><fA66 i1="01"><s0>NLD</s0></fA66><fC01 i1="01" l="ENG"><s0>We study the problem of gathering information from the nodes of a multi-hop radio network into a predefined destination node under reachability and interference constraints. In such a network, a node is able to send messages to other nodes within reception distance, but doing so it might create interference with other communications. Thus, a message can only be properly received if the receiver is reachable from the sender and there is no interference from another message being transmitted simultaneously. The network is modeled as a graph, where the vertices represent the nodes of the network and the edges, the possible communications. The interference constraint is modeled by a fixed integer d ≥ 1, which implies that nodes within distance d in the graph from one sender cannot receive messages from another node. In this paper, we suppose that each node has one unit-length message to transmit and, furthermore, we suppose that it takes one unit of time (slot) to transmit a unit-length message and during such a slot we can have only calls which do not interfere (called compatible calls). A set of compatible calls is referred to as a round. We give protocols and lower bounds on the minimum number of rounds for the gathering problem when the network is a path and the destination node is either at one end or at the center of the path. These protocols are shown to be optimal for any d in the first case, and for 1 ≤ d ≤ 4, in the second case.</s0></fC01><fC02 i1="01" i2="X"><s0>001A02C</s0></fC02><fC02 i1="02" i2="X"><s0>001A02B01</s0></fC02><fC02 i1="03" i2="X"><s0>001D02A06</s0></fC02><fC02 i1="04" i2="X"><s0>001D02A05</s0></fC02><fC03 i1="01" i2="X" l="FRE"><s0>Chemin optimal</s0><s5>17</s5></fC03><fC03 i1="01" i2="X" l="ENG"><s0>Optimal path</s0><s5>17</s5></fC03><fC03 i1="01" i2="X" l="SPA"><s0>Camino óptimo</s0><s5>17</s5></fC03><fC03 i1="02" i2="X" l="FRE"><s0>Protocole</s0><s2>563</s2><s5>18</s5></fC03><fC03 i1="02" i2="X" l="ENG"><s0>Protocols</s0><s2>563</s2><s5>18</s5></fC03><fC03 i1="02" i2="X" l="SPA"><s0>Protocolo</s0><s2>563</s2><s5>18</s5></fC03><fC03 i1="03" i2="X" l="FRE"><s0>Interférence</s0><s5>19</s5></fC03><fC03 i1="03" i2="X" l="ENG"><s0>Interference</s0><s5>19</s5></fC03><fC03 i1="03" i2="X" l="SPA"><s0>Interferencia</s0><s5>19</s5></fC03><fC03 i1="04" i2="X" l="FRE"><s0>Contrainte</s0><s5>20</s5></fC03><fC03 i1="04" i2="X" l="ENG"><s0>Constraint</s0><s5>20</s5></fC03><fC03 i1="04" i2="X" l="SPA"><s0>Coacción</s0><s5>20</s5></fC03><fC03 i1="05" i2="X" l="FRE"><s0>Noeud</s0><s5>21</s5></fC03><fC03 i1="05" i2="X" l="ENG"><s0>Node</s0><s5>21</s5></fC03><fC03 i1="05" i2="X" l="SPA"><s0>Nudo</s0><s5>21</s5></fC03><fC03 i1="06" i2="X" l="FRE"><s0>Radio</s0><s5>22</s5></fC03><fC03 i1="06" i2="X" l="ENG"><s0>Radio</s0><s5>22</s5></fC03><fC03 i1="06" i2="X" l="SPA"><s0>Radio</s0><s5>22</s5></fC03><fC03 i1="07" i2="X" l="FRE"><s0>Atteignabilité</s0><s5>23</s5></fC03><fC03 i1="07" i2="X" l="ENG"><s0>Reachability</s0><s5>23</s5></fC03><fC03 i1="07" i2="X" l="SPA"><s0>Asequibilidad</s0><s5>23</s5></fC03><fC03 i1="08" i2="X" l="FRE"><s0>Communication</s0><s5>24</s5></fC03><fC03 i1="08" i2="X" l="ENG"><s0>Communication</s0><s5>24</s5></fC03><fC03 i1="08" i2="X" l="SPA"><s0>Comunicación</s0><s5>24</s5></fC03><fC03 i1="09" i2="X" l="FRE"><s0>Nombre entier</s0><s5>25</s5></fC03><fC03 i1="09" i2="X" l="ENG"><s0>Integer</s0><s5>25</s5></fC03><fC03 i1="09" i2="X" l="SPA"><s0>Entero</s0><s5>25</s5></fC03><fC03 i1="10" i2="X" l="FRE"><s0>Graphe distance</s0><s5>26</s5></fC03><fC03 i1="10" i2="X" l="ENG"><s0>Distance graph</s0><s5>26</s5></fC03><fC03 i1="10" i2="X" l="SPA"><s0>Grapho distancia</s0><s5>26</s5></fC03><fC03 i1="11" i2="X" l="FRE"><s0>Unité</s0><s5>27</s5></fC03><fC03 i1="11" i2="X" l="ENG"><s0>Unit</s0><s5>27</s5></fC03><fC03 i1="11" i2="X" l="SPA"><s0>Unidad</s0><s5>27</s5></fC03><fC03 i1="12" i2="X" l="FRE"><s0>Borne inférieure</s0><s5>28</s5></fC03><fC03 i1="12" i2="X" l="ENG"><s0>Lower bound</s0><s5>28</s5></fC03><fC03 i1="12" i2="X" l="SPA"><s0>Cota inferior</s0><s5>28</s5></fC03><fC03 i1="13" i2="X" l="FRE"><s0>Algorithme</s0><s5>29</s5></fC03><fC03 i1="13" i2="X" l="ENG"><s0>Algorithm</s0><s5>29</s5></fC03><fC03 i1="13" i2="X" l="SPA"><s0>Algoritmo</s0><s5>29</s5></fC03><fC03 i1="14" i2="X" l="FRE"><s0>Mathématiques discrètes</s0><s5>30</s5></fC03><fC03 i1="14" i2="X" l="ENG"><s0>Discrete mathematics</s0><s5>30</s5></fC03><fC03 i1="14" i2="X" l="SPA"><s0>Matemáticas discretas</s0><s5>30</s5></fC03><fC03 i1="15" i2="X" l="FRE"><s0>Combinatoire</s0><s5>31</s5></fC03><fC03 i1="15" i2="X" l="ENG"><s0>Combinatorics</s0><s5>31</s5></fC03><fC03 i1="15" i2="X" l="SPA"><s0>Combinatoria</s0><s5>31</s5></fC03><fC03 i1="16" i2="X" l="FRE"><s0>68R10</s0><s4>INC</s4><s5>70</s5></fC03><fC03 i1="17" i2="X" l="FRE"><s0>68Wxx</s0><s4>INC</s4><s5>71</s5></fC03><fN21><s1>032</s1></fN21><fN44 i1="01"><s1>OTO</s1></fN44><fN82><s1>OTO</s1></fN82></pA></standard></inist></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=FranceBresilV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001996 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001996 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= *** parameter Area/wikiCode missing ***
|area= FranceBresilV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= Pascal:10-0048776
|texte= Optimal gathering protocols on paths under interference constraints
}}
| This area was generated with Dilib version V0.6.01. |  |