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.
Optimal controlled flooding search in a large wireless network
By: Chang, N.B.; Mingyan Liu;
2005 / IEEE / 0-7695-2267-X
This item was taken from the IEEE Conference ' Optimal controlled flooding search in a large wireless 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 wireless network. We consider 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. 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 lower bounded by 4 among all deterministic search strategies. In this paper we show that by using randomized strategies this ratio is lower bounded by e. We derive an optimal strategy that achieves this lower bound, and discuss its performance under other performance criteria.
Optimal Controlled Flooding Search
Large Wireless Network
Deterministic Search Strategy
Wireless Sensor Networks
Mobile Ad Hoc Networks