A Novel Approach for Localization in Sensor Network

A Novel Approach for Localization in Sensor Network

Anil Kumar Biswal

Department of Computer Science Udayanath Autonomous College of Science &

Technology,Odisha,India

Milan Samantaray

Department of BSc(ITM) Udayanath Autonomous College of Science &

Technology,Odisha,India

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. Many localization algorithms sited the position of nodes by using anchor nodes. And it focus on increasing the accuracy in position estimation by using different heuristic-based or mathematical techniques. In this paper, we propose a new approach Absolute Relative Hybrid Positioning with Nearest 3 Anchor Selection(ARHP-N3AS). Again we use Ad-hoc positioning (Nearest-3) method to select good anchor nodes and analyze the feasibility for the proposed method.

Keyword: Sensor network, multihop

1. INTRODUCTION

   Wireless sensor networks have wide range of application including environment monitoring, habit monitoring, condition based monitoring, military applications, disaster management, etc. Nodes require to know their real physical positions in order to target object or track unknown behavior in the system. it is obviously infeasible to have nodes equipped with special hardware to obtain precise location due to cost, space, weather or other constraints.. Applications in a variety of fields such as environmental monitoring, military purpose and gathering sensing information in inhospitable locations. A general setup of a wireless sensor network consists of a large number of sensors randomly and densely deployed over a wide area. Each sensor node is capable of only a limited amount of processing. But when coordinate with the information from other nodes, they have the ability to measure a given physical environment in great detail. In a typical wireless sensor network, each node has a microprocessor and small memory for signal processing and task scheduling. Each node is also equipped with one or more sensing devices to sense acoustic, magnetic, and infrared, temperature or light known as sensing modalities. Within this range the communication is by broadcast. The advantage of wireless sensor networks over traditional centralized networks is in terms of increased energy efficiency in communications by means of the multi-hop topology. The amount of energy consumed can be minimized through local collaboration among sensor nodes, duplicate data suppression, or invoking only the nodes that are relevant. However, the greatest advantages

   of networked sensing are in improved robustness and scalability. The importance of localization in sensor network lies in the fact, that the data that has to be exchanged bears no meaning if it is not stamped with time and location. In order to track and detect objects the physical position of each sensor should be known in advance for identifying the position of detected objects. However, sensor in most cases are deployed without knowing their physical position in advance. In cases of ad- hoc networks, certain distance-based algorithms can be implemented to find out the location information of a particular sensor. Moreover, for applications such as inventory management and manufacturing logistics, localization and tracking of sensors are the primary goals of sensor networks. Localization of sensor nodes has many uses such as beam forming for localization of targets and events, geographical forwarding geographical addressing.

   This paper organized as follows:

   In section 2, we discussed the overview of sensor network. In section 3, we discuss the related work. In section 4, we presented the our proposed novel approach. Lastly, section 5, concludes the work with its future scope.

