Aerial Platform placement algorithms to satisfy connectivity, capacity and survivability constraints in wireless ad-hoc networks
Aerial Platform placement algorithms to satisfy connectivity, capacity and survivability constraints in wireless ad-hoc networks
复制标题
空中平台放置算法，以满足无线自组织网络中的连接性、容量和生存性约束
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
David. Yee
中科院分区：
文献类型：
--
作者：
Senni Perumal;J. Baras;Charles J. Graff;David. Yee;David. Yee
在本文中，我们通过在适当的位置放置最少数量的优势高空飞行平台（AP）作为中继节点，解决大型无线自组织地面网络中断开集群之间建立完全连接并满足所需流量容量的问题。我们还扩展了连接解决方案，以使网络能够应对单个 AP 故障。在断开连接的地面集群之间提供连接性和所需容量的问题被表述为求和形式的集群问题，其具有使 AP 网络完全连接的 AP 间距离约束以及考虑集群到 AP 容量约束的复杂性成本。使用确定性退火来解决由此产生的集群问题，以找到（接近）全局最优的 AP 数量和位置的最佳解决方案，以建立完全连接并在断开连接的集群之间提供所需的流量容量。为了使网络单AP可生存，连接解决方案被扩展，使得每个AP连接到至少两个相邻AP，并且每个地面集群连接到至少两个AP。我们通过将算法与最佳穷举搜索算法进行比较来确定算法的有效性，并表明我们的算法对于在断开的集群之间建立连接的问题接近最优。
In this paper, we address the problem of establishing full connectivity and satisfying required traffic capacity between disconnected clusters in large wireless ad-hoc ground networks by placing a minimum number of advantaged high flying Aerial Platforms (APs) as relay nodes at appropriate places. We also extend the connectivity solution in order to make the network survivable to a single AP failure. The problem of providing both connectivity and required capacity between disconnected ground clusters is formulated as a summation-form clustering problem with inter-AP distance constraints that make the AP network fully connected and with complexity costs that take care of cluster to AP capacity constraints. The resultant clustering problem is solved using deterministic annealing to find (near) globally optimal solutions for the minimum number and locations of the APs to establish full connectivity and provide required traffic capacity between disconnected clusters. In order to make the network single AP survivable, the connectivity solution is extended so that each AP connects to at least two neighboring APs and each ground cluster connects to at least two APs. We establish the validity of our algorithms by comparing it with optimal exhaustive search algorithms and show that our algorithms are near-optimal for the problem of establishing connectivity between disconnected clusters.