Show simple item record

dc.contributor.authorJaggi, Neeraj
dc.contributor.authorTakahashi, Masaaki
dc.contributor.authorTang, Bin
dc.date.accessioned2015-08-31T15:27:37Z
dc.date.available2015-08-31T15:27:37Z
dc.date.issued2014-08-04
dc.identifier.citationBin Tang; Jaggi, N.; Takahashi, M., "Achieving data K-Availability in intermittently connected sensor networks," in Computer Communication and Networks (ICCCN), 2014 23rd International Conference on , vol., no., pp.1-8, 4-7 Aug. 2014
dc.identifier.isbn9781479935727
dc.identifier.otherWOS:000363326300070
dc.identifier.urihttp://hdl.handle.net/10057/11490
dc.identifier.urihttp://dx.doi.org/10.1109/ICCCN.2014.6911795
dc.descriptionClick on the DOI link to access this conference paper (may not be free)
dc.description.abstractWe consider the problem of preserving data in intermittently connected sensor networks wherein sensor nodes do not always have connected paths to the base stations. The generated data is first stored inside the network before being uploaded to the base station when uploading opportunities arise. Each node has both limited energy level and limited storage space, and is associated with a probability of failure. To guarantee that at any moment, each generated data item is available for being uploaded in the presence of node failure, we propose to replicate K copies of each data item in the network, where K depends upon the node failure probability. We refer to the problem as Data K-Availability Problem (DKAP). DKAP is naturally divided into two phases: K-Availability creation and K-Availability maintenance. For K-Availability creation, we show that the problem is NP-hard for arbitrary data sizes, and that it is equivalent to minimum cost flow problem for unit data sizes. For K-Availability maintenance, we show that it is NP-hard even for unit data sizes and design a centralized greedy heuristic. We further design an efficient and low-overhead distributed algorithm, which is applicable to both phases, and show using extensive simulations that it performs close to the heuristic.
dc.language.isoen_US
dc.subjectData availability
dc.subjectData replication and (re)distribution
dc.subjectIntermittently connected sensor networks
dc.subjectComputational complexity
dc.subjectGreedy algorithms
dc.subjectNP-hard problem
dc.subjectDistributed databases
dc.titleAchieving data K-availability in intermittently connected sensor networks
dc.typeConference paper
dc.rights.holderCopyright IEEE, 2014


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record