diff_rate.cc

ns下的dd协议代码 可以进行wsn路由协议的仿真

/*
 * diff_rate.cc
 * Copyright (C) 2000 by the University of Southern California
 * $Id: diff_rate.cc,v 1.8 2005/08/25 18:58:03 johnh 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.
 *
 *
 * The copyright of this module includes the following
 * linking-with-specific-other-licenses addition:
 *
 * In addition, as a special exception, the copyright holders of
 * this module give you permission to combine (via static or
 * dynamic linking) this module with free software programs or
 * libraries that are released under the GNU LGPL and with code
 * included in the standard release of ns-2 under the Apache 2.0
 * license or under otherwise-compatible licenses with advertising
 * requirements (or modified versions of such code, with unchanged
 * license).  You may copy and distribute such a system following the
 * terms of the GNU GPL for this module and the licenses of the
 * other code concerned, provided that you include the source code of
 * that other code when and as the GNU GPL requires distribution of
 * source code.
 *
 * Note that people who make modified versions of this module
 * are not obligated to grant this special exception for their
 * modified versions; it is their choice whether to do so.  The GNU
 * General Public License gives permission to release a modified
 * version without this exception; this exception also makes it
 * possible to release a modified version which carries forward this
 * exception.
 *
 */

/****************************************************************/
/* diff_rate.cc : Chalermek Intanagonwiwat (USC/ISI)  05/18/99  */
/****************************************************************/

// Important Note: Work still in progress !

#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <signal.h>
#include <float.h>

#include <tcl.h>
#include <stdlib.h>

#include "diff_header.h"
#include "agent.h"
#include "tclcl.h"
#include "ip.h"
#include "config.h"
#include "packet.h"
#include "trace.h"
#include "random.h"
#include "classifier.h"
#include "node.h"
#include "mobilenode.h"
#include "diffusion.h"
#include "iflist.h"
#include "hash_table.h"
#include "arp.h"
#include "mac.h"
#include "ll.h"
#include "dsr/path.h"
#include "god.h"
#include "routing_table.h"
#include "diff_rate.h"

extern char *MsgStr[];

static class DiffusionRateClass : public TclClass {
public:
  DiffusionRateClass() : TclClass("Agent/Diffusion/RateGradient") {}
  TclObject* create(int , const char*const* ) {
    return(new DiffusionRate());
  }
} class_diffusion_rate;


void GradientTimer::expire(Event *)
{
  a_->GradientTimeOut();
}


void NegativeReinforceTimer::expire(Event *)
{
  a_->NegReinfTimeOut();
}


DiffusionRate::DiffusionRate() : DiffusionAgent()
{
  DUP_SUP_ = true;

  sub_type_ = BCAST_SUB;
  org_type_ = UNICAST_ORG;
  pos_type_ = POS_ALL;
  pos_node_type_ = INTM_POS;
  neg_win_type_ = NEG_TIMER;
  neg_thr_type_ = NEG_ABSOLUTE;
  neg_max_type_ = NEG_FIXED_MAX;

  num_not_send_bcast_data = 0;
  num_data_bcast_send = 0;
  num_data_bcast_rcv = 0;
  num_neg_bcast_send = 0;
  num_neg_bcast_rcv = 0;
}


void DiffusionRate::recv(Packet* packet, Handler*)
{
  hdr_cdiff* dfh = HDR_CDIFF(packet);

  // Packet Hash Table is used to keep info about experienced pkts.

  Pkt_Hash_Entry *hashPtr= PktTable.GetHash(dfh->sender_id, dfh->pk_num);


#ifdef DEBUG_RATE
     printf("DF node %x recv %s (%x, %x, %d)\n",
	    THIS_NODE, MsgStr[dfh->mess_type], (dfh->sender_id).addr_, 
	    (dfh->sender_id).port_, dfh->pk_num);
#endif


     // Received this packet before ?

     if (hashPtr != NULL) {
       consider_old(packet);
       return;
     }

     // Never receive it before ? Put in hash table.

     PktTable.put_in_hash(dfh);

     // Take action for a new pkt.
     // Check for dupplicate data at application
     
     if (DUP_SUP_ == true) {  
       
       if (dfh->mess_type == DATA) {
	 if (DataTable.GetHash(dfh->attr) != NULL) {
	   consider_old(packet);
	   return;
	 } else {
	   DataTable.PutInHash(dfh->attr);
	 }
	 
       }
     } 
       
     consider_new(packet);     
}


