Subject: [manet] How to calculate the average node degree and the average hop count?

From: "zhang zhi" <[email-masked]>
Date: Sun, 30 Apr 2006 16:37:32 +0800

Hi ,all
     How to calculate the average node degree( or the average number of
neighbor ) and the average hop count
in the ad hoc network?
     In following scenario, in a field of 250m*250m random place 50 nodes,
each node have a communication range of 70m, how to calculate the average
node degree(average number of neighbor)? how about the average hop count
between every node?
     Thanks, waiting for reply!

Zhangzhi

--
Zhang Zhi       PhD Candidate
Northwesten Polytechnical University    College of Automation
Email: [email-masked]
          [email-masked]
_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: Bachar WEHBI <[email-masked]>
Date: Sun, 30 Apr 2006 15:36:36 +0200

Hi Zhang,

I used a C program (see below) that generates random graphs and computes the
connectivity, average nb of neighbors, average hop count...
these parameters are computed between all the nodes in the network and an
"access point" placed at the center of the network! this can be easily relaxed
by making some slight modifications to the code.
hope this will help you!
Bachar

/********************************************************************/

/*Author: Bachar Wehbi
 *
 *This is a simple code to compute the connectivity of random graphs (simulating
 *an ad hoc networks). the node density, network size, and cooperation level of
nodes
 *are considered. note that cooperation means the ability of a node to have
children;
 *in other words to reply for RREQ messages if we consider AODV case!
 *
 *the considered scenario consists of a square area where are inserted the nodes
and
 *an "access point" (connection range = 100m) located at the center of the
network.
 *all obtained results are relative to the "access point";
 *per example: the connectivity ratio reflects the proportion of nodes that are
connected
 *to the access point! the same for the "hop count" that indicates the nb of
hops
 *seperating a node from the access point.
 *
 *This hypothesus can be relaxed by a slight modification of the code to perform
a
 *loop to compute all the parameters for all the node! I will try to make it
some day :-)
 *
 *to run the program type: "./executable_name nb_of_repetition log_file1
log_file2"
 *where nb_of_repetition indicates how many times you want the programm to
repeat
 *the process this helps to overcome the random nature of graph generation
 *log_file1 and log_file2 are two files where are stocked the test resuls
 *log_file1 contains the following information for distances the unit is the
connection range)
 *network width; number of nodes; density of the network; cooperation level as
percentage
 *mean number of hops distance; mean number of neighbors; and hops rate.
 *the last information is as follows: first is represented the percentage of
disconnected
 *nodes, second percentage of nodes that are one hop away from the ccess point,
then the
 *percentage of nodes that are two hops away from the access point ect. until we
arrive to
 *the max_hops_nb value! (all the nodes that are more than max_hops_nb away from
the access
 *point are considered as disconnected from the network!!!
 *
 *please contact "bachar dot wehbi at int dash evry dot fr" to report a problem
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <unistd.h>

int main(int argc, char *argv[])
{

  const length_steps=20, coop_steps=5;
  int test_type, min_size, max_size, min_coop, max_coop=100, max_hops_nb=4,
network_size, nodes_nb, cooperation;
  float density_steps=0.25, network_density,min_density, max_density;
  int connected(int,int,int,int);
  void network_construction(int,int,int,int,int,char *, char *);

  int test_repetition_times=atoi(argv[1]);

  printf("choose what test to perform:\n");
  printf("\tfor connection if function of density and network size press 1\n");
  printf("\tfor connection if function of density and cooperation level press 2
(network size is supposed cte)\n");
  printf("\tfor connection if function of network size and cooperation level
press 3\n");

  scanf("%d",&test_type);

  if(test_type==1)
    {
      printf("enter the minimal density: ");
      scanf("%f",&min_density);
      printf("enter the maximal density: ");
      scanf("%f",&max_density);
      printf("enter the minimal network size: ");
      scanf("%d",&min_size);
      printf("enter the maximal network size: ");
      scanf("%d",&max_size);
    }
  else
    {
      if(test_type==2)
	{
	  printf("enter the minimal density: ");
	  scanf("%f",&min_density);
	  printf("enter the maximal density: ");
	  scanf("%f",&max_density);
	  printf("enter the minimal cooperation level: ");
	  scanf("%d",&min_coop);
	  printf("enter the maximal cooperation level: ");
	  scanf("%d",&max_coop);
	  printf("enter the network size: ");
	  scanf("%d",&max_size);
	}
      else
	{
	  if(test_type==3)
	    {
	      printf("enter the minimal network size: ");
	      scanf("%d",&min_size);
	      printf("enter the maximal network size: ");
	      scanf("%d",&max_size);
	      printf("enter the minimal cooperation level: ");
	      scanf("%d",&min_coop);
	      printf("enter the maximal cooperation level: ");
	      scanf("%d",&max_coop);
	      printf("enter the density: ");
	      scanf("%f",&max_density);
	    }
	}
    }
  if(test_type==1)
    {
     
for(network_size=min_size;network_size<=max_size;network_size=network_size+length_steps)
	{
	  printf("actual phase : %d\n",network_size);

for(network_density=min_density;network_density<=max_density;network_density=network_density+density_steps)
	    {
	      nodes_nb=network_density*network_size*network_size/(10000);
	      network_construction(nodes_nb, network_size, max_coop, max_hops_nb,
test_repetition_times, argv[2], argv[3]);
	    }
	}
    }
  else
    {
      if(test_type==2)
	{
	 
for(cooperation=min_coop;cooperation<=max_coop;cooperation=cooperation+coop_steps)
	    {
	      printf("actual phase : %d\n",cooperation);

for(network_density=min_density;network_density<=max_density;network_density=network_density+density_steps)
		{
		  nodes_nb=network_density*max_size*max_size/(10000);
		  network_construction(nodes_nb, max_size, cooperation, max_hops_nb,
test_repetition_times, argv[2], argv[3]);
		}
	    }
	}
      else
	{
	  if(test_type==3)
	    {
	     
for(network_size=min_size;network_size<=max_size;network_size=network_size+length_steps)
		{
		  printf("actual phase : %d\n",network_size);
		  nodes_nb=max_density*network_size*network_size/(10000);

for(cooperation=min_coop;cooperation<=max_coop;cooperation=cooperation+coop_steps)
		    {
		      network_construction(nodes_nb, network_size, cooperation, max_hops_nb,
test_repetition_times, argv[2], argv[3]);
		    }
		}
	    }
	}
    }
}

int connected(int a,int b,int c,int d)
{
  int distance;
  distance = (a-c)*(a-c)+(b-d)*(b-d);
  if (distance<=10000)
    return 1;
  else
    return 0;
}

void network_construction(int nb_nodes,int square_length,int
cooperation_level,int max_hops, int test_repetition,char *name1, char *name2)
{

  const connection_limit=100;

  int test_cnt, i, j, r, min=max_hops, chosen_node;
  float hops_rate[max_hops];
  float length_rate, nodes_rate, mean_hops=0, mean_neighbors=0, relayed_nb=0;

  FILE *file1=fopen(name1,"a");
  FILE *file2=fopen(name2,"a");

  struct AP {
    int x_pos, y_pos;
  }AP;

  typedef struct node {
    int x_pos, y_pos;
    int coop;
    int nb_hops;
    int visite;
  }node;

  node nodes[nb_nodes];

  struct timeval  start_time;

  /*the access point is placed at the
    middle of the square*/

  AP.x_pos=square_length/2;
  AP.y_pos=square_length/2;

  for(i=0;i<max_hops;i++)
    {
      hops_rate[i]=0;
    }

  for(test_cnt=0;test_cnt<test_repetition;test_cnt++)
    {
      gettimeofday(&start_time,NULL);
      srand(start_time.tv_usec);
      sleep(0.000007);

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

	  /*network initialization*/

	  nodes[i].x_pos = rand() % square_length;
	  nodes[i].y_pos = rand() % square_length;
	  //	  printf("node:%d  x=%d y=%d\n", i,nodes[i].x_pos, nodes[i].y_pos);
	  r=rand()%100;

	  if (r>=cooperation_level)
	    nodes[i].coop=0;//non cooperation
	  else
	    nodes[i].coop=1;//cooperation

	  nodes[i].nb_hops=max_hops;
	  nodes[i].visite=0;//not visited
	}

      /*end of network initialization*/

      /*construction of the network graph
	only the route to the access point is considered
	so the graph represents a tree with the AP as root
	just to note that non cooperated nodes will not serve
	as relays for farther nodes, they can only be leafs
	in the tree*/

      for(i=0;i<nb_nodes;i++)
	{
	  if (connected(AP.x_pos, AP.y_pos, nodes[i].x_pos, nodes[i].y_pos)==1)
	    {
	      nodes[i].nb_hops=1;
	      mean_neighbors=mean_neighbors+1;
	      //printf("nb hops for node %d = %d\n",i,nodes[i].nb_hops);
	    }
	}
      for(i=0;i<nb_nodes;i++)
	{
	  for (j=0;j<nb_nodes;j++)
	    {
	      if(nodes[j].nb_hops<min && nodes[j].visite==0 && nodes[j].coop==1)
		{
		  min=nodes[j].nb_hops;
		  chosen_node=j;
		}
	    }
	  min=max_hops;
	  nodes[chosen_node].visite=1;
	  if(nodes[chosen_node].nb_hops<max_hops)
	    {
	      for (j=0;j<nb_nodes;j++)
		{
		  if(connected(nodes[chosen_node].x_pos, nodes[chosen_node].y_pos,
nodes[j].x_pos, nodes[j].y_pos)==1)
		    {
		      if(nodes[j].nb_hops>nodes[chosen_node].nb_hops)
			{
			  nodes[j].nb_hops=nodes[chosen_node].nb_hops+1;
			}
		    }
		}
	    }
	}

      /*end of the graph construction*/
      for(j=0;j<nb_nodes;j++)
	{
	  if(nodes[j].nb_hops==max_hops)
	    {
	      hops_rate[0]=hops_rate[0]+1;
	    }
	  else
	    {
	      hops_rate[nodes[j].nb_hops]=hops_rate[nodes[j].nb_hops]+1;
	    }
	}

      for(i=0;i<nb_nodes;i++)
	{
	  for(j=0;j<nb_nodes;j++)
	    {
	      if(connected(nodes[i].x_pos, nodes[i].y_pos, nodes[j].x_pos,
nodes[j].y_pos)==1)
		mean_neighbors=mean_neighbors+1;
	    }
	}

    }

  for(i=0;i<max_hops;i++)
    {
      hops_rate[i]=hops_rate[i]*100/(nb_nodes*test_repetition);
      // printf("nb nodes with hops %d = %.2f\n",i,hops_rate[i]);
    }

  for(i=1;i<max_hops;i++)
    {
      mean_hops=mean_hops+hops_rate[i]*i;
    }

  mean_hops=mean_hops/(100-hops_rate[0]);
  mean_neighbors=mean_neighbors/(nb_nodes*test_repetition);

  length_rate = square_length;
  length_rate = length_rate/connection_limit;
  nodes_rate = nb_nodes;
  nodes_rate = nodes_rate/(length_rate*length_rate);

