TIME-SYNCHRONIZATION IN UNDERWATER SENSOR NETWORKS

KULURKAR P.G.¹*, YOGADHAR PANDEY^2
1SIRT, Bhopal, MP, India.
²Dept. of CS & E., Bhopal, MP, India.
* Corresponding Author : pravinkulurkar@gmail.com

Received : 21-02-2012     Accepted : 12-03-2012     Published : 19-03-2012
Volume : 2     Issue : 1       Pages : 21 - 24
Bioinfo Sens Netw 2.1 (2012):21-24

In This Paper we Propose on Time-Synchronization underwater sensor-network. We use the Basic Time-synchronization free localization technique for small area. Same technique used In Large scale localization in under water sensor for large area. We then introduce a localization scheme specifically designed for large scale underwater sensor networks. The proposed localization scheme does not relies on time-differences of arrival (TDoA) measured locally at a sensor to detect range differences from the sensor to three anchors that can mutually hear each other. We consider variations in the speed of sound and analyze the performance of the proposed scheme in terms of the number of localized nodes, location errors, and the number of reference nodes. Considering that depth information is typically available for underwater sensors, we transform the 3D underwater positioning problem into its two-dimensional counterpart via a projection technique.

Underwater Sensor Networks (UW-SNs) consist of a number of sensors and vehicles(Unmanned Underwater vehicle(UUV), Autonomous Underwater Vehicle (AUV), etc.) which perform collaborative monitoring tasks over a given area. Relatively easy deployment, maintenance and low cost make UWA-SNs an ideal solution for a variety of applications in the complex underwater environment, such as disaster prevention, undersea exploration and assisted navigation.
Almost all underwater sensor network applications require position information. Unfortunately, location discovery of vehicle/sensor is difficult in environment. Propagation delay, motion induction Doppler shift, phase and amplitude functions, multi-path interference etc., are present in underwater environment and complicate location measurement. Global positioning System (GPS) do not propagate well in water.
Some approaches for terrestrial sensor network Localization includes the received signals strength(RSS), time of arrival (ToA), and angle of arrival(AoA). Many of these approaches are degraded in underwater environment due to channel variations, bandwidth constraints and underwater vehicle sensor mobility. For example ,the Doppler shift from mobility adversely affects the (AoA) Algorithm and distance and frequency dependent underwater signal loss make RSS-based estimation results imprecise. The accuracy of RSS based localization varies with the bandwidth of signals and signals to the noise ratio at the receiver.
Our research is motivated by the following three observation (i) Underwater sensors typically have depth information available through either a pressure sensor or techniques (ii) GIB (GPS Intelligent Buoys) can be exploited as on the sea surface. It is often not feasible to deploy anchor nodes or especially for deep ocean environment. (iii) Precise time-synchronization is difficult to achieve in underwater environments due to long propagation delays and variances in sound velocity caused by water temperature and salinity.
In this paper, we investigate underwater localization via projection. Our major contributions can be summarized as follows: (i) we outline a projection based localization method that requires no time-synchronization among sensors and anchors when at least three anchors can mutually hear each other; (ii) we devise a localization scheme employing the above method that can iteratively localize large scale underwater sensor network without the requirement for time-synchronization (iii) we evaluate the performance of the proposed scheme when the speed of sound varies in sea-water.

Various papers have been written on sensor location discovery in indoor and outdoor sensor networks. Underwater acoustic localization techniques can be broadly classified into two categories: range-based and range-free. Range based techniques measure or estimate distances or angles to a small number of anchor nodes via ToA/TDoA or even network connectivity, and then apply triangulation or multi-lateration to transform ranges into coordinates. A sufficient and necessary condition for range based localizability is proposed .This work also proves the equivalence in localizability between Distributed and centralized implementations of geometric localization methods. Range-free techniques explore the local topology and derive the position estimate from the locations of the surrounding anchor nodes. Range-based techniques generally provide better position accuracy than range-free techniques.
An area-based range-based under Water positioning (ALS) ALS relies on anchor nodes transmitting unique signals at various power levels to partition the sensor field. A vehicle/sensor receives and decodes signals of sufficient strength. The vehicle/sensor then reports the lowest strength signals received from anchors to a central server. The central server determines which partition the node reside in based on the set of signals received.
Network connectivity can be exploited for range estimation if there is no direct communication between anchor nodes and sensors. In authors propose three range detection methods based on network connectivity: DV-hop, DV-distance, and Euclidean. DV-Hop estimates distance to anchor nodes by counting the number of hops and using an average hop distance estimate. DV-distance replaces hop counts with summed distance estimates based on received signal strength. Euclidean calculates distances to anchor nodes using range estimates to neighbouring nodes and the Pythagorean theorem. The paper’s comparison study shows Euclidean performs better in anisotropic topologies with the tradeoff of more computation and communication.
Range-based underwater localization requires either long-range or short-range anchors. Since a short-range beacon covers a smaller space, a larger number of anchor nodes are required increasing deployment cost. In PARADIGM vehicles interrogate anchors and measure round trip times from anchor responses to find their location for navigation. The PARADIGM network can alternatively find a vehicle by interrogating its transponder and computing its position based on the arrival times of the responses at the anchors. Motivated by terrestrial GPS, GIB also measures time of arrival of a vehicle beacon at a set of anchors. GIB has the disadvantages of requiring vehicle clock synchronization with anchors and processing by a centralized server.
We concentrate on range-based localization in this paper to achieve better accuracy. Acoustic ranging is the preferred ranging method in underwater environments. Network time-synchronization and the speed of sound are two key requirements in acoustic ranging.

