Community Company Search Contact

model.c from EmStar at Krugle

Show model.c syntax highlighted

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

#define MAX_NODES  100

struct node {
  float conn_to[MAX_NODES];
  float ETX_spent;  
  int in_use;
  int has_data;
  float cost;
  float hop_cost;
  int count;
  int prev;
  int prev_locked;
};

struct node nodes[MAX_NODES];
int queue[MAX_NODES];
int queue_len;

void enqueue(int i)
{
  queue[queue_len++] = i;
}

int dequeue()
{
  int retval = queue[0];
  if (queue_len > 0) {
    queue_len--;
    memmove(&(queue[0]), &(queue[1]), sizeof(queue)-sizeof(int));
    return retval;
  }
  return -1;
}

int main()
{
  int src,dst;
  float p;
  int i,j,k,w;
  int source;
  int node_count = 0;

  memset(nodes, 0, sizeof(nodes));
  memset(queue, 0, sizeof(queue));

  while (1) {
    int status = fscanf(stdin, "0.0.0.%d -> 0.0.0.%d : %f\n", &src, &dst, &p);
    if (status != 3) goto done;
    printf("parsed %d %d %.2f\n", src, dst, p);
    if (p == 100) p = 99;
    nodes[src].conn_to[dst] = p/100.0;
    if (!nodes[src].in_use) {
      node_count++;
      nodes[src].in_use = 1;
    }
  }

 done:

  source = 1;
  
  /****/

  float total_ETX = 0;

  /* clear paths */
  for (i=0; i<MAX_NODES; i++) {
    nodes[i].ETX_spent = 0;
    nodes[i].has_data = 0;
  }

  nodes[source].has_data = 1;

 repeat:
  
  /* bfs to find shortest path from any source node */
  queue_len=0;
  for (i=0; i<MAX_NODES; i++) {
    nodes[i].cost = 0;
    nodes[i].count = 0;
    nodes[i].prev = -1;
    if (nodes[i].has_data) {
      //printf("queueing %d\n", i);
      enqueue(i);
    }
  }
  
  while ((j = dequeue()) >= 0) {
    //printf("processing %d\n", j);
    for (k=0; k<MAX_NODES; k++) {
      /* if this node is in use and has a path and hasnt already got data */
      if (nodes[k].in_use &&
	  nodes[k].has_data == 0 &&
	  j != k &&
	  nodes[j].conn_to[k] > 0 &&
	  nodes[k].conn_to[j] > 0) {

	//printf("checking hop from %d to %d\n", j, k);
	
	/* compute the new ETX cost of this hop */
	float hop_cost = nodes[k].conn_to[j];
	float min_prob = nodes[j].conn_to[k];

	for (w = 0; w < MAX_NODES; w++) {
	  if (nodes[w].prev_locked == j) {
	    if (nodes[j].conn_to[w] < min_prob)
	      min_prob = nodes[j].conn_to[w];
	    hop_cost *= nodes[w].conn_to[j];
	  }
	}
	hop_cost *= min_prob;
	hop_cost = 1.0 / hop_cost;

	//printf("hop cost of %d->%d is %.2f (spent %.2f already)\n", j, k, hop_cost, nodes[j].ETX_spent);
	
	hop_cost -= nodes[j].ETX_spent;
	if (hop_cost < 0) hop_cost = 0;
	
	/* is cost lower, or the same and higher count, or no count yet? */
	float cost = nodes[j].cost + hop_cost;
	int count = nodes[j].count+1;
	
	if (cost < nodes[k].cost || 
	    nodes[k].cost == 0 ||
	    (cost == nodes[k].cost &&
	     count > nodes[k].count)) {
	  nodes[k].count = count;
	  nodes[k].cost = cost;
	  nodes[k].prev = j;
	  nodes[k].hop_cost = hop_cost;
	  enqueue(k);
	}
      }
    }
  }
  
  /* locate least expensive node to reach */
  float max_cost = 0;
  int max_ind = -1;
  for (i=0; i<MAX_NODES; i++)
    if (nodes[i].in_use &&
	!nodes[i].has_data && 
	nodes[i].prev >= 0) {
      if (max_ind < 0 ||
	  nodes[i].cost > max_cost) {
	max_ind = i;
	max_cost = nodes[i].cost;
      }
    }
  
  if (max_ind < 0) {
    printf("DONE\n%d nodes, Total ETX=%.2f\n", node_count, total_ETX);
    return 0;
  }

  /* lock down min path */
  printf("min path: ");
  for (i=max_ind; !nodes[i].has_data; i = nodes[i].prev) {
    total_ETX += nodes[i].hop_cost;
    nodes[nodes[i].prev].ETX_spent += nodes[i].hop_cost;
    nodes[i].prev_locked = nodes[i].prev;
    printf("%d(%.2f)->", i, nodes[i].hop_cost);
    nodes[i].has_data = 1;    
  }
  printf("%d, total=%.2f\n", i, total_ETX);

  goto repeat;

  return 0;
}

See more files for this project here

EmStar

EmStar is a software system for developing and deploying wireless sensor networks involving Linux-based platforms. As the wireless sensor network community has attempted to deploy more complex designs---large-scale, long-lived systems that need self-organization and adaptivity---a number of difficult software design issues have arisen. Advances in software design have not kept pace with the capabilities of hardware. This is because designing for an adaptive, efficient, and useful sensor network has turned out to be surprisingly complex and difficult. EmStar is a Linux-based software framework, whose goal is to dramatically reduce this complexity, enabling work to be shared and reused, and simplifying and speeding the design of new sensor network applications.

Project homepage: http://cvs.cens.ucla.edu/emstar/
Programming language(s): C,Shell Script
License: other

  buildmodel.pl
  model.c
  pub.c
  retx_proto_test.c
  send_rr.c
  sub.c