antnet.cc.bak

基于 NS2 的 AntNet 源代码

	nsaddr_t next = rtable_.calc_next(addr(), ah->pkt_dst(), parent);
	// if next hop is this node or parent node, dead end, release packet
	if(next == addr() || next == parent) {
		Packet::free(p);
		return;
	}
	
	ch->next_hop() = next;	// set next hop node address in common header
	ih->saddr() = addr();	// set source address in ip header
	ih->daddr() = next;	// set destination address in ip header
	if(DEBUG)
		fprintf(stdout,"forwarding antnet packet from %d source %d dest %d next hop %d\n", addr(), ah->pkt_src(), ah->pkt_dst(), ih->daddr());
	// send packet to next hop node
	target_->recv(p);
}

//////////////////////////////////////////////////////////////////////////
/// Method to create backward ant packet
/// called when forward ant reaches destination node
//////////////////////////////////////////////////////////////////////////
void Antnet::create_backward_ant_pkt(Packet* p) {
	struct hdr_ip* ih = HDR_IP(p);
	struct hdr_cmn* ch = HDR_CMN(p);
	struct hdr_ant_pkt* ah = HDR_ANT_PKT(p);
	
	// swap source and destination address
	nsaddr_t temp = ah->pkt_src();
	ah->pkt_src() = ah->pkt_dst();
	ah->pkt_dst() = temp;
	
	// retrieve last second entry in memory (last entry is this node)
	int index = ah->pkt_mem_size() - 2;
	ch->direction() = hdr_cmn::UP;	// chnge direction to backward Ant
	ch->ptype() = PT_ANT;	// set packet type as Ant
	ch->next_hop() = ah->pkt_memory_[index].node_addr;	// next hop as determined from memory
	ih->saddr() = addr();	// source address
	ih->daddr() = ch->next_hop();	// destination address
	
	if(DEBUG)
		fprintf(stdout,"creating backward antnet packet from %d source %d dest %d next hop %d\n", addr(), ah->pkt_src(), ah->pkt_dst(), ih->daddr());
	// send backward ant packet
	target_->recv(p);
}

//////////////////////////////////////////////////////////////////////////////////
/// Method to send backward ant packet to next hop node as determined from memory
/// called when agent recieves a backward ant
//////////////////////////////////////////////////////////////////////////////////
void Antnet::backward_ant_pkt(Packet* p) {
	struct hdr_ip* ih = HDR_IP(p);
	struct hdr_cmn* ch = HDR_CMN(p);
	struct hdr_ant_pkt* ah = HDR_ANT_PKT(p);
	
	// find node previous to this node in memory
	int index;
	for(int i = ah->pkt_mem_size()-1; i >= 0; i--) {
		if(ah->pkt_memory_[i].node_addr == addr()) {
			index = i-1;
			break;
		}
	}
	// next hop node determined from memory
	ch->next_hop() = ah->pkt_memory_[index].node_addr;
	ch->direction() = hdr_cmn::UP;	// backward ant
	ch->ptype() = PT_ANT;	// packet type = Ant
	ih->saddr() = addr();	// source address
	ih->daddr() = ch->next_hop();	// destination addres
	
	if(DEBUG)
		fprintf(stdout,"forwarding backward antnet packet from %d source %d dest %d next hop %d\n", addr(), ah->pkt_src(), ah->pkt_dst(), ih->daddr());
	// send backward ant to next hop
	target_->recv(p);
}

///////////////////////////////////////////////////////////////
/// Method to return size of observation window
///////////////////////////////////////////////////////////////
int Antnet::get_win_size(nsaddr_t dest) {
	int count = 0;
	window_t::iterator iterWin = window_.find(dest);
	triptime_t win_tt = (*iterWin).second;
	triptime_t::iterator itertt;
	for(itertt = win_tt.begin(); itertt != win_tt.end(); itertt++) {
		count++;
	}
	return count;
}

