Abstract—This article considers the joint problem of packetscheduling and self-localization in an underwater acoustic sensornetwork with randomly distributed nodes. In terms of packetscheduling, our goal is to minimize the localization time, andto do so we consider two packet transmission schemes, namelya collision-free scheme (CFS), and a collision-tolerant scheme(CTS). The required localization time is formulated for theseschemes, and through analytical results and numerical examplestheir performances are shown to be dependent on the circumstances.When the packet duration is short (as is the case for alocalization packet), the operating area is large (above 3 km in atleast one dimension), and the average probability of packet-loss isnot close to zero, the collision-tolerant scheme is found to requirea shorter localization time. At the same time, its implementationcomplexity is lower than that of the collision-free scheme, becausein CTS, the anchors work independently. CTS consumes slightlymore energy to make up for packet collisions, but it is shown toprovide a better localization accuracy. An iterative Gauss-Newtonalgorithm is employed by each sensor node for self-localization,and the Cramér Rao lower bound is evaluated as a benchmark.Index Terms—Underwater acoustic networks, localization,packet scheduling, collision.I. INTRODUCTIONAFTER the emergence of autonomous underwater vehicles(AUVs) in the 70s, developments in computer systemsand networking have been paving a way toward fullyautonomous underwater acoustic sensor networks (UASNs)[1], [2]. Modern underwater networks are expected to handlemany tasks automatically. To enable applications such astsunami monitoring, oil field inspection, bathymetry mapping,or shoreline surveillance, the sensor nodes measure variousManuscript received April 24, 2014; revised October 23, 2014; acceptedDecember 29, 2014. Date of publication January 8, 2015; date of currentversion May 7, 2015. The research leading to these results has receivedfunding in part from the European Commission FP7-ICT Cognitive Systems,Interaction, and Robotics under the contract #270180 (NOPTILUS), NSF GrantCNS-1212999, and ONR Grant N00014-09-1-0700. Part of this work waspresented at the IEEE ICC Workshop on Advances in Network Localizationand Navigation (ANLN), Sydney, Australia, June 10–14, 2014. The associateeditor coordinating the review of this paper and approving it for publication wasA. Zajic.H. Ramezani and G. Leus are with the Faculty of Electrical Engineering,Mathematics and Computer Science, Delft University of Technology, 2826 CDDelft, The Netherlands (e-mail: h.mashhadiramezani@tudelft.nl; g.j.t.leus@tudelft.nl).F. Fazel and M. Stojanovic are with the Department of Electrical andComputer Engineering, Northeastern University, MA 02611 USA (e-mail:ffazel@ece.neu.edu; millitsa@ece.neu.edu).Color versions of one or more of the figures in this paper are available onlineat http://ieeexplore.ieee.org.Digital Object Identifier 10.1109/TWC.2015.2389220environmental parameters, encode them into data packets, andexchange the packets with other sensor nodes or send them to afusion center. In many underwater applications, the sensed datahas to be labeled with the time and the location of their origin toprovide meaningful information. Therefore, sensor nodes thatexplore the environment and gather data have to know theirposition, and this makes localization an important task for thenetwork.Due to the challenges of underwater acoustic communicationssuch as low data rates and long propagation delays withvariable sound speed [3], a variety of localization algorithmshave been introduced and analyzed in the literature [4], [5].In contrast to underwater systems, sensor nodes in terrestrialwireless sensor networks (WSNs) can be equipped with a GPSmodule to determine location. GPS signals (radio-frequencysignals), however, cannot propagate more than a few meters,and underwater acoustic signals are used instead. In addition,radio signals experience negligible propagation delays as comparedto the sound (acoustic) waves.An underwater sensor node can determine its location bymeasuring the time of flight (ToF) to several anchors withknown positions, and performing multilateration. Other approachesmay be employed for self-localization, such as fingerprinting[6] or angle of arrival estimation [7]. All theseapproaches require packet transmission from anchors.Many factors determine the accuracy of self-localization.Other than noise, the number of anchors, their constellation andrelative position of the sensor node [8], propagation losses andfading also affect the localization accuracy. Some of these parameterscan be adjusted to improve the localization accuracy,but others cannot.Although a great deal of research exists on underwater localizationalgorithms [1], little work has been done to determinehow the anchors should transmit their packets to the sensornodes. In long base-line (LBL) systems where transpondersare fixed on the sea floor, an underwater node interrogatesthe transponders for round-trip delay estimation [9]. In theunderwater positioning scheme of [10], a master anchor sendsa beacon signal periodically, and other anchors transmit theirpackets in a given order after the reception of the beaconfrom the previous anchor. The localization algorithm in [11]addresses the problem of joint node discovery and collaborativelocalization without the aid of GPS. The algorithm starts witha few anchors as primary seed nodes, and as it progresses,suitable sensor nodes are converted to seed nodes to help indiscovering more sensor nodes. The algorithm works by broadcastingcommand packets which the nodes use for time-of-flight1536-1276 © 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.RAMEZANI et al.: PACKET SCHEDULING FOR UNDERWATER ACOUSTIC LOCALIZATION 2585measurements. The authors evaluate the performance of thealgorithm in terms of the average network set-up time andcoverage. However, physical factors such as packet loss due tofading or shadowing and collisions are not included, and it is notestablished whether this algorithm is optimal for localization.In reactive localization [12], an underwater node initiates theprocess by transmitting a “hello” message to the anchors inits vicinity, and those anchors that receive the message transmittheir packets. An existing medium access control (MAC)protocol may be used for packet exchanging [13]; however,there is no guarantee that it will perform satisfactorily forthe localization task. The performance of localization underdifferent MAC protocols is evaluated in [14], where it is shownthat a simple carrier sense multiple access (CSMA) protocolperforms better than the recently introduced underwater MACprotocols such as T-Lohi [15].In our previous work, we considered optimal collision-freepacket scheduling in a UASN for the localization task insingle-channel (L-MAC) [16] and multi-channel [17] scenarios(DMC-MAC). In these algorithms, the position information ofthe anchors is used to minimize the localization time. In spiteof the remarkable performance of L-MAC and DMC-MAC overother algorithms (or MAC protocols), they are highly demanding.The main drawback of L-MAC or DMC-MAC is that theyrequire a fusion center which gathers the positions of all theanchors, and decides on the time of packet transmission fromeach anchor. In addition, these two collision-free algorithmsneed the anchors to be synchronized and equipped with radiomodems to exchange information fast.In this paper, we also consider packet scheduling algorithmsthat do not need a fusion center. Although the synchronizationof the anchors which are equipped with GPS is not difficult, theproposed algorithms can work with asynchronized anchors ifthere is a request from a sensor node.We assume a single-hop UASN where anchors are equippedwith half-duplex acoustic modems, and can broadcast theirpackets based on two classes of scheduling: a collision-freescheme (CFS), where the transmitted packets never collidewith each other at the receiver, and a collision-tolerant scheme(CTS), where the collision probability is controlled by thepacket transmission rate in such a way that each sensornode can receive sufficiently many error-free packets for selflocalization.Our contributions are listed below.• Assuming packet loss and collisions, the localizationtime is formulated for each scheme, and its minimum isobtained analytically for a predetermined probability ofsuccessful localization for each sensor node. A shorterlocalization time allows for a more dynamic network, andleads to a better network efficiency in terms of throughput.• It is shown how the minimum number of anchors canbe determined to reach the desired probability of selflocalization.• An iterative Gauss-Newton self-localization algorithm isintroduced for a sensor node which experiences packetloss or collision. Furthermore, the way in which thisalgorithm can be used for each packet scheduling schemeis outlined.• The Cramér Rao lower bound (CRB) on localization is derivedfor each scheme. Other than the distance-dependentsignal to noise ratio, the effects of packet loss due to fadingor shadowing, collisions, and the probability of successfulself-localization are included in this derivation.The structure of the paper is as follows. Section II describesthe system model, and outlines the self-localizationprocess. The problem of minimizing the localization time inthe collision-free and collision-tolerant packet transmissionschemes is formulated and analyzed in Section III-A andSection III-B, respectively. The self-localization algorithm isintroduced in Section IV. The average energy consumption isanalyzed in Section V, and Section VI compares the two classesof localization packet scheduling through several numericalexamples. Finally, we conclude the paper in Section VII, andoutline the topics of future works.II. SYSTEM MODELWe consider a UASN consisting of M sensor nodes and Nanchors. The anchor index starts from 1, whereas the sensornode index starts from N + 1. Each anchor in the networkencapsulates its ID, its location, time of packet transmission,and a predetermined training sequence for the time of flightestimation. The so-obtained localization packet is broadcast tothe network based on a given protocol, e.g., periodically, orupon the reception of a request from a sensor node. The systemstructure is specified as follows.• Anchors and sensor nodes are equipped with half-duplexacoustic modems, i.e., they cannot transmit and receivesimultaneously.• Anchors are placed randomly on the surface, and havethe ability to move within the operating area. The anchorsare equipped with GPS and can determine their positionswhich will be broadcast to the sensor nodes. It is assumedthat the probability density function (pdf) of the distancebetween the anchors is known, fD(z). It is further assumedthat the sensor nodes are located randomly in an operatingarea according to some probability density function. Thesensor nodes can move in the area, but within the localizationprocess, their position is assumed to be constant. Thepdf of the distance between a sensor node and an anchoris gD(z). These pdfs can be estimated from the empiricaldata gathered during past network operations.• We consider a single-hop network where all the nodes arewithin the communication range of each other.• The received signal strength (which is influenced by pathloss,fading and shadowing) is a function of transmissiondistance. Consequently, the probability of a packet loss isa function of distance between any pair of nodes in thenetwork.The considered localization algorithms are assumed to bebased on ranging, whereby a sensor node determines its distanceto several anchors via ToF or round-trip-time (RTT). Eachsensor node can determine its location if it receives at leastK different localization packets from K different anchors. Thevalue of K depends on the geometry (2-D or 3-D), and other2586 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 14, NO. 5, MAY 2015factors such as whether depth of the sensor node is available,or whether sound speed estimation is required. The value ofK is usually 3 for a 2-D operating environment with knownsound speed and 4 for a 3-D one. In a situation where theunderwater nodes are equipped with pressure sensors, threedifferent successful packets would be enough for a 3-D localizationalgorithm [18].The localization procedure starts either periodically for apredetermined duration (in a synchronized network), or uponreceiving a request from a sensor node (in any kind of network,synchronous or asynchronous) as explained below.Periodic localization: If all the nodes in the network includinganchors and sensor nodes are synchronized with eachother, a periodic localization approach may be employed. Inthis approach, after the arrival of a packet from the jth anchor,the mth sensor node estimates its distance to that anchor asˆdm, j = c(ˆtRm, j− tTj) where c is the sound speed, tTjis thetime at which the anchor transmits its packet, and ˆtRm, j is theestimated time at which the sensor node receives this packet.The departure time tTjis obtained by decoding the receivedpacket (the anchor inserts this information into the localizationpacket), and the arrival time ˆtRm, j can be calculated by correlatingthe received signal with the known training sequence (or similarprocedures). The estimated time of arrival is related to theactual arrival time through ˆtRm, j = tRm, j + nm, j , where nm, j iszero-mean Gaussian noise with power ó2m, j which varies withdistance and can be modeled as [19]ó2m, j = kEdn0m, j, (1)with dm, j the distance between the jth anchor and the sensornode, n0 the path-loss exponent (spreading factor), and kE aconstant that depends on system parameters (such as signalbandwidth, sampling frequency, channel characteristics, andnoise level). In periodic localization, sensor nodes are notrequired to be synchronized with the anchors. If they arenot synchronized, they can calculate the time-differences ofarrival (TDoAs) from the measured ToFs; however, we will notconsider this situation in our calculation.On-demand localization: In this procedure (which can beapplied to a synchronous or an asynchronous network) a sensornode initiates the localization process. It transmits a highpowerfrequency tone immediately before the request packet.The tone wakes up the anchors from their idle mode, and putsthem into the listening mode. The request packet may also beused for a more accurate estimation of the arrival time. Weassume that all the anchors have been correctly notified by thisfrequency tone. After the anchors have received the wake uptone, they reply with localization packets. The time when therequest has been received by an anchor, tRj,m, and the time tTjatwhich a localization packet is transmitted are included in thelocalization packet. This information will be used by the sensornode to estimate its round-trip-time (which is proportional totwice the distance) to the anchor. The round-trip-time can bemodeled asˆtRTTm, j = (tRm, j−tTm)−(tRj,m−tTj)+nj,m+nm, j, (2)Fig. 1. Packet transmission from anchors in the collision-free scheme. Here,each anchor transmits its packets according to its index value (ID number). Alllinks between anchors are assumed to function properly in this figure (there areno missing links).where tTmis the transmission time of the request signal from thesensor node. Therefore, the estimated distance to anchor j isˆdm, j =12cˆtRTTm, j . (3)After the sensor node estimates its location, it broadcasts itsposition to other sensor nodes. This enables the sensor nodeswhich have overheard the localization process to estimate theirpositions without initializing another localization task [20].The time it takes for an underwater node to gather atleast K different packets from K different anchors is called thelocalization time. In the next section, we formally define thelocalization time, and show how it can be minimized forthe collision-free and collision-tolerant packet transmissionschemes.III. PACKET SCHEDULINGA. Collision-Free Packet SchedulingCollision-free localization packet transmission is analyzedin [16], where it is shown that in a fully-connected (singlehop)network, based on a given sequence of the anchors’indices, each anchor has to transmit immediately after receivingthe previous anchor’s packet. Furthermore, it is shown thatthere exists an optimal ordering sequence which minimizes thelocalization time. However, to obtain that sequence, a fusioncenter is required to know the positions of all the anchors. Ina situation where this information is not available, we may assumethat anchors simply transmit in order of their ID numbersas illustrated in Fig. 1.In the event of a packet loss, a subsequent anchor will notknow when to transmit. If an anchor does not receive a packetfrom a previous anchor, it waits for a predefined time (countingfrom the starting time of the localization process), and thentransmits its packet, similarly as introduced in [21]. With aslight modification of the result from [21], the waiting time forthe jth anchor who has not received a packet from its previousanchor, could be as short as tk+(j−k)(Tp+ Daac ), where k is theindex of the anchor whose packet is the last one which has beenreceived by the jth anchor, tk is the time at which this packetRAMEZANI et al.: PACKET SCHEDULING FOR UNDERWATER ACOUSTIC LOCALIZATION 2587Fig. 2. Packet transmission from anchors in the collision-tolerant scheme.Here, each anchor transmits its packets at random according to a Poissondistribution.TABLE IPOSSIBLE TIMES THAT ANCHOR j TRANSMITS ITS PACKETwas transmitted from the kth anchor (counting from the startingtime of the localization process), c is the sound speed, Daac isthe maximum propagation delay between two anchors, and Tpis the packet length. The packet length is related to the systembandwidth B (or symbol time Ts ≈ 1B), number of bits in eachsymbol bs, number of bits in each packet bp, and guard time Tgas formulated inTp = Tg+bpbsTs. (4)Under this condition, the transmission time of the jth anchort j can be selected from one of the values listed in Table I whereDr = Dsa in on-demand localization which is the distance correspondingto the maximally separated sensor-anchor pair, andDr = 0 in periodic localization, t1 = 0 for periodic localization,and t1 = dsc for on-demand localization, with ds the distancebetween the first anchor and the sensor who sent the requestpacket, and pl(di, j) is the probability of packet loss betweentwo anchors located di, j meters away from each other. Thepacket loss can be defined aspl(d) =_ ∞ã0N0BfX0|d(x)dx (5)where N0B is the noise power, ã0 is the minimum SNR at whicha received packet can be detected at the receiver, and given thedistance between two nodes, d, fX0|d(x) is the conditional pdfof the received signal power which will be derived in the nextsubsection. The first row of Table I indicates that no packetloss (with probability 1− pl(dj, j−1)) occurs between the jthand ( j − 1)th anchor, and the jth anchor transmits after itreceives the packet from the ( j−1)th anchor. The second rowdenotes that there is a packet loss between the jth and ( j−1)thanchor (with probability pl(dj, j−1)), but there is no packetlossbetween the jth and ( j − 2)th anchor (with probability1− pl(dj, j−2)). Therefore, according to the protocol, the jthanchor waits until t j−2 + 2(Daac + Tp) before it transmits itspacket. The last row of Table I specifies that the jth anchor haslost all the packets from all anchors, and as a result transmits ata worst possible time to avoid any collision.Since di, j for j =1, . . . ,N−1, and ds are independent of eachother, the average time at which the jth anchor transmits itspacket can be obtained as¯t j =(1− ¯pl)j−1Ók=1¯tk ¯pj−k−1l +Tp(1− ¯pl)+¯dc−d¯plc+(1− ¯pl)_Daac+Tp_ j−1Ók=2k ¯pk−1l+(j−1)_Daac+Tp_¯pj−1l +Drc¯pj−1l (6)where ¯pl , ¯d, and d¯pl are the expected values of pl(di, j), di, j,and di, j pl(di, j), respectively.The average localization time of a collision-free scheme canbe obtained asTavgCF = ¯tN +Tp+Dsac, (7)where Dsac is added to ensure that the last transmitted packetfrom the Nth anchor reaches the furthest point in the operatingarea.In the best case there is no packet loss between the anchorsand the average localization time reaches its minimum value atTlowCF = (N −1)¯dc+¯dsc+NTp+Dsac, (8)where ¯ds is the average distance between a sensor node and ananchor. In the worst case, all the packets between the anchorsare lost, and the requesting sensor node is the farthest from theinitiating anchor. This case yields the longest localization timegiven byTuppCF = NTp +(N −1)Daac+Dsac+Dsac, (9)which is equivalent to a packet transmission based on timedivision multiple access (TDMA) with time-slot duration Tp +Dc(assuming D = Dsa = Daa).Another figure of merit is the probability with which a nodecan localize itself. If this probability is required to be abovea design value Pss, the necessary number of anchors whichalso minimizes TavgCF (TavgCF is an increasing function of N) isdetermined as the smallest N for whichPlocCF =NÓk=K_Nk_pkCF (1− pCF )N−k ≥ Pss (10)2588 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 14, NO. 5, MAY 2015where pCF is the probability that a transmitted packet reaches asensor node correctly, and it can be calculated aspCF =_ ∞ã0N0BfX0 (x)dx, (11)where fX0 (x) is the pdf of the received signal power.B. Collision-Tolerant Packet SchedulingTo avoid the need for coordination among anchor nodes,in a collision-tolerant packet scheduling, anchors work independentlyof each other. During a localization period or uponreceiving a request from a sensor node, they transmit randomly,e.g., according to a Poisson distribution with an average transmissionrate of ë packets per second. Packets transmitted fromdifferent anchors may now collide at a sensor node, and thequestion arises as to what is the probability of successful reception.This problem is a mirror image of the one investigated in[22] where sensor nodes transmit their packets to a commonfusion center. Unlike [22] however, where the sensors knowtheir location, and power control fully compensates for theknown path-loss, path-loss is not known in the present scenario,and there is no power control. The average received signalstrength is thus different for different links (this signal strength,along with a given fading model, determines the probability ofpacket loss). In this regard, the signal received at the mth sensornode from the jth anchor isvm, j(t) = cm, jvj(t)+im(t)+wm(t), (12)where vj(t) is the signal transmitted from the jth anchor, cm, jis the channel gain, wm(t) is the additive white Gaussian noisewith power N0B, and im(t) is the interference caused by otheranchors whose packets overlap with the desired packet,im(t) = Ók_=jcm,kvk(t −ôk), (13)with ôk being the difference in the arrival times of the interferingsignals w.r.t. the desired signal which is modeledas an exponentially distributed random variable. The signal-tointerference-plus-noise-ratio (SINR) at the receiver depends onthe interference level, and is given byã =X0I0+N0B, (14)where X0 = |cm, j|2P0 is the power of the signal of interestwith P0 the anchor’s transmit power, and where I0 is the totalinterference power which can be expressed asI0 =qÓi=1|cm,ki|2P0 (15)with q the number of interferers, and ki the index of the ithinterferer. We can express the signal power as|cm, j|2 = a−1PL (dm, j)egm, j |hm, j|2, (16)where gm, j ∼N (0,ó2g) models the large scale log-normal shadowing,hm, j ∼ CN (¯h,ó2h) models the small scale fading, andaPL models the path-loss attenuation which can be formulatedas [23]aPL(di, j) = á0_di, jd0_n0a( f )di, j (17)where á0 is a constant, d0 is the reference distance, n0 isthe path-loss exponent, and a( f ) is the frequency-dependentabsorption coefficient. For localization, where the bandwidthis not large, á( f ) can be approximated by a constant.The pdf of the received signal power, fX0 (x) can be obtainednumerically. Since aPL, gm, j and hm, j are independent randomvariables, we calculate the pdfs of 10log|hm, j|2, 10logegm, j , and−10logaPL separately. Then we convolve them which resultsin fX0,dB(xdB). With a simple change of variables x = 100.1xdBwe can find fX0 (x), and the pdf of the interference can beobtained asfI0 (x) = fX0 (x) ∗ fX0 (x) ∗ . . . ∗ fX0 (x) _ __ _qtimes. (18)The probability that a packet is received correctly by a sensornode is then [22]ps =N−1Óq=0P(q)ps|q, (19)where P(q) = (2NëTp)qq! e−2NëT p is the probability that q packetsinterfere with the desired packet, and ps|q is the probability thatthe desired packet “survives” under this condition,ps|q =__ ∞ã0N0B fX0 (x)dx q = 0 _ ∞ã0_ ∞N0B fX0 (ãw) fI0 (w−N0B)wdwdã q ≥ 1(20)where w = I0+N0B.In addition, it should be noted that multiple receptions ofa packet from an anchor does not affect the probability ofself-localization (localization coverage), but in case where asensor node is able to localize itself, multiple receptions of apacket from an anchor affects the accuracy of the localization(see Section IV).If we assume that the packets transmitted from the sameanchor fade independently, the probability of receiving a usefulpacket from an anchor during the transmission time TT can nowbe approximated by [22]pCT = 1−e−psëTT , (21)and the probability that a sensor node accomplishes selflocalizationusing N anchors can be obtained asPlocCT =NÓk=K_Nk_pkCT (1− pCT )N−k, (22)which is equivalent to the probability that a node receives atleast K different localization packets.It can be shown that PlocCT is an increasing function of TT (seeAppendix A), and as a result for any value of psë _= 0, thereis a TT that leads to a probability of self-localization equal toor greater than Pss. The minimum value for the required TT canRAMEZANI et al.: PACKET SCHEDULING FOR UNDERWATER ACOUSTIC LOCALIZATION 2589Fig. 3. Probability of successful localization for different values of ë and TCT .be obtained at a point where psë is maximum (ëopt). It can beproven that the lower bound of ëopt is ëlowopt = 12NTp, and its upperbound is N+12NTp(see Appendix B). These points will be illustratedvia numerical examples in Section VI (cf. Fig. 3).Given the number of anchors N, and a desired probabilityof successful self-localization Pss, one can determine pCTfrom (22), while ë and the minimum localization time canbe determined jointly from (19) and (21). Similarly as in thecollision-free scheme, we then add the time of request dsc , andthe maximum propagation delay between a sensor-anchor pairDsac to the (minimum) TT that is obtained from (19) and (21).The so-obtained value represents the (minimum) localizationtime (TminCT ) TCT , for the collision-tolerant scheme.IV. SELF-LOCALIZATION PROCESSWe have seen that a sensor node requires at least K distinctpackets (or time-of-flight measurements) to determine its location.However, it may receive more than K different packets,as well as some replicas, i.e., qj packets from anchor j, wherej = 1, . . . ,N. In this case, a sensor uses all of this informationfor self-localization. Note that in the collision-free scheme, qj iseither zero or one; however, in the collision-tolerant scheme qjcan be more than 1. Packets received from the jth anchor can beused to estimate the sensor node’s distance to that anchor, andthe redundant packets add diversity (or reduce measurementnoise) for this estimate. In the next two subsections, we showhow all of the correctly received packets can be used in a localizationalgorithm, and how the CRB of the location estimatecan be obtained for the proposed scheduling schemes.A. Localization AlgorithmAfter the anchors transmit their localization packets, eachsensor node has Q measurements. Each measurement is contaminatedby noise whose power is related to the distancebetween the sensor and the anchor from which the measurementhas been obtained. The lth measurement obtained from the jthanchor is related to the sensor’s position x (sensor index isomitted for simplicity) asˆtl = f (x)+nl , (23)where nl is the measurement noise (see (1)) and f (x) isf (x) =1c_x−xj_2 (24)where xj is the jth anchor’s position. Stacking all the measurementsgives us a Q ×1 vectorˆt. The number of measurementsis given byQ =NÓj=1qj, (25)where qj is the number of measurements which are obtainedcorrectly from the jth anchor. In CFS, qj is a Bernoulli randomvariable with success probability P1j= P(qj = 1) = 1− pl(dj)where dj is the distance between the sensor node and thejth anchor. In CTS qj is a Poisson random variable withdistributionPnj= P(qj = n) =(psëTT )nn!e−ëTT pjs|d , (26)where pjs|d is the conditional probability that a sensor nodecorrectly receives a packet from the jth anchor, knowing itsdistance from all anchors (elements of d). This pdf can befound from the conditional pdf of the received signal and theinterference power (see (19) and (20)).Since the measurement errors are independent of each other,the maximum likelihood solution for x is given byˆx = argminx ˆt−f(x) 2 , (27)which can be calculated using a method such as theGauss-Newton algorithm specified in Algorithm 1. In thisalgorithm, ç controls the convergence speed, ∇f(x(i)) =[ ∂ f1∂x , ∂ f2∂x , . . . ,∂ fQ∂x ]Tx=x(i) represents the gradient of the vector fw.r.t. the variable x at x(i), x(i) is the estimate in the ith iteration,and ∂ fl∂x = [∂ fl∂x , ∂ fl∂y , ∂ fl∂z ]T where l = 1, . . . ,Q . Here, I and å arethe user-defined limits on the stopping criterion. The initialguess is also an important factor and can be determined throughtriangulation, similarly as explained in [24].Algorithm 1 Gauss-Newton AlgorithmStart with an initial location guess.Set i = 1 and E = ∞.while i ≤ I and E ≥ å doNext state:x(i+1) = x(i)−ç(∇f(x(i))T∇f(x(i)))−1∇f(x(i))T (f(x(i))−ˆt)E = _x(i+1)−x(i)_i = i+1end whileˆx = x(i)2590 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 14, NO. 5, MAY 2015B. Cramér-Rao BoundThe Cramér-Rao bound is a lower bound on the varianceof any unbiased estimator of a deterministic parameter. In thissubsection, we derive the CRB for the location estimate of asensor node.To find the CRB, the Fisher information matrix (FIM) hasto be calculated. The Fisher information is a measure of informationthat an observable random variable ˆt carries about anunknown parameter x upon which the pdf of ˆt depends. Theelements of the FIM are defined asI(x)i, j = −E∂2 logh(ˆt;x)|x∂xi∂xj_(28)where x is the location of the sensor node, h(ˆt;x) is the pdfof the measurements parametrized by the value of x, and theexpected value is over the cases where the sensor is localizable.In a situation where the measurements (ToFs or RTTs betweena sensor node and the anchors) are contaminated withGaussian noise (whose power is related to the mutual distancebetween a sensor-anchor pair), the elements of the FIM can beformulated asI(x)i, j =1PlocQNÓqN=0. . .Q2Óq2=0Q1Óq1=0s.t.{q1,…,qN} enable self-localization×_∂f∂xiTR−1w∂f∂xj+12trR−1w∂Rw∂xiR−1w∂Rw∂xj_ÐNj=1Pqjj (29)where Ploc is the localization probability (see (10) and (22)),Qi = 1 for CFS, and ∞ for CTS, Rw is the Q × Q noisecovariance matrix∂Rw∂xi= diag_∂[Rw]11∂xi,∂[Rw]22∂xi, . . . ,∂[Rw]QQ∂xi_, (30)and∂f∂xi=∂ f1∂xi,∂ f2∂xi, . . . ,∂ fQ∂xi_T, (31)with fi a ToF or RTT measurement.Once the FIM has been computed, the lower bound on thevariance of the estimation error can be expressed as CRB =Ó3i=1CRBxi where CRBxi is the variance of the estimation errorin the ith variable, defined asCRBxi =_I−1(x)_ii . (32)Note that the CRB is meaningful if a node is localizable ( 1Plocin (29)), meaning that a sensor node has at least K differentmeasurements. Hence, only ÓNk=K_Nk_possible states have tobe considered to calculate (29) for collision-free scheduling,while the number of states is countless for collision-tolerantscheduling. Nonetheless, it can be shown that the numberof possible states in CTS can be dropped to that of CFS(see Appendix C).TABLE IIVALUES OF ès AND èe BASED ON DISTANCE dV. ENERGY CONSUMPTIONIn this section, we investigate the average energy consumedby all the anchors during the localization. In CFS, the receiverof anchor j is on for t j seconds, and its transmitter is on onlyfor Tp seconds. With power consumption PL in listening modeand PT in transmitting mode, the average energy consumptionin CFS isEavgCF = NTpPT+NÓj=1¯t jPL, (33)where the energy consumed for processing is ignored. As isclear from (6), an anchor with a higher index value has to listento the channel longer, and consequently consumes more energyin comparison with the one that has a lower index. To overcomethis problem, anchors can swap indices between localizationprocedures.In CTS, the anchors do not need to listen to the channel andthey only transmit at an average rate of ë packets per second.The average energy consumption is thusEavgCT = ëTTNTpPT. (34)For ( PLPT<NTp(ëTT−1)ÓNj=1 ¯t j), the average energy consumption of CTSis always greater than that of CFS. However, as ë gets smaller(or equivalently TCT gets larger), the energy consumption ofCTS reduces.VI. NUMERICAL RESULTSTo illustrate the results, a 2-D rectangular-shape operatingarea with length Dx and width Dy is considered with uniformlydistributed anchors and sensors. There is no difference in howthe anchors and sensor nodes are distributed, and therefore wehave fD(d) = gD(d) which can be obtained as [26]fD(d) =2dD2xD2y_d2(sin2 èe−sin2 ès)+2DxDy(èe−ès)+2Dxd(cosèe−cosès)−2Dyd(sinèe−sinès)] (35)where ès and èe are related to d as given in Table II.The parameter values for the numerical results are listed inTable III, and used for all examples.The number of bits in each packet is set to bp = 200 whichis sufficient for the position information of each anchor, timeof transmission, (arrival time of the request packet), and thetraining sequence. Assuming QPSK modulation (bs =2), guardtime Tg =50 ms, and a bandwidth of B=2 kHz the localizationpacket length is Tp = 100 ms (see (4)). In addition, kE is setRAMEZANI et al.: PACKET SCHEDULING FOR UNDERWATER ACOUSTIC LOCALIZATION 2591TABLE IIISIMULATION PARAMETERS. NOTE THAT, IN THIS TABLE SOMEPARAMETERS SUCH AS N, Daa, Tg, etc. ARE RELATED TO OTHERPARAMETERS, e.g., N DEPENDS ON THE VALUES OF THE ¯pl , AND Pssto 10−10 which is approximately equivalent to 1.9 m rangeaccuracy at 1 km away from an anchor. Moreover, to keepthe transmitted packets from an anchor in CTS independentof each other, we set óg = 0 (no shadowing effect) for thesimulations. Fig. 3 shows the probability of successful selflocalizationin the collision-tolerant scheme as a function of ëand the indicated value for TCT . It can be observed that thereis an optimal value of ë (denoted by ëopt) which correspondsto the minimal value of TCT (TminCT ) which satisfies PlocCT≥ Pss.The highlighted area in Fig. 3 shows the predicted region ofëopt (obtained in Appendix B). As it can be seen, ëopt is closeto ëlowopt , and it gets closer to this value as Ps|q>0 gets smaller.In addition, for the values of TCT greater than TminCT , a range ofvalues for ë ∈ [ëlow,ëupp] can attain the desired probability ofself-localization. In this case, the lowest value for ë should beselected to minimize the energy consumption.Fig. 4 shows the probability of correct packet receptionversus the number of interferers (the desired Pss is set to 0.90in this example) for different values of the path-loss exponentn0. When there is no interference, the probability of packetreception is high. Yet, when there is an interferer, the chanceof correct reception of a packet becomes small (0.126 for n0 =1.4), and as the number of interferers grows, it gets smaller.The probability that two or more packets overlap is alsodepicted in part (b) of this figure for the three values of ëshown in Fig. 3. It can be seen that as the value of ë is reducedfrom ëopt (which is equivalent to a larger TCT ), the probabilityof collision becomes smaller. The chance of correct packetreception thus increases, and the energy consumption reducesas explained in Section V. In addition, it can be observed thatalthough using ëupp results in the same performance as ëlow,Fig. 4. (a) Probability of successful packet reception versus different numberof interferers. (b) Probability that q interferers collide with the desired packet.For this figure, ëlow, ëopt and ëupp are chosen from Fig. 3.it relies on the packets that have survived collisions, which isnot energy-efficient in practical situations neither for anchors(required energy for multiple packet transmissions) nor forsensor nodes (processing energy needed for packet detection).Part (a) of Fig. 5 shows the time required for localizationversus the transmit power. As P0 increases, ¯pl gets smaller,and consequently fewer anchors are required for collision-freelocalization. In Fig. 5, for a given P0, the number of anchorsN is calculated using (10), which is then used to calculatethe minimum required time for the collision-free and collisiontolerantlocalization. Each fall in TuppCF in CFS indicates that thenumber of anchors has been decreased by one.We also note thatfor a given number of anchors, the upper and lower bounds ofTCF are constant over a range of P0 values; however, the actualperformance of both schemes becomes better as P0 grows. Thecollision-tolerant approach performs better for a wide rangeof P0 values, and as the number of anchors decreases, itsperformance slightly degrades. In part (b) of Fig. 5, we calculatethe ratio PLPTbelow which the average energy of CTS is greaterthan that of CFS. The ratio of EavgCF /EavgCT is a linear functionof PLPT, and as P0 increases for larger values of PLPT, the averageenergy consumption of CTS becomes greater than that of CFS.In practice, for a range of 6 km the PLPTis less than 1100 [25], andthis means that CTS consumes more energy.Many factors such as noise power or packet length aredirectly dependent on the operating frequency and the systembandwidth. Assuming single-hop communication among thesensor nodes, an optimum frequency band exists for a given2592 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 14, NO. 5, MAY 2015Fig. 5. (a) Effect of transmit power on the minimum time required forlocalization, and the average probability of a packet-loss ¯pl (dashed-line).(b) The minimum value of PLPTin dB below which the average energy consumptionof CTS is greater than that of CFS.operating area. As the size of the operating area increases,a lower operating frequency (with less bandwidth) is used tocompensate for the increased attenuation. Furthermore, as thedistance increases, the amount of available bandwidth for theoptimum operating frequency also gets smaller [23]. As it wasmentioned before, the localization packet is usually short interms of the number of bits, but its duration (in seconds) stilldepends on the system bandwidth. Below, we investigate theeffect of packet length (or equivalently system bandwidth) onthe localization time.As it is shown in Fig. 6, the length of the localization packetplays a significant role in the collision-tolerant algorithm. Theminimum localization time grows almost linearly with Tp inall cases; however, the rate of growth is much higher for thecollision-tolerant system than for the collision-free one. At thesame time, as shown in Fig. 7, the size of the operating areahas a major influence on the performance of the CFS, whilethat of the CTS does not change very much. It can be deducedthat in a network where the ratio of packet length to the maximumpropagation delay is low, the collision-tolerant algorithmoutperforms the collision-free one in terms of localization time.The localization accuracy is related to the noise level atwhich a ToF measurement is taken, and to the anchors’ constellation.If a sensor node in a 2-D operating system receivespackets from the anchors which are (approximately) locatedon a line, the sensor node is unable to localize itself (or itexperiences a large error). To evaluate the localization accuracyof each algorithm, we considered M = 100 sensor nodes, andFig. 6. Effect of packet length on the minimum time required for localization.Fig. 7. Effect of the operating area size on the time required localization.run a Monte Carlo simulation (103 runs) to extract the results.The number of iterations in Algorithm 1 is set to I =50, and theconvergence rate is ç = 15. The TCF was set equal to the averagelocalization time of CFS. In this special case where TminCT islower than TavgCF , the successful localization probability (Ploc)of CTS is greater than that of CFS. The probability distributionof the localization error _ˆx−x_ is illustrated in Fig. 8 for bothschemes. In this figure, the root mean square error (RMSE),and root CRB (R-CRB) are also shown with the dashed anddash-dotted lines, respectively. It can be observed that in CTSthe pdf is concentrated at lower values of the localization errorcompared to CFS, because each sensor in CTS has a chance ofreceiving multiple copies of the same packet, and thus reducingthe range estimation error.VII. CONCLUSIONWe have considered two classes of packet scheduling forself-localization in an underwater acoustic sensor network,RAMEZANI et al.: PACKET SCHEDULING FOR UNDERWATER ACOUSTIC LOCALIZATION 2593Fig. 8. Probability distribution of the localization error, and its correspondingCRB for CTS and CFS.one based on a collision-free design and another based on acollision-tolerant design. In collision-free packet scheduling,the time of the packet transmission from each anchor is setin such a way that none of the sensor nodes experiences acollision. In contrast, collision-tolerant algorithms are designedso as to control the probability of collision to ensure successfullocalization with a pre-specified reliability. We have alsoproposed a simple Gauss-Newton based localization algorithmfor these schemes, and derived their Cramér-Rao lower bounds.The performance of the two classes of algorithms in terms ofthe time required for localization was shown to be dependenton the circumstances. When the ratio of the packet length tothe maximum propagation delay is low, as it is the case withlocalization, and the average probability of packet-loss is notclose to zero, the collision-tolerant protocol requires less timefor localization in comparison with the collision-free one forthe same probability of successful localization.Except for theaverage energy consumed by the anchors, the collision-tolerantscheme has multiple advantages. The major one is its simplicityof implementation due to the fact that anchors work independentlyof each other, and as a result the scheme is spatiallyscalable, with no need for a fusion center. Furthermore, itslocalization accuracy is always better than that of the collisionfreescheme due to multiple receptions of desired packets fromanchors. These features make the collision-tolerant localizationscheme appealing from a practical implementation view point.In the future, we will extend our work to a multi-hop networkwhere the communication range of the acoustic modems ismuch shorter than the size of the operating area.APPENDIX APlocCT IS AN INCREASING FUNCTION OF TCTIn this appendix, we show that the probability of successfullocalization is an increasing function of the localization time.According to (21), and the fact that psë is independent of TT, itis clear that pCT is an increasing function of TT. Therefore, PlocCTis an increasing function of TT if PlocCT is an increasing functionof pCT . The derivative of PlocCT w.r.t. pCT is∂PlocCT∂pCT=NÓk=K_Nk_(k−NpCT )pk−1CT (1−pCT )N−k−1. (36)With a simple modification we have∂PlocCT∂pCT=1pCT (1− pCT )×__NÓk=0_Nk_kpkCT (1− pCT )N−k−K−1Ók=0_Nk_kpkCT (1− pCT )N−k_−NpCT_NÓk=0_Nk_pkCT (1− pCT )N−k−K−1Ók=0_Nk_pkCT (1− pCT )N−k_. (37)Using the properties of binomial random variables we have thatNÓk=0_Nk_kpkCT (1− pCT )N−k = NpCT , (38)andNÓ k=0_Nk_pkCT (1− pCT )N−k = 1. (39)Now, equation (37) (or equivalently (36)) is equal to∂PlocCT∂pCT=K−1Ók=0_Nk_(NpCT−k)pk−1CT (1−pCT )N−k−1. (40)It can be observed that (36) is always positive for pCT < KN ,and (40) is always positive for pCT > KN . As a result∂PlocCT∂pCTispositive for any value of pCT ; therefore, PlocCT is an increasingfunction of pCT , and consequently of TT.APPENDIX BMAXIMUM VALUE OF psëThe first and second derivatives of psë w.r.t. ë can beobtained as∂psë∂ë =NÓq=0ps|qxqe−xq!(q−x+1), (41)(∂psë)2∂2ë =NÓq=0ps|qxq−1e−xq![(q−x)(q−x+1)−x] , (42)where x = 2NëTp. For x < 1 the derivative in (41) is positive,and for x > N +1 it is negative. Therefore, psë has at least onemaximum within x ∈ [1,N+1]. In practical scenarios the valueof ps|q for k > 0 is usually small, so that it can be approximatedby zero. For a special case where ps|q>0 = 0, (41) is zero if2594 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 14, NO. 5, MAY 2015x = 1, and (42) is negative, and as a result ëlowopt = 12NT p maximizesPlocCT . This corresponds to a lower bound on the optimalpoint in a general problem (i.e., ps|q>0 _= 0).APPENDIX CCRAMÉR RAO LOWER BOUND FOR CTSThe upper bound on the sum operation in (29) for CTS is ∞(note that in practice at most TTTppackets can be transmitted froman anchor), and this makes the CRB calculation very difficulteven if it is implemented numerically. To reduce the complexityof the problem, the observation of a sensor node from thejth anchor is divided into two parts: Either a sensor nodedoes not receive any packet from this anchor (no informationis obtained), or it receives one or more packets. Since theanchor and the sensor node do not move very much during thelocalization procedure, their distance can be assumed almostconstant, and therefore the noise power is the same for allmeasurements obtained from an anchor. When a sensor nodegathers multiple measurements contaminated with independentnoise with the same power (diagonal covariance matrix), CRBcan be computed with less complexity. We will explain complexityreduction for the first anchor, and then generalize forthe other anchors.Considering the first anchor, each element of the FIM can becalculated in two parts: no correct packet reception, and one ormore correct packet receptions from this anchor, which can beformulated asI(x)i, j = P01 I (x|q1 = 0)i, j +P>01 I (x|q1 > 0)i, j , (43)where P01 is the probability that no packet is received from thefirst anchor, and P>01 = Ó∞q1=1 Pk1 is the probability that oneor more than one packets are received from the first anchorwhich depends on the distance between the sensor node andthe anchor. The second term in (43) can be expanded asI(x|q1 > 0)i, j=1PlocQNÓqN=0. . .Q2Óq2=0s.t. {q1,…,qN} enable self-localization×_1ó−21∂ f1∂xi∂ f1∂xj+c1+1ó−41∂ó21∂xi∂ó21∂xj+c2_×P11 /P>01 ÐNj=2Pqjj+_2ó−21∂ f1∂xi∂ f1∂xj+c1+2ó−41∂ó21∂xi∂ó21∂xj+c2_×P21 /P>01 ÐNj=2Pqjj+… _ kó−21∂ f1∂xi∂ f1∂xj+c1+kó−41∂ó21∂xi∂ó21∂xj+c2_×Pk1/P>01 ÐNj=2Pqjj+…(44)where c1 and c2 are affected only by measurements from theother anchors. Using a simple factorization we haveI(x|q1 > 0)i, j =1PlocQNÓqN=0. . .Q2Óq2=0s.t. {q1,…,qN} enable self-localization×_gjó−21∂ f1∂xi∂ f1∂xj+ó−41∂ó21∂xi∂ó21∂xj_+c1+c2_ÐNj=2Pqjj (45)wheregj =Ó∞qj=1 kPkjÓ∞q j=1 Pkj=ëTT pjs|d1−P0j. (46)Now, we define aN×1 with its kth element ak either zero (ifqk = 0) or gj (if qk > 0). We also define bN×1 with its kthelement bk = [ó−2k∂ fk∂xi∂ fk∂x j+ó−4k∂ó2k∂xi∂ó2k∂x j]. Then, we haveI(x|a)i, j =1Ploc×_aT b__ÐN−nan=1 P0k,ak=0__Ðnan=1(1−P0k,ak>0)_, (47)where na is the number of non-zero elements in a. Hence, toevaluate I(x)i, j for the localizable scenarios only_NK_possiblestates (different realizations of a which lead to localizablescenarios) have to be considered. This number is the same asthat of CFS.Hamid Ramezani (S’11) was born in Tehran, Iran.He received the B.Sc. degree in electrical engineeringfrom Tehran University, Tehran, and the M.Sc.degree in telecommunications engineering from theIran University of Science and Technology, Tehran,in 2007. He worked at several companies focusingon the implementations of wireless system standardssuch as DVB-T and DVB-H. He is currently pursuingthe Ph.D. degree with the Electrical EngineeringDepartment, Delft University of Technology (TUDelft), Delft, The Netherlands. His current researchinterests include Underwater acoustic communications and networking.Fatemeh Fazel (S’05–M’07) received the B.Sc. degreefrom Sharif University, Tehran, Iran, the M.Sc.degree from University of Southern California, andthe Ph.D. degree from the University of California,Irvine, all in electrical engineering. She is currentlyan Associate Research Scientist in the Electricaland Computer Engineering Department, NortheasternUniversity, Boston, MA, USA. Her research interestsare in signal processing methods for wirelesscommunications and sensor networks.Milica Stojanovic (S’90–M’93–SM’08–F’10)received the B.S. degree from the University ofBelgrade, Serbia, in 1988, and the M.S. and Ph.D.degrees in electrical engineering from NortheasternUniversity, Boston, MA, USA, in 1991 and 1993,respectively. She was a Principal Scientist at theMassachusetts Institute of Technology, and in2008 joined Northeastern University where she iscurrently a Professor of electrical and computerengineering. She is also a Guest Investigatorat the Woods Hole Oceanographic Institution,and a Visiting Scientist at MIT. Her research interests include digitalcommunications theory, statistical signal processing and wireless networks,and their applications to underwater acoustic systems. She is an AssociateEditor for the IEEE JOURNAL OF OCEANIC ENGINEERING and a pastAssociate Editor for the IEEE TRANSACTIONS ON SIGNAL PROCESSINGand TRANSACTIONS ON VEHICULAR TECHNOLOGY. She also serves onthe Advisory Board of the IEEE Communication Letters, and chairs theIEEE Ocean Engineering Society’s Technical Committee for UnderwaterCommunication, Navigation and Positioning.Geert Leus (M’01–SM’05–F’12) received the M.Sc.and the Ph.D. degrees in applied sciences from theKatholieke Universiteit Leuven, Belgium, in June1996 and May 2000, respectively. Currently, he is an“Antoni van Leeuwenhoek” Full Professor with theFaculty of Electrical Engineering, Mathematics andComputer Science, Delft University of Technology,The Netherlands. His research interests are in thearea of signal processing for communications. Hereceived a 2002 IEEE Signal Processing SocietyYoung Author Best Paper Award and a 2005 IEEESignal Processing Society Best Paper Award. He was the Chair of the IEEESignal Processing for Communications and Networking Technical Committee,and an Associate Editor for the IEEE TRANSACTIONS ON SIGNAL PROCESSING,the IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, the IEEESIGNAL PROCESSING LETTERS, and the EURASIP Journal on Advancesin Signal Processing. Currently, he is a Member-at-Large to the Board ofGovernors of the IEEE Signal Processing Society and a member of the IEEESensor Array and Multichannel Technical Committee. Finally, he serves as theEditor in Chief of the EURASIP Journal on Advances in Signal Processing.