spanagent.cc

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

#include "hdr_span.h"
#include "spanagent.hh"
#include "gfrt.hh"

#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR)) 
#include "coverage.h"
#endif
 
#define StaticAssert(c) switch (c) case 0: case (c):
#define NOW (Scheduler::instance().clock())
#define TRACE_ANNOUNCE      1

#if(PROTOCOL==CLEAR)
#define ROTATE_COORDINATORS 0
#else
#define ROTATE_COORDINATORS 0
#endif
 
double SpanBcast = 3;

#if((PROTOCOL==SPAN_CLEAR) || (PROTOCOL==CLEAR)) 
//double SpanExpire = 4.5 * SpanBcast;
double SpanExpire = 2.5 * SpanBcast;
double Tw = 4 * SpanBcast;
#else
double SpanExpire = 4.5 * SpanBcast;
#endif

double SpanAnnounceCheck = SpanBcast/3;
double SpanWithdrawCheck = SpanBcast/3;
double SpanCoordinatorWindow = 60/SpanWithdrawCheck;
double SpanCoordinatorWindowMin = 30/SpanWithdrawCheck;


static inline double
jitter (double max)
{ 
  return Random::uniform(max);
}

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

// A couple of helper functions for the geometric calculations
double dist_square(pos_t* source,pos_t* dist)
{
  return (source->x-dist->x)*(source->x-dist->x) + (source->y-dist->y)*(source->y-dist->y);
}

// check if the point falls on or within the circle centering at 'center'
bool within_circle(pos_t* point,pos_t* center,double radius)
{
  return dist_square(point,center) <= radius*radius;

}

// Check if the node is within our 'coverage neighbor distance'
int
SpanAgent::is_sensing_neighbor(pos_t *node,pos_t*self)
{

  //if(cover_debug)
    //    cerr<<"is_sensing_neighbor<"<<node->id<<"("<<node->x<<","<<node->y<<"),"
    //    <<self->id<<"("<<self->x<<","<<self->y<<")>"<<endl;

  return within_circle(node,self,2*Rs);
}

//check two circle is intersected or not
int is_intersected(node_t *node1, node_t *node2)
{
  double dist;
  pos_t node1_pos,node2_pos;
  node1_pos.x = node1->x;
  node1_pos.y = node1->y;
  node2_pos.x = node2->x;
  node2_pos.y = node2->y;
  
  dist = dist_square(&node1_pos, &node2_pos);
  if (dist >= 4*Rs*Rs)
    return 0;
  else
    return 1;
}

int circle_intersection(intersec_t* sec1,intersec_t* sec2,node_t *n1, node_t *n2) 
{
	double a, b, c;
	double x_square, y_square;
	double tmp2, tmp3, tmp4,tmp5;
        pos_t node1_pos,node2_pos;
        node1_pos.x = n1->x;
        node1_pos.y = n1->y;
        node2_pos.x = n2->x;
        node2_pos.y = n2->y;

	sec1->node1 = n1->id;
	sec1->node2 = n2->id;
        sec2->node1 = n1->id;
	sec2->node2 = n2->id;

        //   if(cover_debug)
        //           cerr<<"circle_intersection ["<<n1->id<<","<<n2->id<<"]: ";

	if (!is_intersected(n1, n2)) {
		sec1->y = -1;
		sec1->x = -1;
		sec2->y = -1;
		sec2->x = -1;

                //       if(cover_debug)
                //                   cerr<<"No sec...."<<endl;

		return 0;
	}
        if (node1_pos.x!=node2_pos.x) {

          y_square = (node1_pos.y - node2_pos.y)*(node1_pos.y - node2_pos.y);
          x_square = (node1_pos.x - node2_pos.x)*(node1_pos.x - node2_pos.x);
          a = y_square+x_square;

          tmp2 = node2_pos.y*node2_pos.y - node1_pos.y*node1_pos.y;
          b = (node1_pos.y - node2_pos.y) * (tmp2 + x_square) - 2*node1_pos.y*x_square;
          c = (tmp2+x_square)*(tmp2+x_square)/4 + node1_pos.y*node1_pos.y*x_square-Rs*Rs*x_square;
          tmp3 = sqrt(b*b - 4*a*c);
          sec1->y = (-b + tmp3)/(2*a);
          sec2->y = (-b - tmp3)/(2*a);
          tmp4 = 
            node2_pos.y*node2_pos.y - node1_pos.y*node1_pos.y + node2_pos.x*node2_pos.x - node1_pos.x*node1_pos.x;
          sec1->x = (2*(node1_pos.y - node2_pos.y)*(sec1->y) + tmp4)/(2*node2_pos.x-2*node1_pos.x);
          sec2->x = (2*(node1_pos.y - node2_pos.y)*(sec2->y) + tmp4)/(2*node2_pos.x-2*node1_pos.x);
        }
        else{
          sec1->y = (node1_pos.y + node2_pos.y)/2;
          sec2->y = (node1_pos.y + node2_pos.y)/2;
          tmp5= Rs*Rs-(node2_pos.y-node1_pos.y)*(node2_pos.y-node1_pos.y)/4;
          sec1->x = node1_pos.x+ sqrt(tmp5);
          sec2->x = node1_pos.x- sqrt(tmp5);
        }

        if (sec1->y > SideLen || sec1->y < 0) {sec1->y = -1;return 0;}
        if (sec1->x > SideLen || sec1->x < 0) {sec1->x = -1;return 0;}
	if (sec2->y > SideLen || sec2->y < 0) {sec2->y = -1;return 0;}
	if (sec2->x > SideLen || sec2->x < 0) {sec2->x = -1;return 0;}

        //         if(cover_debug)
        //           cerr<<"(" <<sec1->x<<","<<sec1->y<<" | "<<sec2->x<<","<<sec2->y<<")"<<endl;

	return 1;
}

