Synthesizing Robust Communication Networks for Unmanned Aerial Vehicles With Resource Constraints
- 1 June 2015
- journal article
- Published by ASME International in Journal of Dynamic Systems, Measurement, and Control
- Vol. 137 (6) , 061001
Abstract
In this article, we address the problem of synthesizing communication networks for unmanned aerial vehicles (UAVs) in the presence of resource constraints. UAVs can be deployed as backbone nodes in ad hoc networks that can be central to civilian and military applications. The cost of operation of the network depends on the resources that are used such as the total power consumption associated with the network and the number of communication links in the network. The objective of the problem is to synthesize a communication network that maximizes connectivity subject to the cost of operation being within the specified budget for the resources. It is known that algebraic connectivity is a measure of robust connectivity and hence, it is chosen as an objective for optimization. We pose the network synthesis problem as a mixed-integer semidefinite program (MISDP): (1) provide an algorithm for computing optimal solutions using cutting plane methods; (2) develop lower bounds by posing the problem as a binary semidefinite program; and (3) construct feasible solutions using heuristics and estimate their quality. The network synthesis problem is a nondeterministic polynomial--time (NP)-hard problem. We provide some computational results to corroborate the performance of the proposed algorithms.Keywords
This publication has 20 references indexed in Scilit:
- Algorithms for synthesizing mechanical systems with maximal natural frequenciesNonlinear Analysis: Real World Applications, 2012
- Throughput Optimization in Mobile Backbone NetworksIEEE Transactions on Mobile Computing, 2010
- Distributed inference networks with costly wires2010
- Relay Positioning for Unmanned Aerial Vehicle Surveillance*The International Journal of Robotics Research, 2010
- Construction and Maintenance of Wireless Mobile Backbone NetworksIEEE/ACM Transactions on Networking, 2009
- Optimization of MANET connectivity via smart deployment/movement of unmanned air vehiclesIEEE Transactions on Vehicular Technology, 2009
- Maximum algebraic connectivity augmentation is NP-hardOperations Research Letters, 2008
- Improving Connectivity via Relays Deployment in Wireless Sensor Networks2007
- On Maximizing the Second Smallest Eigenvalue of a State-Dependent Graph LaplacianIEEE Transactions on Automatic Control, 2006
- Transportation in graphs and the admittance spectrumDiscrete Applied Mathematics, 1987