spanagent.cc

ns-2 code for coverage and connectivity protocol for wireless sensor network

    drop(p, SPAN_DROP_RECEIVED);
    return;
  }

  // GX - If we got lots of packets, anounce to be coordinator

#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==SPAN)) 
  if (asleep() && _usespan && spanh->type == SPAN_DATA) {
    double now = NOW;
    _force_counter++;
    if (_force_counter > 5) {
      if (!is_coordinator() && _usespan) {
#if TRACE_ANNOUNCE > 0
        fprintf(stderr, "# %f: %d forced to announce\n", now, _my_id);
#endif
	announce_coordinator(true);
      }
    }
    if (_last_force == 0 || (now - _last_force) > 1) {
      _last_force = now;
      _force_counter = 0;
    }
  }
#endif

  switch(spanh->type) {
    case SPAN_DATA:
      forward_pkt(p);
      break;
    case SPAN_HELLO:
      process_span_hello(p);
      Packet::free(p);
      break;
    default:
      Packet::free(p);
      break;
  }
}

void 
SpanAgent::process_span_hdr(Packet *p)
{

#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR))
  if(cover_debug>2)
    fprintf(stderr,"# %f: %d process_span_hdr \n", NOW, _my_id);
#endif


  hdr_span *spanh =  (hdr_span*)p->access(_off_span);
  NeighborTable::Neighbor *n = _neighbors.search_neighbor(spanh->node_id);

  if (!spanh->is_coordinator && n && n->is_coordinator)
      _last_withdraw_seen = Scheduler::instance().clock();

  NeighborTable::Neighbor *new_n = new NeighborTable::Neighbor();
  new_n->id = spanh->node_id;
  new_n->x = spanh->x;
  new_n->y = spanh->y;
  new_n->nounce = spanh->nounce;
  new_n->is_coordinator = spanh->is_coordinator;
  new_n->coordinators = 0;

// #if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR)) 
//   if(n && !(n->is_coordinator) && spanh->is_coordinator){
//     node_intersecs(spanh->node_id);
//   }
// #endif

  if (_neighbors.update_neighbor(*new_n) < 0) {
    new_n->coordinators = 0;
    new_n->neighbors.clear();
    _neighbors.add_neighbor(new_n);
    n = new_n;
    // CLEAR: compute the intersections caused by the new neighbor
     // (node_intersecs(node_t *node,size_t index)
// #if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR)) 
//     if(new_n->is_coordinator)
//       node_intersecs(spanh->node_id);
// #endif

  } else
    delete new_n;

  if (spanh->is_coordinator){

#ifdef TWO_HOP_BEACON
    _neighbors.add_coordinator(_my_id, spanh->node_id,spanh->x,spanh->y, spanh->is_tentative);
#else
    _neighbors.add_coordinator(_my_id, spanh->node_id, spanh->is_tentative);
#endif
  }
  else
    _neighbors.remove_coordinator(_my_id, spanh->node_id);
}

void
SpanAgent::process_span_hello(Packet *p)
{

#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR))
  if(cover_debug>2)
    fprintf(stderr,"# %f: %d process_span_hello \n", NOW, _my_id);
#endif

  hdr_span *spanh =  (hdr_span*)p->access(_off_span);
  span_hello *hello =  (span_hello*)p->access(_off_span_hello);

  NeighborTable::Neighbor *n = _neighbors.search_neighbor(spanh->node_id);
  if (!n) {
    n = new NeighborTable::Neighbor();
    n->id = spanh->node_id;
    n->x = spanh->x;
    n->y = spanh->y;
    n->nounce = spanh->nounce;
    n->is_coordinator = spanh->is_coordinator;
    n->coordinators = 0;
    _neighbors.add_neighbor(n);

  }

  n->clear_coordinators();
  for (unsigned i=0; i<hello->ncoordinators; i++)

#ifdef TWO_HOP_BEACON
    n->add_coordinator(hello->coordinators[i],
                       hello->coordinators_pos[2*i],
                       hello->coordinators_pos[2*i+1],
                       false);
  if(cover_debug>2)
    fprintf(stderr,"# %f: %d process_span_hello: add coordinator done \n", NOW, _my_id);
#else
    n->add_coordinator(hello->coordinators[i], false);
#endif

  n->neighbors.clear();
  for (unsigned i=0; i<hello->nneighbors; i++) {
    n->neighbors.push_back(hello->neighbors[i]);
    if (spanh->is_coordinator)
#ifdef TWO_HOP_BEACON
      _neighbors.add_coordinator
	(hello->neighbors[i], spanh->node_id,spanh->x,spanh->y,spanh->is_tentative);

    if(cover_debug>2)
      fprintf(stderr,"# %f: %d process_span_hello: add coordinator to neighbors done \n ", NOW, _my_id);

#else
      _neighbors.add_coordinator
	(hello->neighbors[i], spanh->node_id, spanh->is_tentative);
#endif
  }

#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR)) 
  node_intersecs();
#endif

#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR))
  if(cover_debug>2)
    fprintf(stderr,"# %f: %d process_span_hello: done \n ", NOW, _my_id);
#endif

}

