Power consumption in packet radio networks View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005-06-10

AUTHORS

Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc

ABSTRACT

In this paper we study the problem of assigning transmission ranges to the nodes of a multi-hop packet radio network so as to minimize the total power consumed under the constraint that adequate power is provided to the nodes to ensure that the network is strongly connected (i.e., each node can communicate along some path in the network to every other node). Such assignment of transmission ranges is called complete. We also consider the problem of achieving strongly connected bounded diameter networks. For the case of n+1 colinear points at unit distance apart (the unit chain) we give a tight asymptotic bound for the minimum cost of a range assignment of diameter h when h is a fixed constant and when h ∈ Ω(log n). When the distances between the colinear points are arbitrary, we give an O(n4) time dynamic programming algorithm for finding a minimum cost complete range assignment. For points in three dimensions we show that the problem of deciding whether a complete range assignment of a given cost exists, is NP-hard. For the same problem we give an O(n2) time approximation algorithm which provides a complete range assignment with cost within a factor of two of the minimum. The complexity of this problem in two dimensions remains open, while the approximation algorithm works in this case as well. More... »

PAGES

363-374

Book

TITLE

STACS 97

ISBN

978-3-540-62616-9
978-3-540-68342-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0023473

DOI

http://dx.doi.org/10.1007/bfb0023473

DIMENSIONS

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


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/1005", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Communications Technologies", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/10", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Technology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "Department of Computer Engineering and Informatics, Rio, University of Patras, 26500, Patras, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kirousis", 
        "givenName": "Lefteris M.", 
        "id": "sg:person.014347654260.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014347654260.47"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Carleton University", 
          "id": "https://www.grid.ac/institutes/grid.34428.39", 
          "name": [
            "School of Computer Science, Carleton University, K1S 5B6, Ottawa, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kranakis", 
        "givenName": "Evangelos", 
        "id": "sg:person.01015450242.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01015450242.93"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Carleton University", 
          "id": "https://www.grid.ac/institutes/grid.34428.39", 
          "name": [
            "School of Computer Science, Carleton University, K1S 5B6, Ottawa, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Krizanc", 
        "givenName": "Danny", 
        "id": "sg:person.01200667100.87", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01200667100.87"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Universit\u00e9 du Qu\u00e9bec en Outaouais", 
          "id": "https://www.grid.ac/institutes/grid.265705.3", 
          "name": [
            "D\u00e9partement d'Informatique, Universit\u00e9 du Qu\u00e9bec \u00e0 Hull, J8X 3X7, Hull, Qu\u00e9bec, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pelc", 
        "givenName": "Andrzej", 
        "id": "sg:person.013306156242.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013306156242.32"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "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/90.222924", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061247023"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/proc.1978.11151", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061444074"
        ], 
        "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.1109/tcom.1984.1096061", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061553870"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.1984.1056928", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061649050"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/infcom.1989.101493", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086254353"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/infcom.1996.493055", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094245685"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005-06-10", 
    "datePublishedReg": "2005-06-10", 
    "description": "In this paper we study the problem of assigning transmission ranges to the nodes of a multi-hop packet radio network so as to minimize the total power consumed under the constraint that adequate power is provided to the nodes to ensure that the network is strongly connected (i.e., each node can communicate along some path in the network to every other node). Such assignment of transmission ranges is called complete. We also consider the problem of achieving strongly connected bounded diameter networks. For the case of n+1 colinear points at unit distance apart (the unit chain) we give a tight asymptotic bound for the minimum cost of a range assignment of diameter h when h is a fixed constant and when h \u2208 \u03a9(log n). When the distances between the colinear points are arbitrary, we give an O(n4) time dynamic programming algorithm for finding a minimum cost complete range assignment. For points in three dimensions we show that the problem of deciding whether a complete range assignment of a given cost exists, is NP-hard. For the same problem we give an O(n2) time approximation algorithm which provides a complete range assignment with cost within a factor of two of the minimum. The complexity of this problem in two dimensions remains open, while the approximation algorithm works in this case as well.", 
    "editor": [
      {
        "familyName": "Reischuk", 
        "givenName": "R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Morvan", 
        "givenName": "Michel", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0023473", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-62616-9", 
        "978-3-540-68342-1"
      ], 
      "name": "STACS 97", 
      "type": "Book"
    }, 
    "name": "Power consumption in packet radio networks", 
    "pagination": "363-374", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004661921"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0023473"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "1636e169096da5e73f3279af5d830c52c030efa015ca2c0504f4544839014abb"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0023473", 
      "https://app.dimensions.ai/details/publication/pub.1004661921"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T09:26", 
    "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/0000000372_0000000372/records_117092_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2FBFb0023473"
  }
]
 

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.1007/bfb0023473'

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.1007/bfb0023473'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0023473'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0023473'


 

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

