antnest.cc

use swarm intelligence to simulate network routings in omnet

// -*- 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(const char *name, cModule *parentmodule, unsigned stacksize)
  : cSimpleModule(name, parentmodule,stacksize)
{
	averageOfTimeToDest = NULL;
	varianceOfTimeToDest = NULL;
	bestTimeToDest = NULL;
	timeWindowSamples = NULL;
	bestTimeToDestInWindow = NULL;
}

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();
	myAddress = ptr->getMyAddress();

	const char *statModulePath = par("statModulePath");
	cModule *tmp1 = simulation.moduleByPath(statModulePath);
	sPtr= check_and_cast<statistics *> (tmp1);


	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;
	ptr->initAntRoutingTable(initialTransProb);

	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;
		int size = current->forwardAntSize();
		current->setLength( size );
		processForwardAnts();
	}
	else if(kind == NETLAYER_BACKWARD_ANT)
	{
		current = (Ant *) msg;
		int size = current->backwardAntSize( current->length() );
		current->setLength( size );
		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();
		entry.estimatedEntryTime = current->getTimeAtNextHop(); //this was the time estimated at the last node

		// 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();
	int hops = current->getHops();
	hops++;
	current->setHops(hops);

	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();
		entry.estimatedEntryTime = current->getTimeAtNextHop(); //this was the time estimated at the last node

		// 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)
	{
		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