tree.m

best routing protocol

function tree(n_nodes, density)
%study how many broadcasting trees can cover the whole graph
width = sqrt(n_nodes/density);
[D coord] = simulate_topology(n_nodes, width, width);
missing_edges = find(D);
n_missing_edge = [length(missing_edges)];
for i=1:n_nodes
  if mod(i,100)==0
    i
  end
  
  t = BFS(i, Inf, D);
  missing_edges = setdiff( missing_edges, find(t));
  n_missing_edge(i+1) = length(missing_edges)/2;
  if length(missing_edges)==0
    fprintf('last i:%d\n',i);
    break
  end
end

plot(n_missing_edge)
t = sprintf( '%d nodes with density %.2f', n_nodes, ...
	     density);
title(t);
ylabel('missing edges');
xlabel('number of trees');
return


function [tree_topology] = BFS(start_node, range, neighbor_dist)
% use breadth first search to simulate broadcasting a packet from a
% node within certain range
% BFS is more realistic than DFS because the nature of broadcasting
tree_topology = sparse([]);
label = 0;
queue = [[start_node, range, 0]];
b_snd = 0;
b_rcv = 0;
nexthop = sparse([]);

n = length(neighbor_dist);
nexthop(n) = 0;
shortest_dist = repmat(Inf, 1, n); % the initial shortest distance to node
shortest_dist(start_node) = 0; %except to itself
%fprintf('start brdcst(cent%d):',cent);
while length(queue)>0
  %dequeue
  current = queue(1,:);
  node = current(1); range = current(2); dist = current(3);
  [l,tmp] = size(queue);
  queue = queue(2:l,:);

  %fprintf('->%d',node);
  
  %broadcast on current node
  neighbors = find(neighbor_dist(node,:));
  b_snd = b_snd + 1;
  ll = length(neighbors);
  b_rcv = b_rcv + ll; % all neighbors will hear it
  for i=1:length(neighbors)
    dst = neighbors(i);
    if dist+neighbor_dist(node,dst)<shortest_dist(dst)
      tree_topology(node, dst) = 1;
      tree_topology(dst, node) = 1;
      
      shortest_dist(dst) = dist+neighbor_dist(node,dst);
%      fprintf('%d->%d---->%d\n',dst, node, start_node);
      nexthop(dst) = node;
      [l,tmp] = size(queue);
      queue(l+1,:) = [dst, range-neighbor_dist(node, dst),dist+ ...
		      neighbor_dist(node,dst)];
    end
  end
end
%fprintf('\n');