path_length.c

This code was used to produce simulation results described in: Using Directional Antennas to Pre

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define PROTOCOL 1		/* 0 denotes verified protocol, 1 denotes strict protocol */
#define X_RANGE 500		/* The X Range of Terrain Area */
#define Y_RANGE 500		/* The Y Range of Treeain Area */
#define NODE_NUM 1000		/* The number of sensor nodes */
#define ANTENNA_NUM 6		/* The number of antennas one node has */
#define RADIO_RANGE 40		/* The transmission range of omni antenna */
#define DIRECTIONAL_RANGE  72   /* The transmission range of directional antenna */
#define ITERATION 10		/* simulation times */
#define PI 3.14159265
#define VERIFIED_LENGTH_FILE "verified_path_length.out" /* The path length file for verified protocol */
#define STRICT_LENGTH_FILE "strict_path_length.out"	/* The path length file for strict protocol */




struct NODE_LIST
{
    struct NODE *node;
    struct NODE_LIST *next;
};

struct NODE
{
    float x;			/* the x pixel of node*/		
    float y;			/* the y pixel of node */
    int id;			/* the ID of node */
    struct NODE_LIST *neighbor; /* node's directional neighbor list (as a whole) */
    struct NODE_LIST *directional_neighbor[ANTENNA_NUM]; /* node's directional neighbor list (in each direction) */
} node[NODE_NUM];

char trust[NODE_NUM][NODE_NUM];		/* If node i trust j */
int hops[NODE_NUM][NODE_NUM];		/* The hop distance from node i to j */
int trust_hops[NODE_NUM][NODE_NUM];	/* The trusted hop distance from node i to j */


/* This function defines the distance from node n1 to node n2 */
float distance (struct NODE n1, struct NODE n2);

/* This function defines the direction that node n2 to n1 */
int direction(struct NODE n1, struct NODE n2);

/* This function defines the minimal hop distance from node i to other nodes */
void min_hop (int i);

/* This funiction defines the minimal trusted hop distance from node i to other nodes */
void min_trust_hop (int i);

