Efficient algorithms for topology control problem with routing cost constraints in wireless networks

Ling Ding; Weili Wu; James Willson; Hongjie Du; Wonjun Lee; Ding Zhu Du

doi:10.1109/TPDS.2011.30

Efficient algorithms for topology control problem with routing cost constraints in wireless networks

Ling Ding, Weili Wu, James Willson, Hongjie Du, Wonjun Lee, Ding Zhu Du

School of Cybersecurity

Research output: Contribution to journal › Article › peer-review

54 Citations (Scopus)

Abstract

Topology control is one vital factor to a wireless network's efficiency. A Connected Dominating Set (CDS) can be a useful basis of a backbone topology construction. In this paper, a special CDS, named α Minimum rOuting Cost CDS (α-MOC-CDS), will be studied to improve the performance of CDS based broadcasting and routing. In this paper, we prove that construction of a minimum α-MOC-CDS is NP-hard in a general graph and we propose a heuristic algorithm for construction of α-MOC-CDS.

Original language	English
Article number	5703070
Pages (from-to)	1601-1609
Number of pages	9
Journal	IEEE Transactions on Parallel and Distributed Systems
Volume	22
Issue number	10
DOIs	https://doi.org/10.1109/TPDS.2011.30
Publication status	Published - 2011

Keywords

Connected dominating set
NP-hard
general graph
obstacle
routing path
topology control
wireless network

ASJC Scopus subject areas

Signal Processing
Hardware and Architecture
Computational Theory and Mathematics

Access to Document

10.1109/TPDS.2011.30

Cite this

@article{3e049d2314ad4bb7a4ea522606b978a3,

title = "Efficient algorithms for topology control problem with routing cost constraints in wireless networks",

abstract = "Topology control is one vital factor to a wireless network's efficiency. A Connected Dominating Set (CDS) can be a useful basis of a backbone topology construction. In this paper, a special CDS, named α Minimum rOuting Cost CDS (α-MOC-CDS), will be studied to improve the performance of CDS based broadcasting and routing. In this paper, we prove that construction of a minimum α-MOC-CDS is NP-hard in a general graph and we propose a heuristic algorithm for construction of α-MOC-CDS.",

keywords = "Connected dominating set, NP-hard, general graph, obstacle, routing path, topology control, wireless network",

author = "Ling Ding and Weili Wu and James Willson and Hongjie Du and Wonjun Lee and Du, {Ding Zhu}",

note = "Funding Information: This research was supported by US National Science Foundation (NSF) under Grant CNS 1016320, CCF 0829993, and CCF 0627233. This research was jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), a NRF Grant under (KRF-2008-314-D00354), and MKE, Korea under ITRC NIPA-2010-(C1090-1021-0008).",

year = "2011",

doi = "10.1109/TPDS.2011.30",

language = "English",

volume = "22",

pages = "1601--1609",

journal = "IEEE Transactions on Parallel and Distributed Systems",

issn = "1045-9219",

publisher = "IEEE Computer Society",

number = "10",

}

TY - JOUR

T1 - Efficient algorithms for topology control problem with routing cost constraints in wireless networks

AU - Ding, Ling

AU - Wu, Weili

AU - Willson, James

AU - Du, Hongjie

AU - Lee, Wonjun

AU - Du, Ding Zhu

N1 - Funding Information: This research was supported by US National Science Foundation (NSF) under Grant CNS 1016320, CCF 0829993, and CCF 0627233. This research was jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), a NRF Grant under (KRF-2008-314-D00354), and MKE, Korea under ITRC NIPA-2010-(C1090-1021-0008).

PY - 2011

Y1 - 2011

N2 - Topology control is one vital factor to a wireless network's efficiency. A Connected Dominating Set (CDS) can be a useful basis of a backbone topology construction. In this paper, a special CDS, named α Minimum rOuting Cost CDS (α-MOC-CDS), will be studied to improve the performance of CDS based broadcasting and routing. In this paper, we prove that construction of a minimum α-MOC-CDS is NP-hard in a general graph and we propose a heuristic algorithm for construction of α-MOC-CDS.

AB - Topology control is one vital factor to a wireless network's efficiency. A Connected Dominating Set (CDS) can be a useful basis of a backbone topology construction. In this paper, a special CDS, named α Minimum rOuting Cost CDS (α-MOC-CDS), will be studied to improve the performance of CDS based broadcasting and routing. In this paper, we prove that construction of a minimum α-MOC-CDS is NP-hard in a general graph and we propose a heuristic algorithm for construction of α-MOC-CDS.

KW - Connected dominating set

KW - NP-hard

KW - general graph

KW - obstacle

KW - routing path

KW - topology control

KW - wireless network

UR - http://www.scopus.com/inward/record.url?scp=80052324399&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2011.30

DO - 10.1109/TPDS.2011.30

M3 - Article

AN - SCOPUS:80052324399

SN - 1045-9219

VL - 22

SP - 1601

EP - 1609

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

IS - 10

M1 - 5703070

ER -

Efficient algorithms for topology control problem with routing cost constraints in wireless networks

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this