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, making link quality measurements with the previous relay at equally spaced locations, and deploys relays at some of these locations, so as to connect a sensor placed on the line with a sink at the start of the line. In this paper, we extend our earlier work on the problem (see [1]) to incorporate two new aspects: (i) inclusion of path outage in the deployment objective, and (ii) permitting the deployment agent to make measurements over several consecutive steps before selecting a placement location among them (which we call backtracking). We consider a light traffic regime, and formulate the problem as a Markov decision process. Placement algorithms are obtained for two cases: (i) the distance to the source is geometrically distributed with known mean, and (ii) the average cost per step case. We motivate the per-step cost function in terms of several known forwarding protocols for sleep-wake cycling wireless sensor networks. We obtain the structures of the optimal policies for the various formulations, and provide some sensitivity results about the policies and the optimal values. We then provide a numerical study of the algorithms, thus providing insights into the advantage of backtracking, and a comparison with simple heuristic placement policies.
[label=( * )] The framework of @cite_1 requires the link of each hop to have a certain outage probability. In practice, as the deployment agent walks away from the previously placed node, he can reach a point where even the maximum node power does not provide a link of the desired quality to the previous relay, and walking any farther is unlikely to provide a workable link. At this point the deployment is considered to have failed. In our present paper, we do not bound the outage probability of each hop but make the sum outage over all the hops a part of the optimization objective.
@cite_1
2114106914
We develop a new metric for quantifying end-to-end throughput in multihop wireless networks, which we term random access transport capacity, since the interference model presumes uncoordinated transmissions. The metric quantifies the average maximum rate of successful end-to-end transmissions, multiplied by the communication distance, and normalized by the network area. We show that a simple upper bound on this quantity is computable in closed-form in terms of key network parameters when the number of retransmissions is not restricted and the hops are assumed to be equally spaced on a line between the source and destination. We also derive the optimum number of hops and optimal per hop success probability and show that our result follows the well-known square root scaling law while providing exact expressions for the preconstants, which contain most of the design-relevant network parameters. Numerical results demonstrate that the upper bound is accurate for the purpose of determining the optimal hop count and success (or outage) probability.