TY - JOUR
T1 - Distributed algorithms for connected domination in wireless networks
AU - Gandhi, Rajiv
AU - Parthasarathy, Srinivasan
N1 - Funding Information:
∗ Corresponding author. Fax: +1 301 405 6707. E-mail addresses: [email protected] (R. Gandhi), [email protected] (S. Parthasarathy). 1Part of this work was done when the author was a student at the University of Maryland and was supported by NSF Award CCR-9820965. Research was also supported by the Rutgers University’s Research Council grant. 2Research supported by NSF Award CCR-0208005 and NSF ITR Award CNS-0426683.
PY - 2007/7
Y1 - 2007/7
N2 - We present fast distributed local control connected dominating set (CDS) algorithms for wireless ad hoc networks. We present two randomized distributed algorithms, CDSColor and CDSTop which take into account the effect of wireless interference and the consequent loss of messages during the execution of the algorithm. These algorithms produce a CDS of constant size and constant stretch ratio with high probability, and converge in polylogarithmic running time. Specifically, algorithm CDSColor requires the nodes to know (estimates of) the maximum degree Δ and the size of the network n and converges in O (Δ log2 n) time. Algorithm CDSTop requires the nodes to know their three-hop topology and (an estimate of) the network size n and converges in O (log2 n) time. To the best of our knowledge, these are the first distributed interference-aware CDS algorithms for wireless ad hoc networks which break the linear running-time barrier.
AB - We present fast distributed local control connected dominating set (CDS) algorithms for wireless ad hoc networks. We present two randomized distributed algorithms, CDSColor and CDSTop which take into account the effect of wireless interference and the consequent loss of messages during the execution of the algorithm. These algorithms produce a CDS of constant size and constant stretch ratio with high probability, and converge in polylogarithmic running time. Specifically, algorithm CDSColor requires the nodes to know (estimates of) the maximum degree Δ and the size of the network n and converges in O (Δ log2 n) time. Algorithm CDSTop requires the nodes to know their three-hop topology and (an estimate of) the network size n and converges in O (log2 n) time. To the best of our knowledge, these are the first distributed interference-aware CDS algorithms for wireless ad hoc networks which break the linear running-time barrier.
KW - Connected dominating set
KW - Distributed algorithms
KW - Interference
KW - Wireless networks
UR - http://www.scopus.com/inward/record.url?scp=34249744507&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34249744507&partnerID=8YFLogxK
U2 - 10.1016/j.jpdc.2007.04.003
DO - 10.1016/j.jpdc.2007.04.003
M3 - Article
AN - SCOPUS:34249744507
SN - 0743-7315
VL - 67
SP - 848
EP - 862
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
IS - 7
ER -