A. James Clark School of Engineering
Permanent URI for this communityhttp://hdl.handle.net/1903/1654
The collections in this community comprise faculty research works, as well as graduate theses and dissertations.
Browse
4 results
Search Results
Item Enhancement and Robustness of Large Timely Gossip Networks(2024) Kaswan, Priyanka; Ulukus, Sennur; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this thesis, we explore the subject of fast dissemination of real-time data from a source to multiple users, critical for time-sensitive applications such as autonomous driving sytems, internet of things (IoT), augmented reality (AR), virtual reality (VR), and real-time content sharing in social networks, that feature dense interconnected networks of devices and humans. In face of network resource limitations and increasingly dynamic data generated by various sources in these networks, it is imperative that all nodes within these networks have timely information, i.e., the latest possible updates about the source nodes at all times for seamless functioning of these networks. Although it might seem straightforward to transmit changing data at high speed to all users, practical challenges such as limited bandwidth, server servicing speed, and intermittent connectivity hinder this approach. Therefore, to achieve the goal of timeliness, measured by metrics such as the age of information, this thesis leverages gossip algorithms, which are decentralized algorithms whose popularity stems from their efficiency and scalablility for information dissemination in such constrained and uncertain networks. This thesis aims to deepen our understanding of the capabilities and limitations of timely gossip networks of various topologies in managing large volumes of dynamic data. As importantly, this thesis explores the unique threats and vulnerabilities these next-generation networks face in the evolving landscape of 5G and 6G technologies. We open our analysis of this subject by first exploring efficient strategies for timely dissemination of time-varying data files from a source to a user via a simple network of parallel relays. We find that consolidating file update rates to the minimum number of relays improves timeliness, contrary to using all relays for each file. By solving an auxiliary single-cache problem and adapting its solution to our multi-cache network, we provide a sub-optimal solution, such that the upper bound on its gap to the optimal policy is independent of the number of files. Next, we explore complex network topologies and examine the resilience of gossip networks as a function of their connectivity to jamming attacks. We analyze the average version age in the presence of $\tilde{n}$ jammers for both connectivity-constrained ring and connectivity-rich fully connected topologies of $n$ nodes. Our findings reveal that a ring network is robust against up to $\sqrt{n}$ jammers, while a fully connected network withstands $n\log{n}$ jammers, showing that higher connectivity enhances resilience to jamming. To maximize age deterioration in the network, the jammers should attack in a manner that consolidates all remaining unjammed links into a dense cluster of the fewest possible nodes, leaving a higher number of nodes isolated. Next, we uncover a new type of attack in age-based networks, called timestomping, where an adversary manipulates timestamps of information packets, causing nodes to discard fresh packets for stale ones. We show that in fully connected networks, a single infected node can increase the expected age from $O(\log n)$ to $O(n)$, highlighting how full connectivity can expedite adversarial impacts. Conversely, in unidirectional ring networks with sparse inter-node connectivity, we find that the adversarial impact on node age scaling is confined by its distance from the adversary, maintaining an age scaling of $O(\sqrt{n})$ for a significant fraction of the network. Then, we demonstrate how the age-specific nature of file exchange protocols also makes gossip networks susceptible to the propagation of misinformation. We consider networks where packets can potentially get mutated during inter-node gossiping, creating misinformation. Nodes prefer latest versions of information, however, when a receiving node encounters both accurate information and misinformation for the same version, we consider two models: one where truth prevails over misinformation and another where misinformation prevails over truth. Using stochastic hybrid systems (SHS) modeling, we examine the expected fraction of nodes with correct information and the version age. We show that higher or lower gossiping rates effectively reduce misinformation when truth prevails, whereas moderate rates increase its spread. Conversely, misinformation prevalence rises with increased gossiping under the misinformation-prevailing scenario. Then, we consider the balance between freshness and reliability of information in an age-based gossip network, where two sources (reliable and unreliable) disseminate updates to $n$ network nodes. Nodes wish to have fresh information, however, they have preference for packets that originate at the reliable source and are willing to sacrifice their version age of information by up to $G$ versions to switch from an unreliable packet to a reliable packet. We show that increasing $G$ reduces unreliable packets but raises the network version age, revealing a freshness-reliability trade-off. Next, we develop a theory of timeliness for non-Poisson updating and study cache-aided networks where the inter-update times on the links are not necessarily exponentially distributed. We characterize the expressions for instantaneous age and version age in arbitrary networks, then derive their closed form expressions in case of tree networks, where they exhibit an additive structure. Finally, we analyze age of information in networks where update processes on the links become sparse as network size increases, noting that in symmetric fully connected networks, expected age scales as $O(\log{n})$. Then, we study a system where a group of users, interested in closely tracking a time-varying event and maintaining their expected version ages below a threshold, choose between either preferably relying on gossip from their neighbors or directly subscribing to a server publishing about the event, to meet the timeliness requirements. The server wishes to maximize its profit by boosting subscriptions from users and minimizing event sampling frequency to reduce costs, setting up a Stackelberg game between the server and the users. We analyze equilibrium strategies in both directed and undirected networks, finding that well-connected networks have fewer subscribers since well-connected users dissuade their multiple neighboring nodes from subscribing. Next, we consider a gossip network of $n$ users hosting a library of files, such that each file is initially present at exactly one node, designated as the file source. The source gets updated with newer versions of the file according to an arbitrary distribution in real-time, and the other users in the network wish to acquire the latest possible version of the file. We present a class of gossip protocols that achieve $O(1)$ age at a typical node in a single-file system and $O(n)$ age at a typical node for a given file in an $n$-file system. We show that file slicing and network coding based protocols fall under the presented class of protocols. Finally, we further explore timestomping attacks in a simplified communication model, where a source attempts to minimize the age of a user, but due to a power constraint, the source can only transmit updates directly to the user for a fraction of timeslots over a fixed time horizon. A cache node, which can afford more frequent transmissions, lies in between the source and the user, however the communication link between the cache and the user is under attack by a timestomping adversary. We formulate this adversarial cache updating problem as an online learning problem and study the achievable competitive ratios for this problem.Item Age of Information Optimization for Timeliness in Communication Networks(2021) Bastopcu, Melih; Ulukus, Sennur; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)With the emergence of technologies such as autonomous vehicular systems, holographic communications, remote surgery and high frequency automated trading, timeliness of information has become more important than ever. Most traditional performance metrics, such as delay or throughput, are not sufficient to measure timeliness. For that, age of information (AoI) has been introduced recently as a new performance metric to quantify the timeliness in communication networks. In this dissertation, we consider timely update delivery problems in communication networks under various system settings. First, we introduce the concept of soft updates, where different from the existing literature, here, updates are soft and begin reducing the age immediately but drop it gradually over time. Our setting models human interactions where updates are soft, and also social media interactions where an update consists of viewing and digesting many small pieces of information posted, that are of varying importance, relevance and interest to the receiver. For given total system duration, the number of updates, and the total allowed update duration, we find the optimum start times of the soft updates and their optimum durations to minimize the overall age. Then, we consider an information updating system where not only the timeliness but also the quality of the updates is important. Here, we use distortion as a proxy for quality, and model distortion as a decreasing function of processing time spent while generating the updates. Processing longer at the transmitter results in a better quality (lower distortion) update, but it causes the update to age in the process. We determine age-optimal policies by characterizing the update request times at the receiver and the update processing times at the transmitter subject to constant or age-dependent distortion constraints on each update. Next, different from most of the existing literature on AoI where the transmission times are based on a given distribution, by assigning codeword lengths for each status update, we design transmission times through source coding schemes. In order to further improve timeliness, we propose selective encoding schemes where only the most probable updates are transmitted. For the remaining least probable updates, we consider schemes where these updates are never sent, randomly sent, or sent by an empty symbol. For all these encoding schemes, we determine the optimal number of encoded updates and their corresponding age-optimal real-valued codeword lengths to minimize the average age at the receiver. Then, we study the concept of generating partial updates which carry less information compared to the original updates, but their transmission times are shorter. Our aim is to find the age-optimal partial update generation process and the corresponding age-optimal real-valued codeword lengths for the partial updates while maintaining a desired level of fidelity between the original and partial updates. Next, we consider information freshness in a cache updating system consisting of a source, cache(s) and a user. Here, the user may receive an outdated file depending on the freshness status of the file at the cache. We characterize the binary freshness metric at the end user and propose an alternating maximization based method to optimize the overall freshness at the end user subject to total update rate constraints at the cache(s) and the user. Then, we study a caching system with a limited storage capacity for the cache. Here, the user either gets the files from the cache, but the received files can be sometimes outdated, or gets fresh files directly from the source at the expense of additional transmission times which inherently decrease the freshness. We show that when the total update rate and the storage capacity at the cache are limited, it is optimal to get the frequently changing files and files with relatively small transmission times directly from the source, and store the remaining files at the cache. Next, we focus on information freshness in structured gossip networks where in addition to the updates obtained from the source, the end nodes share their local versions of the updates via gossiping to further improve freshness. By using a stochastic hybrid systems (SHS) approach, we determine the information freshness in arbitrarily connected gossip networks. When the number of nodes gets large, we find the scaling of information freshness in disconnected, ring and fully connected network topologies. Further, we consider clustered gossip networks where multiple clusters of structured gossip networks are connected to the source through cluster heads, and find the optimal cluster sizes numerically. Then, we consider the problem of timely tracking of multiple counting random processes via exponential (Poisson) inter-sampling times, subject to a total sampling rate constraint. A specific example is how a citation index such as Google Scholar should update citation counts of individual researchers to keep the entire citation index as up-to-date as possible. We model citation arrival profile of each researcher as a counting process with a different mean, and consider the long-term average difference between the actual citation numbers and the citation numbers according to the latest updates as a measure of timeliness. We show that, in order to minimize this difference metric, Google Scholar should allocate its total update capacity to researchers proportional to the square roots of their mean citation arrival rates. Next, we consider the problem of timely tracking of multiple binary random processes via sampling rate limited Poisson sampling. As a specific example, we consider the problem of timely tracking of infection status (e.g., covid-19) of individuals in a population. Here, a health care provider wants to detect infected and recovered people as quickly as possible. We measure the timeliness of the tracking process as the long term average difference between the actual infection status of people and their real-time estimate at the health care provider which is based on the most recent test results. For given infection and recovery rates of individuals, we find the exponentially applied testing rates for individuals to minimize this difference. We observe that when the total test rate is limited, instead of applying tests to everyone, only a portion of the population should be tested. Finally, we consider a communication system with multiple information sources that generate binary status updates, which in practical application may indicate an anomaly (e.g., fire) or infection status (e.g., covid-19). Each node exhibits an anomaly or infection with probability $p$. In order to send the updates generated by these sources as timely as possible, we propose a group updating method inspired by group testing, but with the goal of minimizing the overall average age, as opposed to the average number of tests (updates). We show that when the probability $p$ is small, group updating method achieves lower average age than the sequential updating methods.Item Energy Harvesting Communication Networks with System Costs(2017) Arafa, Ahmed; Ulukus, Sennur; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation focuses on characterizing optimal energy management policies for energy harvesting communication networks with system costs. The system costs that we consider are the cost of circuitry to be on (processing cost) at the transmitters, cost of decoding at the receivers, cost of moving to harvest more energy in mobile energy harvesting nodes, and the cost of collecting measurements (sampling cost) from physical phenomena. We first consider receiver decoding costs in networks where receivers, in addition to transmitters, rely on energy harvested from nature to communicate. Energy harvested at the receivers is used to decode their intended messages, and is modeled as a convex increasing function of the incoming rate. With the goal of maximizing throughput by a given deadline, we study single-user and multi-user settings, and show that decoding costs at the receivers can be represented as generalized data arrivals at the transmitters. This introduces a further coupling between the transmitters and receivers of the network and allows us to characterize optimal policies by moving all constraints to the transmitter side. Next, we study the decoding cost effect on energy harvesting cooperative multiple access channels, where users employ data cooperation to increase their achievable rates. Data cooperation requires each user to decode the other user's data before forwarding it to the destination, which uses up some of the harvested energy. With the presence of decoding costs, we show that data cooperation may not be always helpful; if the decoding costs are relatively high, then sending directly to the receiver without data cooperation between the users achieves higher throughput. When cooperation is helpful, we determine the optimum allocation of available energy between decoding cooperative partner's data and forwarding it to the destination. We then study the impact of adding processing costs, on top of decoding costs, in energy harvesting two-way channels. Processing costs are the amounts of energy spent for circuitry operation, and are incurred whenever a user is communicating. We show that due to processing costs, transmission may become bursty, where users communicate through only a portion of the time. We develop an optimal scheme that maximizes the sum throughput by a given deadline under both decoding and processing costs. Next, we focus on online policies. We consider a single-user energy harvesting channel where the transmitter is equipped with a finite-sized battery, and the goal is to maximize the long term average utility, for general concave increasing utility functions. We show that fixed fraction policies are near optimal; they achieve a long term average utility that lies within constant multiplicative and additive gaps from the optimal solution for all battery sizes and all independent and identically distributed energy arrival patterns. We then consider a specific scenario of a utility function that measures the distortion of Gaussian samples communicated over a Gaussian channel. We formulate two problems: one with, and the other without sampling costs, and design near optimal fixed fraction policies for the two problems. Then, we consider another aspect of costs in energy harvesting single-user channels, that is, the energy spent in physical movement in search of better energy harvesting locations. Since movement has a cost, there exists a tradeoff between staying at the same location and moving to a new one. Staying at the same location allows the transmitter to use all its available energy in transmission, while moving to a new one may let the transmitter harvest higher amounts of energy and achieve higher rates at the expense of a cost incurred through the relocation process. We characterize this tradeoff optimally under both offline and online settings. Next, we consider different performance metrics, other than throughput, in energy harvesting communication networks. First, we study the issue of delay in single-user and broadcast energy harvesting channels. We define the delay per data unit as the time elapsed from the unit's arrival at the transmitter to its departure. With a pre-specified amount of data to be delivered, we characterize delay minimal energy management policies. We show that the structure of the optimal policy is different from throughput-optimal policies; to minimize the average delay, earlier arriving data units are transmitted using higher powers than later arriving ones, and the transmit power may reach zero, leading to communication gaps, in between energy or data arrival instances. Finally, we conclude this dissertation by considering the metric of the age of information in energy harvesting two-hop networks, where a transmitter is communicating with a receiver through a relay. Different from delay, the age of information is defined as the time elapsed since the latest data unit has reached the destination. We show that age minimal policies are such that the transmitter sends message updates to the relay just in time as the relay is ready to forward them to the receiver.Item Age of Information and Energy Efficiency in Communication Networks(2015) Dutra da Costa, Maice; Ephremides, Anthony; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation focuses on two important aspects of communication systems, namely energy efficiency and age of information. Both aspects have received much less attention than traditional performance metrics, such as throughput and delay. The need to improve the energy efficiency in communication networks is apparent, given the high demand for power consuming applications to be implemented in devices with limited energy supplies. Additionally, improvements in energy efficiency are encouraged by possible reductions in network operation costs, and by the increasing awareness of the environmental impact caused by the information and communication technologies. In this dissertation, energy efficiency is studied in the context of a cognitive wireless network, in which users have different priorities to access the network resources, possibly interfering and cooperating among themselves. A new parametrization is proposed to characterize performance trade-offs associated with energy efficiency for non-cooperative and cooperative network models. Additionally, a game theoretic model is proposed to study resource allocation in a cooperative cognitive network, accounting for energy efficiency in the utility functions. Age of information is a relatively new concept, which aims to characterize the timeliness of information. It is relevant to any system concerned with timeliness of information, and particularly relevant when information is used to make decisions, but the value of the information is degraded with time. This is the case in many applications of communications and control systems. In this dissertation, the age of information is first investigated for status update communication systems. The status updates are samples of a random process under observation, transmitted as packets, which also contain the time stamp to identify when the sample was generated. The age of information at the destination node is the time elapsed since the last received update was generated. The status update systems are modeled using queuing theory. We propose models for status update systems capable of managing the packets before transmission, aiming to avoid wasting network resources with the transmission of stale information. In addition to characterizing the average age, we propose a new metric, called peak age, which provides information about the maximum value of the age, achieved immediately before receiving an update. We also propose a new framework, based on the concept of age of information, to analyze the effect of outdated Channel State Information (CSI) on the performance of a communication link in which the source node acquires the CSI through periodic feedback from the destination node. The proposed framework is suitable to analyze the trade-off between performance and timeliness of the CSI, which is a fundamental step to design efficient adaptation functions and feedback protocols.