"Hierarchical routing in sensor networks using κ-dominating sets "
Rieck, Michael Q.
MetadataShow full item record
SubjectAd hoc wireless networks.; Dominating set.; Routing algorithm.; Set covering problem.; Shortest path routing.
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  and . 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.
Michael Q. Rieck is Associate Professor of Computer Science in the Department of Math and Computer Science at Drake University. He can be contacted at email@example.com