The (k, l) Coredian Tree for Ad Hoc Networks
In this paper, we present a new efficient strategy for constructing a wireless tree network containing it nodes of diameter Delta 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 I 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(Delta) time with O(n) messages and a k-coredian tree can be constructed at O(k Delta) time with O(kn) messages. We provide an O(n(2)) time construction algorithm for the (k, l)-coredian tree that requires O(n(2)) 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 k.
ad hoc networks centdian backbone sensor networks