GLIDER: gradient landmark-based distributed routing for sensor networks
GLIDER: gradient landmark-based distributed routing for sensor networks
复制标题
DOI：
10.1109/infcom.2005.1497904
复制
发表时间：
2005-03
期刊：
影响因子：
--
通讯作者：
Qing Fang;Jie Gao;L. Guibas;V. Silva;Li Zhang
中科院分区：
文献类型：
--
作者：
Qing Fang;Jie Gao;L. Guibas;V. Silva;Li Zhang
我们提出了基于梯度地标的分布式路由（GLIDER），这是一种新的无线通信节点网络命名/寻址方案和相关的路由算法。我们假设节点是固定的（尽管它们的地理位置不一定是已知的），并且每个节点可以与其地理上的一些相邻节点进行无线通信——这是传感器网络中的常见场景。我们开发了一种协议，该协议在预处理阶段发现传感器场的全局拓扑结构，并作为副产品，将节点划分为可路由的块-节点放置足够密集和规则的区域，局部贪婪方法可以很好地工作。这样的全局拓扑不仅包括连通性，还包括更高阶的拓扑特征，比如洞的存在。我们通过包含该节点的块的名称和一组局部坐标来寻址每个节点，这些坐标来源于节点与与其自身和相邻块相关的某些地标节点之间的连接图距离。我们使用瓦片邻接图进行全局路由规划，使用局部坐标实现瓦片间和瓦片内的实际路由。我们证明了使用这种方案可以非常简单地实现高效的负载均衡全局路由。
We present gradient landmark-based distributed routing (GLIDER), a novel naming/addressing scheme and associated routing algorithm, for a network of wireless communicating nodes. We assume that the nodes are fixed (though their geographic locations are not necessarily known), and that each node can communicate wirelessly with some of its geographic neighbors - a common scenario in sensor networks. We develop a protocol which in a preprocessing phase discovers the global topology of the sensor field and, as a byproduct, partitions the nodes into routable tiles - regions where the node placement is sufficiently dense and regular that local greedy methods can work well. Such global topology includes not just connectivity but also higher order topological features, such as the presence of holes. We address each node by the name of the tile containing it and a set of local coordinates derived from connectivity graph distances between the node and certain landmark nodes associated with its own and neighboring tiles. We use the tile adjacency graph for global route planning and the local coordinates for realizing actual inter- and intra-tile routes. We show that efficient load-balanced global routing can be implemented quite simply using such a scheme.