void
SpanAgent::add_span_hdr(Packet *p)
{

#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR))
  if(cover_debug>2)
    fprintf(stderr,"# %f: %d add_span_hdr \n", NOW, _my_id);
#endif

  hdr_span *spanh =  (hdr_span*)p->access(_off_span);
  spanh->is_coordinator = _is_coordinator;
  spanh->is_tentative = _is_tentative;
  double x, y, z;
  (God::instance()->nodelist[_my_id])->getLoc(&x, &y, &z);
  spanh->node_id = _my_id;
  spanh->x = (int)x;
  spanh->y = (int)y;
  spanh->nounce = (int)NOW;
}

void
SpanAgent::broadcast_hello()
{
#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR))
  if(cover_debug>2) 
    cerr<<"# "<<NOW<<": Node["<<_my_id<<"] is beaconing.."<<endl;
#endif

  NeighborTable::Neighbor *self = _neighbors.search_neighbor(_my_id);
  _neighbors.expire_old_entries(_my_id, SpanExpire);

  Packet *p = allocpkt();
  hdr_cmn *cmnh =  (hdr_cmn*)p->access(off_cmn_); 
  hdr_span *spanh =  (hdr_span*)p->access(_off_span);
  span_hello *hello =  (span_hello*)p->access(_off_span_hello);
  spanh->type = SPAN_HELLO; 

  unsigned i = 0;
  LLIterator *c_i = self->coord_iter();
  NeighborTable::Coordinator *c = (NeighborTable::Coordinator*) c_i->peek();
  while (c && i < MAX_SPAN_COORDINATORS) {
    if (!c->tentative) {
      hello->coordinators[i] = c->id;

#ifdef TWO_HOP_BEACON
      hello->coordinators_pos[2*i] = c->x;
      hello->coordinators_pos[2*i+1] = c->y;
#endif

      i++;
    }
    c = (NeighborTable::Coordinator*)c_i->next();
  }
  delete c_i;
  hello->ncoordinators = i;

  i = 0;
  LLIterator *n_i = _neighbors.neighbors();
  NeighborTable::Neighbor *n = (NeighborTable::Neighbor*) n_i->peek();
  while(n && i < MAX_SPAN_NEIGHBORS) {
    hello->neighbors[i] = n->id;
    i++;
    n = (NeighborTable::Neighbor*)n_i->next();
  }
  delete n_i;
  hello->nneighbors = i;

  cmnh->next_hop_ = MAC_BROADCAST;
  cmnh->size() = spanh->size() + hello->size();
  hdr_ip *iph =  (hdr_ip*)p->access(off_ip_);
  iph->dst() = IP_BROADCAST;
  iph->src() = _my_id;

  add_span_hdr(p);
  process_span_hello(p); // this keeps self->neighbors[] in sync
  send_packet(p, false);
  
  double x, y, z;
  (God::instance()->nodelist[_my_id])->getLoc(&x, &y, &z);
  self->x = (int)x;
  self->y = (int)y;
  self->nounce = (int)NOW;

  _last_bcast = NOW;

#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR))
  if(cover_debug>2) 
    cerr<<"# "<<NOW<<": Node["<<_my_id<<"] beacon done.."<<endl;
#endif

}

  
void
SpanAgent::sleep()
{
  assert(!_is_coordinator);
  _asleep = true;
  if (_usepsm)
    _mobile_node->PowerSave(0, true);
} 

