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
2952542244
This paper presents the evaluation of the multi-hop aggregate information efficiency of the slotted and unslotted ALOHA protocols. We consider a multi-hop wireless network where the nodes are spatially characterized by a Poisson point process and the traffic generation also follows a Poisson distribution. By applying the properties of stochastic geometry, we derive a closed-form lower bound on the outage probability as a function of the required communication rate, the single-hop distance, the number of hops and the maximum number of retransmissions. The results indicate that slotted ALOHA always outperforms its unslotted version, demonstrating the importance of synchronization in distributed networks. In addition, we show that it is always possible to optimize the network efficiency by properly setting the required rate for a given packet density. Finally, in the scenario considered, the use of retransmissions and multiple hops never achieves the best performance if compared to the option of single-hop links without retransmissions.