Expanding Ring-Based Search in Ad Hoc Networks

Expanding Ring-Based Search in Ad Hoc Networks

Dr Simon Shamoun

---

On demand routing protocols establish routes between nodes by forwarding route requests from one node to another until a path is found. This type of search is useful in a variety of settings, such as peer-to-peer networks, social networks, and any environment in which it is difficult to maintain lookup tables of the desired information. I will discuss a variety of search techniques we developed to keep expected search costs low based on a well studied technique called expanding ring search.

 

In expanding ring search, the searcher broadcasts a query to all nodes up to a specific number of hops away, and repeats the query with a higher limit on the hop distance until the target is found. For all these techniques, we can use dynamic programming to find the search sequence with minimum expected cost given the probability distribution of the number of hops between them and the distribution of costs of flooding up to different hop extents. The advantage of these techniques is that they weakly dominate expanding ring search.

 

I will focus on the advantages of a two-sided search, in which two nodes search for a path between them using separate expanding ring searches, and the challenges in deriving optimal sequences, and briefly discuss our two other techniques, elastic ring search and blocking expanding ring search.