This paper explores differentially-private federated learning (FL) across time-varying databases, delving into a nuanced three-way tradeoff involving age, accuracy, and differential privacy (DP). Emphasizing the potential advantages of scheduling, we propose an optimization problem aimed at meeting DP requirements while minimizing the loss difference between the aggregated model and the model obtained without DP constraints. To harness the benefits of scheduling, we in-troduce an age-dependent upper bound on the loss, leading to the development of an age-aware scheduling design. Simulation results underscore the superior performance of our proposed scheme compared to FL with classic DP, which does not consider scheduling as a design factor. This research contributes insights into the interplay of age, accuracy, and DP in FL, with practical implications for scheduling strategies.

Age of information (AoI) is an effective performance metric measuring the freshness of information and is particularly suitable for applications involving status update. In this paper, using the age violation probability as the metric, scheduling for heterogeneous multi-source systems is studied. Two queueing disciplines, namely the infinite packet queueing discipline and the single packet queueing discipline, are considered for scheduling packets within each source. A generalized round-robin (GRR) scheduling policy is then proposed to schedule the sources. Bounds on the exponential decay rate of the age violation probability for the proposed GRR scheduling policy under each queueing discipline are rigorously analyzed. Simulation results are provided, which show that the proposed GRR scheduling policy can efficiently serve many sources with heterogeneous arrivals and that our bounds can capture the true decay rate quite accurately. When specialized to the homogeneous source setting, the analysis concretizes the common belief that the single packet queueing discipline has a better AoI performance than the infinite packet queueing discipline. Moreover, simulations on this special case reveals that under the proposed scheduling policy, the two disciplines would have similar asymptotic performance when the inter-arrival time is much larger than the total transmission time.

The index coding problem includes a server, a group of clients, and a set of data chunks. While each client wants a subset of the data chunks and already has another subset as its side information, the server transmits some (uncoded or coded) chunks to the clients over a noiseless broadcast channel. The objective of the problem is to satisfy the demands of all clients with the minimum number of transmissions. This paper investigates the index coding setting from a game-theoretical perspective. We consider selfish clients, where each selfish client has private side information and a private valuation of each data chunk it wants. In this context, our objectives are following: 1) to motivate each selfish client to reveal the correct side information and true valuation of each data chunk it wants; 2) to maximize the social welfare, i.e., the total valuation of the data chunks recovered by the clients minus the total cost incurred by the transmissions from the server. Our main contribution is to jointly develop coding and incentive schemes for achieving the first objective perfectly and achieving the second objective optimally or approximately with guaranteed approximation ratios (potentially within some restricted sets of coding matrices).

In this paper, the problem of using uncoordinated multiple access (UMA) to serve a massive amount of heterogeneous users is investigated. Leveraging the heterogeneity, we propose a novel UMA protocol, called iterative collision resolution for slotted ALOHA (IRSA) with non-orthogonal multiple access (NOMA), to improve the conventional IRSA. In addition to the inter-slot successive interference cancellation (SIC) technique used in existing IRSA-based schemes, the proposed protocol further employs the intra-slot SIC technique that enables collision resolution for certain configurations of collided packets. A novel multi-dimensional density evolution is then proposed to analyze and to optimize the proposed protocol. Simulation results show that the proposed IRSA with NOMA protocol can efficiently exploit the heterogeneity among users and the multi-dimensional density evolution can accurately predict the throughput performance. Last, an extension of the proposed IRSA with NOMA protocol to the frame-asynchronous setting is investigated, where a boundary effect similar to that in spatially-coupled low-density parity check codes can be observed to bootstrap the decoding process.

