Physical layer security is a common concern in dual-function radar communications (DFRC) because of sharing of information between different emitters. We study covert communications between a DFRC unit and multiple legitimate users, with assistance from an intelligent reflecting surface (IRS). The system has multiple targets that need to be detected, and each target is collocated with a warden trying to detect the ongoing communication. We seek to maximize the worst-case data rate across users under radar detection constraint and covertness constraint. To this end, we superpose artificial noise with our message signal so that the wardens’ received signal statistics do not change significantly if communications suddenly starts. We formulate a highly non-convex optimization problem to determine the passive beamforming scheme for the IRS and active precoding scheme at the transmitter, and solve it using a combination of auxiliary matrices, alternating optimization, and a variant of stochastic gradient descent. Finally, we validate the proposed algorithm numerically.

In recent years, research on signal and information theory from the electromagnetics viewpoint has drawn significant attention, mostly due to its potential use in various communication technologies such as multiple-input-multiple-output (MIMO) and Reconfigurable Intelligent Surface (RIS). In this paper, we introduce a new attack called controller manipulation attack (CMA) on a RIS assisted communication system between a transmitter and a receiver, and develop mathematical theory for its design and detection. An attacker has the capability to manipulate the RIS controller and modify the phase shift induced by the RIS elements on the incident electromagnetic signal. The goal of the attacker is to minimize the data rate at the receiver, subject to a constraint on the attack detection probability at the receiver. We consider a number of attack detection models: (i) composite hypothesis testing based attack detection in a given fading block for known channel gains, (ii) quickest detection of CMA in a given fading block for known channel gains, (iii) nonparametric hypothesis test to detect CMA for unknown channel gains over a fading block, and (iv) signal-to-noise-ratio (SNR) moment based detection over possibly multiple fading blocks. In the first case, we show that a simple energy detector is uniformly most powerful (UMP). In the second case, simplification of the standard CUSUM test and its performance bounds are obtained. In the third case, non-parametric Kolmogorov-Smirnov test is further simplified to a simple per-sample double threshold test. The optimal attack against these three detectors are designed via novel optimization formulations and semidefinite relaxation based solutions. In the fourth case, we consider threshold detection using moments of SNR; various SNR moments under no attack are obtained analytically for large RIS and then used to formulate the optimal attack design problem as a linear program. Finally, numerical results demonstrate the efficacy of the proposed schemes.

In this paper, we consider age-of-information (AoI) minimization for an energy harvesting (EH) source that samples and sends the observations to a sink node. At each time, the source observes the channel quality, the available energy, and the age, and decides whether to sample and send the observation to the sink. We formulate the problem as a Markov decision process (MDP) and establish a threshold structure for the optimal sampling policy. Next, motivated by the popular sliding window upper confidence bound reinforcement learning (SW-UCRL2) algorithm for non-stationary reinforcement learning (RL), we leverage this threshold structure and propose an age-energy-channel based SW-UCRL2 (AEC-SW-UCRL2) algorithm to handle unknown and time-varying energy harvesting rate and channel statistics, when an upper bound to the total variation of each of these quantities over the time horizon is available. Next, for the case when these variation budgets are not available, motivated by the popular bandit-over-RL (BORL) algorithm, we propose an algorithm named age-energy-channel based bandit-over-reinforcement learning (AEC-BORL). Finally, we demonstrate the superior numerical performance of these proposed algorithms via numerical experiments.

Millimeter wave (mmWave) device to device (D2D) communication is highly susceptible to obstacles due to severe penetration losses. Dynamic obstacles may cause unpredictable fluctuations to D2D channel quality and hence a D2D relay initially chosen by base station (BS) might undergo failed transmissions resulting in severe packet loss and delay. This local information regarding link quality deterioration needs to be informed to the BS by the user equipments (UEs) which may result in some delay. Also, exploring a new relay on mmWave channel results in significant delay due to directional search. Hence the following optimal sequential decision must be made when packet loss occurs: whether to explore for a new relay link considering exploration cost, or to continue communication via the existing relay. We model this sequential decision problem locally at each UE as partially observable Markov decision process to capture uncertainty in D2D links while minimizing delay. We derive an optimal threshold policy for both positively and negatively correlated links. We also provide a simplified and easy to implement policy based on successive acknowledgment failures for positively correlated links. Through simulation, we validate theoretical findings and demonstrate that our approach outperforms existing state of the art algorithms.