void DiffusionRate::consider_old(Packet *pkt)
{
  hdr_cdiff* dfh = HDR_CDIFF(pkt);
  hdr_cmn* cmh = HDR_CMN(pkt);
  unsigned char msg_type = dfh->mess_type;
  unsigned int dtype = dfh->data_type;

  switch (msg_type) {
    case INTEREST :
      InterestHandle(pkt);
      return;

    case DATA: 

      if (cmh->next_hop_ == (nsaddr_t)MAC_BROADCAST) {
	num_data_bcast_rcv++;
      }

      if (dfh->report_rate == ORIGINAL) {
	  routing_table[dtype].CntOldOrg(dfh->forward_agent_id);
      }
      Packet::free(pkt);
      return;
    
    case NEG_REINFORCE:
      if (cmh->next_hop_ == (nsaddr_t)MAC_BROADCAST) {
	num_neg_bcast_rcv++;
      }
      break;
      
    default : 
      Packet::free(pkt);        
      break;
  }
}


void DiffusionRate::consider_new(Packet *pkt)
{
  hdr_cdiff* dfh = HDR_CDIFF(pkt);
  hdr_cmn * cmh = HDR_CMN(pkt);
  unsigned char msg_type = dfh->mess_type;
  unsigned int dtype = dfh->data_type;

  Agent_List *agentPtr;
  Packet *gen_pkt;
  hdr_cdiff *gen_dfh;

  switch (msg_type) {
    case INTEREST : 
      InterestHandle(pkt);
      return;

    case POS_REINFORCE :
      if ( POS_REINF_ == false ) {
	printf("Hey, we are not in pos_reinf mode.\n");
	Packet::free(pkt);
	exit(-1);
      }

      ProcessPosReinf(pkt);
      return;

    case NEG_REINFORCE :  
      if (cmh->next_hop_ == (nsaddr_t)MAC_BROADCAST) {
	num_neg_bcast_rcv++;
      } else {
	routing_table[dtype].CntNeg(dfh->forward_agent_id);
      }

      if (NEG_REINF_ == false) {
	printf("Hey, we are not in neg_reinf mode.\n");
	Packet::free(pkt);
	exit(-1);
      }

      ProcessNegReinf(pkt);
      return;

    case DATA_READY :

      // put source_agent in source list of routing table

      agentPtr = new Agent_List;
      AGT_ADDR(agentPtr) = dfh->sender_id;
      agentPtr->next = routing_table[dtype].source;
      routing_table[dtype].source = agentPtr;

      God::instance()->AddSource(dtype, (dfh->sender_id).addr_);
	/*
	printf("DF %d received DATA_READY (%d, %d, %d) at time %lf\n",
	       THIS_NODE, dfh->sender_id.addr_, dfh->sender_id.port_,
	       dfh->pk_num, NOW);
	*/

      if (routing_table[dtype].active != NULL ||
	    routing_table[dtype].sink != NULL) {
	gen_pkt = prepare_message(dtype, dfh->sender_id, DATA_REQUEST);
	gen_dfh = HDR_CDIFF(gen_pkt);
	gen_dfh->report_rate = SUB_SAMPLED;
	send_to_dmux(gen_pkt, 0);

	  /*
	  printf("DF %d sent DATA_REQUEST (%d, %d, %d) at time %lf\n",
		 THIS_NODE, gen_dfh->sender_id.addr_, gen_dfh->sender_id.port_,
		 gen_dfh->pk_num, NOW);
	  */
      }
	  
      Packet::free(pkt);
      return;

    case DATA :

      if (cmh->next_hop_ == (nsaddr_t)MAC_BROADCAST) {
	num_data_bcast_rcv++;
      }

      DataForSink(pkt);

      if (dfh->report_rate == SUB_SAMPLED) {
       	  routing_table[dtype].CntNewSub(dfh->forward_agent_id);
	  FwdData(pkt);
	  return;
      }

      if (dfh->report_rate == ORIGINAL) {
	  routing_table[dtype].new_org_counter++;
	  routing_table[dtype].CntNewOrg(dfh->forward_agent_id);
	  FwdData(pkt);

	  if (neg_win_type_ == NEG_COUNTER) {
	    CheckNegCounter(dtype);
	    return;
	  }
      }
      return;

    default : 
      Packet::free(pkt);        
      break;
  }
}


void DiffusionRate::CheckNegCounter(int dtype)
{
  if (neg_max_type_ == NEG_FIXED_MAX) {
	  if (routing_table[dtype].new_org_counter >= MAX_NEG_COUNTER
	      && NEG_REINF_ == true) {
	    GenNeg(dtype);
	    routing_table[dtype].new_org_counter = 0;
	    routing_table[dtype].ClrAllNewOrg();
	    routing_table[dtype].ClrAllOldOrg();
	  }
	  return;
  }

  if (neg_max_type_ == NEG_SCALE_MAX) {
	  if (routing_table[dtype].new_org_counter >= 
	      PER_IIF * routing_table[dtype].num_iif
	      && NEG_REINF_ == true) {
	    GenNeg(dtype);
	    routing_table[dtype].new_org_counter = 0;
	    routing_table[dtype].ClrAllNewOrg();
	    routing_table[dtype].ClrAllOldOrg();
	  }
	  return;
  }
}


