Population-Aware Relay Placement for Wireless Multi-Hop Based Network Disaster Recovery
Population-Aware Relay Placement for Wireless Multi-Hop Based Network Disaster Recovery
复制标题
DOI：
10.1109/glocom.2017.8253922
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
L. Zhong;Yusheng Ji;Xiaoyan Wang;S. Yamada;K. Takano;G. Xue
中科院分区：
文献类型：
--
作者：
L. Zhong;Yusheng Ji;Xiaoyan Wang;S. Yamada;K. Takano;G. Xue
网络灾难恢复是移动的网络运营商（MNO）和第一响应者在诸如地震的大规模自然灾害期间最关心的问题之一。在最近的许多研究中，无线多跳网络已被证明是一种有效的技术，在灾难期间快速，有效地扩大网络覆盖范围。在本文中，我们专门解决网络部署问题，提出了人口感知中继放置（PARP）的解决方案，寻求有效的部署有限数量的中继，使人口覆盖率最大化的情况下，网络灾难恢复。我们提供了一个基于图的建模，并证明了其NP-困难。为了有效地解决这个问题，我们提出了一个启发式的解决方案，这是构造在两个步骤。我们首先设计了一个简单的算法，基于一个磁盘图来确定Steiner位置，这是在这个问题中最大的挑战。然后，我们制定的问题作为一个整数规划问题，这是由制定奖励收集斯坦纳树（PCST）的启发。因此，整数问题的解决，探索现有的PCST算法的相似性。为了广泛地评估所提出的解决方案，我们提出了在现实世界和随机情况下的数值结果，验证了所提出的解决方案的有效性，并通过与以前的相比，显示出显着的改善。
Network disaster recovery is one of the greatest concerns for Mobile Network Operators (MNOs) and first responders during large-scale natural disasters such as earth- quakes. In many recent studies, wireless multi-hop networking has been demonstrated as an effective technique to quickly and efficiently extend the network coverage during disasters. In this paper, we specifically address the network deployment problem by proposing the Population-Aware Relay Placement (PARP) solution, which seeks the efficient deployment of a limited number of relays such that population coverage is maximized in the scenario of network disaster recovery. We provide a graph-based modeling and prove its NP-hardness accordingly. In order to efficiently solve this problem, we propose a heuristic solution, which is constructed in two steps. We first design a simple algorithm based on a disk graph to determine the Steiner locations, which is the biggest challenge in this problem. Then, we formulate the problem as an integer programming problem, which is inspired by the formulation of Prize-Collecting Steiner Tree (PCST). Thus, the integer problem is solved by exploring the similarity of the existing algorithm for PCST. To evaluate the proposed solution extensively, we present numerical results on both real-world and random scenarios, which validate the effectiveness of the proposed solution and show substantial improvement by comparing to the previous one.