Distributed vertex cover algorithms for wireless sensor networks


Creative Commons License

Kavalcı V. , Ural A., Dağdeviren O.

International Journal of Computer Networks & Communications (IJCNC), cilt.6, sa.1, ss.95-110, 2014 (Diğer Kurumların Hakemli Dergileri)

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 6 Konu: 1
  • Basım Tarihi: 2014
  • Doi Numarası: 10.5121/ijcnc.2014.6107
  • Dergi Adı: International Journal of Computer Networks & Communications (IJCNC)
  • Sayfa Sayıları: ss.95-110

Özet

Vertex covering has important applications for wireless sensor networks such as monitoring link failures,

facility location, clustering, and data aggregation. In this study, we designed three algorithms for

constructing vertex cover in wireless sensor networks. The first algorithm, which is an adaption of the

Parnas & Ron’s algorithm, is a greedy approach that finds a vertex cover by using the degrees of the

nodes. The second algorithm finds a vertex cover from graph matching where Hoepman’s weighted

matching algorithm is used. The third algorithm firstly forms a breadth-first search tree and then

constructs a vertex cover by selecting nodes with predefined levels from breadth-first tree. We show the

operation of the designed algorithms, analyze them, and provide the simulation results in the TOSSIM

environment. Finally we have implemented, compared and assessed all these approaches. The transmitted

message count of the first algorithm is smallest among other algorithms where the third algorithm has

turned out to be presenting the best results in vertex cover approximation ratio.