shr.h

大名鼎鼎的传感器网络仿真实验室平台SENSE

/*************************************************************************
 *   @<title> Self Healing Routing </title>@
 *
 *   @<!-- Copyright 2006, 2003 Mark Lisee, Gilbert (Gang) Chen, Boleslaw
 *   K. Szymanski and Rensselaer Polytechnic Institute. All worldwide rights
 *   reserved.  A license to use, copy, modify and distribute this software
 *   for non-commercial research purposes only is hereby granted, provided
 *   that this copyright notice and accompanying disclaimer is not modified or
 *   removed from the software.
 *
 *   DISCLAIMER: The software is distributed "AS IS" without any
 *   express or implied warranty, including but not limited to, any
 *   implied warranties of merchantability or fitness for a particular
 *   purpose or any warranty of non-infringement of any current or
 *   pending patent rights. The authors of the software make no
 *   representations about the suitability of this software for any
 *   particular purpose. The entire risk as to the quality and
 *   performance of the software is with the user. Should the software
 *   prove defective, the user assumes the cost of all necessary
 *   servicing, repair or correction. In particular, neither Rensselaer
 *   Polytechnic Institute, nor the authors of the software are liable
 *   for any indirect, special, consequential, or incidental damages
 *   related to the software, to the maximum extent the law
 *   permits.-->@
 *
 *************************************************************************/

#ifndef _shr_h_
#define _shr_h_
#include <map>
#include <list>

#define	MWL_DOUBLE_DELAY
const int	MWLTimeoutMultiplier = 10;

#ifdef	SHR_PRINT
#define shrDoPrint	(true)
#define	shrPrint(x)	 printf x
#else	//SHR_PRINT
#define	shrPrint(x)
#define	shrDoPrint	(false)
#endif	//SHR_PRINT

template <class PLD>
struct SHR_Struct
{
  enum PktType { REQUEST, REPLY, DATA, ACK, HELLO };
  enum AckType { AT_Destination, AT_Intermediate };
  // RREQ: type + src_addr + dst_addr + seq_number + hop
  enum { REQUEST_SIZE = 3 * sizeof(int) + 2 * ether_addr_t::LENGTH };
  // RREP: type + src_addr + dst_addr + seq_number + 2 * hop
  enum { REPLY_SIZE = 4 * sizeof(int) + 4 * ether_addr_t::LENGTH };
  // DATA: type + src_addr + dst_addr + seq_number + 2* hop 
  enum { DATA_SIZE = 4 * sizeof(int) + 4 * ether_addr_t::LENGTH };
  // ACK: type + ACK Type + src_addr + dst_addr + seq_number
  enum { ACK_SIZE = 3 * sizeof(int) + 2 * ether_addr_t::LENGTH };
  // HELLO: type + src_addr + dest_addr + hopCount
  enum { HELLO_SIZE = 2 * sizeof( int) + 2 * ether_addr_t::LENGTH };
    
  struct hdr_struct
  {
    PktType	type;
    AckType	ackType;
    ether_addr_t src_addr;
    ether_addr_t dst_addr;
    ether_addr_t cur_addr;
    ether_addr_t pre_addr;
    unsigned int seq_number;
    unsigned int size;
    double	send_time;
    unsigned int actual_hop;
    unsigned int expected_hop;
    unsigned int max_hop;
    double	delay;
    int		ackIndex;
    int		pktDelayIndex;
    bool	canceled;
    int		resend;
    bool	suboptimal;
    bool	newSeqNumber;
    int		helloData;
    Path	path;

    bool dump(std::string& str) const;
  };
  typedef PLD payload_t;
  typedef smart_packet_t<hdr_struct,PLD> packet_t;
};

/*
** Array to keep track of how many packets required a certain number of hop
** counts to reach the destination.
*/
#define	HCArraySize	(20+1)

enum SHRBackOff
{
  SHRBackOff_SSR = 1,
  SHRBackOff_SHR = 2,
  SHRBackOff_Incorrect = 3
};

