Q. What gave you the idea?

A. My current area of research involves designing network architectures and protocols for large-scale ad hoc and sensor networks. These are networks that comprise of, potentially, thousands of small mobile devices (such as PDAs, laptops, and wireless sensors). Since these devices are power-constraint, efficiency is of prime concern. Also, their mobility renders the problem of locating a specific node (or resource) in such networks a very challenging problem. The simplest way to discover resources in such networks (according to previous work in this area) is flooding (either global flooding throughout the network, or expanding ring search involving repeated controlled flooding). This approach incurs unacceptable overhead in large-scale networks and consumes a lot of power, and hence should be completely avoided if at all possible.
Other, more scalable approaches, propose hierarchical structures, in which a group of wireless nodes forms a cluster and elects a cluster-head. That cluster-head is responsible for communication between this group and the other groups. One major problem to this approach in mobile networks, is that it is susceptible to single-point of failure (or single point of movement) scenarios. Meaning that if the cluster-head fails or moves, this group would have to re-configure itself (using more communication and power) to elect another head, so on. Unfortunately, this may happen quite frequently as mobility is part of the normal operation in ad hoc and sensor networks.

So, I made a lot of effort to investigate new approaches to network architecture for such highly dynamic environments. One concept that I found appealing is the small worlds concept. Previous work (by Milgram in the 60's and recently by Watts in the late 90's) suggested the existence of small worlds (also known as 'six degrees of separation') in social networks (and other settings). Also, it suggested that having short cuts (or far away acquaintances) helps in reducing the degrees of separation between people. [If I know a person X, and he/she knows person Y that I do not know directly, then I am two degrees of separation from Y]. So, one idea was to use the concept of short cuts in order to discover resources in ad hoc and sensor networks. For that I had to re-visit the small world concept and its applicability to wireless networks. Questions I wanted to answer included, how many short cuts should be created in order to be effective? where should these short cuts be located? (the shorter the short cut the better in terms of creating and maintaining it, but what's its effectiveness?). Previous work suggested that these short cuts should be random. This, however, may create unpredictable overhead for our network. Adding more structure and constraints to the short cuts (in order to control the overhead) while maintaining the desirable small world characteristics was one goal of my research.

Even if the concept is applicable from this new perspective of resource discovery, how will we create and use these short cuts in practice? In mobile networks it would be a continuous process to create and maintain short cuts, because the nodes continuously move. Mobility has always created new challenges in wireless networks. So, the second idea is actually take advantage of mobility to create these short cuts.

Q. How exactly does adding only a few random links cause path length to be reduced so drastically? How does clustering come into play?

A. A random link creates a short cut between two ends (or network nodes) that were previously far away. Although such link is between two nodes, it also affects the groups of nodes that are close to these two nodes, and groups close to these groups, so on. For example, if I know a person in a far away country, I will probably also get to know his/her acquaintances, and they will get to know my acquaintances, so on. This chain effect is what leads to the significant reduction in degrees of separation (or path length) with only a few number of added links.

Clustering, on the other hand, represents (to some extent) the underlying network structure. One measure of clustering could be 'how many of my direct acquaintances are also direct acquaintances?' Adding only a very small fraction of links usually does not alter the structure of the network and does not change the clustering measure (or clustering coefficient) drastically. One may view clustering as a localized characteristic of a network, while path length as a more global characteristic of a network. In a way, keeping the clustering coefficient relatively stable translates into little effort exerted at the network architecture level. Hence, this leads to the possibility of devising efficient architectures that do not change the structure of the network drastically but do lead to significant reduction in path length.

Q. I'm hoping you can briefly describe your study.

A. The study starts by investigating the applicability of small world concepts to large-scale wireless ad hoc and sensor networks. The first part describes a set of re-wiring and link addition experiments to graphs that correspond to wireless networks. These experiments illustrate several points. First, the reduction in path length observed in earlier small world studies was also observed in wireless networks by adding only a few number of links (e.g., addition of 0.2% to 20% of the links results in 25% to 70% reduction in path length), while hardly affecting clustering. For example, in a network of 1000 nodes and around 5000 links, adding 25-150 links achieves 40-60% reduction in path length. Second, maximum reduction in path length does not occur with short cuts of maximum distance (i.e., diameter of the network). Rather, it occurs with short cuts of distance of 25-40% of the maximum distance in the network. Hence, the two ends of the short cut need not be chosen randomly, but may be chosen within a distance that is a small fraction of the network diameter. This has a practical implication, since now we can introduce short cuts that are not hard to create and maintain, and that have overhead that is predictable and manageable.

The study then establishes a connection between the above understanding and resource discovery in large-scale ad hoc and sensor networks. The main connection is established by defining the concept of degrees of separation as the number of search queries that are needed by a source node in order to find a target node. Reducing such degrees of separation leads to reduction in resource discovery overhead. Hence, from that perspective, the created short cuts are logical (not physical) short cuts.

A new architecture for resource discovery is then proposed based on two main components. The first is zones, in which every node knows a few other nodes within its neighboring vicinity (or zone). The second is contacts. Contacts represent short cuts that transform the wireless network into a small world. These are created to extend beyond the zone and increase the network view for each node. A question is posed as to how to choose contacts located at the desirable region (e.g., between 25-40% of the network diameter) efficiently? Keep in mind that the nodes are mobile and nodes only know routes to other nodes within their own zone (up to perhaps 5-10% of the network diameter). The proposed answer to this question is for a node to choose potential (or candidate) contacts from within its own zone, leveraging knowledge of other nodes therein (with minimum or no extra overhead). These candidate contacts are then tracked, using low overhead mechanisms, as they gradually move away from the node's zone and are promoted into contacts if/when they reach the desirable region. Such nodes are used in resource discovery queries and should produce a significantly reduced degrees of separation for the search. Two protocols are proposed for selecting and promoting contacts. The study provides evaluation of these protocols under mobility conditions. Initial results illustrate that efficient mechanisms can be devised to track candidate contacts that are likely to move (and remain for some time) in the desirable region, and thus are quite useful for resource discovery.

In contrast to previous work in this area, the proposed architecture does not assume knowledge of location or geographical information, nor does it use any kind of global flooding.

Q. What was the technical or conceptual breakthrough that allowed you to prove this?

A. First, understanding that wireless networks (due to physics of radio transmission) are by nature spatial (or geographical) graphs, in which the connection is a function of distance. Based on simulation models for various types of such networks, and based on carefully devised re-wiring and link addition experiments, I was able to show the ability to create a small world out of a spatial graph (or a wireless network) using short cuts that extend only a small fraction of the network diameter. This provides the predictability and manageability required for scalability (i.e., to make the architecture applicable to very large-scale networks).

Second, the concept that mobility can (and should) be utilized to increase the network view per node. Mobility has usually been viewed as a challenge in wireless networks and for good reasons, but I have shown that it may be used to assist in creating efficient resource discovery protocols.

Q. Was there anything surprising about your results? Why?

A. Yes, the fact that at a certain (relatively small) distance (not the longest distance) for short cuts we get the maximum decrease in degrees of separation. Also the fact that we can utilize mobility in wireless networks to design very efficient protocols to choose (potential) future short cuts with high likelihood of success.

Q. How does your work fit into the body of work on network structure's, and what is different about it?

A. I have studied wireless (ad hoc and sensor) networks that belong to the class of 'spatial' or geographical graphs or networks. These are networks in which physical links are created as a function of the distance between the nodes. From this perspective, previous work has shown that such graphs or networks are (by their own nature) highly clustered with very high path lengths (as compared to random graphs). Hence, it is hard to create small worlds in such networks by introducing physical short cuts. I have also observed such characteristics in my research. Previous work has also shown that short cuts in relational graphs (in which links are not restricted by distance) small worlds may be created from regular graphs by adding only a few random links (to act as short cuts).
However, if we consider logical (viz. physical) short cuts, for resource discovery purposes, and define degrees of separation as the number of queries required for search, then we indeed can re-cast the problem to enable creation of logical small worlds in spatial graphs (i.e., wireless networks). That is what I have done for my study. What was also different in my study is that I simulated various models of wireless networks and performed new experiments that investigate the space of possible distances for short cuts. Through such experiments I was able to show the result that short cuts in spatial networks need not be of maximum distance (and not even close to maximum distance). In fact, they may be of very manageable and predictable distance and still achieve the maximum reduction in degrees of separation.

Also, previous work on network structures did not study the dynamic characteristics of graphs under mobility conditions. My study investigates such dynamics under mobility conditions in several ways. First, the protocols I designed utilize mobility for efficient contact selection. Second, the evaluation carried out in my study included performance analysis of the proposed architecture under various mobility degrees.

Q. How could this research eventually be applied practically?

A. This work is specifically applicable to infrastructure-less wireless mobile networks. These include the various kinds of ad hoc and sensor networks. There are various emerging classes of applications for ad hoc and sensor networks, especially in the areas of search and rescue, vehicular networks, habitat and environmental monitoring, remote reconnaissance missions, rapidly deployable networks, battlefields, among others.
Locating resources in such environments is quite hard for large-scale networks. My research could help in providing an efficient architecture for discovery of resources in such networks.

Q. What are the next steps in your research? What are you ultimately aiming for?

A. The next steps of my research include more experimentation and analysis in hopes of understanding the architectural dynamics and protocol performance over richer mobility and network models. Specifically, I want to answer questions about when we can take advantage of mobility and why. I also plan to provide a set of adaptive protocols that are flexible enough to allow mobility utilization when possible, yet still provide efficient operation when mobility cannot be utilized. Work is already underway in this direction.
Furthermore, I plan to build a prototype network in my networking wireless and sensor networks lab at USC, to demonstrate the feasibility of the proposed architecture.

My ultimate goal is to realize (practically) networks of small devices and sensors that scale up to tens of thousands (or even millions) of nodes. I believe that resource discovery is one major component of such future networks. My research attempts to provide a very efficient solution to such a challenging problem, such that these networks can be deployable in many aspects of our lives.