21763 articles – 15575 Notices  [english version]

hal-00620256, version 2

Tolerant identification with Euclidean balls

Ville Junnila () 1, Tero Laihonen () 2, Aline Parreau (Auteur à contacter de préférence) 3

(08/2011)

Résumé : The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. The identifying codes can be applied, for example, to sensor networks. In this paper, we consider as sensors the set Z^2 where one sensor can check its neighbours within Euclidean distance r. We construct tolerant identifying codes in this network that are robust against some changes in the neighbourhood monitored by each sensor. We give bounds for the smallest density of a tolerant identifying code for general values of r and Delta. We also provide infinite families of values (r,Delta) with optimal such codes and study the case of small values of r.

  • 1 :  Department of Mathematics
  • University of Turku
  • 2 :  Turku Centre for Computer Science
  • University of Turku
  • 3 :  Institut Fourier (IF)
  • CNRS : UMR5582 – Université Joseph Fourier - Grenoble I
  • Domaine : Informatique/Théorie de l'information et codage
    Mathématiques/Combinatoire
    Informatique/Mathématique discrète
    Mathématiques/Théorie de l'information et codage
  • Mots-clés : Identifying code – Optimal code – Sensor network – Fault diagnosis
  • Référence interne : IF_PREPUB
  • Versions disponibles :  v1 (09-09-2011) v2 (13-09-2011) v3 (01-03-2012)
 
  • hal-00620256, version 2
  • http://hal.archives-ouvertes.fr/hal-00620256
  • oai:hal.archives-ouvertes.fr:hal-00620256
  • Contributeur : Aline Parreau <>
  • Soumis le : Lundi 12 Septembre 2011, 16:17:08
  • Dernière modification le : Vendredi 14 Octobre 2011, 11:39:48