antnest.cc

Programming language: Developed in Omnet++. Comment: The model implements the AntNet routing algori

// -*- 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 original
int 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
// GIANNI

int 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;
}
#endif


int 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