geo-routing.cc

定向扩散路由协议

PktHeader * GeoRoutingFilter::preProcessMessage(Message *msg)
{
  float longitude_min, longitude_max;
  float latitude_min, latitude_max;
  PktHeader *pkt_header = NULL;

  pkt_header = stripOutHeader(msg);

  if (!pkt_header){
    // This is a message either coming from a local application (for
    // which a geo_header hasn't been extracted yet) or a message with
    // no geographic information (in which case there's nothing we can
    // do about). We first try to extract geographic information from
    // the message in order to create a new geo_header
    if (extractLocation(msg, &longitude_min, &longitude_max,
			&latitude_min, &latitude_max)){

      // Create new Packet Header
      pkt_header = new PktHeader;

      // Fill in the new packet header
      pkt_header->pkt_num_ = msg->pkt_num_;
      pkt_header->rdm_id_ = msg->rdm_id_;
      pkt_header->prev_hop_ = msg->last_hop_;
      pkt_header->pkt_type_ = UNICAST_ORIGINAL;
      pkt_header->path_len_ = 0;

      pkt_header->dst_region_.center_.longitude_ = (longitude_min +
						    longitude_max) / 2;
      pkt_header->dst_region_.center_.latitude_ = (latitude_min +
						   latitude_max) / 2;

      DiffPrint(DEBUG_IMPORTANT, "GEO: ExtractLocation %f,%f, %f,%f (%f,%f)\n",
		longitude_min, longitude_max, latitude_min, latitude_max,
		pkt_header->dst_region_.center_.longitude_,
		pkt_header->dst_region_.center_.latitude_);

      pkt_header->dst_region_.radius_ = Distance(longitude_min, latitude_min,
						 longitude_max,
						 latitude_max) / 2;
    }
  }

  return pkt_header;
}

PktHeader * GeoRoutingFilter::stripOutHeader(Message *msg)
{
  NRSimpleAttribute<void *> *geo_header_attribute;
  GeoHeader *geo_header;
  PktHeader *pkt_header = NULL;

  geo_header_attribute = GeoHeaderAttr.find(msg->msg_attr_vec_);

  if (geo_header_attribute){
    geo_header = (GeoHeader *)(geo_header_attribute->getVal());

    // Create Packet Header structure
    pkt_header = new PktHeader;

    pkt_header->pkt_num_ = msg->pkt_num_;
    pkt_header->rdm_id_ = msg->rdm_id_;
    pkt_header->prev_hop_ = msg->last_hop_;

    // Copy the msg from Geo_header to PktHeader
    pkt_header->pkt_type_ = geo_header->pkt_type_;
    pkt_header->dst_region_.center_.longitude_ = geo_header->dst_region_.center_.longitude_;
    pkt_header->dst_region_.center_.latitude_ = geo_header->dst_region_.center_.latitude_;
    pkt_header->dst_region_.radius_ = geo_header->dst_region_.radius_;
    pkt_header->path_len_ = geo_header->path_len_;

    takeOutAttr(msg->msg_attr_vec_, GEO_HEADER_KEY);
    delete geo_header_attribute;
  }
  else{
    DiffPrint(DEBUG_IMPORTANT, "GEO: GeoHeader Attribute not present !\n");
  }
  return pkt_header;
}

void GeoRoutingFilter::takeOutAttr(NRAttrVec *attrs, int32_t key)
{
  NRAttrVec::iterator attr_itr;

  for (attr_itr = attrs->begin(); attr_itr != attrs->end(); ++attr_itr){
    if ((*attr_itr)->getKey() == key){
      break;
    }
  }

  if (attr_itr != attrs->end())
    attrs->erase(attr_itr);
}

bool GeoRoutingFilter::extractLocation(Message *msg,
				       float *longitude_min,
				       float *longitude_max,
				       float *latitude_min,
				       float *latitude_max)
{
  NRSimpleAttribute<float> *lat_attr;
  NRSimpleAttribute<float> *long_attr;
  NRAttrVec::iterator itr;
  NRAttrVec *attrs;
  bool has_long_min = false;
  bool has_long_max = false;
  bool has_lat_min = false;
  bool has_lat_max = false;

  attrs = msg->msg_attr_vec_;

  // Extracts longitude coordinates of the target region from the
  // message
  itr = attrs->begin();

  for (;;){

    long_attr = LongitudeAttr.find_from(attrs, itr, &itr);

    if (!long_attr)
      break;

    if ((long_attr->getOp() == NRAttribute::GT) ||
	(long_attr->getOp() == NRAttribute::GE)){
      has_long_min = true;
      *longitude_min = long_attr->getVal();
    }

    if ((long_attr->getOp() == NRAttribute::LT) ||
	(long_attr->getOp() == NRAttribute::LE)){
      has_long_max = true;
      *longitude_max = long_attr->getVal();
    }

    // Increment itr to avoid an infinite loop
    itr++;
  }

  // Now we extract latitude coordinates of the target region from the
  // message
  itr = attrs->begin();

  for (;;){

    lat_attr = LatitudeAttr.find_from(attrs, itr, &itr);

    if (!lat_attr)
      break;

    if ((lat_attr->getOp() == NRAttribute::GT) ||
	(lat_attr->getOp() == NRAttribute::GE)){
      has_lat_min = true;
      *latitude_min = lat_attr->getVal();
    }

    if ((lat_attr->getOp() == NRAttribute::LT) ||
	(lat_attr->getOp() == NRAttribute::LE)){
      has_lat_max = true;
      *latitude_max = lat_attr->getVal();
    }

    // Increment itr to avoid an infinite loop
    itr++;
  }

  if (has_long_min && has_long_max && has_lat_min && has_lat_min)
    return true;

  return false;
}