2. OVERVIEW OF SENSOR NETWORK

   In sensor network the sensor nodes are usually scattered in a field randomly as shown in Fig 1.

   Fig- 1

   Each of these nodes collects data and has the capability to route back the data to the sink by multihop architecture. The sink may communicate with the task manager via Internet of satellite. The design, sated above is influenced by several factors, such as fault tolerance, scalability, production cost, operating environment, sensor network topology, hardware constraints, transmission media and power consumption.

   Fig- 2

   A sensor node is made of four basic components as shown in Fig. 2: a sensing unit, a processing unit, a transceiver unit, and a power unit. They may also have additional application-dependent components such as location finding system, power generator, and mobilizer. Sensing units are usually composed of tow subunits : sensors and analog-to-digital converters (ADCS). The processing unit, which is generally associated with a small storage unit, manages the procedures that make the sensor nodes collaborate with the other nodes to carry out the assigned sensing tasks. A transceiver unit connects the node to the network. One of the most important components of a sensor node is the power unit. Power units may be supported by power scavenging units such as solar cells.

   There are also other subunits that are application- dependent. Most of the sensor network routing techniques and sensing tasks require knowledge of location with high accuracy. Thus, it is common that a sensor node ahs a location finding system. A mobilize may sometimes be needed to move sensor nodes when it is required to carry out the assigned tasks.

   Sensor nodes are densely deployed either very close or directly inside the phenomenon to be observed. Therefore, they usually work unattended in remote geographic areas. They may be working in the interior of large machinery, at the bottom of an ocean, in a biologically or chemically contaminated field, in a battlefield beyond the enemy lines, and in a home or large building.

   The wireless sensor node, being a microelectronic device, can only be equipped with a limited power source (< 0.5 Ah, 1.2 V). In some application scenarios, replenishment of power resource might be impossible. Sensor node lifetime, therefore, shows a strong dependence on battery lifetime. In a multihop ad-hoc sensor network, each node plays the dual role of data originator and data router. The malfunctioning of a few nodes can cause significant topological changes and might require rerouting of packets and reorganization of the network. Hence, power conservation and power management take on additional importance. The main task of a sensor node in a sensor network is to detect events, perform quick local data

   processing, and then transmit the data. Power consumption can hence be divided in three domains : sensing, communication and data processing.

   1. Localization and Tracking

      Most research works till now has targeted to closely co- located wireless ad-hoc networks. Such work has tended to overlook the potential importance of wide area sensor systems heterogeneous collections of Internet-connected sensor devices. It can enable to connect a rich collection of sensor devices such as cameras, microphone, infra red detectors etc. However, the challenges in wireless sensor network comprises of scalability, robustness/manageability. The tracking of mobile targets and phenomena is a canonical problem in sensor networks. A related significant problem is that of localizing the sensor nodes themselves in case of random or ad-hoc deployment. We have used popular Bayesian algorithms that exploit the redundany of dense sensors to correct for measurement errors that may be likely in inexpensive devices.

      In most of the cases, sensor nods are deployed in an ad-hoc manner. It is up to the nodes to identify themselves in some spatial coordinate system. This problem is known as the Localization problem. In short, it is nothing but providing coordinates to the vertices of a network of nodes based on some constraints of the edge lengths between the corresponding vertices. The immediate solution that can come into mind is the GPS system. But GPS has certain drawback. An administrator has to manually provide coordinates to the devices. Moreover, it is expensive, power consumption is very high and there are limitations to line to sight conditions. So sensor nodes should have other means of establishing their positions and organizing themselves into a coordinate system without relying on the existing infrastructure. Today most of the sensor node operating networks use the trilateration / multilateraion techniques recursively. One way of considering sensor networks is taking the network to be organized as a hierarchy with nodes in the upper level being more complex and already knowing their location through some technique, GPS, as for example. One of these nodes initializes flooding and sends their own positions to other nodes whose positions are already known. These nodes with positions known are referred to as anchor nodes. With the help of these anchors the positions of other unknown nodes are estimated by using the information with low message loss from the anchors. A simple technique would be to calculated its position as the centric of all the locations it ahs obtained. This is called as proximity based localization. It is quite possible that all nodes do not have access to the anchors. In this case, the nodes which have obtained positions through proximity based localization themselves act as anchors to other nodes. This process is called iterative multilateration [9]. But one drawback of iterative multilateration is that leads to accumulation of localization error. We briefly discuss about the trilateration

      / multilateration technique [8] which allows us to find a location if its distance from other already known locations are as the radius of a circle and can consider himself to be

      present anywhere in the circle around the anchor position. Likewise, two more nodes are considered. Now he knows at which of the intersecting points he is one because only one of them will intersect with the third circle also. The same principle is extended to 3-D space. In this case, spheres instead of circles are used and at least four spheres are required. When localization technique using anchors is used, an important question would be to how many anchors to be initially deployed. Too many anchors would result in self-interference among the anchors while too less number of anchors would mean that many of the nodes would have to depend on iterative multilateration. There are other localization techniques available which are classified as range based or range free localization.

3. RELATED WORK

   There have been many efforts on the sensor positioning problem. They mainly fall into one of the following four classes [3] or the combination of them.

   The first class of methods improves the accuracy of distance estimation with different signal techniques. The Received Signal Strength Indicator (RSSI) technique was employed to measure the power of the signal at the receiver. Relatively low accuracy is achieved in this way. However, because of its simplicity, it is widely used in previous research. Later, time of arrival (TOA) and time difference of arrival (TDoA) are used by savvides et al. and Priyantha et al. to reduce the errors of range estimation, but this require each sensor node being equipped CPU with powerful computation capability. Recently Niculescu et al. used Angle of Arrival (AoA) to measure the position sensors. The AoA sensing requires each sensor node installed with antenna array or ultrasound receivers.

   The second class of positioning methods relies on a large amount of sensor nodes with positions known densely distributed in a sensor network. These nodes with positions known, which are also named as beacons or anchor nodes, are arranged in a grid across the network to estimate other nodes positions nearby them.

   Given :

   • A set of N points in the plane (nodes coordinates)

   • Coordinates of 0 < K < N points (anchors)

   • M < N x (N-1) distances between pairs of points

   Find : Positions of all N K points of unknown coordinates

   The third class of methods employ distance vector exchange to find the distances from the non-anchor nodes to the anchor nodes. Based on these distances, each node can estimate its position by performing a trilateration or multilateraion. The performance of the algorithm is deteriorated by performing a trilateration or multilateraion. The performance of the algorithm is deteriorated by range estimation errors and inaccurate distance measures, which are caused by complex terrain and anisotropic topology of the sensor network. Savarese tried to improve the above approach by iteratively computing. However, this method adds a large number of communication cost into the algorithm and still cannot generate good position estimation in certain circumstances. Moreover, the accuracy of this class of algorithms relies on the average radio range estimation, and it tends to deteriorate when the topology of sensor network is anisotropic. The complexity of area and terrain lead to different signal attenuation factors and radio ranges in the field.

   The last class of methods locally calculates maps of adjacent nodes with trilateration or multilateration and stitches these maps together. The nodes update their positions with this new information and thereby estimate their physical or relative positions. The performance of these algorithms depends heavily on the average radio range estimation and suffers from the cumulative range error during the map stitching.

