A Dynamic Addressing Protocol on Code Messages for an Underwater Wireless Half Duplex Networks of Autonomous Sensors

International Journal of Wireless & Mobile Networks (IJWMN) Vol. 9, No. 6, December 2017 DOI: 10.5121/ijwmn.2017.9603 43 A DYNAMIC ADDRESSING PROTOCOL ON CODE MESSAGES FOR AN UNDERWATER WIRELESS HALFDUPLEX NETWORKS OF AUTONOMOUS SENSORS Alexander Dikarev 1 , Stanislav Dmitriev 1 ,Vitaliy Kubkin 1 , Arthur Abelentsev 1 1 Underwater communication and navigation laboratory, LLC, Moscow, Russia A BSTRACT This paper presents the new protocol for the organization of dynamic addressing nodes in the underwater wireless networks. In view of the extremely limited frequency band and significant delays inherent in the underwater acoustic data transmission channel, as well as the nonlinearity of the propagation paths of the acoustic signal in water, an approach is proposed for constructing a dynamic addressing protocol based on avoiding collisions at the receiving point. The protocol takes into account the peculiarities of the physical layer of the data transmission and is designed for servicing the network of autonomous non-synchronized nodes. K EYWORDS Network Protocols, Underwater Wireless Network,underwater acoustic communication 1. I NTRODUCTION Underwater sensor networks are increasingly used for monitoring the state of the environment, research on the world ocean [1, 2]. At the same time, the limited nature of their application is mostly related to the conditions of the acoustic propagation medium in water [3], in particular, with a low speed of acoustic signal propagation in the medium, the narrowness of the available frequency band, and the rapidity of the impulse response of the channel. Taking into account the specific environmental conditions, the following tasks were set in the development of the described protocol: • minimize or completely eliminate the possibility of overlapping signals at the receiving point; • ensure minimal identification time (assignment of address) to new nodes of the network; • eliminate the need for time synchronization of network elements; • minimize the energy costs of autonomous network elements; • minimize or completely eliminate the need for retransmission of network and/or data control signals. In most works devoted to this topic [4, 5, 6] special attention is paid to the necessity of time synchronization of network elements, however, the authors are convinced that for the network of underwater sensors this requirement is not critical - most efficiently, in terms of energy consumption for information transfer, apply on-demand transmission, i.e. it is difficult to imagine such tasks in which individual nodes of the network (sensors and/or actuators) would transmit data at their discretion. In the case of on-demand transmission, the problem of overlapping signals at the receiving point is completely solved, but the time for identifying new devices is significantly increased since a network interrogation, in this case, can only be carried out by a full search of the address range. International Journal of Wireless & Mobile Networks (IJWMN) Vol. 9, No. 6, December 2017 44 2. T HE ARCHITECTURE OF THE UNDERWATER SENSOR NETWORK AND THE LEVEL OF ABSTRACTION To describe the synchronization protocol, we introduce the following concepts: access point (AP) is a base station, network arbiter, solving the task of identifying nodes of the network, issuing addresses to nodes. A network node is a specialized device that is interfaced with a sensor and/or an actuator that is a subscriber of the network. The physical channel identifier (PID) is a pair of generating polynomials of pseudo-random sequences (SIP) - synchronizing and informational. The code space identifier (CID) is the range of the values of the transmitted message. A similar implementation of the transmission system on code messages described in [7] and in more detail in [8]. All APs in current water area are synchronized, and receive at the same PID and CID and should be understood as a single AP with a distributed antenna. Assuming, those exact locations of APs are random, as well as locations of nodes. The number of nodes is unknown and can vary in time. The number of possible code combinations C c for one PID is determined by the degree N of generating polynomials as in (1): С  = 2  − 1 (1) Let for assigning addresses a separate physical channel PIDs, in which by default all nodes that have not yet been assigned an address receive reception. From the code range D c = {0..C s }, the subrange of codes D at = {0..C at -1}, where C at = 2 N-2 , and the subrange D aa = {C at ..C aa -1}, where C aa = 2 N-1 . In this case, the elements of the subranges fully correspond to each other with a difference of 1 bit:   =   |2  (2) where the operator "|" means a bitwise "OR". The codes from the subrange D g = {C aa ..C c } are control codes and the APs are used to initiate remote nodes whose destination addresses are within the specified range, the transmission of their own candidate addresses. The transfer of candidate addresses by remote nodes occurs with a random delay T ar . 3. D ESCRIPTION OF THE PROTOCOL After the remote node receives the command to transfer its candidate address if during a random delay Tar receives a code from the range of D at equivalent to its candidate address, this situation is regarded as a collision of addresses and this node generates a new candidate address. The method of introducing random delay originates from ALOHA algorithm [9]. The diagram in Figure 1 shows the algorithm for the action of the remote node. International Jour nal of Wireless & Mobil Figure 1. Remote node operation algorithm After the transfer of its candidate address if the node receives the co equivalent to the transmitted address to the candidate, then the node generates a new address and waits again for the AP command. If it receives a code from the D candidate address according to (2), then from that moment the address is considered to be approved and the remote node proceeds to receive in another physical channel, determined by its current address. When the node receives any other codes from the D exception array, later when the node generate new candidate addresses, the values that are absent in the exception table are selected. It should be noted, that the protocol provides the t through which the address exclusion tables should be updated. However, the specific values of the time intervals are subject to additional research and may depend on specific properties of the network as well as external conditions. After se nding a command to transfer candidate addresses in a given range of addresses, the AP receives candidate addresses from remote nodes during the time T maximum possible distance to the nodes and T nal of Wireless & Mobil e Networks (IJWMN) Vol. 9, No. 6, December Figure 1. Remote node operation algorithm After the transfer of its candidate address if the node receives the co de from the range of D equivalent to the transmitted address to the candidate, then the node generates a new address and waits again for the AP command. If it receives a code from the D aa range, equivalent to its candidate address according to (2), then from that moment the address is considered to be approved and the remote node proceeds to receive in another physical channel, determined by its other codes from the D aa range, these codes are stored in a special exception array, later when the node generate new candidate addresses, the values that are absent in the exception table are selected. It should be noted, that the protocol provides the t through which the address exclusion tables should be updated. However, the specific values of the time intervals are subject to additional research and may depend on specific properties of the network as well as external conditions. nding a command to transfer candidate addresses in a given range of addresses, the AP receives candidate addresses from remote nodes during the time T dmax determined by the maximum possible distance to the nodes and T armax is the maximum value of the rando e Networks (IJWMN) Vol. 9, No. 6, December 2017 45 de from the range of D at , equivalent to the transmitted address to the candidate, then the node generates a new address and range, equivalent to its candidate address according to (2), then from that moment the address is considered to be approved and the remote node proceeds to receive in another physical channel, determined by its range, these codes are stored in a special exception array, later when the node generate new candidate addresses, the values that are absent in the exception table are selected. It should be noted, that the protocol provides the t ime intervals through which the address exclusion tables should be updated. However, the specific values of the time intervals are subject to additional research and may depend on specific properties of the nding a command to transfer candidate addresses in a given range of addresses, the AP determined by the is the maximum value of the rando m delay. International Journal of Wireless & Mobile Networks (IJWMN) Vol. 9, No. 6, December 2017 46 At the end of the waiting time, the received candidate addresses are analyzed for their repetition, for all repeated addresses, the AP sends them back without changes, which will be perceived by remote nodes as a collision of the address and their candidate addresses will be generated again. For all unique candidate addresses, the AP gets their mapping on the D aa subband according to (2) and sends them. The procedure for identifying nodes can be repeated many times with a gradual accumulation of information about nodes. For instance, nodes can transmit (by the APs request) its depth or hydrostatic pressure, water temperature, internal battery charge, specific sensorrelated data etc. Commands from the D g range explicitly indicate that the remote nodes in which range of addresses must pass their candidate addresses. In this case, the range of D g by volume is equal to the sum of the sizes of the ranges D at and D aa minus 1, and its size is equal to the sum of the first N-1 members of the geometric progression with the denominator 2, which means it is sufficient to place instructions for transferring addresses in ranges of 1, 2, 4, ... N-1 addresses: C  = ∙(  )  (3) For example, with N = 10, the network can contain up to 2 N-2 = 256 unique addresses, and the D g range of which C Dg is 511 codes is sufficient for placing commands to transfer node addresses in the ranges, according to table 1. Table 1. Address ranges vs. number of nodes per range Thus, there are enough codes in D g to request addresses transmission for all possible addresses in D aa . In the case when the number of nodes per address range is 1 algorithm works as sequential polling. Since there is random delay Tar used to avoid collisions, there are no possibilities to localize nodes during network identification procedure. However, in normal data collection mode nodes can be localized on every response simultaneously with data transmission. All APs internal clock can be precisely synchronized by GNSS, thus, measuring times of arrival of response nodes signal, considering known locations of all APs, exact time of transmission of a request signal and depth of the node (which can be transmitted by the node) requesting AP can calculate node location using TOA technique. More detailed TOA technique described in [10][11]. In the case of distributed receivers with known locations, all times of arrival can be recalculated to distances as follows. International Jour nal of Wireless & Mobil Figure 2. Distance measurement for distributed receiver Consider that one AP is the leader AP, it sends request signal at time T this signal and answers with fixed delay T and at time T OAi it arrives at i th AP (fig. 2). In this case slant range d the remote node can be calculated as in (4): where v - speed of sound. Slant range d i between the requested node and i which comes from fig. 2: Calculating slant ranges di for 3 or more APs according to (4) and (5) the node localization can be performed by solving a TOA problem. 4. S IMULATION 4.1. MODEL AND C ONDITIONS In the water area of D max by D randomly distributed (uniformly ) assumed to be equal to Z b . Also in the same water area, N randomly (x and y uniformly, z from the range [N zmin , N zmax ]. The cod (N = 9, see (1)), and the number of possible addresses is C generated randomly from the D at Typical deploymen t layout illustrated in Fig. 3 The probability of reception is equal to all nodes and access points and is assumed equal to P At time T 0 , the access point with address 1 and coordinates B The times of arrival T OAnj of the request signal to the j nal of Wireless & Mobil e Networks (IJWMN) Vol. 9, No. 6, December Figure 2. Distance measurement for distributed receiver Consider that one AP is the leader AP, it sends request signal at time T OR0 , a remote node receives this signal and answers with fixed delay T fd . At time T OA0 response signal arrives at leader AP, AP (fig. 2). In this case slant range d 0 between the leader AP and the remote node can be calculated as in (4):   = (  ! −  "! −  #$ )/2 requested node and i th AP can be obtained from simple relation (5)   & =  "! ' $! ( '  #$ '  ) / ranges di for 3 or more APs according to (4) and (5) the node localization can be performed by solving a TOA problem. ONDITIONS D max m, N b access points with coordinates B i (bx i , ) , and the depths of the acoustic antennas of the access points are . Also in the same water area, N n sites with N j (x j , y j , z j ) coordinates are uniformly, z - normally) located, and the depth of nodes is chosen randomly ]. The cod ing capacity of the channel is assumed to equal to C (N = 9, see (1)), and the number of possible addresses is C at = 256. The node addresses are range. t layout illustrated in Fig. 3 . The probability of reception is equal to all nodes and access points and is assumed equal to P , the access point with address 1 and coordinates B 1 (bx 1 , by 1 , bz 1 ) emit a request signal. of the request signal to the j th node of the network are defined as (   *+ =   '  ,+ / e Networks (IJWMN) Vol. 9, No. 6, December 2017 47 a remote node receives response signal arrives at leader AP, between the leader AP and (4) AP can be obtained from simple relation (5) (5) ranges di for 3 or more APs according to (4) and (5) the node localization can be , by i , bz i ) are , and the depths of the acoustic antennas of the access points are ) coordinates are located, and the depth of nodes is chosen randomly capacity of the channel is assumed to equal to C c = 511 = 256. The node addresses are The probability of reception is equal to all nodes and access points and is assumed equal to P r . a request signal. node of the network are defined as ( 6): (6) International Journal of Wireless & Mobile Networks (IJWMN) Vol. 9, No. 6, December 2017 48 where v is the sound velocity in water, is assumed in this work to be 1450 m/s, and D b1j is the distance from the 1 st access point to the j th node:  ,+ =-(./  − 0/ + )  '1(.2  − 02 + )  ' (.3  − 03 + )  (7) where nx j , ny j and nz j are the coordinates of the j th node. Figure 3.Typical deployment layout.N b = 3, N n = 128 Response times T ORnj for each of the nodes are defined as (8):  "*+ =   *+ '  #$ '  4 (8) T fd and T ar are the fixed delay of the radiation of the response signal and the randomly generated response delay lying in the range [0..T armax ]. As it was seen from the description of the algorithm of the node operation, since the work occurs in one code channel, each node is able to receive the response signal of the remaining nodes, except for cases when the signals of the nodes overlap at the receiving point. In this paper, the motion of signals in a medium is described by the position of the front D sfj and the end D sej of the signal with respect to the node N j . In this case, since the signal duration is fixed and equal to T s , then D sej can be determined as in (9): D 678 = D 698 − T 6 (9) In the simulation, the signals move discretely in time increments equal to ∆ t, so that: D 6981 (t ' ∆t)= D 698 (t)' v ∙1∆t (10) At that, when D sfj (T ORnj ) = 0. The moment of arrival of the front of the response signal of the j th node to the k th node is defined as:   *+> =  "*+ '  >+ / (11) where D kj is the slope distance between the j th and k th nodes. In this simulation, it is assumed that the k th node can receive a signal from the j th node only if signals from the remaining nodes do not arrive at the time T s from the moment T OAnjk , and at this time it does not itself emit a response signal. The arrival time T OAbinj of the response signal of the j th node to the i th access point can be obtained as in (12): -4000 -3000 -2000 -1000 0 1000 2000 3000 4000 -4000 -3000 -2000 -1000 0 1000 2000 3000 4000 Typical deployement x-Coordinate, m y-Coordinate, m AP Node International Journal of Wireless & Mobile Networks (IJWMN) Vol. 9, No. 6, December 2017 49 T ?@ABC8 = T ?DC8 ' D B8 (12) where D ij is the slope distance between the j th node and the i th access point. The condition for the reception of a node signal on an access point is described in the same way as for a node. In this case, the node signal is considered accepted if it was received by at least one access point. For all unique addresses, whose response signals were received by access points, signals of approval or cancellation of the address are emitted. If the node receives the approval signal of its address, it is further excluded from the addressing procedure and transferred to another code channel. A network is fully identified when all nodes successfully receive unique addresses. 4.2. Simulation results Further, the general parameters of the simulation are: D max = 8000 m, Z b = 10 m, N zmax = 300 m, N zmin = 100 m, ∆ t = 0.001 s, T armax = 8 sec. The size of the sample (the number of simulations for which the result was averaged) is 32 unless otherwise indicated. The size of the range of requested addresses is equal to the volume of the entire address space (0..255) Figure 4.Network identification time vs. number of nodes. N b = 3, P r = 0.8. From the graph in Fig. 4 that the time dependence of the total network identification time on the number of nodes is practically linear in the range of values of the argument of interest. The graph in Fig. 5 shows the time dependence of the total network identification on the number of access points. Figure 5. Network identification time vs. number of access points. N n = 128, P r = 0.8. 0 50 100 150 200 250 300 0 100 200 300 400 500 600 Network addressing time vs. number of nodes (averaging 16) Number of nodes Time, sec 0 2 4 6 8 10 12 14 16 180 200 220 240 260 280 300 320 340 Network addressing time vs number of access points (Averaging 32) Number of access points Time, sec International Journal of Wireless & Mobile Networks (IJWMN) Vol. 9, No. 6, December 2017 50 It can be seen from the graph that an increase in the number of access points greater than 6 does not significantly reduce network identification time, and with the number of access points N b = 3, a network of 128 nodes is identified on average 230 seconds. In this case, N b = 3 is the minimum number of access points at which localization of nodes is possible as mentioned before. The parameters of the network identification time dependency on the number of access points are determined mainly by the duration T s of the applied signal and the distance between the access points. Figure 6. Dependence of the time of complete network identification on the probability of receiving messages. N n = 128, N b = 3. The dependence in Fig. 6 shows how the network identification time varies from the probability of receiving messages. From Fig. 6 that the algorithm provides an acceptable network identification time even at extremely low P r values. From experience, considering using the signal design from [7] and [8], it is known that for the vast majority of water areas (including shallow and extremely shallow waters with depth less than 5 meters) the most realistic for the probability of receiving P r are values from the range [0.7..0.98]. Serial interrogation of the network under the same conditions in the ideal case (P r = 1) gives the network identification time T nt as shown in (13):  * = E * ∗ GHIJ∗ ( = 256 ∗ M∗ NO ≈ 10591STU (13) In this case, the average distance D bna between the access point and the node is assumed to be 3 km. The value for T nt obtained by a full search of addresses for an ideal case is on the average 4 times worse than for the same number of nodes addressed by the described algorithm. It is worth noting that in most cases a sequential poll loses the proposed algorithm catastrophically. For example, with a gradual replenishment of the network with new devices in the case of sequential polling, it is necessary each time to search through the remaining addresses. 5. C ONCLUSION AND FURTHER RESEARCH The presented algorithm of dynamic addressing for underwater networks of sensors based on simulation results provides an acceptable time for complete network identification even in conditions of complex water area and low probability of reception. The algorithm is specifically designed to work on code messages with a limited range of values and significant distances between network nodes and access points, while easily scaling in terms of the application of diversity reception while simultaneously providing localization of network nodes. 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 200 300 400 500 600 700 800 900 1000 1100 Network addressing time vs receiving probability (averaging 32) Receiving probability T im e, sec International Journal of Wireless & Mobile Networks (IJWMN) Vol. 9, No. 6, December 2017 51 The objectives of the further research are to develop test devices and test the results of mathematical modeling in real conditions. A CKNOWLEDGEMENTS The work is supported by the Foundation for Assistance to Small Innovative Enterprises in the Scientific and Technical Sphere www. fasie.ru R EFERENCES [1] Akyildiz, I.F. and D. Pompili, 2005. Underwater Acoustic sensor Networks: Research Challenges A survey, pp: 257-279 [2] Heidemann J, Li Yuan, Syed Affan, Wills Jack, Ye Wei, 2005. Underwater Sensor Networking: Research Challenges and Potential Applications, USC/ISI Technical Report ISI-TR-2005-603 [3] Manjula R.B., Sunilkumar S. Manvi, 2011. Issues in Underwater Acoustic Sensor Networks, International Journal of Computer and Electrical Engineering, Vol.3, No. 1, February, 2011, pp.101102 [4] Jun Liu, Zhong Zhou, Zheng Peng, Jun-Hong Cui, Mobi-Synch: Efficient Time Synchronization for Mobile Underwater Sensor Networks, 2010, UCONN CSE Technical Report: UbiNet-TR10-01, University of Connecticut, Storrs, CT 06269 [5] Ying Guo, Yutao Liu. Time synchronization for Mobile Underwater Sensor Networks. Journal of networks, vol. 8, NO. 1, January 2013 [6] Dhammannagari Deepthi, Shankar Thalla Underwater Sensor System Effective Time Synchronization in Networks of Mobile, International Journal of Computer Trends and Technology (IJCTT) - volume 13 number 4 - Jul 2014 [7] Dikarev, A., Dmitriev, S., Kubkin, V., Kulikov, P., Litvinenko, S., Acoustic communication and positioning system for divers, 1st Underwater Acoustics Conference and Exhibition. Proceedings., 2013., pp 1363-1367 [8] Dikarev A., Griffiths A., Watson S., Lennox B., Green P. R., Combined multiuser acoustic communication and localization system for µ AUVs operating in confined underwater environments, 2015. IFAC Workshop on Navigation, Guidance and Control. Girona, Spain [9] Abramson N., The ALOHA System - Another Alternative for Computer Communications. Proc. 1970 Fall Joint Computer Conference. AFIPS Press [10] Ravindra S.,Jagadeesha S. N., Time of arrival based localisation in wireless sensor networks: a linear approach. Signal & Image Processing : An International Journal (SIPIJ) Vol.4, No.4, August 2013 [11] Long Cheng, Chengdong Wu, Yunzhou Zhang, Hao Wu,MengxinLi,CarstenMaple., ASurveyofLocalizationinWirelessSensorNetwork. Hindawi Publishing Corporation International Journal of Distributed Sensor Networks Volume 2012, Article ID 962523, 12 pages doi:10.1155/2012/962523