fprintf(file1,"\n%.2f\t%d\t%.2f\t%d\t",length_rate,nb_nodes,nodes_rate,cooperation_level);
  fprintf(file1,"%.2f\t%.2f\t",mean_hops,mean_neighbors);
  for(i=0;i<max_hops;i++)
    {
      fprintf(file1,"%.2f\t",hops_rate[i]);
    }
 
fprintf(file2,"\n%.2f\t%.2f\t%d\t%.2f\t%.2f\t",length_rate,nodes_rate,cooperation_level,mean_hops,mean_neighbors);

  for(i=2;i<max_hops;i++)
    {
      if(hops_rate[i]!=0)
	{
	  for(j=i;j<max_hops;j++)
	    {
	      relayed_nb=relayed_nb+hops_rate[j];
	    }
	  relayed_nb=relayed_nb*100/(hops_rate[i-1]*cooperation_level);
	 
fprintf(file2,"%.2f\t%.2f\t",relayed_nb,hops_rate[i]*100/(hops_rate[i-1]*cooperation_level));
	  relayed_nb=0;
	}
    }

  fclose(file1);
  fclose(file2);

}

/************************************************************************/

>      Thanks, waiting for reply!

----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.

---

From: "Gabi Kliot" <[email-masked]>
Date: Sun, 30 Apr 2006 17:43:51 +0200

Hi

average node degree:

d_avg = phi*r^2*n/a^2

r is the transmission range

a is the field length/width.

n is the number of nodes.

Regards,

Gabi

-----Original Message-----
From: zhang zhi [mailto:[email-masked]] 
Sent: Sunday, April 30, 2006 10:38 AM
To: [email-masked]
Subject: [manet] How to calculate the average node degree and the averagehop
count?

Hi ,all
 
Zhangzhi

---

From: Brown Tim <[email-masked]>
Date: Sun, 30 Apr 2006 09:16:58 -0600 (MDT)

The formula below is an upper bound since it does not take into account
edge effects. Also n should be replaced with n-1. For a lower bound
use:
d_avg > (pi*r^2*(n-1)/a^2)*(1-2*r/a)^2

	Regards,
		Tim

>      Thanks, waiting for reply!

Timothy X Brown
Interdisciplinary Telecommunications
Electrical and Computer Engineering
ECOT 256 Campus Box 530
University of Colorado
Boulder, CO 80309
Tel: (303) 492-1630
Fax: (303) 492-1112
http://ece.colorado.edu/~timxb