在圖連通條件下最大化次模集合函數：理論與網路應用

Maximizing Submodular Set Function with Connectivity Constraint: Theory and Application to Networks

郭桐惟(Kuo, Tung Wei)

指導教授 ： 林靖茹 ； 蔡明哲

國立清華大學/電機資訊學院/資訊工程學系/博士(2015年)

https://doi.org/10.6843/NTHU.2015.00366

摘要

在這篇博士論文中，我們探討如何利用有限個無線路由器建構出最佳的無線網路。我們發現很多無線網路布建的目標，例如最大化服務客戶數、最大化覆蓋面積、或是最大化網路傳輸量，都可以利用次模集合函數來表示。更仔細地說，給定一些無線路由器，這篇博士論文的目標是放置這些無線路由器使得某個給定的次模集合函數被最大化。然而，這個問題比起傳統的最大化次模集合函數問題更加困難。這是因為這篇博士論文探討的問題需要這些被選中的地點構成一個連通的網路。除此之外，在不同的地點安裝無線路由器通常需要不同的花費。為了解決這些問題，這篇論文提出了兩個近似演算法，一個適用在所有地點都有相同的安裝花費，另一個適用在不同地點有不同安裝花費。我們的電腦模擬採用了人工合成的資料和來自台北市人口分布的資料。模擬結果顯示，這篇博士論文提出的演算法除了有理論上的效能保證外，實際上也表現得比其他的比較方法更好。

關鍵字

網路布建 ； 近似演算法 ； 次模集合函數

並列摘要

In this thesis, 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 modelled 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 thesis 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, show that the proposed algorithms not only have theoretical performance guarantee but also achieve better performances than other heuristics in practice.

並列關鍵字

Network deployment ； Approximation algorithm ； Submodular set function

參考文獻

[4] D. Johnson, “Evaluation of a single radio rural mesh network in South Africa,”in ICTD, 2007.

[6] P. Dutta, S. Jaiswal, and R. Rastogi, “Routing and channel allocation in rural wireless mesh networks,” in IEEE INFOCOM, 2007.

[7] Community Wireless Solutions (CUWIN). [Online]. Available:

[9] G. L. Nemhauser, L. A.Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions-I,” Mathematical Programming, vol. 14, pp. 265–294, 1978.

[10] M. Sviridenko, “A note on maximizing a submodular set function subject to a knapsack constraint,” Operations Research Letters, vol. 32, pp. 41–43, 2004.