Time-Critical Decisions With Real-Time Information Extraction / Xingran Chen.

Format:

Book

Thesis/Dissertation

Author/Creator:

Chen, Xingran, author.

Contributor:

University of Pennsylvania. Electrical and Systems Engineering, degree granting institution.

Language:

English

Subjects (All):

Information science.

Communication.

Electrical and Systems Engineering--Penn dissertations.

Penn dissertations--Electrical and Systems Engineering.

Local Subjects:

Information science.

Communication.

Electrical and Systems Engineering--Penn dissertations.

Penn dissertations--Electrical and Systems Engineering.

Physical Description:

1 online resource (282 pages)

Contained In:

Dissertations Abstracts International 85-03B.

Place of Publication:

[Philadelphia, Pennsylvania] : University of Pennsylvania, 2022.

Ann Arbor : ProQuest Dissertations & Theses, 2023

Language Note:

English

Summary:

The Internet of Things and the next-generation networks have led to the generation, dissemination, and transformation of a huge amount of real-time information. The information is often governed by processes that evolve over time and/or space (e.g. on an underlying network). This thesis will develop theoretical foundations and algorithmic designs for time-critical decisions with real-time information extraction in networked systems and considers applications such as estimation and network coding in IoT and testing and isolation for COVID-19.In the first part, we study the timeliness of information transfer in communication networks. Timeliness was first captured and quantified in point-to-point channels through the metric of age of information (AoI) and has since become a new design criterion in communications. In this thesis, we go beyond point-to-point channels and consider multiple access networks with multiple senders, broadcast networks with multiple receivers, as well as general ad-hoc networks.In Chapter 2, we study the problem of age minimization in random access channels. This problem is essential in the remote estimation and control of processes that are observed from decentralized sources in wireless networks. Scheduling policies in multiple access channels is no longer realistic due to a huge amount of communication and coordination among sources. We propose decentralized policies to minimize the time-average AoI and provide performance guarantees for them. In particular, we show that in the regime of low packet arrival rate (< 1/eM , where M is the number of sources), the standard slotted ALOHA policy is asymptotically age-optimal as the number of sources gets large. However, when the packet arrival rate gets larger, the age performance for slotted ALOHA deteriorates and diverges when the time horizon is large. To overcome the challenge, we propose the notion of age-gain of a packet to quantify how much the packet will reduce the instantaneous age of information at the receiver side upon successful delivery. We then utilize this notion to propose a transmission policy in which sources act in a decentralized manner based on the age-gain of their available packets. Each source sends its latest packet only if its corresponding age-gain is beyond a certain threshold which could be computed adaptively using the collision feedback or found as a fixed value analytically in advance. In the regime where the packet arrival rate is relatively large (= 1/o(M) ), we achieve the age-performance of e/2 , which provides a multiplicative gain of at least two compared to the minimum age under slotted ALOHA (minimum over all arrival rates). We conclude that it is beneficial to increase the sampling rate (and hence the arrival rate) and transmit packets selectively based on their age-gain. This is surprising and contrary to common practice where the arrival rate is optimized to attain the minimum AoI.In Chapter 3, we study the problem of estimation error minimization in random access channels. Real-time sampling and estimation for autoregressive Markov processes is considered. Two general classes of policies are investigated: oblivious policies and non-oblivious policies. In the former class, decision-making is independent of the processes that are monitored, and we prove that minimizing the expected time-average estimation error is equivalent to minimizing the expected time-average AoI. In the latter class, decision-making depends on the physical processes. We first provide a closed-form expression for the estimation error that is a function of the peak age, the transmission delay, a term which we call the silence delay, as well as the process realization. We then approximately propose an optimal thresholding policy with the threshold σ√eM (where M is the number of sources and σ is the standard deviation in physical processes) and the resulting normalized estimation error is e/6σ2 . The proposed non-oblivious thresholding policy provides a 3-fold improvement compared to age-based oblivious policies, and the age-based oblivious policy provides a 2-fold improvement compared to the state-of-the-art. Simulation results verify that the proposed decentralized thresholding policy outperforms all state-of-the-art policies, and the performance is very close to that of centralized greedy policies.The formulation and approaches outlined in Chapters 2 and 3 are specific to the simple network topology of random multi-access channels. We go beyond random access channels in Chapter 4 and study the problems of age minimization and estimation error minimization in ad-hoc networks. There are M statistically identical sources in an ad-hoc network, where every source transmits packets to connected sources. Collisions happen if two or more sources in proximity simultaneously transmit packets. Here, we seek to design decentralized policies for each source to decide when to sample, whom to communicate with, and what to transmit to minimize the time-average estimation error and/or age. To tackle the multi-dimensionality of the space of decision-making and to capture the complex topologies of wireless networks, we propose a graphical reinforcement learning framework since theoretical methods are no longer tractable. The proposed framework is proven to be permutation equivalent and enjoys desirable transferability property. In particular, the transmission policies trained on small- or moderate-size networks can be executed on large-scale topologies. We also demonstrate, via numerical experiments, that (i) the transmission policies obtained by the proposed framework outperform state-of-the-art baselines, (ii) the trained transmission policies are transferable to larger networks, and their performance gains increase with the number of agents, and (iii) the training procedure can withstand non-stationarity even if we utilize independent learning techniques.In Chapter 5, we investigate the tradeoffs between timeliness and communication rate in broadcast networks. To shed light on the tradeoffs, we first propose a novel framework of network AoI on the broadcast channels under a transmission mechanism with coding. We then propose two classes of coding policies: coding policies with uncoded caching and coding policies with coded caching. Two general lower bounds and an upper bound are derived on the time-average AoI for any transmission policy. The bounds are functions of generation rates, erasure probabilities, and target rate constraints. Simulation results reveal that (i) coding is beneficial, and the benefits increase with the number of users; (ii) a good approximation of proposed policies is obtained based on the maximum clique size of the information graph; (iii) the tradeoff between rate and age exists, which implies that the system has to sacrifice age to achieve a higher rate.Going beyond age minimization in wireless networks, in the second part of this thesis, we study the problem of testing and control of spread processes. This problem is another instance of time-critical decision-making with real-time information extraction. In Chapter 6, the spread of an undesirable contact process, such as an infectious disease (e.g., COVID-19), is contained through testing and isolation of infected nodes. The temporal and spatial evolution of the process (along with containment through isolation) render such detection as fundamentally different from active search detection strategies. Through an active learning approach, we design testing and isolation strategies to contain the spread and minimize the cumulative infections under a given test budget. We prove that the objective can be optimized, with performance guarantees, by greedily selecting the nodes to test. We further design reward-based methodologies that effectively minimize an upper bound on the cumulative infections and are computationally more tractable in large networks. These policies, however, need knowledge about the nodes' infection probabilities which are dynamically changing and have to be learned by sequential testing. We develop a message-passing framework for this purpose and, building on that, show novel tradeoffs between the exploitation of knowledge through reward-based heuristics and the exploration of the unknown through carefully designed probabilistic testing.

The tradeoffs are fundamentally distinct from the classical counterparts under active search or multi-armed bandit problems (MABs). We provably show the necessity of exploration in a stylized network and show through simulations that exploration can outperform exploitation in various synthetic and real-data networks depending on the parameters of the network and the spread.

Notes:

Source: Dissertations Abstracts International, Volume: 85-03, Section: B.

Advisors: Saeedi-Bidokhti, Shirin; Committee members: Sarkar, Saswati; Hassani, Hamed; Modiano, Eytan; Yener, Aylin.

Department: Electrical and Systems Engineering.

Ph.D. University of Pennsylvania 2023.

Local Notes:

School code: 0175

ISBN:

9798380388818

Access Restriction:

Restricted for use by site license.

This item is not available from ProQuest Dissertations & Theses.