4. OUR PROPOSED APPROACH

   In Simple Hybrid Absolute Relative Positioning (SHARP), a relative localization method (M1) is used to relatively localize Nr reference nodes. Then, an absolute localization method (M2) uses these Nr nodes as anchors to localize the rest of the nodes. Choosing Nr, M1 and M2 gives a wide range of performance-cost tuning. Extensive simulations have been carried out using the multi- dimensional scaling (MDS) method [28] as M1 and the Ad- hoc Positioning System (APS) method [20] as M2.

   1. Localization using ARHP-N3AS

      In sensor networks, two types of localization is visible : relative and absolute. For the relative case, sensor nodes use wireless communication to measure distances among themselves using different techniques. These distance measurements form a set of constraints that can be used to estimate the positions of nodes based on some coordinate system. For the absolute positioning, this coordinate system is given. To transform a relatively positioned network into an absolutely positioned one, some nodes should have their positions known relative to the new absolute coordinate system [29]. These nodes called anchors start off knowing their positions. For a 2-D network, three anchors are needed, while for 3-D case, four anchors are required.

      We present a new approach to relative localization which is a derivation of the very simple technique for node localization commonly known as SHARP (Simple Hybrid Absolute Relative Positioning). Unlike SHARP [6] our approach aims at finding the location of nodes in anisotropic network using the traditional distributed relative localization techniques. We name our method as Localization using Absolute-relative hybrid positioning with Nearest three anchor selection (ARHP-N3AS) for Anisotropic Sensor Networks. The goal is to reach the required point of operation in terms of accuracy, less computation and cost.

   2. p>ARHP-N3AS : A distributed approach

      In this section, we describe the hybrid method that we propose : absolute Relative hybrid Positioning with Nearest Three anchor Selection. ARHP-N3AS consists of three phases as in the SHARP [6] approach : selecting reference nodes (Pinitial), localizing reference nodes (P1), and localizing non-reference nodes (P2). In the first phase a set of sensor nodes that we call reference nodes are to be selected. In the second phase we use a relative distributed localization method to localize the reference nodes selected already in the first phase. Finally, an absolute localizing method is to be used in the third phase, to localize the remaining of the non-reference nodes. Three parameters are associated with the design of ARHP-N3AS. First, how many nodes to be localized using P1 and how many to localize using P2. Secondly, at least how many number of nodes are required to be selected as reference nodes. Finally, the selection mechanism for the reference nodes. Determining these parameters to reach the required point of operation depends on the performance and cost of both the methods P1 and P2.

      Pinitial: selecting Reference Nodes

      Our approach starts with Pinitial where reference nodes are selected and relative positioning is initialized thereafter. There are two main approaches to selection of reference nodes. Either nodes can be selected randomly or along the outer perimeter of the network .to choose nodes randomly existing algorithms tend to select nodes with the smallest IDs in a distributed fashion.

      We purpose to select four nodes with smallest IDs perimeter, roughly at the corners of the network using only distance based measurements, thereby extending the algorithm for outer selection distributed [30].let Nr nodes are selected where we assume that Nr=2m={n1,n2,n3,n4}, for some integer 2<=m<=lg N. we also assume dij is the shortest path distance between nodes ni and nj.

      Algorithm 1

      1. Initialize a vector p of size Nr to be empty.

   1. Select a node at outer right denoted by n0.This can be done by selecting a node with the smallest ID at the outer right area where nodes are deployed randomly.

   2. Select a reference node n1 such that d01 is maximized. p[1] n1.

   3. Select a reference node n2 such that d12 is maximized .p[3] n2.

   4. Select a reference node n3 such that d (13+d23) is maximized. p[2] n4.

   5. Select a reference node n4 such that d34 is maximized. p[4] n4.

   7 14.

   8 Return p

   The terminology used in this algorithm as follows: P1: Localizing reference nodes and the nodes along the path

   • In this phase a relative localization method is used to relatively localize the reference nodes selected in the phase Pinitial.

     We implement the distributed algorithm for localization of reference nodes in distributed system. But before that we have to implement another algorithm to find the coordinates of the reference nodes and distance between each of them.

   • Initialize

   • We install a GPS enabled node, commonly known as anchor in the anisotropic network located roughly centrally.

   • This anchor then initializes flooding and invent routes based on RSSI sensing to all the reference nodes.

   • Then using the total number of hop counts and the average radio range we can find some distance constraints, which can calculate the coordinates of the reference node starting from the outer right with respect to the anchor node. Then this reference node in the reverse path routes it coordinates information to other reference node assisted by the intermediate anchor node.

   • Continue this process until the coordinate all the reference nodes are obtained.

     Then compute multilateration technique between the minimum of two-reference nodes n1 and n2 and the anchor node. Thus, we are able to find the distance between the reference nodes n1 and n2.

   • Similarly we continue this process to calculate the distances d23,d34,and d41

   • End

   P2: Localizing remaining nodes

   The phases Pinitial and p1, results into a set of nodes with known coordinates according to some coordinate system. In this phase the rest of the nodes are localized using absolute localization method p2 where the localized nodes acts

   As anchors and provides an aid to localize the rest of the nodes in the anisotropic topology. Selection of anchors to find the accurate positions of unknown nodes is an important criterion in this phase. We demonstrate that using all anchor nodes that does not give the most precise position. Using a subset of anchor nodes is better than all anchor nodes. We then identify the criteria for selecting good anchors to achieve more accurate position estimation in anisotropic sensor networks. We use Ad-hoc positioning (APS)[20] Method for p2, a distributed and hop-by-hop localization approach to estimate node positions in anisotropic sensor networks.

   Algorithm 2

   1. First anchor nodes initialize flooding and send their positions radio signals. All nodes in the network get distances in hops to through the distance vector exchange.

   2. Each anchor node ni receives the positions(aj,bj),where j=1,.Nc-1,of all Anchor nodes and computes the distances hi between each pair of anchor nodes.

   3. Each anchor node then estimates an average size of one hop, which is then deployed as a correction Ci,

      NC 1

      i

      i

      2

      2

      2

      2

      ai a j b bj

      system in Eq. (1) is solved using least-squares maximization.

