landmark.cc

对IEEE 802.11e里的分布式信道接入算法EDCA进行改进

    }
  }
  // If the advertising LM is a potl parent, add to level-1 
  // ParentChildrenList object
  else if(potl_parent_flag) {
    LMNode *old_parent = (*pcl1)->parent_;
    (*pcl1)->UpdatePotlParent(origin_id, next_hop, num_hops, level, num_children, energy, origin_time, FALSE);

    // If we receive this message from a parent at some level, update
    // the assigned addresses
    if((((*pcl1)->parent_)->id_ == origin_id) && (level-1 == highest_level_)) {
      //      if(num_lm_addrs) 
      //	trace("Node %d: Rcvd higher level lm addr from %d at time %f",myaddr_,origin_id,now);
      //      else
      //	trace("Node %d: Rcvd higher level lm addr msg with no addrs from %d at time %f",myaddr_,origin_id,now);
      ((*pcl1)->mylmaddrs_)->delete_lm_addrs();
      assign_lmaddress(lm_addrs, num_lm_addrs, (*pcl1)->level_);
    }

    // Check if parent has changed
    int new_advert = 0;
    // The first condition may arise if the old parent obj is deleted ... (?)
    if((*pcl1)->parent_ == old_parent && old_parent) {
      if(((*pcl1)->parent_)->id_ != old_parent->id_)
	new_advert = 1;
    }
    else if((*pcl1)->parent_ != old_parent && (*pcl1)->parent_ && old_parent) {
      if(((*pcl1)->parent_)->id_ != old_parent->id_)
	new_advert = 1;
    }
    else if((*pcl1)->parent_ != old_parent)
      new_advert = 1;
    
    // Trigger advertisement if parent has changed
    if(new_advert && (level-1 <= highest_level_)) {
      newp = makeUpdate((*pcl1), HIER_ADVS, PERIODIC_ADVERTS);
      s.schedule(target_,newp,0);
      (*pcl1)->last_update_sent_ = now;
    }

  // If a parent has been selected for highest_level_, cancel promotion timer
  // (for promotion to highest_level_+1) if it's running
    if((level == (highest_level_ + 1)) && ((*pcl1)->parent_ != NULL)) {
      if(promo_timer_running_ && !wait_state_) {
	trace("Node %d: Promotion timer cancelled at time %f in ProcessHierUpdate\n",myaddr_,s.clock());
	promo_timer_->cancel();
	total_wait_time_ = 0;
	wait_state_ = 1;
	double wait_time = PERIODIC_WAIT_TIME;
	total_wait_time_ += wait_time;
	promo_timer_->sched(wait_time);
      }
    }
    else if(level > 0 && level == highest_level_) {
      // Check if the potl parent for highest_level_-1 that we see covers our
      // potential children. If so, we can demote ourselves and cancel our 
      // current promotion timer
      pcl = &parent_children_list_;
      while((*pcl) != NULL) {
	if((*pcl)->level_ == level) {
	  break;
	}
	pcl = &((*pcl)->next_);
      }
      assert(*pcl);

      LMNode *lm = (*pcl)->pchildren_;
      int is_subset = TRUE;
      if((*pcl)->num_potl_children_ > num_potl_children) {
	is_subset = FALSE;
	lm = NULL;
      }

      int is_element = FALSE;
      while(lm) {
	is_element = FALSE;
	for(i = 0; i < num_potl_children; ++i) 
	  if(lm->id_ == potl_children[i] && lm->child_flag_ != NOT_POTL_CHILD) {
	    is_element = TRUE;
	    break;
	  }
	if(is_element == FALSE && lm->child_flag_ != NOT_POTL_CHILD) {
	  is_subset = FALSE;
	  break;
	}
	lm = lm->next_;
      }
      // Demotion process
      if(is_subset == TRUE) {
    	--(highest_level_);
    	delete_flag = TRUE;
	if((*pcl1)->parent_)
	  trace("Node %d: Num potl ch %d, Node %d: Num potl ch %d, time %d",myaddr_, (*pcl)->num_potl_children_,origin_id,num_potl_children,(int)now);
	trace("Node %d: Parent before demotion: %d, msg from %d at time %f",myaddr_, ((*pcl1)->parent_)->id_,origin_id,now);
	
	int upd_time = (int)now;
	upd_time = (upd_time << 16) | ((*pcl1)->seqnum_ & 0xFFFF);
	++((*pcl1)->seqnum_);
	(*pcl1)->UpdatePotlParent(myaddr_, 0, 0, 0, 0, 0, upd_time, delete_flag);

	if((*pcl1)->parent_)
	  trace("Node %d: Parent after demotion: %d",myaddr_, ((*pcl1)->parent_)->id_);

	upd_time = (int) now;
	upd_time = (upd_time << 16) | ((*pcl2)->seqnum_ & 0xFFFF);
	++((*pcl2)->seqnum_);
    	(*pcl2)->UpdatePotlChild(myaddr_, 0, 0, 0, 0, 0, upd_time, IS_CHILD, delete_flag,NULL);

	// Send out demotion messages
	newp = makeUpdate(*pcl, HIER_ADVS, DEMOTION);
	s.schedule(target_, newp, 0);

    	if(promo_timer_running_ && !wait_state_) {
    	  trace("Node %d: Promotion timer cancelled due to demotion at time %d\n",myaddr_,(int)now);
    	  promo_timer_->cancel();
	  total_wait_time_ = 0;
	  wait_state_ = 1;
	  double wait_time = PERIODIC_WAIT_TIME;
	  total_wait_time_ += wait_time;
	  promo_timer_->sched(wait_time);
    	}
      }
    }      
  }


  // If new entry, flood advertisements for level > adv LM's level
  if(ret_value == NEW_ENTRY) {
    ParentChildrenList *tmp_pcl = parent_children_list_;
    while(tmp_pcl) {
      // New nodes should have an initial wait time of atleast 0.1 seconds
      if(tmp_pcl->level_ <= highest_level_ && tmp_pcl->level_ >= level && (now - tmp_pcl->last_update_sent_) > 0.1) {
	newp = makeUpdate(tmp_pcl, HIER_ADVS, PERIODIC_ADVERTS);
	s.schedule(target_,newp,0);
	tmp_pcl->last_update_sent_ = now;
      }
      tmp_pcl = tmp_pcl->next_;
    }
  }

  if(num_potl_children) delete[] potl_children;
  if(num_lm_addrs) delete[] lm_addrs;
  if(num_advert_lm_addrs) delete[] advert_lm_addrs;
  // Delete tag list
  tag_ptr1 = adv_tags;
  while(tag_ptr1) {
    tag_ptr2 = tag_ptr1;
    tag_ptr1 = tag_ptr1->next_;
    delete tag_ptr2;
  }
  
  // Do not forward demotion message if we have seen this message before
  if(action == DEMOTION) {
    //    if(myaddr_ == 30)
    //      printf("Am here\n");
    if(CheckDemotionMsg(origin_id, level, (int)origin_time) == OLD_MESSAGE) {
      Packet::free(p);
      return;
    }
  }

  // Do not forward packet if ttl is lower unless the packet is from the global
  // LM in which case the packet needs to be flooded throughout the network
  if(--iph->ttl_ == 0 && action != GLOBAL_ADVERT) {
    //    drop(p, DROP_RTR_TTL);
    Packet::free(p);
    return;
  }

  // Do not forward if the advertisement is for this node
  if((iph->daddr() >> 8) == myaddr_) {
    //    trace("Node %d: Received unicast advert from %d at level %d for us at time %f",myaddr_,iph->saddr(),level,now);
    Packet::free(p);
    return;
  }

  if(action == UNICAST_ADVERT_CHILD) {
    hdrc->next_hop() = get_next_hop(iph->daddr(),level);
    //    if(myaddr_ == 153)
    //      trace("Node %d: Received child unicast advert from %d to %d at level %d at time %f, next hop %d",myaddr_,iph->saddr(),iph->daddr(),level,now,hdrc->next_hop());
  }
  else if(action == UNICAST_ADVERT_PARENT) {
    //    trace("Node %d: Received parent unicast advert from %d to %d at level %d at time %f",myaddr_,iph->saddr(),iph->daddr(),level,now);
    hdrc->next_hop() = get_next_hop(iph->daddr(),level+2);
  }
  
  assert(hdrc->next_hop() != NO_NEXT_HOP);

  //  if(now > 412.5) {
  //    purify_printf("ProcessHierUpdate2\n");
  //    purify_new_leaks();
  //  }

  // Need to send the packet down the stack
  hdrc->direction() = hdr_cmn::DOWN;
  
  //  if(debug_) printf("Node %d: Forwarding Hierarchy Update Packet", myaddr_);
  s.schedule(target_, p, 0);
}
  



