# algorithm

• September 19th, 2009, 04:30 PM
AmmrO
algorithm
Hi everyone,

I am an electrical engineering student, and i am in my senior year and i am working on my senior project and i have never worked with java before but my project needs a java code version of my algorithm. so if anybody can help me with it, i would really appreciate it.

Here is the algorithm:

The lowest magnitude difference algorithm will be explained in details below:
〖AP〗_1=a,〖AP〗_2=b,〖 AP〗_3=c ,〖 AP〗_4=d
x→[x_a,x_b,x_c,x_d ]
y→[y_a,y_b,y_c,y_d ] .............

p_1=[a_1,b_1,c_1,d_1]
p_2=[a_2,b_2,c_2,d_2 ]
p_3=[a_3,b_3,c_3,d_3]

|p_1-x|=√([(〖a_1-x_a)〗^2+(〖b_1-x_b)〗^2+(〖c_1-x_c)〗^2+(〖d_1-x_d)〗^2 ] )=α dB
|p_2-x|=√([(〖a_2-x_a)〗^2+(〖b_2-x_b)〗^2+(〖c_2-x_c)〗^2+(〖d_2-x_d)〗^2 ] )=β dB
|p_3-x|=√([(〖a_3-x_a)〗^2+(〖b_3-x_b)〗^2+(〖c_3-x_c)〗^2+(〖d_3-x_d)〗^2 ] )=γ dB

The smallest value of β,γ,α is the right location match to where the client is.
e.g., if β is the smallest, then p_2≈x

thanks in advance for any help ... i really need it :)
• September 19th, 2009, 06:49 PM
helloworld922
Re: algorithm
Sorry, but I'm not a electrical person...

Could you explain what this algorithm does in plain english :D

A step-by-step description of what your algorithm is would be nice, too.
• September 21st, 2009, 01:36 PM
AmmrO
Re: algorithm
Allright, here is the explanation:

this alogrithm is suppose to help in location identification sytem. i am trying to locate a device in a floor in building covered with Wi-Fi, we have 8 access point in the floor. i am using the pattern matching technique. for example, i will take readings of signal strength in 60 locations in the floor, signal strength of 8 APs at each locations. then i will make a database or java list with all the readings. all this is called the offline stage. the online stage, is when the user is try to locate himself or herself. so for the user to locate him, the software is suppose to take the SSR at his location and send to the algorithm to take the mean of the SSR at the location of the user subtracted from each previously recorded SSR in the database and the smallest value of these means will mean that the user is somewhere closer to this location than the other location in the list.

i hope its clear, any Questions , feel free to ask !!!
• September 21st, 2009, 01:41 PM
AmmrO
Re: algorithm
〖AP〗_1=a,〖AP〗_2=b,〖 AP〗_3=c ,〖 AP〗_4=d
x→[x_a,x_b,x_c,x_d ]
y→[y_a,y_b,y_c,y_d ] .............The values xa, xb …xn, ya .. yn are the mean of the sample of SNR that has been recorded for a certain AP of the 2 different clients

p_1=[a_1,b_1,c_1,d_1]
p_2=[a_2,b_2,c_2,d_2 ] .............The p1, p2, p3….Pn are different locations. The a1, a2, a3 are the mean values of the SNR samples that are recorded into the database for different APs
p_3=[a_3,b_3,c_3,d_3]

|p_1-x|=√([(〖a_1-x_a)〗^2+(〖b_1-x_b)〗^2+(〖c_1-x_c)〗^2+(〖d_1-x_d)〗^2 ] )=α dB
|p_2-x|=√([(〖a_2-x_a)〗^2+(〖b_2-x_b)〗^2+(〖c_2-x_c)〗^2+(〖d_2-x_d)〗^2 ] )=β dB
|p_3-x|=√([(〖a_3-x_a)〗^2+(〖b_3-x_b)〗^2+(〖c_3-x_c)〗^2+(〖d_3-x_d)〗^2 ] )=γ dB

The smallest value of β,γ,α is the right location match to where the client is.
e.g., if β is the smallest, then p_2≈x

