Abstract
In a graph G = (V,E), a k-hop dominating set Dk is a subset of such that all nodes in V are either in or at most k-hop to a node Dk. A k-hop dominating set Dk is connected if there is a path, in which each node is in Dk, between any two nodes in Dk. In a mobile ad hoc network, a node communicates with its neighbors by sending messages across channels, and the others by routing messages via the network. The hierarchical routing protocol that constructs and maintains a connected k-hop dominating set attempts to reduce transmission power and communication overhead. In this paper, the node property of a connected k-hop dominating set is found, and it is proved that a k-hop dominating set is connected if all nodes in V belong to the node property. By its aid, a connected k-hop dominating set is constructed and maintained using only 2-hop neighbor information. Our simulation shows that the connected dominating set shrinks consistently as the hop count of k grows.