Greedy Geographic Routing in Large-Scale Sensor Networks: A Minimum Network Decomposition Approach
Greedy Geographic Routing in Large-Scale Sensor Networks: A Minimum Network Decomposition Approach
复制标题
大规模传感器网络中的贪婪地理路由：最小网络分解方法
DOI：
10.1109/tnet.2011.2167758
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
Anne-Marie Kermarrec
中科院分区：
文献类型：
--
作者：
Guang Tan;Anne-Marie Kermarrec
在地理（或几何）路由中，消息默认以贪婪的方式路由：当前节点总是将消息转发到距离目的地最近的邻居节点。尽管它的简单性和一般效率，这种策略本身并不能保证交付，由于存在局部最小值（或死胡同）。克服局部极小值需要节点保持额外的非局部状态或使用辅助机制。我们研究如何促进贪婪转发使用最小数量的这种非局部状态在拓扑复杂的网络。具体来说，我们调查的问题，分解成一个给定的网络的最小数量的greenerable可路由组件（GRC），贪婪路由是保证工作。我们通过考虑连续域中的问题的近似版本来处理它，其中有一个中心概念，称为可路由区域（GRR）。给出了GRR的几何性质和路由能力的完整刻画。然后，我们开发简单的近似算法的问题。这些结果导致一个实用的路由协议，在连续域中的路由拉伸低于7，在几个现实的网络设置接近1。
In geographic (or geometric) routing, messages are by default routed in a greedy manner: The current node always forwards a message to its neighbor node that is closest to the destination. Despite its simplicity and general efficiency, this strategy alone does not guarantee delivery due to the existence of local minima (or dead ends). Overcoming local minima requires nodes to maintain extra nonlocal state or to use auxiliary mechanisms. We study how to facilitate greedy forwarding by using a minimum amount of such nonlocal states in topologically complex networks. Specifically, we investigate the problem of decomposing a given network into a minimum number of greedily routable components (GRCs), where greedy routing is guaranteed to work. We approach it by considering an approximate version of the problem in a continuous domain, with a central concept called the greedily routable region (GRR). A full characterization of GRR is given concerning its geometric properties and routing capability. We then develop simple approximate algorithms for the problem. These results lead to a practical routing protocol that has a routing stretch below 7 in a continuous domain, and close to 1 in several realistic network settings.
登录
查看更多内容
DOI：
10.1109/infcom.2009.5062091
发表时间：
2009-04
期刊：
IEEE INFOCOM 2009
影响因子：
--
作者：
Guang Tan;M. Bertier;Anne-Marie Kermarrec
通讯作者：
Guang Tan;M. Bertier;Anne-Marie Kermarrec
影响因子：
7.9
作者：
Noa Arad;Y. Shavitt
通讯作者：
Noa Arad;Y. Shavitt
DOI：
10.1145/1161089.1161104
发表时间：
2006-09
期刊：
--
影响因子：
--
作者：
Yue Wang;Jie Gao;Joseph S. B. Mitchell
通讯作者：
Yue Wang;Jie Gao;Joseph S. B. Mitchell
DOI：
10.1007/bf01928918
发表时间：
1988-05
期刊：
Zeitschrift für Operations-Research
影响因子：
--
作者：
H. Alt;E. Welzl
通讯作者：
H. Alt;E. Welzl
DOI：
10.1137/0211025
发表时间：
1982-05
期刊：
SIAM J. Comput.
影响因子：
--
作者：
David Lichtenstein
通讯作者：
David Lichtenstein