ntable.cc

CBRP协议（移动adhoc中基于分簇的路由协议）ns2下的源码

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <random.h>
#include "cbrpagent.h"

int CBRP_Agent::no_of_clusters_;  /*This is a variable shared by all CBRPAgents
                                    and is used to keep track how many cluster heads
                                    have been created */

// Returns a random number between 0 and max, implemented by dmaltz
static inline double
jitter (double max, int be_random_)
{
  return (be_random_ ? Random::uniform(max) : 0);
}

NeighborTablePeriodicHandler::NeighborTablePeriodicHandler(CBRP_Agent *a_, NeighborTable *t_) 
{
  a = a_;
  t = t_;
}

Packet *
NeighborTable::getBroadcastPacket() {

  //periodically broadcast my own neighbor table to my neighbors
  double b_time = 1.1 * BROADCAST_INTEVAL;
  Packet *p = a->allocpkt();

  hdr_cbrp *cbrph =  (hdr_cbrp*)p->access(a->off_cbrp_);
  hdr_ip *iph = (hdr_ip *) p->access (a->off_ip_);
  hdr_cmn *hdrc = HDR_CMN (p);

  ntable_ent *prte;

  unsigned char *walk;
  unsigned char *count_pos;
  unsigned char *n_count_pos;
  
  int adj_count;
  int count;

  double now = Scheduler::instance().clock();



  cbrph->valid()= 0;   // we set the cbrph->valid_ to 0 to indicate it's a broadcast pkt
  hdrc->ptype() = PT_MESSAGE;

  hdrc->next_hop_ = MAC_BROADCAST;
  hdrc->addr_type_ = AF_INET;

  iph->dst_ = IP_BROADCAST;
  iph->dport_ = ROUTER_PORT;
  iph->src() = a->myaddr_;

  if (my_status == CLUSTER_HEAD) {
    adj_count = 0;
  }else {
    adj_count = adjtable_size;
  }

  assert((my_size+adj_count)<= (1500 / 12));

  p->allocdata((MAX_NODE_NUM * 2) + (adj_count * 1) + 3);

  walk = p->accessdata ();
  *(walk++) = my_status;
  n_count_pos = walk++;
  count_pos = walk++;
  *(count_pos) = adj_count;
 
  count = 0;
  for (InitLoop ();
       (prte = NextLoop ()); )
    {

        if ((prte->neighbor<=0 )||(prte->neighbor> MAX_NODE_NUM)){
          abort();
        }
        if ((now - prte->last_update)< b_time) {
          *(walk++) = prte->neighbor; 
          *(walk++) = prte->neighbor_status;
          count++;
        }
    }
  *(n_count_pos) = count;
  
  if (!adj_count) {
    *(count_pos) = 0;
  } else { 
    adjtable_ent *padj = adjtable_1;
    nsaddr_t dest;
    adj_count = 0;

    while (padj) {
      dest = padj->neighbor_cluster;
      assert((dest>0) && (dest<= MAX_NODE_NUM));
      if (!GetEntry(dest)) {
        *(walk++) = dest;
        adj_count++;
      }
      padj = padj->next;
    } 

    assert(adj_count <= adjtable_size);
    *(count_pos) = adj_count; 
  }
//  hdrc->size_ = count * 2 + adj_count * 1 + 20 + 3;
  hdrc->size_ = count * 4 + adj_count*4 + 5; //size of the broadcast packet
  return p;
}



void 
NeighborTablePeriodicHandler::handle(Event *event) {

  Packet *p;
  Scheduler & s = Scheduler::instance();
  p = t->getBroadcastPacket();
  
  //send out the broadcast packet. i.e. schedule it
  s.schedule (a->ll, p, jitter(CBRP_BROADCAST_JITTER, a->be_random_));
  //schedule the next broadcast event
  s.schedule (this, event, BROADCAST_INTEVAL * (0.75 + jitter (0.25, a->be_random_)));

}


NeighborTableTimeoutHandler::NeighborTableTimeoutHandler(CBRP_Agent *a_, NeighborTable *t_) 
{
  a = a_;
  t = t_;
}

