Visibility-Graph-Based Shortest-Path Geographic Routing in Sensor Networks
Visibility-Graph-Based Shortest-Path Geographic Routing in Sensor Networks
复制标题
DOI：
10.1109/infcom.2009.5062091
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
Guang Tan;M. Bertier;Anne-Marie Kermarrec
中科院分区：
文献类型：
--
作者：
Guang Tan;M. Bertier;Anne-Marie Kermarrec
研究了静态传感器网络中的最短路径地理路由问题。现有的算法通常基于本地邻居的节点信息来做出路由决策。然而，Kuhn等人证明了这一点。这样的设计约束导致布线性能的极不希望的下限：如果最佳路线具有长度c，则在最坏的情况下，由任何局部算法产生的路线具有长度Ω(C 2)，这可以任意地比最优路线差。我们提出了Vigor，这是一种基于可见图的路由协议，它产生长度为Θ(C)的路由。我们的设计是基于一个大大减少的可见度图的构建，该图引导节点找到接近最优的路径。每个节点在状态信息和消息传输方面的协议开销仅取决于现场大型拓扑特征的复杂性，而不是取决于网络规模。仿真结果表明，该协议在平均和最差情况下的性能都明显优于GPSR和GOAFR+等局部化协议，并具有合理的额外开销。
We study the problem of shortest-path geographic routing in a static sensor network. Existing algorithms often make routing decisions based on node information in local neighborhoods. However, it is shown by Kuhn et al. that such a design constraint results in a highly undesirable lower bound for routing performance: if a best route has length c ,t hen in the worst case a route produced by any localized algorithm has length Ω(c 2 ), which can be arbitrarily worse than the optimal. We present VIGOR, a VIsibility-Graph-based rOuting pRotocol that produces routes of length Θ(c). Our design is based on the construction of a much reduced visibility graph, which guides nodes to find near-optimal paths. The per-node protocol overheads in terms of state information and message transmission depend only on the complexity of the field's large topological features, rather than on the network size. Simulation results show that our protocol dramatically outperforms localized protocols such as GPSR and GOAFR+ in both average and worst cases, with reasonable extra overheads.