Startseite > Publikationen > Publikationen


Mehler, Jan;Meyer auf der Heide, Friedhelm:

Power-Aware Online File Allocation in Mobile Ad Hoc Networks.

In: Proceedings of the 21st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'09), S. 347-356, 11. - 13. Aug. 2009 ACM SIGACT, ACM SIGARCH, ACM Press


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.




author = {Mehler, Jan and Meyer auf der Heide, Friedhelm},
title = {Power-Aware Online File Allocation in Mobile Ad Hoc Networks},
booktitle = {Proceedings of the 21st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'09)},
pages = {347-356},
organization = {ACM SIGACT, ACM SIGARCH},
publisher = {ACM Press},
month = {11~-~13~} # aug,
year = {2009},

BibTeX in die Zwischenablage kopieren