Power Assignment Problems in Wireless Communication: Covering Points by Disks, Reaching few Receivers Quickly, and Energy-Efficient Travelling Salesman Tours

摘要: A fundamental class of problems in wireless communication is concerned with the assignment suitable transmission powers to devices/stations such that resulting graph satisfies certain desired properties and overall energy consumed minimized. Many concrete tasks a network like broadcast, multicast, point-to-point routing, creation backbone, etc. can be regarded as power problem. This paper considers several kind; first problem was studied before [1,6] aims select assign kout total nwireless stations all are within reach at least one selected stations. We show (1 + i¾?) approximated by only looking small subset input, which size , i.e. independent nand polynomial kand 1/i¾?. Here ddenotes dimension space where devices distributed, so typically d≤ 3 describes relation between Euclidean distance two consumption for establishing connection them. Using this coresetwe able improve considerably on running time $n^{((\alpha/\epsilon)^{O(d)})}$ algorithm Bilo et al. ESA'05 ([6]) actually obtaining linearin n. Furthermore we sketch how outliers handled our coreset construction. The second deals energy-efficient, bounded-hop multicast operation: Given Cout set nstations designated source node swe want every Cis reached from swithin khops. Again k, |C|, 1/i¾?exists, use provide an runs linear n. The last variant non-metric TSP edge costs squared distances; motivated data aggregation schemes sensor networks. good tour under very bad measure simple constant approximation algorithm, partly improving upon previous results [5], [4].