"Hierarchical routing in sensor networks using κ-dominating sets "

Abstract

For a connected graph, representing a sensor network, distributed algorithms for the Set Covering Problem can be employed to construct reasonably small subsets of the nodes, called k-SPR sets. Such a set can serve as a virtual backbone to facilitate shortest path routing, as introduced in [4] and [14]. When employed in a hierarchical fashion, together with a hybrid (partly proactive, partly reactive) strategy, the κ-SPR set methods become highly scalable, resulting in guaranteed minimal path routing, with comparatively little overhead. © Springer-Verlag Berlin Heidelberg 2005.