We consider a distributed computing network consisting of a master and multiple workers processing tasks of different types. The master is running multiple applications. Each application stochastically generates real-time jobs with a strict job deadline, where each job is a collection of tasks of some types specified by the application. A real-time job is completed only when all its tasks are completed by the corresponding workers within the deadline. Moreover, we consider unreliable workers, whose processing speeds are uncertain. Because of the limited processing abilities of the workers, an algorithm for scheduling the jobs in the workers is needed to maximize the average number of completed jobs for each application. The scheduling problem is not only critical but also practical in distributed computing networks. In this paper, we develop two scheduling algorithms, namely, a feasibility-optimal scheduling algorithm and an approximate scheduling algorithm. The feasibility-optimal scheduling algorithm can fulfill the largest region of applications' requirements for the average number of completed jobs. However, the feasibility-optimal scheduling algorithm suffers from high computational complexity when the number of applications is large. To address the issue, the approximate scheduling algorithm is proposed with a guaranteed approximation ratio in the worst-case scenario. The approximate scheduling algorithm is also validated in the average-case scenario via computer simulations.

We analyze a wireless line network employing wireless network coding. The two end nodes exchange their packets through relays. While a packet at a relay might not find its coding pair upon arrival, a transmission cost can be reduced by waiting for coding with a packet from the other side. To strike a balance between the reduced transmission cost and the cost incurred by the delay, a scheduling algorithm determining either to transmit an uncoded packet or to wait for coding is needed. Because of highly uncertain traffic injections, scheduling with no assumption of the traffic is critical. This paper proposes a randomized online scheduling algorithm for a relay in arbitrary traffic, which can be non-stationary or adversarial. The expected total cost (including a transmission cost and a delay cost) incurred by the proposed algorithm is at most $\frac {e}{e-1} \approx 1.58$ times the minimum achievable total cost. In particular, the proposed algorithm is universal in the sense that the ratio is independent of the traffic. With the universality, the proposed algorithm can be implemented at each relay distributedly (in a multi-relay network) with the same ratio. Moreover, the proposed algorithm turns out to generalize the classic ski-rental online algorithm.

Age of information is a new network performance metric that captures the freshness of information at end-users. This paper studies the age of information from a scheduling perspective. To that end, we consider a wireless broadcast network where a base-station (BS) is updating many users on random information arrivals under a transmission capacity constraint. For the offline case when the arrival statistics are known to the BS, we develop a structural MDP scheduling algorithm and an index scheduling algorithm, leveraging Markov decision process (MDP) techniques and the Whittle's methodology for restless bandits. By exploring optimal structural results, we not only reduce the computational complexity of the MDP-based algorithm, but also simplify deriving a closed form of the Whittle index. Moreover, for the online case, we develop an MDP-based online scheduling algorithm and an index-based online scheduling algorithm. Both the structural MDP scheduling algorithm and the MDP-based online scheduling algorithm asymptotically minimize the average age, while the index scheduling algorithm minimizes the average age when the information arrival rates for all users are the same. Finally, the algorithms are validated via extensive numerical studies.

We consider a mobile network where a mobile device is running an application that requires timely information. The information at the device can be updated by downloading the latest information through neighboring access points. The freshness of the information at the device is characterized by the recently proposed age of information. However, minimizing the age of information by frequent downloading increases power consumption of the device. In this context, an energy-efficient scheduling algorithm for timely information downloads is critical, especially for power-limited mobile devices. Moreover, unpredictable movement of the mobile device causes uncertainty of the channel dynamics, which is even non-stationary within a finite amount of time for running the application. Thus, in this paper we devise a randomized online scheduling algorithm for mobile devices, which can move arbitrarily and run the application for any amount of time. We show that the expected total cost incurred by the proposed algorithm, including an age cost and a downloading cost, is (asymptotically) at most e/(e - 1) ≈ 1.58 times the minimum total cost achieved by an optimal offline scheduling algorithm.

Age of information is a new concept that characterizes the freshness of information at end devices. This paper studies the age of information from a scheduling perspective. We consider a wireless broadcast network where a base-station updates many users on stochastic information arrivals. Suppose that only one user can be updated for each time. In this context, we aim at developing a transmission scheduling algorithm for minimizing the long-run average age. To develop a low-complexity transmission scheduling algorithm, we apply the Whittle's framework for restless bandits. We successfully derive the Whittle index in a closed form and establish the indexability. Based on the Whittle index, we propose a scheduling algorithm, while experimentally showing that it closely approximates an age-optimal scheduling algorithm.