void
SpanAgent::wakeup()
{
#ifndef ALL_SLEEP
 
 _asleep = false;
  if (_usepsm)
    _mobile_node->PowerSave(0, false);

#endif

}

void
SpanAgent::update_location()
{ 

 double x, y, z; 
  (God::instance()->nodelist[_my_id])->getLoc(&x, &y, &z); 
  NeighborTable::Neighbor *self = _neighbors.search_neighbor(_my_id);
  self->x = (int)x;
  self->y = (int)y;
  self->nounce = (int)Scheduler::instance().clock();

#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR)) 
  self_.id = _my_id;
  self_.x = (int)self->x;
  self_.y = (int)self->y;
#endif
}

void
SpanEventHandler::handle(Event *e)
{

#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR))
  if(cover_debug>2)
    fprintf(stderr,"# %f: %d handle \n", NOW, _agent->id());
#endif

  double now = Scheduler::instance().clock();
  if (_agent->active()) {
    bool should_broadcast = false;
    double since_withdraw = now - _last_withdraw;
    double since_broadcast = now - _last_broadcast;
    
    _agent->update_location();
   
    if (since_broadcast >= SpanBcast)
      should_broadcast = true; 
 
    if (_agent->id() > _agent->_srcsink) {
      // after withdraw, stay up for a couple of seconds to forward packets
      if (!_agent->is_coordinator() && (since_withdraw >= 2)) {
        if (!_agent->asleep()) 
	  _agent->sleep();
      }
 
      if (!_agent->is_coordinator() && _last_announce_check < now &&
	  (now - _last_announce_check >= SpanAnnounceCheck)) {

        double delay = _agent->check_announce_handler();
        _last_announce_check = now;
        _last_withdraw_check = now + delay + jitter(2);

      }
      else if (_agent->is_coordinator() && _last_withdraw_check < now &&
             (now - _last_withdraw_check >= SpanWithdrawCheck)) {

        should_broadcast |= _agent->check_withdraw_handler();
        _last_withdraw_check = now;
        if (!_agent->is_coordinator()) { // withdrawn
          _last_withdraw = now;
          int n = _agent->_neighbors.nneighbors();
          _last_announce_check = now + n; // give others a chance to announce
        }

      }
    }
    else if (_agent->asleep()) { // src/sink always awake in experiments
      _agent->wakeup();
      fprintf(stderr, "# %d src/sink\n", _agent->id());
    }

    if (should_broadcast) {
      _agent->broadcast_hello();
      _last_broadcast = now;
    }
    Scheduler::instance().schedule(this,e,0.1);

  } else {
    _agent->force_withdraw();
    _agent->broadcast_hello();
#if TRACE_ANNOUNCE > 0
    fprintf(stderr,"# %f: %d out of energy:%f\n", now, _agent->id(),_agent->energy());
#endif
  }
} 

