The problem of online packet scheduling with hard deadlines has been studied extensively in the single-hop setting, whereas it is notoriously difficult in the multihop setting. This difficulty stems from the fact that packet scheduling decisions at each hop influence and are influenced by decisions on other hops, and only a few provably efficient online scheduling algorithms exist in the multihop setting. We consider a multihop wired network (interference-free and full duplex transmissions) in which packets with various deadlines and weights arrive at and are destined to different nodes through given routes. We study the problem of joint admission control and packet scheduling in order to maximize the cumulative weights of the packets that reach their destinations within their deadlines. We first focus on uplink transmissions in the tree topology and show that the well-known Earliest Deadline First algorithm achieves the same performance as the optimal offline algorithm for any feasible arrival pattern. We then address the general topology with multiple source-destination pairs, develop a simple online algorithm, and show that it is O(PMlog PM)-competitive, where PMis the maximum route length among all packets. Our algorithm only requires information along the route of each packet, and our result is valid for general arrival samples. Moreover, we show that O(PMlog PM)-competitive is the best any online algorithm can do. Via numerical results, we also show that our algorithm achieves performance that is comparable to the noncausal optimal offline algorithm. To the best of our knowledge, this is the first algorithm with a provable (based on a sample-path construction) competitive ratio, subject to hard deadline constraints for general network topologies.

The problem of online job or packet scheduling with hard deadlines has been studied extensively in the single hop setting, whereas it is notoriously difficult in the multihop setting. This difficulty stems from the fact that packet scheduling decisions at each hop influences and are influenced by decisions on other hops and only a few provably efficient online scheduling algorithms exist in the multihop setting. We consider a general multihop network topology in which packets with various deadlines and weights arrive at and are destined to different nodes through given routes. We study the problem of joint admission control and packet scheduling in order to maximize the cumulative weights of the packets that reach their destinations within their deadlines. We first focus on uplink transmissions in the tree topology and show that the well known earliest deadline first algorithm achieves the same performance as the optimal off-line algorithm for any feasible arrival pattern. We then address the general topology with multiple source-destination pairs, develop a simple online algorithm and show that it is O(PM log PM)-competitive where PM is the maximum route length among all packets. Our algorithm only requires information along the route of each packet and our result is valid for general arrival samples. Via numerical results, we show that our algorithm achieves performance that is comparable to the non-causal optimal off-line algorithm. To the best of our knowledge, this is the first algorithm with a provable (based on a sample-path construction) competitive ratio, subject to hard deadline constraints for general network topologies.

We consider a single-user, single-hop wireless communication system, in which data packets arrive at a data queue to be transmitted to a receiver over a block fading channel, privately from an eavesdropper. We assume that the eavesdropper listens to the transmitter over another independently fading channel and that the transmitter only has knowledge of the distribution of the eavesdropper's channel. We propose a joint secrecy rate, transmission, and admission controller based on a simple index policy that only relies on the distribution of the eavesdropper's channel rate. Given any arrival sample path, we show that our controller achieves the maximum possible data admission rate, while keeping the data queue stable as well as meeting an upper bound on the rate of secrecy outage, i.e., the fraction of data packets that are in part or fully decodable by the eavesdropper. While the solution is not unique, i.e., there are other schemes that can achieve the aforementioned performance, we show that our scheme also achieves a low queuing delay for the data packets enqueued at the data queue by striking the correct balance between direct secrecy encoding for data bits and secret key generation and utilization. To obtain this result, our transmission controller makes use of the secret key queue to smooth out the variations in the achievable secrecy rate of the associated fading wiretap channel.

Renewable energy sources can be attached to sensor nodes to provide energy replenishment for prolonging the lifetime of sensor networks. However, for networks with replenishment, conservative energy expenditure may lead to missed recharging opportunities due to battery capacity limitations, while aggressive usage of energy may result in reduced coverage or connectivity for certain time periods. Thus, new power allocation schemes need to be designed to balance these seemingly contradictory goals, in order to maximize sensor network performance. In this paper, we study the problem of how to jointly control the data queue and battery buffer to maximize the long-term average sensing rate of a single communication link in rechargeable sensor networks. The coupling between the battery and data buffers does not lend itself amenable to traditional resource optimization techniques. Thus, we develop a new power and rate allocation scheme that explicitly takes this coupling into account. The new scheme is a simple myopic scheme whose performance is shown to be arbitrarily close to optimal analytically and via simulations.

Energy efficiency is critical for wireless sensor networks. The data-gathering process must be carefully designed to conserve energy and extend network lifetime. For applications where each sensor continuously monitors the environment and periodically reports to a base station, a tree-based topology is often used to collect data from sensor nodes. In this work, we first study the construction of a data-gathering tree when there is a single base station in the network. The objective is to maximize the network lifetime, which is defined as the time until the first node depletes its energy. The problem is shown to be NP-complete. We design an algorithm that starts from an arbitrary tree and iteratively reduces the load on bottleneck nodes (nodes likely to soon deplete their energy due to high degree or low remaining energy). We then extend our work to the case when there are multiple base stations and study the construction of a maximum-lifetime data-gathering forest. We show that both the tree and forest construction algorithms terminate in polynomial time and are provably near optimal. We then verify the efficacy of our algorithms via numerical comparisons.