strict_distance_10.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 500		/* 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 PI 3.14159265
#define DISTANCE_FILE "strict_distance_10.out"


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 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;
    int disconnected_num;
    
    char trust[NODE_NUM][NODE_NUM];
    
    FILE *fp;
    
    int link_num[20], trust_link_num[20];

    /* initilize */
    node_num = NODE_NUM;
    
    /* 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);
    
    fp = fopen(DISTANCE_FILE, "w");
    
    for (i = 0; i < 20; i++) {
	    link_num[i] = 0;
	    trust_link_num[i] = 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 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 = (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 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;
			
		    /* 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++;
	    	    link_num[(int)(distance(node[i], node[list1->node->id]) / 3.6)]++;
	    	    if (trust[i][list1->node->id] == 1) {
	    	        trust_neighbor_num++;
	    	        trust_link_num[(int) (distance(node[i], node[list1->node->id]) / 3.6)]++;
	    	    }
	    	}
	    	
	    avg_neighbor_num += (float)neighbor_num / node_num;
	    avg_trust_neighbor_num += (float)trust_neighbor_num / node_num;
	    
	}
	        
        for (i = 0; i < 20; i++) 
            printf(" %.1f-%.1f, %.2f\n", i*3.6, (i+1)*3.6, (float)trust_link_num[i] / link_num[i] * 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;
	    	}
	}

    }
    
    fprintf(fp, "%.2f\t%.4f\n", 0.0, 1.0);
    for (i = 0; i < 20; i++)
    	fprintf(fp, "%.2f\t%.4f\n", (float)(i+1) / 20, (float)trust_link_num[i] / link_num[i]);
    	
    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;

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