Delay performance of downlink non-orthogonal multiple access (NOMA) networks is investigated. To fully realize advantages offered by NOMA, we need to consider more realistic network environment; as such, departing from the literature on NOMA, this paper relaxes the full-buffer assumption and allows each user in the network to have its individual delay-cost function. The former captures the sporadic nature of data arrivals in some applications, while the latter accepts potential coexistence of heterogeneous users. In this context, we propose three transmission scheduling algorithms, namely the MDP-based, the c- μ-based, and the learning-based scheduling algorithms. While the MDP-based scheduling algorithm is shown to be delay-optimal, the other two scheduling algorithms enjoy the online feature where transmitters are oblivious to arrival statistics. Moreover, it turns out that the c-μ-based scheduling algorithm is a greedy version of the MDP-based scheduling algorithm and the learning-based scheduling algorithm is asymptotically delay-optimal. Simulation results corroborate our theoretical analysis and fortify the common belief about the superiority of NOMA over OMA, even without the full-buffer assumption and with heterogeneous users.

Age of information is a newly proposed metric that captures delay from an application layer perspective. The age measures the amount of time that elapsed from the moment the mostly recently received update was generated until the present time. In this paper, we study an age minimization problem over a wireless broadcast network with many users, where only one user can be served at a time. We formulate a Markov decision process (MDP) to find dynamic transmission scheduling schemes, with the purpose of minimizing the long-run average age. While showing that an optimal scheduling algorithm for the MDP is a simple stationary switch-type, we propose a sequence of finite-state approximations for our infinite-state MDP and prove its convergence. We then propose both optimal off-line and online scheduling algorithms for the finite-approximate MDPs, depending on knowledge of time-varying arrivals.

We consider a group of neighboring smartphone users who are roughly at the same time interested in the same network content, while the users can share content enabled by broadcast device-to-device communications. As the users are selfish in practice, an incentive mechanism is needed to motivate the physically neighboring users to form a social group. We propose a novel concept of equal-reciprocal incentive over broadcast networks, which fairly ensures that each pair of users in the social group share the same amount of content with each other. As the equal-reciprocal incentive may restrict the amount of the shared content, we analyze the optimal equal-reciprocal scheme that maximizes the shared content. While ensuring fairness among users, we show that this optimized scheme also maximizes each user's utility. Finally, we look at dynamic content arrivals and extend our incentive scheme successfully by proposing optimal online scheduling algorithms that achieve the equal-reciprocal incentive.

It has been well established that wireless network coding can significantly improve the efficiency of multihop wireless networks. However, in a stochastic environment, some of the packets might not have coding pairs, which limits the number of available coding opportunities. In this context, an important decision is whether to delay packet transmission in hope that a coding pair will be available in the future or transmit a packet without coding. This paper addresses this problem by establishing a stochastic dynamic framework whose objective is to minimize a long-run average cost. We identify an optimal control policy that minimizes the costs due to a combination of transmissions and packet delays. We show that the optimal policy would be stationary, deterministic, and threshold-type based on queue lengths. Our analytical approach is applicable for many cases of interest such as time-varying on/off channels. We further substantiate our results with simulation experiments for more generalized settings.

The Index Coding problem has recently attracted a significant interest from the research community. In this problem, a server needs to deliver a set of packets to a group of wireless clients over a noiseless broadcast channel. Each client requests a subset of packets and has another subset given to it as side information. The objective is to satisfy the demands of all clients with the minimum number of transmissions. In this paper, we study the Index Coding problem from the game-theoretic perspective. We assume that each client is selfish and has a hidden private value for each packet it requests. The objective of the server is to maximize the value of social welfare that captures the trade-off between values of the transmitted packets and the transmission cost incurred by the server. The transmission process is decided through an auction in which the clients are required to submit bids to the server. Our goal is to design a truthful auction scheme that provides an incentive for each client to bid the true value of the packets and maximizes the value of the social welfare. The key challenge in this context is to determine the encoding functions of the transmitted packets. Since finding an optimal encoding function is an NP-hard problem, we propose efficient algorithms that identify the encoding functions as well as a payment scheme that provide an approximate solution and guarantee truthfulness.

