Revisiting the TTL-based controlled flooding search: optimality and randomization

ABSTRACT

In this paper we consider the problem of searching for a node or an object (i.e., piece of data, file, etc.) in a large network. Applications of this problem include searching for a destination node in a mobile ad hoc network, querying for a piece of desired data in a wireless sensor network, and searching for a shared file in an unstructured peer-to-peer network. We limit our attention in this study to the class of controlled flooding search strategies where query/search packets are broadcast and propagated in the network until a preset TTL (time-to-live) value carried in the packet expires. Every unsuccessful search attempt results in an increased TTL value (i.e., larger search area) and the same process is repeated. The primary goal of this study is to derive search strategies (i.e., sequences of TTL values) that will minimize the cost of such searches associated with packet transmissions. The main results of this paper are as follows. 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 that minimize the expected search cost. We also derive the necessary and sufficient conditions %on the location distribution for two very commonly used search strategies to be optimal. When the probability distribution of the location of the object is not known a priori and the object is to minimize the worst-case search cost, we show that the best strategies are randomized strategies, i.e., successive TTL values are chosen from certain probability distributions rather than deterministic values. We show that given any deterministic TTL sequence, there exists a randomized version that has a lower worst-case expected search cost. We also derive an asymptotically (as the network size increases) optimal strategy within a class of randomized strategies.

REFERENCES

• 1: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 2: D. Braginsky and D.Estrin, "Rumor routing algorithm for sensor networks," Proc. International Conference on Distributed Computing Systems (ICDCS-22), 2002.
• 3: D. Johnson and D. Maltz, "Dynamic source routing in ad hoc wireless networks," Mobile Computing, pp. 153--181, 1999.
• 4: Jason Xie , Rajesh R. Talpade , Anthony Mcauley , Mingyan Liu, AMRoute: ad hoc multicast routing protocol, Mobile Networks and Applications, v.7 n.6, p.429-439, December 2002 [doi>10.1023/A:1020748431138]
• 5: Casey Carter , Seung Yi , Prashant Ratanchandani , Robin Kravets, Manycast: exploring the space between anycast and multicast in ad hoc networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939013]
• 6: S. Shakkottai, "Asymptotics of query strategies over a sensor network," Proceedings of IEEE Infocom, March 2004, Hong Kong.
• 7: Zhao Cheng , Wendi B. Heinzelman, Flooding strategy for target discovery in wireless networks, Proceedings of the 6th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/940991.940999]
• 8: Y. Baryshinikov, E. Coffman, P. Jelenkovic, P. Momcilovic, and D. Rubenstein, "Flood search under the california split rule," Operations Research Letters, vol. 32, no. 3, pp. 199--206, May 2004.
• 9: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 10: P. R. Kumar , Pravin Varaiya, Stochastic systems: estimation, identification and adaptive control, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 11: N. Chang and M. Liu, "Revisiting the TTL-based controlled flooding search: Optimality and randomization," EECS Technical Report CGR 04-06, 2004, University of Michigan, Ann Arbor.
• 12: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 13: Brad Williams , Tracy Camp, Comparison of broadcasting techniques for mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513825]
• 14: T-J.Kwon Y. Yi, M. Gerla, "Efficient flooding in ad hoc networks using on-demand (passive) cluster formation," Proceedings of Mobihoc, June 2003, Annapolis, USA.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
TTL, best worst-case performance, competitive ratio, controlled flooding search, data query, dynamic programming, file search, fixed strategy, optimal search, randomized strategy, strategy, wireless sensor networks