Constant time queries for energy efficient paths in multi-hop wireless networks

被引：0
作者：
Funke, Stefan [1 ]
Matijević, Domagoj [1 ]
Sanders, Peter [2 ]
机构：
[1] Max-Planck-Institut für Informatik, Saarbrücken
[2] Universität Karlsruhe, Fakultät für Informatik, Karlsruhe
来源：
Journal of Computing and Information Technology | 2008年 / 16卷 / 02期
关键词：
Ad-hoc and sensor networks; Computational geometry; Power control; Routing; Wireless LANs;
D O I：
10.2498/cit.1001047
中图分类号：
学科分类号：
摘要：
We investigate algorithms for computing energy efficient paths in ad-hoc radio networks. We demonstrate how advanced data structures from computational geometry can be employed to preprocess the position of radio stations in such a way that approximately energy optimal paths can be retrieved in constant time, i.e., independent of the network size. We put particular emphasis on actual implementations which demonstrate that large constant factors hidden in the theoretical analysis are not a big problem in practice.
引用
收藏
页码：119 / 130
页数：11
相关论文
共 19 条
  • [1] Arya S., Mount D.M., Approximate range searching, Computational Geometry: Theory and Applications, 17, pp. 135-152, (2000)
  • [2] Arya S., Mount D.M., Netanyahu N.S., Silverman R., Wu A., An optimal algorithm for approximate nearest neighbor searching, Journal of the ACM, 45, 6, pp. 891-923, (1998)
  • [3] Bambos N., Toward Power-sensitive Network Architectures inWireless Communications: Concepts, Issues, and Design Aspects, IEEE Personal Comm, 5, (1998)
  • [4] Beier R., Sanders P., Sivadasan N., Energy Optimal Routing in Radio Networks Using Geometric Data Structures, Proc. of the 29th Int. Coll. on Automata, Languages, and Programming, (2002)
  • [5] De Berg M., Van Krefeld M., Overmars M., Schwarzkopf O., Computational Geometry: Algorithms and Applications, (1997)
  • [6] Callahan P.B., Kosaraju S.R., A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields, Proc. of the 24th Ann. ACM Symp. on the Theory of Computation, (1992)
  • [7] Callahan P.B., Kosaraju S.R., Algorithms for Dynamic Closest Pair and n-Body Potential Fields, Proc. of the 6th Ann. ACM-SIAM Symp. on Discrete Algorithm, (1995)
  • [8] Carter J.L., Wegman M.N., Universal Classes of Hash Functions, Journal of Computer and System Sciences, 18, 2, pp. 143-154, (1979)
  • [9] Chan T., Efrat A., Fly cheaply: On the minimum fuel consumption problem, Journal of Algorithms, 41, 2, pp. 330-337, (2001)
  • [10] Efrat A., Har-Peled S., Fly Cheaply: On the Minimum Fuel Consumption Problem, Proc. of the 14th ACM Symp. on Computational Geometry, (1998)
12