int SpanAgent::bound_intersecs(node_t *node){

  intersec_t sec;
  double x=0,y=0,x1=0,x2=0,y1=0,y2=0;

  sec.node1 = node->id;
  sec.node2 = node->id;

  pos_t self_pos;
  (God::instance()->nodelist[_my_id])->getLoc(&self_pos.x, &self_pos.y, &self_pos.z);

  // intersects with Y axis?
  sec.y = 0;
  if((node->y > 0 ) && (node->y < Rs)) {
    x = sqrt((Rs*Rs - node->y*node->y));
    x1 = node->x + x;
    x2 = node->x - x;

    sec.x = x1;
    if(x1>0 && x1<SideLen
       &&within_circle((pos_t*)&sec,&self_pos,Rs)){
      intersecs_.push_back(sec);
    }

    sec.x = x2;
    if(x2>0 && x2<SideLen
       &&within_circle((pos_t*)&sec,&self_pos,Rs)){
      intersecs_.push_back(sec);
    }
  }

  x1=0;
  x2=0;
  y1=0;
  y2=0;

  sec.y = SideLen;
  if(((node->y > (SideLen-Rs))) && (node->y < SideLen)) {
    x = sqrt(Rs*Rs - (SideLen-node->y)*(SideLen-node->y));
    x1 = node->x + x;
    x2 = node->x - x;

    sec.x = x1;
    if(x1>0 && x1<SideLen
       &&within_circle((pos_t*)&sec,&self_pos,Rs)){
      intersecs_.push_back(sec);
    }
    
    sec.x = x2;
    if(x2>0 && x2<SideLen
       &&within_circle((pos_t*)&sec,&self_pos,Rs)){
      intersecs_.push_back(sec);
    }
  }

  // intersects with X axis?
  x1=0;
  x2=0;
  y1=0;
  y2=0;

  sec.x = 0;
  if(node->x > 0 && node->x < Rs){
    y = sqrt(Rs*Rs - node->x*node->x);
    y1 = node->y + y;
    y2 = node->y - y;

    sec.y = y1;
    if(y1>0 && y1<SideLen
       &&within_circle((pos_t*)&sec,&self_pos,Rs)){
      intersecs_.push_back(sec);
    }

    sec.y = y2;
    if(y2>0 && y2<SideLen
       &&within_circle((pos_t*)&sec,&self_pos,Rs)){
      intersecs_.push_back(sec);
    }
  }
  
  x1=0;
  x2=0;
  y1=0;
  y2=0;

  sec.x = SideLen;
  if(node->x > (SideLen-Rs)){
    y = sqrt(Rs*Rs - (SideLen-node->x)*(SideLen-node->x));
    y1 = node->y + y;
    y2 = node->y - y;

    sec.y = y1;
    if(y1>0 && y1<SideLen
       &&within_circle((pos_t*)&sec,&self_pos,Rs)){
       intersecs_.push_back(sec);
    }

    sec.y = y2;
    if(y2>0 && y2<SideLen
       &&within_circle((pos_t*)&sec,&self_pos,Rs)){
      intersecs_.push_back(sec);
    }
  }

  return 0;
}

