Optimal Flooding Search in a Large Network

Prof. Mingyan Liu, University of MichiganAbstract: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, we adopt a worst-case cost measure which is also the competitive ratio with respect to an oblivious adversary. In minimizing this cost measure we show that the best strategies are randomized strategies. We then derive an asymptotically (as the network size increases) optimal randomized strategy, and compare its performance with its deterministic counterpart. We will also explore a number of simple but suboptimal strategies. Speaker Bio: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. She is the recipient of the 2002 NSF CAREER Award, and the University of Michigan Elizabeth C. Crosby Research Award in 2003.

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Irina Strelnik