5. CONCLUSION

The work discuss in this paper opens up a number of interesting directions that are worth exploring. We mainly focus on implementation of the distributed multidimensional scaling approach as an important method for localization of small number of nodes initially. we also focus in the later stages the impact of selection of good anchors to localize rest of the nodes straightaway. Carefully selecting less but useful anchor nodes should be advantageous to the APS method especially in anisotropic sensor networks where nodes are unevenly distributed. in the paper we demonstrate that including all anchor nodes in the original APS, or including only best-3 anchors does not give the most precise estimation of position of nodes when compared to the nearest-3 APS approach that we propose. Though our approach aims at choosing the nearest 3 anchors with respect to each individual nodes yet creating an intelligent method for localization that could select sufficient number of good anchors to increase the overall accuracy of position estimation being less susceptible to measurement errors or possible errors will continue to be an interesting challenge in our future investigation.

REFERENCES

1. W. Torgerson. Multidimensional scaling I. theory and method

   Psychometrika

2. I.Borg and p.Groenen, Modern multidimensional scaling theory and applications,Springer,1997.

3. Xiang Ji, Hongyuan Zha, sensor positioning in wireless ad-hoc sensor networks using multisimensional Scaling, IEEE INFOCOM 2004.

4. Ahmed A.Ahmed, Yi shang, and Honchi shi, Variants of multidimensional scaling for node local; ization, IEEE 2005.

5. Jose A.costa, Neal patwari and Alfred o. Hero III, Distributed weight-multidimensional scaling for node in sensor networks, ACM Journal Name, Vol.V, No.N, June 2005.

   Ci

   j 1

   NC 1

6. Ahmed A.Ahmed, Yi Shang, and Honchi Shi, SHARP:A new approach to Relative localization in wireless sensor networks, IEEE 2005.