With the use of common signaling methods for dual-function radar-communications (DFRC) systems, the susceptibility of eavesdropping on messages aimed at legitimate users has worsened. For DFRC systems, the radar target may act as an eavesdropper (ED) that receives a high-energy signal thereby leading to additional challenges. Unlike prior works, we consider a multicast multi-antenna DFRC system with multiple EDs. We then propose a physical layer design approach to maximize the secrecy rate by installing intelligent reflecting surfaces in the radar channels. Our optimization of multiple ED multicast multi-antenna DFRC secrecy rate (OptM3Sec) approach solves this highly nonconvex problem with respect to the precoding matrices. Our numerical experiments demonstrate the feasibility of our algorithm in maximizing the secrecy rate in this DFRC setup.

In this paper, we introduce a new attack called controller manipulation attack (CMA) on a Reconfigurable Intelligent Surface (RIS) assisted communication system between a transmitter and a receiver. An attacker has the potential to manipulate the RIS controller and modify the phase shift induced by the RIS elements. The goal of the attacker is to minimize the data rate at the receiver, subject to a constraint on the attack detection probability at the receiver. We consider two different attack detection models: (i) composite hypothesis testing based attack detection in a given fading block for known channel gains, and (ii) SNR moment based detection over possibly multiple fading blocks. In the first case, a simple energy detector turns out to be uniformly most powerful (UMP) and the attack against this energy detector is designed via a novel optimization formulation and a semidefinite relaxation based solution. In the second case, we consider threshold detection using moments of SNR; various SNR moments under no attack are obtained analytically for large RIS and then used to formulate the attack design problem as a linear program. Finally, numerical results illustrate the performance and trade-offs associated with the attack schemes, and also demonstrate their efficacy.

Herein, design of false data injection attack on a distributed cyber-physical system is considered. A stochastic process with linear dynamics and Gaussian noise is measured by multiple agent nodes, each equipped with multiple sensors. The agent nodes form a multi-hop network among themselves. Each agent node computes an estimate of the process by using its sensor observation and messages obtained from neighboring nodes, via Kalman-consensus filtering. An external attacker, capable of arbitrarily manipulating the sensor observations of some or all agent nodes, injects errors into those sensor observations. The goal of the attacker is to steer the estimates at the agent nodes as close as possible to a pre-specified value, while respecting a constraint on the attack detection probability. To this end, a constrained optimization problem is formulated to find the optimal parameter values of a certain class of linear attacks. The parameters of linear attack are learnt on-line via a combination of stochastic approximation based update of a Lagrange multiplier, and an optimization technique involving either the Karush-Kuhn-Tucker (KKT) conditions or online stochastic gradient descent. The problem turns out to be convex for some special cases. Desired convergence of the proposed algorithms are proved by exploiting the convexity and properties of stochastic approximation algorithms. Finally, numerical results demonstrate the efficacy of the attack.

Blockage due to obstacles in millimeter wave (mmWave) device to device (D2D) communication is a prominent problem due to their severe penetration losses. Potential user equipments (UEs) in vicinity of the source UE must be explored in order to select a new relay when the current link gets blocked. However, dynamic obstacles are not known in advance and thus may cause unpredictable fluctuations to D2D channel quality causing newly selected relay link also to be susceptible to blockage. This might cause frequent relay switching leading to call drops and high energy consumption. We have proposed the idea of reducing frequency in relay exploration and switching and thus average end-to-end delay (in seconds) at the expense of additional exploration time units (few milliseconds) during beam alignment. We seek to learn the uncertainty in D2D link qualities by modeling the problem as finite horizon partially observable Markov decision process (POMDP) framework locally at each UE. We have derived an optimal threshold policy which maps the state to set of actions. We then give a simplified and easy to implement stationary threshold policy which counts the number of successive acknowledgment successes/failures for making decisions of selecting or not selecting a given relay locally. Through extensive simulation, we validate our theoretical findings and demonstrate that our approach captures the tradeoff between average exploration time and average end-to-end (E2E) delay in presence of dynamic obstacles.