GeoHeader * GeoRoutingFilter::restoreGeoHeader(PktHeader *pkt_header, Message *msg)
{
  GeoHeader *geo_header;

  geo_header = new GeoHeader;

  msg->last_hop_ = pkt_header->prev_hop_;

  geo_header->pkt_type_ = pkt_header->pkt_type_;
  geo_header->dst_region_.center_.longitude_ = pkt_header->dst_region_.center_.longitude_;
  geo_header->dst_region_.center_.latitude_ = pkt_header->dst_region_.center_.latitude_;
  geo_header->dst_region_.radius_ = pkt_header->dst_region_.radius_;
  geo_header->path_len_ = pkt_header->path_len_;

  return geo_header;
}

int32_t GeoRoutingFilter::findNextHop(GeoHeader *geo_header, bool greedy)
{
  NeighborList::iterator neighbor_itr;
  NeighborEntry *neighbor_entry;
  GeoLocation destination, min_neighbor_location;
  double current_learned_cost, min_learned_cost;
  double current_distance, min_distance;
  double distance, gap;
  int32_t min_cost_id, neighbor_id;
  int num_neighbors;
  double new_heuristic_value;

  // Load the destination coordinate from the packet
  destination = geo_header->dst_region_.center_;

  current_distance = Distance(geo_longitude_, geo_latitude_,
			      destination.longitude_, destination.latitude_);

  min_distance = MAX_INT;
  min_learned_cost = MAX_INT;
  num_neighbors = 0;

  // Now we go through out list of neighbor and compute the cost to
  // each one
  for (neighbor_itr = neighbors_list_.begin();
       neighbor_itr != neighbors_list_.end(); ++neighbor_itr){
    neighbor_entry = *neighbor_itr;
    num_neighbors++;

    neighbor_id = neighbor_entry->id_;
    current_learned_cost = retrieveLearnedCost(neighbor_id, destination);

    // Calculate distance from this neighbor to dst
    distance = Distance(neighbor_entry->longitude_, neighbor_entry->latitude_,
			destination.longitude_, destination.latitude_);

    // If we are in 'greedy mode', we do not want to move away, so we
    // skip neighbors that are farther away than us from the region
    if (greedy && (distance > current_distance))
      continue;

    DiffPrint(DEBUG_IMPORTANT, "GEO: Neighbor: %d: cost = %f, min_cost = %f\n",
	      neighbor_id, current_learned_cost, min_learned_cost);

    // Found a neighbor with a lower cost
    if (current_learned_cost < min_learned_cost){
      min_learned_cost = current_learned_cost;
      min_cost_id = neighbor_entry->id_;
      min_neighbor_location.longitude_ = neighbor_entry->longitude_;
      min_neighbor_location.latitude_ = neighbor_entry->latitude_;
    }
  }

  DiffPrint(DEBUG_IMPORTANT, "GEO: # neighbors: %d; cur: %f,%f, dst: %f,%f\n",
	    num_neighbors, geo_longitude_, geo_latitude_,
	    destination.longitude_, destination.latitude_);

  // Check if we have neighbors we can use to forward this message
  if (min_learned_cost < MAX_INT){

    // Calculate the cost from me to my next hop neighbor
    gap = Distance(min_neighbor_location.longitude_,
		   min_neighbor_location.latitude_,
		   geo_longitude_, geo_latitude_);

    // Update my heuristic_value
    new_heuristic_value = min_learned_cost + gap;

    // Broadcast the new heuristic value if it's changed significantly
    if (h_value_table_.updateEntry(destination, new_heuristic_value))
      broadcastHeuristicValue(destination, new_heuristic_value);

    // Return neighbor this message should go
    return min_cost_id;
  }

  // We have no neighbors to whom we can forward this message !
  return BROADCAST_ADDR;
}

