node.cc

题描述的是一个旅行商要到几个城市去

/* $Id: node.cc,v 1.5 2006-08-21 15:02:00 jonathan Exp $
 * Jonathan Ledlie, Harvard University.
 * Copyright 2005.  All rights reserved.
 */

#include "sim.h"
#include "node.h"

int nodeCount = 0;
Node *node = NULL;

float **rtts = NULL;

int **neighbors = NULL;
int neighborCount = 0;

int withinMeasurementError = 0;
int maxNeighborCount = 0;
double measurement_error = 0.;

bool FULL_LATENCY_MATRIX = false;
int SAMPLE_EXPIRATION = 0;
double ERROR_FRACTION = 0.25;
double DAMPENING_FRACTION = 0.25;
bool USE_CONFIDENCE = false;
double INITIAL_WEIGHTED_ERROR = 1.;
int APP_VECTOR_HISTORY_TIME = 0;


char Node::appCoordUpdateMethod = ' ';
uint Node::windowSize = 0;
double Node::appCoordUpdateThreshold = 0;
int ctorCount = 0;

bool Node::updateAppVector (double systemDistanceDelta, int stamp,
			    double &appComparison) {
  // we enter here having updated our system-level coordinate
  // with the most recent observation

  bool updatedAppVector = false;
  Point *newStartCoord, *newCurrentCoord, *startCentroid, *currentCentroid;

  switch (appCoordUpdateMethod) {
  case ' ':
  case 's':
    if (systemDistanceDelta > appCoordUpdateThreshold) {
      appVector->assign (vec);    
      updatedAppVector = true;
    }
    break;
  case 'a':
    if (appVector->getEuclideanDistance (vec) > appCoordUpdateThreshold) {
      appVector->assign (vec);
      updatedAppVector = true;
    }
    break;
  case 'l':
  case 'e':
  case 'c':

    // add to windows
    // build both windows at once
    // this way they initially overlap and
    // we always have some state to do a comparison

    if (startCoords.size() < windowSize) {
      newStartCoord = new Point (vec);
      startCoords.push_back (newStartCoord);
    }

    if (currentCoords.size() >= windowSize) {
      Point *p = currentCoords[0];
      currentCoords.pop_front ();
      delete p;
    }
    newCurrentCoord = new Point (vec);
    currentCoords.push_back (newCurrentCoord);

    // compute centroids
    startCentroid = new Point();

    for (uint i = 0; i < startCoords.size(); i++) {
      startCentroid->add (startCoords[i]);
    }
    startCentroid->scale (1./startCoords.size());

    currentCentroid = new Point();

    for (uint i = 0; i < currentCoords.size(); i++) {
      currentCentroid->add (currentCoords[i]);
    }
    currentCentroid->scale (1./currentCoords.size());

    // if sufficient history, do comparison
    if (currentCoords.size() >= windowSize) {

      
      if (appCoordUpdateMethod == 'l') {
	appComparison = findLocalRelativeDistance
	  (startCentroid, currentCentroid);
      } else if (appCoordUpdateMethod == 'e') {
	appComparison = findEnergyDistance ();
      } else if (appCoordUpdateMethod == 'c') {
	appComparison = appVector->getEuclideanDistance (vec);
      }

      if (appComparison > appCoordUpdateThreshold) {
	appVector->assign (currentCentroid);
	clearCoords ();
	updatedAppVector = true;
      }
    }
    delete startCentroid;
    delete currentCentroid;
    break;

  default:
    printf ("Invalid appCoordUpdateMethod\n");
    exit (-1);
  }


  if (debug) {
    if (updatedAppVector) {
      cout << "Updated app vector = " << appVector << endl;
    } else {
      cout << "Did not update app vector" << appVector << endl;
    }
  }

  /*
  if (updatedAppVector) {
    cout << stamp << " Updated app vector = " << *appVector << endl;
    exit (0);
  }
  */

  return updatedAppVector;
}

void Node::addToNearestNeighbor (Point *neighbor, int timestamp) {
  // hmm, note that we are getting this guys updates for free
  // i.e. we are using a point, not our knowledge of the distance
  // TODO
  if (nearestNeighbor->stamp == 0 ||
      vec->getEuclideanDistance (neighbor) <
      vec->getEuclideanDistance (nearestNeighbor)) {
    if (debug) {
      cout << "Updating nearest neighbor " << neighbor << endl;
    }
    nearestNeighbor->assign (neighbor);
    nearestNeighbor->stamp = timestamp;
  }
}

double Node::findLocalRelativeDistance (Point *startCentroid,
					Point *currentCentroid) {  
  double nnStart = nearestNeighbor->getEuclideanDistance (startCentroid);
  double nnCurrent = nearestNeighbor->getEuclideanDistance (currentCentroid);
  double diff = fabs (nnStart - nnCurrent) / nnStart;
  if (debug) {
    cout << "in findLocalRelativeDistance" << endl;
    cout << "startCentroid = " << startCentroid << endl;
    cout << "currentCentroid = " << currentCentroid << endl;
    cout << "local relative distance = " << diff << endl;
  }
  return diff;
}

