Landmark Selection and Greedy Landmark-Descent Routing for Sensor Networks
Landmark Selection and Greedy Landmark-Descent Routing for Sensor Networks
复制标题
DOI：
10.1109/infcom.2007.83
复制
发表时间：
2007-05
期刊：
影响因子：
--
通讯作者：
A. Nguyen;Nikola Milosavljevic;Qing Fang;Jie Gao;L. Guibas
中科院分区：
文献类型：
--
作者：
A. Nguyen;Nikola Milosavljevic;Qing Fang;Jie Gao;L. Guibas
研究了固定无线通信节点网络中基于地标路由的地标选择问题。我们提出了一种不依赖全局时钟同步的分布式地标选择算法，以及一种配套的基于局部贪婪地标的路由方案。我们假设没有节点位置信息，并且每个节点可以与其地理上的一些相邻节点通信。每个节点通过其到少量附近地标的跳数距离来命名。在一个节点上执行贪婪路由，使其地标距离向量与目标距离向量相等。这是通过遵循到地标的最短路径来实现的，从而最大化其到源和目的地的距离之比。此外，我们还提出了一种方法，通过虚拟扩展网络边界来缓解路由到边界附近目的地的困难。当贪婪路由与我们的地标选择方案相结合时，相对于可能的最佳路径具有可证明的有界路径拉伸，并保证数据包在连续域内传输。在离散域，我们的仿真表明，路标选择方案是有效的，同伴路由方案在现实环境下表现良好。地标选择和贪心路由都没有特定的通信模型，都适用于非对称链路。尽管有些分析很重要，但算法简单、灵活且成本效益高，足以保证实际部署。
We study the problem of landmark selection for landmark-based routing in a network of fixed wireless communication nodes. We present a distributed landmark selection algorithm that does not rely on global clock synchronization, and a companion local greedy landmark-based routing scheme. We assume no node location information, and that each node can communicate with some of its geographic neighbors. Each node is named by its hop count distances to a small number of nearby landmarks. Greedy routing at a node is performed to equalize its vector of landmark distances to that of the destination. This is done by following the shortest path to the landmark that maximizes the ratio of its distances to the source and the destination. In addition, we propose a method to alleviate the difficulty in routing to destinations near the boundaries by virtually expanding the network boundaries. The greedy routing, when combined with our landmark selection scheme, has a provable bounded path stretch relative to the best path possible, and guarantees packet delivery in the continuous domain. In the discrete domain, our simulations show that the landmark selection scheme is effective, and the companion routing scheme performs well under realistic settings. Both the landmark selection and greedy routing assumes no specific communication model and works with asymmetric links. Although some of the analysis are non-trivial, the algorithms are simple, flexible and cost-effective enough to warrant a real-world deployment.