Use this resource - and many more! - in *your* textbook!

AcademicPub holds over eight million pieces of educational content for you to mix-and-match *your* way.

**Not an educator**but still interested in using this content? No problem! Visit our provider's page to contact the publisher and get permission directly.

# Controlled Flooding Search in a Large Network

## By: Mingyan Liu; Chang, N.B.;

2007 / IEEE

### Description

This item was taken from the IEEE Periodical ' Controlled Flooding Search in a Large Network ' 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 consider the class of controlled flooding search strategies where query/search packets are broadcast and propagated in the network until a preset time-to-live (TTL) value carried in the packet expires. Every unsuccessful search attempt, signified by a timeout at the origin of the search, results in an increased TTL value (i.e., larger search area) and the same process is repeated until the object is found. The primary goal of this study is to find search strategies (i.e., sequences of TTL values) that will minimize the cost of such searches associated with packet transmissions. Assuming that the probability distribution of the object location is not known a priori, we derive search strategies that minimize the search cost in the worst-case, via a performance measure in the form of the competitive ratio between the average search cost of a strategy and that of an omniscient observer. This ratio is shown in prior work to be asymptotically (as the network size grows to infinity) lower bounded by 4 among all deterministic search strategies. In this paper, we show that by using randomized strategies (i.e., successive TTL values are chosen from certain probability distributions rather than deterministic values), this ratio is asymptotically lower bounded by e. We derive an optimal strategy that achieves this lower bound, and discuss its performance under other criteria. We further introduce a class of randomized strategies that are sub-optimal but potentially more useful in practice

**Related Topics**

Wireless Sensor Networks

Ad Hoc Networks

Mobile Radio

Peer-to-peer Computing

Random Processes

Statistical Distributions

Randomized Strategy

Controlled Flooding Search Strategy

Mobile Ad Hoc Network

Wireless Sensor Network

Unstructured Peer-to-peer Network

Query-search Packets

Time-to-live Value

Probability Distribution

Peer To Peer Computing

Wireless Sensor Networks

Costs

Mobile Ad Hoc Networks

Broadcasting

Probability Distribution

Collaborative Work

H Infinity Control

Anodes

Routing Protocols

Wireless Networks

Best Worst-case Performance

Competitive Ratio

Controlled Flooding Search

Query And Search

Randomized Strategy

Time-to-live (ttl)

Computing And Processing

Communication, Networking And Broadcast Technologies

Engineering

Packet Transmissions