Wireless Communication Graphs

Nieberg, Tim and Hurink, Johann (2004) Wireless Communication Graphs. In: Intelligent Sensors, Sensor Networks and Information Processing Conference, ISSNIP 2004, 14-17 December 2004, Melbourne, Australia.

Preview

PDF
526Kb

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.
Item Type:	Conference or Workshop Item
Copyright:	© 2004 IEEE
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/48713
Official URL:	http://dx.doi.org/10.1109/ISSNIP.2004.1417490
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 220430