Wireless communication graphs

T. Nieberg; Johann L. Hurink

doi:10.1109/ISSNIP.2004.1417490

Wireless communication graphs

T. Nieberg, Johann L. Hurink

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

21 Citations (Scopus)

129 Downloads (Pure)

Abstract

We consider graph models which represent communication in wireless ad-hoc networks. In such networks, each node equipped with a radio has a certain transmission range, and all surrounding nodes in this range can receive a transmission. In ideal settings, this transmission range creates a circular disk around each node, so that disk intersection graphs are common models. We review some properties of these disk graphs and introduce more realistic and sophisticated geometric graphs to model wireless communication. These models are explored and exploited to obtain approximability results for two important problems, maximum independent sets and minimum dominating sets. Although these more realistic models have less structure, the same complexity status as for disk graphs can be achieved. Furthermore, we present simple, constant factor approximation algorithms for the problems that run locally in each node, and that do not rely on positional information, making them independent of localization.

Original language	English
Title of host publication	ISSNIP 2004
Subtitle of host publication	proceedings of the 2004 Intelligent Sensors, Sensor Networks & Information Processing Conference
Editors	M Palaniswami, B. Krishnamachari, A. Sowmya, S. Challa
Place of Publication	Piscataway, NJ
Publisher	IEEE
Pages	367-372
Number of pages	6
ISBN (Print)	0-7803-8894-1
DOIs	https://doi.org/10.1109/ISSNIP.2004.1417490
Publication status	Published - Dec 2004
Event	1st International Conference on Intelligent Sensors, Sensor Networks and Information Processing, ISSNIP 2004 - Melbourne, Australia Duration: 14 Dec 2004 → 17 Dec 2004 Conference number: 1

Publication series

Name
Publisher	IEEE

Conference

Conference	1st International Conference on Intelligent Sensors, Sensor Networks and Information Processing, ISSNIP 2004
Abbreviated title	ISSNIP
Country/Territory	Australia
City	Melbourne
Period	14/12/04 → 17/12/04

Keywords

METIS-220430
EC Grant Agreement nr.: FP5/34734
EWI-7657
IR-48713

Access to Document

10.1109/ISSNIP.2004.1417490

Paper

Cite this

@inproceedings{8af563d099fc4cd6b15774f5b8ffaebf,

title = "Wireless communication graphs",

abstract = "We consider graph models which represent communication in wireless ad-hoc networks. In such networks, each node equipped with a radio has a certain transmission range, and all surrounding nodes in this range can receive a transmission. In ideal settings, this transmission range creates a circular disk around each node, so that disk intersection graphs are common models. We review some properties of these disk graphs and introduce more realistic and sophisticated geometric graphs to model wireless communication. These models are explored and exploited to obtain approximability results for two important problems, maximum independent sets and minimum dominating sets. Although these more realistic models have less structure, the same complexity status as for disk graphs can be achieved. Furthermore, we present simple, constant factor approximation algorithms for the problems that run locally in each node, and that do not rely on positional information, making them independent of localization.",

keywords = "METIS-220430, EC Grant Agreement nr.: FP5/34734, EWI-7657, IR-48713",

author = "T. Nieberg and Hurink, {Johann L.}",

year = "2004",

month = dec,

doi = "10.1109/ISSNIP.2004.1417490",

language = "English",

isbn = "0-7803-8894-1",

publisher = "IEEE",

pages = "367--372",

editor = "M Palaniswami and B. Krishnamachari and A. Sowmya and S. Challa",

booktitle = "ISSNIP 2004",

address = "United States",

note = "1st International Conference on Intelligent Sensors, Sensor Networks and Information Processing, ISSNIP 2004, ISSNIP ; Conference date: 14-12-2004 Through 17-12-2004",

}

Nieberg, T & Hurink, JL 2004, Wireless communication graphs. in M Palaniswami, B Krishnamachari, A Sowmya & S Challa (eds), ISSNIP 2004: proceedings of the 2004 Intelligent Sensors, Sensor Networks & Information Processing Conference. IEEE, Piscataway, NJ, pp. 367-372, 1st International Conference on Intelligent Sensors, Sensor Networks and Information Processing, ISSNIP 2004, Melbourne, Australia, 14/12/04. https://doi.org/10.1109/ISSNIP.2004.1417490

Wireless communication graphs. / Nieberg, T.; Hurink, Johann L.
ISSNIP 2004: proceedings of the 2004 Intelligent Sensors, Sensor Networks & Information Processing Conference. ed. / M Palaniswami; B. Krishnamachari; A. Sowmya; S. Challa. Piscataway, NJ: IEEE, 2004. p. 367-372.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Wireless communication graphs

AU - Nieberg, T.

AU - Hurink, Johann L.

N1 - Conference code: 1

PY - 2004/12

Y1 - 2004/12

N2 - We consider graph models which represent communication in wireless ad-hoc networks. In such networks, each node equipped with a radio has a certain transmission range, and all surrounding nodes in this range can receive a transmission. In ideal settings, this transmission range creates a circular disk around each node, so that disk intersection graphs are common models. We review some properties of these disk graphs and introduce more realistic and sophisticated geometric graphs to model wireless communication. These models are explored and exploited to obtain approximability results for two important problems, maximum independent sets and minimum dominating sets. Although these more realistic models have less structure, the same complexity status as for disk graphs can be achieved. Furthermore, we present simple, constant factor approximation algorithms for the problems that run locally in each node, and that do not rely on positional information, making them independent of localization.

AB - We consider graph models which represent communication in wireless ad-hoc networks. In such networks, each node equipped with a radio has a certain transmission range, and all surrounding nodes in this range can receive a transmission. In ideal settings, this transmission range creates a circular disk around each node, so that disk intersection graphs are common models. We review some properties of these disk graphs and introduce more realistic and sophisticated geometric graphs to model wireless communication. These models are explored and exploited to obtain approximability results for two important problems, maximum independent sets and minimum dominating sets. Although these more realistic models have less structure, the same complexity status as for disk graphs can be achieved. Furthermore, we present simple, constant factor approximation algorithms for the problems that run locally in each node, and that do not rely on positional information, making them independent of localization.

KW - METIS-220430

KW - EC Grant Agreement nr.: FP5/34734

KW - EWI-7657

KW - IR-48713

U2 - 10.1109/ISSNIP.2004.1417490

DO - 10.1109/ISSNIP.2004.1417490

M3 - Conference contribution

SN - 0-7803-8894-1

SP - 367

EP - 372

BT - ISSNIP 2004

A2 - Palaniswami, M

A2 - Krishnamachari, B.

A2 - Sowmya, A.

A2 - Challa, S.

PB - IEEE

CY - Piscataway, NJ

T2 - 1st International Conference on Intelligent Sensors, Sensor Networks and Information Processing, ISSNIP 2004

Y2 - 14 December 2004 through 17 December 2004

ER -

Wireless communication graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this