skip to main content

Search for: All records

Creators/Authors contains: "Chen Yutian"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Base station-less sensor networks (BSNs) refer to emerging sensing applications deployed in challenging environments (e.g., underwater exploration). As installing a base station in such an environment is not feasible, data generated in the BSN will be preserved in the network before being collected by the uploading opportunities. This process is called data preservation in the BSN. Considering that sensor nodes are intelligent and selfish, this paper studies the Nash Equilibrium (NE) for data preservation in BSNs. We design a suite of data preservation algorithms, examine whether they achieve NEs, and rigorously analyze the performance of the NEs using existing (i.e., price of anarchy and price of stability) and our own designed metrics (i.e., rate of efficiency loss). We find that a minimum cost flow-based algorithm produces a NE that achieves the social optimal with minimum energy consumption in the data preservation process. We show the NE from one of our straightforwardly designed greedy algorithms achieves a price of anarchy of 3. On the other hand, we prove that a greedy algorithm always exists (although non-straightforward), achieving the socially optimal NE. Finally, we conduct extensive simulations to investigate the performances of various data preservation NEs and validate our theoretical results under different network parameters. 
    more » « less
    Free, publicly-accessible full text available September 25, 2024
  2. We aim to preserve a large amount of data generated insidebase station-less sensor networks(BSNs) while considering that sensor nodes are selfish. BSNs refer to emerging sensing applications deployed in challenging and inhospitable environments (e.g., underwater exploration); as such, there do not exist data-collecting base stations in the BSN to collect the data. Consequently, the generated data has to be stored inside the BSN before uploading opportunities become available. Our goal is to preserve the data inside the BSN with minimum energy cost by incentivizing the storage- and energy-constrained sensor nodes to participate in the data preservation process. We refer to the problem as DPP:datapreservationproblem in the BSN. Previous research assumes that all the sensor nodes are cooperative and that sensors have infinite battery power and design a minimum-cost flow-based data preservation solution. However, in a distributed setting and under different control, the resource-constrained sensor nodes could behave selfishly only to conserve their resources and maximize their benefit.

    In this article, we first solve DPP by designing an integer linear programming (ILP)-based optimal solution without considering selfishness. We then establish a game-theoretical framework that achieves provably truthful and optimal data preservation in BSNs. For a special case of DPP wherein nodes are not energy-constrained, referred to as DPP-W, we design a data preservation game DPG-1 that integrates algorithmic mechanism design (AMD) and a more efficient minimum cost flow-based data preservation solution. We show that DPG-1 yields dominant strategies for sensor nodes and delivers truthful and optimal data preservation. For the general case of DPP (wherein nodes are energy-constrained), however, DPG-1 fails to achieve truthful and optimal data preservation. Utilizing packet-level flow observation of sensor node behaviors computed by minimum cost flow and ILP, we uncover the cause of the failure of the DPG-1. It is due to the packet dropping by the selfish nodes that manipulate the AMD technique. We then design a data preservation game DPG-2 for DPP that traces and punishes manipulative nodes in the BSN. We show that DPG-2 delivers dominant strategies for truth-telling nodes and achieves provably optimal data preservation with cheat-proof guarantees. Via extensive simulations under different network parameters and dynamics, we show that our games achieve system-wide data preservation solutions with optimal energy cost while enforcing truth-telling of sensor nodes about their private cost types. One salient feature of our work is its integrated game theory and network flows approach. With the observation of flow level sensor node behaviors provided by the network flows, our proposed games can synthesize “microscopic” (i.e., selfish and local) behaviors of sensor nodes and yield targeted “macroscopic” (i.e., optimal and global) network performance of data preservation in the BSN.

    more » « less
    Free, publicly-accessible full text available October 19, 2024
  3. We design a data preservation game called Data-VCG for base station-less sensor networks ( BSNs ). In the BSN, sensor nodes do not have connected paths to a base station thus, sensory data must be preserved inside the network before uploading opportunities arise. Data-VCG incorporates data values into the classic Vickrey-Clark-Groves (VCG) mechanism, a generic truthful mechanism for achieving a socially-optimal solution. It motivates all the sensor nodes (i.e., source, storage, and transition) to voluntarily participate in the data preservation process while achieving minimum data preservation cost. We give a detailed analysis of the performance guarantee of the Data-VCG and show that under certain conditions, its worst-case budget imbalance is at most n−3 times the efficiency gain, where n is the number of sensor nodes in the network. We conduct extensive simulations to validate our results in both grids and randomly generated BSNs under different network dynamics. 
    more » « less
  4. We consider the problem of preserving a large amount of data generated inside base station-less sensor networks, when sensor nodes are controlled by different authorities and behave selfishly. We modify the VCG mechanism to guarantee that each node, including the source nodes with overflow data packets, will voluntarily participate in data preservation. The mechanism ensures that each node truthfully reports its private type and network achieves efficiency for all the preserved data packets. Extensive simulations are conducted to further validate our results. 
    more » « less
  5. Service function chaining (SFC), consisting of a sequence of virtual network functions (VNFs) (i.e., firewalls and load balancers), is an effective service provision technique in modern data center networks. By requiring cloud user traffic to traverse the VNFs in order, SFC im- proves the security and performance of the cloud user applications. In this paper, we study how to place an SFC inside a data center to mini- mize the network traffic of the virtual machine (VM) communication. We take a cooperative multi-agent reinforcement learning approach, wherein multiple agents collaboratively figure out the traffic-efficient route for the VM communication. Underlying the SFC placement is a fundamental graph-theoretical prob- lem called the k-stroll problem. Given a weighted graph G(V, E), two nodes s, t ∈ V , and an integer k, the k-stroll problem is to find the shortest path from s to t that visits at least k other nodes in the graph. Our work is the first to take a multi-agent learning approach to solve k- stroll problem. We compare our learning algorithm with an optimal and exhaustive algorithm and an existing dynamic programming(DP)-based heuristic algorithm. We show that our learning algorithm, although lack- ing the complete knowledge of the network assumed by existing research, delivers comparable or even better VM communication time while taking two orders of magnitude of less execution time. 
    more » « less