NeTS-WN: Agile Wireless Ad Hoc Networks

这项提议的目标是开发先进的算法理论，从而在无线网络中实现现实生活。特别是，我们将试验一些先进的算法思想，灵感来自于PI过去的算法工作。我们将利用我们在Johns Hopkins的Wave Relay系统中使用的实用解决方案，该解决方案结合了两个新组件：用于路由和拓扑更新可伸缩性的Pulse协议，以及为无线网络量身定做的路由度量Medium Time Metric。在仿真实验中，Pulse协议针对大规模和移动性进行了优化，并且比AODV、DSR协议具有更好的可扩展性。事实上，仿真表明Pulse协议可以扩展到多达5000个移动节点。它使用主动构建的树，并在该树上使用按需快捷方式。它可以看作是主动和被动方法的结合。Medium Time Metric利用现代无线设备的多速率能力来最小化共享无线介质的消耗。这种跨层方法结合了来自物理和媒体访问控制层的每数据包反馈，从而显著提高了单播和组播路由的效率和灵活性。它大大优于最小跳路由度量，并已被证明优于其他建议的无线网络度量，如ETX度量。但是，使用新的算法思想来提高路由质量是可能的。第一个改进方向是用基于负载的度量来取代中等时间度量，我们称之为机会成本，它通过对拥塞区域的定价高于非拥塞区域来激励用户避开拥塞区域。有可能证明这会产生近乎最佳的性能。然而，这带来了振荡的危险。我们最近的理论工作展示了如何在有线网络中克服这个问题。此外，这些方法适用于连续的情况，而不是更离散的全有或全无设置，这是实现服务质量要求所必需的。我们目前正在研究对无线网络的适当扩展，以实现包含路由层和MAC层的最佳跨层设计。另一个需要研究的问题是以主动方式在网络中传播拓扑更新的可行性，因为这可能会使生成的解决方案不可扩展。我们在路由可伸缩性方面取得了重大的理论成就，我们希望在这种情况下应用这些成就，例如设计了第一个可证明具有内存效率和通信效率的路由方案，以及用于跟踪移动用户的对等目录。我们希望应用这些方法来提高无线网络中路由的可扩展性。具体地说，我们希望将Pulse协议扩展到与多棵树一起工作，并将研究构建此类树的理论上合理的方法

The goal of this proposal is developing advanced algorithmic theory that will lead to real-life implementation in wireless networks. In particular, we will experiment with some advanced and algorithmic ideas inspired by the past algorithmic work of the PI. We are going to leverage the practical solutions that we used in the Wave Relay system at Johns Hopkins, which combines two new components: the Pulse Protocol for scalability of routing and topology update, and the Medium Time Metric, which is a routing metric tailored for wireless networks. The Pulse protocol has optimized for large scale and mobility and is better scalability properties than AODV, DSR in simulations. In fact, simulations show Pulse protocol to scale for up to 5,000 mobile nodes. It uses a proactively-constructed tree with on-demand shortcuts on that tree. It can be viewed as combination of proactive and reactive methods.The Medium Time Metric exploits the multi-rate capability of modern wireless devices to minimize consumption of the shared wireless medium. This cross layer approach incorporates per-packet feedback from the physical and medium access control layers to dramatically increase efficiency and elasticity of both unicast and multicast routes. It is vastly superior to minimum hop routing metric, and has been shown to outperform other proposed metrics for wireless networks, such as ETX metric.However, it is possible to augment the quality of routing using new algorithmic ideas.First direction of improvement is to replace Medium Time Metric with load-based metric, that we call the opportunity cost, which provides incentives to users to avoid congested areas by pricing them higher compared to the un-congested areas. It is possible to prove that this yields near-optimal performance. However, this introduces the danger of oscillations. Our recent theoretical work shows how to overcome this problem in wired networks. Moreover, these methods work for the continuous case rather than for more discrete all-or-nothing setting that is necessary to accomplish QoS requirements.We are currently examining appropriate extensions to wireless networks to achieve best cross-layer design incorporating both routing and MAC layers.Another issue that needs to be investigated is feasibility of propagating topology updates thru the network in a proactive manner, as it may make the resulting solution non-scalable. We have significant theoretical accomplishments in the area of scalability of routing that we would like to apply in this setting such as designing the first provably memory-efficient and communication-efficient routing schemes, and peer-to-peer directories for tracking mobile users. We would like to apply these methodologies for improved scalability of routing in wireless networks. Specifically, we would like to extend the Pulse protocol to work with multiple trees and will be studying theoretically justified methods of constructing such trees