geo-routing.cc

定向扩散路由协议

//
// geo-routing.cc : GEAR Filter
// authors        : Yan Yu and Fabio Silva
//
// Copyright (C) 2000-2002 by the University of Southern California
// Copyright (C) 2000-2002 by the University of California
// $Id: geo-routing.cc,v 1.14 2002/08/23 01:13:11 fabio Exp $
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License,
// version 2, as published by the Free Software Foundation.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License along
// with this program; if not, write to the Free Software Foundation, Inc.,
// 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
//
//

#include "geo-routing.hh"

#ifdef NS_DIFFUSION
static class GeoRoutingFilterClass : public TclClass {
public:
  GeoRoutingFilterClass() : TclClass("Application/DiffApp/GeoRoutingFilter") {}
  TclObject * create(int argc, const char*const* argv) {
    if (argc == 5)
      return (new GeoRoutingFilter(argv[4]));
    else{
      fprintf(stderr,
	      "Insufficient number of args for creating GeoRoutingFilter");
      return (NULL);
    }
  }
} class_geo_routing_filter;

int GeoRoutingFilter::command(int argc, const char*const* argv) {
  if (argc == 2) {
    if (strcmp(argv[1], "start") == 0) {
      run();
      return TCL_OK;
    }
  }
  if (argc == 3) {
    if (strcmp(argv[1], "node") == 0) {
      node_ = (MobileNode *)TclObject::lookup(argv[2]);
      return TCL_OK;
    }
  }

  return DiffApp::command(argc, argv);
}
#endif // NS_DIFFUSION

void GeoFilterReceive::recv(Message *msg, handle h)
{
  app_->recv(msg, h);
}

int GeoTimerReceive::expire(handle hdl, void *p)
{
  return app_->processTimers(hdl, p);
}

//need to change this funciton later..!!!!!!!
void GeoTimerReceive::del(void *p)
{
  TimerType *timer;
  Message *msg;

  timer = (TimerType *) p;

  switch (timer->which_timer_){

  case MESSAGE_SEND_TIMER:

    msg = ((Message *) timer->param_);

    if (msg)
      delete msg;

    break;

  }

  delete timer;
}

int GeoRoutingFilter::processTimers(handle hdl, void *p)
{
  TimerType *timer;
  Message *msg;
  int timeout = 0;

  timer = (TimerType *) p;
 
  switch (timer->which_timer_){

  case MESSAGE_SEND_TIMER:

    msg = ((Message *) timer->param_);

    messageTimeout(msg);

    // Cancel Timer
    timeout = -1;

    break;

  case BEACON_REQUEST_TIMER:

    beaconTimeout();

    break;

  case NEIGHBOR_TIMER:

    neighborTimeout();

    break;

  default:

    DiffPrint(DEBUG_ALWAYS,
	      "Error: ProcessTimers received unknown timer %d !\n",
	      timer->which_timer_);

    break;
  }

  return timeout;
}

void GeoRoutingFilter::beaconTimeout()
{
  NRAttrVec attrs;
  Message *beacon_msg;
  struct timeval tv;

  GetTime(&tv);

  DiffPrint(DEBUG_IMPORTANT, "GEO: Beacon Timeout !\n");

  // We broadcast the request from time to time, in case a new
  // neighbor joins in and never gets a chance to get its informaiton

  if ((tv.tv_sec - last_neighbor_request_tv_.tv_sec) >
      GEO_NEIGHBOR_REQUEST_PERIOD){

    // Update timestamp
    GetTime(&last_neighbor_request_tv_);

    // Sends a beacon to all neighbors
    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()));

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

    DiffPrint(DEBUG_IMPORTANT, "GEO: Sending Beacon Request...\n");
    ((DiffusionRouting *)dr_)->sendMessage(beacon_msg, post_filter_handle_);

    ClearAttrs(&attrs);
    delete beacon_msg;
  }
}