/*
** The AckWindow is a period of time during which only Acks from intermediate
** nodes are sent. This prevents the Acks from colliding with packets that are
** being forwarded. Note that the destination sends its Ack as a normal packet,
** i.e. after the AckWindow. This is because when node N forwards a packet, it
** causes node N-1 to send an Ack (during the AckWindow) and N+1 to forward the
** packet (after the AckWindow).
*/
template <class PLD>
component SHR : public TypeII, public SHR_Struct<PLD>
{
 public:
  ether_addr_t	MyEtherAddr;
  simtime_t	ForwardDelay;
  double	RXThresh;
  bool		DumpPackets;
  double	AckWindow;	// see comment above
  int		MaxResend;
  unsigned int	TimeToLive;
  unsigned int	AdditionalHop;
    
  // statistics
  int		SentPackets;
  int		SentSuboptimal;
  int		CanceledPackets;
  int		CanceledSuboptimal;
  int		RecvPackets;
  int		RecvUniPackets;
  int		RecvDataPackets;
  double	TotalDelay;
  int		TotalSamples;
  int		TotalHop;
  int		HopCounts[ HCArraySize];

  Timer <trigger_t> transitionTimer;	// time it takes to go from sense to send
  inport void	TransitionTimer( trigger_t &);
  packet_t	*transitionPkt;		// pkt to be sent when timer expires

  inport inline void	from_transport( payload_t& pld, ether_addr_t& dst,
					unsigned int size);
  inport inline void	from_mac_data( packet_t* pkt, double power);
  inport inline void	from_mac_ack( bool errflag);
  inport inline void	from_mac_recv_recv_coll( packet_t *pkt1, packet_t *pkt2);

  // This is called when the power manager wakes up the node.
  inport void	from_pm_node_up();

  outport void		cancel();
  outport void		to_transport( payload_t &pld);
  outport void		to_mac( packet_t *pkt, unsigned int size,
				double backoff);

  InfiTimer <SHR_Struct<PLD>::packet_t *> ackTimer;
  inport inline void	AckTimer( packet_t *pkt, unsigned int index);
/*
** These methods must be defined even though they aren't used with the radio
** model. This is due to a limitation of the cxx utility.
**
** This timer schedules the first HELLO packet that is generated when a node
** comes back. Events on this timer should be scheduled only as a result of
** parsing the configuration file.
*/
 private:
  Timer <trigger_t> helloTimer;
 public:
  inport inline void	HelloTimer( trigger_t &);
/*
** The public interface to schedule a HELLO packet.
*/
 public:
  void		scheduleHELLO( double time);

  void		Start();
  void		Stop();
  void		clearStats();
		SHR();
  virtual	~SHR();
  int		getHCFromCostTable( int addr);
  void		dumpStatic( FILE *fp, int indent, int offset) const;
  void		dumpCacheStatic( FILE *fp, int indent, int offset) const;
  void		dump( FILE *fp, int indent, int offset) const;
  void		dumpCostTable( FILE *fp, int indent, int offset) const;
  void		generateHELLO();
  static void		setSlotWidth( double);
  static double		getSlotWidth();
  static void		setTransitionTime( double);
  static double		getTransitionTime();
  static void		setBackOff( SHRBackOff);
  static SHRBackOff	getBackOff();
  static void		setContinuousBackOff( bool);
  static bool		getContinuousBackOff();
  static void		setRouteRepair( int);
  static void		setVisualizer( Visualizer *ptr);
	
 private:
  enum UpdateType {Lower, Always, Hello};
  bool		updateHopCountInCache( ether_addr_t src,
				       unsigned int hopCount, UpdateType,
				       const char *, packet_t *pkt);
 protected:
  static SHRBackOff	backOff;
  static bool		continuousBackOff;
  static double		slotWidth;
  static double		transitionTime;
  static bool		RouteRepairEnabled;
  static Visualizer	*visualizer;
  void		CancelPacket( ether_addr_t& src, unsigned int seq_number);
  void		SendPacket( packet_t *pkt);
  void		AssignSeqNumber( packet_t *pkt);
  void		SendToMac( packet_t *pkt);
  void		SendAck( ether_addr_t, ether_addr_t, ether_addr_t, unsigned int,
			 simtime_t, bool fromDest);
  void		CheckBuffer( ether_addr_t, unsigned int);
  void		AddToSendQueue( packet_t *pkt);
  void		forwardAsFlood( packet_t *pkt);
  
  // these return pointers to packet_t, but I wasn't able to figure out
  // how to avoid compiler errors, therefore cast them to void *
  void		*createBasicPkt();
  void		*createDataPkt( payload_t &pld, ether_addr_t dst,
				unsigned int size);
  void		*createRequestPkt( ether_addr_t dst);
  void		*createReplyPkt( ether_addr_t src, unsigned int expectedHop);
  void		*createAckPkt( ether_addr_t src_addr, ether_addr_t cur_addr,
			       ether_addr_t pre_addr, unsigned int seq_number,
			       simtime_t delay, bool fromDest);
  void		*createHelloPkt( ether_addr_t dest_addr, int hopCount);

  bool		m_mac_busy;                  // if the mac layer is busy
  unsigned int	m_seq_number;        // current sequence number
  typedef std::list<packet_t* > packet_queue_t;

  class seq_number_t
  {
  public:
    seq_number_t () : state( Initial), current(0), bits(0u) {}
    bool check(int n)
      {
	if( n + (int)sizeof(unsigned long) <= current )
	  return true;
	if ( n > current )
	{
	  bits = bits << (n - current);
	  current = n;
	}
	
	unsigned long flag = 1 << (current - n);
	unsigned long r = flag & bits;
	bits |= flag;
	return r;
      }
    unsigned int	hopCount() const;
    void		hopCount( unsigned int newHC, bool force, bool print);
    static void		setCounter( int);
    static int		getCounter();
    void		dumpStatic( FILE *fp, int indent, int offset) const;
    void		dump( FILE *fp, int dest, int indent, int offset) const;
  private:
    unsigned int	currentHC;
    unsigned int	pendingHC;
    enum { Initial, Steady, Changing}	state;
    int		updateCtr;
    int		current;
    uint32_t	bits;
    static int	maxCounter;
  };

/*******************************************************************
 * For each source, we must maintain a @seq_number_t@ object, so we better
 * keep them in a map.
 *******************************************************************/

  typedef std::map<ether_addr_t, seq_number_t, ether_addr_t::compare> cache_t;
  cache_t	m_seq_cache;
  packet_queue_t m_data_buffer;    
 private:
  void		receiveAck( packet_t *ackPkt);
  void		receiveDataRep( packet_t *rcvdPkt);
  void		receiveHelloPacket( packet_t *pkt);
  void		*getFromAckList( packet_t *rcvdPkt);
  void		removeFromAckList( packet_t *pktToRemove, bool cancelTimer);
  void		doRouteRepair( packet_t *pktFromList, packet_t *rcvdPkt);
  static bool	doubleMsgPrinted;
  packet_queue_t m_send_queue;
  packet_queue_t m_ack_list;
  packet_t	*m_active_packet;

 public:
  InfiTimer <SHR_Struct<PLD>::packet_t *> pktDelayTimer;
  inport inline void	PktDelayTimer( packet_t *pkt, unsigned int index);
 private:
  packet_queue_t m_delay_list;
};

