We are given a set of sensors at given locations, a set of potential locations for placing base stations (BSs, or sinks), and another set of potential locations for placing wireless relay nodes. There is a cost for placing a BS and a cost for placing a relay. The problem we consider is to select a set of BS locations, a set of relay locations, and an association of sensor nodes with the selected BS locations, so that number of hops in the path from each sensor to its BS is bounded by hmax, and among all such feasible networks, the cost of the selected network is the minimum. The hop count bound suffices to ensure a certain probability of the data being delivered to the BS within a given maximum delay under a light traffic model. We observe that the problem is NP-Hard, and is hard to even approximate within a constant factor. For this problem, we propose a polynomial time approximation algorithm (SmartSelect) based on a relay placement algorithm proposed in our earlier work, along with a modification of the greedy algorithm for weighted set cover. We have analyzed the worst case approximation guarantee for this algorithm. We have also proposed a polynomial time heuristic to improve upon the solution provided by SmartSelect. Our numerical results demonstrate that the algorithms provide good quality solutions using very little computation time in various randomly generated network scenarios.
Several variations of the optimal node placement problem have been studied in the literature. @cite_8 @cite_9 @cite_19 studied variations of the problem of , where a minimum number of relays have to be placed in a two-dimensional region (they can be placed anywhere; no locations are given) to obtain a tree spanning a given set of vertices (sources and BS). No QoS constraint was imposed in their formulations. They showed the problems to be NP-Hard, and proposed approximation algorithms. @cite_7 studied the problem of optimal relay placement for @math connectivity. They proposed an @math approximation algorithm for the problem with any @math . However, they also did not impose any QoS constraint.
@cite_19 @cite_9 @cite_7 @cite_8
2122027153 2109785846 2015222956 2952542244
Our work is motivated by impromptu (or ''as-you-go'') deployment of wireless relay nodes along a path, a need that arises in many situations. In this paper, the path is modeled as starting at the origin (where there is the data sink, e.g., the control center), and evolving randomly over a lattice in the positive quadrant. A person walks along the path deploying relay nodes as he goes. At each step, the path can, randomly, either continue in the same direction or take a turn, or come to an end, at which point a data source (e.g., a sensor) has to be placed, that will send packets to the data sink. A decision has to be made at each step whether or not to place a wireless relay node. Assuming that the packet generation rate by the source is very low, and simple link-by-link scheduling, we consider the problem of sequential relay placement so as to minimize the expectation of an end-to-end cost metric (a linear combination of the sum of convex hop costs and the number of relays placed). This impromptu relay placement problem is formulated as a total cost Markov decision process. First, we derive the optimal policy in terms of an optimal placement set and show that this set is characterized by a boundary (with respect to the position of the last placed relay) beyond which it is optimal to place the next relay. Next, based on a simpler one-step-look-ahead characterization of the optimal policy, we propose an algorithm which is proved to converge to the optimal placement set in a finite number of steps and which is faster than value iteration. We show by simulations that the distance threshold based heuristic, usually assumed in the literature, is close to the optimal, provided that the threshold distance is carefully chosen. This paper addresses the following relay sensor placement problem: given the set of duty sensors in the plane and the upper bound of the transmission range, compute the minimum number of relay sensors such that the induced topology by all sensors is globally connected. This problem is motivated by practically considering the tradeoff among performance, lifetime, and cost when designing sensor networks. In our study, this problem is modelled by a NP-hard network optimization problem named Steiner Minimum Tree with Minimum number of Steiner Points and bounded edge length (SMT-MSP). In this paper, we propose two approximate algorithms, and conduct detailed performance analysis. The first algorithm has a performance ratio of 3 and the second has a performance ratio of 2.5. This work addresses the relay node placement problem in wireless sensor networks. We consider a scenario in which all sensor nodes stream data towards sink nodes. Additional relay nodes can be placed with the aim of optimizing overall network performance in terms of data throughput. We formalize the problem with a linear, mixed integer mathematical programming model. We include a number of constraints and penalties to closely model the wireless environment. When relay nodes can be placed anywhere, we define their possible locations using a discrete grid. Model solutions specify both where to place the relays and the paths for routing. Through extensive simulation experiments, we compare model solutions against a state-of-the-art dynamic routing protocol to assess the quality of the routes, and against a relay node placement heuristic to evaluate relay positioning. To tackle the computational complexity, we also propose and study the effect of different strategies for determining the grid resolution. Additionally, an experimental validation carried out in a real testbed shows that the computed solutions clearly increase network performance by enabling the reception of larger number of data packets at the sinks and determining a fair QoS distribution among the nodes. Finally, we propose an on-line application, in which the model is built and solved on-demand, to adapt to changes in traffic patterns induced by external events, and the results are rapidly spread throughout the network and used to modify relay node positioning and routing paths. We study the problem of optimal sequential ("as-you-go") deployment of wireless relay nodes as a person walks along a line of random length (with a known distribution). The objective is to create an impromptu multihop wireless network for connecting a packet source to be placed at the end of the line with a sink node located at the starting point, to operate in the light traffic regime. As the deployment person walks along the line from the sink towards the source, at every step, he measures the channel quality to one (or more) previously placed relays, and places the relay nodes based on these measurements, so as to minimize either the sum power or the maximum power from the source to the sink node in the resultant network, subject to a constraint on the expected number of relays placed. For each of these two objectives, two different relay selection strategies are considered: (i) each relay communicates with the sink via its immediate previous relay, (ii) the communication path can skip some of the deployed relays. With appropriate modeling assumptions, we formulate each of these problems as a Markov decision process (MDP). We provide the optimal policy structures for all these cases, and provide illustrations, via numerical results, for some typical parameters.