TY - JOUR

T1 - The (K, l) coredian tree for ad hoc networks

AU - Dvir, Amit

AU - Segal, Michael

N1 - Publisher Copyright:
© 2008 Old City Publishing, Inc.

PY - 2008

Y1 - 2008

N2 - In this paper, we present a new efficient strategy for constructing a wireless tree network containing n nodes of diameter Δ while satisfying the QoS requirements such as bandwidth and delay. Given a tree network T, a coredian path is a path in T that minimizes the centdian function, a k-coredian tree is a subtree of T with k leaves that minimizes the centdian function, and a (k, l)-coredian tree is a subtree of T with k leaves and diameter l at most that minimizes the centdian function. The (k, l)-coredian tree can serve as a backbone for a network, where the internal nodes belong to the backbone and the leaves serve as the heads of the clusters covering the rest of the network. We show that a coredian path can be constructed at O(Δ) time with O(n) messages and a k-coredian tree can be constructed at O(kΔ) time with O(kn) messages.We provide an O(n2) time construction algorithm for the (k, l)-coredian tree that requires O(n2) messages. We also give upper and lower bounds for a number of nodes covered by the k cluster heads in random geometric graph using critical transmission range of connected network. Finally, simulation is presented for various values of n and k1.

AB - In this paper, we present a new efficient strategy for constructing a wireless tree network containing n nodes of diameter Δ while satisfying the QoS requirements such as bandwidth and delay. Given a tree network T, a coredian path is a path in T that minimizes the centdian function, a k-coredian tree is a subtree of T with k leaves that minimizes the centdian function, and a (k, l)-coredian tree is a subtree of T with k leaves and diameter l at most that minimizes the centdian function. The (k, l)-coredian tree can serve as a backbone for a network, where the internal nodes belong to the backbone and the leaves serve as the heads of the clusters covering the rest of the network. We show that a coredian path can be constructed at O(Δ) time with O(n) messages and a k-coredian tree can be constructed at O(kΔ) time with O(kn) messages.We provide an O(n2) time construction algorithm for the (k, l)-coredian tree that requires O(n2) messages. We also give upper and lower bounds for a number of nodes covered by the k cluster heads in random geometric graph using critical transmission range of connected network. Finally, simulation is presented for various values of n and k1.

KW - Ad hoc networks

KW - Backbone

KW - Centdian

KW - Sensor networks

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

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:77954450866

SN - 1551-9899

VL - 6

SP - 123

EP - 144

JO - Ad-Hoc and Sensor Wireless Networks

JF - Ad-Hoc and Sensor Wireless Networks

IS - 1-2

ER -