////////////////////////////////////////////////////////////////////////////
/// Method to update traffic model and calculate reinforcement factor (r).
/// Presently, constant value of r is used.
/// Value of r can be set form tcl script.
/// Hence, traffic model is not used and this method is not called.
///////////////////////////////////////////////////////////////////////////
void Antnet::update_traffic(Packet* p) {
	//update mean, variance, best.
	struct traffic_matrix temp_traffic;
	nsaddr_t dest, next;
	double tt, oldtt;
	double oldvar;
	double varsigma = VARSIGMA;
	
	struct hdr_ant_pkt* ah = HDR_ANT_PKT(p);
	int i;
	for(i=0; ah->pkt_memory_[i].node_addr != addr(); i++);
	double initialtt = ah->pkt_memory_[i].trip_time;
	i++;
	next = ah->pkt_memory_[i].node_addr;
	
	for(int index = i; index < ah->pkt_mem_size(); index++) {
	
				
		dest = ah->pkt_memory_[index].node_addr;
		tt = ah->pkt_memory_[index].trip_time - initialtt;
		
		/* update sample window */
		window_t::iterator iterWin = window_.find(dest);
		if(iterWin != window_.end()) {	// destination entry exists, add to it in window
			(*iterWin).second.push_back(tt);
		}
		else {	// destination entry does not exist, add new dest entry to window
			triptime_t win_tt;
			win_tt.push_back(tt);
			window_[dest] = win_tt;
		}
	}
	
	/* update traffic */
	for(int index = i; index < ah->pkt_mem_size(); index++) {
		
		dest = ah->pkt_memory_[index].node_addr;
		tt = ah->pkt_memory_[index].trip_time - initialtt;

		/* find best trip time from this node to dest */
		window_t::iterator iterWin = window_.find(dest);
		triptime_t win_tt = (*iterWin).second;
		triptime_t::iterator itertt = win_tt.begin();
		double mintt = (*itertt);
		for(; itertt != win_tt.end(); itertt++) {
			if((*itertt) < mintt)
				mintt = (*itertt);
		}
		
		/* update traffic */
		state_t::iterator iterFind = state_.find(dest);
		if(iterFind != state_.end()) {
			// update existing entry
			oldtt = (*iterFind).second.mean_tt;
			(*iterFind).second.mean_tt = oldtt + varsigma * (tt - oldtt);
			oldvar = (*iterFind).second.var_tt;
			(*iterFind).second.var_tt = oldvar*oldvar + varsigma * ((tt - oldtt)*(tt - oldtt) -  oldvar*oldvar);
			(*iterFind).second.best_tt = mintt;
		}
		else {
			// add map entry
			temp_traffic.mean_tt = tt;
			temp_traffic.var_tt = tt;
			temp_traffic.best_tt = mintt;
			state_[dest] = temp_traffic;
		}
	}
	
	/* find r and update pheromone */
	for(int index = i; index < ah->pkt_mem_size(); index++) {
	
		dest = ah->pkt_memory_[index].node_addr;
		tt = ah->pkt_memory_[index].trip_time - initialtt;
		
	
		/* find r */
		double W_best = state_[dest].best_tt;
		double I_inf = W_best;
		double mu = state_[dest].mean_tt;
		double sigma = sqrt(state_[dest].var_tt);
		int w = get_win_size(dest);
		double I_sup = mu + zee * (sigma/sqrt(w));
		if(I_sup == I_inf && I_inf == tt)
			r = 0.0;
		else
			r = c1*(W_best/tt) + c2 * ((I_sup - I_inf) / ((I_sup - I_inf) + (tt - I_inf) ));
		
		if(DEBUG) {
			printf("r = %f\n", r);
		}
	}
}

