• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Guo, Longkun (Guo, Longkun.) [1] (Scholars:郭龙坤) | Shen, Hong (Shen, Hong.) [2] | Zhu, Wenxing (Zhu, Wenxing.) [3] (Scholars:朱文兴)

Indexed by:

EI Scopus SCIE

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:

approximation algorithm Distributed data dissemination linear programming multi-antennae data retrieval scheduling

Community:

  • [ 1 ] [Guo, Longkun]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou, Fujian, Peoples R China
  • [ 2 ] [Zhu, Wenxing]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou, Fujian, Peoples R China
  • [ 3 ] [Shen, Hong]Univ Adelaide, Sch Comp Sci, Adelaide, SA 5005, Australia
  • [ 4 ] [Shen, Hong]Yat Sen Univ, Sch Informat Sci & Technol, Guangzhou, Guangdong, Peoples R China

Reprint 's Address:

  • 郭龙坤

    [Guo, Longkun]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou, Fujian, Peoples R China

Show more details

Related Keywords:

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

Online/Total:154/10043853
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1