APPENDIX A – C++ SOURCE CODE

(1)

APPENDIX A – C++ SOURCE CODE

A.1. Combined.cc

/* combined.cc

setdest program for the Combined Mobility Model */ extern "C" { #include <assert.h> #include <fcntl.h> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/time.h> #include <sys/types.h> #include <sys/uio.h> #include <unistd.h>

#if !defined(sun) && !defined(__CYGWIN__) #include <err.h> #endif }; #include <fstream> #include <vector> #include <deque> #include <set> #include "setdest_cm_mod.h" #include "af_helper_mod.h" //#define DEBUG_CM //#define DEBUG #define SANITY_CHECKS #define TIME_STEP 0.00625 /*================================================

(2)

Function Prototypes ================================================*/ void usage(char**); void init(void); double uniform(void); void ComputeW(void); void floyd_warshall(void); void show_diffs(void); void show_counters(void); Path build_path(Vertex,Vertex);

/* Neighbor Density Tracking */

void update_neighbors(void);

/*================================================ Global Variables

================================================*/

double RANGE = -91.0; /*transmitter range in dBm */

double RADIUS = 2500;

double TIME = 0.0; /* my clock */

double DISC_TIME = 0.0; /* the discrete clock */

int DISC_STEP = 0;

double MAXTIME = 0.0; /* duration of simulation */ double MAXX = 0.0; double MAXY = 0.0; double MINSPEED_ = 0.0; double MAXSPEED = 0.0; double PAUSE = 0.0; u_int32_t NODES = 0; u_int32_t LinkChangeCount = 0;

/* char* for the input files */

char *INPUTFILE = 0; char *IMGNAME = 0; char *DEFSNAME = 0; Node *NodeList = 0; bool *Connectivity = 0;

(3)

Path *PathMatrix = 0;

map<u_int32_t,u_int32_t> VertexMap; vector<Vertex> VertexVector;

static u_int32_t VerticesCounter = 0;

/* Topology Stat Tracking */

u_int32_t *D1 = 0; u_int32_t *D2 = 0; u_int32_t *D3 = 0; double *neighbor_density = 0; int next_update = 0; /* COMBINED */

double RWPROB_ = 0; /*RW PARAMETER*/

double MAXMOV=100.0; /*MAX MOVEMENT ALONG EACH AXIS DURING THE RWP*/

#define COLOR_FORMAT "$node_(%d) color %s\n" #define COLOR_FORMAT2 "$ns_ at %.12f \"$node_(%d) color %s\"\n"

char *color;

Path build_path_Dijkstra(Vertex,Vertex);

/*================================================ Random Number Generation

================================================*/

#define M 2147483647L

#define INVERSE_M ((double)4.656612875e-10)

#ifdef DEBUG_CM char random_state[32]; #endif RNG *rng; double uniform() { return rng->uniform_double() ; } /*================================================ Misc Functions... ================================================*/

(4)

void

usage(char **argv) {

fprintf(stderr,

"\nusage: %s\t-n <nodes> -r <range> -p <pause time> -s <min speed> -S <max speed> -w <RW prob.(>1 IfDependingOnAreas)> -m <MAXMOV>\n",

argv[0]); fprintf(stderr,

"\t\t-t <simulation time> -x <max X> -y <max Y> -f <graph input file> -g <floorplan input file> -d <af defs file> \n\n");

}

void init() { /*

* Initialized the Random Number Generation * The more portable solution for random number * generation

*/

rng = new RNG;

rng->set_seed(RNG::HEURISTIC_SEED_SOURCE);

/*

* Set up COMBINED model */

loadDefs(DEFSNAME,RWPROB_);

fprintf(stdout, "#File Defs caricato\n"); loadImg(IMGNAME,MAXX,MAXY);

fprintf(stdout, "#File Imm caricato\n");

/*

* Allocate memory for globals */

u_int32_t NumberOfVertices;

D1 = new u_int32_t[NODES * NODES]; if(D1 == 0) {

(5)

exit(1); }

memset(D1, '\xff', sizeof(u_int32_t) * NODES * NODES);

perror("new"); exit(1);

}

neighbor_density = new double[2*(((int) MAXTIME/100)+1)];

memset(neighbor_density, 0,

sizeof(u_int32_t)*2*(((int) MAXTIME/100)+1));

/*

* Initialization of the CM graph

* First, parse the file, add each vertex to the * map

*/

ifstream InputFile(INPUTFILE); if(!InputFile) {

perror("Cannot open file"); exit(1); } while(InputFile) { char string[20]; InputFile >> string; if(!strcmp(string,"vertex"))

(6)

{ double x; double y; u_int32_t ind; int b_dest;

InputFile >> ind >> x >> y >> b_dest; if (b_dest==1)

CreateGateway(x,y,VerticesCounter);

/*Define the vertex as destination vertex of the sub-area it is in */ VertexMap.insert(pair<u_int32_t,u_int32_t>(ind,Vert icesCounter)); VertexVector.push_back(Vertex(x,y,ind,VerticesCount er++,b_dest)); Vertex vv = VertexVector[VerticesCounter-1]; #ifdef DEBUG_CM fprintf(stderr,"vertex: %d %.2f %.2f \n",VerticesCounter-1,x,y); #endif } } NumberOfVertices = VertexMap.size(); Connectivity = new bool[NumberOfVertices*NumberOfVertices]; if(Connectivity == 0) { perror("new"); exit(1); } int i,j; for(i=0;i<NumberOfVertices;i++) for(j=0;j<NumberOfVertices;j++) Connectivity[i*NumberOfVertices+j]=false; InputFile.close();

fprintf(stdout, "#File Graph: %d loaded nodes\n",VerticesCounter);

(7)

while(InputFile2) { char string[20]; InputFile2 >> string; if(!strcmp(string,"edge")) { u_int32_t ind1; u_int32_t ind2; u_int32_t ind1mapped; u_int32_t ind2mapped;

InputFile2 >> ind1 >> ind2;

ind1mapped = VertexMap.find(ind1)->second; ind2mapped = VertexMap.find(ind2)->second; Connectivity[ind1mapped*NumberOfVertices+ind2mapped ]=Connectivity[ind2mapped*NumberOfVertices+ind1mapp ed]=true; #ifdef DEBUG_CM fprintf(stderr,"edge: %d %d\n",ind1mapped,ind2mapped); #endif } } InputFile2.close();

fprintf(stdout, "#File Graph: loaded links\n"); PathMatrix = new

Path[NumberOfVertices*NumberOfVertices]; NodeList = new Node[NODES];

if(NodeList == 0) { perror("new"); exit(1);

} }

extern "C" char *optarg;

/*---MAIN---*/

int

main(int argc, char **argv) {

(8)

/* read & process input arguments */

while ((ch = getopt(argc, argv,

"n:r:p:s:S:w:m:t:x:y:f:g:d:i:o:")) != EOF) { switch (ch) { case 'n': NODES = atoi(optarg); break; case 'r': RADIUS = atof(optarg); break; case 'p': PAUSE = atof(optarg); break; case 's': MINSPEED_ = atof(optarg); break; case 'S': MAXSPEED = atof(optarg); break; case 'w': RWPROB_ = atof(optarg); break; case 'm': MAXMOV = atof(optarg); break; case 't': MAXTIME = atof(optarg); break; case 'x': MAXX = atof(optarg);

(9)

break; case 'y': MAXY = atof(optarg); break; case 'f': INPUTFILE = optarg; break; case 'g': IMGNAME = optarg; break; case 'd': DEFSNAME = optarg; break; default: usage(argv); exit(1); } }

if(MAXX == 0.0 || MAXY == 0.0 || NODES == 0 || MAXTIME == 0.0 || MAXSPEED == 0.0 || RADIUS == 0.0) {

usage(argv); exit(1); }

assert(MAXSPEED > MINSPEED_);

fprintf(stdout, "#\n# nodes: %d, pause: %.2f, min speed: %.2f, max speed: %.2f, RW prob: %.2f, max movement: %.2f, max x = %.2f, max y: %.2f\n# input file: %s, image file %s, defs file %s\n#\n",

NODES , PAUSE, MINSPEED_, MAXSPEED, RWPROB_, MAXMOV, MAXX, MAXY, INPUTFILE, IMGNAME, DEFSNAME);

(10)

/*--- Main loop---*/

while(DISC_STEP <= ((int) ceil(MAXTIME/TIME_STEP))) {

double nexttime = 0.0; u_int32_t i;

for(i = 0; i < NODES; i++) { NodeList[i].Update(); }

for(i = 0; i < NODES; i++) { Node *n = &NodeList[i]; if(n->time_arrival > 0.0) { if(nexttime == 0.0) nexttime = n->time_arrival; else nexttime = min(nexttime, n->time_arrival); } } assert(TIME <= nexttime); if (TIME == DISC_TIME) { /* boundary case */ if (DISC_TIME == 0.0) { TIME = min(nexttime,0.0001); DISC_TIME = TIME; continue; } floyd_warshall(); show_diffs(); if (DISC_STEP == next_update) update_neighbors(); DISC_STEP++; DISC_TIME = TIME_STEP*DISC_STEP; } TIME = min(nexttime,DISC_TIME);

(11)

}

show_counters();

/* Show random state */

#ifdef DEBUG int of;

if ((of = open(".rand_state",O_WRONLY | O_TRUNC | O_CREAT, 0777)) < 0) {

fprintf(stderr, "open rand state\n"); exit(-1);

}

for (unsigned int i = 0; i < sizeof(random_state); i++)

random_state[i] = 0xff & (int) (uniform() * 256);

if (write(of,random_state, sizeof(random_state)) < 0) {

fprintf(stderr, "writing rand state\n"); exit(-1); } close(of); #endif } /*---End of Main---*/ /*================================================ Node Class Functions

================================================*/ u_int32_t Node::NodeIndex = 0; Node::Node() { u_int32_t i; index = NodeIndex++; route_changes = 0; link_changes = 0;

(12)

time_arrival = TIME; time_update = TIME; time_transition = 0.0;

position.X = position.Y = position.Z = 0.0; destination.X = destination.Y = destination.Z = 0.0;

direction.X = direction.Y = direction.Z = 0.0;

speed = 0.0;

RandomPosition();

//paused = 1;

//RandomDestination();

fprintf(stdout, NODE_FORMAT3, index, 'X', position.X);

fprintf(stdout, NODE_FORMAT3, index, 'Y', position.Y);

fprintf(stdout, NODE_FORMAT3, index, 'Z', position.Z);

fprintf(stdout, COLOR_FORMAT, index, color);

neighbor = new Neighbor[NODES]; if(neighbor == 0) {

}

for(i = 0; i < NODES; i++) { neighbor[i].index = i; neighbor[i].reachable = (index == i) ? 1 : 0; neighbor[i].time_transition = 0.0; } }

(13)

void

Node::RandomPosition() {

int VertexNumber; do {

VertexNumber = (int) (uniform() * VerticesCounter); current_position = VertexVector[VertexNumber]; } while (current_position.b_destination == 0); #ifdef DEBUG_CM

fprintf(stderr, "Random Position for node %d: %d \n", index, current_position.index);

#endif destination.X=position.X = current_position.X; destination.Y=position.Y = current_position.Y; destination.Z=position.Z = 0.0; custom_vector currpos; currpos.X=position.X=destination.X; currpos.Y=position.Y=destination.Y; currpos.Z=0.0; if (uniform()<=RWProb(currpos)) {randomwalk=true;newstart=false;color="red";} else {randomwalk=false;newstart=true;color="black";} } int Node::RandomDestination() { custom_vector currpos; if (randomwalk) {

/*Random Waypoint Model*/

currpos.X=position.X=destination.X; currpos.Y=position.Y=destination.Y; currpos.Z=0.0;

(14)

if

((uniform()<=RWProb(currpos))||(isTravellingOutside (currpos,Gateway(currpos)))||((currpos.X==Gateway(c urrpos).X)&&(currpos.Y==Gateway(currpos).Y))) {

/*Keeps moving in RWP if: RWProb says so OR if the Destination vertex in not in line of sight OR the node is already on the Dest vertex*/

do { destination.X=currpos.X+uniform()*MAXMOV*2-MAXMOV; destination.Y=currpos.Y+uniform()*MAXMOV*2-MAXMOV; destination.Z=0.0; } while ((destination.X<=0)||(destination.X>=MAXX)||(destin ation.Y<=0)||(destination.Y>=MAXY)|| (isTravellingOutside(currpos,destination))); color="red";

if (PAUSE>0) return 1;else return 0; }

else {

/*Goes to the destination vertex*/

destination.X=Gateway(currpos).X; destination.Y=Gateway(currpos).Y; destination.Z=0; current_position=final_destination=VertexVector[Num Gateway(currpos)]; randomwalk=false; newstart=true; color="blue"; return 0; } } else { if (newstart||path_to_destination.IsEmpty()||path_to_d estination.Finished()) {

/*Follows the graph*/

int VertexNumber; newstart=false;

if (path_to_destination.Finished()) current_position=final_destination;

(15)

do {VertexNumber = (int) (uniform() * VerticesCounter);} while ((VertexNumber==current_position.number)||(!VertexV ector[VertexNumber].b_destination)); final_destination = VertexVector[VertexNumber]; #ifdef DEBUG_CM fprintf(stderr, "Random Destination for node %d: %d \n", index, final_destination.index);

#endif if

(current_position.number==final_destination.number) fprintf(stdout, "Stesso nodo");

path_to_destination =ActivePath(build_path_Dijkstra(current_position,fi nal_destination)); path_to_destination.NextVertex(); if ((path_to_destination.Finished())&&(uniform()<=RWPr ob(currpos))) randomwalk=true; #ifdef DEBUG_CM

fprintf(stderr, "Next Hop for node %d: %d \n", index, path_to_destination.GetPosition().index); #endif destination.X = path_to_destination.GetPosition().X; destination.Y = path_to_destination.GetPosition().Y; destination.Z = 0.0; color="black"; } else { current_position=final_destination; path_to_destination.NextVertex(); if ((path_to_destination.Finished())&&(uniform()<=RWPr ob(currpos))) randomwalk=true; #ifdef DEBUG_CM

(16)

fprintf(stderr, "Next Hop for node %d: %d \n", index, path_to_destination.GetPosition().index); #endif destination.X = path_to_destination.GetPosition().X; destination.Y = path_to_destination.GetPosition().Y; destination.Z = 0.0; color="black"; } } if ((PAUSE>0)&&(path_to_destination.Finished())) return 1;else return 0;

}

void

Node::RandomSpeed() {

speed = (uniform() * (MAXSPEED-MINSPEED_)) + MINSPEED_; assert(speed != 0.0); } void Node::Update() {

position += (speed * (TIME - time_update)) * direction; if(TIME == time_arrival) { custom_vector v; if (paused==1) { speed = 0.0; time_arrival = TIME + uniform()*PAUSE; paused = 0; color="green"; }

(17)

else { paused=RandomDestination(); RandomSpeed(); v = destination - position; direction = v / v.length();

time_arrival = TIME + v.length() / speed;

}

fprintf(stdout, COLOR_FORMAT2, TIME, index, color);

fprintf(stdout, NODE_FORMAT, TIME, index, destination.X, destination.Y, speed); } time_update = TIME; time_transition = 0.0; } /*--- GOD's Functions ---*/ void

ComputeW() /*Checks the connectivity*/

{

u_int32_t i, j; u_int32_t *W = D2;

bool first_time = DISC_STEP == 0;

memset(W, '\xff', sizeof(int) * NODES * NODES);

for(i = 0; i < NODES; i++) {

for(j = i; j < NODES; j++) { if(i == j) W[i*NODES + j] = 0; else W[i*NODES + j] = W[j*NODES + i] = (Pr(NodeList[i].position,NodeList[j].position) > RANGE) ? 1 : INFINITY;

(18)

/* Find if there was a link change */ if ((!first_time)&&(W[i*NODES + j] != D3[i*NODES + j])) { LinkChangeCount++; NodeList[i].link_changes++; NodeList[j].link_changes++; } } }

memcpy(D3, D2, sizeof(int) * NODES * NODES); }

void

floyd_warshall() {

u_int32_t i, j, k;

ComputeW(); /* the connectivity matrix */

for(i = 0; i < NODES; i++) {

for(j = 0; j < NODES; j++) {

for(k = 0; k < NODES; k++) { D2[j*NODES + k] =

min(D2[j*NODES + k], D2[j*NODES + i] + D2[i*NODES + k]);

} }

}

#ifdef SANITY_CHECKS

for(i = 0; i < NODES; i++)

for(j = 0; j < NODES; j++) { assert(D2[i*NODES + j] == D2[j*NODES + i]); assert(D2[i*NODES + j] <= INFINITY); } #endif }

(19)

/*

* Write the actual GOD entries to a TCL script. */

void

show_diffs() {

u_int32_t i, j;

for(i = 0; i < NODES; i++) {

for(j = i + 1; j < NODES; j++) { if(D1[i*NODES + j] != D2[i*NODES + j]) { if(TIME == 0.0) { fprintf(stdout, GOD_FORMAT2, i, j, D2[i*NODES + j]); #ifdef SHOW_SYMMETRIC_PAIRS fprintf(stdout, GOD_FORMAT2, j, i, D2[j*NODES + i]);

#endif }

else {

fprintf(stdout, GOD_FORMAT, TIME, i, j, D2[i*NODES + j]);

#ifdef SHOW_SYMMETRIC_PAIRS

fprintf(stdout, GOD_FORMAT, TIME, j, i, D2[j*NODES + i]);

#endif }

} }

}

memcpy(D1, D2, sizeof(int) * NODES * NODES); }

void

show_counters() {

(20)

double avg_nd = 0.0; double avg_pl = 0.0; int num_pl = 0;

/* Link Changes */

fprintf(stdout, "# Link Changes: %d\n#\n", LinkChangeCount);

fprintf(stdout, "# Node | Link Changes\n"); for(i = 0; i < NODES; i++)

fprintf(stdout, "# %4d | %4d \n",

i, NodeList[i].link_changes);

fprintf(stdout, "#\n");

/* Neighbor Density & Path Length */

fprintf(stdout,"# Average Neighbor density and optimal path length\n");

fprintf(stdout, "# Time | Neighbor Density | Path Length\n");

for (i = 0;i <= ((int) (MAXTIME/100.0));i++) { fprintf(stdout, "# %4d | %.9f | %.9f\n", i*100,neighbor_density[2*i],neighbor_density[ 2*i+1]); avg_nd +=neighbor_density[2*i]; double a = neighbor_density[2*i+1]; if (a != ((double) -1)) { num_pl++; avg_pl += a; } } fprintf(stdout,"# Totals:\n# %.9f | %.9f\n", avg_nd/(((int) (MAXTIME/100.0))+1),avg_pl/num_pl); } void update_neighbors()

(21)

{

int i,j;

int index = (int)

(next_update/ceil(100/TIME_STEP)); int neighbor_count = 0;

int path_length = 0; int path_nums = 0;

next_update += (int) ceil(100/TIME_STEP);

for(i = 0; i < NODES; i++) {

for(j = i + 1; j < NODES; j++) { if(D2[i*NODES + j] != INFINITY) { path_length += D2[i*NODES + j]; path_nums++; } if(D2[i*NODES + j] == 1){ neighbor_count += 2; } } } neighbor_density[2*index] = (double) neighbor_count/NODES; neighbor_density[2*index+1] = (path_nums) ? (double) path_length/path_nums : (double) -1; }

/*================================================ Path Building Functions

================================================*/

Path build_path_Dijkstra(Vertex Origin, Vertex Destination){ Path NewPath = PathMatrix[Origin.number*VerticesCounter+Destinatio n.number]; if (!PathMatrix[Origin.number*VerticesCounter+Destinat ion.number].IsEmpty()){return PathMatrix[Origin.number*VerticesCounter+Destinatio n.number];}

(22)

double costo[VerticesCounter]; int prev[VerticesCounter]; bool fatto[VerticesCounter]; int c; double cost; int min; deque<int> pi[VerticesCounter];

for (int i=0;i<VerticesCounter;i++){costo[i]=-1;fatto[i]=false;}

c=Origin.number; costo[c]=0; prev[c]=c;

for (int m=0;m<VerticesCounter;m++){ fatto[c]=true;

for (int i=0;i<VerticesCounter;i++){ if ((!fatto[i])&&((Connectivity[c*VerticesCounter+i])| |(Connectivity[i*VerticesCounter+c]))){ cost=sqrt(VertexVector[i].X)* (VertexVector[c].X-VertexVector[i].X) + VertexVector[c].Y-VertexVector[i].Y)* (VertexVector[c].Y-VertexVector[i].Y)); /*cost=distance*/

//cost=1; /*cost=1 hop*/

if ((costo[i]<0)||(costo[i]>costo[c]+cost)) {costo[i]=costo[c]+cost;prev[i]=c;}

} } min=-1;

for (int i=0;i<VerticesCounter;i++){ if ((!fatto[i])&&(costo[i]>0)&&((min==-1)||(costo[i]<min))) {min=costo[i];c=i;} } } for (int m=0;m<VerticesCounter;m++){pi[m].push_back(m);} for (int m=0;m<VerticesCounter;m++){

do {pi[m].push_front(prev[pi[m].front()]);} while (pi[m].front()!=Origin.number);

(23)

PathMatrix[Origin.number*VerticesCounter+m]=Path(pi [m]); } PathMatrix[Origin.number*VerticesCounter+Destinatio n.number].DisplayPath(); return PathMatrix[Origin.number*VerticesCounter+Destinatio n.number]; } /*================================================ Path Class Functions

================================================*/ Path::Path(){ } Path::Path(deque<int> arg){ VerticesList=arg; } bool Path::IsEmpty(){ VerticesList.empty(); } Vertex Path::Origin(){ return VertexVector[VerticesList.front()] ; } Vertex Path::Destination(){ return VertexVector[VerticesList.back()] ; } void Path::DisplayPath(){ int i; fprintf(stdout,"#Path from %d to %d :",VerticesList.front(),VerticesList.back());

(24)

for (i=0;i<VerticesList.size();i++)

fprintf(stdout," %d",VerticesList[i]); fprintf(stdout,"\n");

}

/*================================================ ActivePath Class Functions

================================================*/

ActivePath::ActivePath() : Path() { current_position=0;

}

ActivePath::ActivePath(Path arg) : Path() { VerticesList=arg.VerticesList; current_position=0; } void ActivePath::NextVertex(){ current_position++; } Vertex ActivePath::GetPosition(){ return VertexVector[VerticesList[current_position]]; } bool ActivePath::Finished(){ if (current_position==(VerticesList.size()-1)) { return 1;} else return 0; }

(25)

A.2. af_helper_mod.h

/* af_helper_mod.h: header module for the * encapsulation of all the AF propagation * related functions for different flavours of * setdest */ #ifndef __af_helper_h__ #define __af_helper_h__

#include "common.h" /* To get the custom_vector class */

/* AF Functions */

double Pr(custom_vector t, custom_vector r); void loadImg(const char* fname, double width, double height);

void loadDefs(const char* fname, double prob);

/* Shell functions */

void loadShell(const char *fname, double width, double height);

bool isTravellingOutside(custom_vector t, custom_vector r);

bool isPosOutside(custom_vector position);

/* COMBINED functions */

void CreateGateway(double x,double y, u_int32_t VC);

custom_vector Gateway(custom_vector posiz); u_int32_t NumGateway(custom_vector posiz); double RWProb(custom_vector posiz);

class Vertex { public:

int b_destination; double X;

(26)

u_int32_t index; u_int32_t number;

Vertex(double x = 0.0, double y = 0.0,u_int32_t ind = 0,u_int32_t num = 0,int b_dest = 0) {

X = x; Y = y; index = ind; number = num; b_destination = b_dest;

}

};

#endif

A.3. af_helper_mod.cc

/* af_helper_mod.cc: this module encapsulates * all the AF propagation related functions for * different flavours of setdest

*/

//#define DEBUG_AF

#include "af_helper_mod.h" #include <fstream>

/* AF vars */

unsigned char *pixel; // Bitmap pixels

int imgWidth, imgHeight; // Image pixel measures

double ppmWidth, ppmHeight; // Ratios between the two above

int whiteNum; // White Colour

codification for this bitmap

/* AF params; d0 is hardwired to 1 */

int MaterialsCount,NumOfSolids; double Pd0;

double esp;

(27)

unsigned char *rgb = 0;

/* AF Functions */

double Pr(custom_vector t, custom_vector r); void loadImg(const char* fname, double width, double height);

void loadDefs(const char* fname, double prob); int *getWallCount(double xt, double yt, double xr, double yr);

/* Shell functions */

void loadShell(const char *fname, double width, double height);

bool isTravellingOutside(custom_vector t, custom_vector r);

bool isPosOutside(custom_vector position);

/* COMBINED params and functions */

Vertex *listagateway; double *rwprob;

void CreateGateway(double x,double y, u_int32_t VC);

custom_vector Gateway(custom_vector posiz); u_int32_t NumGateway(custom_vector posiz); double RWProb(custom_vector posiz);

/*================================================ AF Functions

================================================*/

double Pr(custom_vector t, custom_vector r) {

int i, *wallCount; double att = 0.0;

#ifdef DEBUG_AF

(28)

fprintf(stderr,"DANGER\n"); #endif

/* Get wall count between T/R, and corresponding attenuation.

Afterwards, release memory. */

wallCount = getWallCount(t.X, t.Y, r.X, r.Y); for(i=0;i<MaterialsCount;i++)

att += attenuation[i]*wallCount[i]; delete wallCount;

/* Calculate the power */

return Pd0 - 10 * esp * log10((t-r).length()/10) - att;

}

void loadDefs(const char* fname, double prob) {

int i;

ifstream defs(fname);

if (defs.fail()) { fprintf(stderr,"Bad Definitions File!!!"); exit(1); }

defs >> Pd0 >> esp >> MaterialsCount >> NumOfSolids;

#ifdef DEBUG_AF

fprintf(stderr,"%f %f %d %d %d \n",Pd0,n,MaterialsCount,NumOfSolids);

#endif

attenuation = new double[MaterialsCount]; rwprob = new double[MaterialsCount];

listagateway = new Vertex[MaterialsCount]; rgb = new unsigned char[MaterialsCount*3]; unsigned int r,b,g;

for(i=0;i<MaterialsCount;i++) {

(29)

{defs >> attenuation[i] >> r >> g >> b;} else { defs >> attenuation[i] >> r >> g >> b >> rwprob[i]; if (prob<=1) rwprob[i]=prob; }

rgb[i*3] = (unsigned char) r; rgb[i*3+1] = (unsigned char) g; rgb[i*3+2] = (unsigned char) b; #ifdef DEBUG_AF fprintf(stderr,"%f %d %d %d\n",attenuation[i],rgb[i*3],rgb[i*3+1],rgb[i*3+2] ); #endif } }

void loadImg(const char* fname, double width, double height)

{

#ifdef DEBUG_AF FILE *f; #endif

ifstream image( fname );

char magicNumber[3]; char comment[256]; char terminator, r, b, g; unsigned char a; #ifdef DEBUG_AF f = fopen("view","w"); #endif

if( image.fail() ) { printf("image bad!\n"); exit(1); }

if( strstr( fname, ".pnm" ) ) { image >> magicNumber;

(30)

image >> imgWidth >> imgHeight; /* >> whiteNum; */

image >> whiteNum; image.get( terminator );

/* UNTESTED */

} else if( strstr( fname, ".pgm" ) ) { image >> magicNumber;

image.get( terminator );

image >> imgWidth >> imgHeight /* >> whiteNum; */

}

ppmWidth = (double) ((double)imgWidth / (double)width);

ppmHeight = (double) ((double)imgHeight / (double)height); #ifdef DEBUG_AF fprintf(f,"%d %d | %f %f | %f %f\n\n",imgWidth,imgHeight,width,height,ppmWidth,pp mHeight); #endif

pixel = new unsigned char[imgWidth * imgHeight]; for(int n = 0; n < imgHeight; n++) { for(int m = 0; m < imgWidth; m++) { image.get( r ); image.get( g ); image.get( b ); for(a=0;a<MaterialsCount;a++) if ((((unsigned char) r)==rgb[a*3])&&(((unsigned char)

g)==rgb[a*3+1])&&(((unsigned char) b)==rgb[a*3+2])) break; pixel[m + n * imgWidth] = a; #ifdef DEBUG_AF fprintf(f,"%d",a); #endif } #ifdef DEBUG_AF fprintf(f,"\n"); #endif

(31)

} image.close(); #ifdef DEBUG_AF fclose(f); #endif }

int *getWallCount(double xt, double yt, double xr, double yr)

{

unsigned char pix, lastPix;

int *wallCount = new int[MaterialsCount]; memset(wallCount, 0, sizeof(int) *

MaterialsCount);

/* Get the coordinates in pixels */

int xOrig = (int) (xt*ppmWidth); double xPixel = (double) xOrig; int yOrig = (int) (yt*ppmHeight); double yPixel = (double) yOrig; int xDest = (int) (xr*ppmWidth); int yDest = (int) (yr*ppmHeight);

/* Get the pixel distance for each axis */

int dx = xDest-xOrig; int dy = yDest-yOrig;

/* Get the ratios */

int max = (abs(dx)>abs(dy)?abs(dx):abs(dy)); double xRatio = (double) dx/max;

double yRatio = (double) dy/max;

#ifdef DEBUG_AF printf("xO %d xD %d xR %f\n",xOrig,xDest,xRatio); printf("yO %d yD %d yR %f\n",yOrig,yDest,yRatio); #endif

(32)

for (int it=0;it<max;it++) {

pix = pixel[xOrig + (yOrig) * imgWidth]; if (pix != lastPix) { if(pix < MaterialsCount) { wallCount[pix]++; #ifdef DEBUG_AF printf("x:%d,y:%d\n",xOrig,yOrig); #endif } lastPix = pix; }

xPixel += xRatio; yPixel += yRatio; xOrig = (int) xPixel; yOrig = (int) yPixel; #ifdef DEBUG_AF printf("xO %d: yO %d\n",xOrig,yOrig); #endif } return wallCount; } /*================================================ Shell Functions ================================================*/

void loadShell(const char *fname, double width, double height)

{

/* All of this is 'hardwired': the 'exterior' is set to red */

MaterialsCount = 1;

rgb = new unsigned char[3]; rgb[0] = 255;

rgb[1] = 0; rgb[2] = 0;

loadImg(fname,width,height); }

(33)

bool isPosOutside(custom_vector position) {

// Get the coordinates in pixels

int xOrig = (int) (position.X*ppmWidth); int yOrig = (int) (position.Y*ppmHeight); return (pixel[xOrig + (yOrig) * imgWidth] < NumOfSolids);

}

bool isTravellingOutside(custom_vector t, custom_vector r)

/* Horrid cut&paste, only to optimize performance */ { double xt = t.X; double yt = t.Y; double xr = r.X; double yr = r.Y;

unsigned char pix, lastPix;

/* Get the coordinates in pixels */

int xOrig = (int) (xt*ppmWidth); double xPixel = (double) xOrig; int yOrig = (int) (yt*ppmHeight); double yPixel = (double) yOrig; int xDest = (int) (xr*ppmWidth); int yDest = (int) (yr*ppmHeight);

/* Get the pixel distance for each axis */

int dx = xDest-xOrig; int dy = yDest-yOrig;

int max = (abs(dx)>abs(dy)?abs(dx):abs(dy)); if (max==0) return 0;

pix = pixel[xOrig + (yOrig) * imgWidth]; for (int it=0;it<=max;it++) {

double itdx = double (it*dx); double itdy = double (it*dy);

(34)

lastPix=pixel[(int)(xOrig+(itdx/max))+(int)(yOrig+( itdy/max)) * imgWidth]; if (pix != lastPix) { if(lastPix < NumOfSolids) { #ifdef DEBUG_AF printf("x:%d,y:%d\n",xOrig,yOrig); #endif return true; } } #ifdef DEBUG_AF printf("xO %d: yO %d\n",xOrig,yOrig); #endif } return false; } /*================================================ COMBINED Functions (Gateway=Destination Vertex) ================================================*/

void CreateGateway(double x,double y, u_int32_t VC) {

int xOrig = (int) (x*ppmWidth); int yOrig = (int) (y*ppmHeight); listagateway[pixel[(xOrig + (yOrig) * imgWidth)]].X=x; listagateway[pixel[(xOrig + (yOrig) * imgWidth)]].Y=y; listagateway[pixel[(xOrig + (yOrig) * imgWidth)]].number=VC; }

custom_vector Gateway(custom_vector posiz) {

custom_vector dest;

int xOrig = (int) (posiz.X*ppmWidth); int yOrig = (int) (posiz.Y*ppmHeight);

(35)

dest.X=listagateway[pixel[(xOrig + (yOrig) * imgWidth)]].X; dest.Y=listagateway[pixel[(xOrig + (yOrig) * imgWidth)]].Y; dest.Z=0; return dest; }

u_int32_t NumGateway(custom_vector posiz) {

u_int32_t dest;

int xOrig = (int) (posiz.X*ppmWidth); int yOrig = (int) (posiz.Y*ppmHeight); dest=listagateway[pixel[(xOrig + (yOrig) * imgWidth)]].number;

return dest; }

double RWProb(custom_vector posiz) {

int xOrig = (int) (posiz.X*ppmWidth); int yOrig = (int) (posiz.Y*ppmHeight);

return rwprob[pixel[(xOrig + (yOrig) * imgWidth)]]; }

A.4. setdest_cm_mod.h

/* setdest_cm_mod.h: modified header module for the setdest_cm and related programs

*/ #ifndef __setdest_cm_h__ #define __setdest_cm_h__ #include <map> #include <list> #include "common.h" #include "af_helper_mod.h"

(36)

//moved to af_helper_mod.h

/* Adding a path class */

class Path { public: deque<int> VerticesList; Path(void); Path(deque<int>); Vertex Origin(); Vertex Destination(); void DisplayPath(); bool IsEmpty(); };

class ActivePath: public Path{ public: int current_position; ActivePath(void); ActivePath(Path); void NextVertex(); Vertex GetPosition(); bool Finished(); }; class Node {

friend void ReadInMovementPattern(void); public: Node(void); void Update(void); void UpdateNeighbors(void); void Dump(void); int paused; Vertex current_position; Vertex final_destination; ActivePath path_to_destination;

double time_arrival; //time of

arrival at dest

double time_transition; //min of all neighbor times

(37)

bool randomwalk; bool newstart;

// num of optimal route changes for this node

int route_changes; int link_changes;

custom_vector position; //current position

private:

void RandomPosition(void); int RandomDestination(void); void RandomSpeed(void);

u_int32_t index; //unique node identifier

custom_vector destination;

//destination

custom_vector direction;

//computed from pos and dest

double speed;

double time_update; //when

pos last updated

static u_int32_t NodeIndex;

LIST_HEAD(traj, setdest) traj;

public:

// An array of NODES neighbors.

Neighbor *neighbor; };

(38)

A.5. INPUT FILES

The software loads three files: the image of the map of the

obstacles; the file that defines the material properties of the

obstacles; and the file that contains the pathways graph.

A.5.1. Image File

The file is a normal image in PNM format. Every colour is

associated to a different material/sub-area (see Paragraph 3.3).

A.5.2. Define File

The file contains a first line with the following parameters:

• P

0

: the signal power at a reference distance r

0

.

• n: the path loss exponent.

• σ

: the total number of materials (colours).

• s: the number of solid materials (materials that stop the

movement of the nodes).

The other

σ

lines contain the properties of each material as

follows:

• PF

i

: the attenuation factor of the material i.

• R G B: the colour associated to that material.

(39)

• rw: the parameter rw associated to the sub-area (this

parameter is present only if the material is crossable).

The total attenuation factor at a distance r is then calculated as:

(

1

)

0

( )

0 10 1 0

,

,...,

10 log

AF i i i

r

P

r m

m

P r

n

m PF

r

σ σ =





=

−





−

⋅





∑

where m

i

is the number of times the line of sight collides with

the material i.

For example, the Define File of the map 2 (see Fig. 4.2) is:

-31.4627 1.96651 8 1 4.7727 0 0 0 0.0 255 128 255 0.5 0.0 255 255 128 0.5 0.0 255 128 128 0.5 0.0 128 255 128 0.5 0.0 128 128 255 0.5 0.0 128 255 255 0.5 0.0 255 255 255 0.5

As you can see, the first material is black (RGB=0,0,0) and

attenuates with a factor 4.7727. Since the material is solid, the

rw parameter is not present in its line. The other seven

materials do not attenuate (af=0.0) and have rw=0.5.

(40)

A.5.3. Graph File

The file contains the list of all the vertices of the graph as

follows:

• vertex: word that identifies a vertex definition.

• n: ID number of the vertex.

• X Y: the coordinates of the vertex in the map.

The links between two vertices are defined as follows:

• Edge: word that identifies a link.

• A B: the ID number of the two vertices.

For example, the Graph File of the map 2 is:

vertex 1 564.0 666.0 0 vertex 2 108.0 582.0 1 vertex 3 360.0 582.0 0 vertex 4 690.0 546.0 1 vertex 5 570.0 462.0 1 vertex 6 108.0 408.0 1 vertex 7 264.0 324.0 0 vertex 8 360.0 324.0 1 vertex 9 288.0 240.0 0 vertex 10 360.0 240.0 0 vertex 11 444.0 240.0 0 vertex 12 360.0 156.0 0 vertex 13 138.0 66.0 1 vertex 14 648.0 54.0 1 edge 1 4 edge 1 3 edge 3 8

(41)

edge 8 10 edge 10 12 edge 12 14 edge 5 11 edge 11 10 edge 10 9 edge 9 13 edge 8 7 edge 6 7 edge 2 3