double Node::findEnergyDistance () {
  double sum = 0., abSum = 0., aSum = 0., bSum = 0.;

  if (debug) {
    cout << "startCoords size " << startCoords.size() 
	 << " currentCoords size " << currentCoords.size() << endl;

    cout << "startCoords: " << endl;
    for (uint i = 0; i < startCoords.size(); i++) {
      cout << i << ": " << startCoords[i] << endl;
    }

    cout << "currentCoords: " << endl;
    for (uint i = 0; i < currentCoords.size(); i++) {
      cout << i << ": " << currentCoords[i] << endl;
    }
  }

  for (uint i = 0; i < startCoords.size(); i++) {
    for (uint j = 0; j < currentCoords.size(); j++) {
      abSum += startCoords[i]->getEuclideanDistance (currentCoords[j]);
    }
  }
  abSum *= 2./(startCoords.size()*currentCoords.size());
  if (debug)
    cout << "abSum = " << abSum << endl;


  for (uint i = 0; i < startCoords.size(); i++) {
    for (uint j = 0; j < startCoords.size(); j++) {
      aSum += startCoords[i]->getEuclideanDistance (startCoords[j]);
    }
  }
  aSum *= 1./(startCoords.size()*startCoords.size());
  if (debug)
    cout << "aSum = " << aSum << endl;

  for (uint i = 0; i < currentCoords.size(); i++) {
    for (uint j = 0; j < currentCoords.size(); j++) {
      bSum += currentCoords[i]->getEuclideanDistance (currentCoords[j]);
    }
  }
  bSum *= 1./(currentCoords.size()*currentCoords.size());
  if (debug)
    cout << "bSum = " << bSum << endl;

  sum = abSum - aSum - bSum;

  sum *= (startCoords.size()*currentCoords.size()) /
    (startCoords.size()+currentCoords.size());

  if (debug)
    cout << "psum = " << sum << endl;

  return sum;
}

void Node::addSample (int yourId, double sample, 
			Point *yourCoord, double yourWeightedError,
			Point *yourAppCoord,
			int stamp) {
  sampleCount++;
  map<int,Samples*>::iterator samplesIter = node2samples.find(yourId);
  Samples *samples = NULL;
  if (samplesIter == node2samples.end()) {
    Samples *samples = new Samples();
    node2samples.insert(pair<int,Samples*>(yourId,samples));
    samplesIter = node2samples.find(yourId);
  }
  samples = samplesIter->second;
  samples->addSample
    (sample, id, yourId, yourCoord, yourWeightedError,
     yourAppCoord, stamp);
}

double Node::getSample (int yourId) {
  map<int,Samples*>::iterator samplesIter = node2samples.find(yourId);
  Samples *samples = NULL;
  if (samplesIter == node2samples.end()) {
    return -1;
  }
  samples = samplesIter->second;
  return samples->getSample();
}



bool Node::isInInitialState () {
  if (weightedError == INITIAL_WEIGHTED_ERROR &&
      vec->isInInitialState ())
    return true;
  return false;
}

bool Node::hasConfidence () {
  if (weightedError < .99)
    return true;
  return false;
}


Node::Node () {
  vec = new Point();
  appVector = new Point();
  nearestNeighbor = new Point();
  weightedError = INITIAL_WEIGHTED_ERROR;
  lastUpdateTo = 0;
  lastUpdateFrom = 0;
  sampleCount = 0;
  distanceDelta = 0;

  fixedNearestNeighborId = -1;
  fixedNearestNeighborDistance = 0;
  id = ctorCount++;
}

void Node::clearCoords () {

  for (uint i = 0; i < startCoords.size(); i++) {
    Point *p = startCoords[i];
    delete p;
  }
  for (uint i = 0; i < currentCoords.size(); i++) {
    Point *p = currentCoords[i];
    delete p;
  }

  startCoords.clear ();
  currentCoords.clear ();

}

Node::~Node () {
  for (map<int,Samples*>::iterator samplesIter = node2samples.begin();
       samplesIter != node2samples.end(); samplesIter++) {
    Samples *samples = samplesIter->second;
    delete samples;
  }

  clearCoords ();

  delete vec;
  delete appVector;
  delete nearestNeighbor;
}

void Node::printCoord (FILE *fp) {
  for (int i = 0; i < DIMENSIONS; i++) {
    fprintf (fp, "%.1f ", vec->v[i]);
  }
  if (USE_HEIGHT) {
    fprintf (fp, "h %.1f ", vec->height);
  }
}

void Node::printAppCoord (FILE *fp) {
  if (appVector != NULL) {
    for (int i = 0; i < DIMENSIONS; i++) {
      fprintf (fp, "%.1f ", appVector->v[i]);
    }
  }
  if (USE_HEIGHT) {
    fprintf (fp, "h %.1f ", appVector->height);
  }
}

void Node::addDistanceDelta (double dd) {
  // EWMA on recent movement
  distanceDelta = (.05 * dd) + (.95 * distanceDelta);
}

void Node::printStat (FILE *fp) {
  fprintf (fp, "conf %f sC %d dd %f lastTo %d lastFrom %d", weightedError, sampleCount, distanceDelta, lastUpdateTo, lastUpdateFrom);
}

ostream& operator << (ostream& os, Node& n) 
{
  for (int i = 0; i < DIMENSIONS; i++) {
    os << n.vec->v[i] << " ";
  }
  os << "conf " << n.weightedError;
  os << "sC " << n.sampleCount;
  return os;
}

void Node::setFixedSampleArray (int nodeCount) {
  fixedSample.reserve (nodeCount);
  for (int i = 0; i < nodeCount; i++) {
    fixedSample.push_back (0);
  }
}

void Node::setFixedSample (int yourId, double sample) {
  if (fixedNearestNeighborId < 0 ||
      sample < fixedNearestNeighborDistance) {
    fixedNearestNeighborDistance = sample;
    fixedNearestNeighborId = yourId;
  }

  fixedSample[yourId] = sample;
}

double Node::getFixedSample (int yourId) {
  return fixedSample[yourId];
}

double Node::getFixedSamplePercentile (double p) {
  return percentile (fixedSample, p);
}

void Node::printVector () {
  //  appVector->print();
  vec->print(stdout);
}