In this section, we will first brief introduce the underwater projection technique proposed by which depth information can be employed when only three anchors are available.
We then detail our design of the basic positioning method termed BSFL, which stands for Basic time Synchronization-Free Localization. A projection is a mapping of the anchor nodes to the horizontal plane of the to-be-localized node. The projection is non-degenerative if and only if no two anchors have the same X and Y coordinates.
The task of localizing the node S in a three-dimensional space can be [Fig-1] presents an example of the projection technique. Let A, B, C be three anchors at (xa, ya, za), (xb, yb, zb), and (xc, yc, zc), espective-ly, that can mutually hear each other. Let S be the to-be-localized node that can hear the beacon messages from A, B, and C. If we project the three beacons onto the horizontal plane containing S, we will obtain three virtual anchors A’, B’, and C’, which are located at position (xa, ya, zs), (xb, yb, zs), and (xc, yc, zs), respectively. Since this projection is non-degenerative (no two of A, B, C have the same x and y coordinates), we successfully transform the 3D underwater localization problem into a problem of localizing S in a horizontal plane with virtual anchors A, B, and C, The projection distances from S to the three virtual anchors can be computed by d_si ‘=√ d_si^2- (z_s- z_i)² (1)
where i ∈ {a, b, c}. To apply trilateration localization to compute (xs, ys), all the three projection distances are necessary and therefore we must compute dsi, i ∈ {a, b, c}, according to Eq. (1).
In the following, we detail the design of BSFL. BSFL consists of two steps. The first step detects the differences in signal arrival times from three anchor nodes. These time differences are transformed into range differ-ences from the underwater vehicle/sensor to the virtual anchor nodes. In the second step, trilateration is performed to transform these range estimates into coordinates.
Given the locations (xa, ya, zs), (xb, yb, zs), and (xc, yc, zs), of anchor nodes A,B,C respectively, we are going to determine the location (xs, ys, zs) of sensor S as shown in fig.1 where the be known. Let dij the distance Between i and j, where i, j, where i, j ∈{a,b,c,s} representing the three anchor nodes and the sensor S we have
d_ij= √(x_i-x_j)²⁺(y_i-y_j)²⁺(z_i+z_j)² (3)
The first step of BSFL computes the range differences between d_sa, d_sb, d_sc.

Let A be the master (golden anchor) node, which initiates a beacon signal every T seconds. Each beacon interval begins when A transmits a beacon signal. Consider any beacon interval i, assume sensor S, anchor nodes B and C, receive A’s beacon signal at times ti1, tib, and tic, respectively.
At time ti b which is ≥ tib, B (silver anchor) replies to A with a beacon signal conveying information ti b – tib = Δtib. This signal reaches S at time ti2. After receiving beacon signals from both A and B, at time tic , C (bronze anchor) replies to A with a beacon signal conveying information ti_ c −tic = Δtic. This signal reaches S at time ti3. Based on triangle inequality,
ti1 < ti2 < ti3. Let Δti1 = ti2 − ti1, Δti2 = ti3 − ti1,
we obtain
dab + dsb − dsa + v · Δtib = v · Δti1 (4)
dac + dsc − dsa + v · Δtic = v ·Δti2 (5)
which gives
dsb = dsa + v · Δti1 − dab − v · Δtib = dsa+ki1 (6)
dsc = dsa + v · Δti2 − dac − v · Δtic = dsa + ki2 (7)
where dsa, dsb, and dsc are positive real numbers, v is the sound velocity. which we will discuss later in this paper, and
ki1= v · Δti1 − v · Δtib – dab (8)
ki2= v · Δti2 − v · Δtic – dac (9)
Averaging ki1, and ki2 over I intervals gives
K1= V/I[∑(Δti1 − Δtib)] – dab (10)
K2= V/I[∑(Δti1 − Δtic)] – dac (11)
We are going to apply projection and trilateration to compute the coordinates(xs,ys) for sensor S.
Step 2: Location Computation.
From Eqs. (4), (5), (8), and (9), we have
dsb =dsa+k1 (10)
dsc = dsa + k2 (11)
The effectiveness of BSFL depends on the feasible space where dsa has a unique positive root. A sensor can be uniquely localized if it resides in the feasible space of the three [Fig-2] . demonstrates the feasible space of three anchors located at (0, 0, 0), (0, 50, 0), and (50, 0 0), respectively.
Although BSFL provides several desirable features for 3D underwater localization, it can only be applicable to sensors that reside in the feasible space of three anchors that can mutually hear each other. Therefore BSFL does not scale well to large underwater networks. In the following section, we introduce a new scheme in which sensors with resolved location information become anchors such that more sensors can get localized iteratively.

