geo-routing.cc

定向扩散路由协议

	// Update learned cost value table
	dst_location.longitude_ = heuristic_value->dst_longitude_;
	dst_location.latitude_ = heuristic_value->dst_latitude_;

	DiffPrint(DEBUG_IMPORTANT, "GEO: Received h-val update %d: (%f,%f):%f\n",
		  neighbor_id, dst_location.longitude_,
		  dst_location.latitude_,
		  heuristic_value->heuristic_value_);

	learned_cost_table_.updateEntry(neighbor_id, dst_location,
					heuristic_value->heuristic_value_);
      }
    }

    break;

  default:

    // If we do not know about this message, we just pass it to the
    // next filter
    ((DiffusionRouting *)dr_)->sendMessage(msg, pre_filter_handle_);

    break;

  }
}

void GeoRoutingFilter::postProcessFilter(Message *msg)
{
  PktHeader *pkt_header = NULL;
  GeoHeader *geo_header = NULL;
  int action;
  int32_t next_hop;

  switch (msg->msg_type_){

  case INTEREST:
  case EXPLORATORY_DATA:
  case PUSH_EXPLORATORY_DATA:

    // Ignore messages with a local application as destination
    if (msg->next_hop_ != LOCALHOST_ADDR){

      // Retrieve packet header from previous stage
      pkt_header = retrievePacketHeader(msg);

      // If we have record of this packet, we restore the previous
      // geo_header information before forwarding it further
      if (pkt_header){
	geo_header = restoreGeoHeader(pkt_header, msg);

	// Increment path_len
	geo_header->path_len_++;

	// Check if we have to broadcast this message. We do not need
	// to check if I have seen this broadcast packet before, since
	// this is called by PostProcessFilter, so it must be a new
	// packet. We only need to check if we are inside the target
	// region
	action = floodInsideRegion(geo_header);

	// Add GeoHeader attribute to the message
	msg->msg_attr_vec_->push_back(GeoHeaderAttr.make(NRAttribute::IS,
							 (void *) geo_header,
							 sizeof(GeoHeader)));

	switch (action){

	case BROADCAST:

	  // We are inside the region and have at least a neighbor
	  // which is inside the region too, so we just broadcast this
	  // message
	  DiffPrint(DEBUG_IMPORTANT,
		    "GEO: BROADCAST Message: last_hop: %d!\n",
		    msg->last_hop_);
	  
	  msg->next_hop_ = BROADCAST_ADDR;
	  ((DiffusionRouting *)dr_)->sendMessage(msg, post_filter_handle_);

	  break;

	case BROADCAST_SUPPRESS:

	  // We are either inside the region and have no neighbors
	  // also inside this region OR packet came from inside the
	  // region and we are outside the region. In either case, we
	  // do not forward the packet
	  DiffPrint(DEBUG_IMPORTANT, "GEO: BROADCAST_SUPPRESS !\n");

	  break;

	case OUTSIDE_REGION:

	  // The packet is still outside the region. In order to route
	  // it to the region, we first try using a 'greedy mode'. If
	  // that doesn't work, we probably need to navigate around a
	  // hole
	  next_hop = findNextHop(geo_header, true);

	  // If there are no neighbors, let's try to go around a hole
	  if (next_hop == BROADCAST_ADDR){

	    // Check if we should still be looking for a path
	    if (geo_header->path_len_ < MAX_PATH_LEN)
	      next_hop = findNextHop(geo_header, false);
	  }

	  // Still no neighbors, nothing we can do !
	  if (next_hop == BROADCAST_ADDR){
	    DiffPrint(DEBUG_IMPORTANT, "GEO: Cannot find next hop !\n");
	  }
	  else{
	    // Forward message to next_hop
	    msg->next_hop_ = next_hop;
	    DiffPrint(DEBUG_IMPORTANT, "GEO: Next Hop: %d\n", next_hop);
	    DiffPrint(DEBUG_IMPORTANT, "GEO: Last Hop: %d\n", msg->last_hop_);
	    ((DiffusionRouting *)dr_)->sendMessage(msg, post_filter_handle_);
	  }
	
	  break;

	default:

	  break;
	}

	// Let's not forget to delete both geo_header and pkt_header
	delete pkt_header;
	delete geo_header;
      }
      else{
	// This message has no packet header information, so we just forward it
	DiffPrint(DEBUG_IMPORTANT,
		  "GEO: Forwarding message without packet header info !\n");
	((DiffusionRouting *)dr_)->sendMessage(msg, post_filter_handle_);
      }
    }
    else{
      // This is a message from gradient to a local app
      ((DiffusionRouting *)dr_)->sendMessage(msg, post_filter_handle_);
    }

    break;

  default:

    // All other messages are just forwarded without any changes
    ((DiffusionRouting *)dr_)->sendMessage(msg, post_filter_handle_);

    break;
  }
}

