We propose a novel relay augmentation strategy for extending the lifetime of a certain class of wireless sensor networks. In this class sensors are located at fixed and pre-determined positions and all communication takes place via multi-hop paths in a fixed routing tree rooted at the base station. It is assumed that no accumulation of data takes place along the communication paths and that there is no restriction on where additional relays may be located. Under these assumptions the optimal extension of network lifetime is modelled as the Euclidean @math -bottleneck Steiner tree problem. Only two approximation algorithms for this NP-hard problem exist in the literature: a minimum spanning tree heuristic (MSTH) with performance ratio 2, and a probabilistic 3-regular hypergraph heuristic (3RHH) with performance ratio @math . We present a new iterative heuristic that incorporates MSTH and show via simulation that our algorithm performs better than MSTH in extending lifetime, and outperforms 3RHH in terms of efficiency.
As mentioned above, here we model optimal lifetime extension as a @math -bottleneck Steiner problem. This problem was introduced by Saraffzedeh and Wong @cite_11 , and various authors have considered it in the context of facility location science @cite_26 , @cite_23 . The problem is NP-hard; in fact, unless P=NP, no polynomial-time algorithm exists for the problem in the Euclidean plane with a less than @math , where this ratio is defined as the theoretically largest possible value attained when dividing the length of the bottleneck edge produced by a given polynomial-time algorithm by the length of the bottleneck edge in an optimal solution . Wang and Du, the authors who demonstrated this complexity bound, present in @cite_24 the first deterministic approximation algorithm for the @math -bottleneck problem in both the rectilinear and Euclidean planes. They also prove that the performance ratio of their algorithm, the afore-mentioned minimum spanning tree heuristic, is bounded above by @math for each of these metrics. @cite_2 describe a probabilistic @math -regular hypergraph heuristic ( @math RHH) with performance ratio @math which runs in @math time, where @math is the number of given terminals. Recently @cite_22 , @cite_5 developed exact algorithms with exponential complexity.
@cite_26 @cite_22 @cite_24 @cite_23 @cite_2 @cite_5 @cite_11
1990630682 2144383545 2171603211 2975802624 2073061830 2161071733
This paper presents a new method of locating n new facilities among m destinations in accordance with the minimax criterion; that is, the facilities are located to minimize the maximum weighted distance in the system. Distances may be rectangular, Euclidean, or general (lp). The method involves the numerical integration of ordinary differential equations and is computationally superior to methods using nonlinear programming. Given n points, called terminals, in the plane ℝ2 and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ2 and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ2, usually, the Euclidean or the L 1 metric. This problem is known to be NP-hard. In this paper, we study this problem in the L p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog 2 n time for the L 1 and the L ∞ metrics, and the first exact algorithm for the L p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L 2 metric. In the design of wireless communication networks, due to a budget limit, suppose we could put totally n+k stations in the plane. However, n of them must be located at given points. Of course, one would like to have the distance between stations as small as possible. The problem is how to choose locations for other k stations to minimize the longest distance between stations. This problem is NP-hard. We show that if NP P , no polynomial-time approximation for the problem in the rectilinear plane has a performance ratio less than 2 and no polynomial-time approximation for the problem in the Euclidean plane has a performance ratio less than 2 and that there exists a polynomial-time approximation with performance ratio 2 for the problem in both the rectilinear plane and the Euclidean plane. We study variations of Steiner tree problem. Let P = p1, p2, ...,p n be a set of n terminals in the Euclidean plane. For a positive integer k, the bottleneck Steiner tree problem (BSTP for short) is to find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. For a positive constant R, the Steiner tree problem with minimum number of Steiner points (STP - MSP for short) asks for a Steiner tree such that each edge in the tree has length at most R and the number of Steiner points is minimized. In this paper, we give (1) a ratio-√3 + e approximation algorithm for BSTP, where e is an arbitrary positive number; (2) a ratio-3 approximation algorithm for STP-MSP with running time O(n 3 ); (3) a ratio-5 2 approximation algorithm for STP-MSP. We study the Euclidean bottleneck Steiner tree problem: given a set P of n points in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edge in the tree is minimized. This problem is known to be NP-hard even to approximate within ratio 2 and there was no known exact algorithm even for k=1 prior to this work. In this paper, we focus on finding exact solutions to the problem for a small constant k. Based on geometric properties of optimal location of Steiner points, we present an optimal @Q(nlogn)-time exact algorithm for k=1 and an O(n^2)-time algorithm for k=2. Also, we present an optimal @Q(nlogn)-time exact algorithm for any constant k for a special case where there is no edge between Steiner points. A Steiner tree with maximum-weight edge minimized is called a bottleneck Steiner tree (BST). The authors propose a Theta ( mod rho mod log mod rho mod ) time algorithm for constructing a BST on a point set rho , with points labeled as Steiner or demand; a lower bound, in the linear decision tree model, is also established. It is shown that if it is desired to minimize further the number of used Steiner points, then the problem becomes NP-complete. It is shown that when locations of Steiner points are not fixed the problem remains NP-complete; however, if the topology of the final tree is given, then the problem can be solved in Theta ( mod rho mod log mod rho mod ) time. The BST problem can be used, for example, in VLSI layout, communication network design, and (facility) location problems. >