A Robust Advantaged Node Placement Strategy for Sparse Network Graphs
| Autor: | Kai Ding, Homayoun Yousefi'zadeh, Faryar Jabbari |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Networking and Internet Architecture (cs.NI)
FOS: Computer and information sciences Optimization problem Theoretical computer science Computer Networks and Communications Hexagonal crystal system Computer science Coordinate system Brute-force search 020206 networking & telecommunications Systems and Control (eess.SY) 02 engineering and technology Graph Computer Science Applications Computer Science - Networking and Internet Architecture Control and Systems Engineering Robustness (computer science) FOS: Electrical engineering electronic engineering information engineering 0202 electrical engineering electronic engineering information engineering Computer Science - Systems and Control Computer Science - Multiagent Systems 020201 artificial intelligence & image processing Heterogeneous network Multiagent Systems (cs.MA) |
| Zdroj: | IEEE Transactions on Network Science and Engineering. 5:113-126 |
| ISSN: | 2327-4697 |
| DOI: | 10.1109/tnse.2017.2734111 |
| Popis: | Establishing robust connectivity in heterogeneous networks (HetNets) is an important yet challenging problem. For a HetNet accommodating a large number of nodes, establishing perturbation-invulnerable connectivity is of utmost importance. This paper provides a robust advantaged node placement strategy best suited for sparse network graphs. In order to offer connectivity robustness, this paper models the communication range of an advantaged node with a hexagon embedded within a circle representing the physical range of a node. Consequently, the proposed node placement method of this paper is based on a so-called hexagonal coordinate system (HCS) in which we develop an extended algebra. We formulate a class of geometric distance optimization problems aiming at establishing robust connectivity of a graph of multiple clusters of nodes. After showing that our formulated problem is NP-hard, we utilize HCS to efficiently solve an approximation of the problem. First, we show that our solution closely approximates an exhaustive search solution approach for the originally formulated NP-hard problem. Then, we illustrate its advantages in comparison with other alternatives through experimental results capturing advantaged node cost, runtime, and robustness characteristics. The results show that our algorithm is most effective in sparse networks for which we derive classification thresholds. Comment: 14 pages, 11 figures, IEEE Transactions on Network Science and Engineering 2017 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|