int 
NeighborTableTimeoutHandler::checkAdjTimeout(Event *event, int primary) {

  //check if adjtable caused the timeout
  adjtable_ent *p;
  adjtable_ent *p_prev=NULL;
  nexthop_ent *phop = NULL;
  nexthop_ent *phop_prev = NULL;

 //if I am cluster head,then I have to delete from Redundant cluster adj entries
  if (primary) {
    p = t->adjtable_1;
  }else{
    p = t->adjtable_2;
  }

  while (p) {

    //double loop
    phop = p->next_hop;
    phop_prev = NULL;

    while (phop) {

      if (phop->timeout_event == event) {

        if (phop_prev) {
          phop_prev->next = phop->next;
        }else {
          p->next_hop = phop->next;
        }

        if (!p->next_hop) {
          if (p_prev) {
            p_prev->next = p->next;
            delete p;
          }else {
            if (primary) {
              t->adjtable_1 = p->next;
            }else {
              t->adjtable_2 = p->next;
            }
            delete p;
          }
          
          if (primary) {
            t->adjtable_size--;
          }
        }
        phop->timeout_event = NULL;
        delete phop;
        return 1;
      }   
        
      phop_prev = phop;
      phop = phop->next;
    }

    p_prev = p;
    p = p->next;
  }
  return 0;
}

void
NeighborTableTimeoutHandler::handle(Event *event) {

  ntable_ent *prte;
  int deleted=0;

  //check out the entry that caused this timeout event
  for (t->InitLoop(); (prte = t->NextLoop());) {
    if (prte->timeout_event == event) {
      prte->timeout_event = NULL;
      t->DeleteEntry(prte->neighbor);
      delete event;
      deleted++ ;
      if (deleted>1) {
        printf("duplicated!\n");
      }

    }
  }
  if (deleted) {
     return;
  }
  if (checkAdjTimeout(event,1) || checkAdjTimeout(event,0)) {
     delete event;
     return;
  }

}

NeighborTableCFormationHandler::NeighborTableCFormationHandler(CBRP_Agent *a_, NeighborTable *t_)
{
  a = a_;
  t = t_;
}

void
NeighborTableCFormationHandler::handle(Event *event) {

  //check if the no_of_clusterheads is really 0
  if (t->my_status != CLUSTER_UNDECIDED && !t->no_of_clusterheads) {
    return; 
  } 
 
  //if I'm the lowest ID among the undecided, then I proclaim myself clusterhead
  int min_addr = a->myaddr_;
  ntable_ent *tmp = t->head;

  //solution #1 check for min. ID

  while (tmp) {

    if ((tmp->neighbor_status == CLUSTER_UNDECIDED) && 
        (tmp->link_status == LINK_BIDIRECTIONAL) && 
        (tmp->neighbor < min_addr))
      {
       min_addr = tmp->neighbor;
      }

    tmp = tmp->next;
  
  }

  Scheduler & s = Scheduler::instance();

  if (min_addr == a->myaddr_) {

    t->my_status = CLUSTER_HEAD;
    //increase the total number of clusters by 1
    
    CBRP_Agent::no_of_clusters_++;
    a->trace("SUM CLUSTERS %.5f %d",s.clock(), CBRP_Agent::no_of_clusters_);
   

    Packet *p;

    p = t->getBroadcastPacket();
      
    //send out the packet immediately
    s.schedule(a->ll, p, 0);

  }else {

    s.schedule(this, event, BROADCAST_INTEVAL);
  }
  //Jinyang: solution #2, dun check for min. ID  
}

NeighborTableCContentionHandler::NeighborTableCContentionHandler(CBRP_Agent *a_, NeighborTable *t_)
{
  a = a_;
  t = t_;
} 

void
NeighborTableCContentionHandler::handle(Event *event)
{

  if (t->my_status != CLUSTER_HEAD) {
     t->in_contention = 0;
     return;
  }

  ntable_ent *ent;
  ent = t->head;
  Packet *p;
  Scheduler & s = Scheduler::instance();

  while (ent) {
    if (ent->neighbor_status == CLUSTER_HEAD) {
      if (a->myaddr_ < ent->neighbor) {
         // I insist my position as cluster head
         ent->neighbor_status = CLUSTER_UNDECIDED;
         t->no_of_clusterheads = 0;
      }else {
         // I declide my position as cluster head
         s.cancel(t->periodic_event);
         s.schedule(t->periodic_handler,t->periodic_event,BROADCAST_INTEVAL);

         t->my_status = CLUSTER_MEMBER;

         CBRP_Agent::no_of_clusters_--;
         a->trace("SUM CLUSTERS %.5f %d",s.clock(), CBRP_Agent::no_of_clusters_);

      }
    }
    ent = ent->next;
   }

   p = t->getBroadcastPacket();
   s.schedule(a->ll, p, 0);
   t->in_contention = 0;

}       

