bfs2.m

best routing protocol

function [b_snd, b_rcv, nexthop,label] = BFS2(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)
label = 0;
queue = [start_node];
b_snd = 0;
b_rcv = 0;
nexthop = sparse([]);
if range<=min_dist
  return
end

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);

seen = queue;
for i = min_dist:range
  b_snd = b_snd + length(queue);
  [neighbors, ignore] = find(neighbor_dist(queue,:)');
  b_rcv = b_rcv + length(neighbors);
  neighbors = unique(neighbors);
  if (length(find(neighbors == cent)) == 1)
    % intersect cent's neighbors and current nodes in queue
    % all the nodes in label_set can be label since they can all reach cent in one hop
    label_set = intersect(find(neighbor_dist(cent,:)), queue);
    label = label_set(1);
  end
  prev_queue = queue;
  queue = setdiff(neighbors, seen);
  for j = 1:length(queue)
    node = queue(j);
    if length(prev_queue) == 1
      nexthop(node) = prev_queue(1);
    else  
      prevhops = intersect(find(neighbor_dist(node,:)), prev_queue);
      nexthop(node) = prevhops(1);
    end  
  end
  seen = [seen; queue];
end

%fprintf('\n\n\n');

% [dist, nexthop] = allpair_dijkstra(neighbor_dist, start_node);