void
LandmarkAgent::assign_lmaddress(int64_t *lmaddr, int num_lm_addrs, int root_level)
{
  ParentChildrenList *tmp_pcl, *cur_pcl = NULL, *child_pcl = NULL;
  ParentChildrenList *parent_pcl = NULL;
  LMNode *pchild;
  int i;  
  int level = root_level;

  //  assert(root_level != 0);
  
  while(level >= 0) {
    tmp_pcl = parent_children_list_;
    while(tmp_pcl) {
      if(tmp_pcl->level_ == level)
	cur_pcl = tmp_pcl;
      if(tmp_pcl->level_ == (level-1))
	child_pcl = tmp_pcl;
      if(tmp_pcl->level_ == (level+1))
	parent_pcl = tmp_pcl;
      tmp_pcl = tmp_pcl->next_;
    }
    
    assert(cur_pcl);
    if(level) assert(child_pcl);
    assert(parent_pcl);

    // Update LM address at the appropriate level
    if(level == root_level) {
      (cur_pcl->mylmaddrs_)->delete_lm_addrs();
      if(num_lm_addrs) {
	for(i = 0; i < num_lm_addrs; ++i) {
	  (cur_pcl->mylmaddrs_)->add_lm_addr(lmaddr[i]);
	}
	parent_pcl->UpdateChildLMAddr(myaddr_,num_lm_addrs,lmaddr);
      }
    }
    
    int num_addrs = 0;
    int64_t *assigned_addrs = NULL;
    (cur_pcl->mylmaddrs_)->get_lm_addrs(&num_addrs,&assigned_addrs);

    if(num_addrs == 0) {
      pchild = cur_pcl->pchildren_;
      while(pchild) {
	if(pchild->child_flag_ == IS_CHILD) {
	  (pchild->lmaddr_)->delete_lm_addrs();
	  if(pchild->id_ == myaddr_ && level)
	      (child_pcl->mylmaddrs_)->delete_lm_addrs();
	}
	pchild = pchild->next_;
      }
    }
    else if(cur_pcl->num_children_) {
      // ID at a particular level starts from 1
      for(i = 0; i < num_addrs; ++i) {
	int64_t j = 1;
	int64_t addr = assigned_addrs[i] + (j << ((cur_pcl->level_-1)*8));
	// Assign addresses to child nodes
	
	//	while( j <= MAX_CHILDREN) {
	pchild = cur_pcl->pchildren_;
	assert(cur_pcl->num_children_ <= MAX_CHILDREN);
	
	while(pchild) {
	  if(pchild->child_flag_ == IS_CHILD) {
	    (pchild->lmaddr_)->delete_lm_addrs();
	    (pchild->lmaddr_)->add_lm_addr(addr);
	    if(pchild->id_ == myaddr_ && level) {
	      (child_pcl->mylmaddrs_)->delete_lm_addrs();
	      (child_pcl->mylmaddrs_)->add_lm_addr(addr);
	    }
	    ++j;
	    addr = assigned_addrs[i] + (j << ((cur_pcl->level_-1)*8));
	    //	    if(j > MAX_CHILDREN) break;
	    assert(j <= MAX_CHILDREN);
	  } /* if */
	  pchild = pchild->next_;
	  //	  }/* while */
	}
      }
    }
    if(num_addrs) delete[] assigned_addrs;
    --level;
  }
}