In this paper, quickest detection of false data injection attack on remote state estimation is considered. A set of$N$sensors make noisy linear observations of a discrete-time linear process with Gaussian noise, and report the observations to a remote estimator. The challenge is the presence of a few potentially malicious sensors which can start strategically manipulating their observations at a random time in order to skew the estimates. The quickest attack detection problem for a known linear attack scheme is posed as a constrained Markov decision process in order to minimize the expected detection delay subject to a false alarm constraint, with the state involving the probability belief at the estimator that the system is under attack. State transition probabilities are derived in terms of system parameters, and the structure of the optimal policy is derived analytically. It turns out that the optimal policy amounts to checking whether the probability belief exceeds a threshold. Numerical results demonstrate significant performance gain under the proposed algorithm against competing algorithms.

In this paper, minimization of time-averaged age-of-information (AoI) in an energy harvesting (EH) source equipped remote sensing setting is considered. The EH source opportunistically samples one or multiple processes over discrete time instants, and sends the status updates to a sink node over a time-varying wireless link. At any discrete time instant, the EH node decides whether to probe the link quality using its stored energy, and further decides whether to sample a process and communicate the data based on the channel probe outcome. The trade-off is between the freshness of information available at the sink node and the available energy at the energy buffer of the source node. To this end, an infinite horizon Markov decision process theory is used to formulate the problem of minimization of time-averaged expected AoI for a single energy harvesting source node. The following two scenarios are considered: (i) single process with channel state information at transmitter (CSIT), (ii) multiple processes with CSIT. In each scenario, for probed channel state, the optimal source node sampling policy is shown to be a threshold policy involving the instantaneous age of the process(es), the available energy in the buffer and the instantaneous channel quality as the decision variables. Finally, numerical results are provided to demonstrate the policy structures and trade-offs.

Millimeter wave (mmWave) device to device (D2D) communication is highly susceptible to obstacles due to severe penetration losses and requires almost a line of sight (LOS) communication path. D2D channel condition is local to devices/user equipments (UEs) and hence is not directly visible to the base station (BS). Thus quality of the D2D channel needs to be propagated to BS by UEs which may incur some delay. Hence the solution provided by BS to UEs using this gathered channel information might become less useful to establish communication due to moving obstacles. These types of obstacles might not be known in advance and hence may cause unpredictable fluctuations to the D2D channel quality. Hence we seek to learn the D2D channels using the finite horizon partially observable Markov decision process (POMDP) framework to model the uncertainty in such kind of network environments with dynamic obstacles. The objective is to minimize delay when channel quality deteriorates, by making UEs choose locally the best possible decision between i) to continue on the current relay link on which communication is taking place or ii) to switch to another good relay by exploring other possible UEs in its locality. We derive an optimal threshold policy which tells the UE to take appropriate decision locally. Later, we give a simplified and easy to implement stationary threshold policy which counts the number of successive acknowledgement failures, based on which UE make appropriate decision locally. Through extensive simulation, we demonstrate that our approach outperforms recent algorithms.