NeighborTable::NeighborTable(CBRP_Agent *a_) {

  //initialize linked list
  head = NULL;
  my_size = 0;

  adjtable = new nextnode[MAX_NODE_NUM];
  for (int i=0;i<MAX_NODE_NUM;i++) {
    adjtable[i].the_node = 0;
    adjtable[i].last_updated = -BROADCAST_INTEVAL;
  }

  last_update = new double[MAX_NODE_NUM];
  for (int i=0;i<MAX_NODE_NUM;i++) {
    last_update[i] = 0.0;  //the last updated time
  }
  adjtable_1 = NULL;
  adjtable_size = 0;
  adjtable_2 = NULL;

  no_of_clusterheads = 0;
  in_contention = 0;
  my_status = CLUSTER_UNDECIDED;
  a = a_;

  c_form_event = new Event();
  periodic_event = new Event();
  c_contention_event = new Event();

  c_formation_handler = new NeighborTableCFormationHandler(a, this);
  periodic_handler = new NeighborTablePeriodicHandler(a, this);
  timeout_handler = new NeighborTableTimeoutHandler(a, this);
  c_contention_handler = new NeighborTableCContentionHandler(a,this);

}

void
NeighborTable::startUp() {

  //kick off peridic events
  Scheduler & s = Scheduler::instance();

  s.schedule (periodic_handler, 
              periodic_event, jitter(CBRP_STARTUP_JITTER, a->be_random_));
 
  //kick off cluster formation event
  s.schedule(c_formation_handler,c_form_event,2*BROADCAST_INTEVAL);
}

void 
NeighborTable::InitLoop() {
  
  prev = NULL;
  now = NULL;
}

ntable_ent *
NeighborTable::NextLoop() {

  prev = now;
  
  if (!now) {
    now = head;
  }else {
    now = now->next;
  }
  return now;
}

int
NeighborTable::DeleteEntry(nsaddr_t dest) {

  ntable_ent *tmp;
  ntable_ent *tmp_prev;

  Scheduler & s = Scheduler::instance();

  //check if the entry to be deleted is the current entry
  if (now && (now->neighbor == dest)) {
    
    tmp = now;
    tmp_prev = prev;
  
  }else {

    tmp = head;
    tmp_prev = NULL;

    while (tmp && (tmp->neighbor != dest)) {
      tmp_prev = tmp;
      tmp = tmp->next;
    }
  
  } 

  if (tmp) {
    
    //check if the no_of_clusterheads I belong to has decreased
    assert(tmp->neighbor == dest);
    if ((tmp->neighbor_status == CLUSTER_HEAD) && 
        (tmp->link_status == LINK_BIDIRECTIONAL)) {
     
      no_of_clusterheads--;
      //check if the no_of_clusterheads has decreased to zero
      if ((!no_of_clusterheads)&&(my_status == CLUSTER_MEMBER)) {
        lostClusterHeads();
      }
    }

    //delete the entry

    if (tmp_prev) {
      tmp_prev->next = tmp->next;
    }else {
      head = tmp->next;
    }
    my_size--;
   
    if (tmp->n_pkt) {
      Packet::free(tmp->n_pkt);
    }
    tmp->n_pkt = NULL;

    //see if any entries in adjtable_1 need to be deleted
    DeleteAdjEntry(dest,1);

    for (int i=0;i<MAX_NODE_NUM;i++) {
      if (adjtable[i].the_node == dest) {
        if (adjtable[i].dest_status == CLUSTER_HEAD) { //there may be redundancies in adjtable_1
          adjtable_ent *ent = GetAdjEntry(i+1,1);
          if (ent) { 
            adjtable[i].the_node= ent->next_hop->next_node;
            adjtable[i].last_updated = Scheduler::instance().clock();
          }else {
            adjtable[i].the_node= 0;
          }
        }else {
          adjtable[i].the_node= 0;
        }
      }
    }
            
    DeleteAdjEntry(dest,0);
    if (tmp->timeout_event) {
      s.cancel(tmp->timeout_event);
    } 
    tmp->timeout_event = NULL;
    tmp->next = NULL;
    delete tmp;
  
  }else {
    return 0;
  }

  return 1;
}

void 
NeighborTable::lostClusterHeads() {

  nsaddr_t min_addr= a->myaddr_;
  ntable_ent *prte;

  assert((my_status == CLUSTER_MEMBER) && (no_of_clusterheads == 0));

  for (InitLoop ();
      (prte = NextLoop ()); ) {
     
    if ((prte->link_status == LINK_BIDIRECTIONAL) && 
        (prte->neighbor < min_addr)) {
      min_addr = prte->neighbor;
    }
    
  }

  if (min_addr == a->myaddr_) {
    my_status = CLUSTER_HEAD;

    CBRP_Agent::no_of_clusters_++;
    a->trace("SUM CLUSTERS %.5f %d",Scheduler::instance().clock(), CBRP_Agent::no_of_clusters_);


  }else {     

    my_status = CLUSTER_UNDECIDED;
    Scheduler::instance().schedule(c_formation_handler,c_form_event,1.1*BROADCAST_INTEVAL);

  }

}

  
ntable_ent *
NeighborTable::GetEntry(nsaddr_t dest) {

  ntable_ent *ent;