Sensor network location papers

Archana Bharathidasan, Vijay Anand Sai Ponduru

Abstract: Sensor networks are dense wireless networks of small, low-cost sensors, which collect and disseminate environmental data. Wireless sensor networks facilitate monitoring and controlling of physical environments from remote locations with better accuracy. They have applications in a variety of fields such as environmental monitoring, military purposes and gathering sensing information in inhospitable locations. Sensor nodes have various energy and computational constraints because of their inexpensive nature and ad- hoc method of deployment. Considerable research has been focused at overcoming these deficiencies through more energy efficient routing, localization algorithms and system design. Our survey attempts to provide an overview of these issues as well as the solutions proposed in recent research literature

• A different approach towards localization has been adapted in [10]. Here, the task of determining the position of sensor node is treated as a mathematical problem. The nodes can be treated as nodes of a graph and the connections between them can be treated as edges. Also, the placement of the nodes is constrained by certain requirements like line of sight etc. Hence, the problem becomes similar to solving an LP (Linear Problem) with a set of equations and a set of constraints.
  • idea 1: relaxing technique, exponentialize a distance to distinguish direct signals and the reflexed ones.
    Edit

    Locating the Nodes - Cooperative localization in wireless sensor networks
• Traditional localization techniques: GPS, LPS (local positioning systems)
  • GPS:
    • cost and energy prohibited.
    • not robust to jamming for military applications.
    • limited to outdoor applications.
  • LPS:
    • high cappablity base station for each coverage area.
    • costly.

Problem: m reference nodes, which know their position through the use of GPS or preconfigured during start up. and n unknown-location nodes.

Nodes capable of high-power transmission MS (cellular mobile station), WLAN can make measurements to multiple reference nodes. Low-capability, energy-conserving devices are lack of energy for long-range communication and may be limited by regulatory constraints or transmit power.

Wireless sensor networks, and localization will be multi-hop (a.k.a. cooperative localization). A location solver will estimate all sensor position simultaneously.

Communication btw. reference nodes and unknown-location nodes as extension to MS, WLAN network. Communication btw. pairs of unknown-location nodes enhances accuracy and robustness of the localization systems. These systems are also known as “cooperative,” “relative,” “distributed,” “GPS-free,” “multihop,” or “network” localization; “self-localization;” “ad-hoc” or “sensor” positioning; or “network calibration.”

Standards in wireless sensor network: Two major sensor network standards are the IEEE 802.15.4 physical (PHY) layer and medium access control (MAC) layer standard for low-rate wireless personal area networks (LR-WPANs) and the ZigBee networking and application layer standard. Also 6LoWPAN.

Sensor location estimation problem from signal processing perspective. Measurement-based statistical models for RSS, TOA, AOA measurements. Assumptions about the measurement model: 1) measurements in a network are independent and from the same family of distribution. 2) the choice of a family of distribution. We tend to subtract from each measurement its ensemble mean and then assume that the error (the difference) is characterized by a particular parameterized distribution (such as a Gaussian, log-normal, or mixture distribution). We then use the measurements to estimate the parameters of the distribution, such as the variance. With this method, one set of parameters can be used to characterize the whole set of measurements.

RSS:

• source of error: multipath signals, shadowing.
• statistical model:

TOA:

• source of error: multipath signals, additive noise.
• statistical model:

AOA: direction to neighboring sensors. Addtion to RSS/TOA.

• Measuring AOA
  • sensor array and array signal processing techniques: node has two or more individual sensors, whose location in respect to the node center are known.
  • Using RSS ration btw. two or more directional antennas.
• Acoustic sensor arrays are natural for many applications. RF antenna arrays [1]
• sources of error: impared by the same sources in TOA.

CRB (Cramer-Rao Bound): [2] [3]

[1] H. Xu, V. Kukshya, and T.S. Rappaport, “Spatial and temporal characterization of 60 GHz indoor channels,’’ in Proc. IEEE VTC Fall, Sept. 2000, vol. 1, pp. 6–13.

[2] J. Ash, Sensor Network Localization Explorer [Online]. Available: http://www.ece.osu.edu/~randy/localization

[3] H.L. Van Trees, Detection, Estimation, and Modulation Theory, Part I. New York: Wiley, 1968.

