Paper Info
Title
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.
Year
DOI
Venue
2009
10.1145/1583991.1584072
SPAA
Keywords
Field
DocType
indivisible file,mobile node,competitive ratio,power-aware online file allocation,mobile nodes access,online file allocation problem,arbitrary mobile node,demand-driven algorithm,complete file,data transfer,data management,amortized analysis,mobile ad hoc network,online algorithms,randomized algorithm,unit disk graph,online algorithm,lower bound,mobile ad hoc networks
Mobile ad hoc network,Online algorithm,Computer science,Server,Computer network,Mobile database,Optimized Link State Routing Protocol,Wireless ad hoc network,Competitive analysis,Unit disk graph,Distributed computing
Conference
Citations 
PageRank 
References 
0
0.34
13
Authors
2
Name
Order
Citations
PageRank
Jan Mehler100.34
Friedhelm Meyer auf der Heide21744238.01