skip to main content


Title: Age-Dependent Distributed MAC for Ultra-Dense Wireless Networks
We consider an ultra-dense wireless network with N channels and M = N devices. Messages with fresh information are generated at each device according to a random process and need to be transmitted to an access point. The value of a message decreases as it ages, so each device searches for an idle channel to transmit the message as soon as it can. However, each channel probing is associated with a fixed cost (energy), so a device needs to adapt its probing rate based on the "age" of the message. At each device, the design of the optimal probing strategy can be formulated as an infinite horizon Markov Decision Process (MDP) where the devices compete with each other to find idle channels. While it is natural to view the system as a Bayesian game, it is often intractable to analyze such a system. Thus, we use the Mean Field Game (MFG) approach to analyze the system in a large-system regime, where the number of devices is very large, to understand the structure of the problem and to find efficient probing strategies. We present an analysis based on the MFG perspective. We begin by characterizing the space of valid policies and use this to show the existence of a Mean Field Nash Equilibrium (MFNE) in a constrained set for any general increasing cost functions with diminishing rewards. Further we provide an algorithm for computing the equilibrium for any given device, and the corresponding age-dependent channel probing policy.  more » « less
Award ID(s):
1719384 2001687 2002608
NSF-PAR ID:
10296547
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
IEEE Conference on Computer Communications INFOCOM
Page Range / eLocation ID:
1 to 10
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We consider a class of deterministic mean field games, where the state associated with each player evolves according to an ODE which is linear w.r.t. the control. Existence, uniqueness, and stability of solutions are studied from the point of viewof generic theory. Within a suitable topological space of dynamics and cost functionals, we prove that, for “nearly all” mean field games (in the Baire category sense) the best reply map is single-valued for a.e. player. As a consequence, the mean field game admits a strong (not randomized) solution. Examples are given of open sets of games admitting a single solution, and other open sets admitting multiple solutions. Further examples show the existence of an open set of MFG having a unique solution which is asymptotically stable w.r.t. the best reply map, and another open set of MFG having a unique solution which is unstable. We conclude with an example of a MFG with terminal constraints which does not have any solution, not even in the mild sense with randomized strategies. 
    more » « less
  2. We formulate a mean field game where each player stops a privately observed Brownian motion with absorption. Players are ranked according to their level of stopping and rewarded as a function of their relative rank. There is a unique mean field equilibrium, and it is shown to be the limit of associated n-player games. Conversely, the mean field strategy induces n-player ε-Nash equilibria for any continuous reward function—but not for discontinuous ones. In a second part, we study the problem of a principal who can choose how to distribute a reward budget over the ranks and aims to maximize the performance of the median player. The optimal reward design (contract) is found in closed form, complementing the merely partial results available in the n-player case. We then analyze the quality of the mean field design when used as a proxy for the optimizer in the n-player game. Surprisingly, the quality deteriorates dramatically as n grows. We explain this with an asymptotic singularity in the induced n-player equilibrium distributions. Funding: M. Nutz is supported by an Alfred P. Sloan Fellowship and the Division of Mathematical Sciences of the National Science Foundation [Grants DMS-1812661 and DMS-2106056]. Y. Zhang is supported in part by the Natural Sciences and Engineering Research Council of Canada [NSERC Discovery Grant RGPIN-2020-06290]. 
    more » « less
  3. null (Ed.)
    Considered is a multi-channel wireless network for secret communication that uses the signal-to-interference-plus-noise ratio (SINR) as the performance measure. An eavesdropper can intercept encoded messages through a degraded channel of each legitimate transmitter-receiver communication pair. A friendly interferer, on the other hand, may send cooperative jamming signals to enhance the secrecy performance of the whole network. Besides, the state information of the eavesdropping channel may not be known completely. The transmitters and the friendly interferer have to cooperatively decide on the optimal jamming power allocation strategy that balances the secrecy performance with the cost of employing intentional interference, while the eavesdropper tries to maximize her eavesdropping capacity. To solve this problem, we propose and analyze a non-zero-sum game between the network defender and the eavesdropper who can only attack a limited number of channels. We show that the Nash equilibrium strategies for the players are of threshold type. We present an algorithm to find the equilibrium strategy pair. Numerical examples demonstrate the equilibrium and contrast it to baseline strategies. 
    more » « less
  4. The PoseASL dataset consists of color and depth videos collected from ASL signers at the Linguistic and Assistive Technologies Laboratory under the direction of Matt Huenerfauth, as part of a collaborative research project with researchers at the Rochester Institute of Technology, Boston University, and the University of Pennsylvania. Access: After becoming an authorized user of Databrary, please contact Matt Huenerfauth if you have difficulty accessing this volume. We have collected a new dataset consisting of color and depth videos of fluent American Sign Language signers performing sequences ASL signs and sentences. Given interest among sign-recognition and other computer-vision researchers in red-green-blue-depth (RBGD) video, we release this dataset for use by the research community. In addition to the video files, we share depth data files from a Kinect v2 sensor, as well as additional motion-tracking files produced through post-processing of this data. Organization of the Dataset: The dataset is organized into sub-folders, with codenames such as "P01" or "P16" etc. These codenames refer to specific human signers who were recorded in this dataset. Please note that there was no participant P11 nor P14; those numbers were accidentally skipped during the process of making appointments to collect video stimuli. Task: During the recording session, the participant was met by a member of our research team who was a native ASL signer. No other individuals were present during the data collection session. After signing the informed consent and video release document, participants responded to a demographic questionnaire. Next, the data-collection session consisted of English word stimuli and cartoon videos. The recording session began with showing participants stimuli consisting of slides that displayed English word and photos of items, and participants were asked to produce the sign for each (PDF included in materials subfolder). Next, participants viewed three videos of short animated cartoons, which they were asked to recount in ASL: - Canary Row, Warner Brothers Merrie Melodies 1950 (the 7-minute video divided into seven parts) - Mr. Koumal Flies Like a Bird, Studio Animovaneho Filmu 1969 - Mr. Koumal Battles his Conscience, Studio Animovaneho Filmu 1971 The word list and cartoons were selected as they are identical to the stimuli used in the collection of the Nicaraguan Sign Language video corpora - see: Senghas, A. (1995). Children’s Contribution to the Birth of Nicaraguan Sign Language. Doctoral dissertation, Department of Brain and Cognitive Sciences, MIT. Demographics: All 14 of our participants were fluent ASL signers. As screening, we asked our participants: Did you use ASL at home growing up, or did you attend a school as a very young child where you used ASL? All the participants responded affirmatively to this question. A total of 14 DHH participants were recruited on the Rochester Institute of Technology campus. Participants included 7 men and 7 women, aged 21 to 35 (median = 23.5). All of our participants reported that they began using ASL when they were 5 years old or younger, with 8 reporting ASL use since birth, and 3 others reporting ASL use since age 18 months. Filetypes: *.avi, *_dep.bin: The PoseASL dataset has been captured by using a Kinect 2.0 RGBD camera. The output of this camera system includes multiple channels which include RGB, depth, skeleton joints (25 joints for every video frame), and HD face (1,347 points). The video resolution produced in 1920 x 1080 pixels for the RGB channel and 512 x 424 pixels for the depth channels respectively. Due to limitations in the acceptable filetypes for sharing on Databrary, it was not permitted to share binary *_dep.bin files directly produced by the Kinect v2 camera system on the Databrary platform. If your research requires the original binary *_dep.bin files, then please contact Matt Huenerfauth. *_face.txt, *_HDface.txt, *_skl.txt: To make it easier for future researchers to make use of this dataset, we have also performed some post-processing of the Kinect data. To extract the skeleton coordinates of the RGB videos, we used the Openpose system, which is capable of detecting body, hand, facial, and foot keypoints of multiple people on single images in real time. The output of Openpose includes estimation of 70 keypoints for the face including eyes, eyebrows, nose, mouth and face contour. The software also estimates 21 keypoints for each of the hands (Simon et al, 2017), including 3 keypoints for each finger, as shown in Figure 2. Additionally, there are 25 keypoints estimated for the body pose (and feet) (Cao et al, 2017; Wei et al, 2016). Reporting Bugs or Errors: Please contact Matt Huenerfauth to report any bugs or errors that you identify in the corpus. We appreciate your help in improving the quality of the corpus over time by identifying any errors. Acknowledgement: This material is based upon work supported by the National Science Foundation under award 1749376: "Collaborative Research: Multimethod Investigation of Articulatory and Perceptual Constraints on Natural Language Evolution." 
    more » « less
  5. Shared/buy-in computing systems offer users the option to select between buy-in and shared services. In such systems, idle buy-in resources are made available to other users for sharing. With strategic users, resource purchase and allocation in such systems can be cast as a non-cooperative game, whose corresponding Nash equilibrium does not necessarily result in the optimal social cost. In this study, we first derive the optimal social cost of the game in closed form, by casting it as a convex optimization problem and establishing related properties. Next, we derive a closed-form expression for the social cost at the Nash equilibrium, and show that it can be computed in linear time. We further show that the strategy profiles of users at the optimum and the Nash equilibrium are directly proportional. We measure the inefficiency of the Nash equilibrium through the price of anarchy, and show that it can be quite large in certain cases, e.g., when the operating expense ratio is low or when the distribution of user workloads is relatively homogeneous. To improve the efficiency of the system, we propose and analyze two subsidy policies, which are shown to converge using best-response dynamics. 
    more » « less