void GeoRoutingFilter::neighborTimeout()
{
  NeighborList::iterator neighbor_itr;
  NeighborEntry *neighbor_entry;
  struct timeval tv;

  GetTime(&tv);

  DiffPrint(DEBUG_IMPORTANT, "GEO: Neighbors Timeout !\n");

  neighbor_itr = neighbors_list_.begin();

  while (neighbor_itr != neighbors_list_.end()){
    neighbor_entry = *neighbor_itr;
    DiffPrint(DEBUG_IMPORTANT, "GEO: Check: %d: %d --> %d\n",
	      neighbor_entry->id_, neighbor_entry->tv_.tv_sec, tv.tv_sec);

    if ((tv.tv_sec - neighbor_entry->tv_.tv_sec) >= GEO_NEIGHBOR_EXPIRED){
      // Delete timed-out neighbor
      DiffPrint(DEBUG_IMPORTANT, "GEO: Deleting neighbor %d\n",
		neighbor_entry->id_);
      neighbor_itr = neighbors_list_.erase(neighbor_itr);
      delete neighbor_entry;
    }
    else{
      DiffPrint(DEBUG_IMPORTANT, "GEO: Neighbor %d, (%d,%d)\n",
		neighbor_entry->id_, neighbor_entry->tv_.tv_sec,
		neighbor_entry->tv_.tv_usec);
      neighbor_itr++;
    }
  }
}

void GeoRoutingFilter::messageTimeout(Message *msg)
{
  // Send message
  DiffPrint(DEBUG_IMPORTANT, "Message Timeout !\n");

  ((DiffusionRouting *)dr_)->sendMessage(msg, post_filter_handle_,
					 GEOROUTING_POST_FILTER_PRIORITY);
}

void GeoRoutingFilter::recv(Message *msg, handle h)
{
  if (h == pre_filter_handle_){
    preProcessFilter(msg);
    return;
  }

  if (h == post_filter_handle_){
    postProcessFilter(msg);
    return;
  }

  DiffPrint(DEBUG_ALWAYS,
	    "Error: Received message for an unknown handle %d !\n", h);
}

