Computer Science
ComputerScience,1970-2008-Computer Science-2004.jsonl.gz.gz
Computer Science Mathematics
b19a1f2b38f2340086d7cd951cb8172947df8469
2-Sensor Problem

Ad-hoc networks of sensor nodes are in general semi-permanently deployed. However, the topology of such networks continuously changes over time, due to the power of some sensors wearing out to new sensors being inserted into the network, or even due to designers moving sensors around during a network re-design phase (for example, in response to a change in the requirements of the network). In this paper, we address the problem of covering a given path by a limited number of sensors — in our case to two, and show its relation to the well-studied matrix multiplication problem.


Introduction
Ad-hoc sensor networks are emerging as a new sensing paradigm and have thus, received massive research interest recently. Usually sensor nodes are semi-permanently deployed, since the sensors themselves barely have any moving capacity. However, the topology of such networks continuously changes over time due to a variety of reasons: For example, a sensor node may wear out due to its very limited battery power, a new sensor node may be inserted into the network, or the layout of a sensor network may need to be changed in order to improve the quality of the network coverage in response to a change in the network requirements, which is accomplished by changing the placement of current (or inserting, deleting) sensors in network.
In this paper, we address a problem of covering a path in the network using a limited number of sensors. In a sensor network, each sensor bears the ability to detect objects around it. The coverage of a sensor is limited by its energy level. Assume the sensor's detecting ability is omnidirectional, then we can model the coverage of a sensor as a disk (under 2-norm on the Euclidean plane 1 ) centered at the sensor. The radii of such disks are determined by the energy level of the sensors. The coverage area (or simply coverage) of the sensor network is the union of all such disks.
A sensor network is often used to detect intruders. An intruder may start at a point S on the plane, may follow an arbitrary trajectory (path), and may stop at some other point T on the plane. In some applications, a sensor network may need to keep track of the intruder at all times, as it follows its trajectory; in some other applications, the network's function may be simply to detect the presence of an intruder, in which case the network only needs to cover some part of the trajectory. Thus, given two points S and T , two relevant types of trajectories are proposed [1]: The maximum breach path and the maximum support path (In [1], these paths are called maximal breach path and maximal support path, respectively).
The maximum breach path measures the vulnerability of a sensor network by, as the name suggests, completely avoiding the coverage area of the sensor network: It is a trajectory between the start point S and the stop point T that stays "as far away" from the sensors as possible. On the other hand, the maximum support path measures the efficiency of the network coverage: This path is a trajectory between S and T , which stays "as close to the sensors" as possible. The distance of a point P to the sensor network is defined as the smallest Euclidean distance from P to one of the sensor nodes. A maximum breach path from S to T is a path from S to T such that the minimum distance from a point P in the path to the sensor network is maximized: This distance is called the worst-case coverage distance of the network. Similarly, a maximum support path from S to T is a path such that the maximum distance of a point P in the path to the sensor network is minimized: This distance is called the best-case coverage distance of the network.
We consider this problem of covering an entire trajectory using two sensors only, where each of the sensors should be located on opposite sides of the trajectory. This problem is an extension of the well-studied two-center problem, which we describe in the next section "Two-sensor-problem". We O n time algorithm for this problem, improving on the exhaustive search bound of 3 ( ) O n . The solution proposed is of interest on its own, since it establishes an interesting relation to the matrix multiplication problem. In the section "Two-sensor-problem" we define our problem formally and give an efficient solution for it.

Two-sensor problem
We consider the following problem: There are two groups of sensors A and B of total size n divided by a polygonal xy -monotone path P containing n edges, such that each group is located on opposite sides of P . A path Each sensor i s has its covering area radius i R , so it can detect any object at a distance at most i R from it. We are interested in determining whether there exists a sensor from group A and a sensor from group B that cover the entire path P . The path P is playing role of a possible way for intruder penetration inside the sensors area and each group of sensors wants to catch the intruder while it is important to keep a visual guard of him all the time. We will refer to our problem as the two-sensor problem. Some similar problem has been considered by Huang and Tseng [2], who tried to cover a target area by k sensors from a set consisting of n sensors. Clearly, our task can be performed in O n runtime algorithm based on matrix multiplication and Matoušek algorithm [3] for computing dominance in n -dimensional space. The two-sensor problem naturally extends a list of optimization problems related to the famous two-center problem. In the two-center problem, we want to cover a set S of n points on the plane by two disks of smallest possible common radius. Agarwal and Sharir give an 2 ( log ) O n n -time algorithm in [4] for determining whether S can be covered by two disks of radius r . Plugging this algorithm into the parametric search machinery, one obtains an 2 3 ( log ) O n n -time algorithm for the two-center problem. The runtime of the decision algorithm of Agarwal and Sharir was improved by Hershberger [5]  ( log ) O n n -time algorithm for the discrete two-center problem, where the disks should be centered at the input points. Shin et al. [11] considered the problem of covering convex polygons using two disks of smallest possible radius by giving two algorithms: The first algorithm runs in time 3 ( log ) O n n and assumes that the disks are constrained to be centered at the input points; the second algorithm runs in 2 3 ( log ) O n n time and assumes arbitrary disks location. Huang et al. [12] considered a variation of the two-center problem, where the distance between two solution disks should be below some given constant, providing a 2 2 ( log ) O n n runtime algorithm for this problem.
The two-sensor problem considered in this paper is harder than all of the related variations of the two-center problem in the literature. The hardness comes from two sources: First, we need to cover the entire path and not just a set of discrete points; second, in the solution obtained, an edge may be partially covered by each of the sensors, implying that the sets of edges covered by each sensor may overlap significantly and, therefore, a simple binary search can no longer be used. We follow the notation used by Matoušek [3]. Let X be an × n n matrix of real numbers; we will use the notation , * i x for the i -th row of X ; we say that , * Matoušek [3] presents an algorithm for computing an × n n matrix C , whose element ,

O n .
In what follows, we show how to apply Matoušek's algorithm in order to get a solution to our problem. We start with the following observation, which is crucial for the solution of the 2-sensor problem.

Observation 1. Given an ×
n n matrix of real numbers X and ∈ n h R , we can determine whether there exists two rows in X , , * i x and , * j x such that , … n using Matoušek's algorithm.

1.
We define a new, 2 2 × n n matrix ′ X as follows. The first n rows of ′ X are the rows of X followed by zeros in places 1 2 + , , n … n. The next n rows of ′ X are defined as follows. The element , We are interested in the quarter corresponding to C , i.e. in the submatrix [ The runtime remains as the runtime of Matoušek's algorithm.
We will use the above observation in order to solve the two-sensor problem.
we define an × n n matrix X in the following way: After we build the matrix X , we apply an algorithm for observation 1 with (1 1 1

Future work
In this paper, we present an efficient algorithm for covering a given path by two sensors. A challenging vein for future work is to consider approximations for the k -sensor problem, where 2 > k . The k -sensor problem, for general k , is NP-complete [14].