On the Power Assignment Problem in Radio Networks View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2004-04

AUTHORS

Andrea E.F. Clementi, Paolo Penna, Riccardo Silvestri

ABSTRACT

Given a finite set S of points (i.e. the stations of a radio network) on a d-dimensional Euclidean space and a positive integer 1≤h≤|S|−1, the MIN DD H-RANGE ASSIGNMENT problem consists of assigning transmission ranges to the stations so as to minimize the total power consumption, provided that the transmission ranges of the stations ensure the communication between any pair of stations in at most h hops. Two main issues related to this problem are considered in this paper: the trade-off between the power consumption and the number of hops; the computational complexity of the MIN DD H-RANGE ASSIGNMENT problem. As for the first question, we provide a lower bound on the minimum power consumption of stations on the plane for constant h. The lower bound is a function of |S|, h and the minimum distance over all the pairs of stations in S. Then, we derive a constructive upper bound as a function of |S|, h and the maximum distance over all pairs of stations in S (i.e. the diameter of S). It turns out that when the minimum distance between any two stations is “not too small” (i.e. well spread instances) the upper bound matches the lower bound. Previous results for this problem were known only for very special 1-dimensional configurations (i.e., when points are arranged on a line at unitary distance) [Kirousis, Kranakis, Krizanc and Pelc, 1997]. As for the second question, we observe that the tightness of our upper bound implies that MIN 2D H-RANGE ASSIGNMENT restricted to well spread instances admits a polynomial time approximation algorithm. Then, we also show that the same approximation result can be obtained for random instances. On the other hand, we prove that for h=|S|−1 (i.e. the unbounded case) MIN 2D H-RANGE ASSIGNMENT is NP-hard and MIN 3D H-RANGE ASSIGNMENT is APX-complete. More... »

PAGES

125-140

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/b:mone.0000013624.32948.87

DOI

http://dx.doi.org/10.1023/b:mone.0000013624.32948.87

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1031720391


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Rome Tor Vergata", 
          "id": "https://www.grid.ac/institutes/grid.6530.0", 
          "name": [
            "Dipartimento di Matematica, Universit\u00e0 di Roma \u201cTor Vergata\u201d, via della Ricerca Scientifica, I-00133, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Clementi", 
        "givenName": "Andrea E.F.", 
        "id": "sg:person.011027660123.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Institute for Theoretical Computer Science, ETH Zentrum, CH-8092, Z\u00fcrich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Penna", 
        "givenName": "Paolo", 
        "id": "sg:person.013624103516.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of L'Aquila", 
          "id": "https://www.grid.ac/institutes/grid.158820.6", 
          "name": [
            "Dipartimento di Matematica Pura e Applicata, Universit\u00e0 de L'Aquila via Vetoio, I-67010, Cappito (AQ), Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Silvestri", 
        "givenName": "Riccardo", 
        "id": "sg:person.012430640403.64", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02086606", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024228802", 
          "https://doi.org/10.1007/bf02086606"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02086606", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024228802", 
          "https://doi.org/10.1007/bf02086606"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/174644.174650", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025317817"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01262051", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033331378", 
          "https://doi.org/10.1007/bf01262051"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01262051", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033331378", 
          "https://doi.org/10.1007/bf01262051"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-1784-8_33", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033694105", 
          "https://doi.org/10.1007/978-1-4612-1784-8_33"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-1784-8_33", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033694105", 
          "https://doi.org/10.1007/978-1-4612-1784-8_33"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(91)90023-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043200457"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/18.133276", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061098657"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/26.52656", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061137305"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/26.681417", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061137967"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/90.222924", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061247023"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/90.282605", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061247076"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tc.1981.6312176", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061532644"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.21236/ada126696", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091745570"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2004-04", 
    "datePublishedReg": "2004-04-01", 
    "description": "Given a finite set S of points (i.e. the stations of a radio network) on a d-dimensional Euclidean space and a positive integer 1\u2264h\u2264|S|\u22121, the MIN DD H-RANGE ASSIGNMENT problem consists of assigning transmission ranges to the stations so as to minimize the total power consumption, provided that the transmission ranges of the stations ensure the communication between any pair of stations in at most h hops. Two main issues related to this problem are considered in this paper: the trade-off between the power consumption and the number of hops; the computational complexity of the MIN DD H-RANGE ASSIGNMENT problem. As for the first question, we provide a lower bound on the minimum power consumption of stations on the plane for constant h. The lower bound is a function of |S|, h and the minimum distance over all the pairs of stations in S. Then, we derive a constructive upper bound as a function of |S|, h and the maximum distance over all pairs of stations in S (i.e. the diameter of S). It turns out that when the minimum distance between any two stations is \u201cnot too small\u201d (i.e. well spread instances) the upper bound matches the lower bound. Previous results for this problem were known only for very special 1-dimensional configurations (i.e., when points are arranged on a line at unitary distance) [Kirousis, Kranakis, Krizanc and Pelc, 1997]. As for the second question, we observe that the tightness of our upper bound implies that MIN 2D H-RANGE ASSIGNMENT restricted to well spread instances admits a polynomial time approximation algorithm. Then, we also show that the same approximation result can be obtained for random instances. On the other hand, we prove that for h=|S|\u22121 (i.e. the unbounded case) MIN 2D H-RANGE ASSIGNMENT is NP-hard and MIN 3D H-RANGE ASSIGNMENT is APX-complete.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1023/b:mone.0000013624.32948.87", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136741", 
        "issn": [
          "1383-469X", 
          "1572-8153"
        ], 
        "name": "Mobile Networks and Applications", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "9"
      }
    ], 
    "name": "On the Power Assignment Problem in Radio Networks", 
    "pagination": "125-140", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "971be196d6de46dc7e3ccb91af93c75f6bc77cc63d3f47aff91e2ad986e187e2"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/b:mone.0000013624.32948.87"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031720391"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/b:mone.0000013624.32948.87", 
      "https://app.dimensions.ai/details/publication/pub.1031720391"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T13:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8659_00000506.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1023%2FB%3AMONE.0000013624.32948.87"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1023/b:mone.0000013624.32948.87'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1023/b:mone.0000013624.32948.87'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/b:mone.0000013624.32948.87'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/b:mone.0000013624.32948.87'


 