• The above algorithm calculates the differences between client and databases each corresponding AP’s values, then adding them up and finally taking the square root to give us a list of finite numbers. The smallest of these finite numbers will match a unique set of pre-defined location with the current client location.
• September 21st, 2009, 07:59 PM
helloworld922
Re: algorithm
Ok, tell me if this is what you want:

* You have 4 different inputs for signal strengths, a,b,c,d which are floating point numbers (inactive set).
* You have a set of sensor readings for xa,xb,xc,xd, and ya,yb,yc,yd from each sensor (active set)
* The points |p1-x|,|p2-x|,|p3-x|...|pn-x| are computed via sqrt((an-ax)^2+...
* The value to take is the smallest |pn-x| of this list
* Do the same thing with y (|p1-y|,|p2-y|,...|pn-y|)

Is this correct?

edit: Here's the code I came up with based on the above algorithm

Code :

```public static class SensorDatabase { private Point[] inactiveDatabase, x, y;   /** * Constructs a database of sensor readings * * @param inactiveAValues * @param inactiveBValues * @param inactiveCValues * @param inactiveDValues * @param xAValues * @param xBValues * @param xCValues * @param xDValues * @param yAValues * @param yBValues * @param yCValues * @param yDValues */ public SensorDatabase(double[] inactiveAValues, double[] inactiveBValues, double[] inactiveCValues, double[] inactiveDValues, double[] xAValues, double[] xBValues, double[] xCValues, double[] xDValues, double[] yAValues, double[] yBValues, double[] yCValues, double[] yDValues) { try { this.inactiveDatabase = new Point[inactiveAValues.length]; this.x = new Point[xAValues.length]; this.y = new Point[yAValues.length]; for (int i = 0; i < inactiveAValues.length; i++) { this.inactiveDatabase[i] = new Point(inactiveAValues[i], inactiveBValues[i], inactiveCValues[i], inactiveDValues[i]); } for (int i = 0; i < xAValues.length; i++) { this.x[i] = new Point(xAValues[i], xBValues[i], xCValues[i], xDValues[i]); this.y[i] = new Point(yAValues[i], yBValues[i], yCValues[i], yDValues[i]); } } catch (Exception e) { throw new RuntimeException("Error: array indices didn't match!"); } }   /** * Constructs a database of sensor readings * * @param inactiveDatabase * @param x * @param y */ public SensorDatabase(Point[] inactiveDatabase, Point[] x, Point[] y) { if (x.length != y.length) { throw new RuntimeException( "Error: x and y lengths aren't the same"); } this.inactiveDatabase = inactiveDatabase.clone(); this.x = x.clone(); this.y = y.clone(); }   /** * Finds the closest x value * * @return */ public Point computeClosestX() { Point closest = this.x[0]; double distance = Point.computeDistance(this.inactiveDatabase[0], this.x[0]); for (int i = 1; i < this.x.length; i++) { if (distance > Point.computeDistance(this.inactiveDatabase[i], this.x[i])) { closest = this.x[i]; distance = Point.computeDistance(this.inactiveDatabase[i], this.x[i]); } } return closest; }   /** * Finds the closest y value * * @return */ public Point computeClosestY() { Point closest = this.y[0]; double distance = Point.computeDistance(this.inactiveDatabase[0], this.y[0]); for (int i = 1; i < this.y.length; i++) { if (distance > Point.computeDistance(this.inactiveDatabase[i], this.y[i])) { closest = this.y[i]; distance = Point.computeDistance(this.inactiveDatabase[i], this.y[i]); } } return closest; }   public static class Point { public double a, b, c, d;   /** * Constructs a point * * @param a * @param b * @param c * @param d */ public Point(double a, double b, double c, double d) { this.a = a; this.b = b; this.c = c; this.d = d; }   /** * Computes the distance between p1 and p2 as defined as: * * sqrt((p1.a - p2.a)^2 + (p1.b - p2.b)^2 + (p1.c - p2.c)^2 + (p1.d * - p2.d, 2)^2); * * @param p1 * @param p2 * @return */ public static double computeDistance(Point p1, Point p2) { return Math.sqrt(Math.pow(p1.a - p2.a, 2) + Math.pow(p1.b - p2.b, 2) + Math.pow(p1.c - p2.c, 2) + Math.pow(p1.d - p2.d, 2)); } } }```
• September 22nd, 2009, 01:14 PM
AmmrO
Re: algorithm
thanks so much for the Code but i think the way the algorithm i wrote it was not clear and confusing .. my bad

i am not working with coordinates, i rewrote the algirthm , look at it and see if its more clear or not... and thank you so much for your help .. i really do appreciate it :)

