Efficient parallel algorithms for dead sensor diagnosis and multiple access channels

ABSTRACT

We study parallel algorithms for identifying the dead sensors in a mobile ad hoc wireless network and for resolving broadcast conflicts on a multiple access channel (MAC). Our approach involves the development and application of new group-testing algorithms, where we are asked to identify all the defective items in a set of items when we can test arbitrary subsets of items. In the standard group-testing problem, the result of a test is binary--the tested subset either contains defective items or not. In the versions we study in this paper, the result of each test is non-binary. For example, it may indicate whether the number of defective items contained in the tested subset is zero, one, or at least two (i.e., the results are 0, 1, or 2+). We give adaptive algorithms that are provably more efficient than previous group testing algorithms (even for generalized response models). We also show how our algorithms can be implemented in parallel, because they possess a property we call conciseness, which allows them to be used to solve dead sensor diagnosis and conflict resolution on a MAC. Dead sensor diagnosis poses an interesting challenge compared to MAC resolution, because dead sensors are not locally detectable, nor are they themselves active participants. Even so, we present algorithms that can be applied in both contexts that are more efficient than previous methods. We also give lower bounds for generalized group testing.

REFERENCES

• 1: A. Allemann. Improved Upper Bounds for Several Variants of Group Testing. PhD thesis, Rheinisch-Westfalischen Technischen Hochschule Aachen, November 2003.
• 2: M. J. Atallah, M. T. Goodrich, and R. Tamassia. Indexing information for data forensics. In 3rd Applied Cryptography and Network Security Conference (ACNS), volume 3531 of Lecture Notes in Computer Science, pages 206--221. Springer, 2005.
• 3: R. Beigel , S. R. Kosaraju , G. F. Sullican, Locating faults in a constant number of parallel testing rounds, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.189-198, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72956]
• 4: Richard Beigel , Grigorii Margulis , Daniel A. Spielman, Fault diagnosis in a small constant number of parallel testing rounds, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.21-29, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165234]
• 5: R. Beigel , W. Hurwood , N. Kahale, Fault diagnosis in a flash, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.571, October 23-25, 1995
• 6: J. I. Capetanakis. Tree algorithms for packet broadcast channels. IEEE Trans. Inf. Theory, IT-25(5):505--515, 1979.
• 7: Colbourn, Dinitz, and Stinson. Applications of combinatorial designs to communications, cryptography, and networking. In Surveys in Combinatorics, 1993, Walker (Ed.), London Mathematical Society Lecture Note Series 187. Cambridge University Press, 1999.
• 8: A. DeBonis, L. Gasieniec, and U. Vaccaro. Generalized framework for selectors with applications in optimal group testing. In Proceedings of 30th International Colloquium on Automata, Languages and Programming (ICALP'03), pages 81--96. Springer, 2003.
• 9: D. Z.Du and F. K. Hwang. Combinatorial Group Testing and Its Applications, 2nd ed. World Scientific, 2000.
• 10: D. Eppstein, M. T. Goodrich, and D. S. Hirschberg. Improved combinatorial group testing for real-world problem sizes. In Workshop on Algorithms and Data Structures (WADS), Lecture Notes Comput. Sci. Springer, 2005.
• 11: M. Farach , S. Kannan , E. Knill , S. Muthukrishnan, Group Testing Problems with Sequences in Experimental Molecular Biology, Proceedings of the Compression and Complexity of Sequences 1997, p.357, June 11-13, 1997
• 12: A. G. Greenberg and R. E. Ladner. Estimating the multiplicities of conflicts in multiple access channels. In Proc. 24th Annual Symp. on Foundations of Computer Science (FOCS'83), pages 383--392. IEEE Computer Society, 1983.
• 13: Albert G. Greenberg , Schmuel Winograd, A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels, Journal of the ACM (JACM), v.32 n.3, p.589-596, July 1985 [doi>10.1145/3828.214125]
• 14: M. Hofri. Stack algorithms for collision-detecting channels and their analysis: A limited survey. In A. V. Balakrishnan and M. Thoma, editors, Proc. Inf. Sem. Modelling and Performance Evaluation Methodology, volume 60 of Lecture Notes in Control and Info. Sci., pages 71--85, 1984.
• 15: F. K. Hwang. A method for detecting all defective members in a population by group testing. J. Amer. Statist. Assoc., 67:605--608, 1972.
• 16: F. K. Hwang and V. T. Sós. Non-adaptive hypergeometric group testing. Studia Scient. Math. Hungarica, 22:257--263, 1987.
• 17: Chalermek Intanagonwiwat , Deborah Estrin , Ramesh Govindan , John Heidemann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.457, July 02-05, 2002
• 18: W. H. Kautz and R. C. Singleton. Nonrandom binary superimposed codes. IEEE Trans. Inf. Th., 10:363--377, 1964.
• 19: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 20: A. J. Macula and G. R. Reuter. Simplified searching for two defects. J. Stat. Plan. Inf., 66:77--82, 1998.
• 21: Miklós Ruszinkó, On the upper bound of the size of the r-cover-free families, Journal of Combinatorial Theory Series A, v.66 n.2, p.302-310, May 1994 [doi>10.1016/0097-3165(94)90067-1]
• 22: J. Schlaghoff and E. Triesch. Improved results for competitive group testing. Report, Forschungsinstitut fur Diskrete Mathematik, Institut fur Okonometrie und Operations Research, Rheinische Friedrich-Wilhelms-Universitat Bonn, 1997. Report 97858.
• 23: W. Yuan , S. V. Krishnamurthy , S. K. Tripathi, Improving the reliability of event reports in wireless sensor networks, Proceedings of the Ninth International Symposium on Computers and Communications 2004 Volume 2 (ISCC"04), p.220-225, June 28-July 01, 2004

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Design, Performance

Keywords:
dead sensor diagnosis, group testing, multiple access channels