bfs.m

best routing protocol

function [b_snd, b_rcv, nexthop,label] = 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)
label = 0;
queue = [[start_node, range, 0]];
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);
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 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;
      if range-neighbor_dist(node, dst)<min_dist
	continue
      end
      [l,tmp] = size(queue);
      queue(l+1,:) = [dst, range-neighbor_dist(node, dst),dist+ ...
		      neighbor_dist(node,dst)];
    end
    if range-neighbor_dist(node, dst)<min_dist
      continue
    end
  end
end
%fprintf('\n');