strict_offset_3.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 X_RANGE 500		/* The X Range of Terrain Area */
#define Y_RANGE 500		/* The Y Range of Treeain Area */
#define NODE_NUM 150		/* 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 100		/* simulation times */
#define GUARD_THRESHOLD 1	/* The threshold number of guard nodes */
#define OFFSET          60	/* The maximum offset */
#define PI 3.14159265


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 */
    float angle;		/* the offset of orientation */
    struct NODE_LIST *neighbor; /* node's neighbor list */
    struct NODE_LIST *directional_neighbor[ANTENNA_NUM]; /* node's directional neighbor list */
} node[NODE_NUM];

/* 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);


int main()
{
       	
    int i, j, d;
    int iteration;
    struct NODE_LIST *neighbor_list, *list1, *list2;
    int id, has_guard[ANTENNA_NUM];
    int node_num, neighbor_num, trust_neighbor_num;			
    float density, directional_density;
    float avg_neighbor_num, avg_trust_neighbor_num;
    float avg_result1, avg_result2;
    int disconnected_num;
    int offset;
    
    char trust[NODE_NUM][NODE_NUM];
    
    FILE *fp;

    /* initilize */
    node_num = NODE_NUM;
    fp = fopen("strict_offset_3.out", "w");
for (offset = 0; offset <= OFFSET; offset += 5)   {
    avg_result1 = 0;
    avg_result2 = 0; 
    /* 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);
    
    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].angle = -offset + (float)2 * offset * 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 neighbor list and directional neighbor list of nodes */
    	for ( i = 0; i < node_num; i++) 
	    for ( j = i+1; j < node_num; j++) {
	    	
	    	/* neighbor list */
	    	if ( distance(node[i], node[j]) < RADIO_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 */			
		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 = direction(node[j], node[i]);
		    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 variables */
    	for (i = 0; i < node_num; i++)
    	    for (j = 0; j < node_num; j++)
    	    	trust[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;
		    
		    if (direction(node[id], node[i]) != (d+3)%6)
		    {
		        trust[id][i] = 0;
		        continue;
		    }
			
		    /* 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) && (direction(node[i], node[list2->node->id]) != (d+1) % 6) && (direction(node[i], node[list2->node->id]) != (d+5) % 6) ) {    	
			    	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) && (direction(node[i], node[list2->node->id]) != (d+1) % 6) && (direction(node[i], node[list2->node->id]) != (d+5) % 6) ) {    	
			    	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;
			    }
			    
		 /* try 5th direction */
		    if (has_guard[d] == 0)
		    	for (list2 = node[id].directional_neighbor[d]; 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;
			
		} 
		
	    }		
	}
	
	 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;
	        }
	       }
		    
	avg_neighbor_num = 0;
	avg_trust_neighbor_num = 0;
	disconnected_num = 0;
	for (i = 0; i < node_num; i++) {
	    neighbor_num = 0;
	    trust_neighbor_num = 0;
	    for (d = 0; d < 6; d++)
	    	for (list1 = node[i].directional_neighbor[d]; list1 != NULL; list1 = list1->next) {
	    	    neighbor_num++;
	    	    if (trust[i][list1->node->id] == 1)
	    	        trust_neighbor_num++;
	    	}
	    	
	    avg_neighbor_num += (float)neighbor_num / node_num;
	    avg_trust_neighbor_num += (float)trust_neighbor_num / node_num;
	    
	    if ( (trust_neighbor_num < neighbor_num) && (trust_neighbor_num == 0 ))
	    	disconnected_num++;
	
	    	
	  
	}
	
	
	avg_result1 += avg_trust_neighbor_num / avg_neighbor_num / ITERATION;
	avg_result2 += (float)disconnected_num / node_num / ITERATION;
	
        printf(" In iteration %d, average link ratio is  %.2f%%, node disconnected ratio is %.2f%%\n",  iteration+1, (float)avg_trust_neighbor_num / avg_neighbor_num * 100, (float)disconnected_num / node_num * 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;
	    	}
	}

    }
    
    printf("The average for offset=%d is link %.2f%%, disconnected %.2f%%\n\n", offset, avg_result1 * 100, avg_result2 * 100);
    fprintf(fp, "%d\t%.4f\t%.4f\n", offset, 1-avg_result1, avg_result2);   
    
}
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));
}	


int direction(struct NODE n1, struct NODE n2)
{
    float x, y, d, sin_value;
    double newx, newy;

    /* compute the cos of angle */
    y = n2.y - n1.y;
    x = n2.x - n1.x;
    
    /* Then new coordinate of n2 according to n1 */
    newx = x*cos((double)PI/180*n1.angle) + y * sin((double)PI/180*n1.angle);
    newy = x*sin((double)PI/180*n1.angle) - y * cos((double)PI/180*n1.angle);
    
    d = sqrt((n1.x - n2.x) * (n1.x - n2.x) + (n1.y - n2.y) * (n1.y - n2.y));
    sin_value = newy/d;

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