- Minimum-energy Packet Forwarding Over Lossy Networks Under Deadline and Reliability Constraints
Zhenhua Zou (KTH-Royal Institute of Technology, Sweden); Mikael Johansson (Royal Institute of Technology, Sweden)
This paper studies the minimum-energy packet forwarding under deadline and reliability constraints over multi-hop and lossy wireless networks. We assume a routing topology in the form of a directed graph with a finite-state Markov chain link loss model, and formulate the minimum energy problem as a finite-horizon constrained Markov decision process. We show that the minimum energy problem can be solved by maximizing a weighted sum of reliability and energy, and that the optimal forwarding policy is a randomized policy over two history-independent and deterministic policies. Numerical examples show that the transmission energy cost of achieving reliabilities close to the maximum can be significant when links are bursty. In addition, transmission power adjustments can further reduce energy cost. Lastly, we develop simple heuristic policies with a good balance between energy and reliability.
- Adaptive Shortest-Path Routing Under Unknown and Stochastically Varying Link States
Keqin Liu (University of California, Davis, USA); Qing Zhao (University of California at Davis, USA)
We consider the adaptive shortest-path routing problem in wireless networks under unknown and stochastically varying link states. In this problem, we aim to optimize the quality of communication between a source and a destination through adaptive path selection. Due to the randomness and uncertainties in the network dynamics, the quality of each link varies over time according to a stochastic process with unknown distributions. After a path is selected for communication, the aggregated quality of all links on this path (e.g., total path delay) is observed. The quality of each individual link is not observable. We formulate this problem as a multi-armed bandit with dependent arms. We show that by exploiting arm dependencies, a regret polynomial with network size can be achieved while maintaining the optimal logarithmic order with time. This is in sharp contrast with the exponential regret order with network size offered by a direct application of the classic MAB policies that ignore arm dependencies. Furthermore, our results are obtained under a general model of link-quality distributions (including heavy-tailed distributions) and find applications in cognitive radio and ad hoc networks with unknown and dynamic communication environments.
- Dynamic Shortest Path Algorithms for Hypergraphs
Jianhang Gao (University of California, Davis, USA); Qing Zhao (University of California at Davis, USA); Wei Ren (Microsoft Corporation, USA); Ananthram Swami (Army Research Lab., USA); Ram Ramanathan (BBN Technologies, USA); Amotz Bar-Noy (Brooklyn College & Graduate Center, CUNY, New York, USA)
hypergraph is a set V of vertices and a set of non-empty subsets of V, called hyperedges. Unlike graphs, hypergraphs can capture higher-order interactions in social and communication networks that go beyond a simple union of pairwise relationships. In this paper, we consider the shortest path problem in hypergraphs. We develop two algorithms for finding and maintaining the shortest hyperpaths in a dynamic network with both weight and topological changes. These two algorithms are the first to address the fully dynamic shortest path problem in a general hypergraph. They complement each other by partitioning the application space based on the nature of the change dynamics and the type of the hypergraph.
- Relay Selection with Channel Probing for Geographical Forwarding in WSNs
Kolar Purushothama Naveen (Indian Institute of Science, India); Anurag Kumar (Indian Institute of Science, India)
In a large wireless sensor network (WSN) with sleep-wake cycling nodes, we are interested in the local decision problem faced by a node that has "custody" of a packet and has to choose one among a set of next-hop relay nodes. Each of the relays is associated with a "reward" that summarizes the cost/benefit of forwarding the packet through that relay. We seek a locally optimal solution to this problem, the idea being that such a solution, if adopted by every node, could provide a reasonable local heuristic for the end-to-end forwarding problem. Towards this end, we propose a local forwarding problem where the relays wake-up at random times, at which instants they reveal the probability distributions of their rewards. To determine a relay's exact reward, the source has to further probe the relay, incurring a probing cost. Thus, at each relay wake-up instant, the source, given a set of relay reward distributions, has to decide whether to stop (and forward the packet to an already probed relay), continue waiting for further relays to wake-up, or probe an unprobed relay. We formulate this local forwarding problem as a Markov decision process (MDP) and obtain some interesting structural results on the optimal policy. Our problem can be considered as a new variant of the optimal stopping problem.