This table displays all metadata directly associated to this object as RDF triples.

120 TRIPLES      21 PREDICATES      39 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/b:mone.0000013624.32948.87 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nd47fc16096f4445cb6b35be52f7e149f
4 schema:citation sg:pub.10.1007/978-1-4612-1784-8_33
5 sg:pub.10.1007/bf01262051
6 sg:pub.10.1007/bf02086606
7 https://doi.org/10.1016/0022-0000(91)90023-x
8 https://doi.org/10.1109/18.133276
9 https://doi.org/10.1109/26.52656
10 https://doi.org/10.1109/26.681417
11 https://doi.org/10.1109/90.222924
12 https://doi.org/10.1109/90.282605
13 https://doi.org/10.1109/tc.1981.6312176
14 https://doi.org/10.1145/174644.174650
15 https://doi.org/10.21236/ada126696
16 schema:datePublished 2004-04
17 schema:datePublishedReg 2004-04-01
18 schema:description Given a finite set S of points (i.e. the stations of a radio network) on a d-dimensional Euclidean space and a positive integer 1≤h≤|S|−1, the MIN DD H-RANGE ASSIGNMENT problem consists of assigning transmission ranges to the stations so as to minimize the total power consumption, provided that the transmission ranges of the stations ensure the communication between any pair of stations in at most h hops. Two main issues related to this problem are considered in this paper: the trade-off between the power consumption and the number of hops; the computational complexity of the MIN DD H-RANGE ASSIGNMENT problem. As for the first question, we provide a lower bound on the minimum power consumption of stations on the plane for constant h. The lower bound is a function of |S|, h and the minimum distance over all the pairs of stations in S. Then, we derive a constructive upper bound as a function of |S|, h and the maximum distance over all pairs of stations in S (i.e. the diameter of S). It turns out that when the minimum distance between any two stations is “not too small” (i.e. well spread instances) the upper bound matches the lower bound. Previous results for this problem were known only for very special 1-dimensional configurations (i.e., when points are arranged on a line at unitary distance) [Kirousis, Kranakis, Krizanc and Pelc, 1997]. As for the second question, we observe that the tightness of our upper bound implies that MIN 2D H-RANGE ASSIGNMENT restricted to well spread instances admits a polynomial time approximation algorithm. Then, we also show that the same approximation result can be obtained for random instances. On the other hand, we prove that for h=|S|−1 (i.e. the unbounded case) MIN 2D H-RANGE ASSIGNMENT is NP-hard and MIN 3D H-RANGE ASSIGNMENT is APX-complete.
19 schema:genre research_article
20 schema:inLanguage en
21 schema:isAccessibleForFree true
22 schema:isPartOf N983365bc1e354251abdfe9b727cc93cd
23 Nce48b4e907364d1ea0729857460a6393
24 sg:journal.1136741
25 schema:name On the Power Assignment Problem in Radio Networks
26 schema:pagination 125-140
27 schema:productId N510033db5c8e40a197ac02486385d1a2
28 N744d8d1e19f34fa9ad2efa26d6990f42
29 N8c00792aaf4043bc950ebb8a6f8cac72
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031720391
31 https://doi.org/10.1023/b:mone.0000013624.32948.87
32 schema:sdDatePublished 2019-04-10T13:14
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N066fb28112514e3cb73f1341a2c7f263
35 schema:url http://link.springer.com/10.1023%2FB%3AMONE.0000013624.32948.87
36 sgo:license sg:explorer/license/
37 sgo:sdDataset articles
38 rdf:type schema:ScholarlyArticle
39 N066fb28112514e3cb73f1341a2c7f263 schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N155bcfdae7164a5b8bc3418ff2564114 rdf:first sg:person.012430640403.64
42 rdf:rest rdf:nil
43 N510033db5c8e40a197ac02486385d1a2 schema:name doi
44 schema:value 10.1023/b:mone.0000013624.32948.87
45 rdf:type schema:PropertyValue
46 N744d8d1e19f34fa9ad2efa26d6990f42 schema:name dimensions_id
47 schema:value pub.1031720391
48 rdf:type schema:PropertyValue
49 N8c00792aaf4043bc950ebb8a6f8cac72 schema:name readcube_id
50 schema:value 971be196d6de46dc7e3ccb91af93c75f6bc77cc63d3f47aff91e2ad986e187e2
51 rdf:type schema:PropertyValue
52 N983365bc1e354251abdfe9b727cc93cd schema:issueNumber 2
53 rdf:type schema:PublicationIssue
54 Naed251e32a254168a08ed52143c1c596 rdf:first sg:person.013624103516.76
55 rdf:rest N155bcfdae7164a5b8bc3418ff2564114
56 Nce48b4e907364d1ea0729857460a6393 schema:volumeNumber 9
57 rdf:type schema:PublicationVolume
58 Nd47fc16096f4445cb6b35be52f7e149f rdf:first sg:person.011027660123.21
59 rdf:rest Naed251e32a254168a08ed52143c1c596
60 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
61 schema:name Mathematical Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
64 schema:name Pure Mathematics
65 rdf:type schema:DefinedTerm
66 sg:journal.1136741 schema:issn 1383-469X
67 1572-8153
68 schema:name Mobile Networks and Applications
69 rdf:type schema:Periodical
70 sg:person.011027660123.21 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
71 schema:familyName Clementi
72 schema:givenName Andrea E.F.
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21
74 rdf:type schema:Person
75 sg:person.012430640403.64 schema:affiliation https://www.grid.ac/institutes/grid.158820.6
76 schema:familyName Silvestri
77 schema:givenName Riccardo
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64
79 rdf:type schema:Person
80 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
81 schema:familyName Penna
82 schema:givenName Paolo
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
84 rdf:type schema:Person
85 sg:pub.10.1007/978-1-4612-1784-8_33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033694105
86 https://doi.org/10.1007/978-1-4612-1784-8_33
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/bf01262051 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033331378
89 https://doi.org/10.1007/bf01262051
90 rdf:type schema:CreativeWork
91 sg:pub.10.1007/bf02086606 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024228802
92 https://doi.org/10.1007/bf02086606
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1016/0022-0000(91)90023-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043200457
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1109/18.133276 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061098657
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1109/26.52656 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061137305
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1109/26.681417 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061137967
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1109/90.222924 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061247023
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1109/90.282605 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061247076
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1109/tc.1981.6312176 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532644
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1145/174644.174650 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025317817
109 rdf:type schema:CreativeWork
110 https://doi.org/10.21236/ada126696 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091745570
111 rdf:type schema:CreativeWork
112 https://www.grid.ac/institutes/grid.158820.6 schema:alternateName University of L'Aquila
113 schema:name Dipartimento di Matematica Pura e Applicata, Università de L'Aquila via Vetoio, I-67010, Cappito (AQ), Italy
114 rdf:type schema:Organization
115 https://www.grid.ac/institutes/grid.5801.c schema:alternateName Swiss Federal Institute of Technology in Zurich
116 schema:name Institute for Theoretical Computer Science, ETH Zentrum, CH-8092, Zürich, Switzerland
117 rdf:type schema:Organization
118 https://www.grid.ac/institutes/grid.6530.0 schema:alternateName University of Rome Tor Vergata
119 schema:name Dipartimento di Matematica, Università di Roma “Tor Vergata”, via della Ricerca Scientifica, I-00133, Rome, Italy
120 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...