handle GeoRoutingFilter::setupPreFilter()
{
  NRAttrVec attrs;
  handle h;

  // Set up a filter that matches every packet coming in
  attrs.push_back(NRClassAttr.make(NRAttribute::IS,
				   NRAttribute::INTEREST_CLASS));

  h = ((DiffusionRouting *)dr_)->addFilter(&attrs,
					   GEOROUTING_PRE_FILTER_PRIORITY,
					   filter_callback_);
  ClearAttrs(&attrs);
  return h;
}

handle GeoRoutingFilter::setupPostFilter()
{
  NRAttrVec attrs;
  handle h;

  // This is a filter that matches all packets after processing by the
  // gradient filter
  attrs.push_back(NRClassAttr.make(NRAttribute::IS,
				   NRAttribute::INTEREST_CLASS));

  h = ((DiffusionRouting *)dr_)->addFilter(&attrs,
					   GEOROUTING_POST_FILTER_PRIORITY,
					   filter_callback_);

  ClearAttrs(&attrs);
  return h;
}

void GeoRoutingFilter::run()
{
#ifdef NS_DIFFUSION
  TimerType *timer;

  // Set up filters
  pre_filter_handle_ = setupPreFilter();
  post_filter_handle_ = setupPostFilter();

  // Add periodic neighbor checking timer
  timer = new TimerType(NEIGHBOR_TIMER);
  ((DiffusionRouting *)dr_)->addTimer(GEO_NEIGHBOR_DELAY,
				      (void *) timer,
				      timer_callback_);

  // Add periodic beacon request timer
  timer = new TimerType(BEACON_REQUEST_TIMER);
  ((DiffusionRouting *)dr_)->addTimer(GEO_BEACON_REQUEST_CHECK_PERIOD,
				      (void *) timer,
				      timer_callback_);

  DiffPrint(DEBUG_ALWAYS, "GEAR Received handle %d for pre Filter !\n",
	    pre_filter_handle_);
  DiffPrint(DEBUG_ALWAYS, "GEAR Received handle %d for post Filter !\n",
	    post_filter_handle_);
  DiffPrint(DEBUG_ALWAYS, "GEAR Initialized !\n");
#endif // NS_DIFFUSION

  // Sends a beacon request upon start-up
  beaconTimeout();

#ifndef NS_DIFFUSION
  // We don't do anything
  while (1){
    sleep(1000);
  }
#endif // !NS_DIFFUSION
}

