The Scheduling Problem in Wireless Networks

Pantelidou, Anna,Ephremides, Anthony The Korea Institute of Information and Commucation 2009 Journal of communications and networks Vol.11 No.5

We describe the fundamental issue of scheduling the allocation of wireless network resources and provide several formulations of the associated problems. The emphasis is on scheduling transmission attempts. We place this problem in the context of existing approaches, like information theoretic and traditional network theoretic ones, as well as novel avenues that open up the possibility of addressing this issue for non-stationary and non-ergodic environments. We summarize concrete recent results for specific special cases that include unicast and multicast traffic, different objective functions, and reduced complexity versions of the problem. We conclude with some thoughts for future work. We identify and single out the cross-layer nature of the problem and include a simple physical-layer criterion in what is mostly a medium access control (MAC) problem.

Optimal Packet Scheduling for Energy Harvesting Sources on Time Varying Wireless Channels

Kashef, Mohamed,Ephremides, Anthony The Korea Institute of Information and Commucation 2012 Journal of communications and networks Vol.14 No.2

In this paper, we consider a source node that operates over a time varying channel with energy harvesting capability. The goal of the source is to maximize the average number of successfully delivered packets per time slot. The source is able to choose whether to transmit a packet or defer the transmission in each time slot. The decision which is chosen by the source depends on the channel information available and the length of the energy queue. We formulate the problem of finding the optimal policy as a Markovian decision problem. We show some properties of the value function that represents the discounted number of successfully delivered packets per time slot. We prove that the optimal policy is a threshold type policy depending on the state of the channel and the length of the energy queue. We also derive an upper bound for the average number of packets per time slots successfully received by the destination. We show using numerical results that this bound is a tight bound on the performance of the optimal policy. And we consider the case of time varying channel but without channel state information (CSI). Then, we study the impact of channel time varying nature and the availability of CSI. In this case, we show that the optimal policy is a greedy policy. The performance of this greedy policy is also calculated.

Neighbor Discovery in a Wireless Sensor Network: Multipacket Reception Capability and Physical-Layer Signal Processing

Jeon, Jeongho,Ephremides, Anthony The Korea Institute of Information and Commucation 2012 Journal of communications and networks Vol.14 No.5

In randomly deployed networks, such as sensor networks, an important problem for each node is to discover its neighbor nodes so that the connectivity amongst nodes can be established. In this paper, we consider this problem by incorporating the physical layer parameters in contrast to the most of the previous work which assumed a collision channel. Specifically, the pilot signals that nodes transmit are successfully decoded if the strength of the received signal relative to the interference is sufficiently high. Thus, each node must extract signal parameter information from the superposition of an unknown number of received signals. This problem falls naturally in the purview of random set theory (RST) which generalizes standard probability theory by assigning sets, rather than values, to random outcomes. The contributions in the paper are twofold: First, we introduce the realistic effect of physical layer considerations in the evaluation of the performance of logical discovery algorithms; such an introduction is necessary for the accurate assessment of how an algorithm performs. Secondly, given the double uncertainty of the environment (that is, the lack of knowledge of the number of neighbors along with the lack of knowledge of the individual signal parameters), we adopt the viewpoint of RST and demonstrate its advantage relative to classical matched filter detection method.

Power Control in Uplink and Downlink CDMA Systems with Multiple Flow Types

Li Yun,Ephremides Anthony The Korea Institute of Information and Commucation 2006 Journal of communications and networks Vol.8 No.3

We consider a power controlled code division multiple access (CDMA) system with multiple flow types. At each of the N nodes, there are F flow types with different signal-to-interference-and-noise-ratio (SINR) requirements. To keep the complexity of the transmitter low, we assume that each node uses the same power level for all its flows. The single flow case has been fully solved and is well-understood. We concentrate on the multiple flow case, and use a novel and different approach. For the uplink problem with N = 2 and F arbitrary, the necessary and sufficient conditions to have a solution are found and proved. For the general N > 1 uplink problem, we provide a necessary condition for the problem to have a solution and an iterative algorithm to find the optimum solution. For the downlink case with F > 1 some properties of the optimal sequences are obtained.

The Scheduling Problem in Wireless Networks

Anna Pantelidou,Anthony Ephremides 한국통신학회 2009 Journal of communications and networks Vol.11 No.5

We describe the fundamental issue of scheduling the allocation of wireless network resources and provide several formulations of the associated problems. The emphasis is on scheduling transmission attempts. We place this problem in the context of existing approaches, like information theoretic and traditional network theoretic ones, as well as novel avenues that open up the possibility of addressing this issue for non-stationary and non-ergodic environments. We summarize concrete recent results for specific special cases that include unicast and multicast traffic, different objective functions, and reduced complexity versions of the problem. We conclude with some thoughts for future work. We identify and single out the cross-layer nature of the problem and include a simple physical-layer criterion in what is mostly a medium access control (MAC) problem.

Age of Information Games Between Power Constrained Schedulers and Adversaries

Banerjee, Subhankar,Ulukus, Sennur,Ephremides, Anthony 한국통신학회 2023 Journal of communications and networks Vol.25 No.5

We consider a time slotted communication network consisting of a base station (BS), an adversary, $N$ users and $N_{s}$ communication channels. In the first part of the paper, we consider the setting where $N_{s}$ communication channels $\mathcal{N}_{s}$ are heterogeneously divided among $N$ users. The BS transmits an update to the $i$th user on a subset of the communication channels $\mathcal{N}_{s,i}$ where $\mathcal{N}_{s,i}\cap \mathcal{N}_{s,j}$ is not necessarily an empty set. At each time slot, the BS transmits an update packet to a user through a communication channel and the adversary aims to block the update packet sent by the BS by blocking a communication channel. The BS has $n$ discrete transmission power levels to communicate with the users and the adversary has $m$ discrete blocking power levels to block the communication channels. The probability of successful transmission of an update packet depends on these power levels. The BS and the adversary have a transmission and blocking average power constraint, respectively. We provide a universal lower bound for the average age of information for this communication network. We prove that the uniform user choosing policy, the uniform communication channel choosing policy with any arbitrary feasible transmission power choosing policy is $4$ optimal; and the max-age user choosing policy, the uniform communication channel choosing policy with any arbitrary feasible transmission power choosing policy is $2$ optimal. In the second part of the paper, we consider the setting where the BS chooses a transmission policy and the adversary chooses a blocking policy from the set of randomized stationary policies and $\mathcal{N}_{s,i}=\mathcal{N}_{s}$ for all $i$, i.e., all users can receive updates on all channels. We show that a Nash equilibrium may or may not exist for this communication network, and identify special cases where a Nash equilibrium always exists.

Neighbor Discovery in aWireless Sensor Network: Multipacket Reception Capability and Physical-Layer Signal Processing

Jeongho Jeon,Anthony Ephremides 한국통신학회 2012 Journal of communications and networks Vol.14 No.5

In randomly deployed networks, such as sensor networks,an important problemfor each node is to discover its neighbor nodes so that the connectivity amongst nodes can be established. In this paper, we consider this problem by incorporating the physical layer parameters in contrast to the most of the previous work which assumed a collision channel. Specifically, the pilot signals that nodes transmit are successfully decoded if the strength of the received signal relative to the interference is sufficiently high. Thus, each node must extract signal parameter information from the superposition of an unknown number of received signals. This problem falls naturally in the purview of random set theory (RST)which generalizes standard probability theory by assigning sets,rather than values, to random outcomes. The contributions in the paper are twofold: First, we introduce the realistic effect of physical layer considerations in the evaluation of the performance of logical discovery algorithms; such an introduction is necessary for the accurate assessment of how an algorithm performs. Secondly,given the double uncertainty of the environment (that is, the lack of knowledge of the number of neighbors along with the lack of knowledge of the individual signal parameters), we adopt the viewpoint of RST and demonstrate its advantage relative to classical matched filter detection method.

Optimal Packet Scheduling for Energy Harvesting Sources on Time Varying Wireless Channels

Mohamed Kashef,Anthony Ephremides 한국통신학회 2012 Journal of communications and networks Vol.14 No.2

In this paper, we consider a source node that operates over a time varying channel with energy harvesting capability. The goal of the source is to maximize the average number of successfully delivered packets per time slot. The source is able to choose whether to transmit a packet or defer the transmission in each time slot. The decision which is chosen by the source depends on the channel information available and the length of the energy queue.We formulate the problem of finding the optimal policy as a Markovian decision problem.We show some properties of the value function that represents the discounted number of successfully delivered packets per time slot. We prove that the optimal policy is a threshold type policy depending on the state of the channel and the length of the energy queue.We also derive an upper bound for the average number of packets per time slots successfully received by the destination. We show using numerical results that this bound is a tight bound on the performance of the optimal policy. And we consider the case of time varying channel but without channel state information (CSI). Then, we study the impact of channel time varying nature and the availability of CSI. In this case, we show that the optimal policy is a greedy policy. The performance of this greedy policy is also calculated.

Information Freshness and Packet Drop Rate Interplay in a Two-User Multi-Access Channel

Emmanouil Fountoulakis,Themistoklis Charalambous,Nikolaos Nomikos,Anthony Ephremides,Nikolaos Pappas 한국통신학회 2022 Journal of communications and networks Vol.24 No.3

In this work, we combine the two notions of timelydelivery of information to study their interplay; namely, deadlineconstrainedpacket delivery due to latency constraints andfreshness of information. More specifically, we consider a twousermultiple access setup with random access, in which user 1is a wireless device with a buffer and has external bursty trafficwhich is deadline-constrained, while user 2 monitors a sensorand transmits status updates to the destination. We provideanalytical expressions for the throughput and drop probabilityof user 1. For user 2, we derive in closed form the age ofinformation distribution, the average age of information (AoI),and the probability the AoI to be larger than a certain valuefor each time slot. The relations reveal a trade-off between theaverage AoI of user 2 and the drop rate of user 1: the lower theaverage AoI, the higher the drop rate, and vice versa. Simulationscorroborate the validity of our theoretical results.

Bandwidth Partition and Allocation for Efficient Spectrum Utilization in Cognitive Communications

Song Huang,Di Yuan,Anthony Ephremides 한국통신학회 2019 Journal of communications and networks Vol.21 No.4

Conventional cognitive communications rely heavily onthe smartness of secondary (unlicensed) users (SUs) to achieve highspectrum utilization, which involves the optimization of the SUs’policies and behaviors for dynamic spectrum access, power allocationamong multiple channels, etc. Due to the inherent randomnessof the primary users’ (PUs’) transmission, those efforts inevitablyincrease the implementation complexity and sensing overheads ofthe SUs, and in turn lower the spectrum utilization efficiency. Inthis paper, we try to change the focus from SU to PU. A cooperativetraffic allocation strategy for PU, together with the non-uniformbandwidth partition, is employed to regularize the PU’s resourceoccupancy pattern without compromising its performance, and tomaximize the spare bandwidth for the SU at the same time. Wefirst study the capacity based optimization problem (COP) togetherwith the fully polynomial time approximation scheme (FPTAS) foran approximation guarantee of the global optimum. Then we analyzethe subcarrier based optimization problem as the surrogateproblem of COP, which can be solved by a greedy algorithm exactly. Both the theoretical analysis and the numerical simulationsdemonstrate the effectiveness of those methods to achieve the performancethat almost identical to that of the global optimum solution.