Task List

• Research Estimators
  • Linear Intersection (LI)
  • Maximum Likelihood (ML)
  • Spherical Interpolation (SI)
• Create m-File that takes in time delays and outputs vectors. Geometry problem.
• Create m-function that does change of coordinates for the microphones, for use in above m-File.
• Build a simulator that will get the TDOA vector and translate it back to room’s global coordinates.
• Start writing abstract for Undergrad Research Conference
• Read papers
  • Chen/Yao/Hudson
  • Brandstein/Adcock/Silverman
  • Abel/Smith
  • Minero (literature review)
• Keep in mind several applications
  • GIZMO Project (collective of small robots)
  • CONDOR Project (wireless access point UAV)
  • ShotSpotter

     
     

Linear Intersection Estimator

Introduction

The maximum likelihood estimator is a clever way to deal with noise, but it is unattractive because either every point in the room has to be considered or one needs to take the derivative of a summation to find the minimum. It is called a “search-based” estimator for this reason. One way to improve on this is to narrow to field from an infinite number of possibilities to a much smaller finite number.

 
 

Creating Vectors

With a given time delay at a given sensor pair, there is a locus of points for the source given by half a hyperboloid of two sheets with a vertex centered between the sensors. When the distance between the sensors is very small compared to the distance to the source, the hyperboloid can be approximated by a cone. The direction angle of this cone is given by the formula:

But before we get ahead of ourselves, let’s lay out some geometry. To make things simple, we’ll create a coordinate system with the origin at the center of the cluster. The cluster will consist of 4 sensors, and each sensor lies on a midpoint of a rectangle centered about our origin. Here’s a diagram.

There are 3 unit vectors in this system, xi, yi, zi, in the positive x, y, and z directions, respectively. Our two sensor pairs will form two cones, with direction angles given by

and

α is with respect to the positive x-axis, β is with respect to the positive y-axis. A graph is shown below.

It’s obvious that our vector towards the source will satisfy both direction angles. We notice that the intersection of the two cones satisfies both direction angles, and the intersection can describe a vector from the origin to the source. In order to generate a vector, however, we need a third angle, γ, with respect to the positive z-axis. We can find it by solving the identity:

This then translates to a Cartesian vector a’i, given by

This vector can be used to describe a bearing line of all possible source locations. Shown in parametric form,

In order to bring the line into the coordinate system of the room, we need to use a rotation matrix Ri. The full form of the line is

 
 

Points of Closest Intersection

Assume we have two bearing lines

The minimum distance between the lines is given by a line perpendicular to both lines. The length of this line is:

The points of closest intersection (PCI) from one line to another are important to the LI estimator. The PCI of lines 1 and 2 are point A from line 1 and B from line 2 such that line segment AB is perpendicular to both line 1 and line 2, and the length of the segment AB is given by djk. The finding of the PCI is a linear algebra problem that requires a little bit of work. Remember that there is no such thing as a line per se in 3-space. What we consider a line is merely a locus of vectors that satisfy an addition of two given vectors, one scaled by an arbitrary parameter. What we want to do is find vectors lk and lj such that

Substituting in for li and lj and then separating known values from the unknowns, we get the following

If we evaluate the right-hand side and call it a matrix c, we get the following equation.

Solving this for tj and tk gives us the two vectors of closest intersection. An example done in MATLAB is shown below:

The purple line is the mutually perpendicular vector.

 
 

Estimating the location of the source

For a sensor network with 4 nodes, there are

PCI that approximate the location of the source. We need a systematic way to average out these multiple points and get a single location estimate. Brandstein et al. devised a method where each point is given a weight Wjk. Wjk is a number derived from a probability similar to that we used in the ML estimator to deal with noise. The estimation of the location is given by the huge summation:

Let’s explain what this mess means. The numerator multiplies each vector by its weight, and the denominator normalizes all the weights by dividing everything by the sum of all weights. This way, all PCI contribute an appropriate amount to the final estimate of the source location.

Day’s Reflections

The work on the linear intersection estimator is nearly complete. I have written up how to generate vectors using this algorithm, and have created a MATLAB code that randomly generates a TDOA and creates a vector corresponding to it. The steps from here are to translate the vector from the relative coordinates of the microphone to the global coordinates of our room, and to finish my notes on the linear estimator.

This weekend, I have a lot of literature to review, and I want to be able to build a simulator that can, for a given set of delays, draw all the needed vectors. That will be a huge step towards my first presentation goal, in a little less than 2 weeks .

Paolo and I discussed the mechanics of the hardware. We will most likely need to do some sort of hardware fabrication for the microphone clusters, because it’s more practical than looking for a sound card which has 4 line-in inputs. I imagine it would connect through USB to the laptop. We will need to see if USB has the kind of fidelity we would need, and take it from there.

All in all, I feel good about today. We’ll see what tomorrow brings.

Task List

• Research Estimators
  • Linear Intersection (LI) (in progress)
  • Spherical Interpolation (SI) (literature found)
  • Maximum Likelihood (ML)
