dynamic deployment in ad hoc networks accommodating uncertain transmission range
Proposals for optimal network deployment in wireless ad hoc networks generally seek to meet specific performance objectives (e.g., connectivity and coverage), typically assuming known and constant transmission ranges for nodes at different locations and in different directions. In practice transmission range is highly uncertain a priori, even for homogeneous networks. In this paper, we explore physical layer models for estimating node connectivity in planar networks based on connectivity observations available from previously deployed nodes, taking into consideration the lognormal distribution and spatial correlation of signal strength. Then we examine application in deployment problems in which an agent (e.g., a robot) would be responsible for maximizing the probability of connecting all separate sensing nodes given a limited number of wireless routing nodes. Though theoretically the dynamic programming framework is suitable for addressing the deployment problem, it would easily become computational intractable even for a small-sized network. This paper proposes heuristics for the deployment problem involving two steps. We alternatively construct a network tree spreading all the separate sensing nodes, and then determine locations for placing routing nodes based on the constructed tree and available connectivity observations, until either the network is connected or the routing nodes are used up. Numerical examples are provided to illustrate the application and performance of the proposed heuristics.
deployment ad hoc networks transmission range uncertainty