int SpanAgent::node_intersecs(){

  if(cover_debug>2)
    fprintf(stderr,"# %f: %d node_intersecs - enter\n ", NOW, _my_id);

  LLIterator *ni = _neighbors.neighbors();
  NeighborTable::Neighbor *neibor = (NeighborTable::Neighbor*)ni->peek();

  pos_t self_pos;
  (God::instance()->nodelist[_my_id])->getLoc(&self_pos.x, &self_pos.y, &self_pos.z);

  //Clear the intersection set
  intersecs_.clear();
  coordinators_.clear();

  //Put all coordinators within one or two hops into a vector
  while(neibor){

    if(cover_debug) 
      fprintf(stderr,"# %f: %d node_intersecs - got coordinators: ", NOW, _my_id);

#ifdef TWO_HOP_BEACON
    LLIterator *ci = neibor->coord_iter();
    NeighborTable::Coordinator *coordinator;
    coordinator = (NeighborTable::Coordinator *)ci->peek();
    
    for(;coordinator;coordinator=(NeighborTable::Coordinator *)ci->next()){

      pos_t pos;
      pos.x=coordinator->x;
      pos.y=coordinator->y;

      if((coordinator->id==_my_id) || !is_sensing_neighbor(&self_pos,&pos))
        continue;

      // Is the coordinator already in our list?
      vector<node_t>::iterator iter;
      for(iter=coordinators_.begin();iter!=coordinators_.end();iter++){
        if(iter->id == coordinator->id)
          break;
      }

      if(iter==coordinators_.end()){
        node_t node;
        node.x = coordinator->x;
        node.y = coordinator->y;
        node.id = coordinator->id;
        coordinators_.push_back(node);
      }
   
    }

    delete ci;

#else
    if(neibor->id!=_my_id && neibor->is_coordinator){
      node_t coordinator;
      coordinator.x = neibor->x;
      coordinator.y = neibor->y;
      coordinator.id = neibor->id;
      coordinators_.push_back(coordinator);
    }
#endif

    neibor=(NeighborTable::Neighbor*)ni->next();
  }

  delete ni;

  if(cover_debug)
    fprintf(stderr,"# %f: %d node_intersecs - got coordinators: ", NOW, _my_id);

  // Calculate the intersections of all coordinators
  for(size_t i=0;i<coordinators_.size();i++){

    node_t *coor_i = &coordinators_[i];

    if(cover_debug){
      pos_t pos;
      pos.x = coor_i->x;
      pos.y = coor_i->y;
      fprintf(stderr,"[%d (%d,%d)]*%f* ",
              coor_i->id,coor_i->x,coor_i->y,
              sqrt(dist_square(&self_pos,&pos)));
    }

    //calculate the intersections with bounds of network
    bound_intersecs(coor_i);

    for(size_t j=i+1;j<coordinators_.size();j++){

      intersec_t sec1,sec2;
      node_t *coor_j = &coordinators_[j];

      circle_intersection(&sec1,&sec2,coor_i,coor_j);

      if(sec1.x>0 && sec1.x<=SideLen && sec1.y>0 && sec1.y<=SideLen 
         && within_circle((pos_t*)&sec1,&self_pos,Rs))
        intersecs_.push_back(sec1);

      if(sec2.x>0 && sec2.x<=SideLen && sec2.y>0 && sec2.y<=SideLen 
         && within_circle((pos_t*)&sec2,&self_pos,Rs))
        intersecs_.push_back(sec2);
    }
  }

  if(cover_debug)
    fprintf(stderr,"\n");
  
  if(cover_debug>2)
    fprintf(stderr,"# %f: %d node_intersecs - leave\n ", NOW, _my_id);

  return 0;
}

