 Wave Relay™ is the first technology to have solved the infamous peer-to-peer routing scalability problem, which for the last 3 decades was considered to be unsolvable in spite of tremendous joint effort by researchers in academia, military and industry.
Wave Relay™ achieves an unprecedented combination of scalability and low routing overhead without sacrificing the quality of routing, such as rate and reliability. As a result, our technology can scale to thousands of devices via multiple hops enabling true peer-to-peer connectivity while still providing high quality routing that is capable of delivering live VoIP, video, and other extremely demanding applications in a constantly changing wireless network topology.
Our proprietary algorithms go well beyond just a new engineering solution. The commercial and scientific importance of the wireless peer-to-peer routing problem is well known.
Scalability
Scalability of routing is one of the fundamental challenges that have historically limited the performance of MANETs. In the Internet, this problem was solved using hierarchical routing schemes. However, in the wireless domain, hierarchical schemes clash with the inherently flat and dynamic nature of ad hoc communication systems. Existing techniques for routing on flat networks, such as link state, are unscalable as they require storage and communication complexity that grows quadratically with the number of nodes (Nē). However, achieving truly scalable flat routing is possible. The Wave Relay™ system provides the first provable algorithmic methodology that enables logarithmic overhead in flat routing. While this strategy was not needed in the hierarchically structured Internet, it is ideal for use in large flat wireless networks. The Wave Relay™ routing architecture is the first truly scalable routing strategy for wireless ad hoc networks. This scalability directly affects the network bandwidth efficiency by minimizing the resources needed to establish and maintain routes, particularly in large highly mobile networks.
Why Existing Approaches Fail:
A large number of MANET routing protocols have been proposed by the ad hoc wireless networking community. Typically these have adopted one of two major strategies: On-Demand and Proactive. Proactive link-state routing protocols maintain a database of every link in the network. Each node monitors their neighboring links and reports changes to the entire network. The highly dynamic nature of wireless links can cause this strategy to overwhelm the network with topology information, particularly as the size of the network grows. In addition, link state approaches are forced to use a coarse grain routing metric, since a fine grain metric would only further increase their route maintenance overhead. This restriction further reduces the performance of this class of protocols.
In contrast to proactive protocols, on-demand protocols do not track any topology information until data needs to be routed. When a data packet arrives, on-demand protocols utilize a flooding operation to determine a route to the destination. This route is typically used until it breaks, in which case the flooding operation is repeated in order to find a new route. While at first glance this strategy dramatically improves scalability, this is only the case in a network with no traffic flows. Link volatility forces on-demand protocols to continuously re-flood the network as the connectivity changes. As a result, on-demand protocols have a similar scalability issue as link state protocols; the use of the global flooding operation in response to local changes in connectivity. In addition, since reactive protocols do not have any link metric data a priori, they are also forced to use a course grain metric (determined on the fly) which results in poor route selection and inefficient utilization of the wireless medium.
 Reach-back:
In current military networks more then 90% of the data is sent to a common destination. This is partially due to the data gathering and analysis architecture of current systems and partially due to the hierarchical command structure imposed by the military. Wave Relay™ is extremely optimized for the reach-back communication pattern and provides near optimal route selection. By optimal route selection, we mean that Wave Relay™ is able to select communication paths that minimize consumption of the shared wireless medium, maximize end-to-end throughput in a heterogeneous environment, and maximize the residual capacity to other flows in the network. This allows Wave Relay™ to simultaneously optimize the routing based on both the best path for the data flow and the best path to optimize the network capacity. Wave Relay™’s routing protocol is continuously adjusting its reach back path in order to maintain these performance characteristics. Scalable proactive maintenance of the reach back path means that greater then 90% of military traffic is optimally routed with zero route setup delay.
Peer-to-Peer Connectivity:
While a large fraction of the military’s traffic might be destined for specific locations, a still significant fraction of the traffic needs to be routed towards arbitrary peer-to-peer destinations. We characterize the performance of routing protocols using the term ‘stretch’, where the stretch is the difference in metric (or efficiency or optimality) of the routing protocols selected path and the best possible path that existed in the same metric space. The best possible path can be determined a posteriori based on a comparison of all of the possible options. Since no routing protocol can ever anticipate the exact performance of every link in the network (since these links are continuously changing) all routing protocols exhibit stretch. Link state protocols track course grain routing metrics and use topology dissemination techniques which directly trade stretch for protocol scalability. On-demand protocols select routing paths without taking into account specific link characteristics, only relying on the results of their route request flood. Therefore on-demand protocols trade fixed proactive link estimate overhead for increased route stretch. The Wave Relay™ system also trades some stretch in the peer to peer case for increased scalability. However, independent 3rd party evaluations of the Wave Relay™ routing mechanisms show that in networks with 100’s of nodes, the stretch is limited to less then 5% on average. This means that any competing routing approach can only do up to 5% better then Wave Relay™ in terms of route selection and it would have to accomplish this using less overhead then Wave Relay™ whose routing overhead is fixed and extremely low. In addition, these preliminary studies only considered Wave Relay™’s ability to select a route with no other load on the network. Wave Relay™ is designed to perform better when other flows exist in the network. This means that in practice, Wave Relay™ is already reducing the stretch to be significantly less then 5%. This scalable peer-to-peer routing capability is a truly spectacular aspect of the Wave Relay™ system which sets it apart from all competing approaches.
 Mobility:
