Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/110582
|
| Title: | Maximizing Submodular Set Function with Connectivity Constraint: Theory and Application to Networks |
| Authors: | 郭桐惟
Kuo, Tung-Wei;Lin, Kate Ching-Ju;Tsai, Ming-Jer |
| Contributors: | 資科系 |
| Keywords: | Approximation algorithm, network deployment, submodular set function |
| Date: | 2015-04 |
| Issue Date: | 2017-06-29 09:44:23 (UTC+8) |
| Abstract: | In this paper, we investigate the wireless network deployment problem, which seeks the best deployment of a given limited number of wireless routers. We find that many goals for network deployment, such as maximizing the number of covered users, the size of the coverage area, or the total throughput of the network, can be modeled with a submodular set function. Specifically, given a set of routers, the goal is to find a set of locations S, each of which is equipped with a router, such that S maximizes a predefined submodular set function. However, this deployment problem is more difficult than the traditional maximum submodular set function problem, e.g., the maximum coverage problem, because it requires all the deployed routers to form a connected network. In addition, deploying a router in different locations might consume different costs. To address these challenges, this paper introduces two approximation algorithms, one for homogeneous deployment cost scenarios and the other for heterogeneous deployment cost scenarios. Our simulations, using synthetic data and real traces of census in Taipei, Taiwan, show that the proposed algorithms achieve better performances than other heuristics. |
| Relation: | IEEE/ACM Transactions on Networking, 23(2), 533-546 |
| Data Type: | article |
| DOI 連結: | http://dx.doi.org/10.1109/TNET.2014.2301816 |
| DOI: | 10.1109/TNET.2014.2301816 |
| Appears in Collections: | [資訊科學系] 期刊論文
|
Files in This Item:
| File |
Description |
Size | Format | |
|---|
| 533-546.pdf | | 3448Kb | Adobe PDF2 | 304 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