#ifdef NS_DIFFUSION
GeoRoutingFilter::GeoRoutingFilter(const char *mnode)
{
  struct timeval tv;

  node_ = (MobileNode *) TclObject::lookup(mnode);
#else
GeoRoutingFilter::GeoRoutingFilter(int argc, char **argv)
{
  TimerType *timer;
  struct timeval tv;

  // Parse command line options
  parseCommandLine(argc, argv);
#endif // NS_DIFFUSION

  // Initialize a few parameters
  initial_energy_ = GEO_INITIAL_ENERGY;
  unit_energy_for_send_ = GEO_UNIT_ENERGY_FOR_SEND;
  unit_energy_for_recv_ = GEO_UNIT_ENERGY_FOR_RECV;
  num_pkt_sent_ = 0;
  num_pkt_recv_ = 0;

  // Initialize beacon timestamp
  last_beacon_reply_tv_.tv_sec = 0; 
  last_beacon_reply_tv_.tv_usec = 0; 
  last_neighbor_request_tv_.tv_sec = 0;
  last_neighbor_request_tv_.tv_usec = 0;

  getNodeLocation(&geo_longitude_, &geo_latitude_);

  DiffPrint(DEBUG_ALWAYS, "GEAR: Location %f,%f\n",
	    geo_longitude_, geo_latitude_);

  GetTime(&tv);
  SetSeed(&tv);
  pkt_count_ = GetRand();
  rdm_id_ = GetRand();

#ifndef NS_DIFFUSION
  // Create Diffusion Routing class
  dr_ = NR::createNR(diffusion_port_);
#endif // !NS_DIFFUSION

  filter_callback_ = new GeoFilterReceive(this);
  timer_callback_ = new GeoTimerReceive(this);

#ifndef NS_DIFFUSION
  // Set up filters
  pre_filter_handle_ = setupPreFilter();
  post_filter_handle_ = setupPostFilter();

  // Add periodic neighbor checking timer
  timer = new TimerType(NEIGHBOR_TIMER);
  ((DiffusionRouting *)dr_)->addTimer(GEO_NEIGHBOR_DELAY,
				      (void *) timer,
				      timer_callback_);

  // Add periodic beacon request timer
  timer = new TimerType(BEACON_REQUEST_TIMER);
  ((DiffusionRouting *)dr_)->addTimer(GEO_BEACON_REQUEST_CHECK_PERIOD,
				      (void *) timer,
				      timer_callback_);

  DiffPrint(DEBUG_ALWAYS, "GEAR Received handle %d for pre Filter !\n",
	    pre_filter_handle_);
  DiffPrint(DEBUG_ALWAYS, "GEAR Received handle %d for post Filter !\n",
	    post_filter_handle_);
  DiffPrint(DEBUG_ALWAYS, "GEAR Initialized !\n");
#endif // !NS_DIFFUSION
}

void GeoRoutingFilter::getNodeLocation(double *longitude, double *latitude)
{
#ifdef NS_DIFFUSION
  double z;

  node_->getLoc(longitude, latitude, &z);
#else
  char *longitude_env, *latitude_env;

  longitude_env = getenv("gear_longitude");
  latitude_env = getenv("gear_latitude");

  if (longitude_env && latitude_env){
    *longitude = atof(longitude_env);
    *latitude = atof(latitude_env);
  }
  else{
    DiffPrint(DEBUG_ALWAYS, "Error: Cannot get location (gear_longitude, gear_latitude) !\n");
    exit(-1);
  }
#endif // NS_DIFFUSION
}

bool GeoRoutingFilter::checkNeighbors()
{
  NeighborList::iterator neighbor_itr;
  NeighborEntry *neighbor_entry;
  struct timeval tv;

  GetTime(&tv);

  for (neighbor_itr = neighbors_list_.begin();
       neighbor_itr != neighbors_list_.end(); ++neighbor_itr){
    neighbor_entry = *neighbor_itr;

    if ((tv.tv_sec - neighbor_entry->tv_.tv_sec) >= GEO_NEIGHBOR_UPDATE)
      return true;
  }
  
  return false;
}

void GeoRoutingFilter::sendNeighborRequest()
{
  NRAttrVec attrs;
  Message *beacon_msg;
  TimerType *timer;

  // Check if we need to send a beacon request to update our neighbor
  // information
  if (!checkNeighbors())
    return;

  // Yes ! Create the beacon message
  attrs.push_back(GeoBeaconTypeAttr.make(NRAttribute::IS, GEO_REQUEST));
  attrs.push_back(GeoLatitudeAttr.make(NRAttribute::IS, geo_latitude_));
  attrs.push_back(GeoLongitudeAttr.make(NRAttribute::IS, geo_longitude_));
  attrs.push_back(GeoRemainingEnergyAttr.make(NRAttribute::IS,
					      remainingEnergy()));

  // Neighbor beacon msg is a DATA message
  beacon_msg = new Message(DIFFUSION_VERSION, DATA, 0, 0,
			   attrs.size(), pkt_count_, rdm_id_,
			   BROADCAST_ADDR, LOCALHOST_ADDR);
  // Don't forget to increment pkt_count
  pkt_count_++;

  beacon_msg->msg_attr_vec_ = CopyAttrs(&attrs);

  // Generate a beacon request, add some random jitter before actually
  // sending it
  DiffPrint(DEBUG_IMPORTANT, "GEO: Broadcast neighbor info request...\n");

  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_);

  GetTime(&last_neighbor_request_tv_);

  ClearAttrs(&attrs);
  delete beacon_msg;
}

void GeoRoutingFilter::updateNeighbor(int32_t neighbor_id,
				      double neighbor_longitude,
				      double neighbor_latitude,
				      double neighbor_energy)
{
  NeighborEntry *neighbor_entry;

  // Look for this neighbor in our neighbor's list
  neighbor_entry = findNeighbor(neighbor_id);

  if (!neighbor_entry){
    // Insert a new neighbor into our list
    DiffPrint(DEBUG_IMPORTANT, "GEO: Inserting a new neighbor %d !\n",
	      neighbor_id);

    neighbor_entry = new NeighborEntry(neighbor_id, neighbor_longitude,
				       neighbor_latitude, neighbor_energy);

    // Insert new element with key neighbor_id into the hash map
    neighbors_list_.push_back(neighbor_entry);
  }
  else{
    // Update an existing neighbor entry
    
    neighbor_entry->longitude_ = neighbor_longitude;
    neighbor_entry->latitude_ = neighbor_latitude;
    neighbor_entry->remaining_energy_ = neighbor_energy;

    GetTime(&(neighbor_entry->tv_));
  }
}

PktHeader * GeoRoutingFilter::retrievePacketHeader(Message *msg)
{
  PacketList::iterator packet_itr;
  PktHeader *pkt_header = NULL;

  for (packet_itr = message_list_.begin();
       packet_itr != message_list_.end(); ++packet_itr){
    pkt_header = *packet_itr;
    if ((pkt_header->rdm_id_ == msg->rdm_id_) &&
	(pkt_header->pkt_num_ == msg->pkt_num_)){
      packet_itr = message_list_.erase(packet_itr);
      return pkt_header;
    }
  }

  // Entry not found in our list
  return NULL;
}