Flooding Strategy for Single Target Discovery in Wireless Sensor Networks

Abstract: We address a fundamental problem concerning the optimal flooding strategy to minimize cost and latency for target discovery in wireless networks. Should we flood the network for only once, or should we apply a so-called "expansion ring" scheme to reduce the cost? If the "expansion ring" scheme is better in terms of the average cost, how many rings should there be and what should be the radius of each ring? We explore these question over categorized wireless networks based on network scale and flooding control methods. We prove that when using a geography-based flooding control method, the number of flooding attempts should be one. When using a hop-based flooding control method, we prove that two-ring and three-ring schemes can reduce the cost in an insignificant amount. Simulations validate our claim that one-ring search is good enough for single target discovery.

In the above figure, M indicates the estimated network hop diameter. However, despite the fact that we find out the optimal parameters for saving searching cost, we notice that the saving is as minimal as less than 8%. This ratio decreases as the network scale increases. We argue that one-ring search is good enough for single target discovery, and more than two searches can only increase the searching cost.

Searching Strategy for Multi-target Discovery in Wireless Networks

Abstract: We address a fundamental problem concerning the optimal searching strategy in terms of searching cost for the multi-target discovery problem in wireless networks. In order to find the nearest k targets from a total of m members with the least cost, how many searching attempts should we use, and how large should each searching area be? We model the problem and derive a general formula for the expected cost as a function of the parameters of the number of searching attempts n and the searching area for each attempt, A_i. We propose several algorithms to determine the parameters to achieve the optimal cost, either pre-calculated or performed online. We experiment these algorithms on general scenarios. The results show that our algorithms perform consistently close to optimal, and they exhibit much better performance than traditional schemes.

When searching k out of m targets, if n searches are used and each searching area is A_i, the searching cost C is

The performance of our algorithm ORS compared to the EXPansion ring and the DSR scheme for different searching conditions is shown as below.

Our algorithm ORS shows a consistent better performance than the other two schemes, in terms of both cost and latency.

Adaptive Local Searching and Caching Strategies for on-demand Routing Protocols in MANET

Abstract: On-demand routing protocols are widely used in mobile ad hoc networks due to their capability of adjusting to frequent network topology changes within acceptable routing overhead. In order to further reduce routing overhead, especially the overhead from the network-wide flooding in the route discovery phase, two techniques named routing caching and searching localization are usually performed. In this work, we reinvestigate these two techniques, in particular their joint effect on the routing overhead. For quantitative analysis purposes, we define one essential parameter for each technique: routing cahcing validation probability and local searching radius. We propose a new routing strategy that adapts to the current caching availability and is self-tunable towards the optimal performance. We demonstrate through extensive simulations that this routing strategy can reduce the routing overhead significantly under general scenarios.

For more information about this project, contact Zhao Cheng.