In this talk I will consider the problem of searching for a node or an object in a large network. Applications of this problem include route establishment in a mobile ad hoc network, data querying in a wireless sensor network, and file searching in a peer-to-peer network. We will limit our attention to the class of controlled flooding search strategies where query packets are broadcast and propagated in the network until a preset TTL (time-to-live) expires. Every unsuccessful search attempt (signified by a timeout) results in an increased TTL value (i.e., larger search area). The primary goal is to derive strategies that will minimize the search cost associated with packet transmissions. We consider two cases. When the probability distribution of the location of the object is known a priori, we present a dynamic programming formulation with which optimal search strategies can be derived. We also derive necessary and sufficient conditions under which two widely used search strategies are optimal. When the probability distribution is not known a priori and the objective is to minimize the worst-case search cost, the best strategies are shown to be randomized strategies. We present a randomization method that gives better performance given any deterministic strategy. We also derive an asymptotically (as the network size increases) optimal strategy within a class of randomized strategies.

Mingyan Liu received her B.Sc. degree in electrical engineering in 1995 from the Nanjing University of Aero. and Astro., Nanjing, China, M.Sc. degree in systems engineering and Ph.D. Degree in electrical engineering from the University of Maryland, College Park, in 1997 and 2000, respectively. She joined the Department of Electrical Engineering and Computer Science at the University of Michigan, Ann Arbor, in September 2000, where she is currently an Assistant Professor. Her research interests are in performance modeling, analysis, energy-efficiency and resource allocation issues in wireless mobile ad hoc networks, wireless sensor networks, and terrestrial satellite hybrid networks.