An achievable bit rate per source-destination pair in a wireless network of n randomly located nodes is determined adopting the scaling limit approach of statistical physics. It is shown that ...randomly scattered nodes can achieve, with high probability, the same 1/radicn transmission rate of arbitrarily located nodes. This contrasts with previous results suggesting that a 1/radicnlogn reduced rate is the price to pay for the randomness due to the location of the nodes. The network operation strategy to achieve the result corresponds to the transition region between order and disorder of an underlying percolation model. If nodes are allowed to transmit over large distances, then paths of connected nodes that cross the entire network area can be easily found, but these generate excessive interference. If nodes transmit over short distances, then such crossing paths do not exist. Percolation theory ensures that crossing paths form in the transition region between these two extreme scenarios. Nodes along these paths are used as a backbone, relaying data for other nodes, and can transport the total amount of information generated by all the sources. A lower bound on the achievable bit rate is then obtained by performing pairwise coding and decoding at each hop along the paths, and using a time division multiple access scheme
We study event-triggered control for stabilization of unstable linear plants over rate-limited communication channels subject to unknown bounded delay. On one hand, the timing of event triggering ...carries implicit information about the state of the plant. On the other hand, the delay in the communication channel causes information loss, as it makes the state information available at the controller out of date. Combining these two effects, we show a phase transition behavior in the transmission rate required for stabilization using a given event-triggering strategy. For small values of the delay, the timing information carried by the triggering events is substantial, and the system can be stabilized with any positive rate. When the delay exceeds a critical threshold, the timing information alone is not enough to achieve stabilization, and the required rate grows. When the delay equals the inverse of the entropy rate of the plant, the implicit information carried by the triggering events perfectly compensates the loss of information due to the communication delay, and we recover the rate requirement prescribed by the data-rate theorem. We also provide an explicit construction yielding a sufficient rate for stabilization, as well as results for vector systems. Our results do not rely on any a priori probabilistic model for the delay or the initial conditions.
This paper considers control and estimation problems where the sensor signals and the actuator signals are transmitted to various subsystems over a network. In contrast to traditional control and ...estimation problems, here the observation and control packets may be lost or delayed. The unreliability of the underlying communication network is modeled stochastically by assigning probabilities to the successful transmission of packets. This requires a novel theory which generalizes classical control/estimation paradigms. The paper offers the foundations of such a novel theory. The central contribution is to characterize the impact of the network reliability on the performance of the feedback loop. Specifically, it is shown that for network protocols where successful transmissions of packets is acknowledged at the receiver (e.g., TCP-like protocols), there exists a critical threshold of network reliability (i.e., critical probabilities for the successful delivery of packets), below which the optimal controller fails to stabilize the system. Further, for these protocols, the separation principle holds and the optimal LQG controller is a linear function of the estimated state. In stark contrast, it is shown that when there is no acknowledgement of successful delivery of control packets (e.g., UDP-like protocols), the LQG optimal controller is in general nonlinear. Consequently, the separation principle does not hold in this circumstance
Happiness and other emotions spread between people in direct contact, but it is unclear whether massive online social networks also contribute to this spread. Here, we elaborate a novel method for ...measuring the contagion of emotional expression. With data from millions of Facebook users, we show that rainfall directly influences the emotional content of their status messages, and it also affects the status messages of friends in other cities who are not experiencing rainfall. For every one person affected directly, rainfall alters the emotional expression of about one to two other people, suggesting that online social networks may magnify the intensity of global emotional synchrony.
Celotno besedilo
Dostopno za:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, SIK, UILJ, UKNU, UL, UM, UPUK
Network Coding for Computing: Cut-Set Bounds Appuswamy, R; Franceschetti, M; Karamchandani, N ...
IEEE transactions on information theory,
2011-Feb., 2011-02-00, 20110201, Letnik:
57, Številka:
2
Journal Article
Recenzirano
Odprti dostop
The following network computing problem is considered. Source nodes in a directed acyclic network generate independent messages and a single receiver node computes a target function f of the ...messages. The objective is to maximize the average number of times f can be computed per network usage, i.e., the "computing capacity". The network coding problem for a single-receiver network is a special case of the network computing problem in which all of the source messages must be reproduced at the receiver. For network coding with a single receiver, routing is known to achieve the capacity by achieving the network min-cut upper bound. We extend the definition of min-cut to the network computing problem and show that the min-cut is still an upper bound on the maximum achievable rate and is tight for computing (using coding) any target function in multi-edge tree networks. It is also tight for computing linear target functions in any network. We also study the bound's tightness for different classes of target functions. In particular, we give a lower bound on the computing capacity in terms of the Steiner tree packing number and a different bound for symmetric functions. We also show that for certain networks and target functions, the computing capacity can be less than an arbitrarily small fraction of the min-cut bound.
Immunoglobulin genes are formed through V(D)J recombination, which joins the variable (V), diversity (D), and joining (J) germline genes. Since variations in germline genes have been linked to ...various diseases, personalized immunogenomics focuses on finding alleles of germline genes across various patients. Although reconstruction of V and J genes is a well-studied problem, the more challenging task of reconstructing D genes remained open until the IgScout algorithm was developed in 2019. In this work, we address limitations of IgScout by developing a probabilistic MINING-D algorithm for D gene reconstruction, apply it to hundreds of immunosequencing datasets from multiple species, and validate the newly inferred D genes by analyzing diverse whole genome sequencing datasets and haplotyping heterozygous V genes.
Celotno besedilo
Dostopno za:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, SIK, UILJ, UKNU, UL, UM, UPUK
To what extent can online social networks predict who is at risk of an infection? Many infections are transmitted through physical encounter between humans, but collecting detailed information about ...it can be expensive, might invade privacy, or might not even be possible. In this paper, we ask whether online social networks help predict and contain epidemic risk. Using a dataset from a popular online review service which includes over 100 thousand users and spans 4 years of activity, we build a time-varying network that is a proxy of physical encounter between its users (the encounter network) and a static network based on their reported online friendship (the friendship With computer simulations, we compare stochastic infection processes on the two networks, considering infections on the encounter network as the benchmark. First, we show that the friendship network is useful to identify the individuals at risk of infection, despite providing lower accuracy than the ideal case in which the encounters are known. This limited prediction accuracy is not only due to the static nature of the friendship network because a static version of the encounter network provides more accurate prediction of risk than the friendship network. Then, we show that periodical monitoring of the infection spreading on the encounter network allows to correct the infection predicted by a process spreading on the friendly staff ndship network, and achieves high prediction accuracy. Finally, we show that the friendship network contains valuable information to effectively contain epidemic outbreaks even when a limited budget is available for immunization. In particular, a strategy that immunizes random friends of random individuals achieves the same performance as knowing individuals' encounters at a small additional cost, even if the infection spreads on the encounter network.
Celotno besedilo
Dostopno za:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, SIK, UILJ, UKNU, UL, UM, UPUK
A variation of the Pearson-Rayleigh random walk in which the steps are i.i.d. random vectors of exponential length and uniform orientation is considered. Conditioned on the total path length, the ...probability density function of the position of the walker after n steps is determined analytically in one and two dimensions. It is shown that in two dimensions n = 3 marks a critical transition point in the behavior of the random walk. By taking less than three steps and walking a total length l, one is more likely to end the walk near the boundary of the disc of radius l, while by taking more than three steps one is more likely to end near the origin. Somehow surprisingly, by taking exactly three steps one can end uniformly anywhere inside the disc of radius l. This means that conditioned on l, the sum of three vectors of exponential length and uniform direction has a uniform probability density.While the presented analytic approach provides a complete solution for all n, it becomes intractable in higher dimensions. In this case, it is shown that a necessary condition to have a uniform density in dimension d is that 2(d + 2)/d is an integer, equal to n + 1.
This paper considers a random access system where each sender is in one of two possible states, active or not active, and the states are only known to the common receiver. Active senders encode data ...into independent information streams, a subset of which is decoded depending on the collective interference. An information-theoretic formulation of the problem is presented and the set of achievable rates is characterized with a guaranteed gap to optimality. Inner and outer bounds on the capacity region of a two-sender system are tight in the case of a binary-expansion deterministic channel and differ by less than one bit in the case of a Gaussian channel. In systems with an arbitrary number of senders, the symmetric scenario of equal access probabilities and received power constraints is studied and the system throughput, i.e., the maximum achievable expected sum rate, is characterized. It is shown that a simple coding scheme where active senders transmit a single message is optimum for a binary-expansion deterministic channel and achieves within one bit of the optimum in the case of a Gaussian channel. Finally, a comparison with the slotted ALOHA protocol is provided, showing that encoding rate adaptation at the transmitters achieves constant (rather than zero) throughput as the number of users tends to infinity.
A variation of Landau's eigenvalue theorem describing the phase transition of the eigenvalues of a time-frequency limiting, self adjoint operator is presented. The total number of degrees of freedom ...of square-integrable, multidimensional, bandlimited functions is defined in terms of Kolmogorov's n -width and computed in some limiting regimes, where the original theorem cannot be directly applied. Results are used to characterize up to order the total amount of information that can be transported in time and space by multiple-scattered electromagnetic waves, rigorously addressing a question originally posed in the early works of Toraldo di Francia and Gabor. Applications in the context of wireless communication and electromagnetic sensing are discussed.
PDF