these are the APs - access points - that we have in the floor :
AP_1=a, AP_2=b, AP_3=c , AP_4=d, AP_5 =e, AP_6=f, AP_7=g, AP_8=h

i will take the mean of the signal in 4 samples of signal strength so it will be more accurate from each AP:
|x_a|=√([(〖x_a1)〗^2+(〖x_a2)〗^2+(〖x_a3)〗^2+(〖x_a4)〗^2 ] )
|x_b|=√([(〖x_b1)〗^2+(〖x_b2)〗^2+(〖x_b3)〗^2+(〖x_b4)〗^2 ] )
|x_c|=√([(〖x_c1)〗^2+(〖x_c2)〗^2+(〖x_c3)〗^2+(〖x_c4)〗^2 ] )
x_d|=√([(〖x_d1)〗^2+(〖x_d2)〗^2+(〖x_d3)〗^2+(〖x_d4)〗^2 ] )
|x_e|=√([(〖x_e1)〗^2+(〖x_e2)〗^2+(〖x_e3)〗^2+(〖x_e4)〗^2 ] )
|x_f|=√([(〖x_f1)〗^2+(〖x_f2)〗^2+(〖x_f3)〗^2+(〖x_f4)〗^2 ] )
|x_g|=√([(〖x_g1)〗^2+(〖x_g2)〗^2+(〖x_g3)〗^2+(〖x_g4)〗^2 ] )
|x_h|=√([(〖x_h1)〗^2+(〖x_h2)〗^2+(〖x_h3)〗^2+(〖x_h4)〗^2 ] )

x→[x_a,x_b,x_c,x_d,x_e,x_f,x_g,x_h] .............The values xa, xb …xn are the mean of the sample of SNR that has been recorded for a certain AP of the 2 different clients

this is the list of the previously recorded signal strengths: can we have a list of them in Java instead of database????

p_1=[a_1,b_1,c_1,d_1]
p_2=[a_2,b_2,c_2,d_2 ] .............The p1, p2, p3….Pn are different locations. The a1, a2, a3 are the mean values of the SNR samples that are recorded into the database for different APs
p_3=[a_3,b_3,c_3,d_3,e_3,f_3,g_3,h_3]
.
.
.
.
.
P_n=[a_n,b_n,c_n,d_n,e_n,f_n,g_n,h_n]

this is where the matching will take place:

|p_1-x|=√([(〖a_1-x_a)〗^2+(〖b_1-x_b)〗^2+(〖c_1-x_c)〗^2+(〖d_1-x_d)〗^2+(〖e_1-x_e)〗^2+(〖f_1-x_f)〗^2+(〖g_1-x_g)〗^2+(〖h_1-x_h)〗^2 ] )=α dB
|p_2-x|=√([(〖a_2-x_a)〗^2+(〖b_2-x_b)〗^2+(〖c_2-x_c)〗^2+(〖d_2-x_d)〗^2+(〖e_2-x_e)〗^2+(〖f_2-x_f)〗^2+(〖g_2-x_g)〗^2+(〖h_2-x_h)〗^2 ] )=β dB
|p_3-x|=√([(〖a_3-x_a)〗^2+(〖b_3-x_b)〗^2+(〖c_3-x_c)〗^2+(〖d_3-x_d)〗^2+(〖e_3-x_e)〗^2+(〖f_3-x_f)〗^2+(〖g_3-x_g)〗^2+(〖h_3-x_h)〗^2 ] )=γ dB
.
.
.
.
.
p_n-x|=√([(〖a_n-x_a)〗^2+(〖b_n-x_b)〗^2+(〖c_n-x_c)〗^2+(〖d_n-x_d)〗^2+(〖e_n-x_e)〗^2+(〖f_n-x_f)〗^2+(〖g_n-x_g)〗^2+(〖h_n-x_h)〗^2 ] )= mega dB