In this paper, selection of an active sensor subset for tracking a discrete time, finite state Markov chain having an unknown transition probability matrix (TPM) is considered. A total of N sensors are available for making observations of the Markov chain, out of which a subset of sensors are activated each time in order to perform reliable estimation of the process. The trade-off is between activating more sensors to gather more observations for the remote estimation, and restricting sensor usage in order to save energy and bandwidth consumption. The problem is formulated as a constrained minimization problem, where the objective is the long-run averaged mean-squared error (MSE) in estimation, and the constraint is on sensor activation rate. A Lagrangian relaxation of the problem is solved by an artful blending of two tools: Gibbs sampling for MSE minimization and an on-line version of expectation maximization (EM) to estimate the unknown TPM. Finally, the Lagrange multiplier is updated using slower timescale stochastic approximation in order to satisfy the sensor activation rate constraint. The on-line EM algorithm, though adapted from literature, can estimate vector-valued parameters even under time-varying dimension of the sensor observations. Numerical results demonstrate approximately 1 dB better error performance than uniform sensor sampling and comparable error performance (within 2 dB bound) against complete sensor observation. This makes the proposed algorithm amenable to practical implementation.

In this paper, a point-to-point network transmission control problem is formulated as a Markov decision process (MDP). Classical dynamic programming techniques such as value iteration, policy iteration, and linear programming can be employed to solve the optimization problem, but they suffer from high-computational complexity in networks with large state space. To achieve complexity reduction, the structure of the optimal policy can be exploited and incorporated into standard algorithms. In addition, function approximation can also be applied, where the value function is approximated by the linear combination of some basis vectors in a lower dimensional subspace. The main challenge for function approximation lies in the absence of general guidelines for subspace construction. In this paper, a proper subspace for projection is first generated based on system information, and more general construction methods are proposed using tools from graph signal processing (GSP). Graph symmetrization methods are also used to tackle the directed nature of the probability transition graph so that the well-developed GSP theory for undirected graphs can be employed. The numerical results for a typical wireless system show that standard algorithms with structural information incorporated can achieve 50% complexity reduction without performance loss. The subspace generated from the system can achieve zero policy error with faster runtime, and the GSP approach can also provide a proper subspace for perfect reconstruction of the optimal policy. It is also shown that how the proposed method can be applied to other MDP problems.

In this paper, we consider the problem of location-dependent opportunistic bandwidth sharing between static and mobile (i.e., moving) downlink users in a cellular network. Each cell of the network has some fixed number of static users. Mobile users enter the cell, move inside the cell for some time, and then leave the cell. In order to provide higher data rate to the highly mobile users whose fast fading channel variation is difficult to track, we propose location dependent bandwidth sharing between the two classes of static and mobile users; the idea is to provide higher bandwidth to the mobile users at favourable locations, and provide higher bandwidth to the static users in other times. Our approach is agnostic to the way the bandwidth is further shared within the same class of users; it can be combined with any particular bandwidth allocation policy employed for one of these two classes of users. We formulate the problem as a long run average reward Markov decision process (MDP) where the per-step reward is a linear combination of instantaneous data volumes received by static and mobile users, and find the optimal policy. The optimal policy is binary in nature; it allocates the entire bandwidth either to the static users or to the mobile users at any given time. The reward structure of this MDP is not known in general, and it may change with time. To alleviate these issues, we propose a learning algorithm based on single timescale stochastic approximation. Also, noting that the MDP problem can be used to maximize the long run average data rate for mobile users subject to a constraint on the long run average data rate of static users, we provide a learning algorithm based on multi-timescale stochastic approximation. We prove asymptotic convergence of the bandwidth sharing policies under these learning algorithms to the optimal policy. The results are extended to address the issue of fair bandwidth sharing between the two classes of static and mobile users, where the notion of fairness is motivated by the popular notion of α-fairness in the literature. Numerical results exhibit significant performance improvement by our scheme, as well as fast convergence, and also demonstrate the trade-off between performance gain and fairness requirement.

