package DataStructure; import helper.ListBTS; import java.awt.Point; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.ObjectInputStream; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.Date; import java.util.List; public class gsmBayes { GSMMap map; public static void main(String[] args) throws FileNotFoundException, IOException, ClassNotFoundException { NormDistribution one = new NormDistribution(30, 0.21); NormDistribution two = new NormDistribution(30, 0.21); System.out.println(one.intersection(two) + " " + two.intersection(one)); // System.out.println(10 * Math.log10(0.0)); // Comparator test // ArrayList testlist = new ArrayList(); // testlist.add(new SingleBTS(999, "letzte")); // testlist.add(new SingleBTS(124, "zweite")); // testlist.add(new SingleBTS(123, "erste")); // ArrayList testlistcopy = new // ArrayList(testlist); // Collections.copy(testlistcopy, testlist); // Collections.sort(testlist, new BTSArfcnComparator()); // testlist.get(0).name = "blabla"; // System.out.println(testlist); // System.out.println(testlistcopy); // gsmmap object einlesen ObjectInputStream ois = new ObjectInputStream(new FileInputStream( "interpolatedGSMMap.obj")); GSMMap map = (GSMMap) ois.readObject(); System.out.println("Start"); // ArrayList MR = getMR106(); ArrayList MR = subtractBTS(getMensa(), 0); double[][] scoremap = computeScore(MR, map); System.out.println("fertig"); double maxSingleProbability = 0; double sumOfProbabilities = 0; for (int x = 0; x < scoremap.length; x++) { for (int y = 0; y < scoremap[0].length; y++) { if (scoremap[x][y] > 0) { // System.out.println("positive Wahrsch. gefunden! " // + scoremap[x][y]); if (scoremap[x][y] > maxSingleProbability) { maxSingleProbability = scoremap[x][y]; System.out.println("neues Maximum bei " + x + "/" + y + " !"); } sumOfProbabilities += scoremap[x][y]; // sind das vll. die falschen Wahrscheinlihckeiten? // P(RSS|Kachel) = 1 oder // P(Kachel|RSS) = 1? } } } System.out.println("Summe: " + sumOfProbabilities + ", maximum: " + maxSingleProbability); GoogleOut out = new GoogleOut(map, "bla"); // out.write(); // fill up to confidence level double[][] confidence = toConfidence(scoremap, 0.75); double confidencesum = 0; for (int x = 0; x < confidence.length; x++) { for (int y = 0; y < confidence[0].length; y++) { confidencesum += confidence[x][y]; } } System.out.println("Confidence level bei: " + confidencesum); out.writeProbability(confidence, "probabilities.kml"); } /** * Returns all tiles until they sum up to confidence. scoremap gets * destroyed * * @param scoremap * @param d * @return */ public static double[][] toConfidence(double[][] scoremap, double confidence) { if (confidence == 1 || confidence > 1) { return scoremap; } // scoremap to possibility objects (faster...) PossibilityObject[] possibilities = toPossibility(scoremap); double sum_confidence = 0; double[][] result = new double[scoremap.length][scoremap[0].length]; int boundary = possibilities.length - 1; while (sum_confidence < confidence) { sum_confidence += possibilities[boundary].possibility; int x = possibilities[boundary].x; int y = possibilities[boundary].y; result[x][y] = possibilities[boundary].possibility; boundary--; } // result = PossObjToScoremap(possibilities, boundary, result); /* * double max = 0; int xmax = 0; int ymax = 0; for (int x = 0; x < * scoremap.length; x++) { for (int y = 0; y < scoremap[0].length; y++) * { if (scoremap[x][y] > max) { max = scoremap[x][y]; xmax = x; ymax = * y; } * * } } // max found. * * result[xmax][ymax] = scoremap[xmax][ymax]; sum_confidence += * scoremap[xmax][ymax]; scoremap[xmax][ymax] = 0; } */ return result; } @SuppressWarnings("unused") private static double[][] PossObjToScoremap( PossibilityObject[] possibilities, int boundary, double[][] result) { for (int i = possibilities.length - 1; i <= boundary; i--) { int x = possibilities[i].x; int y = possibilities[i].y; result[x][y] = possibilities[i].possibility; } return result; } @SuppressWarnings("unused") private static ArrayList gettheater() { ArrayList MR2 = new ArrayList(); ArrayList MR = new ArrayList(); MR.add(new SingleBTS(806, Double.NaN, -101, true, new Date(), "lookup", 1)); MR.add(new SingleBTS(817, Double.NaN, -96, true, new Date(), "lookup", 1)); MR.add(new SingleBTS(815, Double.NaN, -92, true, new Date(), "lookup", 12)); MR.add(new SingleBTS(823, Double.NaN, -97, true, new Date(), "lookup", 0.25)); MR.add(new SingleBTS(871, Double.NaN, -90, true, new Date(), "lookup", 1)); MR.add(new SingleBTS(877, Double.NaN, -101, true, new Date(), "lookup", 1)); MR2.add(new SingleBTS(806, Double.NaN, -101, true, new Date(), "lookup")); MR2.add(new SingleBTS(817, Double.NaN, -96, true, new Date(), "lookup")); MR2.add(new SingleBTS(815, Double.NaN, -92, true, new Date(), "lookup")); MR2.add(new SingleBTS(823, Double.NaN, -97, true, new Date(), "lookup")); MR2.add(new SingleBTS(871, Double.NaN, -90, true, new Date(), "lookup")); MR2.add(new SingleBTS(877, Double.NaN, -101, true, new Date(), "lookup")); return MR; } @SuppressWarnings("unused") private static ArrayList getArt() { ArrayList MR = new ArrayList(); MR.add(new SingleBTS(806, Double.NaN, -90, true, new Date(), "lookup", 3.33)); MR.add(new SingleBTS(817, Double.NaN, -90, true, new Date(), "lookup", 2.28)); MR.add(new SingleBTS(815, Double.NaN, -88, true, new Date(), "lookup", 2.05)); MR.add(new SingleBTS(823, Double.NaN, -76, true, new Date(), "lookup", 9)); MR.add(new SingleBTS(880, Double.NaN, -96, true, new Date(), "lookup", 4)); MR.add(new SingleBTS(877, Double.NaN, -65, true, new Date(), "lookup", 3.77)); return MR; } @SuppressWarnings("unused") private static ArrayList getMR101() { ArrayList MR = new ArrayList(); MR.add(new SingleBTS(806, Double.NaN, -94, true, new Date(), "lookup")); MR.add(new SingleBTS(817, Double.NaN, -92, true, new Date(), "lookup")); MR.add(new SingleBTS(815, Double.NaN, -88, true, new Date(), "lookup")); MR.add(new SingleBTS(823, Double.NaN, -79, true, new Date(), "lookup")); MR.add(new SingleBTS(880, Double.NaN, -97, true, new Date(), "lookup")); MR.add(new SingleBTS(877, Double.NaN, -84, true, new Date(), "lookup")); return MR; } @SuppressWarnings("unused") private static ArrayList getMR106() { ArrayList MR = new ArrayList(); MR.add(new SingleBTS(806, Double.NaN, -98, true, new Date(), "lookup", 0.25)); MR.add(new SingleBTS(817, Double.NaN, -89, true, new Date(), "lookup", 0.25)); MR.add(new SingleBTS(815, Double.NaN, -85, true, new Date(), "lookup", 0.25)); MR.add(new SingleBTS(823, Double.NaN, -90, true, new Date(), "lookup", 0)); MR.add(new SingleBTS(880, Double.NaN, -98, true, new Date(), "lookup", 0)); MR.add(new SingleBTS(877, Double.NaN, -102, true, new Date(), "lookup", 6.25)); return MR; } @SuppressWarnings("unused") private static ArrayList get79() { ArrayList MR = new ArrayList(); MR.add(new SingleBTS(806, Double.NaN, -88, true, new Date(), "lookup", 2.64)); MR.add(new SingleBTS(817, Double.NaN, -90, true, new Date(), "lookup", 2.05)); MR.add(new SingleBTS(815, Double.NaN, -86, true, new Date(), "lookup", 1.42)); MR.add(new SingleBTS(823, Double.NaN, -87, true, new Date(), "lookup", 1.57)); MR.add(new SingleBTS(871, Double.NaN, -63, true, new Date(), "lookup", 25.4)); MR.add(new SingleBTS(880, Double.NaN, -83, true, new Date(), "lookup", 0.658)); MR.add(new SingleBTS(877, Double.NaN, -93, true, new Date(), "lookup", 10)); ArrayList MR2 = new ArrayList(); MR2.add(new SingleBTS(806, Double.NaN, -87, true, new Date(), "lookup", 2.04)); MR2.add(new SingleBTS(817, Double.NaN, -91, true, new Date(), "lookup", 2.25)); MR2.add(new SingleBTS(815, Double.NaN, -88, true, new Date(), "lookup", 1.32)); MR2.add(new SingleBTS(823, Double.NaN, -85, true, new Date(), "lookup", 1.47)); MR2.add(new SingleBTS(871, Double.NaN, -62, true, new Date(), "lookup", 20.4)); MR2.add(new SingleBTS(880, Double.NaN, -81, true, new Date(), "lookup", 10.658)); MR2.add(new SingleBTS(877, Double.NaN, -97, true, new Date(), "lookup", 10)); /* * MR.add(new SingleBTS(806, Double.NaN, -88, true, new Date(), * "lookup")); MR.add(new SingleBTS(817, Double.NaN, -90, true, new * Date(), "lookup")); MR.add(new SingleBTS(815, Double.NaN, -86, true, * new Date(), "lookup")); MR.add(new SingleBTS(823, Double.NaN, -87, * true, new Date(), "lookup")); MR.add(new SingleBTS(871, Double.NaN, * -63, true, new Date(), "lookup")); MR.add(new SingleBTS(880, * Double.NaN, -83, true, new Date(), "lookup")); MR.add(new * SingleBTS(877, Double.NaN, -93, true, new Date(), "lookup")); */ System.out.println("slightly altered"); return MR; } @SuppressWarnings("unused") private static ArrayList getBermuda() { ArrayList MR = new ArrayList(); MR.add(new SingleBTS(806, Double.NaN, -93, true, new Date(), "lookup", 3.4)); MR.add(new SingleBTS(817, Double.NaN, -88, true, new Date(), "lookup", 5.65)); MR.add(new SingleBTS(815, Double.NaN, -85, true, new Date(), "lookup", 5.1)); MR.add(new SingleBTS(823, Double.NaN, -47, true, new Date(), "lookup", 12.36)); MR.add(new SingleBTS(880, Double.NaN, -92, true, new Date(), "lookup", 10.6)); MR.add(new SingleBTS(877, Double.NaN, -68, true, new Date(), "lookup", 9.1)); return MR; } private static ArrayList getMensa() { ArrayList MR = new ArrayList(); MR.add(new SingleBTS(806, Double.NaN, -95, true, new Date(), "lookup")); MR.add(new SingleBTS(817, Double.NaN, -91, true, new Date(), "lookup")); MR.add(new SingleBTS(815, Double.NaN, -86, true, new Date(), "lookup")); MR.add(new SingleBTS(823, Double.NaN, -86, true, new Date(), "lookup")); MR.add(new SingleBTS(871, Double.NaN, -75, true, new Date(), "lookup")); MR.add(new SingleBTS(880, Double.NaN, -74, true, new Date(), "lookup")); MR.add(new SingleBTS(877, Double.NaN, -87, true, new Date(), "lookup")); return MR; } private static ArrayList subtractBTS(ArrayList MR, double value) { ArrayList result = new ArrayList(); for (int i = 0; i < MR.size(); i++) { int arfcn = MR.get(i).ARFCN; double RXul = MR.get(i).getUldB(); double RXdl = MR.get(i).getDldB(); double var = MR.get(i).getVarianceDLdB(); SingleBTS element = new SingleBTS(arfcn, RXul, RXdl, true, new Date(), "lookup", var); result.add(element); } return result; } public gsmBayes(GSMMap map) { this.map = map; // generate difference between multiple BTSs. // For example: arfcn 877 - arfcn 880, 877-823,... // get OpenBSC arfcn's to calculate ratios // go over all tiles and calculate the probability that this RSS-vector // falls within this tile. Use the gaussian assumption here! // than, return all tiles until they sum up to confidence } /** * Makes a scoremap to a SORTED one dimensional PossibilityObject Array. * Calculates the entropy on the way and prints to Console * * @param scoremap * @return */ private static PossibilityObject[] toPossibility(double[][] scoremap) { int gsmmapsize = (scoremap.length + 1) * (scoremap[0].length + 1); // PossibilityObject[] possibilities = new // PossibilityObject[gsmmapsize]; ArrayList result = new ArrayList( gsmmapsize); double entropy = 0; for (int x = 0; x < scoremap.length; x++) { for (int y = 0; y < scoremap[0].length; y++) { if (scoremap[x][y] != 0) { entropy = entropy + scoremap[x][y] * (Math.log(scoremap[x][y])); } PossibilityObject current = new PossibilityObject(); current.possibility = scoremap[x][y]; current.x = x; current.y = y; result.add(current); } } System.out.println("Entropy dieser Wahrscheibnlichkeitskarte: " + (entropy * (-1))); PossibilityObject[] possibilities = result .toArray(new PossibilityObject[1]); Arrays.sort(possibilities); return possibilities; } /** * Returns all possible tiles that fall within the confidence. Output is the * tile coordinate within the gsm map. DO NOT USE IN THE MOMENT!!!!! * * @param MR * The measurement from the phone that you want to locate * @return */ @SuppressWarnings("unused") static private Point[] search(List MR, GSMMap map, double confidence) { double[][] possibility = new double[map.Xcoords.length][map.Ycoords.length]; double rssProbability = 0; rssProbability = getProbOfMR(map); for (int x = 0; x < map.Xcoords.length; x++) { for (int y = 0; y < map.Ycoords.length; y++) { possibility[x][y] = getPossibility(map.map[x][y], MR, rssProbability); } } return null; } /** * Computes just raw score (not probability) for each tile with given MR * * @param MR * @param map * @return */ static public double[][] computeScore(List MR, GSMMap map) { // get Vector how to sort!!! Important so that subtraction with NaN // doesnÄt destroy too much Information! SingleBTS[] sortVector = getSortVector(MR, map.content()); // sortVector = MR.toArray(new SingleBTS[0]); ArrayList sortedMR = substituteMR(MR, sortVector); // get ratio map ratioElem[][][] ratiomap = getRatio(map, sortVector); // get RatioVector for MR: // make a (shallow) copy of MR to work with // ArrayList sortedMR = new ArrayList(MR); // take the measured MR. Make it to a complete Measurement vector. // SingleBTS[] content = map.content(); // Arrays.sort(content, new BTSArfcnComparator()); // sortedMR = substituteMR(sortedMR, content); // now MR is a complete Vector // sort MR: ascending arfcn. Its the same order as in ratiomap // Collections.sort(sortedMR, new BTSArfcnComparator()); // get Ratio out of sortedMR (MeasurementReportRatio) ratioElem[] MRRatio = new ratioElem[sortedMR.size() - 1]; for (int i = 0; i < sortedMR.size() - 1; i++) { MRRatio[i] = new ratioElem(sortedMR.get(i), sortedMR.get(i + 1)); } // now we can do the Bayes stuff with sortedMR and ratioElem // first get probability that sortedMR appears in ratiomap double[][] probabilitymap = doBayes(MRRatio, ratiomap); return probabilitymap; } private static SingleBTS[] getSortVector(List mR, SingleBTS[] content) { ArrayList result = new ArrayList(content.length); ArrayList NaNs = new ArrayList(content.length); for (int i = 0; i < content.length; i++) { SingleBTS element = ListBTS.getARFCN(mR, content[i]); if (element != null) { result.add(element); } else { NaNs.add(new SingleBTS(content[i].ARFCN, Double.NaN, Double.NaN, true, new Date(), content[i].name)); } } result.addAll(NaNs); return result.toArray(new SingleBTS[content.length]); } private static double[][] doBayes(ratioElem[] MRRatio, ratioElem[][][] ratiomap) { double[][] score = new double[ratiomap.length][ratiomap[0].length]; double totalProb = 0; for (int x = 0; x < ratiomap.length; x++) { for (int y = 0; y < ratiomap[0].length; y++) { // if (x == 48 && y == 14) { // System.out.println("halt!"); // } totalProb += getProbOfSingleHit(ratiomap[x][y], MRRatio); } } double numberTiles = (ratiomap.length * ratiomap[0].length); totalProb = totalProb / numberTiles; // now we have P(S):totalProb for (int x = 0; x < ratiomap.length; x++) { for (int y = 0; y < ratiomap[0].length; y++) { score[x][y] = (getProbOfSingleHit(MRRatio, ratiomap[x][y]) * (1 / numberTiles)) / totalProb; } } return score; } private static double getProbOfSingleHit(ratioElem[] MapRatio, ratioElem[] MRRatio) { double probability = 1; // for now: MR is without variance! and only Downlink! for (int i = 0; i < MapRatio.length; i++) { probability *= MapRatio[i].probability(MRRatio[i]); } if (probability > 0) { // System.out.println("Probability größer 0! gut! Debug"); } if (Double.isNaN(probability)) { System.out.println("Probability = NaN"); } return probability; } /** * Sort content before use! Takes a list of measurements (MR) and checks if * it contains all the elements given in content. If not, this element gets * added with NaN value. MR itself is not altered. Elements are ordered * accordingly to content. If content was ordered to e.g. arfcn, so the * result. At the end, all Ratios with NaN get pushed * * @param mR * @param content * @return */ private static ArrayList substituteMR(List mR, SingleBTS[] content) { // TODO Auto-generated method stub ArrayList result = new ArrayList(content.length); // ArrayList NaNs = new ArrayList(content.length); SingleBTS element; for (int i = 0; i < content.length; i++) { if ((element = helper.ListBTS.getARFCN(mR, content[i])) != null) { // result.add(element); } else { // BTS not there. Put in Double.NaN instead! element = new SingleBTS(content[i].ARFCN, Double.NaN, Double.NaN, true, new Date(), content[i].name); // element = new SingleBTS(content[i].ARFCN, -999, -999, true, // new Date(), content[i].name); // NaNs.add(element); } // Collections.sort(NaNs, new BTSArfcnComparator()); result.add(element); // result.addAll(NaNs); } // now, sort NaN return result; } /** * Returns all Ratios out of MapElement that can be build using the * measurements from MR. Non existing elements are substituted with NaN. * * @param MR * that is to be located * @return */ private static ratioElem[][][] getRatio(GSMMap map, SingleBTS[] sortVector) { // sort the map content. This makes sure that RSSVector is sorted // accordingly SingleBTS[] content = sortVector; // Arrays.sort(content, new BTSArfcnComparator()); // create ratioMap ratioElem[][][] ratiomap = new ratioElem[map.Xcoords.length][map.Ycoords.length][content.length - 1]; // built ratio for every cell in map for (int x = 0; x < map.Xcoords.length; x++) { for (int y = 0; y < map.Ycoords.length; y++) { // substitute map at position [x][y] to get full Vector // ArrayList RSSVector = new ArrayList( // map.map[x][y]); ArrayList RSSVector = substituteMR(map.map[x][y], sortVector); // debug: only if RSSVector has some stuff inside // if (!RSSVector.isEmpty() && RSSVector.get(0).getDldB() < 0) { // System.out.println("etwas da!"); // } // get full vector // RSSVector = substituteMR(RSSVector, content); // sort the vector. Not needed. already sorted // Collections.sort(RSSVector, new BTSArfcnComparator()); // built ratios for (int i = 0; i < content.length - 1; i++) { ratiomap[x][y][i] = new ratioElem(RSSVector.get(i), RSSVector.get(i + 1)); } } } // TODO Auto-generated method stub return ratiomap; } /** * Returns the probability that this measurement is received within map * * @param map * @return */ private static double getProbOfMR(GSMMap map) { // TODO Auto-generated method stub return 0; } /** * Calculates the possibility that MR was received on this tile's * RSS-Vector. * * @param rssVector * @param MR * @param PRssV * Probability that MR is received * @return */ private static double getPossibility(ArrayList rssVector, List MR, double PRssV) { // get all ratios out of MR. Compare with rssVector // TODO Auto-generated method stub return 0; } } /* * class ratioBTS { SingleBTS own; SingleBTS second; * * public ratioBTS(SingleBTS ownBTS, SingleBTS second) { this.own = ownBTS; * this.second = second; } * * public double getRatioDL() { return own.getDldB() - second.getDldB(); } * * public double getRatioUL() { if (own.fullBTS && second.fullBTS) { return * own.getUldB() - second.getUldB(); } return Double.NaN; } } */ /** * Comperator that computes the ARFCN of this bts * * @author richy * */ class BTSArfcnComparator implements Comparator { public int compare(SingleBTS bts1, SingleBTS bts2) { if (((SingleBTS) bts1).ARFCN > ((SingleBTS) bts2).ARFCN) { return 1; } else if (((SingleBTS) bts1).ARFCN < ((SingleBTS) bts2).ARFCN) { return -1; } else return 0; } } /** * Everything in dBm! * * @author richy * */ class ratioElem2 { SingleBTS top; SingleBTS bottom; double ratioDL; double ratioUL; double varDL; double varUL; public ratioElem2(SingleBTS top, SingleBTS bottom) { this.top = top; this.bottom = bottom; // double topUL = top.getDldB(); // double bottomUL = bottom.getDldB(); ratioDL = top.getDldB() - bottom.getDldB(); ratioUL = top.getUldB() - bottom.getUldB(); // varDL = Math.sqrt(Math.pow(top.getVarianceDLdB(), 2)); // - Math.pow(bottom.getVarianceDLdB(), 2)); // varUL = Math.sqrt(Math.pow(top.getVarianceULdB(), 2) // - Math.pow(bottom.getVarianceULdB(), 2)); varDL = top.getVarianceDLdB() + bottom.getVarianceDLdB(); varUL = top.getVarianceULdB() + bottom.getVarianceULdB(); // if (varDL != 0 && varDL != Double.NaN) { // System.out.println("var ungleich 0"); // } } public String toString() { return "RatioDL: " + ratioDL + ", varDl: " + varDL; } public double probability(ratioElem vector) { if (top.ARFCN != vector.top.ARFCN || bottom.ARFCN != vector.bottom.ARFCN) { System.out.println("Sortierung falsch!"); } if (Double.isNaN(vector.ratioDL) || Double.isNaN(this.ratioDL)) { if (Double.isNaN(vector.ratioDL) && Double.isNaN(this.ratioDL)) { // ratio between both bts cannot been built. This means top or // bottom bts is not received. let's say a cell phone has a poor // antenna, than this would not neccesarily mean that the // probability of beeing there is one. It can although be used // to // boost the probability return 1; } else return 0; } if (vector.varDL == 0 && this.varDL == 0) { if (Math.abs(vector.ratioDL - this.ratioDL) <= 1) { return 1; } else { return 0; } } /* * if (this.ratioDL == Double.NaN && vector.ratioDL == Double.NaN) { * return 1; } else if (this.ratioDL != Double.NaN && vector.ratioDL == * Double.NaN) { return Double.MIN_VALUE; } else if (this.ratioDL == * Double.NaN && vector.ratioDL != Double.NaN) { return * Double.MIN_VALUE; } else if (this.ratioDL == 0 && vector.ratioDL == * 0) { return 1; } else if (this.ratioDL == 0 && vector.ratioDL == * Double.NaN) { return 1; } else if (this.ratioDL == Double.NaN && * vector.ratioDL == 0) { return 1; } * * else */if (vector.varDL == 0 && this.varDL != 0) { // compute just value at given point. No integration! double std = Math.sqrt(varDL); double x = vector.ratioDL; double u = this.ratioDL; double sqrtPI = Math.sqrt(2 * Math.PI); double exp = Math.exp(-0.5 * Math.pow((x - u) / std, 2)); double result = (1 / (std * sqrtPI)) * exp; if (Double.isNaN(result)) return 0; return result; } else if (this.varDL == 0 && vector.varDL != 0) { // compute just value at given point. No integration! double std = Math.sqrt(vector.varDL); double x = ratioDL; double u = vector.ratioDL; double sqrtPI = Math.sqrt(2 * Math.PI); double exp = Math.exp(-0.5 * Math.pow((x - u) / std, 2)); double result = (1 / (std * sqrtPI)) * exp; if (Double.isNaN(result)) return 0; return result; } else { // integration! // System.out.println("Integration now implemented!"); return new NormDistribution(ratioDL, varDL) .intersection(new NormDistribution(vector.ratioDL, vector.varDL)); } } }