Brief announcement: routing with obstacle avoidance mechanism with constant approximation ratio
Brief announcement: routing with obstacle avoidance mechanism with constant approximation ratio
复制标题
简要公告：具有恒定逼近比避障机制的路由
DOI：
10.1145/1835698.1835727
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
J. Rolim
中科院分区：
文献类型：
--
作者：
Florian Huc;Aubin Jarry;Pierre Leone;J. Rolim
我们研究了传感器网络中的消息路由问题，其中节能问题是至关重要的。在本文中，我们提出了ROAM2，它是对[HJL+09]中提出的具有避障机制的ROAM(路由协议)的改进。该分布式协议具有消息和计算开销低的轻型障碍物检测和避障组件，以及沿短路径发送消息的路由组件，从而节省了能量。我们对其进行了改进，使其具有100%的投递率，并证明了漫游发现的路径具有与最短路径长度相当的高概率路径。此外，我们还证明了以贪婪的方式计算的任何路径的长度的一个一般性结果。虽然漫游在节点中使用一位内存(即使有多个目的地)，但在[KWZ08]中，证明了任何不使用任何传感器内存的地理路由算法都不能计算出一条长度保证小于O(L2)阶的路径，其中L是最短路径的长度。最后，我们通过仿真比较了漫游与GPSR(或GFG)[KK00]，[MLNR08]和SLGF[JMLW08]中提出的算法的能量效率，验证了我们的理论结果
We study the problem of routing messages in sensor networks where the energy saving issue is essential. In this paper, we propose ROAM2, an improvement of ROAM (Routing protocol with Obstacle Avoidance Mechanism) proposed in [HJL+09]. This distributed protocol has a light obstacle detection and avoidance component with low message and computation overhead and a routing component which sends messages along short paths, thus saving energy. We improved it so that is has an 100% delivery rate and we prove that ROAM finds with high probability paths whose lengths are comparable to the length of the shortest paths. Furthermore, we prove a general result on the length of any path computed in a greedy way. Whereas ROAM uses one bit of memory in nodes (even if there are several destinations), in [KWZ08], it was shown that no geographic routing algorithm not using any sensor memory can compute a path whose length is guaranteed to be of order less than O(l2), where l is the length of the shortest path. Finally, we compare the energy efficiency of ROAM against GPSR (or GFG) [KK00], the algorithm proposed in [MLNR08] and SLGF [JMLW08], by running simulations which validates our theoretical results