In small cell networks, the high mobility of users results in frequent handoff and thus severely restricts the data rate for mobile users (MUs). To alleviate this problem, we propose use of the heterogeneous two-tier network structure where static users (SUs) are served by both macro and micro base stations (BSs), whereas the mobile (i.e., moving) users are served only by the macro BSs having larger cells; the idea is to prevent frequent data outage for MUs due to handoff. We use the classical two-tier Poisson network model with different transmit powers, and assume the independent Poisson process of SUs and doubly stochastic Poisson process of MUs moving at a constant speed along infinite straight lines generated by a Poisson line process. Using tools from stochastic geometry, we calculate the average downlink data rate of the typical static and mobile (i.e., moving) users, and the latter accounted for handoff outage periods. We consider also the average throughput of these two types of users defined as their average data rates divided by the mean total number of users co-served by the same base station. We find that if the density of a homogeneous network and/or the speed of MUs is high, it is advantageous to let the MUs connect only to some optimal fraction of BSs (i.e., an optimal random subset of BSs) to reduce the frequency of handoffs during which the connection is not assured. If a heterogeneous structure of the network is allowed, one can further jointly optimize the mean throughput of MUs and SUs. This joint optimization is done by appropriately tuning the powers of micro and macro BSs subject to some aggregate power constraint ensuring unchanged mean data rates of SUs via the network equivalence property.

Motivated by the Internet-of-things and sensor networks for cyberphysical systems, the problem of low complexity dynamic sensor activation for the tracking of a time-varying process is examined. The tradeoff is between energy efficiency and fidelity. The problem of minimizing the time-averaged mean-squared error over infinite horizon is examined under a constraint on the mean number of active sensors. The proposed method artfully combines two key ingredients: Gibbs sampling for sensor subset selection, and stochastic approximation for learning, in order to create a high performance, energy efficient tracking mechanism with active sensor selection. Tracking of an i.i.d. process with unknown parametric distribution is considered; the main challenge here is that the unknown parameter vector must be learned. The key theoretical result proves that the proposed algorithm converges to locally optimal solutions. Numerical results suggest that global optimality is in fact achieved in some cases.

We are motivated by the need, in emergency situations, for impromptu (or “as-you-go”) deployment of multihop wireless networks, by human agents or robots (e.g., unmanned aerial vehicles (UAVs)); the agent moves along a line, makes wireless link quality measurements at regular intervals, and makes on-line placement decisions using these measurements. As a first step, we have formulated such deployment along a line as a sequential decision problem. In our earlier work, reported in [1], we proposed two possible deployment approaches: (i) the pure as-you-go approach where the deployment agent can only move forward, and (ii) the explore-forward approach where the deployment agent explores a few successive steps and then selects the best relay placement location among them. The latter was shown to provide better performance (in terms of network cost, network performance, and power expenditure), but at the expense of more measurements and deployment time, which makes explore-forward impractical for quick deployment by an energy constrained agent such as a UAV. Further, since in emergency situations the terrain would be unknown, the deployment algorithm should not require a-priori knowledge of the parameters of the wireless propagation model. In [1], we, therefore, developed learning algorithms for the explore-forward approach. The current paper fills in an important gap by providing deploy-and-learn algorithms for the pure as-you-go approach. We formulate the sequential relay deployment problem as an average cost Markov decision process (MDP), which trades off among power consumption, link outage probabilities, and the number of relay nodes in the deployed network. While the pure as-you-go deployment problem was previously formulated as a discounted cost MDP (see [1]), the discounted cost MDP formulation was not amenable for learning algorithms that are proposed in this paper. In this paper, first we show structural results for the optimal policy corresponding to the average cost MDP, and provide new insights into the optimal policy. Next, by exploiting the special structure of the average cost optimality equation and by using the theory of asynchronous stochastic approximation (in single and two timescale), we develop two learning algorithms that asymptotically converge to the set of optimal policies as deployment progresses. Numerical results show reasonably fast speed of convergence, and hence the model-free algorithms can be useful for practical, fast deployment of emergency wireless networks.