• Create m-File that takes in time delays and outputs vectors. Geometry problem.
• Create m-function that does change of coordinates for the microphones, for use in above m-File.
• Build a simulator that will get the TDOA vector and translate it back to room’s global coordinates.
• Start writing abstract for Undergrad Research Conference
• Read papers
  • Chen/Yao/Hudson
  • Brandstein/Adcock/Silverman (in progress)
  • Abel/Smith
  • Minero (literature review)
• Keep in mind several applications
  • GIZMO Project (collective of small robots)
  • CONDOR Project (wireless access point UAV)
  • ShotSpotter

     
     

Day’s Reflections

Today wasn’t as productive. I got to Calit2 late, so not too much happened. I suppose the nature of research is that some days, you don’t get to cross anything off of your list.

 

Last quarter I withdrew from a course in probability and statistics. I hadn’t fared well on the midterm, and wanted to protect my GPA. Sitting in the library, trying to solve problems asking about the probability of a light bulb failing, the material seemed insurmountable.

 
 

I got a round two the other day, working on the ML estimator. Random variables came back to haunt me. Why? Because in our room, what is transmitted and what is received are not the same, as the diagram below shows.

 
 

I feel that in learning it this time, I see that those problems had a purpose. I intend to specialize in wireless communications, and this kind of noise will always pose an issue. With a cable between two systems, you can potentially limit the noise with a good enough cable. But you can’t fill a room with a better quality air for a wireless system. Unlike other systems, wireless systems need to be robust enough to work regardless of the quality of the medium.

 
 

I find it fascinating to see that we are able to mimic the effect noise has on a signal, and are able to come up with systematic ways of extracting the transmitted signal from the received signal. It’s amazing what math can do.

 
 

I am currently working on the Linear Intersection estimator, and will type up my rough notes tomorrow. I also managed to find papers on another estimator, called the spherical interpolation estimator. We’ll see how well that works tomorrow.

 
 

Task List

• Research Estimators
  • Linear Intersection (LI) (in progress)
  • Spherical Interpolation (SI) (literature found)
  • Maximum Likelihood (ML)
• Create m-File that takes in time delays and outputs vectors. Geometry problem.
• Create m-function that does change of coordinates for the microphones, for use in above m-File.
• Start writing abstract for Undergrad Research Conference
• Read papers
  • Chen/Yao/Hudson
  • Brandstein/Addock/Silverman
  • Abel/Smith
• Keep in mind several applications
  • GIZMO Project (collective of small robots)
  • CONDOR Project (wireless access point UAV)
  • ShotSpotter

     
     

Day’s Reflections

I spent the majority of today learning about the Maximum Likelihood Estimator. I finished up notes on one of the papers I’ve been working on as well.

I drafted an explanation of the Maximum Likelihood estimator (see my previous post). It’s very complex, and I can see already why it’s not an attractive algorithm.

First, it’s very computationally heavy–it needs to do analysis for every time delay for each sensor pair for each point using the least-squares method. This can lead to infinitely many calculations, and would require some serious hardware, driving up the cost of our system . The number of calculations would also slow our system down, making it unsuitable for many applications.

Second, it stems from a very simplistic assumption that noise mediates a linear relationship between input and output. Though this approximation can lead to suitable results some of the time, It cannot guarantee such a thing all the time. It’s possible that there can be a nonlinear correlation between the input and output, and that it cannot be suitably described by a linear relation involving a random variable.

Third, it’s hard to generalize. Noise is something which will change with the size of the room. If you were to install the system in multiple rooms, depending on the size and shape of the room, performance will vary. Further, should you so much as switch off a fan or move a table, you would need to recalibrate the system.

I’ve also decided to enter in the UCSD Undergraduate Research Conference. I need to prepare a 15-minute presentation on my project, and have an abstract and title ready ASAP. In order to have enough material and be prepared, my timeline for this project will be quite compressed. It’s going to be a challenge, but I’m looking forward to it.

And now, I shut my laptop, and leave my project here at my desk in Calit2 for the day. See you tomorrow!

Maximum Likelihood Estimator

Introduction

The localization problem can seem fairly straightforward. Compute the lines and find the point at which they intersect–high-school algebra, almost. A difficulty arises when the lines do not intersect–something which will always happen in our localization system.

Why does this happen? The theoretical TDOA for the ith sensor pair is given by

Where mi1 and mi2 are coordinates of the two sensors, and s is the coordinate of the source. When we say sensor pair, we mean a unique combination of two sensors within a single cluster. (For a cluster with 4 sensors, there are 6 unique pairs)

It seems fairly easy to get the source coordinates from here. One just has to back solve Ti for the vector s, and everything is dandy. There are two issues here.

One is the issue of noise. No system is perfect. There is always electric noise and ambient noise that alters the signal the microphone and the signal processor receive. Another comes from the calculation of the time shift. Unlike other vibrations, sound waves have a wide band of frequencies, and can be non-periodic. In order to get time delay, you need to decompose the signal into the sine waves that compose it (by using a Fourier Transform), computing the phase shift of one of the components, and then get the time delay using the frequency and phase shift. Both problems compound each other to create errors in our observed TDOA. To distinguish it from our theoretical TDOA T, we will call this observed TDOA τ.