120 TRIPLES      23 PREDICATES      34 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0023473 schema:about anzsrc-for:10
2 anzsrc-for:1005
3 schema:author Nca69f921c1cd4acd9db6ca1fb52ed9fc
4 schema:citation https://doi.org/10.1109/26.52656
5 https://doi.org/10.1109/90.222924
6 https://doi.org/10.1109/infcom.1989.101493
7 https://doi.org/10.1109/infcom.1996.493055
8 https://doi.org/10.1109/proc.1978.11151
9 https://doi.org/10.1109/tc.1981.6312176
10 https://doi.org/10.1109/tcom.1984.1096061
11 https://doi.org/10.1109/tit.1984.1056928
12 schema:datePublished 2005-06-10
13 schema:datePublishedReg 2005-06-10
14 schema:description In this paper we study the problem of assigning transmission ranges to the nodes of a multi-hop packet radio network so as to minimize the total power consumed under the constraint that adequate power is provided to the nodes to ensure that the network is strongly connected (i.e., each node can communicate along some path in the network to every other node). Such assignment of transmission ranges is called complete. We also consider the problem of achieving strongly connected bounded diameter networks. For the case of n+1 colinear points at unit distance apart (the unit chain) we give a tight asymptotic bound for the minimum cost of a range assignment of diameter h when h is a fixed constant and when h ∈ Ω(log n). When the distances between the colinear points are arbitrary, we give an O(n4) time dynamic programming algorithm for finding a minimum cost complete range assignment. For points in three dimensions we show that the problem of deciding whether a complete range assignment of a given cost exists, is NP-hard. For the same problem we give an O(n2) time approximation algorithm which provides a complete range assignment with cost within a factor of two of the minimum. The complexity of this problem in two dimensions remains open, while the approximation algorithm works in this case as well.
15 schema:editor N50454cf7a500448cb4fb1195c05885f1
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf Ne4d1f910aaff4b30965fb09ad7395956
20 schema:name Power consumption in packet radio networks
21 schema:pagination 363-374
22 schema:productId N02c9f7ea1d3244299cee8b1f7c17e837
23 Na705b298d2bc418183ba3d195dc66bf6
24 Nbb8703425cf741ca90e86c47cecef309
25 schema:publisher Ne4f240338e014f43875582d3566fc833
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004661921
27 https://doi.org/10.1007/bfb0023473
28 schema:sdDatePublished 2019-04-16T09:26
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N9f5794aecf0e48a5a815f1b1fb1cff9e
31 schema:url https://link.springer.com/10.1007%2FBFb0023473
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N02c9f7ea1d3244299cee8b1f7c17e837 schema:name dimensions_id
36 schema:value pub.1004661921
37 rdf:type schema:PropertyValue
38 N19965c6f128f424abca7064116c2f25a schema:name Department of Computer Engineering and Informatics, Rio, University of Patras, 26500, Patras, Greece
39 rdf:type schema:Organization
40 N379715edc7e1473eb3a9796317a91b2b rdf:first sg:person.013306156242.32
41 rdf:rest rdf:nil
42 N50454cf7a500448cb4fb1195c05885f1 rdf:first N5f1c5542e5ba4b23947974f6003d70b5
43 rdf:rest Ncdfcd89a4cff4bf3be536321ef0e97fe
44 N5f1c5542e5ba4b23947974f6003d70b5 schema:familyName Reischuk
45 schema:givenName Rüdiger
46 rdf:type schema:Person
47 N60ffe24307fd47159faa3e3fc2c28b15 rdf:first sg:person.01015450242.93
48 rdf:rest Nddd970f22c204b56a9d595fe671b23b1
49 N8fefe22be02b4cd3b886d8d00bfe8b90 schema:familyName Morvan
50 schema:givenName Michel
51 rdf:type schema:Person
52 N9f5794aecf0e48a5a815f1b1fb1cff9e schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 Na705b298d2bc418183ba3d195dc66bf6 schema:name readcube_id
55 schema:value 1636e169096da5e73f3279af5d830c52c030efa015ca2c0504f4544839014abb
56 rdf:type schema:PropertyValue
57 Nbb8703425cf741ca90e86c47cecef309 schema:name doi
58 schema:value 10.1007/bfb0023473
59 rdf:type schema:PropertyValue
60 Nca69f921c1cd4acd9db6ca1fb52ed9fc rdf:first sg:person.014347654260.47
61 rdf:rest N60ffe24307fd47159faa3e3fc2c28b15
62 Ncdfcd89a4cff4bf3be536321ef0e97fe rdf:first N8fefe22be02b4cd3b886d8d00bfe8b90
63 rdf:rest rdf:nil
64 Nddd970f22c204b56a9d595fe671b23b1 rdf:first sg:person.01200667100.87
65 rdf:rest N379715edc7e1473eb3a9796317a91b2b
66 Ne4d1f910aaff4b30965fb09ad7395956 schema:isbn 978-3-540-62616-9
67 978-3-540-68342-1
68 schema:name STACS 97
69 rdf:type schema:Book
70 Ne4f240338e014f43875582d3566fc833 schema:location Berlin, Heidelberg
71 schema:name Springer Berlin Heidelberg
72 rdf:type schema:Organisation
73 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
74 schema:name Technology
75 rdf:type schema:DefinedTerm
76 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
77 schema:name Communications Technologies
78 rdf:type schema:DefinedTerm
79 sg:person.01015450242.93 schema:affiliation https://www.grid.ac/institutes/grid.34428.39
80 schema:familyName Kranakis
81 schema:givenName Evangelos
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01015450242.93
83 rdf:type schema:Person
84 sg:person.01200667100.87 schema:affiliation https://www.grid.ac/institutes/grid.34428.39
85 schema:familyName Krizanc
86 schema:givenName Danny
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01200667100.87
88 rdf:type schema:Person
89 sg:person.013306156242.32 schema:affiliation https://www.grid.ac/institutes/grid.265705.3
90 schema:familyName Pelc
91 schema:givenName Andrzej
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013306156242.32
93 rdf:type schema:Person
94 sg:person.014347654260.47 schema:affiliation N19965c6f128f424abca7064116c2f25a
95 schema:familyName Kirousis
96 schema:givenName Lefteris M.
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014347654260.47
98 rdf:type schema:Person
99 https://doi.org/10.1109/26.52656 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061137305
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1109/90.222924 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061247023
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1109/infcom.1989.101493 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086254353
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1109/infcom.1996.493055 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094245685
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1109/proc.1978.11151 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061444074
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1109/tc.1981.6312176 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532644
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1109/tcom.1984.1096061 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061553870
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1109/tit.1984.1056928 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061649050
114 rdf:type schema:CreativeWork
115 https://www.grid.ac/institutes/grid.265705.3 schema:alternateName Université du Québec en Outaouais
116 schema:name Département d'Informatique, Université du Québec à Hull, J8X 3X7, Hull, Québec, Canada
117 rdf:type schema:Organization
118 https://www.grid.ac/institutes/grid.34428.39 schema:alternateName Carleton University
119 schema:name School of Computer Science, Carleton University, K1S 5B6, Ottawa, ON, Canada
120 rdf:type schema:Organization
 




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


...