• Login
    View Item 
    •   Home
    • Theses and Dissertations
    • Theses and Dissertations
    • View Item
    •   Home
    • Theses and Dissertations
    • Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of TUScholarShareCommunitiesDateAuthorsTitlesSubjectsGenresThis CollectionDateAuthorsTitlesSubjectsGenres

    My Account

    LoginRegister

    Help

    AboutPoliciesHelp for DepositorsData DepositFAQs

    Statistics

    Display statistics

    INFORMATION-UPDATE SYSTEMS: MODELS, ALGORITHMS, AND ANALYSIS

    • CSV
    • RefMan
    • EndNote
    • BibTex
    • RefWorks
    Thumbnail
    Name:
    Sang_temple_0225E_13828.pdf
    Size:
    1.817Mb
    Format:
    PDF
    Download
    Genre
    Thesis/Dissertation
    Date
    2019
    Author
    Sang, Yu
    Advisor
    Ji, Bo, 1982-
    Department
    Computer and Information Science
    Subject
    Computer Science
    Permanent link to this record
    http://hdl.handle.net/20.500.12613/2307
    
    Metadata
    Show full item record
    DOI
    http://dx.doi.org/10.34944/dspace/2289
    Abstract
    Age of information (AoI) has been proposed as a new metric to measure the staleness of data. For time-sensitive information, it is critical to keep the AoI at a low level. A lot of work have been done on the analysis and optimization on AoI in information-update systems. Prior studies on AoI optimization often consider a push model, which is concerned about when and how to "push" (i.e., generate and transmit) the updated information to the user. In stark contrast, we introduce a new pull model, which is more relevant for certain applications (such as the real-time stock quotes service), where a user sends requests to the servers to proactively "pull" the information of interest. Moreover, we propose to employ request replication to reduce the AoI. Interestingly, we find that under this new Pull model, replication schemes capture a novel tradeoff between different levels of information freshness and different response times across the servers, which can be exploited to minimize the expected AoI at the user's side. Specifically, assuming Poisson updating process for the servers and exponentially distributed response time with known expectation, we derive a closed-form formula for computing the expected AoI and obtain the optimal number of responses to wait for to minimize the expected AoI. Then, we extend our analysis to the setting where the user aims to maximize the utility, which is an exponential function of the negative AoI and represents the user's satisfaction level about the timeliness of the received information. We can similarly derive a closed-form formula of the expected utility and find the optimal number of responses to wait for. Further, we consider a more realistic scenario where the updating rate and the mean response time at the servers are unknown to the user. In this case, we formulate the utility maximization problem as a stochastic Multi-Armed Bandit (MAB) Problem. The formulated MAB problem has a special linear feedback graph, which can be leveraged to design policies with an improved regret upper bound. We also notice that one factor has been missing in most of the previous solutions on AoI minimization, which is the cost of performing updates. Therefore, we focus on the tradeoff between the AoI and the update cost, which is of significant importance in time-sensitive data-driven applications. We consider the applications where the information provider is directly connected to the data source, and the clients need to obtain the data from the information provider in a real-time manner (such as the real-time environmental monitoring system). The provider needs to update the data so that it can reply to the clients' requests with fresh information. However, the update cost limits the frequency that the server can refresh the data, which makes it important to design an efficient policy with optimal tradeoff between data freshness and update cost. We define the staleness cost, which reflects the AoI of the data and formulate the problem as the minimization over the summation of the update cost and the staleness cost. We first propose important guidelines of designing update policies in such information-update systems that can be applied to arbitrary request arrival processes. Then, we design an update policy with a simple threshold-based structure, which is easy to implement. Under the assumption of Poisson request arrival process, we derive the closed-form expression of the average cost of the threshold-based policy and prove its optimality among all online update policies. In almost all prior works, the analysis and optimization are based on traditional queueing models with the probabilistic approaches. However, in the traditional probabilistic study of general queueing models, the analysis is heavily dependent on the properties of specific distributions. Under this framework, it is also usually hard to handle distributions with heavy tail behavior. To that end, in this work, we take an alternative new approach and focus on the Peak Age of Information (PAoI), which is the largest age of each update shown to the end users. Specifically, we employ a recently developed analysis framework based on robust optimization and model the uncertainty in the stochastic arrival and service processes by uncertainty sets. This robust queueing framework enables us to approximate the steady-state PAoI performance of information-update systems with very general arrival and service processes, including those exhibiting heavy-tailed behavior. We first propose a new bound of the PAoI under the single-source system that performs much better than previous results, especially with light traffic. Then, we generalize it to multi-source systems with symmetric arrivals, which involves new technical challenges. It has been extensively investigated for various queueing models based on the probabilistic approaches. However, in the traditional probabilistic study of general queueing models, the analysis is heavily dependent on the properties of specific distributions, such as the memoryless property of the Poisson distribution. Under this framework, it is also usually hard to handle distributions with heavy tail behavior. To that end, we take an alternative new approach and focus on the Peak Age of Information (PAoI), which is the largest age of each update shown to the end users. Specifically, we employ a recently developed analysis framework based on robust optimization and model the uncertainty in the stochastic arrival and service processes by uncertainty sets. This robust queueing framework enables us to approximate the steady-state PAoI performance of information-update systems with very general arrival and service processes, including those exhibiting heavy-tailed behavior. We first propose a new bound of the PAoI under the single-source system that performs much better than previous results, especially with light traffic. Then, we generalize it to multi-source systems with symmetric arrivals, which involves new technical challenges.
    ADA compliance
    For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.edu
    Collections
    Theses and Dissertations

    entitlement

     
    DSpace software (copyright © 2002 - 2021)  DuraSpace
    Temple University Libraries | 1900 N. 13th Street | Philadelphia, PA 19122
    (215) 204-8212 | scholarshare@temple.edu
    Open Repository is a service operated by 
    Atmire NV
     

    Export search results

    The export option will allow you to export the current search results of the entered query to a file. Different formats are available for download. To export the items, click on the button corresponding with the preferred download format.

    By default, clicking on the export buttons will result in a download of the allowed maximum amount of items.

    To select a subset of the search results, click "Selective Export" button and make a selection of the items you want to export. The amount of items that can be exported at once is similarly restricted as the full export.

    After making a selection, click one of the export format buttons. The amount of items that will be exported is indicated in the bubble next to export format.