In this paper, we develop Gibbs sampling-based techniques for learning the optimal placement of contents in a cellular network. We consider the situation where a finite collection of base stations are scattered on the plane, each covering a cell (possibly overlapping with other cells). Mobile users request downloads from a finite set of contents according to some popularity distribution which may be known or unknown to the base stations. Each base station has a fixed memory space that can store only a strict subset of the contents at a time; hence, if a user requests content that is not stored at any of its serving base stations, the content has to be downloaded from the backhaul. Hence, we consider the problem of optimal content placement which minimizes the rate of download from the backhaul, or equivalently maximize the cache hit rate. It is known that, when multiple cells can overlap with one another (e.g., under dense deployment of base stations in small cell networks), it is not optimal to place the most popular contents in each base station. However, the optimal content placement problem is NP-complete. Using the ideas of Gibbs sampling, we propose simple sequential content update rules that decide whether to store content at a base station (if required from the base station) and which content has to be removed from the corresponding cache, based on the knowledge of contents stored in its neighboring base stations. The update rule is shown to be asymptotically converging to the optimal content placement for all nodes under the knowledge of content popularity. Next, we extend the algorithm to address the situation where content popularities and cell topology are initially unknown, but are estimated as new requests arrive to the base stations; we show that our algorithm working with the running estimates of content popularities and cell topology also converges asymptotically to the optimal content placement. Finally, we demonstrate the improvement in cache hit rate compared with the most popular content placement and independent content placement strategies via numerical exploration.

An energy efficient use of large scale sensor networks necessitates activating a subset of possible sensors for estimation at a fusion center. The problem is inherently com- binatorial; to this end, a set of iterative, randomized algorithms are developed for sensor subset selection by exploiting the underlying statistics. Gibbs sampling-based methods are designed to optimize the estimation error and the mean number of activated sensors. The optimality of the proposed strategy is proven, along with guarantees on their convergence speeds. Also, another new algorithm exploiting stochastic approximation in conjunction with Gibbs sampling is derived for a constrained version of the sensor selection problem. The methodology is extended to the scenario where the fusion center has access to only a parametric form of the joint statistics, but not the true underlying distribution. Therein, expectation-maximization is effectively employed to learn the distribution. Strategies for iid time- varying data are also outlined. Numerical results show that the proposed methods converge very fast to the respective optimal solutions, and therefore can be employed for optimal sensor subset selection in practical sensor networks.

We use information theoretic achievable rate formulas for the multi-relay channel to study the problem of as-you-go deployment of relay nodes. The achievable rate formulas are for full-duplex radios at the relays and for decode-and-forward relaying. Deployment is done along the straight line joining a source node and a sink node at an unknown distance from the source. The problem is for a deployment agent to walk from the source to the sink, deploying relays as he walks, given the knowledge of the wireless path-loss model, and given that the distance to the sink node is exponentially distributed with known mean. As a precursor to the formulation of the deploy-as-you-go problem, we apply the multi-relay channel achievable rate formula to obtain the optimal power allocation to relays placed along a line, at fixed locations. This permits us to obtain the optimal placement of a given number of nodes when the distance between the source and sink is given. Numerical work for the fixed source-sink distance case suggests that, at low attenuation, the relays are mostly clustered close to the source in order to be able to cooperate among themselves, whereas at high attenuation they are uniformly placed and work as repeaters. We also prove that the effect of path-loss can be entirely mitigated if a large enough number of relays are placed uniformly between the source and the sink. The structure of the optimal power allocation for a given placement of the nodes, then motivates us to formulate the problem of as-you-go placement of relays along a line of exponentially distributed length, and with the exponential path-loss model, so as to minimize a cost function that is additive over hops. The hop cost trades off a capacity limiting term, motivated from the optimal power allocation solution, against the cost of adding a relay node. We formulate the problem as a total cost Markov decision process, establish results for the value function, and provide insights into the placement policy and the performance of the deployed network via numerical exploration.