void DiffusionRate::InterestHandle(Packet *pkt)
{
  hdr_cdiff *dfh = HDR_CDIFF(pkt);
  unsigned int dtype = dfh->data_type;
  Agent_List *agentPtr;

  nsaddr_t from_nodeID;
  PrvCurPtr RetVal;
  Out_List *OutPtr;


   if (dfh->ts_ + INTEREST_TIMEOUT < NOW) {
      Packet::free(pkt);
      return;
   }

   // Check if it comes from sink agent of this node
   // If so we have to keep it in sink list 

   from_nodeID = (dfh->sender_id).addr_;

   if (THIS_NODE == from_nodeID) {       // From sink agent on the same node.

     // It's from a sink on this node.
     // Is it already in list ?

     RetVal = INTF_FIND(routing_table[dtype].sink, dfh->sender_id);

     if (RetVal.cur == NULL) {            
	// No, it's not.
	agentPtr = new Agent_List;
	AGT_ADDR(agentPtr) = dfh->sender_id;
	INTF_INSERT(routing_table[dtype].sink, agentPtr);

	God::instance()->AddSink(dtype, THIS_NODE);
     }	
   } else {                                    // From different node.

     // If we have gradient for the forwarder.
	
     RetVal = INTF_FIND(routing_table[dtype].active, dfh->forward_agent_id);
     if (RetVal.cur == NULL) {
       OutPtr = new Out_List;
       AGT_ADDR(OutPtr) = dfh->forward_agent_id;
       GRADIENT(OutPtr) = dfh->report_rate;
       GRAD_TMOUT(OutPtr) = dfh->ts_ + INTEREST_TIMEOUT;
       INTF_INSERT(routing_table[dtype].active, OutPtr);
       routing_table[dtype].num_active ++;	  
     } else {
      GRAD_TMOUT(RetVal.cur) = max(GRAD_TMOUT(RetVal.cur),
				   dfh->ts_ + INTEREST_TIMEOUT);
     }

   }

   if (NOW > routing_table[dtype].last_fwd_time + INTEREST_PERIODIC) {
     if (routing_table[dtype].ExistOriginalGradient() == true) {
       DataReqAll(dtype, ORIGINAL);
     } else {
       DataReqAll(dtype, SUB_SAMPLED);
     }
     routing_table[dtype].last_fwd_time = NOW;

     double x,x1,y,y1,m,z;
     x1=dfh->x;
     y1=dfh->y;
     node->getLoc(&x,&y,&z);
     m=(x-x1)*(x-x1)+(y-y1)*(y-y1);
     m=sqrt(m)*0.0316;                   //计算当前节点到达汇聚节点的最佳跳数
     node->goodhop=m;

     MACprepare(pkt, MAC_BROADCAST, NS_AF_ILINK, 0);
     MACsend(pkt, JITTER*Random::uniform(1.0));
     overhead++;

#ifdef DEBUG_RATE
     hdr_cmn *cmh = HDR_CMN(pkt);
     printf("DF node %x will send %s (%x, %x, %d) to %x\n",
	    THIS_NODE, MsgStr[dfh->mess_type], (dfh->sender_id).addr_, 
	    (dfh->sender_id).port_, dfh->pk_num, cmh->next_hop());
#endif


     


     return;
   }
     
    
   Packet::free(pkt);
   return;
}


void DiffusionRate::NegReinfTimeOut()
{
  for (int i=0; i<MAX_DATA_TYPE; i++) {
    GenNeg(i);
    routing_table[i].new_org_counter = 0;
    routing_table[i].ClrAllNewOrg();
    routing_table[i].ClrAllOldOrg();
  }
  
  neg_reinf_timer->resched(NEG_CHECK);
}


void DiffusionRate::GradientTimeOut()
{
  int i;
  Agent_List *cur_out, **prv_out;
 
  for (i=0; i<MAX_DATA_TYPE; i++) {
    for (cur_out = routing_table[i].active, 
	 prv_out = (Agent_List **)&routing_table[i].active; 
	 cur_out != NULL; ) {
      
      if (NOW > GRAD_TMOUT(cur_out)) {
	INTF_REMOVE(prv_out, cur_out);
	routing_table[i].num_active -- ;
	cur_out = *prv_out;
      }
      else {
	prv_out = &(cur_out->next);
	cur_out = cur_out->next;
      }
      
    }
  }
  
  gradient_timer->resched(INTEREST_TIMEOUT);
}