7. King-Yip cheng, Vincent Tam and King-shan Lui, Improving

   hi j 1

   1. For each unknown node, nk, computer the hop distance Pkj,j=1,., Nc, to the Nearest three anchor nodes. Then perform triangulation based on all anchor nodes to determine position (xk,yk.

   2. A system of quadratic equations of two variables is formed.

      (xk-aj)2+(yk-bj)2=(cspkj)2. (1)

      For j=1,., Nc, where ns is the closest reference node to node nk.

   3. The system of equations in Eq. (1) is linearized by substracting one equation, e.g, the first one from the rest.

      2(a1-aj)xk+2(b1-bj)yk+aj2+bj2-a12- b12=(cspkj)2-(cspk1)2(2)

      For j=2,, Nc.

   4. The linear system in Eq. (2) is solved. Then, using the solution as the initial point, the nonlinear

   APS with ANCHOR Selection Anisotropic Sensor Networks ,IEEE 2005.

8. Archana Bharathidasan, Vijay Anand Sai Ponduru Sensor networks: An Overview, university of California.

9. Leonidas Guibas, Feng Zhao, wireless sensor network An information processing approach, Elsevier press

10. Ian F.Akyildiz, Weilan su, Yogesh sankarsubrasubranium. and Erdal Cayirci, Georgia Institute of technology, A survey on sensor networks, IEEE 2002.

11. F.L.Lewis, Automation and Robotics research institute, The university ofTexas, Wireless sensor networks.

12. Feng Zhao,J ie liu, Elaine Cheong, Prabal Dutta, Kamin whitehouse, Networked Embedded Computing Group, Microsoft Research, Wireless sensor networks: seamless computing across the physical and pc worlds, MSR faculty summit talk, August 2,2004

13. Deborah Estrin & Mani srivastava, UCLA, and Akbar Sayeed, University of Wisconsin, wireless sensor network, MOBICOM 2002.

14. G.Hoblos, M.staroswiecki, and A.Aitouche, optimal Design of fault tolerant sensor networks, IEEE Intl.conf.cont.apps.,Anchorage,AK,sept.2000,

15. Bulusu et al, Scalable coordination for wireless sensor networks: self-confioguring localization Systems, ISCTA 2001,Ambleside,U.k,JULY2001.

16. j.m.Rabaey et al,pico radio supports Ad hoc ultra-Low power wireless Networking, IEEE Comp.Mag,2000.

17. C.Intanagaonwiwat, R.Govindan, and D.Estrin, Directed Diffusion :A scalable and Robust Communication paradigm for sensor network, Proc, ACM Mobicom00,Boston,MA 2000.

18. N.Bulusu, J.Heidemann, and D.Estrin, GPS-low-cost outdoor localization for very small devices, IEEE personal Communivcations,pp.28-34,2000.

19. L.Doherty, K.pister, and L.Ghaoui, Convex position estimation in wireless sensor networks, in proceeding of IEEE Infocomm, 2001.

20. D.Niculesu and B.nath, Ad-hoc positioning system(APS),in proceedings of IEEE Globecom,2001.

21. A.savvides, C.C.Han, and M.B.Srivastava, Dynamic fine-grained localization in ad-hoc wireless sensor networks, in proceedings of ACM Mobicum,2001.

22. A.savvides, H.park, and M.B.Srivastava. The bits and flops of the N-hop multilateration primitive for node localization problems, in proceedings of WSNA,2002.

23. C.savarse, J.Rabaey, and k.Langendoen, Robust positioning algorithms for distributed ad-hoc wireless sensor networks, in proceedings of USENIX Technical Annual Conference,2002.

24. R.Nagal, H.Shrobe, and J.Bacharach, Organising a global coordinate system from local information on ad-hoc sensor network in proceedings of IPSN,2003.

25. T.He, C.Huang, B.M.Blum, J.A.Stankovic, and T.AbdelZaher, Range-free localization schemes for large scale sensor network in proceedings of ACM Mobicum,2003.

26. V.rayker, I.Kozintsev, and R.lienhart, position calibration of audio sensors and actuators in a distributed computing platform, in proceedings of ACM Multimedia,2003.

27. Y.shang, W.Rumi, and Y.Zhang. Localization from mere connectivity, Proceedings IEEE Infocomm,2004.

28. Y.shang, W.Rumi. Improved MDS-based localization. In

    proceedings of IEEE Infocom,2004.

29. C.Savarse, J.Rabaey, and J.Rabaey, and J.Beutel Locationing in distributed ad-hoc wireless. Sensor networks .In proceedings of ICASSP, pages 2037-2040,Salt Lake, UT, May 2001.

30. N.B.Priyantha, H.Balakrishnan,E.Demaine, and S.Teller.Anchor- free distributed local;ization in sensor networks.technical report 892,MIT Laboratory for Computer Science, April 2003