cr_bf.m

best routing protocol

						 routing_nexthop(:, A) = optimal_nexthop(:, A); % routes to
												% landmarks are optimal
  for src = 1:n
    routing_nexthop(src, src) = src; %route to itself
    dest = src;
    routing_nexthop(A(cent(dest)),dest) = optimal_nexthop(A(cent(dest)),dest);
  end
  optimal_mask = C | (neighbor_dist>0); %routing within the cluster
                                        %and routing within
                                        %neighborhood is optimal
  routing_nexthop = optimal_nexthop.*optimal_mask + ...
      routing_nexthop.*(1-optimal_mask); % if C(src,dest)==1, next hop is the optimal one
end
routing_load = zeros(n,1);
routing_dist = zeros(length(test_pairs), 1);

for count = 1:length(test_pairs)
  src = test_pairs(count,1);
  dest = test_pairs(count,2); %@!@@@!!!!

%fprintf(1,'src %d, dest %d\n',src,dest);

%{
  [routing_path, routing_dist(count), routing_table, direct_dist] = cr_routing(src, ...
	dest, cent, A, debug_route, beacon_vectors, neighbor_dist, ...
        routing_table, nexthop2bcn, isbeacon, tlabel{dest},reactive, ...
						  deltaA,direct_dist, ...
						  failure_nodes);
%}
  [routing_path, routing_dist(count), direct_dist] = cr_bf_routing(src, ...
	dest, cent, A, debug_route, beacon_vectors, neighbor_dist, ...
        p, coe1, coe2, rbf, rtb, reactive, ...
						  deltaA,direct_dist, ...
						  failure_nodes);
  routing_load(routing_path)=  routing_load(routing_path)+1;
end

% check out the overhead
cluster = full(sum(routing_table>0,2));
if debug
  fprintf('mean and max cluster size:%.1f, %.1f\n', mean(cluster), ...
	  max(cluster));
  %[tmp idx] = max(cluster);
  %deltaA(idx)
  %beacon_vectors(idx,:)
  if n<100
    fprintf('cluster size for each node:');
    cluster'
    fprintf('total cluster size:%d\n',sum(cluster));
  end
end


function [routing_path, routing_dist, routing_table, direct_dist] =cr_routing(src, ...
	dest, cent, A, debug_route, beacon_vectors, neighbor_dist, ...
	  routing_table, nexthop2bcn, isbeacon, label, reactive, ...
	  deltaA, direct_dist, failure_nodes)
routing_path = [src];
routing_dist = 0;
hops =1;
if src==dest
  routing_dist = 0;
  return
end
k=5;
header = zeros(k,3); %packet annotation: k1 node's info:
                     %format(id,range,dist) range+dist==deltaA(id)
cent_dest = A(cent(dest)); %the closest landmark to dest
if debug_route
  fprintf('%d->%d:', src, dest);
end
  
if beacon_vectors(dest, cent(dest))==Inf | beacon_vectors(src, ...
						  cent(dest))==Inf
  %not reachable
  routing_dist = Inf;
  fprintf('unreachable\n');
  return
end
curr = src;
prev = -1;
passed_beacon = 0;
est_dist = Inf; %estimated distance to the destination