bool DiffusionRate::FwdSubsample(Packet *pkt)
{
  hdr_cdiff *dfh = HDR_CDIFF(pkt);
  Out_List *cur_out;
  Packet   *cur_pkt;
  hdr_cdiff *cur_dfh;
  hdr_ip   *cur_iph;
  unsigned int dtype = dfh->data_type;

    if (routing_table[dtype].num_active <= 0) {   // Won't forward
      num_not_send_bcast_data++;
      return false;
    } 

    // Will forward
      
    num_data_bcast_send++;

    if (sub_type_ == BCAST_SUB) {
	MACprepare(pkt, MAC_BROADCAST, NS_AF_ILINK, 0);
	MACsend(pkt, JITTER*Random::uniform(1.0));

#ifdef DEBUG_RATE 
	hdr_cmn *cmh = HDR_CMN(pkt);
	printf("DF node %x will send %s (%x, %x, %d) to %x\n",
	   THIS_NODE, MsgStr[dfh->mess_type], (dfh->sender_id).addr_,
	   (dfh->sender_id).port_, dfh->pk_num, cmh->next_hop());
#endif // DEBUG_RATE

	return true;
    }

    if (sub_type_ == UNICAST_SUB) {
	for (cur_out = routing_table[dtype].active; cur_out!= NULL; 
	   cur_out = OUT_NEXT(cur_out)) {

	  cur_pkt       = pkt->copy();
	  cur_iph       = HDR_IP(cur_pkt);
	  cur_iph->dst_ = AGT_ADDR(cur_out);

	  cur_dfh       = HDR_CDIFF(cur_pkt);
	  cur_dfh->forward_agent_id = here_;
	  cur_dfh->num_next = 1;
	  cur_dfh->next_nodes[0] = NODE_ADDR(cur_out);

	  MACprepare(cur_pkt, NODE_ADDR(cur_out), NS_AF_INET, 
		 MAC_RETRY_);
	  MACsend(cur_pkt, 0);      

#ifdef DEBUG_RATE
	  cur_cmh = HDR_CMN(cur_pkt);
	  printf("DF node %x will send %s (%x, %x, %d) to %x\n",
	     THIS_NODE, MsgStr[cur_dfh->mess_type], 
	     (cur_dfh->sender_id).addr_, (cur_dfh->sender_id).port_, 
	     cur_dfh->pk_num, cur_cmh->next_hop());
#endif // DEBUG_RATE

	} // endfor
	
	return true;
    }   // endif unicast sub

    return false;
}


void DiffusionRate::TriggerPosReinf(Packet *pkt, ns_addr_t forward_agent)
{
  hdr_cdiff *dfh = HDR_CDIFF(pkt);
  unsigned int dtype = dfh->data_type;
  nsaddr_t forwarder_node = forward_agent.addr_;

  if (pos_node_type_ == INTM_POS) {
    if (routing_table[dtype].sink != NULL ||
	routing_table[dtype].ExistOriginalGradient() == true) {
      DataReqAll(dtype, ORIGINAL);
      if (THIS_NODE != forwarder_node) {
       PosReinf(dtype, forwarder_node, dfh->sender_id,
		      dfh->pk_num);
       routing_table[dtype].CntPosSend(forward_agent);
       routing_table[dtype].ClrNewSub(forward_agent);
      } 
    }
    return;
  }
 

  if (pos_node_type_ == END_POS) {
    if (routing_table[dtype].sink != NULL) {
      DataReqAll(dtype, ORIGINAL);
      if (THIS_NODE != forwarder_node) {
       PosReinf(dtype, forwarder_node, dfh->sender_id,
		      dfh->pk_num);
       routing_table[dtype].CntPosSend(forward_agent);
       routing_table[dtype].ClrNewSub(forward_agent);
      } 
    }

    return;
  }
}


void DiffusionRate::FwdOriginal(Packet *pkt)
{
  hdr_cdiff *dfh = HDR_CDIFF(pkt);
  unsigned int dtype = dfh->data_type;
  Out_List *cur_out;
  Packet   *cur_pkt;
  hdr_cdiff *cur_dfh;
  hdr_ip   *cur_iph;
 
  if (org_type_ == BCAST_ORG) {
    MACprepare(pkt, MAC_BROADCAST, NS_AF_ILINK, 0);
    MACsend(pkt, JITTER*Random::uniform(1.0));

#ifdef DEBUG_RATE 
    hdr_cmn *cmh = HDR_CMN(pkt);
    printf("DF node %x will send %s (%x, %x, %d) to %x\n",
	   THIS_NODE, MsgStr[dfh->mess_type], (dfh->sender_id).addr_,