Inference of Graph Topology
Gonzalo Mateos, ... AntonioG. Marques, in Cooperative and Graph Signal Processing, 2018
Abstract
Network topology inference is a prominent problem in network science. Most graph signal processing [GSP] efforts to date assume that the underlying network is known, and then analyze how the graphs algebraic and spectral characteristics impact the properties of the graph signals of interest. However, such assumption is often untenable in practice and typically adopted graph construction schemes are largely informal, distinctly lacking an element of validation. The present chapter outlines a framework recently developed to bridge the aforementioned gap by using information available from graph signals to infer the underlying graph topology. The unknown graph represents direct relationships between signal elements, which one aims to recover from observable indirect relationships generated by a diffusion process on the graph. The fresh look advocated here leverages concepts from convex optimization and stationarity of graph signals in order to identify the graph-shift operator [a matrix representation of the graph] given only its eigenvectors. These spectral templates can be obtained, e.g., from the sample covariance of independent graph signals diffused on the sought network. The novel idea is to find a graph-shift operator that, while being consistent with the provided spectral information, endows the network with certain desired properties such as sparsity or minimum-energy edge weights.
Multi-Modal Data Fusion Techniques and Applications
Alessio Dore, ... Carlo S. Regazzoni, in Multi-Camera Networks, 2009
Network Topologies in Distributed Architectures
Network topology plays an important role in distributed data fusion systems, and it runs into some problems such as redundancy of information and time alignment. The most conceptually simple topology is fully connected [Figure 9.5[a]], in which each node is connected with every other node or all nodes communicate via a same communication media [e.g., bus or radio]. The major problem with this kind of connection is that it is often unreliable if the number of nodes is high. A second type of topology is the one shown in Figure 9.5[b]namely, the tree or singly connected network, in which only one path exists between two nodes. This topology, in general, is not robust; in fact the improper functioning of a node prejudices the acquisition of all information coming from the nodes connected to it.
FIGURE 9.5. [a] Fully connected network topology. [b] Tree or singly connected network topology. [c] Multiply connected network topology.
The topology shown in Figure 9.5[c] is related to the multiply connected network. In this network one node is connected in an arbitrary way to the other nodes, so any topology configuration is allowed. Generally this kind of network allows dynamic changes, ensuring the system characteristics of scalability, modularity, and survival to loss or addition of nodes. In [43] a decentralized system is described where unmanned air vehicles are equipped with GPS, an inertial sensor, a vision system, and a mm-wave radar or laser sensor. These vehicles are connected by a fully decentralized, scalable and modular architecture, and the task of the system is to perform position and velocity estimation of ground targets.
IEEE 802.15.4 Based Wireless Sensor Network Design for Smart Grid Communications
Chun-Hao Lo, Nirwan Ansari, in Handbook of Green Information and Communication Systems, 2013
4.4.1 LR-WPAN Studies and Challenges
IEEE 802.15.4 LR-WPAN essentially employs the TDMA [time division multiple access] method along with the CSMA-CA [carrier sense multiple access with collision avoidance] medium contention mechanism for its network operation. Meanwhile, it mainly adopts DSSS [direct-sequence spread spectrum] rather than FHSS for various modulation schemes in order for battery-powered [or power-constrained] devices to save considerable energy as well as lengthen the network longevity.
Network topology control and traffic engineering involve a number of nodes connected in a network, placement of the nodes, data generation from the nodes, and accumulated loads throughout a network. Figure 4.2 depicts the key elements dependent on different scenarios that predominantly determine the network performance. Each of them can have tremendous and consequential impacts on
Figure 4.2. The influential network metrics and measurements.
frequency of wireless medium contention;
success ratio of data delivery, which can be degraded by collisions from regular CSMA contention and hidden node transmission, congestions due to heavy traffic loads, as well as losses and drops due to the inherent wireless deterioration and buffer overflow;
latency induced by unnecessary delayed transmission from the exposed node problem, a clumsy increase in MAC CSMA backoff periods, and inflexible routing design;
rate of energy depletion affected by the duty-cycle arrangement as well as data aggregation and fusion mechanisms.
4.4.1.1 Wireless Impairments
Background noise and signal attenuation are inevitable in wireless transmission environments. Along the propagation path, losses attributed to refraction, diffraction, and scattering are likely to occur; multipath further incurs fading effects in mobile conditions. Several well-known path-loss models including free space, two-ray ground, and log-distance path have been extensively used to derive radio channel effects in RF-based wireless propagation network testing and experiments [22].
Interference is a critical phenomenon that could also degrade the overall performance in LR-WPANs. It is predominantly dependent upon the power transmission range, distance between transmitters and receivers, as well as orientation of antennae. Specifications in PHY such as ED [receiver energy detection]3 within the current channel, LQI [link quality indicator] for received packets and channel frequency selection, as well as CCA [clear channel assessment] for CSMA-CA, are principal attributes to tackle the effect of interference. Analyses of multichannel, overlapping channel, and cross- or interchannel interference models and solutions for various scenarios can be found in [2325].
4.4.1.2 Data Packet Length and Data Delivery
The PHY payload [i.e., PHY service data unit or PSDU] in IEEE 802.15.4 is limited to 127bytes4[18]. Excluding the control bytes, the application payload carrying useful information is approximately 100bytes. The payload is further reduced to a range of 60bytes and 80bytes if routing and security parameters are appended to the PHY overhead [19]. In other words, more than one-third of the space of each transmitted data packet in IEEE 802.15.4 is occupied for the control overhead purpose. Issues addressed in LR-WPAN entail [1] the use of bandwidth efficiently in transmission of small-size data packets to attain high goodput, and [2] the appropriateness of data packet size along with useful information to achieve low delay and low packet-loss rate in HAN and SUN. Meanwhile, security and privacy protection mechanisms supported in the data packets brings further challenges, especially when energy saving is required.
Furthermore, the network topologies supported in LR-WPAN are star, tree, and mesh. The routing schemes may include source routing [up to 5 hops], tree routing [up to 10], mesh routing [up to 30], and broadcasting [up to 30 as well] [19]. Choosing an appropriate scheme or hybrid among these routing protocols is critical for different networking environments. For example, tree routing might surpass mesh routing when a network becomes denser and crowded; source routing may not be valid in multihop transmission once beyond five hops when considering energy consumption, routing table size, and additional overhead factors. Apparently, data aggregation performs a key role in LR-WPAN.
4.4.1.3 CSMA-CA Contention Collision [CC]
The unslotted CSMA-CA channel access mechanism in IEEE 802.15.4 usually works well when the node density is sparse and nodes are more uniformly distributed in the network. Once beyond a certain boundary, the overall network performance can be degraded dramatically as more nodes are contending for the same medium. This results in transmission failures, leading to large backoff periods, and finally connection terminations. Each node in LR-WPAN specifies three variables for each transmission attempt:
NB: the number of times that CSMA-CA is required to backoff; it is denoted by macMaxCSMABackoffs: 05 [default=4].
BE: a backoff exponent that is used to calculate the backoff period [i.e., 0~[2BE1]] a node shall wait before attempting to access a channel; it is denoted by macMaxBE: 38 [default=5]; macMinBE: 0~macMaxBE [default=3].
CW: the contention window length that represents the number of backoff periods in ensuring that a channel is free; it is denoted by CW: 02, [default=2]. This variable is only used in the beacon-enabled operational mode [to be discussed in Section 4.2]. Two successful clear channel assessments [CCAs] in a row are required before transmission. Otherwise, CW is always reset to 2.
Notably, the CW parameter in LR-WPAN is used differently than that in IEEE 802.11 WLAN. The difference is that CW in IEEE 802.11 can be doubled when network congestion occurs, and may be frozen if a packet loss is detected.
4.4.1.4 Hidden Node Collision [HNC] and Exposed Node Problem [ENP]
The hidden node problem [HNP] [34, 37] is a well-known problem in wireless communications. The issue should be carefully addressed since the probability of having a hidden node in a wireless network can be as high as 41% [26]. The situation happens when two or more sending nodes outside the transmission range of each other transmit data to the same node in the next hop nearly at the same time, thus likely resulting in data collision at the receiving node. These sending nodes are hidden from each other because they are unable to detect the existence of one another. Unlike the RTS/CTS handshake schemes5 used in IEEE 802.11 networks, LR-WPAN does not support the probing mechanism because of the inherent characteristics of energy saving and small data transmission. Instead, a few grouping techniques6 proposed to mitigate HNP in LR-WPAN include pulse signal tactic and dynamic channel allocation mechanisms to prevent channels from being wasted [34, 35].
The exposed node problem [ENP] is the opposite of HNP that may also occur in WPAN and degrade the network performance [36]. In short, two or more sending nodes inside the transmission range of each other are actually allowed to transmit nearly at the same time without severely interfering one another, if their destined nodes in the next hop are outside the transmission range of each other. Both the HNP and ENP can be tackled by various power control management, which may, however, induce a trade-off between raising and reducing transmission power [as related to receiver sensitivity] at the transmitters and receivers. They have been challenges in WSN topology control as well as in LR-WPAN. For further studies, readers are referred to [37] for discussions on accumulated overheads attributed to contention collision from HNP, as well as consequent retransmission effects on the system performance in terms of MAC delay. In addition, Zhang and Shu [38] were among the first to study how to optimize the packet size in order to maximize the network resource and energy efficiency. Both research works used a cross-layer approach.
Networking and Network Routing: An Introduction
Deep Medhi, Karthik Ramasamy, in Network Routing [Second Edition], 2018
1.9 Network Topology Architecture
The Network topology architecture encompasses how a network is to be architected in an operational environment while accounting for future growth. What does topology mean? It refers to the form that a network will adopt, such as a star, ring, Manhattan-street network, or a fully-mesh topology, or a combination of them. The topological architecture then covers architecting a network topology that factors in economic issues, different technological capabilities, and limitations of devices to carry a certain volume of expected traffic and types of traffic, for an operational environment. Certainly, a network topology architecture also needs to take into account routing capability, including any limitation or flexibility provided by a routing protocol. It is up to a network provider, also referred to as a network operator or a service provider, to determine the best topological architecture for the network.
It is important to note that the operational experience of an existing network can contribute to the identification of additional features required from a routing protocol, the development of a new routing protocol, the development of a new routing algorithm, or modification of an existing algorithm. We briefly discuss two examples: 1] when it was recognized in the late 1980s that the Internet needed to move from being under one network administrative domain to more flexible loosely connected networks managed by different administrative domains, the Border Gateway Protocol [BGP] was developed; 2] when it was felt in the late 1970s that the telephone network needed to move away from a hierarchical architecture that provided limited routing capabilities to a more efficient network, dynamic call routing was developed and deployed. This also requires changes in the topological architecture.
It may be noted that the term network architecture is also fairly commonly used in place of a network topology architecture. A difficulty with the term network architecture is that it is also used to refer to a protocol architecture. It is not hard to guess that network providers are the ones who usually use the term network architecture to refer to a topological architecture.
Dynamic Resource Management
Christofer Larsson, in 5G Networks, 2018
Network Topology
The network topology is chosen so that there are sufficiently many routing possibilities to yield interesting results and still small enough to allow for fast simulation. The speed of simulation is imperative in generating a large number of cases, which is necessary due to the self-similar nature of the traffic.
The topology is a 3-connected network, described in [93]. The 3-connectivity ensures a certain level of resilience, which also implies path diversity [see Fig. 13.2].
Figure 13.2. The topology used allows path diversity, like the three different paths between bottom left and upper right nodes.
The network is modeled by a graph, on which shortest paths are determined. Since the network topology is assumed given and the shortest paths are determined with respect to delay rather than distance, only the connectivity matrix is used in most of the simulations.
We assume that the links have infinite capacity and induce zero delay. This is considered a good approximation for optical fiber networks carrying moderate data volumes. To be able to compute the shortest paths, however, the links are associated with a fictitious delay parameter deduced from the router delays.
The Objectives of Reliability
Lambert Pierrat, in Reliability of High-Power Mechatronic Systems 1, 2017
5.4 Components and system
Todays electronic devices incorporate increasingly numerous and diverse functionalities.
A logical approach to reliability prediction is not to consider the system from the outset, but first and foremost in terms of its constituent components. This is contrary to the approach used in the field of RAMS, which is essentially at the systems level and considers that the failure rates of the components are known a priori.
In terms of structures, the topology of the technological device makes it possible to generate a topology of a different nature [reliability network or failure tree]. This approach, which makes it possible to precisely estimate the reliability of a system, requires the use of simulation software [BAR 75].
In fact, it will be seen that it is possible, as a first approximation, to approach the question in a much more direct way, considering that all the elementary components intervene within a series topological structure comparable to the weak link notion.
In the case of constant elementary failure rates, this approach makes it possible to calculate an upper limit boundary for the overall failure rate through the addition of elementary rates. A more general asymptotic property has been formulated by [DRE 60].
The network topology equivalent to the real network is based on two successive levels of complexity:
that of the elementary components: considered in the usual sense of the term in electronics, that is to say, technologically non-breakable and whose failure rates are inherently weak and generally well established on the basis of sufficient feedback: passive components [resistors, capacitors, etc.] and active components [diodes, transistors, integrated circuits, memories, etc.];
that of the system: integrating various elementary components within a topological structure whose objective is to ensure the function assigned to the device.
These two levels are the subject of specific approaches, each corresponding to their very different natures.
Among the elementary components, some of them, those subject to degradation, are called critical and their model of generic reliability obeys a Weibull law [or if necessary any other bi- or even tri-parametric].
As for the system, its modeling is due to combinatorial aspects induced by its topological organization and, if its size is sufficient [inclusion of a large number of non-critical elementary components], its generic reliability model tends to an exponential law with a constant rate [DRE 60].
These distinctions may lead to different reliability indicators for each of these two entities.
LAN Access Technologies
Edward Insam PhD, BSc, in TCP/IP Embedded Internet Applications, 2003
Overall network topologies
Wireless networks topologies are different to wired LANs. In a wired network, the system manager knows who and where all the nodes are. In a wireless network, nodes can be out of range, disconnected, or roaming [traveling across nodes]. Signal strength can vary considerably from one second to the next, and offices and buildings can be full of dead spots where radiation cannot reach. Network topology must be flexible enough to allow multiple domains to coexist, and for stations to be easily identified and accepted when they join a new network. IEEE 802.11 defines two basic topologies: BSS and ESS. A simple wireless LAN may be formed by one or more roaming cells or stations without a central unit. This is called a basic service set [BSS], also known as an ad hoc network; see Figure 5-11.
Figure 5-11. IEEE 802.11 network topologies
Another format uses many cells with a single access point. The access point is a fixed unit connected to the wired LAN in the building. This is called an extended service set [ESS]. The access points are connected through some kind of backbone [called distribution system or DS]. This backbone is typically Ethernet and, in some cases, may be another form of wireless itself. The whole interconnected wireless LAN, including the cells, their respective access points and the distribution system, is seen as a single 802 network to the upper layers of the OSI model. The IEEE 802 standard also defines the concept of a portal. A portal is a device that interconnects between an 802.11 and another 802 LAN. This concept is an abstract description of part of the functionality of a translation bridge.