while curr~=dest
  tmpid = [];
  redirected_by_bcn = 0;
  if reactive & length(label)>0
    tmpid = find(label==curr);
  end
  
  if neighbor_dist(curr, dest)>0;
    next = dest;
    est_dist = 1;
    if debug_route
      fprintf('->n%d[1]', next);
    end
  elseif routing_table(curr,dest)>0
    next = routing_table(curr, dest);
    est_dist = direct_dist(curr, dest);
    if debug_route
      fprintf('->c%d[%d]', next,direct_dist(curr,dest));
      if direct_dist(curr,dest)<=0
	fprintf('??????');
      end
    end
  elseif isbeacon(dest)
    next = nexthop2bcn(curr,isbeacon(dest));
    est_dist = beacon_vectors(curr,isbeacon(dest));
    if debug_route
      fprintf('->B%d[%d]', next, beacon_vectors(curr,isbeacon(dest)));
    end
  elseif curr ==cent_dest
    next = label(1);
    redirected_by_bcn = 1;
    passed_beacon = 1;
    est_dist = deltaA(dest);
    if debug_route
      fprintf('->L%d[%d]', next, deltaA(dest));
    end
  elseif reactive & length(tmpid)==1
    next = label(tmpid+1);
    est_dist = length(label)-tmpid+1;
    if debug_route
      fprintf('->LL%d[?]', next);
    end
  else
    next = nexthop2bcn(curr, cent(dest));
    est_dist = deltaA(dest)+beacon_vectors(curr,cent(dest));
    if debug_route
      fprintf('->b%d[[%d]]', next,deltaA(dest)+beacon_vectors(curr,cent(dest)));
    end
  end
  hops = hops +1;
  routing_path(hops) = next;
  routing_dist = routing_dist+neighbor_dist(curr, next);
  
  if reactive 
    if redirected_by_bcn
      if header(k,2)>0
	error('something impossible happened');
      end
      %clear all headers anyway -- path may not be optimal
      header(:,1) = zeros(k,1);
    end
    %update the header
    if deltaA(curr)>neighbor_dist(curr, next)
      header(1,:) = [curr deltaA(curr) 0]; 
    end
    header(:,2) = header(:,2)-neighbor_dist(curr, next);
    header(:,3) = header(:,3)+neighbor_dist(curr, next);
    %expired_idx = find(header(:,2)<=0); 
    %expired_idx = find(header(:,2)<0); %!!!not compact routing
    %header(expired_idx,1) = zeros(length(expired_idx), 1);
    [tmp idx] = sort(header(:,2));
    header = header(idx,:);
  
  end
  prev = curr;
  curr = next;
  %the actual packet got transmitted here to the next hop
  
  if reactive%upon receiving the packet, update routing table
    in_cluster_id = find(header(:,2)>=0 & header(:,1)>0); %!!>= is
                                                          %not
                                                          %exactly CR
    %in_cluster_id = find(header(:,2)>0 & header(:,1)>0);
    l = length(in_cluster_id);
    if l>0
    %if 0 %!!!!!!!!!!!!!!!
      routing_table(curr, header(in_cluster_id,1)) = ...
 	  repmat(prev, 1, l);
      direct_dist(curr, header(in_cluster_id,1)) = header(in_cluster_id,3)';
%      if debug_route
      if 0
	fprintf('updating routing table of %d: nexthop:%d,dests:',curr, ...
		routing_path(hops-1));
	header(in_cluster_id,1)
      end
      
    end
  end  
end
if debug_route
  fprintf('\n');
end


function S = sample(W, s)
%return a random subset of W by selecting each element,
%independently with probability s/|W|

n = length(W);
if n<=s
  S = W;
  return
end
idx = find(rand(1,n) < s/n);
S = W(idx);
return

function [b_snd, b_rcv, nexthop,label,d_dist] = BFS(start_node, range, neighbor_dist, ...
			       min_dist, cent)
% 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
% min_dist: the minimal distance that two nodes could possibly be,
% 1 if it's hop count, must be >=0
% b_snd: how many broadcast packets are sent
% b_rcv: how many broadcast packets are received
% nexthop(i): to start_node
% cent: closest beacon to start_node
% label: =nexthop(cent,start_node)
% d_dist(i): distance between i and start_node if i is in routing_table
label = 0;
queue = [[start_node, range, 0]];
b_snd = 0;
b_rcv = 0;
nexthop = sparse([]);
n = length(neighbor_dist);
nexthop(n) = 0;
d_dist = nexthop;
if range<=min_dist
  return
end


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;
  b_rcv = b_rcv + length(neighbors); % all neighbors will hear it
  for i=1:length(neighbors)
    dst = neighbors(i);
    if dst==node
      continue
    elseif dst==cent
      label = node;
    end
    if range-neighbor_dist(node, dst)<min_dist
      continue
    end
    if dist+neighbor_dist(node,dst)<shortest_dist(dst)
      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
idx = find(shortest_dist<Inf);
d_dist(idx) = shortest_dist(idx);
%fprintf('\n');