// -*- C++ -*-// Copyright (C) 2003 Leherstuh f黵 Betrieb System/ Verteilte System, // Universitaet Dortmund //// This program is free software; you can redistribute it and/or// modify it under the terms of the GNU General Public License// as published by the Free Software Foundation; either version 2// of the License, or (at your option) any later version.//// This program is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the// GNU General Public License for more details.//// You should have received a copy of the GNU General Public License// along with this program; if not, write to the Free Software// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.// Author: Muddassar Farooq// Informatik III, Universitaet Dortmund// Germany//-------------------------------------------------------------// file: antNest.cpp//        (part of AntNet Routing Simulation)//-------------------------------------------------------------#include "antNest.h"/* #define original */

// There are small variations suggested by the author of AnNet Algorithm.
// If some one wants to omitt them then simply uncomment following line

/* #define original */Define_Module( antNest );antNest::~antNest(){	delete[] averageOfTimeToDest;	delete[] varianceOfTimeToDest;	delete[] bestTimeToDest;	delete[] timeWindowSamples;	delete[] bestTimeToDestInWindow;}void antNest::initializeNestFromRouter(){	antsDeleted = 0;	ptr = (Router *) gate("toRouter")->toGate()->ownerModule();	numNeighbors = ptr->getNumNeighbors();	numNodes = ptr->getNumNodes();	queueSize = ptr->getQueueMaxLen();	dataRate = ptr->getBandwidth();	myAddress = ptr->getMyAddress();	strcpy(sFileName,par("statFile"));	sPtr = statistics::Instance(sFileName);	hopsLimit = (int) (maxHopsCoefficient * numNodes);	// Co-efficient of exponential (n) means is used to compute	// exponential averages for the local traffic statistics	// 5*(1/n). Hence with the help of this 	// coefficient we could easily determine the number	// of samples that must be used in the computation	// of interval of confidence.	exponentialWinSize = (int) (1./expMeanCoefficient) * 5;	squreExpWinSize = (int) sqrt( (double)exponentialWinSize );	//  The purpose of this window size is to determine the	//  best round trip time over a window and then use it	//  in the reinforcement. Reinforcement takes into account	//  the ratio between current trip time and the best	//  trip time observed over this window.	//  | Wmax | = 5*(c/n) where c is windowSizeCoefficient	windowSize = (int) (windowSizeCoefficient * exponentialWinSize);	// initializing the probability in a uniform fashion	const double initialTransProb = 1./numNeighbors;	for(int i = 0; i < numNodes; i++)	{		for(int j = 0; j < numNeighbors; j++)		{			int neighbor = ptr->findNeighborAtIndex(j);			if( i != myAddress)			{				ptr->setProb(i,neighbor,initialTransProb);			}			else			{				ptr->setProb(i,neighbor,0.0);			}				} 	}		averageOfTimeToDest = new double[numNodes];	varianceOfTimeToDest = new double[numNodes];	bestTimeToDest = new double[numNodes];	timeWindowSamples = new int[numNodes];	bestTimeToDestInWindow = new double[numNodes];		for(int k = 0; k < numNodes; k++)	{		timeWindowSamples[k] = 0;		bestTimeToDest[k] = MAXFLOAT;		bestTimeToDestInWindow[k] = MAXFLOAT;		averageOfTimeToDest[k] = 0.0;		varianceOfTimeToDest[k] = 0.0;	}}

void antNest::initialize()
{
	expMeanCoefficient = par("expMeanCoefficient");
	windowSizeCoefficient = par("windowSizeCoefficient");
	zetaConfidenceLevel = par("zetaConfidenceLevel");
	explorationProbablity = par("explorationProbablity");
	rescalingPower = par("rescalingPower");
	queueWeight = par("queueWeight");
	forkProbability = par("forkProbability");
	maxHopsCoefficient = par("maxHopsCoefficient");
	ageLimit = par("ageLimit");
	squashFunctionCoefficient = par("squashFunctionCoefficient");
	probabilisticRouting = par("probabilisticRouting");
	timeWeight = par("timeWeight");
	converganceTime = par("converganceTime");

	double sleepTime = (double) par("sleepTimeAtStart");
	initRouter = new cMessage("InitRouter");
	scheduleAt( simTime() + sleepTime, initRouter);
}void antNest::handleMessage(cMessage *msg){
	int kind = msg->kind();

	if(kind == NETLAYER_FORWARD_ANT)
	{
		current = (Ant *) msg;
		processForwardAnts();
	}
	else if(kind == NETLAYER_BACKWARD_ANT)
	{
		current = (Ant *) msg;
		processBackwardAnts();
	}
	else if( msg == initRouter)
	{
		initializeNestFromRouter();
	}
	else	{		throw new cException("Unknown Message %d in AntNest of router %d",								kind, myAddress);	}}void antNest::processForwardAnts(){	bool antDeleted = false;	// 1. Check whether hop or age limit has been reached 	// 2. check whether the ant has reached the destination	if( current->getDestNode() == myAddress)	{		current->setKind( NETLAYER_BACKWARD_ANT );		// Determine the previous node and set it as neighbor chosen		// to simpliy processing of this ant at router module		int previousNode = (current->topOfStack()).nodeAddress;		current->setNeighborChosen(previousNode);		antStackEntry entry;		entry.nodeAddress = myAddress;		entry.nodeEntranceTime = simTime();				// now do the recording keep values by pushing the		// entrance time and nodeID onto the stack.		// for quick checking of cycles, we keep another		// array for the nodes being visited by the ant.		current->addToVisitedNodes( myAddress );		current->addToCycleNodes( entry );	}		else	{		// Determine if ant were generated at this node		findSourceForAnt( current );		if(nTcb.source == ROUTER)		{			//3. doForwardAntActions()			antDeleted = doForwardAntActions();		}		else if (nTcb.source == ANT_GEN)		{			selectLinks();		}	}	// Finally now send this forward ant back to the router	if( !antDeleted )	{		int hops = current->getHops();
		hops++;		current->setHops(hops);		current->setSourceModule( (int) ANT_NEST);		send(current,"toRouter");	}}void antNest::processBackwardAnts(){	// Update Routing Table	doBackwardAntActions();	if(current->getSourceNode() == myAddress)	{		// send to the sink		send(current,"toAntSink");			}	else	{		// set the source of this ant		current->setSourceModule( (int) ANT_NEST);		send(current,"toRouter");	}}void antNest::doBackwardAntActions(){	int dest = current->getDestNode();	updateRoutingTable(dest);}void antNest::selectLinks(){		int destNode = current->getDestNode();		int nextHop = 0;		int fLinks = 0; // number of feasible links		nodeProbPair *goodnessProbability = new nodeProbPair[numNeighbors];		// calculate goodness for feasible links		goodnessForFeasibleLinks(destNode,fLinks,goodnessProbability);		int node = 0;#ifdef original		if( explorationProbablity > 0 && 			(node = selectLinkInRandomUniformWay()) != UNIFORM_RANDOM_SELECTION_FAILED)#else // GIANNI		double prob = uniform(0.0, 1.0);		if( explorationProbablity > prob && 			(node = selectLinkInRandomUniformWay()) != UNIFORM_RANDOM_SELECTION_FAILED)#endif		{						nextHop = node;		}	  // Select the outlink in a probabilistic proportional way according to the 	  // computed goodness estimates goodnessProbability. The selection is made among 	  // the nodes not visited yet. If all the nodes have been already visited, 	  // the one with the highest goodness estimate is deterministically selected#ifdef original		else if (fLinks == numNeighbors) // all neighbors visited		{			nextHop = selectLinkWithHighestGoodness(fLinks, goodnessProbability);		}#else// GIANNI		else if (fLinks == numNeighbors) // all neighbors visited		{		  node = selectLinkInRandomUniformWay();		  if( node == UNIFORM_RANDOM_SELECTION_FAILED )		    node =  ptr->findNeighborAtIndex(0);		  nextHop = node;		}#endif		else		{#ifdef original		  double binProb = uniform(0.0,1.0);		  if( binProb <= 0.75)		    {		      nextHop = selectLinkInRandomPropotionalWay(fLinks, goodnessProbability);		      		    }		  else		    {		      nextHop = selectLinkWithHighestGoodness(fLinks, goodnessProbability);		    }#else//GIANNI		  double binProb = uniform(0.0,1.0);		  nextHop = selectLinkInRandomPropotionalWay(fLinks, goodnessProbability);#endif		}		delete[] goodnessProbability;				antStackEntry entry;		entry.nodeAddress = myAddress;		entry.nodeEntranceTime = simTime();				// now do the recording keep values by pushing the		// entrance time and nodeID onto the stack.		// for quick checking of cycles, we keep another		// array for the nodes being visited by the ant.		current->setNeighborChosen( nextHop );		current->addToVisitedNodes( myAddress );		current->addToCycleNodes( entry );}bool antNest::doForwardAntActions(){	// check if this ant reached age or hop limits	if( !checkIfAntReachedAgeOrHopsLimitThenDelete())	{		if( !checkIfAntIsObsoleteThenDelete() ) 		{			selectLinks();			return false;		}	}	antsDeleted++;	sPtr->incrTotalAntsDeleted();
	return true;	// do nothing as this ant has been deleted}#ifdef originalint antNest::selectLinkInRandomUniformWay(){	double prob = uniform(0.0, 1.0);	int index = 0;	int sourceNode = current->getSourceNode();	if ( sourceNode != myAddress)	{		int lastNode = (current->topOfStack()).nodeAddress;		int neighborIndex = ptr->findIndexForNeighbor(lastNode);		if( prob < explorationProbablity)		{			// Do not select the same neighbor from which this ant came			while(( index = intrand( numNeighbors )) == neighborIndex)			{				int neighbor = ptr->findNeighborAtIndex(index);				return neighbor;			}		}	}	else	{		if( prob < explorationProbablity)		{			int index = intrand( numNeighbors );			int neighbor = ptr->findNeighborAtIndex(index);			return neighbor;		}	}	return UNIFORM_RANDOM_SELECTION_FAILED;}#else// GIANNIint antNest::selectLinkInRandomUniformWay(){  int index = 0;    int sourceNode = current->getSourceNode();    if( numNeighbors == 1 )    return UNIFORM_RANDOM_SELECTION_FAILED;  if ( sourceNode != myAddress)    {      int lastNode = (current->topOfStack()).nodeAddress;            int lastNodeNeighborIndex = ptr->findIndexForNeighbor(lastNode);            // Do not select the same neighbor from which this ant came      while(1)	{	  index = intrand( numNeighbors ); 	  	  if(index != lastNodeNeighborIndex)	    return ptr->findNeighborAtIndex(index);	}    }  else    {      int index = intrand( numNeighbors );      return ptr->findNeighborAtIndex(index);    }    return UNIFORM_RANDOM_SELECTION_FAILED;}#endifint antNest::selectLinkInRandomUniformWayAntsGeneratedAtThisNode(){	int neighbor;	do	{		// Do not select the node that generated current ant as next hop		int index =  intrand( numNeighbors);		neighbor = ptr->findNeighborAtIndex(index);	} while ( neighbor == myAddress);	return neighbor;		}int antNest::selectLinkInRandomPropotionalWay(int count, nodeProbPair *goodnessProb){	double incrProb = 0.0;	int selectedNeighbor = -2;	int neighbor;	double binProb = uniform(0.0, 1.0);	int lastNode;	int sourceNode = current->getSourceNode();		// if ant is origanted at this node, so it would not be having	// any last node hence we could set it to currentNode. In this	// way neighbor != lastNode will be true in any case	if( sourceNode != myAddress)	{		int lastNode = (current->topOfStack()).nodeAddress;	}	else	{		lastNode = myAddress;	}	// we need to ensure that we do not send the ant to the same node 	// from where it arrived. 	for(int i = 0; i < numNeighbors; i++)	{		int k = goodnessProb[i].neighbor;		if ( k != -1)		{					incrProb += goodnessProb[i].value;			neighbor = goodnessProb[i].neighbor;			if( binProb <= incrProb && neighbor != lastNode) 			{				return neighbor;			}		}	}	for(int j = 0; j < numNeighbors; j++)	{		int k = goodnessProb[j].neighbor;		if ( k != -1 && k != lastNode)		{					selectedNeighbor = k;			break;		}	}		if(selectedNeighbor == -2)	{		selectedNeighbor = lastNode;	}	return selectedNeighbor;}int antNest::selectLinkWithHighestGoodness(int count, nodeProbPair *goodnessProb){	nodeProbPair temp;	temp.value = 0.0;	temp.neighbor = -2;	int lastNode;	int sourceNode = current->getSourceNode();		// if ant is origanted at this node, so it would not be having	// any last node hence we could set it to currentNode. In this	// way neighbor != lastNode will be true in any case	if( sourceNode != myAddress)	{		 lastNode = (current->topOfStack()).nodeAddress;	}	else	{		lastNode = myAddress;	}	for(int i = 0; i < numNeighbors; i++)	{		int k = goodnessProb[i].neighbor;		if ( k != -1 && k != lastNode)		{			if ( goodnessProb[i].value > temp.value )			{				temp.value = goodnessProb[i].value;				temp.neighbor = goodnessProb[i].neighbor;							}		}	}	if(temp.neighbor == -2)	{		temp.neighbor = lastNode;	}	return temp.neighbor;}void antNest::goodnessForFeasibleLinks(int destNode, int& count, nodeProbPair *goodnessProb){	int feasibleNeighbors = 0;	double normGoodness = 0.0;	nodeProbPair *neighbors = new nodeProbPair[numNeighbors];	heuristicCorrectionFactor(feasibleNeighbors, neighbors);	count = feasibleNeighbors;	for(int i = 0; i < numNeighbors ; i++)	{		int k =  neighbors[i].neighbor;		if ( k != -1)		{			int neighbor = neighbors[i].neighbor;			double Pnd = ptr->getProb(destNode,neighbor);					// Pnd + aplha * Ln			double ln = neighbors[i].value;			double Pgoodness = Pnd + queueWeight * ln;			normGoodness += Pgoodness;		}	}	for(int j = 0; j < numNeighbors ; j++)	{		int k = neighbors[j].neighbor;		if ( k != -1)		{			int neighbor = neighbors[j].neighbor;					double Pnd = ptr->getProb(destNode,neighbor);			// Pnd + aplha * Ln			double ln = neighbors[j].value;			double Pgoodness = Pnd + queueWeight * ln;			goodnessProb[j].neighbor = neighbor;			goodnessProb[j].value = Pgoodness / normGoodness;		}		else		{			goodnessProb[j].neighbor = k;		}	}	delete[] neighbors;}// ln = 1 - qn/sum(qn