Abstract Techniques for improving network congestion have been proposed in different fields. In recent years, the congestion control problems were studied to enhance the routing performance in wireless multihop networks (WMNs). In this paper, the network allocation vector (NAV) introduced by the contention‐based medium access control (MAC) protocols is utilized for the determination of the channel status around a wireless node (WN). A MAC‐assisted congestion‐controlled routing (MCR) algorithm is proposed to alleviate the network congestion problem by adopting the information from the MAC layer. The routing path is selected based on the congestion‐free probability along the path for transmitting the data packets. Moreover, the adaptive path‐switching scheme and the aggressive hop‐reduction (AHR) local repair mechanism further enhance the routing performance of the proposed MCR algorithm. The effectiveness of the MCR protocol is evaluatedviaboth the analytical study and the simulation results. Without consuming excessive control packets for each WN, the MCR algorithm can achieve better performance when compared with other existing schemes, especially under the scenarios with network congestion. Copyright © 2010 John Wiley & Sons, Ltd.

It has been well established that reverse-carpooling based network coding can significantly improve the efficiency of multi-hop wireless networks. However, in a stochastic environment when there are no opportunities to code because of packets without coding pairs, should these packets wait for a future opportunity or should they be transmitted without coding? To help answer that question we formulate a stochastic dynamic program with the objective of minimizing the long-run average cost per unit time incurred due to transmissions and delays. In particular, we develop optimal control actions that would balance between costs of transmission against those of delays. In that process we seek to address a crucial question: what should be observed as the state of the system? We analytically show that just the queue lengths is enough if it can be modeled as a Markov process. Subsequently we show that a stationary policy based on queue lengths is optimal and describe a procedure to find such a policy. We further substantiate our results with simulation experiments for more generalized settings.

In recent years, channel-hopping based medium access control (MAC) protocols are proposed to improve the capacity in a decentralized multi-channel cognitive radio (CR) networks without extra usage of a control channel. Each CR user has to stochastically follow a default channel-hopping sequence in order to sense a channel and to conduct its frame transmission. In this paper, based on the channel-hopping protocol, an analysis is conducted on both the probability of channel availability and the average frame delay for the primary queueing networks. The analytical model is proposed by considering the impact caused by imperfect sensing of the CR users and the imperfect synchronization between the primary and CR networks. According to the proposed model with more realistic considerations, an optimal channel-hopping sequence (OCS) approach is designed for the CR users based on dynamic programming technique. It is designed by exploiting the optimal load balance between both the channel availability and channel utilization within the delay constraints of primary users (PUs). By adopting the OCS approach, the maximum aggregate throughput of CR users and the quality of service (QoS) requirement of PUs can both be achieved. Numerical results illustrate that the proposed OCS scheme can effectively maximize the aggregate throughput compared to conventional channel-hopping sequences, and as well guarantee the QoS requirement of the PUs.

Recent studies have been conducted to indicate the ineffective usage of licensed bands due to the static spectrum allocation. In order to improve the spectrum utilization, the cognitive radio is therefore suggested to dynamically exploit the opportunistic primary frequency spectrums. The interference from the secondary users to the primary user consequently draws the attention to the spectrum and power management for the cognitive radio networks. In this paper, the constrained stochastic games are utilized to exploit the optimal policies for power management by considering the variations from both the channel gain and the primary traffic. Both the underlay and overlay waveforms are considered within the network scenarios for the proposed power management scheme. Constraints for allowable interferences will be applied in order to preserve the communication quality among the primary and the secondary users. According to the formulation of the constrained stochastic games, the existence of the constrained Nash equilibrium will be validated with rigorous proofs, which will be acquired as the optimal policies for the power management problem. Simulation results further validate the correctness of the theoretically-derived policies for dynamic power management.