int main()
{
       	
    int i, j, d, id;
    int iteration;
    struct NODE_LIST *neighbor_list, *list1, *list2;	
    int has_guard[ANTENNA_NUM];				/* If verifier exitsts in the direction (according to announcer) */
    int node_num;					/* The number of nodes */
    float density, directional_density;			/* The network density */
    int total_pairs, total_trust_pairs;			/* The number of links */
    float avg_hops, avg_trust_hops;			/* The average hops length of all links in one iteration */
    float final_avg_hops, final_avg_trust_hops;		/* The average hops length of all iterations */
    
    FILE *fp;

    /* initilize */
    node_num = NODE_NUM;
    
    if (PROTOCOL == 0) // The verified protocol 
    	fp = fopen(VERIFIED_LENGTH_FILE, "w");
    else
    	fp = fopen(STRICT_LENGTH_FILE, "w");
    

for (node_num = 200; node_num <= 1000; node_num += 100) {
    
    /* Estsimated density and directional density */
    density = PI*RADIO_RANGE*RADIO_RANGE*node_num/X_RANGE/Y_RANGE;
    directional_density = PI*DIRECTIONAL_RANGE*DIRECTIONAL_RANGE*node_num/X_RANGE/Y_RANGE;
    printf("network density is %.2f, directional network density is %.2f\n", density, directional_density);
    
    /* Initiliaze the average hop length */
    final_avg_hops = 0;
    final_avg_trust_hops = 0;
    
    
    for (iteration = 0; iteration < ITERATION; iteration++) {    
	
	printf("start iteration %d......\n", iteration + 1);
	    
	/* initilize the position of randomly distributed nodes */
        for ( i = 0; i < node_num; i++) {
            node[i].x = (float)X_RANGE * rand() / RAND_MAX;
	    node[i].y = (float)Y_RANGE * rand() / RAND_MAX;
	    node[i].neighbor = NULL;
	    for (d = 0; d < 6; d++)
	        node[i].directional_neighbor[d] = NULL;
	    node[i].id = i;
	     
        }	
	    
    
    	/* initilize the directional neighbor list (in a whole and for each direction) */
    	for ( i = 0; i < node_num; i++) 
	    for ( j = i+1; j < node_num; j++) {
	    	
	    	/* directional_neighbor list (in a whole) */
	    	if ( distance(node[i], node[j]) < DIRECTIONAL_RANGE ) {
		    neighbor_list = malloc(sizeof(struct NODE_LIST));
		    neighbor_list->node = &node[j];	
		    neighbor_list->next = node[i].neighbor;
		    node[i].neighbor = neighbor_list;
		
		    neighbor_list = malloc(sizeof(struct NODE_LIST));
		    neighbor_list->node = &node[i];
		    neighbor_list->next = node[j].neighbor;
		    node[j].neighbor = neighbor_list;
	      
	    	} 

		/* directional neighbor list (for each direction) */			
		if ( distance(node[i], node[j]) < DIRECTIONAL_RANGE ) {
			
		    d = direction(node[i], node[j]);
		    neighbor_list = malloc(sizeof(struct NODE_LIST));
		    neighbor_list->node = &node[j];	
		    neighbor_list->next = node[i].directional_neighbor[d];
		    node[i].directional_neighbor[d] = neighbor_list;
		
		    d = (d + 3) % 6;
		    neighbor_list = malloc(sizeof(struct NODE_LIST));
		    neighbor_list->node = &node[i];
		    neighbor_list->next = node[j].directional_neighbor[d];
		    node[j].directional_neighbor[d] = neighbor_list;
	      
	    	} 
	    }
	  
    	/* initilize the trust and hop length arrarys */
    	for (i = 0; i < node_num; i++)
    	    for (j = 0; j < node_num; j++) {
    	    	trust[i][j] = 1;
    	    	if (i == j) {
    	    	    hops[i][j] = 0;
    	    	    trust_hops[i][j] = 0;
    	    	}
    	    	else {
    	    	    hops[i][j] = -1;
    	    	    trust_hops[i][j] = -1;
    	    	}
   	    }

	
	for (i = 0; i < node_num; i++) { /* For each sensor nodes */
	
	    /* Initilize the array */
	    for (d = 0; d < 6; d++) 
		has_guard[d] = 0;
	    	
   	    for (d = 0; d < 6; d++) { /* For each direction */
		    
		/* Condition 1, no node in this direction of wormhole so the attack is not meaningful */
		if (node[i].directional_neighbor[d] == NULL) {
		    has_guard[d] = 1;
		    continue;
		}
		
		/* Conditon 2, at least one node in other direction can detect anomaly */
		for (list1 = node[i].directional_neighbor[d]; list1 != NULL; list1 = list1->next) {
		    id = list1->node->id;
		    has_guard[d] = 0;
			
		    /* try 1st direction */
		    for (list2 = node[id].directional_neighbor[(d+1)%6]; list2 != NULL; list2 = list2->next) 
			if ( (i != list2->node->id) && (distance(node[list2->node->id], node[i]) < DIRECTIONAL_RANGE) && (direction(node[i], node[list2->node->id]) != d)) {    	
			    has_guard[d] = 1;
			    if (has_guard[d] == 1)
				break;
			}
			
		    /* try 2nd direction */
		    if (has_guard[d] == 0)
		    	for (list2 = node[id].directional_neighbor[(d+2)%6]; list2 != NULL; list2 = list2->next) 
			    if ( (i != list2->node->id) && (distance(node[list2->node->id], node[i]) < DIRECTIONAL_RANGE) && (direction(node[i], node[list2->node->id]) != d) ) {    	
			    	if ( (PROTOCOL == 1) && ( (direction(node[i], node[list2->node->id]) == (d+1) % 6) || (direction(node[i], node[list2->node->id]) == (d+5) % 6)))
			    	    continue;
			    	has_guard[d] = 1;
			    	if (has_guard[d] == 1)
				    break;
			    }
			    
		    /* try 3rd direction */
		    if (has_guard[d] == 0)
		    	for (list2 = node[id].directional_neighbor[(d+4)%6]; list2 != NULL; list2 = list2->next) 
			    if ( (i != list2->node->id) && (distance(node[list2->node->id], node[i]) < DIRECTIONAL_RANGE) && (direction(node[i], node[list2->node->id]) != d) ) {    	
			    	if ( (PROTOCOL == 1) && ( (direction(node[i], node[list2->node->id]) == (d+1) % 6) || (direction(node[i], node[list2->node->id]) == (d+5) % 6)))
			    	    continue;
			    	has_guard[d] = 1;
			    	if (has_guard[d] == 1)
				    break;
			    }
			    
		    /* try 4th direction */
		    if (has_guard[d] == 0)
		    	for (list2 = node[id].directional_neighbor[(d+5)%6]; list2 != NULL; list2 = list2->next) 
			    if ( (i != list2->node->id) && (distance(node[list2->node->id], node[i]) < DIRECTIONAL_RANGE) && (direction(node[i], node[list2->node->id]) != d)) {    	
			    	has_guard[d] = 1;
			    	if (has_guard[d] == 1)
				    break;
			    }
		
		    if (has_guard[d] == 0) 
			trust[id][i] = 0;
			
		} 
		
	    }		
	}
	
	/* Ensure bi-directional trust */
	for (i = 0;i < node_num; i++)
	    for (j = 0; j < node_num; j++) {
	    	if ( (trust[i][j] == 1) || (trust[j][i] == 1) ) {
	            trust[i][j] = 1;
	            trust[j][i] = 1;
	        }
	       }
	
	/* Calculate hop length for each node */
	for (i = 0; i < node_num; i++) {
	    min_hop(i);
	    min_trust_hop(i);
	}



	total_pairs = 0;
	total_trust_pairs = 0;
	avg_hops = 0;
	avg_trust_hops = 0;
	
	/* Calculate the average hop length */
	for (i = 0; i < node_num; i++)
	    for (j = i+1; j < node_num; j++) {
	    	if (hops[i][j] > 0) {
	    	    total_pairs++;
	    	    avg_hops += hops[i][j];
	    	}
	    	
	    	if (trust_hops[i][j] > 0) {
	    	    total_trust_pairs++;
	    	    avg_trust_hops += trust_hops[i][j];
	    	}
	   }
	    	    
	avg_hops /= total_pairs;
	avg_trust_hops /= total_trust_pairs;
	final_avg_hops += avg_hops;
	final_avg_trust_hops += avg_trust_hops;
	
	/* Print result */
	printf(" In interation %d...\n", iteration + 1);
	printf("avg hops is %.2f [%d links], avg trust hops is %.2f [%d links], hop length increases %.2f%%\n\n", avg_hops, total_pairs, avg_trust_hops, total_trust_pairs, (avg_trust_hops - avg_hops) / avg_hops * 100);
	           
    	/* free the key_list and neighbor_list */
    	for ( i = 0; i < node_num; i++) {
	    for (list1 = node[i].neighbor; list1!=NULL; ) {
		list2 = list1->next;
		free(list1);
		list1 = list2;
	    }

	    for (d = 0; d < 6; d++)
		for (list1 = node[i].directional_neighbor[d]; list1 != NULL; ) {
		    list2 = list1->next;
		    free(list1);
		    list1 = list2;
	    	}
	}

	
    
    }
	
    final_avg_hops /= ITERATION;
    final_avg_trust_hops /= ITERATION;
    fprintf(fp, "%d\t%.2f\t%.2f\n", (int)(density + 0.5), final_avg_hops, final_avg_trust_hops);
    printf("Final avg hops is %.2f, final avg trust hops is %.2f, increase is %.2f%%\n\n", final_avg_hops, final_avg_trust_hops, (final_avg_trust_hops - final_avg_hops) / final_avg_hops * 100);
}
fclose(fp);
    
    exit(0);
}