double
SpanAgent::check_announce_handler()
{
  if (is_coordinator() || (_usespan && !active()))
    return 0;

  if (!_announce_pending) {
    int c;

#if((PROTOCOL==SPAN_CLEAR))
 
    double Ucover=0,Uspan=0;
    if (_usespan && (((c = check_announce()) > 0) || ((Ucover = coverage_contrib(RANDOM))>0))) {
      //      if (cover) c = cover;
      int n = _neighbors.nneighbors();

      Ucover = Ucover>0 ? Ucover : 0;

      double U = Ucover;

      // Use span's delay when it is larger than zero
      if(c>0){

        Uspan = (n == 1) ? 1 : (1-(((double)c)/(double)(n*(n-1)*0.5)));
        
        if (Uspan < 0) Uspan = 0;
        if (Uspan > 1) Uspan = 1;
        U = Uspan;
      }

#elif(PROTOCOL==CLEAR)

    double U;
    if (_usespan && ((U = coverage_contrib(RANDOM))>0)) {
      int n = _neighbors.nneighbors();

#else

    if (_usespan && (c = check_announce()) > 0) {
      int n = _neighbors.nneighbors();
      double U = (n == 1) ? 1 : (1-(((double)c)/(double)(n*(n-1)*0.5)));

      if (U < 0) U = 0;
      if (U > 1) U = 1;
 
#endif

      double fe = 1-_energy_model->energy() / initial_energy_; //_energy_model->initialenergy();

      double R = jitter(1);
      int slot = (int)(n*(fe+U+R));
      double delay = slot * 0.4; // 400 ms propagation delay

      // compensate so everyone starts competing at the same time
      double now = Scheduler::instance().clock();
      if ((now-_last_withdraw_seen) < SpanAnnounceCheck) {
        double jj = _last_withdraw_seen+SpanAnnounceCheck-now;
        delay += jj;
      }

#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR)) 

      if(cover_debug)
        fprintf(stderr,
                "# %f: Node[%d] announce delay is %f \n",
                NOW,self_.id,delay);

#endif

#if TRACE_ANNOUNCE > 1
      fprintf(stderr,"# %d: d=%3.3f (s %d n %d c %d fe %3.3f e %5.1f U %f)\n", 
              id(), delay, slot, n, c, fe, _energy_model->energy(), U);
#endif
      _announce_pending = true; 
      Event *ev = new Event; 
      Scheduler::instance().schedule 
        (&_announce_coordinator_handler, ev, delay); 
      return delay;
    } 
    else if (!_usespan) {
      _announce_pending = true; 
      Event *ev = new Event; 
      Scheduler::instance().schedule (&_announce_coordinator_handler, ev, 0); 
      return 0;
    }
  }
  return 0;
}

int
SpanAgent::check_announce()
{
  if (_my_id <= _srcsink)
    return 0;

  int nn = 0;
  LLIterator *ni = _neighbors.neighbors();
  NeighborTable::Neighbor *n = (NeighborTable::Neighbor*)ni->peek();
  while(n) {
    LLIterator *ni2 = _neighbors.neighbors();
    NeighborTable::Neighbor *n2 = (NeighborTable::Neighbor*)ni2->peek();
    while (n2) {
      if (n2->id > n->id) {
        int j = 0;
	if ((j = _neighbors.share_coordinator(n2->id, n->id, -1)) < 0) {
#if TRACE_ANNOUNCE > 2
	  fprintf(stderr,"## %d: %d %d share %d (%f)\n",
	          _my_id, n2->id, n->id, j, Scheduler::instance().clock());
#endif
	  nn++; 
	}
      }
      n2 = (NeighborTable::Neighbor*)ni2->next();
    }
    delete ni2;
    n = (NeighborTable::Neighbor*)ni->next();
  }
  delete ni;
  return nn;
}

// returns true if a broadcast msg should be sent afterward
bool
SpanAgent::check_withdraw_handler()
{
  // if everyone has low amount of energy relative to initialenergy,
  // we may get into a case where everyone uses WindowMin, that's why
  // we should make sure WindowMin is decently big enough to not cause
  // to much unstability

#if((PROTOCOL==SPAN_CLEAR))

  if (withdraw_pending_)
    return false;

#elif(PROTOCOL==CLEAR)

  if (withdraw_pending_)
    return false;
  
  if (!check_coverage()) {
    withdraw_coordinator();
    return true;
  }
  return false; 
#endif

  double fe = _energy_model->energy() / initial_energy_ ;//_energy_model->initialenergy();
  unsigned window = (unsigned)(SpanCoordinatorWindow*fe);
  if (window < SpanCoordinatorWindowMin)
    window = (unsigned)SpanCoordinatorWindowMin;

  if (!_usespan)
    return false;

  _withdraw_meter++;

  if (!active() || check_withdraw(false) ) {
//     if(cover_debug)
//       fprintf(stderr,"# %d checked coverage in with__draw handler\n", _my_id);

    _withdraw_meter = 0;
    _is_tentative = false;
    withdraw_coordinator();
    return true;
  }

#if ROTATE_COORDINATORS
  else if (_withdraw_meter >= window) {
    if (check_withdraw(true)) {
      // GX-if we can withdraw
      if (!_is_tentative) {
        _is_tentative = true;
#if TRACE_ANNOUNCE > 1
        fprintf(stderr, "# %f: %d coordinator is tentative\n", NOW, _my_id);
#endif
	return true;
      }
      unsigned n = _neighbors.nneighbors() + 1;
      if (_withdraw_meter >= window+n) {
	// nobody else elected
        _withdraw_meter = 0;