geo-routing.cc

无线个域网（WPAN）就是在个人周围空间形成的无线网络

//
// 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/11/26 22:45:37 haldar 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) {
    return (new GeoRoutingFilter());
  }
} 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;
    }
  }
  return DiffApp::command(argc, argv);
}
#endif // NS_DIFFUSION

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

int GeoMessageSendTimer::expire()
{
  // Call timeout function
  agent_->messageTimeout(msg_);

  // Do not reschedule this timer
  return -1;
}

int GeoNeighborsTimer::expire()
{
  // Call timeout function
  agent_->neighborTimeout();

  // Reschedule this timer
  return 0;
}

int GeoBeaconRequestTimer::expire()
{
  // Call the timeout function
  agent_->beaconTimeout();

  // Reschedule this timer
  return 0;
}

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

  GetTime(&tv);

  DiffPrint(DEBUG_IMPORTANT, "Gear: %d.%06d - Beacon Timeout !\n",
	    tv.tv_sec, tv.tv_usec);

  // 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 ((last_neighbor_request_tv_.tv_sec == 0) ||
      ((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, "Gear: %d.%06d - Sending Beacon Request...\n",
	      tv.tv_sec, tv.tv_usec);
    ((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, "Gear: %d.%06d - Neighbors Timeout !\n",
	    tv.tv_sec, tv.tv_usec);

  neighbor_itr = neighbors_list_.begin();

  while (neighbor_itr != neighbors_list_.end()){
    neighbor_entry = *neighbor_itr;
    DiffPrint(DEBUG_IMPORTANT, "Gear: %d.%06d - Check: %d: %d --> %d\n",
	      tv.tv_sec, tv.tv_usec, 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, "Gear: %d.%06d - Deleting neighbor %d\n",
		tv.tv_sec, tv.tv_usec, neighbor_entry->id_);
      neighbor_itr = neighbors_list_.erase(neighbor_itr);
      delete neighbor_entry;
    }
    else{
      DiffPrint(DEBUG_IMPORTANT, "Gear: %d.%06d - Neighbor %d, (%d,%d)\n",
		tv.tv_sec, tv.tv_usec, neighbor_entry->id_,
		neighbor_entry->tv_.tv_sec, neighbor_entry->tv_.tv_usec);
      neighbor_itr++;
    }
  }
}

void GeoRoutingFilter::messageTimeout(Message *msg)
{
  struct timeval tv;

  // Get current time
  GetTime(&tv);

  // Send message
  DiffPrint(DEBUG_IMPORTANT, "Gear: %d.%06d - Message Timeout !\n",
	    tv.tv_sec, tv.tv_usec);

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

void GeoRoutingFilter::recv(Message *msg, handle h)
{
  struct timeval tv;

  GetTime(&tv);

  if (h == pre_filter_handle_){
    preProcessFilter(msg);
    return;
  }

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

  DiffPrint(DEBUG_ALWAYS,
	    "Gear: %d.%06d - Received message for an unknown handle %d !\n",
	    tv.tv_sec, tv.tv_usec, 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;
  TimerCallback *beacon_timer = NULL;
  NRAttrVec attrs;
  Message *beacon_msg = NULL;
  PktHeader *pkt_header = NULL;

  // Get current time
  GetTime(&tv);

  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
    neighbor_id = msg->last_hop_;

    if ((neighbor_id == BROADCAST_ADDR) ||
	(neighbor_id == LOCALHOST_ADDR)){
      DiffPrint(DEBUG_ALWAYS, "Gear: %d.%06d - Neighbor ID Invalid !\n",
		tv.tv_sec, tv.tv_usec);
      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);

    // Update time
    GetTime(&tv);

    DiffPrint(DEBUG_IMPORTANT, "Gear: %d.%06d - Beacon Information id: %d - location: %f,%f - energy: %f\n",
	      tv.tv_sec, tv.tv_usec,
	      neighbor_id, neighbor_longitude,
	      neighbor_latitude, neighbor_energy);

    if (beacon_type == GEO_REQUEST){
      DiffPrint(DEBUG_IMPORTANT,
		"Gear: %d.%06d - Received a beacon request...\n",
		tv.tv_sec, tv.tv_usec);
      // 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,
		    "Gear: %d.%06d - Ignoring beacon request until %d.%06d!\n",
		    tv.tv_sec, tv.tv_usec,
		    (tv.tv_sec + GEO_BEACON_REPLY_PERIOD), tv.tv_usec);
	  break;
	}
      }

      // Create beacon reply message
      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,
		  "Gear: %d.%06d - Requesting h-value in (%lf,%lf)\n",
		  tv.tv_sec, tv.tv_usec,
		  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,
		    "Gear: %d.%06d - Current h-value for (%lf,%lf):%lf\n",
		    tv.tv_sec, tv.tv_usec,
		    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);

      beacon_timer = new GeoMessageSendTimer(this, 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))),
					  beacon_timer);

      ClearAttrs(&attrs);
      delete beacon_msg;

      DiffPrint(DEBUG_IMPORTANT,
		"Gear: %d.%06d - Sending a beacon reply in response to request !\n",
		tv.tv_sec, tv.tv_usec);
      DiffPrint(DEBUG_IMPORTANT,
		"Gear: %d.%06d - Local info: location: %f,%f - energy: %f\n",
		tv.tv_sec, tv.tv_usec,
		geo_longitude_,	geo_latitude_, remainingEnergy());

      // Update beacon timestamp
      GetTime(&last_beacon_reply_tv_);
    }
    else{
      if (beacon_type == GEO_REPLY){
	DiffPrint(DEBUG_IMPORTANT, "Gear: %d.%06d - Received beacon reply\n",
		  tv.tv_sec, tv.tv_usec);
      }
      else{
	if (beacon_type == GEO_UPDATE){
	  DiffPrint(DEBUG_IMPORTANT,
		    "Gear: %d.%06d - Received beacon update\n",
		    tv.tv_sec, tv.tv_usec);
	}
	else{
	  DiffPrint(DEBUG_ALWAYS,
		    "Gear: %d.%06d - Received unknown message !\n",
		    tv.tv_sec, tv.tv_usec);
	  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();

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

	DiffPrint(DEBUG_IMPORTANT,
		  "Gear: %d.%06d - Received h-val update %d: (%lf,%lf):%f\n",
		  tv.tv_sec, tv.tv_usec,
		  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;
  struct timeval tv;

  // Get current time
  GetTime(&tv);

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