study_cr_bf.m

best routing protocol

function study_cr_bf(n_nodes, density, n_beacons)
% study compact routing
% randomly generated topology, density = # of nodes per unit area
run_bvr = 0;
run_optimal = 1;
show_all_figures = 1;
DEFAULT_NODE_NO = 3200;

if nargin<1
  n_nodes = DEFAULT_NODE_NO; %this is what is used in the BVR paper
  density = 5.12;
end

if nargin<3
  n_beacons = ceil(sqrt(n_nodes));
end
n_random_pairs = min(ceil(n_nodes*n_nodes/2),DEFAULT_NODE_NO*10);
k = min(n_beacons, 10); %routing beacon for bvr

if nargin<1
  n_random_pairs = DEFAULT_NODE_NO*10;
  k = 10;
end

fprintf(['# of nodes:%d, density: %.2f, # of test pairs: %d\n# of' ...
	 ' beacons: %d, # of routing beacons: %d\n'], n_nodes, density, ...
	 n_random_pairs, n_beacons, k);

rand('state',100*(sum(clock)+cputime));

width = sqrt(n_nodes/density);
[D coord] = simulate_topology(n_nodes, width, width);
%[optimal_dist optimal_nexthop] = floyd_warshall(D);
if run_optimal
  [optimal_dist optimal_nexthop] = allpair_dijkstra(D);
else
  optimal_dist = [];
  optimal_nexthop = [];
end



tmp = randperm(n_nodes);
beacons = tmp(1:n_beacons);

t = sprintf( '%d nodes with density %.2f', n_nodes, ...
	     density);
%{
if n_nodes<=200 & show_all_figures
  figure(1);
  visualize(D, coord, beacons);
  title(t);
else
  fprintf('n_nodes>100, omit visualization\n');
end
%}

random_pairs = ceil(rand(n_random_pairs, 2)*n_nodes);

%[routing_path, routing_hops, routing_dist_bvr, load_bvr]=bvr(D, n_beacons, ...
%	 ceil(n_beacons/2), beacons);
if run_bvr
  [routing_path, routing_dist_bvr, load_bvr, storage_bvr, dht_bvr, failure_bvr]=bvr(D, n_beacons, ...
	k , beacons, random_pairs, 1);
  [routing_path, routing_dist_bvr2, load_bvr2, storage_bvr2, dht_bvr2, failure_bvr2]=bvr(D, n_beacons, ...
	k , beacons, random_pairs, 0);
else
  load_bvr = 0;load_bvr2=0;
  dht_bvr = -1; dht_bvr2 = -1;
end
[routing_dist_cr, load_cr,storage_cr, dht_cr, cluster_cr] = ...
    compactrouting(D, beacons, random_pairs,[], 0);%default, proactive one

%{
[routing_dist_cr2, load_cr2,storage_cr2, dht_cr2, cluster_cr2] = ...
    compactrouting(D, beacons, random_pairs,[], 1); %reactive
%}

[routing_dist_cr2, load_cr2,storage_cr2, dht_cr2, cluster_cr2] = ...
    cr_bf(D, beacons, random_pairs,[], 0);%default, proactive one

%fprintf('calculating routing distance..\n');
%[routing_dist_cr, pairhop] = routing_distance(D, nexthop_cr);
%[routing_dist_cr, pairhop] = routing_distance(D, nexthop_cr, random_pairs);

if run_optimal
  pair_indices = random_pairs(:,1)+(random_pairs(:,2)-1)*n_nodes;
  optimal_dist = optimal_dist(pair_indices);
else
  %nothing
end


%[routing_dist_bvr routing_dist_cr optimal_dist]
if show_all_figures
  figure(2);
  hold on
  plot_routing_stretch(routing_dist_cr,optimal_dist,'g');
  plot_routing_stretch(routing_dist_cr2,optimal_dist,'r.');
  if run_bvr
    plot_routing_stretch(routing_dist_bvr,optimal_dist,'b');
    plot_routing_stretch(routing_dist_bvr2,optimal_dist,'b.');
  end

  xlim([1 3.1])
  xlabel('routing stretch');
  ylabel('CDF');
  if run_bvr
    legend('cr','cr reactive','bvr','bvr edist',0);
  else
    %legend('cr','cr reactive', 0);
    legend('cr','cr bloom filter', 0);
  end
  
  title(t);
end