int SpanAgent::check_coverage(){
 
  pos_t pos,self_pos,neibor_pos;
  bool covered;

  if(!intersecs_.size())
    return 1;

  (God::instance()->nodelist[_my_id])->getLoc(&self_pos.x, &self_pos.y, &self_pos.z);

  if(cover_debug>1)
  //if(_my_id==49 || _my_id==170 ||_my_id==31 ||_my_id==112 ||_my_id==94 ||_my_id==176)
    fprintf(stderr,"# %f: %d check_coverage - ", NOW, self_.id);

  vector<intersec_t>::iterator iter=intersecs_.begin();
  while(iter!=intersecs_.end()){

    pos.x = iter->x;
    pos.y = iter->y;
    iter->msr = 0;

    covered = 0;

    if(cover_debug>1)
    //if(_my_id==49 || _my_id==170 ||_my_id==31 ||_my_id==112 ||_my_id==94 ||_my_id==176)
      cerr<<"["<<iter->node1<<","<<iter->node2<<"]("<<pos.x<<","<<pos.y<<") ";
 
    for( size_t i=0;i<coordinators_.size();i++){

      node_t *neibor=&coordinators_[i];
      neibor_pos.x = neibor->x;
      neibor_pos.y = neibor->y;
      
      if((neibor->id!=iter->node1) && (neibor->id!=iter->node2)){
          // The intersection point is within a node
          if(within_circle(&pos,&neibor_pos,Rs)){
            if((++iter->msr) >= MSR){

              if(cover_debug>1)
              //if(_my_id==49 || _my_id==170 ||_my_id==31 ||_my_id==112 ||_my_id==94 ||_my_id==176)
                cerr<<" covered by "<<neibor->id;

              covered = 1;
              break;
            }
          }
      }
    }
 
    // Now we got an 'INSIDE' node, check if we are covering it
    if((!covered)){
      if(cover_debug>1)
      //    if(_my_id==49 || _my_id==170 ||_my_id==31 ||_my_id==112 ||_my_id==94 ||_my_id==176)
        cerr<<endl;
      return 1;
    }
    
    iter++;
  }

  if(cover_debug>1)
  //if(_my_id==49 || _my_id==170 ||_my_id==31 ||_my_id==112 ||_my_id==94 ||_my_id==176)
    cerr<<endl;

  return 0;
}

double
SpanAgent::coverage_contrib(contrib_strategy_t strategy){

  // Check if we have been fully covered by others
  if(!check_coverage())
    return -1;

  double delay;
  switch(strategy){

  case RANDOM:
    delay = random_.uniform(1.00);
    if(cover_debug)
      fprintf(stderr,"# %f: Node[%d] coverage contrib %f\n",
              NOW, self_.id,delay);
    return delay;
  case DIST_SCORE:
    return score();
  }
  return 0;
}

double SpanAgent::score(){
//   double score=0,dist=0;
//   node_t* neibor;
  double ROOT_3 = 1.732050808;

//   for( size_t i=0;i<active_neibors_.size();i++){
//     neibor = &active_neibors_[i];
//     dist = dist_square(&self_.pos,&neibor->pos);
//     dist = sqrt(dist);
//     score += (dist/(Rs*ROOT_3) -1)*(dist/(Rs*ROOT_3) -1);
//   }
//   score /= active_neibors_.size();
  return ROOT_3;
}

void
ClearWithdrawCoordinatorHandler::handle(Event *e)
{
	_agent->clear_withdraw_coordinator();
	delete e;
}

void
SpanAgent::clear_withdraw_coordinator()
{
  if (!check_withdraw(false)) {
    withdraw_pending_ = false;
    fprintf(stderr,"#%f %d withdraw is canceled  -- CLEAR\n",NOW,_my_id);
    return; 
  }

  fprintf(stderr,"#%f: %d withdraw coordinator  -- CLEAR\n",
          NOW,_my_id);
 
  _is_coordinator = false;
  NeighborTable::Neighbor *self = _neighbors.search_neighbor(_my_id);
  self->is_coordinator = false;
  self->nounce = (int)NOW;
  _neighbors.remove_coordinator(_my_id, _my_id);

  withdraw_pending_ = false;

  // notify neighbors my withdraw
  //  broadcast_hello();
}

#endif

void 
SpanAgent::recv(Packet *p, Handler *callback)
{ 


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

  hdr_ip *iph = (hdr_ip *) p->access (_off_ip); 
  hdr_cmn *cmnh =  (hdr_cmn*)p->access(off_cmn_);
  hdr_span *spanh =  (hdr_span*)p->access(_off_span);

  if (!alive()) {
    Packet::free(p);
    return;
  }
  cmnh->retries_ = 0;

  if (_my_id == iph->src() && cmnh->num_forwards()==0) { // source
    spanh->type = SPAN_DATA;
    iph->ttl_ = SPAN_DEF_TTL;
    cmnh->size() += IP_HDR_LEN + spanh->size();
    double x, y, z;
    (God::instance()->nodelist[iph->dst()])->getLoc(&x, &y, &z);
    spanh->dst_x = (int)x;
    spanh->dst_y = (int)y;
    forward_pkt(p);
    return;
  }
  // GX - Add the node to the neighbor and check if it is coordinator  
  process_span_hdr(p);

  if (iph->dst() == _my_id && spanh->type == SPAN_DATA) { // sink
    _pkts_received++;
    _pkts_hops += ((SPAN_DEF_TTL-iph->ttl())+1);