We consider the ad-hoc networks consisting of n wireless nodes that are located on the plane. Any two given nodes are called neighbors if they are located within a certain distance (communication range) from one another. A given node can be directly connected to any one of its neighbors, and picks its connections according to a unique topology control algorithm that is available at every node. Given that each node knows only the indices (unique identification numbers) of its one and two-hop neighbors, we identify an algorithm that preserves connectivity and can operate without the need of any synchronization among nodes. Moreover, the algorithm results in a sparse graph with at most 5n edges and a maximum node degree of 10. Existing algorithms with the same promises further require neighbor distance and/or direction information at each node. We also evaluate the performance of our algorithm for random networks. In this case, our algorithm provides an asymptotically connected network with n(1+o(1)) edges with a degree less than or equal to 6 for 1-o(1) fraction of the nodes. We also introduce another asynchronous connectivity-preserving algorithm that can provide an upper bound as well as a lower bound on node degrees.
more »
« less
Finding Link Topology of Large Scale Networks from Anchored Hop Count Reports
Learning network topology from partial knowledge
of its connectivity is an important objective in practical
scenarios of communication networks and social-media networks.
Representing such networks as connected graphs, exploring and
recovering connectivity information between network nodes can
help visualize the network topology and improve network utility.
This work considers the use of simple hop distance measurement
obtained from a fraction of anchor/source nodes to reconstruct
the node connectivity relationship for large scale networks of
unknown connection topology. Our proposed approach consists
of two steps. We first develop a tree-based search strategy to
determine constraints on unknown network edges based on the
hop count measurements. We then derive the logical distance
between nodes based on principal component analysis (PCA) of
the measurement matrix and propose a binary hypothesis test
for each unknown edge. The proposed algorithm can effectively
improve both the accuracy of connectivity detection and the
successful delivery rate in data routing applications.
more »
« less
- NSF-PAR ID:
- 10054100
- Date Published:
- Journal Name:
- 2017 IEEE GLOBECOM
- Page Range / eLocation ID:
- 1 to 6
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Dynamic network topology can pose important challenges to communication and control protocols in networks of autonomous vehicles. For instance, maintaining connectivity is a key challenge in unmanned aerial vehicle (UAV) networks. However, tracking and computational resources of the observer module might not be sufficient for constant monitoring of all surrounding nodes in large-scale networks. In this paper, we propose an optimal measurement policy for network topology monitoring under constrained resources. To this end, We formulate the localization of multiple objects in terms of linear networked systems and solve it using Kalman filtering with intermittent observation. The proposed policy includes two sequential steps. We first find optimal measurement attempt probabilities for each target using numerical optimization methods to assign the limited number of resources among targets. The optimal resource allocation follows a waterfall-like solution to assign more resources to targets with lower measurement success probability. This provides a 10% to 60% gain in prediction accuracy. The second step is finding optimal on-off patterns for measurement attempts for each target over time. We show that a regular measurement pattern that evenly distributed resources over time outperforms the two extreme cases of using all measurement resources either in the beginning or at the end of the measurement cycle. Our proof is based on characterizing the fixed-point solution of the error covariance matrix for regular patterns. Extensive simulation results confirm the optimality of the most alternating pattern with up to 10-fold prediction improvement for different scenarios. These two guidelines define a general policy for target tracking under constrained resources with applications to network topology prediction of autonomous systemsmore » « less
-
The monitoring of data streams with a network structure have drawn increasing attention due to its wide applications in modern process control. In these applications, high-dimensional sensor nodes are interconnected with an underlying network topology. In such a case, abnormalities occurring to any node may propagate dynamically across the network and cause changes of other nodes over time. Furthermore, high dimensionality of such data significantly increased the cost of resources for data transmission and computation, such that only partial observations can be transmitted or processed in practice. Overall, how to quickly detect abnormalities in such large networks with resource constraints remains a challenge, especially due to the sampling uncertainty under the dynamic anomaly occurrences and network-based patterns. In this paper, we incorporate network structure information into the monitoring and adaptive sampling methodologies for quick anomaly detection in large networks where only partial observations are available. We develop a general monitoring and adaptive sampling method and further extend it to the case with memory constraints, both of which exploit network distance and centrality information for better process monitoring and identification of abnormalities. Theoretical investigations of the proposed methods demonstrate their sampling efficiency on balancing between exploration and exploitation, as well as the detection performance guarantee. Numerical simulations and a case study on power network have demonstrated the superiority of the proposed methods in detecting various types of shifts. Note to Practitioners —Continuous monitoring of networks for anomalous events is critical for a large number of applications involving power networks, computer networks, epidemiological surveillance, social networks, etc. This paper aims at addressing the challenges in monitoring large networks in cases where monitoring resources are limited such that only a subset of nodes in the network is observable. Specifically, we integrate network structure information of nodes for constructing sequential detection methods via effective data augmentation, and for designing adaptive sampling algorithms to observe suspicious nodes that are likely to be abnormal. Then, the method is further generalized to the case that the memory of the computation is also constrained due to the network size. The developed method is greatly beneficial and effective for various anomaly patterns, especially when the initial anomaly randomly occurs to nodes in the network. The proposed methods are demonstrated to be capable of quickly detecting changes in the network and dynamically changes the sampling priority based on online observations in various cases, as shown in the theoretical investigation, simulations and case studies.more » « less
-
null (Ed.)Anchor-based ad-hoc networks utilize hop measurements to generate a virtual coordinate system for topology inference and routing applications. A common problem with such coordinate system is its sensitivity to anchor placement. We present a general formulation to the anchor node selection problem. Then, we relax the optimization problem by deriving an upper-bound of the objective function. We finally propose an iterative algorithm that consists in choosing additional anchor nodes based on the connectivity information provided by the current anchor set. Numerical simulations indicate that our anchor selection method is robust to missing measurements and improves network topology inference and routing performance.more » « less
-
Connectivity is at the heart of the future Internet-of-Things (IoT) infrastructure, which can control and communicate with remote sensors and actuators for the beacons, data collections, and forwarding nodes. Existing sensor network solutions cannot solve the bottleneck problems near the sink node; the tree-based Internet architecture has the single point of failure. To solve current deficiencies in multi-hop mesh network and cross-domain network design, we propose a mesh inside a mesh IoT network architecture. Our designed "edge router" incorporates these two mesh networks together and performs seamlessly transmission of multi-standard packets. The proposed IoT testbed interoperates with existing multi-standards (Wi-Fi, 6LoWPAN) and segments of networks, and provides both high-throughput Internet and resilient sensor coverage throughout the community.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/GLOCOM.2017.8253952