The purpose of the estimator is to use the data we have to get the data we don’t have, taking into account the errors present in our estimation. I will begin my investigation of estimators with the Maximum Likelihood estimator, and make subsequent posts as I get further into this project.

 
 

Maximum Likelihood estimator [2] [3]

http://en.wikipedia.org/wiki/Maximum_likelihood

The maximum likelihood estimator is a standard method based on the signal sent, the signal received, and the noise in the system.

The maximum likelihood estimator starts with a basic assumption. It assumes that there is a linear relationship between the signal that is sent (theoretical) and the signal that is received (observed). In other words:

where zI is a real Gaussian random variable. A real random variable is a variable which can take on any real value, but certain values have certain probability densities. Generally, Gaussian random variables are in written in the form

σ is the variance of the function, and μ is the mean.

The probability density function (pdf) determines the probability densities. For a Gaussian random variable, the pdf is given by

The variance is a measure of how fast the probability density falls off. For example, MATLAB tells us that for a variance of one, we see the following:

The blue dotted lines show the variance, the solid blue line shows the mean. It’s easy to see that it is most likely for the variable to be in the region bounded by the variance, but the probability of something like that happening is very low. The variance of our noise will be determined by various factors of the room size, configuration, ambient noise, etc.

We need to know the probability that the noise will stay in a defined region. To get the probability of the random variable being less than a given value, we need something called a cumulative density function (cdf). The cdf is given as

In order to understand the error, we need to find the probability that our τ is the same as our T. We begin by revisiting our first equation, and fixing Ti to be a constant.

Since Ti is now constant, it is the same as saying that zi is being shifted by Ti. We can now write τ as a Gaussian random variable:

We want to know the probability density of τi, given by

The idea of the ML estimator is that it picks the result with the lowest error over all possible Ti values. To do this, we need to find when the probability is at its highest. It’s worth noticing that for any constant C, the following is true:

Therefore, the maximum value of this function happens when the value

is at its lowest for the sensor pair within the cluster. For the cluster as a whole, the goal is to minimize the quantity

 
 

Revisiting our formula for Ti:

it becomes clear the only real variable in this problem is the coordinates of the source. So, the minimized quantity will take into account the positions of the microphones, our estimate of time delay, and the supposed position of the source.

Task List

• Research Estimators
  • Linear Intersection (LI)
  • Spherical Interpolation (SI)
  • Maximum Likelihood (ML)
• Create m-File that takes in time delays and outputs vectors. Geometry problem.
• Create m-function that does change of coordinates for the microphones, for use in above m-File.
• Start writing abstract for Undergrad Research Conference
• Read papers
  • Chen/Yao/Hudson
  • Brandstein/Addock/Silverman
• Keep in mind several applications
  • GIZMO Project (collective of small robots)
  • CONDOR Project (wireless access point UAV)
  • ShotSpotter

     
     

Chen, Yao, Hudson: Source Localization and Beamforming

My notes on a research paper. Underlined text marks points needing more investigation.

• Distributed sensor networks have many applications
• Main purpose of a sensor network is to detect, ID, locate, track any objects of interest.
• Applications
  • Military: surveillance, recon, combat
  • Hearing aids, sound enhancement, guiding a camera
• Physical Features
  • Paper deals with acoustic and seismic sources. My notes will focus on the characteristics of the acoustic source. (Seismic sources are sources of vibration). Obviously, the sources differ by the kind of waves they put out.
  • Wideband.
    • Any waveform can be decomposed into a bunch of sine waves at differing frequencies and amplitude. The bandwidth of the signal is determined by comparing the highest frequency component to the lowest frequency component.
    • Acoustic signals have a very wide band (the highest frequency is 500 times greater than the lowest frequency). Because the components are so vastly different, there is no characteristic wavelength, and time delays require some signal processing to compute.
  • Far-field vs. Near-field source
    • Waves emanating from a source are spherical. If the distance between sensors in a cluster is comparable to the distance to the source, there will be a noticeable time delay between several sensors clustered together. This is called a near-field source.
    • When the distance between sensors is much smaller than the distance to the source, the wavefront appears as a plane to the cluster. The cluster can only determine the direction of arrival of the sound, which is the normal vector of the “plane” received.
  • Speed of propagation
    • Thankfully, the speed of propagation of sound waves in air is a known constant. Any environmental factors have a predictable effect on propagation speed, and the speed of sound in the environment can be accurately calculated.
    • This is important; it means less work in localization.
  • Free Space versus reverberant propagation
    • If a sensor network is outdoors in a flat plane, there is no reverberation (echoes). The sensor network only sees the waves from the source.
    • If a sensor network’s environment has obstacles that can reflect sound (hills, trees, walls, desks, etc), reverberation will occur. The sensor network will see the waves directly from the source, as well as waves from the source that have been reflected off of obstacles. These indirect waves can give the false illusion of a second source, and cause the localization to be incorrect.

  Source:

  J.C. Chen, R.E. Hudson, and K. Yao, “Collaborative Signal and Information Processing in Microsensor Networks: Source Localization and Beamforming”, in IEEE Signal Processing Magazine, Mar. 2002, pp. 30-39