Optimal solutions for fault-tolerant topology control in wireless ad hoc networks

Topology control is one of the most important techniques used in wireless ad hoc and sensor networks to reduce energy consumption. Algorithms for topology control attempt to reduce the number of links and the power consumption in a network subject to connectivity constraints. We show that the relate...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on wireless communications 2009-12, Vol.8 (12), p.5970-5981
Main Authors: Moraes, R.E.N., Ribeiro, C.C., Duhamel, C.
Format: Article
Language:English
Subjects:
Ad hoc networks
Algorithms
Applied sciences
Computer Science
Detection, estimation, filtering, equalization, prediction
Energy consumption
energy consumption optimization
Exact sciences and technology
Fault tolerance
Formulations
Information, signal and communications theory
Integer programming
k-connectivity
Linear programming
Mathematical models
mixed integer programming
Mobile ad hoc networks
Network topology
Networks
Operations Research
Optimal control
Optimization
Organization and planning of networks (techniques and equipments)
Power consumption
Signal and communications theory
Signal, noise
Studies
Systems, networks and services of telecommunications
Telecommunications
Telecommunications and information theory
Topology
topology control
Transceivers
Wireless communication
Wireless networks
Wireless sensor networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Topology control is one of the most important techniques used in wireless ad hoc and sensor networks to reduce energy consumption. Algorithms for topology control attempt to reduce the number of links and the power consumption in a network subject to connectivity constraints. We show that the related optimization problems may be classified into four main variants, regarding the topology of the input graph (symmetric or asymmetric) and of the solution (unidirectional or bidirectional). We present three mixed integer programming formulations for the k-connected minimum power consumption problem, which consists in finding a power assignment to the nodes of a wireless network so as that the resulting network topology be k-vertex connected (i.e., k-fault tolerant) and the total power consumption be minimum. These formulations are sufficiently general to encompass all four problem variants. We report computational experiments comparing the formulations. Optimal solutions for moderately sized networks are obtained using a commercial solver.
ISSN:1536-1276
1558-2248
DOI:10.1109/TWC.2009.12.081566