The smallest value among β,γ,α is the right location match to where the client is. e.g., if β is the smallest, then p_2≈x
• September 22nd, 2009, 11:48 PM
helloworld922
Re: algorithm
Ok, here's the what i've come up with:

* You have access points on 8 different floors. They will read in 4 (or more) x values each, and compute their mean via those formula you had for |xa|,...|xh|. *note: did you mean to divide by 4 since you wanted an average, or was that intentionally left out?
* p_1,p_2,...p_n are SNR sample data from different access points (each have an a,b,c,d,e,f,g,h value)
* compute |p_1-x|...|p_n-x| and pick the smallest value. This is ≈x

correct?

Code :

```public class SensorList { private Readings[] snrList; private Readings averageX;   /** * Constructs the SNR list * * @param snrList * @param x */ public SensorList(Readings[] snrList, Readings[] x) { this.snrList = snrList.clone(); // compute the mean values for x // compute a double a = 0; for (int i = 0; i < x.length; i++) { a += x[i].a; } a /= x.length; // compute b double b = 0; for (int i = 0; i < x.length; i++) { b += x[i].b; } b /= x.length; // compute c double c = 0; for (int i = 0; i < x.length; i++) { c += x[i].c; } c /= x.length; // compute d double d = 0; for (int i = 0; i < x.length; i++) { d += x[i].d; } d /= x.length; // compute e double e = 0; for (int i = 0; i < x.length; i++) { e += x[i].e; } e /= x.length; // compute f double f = 0; for (int i = 0; i < x.length; i++) { f += x[i].f; } f /= x.length; // compute g double g = 0; for (int i = 0; i < x.length; i++) { g += x[i].g; } g /= x.length; // compute h double h = 0; for (int i = 0; i < x.length; i++) { h += x[i].h; } h /= x.length; this.averageX = new Readings(a, b, c, d, e, f, g, h); }   /** * Finds the smallest |pn-x| value * * @return |pn-x| */ public double computeSmallestX() { double smallest = Readings.computeVal(this.snrList[0], this.averageX); for (int i = 1; i < this.snrList.length; i++) { double val = Readings.computeVal(this.snrList[i], this.averageX); if (smallest > val) { smallest = val; } } return smallest; }   /** * Finds the which pn gives the smallest |pn-x| value * * @return Readings of |pn-x| that is the smallest */ public Readings computeWhichSmallestX() { int index = 0; double smallest = Readings.computeVal(this.snrList[0], this.averageX); for (int i = 1; i < this.snrList.length; i++) { double val = Readings.computeVal(this.snrList[i], this.averageX); if (smallest > val) { index = i; smallest = val; } } return this.snrList[index]; }   public static class Readings { public double a, b, c, d, e, f, g, h;   /** * Constructs a reading sample * @param a * @param b * @param c * @param d * @param e * @param f * @param g * @param h */ public Readings(double a, double b, double c, double d, double e, double f, double g, double h) { this.a = a; this.b = b; this.c = c; this.d = d; this.e = e; this.f = f; this.g = g; this.h = h; }   /** * Computes |pn-x| as defined: * * sqrt((pn.a - x.a)^2 + (pn.b - x.b)^2 + (pn.c - x.c)^2 + (pn.d - * x.d)^2+(pn.e-x.e)^2+(pn.f-x.f)^2+(pn.g-x.g)^2+(pn.h-x.h)^2); * * @param pn * @param x * @return */ public static double computeVal(Readings pn, Readings x) { return Math.sqrt(Math.pow(pn.a - x.a, 2) + Math.pow(pn.b - x.b, 2) + Math.pow(pn.c - x.c, 2) + Math.pow(pn.d - x.d, 2) + Math.pow(pn.e - x.e, 2) + Math.pow(pn.f - x.f, 2) + Math.pow(pn.g - x.g, 2) + Math.pow(pn.h - x.h, 2)); } } }```
• September 23rd, 2009, 01:27 AM
AmmrO
Re: algorithm
Quote:

* You have access points on 8 different floors. They will read in 4 (or more) x values each, and compute their mean via those formula you had for |xa|,...|xh|.
actually i am having 8 access point in the floor. i will get 4 readings from each AP. a reading per second for 4 seconds and then calculate the mean of the each AP values to get the mean Xa .....xh

Quote:

*note: did you mean to divide by 4 since you wanted an average, or was that intentionally left out?
i left intentionally :)

Quote:

* p_1,p_2,...p_n are SNR sample data from different access points (each have an a,b,c,d,e,f,g,h value)
P_1 is a location in the floor where i will take the reading so i can use this reading in my program for comparing and matching. so i might have over 30 locations. these values will be a constant in the code because i will take the reading and insert it in the code. in the list form i was asking you about :)

Quote:

* compute |p_1-x|...|p_n-x| and pick the smallest value. This is ≈x
yeah the smallest value u would get means that P_n location is the closest to the user's location x
• September 23rd, 2009, 06:23 PM
helloworld922
Re: algorithm
Hmm... ok, maybe finally i've understood what you want :P

From the program's perspective, it doesn't matter which floor the access points are on, just that there are 8 of them :)

I do have to change computing the averages, though.

Whether it's called a list or a database from the program's perspective doesn't matter.

What did you mean by comparing to P_1? Is that the user's location? Or is P_1 through P_N a potential position for the user?

Code :

```public class SensorList { private Readings[] snrList; private Readings averageX;   /** * Constructs the SNR list * * @param snrList * @param x */ public SensorList(Readings[] snrList, Readings[] x) { this.snrList = snrList.clone(); // compute the mean values for x // compute a double a = 0; for (int i = 0; i < x.length; i++) { a += x[i].a * x[i].a; } a = Math.sqrt(a); // compute b double b = 0; for (int i = 0; i < x.length; i++) { b += x[i].b * x[i].b; } b = Math.sqrt(b); // compute c double c = 0; for (int i = 0; i < x.length; i++) { c += x[i].c * x[i].c; } c = Math.sqrt(c); // compute d double d = 0; for (int i = 0; i < x.length; i++) { d += x[i].d * x[i].d; } d = Math.sqrt(d); // compute e double e = 0; for (int i = 0; i < x.length; i++) { e += x[i].e * x[i].e; } e = Math.sqrt(e); // compute f double f = 0; for (int i = 0; i < x.length; i++) { f += x[i].f * x[i].f; } f = Math.sqrt(f); // compute g double g = 0; for (int i = 0; i < x.length; i++) { g += x[i].g * x[i].g; } g = Math.sqrt(g); // compute h double h = 0; for (int i = 0; i < x.length; i++) { h += x[i].h * x[i].h; } h = Math.sqrt(h); this.averageX = new Readings(a, b, c, d, e, f, g, h); }   /** * Finds the smallest |pn-x| value * * @return |pn-x| */ public double computeSmallestX() { double smallest = Readings.computeVal(this.snrList[0], this.averageX); for (int i = 1; i < this.snrList.length; i++) { double val = Readings.computeVal(this.snrList[i], this.averageX); if (smallest > val) { smallest = val; } } return smallest; }   /** * Finds the which pn gives the smallest |pn-x| value * * @return Readings of |pn-x| that is the smallest */ public Readings computeWhichSmallestX() { int index = 0; double smallest = Readings.computeVal(this.snrList[0], this.averageX); for (int i = 1; i < this.snrList.length; i++) { double val = Readings.computeVal(this.snrList[i], this.averageX); if (smallest > val) { index = i; smallest = val; } } return this.snrList[index]; }   public static class Readings { public double a, b, c, d, e, f, g, h;   /** * Constructs a reading sample * * @param a * @param b * @param c * @param d * @param e * @param f * @param g * @param h */ public Readings(double a, double b, double c, double d, double e, double f, double g, double h) { this.a = a; this.b = b; this.c = c; this.d = d; this.e = e; this.f = f; this.g = g; this.h = h; }   /** * Computes |pn-x| as defined: * * sqrt((pn.a - x.a)^2 + (pn.b - x.b)^2 + (pn.c - x.c)^2 + (pn.d - * x.d)^2+(pn.e-x.e)^2+(pn.f-x.f)^2+(pn.g-x.g)^2+(pn.h-x.h)^2); * * @param pn * @param x * @return */ public static double computeVal(Readings pn, Readings x) { return Math.sqrt(Math.pow(pn.a - x.a, 2) + Math.pow(pn.b - x.b, 2) + Math.pow(pn.c - x.c, 2) + Math.pow(pn.d - x.d, 2) + Math.pow(pn.e - x.e, 2) + Math.pow(pn.f - x.f, 2) + Math.pow(pn.g - x.g, 2) + Math.pow(pn.h - x.h, 2)); } } }```
• September 23rd, 2009, 07:17 PM
AmmrO
Re: algorithm
Quote:

