Details

Autor(en) / Beteiligte

• Bein, D.

Titel

Fault-Tolerant k-Fold Pivot Routing in Wireless Sensor Networks

Ist Teil von

• Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008), 2008, p.494DoinaBein-494DoinaBein

Ort / Verlag

IEEE

Erscheinungsjahr

2008

Link zum Volltext

• IEEE_Xplore

Quelle

IEEE Xplore

Beschreibungen/Notizen

• Selecting a small set of nodes called pivots, from all the nodes in a network and maintaining the routing infrastructure to and among each other can reduce routing overhead and excessive broadcast redundancy. In this paper a new problem, called "k-fold cover t- set" (for short, k-fold cover), is proposed: we select a smaller set of nodes than the k-fold dominating set, to act as alternative routers for messages in the network. An advantage of the k-fold cover is that it can be defined for graphs where the k-fold dominating set cannot be defined. Computing the minimum size k-fold cover for any k ges 1 is NP-complete. Two approximation algorithms for the k-fold cover problem are proposed: one uses a greedy approach to compute the cover and the other uses randomization.