Indexed by:
Abstract:
In a mobile network, wireless data broadcast over m channels (frequencies) is a powerful means for distributed dissemination of data to clients who access the channels through multi-antennae equipped on their mobile devices. The delta-antennae largest weight data retrieval (delta ALWDR) problem is to compute a schedule for downloading a subset of data items that has a maximum total weight using delta antennae in a given time interval. In this paper, we first give a linear programming (LP) relaxation for delta ALWDR and show that it is polynomial-time solvable when every data item appears at most once. We also show that when there exist data items with multiple occurrences, the integrality gap of this LP formula is 2. We then present an approximation algorithm of ratio 1 - 1/e for the delta-antennae gamma-separated largest weight data retrieval (delta A gamma LWDR) problem, a weaker version of delta ALWDR where each block of up to gamma data (time) slots is separated by a vacant slot on all channels, applying the techniques called collectively randomized LP rounding and layered DAG construction. We show that delta A gamma LWDR is NP-complete even for the simple case of gamma = 2, m = 3, and equal-weight data items each appearing up to 3 times. Our algorithm runs in time O(2(gamma)m(7)T(3.5)L), where T is the number of time slots, and L is the maximum length of the input. Then, from the simple observation that a ratio alpha approximation solution to delta A gamma LWDR implies a ratio alpha - is an element of approximation solution to delta ALWDR for any fixed is an element of > 0, we immediately have an approximation algorithm of ratio 1 - 1/e - is an element of for delta ALWDR. Our algorithm has the same approximation ratio as the known result in [15] which holds only for delta = 1, with a significantly lower time complexity of O(2(1/is an element of)1/is an element of m(7)T(3.5)L) (improved from O(is an element of(3.5) m(3.5/)is an element of(TL)-L-3.5) . As a by-product, we also give a fixed-parameter tractable (fpt-) algorithm of time complexity O(2(B)m(7)T(3.5)L) for delta ALWDR, where B is the number of time slots that contain data items with multiple occurrences.
Keyword:
Reprint 's Address:
Version:
Source :
IEEE TRANSACTIONS ON MOBILE COMPUTING
ISSN: 1536-1233
Year: 2017
Issue: 12
Volume: 16
Page: 3320-3333
4 . 0 9 8
JCR@2017
7 . 7 0 0
JCR@2023
ESI Discipline: COMPUTER SCIENCE;
ESI HC Threshold:187
JCR Journal Grade:1
CAS Journal Grade:2
Cited Count:
WoS CC Cited Count: 18
SCOPUS Cited Count: 18
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: