We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of N non-colluding databases, each storing an MDS-coded version of M ...messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is C = (1 + K/N + K2/N2 + ⋯ + KM-1/NM-1)-1 = (1 + Rc + Rc2 + ⋯ + RcM-1)-1 = (1 - Rc)/(1 - RcM), where Rc is the rate of the (N, K) MDS code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost when the storage code is restricted to the class of MDS codes. The result generalizes the achievability and converse results for the classical PIR with replicated databases to the case of MDS-coded databases.
We consider the problem of single-round private information retrieval (PIR) from <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula> replicated databases. We consider the case ...when <inline-formula> <tex-math notation="LaTeX">B </tex-math></inline-formula> databases are outdated (unsynchronized), or even worse, adversarial (Byzantine), and therefore, can return incorrect answers. In the PIR problem with Byzantine databases (BPIR), a user wishes to retrieve a specific message from a set of <inline-formula> <tex-math notation="LaTeX">M </tex-math></inline-formula> messages with zero-error, irrespective of the actions performed by the Byzantine databases. We consider the <inline-formula> <tex-math notation="LaTeX">T </tex-math></inline-formula>-privacy constraint in this paper, where any <inline-formula> <tex-math notation="LaTeX">T </tex-math></inline-formula> databases can collude, and exchange the queries submitted by the user. We derive the information-theoretic capacity of this problem, which is the maximum number of correct symbols that can be retrieved privately (under the <inline-formula> <tex-math notation="LaTeX">T </tex-math></inline-formula>-privacy constraint) for every symbol of the downloaded data. We determine the exact BPIR capacity to be <inline-formula> <tex-math notation="LaTeX">C=(N-2B)/N \cdot (1-T/(N-2B))/(1-(T/(N-2B))^{M}) </tex-math></inline-formula>, if <inline-formula> <tex-math notation="LaTeX">2B+T < N </tex-math></inline-formula>. This capacity expression shows that the effect of Byzantine databases on the retrieval rate is equivalent to removing <inline-formula> <tex-math notation="LaTeX">2B </tex-math></inline-formula> databases from the system, with a penalty factor of <inline-formula> <tex-math notation="LaTeX">(N-2B)/N </tex-math></inline-formula>, which signifies that even though the number of databases needed for PIR is effectively <inline-formula> <tex-math notation="LaTeX">N-2B </tex-math></inline-formula>, the user still needs to access the entire <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula> databases. The result shows that for the unsynchronized PIR problem, if the user does not have any knowledge about the fraction of the messages that are mis-synchronized, the single-round capacity is the same as the BPIR capacity. Our achievable scheme extends the optimal achievable scheme for the robust PIR (RPIR) problem to correct the errors introduced by the Byzantine databases as opposed to erasures in the RPIR problem. Our converse proof uses the idea of the cut-set bound in the network coding problem against adversarial nodes.
We consider the optimal packet scheduling problem in a single-user energy harvesting wireless communication system. In this system, both the data packets and the harvested energy are modeled to ...arrive at the source node randomly. Our goal is to adaptively change the transmission rate according to the traffic load and available energy, such that the time by which all packets are delivered is minimized. Under a deterministic system setting, we assume that the energy harvesting times and harvested energy amounts are known before the transmission starts. For the data traffic arrivals, we consider two different scenarios. In the first scenario, we assume that all bits have arrived and are ready at the transmitter before the transmission starts. In the second scenario, we consider the case where packets arrive during the transmissions, with known arrival times and sizes. We develop optimal off-line scheduling policies which minimize the time by which all packets are delivered to the destination, under causality constraints on both data and energy arrivals.
Physical-layer security utilizes resources of the transmission medium to guarantee secure communication against an adversary with unlimited computational power. Rooted in information theory, ...physical-layer security advocates for a foundational approach by requiring security of communicated information as well as its reliability at the outset. The past decade has seen an unprecedented effort in physical-layer security research resulting in promising new design insights. The majority of these advances has been in wireless communications security, well-motivated by the fact that most data at large, including those of sensitive nature, flow over wireless links that are more vulnerable to security breaches, e.g., eavesdropping. At the same time, the open broadcast nature of wireless brings possibilities of cooperation by the network entities for improving security, e.g., resistance to eavesdropping. This article aims to provide an overview of research results in information-theoretic security with multiple wireless transmitters, and focuses on distilling insights for designing wireless systems with confidentiality guarantees.
In energy harvesting communication systems, an exogenous recharge process supplies energy necessary for data transmission and the arriving energy can be buffered in a battery before consumption. We ...determine the information-theoretic capacity of the classical additive white Gaussian noise (AWGN) channel with an energy harvesting transmitter with an unlimited sized battery. As the energy arrives randomly and can be saved in the battery, codewords must obey cumulative stochastic energy constraints. We show that the capacity of the AWGN channel with such stochastic channel input constraints is equal to the capacity with an average power constraint equal to the average recharge rate. We provide two capacity achieving schemes: save-and-transmit and best-effort-transmit. In the save-and-transmit scheme, the transmitter collects energy in a saving phase of proper duration that guarantees that there will be no energy shortages during the transmission of code symbols. In the best-effort-transmit scheme, the transmission starts right away without an initial saving period, and the transmitter sends a code symbol if there is sufficient energy in the battery, and a zero symbol otherwise. Finally, we consider a system in which the average recharge rate is time varying in a larger time scale and derive the optimal offline power policy that maximizes the average throughput, by using majorization theory.
Age of Information: An Introduction and Survey Yates, Roy D.; Sun, Yin; Brown, D. Richard ...
IEEE journal on selected areas in communications,
05/2021, Letnik:
39, Številka:
5
Journal Article
Recenzirano
Odprti dostop
We summarize recent contributions in the broad area of age of information (AoI). In particular, we describe the current state of the art in the design and optimization of low-latency cyberphysical ...systems and applications in which sources send time-stamped status updates to interested recipients. These applications desire status updates at the recipients to be as timely as possible; however, this is typically constrained by limited system resources. We describe AoI timeliness metrics and present general methods of AoI evaluation analysis that are applicable to a wide variety of sources and systems. Starting from elementary single-server queues, we apply these AoI methods to a range of increasingly complex systems, including energy harvesting sensors transmitting over noisy channels, parallel server systems, queueing networks, and various single-hop and multi-hop wireless networks. We also explore how update age is related to MMSE methods of sampling, estimation and control of stochastic processes. The paper concludes with a review of efforts to employ age optimization in cyberphysical applications.
In energy harvesting communications, users transmit messages using energy harvested from nature during the course of communication. With an optimum transmit policy, the performance of the system ...depends only on the energy arrival profiles. In this paper, we introduce the concept of energy cooperation, where a user wirelessly transmits a portion of its energy to another energy harvesting user. This enables shaping and optimization of the energy arrivals at the energy-receiving node, and improves the overall system performance, despite the loss incurred in energy transfer. We consider several basic multi-user network structures with energy harvesting and wireless energy transfer capabilities: relay channel, two-way channel and multiple access channel. We determine energy management policies that maximize the system throughput within a given duration using a Lagrangian formulation and the resulting KKT optimality conditions. We develop a two-dimensional directional water-filling algorithm which optimally controls the flow of harvested energy in two dimensions: in time (from past to future) and among users (from energy-transferring to energy-receiving) and show that a generalized version of this algorithm achieves the boundary of the capacity region of the two-way channel.
In this paper, we investigate the optimal packet scheduling problem in a two-user multiple access communication system, where the transmitters are able to harvest energy from the nature. Under a ...deterministic system setting, we assume that the energy harvesting times and harvested energy amounts are known before the transmission starts. For the packet arrivals, we assume that packets have already arrived and are ready to be transmitted at the transmitter before the transmission starts. Our goal is to minimize the time by which all packets from both users are delivered to the destination through controlling the transmission powers and transmission rates of both users. We first develop a generalized iterative backward waterfilling algorithm to characterize the maximum departure region of the transmitters for any given deadline T. Then, based on the sequence of maximum departure regions at energy arrival instants, we decompose the transmission completion time minimization problem into convex optimization problems and solve the overall problem efficiently.
We study the secure degrees of freedom (d.o.f.) of one-hop wireless networks by considering four fundamental wireless network structures: 1) Gaussian wiretap channel; 2) Gaussian broadcast channel ...with confidential messages; 3) Gaussian interference channel with confidential messages; and 4) Gaussian multiple access wiretap channel. The secrecy capacity of the canonical Gaussian wiretap channel does not scale with the transmit power, and hence, the secure d.o.f. of the Gaussian wiretap channel with no helpers is zero. It has been known that a strictly positive secure d.o.f. can be obtained in the Gaussian wiretap channel by using a helper, which sends structured cooperative signals. We show that the exact secure d.o.f. of the Gaussian wiretap channel with a helper is 1/2. Our achievable scheme is based on real interference alignment and cooperative jamming, which renders the message signal and the cooperative jamming signal separable at the legitimate receiver, but aligns them perfectly at the eavesdropper preventing any reliable decoding of the message signal. Our converse is based on two key lemmas. The first lemma quantifies the secrecy penalty by showing that the net effect of an eavesdropper on the system is that it eliminates one of the independent channel inputs. The second lemma quantifies the role of a helper by developing a direct relationship between the cooperative jamming signal of a helper and the message rate. We extend this result to the case of M helpers, and show that the exact secure d.o.f. in this case is M/M+1.We then generalize this approach to more general network structures with multiple messages. We show that the sum secure d.o.f. of the Gaussian broadcast channel with confidential messages and M helpers is 1, the sum secure d.o.f. of the twouser interference channel with confidential messages is 2/3, the sum secure d.o.f. of the two-user interference channel with confidential messages and M helpers is 1, and the sum secure d.o.f. of the K-user multiple access wiretap channel is K(K-1)/K(K-1)+1.
We consider an information updating system where an information provider and an information receiver engage in an update process over time. Different from the existing literature where updates are ...countable (hard) and take effect either immediately or after a delay, but instantaneously in both cases, here updates start taking effect right away but gradually over time. We coin this setting soft updates. When the updating process starts, the age decreases until the soft update period ends. We constrain the number of times the information provider and the information receiver meet (number of update periods) and the total duration of the update periods. We consider two models for the decrease of age during an update period: In the first model, the rate of decrease of age is proportional to the current age, and in the second model, the rate of decrease of age is constant. The first model results in an exponentially decaying age, and the second model results in a linearly decaying age. In both cases, we determine the optimum updating schemes, by determining the optimum start times and optimum durations of the updates, subject to the constraints on the number of update periods and the total update duration.
PDF