In military networks, most of the nodes are continuously in motion. Soldiers are moving through complex urban city environments, vehicles are continuously driving around the battlefield, and unmanned aerial vehicles are flying at high speeds overhead. All of these mobile assets need to remain continuously connected to enable arbitrary peer to peer communication as well as connectivity back to the Global Information Grid (GIG). The Wave Relay™ system is design and tested specifically in complex urban environments where channel
conditions are continuously fluctuating and
fading and where
connectivity is continuously changing as nodes move around obstructions which create fast RF transitions.
The Wave Relay™ system has a few specific properties which made it ideally suited for these complex environments. Unlike both link state and on-demand approaches, in the Wave Relay™ system local changes in connectivity do not create global overhead in the network. In link state protocols when a change occurs in local connectivity, the change needs to be flooded through the network such that all the nodes can update their link state databases. This property makes this class of protocols poorly suited for providing connectivity in a mobile urban environment. On-demand protocols on the other hand need to flood the whole network every time a link breaks on an active route. This local connectivity change again results in global overhead to the whole network, making the approach unscalable and poorly suited for dynamic environments. Wave Relay™ is able to use path adaptation techniques and a make before break strategy to increase route agility utilizing only local coordination along active paths. Wave Relay™ utilizes an extremely fine grained routing metric which allows it to continuously shift the routing path to minimize the routing metric as conditions change. Wave Relay™ is able to continuously shift paths without causing a disruption to the data flow, allowing routing adjustments on paths which are even carrying latency sensitive voice traffic. This fundamental difference in routing approach makes Wave Relay™ ideally suited for providing connectivity between mobile nodes in a complex urban environment.
Optimized Broadcasting:
In contrast to commercial networks, military networks rely heavily on multicast and broadcast communication to disseminate tactical information. This communication pattern motivates the need for a MANET protocol that is both scalable and efficient with respect to both unicast and multicast data delivery. Many MANET protocols (both proactive link-state and on-demand) overwhelm the network by broadcasting topology updates. This scalability barrier has prompted an extensive research effort into reducing the overhead of the network wide broadcast operation.
The Wave Relay™ system is designed to maximize the broadcast capacity of the network and to minimize the overhead caused by broadcast message dissemination. While simultaneously optimizing efficiency, Wave Relay™ also implements techniques which increase broadcast reliability. Unlike unicast messages which are typically acknowledged hop by hop at the medium access control layer to provide high reliability, broadcast packets are extremely susceptible to getting lost due to collisions. Wave Relay™’s broadcast dissemination techniques dramatically increase reliability with very little increase in overhead.
In addition to increasing message reliability, Wave Relay™ also employs techniques to decrease the overhead of broadcasting which increases the network’s broadcast capacity. The dissemination strategy provides between 1 and 2 orders of magnitude increase in broadcast capacity. In addition, unlike existing approaches (Connected Dominating Set, Neighbor Set Difference, and Probabilistic) which are commonly used by link-state protocols, Wave Relay™ is able to reduce the broadcast overhead even in low density networks. Wave Relay™ is able to provide these broadcast optimizations using only the information it was already tracking for the unicast aspects of the protocol. This allows optimized broadcasting with no additional control packet overhead.
 Incorporating the Airborne Layer:
In order to enable easy integration of the Wave Relay™ MANET system into existing unmanned aerial vehicle (UAV) platforms, careful attention was given to size, weight, and power consumption. The Wave Relay™ system is available in an embedded 4 x 4 x 0.6 inch form factor which allows it to be integrated into even the smallest UAV platforms. The total weight of the Wave Relay™ board is approximately 4 oz. In addition to minimizing both size and weight, the Wave Relay™ radio also minimizes power consumption and only consumes around 5 Watts on average. This careful attention to both weight and power consumption enables the UAV’s to fly for longer periods of time. The Wave Relay™ system has already been successfully tested and deployed on UAV’s developed by Procerus Technologies. |