//////////////////////////////////////////////////////////
/// Method to update routing table
//////////////////////////////////////////////////////////
void Antnet::update_table(Packet* p) {
	
	nsaddr_t dest, next;
		
	struct hdr_ant_pkt* ah = HDR_ANT_PKT(p);	// ant header
	
	// read node visited next to this node from memory
	// this is the nieghbor node for which routing table will be updated
	int i;
	for(i=0; ah->pkt_memory_[i].node_addr != addr(); i++);
	i++;
	next = ah->pkt_memory_[i].node_addr;
	
	if(DEBUG) {
		fprintf(stdout,"updating ph at %d\n", addr());
		fprintf(stdout,"next: %d\n",next);
	}
		
	nsaddr_t node_addr = addr();
	N = get_num_neighbors(node_addr);
	
	// routing table is updated for all the destination nodes that are visited after the neighbor node
	// update pheromone value corresponding to neighbor node and destination nodes visited thereafter
	for(int index = i; index < ah->pkt_mem_size(); index++) {
		// read destination nodef rom memory
		dest = ah->pkt_memory_[index].node_addr;
		// update pheromone valu fro neighbor node and this destination node
		rtable_.update(dest, next);		
	}
}

//////////////////////////////////////////////////////////
/// Method to initialize routing table
//////////////////////////////////////////////////////////
void Antnet::initialize_rtable() {
	//NUM_NODES = num_nodes_x_ * num_nodes_y_;
	NUM_NODES = num_nodes_;		// set number of nodes in topology (read from tcl script)
	r = r_factor_;	// set reinforcement factor (read from tcl script)
	nsaddr_t node_addr = addr();
	int num_nb = get_num_neighbors(node_addr);
	Node *nd = nd->get_node_by_address(addr());
	// add destination entry for each node in topology
	for(int i = 0; i < NUM_NODES; i++) {
		if(addr() != i) {
			// read list of neighbors
			neighbor_list_node* nb = nd->neighbor_list_;
			while(nb != NULL) {
				// read node id of neighbor node
				int neighb = nb->nodeid;
				// initialize equal pheromone value to all neighbor links
				double phvalue = 1.0/num_nb;
				// add routing table entry
				rtable_.add_entry(i, neighb, phvalue);
				// iterate in neighbor list
				nb = nb->next;
			}
		}
	}
	FILE *fp = fopen(file_rtable,"w");
	fclose(fp);
}

//////////////////////////////////////////////////////////
/// Method to print neighbors of a node
//////////////////////////////////////////////////////////
void
Antnet::print_neighbors() {
	nsaddr_t node_addr = addr();
	fprintf(stdout,"addr: %d\tra_addr:%d\n",addr(), ra_addr());
	Node *n = n->get_node_by_address(node_addr);
	fprintf(stdout,"node id: %d\tnode address: %d\n", n->nodeid(), n->address());
	fprintf(stdout,"Neighbors:\n");
	neighbor_list_node* nb = n->neighbor_list_;
	do {
		int neigh = nb->nodeid;
		printf("%d\n",neigh);
		nb = nb->next;
	}while(nb != NULL);
}

//////////////////////////////////////////////////////////
/// Method to add neighbors of a node
/// Parameters: addresses of two neighbor nodes (n1, n2)
/// We assume duplex links
/// - Add n1 to neighbor list of n2
/// - Add n2 to neighbor list of n1
//////////////////////////////////////////////////////////
void
Antnet::add_Neighbor(Node *n1, Node *n2) {
	n1->addNeighbor(n2);
	n2->addNeighbor(n1);
}

//////////////////////////////////////////////////////////
/// Method to reset Ant timer
//////////////////////////////////////////////////////////
void Antnet::reset_ant_timer() {
	ant_timer_.resched(timer_ant_);
}

//////////////////////////////////////////////////////////
/// Method to handle Ant timer expire event
//////////////////////////////////////////////////////////
void Ant_timer::expire(Event *e) {
	// generate forward ant
	agent_->send_ant_pkt();
	// reschedule timer
	agent_->reset_ant_timer();
}