Abstract:
We study group-testing algorithms that have applications for identifying the dead sensors in a mobile ad hoc wireless network and for resolving broadcast conflicts on a multiple access channel (MAC).
In group-testing problems, we are asked to identify all the defective items in a set of items when we can test arbitrary subsets of items for "contamination." In the standard group-testing problem, the result of a test is binary -- the tested subset either contains defective items or it does not. In the versions we study here, 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 group testing algorithms that are provably more efficient than previous group testing algorithms (even for generalized response models). We also show how our algorithms can be applied 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. We also give lower bounds for generalized group testing.
(Joint work with Michael T. Goodrich.)