What did you mean by comparing to P_1? Is that the user's location? Or is P_1 through P_N a potential position for the user?
its a potiental position not the user location, we will have 30 or more potiential locations that will be used as reference .. i hope this explaination is clearer :) ...

i realllly reallly appriecate your help so much, i am sorry that i wasnt clear from the beginning :)

the code looks awesome but i dont understand anything :) lol
• September 23rd, 2009, 11:29 PM
helloworld922
Re: algorithm
Haha, it's not awesome, too be honest. It was really lousy programming, even for me. But hopefully it should get done what you needed to get done. I'd explain it, but there's an awful lot of cs topics in there. Now that I think about it, I didn't tell you how to use it... :P

How were you planning on sending information to this program? I can write you a harness so that you can actually use this code with little effort :D

I didn't change the code for the Pn stuff, so hopefully it should work correctly.

Here's what it's doing:

I'm assuming you have sensor readings at each of the access points (these are the Pn stuff), and the user has some device that has the X readings. Then, the closest access point (or what-ever the |Pn-X| formulas do) is computed by |Pn-X|

I wrote two methods, one that tells you which Pn gives the closest value, and another one that gives what that value was.
• September 24th, 2009, 12:47 AM
AmmrO
Re: algorithm
WOW, thats exactly what is its suppose to do, compare Pn with the X and the algorithm does some math and when we get the smallest value, then the user is at this Pn :) ..... whats up with the harness ?? how can we do this ??
i owe you seriously man...
• September 24th, 2009, 09:58 AM
helloworld922
Re: algorithm
A harness is basically code that allows someone who is either lazy or has little programming experience to use the algorithm easily :) Right now, it's just a bare algorithm. Depending on how this data will be sent to this program, I can write a useful harness. Is the data being read from a file? Are you/someone going to type it in (in which case, GUI or console)? Is there some sort of data stream that the program can read from? The possibilities are endless.

Oh, and it would be much easier to write the harness if you gave me specifications on how the data would be formatted, and some sample values (and the expected output if possible).
• September 24th, 2009, 09:18 PM
AmmrO
Re: algorithm
Yes. I want the data to be read from a text file. The text file has an indent in between each String and a line of Strings for each data set. Example shown below:

# \$Creator: Network Stumbler Version 0.4.0
# \$Format: wi-scan summary with extensions
# Latitude Longitude ( SSID ) Type ( BSSID ) Time (GMT) [ SNR Sig Noise ] # ( Name ) Flags Channelbits BcnIntvl DataRate LastChannel
# \$DateGMT: 2009-09-18
N 0.0000000 E 0.0000000 ( wifi ) BSS ( ab:cd:ef:gh:ij:kl ) 00:35:19 (GMT) [ 35 84 49 ] # ( ) 0421 00000002 102 540 1
N 0.0000000 E 0.0000000 ( wifi ) BSS ( mn:rp:qr:st:uv:wx ) 00:35:19 (GMT) [ 73 122 49 ] # ( ) 0421 00000040 102 540 6
N 0.0000000 E 0.0000000 ( wifi ) BSS ( 12:34:56:78:90:12 ) 00:35:19 (GMT) [ 17 66 49 ] # ( ) 0421 00000800 102 540 11
N 0.0000000 E 0.0000000 ( wifi ) BSS ( zy:09:ab:87:cd:76 ) 00:35:19 (GMT) [ 31 80 49 ] # ( ) 0421 00000002 102 540 1

The colored numbers are the SNR (signal strength) values. Each different color represents a different AP. The closer the client is to the AP, the larger this value becomes with respect to that AP.

I am planing on building a GUI and trying to use simple GUI builders like Jvider. I don't know how to use the algorithm and import the file into the GUI builder.
I am also planing to displaying the result on a floor plan that I already have. This is another big challenge for me.

I really appreciate your time and efforts.