if show_all_figures
  figure(3);
  hold on
  plot_abs_error(routing_dist_cr, optimal_dist,'g');
  plot_abs_error(routing_dist_cr2, optimal_dist,'r.');

  if run_bvr
    plot_abs_error(routing_dist_bvr, optimal_dist,'b');
    plot_abs_error(routing_dist_bvr2, optimal_dist,'b.');
  end
  ylabel('CDF');
  xlabel('abs routing error');
  if run_bvr
    legend('cr','cr reactive','bvr','bvr edist',0);
  else
    %legend('cr','cr reactive', 0);
    legend('cr','cr bloom filter', 0);
  end
  
  title(t);
  fprintf('Done.\n');
end

%%%compare routing load
if run_optimal
  load_optimal = get_nexthop_load(optimal_nexthop, random_pairs);
else
  load_optimal = zeros(length(random_pairs),1);
end

%load_cr = get_nexthop_load(nexthop_cr, random_pairs);
fprintf('==========\n');
fprintf('dht packets: cr:%d \tcr-reactive %d \tbvr %d \tbvr-edist %d\n\n', dht_cr,dht_cr2, ...
	dht_bvr,dht_bvr2);

fprintf('CR mean/max cluster size: %.1f/%d, %.1f/%d\n\n', ...
	mean(cluster_cr), max(cluster_cr), mean(cluster_cr2), ...
	max(cluster_cr2));

if run_bvr
  fprintf('BVR failure rate: %.2f%%, %.2f%%\n\n', failure_bvr*100, failure_bvr2*100);
end
mmmm(storage_cr,'storage cr',1);
mmmm(storage_cr2,'storage cr-2',0);
if run_bvr
  mmmm(storage_bvr,'storage bvr',0);
  mmmm(storage_bvr2,'storage bvr-edist',0);
end
fprintf('\n');


mmmm(load_cr,'load cr',0);
mmmm(load_cr2,'load cr-2',0);
if run_bvr
  mmmm(load_bvr,'load bvr',0);
  mmmm(load_bvr2,'load bvr-edist',0);
end
if run_optimal
  mmmm(load_optimal,'load opt',0);
end

%fprintf('max load: optimal, cr, bvr = %d,%d,%d\n',max(load_optimal), ...
%	max(load_cr),max(load_bvr));
%fprintf('mean load: optimal, cr, bvr = %.2f,%.2f,%.2f\n',mean(load_optimal), ...
%	mean(load_cr),mean(load_bvr));
if show_all_figures
  figure(4);
  plot_cumu_matrix(load_optimal,'k');
  hold on
  plot_cumu_matrix(load_cr,'g');
  plot_cumu_matrix(load_cr2,'r.');
  if run_bvr
    plot_cumu_matrix(load_bvr,'b');
    plot_cumu_matrix(load_bvr2,'b.');
  end
  %legend('optimal','cr','cr reactive','bvr','bvr edist',0);
  legend('optimal','cr','cr bloom filter','bvr','bvr edist',0);
  title(t);
  ylabel('CDF');
  xlabel('node load');
end

function mmmm(m, str, header)
%print mean, max, min, median
m = m(:);
if header
  fprintf('%20s\tmean \t max \t min \t median\n','');
end
fprintf('%20s\t%.1f \t %.1f \t %.1f \t %.1f\n', str, mean(m),max(m), ...
	min(m),median(m));
return
  
function routing_load = get_nexthop_load(routing_nexthop, ...
					 test_pairs)
N = length(routing_nexthop);
if nargin<2 | length(test_pairs)==0
  p = 0;
  fromloop = 1:N;
else
  [p, tmp] = size(test_pairs);
  fromloop = test_pairs(:,1)';
end
routing_load = zeros(N,1);
count = 0;
for from = fromloop
  if p==0
    toloop = 1:N;
  else
    toloop = test_pairs(count+1,2);
  end
  
  for to=toloop
    count = count +1;
    next = from;
    tmp = 0;
    seen_nodes = zeros(N,1);
    routing_load(from) = routing_load(from)+1;
    while next~=to 
      previous = next;
      next = routing_nexthop(next, to);
      %if sum(ismember(current_nodes, next))>0
      if next<0 
	fprintf('DEAD loop\n');
	%print_route(routing_nexthop, from, to);
	break
      end
      if seen_nodes(next)
	fprintf('DEAD loop\n');
	%print_route(routing_nexthop, from, to);
	break
      end
      seen_nodes(next) = 1;
      routing_load(next) = routing_load(next)+1;
    end
  end
end