void GeoRoutingFilter::broadcastHeuristicValue(GeoLocation dst,
					       double new_heuristic_value)
{
  NRAttrVec attrs;
  HeuristicValue *heuristic_value;
  Message *beacon_msg;
  TimerType *timer;

  attrs.push_back(GeoLongitudeAttr.make(NRAttribute::IS, geo_longitude_));
  attrs.push_back(GeoLatitudeAttr.make(NRAttribute::IS, geo_latitude_));
  attrs.push_back(GeoRemainingEnergyAttr.make(NRAttribute::IS,
					      remainingEnergy()));
  attrs.push_back(GeoBeaconTypeAttr.make(NRAttribute::IS, GEO_UPDATE));

  heuristic_value = new HeuristicValue(dst.longitude_,
				       dst.latitude_, new_heuristic_value);

  attrs.push_back(GeoHeuristicValueAttr.make(NRAttribute::IS,
					     (void *) heuristic_value,
					     sizeof(HeuristicValue)));

  beacon_msg = new Message(DIFFUSION_VERSION, DATA, 0, 0,
			   attrs.size(), pkt_count_, rdm_id_,
			   BROADCAST_ADDR, LOCALHOST_ADDR);

  // Don't forget to increase pkt_count
  pkt_count_++;

  beacon_msg->msg_attr_vec_ = CopyAttrs(&attrs);

  // Now, we generate a beacon to broadcast triggered h-value update
  // but first we add some random jitter before actually sending it
  timer = new TimerType(MESSAGE_SEND_TIMER);
  timer->param_ = (void *) CopyMessage(beacon_msg);

  ((DiffusionRouting *)dr_)->addTimer(GEO_BEACON_DELAY +
				      (int) ((GEO_BEACON_JITTER *
					      (GetRand() * 1.0 / RAND_MAX) -
					      (GEO_BEACON_JITTER / 2))),
				      (void *) timer, timer_callback_);

  // Delete everything we created here
  ClearAttrs(&attrs);
  delete beacon_msg;
  delete heuristic_value;
}

int GeoRoutingFilter::floodInsideRegion(GeoHeader *geo_header)
{
  NeighborList::iterator neighbor_itr;
  NeighborEntry *neighbor_entry;
  GeoLocation destination;
  double radius, distance;

  // Load destination coordinates
  destination = geo_header->dst_region_.center_;
  radius = geo_header->dst_region_.radius_;

  if (Distance(geo_longitude_, geo_latitude_,
	       destination.longitude_, destination.latitude_) < radius){

    // We are inside the target region, change mode to BROADCAST
    geo_header->pkt_type_ = BROADCAST_TYPE;

    // If all my neighbors are outside this region, suppress this
    // broadcast message
    for (neighbor_itr = neighbors_list_.begin();
	 neighbor_itr != neighbors_list_.end(); ++neighbor_itr){
      neighbor_entry = *neighbor_itr;

      // Calculate distance between neighbor and dst
      distance = Distance(neighbor_entry->longitude_,
			  neighbor_entry->latitude_,
			  destination.longitude_, destination.latitude_);

      // As long as we have one neighbor inside the region, broadcast
      // the message
      if (distance < radius)
	return BROADCAST;
    }
    return BROADCAST_SUPPRESS;
  }
  else{
    if (geo_header->pkt_type_ == BROADCAST_TYPE){
      // This is a BROADCAST packet flooded outside the region
      return BROADCAST_SUPPRESS;
    }
    else{
      // We are still outside the target region, continue forwading
      // the packet towards the region
      return OUTSIDE_REGION;
    }
  }
}

double GeoRoutingFilter::retrieveLearnedCost(int neighbor_id, GeoLocation dst)
{
  int index;

  index = learned_cost_table_.retrieveEntry(neighbor_id, &dst);

  if (index != FAIL)
    return learned_cost_table_.table_[index].learned_cost_value_;
  else
    return estimateCost(neighbor_id, dst);
}

double GeoRoutingFilter::estimateCost(int neighbor_id, GeoLocation dst)
{
  NeighborEntry *neighbor_entry;
  double distance;

  // To get this neighbor's location, we first find the entry with neighbor_id
  // Since right now it is pure geographical routing, the estimated cost is
  // just the distance between neighbor_id to dst.

  if (neighbor_id < 0){
    DiffPrint(DEBUG_IMPORTANT, "GEO: Invalid neighbor ID !\n");
    return FAIL;
  }

  neighbor_entry = findNeighbor(neighbor_id);

  if (!neighbor_entry)
    return FAIL;

  distance = Distance(neighbor_entry->longitude_, neighbor_entry->latitude_,
		      dst.longitude_, dst.latitude_);

  return distance;
}

NeighborEntry * GeoRoutingFilter::findNeighbor(int32_t neighbor_id)
{
  NeighborList::iterator neighbor_itr;
  NeighborEntry *neighbor_entry;

  for (neighbor_itr = neighbors_list_.begin();
       neighbor_itr != neighbors_list_.end(); ++neighbor_itr){
    neighbor_entry = *neighbor_itr;
    if (neighbor_entry->id_ == neighbor_id)
      return neighbor_entry;
  }
  return NULL;
}

double GeoRoutingFilter::retrieveHeuristicValue(GeoLocation dst)
{
  int index;

  index = h_value_table_.retrieveEntry(&dst);

  if (index != FAIL)
    return h_value_table_.table_[index].heuristic_value_;

  return INITIAL_HEURISTIC_VALUE;
}

#ifndef NS_DIFFUSION
int main(int argc, char **argv)
{
  GeoRoutingFilter *geo_filter;

  geo_filter = new GeoRoutingFilter(argc, argv);
  geo_filter->run();

  return 0;
}
#endif // !NS_DIFFUSION