Recent studies have been conducted to indicate the ineffective usage of licensed bands due to the static spectrum allocation. In order to improve the spectrum utilization, the cognitive radio (CR) is therefore suggested to dynamically exploit the opportunistic primary frequency spectrums. How to provide efficient spectrum handoff has been considered a crucial issue in the CR networks. Existing spectrum handoff algorithms assume that all the channels within the network can be correctly sensed by the CR users in order to perform appropriate spectrum hand-off process. However, this assumption is considered impracticable in realistic circumstances primarily due to the excessive time required for the CR user to sense the entire spectrum space. In this paper, the partially observable Markov decision process (POMDP) is exploited to estimate the network information by partially sensing the frequency spectrums. A POMDP-based spectrum handoff (POSH) scheme is proposed to determine the optimal target channel for spectrum handoff according to the partially observable channel state information. By adopting the policy resulted from the POSH algorithm for target channel selection, minimal waiting time at each occurrence of spectrum handoff can be achieved. Numerical results illustrate that the proposed POSH scheme can effectively minimize the required waiting time for spectrum handoff in the CR networks.

In recent years, cooperative communication has been proposed as a new communication paradigm that incorporates a relay node to assist the direct point-to-point transmission. By exploiting the cooperative diversity, different types of techniques have been proposed to improve the transmission reliability from the physical layer perspective, e.g. the cooperative automatic repeat request. However, owing to the longer transmission time resulting from the cooperative schemes, there is no guarantee to enhance the network throughput in view of the medium access control (MAC) performance. In this paper, the system throughput of the cooperative communication is evaluated by exploiting the proposed analytical model based on the IEEE 802.11 MAC protocol. Both the relay-based and the original direct communications are considered in the analytical studies. Simulations are conducted to further validate the effectiveness of the proposed model. In terms of the network throughput, whether to adopt the cooperative schemes depends on the tradeoff between the cooperative transmission delay and the channel condition of the direct communication.

Different types of power-saving techniques have been proposed in various fields to alleviate the limitation on the battery lifetime for the mobile stations (MSs). In order to provide feasible energy-conserving mechanism, three different power-saving types have been introduced in the IEEE 802.16e broadband wireless networks. By means of pre-negotiations, the MS can be absent from the serving base station (BS) by performing the sleep mode operation. For each involved MS, connections with similar properties can be group into the defined power-saving classes. In this paper, a comprehensive performance modeling of the IEEE 802.16e power-saving classes of Type I and II are proposed. Multiple connections between the BS and the MS with both the downlink and the uplink traffic are considered in the analytical models. The power-saving efficiency and the mean waiting time are utilized as the metrics for performance analysis. Simulations are performed in order to validate the results obtained from the analytical models.

The limitation on the battery lifetime has been a critical issue for the advancement of mobile computing. Different types of power-saving techniques have been proposed in various fields. In order to provide feasible energy-conserving mechanism for the mobile subscriber stations (MSSs), three power-saving types have been proposed for the IEEE 802.16e broadband wireless networks. However, these power-saving types are primarily targeting for the cases with a single connection between the base station (BS) and the MSS. With the existence of multiple connections, the power efficiency obtained by adopting the conventional scheduling algorithm can be severely degraded. In this paper, a maximal power-conserving (MPC) scheduling algorithm is proposed to consider the aggregated effect from the multiple connections to the power efficiency. Moreover, the quality-of-service (QoS) constraints from both the downlink and the uplink traffic are employed in the design of the MPC algorithm in order to facilitate the corresponding MSS to fulfill its QoS requirements in both directions. Numerical results show that the proposed MPC scheduling algorithm outperforms the conventional 802.16e power-saving mechanism, especially under the multi-connection scenarios.