/* This function defines the distance from node n1 to node n2 */
float distance (struct NODE n1, struct NODE n2)
{
    return sqrt((n1.x - n2.x) * (n1.x - n2.x) + (n1.y - n2.y) * (n1.y - n2.y));
}	

/* This function defines the direction that node n2 to n1 */
int direction(struct NODE n1, struct NODE n2)
{
    float x, y, d, sin;

    /* compute the cos of angle */
    y = n2.y - n1.y;
    x = n2.x - n1.x;
    d = sqrt((n1.x - n2.x) * (n1.x - n2.x) + (n1.y - n2.y) * (n1.y - n2.y));
    sin = y/d;

    if ( (sin >= -0.5) && (sin <= 0.5) ) {
    	if (x > 0) return 0;
    	else return 3;
    }
    else if ( (sin >= 0.5) && (sin <= 1 ) ){
    	if (x > 0) return 1;
    	else return 2;
    }
    else {
    	if (x > 0) return 5;
    	else return 4;
    }    	 
   
}

/* This function defines the minimal hop distance from node i to other nodes */
void min_hop (int i)
{
    int queue[NODE_NUM + 1];		/* The queue used for breadth first search */
    int queue_head, queue_tail;		/* The head and tail of queue */
    struct NODE_LIST *list;
    int j, k;
    
    queue_head = 0;
    queue_tail = 0;
    queue[0] = i;
	    
    while (queue_head <= queue_tail) {
    	j = queue[queue_head];
    	queue_head++;
    	for (list = node[j].neighbor; list != NULL; list = list->next) {
            k = list->node->id;
            if (hops[i][k] < 0) {
            	hops[i][k] = hops[i][j] + 1;
            	queue_tail++;
            	queue[queue_tail] = k;
            }
            //printf("j = %d, hops[%d][%d] is %d\n", j, i, k, hops[i][k]);
    	}
    	
    }
    
    return;
}

/* This function defines the minimal trust hop distance from node i to other nodes */
void min_trust_hop (int i)
{
    
    int queue[NODE_NUM + 1];		/* The queue used for breadth first search */
    int queue_head, queue_tail;		/* The head and tail of queue */
    struct NODE_LIST *list;
    int j, k;
    
    queue_head = 0;
    queue_tail = 0;
    queue[0] = i;
	    
    while (queue_head <= queue_tail) {
    	j = queue[queue_head];
    	queue_head++;
    	for (list = node[j].neighbor; list != NULL; list = list->next) {
            k = list->node->id;
            if ( trust[j][k] && (trust_hops[i][k] < 0) ) {
            	trust_hops[i][k] = trust_hops[i][j] + 1;
            	queue_tail++;
            	queue[queue_tail] = k;
            }
            //printf("j = %d, hops[%d][%d] is %d\n", j, i, k, trust_hops[i][k]);
    	}
    	
    }
    
    return;
}