void
LandmarkAgent::periodic_callback(Event *e, int level)
{
  //  if(debug_) printf("Periodic Callback for level %d", level);
  Scheduler &s = Scheduler::instance();
  double now = Scheduler::instance().clock(), next_update_delay;
  int energy = (int)(node_->energy());
  int unicast_flag = FALSE, suppress_flag = FALSE;
  Packet *newp;
  hdr_ip *iph, *new_iph;
  hdr_cmn *cmh, *new_cmh;
  int action = PERIODIC_ADVERTS, parent_changed = 0, child_changed = 0;
  int upd_time = (int) now;

  //  if(now > 412.5) {
  //    purify_printf("periodic_callback1: %f,%d\n",now,myaddr_);
  //    purify_new_leaks();
  //  }

  //  if(myaddr_ == 12 && now > 402)
  //    purify_new_leaks();

  // Should always have atleast the level 0 object
  assert(parent_children_list_ != NULL); 
  ParentChildrenList *pcl = parent_children_list_;
  ParentChildrenList *cur_pcl = NULL;
  ParentChildrenList *new_pcl = NULL;
  ParentChildrenList *pcl1 = NULL;
  ParentChildrenList *pcl2 = NULL;

  // return if we have been demoted from this level
  if(highest_level_ < level) 
    return; 
  
  while(pcl != NULL) {
    new_pcl = pcl;
    if(pcl->level_ == level){
      cur_pcl = pcl;
    }
    if(pcl->level_ == (level - 1)){
      pcl1 = pcl;
    }
    if(pcl->level_ == (level + 1)){
      pcl2 = pcl;
    }
    pcl = pcl->next_;
  }
  
  assert(cur_pcl);
  if(level)
    assert(pcl1);

  // Create level+1 object if it doesnt exist
  if(!pcl2) {
    new_pcl->next_ = new ParentChildrenList(level+1, this);
    pcl2 = new_pcl->next_;
  }

  assert(pcl2);

  // Delete stale potential parent entries
  LMNode *lmnode = cur_pcl->pparent_;
  LMNode *tmp_lmnode;
  int delete_flag = TRUE;
  LMNode *old_parent = cur_pcl->parent_;
  while(lmnode) {
    // Record next entry in linked list incase the current element is deleted
    tmp_lmnode = lmnode->next_;
    if(((now - lmnode->last_update_rcvd_) > cur_pcl->update_timeout_)) {
      //      if(debug_) trace("Node %d: Deleting stale entry for %d at time %d",myaddr_,lmnode->id_,(int)now);
      upd_time = (int) now;
      upd_time = (upd_time << 16) | ((lmnode->last_upd_seqnum_ + 1) & 0xFFFF);
      cur_pcl->UpdatePotlParent(lmnode->id_, 0, 0, 0, 0, 0, upd_time, delete_flag);
    }
    lmnode = tmp_lmnode;
  }
  
  // The first condition may arise if the old parent obj is deleted ... (?)
  if(cur_pcl->parent_ == old_parent && old_parent) {
    if((cur_pcl->parent_)->id_ != old_parent->id_)
      parent_changed = 1;
  }
  else if(cur_pcl->parent_ != old_parent && cur_pcl->parent_ && old_parent) {
    if((cur_pcl->parent_)->id_ != old_parent->id_)
      parent_changed = 1;
  }
  else if(cur_pcl->parent_ != old_parent)
    parent_changed = 1;
  

  // Delete stale potential children entries
  lmnode = cur_pcl->pchildren_;
  delete_flag = TRUE;
  int demotion = FALSE;
  while(lmnode) {
    // Record next entry in linked list incase the current element is deleted
    tmp_lmnode = lmnode->next_;
    if((now - lmnode->last_update_rcvd_) > cur_pcl->update_timeout_) {
      if(lmnode->child_flag_ == IS_CHILD)
	child_changed = 1;
      assert(level && lmnode->id_ != myaddr_);
      upd_time = (int) now;
      upd_time = (upd_time << 16) | ((lmnode->last_upd_seqnum_ + 1) & 0xFFFF);
      cur_pcl->UpdatePotlChild(lmnode->id_, 0, 0, 0, 0, 0, upd_time, lmnode->child_flag_, delete_flag,NULL);
    }
    lmnode = tmp_lmnode;
  }
  
  // Send updates if tag list has changed i.e., when a child has changed
  if(child_changed)
    SendChangedTagListUpdate(0,level-1);
  
  // Demote ourself if any child's energy > 30 % of our energy
  if(demotion) {