Minimum Cost Topology Construction for Rural Wireless Mesh Networks
Minimum Cost Topology Construction for Rural Wireless Mesh Networks
复制标题
农村无线网状网络的最低成本拓扑构建
DOI：
10.1109/infocom.2008.128
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
R. Rastogi
中科院分区：
文献类型：
--
作者：
Debmalya Panigrahi;P. Dutta;Sharad Jaiswal;K. Naidu;R. Rastogi
基于IEEE 802.11无线设备的无线Mesh网络最近被提议作为连接偏远农村地区的一种廉价方法。这样的网络是使用高增益定向天线建立的，可以建立远距离无线点对点链路。网络中的一些节点(称为网关节点)直接连接到有线互联网，其余节点使用一个或多个跳数连接到网关(S)。构建这样的网状网络的主要成本是在节点上建造天线塔的成本。一座塔的成本取决于它的高度，而它的高度又取决于它的链接的长度和这些链接上的物理障碍物。我们研究了选择应该建立哪些链路的问题，使得所有节点都被连接，而建立所选链路所需的天线塔的构建成本最小。我们证明了这个问题是NP难的，并且不能期望比O(Logn)更好的近似，其中n是图中的顶点数。然后，我们提出了文献中的第一个算法，用于这个问题，具有可证明的性能界限。更准确地说，我们给出了一个贪婪算法，它是该问题的O(Logn)近似算法。最后，通过仿真，我们将我们的近似算法与最优解和朴素启发式算法进行了比较。
IEEE 802.11 WiFi equipment based wireless mesh networks have recently been proposed as an inexpensive approach to connect far-flung rural areas. Such networks are built using high-gain directional antennas that can establish long-distance wireless point-to-point links. Some nodes in the network (called gateway nodes) are directly connected to the wired internet, and the remaining nodes connect to the gateway(s) using one or more hops. The dominant cost of constructing such a mesh network is the cost of constructing antenna towers at nodes. The cost of a tower depends on its height, which in turn depends on the length of its links and the physical obstructions along those links. We investigate the problem of selecting which links should be established such that all nodes are connected, while the cost of constructing the antenna towers required to establish the selected links is minimized. We show that this problem is NP-hard and that a better than O(log n) approximation cannot be expected, where n is the number of vertices in the graph. We then present the first algorithm in the literature, for this problem, with provable performance bounds. More precisely, we present a greedy algorithm that is an O(log n) approximation algorithm for this problem. Finally, through simulations, we compare our approximation algorithm with both the optimal solution, and a naive heuristic.