Efficient Algorithms for Topology Control Problem with Routing Cost Constraints in Wireless Networks

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

doi:10.1109/TPDS.2011.30

상세 보기

Efficient Algorithms for Topology Control Problem with Routing Cost Constraints in Wireless Networks

Ding, Ling;
Wu, Weili;
Willson, James;
Du, Hongjie;
Lee, Wonjun;
외 1명

Citations

WEB OF SCIENCE

55

Citations

SCOPUS

62

초록

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 alpha Minimum rOuting Cost CDS (alpha-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 alpha MOC-CDS is NP-hard in a general graph and we propose a heuristic algorithm for construction of alpha-MOC-CDS.

키워드

Connected dominating set; routing path; wireless network; obstacle; general graph; NP-hard; topology control; CONNECTED DOMINATING SETS; UNIT DISK GRAPHS; CONSTRUCTION; APPROXIMATION

제목: Efficient Algorithms for Topology Control Problem with Routing Cost Constraints in Wireless Networks

저자: Ding, Ling; Wu, Weili; Willson, James; Du, Hongjie; Lee, Wonjun; Du, Ding-Zhu

DOI: 10.1109/TPDS.2011.30

발행일: 2011-10

유형: Article

저널명: IEEE Transactions on Parallel and Distributed Systems

권: 22

호: 10

페이지: 1601 ~ 1609