void GeoRoutingFilter::preProcessFilter(Message *msg)
{
  NRSimpleAttribute<void *> *heuristic_value_attribute = NULL;
  NRSimpleAttribute<int> *beacon_type_attribute = NULL;
  NRSimpleAttribute<double> *beacon_info_attribute = NULL;
  double neighbor_energy = 0.0;
  double neighbor_longitude = 0.0;
  double neighbor_latitude = 0.0;
  double new_heuristic_value = 0.0;
  int32_t neighbor_id;
  int beacon_type;
  struct timeval tv; 
  HeuristicValue *heuristic_value = NULL;
  GeoLocation dst_location;
  TimerType *timer = NULL;
  NRAttrVec attrs;
  Message *beacon_msg = NULL;
  PktHeader *pkt_header = NULL;

  switch (msg->msg_type_){

  case INTEREST:
  case EXPLORATORY_DATA:
  case PUSH_EXPLORATORY_DATA:

    if (msg->new_message_){
      // Don't worry about old messages

      // Pre-process the messages, extracting the geo-header attribute
      // if it's present (or trying to create a new geo-header
      // otherwise)
      pkt_header = preProcessMessage(msg);

      // If we have a packet header, add it to the message list
      if (pkt_header){
	sendNeighborRequest();
      	message_list_.push_back(pkt_header);
      }
    }

    ((DiffusionRouting *)dr_)->sendMessage(msg, pre_filter_handle_);

    break;

  case DATA:

    // Look for a beacon type attribute in the data message
    beacon_type_attribute = GeoBeaconTypeAttr.find(msg->msg_attr_vec_);

    // If there is no beacon_type attribute, this is not a beacon data
    // message. So, we just forward it to the next filter
    if (!beacon_type_attribute){
      ((DiffusionRouting *)dr_)->sendMessage(msg, pre_filter_handle_);

      break;
    }

    // Get neighbor id and time
    neighbor_id = msg->last_hop_;
    GetTime(&tv);

    if ((neighbor_id == BROADCAST_ADDR) ||
	(neighbor_id == LOCALHOST_ADDR)){
      DiffPrint(DEBUG_ALWAYS, "GEO: Neighbor ID Invalid !\n");
      return;
    }

    // Look for the rest of the information
    beacon_type = beacon_type_attribute->getVal();

    beacon_info_attribute = GeoLongitudeAttr.find(msg->msg_attr_vec_);
    if (beacon_info_attribute){
      neighbor_longitude = beacon_info_attribute->getVal();
    }

    beacon_info_attribute = GeoLatitudeAttr.find(msg->msg_attr_vec_);
    if (beacon_info_attribute){
      neighbor_latitude = beacon_info_attribute->getVal();
    }

    beacon_info_attribute = GeoRemainingEnergyAttr.find(msg->msg_attr_vec_);
    if (beacon_info_attribute){
      neighbor_energy = beacon_info_attribute->getVal();
    }

    // Update our neighbor list with the beacon's information
    updateNeighbor(neighbor_id, neighbor_longitude,
		   neighbor_latitude, neighbor_energy);

    DiffPrint(DEBUG_IMPORTANT, "GEO: Id: %d - Location: %f,%f - Energy: %f\n",
	      neighbor_id, neighbor_longitude,
	      neighbor_latitude, neighbor_energy);

    if (beacon_type == GEO_REQUEST){
      DiffPrint(DEBUG_IMPORTANT, "GEO: Received a beacon request...\n");
      // If we received a neighbor request, we have to generate a
      // reply and send it after some random time. But this has to be
      // suppresed if we have recently done it already

      if (last_beacon_reply_tv_.tv_sec > 0){
	// Send at most one neighbor beacon every
	// GEO_BEACON_REPLY_PERIOD seconds
	if ((tv.tv_sec - last_beacon_reply_tv_.tv_sec)
	    < GEO_BEACON_REPLY_PERIOD){
	  DiffPrint(DEBUG_IMPORTANT, "GEO: Ignore beacon request !\n");
	  break;
	}
      }

      // Send out a beacon
      timer = new TimerType(MESSAGE_SEND_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_REPLY));

      // Let's try to extract the beacon's heuristic_value
      heuristic_value_attribute = GeoHeuristicValueAttr.find(msg->msg_attr_vec_);

      if (heuristic_value_attribute){
	// Heuristic Value attribute found ! Include information about
	// this destination if we have anything in our table
	heuristic_value = (HeuristicValue *) heuristic_value_attribute->getVal();
	dst_location.longitude_ = heuristic_value->dst_longitude_;
	dst_location.latitude_ = heuristic_value->dst_latitude_;

	// Retrieve heuristic_value
	DiffPrint(DEBUG_IMPORTANT,
		  "GEO: Request h-value in BEACON_REQUEST, (%lf, %lf)\n",
		  dst_location.longitude_, dst_location.latitude_); 

	new_heuristic_value = retrieveHeuristicValue(dst_location);

	if (new_heuristic_value != INITIAL_HEURISTIC_VALUE){
	  // Add the heuristic_value to the message if we have any
	  // information about this particular destination
 
	  heuristic_value = new HeuristicValue(dst_location.longitude_,
					       dst_location.latitude_,
					       new_heuristic_value);

	  DiffPrint(DEBUG_IMPORTANT,
		    "GEO: Generated h-value in BEACON_REPLY, (%lf,%lf):%lf\n",
		    dst_location.longitude_, dst_location.latitude_,
		    new_heuristic_value);

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

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

      // Don't forget to update pkt_count
      pkt_count_++;
      beacon_msg->msg_attr_vec_ = CopyAttrs(&attrs);

      timer->param_ = (void *) CopyMessage(beacon_msg);

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

      ClearAttrs(&attrs);
      delete beacon_msg;

      DiffPrint(DEBUG_IMPORTANT,
		"GEO: Sent a beacon reply in response to beacon request !\n");
      DiffPrint(DEBUG_IMPORTANT,
		"GEO: Local info: Location: %f,%f - Energy :%f\n",
		geo_longitude_,	geo_latitude_, remainingEnergy());

      // Update beacon timestamp
      GetTime(&last_beacon_reply_tv_);
    }
    else{
      if (beacon_type == GEO_REPLY){
	DiffPrint(DEBUG_IMPORTANT, "GEO: Received a beacon reply\n");
      }
      else{
	if (beacon_type == GEO_UPDATE){
	  DiffPrint(DEBUG_IMPORTANT, "GEO: Received a beacon update\n");
	}
	else{
	  DiffPrint(DEBUG_ALWAYS, "GEO: Received an unknown message !\n");
	  return;
	}
      }

      // Extract the heuristic_value from the message
      heuristic_value_attribute = GeoHeuristicValueAttr.find(msg->msg_attr_vec_);

      if (heuristic_value_attribute){
	heuristic_value = (HeuristicValue *) heuristic_value_attribute->getVal();