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 Nb6ecf7c821e64a93a5bba8df9211e67b
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 N806742f54e9742d69fe5d85d7d5caf1e
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf N7518a09ff92c4fa3bcc0904f29a94ab2
20 schema:name Power consumption in packet radio networks
21 schema:pagination 363-374
22 schema:productId N000d22428fee47e4af05553de3ed5e44
23 Ne9a396667f774167971a03773afe06c1
24 Nf6a1d7ecf8bf429ea80284661a5e5b02
25 schema:publisher N370e8d3db66347ef9afb9d4648fc2fd6
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 N2649570d37974abda399fadeaa12e71a
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 N000d22428fee47e4af05553de3ed5e44 schema:name dimensions_id
36 schema:value pub.1004661921
37 rdf:type schema:PropertyValue
38 N088d2827e18149b6b929d57f954ad400 rdf:first sg:person.01015450242.93
39 rdf:rest N16bd9a94983844ba916b47bccc7b2229
40 N16bd9a94983844ba916b47bccc7b2229 rdf:first sg:person.01200667100.87
41 rdf:rest Ne7b4298a65464270bbd8905e11ed276a
42 N2649570d37974abda399fadeaa12e71a schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 N3118b6d364394a09b436b01b587f9b8d schema:name Department of Computer Engineering and Informatics, Rio, University of Patras, 26500, Patras, Greece
45 rdf:type schema:Organization
46 N370e8d3db66347ef9afb9d4648fc2fd6 schema:location Berlin, Heidelberg
47 schema:name Springer Berlin Heidelberg
48 rdf:type schema:Organisation
49 N6020e641933d4893a98277344248addf rdf:first Nf52ebf6d0ba14d2fa14adf13a6cf8c42
50 rdf:rest rdf:nil
51 N7518a09ff92c4fa3bcc0904f29a94ab2 schema:isbn 978-3-540-62616-9
52 978-3-540-68342-1
53 schema:name STACS 97
54 rdf:type schema:Book
55 N806742f54e9742d69fe5d85d7d5caf1e rdf:first Nb62d7108261a4c5aa381c2b029d45fd9
56 rdf:rest N6020e641933d4893a98277344248addf
57 Nb62d7108261a4c5aa381c2b029d45fd9 schema:familyName Reischuk
58 schema:givenName Rüdiger
59 rdf:type schema:Person
60 Nb6ecf7c821e64a93a5bba8df9211e67b rdf:first sg:person.014347654260.47
61 rdf:rest N088d2827e18149b6b929d57f954ad400
62 Ne7b4298a65464270bbd8905e11ed276a rdf:first sg:person.013306156242.32
63 rdf:rest rdf:nil
64 Ne9a396667f774167971a03773afe06c1 schema:name doi
65 schema:value 10.1007/bfb0023473
66 rdf:type schema:PropertyValue
67 Nf52ebf6d0ba14d2fa14adf13a6cf8c42 schema:familyName Morvan
68 schema:givenName Michel
69 rdf:type schema:Person
70 Nf6a1d7ecf8bf429ea80284661a5e5b02 schema:name readcube_id
71 schema:value 1636e169096da5e73f3279af5d830c52c030efa015ca2c0504f4544839014abb
72 rdf:type schema:PropertyValue
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 N3118b6d364394a09b436b01b587f9b8d
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)


...