template <class PLD> SHRBackOff	SHR<PLD>::backOff;
template <class PLD> bool	SHR<PLD>::continuousBackOff;
template <class PLD> double	SHR<PLD>::slotWidth;
template <class PLD> double	SHR<PLD>::transitionTime;
template <class PLD> bool	SHR<PLD>::RouteRepairEnabled;
template <class PLD> int	SHR<PLD>::seq_number_t::maxCounter = 1;
template <class PLD> bool	SHR<PLD>::doubleMsgPrinted = false;
template <class PLD> Visualizer	*SHR<PLD>::visualizer = NULL;

template <class PLD>
void SHR<PLD>::setVisualizer(
  Visualizer	*ptr)
{
  visualizer = ptr;
  return;
}

template <class PLD>
int SHR<PLD>::seq_number_t::getCounter()
{
  return maxCounter;
}

template <class PLD>
void SHR<PLD>::seq_number_t::setCounter(
  int	newCounter)
{
  maxCounter = newCounter;
  return;
}

template <class PLD>
unsigned int SHR<PLD>::seq_number_t::hopCount() const
{
  switch( state)
  {
    case Initial:
      return 0;
    case Steady:
    case Changing:
      return currentHC;
    default:
      assert( 0);	// something really bad happened
      return 0;
  }
}

