ECE 174 Computer Assignment #2 — Due Thursday 12/1/2011GLOBAL POSITIONING SYSTEM (GPS) ALGORITHMOverviewBy utilizing measurements of the so-called pseudorange between an object and each ofseveral earth orbiting GPS satellites, the object can be very accurately located in space. Ageneral description of GPS can be found in the article [1], which you should read thoroughly,and in the detailed Web site [2]. Additional technical information can be found in [3] andother articles in [4]. Using your knowledge of the nonlinear least-squares problem you willsolve the problem of locating an object given GPS pseudorange data. A self-containedtechnical development, sufficient for you to perform this task, can be found in the appendixto this assignment and in the class lecture supplement on gradient descent GPS algorithms[5].Signals are sent from earth orbiting satellites to a receiver located on the surface of theearth. In principle, utilizing timing information and knowledge of the satellite orbit, thetrue range (the receiver-to-satellite distance) to each satellite can be measured. In practicethe range measurement is errorful due to a systematic error caused by an inaccurate receiverclock (to keep the cost of commercial GPS units low) and random errors due to atmosphericdistortion, communication channel noise, sensor noise, etc. The errorful range measurementis known as a pseudorange in order to distinguish it from the unknown true range (see theAppendix below). Because of the speed of light; the non-relativistic speeds of the satellitesand receiver; and the close proximity of the satellites and object, it is assumed that duringthe time period needed to collect all the pseudorange information the satellites and receiverare motionless.Notation and Problem StatementAll locations are given with respect to a fixed-earth (geostationary) reference coordinatesystem located at the center of the earth. Distances are given in units of Earth Radii (ER)(using an average value of 1ER = 6,370km). Note that according to [1], GPS satellites arelocated at about 4.14ER from the center of the earth (20,000km above the earth’s surface).Use the notation S`= (x`, y`, z`)T= position of `thSatellite, ` = 1, · · · 4; S = (x, y, z)T=position of receiver (the Station to be tracked); R`= true range to the receiver located atS from the satellite located at S`; and ∆S`= S − S`= satellite-to-receiver distance vector.For fixed satellite location, S`, the true range, R`, is a nonlinear function of the receiverlocation, S, and is given by,R`(S) = kS − S`k = k∆S`k =p(∆S`)T∆S`, ` = 1, · · · , 4.The pseudorange measurements are denoted by y`, and modeled as1y`= R`(S) + b + ν`, ` = 1, · · · , 4 , (1)1See the attached appendix.1where the random noise term ν`is i.i.d. with p.d.f. N(0, σ2). Further discussion of this modelis given in the lecture supplement [5]. The (constant) systematic clock bias error b is causedby an inaccurate clock in the GPS receiver. The number of range measurements taken toeach satellite, m, is the same for each satellite.• Knowing the satellite locations, S`, ` = 1, · · · , 4, and having m pseudorange measure-ments, y`, to each of the ` satellites, you are to estimate the receiver location, S, andthe clock bias, b, using the Gradient Descent and Gauss methods for solving nonlinearleast squares problems.Simulation Parameter Values. For the purposes of generating synthetic data, the receiverposition, S, and the satellite positions, S`, are taken to be as follows (in ER units):S = (1.000000000, 0.000000000, 0.000000000)TS1= (3.585200000, 2.070000000, 0.000000000)TS2= (2.927400000, 2.927400000, 0.000000000)TS3= (2.661200000, 0.000000000, 3.171200000)TS4= (1.415900000, 0.000000000, 3.890400000)T.The receiver is assumed to be at mean sea level. The clock bias error, b, is taken to beb = 2.354788068 × 10−3ER,which is equivalent to b = 15 km, or approximately 0.05 millisecond.2As discussed in theappendix, b > 0 corresponds to the clock on the receiver running fast compared to the clockson the satellites. Note the degree of numerical round-off precision required to locate anobject to well within a kilometer (1km = 1.569858713×10−4ER). By default Matlab usesdouble precision to minimize numerical round-off error, which should be adequate for ourproblem.Procedure1. Linearization. Assume a nominal receiver location,bS, and clock biasbb and linearizethe pseudorange equation (1) about the nominal values. Discuss whether the linearizedapproximation gets better or worse as the true range increases.2. Algorithm Development. Formulate the Steepest Descent and Gauss’ methods,explicitly showing the actual equations you will use. Identify the step size you willuse. Identify your termination criteria. Remember that, in general, it is assumed thatm pseudorange measurements have been taken to each satellite. To accomplish thisstep, you will need to carefully read and understand the material presented in LectureSupplements 2 and 3.2Using c = 299, 792.458 km/sec. The specified value of b, then, is the instantaneous clock accuracy neededto locate an object to within 15 kilometers. Note that to attain the accuracy needed to locate an object towithin 10 meters requires that we reduce this clock imprecision by a factor of at least 1/1, 500.23. Simulation. Generate synthetic data and test and compare the Steepest Descent andGauss’ Methods. For your initial estimate of the vehicle location,bS(0), usebS(0) = (0.93310, 0.25000, 0.258819)TER .(The initial estimatebS(0) corresponds to a location which is about 0.5km above sealevel and about 2,330km off of the actual location, S. Note that this is a very crudeinitial guess—as a comparison, the distance between San Diego and Los Angeles is lessthan 200km.) For your initial estimate of the clock bias usebb(0) = 0.You will need to generate pseudorange measurements for three different noise levels:σ = 0.00000 (no noise); σ = 0.00040 (a range error standard deviation of about 2.5km);σ = 0.00400 (standard deviation of about 25km). Using this data you should:(a) Apply the Steepest Descent Algorithm to locate the vehicle for the three differentnoise cases. For the no-noise case do this for m = 1. For the two nonzero noisecases, do this for m = 1, 4, 16, and 256. Show the error in your position estimatesusing units of meters.(b) Repeat step (a) for the Gauss-Newton method. Again, use units of meters inthe error analysis. For the two nonzero noise