In this section, we design LSLS (Localization Scheme for Large Scale) that utilizes BSFL as a prime method to localize large scale underwater networks while retaining the nice features of BSFL such as free of time synchronization.

The major design motivation of LSLS is to overcome the constraints of BSFL, which requires that the to-be- localized node reside in the feasible space of three anchors that can mutually hear each other. Since we target large scale underwater sensor networks, LSLS must be distributed.
A distributed implementation is necessary for a large-scale localization scheme because global information collection and Distribution is costly, and central processing may not provide robustness or meet real-time requirements.
Additionally LSLS should avoid the use of anchors on the sea floor as their deployment is difficult. Furthermore LSLS must take into consideration the fact that underwater sensor networks are usually sparsely deployed. LSLS is an iterative procedure in which a sensor whose location is determined will become a candidate anchor in the next round. To reduce communication cost and preserve privacy. LSLS will not ask all candidate become real reference nodes.

LSLS includes three phases: Sea Surface anchor localization, iterative localization and the complementary phase. In the first phase, BSFL is employed to localize the direct localizable area where nodes can be localized by the initial group of anchors. In second phase, certain localize bed nodes will be selected to serve as reference nodes, and BSFL will be applied to localize the new localizable area covered by anchors and new reference nodes. The selection of new reference nodes and the localization procedure are repeated iteratively. At each round LSLS will choose as small number of reference nodes and as possible, such that most of the nodes are still passive. If a node fails to be localized in the first two phase. It can initiate a location request in the third phase. A new group of anchors will then be selected to localize the to-be-localized area of the unlocalized node. The Selected groups of anchors will cover as large to-be-localized area as possible to preserve communication overhead.
Table summarizes the major parameters utilized by LSLS. Assume Ra and Rs are both roughly known prior to the deployment and Ra>=Rs.

In this phase three surface anchors in communications range send their beacons messages sequentially as described in BSFL. A node is localized if a unique location solution is obtained. A localized node records the center of the three surface anchors in Acenter and sets itself a Active node if it intends to become a reference node and its distance to the Acenter which is defined as Dcenter is larger than Ra-Rs, such that the localization coverage could be increased in the next phase by adopting this node as a reference.

In this phase active nodes self-organize into anchor groups where three active nodes in communications range becomes new anchors to localize unlocalized node. Once a node is localized, it can become an active node and join the process of anchor group construction.
At the beginning of each round, every active node is a gold candidate that might work as a gold anchor in BSFL. A gold candidate initiates a timer starting from(Rs-Dcenter)2ms. If it does not receive an anchor messages. This method for setting the timer helps maximize incremental coverage as the furthest active child of an anchor group will be selected such that coverage overlap with original and new anchor group is minimized. If a gold candidates receives a gold messages before its timer expires, it notes the gold anchor locations becomes a silver candidate. A silver candidate immediately initiates a timer starting from(Rs-Dgolden)2 ms, where Dgolden is the distance between the silver candidates and its golden anchor. If a silver candidates timer expires before receiving a silver or bronze messages. It will assume the role of silver anchor and send an announcement. If a silver candidate receives a silver messages before its timer expires, it becomes a bronze candidate and initiates a timer starting from(Rs-Dsilver)2ms. Where Dsilver is the distance between the bronze candidate to its silver anchor. A bronze candidate assume the role of bronze anchor message, otherwise it remains silent for the round.

[1] Akyildiz I.F., Pompili D. and elodia T. Journal of Ad Hoc Networks.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[2] Cheng W., Teymorian A.Y., Ma L., Cheng X., Lu X. and Lu Z. (2008) IEEE Infocom, 798-806.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[3] Chandrasekhar V. and Seah W.K. (2006) IEEE OCEANS Asia Pacific Conference.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[4] Bechaz C. and Thomas H. (2000) 5th Europe Conference on Underwater Acoustics.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

Fig. 1- The sensor S will measure the arrival times of beacon signals from anchor nodes A, B and C. B’s transmission will start after it receives A’s beacon signal; C’s transmission will start after it receives both A and B’s beacon signals. S will also receive the turn-around delay information from B and C. This procedure will be repeated once every T seconds reduced to localizing the node in a two-dimensional space

Fig. 2-