Power-aware online file allocation in mobile ad hoc networks: [extended abstract]

ABSTRACT

This paper extends the online file allocation problem of Bartal et al. to the following scenario: An indivisible file consisting of multiple units is stored on a network of stationary servers which are connected to a mobile ad hoc network. We model the mobile ad hoc network as a dynamic unit disk graph. The mobile nodes access single units (read/write) of the file using multihop paths to a close-by server, if they do not posses a copy of the file. In order to minimize the amount of data to be transferred, the data management system may create/delete copies of the complete file on arbitrary mobile nodes. Our cost model addresses the overall power consumption of the nodes of the mobile ad hoc network needed for the data management. It consists of a time dependent stand-by power consumption of the mobile nodes and the power consumption used by the hops during data transfers between the servers and the mobile nodes. We introduce the notion of an "energy-distance" which is the energy consumed by a data transfer of an unit-sized message between a server and a mobile node.

Our main focus lies on the online version of the problem. An online algorithm neither knows the dynamics of the mobile ad hoc network nor the requests of the nodes in advance. We give oblivious lower bounds of the competitive ratio for arbitrary randomized algorithms and for the natural class of demand-driven algorithms, i.e. algorithms which replicate only near nodes which recently accessed the file. Furthermore, we give two demand-driven algorithms. We measure the quality of these algorithms using a refinement of the competitive ratio which gives an amortized competitive ratio for every time step depending on the actual changes of the energy-distances of the nodes in this step.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 2: Y. Bartal. Competitive Analysis of Distributed On-line Problems--Distributed Paging. PhD thesis, Tel-Aviv University, 1994.
• 3: Yair Bartal, Distributed Paging, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.97-117, January 1998
• 4: Yair Bartal , Amos Fiat , Yuval Rabani, Competitive algorithms for distributed data management (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.39-50, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129717]
• 5: M. Bienkowski. Page Migration in Dynamic Networks. PhD thesis, University of Paderborn, 2005.
• 6: M. Bienkowski, J. Byrka, M. Korzeniowski, and F. Meyer auf der Heide. Optimal algorithms for page migration in dynamic networks. Journal of Discrete Algorithms, 2008. Accepted for publication.
• 7: M. Bienkowski, M. Dynia, and M. Korzeniowski. Improved algorithms for dynamic page migration. In STACS, pages 365--376, 2005.
• 8: Marcin Bienkowski , Miroslaw Korzeniowski , Friedhelm Meyer auf der Heide, Fighting against two adversaries: page migration in dynamic networks, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007923]
• 9: M. Bienkowski and F. Meyer auf der Heide. Page migration in dynamic networks. In MFCS, pages 1--14, 2005. Invited talk.
• 10: D. L. Black and D. D. Sleator. Competitive algorithms for replication and migration problems. Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989.
• 11: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 12: S. Corson , J. Macker, Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations, RFC Editor, 1999
• 13: Bezalel Gavish , Olivia R. Liu Sheng, Dynamic file migration in distributed computer systems, Communications of the ACM, v.33 n.2, p.177-189, Feb. 1990 [doi>10.1145/75577.75583]
• 14: A. R. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator. Competitive snoopy caching. Algorithmica, 3:77--119, 1988.
• 15: Carsten Lund , Nick Reingold , Jeffery Westbrook , Dicky Yan, Competitive On-Line Algorithms for Distributed Data Management, SIAM Journal on Computing, v.28 n.3, p.1086-1111, Feb. 1999 [doi>10.1137/S0097539795287824]
• 16: B. Maggs , F. Meyer auf der Heide , B. Voecking , M. Westermann, Exploiting Locality for Data Management in Systems of Limited Bandwidth, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p.284, October 19-22, 1997
• 17: Friedhelm Meyer auf der Heide , Berthold Vöcking , Matthias Westermann, Provably Good and Practical Strategies for Non-Uniform Data Management in Networks, Proceedings of the 7th Annual European Symposium on Algorithms, p.89-100, July 16-18, 1999
• 18: A. Wang and C. Sodini. A simple energy model for wireless microsensor transceivers. Global Telecommunications Conference, 2004. GLOBECOM '04. IEEE, 5:3205--3209, 2004.
• 19: Q. Wang, M. Hempstead, and W. Yang. A realistic power consumption model for wireless sensor network devices. Sensor and Ad Hoc Communications and Networks, 2006. SECON '06. 2006 3rd Annual IEEE Communications Society on, 1:286--295, Sept. 2006.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services

General Terms:
Algorithms, Performance, Theory

Keywords:
amortized analysis, file allocation, mobile ad hoc networks, online algorithms