Motivated by the need for impromptu or as-you-go deployment of wireless sensor networks in some situations, we study the problem of optimal sequential deployment of wireless sensors and relays along a line (e.g., a forest trail) of unknown length. Starting from the sink node (e.g., a base station), a ”deployment agent„ walks along the line, stops at equally spaced points (”potential„ relay locations), placing relays at some of these points, until he reaches a location at which the source node (i.e., the sensor) needs to be placed, the objective being to create a multihop wireless relay network between the source and the sink. The deployment agent decides whether to place a relay or not at each of the potential locations, depending upon the link quality measurements to the previously placed relays. In this article, we seek to design efficient deployment algorithms for this class of problems, to achieve the objective of 2-connectivity in the deployed network. We ensure multi-connectivity by allowing each node to communicate with more than one neighbouring node. By proposing a network cost objective that is additive over the deployed relays, we formulate the relay placement problem as a Markov decision process. We provide structural results for the optimal policy and evaluate the performance of the optimal policy via numerical exploration. Computation of such an optimal deployment policy requires a statistical model for radio propagation; we extract this model from the raw data collected via measurements in a forestlike environment. To validate the results obtained from the numerical study, we provide an experimental study of algorithms for 2-connected network deployment.

We consider the Medium Access Control (MAC) problem in resource-constrained ad-hoc wireless networks typical of the Internet of Things (IoT). Due to the delay-sensitive nature of emerging IoT applications, there has been increasing interest in developing medium access control (TDMA) protocols in a slotted framework. The design of such MAC protocols must keep in mind the need for contention access at light traffic, and scheduled access in heavy traffic (leading to the long-standing interest in hybrid, adaptive MACs. In this paper, we consider the collocated node setting and require that each node acts autonomously only on the basis of locally available information. We propose EZMAC, a simple extension of ZMAC, and QZMAC which is designed using motivations from our extensions of certain delay-optimality and throughput-optimality theory from the literature. Practical implementation issues are outlined. Finally, we show, through simulations, that both protocols achieve mean delays much lower than those achieved by ZMAC and indeed, QZMAC provides mean delays very close to the minimum achievable in this setting, i.e., that of the centralized complete knowledge scheduler.

We are motivated by the need, in some applications, for impromptu or as-you-go deployment of wireless sensor networks. A person walks along a line, starting from a sink node (e.g., a base-station), and proceeds towards a source node (e.g., a sensor) which is at an a priori unknown location. At equally spaced locations, he makes link quality measurements to the previous relay, and deploys relays at some of these locations, with the aim to connect the source to the sink by a multihop wireless path. In this paper, we consider two approaches for impromptu deployment: (i) the deployment agent can only move forward (which we call a pure as-you-go approach), and (ii) the deployment agent can make measurements over several consecutive steps before selecting a placement location among them (the explore-forward approach). We consider a very light traffic regime, and formulate the problem as a Markov decision process, where the trade-off is among the power used by the nodes, the outage probabilities in the links, and the number of relays placed per unit distance. We obtain the structures of the optimal policies for the pure as-you-go approach as well as for the explore-forward approach. We also consider natural heuristic algorithms, for comparison. Numerical examples show that the explore-forward approach significantly outperforms the pure as-you-go approach in terms of network cost. Next, we propose two learning algorithms for the explore-forward approach, based on Stochastic Approximation, which asymptotically converge to the set of optimal policies, without using any knowledge of the radio propagation model. We demonstrate numerically that the learning algorithms can converge (as deployment progresses) to the set of optimal policies reasonably fast and, hence, can be practical model-free algorithms for deployment over large regions. Finally, we demonstrate the end-to-end traffic carrying capability of such networks via field deployment.

We are motivated by the problem of impromptu or as-you-go deployment of wireless sensor networks. As an application example, a person, starting from a sink node, walks along a forest trail, makes link quality measurements (with the previously placed nodes) at equally spaced locations, and deploys relays at some of these locations, so as to connect a sensor placed at some a priori unknown point on the trail with the sink node. In this paper, we report our experimental experiences with some as-you-go deployment algorithms. Two algorithms are based on Markov decision process (MDP) formulations, these require a radio propagation model. We also study purely measurement based strategies: one heuristic that is motivated by our MDP formulations, one asymptotically optimal learning algorithm, and one inspired by a popular heuristic. We extract a statistical model of the propagation along a forest trail from raw measurement data, implement the algorithms experimentally in the forest, and compare them. The results provide useful insights regarding the choice of the deployment algorithm and its parameters, and also demonstrate the necessity of a proper theoretical formulation.