template <class PLD>
void SHR<PLD>::seq_number_t::hopCount(
  unsigned int	newHC,
  bool		force,	// if true, then don't go through count
  bool		print)
{
  switch( state)
  {
    case Initial:
      currentHC = newHC;
      updateCtr = maxCounter;
      state = Steady;
      if( print) printf( "\n");
      break;
    case Steady:
      if( newHC != currentHC)
      {
	if( force == true || maxCounter < 2)		// single step, so don't use state Changing
	  currentHC = newHC;
	else
	{
	  --updateCtr;
	  pendingHC = newHC;
	  state = Changing;
	  if( print) printf( " start change");
	}
      }
      if( print) printf( "\n");
      break;
    case Changing:			// only happens if maxCounter >= 2
      if( force == true)
      {
	state = Steady;
	currentHC = newHC;
	updateCtr = maxCounter;
	if( print) printf( " forced\n");
      }
      else if( newHC == currentHC)
      {
	if( ++updateCtr == maxCounter)
	{
	  state = Steady;
	  if( print) printf(" back out of change\n");
	}
	else
	  if( print) printf(" reversing\n");
      }
      else if( newHC == pendingHC)
      {
	if( --updateCtr == 0)
	{
	  currentHC = newHC;
	  updateCtr = maxCounter;
	  state = Steady;
	  if( print) printf(" end change\n");
	}
	else
	  if( print) printf(" still changing\n");
      }
      else	// newHC is neither the old nor new HC
      {
	pendingHC = newHC;
	if( print) printf(" new HC during change\n");
      }
      break;
    default:
      assert( 0);	// something really bad happened
  }
  return;
}

template <class PLD>
void *SHR<PLD>::createBasicPkt()
{
  packet_t	*newPkt = packet_t::alloc();

  // type, ack_type, addresses set by caller
  newPkt->hdr.seq_number = 0xFFFFFFFF;
  // size set by caller
  newPkt->hdr.send_time = SimTime();
  newPkt->hdr.actual_hop = 1;
  newPkt->hdr.expected_hop = 0;
  newPkt->hdr.max_hop = 1;
  newPkt->hdr.delay = 0.0;
  newPkt->hdr.ackIndex = 0;
  newPkt->hdr.pktDelayIndex = 0;
  newPkt->hdr.canceled = false;
  newPkt->hdr.resend = 0;
  newPkt->hdr.suboptimal = false;
  newPkt->hdr.newSeqNumber = false;
  return newPkt;
}

/*
** There is no delay when the source sends an packet.
** This method isn't called when a packet is forwarded. Instead, the incoming
** packet is copied to make the outgoing packet.
*/
template <class PLD>
void *SHR<PLD>::createDataPkt(
  payload_t	&pld,
  ether_addr_t	dst,
  unsigned int	size)
{
  packet_t	*newPkt = (packet_t *) createBasicPkt();

  newPkt->hdr.type = DATA;
  newPkt->hdr.size = size + DATA_SIZE;
  newPkt->hdr.src_addr = MyEtherAddr;
  newPkt->hdr.dst_addr = dst;
  newPkt->hdr.cur_addr = MyEtherAddr;
  newPkt->hdr.pre_addr = MyEtherAddr;
  newPkt->hdr.newSeqNumber = true;
  newPkt->pld = pld;
  return newPkt;
}

template <class PLD>
void *SHR<PLD>::createRequestPkt(
  ether_addr_t	dst)
{
  packet_t	*newPkt = (packet_t *) createBasicPkt();

  newPkt->hdr.type = REQUEST;
  newPkt->hdr.size = REQUEST_SIZE;
  newPkt->hdr.expected_hop  =  1;
  newPkt->hdr.max_hop = TimeToLive;