simulate_topology.m

best routing protocol

function [D, coord, n_blocked] = simulate_topology(n, len, width, radio_range, ...
				obstacles)
% function [D, coord] = simulate_topology(n, len, width)
% randomly generate points in a 2D plane
% return a connectivity matrix
% if the distance between two nodes are within radio_range(1), they are
% connected
% obstacles: cells of obstacles. obstacles{n}(1,1): first pt.x;
% obstacles{n}(1,2) first pt.y; second pt x(2,1), y (2,2)
% n_blocked: number of links that are blocked by obstacles
if nargin<4
  radio_range=1;
end

if nargin<3
  width=len;
end

if nargin<5
  obstacles={};
end

fprintf('generating random topology\n');
coord = rand(n,2).* repmat([len, width], n,1);

n_blocked = 0;

D = sparse([]);
D(n,n) = 0;

for i=1:n-1
%  if mod(i,2000)==0
%    i
%  end
  
  connected = euclidean_distance(coord(i,:),coord(i+1:n,:))<=radio_range;
  
  D(i,i+1:n) = connected;
  D(i+1:n,i) = connected';
end

%check with the obstacles
fprintf('updating topology due to obstacles\n');
if length(obstacles)>0
  [from to]=find(D);
  for i=1:length(obstacles)
	ob = obstacles{i};
	for j=1:length(from)
	  if is_cross(coord(from(j),:), coord(to(j),:), ob(1,:), ob(2,:))
		D(from(j),to(j))=0;
		n_blocked = n_blocked + 1;
	  end
	  
	end
  end
end

% check out the overhead
out_degree = full(sum(D>0,1));
m = sum(out_degree); % m is the total number of edges(considered
                     % directed graph)
fprintf('mean and max out_degree:%.1f, %.1f\n', mean(out_degree), ...
	max(out_degree));
fprintf('# of edges:%d\n',m);
return

%%%%%%slower version%%%derecated
D = zeros(n,n);
dist = euclidean_distance(coord, coord);
D(:,:) = dist<=radio_range;
D = sparse(D);
%idx = find(D==0);
%D(idx) = repmat(Inf, length(idx), 1);
for i=1:n
  D(i,i)=0;
end

%D = dist_full2sparse(D);