Abstract: Wireless Sensor Networks have been proposed for a multitude of location-dependent applications. For such systems, the cost and limitations of the hardware on sensing nodes prevent the use of range-based localization schemes that depend on absolute point- to-point distance estimates. Because coarse accuracy is sufficient for most sensor network applications, solutions in range-free localization are being pursued as a cost-effective alternative to more expensive range-based approaches. In this paper, we present APIT, a novel localization algorithm that is range-free. We show that our APIT scheme performs best when an irregular radio pattern and random node placement are considered, and low communication overhead is desired. We compare our work via extensive simulation, with three state-of-the-art range-free localization schemes to identify the preferable system configurations of each. In addition, we study the effect of location error on routing and tracking performance. We show that routing performance and tracking accuracy are not significantly affected by localization error when the error is less than 0.4 times the communication radio radius.

• Centroid Algorithm: N. Bulusu, J. Heidemann and D. Estrin, GPS-less Low Cost Outdoor Localization for Very Small Devices, IEEE Personal Communications Magazine, 7(5):28-34, October 2000.
• DV-Hop D. Niculescu and B. Nath, DV Based Positioning in Ad hoc Networks, In Journal of Telecommunication Systems, 2003.

• area-based, range-free.
• reference nodes as anchors.
• Anchors nodes form triangular regions. A node's presence in/outside of these triangulars allows that node to narrow down in which it can potentially reside.

• Description: The theoretical method used to narrow down the possible area

in which a target node resides is called the Point-In-Triangulation Test (PIT). In this test, a node chooses three anchors from all audible anchors (anchors from which a beacon was received) and tests whether it is inside the triangle formed by connecting these three anchors. APIT repeats this PIT test with different audible anchor combinations until all combinations are exhausted or the required accuracy is achieved. At this point, APIT calculates the center of gravity (COG) of the intersection of all of the triangles in which a node resides to determine its estimated position.

• 4 steps: 1)

Beacon exchange, 2) PIT Testing, 3) APIT aggregation and 4) COG calculation. These steps are performed at individual nodes in a purely distributed fashion.

• pseudo code

Receive location beacons (Xi,Yi) from N anchors.
InsideSet = Φ // the set of triangles in which I reside
For (each triangle Ti ∈
N
(3 )
triangles) {
If (Point-In-Triangle-Test (Ti) == TRUE)
InsideSet = InsideSet ∪ { Ti }
If( accuracy(InsideSet) > enough ) break;
}
/* Center of gravity (COG ) calculation */
Estimated Position = COG ( ∩Ti ∈ InsideSet);

abstract: In this paper we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.

Abstract: We demonstrate a system built using probabilistic techniques that allows for remarkably accurate localization across our entire office building using nothing more than the built-in signal intensity meter supplied by standard 802.11 cards. While prior systems have required significant investments of human labor to build a detailed signal map, we can train our system by spending less than one minute per office or region, walking around with a laptop and recording the observed signal intensities of our building’s unmodified base stations. We actually collected over two minutes of data per office or region, about 28 man-hours of effort. Using less than half of this data to train the localizer, we can localize a user to the precise, correct location in over 95 % of our attempts, across the entire building. Even in the most pathological cases, we almost never localize a user any more distant than to the neighboring office. A user can obtain this level of accuracy with only two or three signal intensity measurements, allowing for a high frame rate of localization results. Furthermore, with a brief calibration period, our system can be adapted to work with previously unknown user hardware. We present results demonstrating the robustness of our system against a variety of untrained time-varying phenomena, including the presence or absence of people in the building across the day. Our system is sufficiently robust to enable a variety of locationaware applications without requiring special-purpose hardware or complicated training and calibration procedures.

1. Construct triangles
2. Test if a sensor in/outside a triangles
3. Estimate the sensor's position inside a triangles: da, db, dc
4. Combine the estimations of multiple triangles
5. Calculate the quality of estimation inside each triangle or train the network to learn from the quality.
6. …

1. math algorithm to estimate position inside a triangle
2. real-life deployments and quality of results

• http://code.google.com/p/etrack/
• http://ductran.org/
• http://www.cs.umb.edu/~cpham
• Literature search:
  • http://arxiv.org/find/all/1/all:+AND+network+AND+localization+sensor/0/1/0/all/0/1